The New Jersey Institute of Technology's
Electronic Theses & Dissertations Project

Title:	Point pattern matching by heuristic methods : a genetic algorithm and simulated annealing
Author:	Chen, Erh-Chin
View Online:	njit-etd1992-059 (ix, 32 pages ~ 1.0 MB pdf)
Department:	Department of Electrical and Computer Engineering
Degree:	Master of Science
Program:	Electrical Engineering
Document Type:	Thesis
Advisory Committee:	Ansari, Nirwan (Committee chair) Hou, Edwin (Committee member) Siveski, Zoran (Committee member)
Date:	1992-10
Keywords:	Heuristic programming Pattern recognition Simulated annealing (Mathematics)
Availability:	Unrestricted
Abstract:	The problem we consider is to find a subset of points in a pattern that best match to a subset of points in another pattern through a transformation in an optimal sense. Exhaustive search to find the best assignment mapping one set of points to another set is, if the number of points that are to be matched is large, computationally expensive. We propose two stochastic searching techniques - a genetic algorithm and simulated annealing to search for the best ("almost the best") assignment efficiently. To make the comparison between GA and SA fair, we introduce a piece-wise linear cooling schedule for the SA. As compared to conventional searching techniques such as simple hill climbing and random search techniques, the proposed methods are able to attain better solutions much faster. The proposed methods can be applied to n-dimensional point patterns and any transformation, but we only present results for two-dimensional point patterns and similarity transformations.