# An Improved Ant Colony Matching by Using Discrete Curve Evolution

Younes Saadi, Eka Novita Sari, Tutut Herawan

► To cite this version:

Younes Saadi, Eka Novita Sari, Tutut Herawan. An Improved Ant Colony Matching by Using Discrete Curve Evolution. 2nd Information and Communication Technology - EurAsia Conference (ICT-EurAsia), Apr 2014, Bali, Indonesia. pp.248-256, 10.1007/978-3-642-55032-4_24. hal-01397203

HAL Id: hal-01397203

https://inria.hal.science/hal-01397203

Submitted on 15 Nov 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# An Improved Ant Colony Matching by using Discrete Curve Evolution

Younes Saadi¹, Eka Novita Sari², and Tutut Herawan¹

¹Department of Information System
University of Malaya
50603 Pantai Valley, Kuala Lumpur, Malaysia
²AMCS Research Center
Yogyakarta, Indonesia

younessaadi@gmail.com, eka@amcs.co, tutut@um.edu.my

**Abstract.** In this paper we present an improved Ant Colony Optimization (ACO) for contour matching, which can be used to match 2D shapes. Discrete Curve Evolution (DCE) technique is used to simplify the extracted contour. In order to find the best correspondence between shapes, the match process is formulated as a Quadratic Assignment Problem (QAP) and resolved by using Ant Colony Optimization (ACO). The experimental results justify that Discrete Curve Evolution (DCE) performs better than the previous Constant Sampling (CS) technique which has been selected for the ACO matching.

**Keywords:** Ant Colony Optimization; Quadratic assignment problem; Discrete curve evolution; Contour matching.

## 1 Introduction

Nowadays, shape analysis has become an important topic in computer vision. It has been widely adopted in many applications of computer graphics. In particular, shape matching one of the fundamental techniques of shape analysis. It plays a primordial role in shape retrieval, recognition and classification, and medical registration [1]. Shape matching has reached a state of maturity in which many real products based on shape matching are commercialized in different areas [2]. In the commercial domain, shape matching methods are being used to retrieve and classify images, for personal and institutional needs like security and military. In the medical domain, shape matching is used in radiology to diagnose and to assess medical images to determine the progress and the suitable treatment options.

Shape matching is application dependent. Different applications may have different requirements on invariance and tolerance to noise, distortion, blur, transformation, scale and orientation. Thus, it is difficult to design a universal method which is suitable for all applications. Nowadays, many techniques have been proposed but most of them only focus on the applications where shape is invariant to transformation.

Based on the representation techniques, shape matching techniques can be classified into two categories: contour based matching and region based matching [3]. This research is focusing on contour based matching techniques, in which only the information located on the shape contour is explored. Majority of the past researches have concentrated on how to achieve a meaningful correspondence. On the other hand,
some researches focused on improving representation methods of a contour in such a
way that the resulted contour could be used to extract meaningful information. This is
called simplification, evolution or smoothing in some sources [3] [4] [5] [6] [7].

However, challenges still remain. The first challenge is the invariance [8] [9]. Since
shape in many applications is often discussed based on the property of invariance,
shape matching is expected to be invariant to transformations such as example transla-
tion, scale and orientation. The second challenge is tolerance as noise, blur, crack and
deformation are usually introduced when the shape of an object is extracted from an
image [10]. In this case, a shape matching is required to be robust to these imperfec-
tions.

Moreover, in contour based matching, the points along the contours as a bipartite
graph can be figured out and formulated as a QA. This is considered as an NP-hard
problem [11]. In order to find an acceptable solution, heuristics1s techniques are often
used. The main idea is to compute the mapping between two contours by minimizing
the global dissimilarity. Many research studies have been proposed. For example,
Hungarian method uses the simple greedy matching [12], and COPAP [13] takes into
account the order preserving. However, the main drawback of these techniques is the
omission of proximity information measurement between feature points on the same
shape contour. For this reason, Kaick [14] proposed an Ant Colony Optimization
(ACO) approach based on incorporating proximity into an optimization framework.
However, the huge number of points incorporated in the correspondence makes the
matching more complex and less accurate [11]. A modified ACO matching approach
has been proposed by Ruberto and Morgera [11] based on genetic algorithm; only
dominant points are used instead of the sampling distribution of contour points, which
improves the correspondence accuracy and reduces the complexity.

Generally, speaking a heuristic is a method that achieves good (but not necessarily
optimal) results at low expense. However, which results are to be considered good
heavily depends on the application at hand. Analysing contour matching we can fig-
ure out the points along the contour as a bipartite graph, which can be formulated as a
Quadratic Assignment (QA). This is one of the NP-hard problems [15]. Finding an
optimal solution for such problem seems difficult by using conventional methods.
Heuristics methods are used to find an acceptable solution for such cases.

It is important to mention the Hungarian method as one of the well-studied methods
in this context. In fact it is based on solving the complexity which is a part of the
combinatorial optimization solved by using Iterative Closest Point (ICP) scheme [16].
Following the requirements of the applications, many versions of heuristics approach-
es have been proposed. A review about correspondence introduced in [17] shows
clearly the importance of heuristic methods to solve complexity related to shape
matching issues.

In this paper, an improved ACO matching approach based on Discrete Curve Evolu-
tion (DCE) was proposed. In order to reduce the number of contour points incorpo-
rated in the correspondence, a polygonal approximation proposed previously by
Latecki and Lakamper [18] was selected to simplify the extracted contour. Mainly, it
simplifies the contour by neglecting distortions while at the same time preserving the
perceptual appearance at a level sufficient for object recognition. To test the effec-
tiveness of our approach, an MPEG-7 subset described by Ruberto and Morgera [11]
was used to test shape retrieval considering noise and distortions effect. The results
were also compared with the previous work of ACO matching by Ruberto and Mor- gera [11].

## 2 Proposed Method

The structure of the proposed method is shown in (Fig. 1). It operates into four stages. In the first stage the contour is traced by using a basic Matlab function. In the second stage the extracted contours are approximated by using Discrete Curve Evolution (DCE) which is proposed previously by Latecki and Lakamper [18]. After that, Ant Colony Optimization proposed previously [14] is used to compute the correspondence in the third stage. Finally in the fourth stage, the Euclidean distance has been selected to compute the dissimilarity between shapes according to the resulted matrix of correspondence.

<figure><img src="image_2.png" /><figcaption>Fig. 1. Method structure</figcaption></figure>

After analyzed the shortcoming of polygonal evolution methods, discrete curve evolution [18] has been selected to be used in our approach (See Figures 2, 3, and 4). The main reason is that this method allows the user to control the degree of evolution according to the human judgment. In every iteration, a pair of consecutive line segments s1, s2 is replaced with a single line related to the endpoints of s1U s2. The substitution is calculated according to the relevance value K given by the following equation:

$$K(s_1, s_2) = \frac{\beta(s_1, s_2)l(s_1)l(s_2)}{l(s_1)+l(s_2)} \quad (1)$$

$\beta(s_1, s_2)$ is the turn angle at the common vertex between s1 and s2. $l$ is the length function normalized with respect to the total length of a polygonal curve C.
<figure><img src="image_3.png" /><figcaption>Fig. 2. A series of polygonal evolution</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 3. Two simplified contours</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 4. ACO matching after DCE</figcaption></figure>

A new matching algorithm based on ant colony optimization is described previously [14]. It consists of taking in consideration the proximity measured between feature points on the same shape (Fig. 5). The matching is formulated as a two sets of points I and J where the ants cross these two sets doing a complete tour. All the movements produce a collection of possible paths between the two sets. During building of these paths Ants release the pheromone with different amounts for each possible path. A bigger amount of pheromone on a path means that it is more eligible in term of cost of correspondence. The traversing from a vertex i ∈ I to a vertex j ∈ J is given by the equation below [11].

## 2.1 Edge Probability

