Sage Journals: Discover world-class research

Abstract

Shape recognition is a classically difficult problem because of the affine transformation between two shapes. The current study proposes an affine parameter estimation method for shape recognition based on a genetic algorithm (GA). The contributions of this study are focused on the extraction of affine-invariant features, the individual encoding scheme, and the fitness function construction policy for a GA. First, the affine-invariant characteristics of the centroid distance ratios (CDRs) of any two opposite contour points to the barycentre are analysed. Using different intervals along the azimuth angle, the different numbers of CDRs of two candidate shapes are computed as representations of the shapes, respectively. Then, the CDRs are selected based on predesigned affine parameters to construct the fitness function. After that, a GA is used to search for the affine parameters with optimal matching between candidate shapes, which serve as actual descriptions of the affine transformation between the shapes. Finally, the CDRs are resampled based on the estimated parameters to evaluate the similarity of the shapes for classification. The experimental results demonstrate the robust performance of the proposed method in shape recognition with translation, scaling, rotation and distortion.

Keywords

Shape Recognition Affine Transformation Centroid Distance Ratio Genetic Algorithm Fitness Function

1. Introduction

Shape recognition is one of the most challenging tasks for pattern recognition with affine transformation among different images. The fundamental work of shape recognition is the extraction of affine invariant features that fit the variations in viewpoints. Researchers have proposed many shape descriptors in the past decades, including the Fourier descriptor [1, 2]. Other image processing approaches, such as principal component analysis (PCA) [3, 4], independent component analysis (ICA) [5, 6], Wavelet Transformation [7, 8], and Neural network [9, 10], have been used to build representations of shapes. Mei and Androutsos [4] proposed two affine-invariant shape descriptors, namely, the ICA-Fourier and the PCA-Fourier descriptors, which gave satisfying performances in shape-based silhouette image retrieval. Bala and Cetin [8] developed an affine-invariant function for object recognition based on the decimated wavelet transform, which decreased computational complexity without decreasing recognition performance. The blind source separation (BSS) [11] is an efficient algorithm because of its valuable characteristics in extracting affine invariants from object boundaries.

More research has recently focused on multiple-resolution techniques to improve accuracy and robustness in response to the influences of noise and occlusion [12 –14]. Thourn, Kitjaidure and Kondo proposed a new multi-resolution technique in the spatial domain called the multi-level of barycentre contour [12], which can reduce noises caused by deformation and distortion. However, the multi-level of barycentre contour still contains some defects. First, since the triangular area of two adjacent boundary points and the barycentre are used as a shape descriptor for matching, errors occur when the corresponding points are not found in both images with high distortions. In addition, the multi-level of barycentre contour might not work properly if the contour is broken because of occlusion. Lihua Zhang, Wenli Xu and Cheng Chang proposed an affine point pattern matching method based on a genetic algorithm [15], which was dependent on the two point sets corresponding to two affine transformed images. Since the proper matching points are difficult to extract, this method is limited with respect to its real applications.

Considering that lots of effective contour extraction algorithms can be applied, the shape of the target is more likely to be achieved than the point set. Thus, our research focuses on the shape identification. The basic idea is: Firstly, the affine transformation parameters between two shapes are estimated. Then, the matching points in the two shapes are directly obtained according to the transform parameters. Finally, the shapes are classified based on the degree of similarity between the two matching point sets. Nevertheless, estimating the affine parameters among the shapes remains a challenge. T. IZUMI et al. proposed a method using a Karhunen–Loeve (KL) expansion, spatial correlation, and a correction equation based on Taylor's expansion of the transform to address the problem described above [16]. Trace transform is also used to estimate the parameters between two images affinely distorted from each other [17].

In our study, the affine parameters are estimated based on a genetic algorithm (GA). The centroid distance ratios (CDRs) of any two opposite contour points to the barycentre are obtained as the representation of the shapes, which are invariant to the affine transformation, to construct the fitness function for the GA. The parameters derived from the iteration results of the GA are regarded as real affine parameters for building the corresponding point pairs. Furthermore, the same method of similarity evaluation used for the fitness function is used for shape classification.

The remainder of this paper is organized as follows: Section 2 analyses the proposed extraction method of affine-invariant features. Section 3 introduces the details of the affine parameter estimation based on GA, which consists of the constraint condition designation and the fitness function construction. Section 4 presents the experimental results of the proposed algorithm. Finally, section 5 draws some conclusions and discusses future works.

2. Affine invariant features extraction

In this section, the characteristics and the definitions of the parameters of affine transformation are discussed. Then, the concept of CDRs is introduced, and the affine invariant property of CDRs is demonstrated. Finally, the fact that CDRs corresponding to two candidate shapes can be resampled using the affine parameters to construct matching pairs for similarity evaluation is analysed.

2.1 Affine transformation and the definitions of its parameters

The general affine transformation can be mathematically represented as follows:

[\begin{matrix} \tilde{x} \\ \tilde{y} \end{matrix}] = [\begin{matrix} a_{1} & a_{2} \\ a_{3} & a_{4} \end{matrix}] [\begin{matrix} x \\ y \end{matrix}] + [\begin{matrix} b_{1} \\ b_{2} \end{matrix}]

(1)

where $\tilde{x}$ and $\tilde{y}$ are the distorted pixel coordinates via affine transformation, x and y are the pixel coordinates of the original shape, and b₁ and b₂ represent the translation coefficients. According to Wikipedia (see http://en.wikipedia.org/wiki/Affine_transformation), affine transformation is a transformation that preserves straight lines and the ratios of distances. Although an affine transformation preserves the proportions of lines, it does not necessarily preserve the angles or lengths of the lines. This property describes the most general class of transformations. Geometric contraction, expansion, dilation, reflection, rotation, shear, similarity transformations, spiral similarities and translation, including their combinations, are all affine transformations. An affine transformation is similar to a translation followed by a linear transformation. The matrix $[\begin{matrix} a_{1} & a_{2} \\ a_{3} & a_{4} \end{matrix}]$ represents linear transformation coefficients, which can be described as follows:

[\begin{matrix} s_{x} & 0 \\ 0 & s_{y} \end{matrix}] [\begin{matrix} \cos θ & - \sin θ \\ \sin θ & \cos θ \end{matrix}] [\begin{matrix} 1 & s h_{x} \\ s h_{y} & 1 \end{matrix}]

(2)

where S_x and S_y are the scaling parameters, sh_x and sh_y are the shear parameters, and θ is the rotation angle. Thus, a₁, a₂, a₃, and a₄ can be expressed as follows:

\begin{array}{l} a_{1} = s_{x} \cos θ - s_{x} s h_{y} \sin θ \\ a_{2} = s_{x} s h_{x} \cos θ - s_{x} \sin θ \\ a_{3} = s_{y} \sin θ + s_{y} s h_{y} \cos θ \\ a_{4} = s_{y} s h_{x} \sin θ + s_{y} \cos θ \end{array}

(3)

2.2 Definition of CDRs and their affine invariant property

Figure 1 shows two bird shapes that were defined as being affinely related with each other. Points P₀: [^x₀, y₀]^T and $P_{0} : {[x_{0}, y_{0}]}^{T}$ represent the barycentres of the two bird shapes, respectively. The coordinates of the barycentres are defined as the average coordinates of all the contour points as follows:

Figure 1.

Two contour points chosen for CDR computation

x_{0} = \sum_{k} x_{k} / N, \begin{matrix} y_{0} = \sum_{k} y_{k} / N \end{matrix}

(4)

where N is the number of contour points and [x_k, y_k]^T represents the coordinates of any contour point. Contour points ${\tilde{P}}_{1} : {[{\tilde{x}}_{1}, {\tilde{y}}_{1}]}^{T}$ and ${\tilde{P}}_{2} : {[{\tilde{x}}_{2}, {\tilde{y}}_{2}]}^{T}$ in the second shape correspond to points P_{1_:}[x₁, y₁]^T and P_{2_:} [x₂, y₂]^T in the first shape. The centroid distance d_i is the distance between the barycentre and a given boundary point P_i: [x_i, y_i]^T given by

d_{i} = \sqrt{{(x_{i} - x_{0})}^{2} + {(y_{i} - y_{0})}^{2}}

(5)

Similarly, distance ${\tilde{d}}_{i}$ is related to the affine-transformed image. Since ${\tilde{d}}_{i}$ is different from d_i, the CDRs can be defined as the representations of the shapes because of their affine invariant properties.

\begin{array}{l} C D R (P_{1}, P_{2}) = d_{1} / d_{2} \\ C D R ({\tilde{P}}_{1}, {\tilde{P}}_{2}) = {\tilde{d}}_{1} / {\tilde{d}}_{2} \end{array}

(6)

Suppose points P₁ and P₂ are located opposite to the barycentre P₀, and these three points are located on a straight line. According to the properties of affine transformation mentioned in section 2.1, points ${\tilde{P}}_{1}$ , ${\tilde{P}}_{2}$ , and ${\tilde{P}}_{0}$ in the second shape must be collinear. Thus, the following equation can be deduced:

d_{1} / d_{2} = {\tilde{d}}_{1} / {\tilde{d}}_{2}

(7)

Equation (7) shows that the CDR derived from two opposite contour points to the barycentre will be invariant to affine transformation, and thus, it can be adopted as a feature of shape representation.

2.3 Principle of affine parameter estimation

Although CDRs are invariant to affine transformation, some issues need to be further analysed for real applications. As mentioned above, the equivalent relations of equation (7) are constructed under the following constraints:

1)
Points P₁ and P₂ are located opposite the barycentre P₀.
2)
Points ${\tilde{P}}_{1}$ and ${\tilde{P}}_{2}$ are affine-transformed points of P₁ and P₂.

The original point of the coordinate system can be translated to the barycentre P₀ to address the first problem. Thus, the azimuth angles of P₁ and P₂ will have a difference of 180°. This property can be applied to construct all pairs of corresponding points for computing CDRs. On the other hand, the second problem is difficult to solve because the affine parameters between the candidate shapes cannot be obtained directly.

Fortunately, the equivalent relation of CDRs expressed in equation (6) can be applied to estimate the affine parameters, as shown in Figure 2.

Figure 2.
Affine parameter estimation method based on GA

First, multiple contour points along the azimuth angle of the first shape are selected and then the CDRs are computed. More CDRs related to the contour points in the second shape are computed with minor angle intervals to match the selected contour points with the azimuth angles of the affine-transformed points. Then, a GA is adopted to find the optimal affine transformation parameters. For a group of given affine parameters, the affine-transformed coordinates related to the selected contour points from the first shape are computed and their azimuth angles are obtained to select the CDRs of the corresponding points in the second shape. Thereafter, the correlation value of the two sets of CDRs is obtained with a matching strategy referred to as the degree of fitness of the GA. The correlation value can be used to modify the affine parameters for the next GA generation until the iteration is terminated. Finally, the affine parameters with optimal matching to the two shapes are regarded as the real affine parameters between the two shapes.
2.4 Constructing the CDRs for matching

As mentioned in section 2.3, the contour points for CDR computation in the first shape can be chosen arbitrarily. Nevertheless, the contour points for CDR computation in the second shape should be determined according to the original points and the affine parameters. Symbols α and $\tilde{α}$ are defined to represent the azimuth angles of two affine-related contour points P and $\tilde{P}$ in the two shapes, respectively, to clearly describe the proposed method (see Figure 3).

Figure 3.

Definition of the azimuth angles of the contour points

Considering an arbitrary pair of contour points P_i and $\tilde{P}$ , the azimuth angles α_i and ${\tilde{α}}_{i}$ , of P_i and ${\tilde{P}}_{i}$ can be determined as follows:

\begin{array}{l} α_{i} = \tan^{- 1} ((y_{i} - y_{0}) / (x_{i} - x_{0})) \\ {\tilde{α}}_{i} = \tan^{- 1} (({\tilde{y}}_{i} - {\tilde{y}}_{0}) / ({\tilde{x}}_{i} - {\tilde{x}}_{0})) \end{array}

(8)

According to equation (1), ${\tilde{α}}_{i}$ can be expressed in terms of α_i as follows:

{\tilde{α}}_{i} = \tan^{- 1} ((a_{3} + a_{4} \tan α_{i}) / (a_{1} + a_{2} \tan α_{i}))

(9)

Therefore, an azimuth angle-based approach is obtained for matching point construction. For any contour point P_i: [x_i, y_i]^T in the first shape, the azimuth angle α_i can be obtained using equation (8). Given a group of affine parameters s_x, s_y, sh_x, sh_y, and θ, the linear transformation coefficients of matrix $[\begin{matrix} a_{1} & a_{2} \\ a_{3} & a_{4} \end{matrix}]$ can be computed using equation (3). Then, ${\tilde{α}}_{i}$ can be obtained using equation (9), together with coefficients a₁, a₂, a₃, and a₄. Finally, ${\tilde{α}}_{i}$ can be used to determine the point selected for the CDRs, which was computed in the affine-transformed shape corresponding to the point with α_i in the first shape. Figure 4 shows the curves of CDR-α and CDR- $\tilde{α}$ for two affine-related bird shapes.

