Although pattern recognition is one of the earliest digital image processing tasks, it still represents a fundamental aspect of many contemporary and future machine vision systems. Over time, pattern recognition software tools have evolved to become highly flexible and tolerant to noise, rotation, scale, occlusion, uneven lighting variations, etc. Nevertheless, certain machine vision applications still benefit from the fast and well-known pattern matching technique based on normalized grayscale correlation (NGC). As a result, the Matrox Imaging Pattern Matching tool is still subject to continuous enhancement in order to address today’s challenges. This Vision Squad File introduces the latest improvements to this tool and provides some tips and tricks on how to use it most efficiently.
New automatic content-based resolution level selection
The normalized grayscale correlation of a model image and a target image is a computationally intensive task, which greatly depends on the size of both target and model. To speed up the process, the Pattern Matching tool employs a hierarchical search strategy using a series of sub-sampled images, called the resolution pyramid, where the image at each level is half the size of the previous one. Figure 1
The search starts at a low resolution level, where attempts are made to quickly locate candidates that are then passed to a higher resolution level for local validation and better positional accuracy. The automatic selection of the resolution levels is the task of choosing the first and last level of the resolution pyramid before starting the hierarchical search. By default, the automatic selection of these levels is based only on the size of the model. However, this simple decision may lead to one of the following situations:
1.
An overly aggressive first-level selection when a small prominent feature is enclosed in a large model image Suppose a very small circular-shaped object is the only meaningful feature in a large model image. Since the model image is very big, the algorithm assumes that it can work on a highly sub-sampled version of the model. However, at this very low resolution, the small feature has almost disappeared and the hierarchical search will not be able to find any candidates as illustrated in Figure 2.
2.
Suboptimal selection of the first level when a large object is enclosed in the model image The simple criteria based on the size of the model can lead to the situation where a model image could have been sub-sampled more without affecting the robustness of the hierarchical search algorithm. This is the case when the prominent feature occupies most of the model image as illustrated in Figure 3.
As of MIL 9 Processing Pack 2, the Pattern Matching tool offers a new automatic content-based level selection algorithm that performs a content analysis of the model. This allows the first and last level of the hierarchical search to be chosen more “intelligently”. This new automatic mode is even more useful given that the limitation on the size of the model has been removed since MIL 9. The mode is easily enabled by explicitly setting a tool parameter (M_FIRST_LEVEL control to M_AUTO_CONTENT_BASED).
Additional tips:
To adapt to the relaxed constraint on the size of the model image, the first and last level can now be manually set to a value in the range [0, MaxLevel] instead of [0, 7] previously. The MaxLevel is a read-only value provided by the module that can be inquired with MpatInquire(…, M_MODEL_MAX_LEVEL, …)
New automatic content-based selection of angle tolerance and accuracy
When the angle mode is activated, there are a few important parameters that define the behavior of the algorithm with regards to the following aspect:
1.
The range of angles to cover in the search operation
Figure 4:
2.
The tolerance and accuracy of the search
At the preprocessing step (MpatPreprocModel), multiple models, each at different orientations, are generated using the tolerance parameter (M_SEARCH_ANGLE_TOLERANCE) for the angle step. The search algorithm then uses these rotated models to find possible occurrences in the target image. If this initial coarse search succeeds, the angle is refined using the accuracy parameter (M_SEARCH_ANGLE_ACCURACY).
By default, the tolerance parameter is a fixed value (5 degree), which is enough for most situations although it is not optimal. The new automatic mode intelligently chooses the angle tolerance by analyzing the content of the model image. This mode is enabled by explicitly setting a tool parameter (M_SEARCH_ANGLE_TOLERANCE control to M_AUTO).
If we rotate the model by 5 degrees but the target occurrence is 5.5 degrees, the misalignment will result in a lower score. The extent of this decrease in score depends on the shape of the model. For example, a circle is not sensitive to rotation while a line segment will almost not correlate at all as a result of rotation. To help determine the angle accuracy to use, the Pattern Matching tool also offers a new parameter (M_ROTATED_MODEL_MINIMUM_SCORE) to set the minimum acceptable score due to the angle range sampling. In this case, the angle step accuracy will automatically be refined during the preprocessing step with respect to the score constraint. By default, this control is set to M_DISABLE, in which case no automatic accuracy is computed. If a value between 0.0 and 100.0 is given, it will be used to automatically compute the necessary accuracy. The maximum rotation angle that gives this score will be used to calculate the accuracy.
To prevent missing an occurrence in the target image due to the angular sampling, the minimum score (M_ROTATED_MODEL_MINIMUM_SCORE) should be set to a value higher than the overall acceptance score (MpatSetAcceptance()). However, the higher the rotated minimum score, the smaller the refined angular search, and the longer the matching.
Speed optimisation
Also as of MIL 9 Processing Pack 2, the Pattern Matching tool can take advantage of a CPU’s multiple cores to accelerate a search by transparently splitting the task between cores (see Figure 5). Multiple cores will be automatically used when beneficial, which depends on the size of the model, the number of pyramid levels, the search angle range, the size of the target, and the number of models.
Link to Matrox Imaging Library Overview:
http://www.rauscher.de/...
For more information please contact:
RAUSCHER
Johann-G.Gutenberg-Str. 20
D-82140 Olching
Phone +49 81 42 / 4 48 41-0
Fax +49 81 42 / 4 48 41-90
E-Mail: info@rauscher.de
www.rauscher.de
New automatic content-based resolution level selection
The normalized grayscale correlation of a model image and a target image is a computationally intensive task, which greatly depends on the size of both target and model. To speed up the process, the Pattern Matching tool employs a hierarchical search strategy using a series of sub-sampled images, called the resolution pyramid, where the image at each level is half the size of the previous one. Figure 1
The search starts at a low resolution level, where attempts are made to quickly locate candidates that are then passed to a higher resolution level for local validation and better positional accuracy. The automatic selection of the resolution levels is the task of choosing the first and last level of the resolution pyramid before starting the hierarchical search. By default, the automatic selection of these levels is based only on the size of the model. However, this simple decision may lead to one of the following situations:
1.
An overly aggressive first-level selection when a small prominent feature is enclosed in a large model image Suppose a very small circular-shaped object is the only meaningful feature in a large model image. Since the model image is very big, the algorithm assumes that it can work on a highly sub-sampled version of the model. However, at this very low resolution, the small feature has almost disappeared and the hierarchical search will not be able to find any candidates as illustrated in Figure 2.
2.
Suboptimal selection of the first level when a large object is enclosed in the model image The simple criteria based on the size of the model can lead to the situation where a model image could have been sub-sampled more without affecting the robustness of the hierarchical search algorithm. This is the case when the prominent feature occupies most of the model image as illustrated in Figure 3.
As of MIL 9 Processing Pack 2, the Pattern Matching tool offers a new automatic content-based level selection algorithm that performs a content analysis of the model. This allows the first and last level of the hierarchical search to be chosen more “intelligently”. This new automatic mode is even more useful given that the limitation on the size of the model has been removed since MIL 9. The mode is easily enabled by explicitly setting a tool parameter (M_FIRST_LEVEL control to M_AUTO_CONTENT_BASED).
Additional tips:
To adapt to the relaxed constraint on the size of the model image, the first and last level can now be manually set to a value in the range [0, MaxLevel] instead of [0, 7] previously. The MaxLevel is a read-only value provided by the module that can be inquired with MpatInquire(…, M_MODEL_MAX_LEVEL, …)
New automatic content-based selection of angle tolerance and accuracy
When the angle mode is activated, there are a few important parameters that define the behavior of the algorithm with regards to the following aspect:
1.
The range of angles to cover in the search operation
Figure 4:
2.
The tolerance and accuracy of the search
At the preprocessing step (MpatPreprocModel), multiple models, each at different orientations, are generated using the tolerance parameter (M_SEARCH_ANGLE_TOLERANCE) for the angle step. The search algorithm then uses these rotated models to find possible occurrences in the target image. If this initial coarse search succeeds, the angle is refined using the accuracy parameter (M_SEARCH_ANGLE_ACCURACY).
By default, the tolerance parameter is a fixed value (5 degree), which is enough for most situations although it is not optimal. The new automatic mode intelligently chooses the angle tolerance by analyzing the content of the model image. This mode is enabled by explicitly setting a tool parameter (M_SEARCH_ANGLE_TOLERANCE control to M_AUTO).
If we rotate the model by 5 degrees but the target occurrence is 5.5 degrees, the misalignment will result in a lower score. The extent of this decrease in score depends on the shape of the model. For example, a circle is not sensitive to rotation while a line segment will almost not correlate at all as a result of rotation. To help determine the angle accuracy to use, the Pattern Matching tool also offers a new parameter (M_ROTATED_MODEL_MINIMUM_SCORE) to set the minimum acceptable score due to the angle range sampling. In this case, the angle step accuracy will automatically be refined during the preprocessing step with respect to the score constraint. By default, this control is set to M_DISABLE, in which case no automatic accuracy is computed. If a value between 0.0 and 100.0 is given, it will be used to automatically compute the necessary accuracy. The maximum rotation angle that gives this score will be used to calculate the accuracy.
To prevent missing an occurrence in the target image due to the angular sampling, the minimum score (M_ROTATED_MODEL_MINIMUM_SCORE) should be set to a value higher than the overall acceptance score (MpatSetAcceptance()). However, the higher the rotated minimum score, the smaller the refined angular search, and the longer the matching.
Speed optimisation
Also as of MIL 9 Processing Pack 2, the Pattern Matching tool can take advantage of a CPU’s multiple cores to accelerate a search by transparently splitting the task between cores (see Figure 5). Multiple cores will be automatically used when beneficial, which depends on the size of the model, the number of pyramid levels, the search angle range, the size of the target, and the number of models.
Link to Matrox Imaging Library Overview:
http://www.rauscher.de/...
For more information please contact:
RAUSCHER
Johann-G.Gutenberg-Str. 20
D-82140 Olching
Phone +49 81 42 / 4 48 41-0
Fax +49 81 42 / 4 48 41-90
E-Mail: info@rauscher.de
www.rauscher.de
