Advanced Pattern Matching Concepts

Introduction

Advanced pattern matching contains low-level learning and matching options that enable you to customize the pattern matching algorithm to your specific machine vision application. In order to be useful to a broad audience, a pattern matching algorithm needs to process numerous diverse template images and search images. Determining a set of default advanced pattern matching options that is optimal for all possible applications is improbable. However, you can customize the IMAQ Vision pattern matching algorithm for your application by configuring several advanced options that affect the speed and accuracy of pattern matching.

When To Use

If the pattern matching portion of your application is not working as expected, make sure you have defined a template with the following qualities:

• Good feature detail,
• Adequate positional data,
• Sufficient background information,
• Appropriate level of asymmetry (for rotation-invariant matching).

You can change the template slightly to remove excessive background information or include additional feature information. You may also consider restricting the angle ranges, if possible, or defining a search region. In addition, make sure your application is running in optimal lighting conditions and that you are acquiring quality images. Nonuniform lighting and poor image quality adversely affect other image processing algorithms as well as pattern matching. If you have suitable template images and search images but want to improve the speed and/or accuracy of the pattern matching process, you can configure the advanced pattern matching options.

Pattern Matching Phases

Pattern matching consists of two stages: a learning stage, which is usually performed offline, and a matching stage. For the purpose of discussing advanced pattern matching options and the consequences of changing the default values, this document divides the matching stage into the following four phases.

Initial phase—The first phase of shift- and rotation-invariant pattern matching. The algorithm makes steps larger than a pixel to locate potential matches.

Intermediate phase—The second phase of rotation-invariant pattern matching. The algorithm makes coarse refinements to the location of matches found during the initial phase. Normally, this phase is skipped during shift-invariant matching.

Final phase—The third, and often final, phase of shift- and rotation-invariant pattern matching. The algorithm makes small refinements to the matches.

Subpixel refinement phase—The last phase of pattern matching if the Enable Subpixel Accuracy parameter is set to 1 (TRUE). The algorithm refines the matches to achieve subpixel and subangle accuracy.

Most advanced options influence only one phase of the pattern matching process. In most cases, you control one phase of the pattern matching process using multiple advanced options.

Guidelines for Using Advanced Options

If you still require better results after configuring the advanced match options, try changing the advanced learn options. The advanced learn options allow you to manage the amount of data used in different segments of the matching process. You have control of the number of data points and/or the angular accuracy of the data points while the algorithm selects the points.

The results you get from changing the advanced learn options vary significantly from one template to the next. At times, changing the options might produce undesired results. For example, requesting more data points for a template could result in less accurate matches because too many data points cause the algorithm to sample image noise. This scenario is not unusual or unexpected.

Advanced Match Options

The following list describes the advanced options you can configure for the match process.

Minimum Contrast—Specifies the minimum contrast value a potential match region must have to contain a match. When used with templates having high contrast, this option improves speed by excluding regions of an image.

Enable Subpixel Accuracy—Enables the subpixel refinement phase applied to matches at the end of the final phase. When the correct matches are found but their location is less accurate than expected, set this option to 1 (TRUE).

Subpixel Iterations—Defines the number of refinements performed by the match process using the subpixel information stored in the template. These refinement iterations are applied to the number of matches requested.

Subpixel Tolerance—Specifies the control tolerance used during subpixel refinement to stop processing when a match location has been improved to the given accuracy. This option can improve the speed of the algorithm when you have multiple matches because the amount of refinement for each match varies with the accuracy of its location. For shift-invariant matching, this option represents the tolerance, in pixels, for position. For rotation-invariant matching, this option represents the tolerance, in degrees, for angular accuracy and indirectly sets a lower tolerance using radian distances, in pixels, for position.

Initial Match List Length—Specifies the number of match regions cached from the initial phase of matching. The match algorithm focuses on these regions in later processing. If the template is very distinct in the search images, reducing this length improves speed significantly. If the application is missing matches, increasing this value may solve the problem but processing becomes slower.

Match List Reduction Factor—Controls how quickly the match list is shortened from one matching phase to the next. The value is a divisor of the list length. For example, a value of 2 cuts the list in half. If you increase the list length with Initial Match List Length, you can recover some speed by increasing the Match List Reduction Factor. In most instances, reduce the Match List Reduction Factor to keep more match regions for later processing, which increases accuracy but decreases speed.

Initial Step Size—pecifies the number of pixels to shift the template across the inspection image during the initial phase of matching. The optimal step size is computed during the learning phase, stored with the template, and used by default. You can reduce the step size to improve match accuracy, but doing so greatly reduces speed. Do not increase this value to make larger steps.

