Given two-dimensional images T1..n,1.ln and P1..m,1..m whereM< n, we develop a fast rotation invariant filtration algorithm forfinding the locations of approximate occurrences of P in T. In suchan occurrence, each pixel of T should match the correspondingintervals of pixels defined by P. Our filter works by extractinglinear sequences of intervals, called features, from P, and bysearching these in T to find candidate positions and orientations fora whole occurrence of P. We give an exact combinatorial analysis ofthe problem. The number of relevant orientations for P is O(m~3) andthe number of different features of length u is O(u~2). These can bereduced to O(m) and O(u), respectively, using heuristics. We showthat the optimal feature length is O(log m) and give an O(T lng m)worst case time filtering algorithm for the problem. We conclude withexperimental results.
展开▼
