Rank Order Reduction Based Fast Pattern Matching Algorithm

This paper reports a fast pattern matching algorithm which makes use of K-NN (K-nearest neighbor) based rank order reduction approach to detect a pattern or object in a given image efficiently. Initially, the given image is divided into several candidate windows, each of size the input pattern. In the next step, both the input pattern and the candidate windows are characterized by Haar transform. From the characterization, Haar Projection Values (HPV) is determined. Further, rectangle sum on both input pattern and candidate windows is computed using integral image technique. Subsequently, by using sum of absolute difference (SAD) correlation distance between the input pattern and candidate windows is determined. In order to detect the pattern, rank order approach using K-NN is applied to determine the first k number of most similar candidate windows containing the input pattern. To reduce the computational complexity of selecting a perfectly matched window, again sum of absolute differences (SAD) is applied and this leads to select the best match pattern having the total object. Decoupling correlation measures also increase the accuracy of matching pattern. Finally, the input pattern is detected and localized in the given image. The pattern matching accuracy proves the efficacy of the proposed algorithm.