Intermediate Angular Accuracy—Establishes the angular accuracy, in degrees, used when refining rotated matches from the initial phase. Decreasing this value causes higher accuracy in resulting matches but slows processing. If angular accuracy is not important to the application or the template is symmetrical, increase this value to get faster matching with less accurate angles. The angular accuracy value is rounded down to a value that evenly divides 360 and provides at least the accuracy requested.

Search Strategy—Specifies the matching strategy used to find the matches. The default search strategy is Balanced (2), which initially searches the image using a medium step size to improve speed and then uses the match refinement of the Conservative strategy (1) to maintain accuracy. The Conservative strategy initially searches the image with a small step size, which reduces speed but provides very accurate matches. In general, avoid the Aggressive strategy (3) unless the center of the template does not contain distinguishing characteristics or the template is highly rectangular (3:1 or more in dimensions).

Advanced Learn Options

The following list describes the advanced options you can configure for the learning process.

Initial Sample Size—Specifies the size of the sample, in pixels, used during the initial phase of matching. When distinguishing template characteristics are not defined by the edges in the template, increase this value to promote nonedge characteristics during matching. A larger sample size reduces the match speed. Increase the size by a multiple of 12 for the best possible match speed; a size of 60 is optimal. If you have a large template (for example, a template whose dimensions exceed 200 pixels), try increasing the sample size to improve accuracy. Increasing the sample size has less of an impact on match speed with large templates than with small templates.

Initial Sample Size Factor—Determines the size of the sample, in percent of total pixels, used during the initial phase of matching. Defining a sample size as a percent of total pixels facilitates consistent sampling across templates of different dimensions.

Final Sample Size—Specifies the size of the sample, in pixels, used during the final phase of matching. When edges define the most unique template characteristics, increase this value to promote edge characteristics during matching. Increase the size by a multiple of 12 for best match speed; a size of 60 is optimal.

Note A large Final Sample Size does not reduce match speed as much as a large Initial Sample Size.

If you have a large template (for example, a template whose dimensions exceed 200 pixels), increasing this sample size improves match accuracy with only small speed degradation.

Final Sample Size Factor—Determines the size of the sample, in percent of total pixels, used during the final phase of matching. Defining a sample size in percent of total pixels facilitates consistent sampling across templates of different dimensions.

Subpixel Sample Size—Specifies the size of the sample, in pixels, used during the subpixel refinement phase of matching. The default sample size that the algorithm determines during the learning process is conservative—slightly larger than the initial or final sample sizes. Increasing this size may deteriorate match accuracy. Although this sample is used primarily during subpixel refinement, it is used also during final match processing. Therefore, the Subpixel Sample Size affects matching even when Enable Subpixel Accuracy is set to 0 (FALSE).

Subpixel Sample Size Factor—Determines the size of the sample, in percent of total pixels, used during the subpixel refinement phase of matching. Defining a sample size in percent of total pixels facilitates consistent sampling across templates of different dimensions.

Initial Angular Accuracy—Establishes the angular accuracy supported during the initial phase of rotation-invariant matching. Use the advanced match option Intermediate Angular Accuracy to limit the angular accuracy unless you do not need the template to produce matches at this angular accuracy. Reducing the initial accuracy reduces the template size by less than a third.

Final Angular Accuracy—Establishes the angular accuracy supported during the intermediate and final phases of rotation-invariant matching. As with Initial Angular Accuracy, increasing this value reduces the final accuracy by restricting the template from generating more accurate match results regardless of the match options used. However, reducing the accuracy significantly shrinks the template size by as much as half.

Initial Step Size—Defines the initial jump size to support when searching for the template. Because this value depends entirely on the pixel content and other special characteristics of the template, avoid changing this value. If you set a lower Initial Step Size, the initial match phase rigorously searches more match regions located closer together. A better approach to achieving a rigorous initial search is to set Search Strategy Support to 1 (Conservative). This lowers the step size to an optimal value based on the template and automatically adjusts other options according to that value.

Note The value of Initial Step Size is a recommendation for the learn process. The actual step size may be smaller based on the content of the template image.

Search Strategy Support—Defines the set of search strategies supported by the template during matching. The Balanced and Conservative search strategies are supported by default. If you intend to use this template with the advanced match option Search Strategy set to 3 (Aggressive), set Search Strategy Support to 3 (Aggressive, Balanced & Conservative). Set this option to 1 (Conservative) if you are performing matching only with the Conservative search strategy and want to minimize the template size.

Options at a Glance

This section illustrates how the advanced pattern matching options effect the accuracy, speed, and risk of pattern matching in your application. The following illustration shows the impact that each advanced match option has on the accuracy and speed of the matching process.

The following figure shows the impact that each learn option has on the accuracy and speed of the matching process.

The following figure illustrates the risk of getting unexpected results when configuring the advanced match and learn options. The risk levels shown for each option correspond to setting more aggressive values for the option.

Optimizing for Accuracy

Many advanced options impact the accuracy of match results. Accuracy may refer to the following:

• Order in which multiple matches are returned,
• Number of matches returned,
• Match location(s) returned.

Each of these conditions requires a different usage of the advanced options. In general, if you find a match with a lower score than expected or an inaccurate position, use subpixel refinement to improve the results. First, set Enable Subpixel Accuracy to 1 (TRUE) to increase accuracy. Then, increase the number of subpixel iterations with Subpixel Iterations if you need additional improvement.

If only one of several matches is inaccurate, you can set Subpixel Tolerance to the pixel accuracy desired, which is normally between 0.1 and 0.5. By setting this value, the pattern matching algorithm spends time improving only those matches outside the specified tolerance instead of refining all matches for the given number of iterations. When providing a tolerance, set Subpixel Iterations to 0 (default) to allow the refinement process choose when to stop, or set Subpixel Iterations to a maximum iteration to cap the amount of refinement performed when the tolerance is unreachable.

Altering subpixel refinement options is the last phase of the matching process you can manipulate to improve accuracy. If altering subpixel refinement options does not result in the expected match accuracy, you can adjust one or more of the following options. Determining which options to adjust varies among applications, but the following categorization of options provides a general order in which to proceed.

• Basic match options—Shift/rotation invariance, Minimum Contrast, Rotation Angle Ranges:
  • Low risk relative to other advanced options.
  • Can significantly impact match results by impacting the entire match process.
• Advanced match options used in the intermediate and final phases of the match process—Intermediate Angular Accuracy, Match List Reduction Factor:
  • Usually low risk because they occur during pixel-level refinement,
  • Impact on match speed is reduced because these options affect a later match phase.
• Advanced match options used in the initial phase of the match process— Initial Match List Length, Initial Step Size:
  • Higher risk because these options alter match selection from the start,
  • Slower match speed when more conservative values are selected because of additional processing required.
    Note Changing Initial Step Size is not recommended because the template contains the optimal initial step size to use. If you want to perform an exhaustive search for the template, you can set this option to 1, but doing so significantly reduces matching speed.
• Advanced match option defining the match process—Search Strategy: Aggressive, Balanced (default), and Conservative:
  • High risk because changing this option alters most advanced match options and sometimes alters the initial search approach.
  • Conservative works like Balanced but is more rigorous during the initial phase, causing match speeds to double in many cases.
  • Aggressive uses a different initial searching technique, so resulting matches may differ significantly from the other strategies. Use the Aggressive option when searching on very rectangular templates or when many of the distinguishing characteristics are not in the center of the template.
• Advanced learn options used during the subpixel refinement phase—Subpixel Sample Size, Subpixel Sample Size Factor:
  • High risk relative to other advanced match options; low risk relative to other advanced learn options.
  • By default, Subpixel Sample Size is based on the size of the template, in pixels. The following Tables show the relationship between template size and Subpixel Sample Size. The first table depicts the sizes for Shift-Invariant Matching while the second table depicts the sizes for Rotation-Invariant Matching.

• Advanced learn options used during the final phase of matching—Final Sample Size, Final Sample Size Factor, Final Angular Accuracy:
  • High risk relative to other advanced match options; medium risk relative to other advanced learn options.
  • Final sample is used in the final phase of the match process and contains data for refining match locations to within a pixel or degree of accuracy. This sample includes, but is not limited to, locations around edges in the template.
  • By default, the final sample produces an angular accuracy of 1°. If you do not require this level of accuracy, you can increase the Final Angular Accuracy value, which reduces accuracy, reduces the template size, and increases the match speed. The accuracy value is always rounded down to a value that divides 360 evenly.
• Advanced learn options used during the initial phase of matching—Initial Sample Size, Initial Sample Size Factor, Initial Angular Accuracy :
  • Among the highest risk advanced options because they affect the entire match process from start to finish.
  • Initial sample contains representatives from regions having roughly the same pixel values.
  • By default, the initial sample produces an angular accuracy of 6°. This initial accuracy default is necessary to find matches in the final phase of matching with an accuracy of 1°. If you set the final accuracy to be less accurate, you can increase the Initial Angular Accuracy value to reduce accuracy, as well. The accuracy value is always rounded down to a value that divides 360 evenly.