$$p_{ij}^{k} = \frac{\alpha \tau_{ij} + (1-\alpha) \eta_{ij}}{\sum_{l \in N_i} [\alpha \tau_{il} + (1-\alpha) \eta_{il}]} \quad (2)$$

The pheromone accumulated on the edge (i, j) is quantified by $τ_{ij}$, $η_{ij}$ indicates the desirability (or probability) of traversing (i, j) based on heuristic information, $N_i = \{l \in J : (i, l) \in E\}$ is the immediate neighbourhood of vertex i. The parameter $0 \le \alpha \le 1$ regulates the influence of pheromones over heuristic information. After a complete tour of the ants, an ACO iteration, the cost of solutions is computed as defined in second.

Pheromones are updated at the end of ACO iteration. First, pheromones are evaporated at n constant pheromone rate [11] $ρ$, $0 \le ρ \le 1$.
<figure><img src="image_6.png" /><figcaption>Fig. 5.ACO matching before DCE</figcaption></figure>

## 2.2 Pheromone Evaporation

$$ \tau_{ij} \leftarrow (1-\rho)\tau_{ij}, \qquad (3) $$

where $\rho$ is the pheromone evaporation rate and the new pheromone deposition on the edges that were traversed by the ants is regulated by pheromone deposition:

$$ \tau_{ij} \leftarrow \tau_{ij} + \sum_{k=1}^{m} \Delta\tau_{ij}^{k}, \qquad (4) $$

where $\Delta\tau_{ij}^k$ is the amount of pheromone that an ant $k$ has deposited on the edge $(i, j)$.

## 2.3 Cost Function

The formulation of the problem is done by a QAP. When augmenting the shape descriptor $R$ with proximity information. The general objective function is in the form:

$$ \text{QAP}(\pi, R, I, J) = (1-\nu)S(\pi, R, I, J) + \nu\chi(\pi, I, J), \qquad (5) $$

where $0 \le \nu \le 1$ is used to control parameter between $S$ and the proximity $\chi$ and the arguments $I, J$ represents the two points sets, $\pi$ a mapping such that to a point of I correspondents a point in $J$ and $R$ the set of shape descriptors. The form $S$ and $\chi$ is detailed in [11].
Input data:

Query shape and stored shapes: An ordered set of shape contours.

Output data:

Matrix of dissimilarity between the query shapes and all the stored
shapes

1. for i= 1 to M do {M number of query shapes}

2. Read a query shape $S_i$

3. Contour tracing of shape $S_i$

4. Apply DCE

5. end for

6. for j = 1 to N do {N number of stored shapes}

7. Read a stored shape $S_j$

8. Contour tracing of shape $S_j$

9. Apply DCE

10. End for

11. for i= 1 to M do

12. for j = 1 to N do

13. Compute the best correspondence *bc* between $S_i$ and $S_j$ contours

14. Compute the degree of dissimilarity

15. end for

15. for each class sort the dissimilarity degree of each pairwise (query-stored) ascending where the first retrieved is the one with a min value.

3 Experimental Results

In order to test the effectiveness of our approach, which is based on DCE and ACO matching, an MPEG-7 subset (Fig. 6) is used to test shape retrieval and contour matching issues [11]. The database constitutes of 18 classes, each class contains 11 items plus 18 query shapes selected from each class. Basically this database assesses universal measures that are translation rotation and scaling invariant. However, in our scope we are not interested in rotation since we are using the classic shape context as a shape descriptor. For this reason we are using a set of parameters consist of 1 as number of ants and 100 as number of iterations each ants make in optimization process. The experiment is executed on a Matlab environment (Windows 32 OS) running on Intel Pentium 2.2 GHz.

As stated in section 2, DCE reduce the number of points located on the contour. Af-
ter the evolution, ACO is convoked to establish best possible correspondence between
the approximated contours.

