Tracking Patterns with Particle Swarm Optimization and Genetic Algorithms

Tracking Patterns with Particle Swarm Optimization and Genetic Algorithms

Yuri Marchetti Tavares (Brazilian Navy, Rio de Janeiro, Brazil), Nadia Nedjah (Universidade do Estado do Rio de Janeiro, Rio de Janeiro, Brazil) and Luiza de Macedo Mourelle (Universidade do Estado do Rio de Janeiro, Rio de Janeiro, Brazil)
Copyright: © 2017 |Pages: 16
DOI: 10.4018/IJSIR.2017040103
OnDemand PDF Download:
List Price: $37.50


The template matching is an important technique used in pattern recognition. The goal is to find a given pattern, of a prescribed model, in a frame sequence. In order to evaluate the similarity of two images, the Pearson's Correlation Coefficient (PCC) is used. This coefficient is calculated for each of the image pixels, which entails an operation that is computationally very expensive. In order to improve the processing time, this paper proposes two implementations for template matching: one using Genetic Algorithms (GA) and the other using Particle Swarm Optimization (PSO) considering two different topologies. The results obtained by the proposed methodologies are compared to those obtained by the exhaustive search in each pixel. The comparison indicates that PSO is up to 236x faster than the brute force exhausted search while GA is only 44x faster, for the same image. Also, PSO based methodology is 5x faster than the one based on GA.
Article Preview


With the development and enhancement of sensors and intelligent equipment capable of capturing, storing, editing and transmitting images, the acquisition of information, which is extracted from images and videos, became an important research area. In the defense and security fields, this kind of research is very relevant to recognition and tracking targets in image sequences. It can provide solutions for the design of effective surveillance systems (Narayana, 2007), monitoring systems, fire control (Ali, Kausar & Khan, 2009), guidance equipment (Choi & Kim, 2014), navigation (Forlenza, Fasano, Accardo & Moccia, 2012), remote biometrics (Benfold & Reid, 2011) and guided weapons (Olson & Sanford, 1999), among many others.

In general, a pattern is an arrangement, or a collection of objects that are similar, and is usually identified by its element’s disposition (Gonzalez, 2008). It can also be defined as the opposite of chaos, an entity, loosely defined, in which we can put a name (Watanabe, 1985).

One of the most used techniques for finding and tracking patterns in images is generally identified as template matching (Ahuja & Tuli, 2013; Mahalakshmi, Muthaiah & Swaminathan, 2012).

Among the methods used during the evaluation of the matching process, the correlation is very known and widely used. The task consists basically to find the location of a small image, considered as a template, inside a larger image. This task is computationally very expensive, especially when using large templates and extensive sets of images (Sharma & Kaur, 2013).

Figure 1 shows an example of image together with the corresponding correlation computed at each pixel of that image. It can be observed that the correlation graph has a well-defined peak in the center of the desired pattern, which is highlighted by the square.

Figure 1.

Correlation in the frame aircraft

The Genetic Algorithms (GA) is a widely-used method for solving complex engineering and scientific NP-hard problems, including those that fall in the optimization category, automatic programming and machine learning (Mitchell, 1995).

Particle Swarm Optimization (PSO) is used to solve optimization problems that fall in the category of complex non-linear functions. This method provides a high convergence, great simplicity and neat organization (Siciliano, 2007).

This paper proposes the use of GA and PSO, considering two topologies, as a possible ways to reduce the processing time as well as the computational effort to find the maximum point of correlation, considering a given main image and the desired pattern. Furthermore, a performance comparison of the both techniques in solving the problem is carried out, in order to select the best.

For this, Related Works Section presents some related works; in Correlation Section the correlation concept is defined; in Genetic Algorithms Section and Particle Swarm Optimization Section the two used techniques are briefly described; in Methodology Section the methodology and the system implementation are explained; Results Section presents the results and, finally, Conclusion Section concludes the work.

An example of correlation utilization for tracking patterns is verified in (Esteves, 2008). Therein, a simulation of autonomous air navigation by an Unmanned Aerial Vehicle is performed. The cross correlation between satellite images and aerial images, obtained by a simulated camera is used to correct the estimated position of the vehicle.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 9: 4 Issues (2018): 1 Released, 3 Forthcoming
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing