PH.D. DISSERTATION ABSTRACT -- Henry S. Baird

Ph.D. Dissertation Abstract.

An approach to model-based image matching using only location of pattern features is described. The computer vision task of recognizing and locating rigid shapes in the plane can be posed as this search problem:

Given

two sets of feature points in the plane (a model pattern and a noisy, misregistered "instance" pattern), and worst-case constraints on pointwise noise,

find

all total matchings (mapping the model into the instance)

such that

there exists a registration (transformation of the plane combining translation, rotation, and scaling) superimposing matched points within the noise constraints.

Noise constraints are described flexibly by small but otherwise arbitrary convex polygons enclosing the feature points. Search among a potentially exponential number of matchings is pruned by testing feasibility of systems of linear inequalities. The Soviet ellipsoid algorithm is shown to be efficient for these tests. We focus on the case where there are no missing or spurious instance points. Under zero noise, only a low-order polynomial total number of matchings must be examined in the worst case, even for highly regular and symmetric patterns. For random patterns under moderate noise, the expected number of feasible partial matchings examined to find m successful matchings is proved to be O( m n ), where n is the number of points in the patterns. Monte Carlo trials, supported by a partial complexity analysis, show that the expected runtime to find one successful matching is O( n² ). In practice, for n < 100, expected runtime should appear linear in n, since less than 5% is due to non-linear effects. The approach extends to non-singular affine registrations in higher dimensions.