Scene Analysis, Homomorphism, and Consistent Labeling Problem Algorithms

摘要

In this research project the meaning of image matching in the symbolic sense was explored in detail as well as the nature of the algorithms required to do image matching. It was determined that image matching was, in fact, a relational homomorphism problem and that relational homomorphism was a kind of constraint satisfaction problem that is called consistent labeling. Consistent labeling problems are prevalent in image understanding work; for example, line labeling, and region interpretation are consistent labeling problems. Having realized that the hard computational problems were consistent labeling problems, our efforts were concentrated on efficient algorithms for solving them. The results indicate that the forward checking algorithm is the fastest algorithm from all algorithm tried for solving the consistent labeling problem. (Author)