Fast Pattern Matching Algorithms

Pattern matching is an important and basic problem in the field of computer vision and pattern recognition. It has a broad application background scene matching navigation in image registration, stereo vision, image retrieval, object recognition, tracking and medical image analysis and so on. It has important theoretical significance and practical application value to study and has been the hotspot in research of many problems.Pattern matching can be divided into point pattern matching method and the line pattern matching method. Point pattern matching can be divided into parameter matching method based on space transform, the matching method based on invariant or invariant features and matching method based on graph theory and various cross method. Line pattern matching can be divided into the line matching method based on invariant, line matching method based on geometric constraints and line matching method based on structural descriptors, etc. These methods have achieved some results, but in the study of pattern matching, people have been looking for a fast matching algorithm. Aiming at this problem, this paper proposes a fast point pattern matching algorithm and a fast line pattern matching algorithm. In this paper, the main work and research results were as follows:l.We has studied completely point pattern matching method, then put forward a point pattern matching algorithm based on convex hull under the rotation scaling transformation in translation. We has studied the matching algorithm of the convex hull. According to two similar convex hull is proportional to the corresponding angles are equal, the corresponding edge, the calculation of the convex hull inside and side length, through the string matching algorithm, KMP algorithm, match two convex hull of the angles and length.In point set matching, according to the center of gravity is a translation invariant under the rotation scaling transformation, calculation of scaling ratio;Then through calculating the convex hull of point set and convex hull of the matching algorithm, determine the corresponding relation of corresponding points, so as to realize under rotation, scaling, and translation transformation point pattern matching algorithm.The experimental results show that the algorithm is accurate and high efficiency.2.We propose a pattern matching algorithm under the rotation scaling transformation in translation based on line feature. Algorithm use canny operator to extract image edge curve in image, Douglas-Peucker algorithm to segment curves, curve fitting of the piecewise segments using least squares. Signature lines of the two pictures in lines are calculated respectively, calculate each of the target segment and the signature lines segment feature descriptor, and constitute a line feature sequences. By comparing the line feature sequence similarity, line corresponding to the collection of similar line. Use RANSAC algorithm thought correction and eliminate false matching line, matching results are obtained.The experimental results show that the algorithm better balance the relations between the accuracy and speed.