Jump to content

Template matching

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by DannyS712 bot (talk | contribs) at 18:54, 11 May 2020 (Task 70: Update syntaxhighlight tags - remove use of deprecated <source> tags). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

This article is about template matching in digital image processing. For template matching in psychology, see Template matching theory.

Template matching[1] is a technique in digital image processing for finding small parts of an image which match a template image. It can be used in manufacturing as a part of quality control,[2] a way to navigate a mobile robot,[3] or as a way to detect edges in images.[4]

The main challenges in the template matching task are: occlusion, detection of non-rigid transformations, illumination and background changes, background clutter and scale changes.[5]

Feature-based approach

The hidden layer outputs a vector that holds classification information about the image and is used in the Template Matching algorithm as the features of the image

Feature-based approach relies on the extraction of image features such, i.e. shapes, textures, colors, to match in the target image or frame. This approach is currently achieved by using Neural Networks and Deep Learning classifiers such as VGG,[6] AlexNet, ResNet. Deep Convolutional Neural Networks process the image by passing it through different hidden layers and at each layer produce a vector with classification information about the image. These vectors are extracted from the network and are used as the features of the image. Feature extraction by using Deep Neural Networks is extremely effective and thus is the standard in state of the art template matching algorithms.[7]

This method is considered more robust and is state of the art as it can match templates with non-rigid and out of plane transformation, it can match with high background clutter and illumination changes.[8][9] [10]

Template-based approach

For templates without strong features, or for when the bulk of the template image constitutes the matching image, a template-based approach may be effective. As aforementioned, since template-based matching may potentially require sampling of a large number of points, it is possible to reduce the number of sampling points by reducing the resolution of the search and template images by the same factor and performing the operation on the resultant downsized images (multiresolution, or pyramid), providing a search window of data points within the search image so that the template does not have to search every viable data point, or a combination of both.

Motion tracking and occlusion handling

In instances where the template may not provide a direct match, it may be useful to implement the use of eigenspaces – templates that detail the matching object under a number of different conditions, such as varying perspectives, illuminations, color contrasts, or acceptable matching object “poses”.[11] For example, if the user was looking for a face, the eigenspaces may consist of images (templates) of faces in different positions to the camera, in different lighting conditions, or with different expressions.

It is also possible for the matching image to be obscured, or occluded by an object; in these cases, it is unreasonable to provide a multitude of templates to cover each possible occlusion. For example, the search image may be a playing card, and in some of the search images, the card is obscured by the fingers of someone holding the card, or by another card on top of it, or any object in front of the camera for that matter. In cases where the object is malleable or poseable, motion also becomes a problem, and problems involving both motion and occlusion become ambiguous.[12] In these cases, one possible solution is to divide the template image into multiple sub-images and perform matching on each subdivision.

Deformable templates in computational anatomy

Further information: Computational anatomy § Dense image matching in computational anatomy

Template matching is a central tool in Computational anatomy (CA). The deformable template model[13] models the space of human anatomies is an orbit under the group action of diffeomorphisms. Template matching arise as a problem in matching the unknown diffeomorphism that acts on the template to match the target image.

Template matching algorithms in CA have come to be called large deformation diffeomorphic metric mapping (LDDMM); there are now LDDMM template matching algorithms for matching landmark points, curves, surfaces, volumes.

Template-based matching explained using cross correlation or sum of absolute differences

A basic method of template matching uses an image patch (template), tailored to a specific feature of the search image, which we want to detect. This technique can be easily performed on grey images or edge images. The cross correlation output will be highest at places where the image structure matches the mask structure, where large image values get multiplied by large mask values.

This method is normally implemented by first picking out a part of the search image to use as a template: We will call the search image S(x, y), where (x, y) represent the coordinates of each pixel in the search image. We will call the template T(x t, y t), where (xt, yt) represent the coordinates of each pixel in the template. We then simply move the center (or the origin) of the template T(x t, y t) over each (x, y) point in the search image and calculate the sum of products between the coefficients in S(x, y) and T(xt, yt) over the whole area spanned by the template. As all possible positions of the template with respect to the search image are considered, the position with the highest score is the best position. This method is sometimes referred to as 'Linear Spatial Filtering' and the template is called a filter mask [citation needed].

