1 Introduction
Many applications in image processing and computer vision require finding a particular pattern in an image. This task is referred to as pattern matching and may appear in various forms. Some applications require detection of a set of patterns in a single image, for instance, when a pattern may appear under various transformations or when several distinct patterns are sought in the image. Other applications require finding a particular pattern in several images. The pattern is usually a 2D image fragment, much smaller than the image. In video applications, a pattern may also take the form of a 3D spatio-temporal fragment, representing a collection of 2D patterns (see Fig. 1). Pattern matching in 2D and in 3D: For each pixel location, a local neighborhood is compared with the given pattern.