Matching two geometric objects in 2D and 3D spaces is a central problem in computer vision, pattern recognition and protein structure prediction. In particular, the problem of aligning two polygonal chains under translation and rotation to minimize their distance has been studied using various distance measures. It is well known that the Hausdorff distance is useful for matching two point sets, and that the Frechet distance is a superior measure for matching two polygonal chains. The discrete Frechetdistance closely approximates the (continuous) Frechet distance, and is a natural measure for the geometric similarity of the folded 3D structures of bio-molecules such as proteins. In this paper, we present new algorithms for matching two polygonal chains in 2D to minimize their discrete Frechet distance under translation and rotation, and an effective heuristic for matching two polygonal chains in 3D. We also describe our empirical results on the application of the discrete Frechet distance to the protein structure-structure alignment.
展开▼
