Jr. Beveridge et Em. Riseman, HOW EASY IS MATCHING 2D LINE MODELS USING LOCAL SEARCH, IEEE transactions on pattern analysis and machine intelligence, 19(6), 1997, pp. 564-579
Local search is a well established and highly effective method for sol
ving complex combinatorial optimization problems. Here, local search i
s adapted to solve difficult geometric matching problems. Matching is
posed as the problem of finding the optimal many-to-many correspondenc
e mapping between a line segment model and image line segments. Image
data is assumed to be fragmented, noisy, and cluttered. The algorithms
presented have been used for robot navigation, photo interpretation,
and scene understanding. This paper explores how local search performs
as model complexity increases, image clutter increases, and additiona
l model instances are added to the image data. Expected run-times to f
ind optimal matches with 95 percent confidence are determined for 48 d
istinct problems involving six models. Nonlinear regression is used to
estimate run-time growth as a function of problem size. Both polynomi
al and exponential growth models are fit to the run-time data. For pro
blems with random clutter, the polynomial model fits better and growth
is comparable to that for tree search. Far problems involving symmetr
ic models and multiple model instances, where tree search is exponenti
al, the polynomial growth model is superior to the exponential growth
model for one search; algorithm and comparable for another.