Figure 4.

CDR-α and CDR-α curves for two affine-related bird shapes

As can be seen in Figure 4, α and $\tilde{α}$ of the two curves had a certain corresponding relationship that can be uniquely determined using the affine parameters. For simplicity, 60 sample points for CDRs computation with the same angle interval of 3° were chosen in the first shape. More sample points should be extracted with a small angle interval to acquire the corresponding point in the second shape. Thus, 480 CDRs were computed, in which the points were sampled with an angle interval of 0.75°.

The average coordinate of the points in a neighbouring region with a prior-defined angle range in place of the position of each contour point was calculated to reduce the impacts of noises and break caused by partial occlusion.

Selecting 60 appropriate points from the total of 480 points in an affine-transformed shape to match with those found on the original shape was a challenging task. This task, which is one of the major findings in this study, will be discussed in the next section.

3. Affine parameter estimation based on GA

This section describes the affine parameter estimation method using the shape features of CDRs based on a GA. The similarity assessment strategy is also introduced for shape classification.

3.1 GAs and their application in this study

In the 1970s, Holland viewed GAs as an algorithmic concept based on the Darwinian theory of “survival of the fittest.” A GA is a global optimization random searching algorithm that can be classified as a guided random search evolution algorithm that uses probability to guide its search. GAs do not depend on the specific field in question, rather, they are iterative algorithms that depend on the generation-by-generation development of possible solutions, with selection schemes permitting the elimination of bad solutions and the replication of good ones that can be modified. A genetic search process is composed of three stages, namely, selection, crossover and mutation. GAs are widely used for pattern recognition applications, such as handwriting recognition [18], road recognition [19], license plate recognition [20], face recognition [21], and blood cell recognition, [22] among others, because of their excellent characteristics.

In the current study, a GA was used to search for the optimal solution of affine parameters. Some preliminary studies should be conducted for encoding initial population generation, and calculation of the degree of fitness. If S is defined as an individual of a population that consists of affine parameters, then f(S) is defined as the fitness function that represents the degree of similarity between two groups of CDRs. This study can be converted to a problem of searching for an individual S, which allows f(S) to have the maximum value.

1) Individual coding

Considering the affine parameters of s_x, s_y, sh_x, sh_y, and θ in equation (2), s_x can be set to a constant value of 1 without any influence to the value of CDRs in this study. Then, s_y, sh_x, sh_y, and θ can be regarded as the genes of an individual. The individual S can be expressed as follows:

S = {s_{y}, s h_{x}, s h_{y}, θ}

(10)

where each S can build a one-to-one corresponding relationship between the contour points of two shapes. Thus, the degree of matching can be determined using the fitness function f(S).

2) Fitness function definition

The fitness function is used to measure each individual's degree of fitness for finding the optimal solution, and it is the unique rule in the selection stage of GA. As mentioned above, 60 and 480 CDRs were obtained for two shapes, respectively. Suppose the CDR sequences of two shapes are denoted as o[i], i = 0,1,2,…,59 and q[j], j = 0,1,2,…, 479, which can be expressed as follows:

\begin{array}{l} o [i] = C D R (P_{1}, P_{2}) | \begin{matrix} α_{1} = 3 i \\ α_{2} = 3 i + 180 \end{matrix}, i = 0, 1, …, 59 \\ q [j] = C D R ({\tilde{P}}_{1}, {\tilde{P}}_{2}) | \begin{matrix} {\tilde{α}}_{1} = 0.75 j, j = 0, 1, …, 479 \\ {\tilde{α}}_{2} = {\begin{matrix} 0.75 j + 180, j = 0, 1, …, 239 \\ 0.75 j - 180, j = 240, 241, …, 479 \end{matrix} \end{matrix} \end{array}

(11)

Since each individual S can determine a unique relationship between α and $\tilde{α}$ , n[S,i], i = 0,1,2,…,59 can be mathematically defined to reflect the unique relationship as follows:

n [S, i] = int [\frac{{\tilde{α}}_{1}}{0.75}] | \begin{array}{l} {\tilde{α}}_{1} is the corresponding azimuth of \\ α_{1} \det ermined by S while α_{1} = 3 i \end{array}

(12)

where n[S,i] ∊ {0,1,…479} represents the index number of the CDRs of the second shape corresponding to the index number of i of the first shape. The fitness function f(S) can be defined as follows:

f (S) = \frac{1}{1 + \sqrt{\sum_{i = 0}^{59} {(\frac{o (i) - q (n [S, i])}{o (i) + q (n [S, i])})}^{2}}}

(13)

where (o(i)-q(n[S,i]))/(o(i)+q(n[S,i])) is defined as the relative difference between the CDRs of the two shapes. Since the size of the shape may be changed under the affine transformation, the relative difference is more accurate for describing the similarities of the two shapes than the absolute difference of o(i)-q(n[S,i]). According to equation (13), o(i)-q(n[S,i]) will reach zero if the individual S is close to the actual parameters of the affine transformation between the two shapes. Thus, the value of f(S) can reach a maximum value of 1. f(S) can be used as the fitness function for the GA.

3.2 Implementation of the proposed method

According to equation (10), the individual S consists of four factors. The floating point representation (FPR) is used for individual encoding. Moreover, the value range of each factor is designated based on its physical meaning as follows: s_y ∊ [0.25,4], sh_x ∊ [−0.5,0.5], sh_y ∊ [−0.5,0.5], and θ ∊ [0,360°]. In the proposed method, the population size was set to 80 and the generation was set to 100. Russian roulette was used to select the individuals for the next generation. The results of the Russian roulette depend on the fitness probability, which is defined as p(i) as follows:

p (i) = \frac{f (S_{i})}{\sum_{i = 1}^{80} f (S_{i})}

(14)

The number of duplicates of the same individual for the next generation should be restricted in the early period of the generation to avoid the premature convergence problem caused by high selection pressure. In this study, the upper limit value of the number of choices of the same individual was designated as four for the first 40 generations. In addition, no special requests were encountered for the crossover and mutation probabilities. The value ranges of the crossover and mutation probabilities are usually defined as [0.5, 0.99] and [0.001, 0.1], which are determined based on the experimental results. They were designated as 0.8 and 0.08 in the current study, respectively. Moreover, the two-point crossover and the uniform mutation operators were used in the proposed method. The implementation procedures of the proposed method consist of the following steps:

Based on an edge detection algorithm, such as a Sobel, Canny or Prewitt operator, the contour points of the two shapes are extracted. All the coordinates are recorded for the subsequent operations.

For each designated azimuth angle, the average coordinates of all the contour points in the adjacent area with the predefined angle range are computed.

The 60 CDRs for the first shape and the 480 CDRs for the second shape are calculated using equations (5) and (6), respectively.

The initial population consisting of 80 individuals is created.

The fitness value of f(S_t) for each individual of S_i is computed using equations (11)–(13). If the maximum of the fitness values exceeds 0.6 (it will be explained in section 4), the iteration can be terminated, and the affine parameters of the optimal solution are obtained.

The fitness probability is obtained using equation (14), and 80 individuals are selected for a new population.

Using the crossover probability, the selected gene of a given individual is exchanged with the same gene of another individual selected randomly.

Using the mutation probability, the selected gene is replaced with a random value within its value range.

A new generation of the population is obtained. If the generation number is less than 100, go back to step 5).

10)

The individual with the maximum degree of fitness from the last generation is chosen as the optimal solution. If the two shapes are affinely related, the solution obtained from the steps above will be approximated to the real affine parameters. Therefore, the fitness value will be greater compared with those derived from two unrelated images. The value of f(S) can be regarded as the coefficient of the similarity evaluation for shape classification.

4. Analysis of the experimental results

The proposed algorithm was evaluated on a number of natural and synthetic images, including a rabbit, a plane, a bat, a butterfly, and various shapes of birds, among others (see Figure 5). The affine-related shapes of the natural and synthetic images were obtained using image processing software. The operations consisted of translation, scaling rotation, distortion, and the combination of all.

Figure 5.

Some shapes tested in the experiments

The CDRs for both shapes were calculated. As presented in section 2.4, the CDR sequences of the first shape, named as o[i], consists of 60 samples with an angle interval of 3°, whereas the q[j] of the second shape consists of 480 samples with an angle interval of 0.75°. In addition, an angle range of 1.5° was designated for computing the average coordinates of the points. With this method, the impacts of noise and errors of edge detection can be reduced. Meanwhile, The CDR of the breakpoint can still be obtained if its corresponding angle range is less than 1.5°. Thus, our method will be effective for a small partial occlusion.

