Combinatorial methods for approximate image matching under translations and rotations ?
Given two-dimensional images , we develop a fast rotation invariant filtration algorithm for finding the locations of approximate occurrences of P in T. In such an occurrence, each pixel of T should match the corresponding intervals of pixels defined by P. Our filter works by extracting linear sequences of intervals, called features, from P, and by searching these in T to find candidate positions and orientations for a whole occurrence of P. We give an exact combinatorial analysis of the problem. The number of relevant orientations for P is O(m3) and the number of different features of length u is O(u2). These can be reduced to , respectively, using heuristics. We show that the optimal feature length is O(logm) and give an worst case time filtering algorithm for the problem. We conclude with experimental results.
rotation invariance combinatorial string matching image comparison