We compared our approach to retrieval similar objects by using Constant Sampling
points (CS) [11]. It is important to mention that comparison is not possible with Dom-
inant Points (DP) approach proposed by Ruberto and Morgera since it is based on
rotational descriptor, which is not the case of our research. Table 1 shows the accura-
cy rate for each class of our method compared to the CS approach. In Table 1 we
show the experiments made to MPEG-7 subset with CS and the proposed method.
Table 1 also introduces a comparison with 18 classes for both CS and the proposed
method.

It is important to notice the highly performance affected by DCE compared to CS as
a result of the lower number of points incorporated in the matching. There is depend-
ence between lower accuracy and the smoothing of the contour. However th distribu-
tion of dominant points along the contour plays an important role to preserve the orig-
final frame of the shape and thus increasing the matching accuracy. The results obtained with classes 5 and 7 as shown in Table 1 by constant points CS is due to the nature of CS simplification.

Although the descriptor used in our approach is not invariant to rotation, the global average shows that our method performs better than CS. Thus the advantage of incorporating DCE and proximity using ACO is demonstrated.

<figure><img src="image_7.png" /><figcaption>Fig. 6. MPEG-7 dataset [4]</figcaption></figure>

<table><caption>**Table 1. Retrieval rates of different MPEG-7 CE-Shape-1 Part B data set [11]**</caption><thead><tr><th></th><th>Class</th><th>Proposed Method</th><th>CS</th></tr></thead><tbody><tr><td rowspan="14">Average accuracy for each class</td><td>1</td><td>0.9166</td><td>0.6909</td></tr><tr><td>2</td><td>1.0000</td><td>0.9273</td></tr><tr><td>3</td><td>0.9166</td><td>0.8818</td></tr><tr><td>4</td><td>0.8333</td><td>0.7273</td></tr><tr><td>5</td><td>0.9166</td><td>0.9909</td></tr><tr><td>6</td><td>1.0000</td><td>1.0000</td></tr><tr><td>7</td><td>0.9266</td><td>0.9909</td></tr><tr><td>8</td><td>0.9100</td><td>0.8818</td></tr><tr><td>9</td><td>1.0000</td><td>0.9727</td></tr><tr><td>10</td><td>1.0000</td><td>0.9455</td></tr><tr><td>11</td><td>0.9166</td><td>1.0000</td></tr><tr><td>12</td><td>1.0000</td><td>1.0000</td></tr><tr><td>13</td><td>0.5000</td><td>0.6818</td></tr><tr><td>14</td><td>1.0000</td><td>1.0000</td></tr></tbody></table>
<table><tr><td>15</td><td>0.9166</td><td>0.8545</td></tr><tr><td>16</td><td>1.0000</td><td>1.0000</td></tr><tr><td>17</td><td>0.5833</td><td>0.7545</td></tr><tr><td>18</td><td>0.6666</td><td>0.5636</td></tr><tr><td>Global Average</td><td><b>0.8890</b></td><td>0.8854</td></tr></table>

# 4 Conclusion

In this study, an improved ACO matching algorithm based on curve evolution has been introduced. The main challenge to the contour matching was to find the best correspondence between the huge numbers of points along the contours incorporated in the matching. Whenever the number of points participated in the matching increased, the complexity of matching also increased which directly affected the performance of the matching process. A solution based on dominant points has been proposed by Ruberto and Morgera [11]. The obtained results showed the efficiency of our approach.

This research produced an improved ACO matching based on curve evolution. Before starting matching, a proposed DCE was applied in order to simplify the shape contour. This reduced the contour points incorporated along the contour. The DCE algorithm can be personalized according to the number of iterations required. The iterations can be predefined to approximate the shape contour. Instead of the original ACO, the improved ACO matching as shown to be more accurate although the used descriptor is not invariant to rotation.

This does not mean, that heuristics methods might be useful for all matching applications, but the applicability of such methods is only related to: firstly, the domain of application for example sometimes in image registration it is enough to get an approximated matching to obtain the abnormalities. Secondly the applicability depends the requirements of the matching for example in some cases considering proximity between the points along the contour is compulsory which allow the usage of heuristic methods as a key for the solution.