The experiments focused on three issues to test the reliability of the performance of the proposed algorithm. First, since the processing methods used for the two candidate shapes were different from each other, the two affinely related shapes should be alternately regarded as the first and second shapes for conformance testing. Table 1 shows the experimental results on four groups of candidate shapes, each with three CDR curves.

The first curve from array o[i] was built according to the first shape. The other two curves were derived from the second shape. The second curve from array q[j] consisted of 480 samples, whereas the third curve included 60 samples selected from q[j], according to the optimal solution of affine parameters. The vertical and horizontal axes of the CDR curves represent the CDR value and the azimuth angle, respectively. As can be seen in Table 1, the first and third curves were similar, indicating that the two shapes were affinely related. The f(S) value in group I was similar to that in group II, and a similar result was obtained in groups and . The results demonstrate that the proposed method is robust, regardless of which of the two affine-related shapes is designated as the first shape.

Table 1.

Some experimental results of the conformance testing

The second issue verified in the experiments was the differences in the fitness values between the affinely related and unrelated shapes. The unique factor involved was the evaluation of the similarity of the shapes.

As can be seen in Table 2, the maximal fitness value of all the unrelated shapes was 0.5741, whereas the minimal fitness value of the affine-related shapes was 0.6469. Thus, the fitness value of f(S) can be applied to shape discrimination.

Table 2.

Some experimental results on affinely related and unrelated shapes

Multiple affinely related shapes were used to compute the fitness value and to test the capability of the proposed recognition method on affinely related shapes. Table 3 presents experimental results on some affinely related butterfly shapes. During the experiment, the shapes in the first row were regarded as the first shapes, while those in the first column were treated as the second shapes.

Table 3.

Some experimental results on affine-related shapes

As can be seen in Table 3, the fitness values were between 0.6 and 1, and the minimal value was 0.6217, indicating the higher similarity between the affinely related shapes than between the unrelated shapes. Thus, the f(S) value can be used as the evaluation factor for shape classification.

According to the test results of the above experiments, it can be seen that the minimal fitness values of affinely related shapes are greater than 0.6, while the maximal fitness value of unrelated shapes are less than 0.6. Thus, the threshold was set to 0.6 in our method. Of course, this threshold is an empirical value. It looks reasonable in our experiments, but, it should be modified to adjust the trade-off between the false alarm probability and the probability of a miss in a real application.

The computational complexity of the proposed method is mainly dependent on the convergence speed. If the two shapes are affinely related, the iteration process may be terminated early. The time taken to obtain the optimal solution for discriminating between two shapes is usually about three seconds. Two approaches can be used for future studies to reduce time consumption. First, the crossover and mutation operators may be improved to accelerate the convergence speed. For example, the operators can be adjusted to the fitness value and to the characteristics of the coding method of the individuals. Second, the CDRs of some common shapes can be stored in a database as standard samples, which can be directly applied in the current study. Most of the proposed approaches in the literature were critically dependent on the one-by-one coordinate sequences of the contour points. Obtaining coordinate sequences is challenging because the contours of affinely related shapes may be influenced by break and noise. Compared to the methods presented in the literature, the main advantage of the proposed approach is its robustness for break and noise using shapes other than the affine transformation. Moreover, the total time consumed for completing the calculations was also competitive.

5. Discussion

The current study proposed a new method for shape recognition that is invariant to affine transformation. The proposed method consists of two main steps, namely, extracting affine invariant features called CDRs and estimating the affine parameters based on the GA. Compared with other methods found in the literature, the advantages of the proposed method include not having to pre-process the impacts of noise, partial occlusion and a variant starting point. Furthermore, the proposed method does not rely on a one-by-one coordinate sequence of the contour points. In the experiments in the current study, 480 CDRs for the second shape were calculated to provide the corresponding points determined using the 60 points in the first shape and the estimated affine parameters.

The main disadvantage of the proposed method is its failure to work properly on central symmetry shapes because the CDRs are always approximately equal to 1. For example, the proposed method cannot distinguish between circles and rectangles, among others, and thus, further investigations are necessary. Considering most natural shapes are complicated and irregular, the proposed method is valuable for real applications.

Footnotes

6.

This work is supported by the innovative research projects of colleges and universities in Chongqing (12A19369).

References

[1] Chaker

Bannour

M.T.

Ghorbel

, A complete and stable set of affine-invariant Fourier descriptors, Proc. of the 12th International Conference on Image Analysis and Processing, 2003: 578–581.

