The Calculation Theory Of Hausdorff Distance And Its Application To The Matching Of2D Geometrical Objects

Hausdorff distance as a similarity measure is widely used in many engineering fields;Such as pattern recognition, image matching,robot path planning, CAD/CAM and haptic rendering simulation, the interference detection in the collisions of objects and calculation of feedback force, the construction of optimization goal and evaluation of approximation degree in the approach of curve and surface.The research of application of Hausdorff distance in terms of discrete geometric objects, such as image matching, is carried out earlier and more mature. With the development of computer aided image processing technology, more and more image matching algorithms are proposed, which are more intelligent and fast. In contrast, the research of Hausdorff distance application in2D continuous geometry objects is less, so far, only a little study has been carried out in the aspect of the precise calculation of Hausdorff distance between free curves or surfaces.In this paper, the calculation theory of Hausdorff distance, as the research object, is well studied, then its application both in discrete geometric objects and continuous geometry objects are also researched. For its application to discrete geometric objects, a new image matching method based on Hausdorff distance is proposed, in which, image edge line is choosed as feature space, improved Hausdorff distance as similarity measure, the affine coordinate transformation (including translation, scaling transformation, rotation) as transformation model,and genetic algorithm as search strategy. Finally several examples is used to verify the image matching algorithm based on Hausdorff distance, considering small rotation. As a result,the algorithm can meet the requirements of feasibility, real-time, and anti-interference.In addition, the application of Hausdorff distance in2D continuous geometric objects is also researched in this paper, such as curve matching.The difficulty of computation of the Hausdorff distance(HD) between planar curves lies in solving different nonlinear equations for four kinds of special cases that this computing process encountered. In this paper, a new method which contains two steps for the computation of the HD between planar curves is generated. The first step of the method is sampling the curve A, and calculating the approximate solutions. The second step is identifying which case the approximate solution belongs to according to the shape and position of the curves, establishing corresponding optimization model and finding the local optimal solution.comparing these local optimal solutions, the final directed HD with the largest minimum distance will be gotten. By using the proposed method, the trouble of computing the HD beween planar curves is replaced of the problem of calculating minmal distance between a point and a curve. The computational efficiency and stability of the algorithms can be improved. The feasibility of these algorithms has been verified by two numerical examples.