This paper presents three new methods for regularizing the least squares solution of the reconstruction of a surface from its gradient field: firstly, the spectral regularization based on discrete generalized Fourier series (e.g., Gram Polynomials, Haar Functions, etc.); secondly, the Tikhonov regularization applied directly to the 2D domain problem; and thirdly, the regularization via constraints such as arbitrary Dirichlet boundary conditions. It is shown that the solutions to the aforementioned problems all satisfy Sylvester Equations, which leads to substantial computational gains; specifically, the solution of the Sylvester Equation is direct (non-iterative) and for an m × n surface is of the same complexity as computing an SVD of the same size, i.e., an O (n3) algorithm. In contrast, state-of-the-art algorithms are based on large-scale-linear-solvers, and use iterative techniques based on an O [n6) linear sub-step. To emphasize this improvement, it is demonstrated that the new algorithms are upwards of 104(ten-thousand) times faster than the state-of-the-art techniques incorporating regularization. In fact, the new algorithms allow for the realtime regularized reconstruction of surfaces on the order of megapixels, which is unprecedented for this computer vision problem.

This paper presents a new method for the reconstruction of a surface from its x and y gradient field, measured, for example, via Photometric Stereo. The new algorithm produces the unique discrete surface whose gradients are equal to the measured gradients in the global vertical-distance least-squares sense. We show that it has been erroneously believed that this problem has been solved before via the solution of a Poisson equation. The numerical behaviour of the algorithm allows for reliable surface reconstruction on exceedingly large scales, e.g., full digital images; moreover, the algorithm is direct, i.e., non-iterative. We demonstrate the algorithm with synthetic data as well as real data obtained via photometric stereo. The algorithm does not exhibit a low-frequency bias and is not unrealistically constrained to arbitrary boundary conditions as in previous solutions. In fact, it is the first algorithm which can reconstruct a surface of polynomial degree two or higher exactly. It is hence the first viable algorithm for online industrial inspection where real defects (as opposed to phantom defects) must be identified in a robust manner.

There is a prevalent myth in Computer Vision that the gradient weighted algebraic distance, the so-called “Sampson Error,” is a first order approximation of the distance from a point to a curve or surface. In truth, however, it is the exact geometric distance to the first order approximation of the curve. The linguistic difference is subtle, but mathematically, the two statements are at odds. In this paper, we derive the actual first order approximation of the Mahalanobis distance to a curve, a special case of which is the geometric distance. Furthermore, we show that it too, like the Sampson error, is a weighted algebraic distance. The first order distance introduces an increase in computational effort (total “flops”), which is the inevitable cost of a better approximation; however, since it too is an explicit expression, it has the same computational complexity as the Sampson error. Numerical testing shows that the first order distance performs an order of magnitude better than the Sampson error in terms of relative error with respect to the geometric and Mahalanobis distances. Our results suggest that the first order distance is an exceptional candidate cost function for approximate maximum likelihood fitting.

A new method for the non-iterative computation of a homography matrix is described. Rearrangement of the equations leads to a block partitioned sparse matrix, facilitating a residualization based on orthogonal matrix projections. This improves the handling of the error structure of the linear system of equations. The vanishing line is treated as the principal component in the estimation process. This estimate is more robust, since the position of the vanishing line depends only on the relative position and orientation of the camera to the observed plane, and is invariant to the structure of the points observed on the plane. A flop-count indicates that the new method is 11 times faster for four point correspondences, and converges to a factor of 5 for a large number of points. Furthermore, a new non-iterative method of treating error in both images is derived. Combining the forward H and reverse G projections in a suitable manner eliminates the systematic bias of the estimation, and the first order error: a strict bound on the error reduction is derived. This can be achieved faster than a classical DLT due to the improved numerical efficiency. Results of Monte-Carlo simulations are presented to verify the performance. 1

A new method to fit specific types of conics to scattered data points is introduced. Direct, specific fitting of ellipses and hyperbolæ is achieved by imposing a quadratic constraint on the conic coefficients, whereby an improved partitioning of the design matrix is devised so as to improve computational efficiency and numerical stability by eliminating redundant aspects of the fitting procedure. Fitting of parabolas is achieved by determining an orthogonal basis vector set in the Grassmannian space of quadratic conic forms. The linear combination of the basis vectors which fulfills the parabolic condition and has a minimum residual is determined using Lagrange multipliers. 1