[2] Zhang

, Study and evaluation of different Fourier methods for image retrieval, Image and Vision Computing, 2005, 23:33–49.

[3] Thourn

Kitjaidure

, Multi-view shape recognition based on principal component analysis, Proc. of International Conference on Advanced Computer Control, 2009: 265–269.

[4] Mei

Androutsos

, Affine invariant shape descriptors: the ICA-Fourier descriptor and the PCA-Fourier descriptor, Proc. of 19th International Conference on Pattern Recognition, 2008.

[5] Uddin

Md. Zia

Lee

J.J.

Kim

T.-S.

, Shape-based human activity recognition using independent component analysis and hidden Markov model, Proc. of the 21st international conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, 2008: 245–254.

[6] Kalra

Das

Datta

, Generic object recognition using a combination of ICA and shape cues, Proc. of IEEE International Conference on Video and Signal Based Surveillance, 2006.

[7] Nabout

A.A.

Tibken

, Object shape recognition using Mexican hat wavelet descriptors, Proc. of IEEE International Conference on Control and Automation, 2007: 1313–1318.

[8] Bala

Cetin

A.E.

, Computationally efficient wavelet affine invariant functions for shape recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(8):1095–1099.

[9] Yawichai

Kitjaidure

, Multi-view invariant shape recognition based on neural networks, Proc. of 3rd IEEE Conference on Industrial Electronics and Applications, 2008: 1538–1542.

10.

[10] Du

J.-X.

Huang

D.-S.

Wang

X.-F.

, Neural network-based shape recognition using generalized differential evolution training algorithm, Proc. of the International Joint Conference on Neural Networks, 2005: 2012–2017.

11.

[11] Guney

Ertzn

, Undoing the affine transformation using blind source separation, Proc. of 6th International Conference on Independent Component Analysis and Blind Signal Separation, 2006: 360–367.

12.

[12] Thourn

Kitjaidure

Kondo

, Affine invariant shape recognition based on multi-level of barycenter contour, Proc. of International Symposium on Communications and Information Technologies, 2008: 145–149.

13.

[13] Yang

H.S.

Lee

S.U.

Lee

K.M.

, Recognition of 2D Object Contour Multi-Level Using Starting-Point-Independent Wavelet Coefficient Matching, Journal of Visual Communication and Image Representation, 1998, 9(2):171–181.

14.

[14] Kunttu

Lepisto

Rauhamma

Visa

, Multiscale Fourier descriptor for shape-based image retrieval, Proc. of 17th international conference on pattern recognition, 2004: 765–768.

15.

[15] Zhang

Chang

, Genetic algorithm for affine point pattern matching, Pattern Recognition Letters, 2003, (24):9–19.

16.

[16] Izumi

Hattori

S. Q.

Kitajima

Yamasaki

, Face recognition for images of persons against a general background using approximate parameter estimation of affine transform, Electronics and Communications in Japan, 2009, 92(11):1–8.

17.

[17] Kadyrov

Petrou

, Affine parameter estimation from the trace transform, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(10):1631–1645.

18.

[18] Kherallah

Bouri

Alimi

A.M.

, On-line Arabic handwriting recognition system based on visual encoding and genetic algorithm, Engineering Applications of Artificial Intelligence, 2009, 22:153–170.

19.

[19] Zhu-lin

Xian-wei

Hong-lei

, Road recognition in high resolution sar image based on genetic algorithm, Proc. of the 7th World Congress on Intelligent Control and Automation, 2008:6783–6788.

20.

[20] Ji-yin

Rui-rui

Min

Yin

, License plate recognition based on genetic algorithm, Proc. of the International Conference on Computer Science and Software Engineering, 2008: 965–968.

21.

[21] Li

Yuan

, Feature selection of face recognition based on improved chaos genetic algorithm, Proc. of the Third International Symposium on Electronic Commerce and Security, 2010:74–78.

22.

[22] Osowski

Siroi'c

Markiewicz

Siwek

, Application of support vector machine and genetic algorithm for improved blood cell recognition, IEEE Transactions on Instrumentation and Measurement, 2009, 58(7):2159–2168.

Genetic Algorithm-based Affine Parameter Estimation for Shape Recognition

Abstract

Keywords

1. Introduction

2. Affine invariant features extraction

2.1 Affine transformation and the definitions of its parameters

3.1 GAs and their application in this study

1) Individual coding

Footnotes

6.

References