Statistical Analysis of Quadratic Problems in Computer Vision

Ph.D. Thesis YORAM LEEDAN


Abstract

Quadratic forms appear in many computer vision applications. Geometry constraints between matched points in 2-D images and projection of 3-D circular shapes give rise to second order models with respect to the point coordinates. The classical, ordinary least squares (OLS) estimation technique has been widely used to solve such problems but OLS is optimal only under very strict conditions. Data extracted from real images, however most often has a non-normal distribution, and preprocessing, such as edge detection, can introduce gross-errors and ill-conditioned properties in the data. In these practical situations, the OLS based estimators become inefficient and highly biased. In order to attain near optimal results, most current computer vision techniques incorporate heuristics without completely considering statistical aspects of the problem. We propose the use of the errors-in-variables (EIV) class of models to represent the image understanding tasks, and the numerically stable generalized-total-least-squares (GTLS) estimation technique to solve them. A distinction between parameter fitting and data correction is made and discussed separately. A linearized model of the quadratic form is used and analyzed with respect to the EIV model. Drawbacks of current linearization methods, which are known to have poor performance, are explained and a new algorithm is developed. It is shown that all the accepted methods for the estimation of quadratic problems are, in fact, an approximation of the technique derived from the linearized EIV model. The new algorithm was tested on several generic image understanding problems with quadratic constraints: ellipse fitting and recovery of the epipolar geometry. The performance of the new algorithm is compared with current state-of-the-art methods for both synthetic and real data. We were able to remove the bias in the estimation of the ellipse parameters, and attained more accurate results for the estimation of the fundamental matrix which represents the epipolar geometry. The results are shown to be satisfactory for a larger range of noise levels than that of the currently available methods. The new method is general and can be applied to any linearized model with non-i.i.d. errors. The generalized SVD, used in the GTLS estimation procedure, provides a tool with better numerical behavior for solving a large class of eigenproblems appearing in many computer vision applications.

The thesis is about 7.8M compressed. When expanded becomes 23M, and has about 200 pages.


Return to Theses