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^{2} ).
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.