There are many approaches to pattern matching and each approach has its advantages and disadvantages when used in different applications. Pattern matching can be used in two ways. Firstly for localisation of a pattern in a large area, for example in a pick and place robotic application where the camera identifies the object and then tells the robot where it is. The second use, the classification, is to decide which object is at a known location. An example of this can be found in OCR where the location of each character is known, but there is a need to determine which character is being displayed. In practical use many tools do not differentiate between those two steps, but perform them subsequently
Normalised greyscale correlation
Normalised greyscale correlation is the most common pattern matching tool and evolved from the area of statistical image analysis. It is very sensitive to changes in lighting conditions, and is intolerant of changes in scale and rotation. Due to these limitations the object must remain the same size and in the same orientation as the template. Some implementations allow the user to set tolerance ranges for rotation and scale which repeat the inspection with regenerated model templates. However, for each additional model, the search speed is significantly reduced. This technique is area based and if any part of the pattern is hidden or reduced, the match score reduces. The normalised greyscale correlation also has difficulties with partially hidden objects.
Geometric or edge based search
Geometric or edge based search is probably the most popular method. This technique looks for edge patterns within the image. In the training phase, the user can select which edge features are relevant for the object recognition and can combine those to a model for the pattern that needs to be searched. Normally these algorithms are scale and rotation invariant - providing good matches irrespective of orientation and size, and without any significant reduction in speed. CVB ShapeFinder is an example of this approach.
Decision tree based search
Whereas the previous two search techniques usually need only one image to create a search model, the generation of a classifier based on decision trees requires several images per class. The learning algorithm extracts single features out of the images and stores them in a tree structure, also including the concept of negative information such as absence of features. Grouping the single features in a tree structure enables a relatively fast search execution, even with comprehensive models. The search effort does not increase in line with the size of the learning set and can be excellent in the differentiation of two similar patterns. CVB Minos is an example of this approach.
Support vector machines
An advanced method used in vision applications for pattern recognition is the use of support vector machines that were deve loped in the mid 90's. SVMs are generalising classification algorithms that are considered as successors of neural networks, as they offer many advantages in the generation and deployment of the classifier. Support vector machines show their advantages especially in appli cations where objects need to be recognised and classified and where the generation of an analytical search model is not possible with justifiable effort due to the organic nature or complex shape of images that need to be classified together.
Applications such as food grading, gender recognition and vehicle type recognition are all good examples where this technique can be very efficient. This type of tool opens up many possibilities, but it does require a higher level of training to achieve accurate result.
Gender recognition, paper classification, texture recognition and hand written text recogni tion are areas where SVM based tools are capable of achieving accurate results where previous techniques could not. CVB Manto is an example of this approach.
Due to their efficient use of memory and CPU resources and their flexibility, support vector machines were for a long time the most used tool to generate linear classifiers from large amounts of data. Thanks to the continuous development of computers it is now possible to also apply the memory and computational intensive method of the Tikhonov regularisation for generating classifiers in machine vision applications.
At a first glance both methods do not differ much, however, the Tikhonov regularisation offers possibilities that are not - or only with tremendous effort - possible with support vector machines. As an example, using Tikhonov regularisation enables solutions where the learning set from the classifier training undergoes a holdout test to get statistically reliable statements about the performance of the classifier generated - without the need to keep a separate test set.
If the common approach of a two class classification is replaced by a multidimensional system of continuous values, a classification system for a multidimensional regression can be generated that opens up new application areas. Using a 4-dimensional system, it is for example possible, to use an iteration method to detect position, rotation and scale of an object with a precision close to what is possible using geometrical pattern matching algorithms, but with considerably reduced computation time. Using a 6-dimensional system it is possible to estimate affin linear figures, enabling a 3D position and orientation evaluation using a 2D camera image. CVB Polimago is an example of this approach.
Different pattern matching methods
With the progressive entry of new imaging technologies into different markets, the requirements for powerful imaging tools has increased considerably. In the area of pattern matching, a number of different approaches can be found. Whereas in the past a two-dimensional position determination of an object was paramount, new applications now demand additional information about the orientation and size of an object. In addition the spatial position of an object and its relative position to the camera are demanded. Methods for finding the orientation and position of objects are often called pose estimation and present an important basis for pick and place or tracking applications.