Another way to handle translation problems on images using template matching is to compare the intensities of the pixels, using the SAD (Sum of absolute differences) measure.

A pixel in the search image with coordinates (xs, ys) has intensity Is(xs, ys) and a pixel in the template with coordinates (xt, yt) has intensity It(xt, yt ). Thus the absolute difference in the pixel intensities is defined as Diff(xs, ys, x t, y t) = | Is(xs, ys) – It(x t, y t) |.

The mathematical representation of the idea about looping through the pixels in the search image as we translate the origin of the template at every pixel and take the SAD measure is the following:

Srows and Scols denote the rows and the columns of the search image and Trows and Tcols denote the rows and the columns of the template image, respectively. In this method the lowest SAD score gives the estimate for the best position of template within the search image. The method is simple to implement and understand, but it is one of the slowest methods.

Implementation

In this simple implementation, it is assumed that the above described method is applied on grey images: This is why Grey is used as pixel intensity. The final position in this implementation gives the top left location for where the template image best matches the search image. 

minSAD = VALUE_MAX;

// loop through the search image
for ( size_t x = 0; x <= S_cols - T_cols; x++ ) {
    for ( size_t y = 0; y <= S_rows - T_rows; y++ ) {
        SAD = 0.0;

        // loop through the template image
        for ( size_t j = 0; j < T_cols; j++ )
            for ( size_t i = 0; i < T_rows; i++ ) {

                pixel p_SearchIMG = S[y+i][x+j];
                pixel p_TemplateIMG = T[i][j];
		
                SAD += abs( p_SearchIMG.Grey - p_TemplateIMG.Grey );
            }

        // save the best found position 
        if ( minSAD > SAD ) { 
            minSAD = SAD;
            // give me min SAD
            position.bestRow = y;
            position.bestCol = x;
            position.bestSAD = SAD;
        }
    }
    
}

One way to perform template matching on color images is to decompose the pixels into their color components and measure the quality of match between the color template and search image using the sum of the SAD computed for each color separately.

Speeding up the process

In the past, this type of spatial filtering was normally only used in dedicated hardware solutions because of the computational complexity of the operation,[14] however we can lessen this complexity by filtering it in the frequency domain of the image, referred to as 'frequency domain filtering,' this is done through the use of the convolution theorem.

Another way of speeding up the matching process is through the use of an image pyramid. This is a series of images, at different scales, which are formed by repeatedly filtering and subsampling the original image in order to generate a sequence of reduced resolution images.[15] These lower resolution images can then be searched for the template (with a similarly reduced resolution), in order to yield possible start positions for searching at the larger scales. The larger images can then be searched in a small window around the start position to find the best template location.

Other methods can handle problems such as translation, scale, image rotation and even all affine transformations.[16][17][18]

Improving the accuracy of the matching

Improvements can be made to the matching method by using more than one template (eigenspaces), these other templates can have different scales and rotations.

It is also possible to improve the accuracy of the matching method by hybridizing the feature-based and template-based approaches.[19] Naturally, this requires that the search and template images have features that are apparent enough to support feature matching.

Similar methods

Other methods which are similar include 'Stereo matching', 'Image registration' and 'Scale-invariant feature transform'.

Examples of use

Template matching has various applications and is used in such fields as face recognition (see facial recognition system) and medical image processing. Systems have been developed and used in the past to count the number of faces that walk across part of a bridge within a certain amount of time. Other systems include automated calcified nodule detection within digital chest X-rays.[20] Recently, this method was implemented in geostatistical simulation which could provide a fast algorithm.[21]

See also

