Matching of Orthogonal Polygons.

Anshuman Tripathi, Souhadra Upadhyay

Prof Partha Bhowmick, Department of Computer Science and Engineering, IIT Kharagpur

GENERAL : Inexact matching of orhtogonal polygons, is particularly usefull in the field of fingerpring matching, and object detection among others. This project constists of two parts, in first we developed a database of randomly generated orhtogonal polygons using the Inflate and Cut algorithm for their generation. We developed novel representations for storing the polygons in the database so that the representation doesn't change on rotational transformation, and mirror transformations can be easily applied. In the second part of the project, we developed novel heuristic algorithms to match a given query polygon against a database of polygons, and rate each match on a scale of 100. Finaly we reported the best match based on the rating.

END RESULT : We developed two heuristic algorithms and figured out a way to comnine the ratings of these two heuristics, to give the best visually evident results.

STATUS : The final code for this project can be downloaded here.

POSSIBLE IMPROVEMENTS:

The algorithms can be tested on practical situations for object detection and finger print matching, to comment inteligibly on the scalability and efficacy of the algorithms.
The representation developed in the project only takes care of the rotational, mirror and scaling transformations.
The algorithm may be exteded for general polygon matching

RESOURCES:

Code

RESULTS: Here we present some of the results we got while experimentations:

Matching

Query	Match	Rating	Comments
		88.2	Note the inexactness of mached results
		100.0	Mirror Transformations make no effect on the matching
		95.7	Rotational Transformation