**Acknowledgments.** This work is supported by University of Malaya High Impact Research Grant no vote UM.C/625/HIR/MOHE/SC/13/2 from Ministry of Higher Education Malaysia.

# References

1. Tsapanos, N., Tefas, A., Nikolaidis, N., & Pitas, I.: Shape matching using a binary search tree structure of weak classifiers. Pattern Recognition, 45(6), pp. 2363–2376. (2012)

2. Aaron, S. K., Christopher, R. I., & Sharon, C. G.: Characterizing complex particle morphologies through shape matching: descriptors, applications, and algorithms. Journal of Computational Physics, 230(17), p. 20 (2011)

3. Luciano, D. F. C. &Roberto, M. C. J.: Shape Classification and Analysis: Theory and Practice. 2nd Ed. CRC Press (2009)

4. Kolesnikov, A.: ISE-bounded polygonal approximation of digital curves. Pattern Recognition Letters. Volume 33, Issue 10, 15. Pages 1329–1337 (2012)
5. Parvez, M. T. & Sabri, A. M.: Polygonal approximation of digital planar curves through adaptive optimizations. Pattern Recognition, Volume 31, Issue 13, Pages 1997–2005 (2010)

6. Poyato, A. C., Cuevas, F. J. M., Carnicer, R. M., & Salinas, R. M.: Polygonal approximation of digital planar curves through break point suppression. *Pattern Recognition*, Volume 43, Issue 1, Pages 14–25 (2010)

7. Parvez, M. T. & Sabri, A. M.: Polygonal Approximation of Planar Curves Using Triangular Suppression. Proceeding Of International Conference on Information Science, Signal Processing and their Applications (2010)

8. Aaron, S. K., Christopher, R. I., & Sharon, C. G.: Characterizing complex particle morphologies through shape matching: descriptors, applications, and algorithms. Journal of Computational Physics, Volume 230, Issue 17, Pages 6438-6463 (2011)

9. de Sousa, de S., Artner, N.M., Kropatsch, W.G.: On the Evaluation of Graph Centrality for Shape Matching Graph-Based Representations in Pattern Recognition. Lecture Notes in Computer Science Volume 7877, pp 204-213 (2013)

10. Li, G., Kim, H., Tan, J.K., Ishikawa, S.: 3D Organic Shape Correspondence Using Spherical Conformal Mapping, World Congress on Medical Physics and Biomedical Engineering May 26-31, 2012, Beijing, China IFMBE Proceedings Volume 39, pp 943-946 (2013)

11. Ruberto, C.D., Morgera, A.: ACO contour matching: a dominant point approach. 4th International Congress on Image and Signal Processing. Vol 03, pp. 1391 - 1395 (2012)

12. Papadimitriou, C., and Stieglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Prentice hall, ISBN:0-13-152462-3 (1982)

13. Scott, C. & Nowak, R. D.: Robust contour matching via the order-preserving assignment problem. IEEE Trans. On Image Processing, 15(7), pp. 1831–1838 (2006)

14. Kaick, O.V., Hammarneh, G., Zhang, H., Wighton, P.: Contour Correspondence Via Ant Colony Optimization. Proc, 15 Pacific Graphic 2007, United States, pp. 271–280 (2007)

15. Zhu, X.: Shape Matching Based on Ant Colony Optimization, ICIC 2008, CCIS 15, Springer-Verlag. pp 101–108, 2008. (2008)

16. Rusinkiewicz, S. & Levoy, M.: Efficient Variants of the ICP Algorithm. 3-D Digital Imaging and Modeling. Third International Conference IEEE, pp145 – 152 (2001)

17. Kaick, O.V., Zhang, H., Hamarneh, G., Cohen-Or, D.: A survey on shape correspondence. Computer graphics forum, Vol 30, Issue 6, pp 1681–1707 (2011).

18. Latecki, L.J., Lakämper, R.: Shape Similarity Measure Based on correspondence of visual parts. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 22, NO.10, pp 1185-1190 (2000)