PATTERN MATCHING C++ FOIL EXTENSION

Shape Based Pattern Matching

Patterns start from an initial image and a mask image. The mask image selects which pixels from the initial image are part of the pattern (mask=nz) and which are not part of the pattern (mask=z). The mask image defines the ROI of the pattern image. A mask image is used, as the ROI may not be a rectangle. The pattern image may be a grabbed image or an artificially generated image. (i.e. it doesn’t matter where the original pattern image comes from.)

Metrics

Pattern location algorithms use various metrics to determine the fit of an image to a pattern at a particular location.

Normalized Image Correlation

The following equation defines the normalized correlation of an image and a pattern.

(l,c) is the center of the pattern image.
(u,v) range of the full pattern image
(i,j) runs over the region of interest in the image.

Average Image Difference

Geometric Hashing Metric

k ranges over all the pattern elements
(i,j) runs over the region of interest in the image.

A pattern element contains a ‘weight’, a ‘point’, a point ‘operator’ and a ‘value’. A point operator is applied to the source image at an offset from the pattern center. This operator can be as simple as picking the pixel value from the image, or more complex operators like a Sobel of the image at that point. The difference between the value of the point operator and the value from the pattern is multiplied by a weight, and added to the match score. Depending on how these parameters are used a maximum or a minimum score provides the detected location of the modeled object.

Subs-sampled patterns

In order to speed the recognition process the models may be sub-sampled. Sub-sampling is the process of removing model elements to improve computation speed, in a fashion that minimizes the impact on accuracy. If the elements of the pattern are images, then the images are reduced in size. In the geometric model, model points are removed, or replaced by other points.

Hierarchical Patterns

A hierarchical pattern is a collection of patterns, which are created to reduce the computational requirements of pattern recognition. At the top of the hierarchy is a simple pattern or patterns, which are computationally efficient but less accurate. These patterns are used to locate possible spots in the image that should be examined with the more accurate patterns at lower levels. This scheme reduces the computation requirements by eliminating bad fitting locations early. In addition hierarchical patterns can be used to implement scale and rotation invariance. In this case, sets of coarser but easily computable patterns are used to select the properly scaled and rotated patterns, in the hierarchy to be applied for an accurate location.

Pattern Recognition

• A hierarchy of patterns used to do a pattern match is called a model. The pattern recognition takes the model, and applies its metric to each point in the ROI in the input image under consideration.

• Using the threshold for this model level the points that fall above or below the threshold (depending on if it’s looking for a maximum or a minimum score), are removed from the input image ROI.

• At the initial level the models are simple and mainly are used to remove obviously bad points from the initial input ROI, to reduce the computational load at later levels.

• As the algorithm passes from level to level, and along branches within levels, the area of search is reduced, while the computational complexity increases, further contracting the area of search.

• In the final step a sub-pixel fit is obtained by interpolating the score values to find the maximum point to a sub-pixel accuracy, or the pattern and input image is interpolated, and then re-applied over a small ROI around each previously found location.
  

The algorithmic flow described above is diagrammed below.

click to enlarge

Click here to Download DataSheet or here to Register to Download Manuals