Pattern Matching Strategies

Pattern matching is a method of identifying features in an image that match a smaller template image (that is, the "pattern" to be matched). The process involves two phases: an off-line learning phase in which the template is processed, and a matching phase that can be executed in real time. This document explains some of the factors involved in pattern matching performance, and strategies that you can use to achieve the best results.

The Learning Phase

The learning phase of pattern matching involves analyzing the template image to find features that can be exploited for efficient matching performance. This phase is what gives advanced pattern matching techniques dramatically improved performance compared to traditional grayscale correlation methods. The traditional methods have no learning phase; the template is simply compared to every possible location in the image via a 2D correlation. This is very computationally intensive and involves many redundant calculations. Below is an example of a printed circuit board and template. After performing the correlation at every point in the image, two matches were found.


The correlation image produced is shown below. The two bright spots correspond to the two matches found:


With a learning phase, you can incorporate sub-sampling of the template image to drastically reduce the number of calculations. Below is an example of a template that has been sub-sampled. The red squares capture information about the overall structure of the image, while the green circles identify features of the image that will be useful for localizing the match precisely.


The National Instruments pattern matching algorithm incorporates the following features in the learning phase:

• Pseudo-random sub-sampling: If you sub-sample the template by taking a uniform grid, it is possible to miss important features of the template, such as horizontal and vertical edges. Random sampling tends to produce clusters and open areas; having clusters of samples in the same area of the template is inefficient, while the unsampled areas may contain important information. The pseudo-random technique maximizes the uniformity of the sampling throughout the template without using a pre-defined grid.
• Stability analysis: The pseudo-random sample pixels are analyzed by checking their surrounding neighborhood for stability (uniformity). Each pixel is classified according to how large its stable neighborhood is (that is, 3x3, 5x5, and so on). This information is helpful in reducing the number of comparisons needed in the matching phase.
• Feature identification: Finally, an edge detection operation is performed on the template image. The resulting edge locations are retained for use in fine-tuning the location of the matched image.
• Rotational-invariant analysis: If the user needs to be able to find a rotated version of the pattern in the search image, the learning phase also obtains information that can be used to detect rotation. This is done by identifying a circular intensity profile in the template image. A rotated version of the template has the same profile, but is shifted left or right by the amount of rotation.

This learning phase is quite complex, and the calculations can take up to several seconds to perform for large or complex templates. This phase only needs to be done once per template, however. The results can be stored in a file for use later in the actual pattern matching operation.

Matching Patterns

The matching phase uses the information from the learning phase to eliminate as much unnecessary calculation as possible. The matching algorithm used depends on whether the user has specified shift-invariant matching (finding the template at any location in the search image) or rotation-invariant matching (finding the template at any location AND rotation in the search image). Both are two-pass processes.

Shift-Invariant Matching

1. The first pass is a correlation that uses only the pseudo-randomly sampled pixels from the template image. The results of the stability analysis are used to determine how many positions in the search image can be skipped without missing any important features. For example, if all the sub-sampled pixels were found to be stable in a 3x3 neighborhood, the matching algorithm can skip two out of three correlations in each row and column while still guaranteeing that a match will be detected. This reduces the number of calculations required by a factor of 9. The first pass produces a number of candidate matches with rough position information.
2. The second pass only operates on the candidates identified in the first pass. The edge detection results of the learning phase are used to fine-tune the location of each match, and a score is produced for each based on the correlation result at that location. A user-provided score threshold determines which candidates are returned as matches.

Rotation-Invariant Matching

1. The first pass uses the circular intensity profile from the learning phase to search for shifted versions of that profile throughout the image. The user can input an allowable rotation range (in degrees) to reduce the number of calculations required in this pass. Several candidate matches are identified in this pass.
2. The second pass uses the pseudo-randomly sampled pixels to perform a correlation with all the candidates. A score is produced for each candidate to determine whether it should be classified as a match or not.

   Template Selection
   

The choice of the template to be matched can have a great impact on the speed and accuracy of the pattern matching algorithm. There are some general observations we can make based on the algorithms described above:

• The template should be asymmetric enough so that it can be uniquely identified at a certain orientation. The circular feature shown below could be rotated at any angle or flipped, but the pattern matching results won't contain that information.

• Complex templates will take longer to match than very simple ones. If the template is too simple, however, you will get spurious matches. You must ensure that the template includes enough detail to uniquely identify and precisely localize the pattern:
  
  
  
  
  
  
• The template should contain enough detail to fix its spatial position in the image. To do this, it needs to contain both vertical and horizontal features. The image on the right below will locate the exact position of the pattern, but still leaves ambiguity about the rotation (it could be rotated 180 degrees):
  
  
  
  
  
  
• If you are trying to locate a simple feature such as a dot or hole in a board, the template should be large enough to contain background information that distinguishes that particular feature from similar ones in the image:
  
  

Reader Comments | Submit a comment »