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