References

  1. ^ R. Brunelli, Template Matching Techniques in Computer Vision: Theory and Practice, Wiley, ISBN 978-0-470-51706-2, 2009 ([1] TM book)
  2. ^ Aksoy, M. S.; Torkul, O.; Cedimoglu, I. H. (2004). "An industrial visual inspection system that uses inductive learning". Journal of Intelligent Manufacturing. 15 (4): 569–574. doi:10.1023/B:JIMS.0000034120.86709.8c.
  3. ^ Kyriacou, Theocharis, Guido Bugmann, and Stanislao Lauria. "Vision-based urban navigation procedures for verbally instructed robots." Robotics and Autonomous Systems 51.1 (April 30, 2005): 69-80. Expanded Academic ASAP. Thomson Gale.
  4. ^ WANG, CHING YANG, Ph.D. "EDGE DETECTION USING TEMPLATE MATCHING (IMAGE PROCESSING, THRESHOLD LOGIC, ANALYSIS, FILTERS)". Duke University, 1985, 288 pages; AAT 8523046
  5. ^ Talmi, Itamar; Mechrez, Roey; Zelnik-Manor, Lihi (2016-12-07). "Template Matching with Deformable Diversity Similarity". arXiv:1612.02190 [cs.CV].
  6. ^ "Preprint repository arXiv achieves milestone million uploads". Physics Today. 2014. doi:10.1063/pt.5.028530. ISSN 1945-0699.
  7. ^ Zhang, Richard; Isola, Phillip; Efros, Alexei A.; Shechtman, Eli; Wang, Oliver (2018-01-11). "The Unreasonable Effectiveness of Deep Features as a Perceptual Metric". arXiv:1801.03924 [cs.CV].
  8. ^ Talmi, Mechrez, Zelnik-Manor (2016). "Template Matching with Deformable Diversity Similarity". arXiv:1612.02190 [cs.CV].{{cite arXiv}}: CS1 maint: multiple names: authors list (link)
  9. ^ Li, Yuhai, L. Jian, T. Jinwen, X. Honbo. “A fast rotated template matching based on point feature.” Proceedings of the SPIE 6043 (2005): 453-459. MIPPR 2005: SAR and Multispectral Image Processing.
  10. ^ B. Sirmacek, C. Unsalan. “Urban Area and Building Detection Using SIFT Keypoints and Graph Theory”, IEEE Transactions on Geoscience and Remote Sensing, Vol.47 (4), pp. 1156-1167, April 2009.
  11. ^ Luis A. Mateos, Dan Shao and Walter G. Kropatsch. Expanding Irregular Graph Pyramid for an Approaching Object. CIARP 2009: 885-891.
  12. ^ F. Jurie and M. Dhome. Real time robust template matching. In British Machine Vision Conference, pages 123–131, 2002.
  13. ^ Christensen, G.E.; Rabbitt, R.D.; Miller, M.I. (October 1996). "Deformable template model using large deformation kinematics". IEEE Transactions on Image Processing. 5 (10): 1435–1447. doi:10.1109/83.536892. PMID 18290061.
  14. ^ Gonzalez, R, Woods, R, Eddins, S "Digital Image Processing using Matlab" Prentice Hall, 2004
  15. ^ E. H. Adelson, C. H. Anderson, J. R. Bergen, P. J. Burt and J. M. Ogden, Pyramid methods in image processing http://web.mit.edu/persci/people/adelson/pub_pdfs/RCA84.pdf
  16. ^ Yuan, Po, M.S.E.E. "Translation, scale, rotation and threshold invariant pattern recognition system". The University of Texas at Dallas, 1993, 62 pages; AAT EP13780
  17. ^ H. Y. Kim and S. A. Araújo, "Grayscale Template-Matching Invariant to Rotation, Scale, Translation, Brightness and Contrast," IEEE Pacific-Rim Symposium on Image and Video Technology, Lecture Notes in Computer Science, vol. 4872, pp. 100-113, 2007.
  18. ^ Korman S., Reichman D., Tsur G. and Avidan S., "FAsT-Match: Fast Affine Template Matching", CVPR2013.
  19. ^ C. T. Yuen, M. Rizon, W. S. San, and T. C. Seong. “Facial Features for Template Matching Based Face Recognition.” American Journal of Engineering and Applied Sciences 3 (1): 899-903, 2010.
  20. ^ Ashley Aberneithy. "Automatic Detection of Calcified Nodules of Patients with Tuberculous". University College London, 2007
  21. ^ Tahmasebi, P., Hezarkhani, A., Sahimi, M., 2012, Multiple-point geostatistical modeling based on the cross-correlation functions, Computational Geosciences, 16(3):779-79742.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Template_matching&oldid=956146351"