Efficient guaranteed search for gray-level patterns

We address the problem of locating a gray-level pattern in a gray-level image. The pattern can have been transformed by an affine transformation, and may have undergone some additional changes. We define a difference function based on comparing each pixel of the pattern with a window in the image, and search efficiently for transformations that minimize the difference function. The search is guaranteed: it will always find the transformation minimising the difference function, and not get fooled by a local minimum; it is also efficient, in that it does not need to examine every transformation in order to achieve this guarantee. This technique can be applied to object location, motion tracking, optical flow, or block-based motion compensation in video image sequence compression (e.g., MPEG)