Honours Thesis, 1995
Chris Loader
Department of Computer
Science
University of Western Australia
Recognising an object from its shape is an important yet difficult problem in Computer Vision. Typically we wish to find the location of a particular object model in a given image. All attempts at this problem involve significant computation, often in the form of a hypothesis and test or tree pruning procedure. Our approach considers recognition as a combinatorial optimisation problem, in that we wish to find an optimal matching between a set of object model features and image features. Using straight line features provides for the modelling of almost any shape, and methods exist for extracting of line segments from images.
Local search algorithms are a class of combinatorial optimisation algorithms that iteratively move through a space of candidate solutions in order to find the solution with the least cost. In our case cost refers to the quality of a matching through a match error that penalises poor fitting (closeness of matched line segments) and failure to match parts of the object model (omission).
Previous work in this area considered the application of relatively simple local search algorithms to the problem of geometric matching. We extend this work, presenting a study of the application of other local search algorithms: first improvement, steepest descent, simulated annealing and tabu search. We present hybrid algorithms combining both simulated annealing and first improvement with steepest descent which give dramatically improved performance, particularly for complex object models where this increase is up to an order of magnitude.
The thesis is also available in HTML format. This was done using latex2html. Unfortunately the pictures come out too small, the odd page is missing (and I can't get it back) but it is there and it is fully linked.