Template Matching in Digital Images with Swarm Intelligence

Template Matching in Digital Images with Swarm Intelligence

Hugo Alberto Perlin, Chidambaram Chidambaram, Heitor Silvério Lopes
DOI: 10.4018/978-1-4666-5888-2.ch596
(Individual Chapters)
No Current Special Offers

Chapter Preview



Template Matching

Given a I1 × I2 image, called landscape, and a P1 × P2 image patch, called pattern, the template matching consists in finding the precise location (x,y) of the pattern inside the landscape image. Here, it is assumed that the pattern size is smaller than the landscape image.

A simple approach to do this is using a sliding window along the landscape image. The process basically consists in sliding a window, of the same size of the example pattern, over every pixel of the landscape image, and extracting a patch. This patch is then compared with the example pattern using a similarity measure. Figure 1 shows an example of this process. The window with the highest similarity value is said the matching point. Several similarity measures can be used, and the common choices are the sum of the absolute differences and the sum of the squared differences.

Figure 1.

Example of the sliding window approach for the pattern detection problem using template matching


Most common template matching approaches restrict the search in a 2D plane, in this case translation in x and y axis. This restriction occurs mainly to reduce the computational effort demanded to solve the problem.

Besides the translations of the pattern in the 2D plane, other image transformations could occur, such as scale (translation in the z axis) and rotation. Consequently, the template matching problem can be more properly defined as finding a 4-tuple (x, y, s, Θ), where x and y are the center coordinates of the pattern, s, is the scale factor, and Θ, the rotation angle (Gonzales, 2009).

Key Terms in this Chapter

Swarm Intelligence: A discipline of Computational Intelligence inspired by the behavior analysis of groups of animals.

Heuristic: An approach to solve a hard problem, but there are no guaranties that the optimal solution is achieved.

Global Optimization: The class of optimization problem where the entire search is possible to be visited.

Particle Swarm Optimization (PSO): An optimization algorithm inspired by school of fish and flocks of birds, which use the power of collective collaboration to solve complex problems. Suitable to solve global continuous optimization problems.

Search Space: The set of all possible solutions to a determined problem. Generally, the search space is multi-dimensional, as the cost function.

Pattern Detection: An image processing/computer vision problem, which aims to determine the presence or not of a pattern in an image. The pattern could be an object, face, texture, shape, and others.

Template Matching: An approach to solve pattern detection, where a template is used as a basis to find something similar based in some kind of measurement.

Artificial Bee Colony (ABC): An optimization algorithm inspired by bee colonies. Use the same hierarquical distribution and behavior of the bees in the food search process in nature to solve computational problems.

Complete Chapter List

Search this Book: