Affine Invariant Descriptors and Recognizing

International Journal of Reviews in Computing

ISSN: 2076-3328 E-ISSN: 2076-3336

Affine Invariant Descriptors andRecognizing

of 3D objects Using Statisticsmethods

1M. ELHACHLOUFI, 1A. EL OIRRAK, 2D. ABOUTAJDINE , 1M.N. KADDIOUI

1Faculty Semlalia , Department of Informatics, Marrakech, Morocco

2Faculty of Science, LEESA-GSCM, BP 1014, RABAT

E-mail: , , ,

Abstract

The increasing number of objects 3D available on the Internet or in specialized databases which require the establishment of methods to develop description and recognition techniques to access intelligently to the contents of these objects. In this context, our work whose objective is to present the methods of invariantdescription [1,2,3] and recognition of 3D objects based on statistical methods: analysis of data (AD) and the principal component analysis (PCA). The objective of this studies is to determine an invariant description[4,5] of a 3D object using a coefficients vector of canonical correlations from the data analysis. This vector is invariant against affine transformation of the 3D object and recognize the object (s) of a database (3D objects) similar(s) to a given object (query object) using the descriptor vectors extracted from these 3D objects by the principal component analysis.The 3D objects of this database are transformations of 3D objects by one element of the overall transformation. The set of transformations considered in this work is the general affine group. The measure of similarity between two objects is achieved by a similarity function using the Euclidean distance.

Keywords:Invariants Descriptors, Recognizing, 3D objects, Multiple Regression,Principal Component Analysis, Affine Transformation.

International Journal of Reviews in Computing

ISSN: 2076-3328 E-ISSN: 2076-3336

1. INTRODUCTION

With the advent of the Internet, exchanges and the acquisition of information, description and recognition of 3D objects have been as extensive and have become very important in several domains.
On the other hand, the size of 3D objects used on the Internet and in computer systems has become enormous, particularly due to the rapid advancement technology acquisition and storage which require the establishment of methods to develop description and recognition techniques to access intelligently to the contents of these objects.

In fact, several approaches are used: in terms of statistical approaches, the statistical shape descriptors for recognition in general consist either of calculating various statistical moments [6] [7] and [8], or of estimating the distribution of the measurement of a given geometric primitive, when either deterministic or random.

Among the approaches by statistical distribution, we mention the specter of 3D shape (SF3D) [9] which is invariant to geometric

transformations and algebraic invariants [10], which provide global descriptors, which are expressed in terms of moments of different orders.

For structural approaches, approaches representative of the object segmentation in 3D plot of land and performances by adjacency graph are presented in [11] and [12]. Similarly, Tangelder and al [13] have developed an approach based on representations by interest points.

In transform approaches a very rich literature emphasizes any interest in approaches based transform Haugh[14], [15] and [16] which consists in detecting different varieties of dimension (n-1) immersed in the space.

In the same vein, this work interested to define new methods for description and recognition of 3D objects using statistics methods.

2. Method 1 : An affine description invariant Of 3D objects by the canonicalcorrelation coefficients

2.1 Representation of the 3D objects

Consider 3D object represented by a set of points denoted, where , arranged in a matrix . Under the action of an affine transformation, the coordinates are transformed into other coordinatesby the following procedure:

With invertible matrix associated with the infinite,and is a vector translation in .

2.2 The canonical analysis of two vectors:

and

Letand are two vectors.
The principle of this analysis is to search at the first a couple of variables which is a normalized linear combination of variables ( is jth column of X) and a normalized linear combination of variables ( is kth column), such that and are correlated as possible, i.e: that maximizes the quantity available.

Then we search the normed pair where as being a linear combination of uncorrelated to , i.e.: , and linear uncorrelated to i.e.:, witch and are correlated as possible, i.e.: maximizes the quantity available.

And so on...

The canonical analysis product p of pairs of variables where s = 1... p.The variables are an orthogonal basis of the space generated by. The variables is e an orthogonal space generated by. The couples, particularly the first of them, reflect the linear connections between two groups of initial variables. The variables are are called canonical variables. Their successive correlations (decreasing) are called canonical correlation coefficients (or canonical correlations). The canonical correlation coefficients are invariant quantities over an affine transformation and are all equal to 1 in this case.

2.3 Results and evaluation

We consider two 3D objects and related by an affine transformation (figure 1 and 2).The calculation of canonical correlation coefficients from these objects requires computing the first a pairs of canonicalvariables of and then the coefficients of canonical correlations from these couples.

Figure 4 shows the values of canonical correlation coefficients are all equal to 1.Figures 3 shows that the canonical variables of origin objects and its transformed are the same which leads us to conclude that is an affine transformation of according to the procedure of canonical analysis.

3.Method 2: Recognition 3D object principal component analysis normalized

3.1 Principal component analysis

The principal component analysis is a method factorial analysis of multidimensional data [18]. It determines a decomposition of a random vector with uncorrelated components, orthogonal and adjusting to better distribution of . In this sense the components are called principal components and are arranged in descending order according to their degree of adjustment.

The calculation of normalized principal components of the vector is carried out initially by calculating the covariance matrix as follows:

Wheretransposed of. Then we passes to extract eigenvalues and eigenvectors associated to by the following process

and are eigenvalues and eigenvectors associated .

The eigenvaluesand eigenvectors associated are and

where and is the number of line of .The reconstruction of from vector is doing as follows , we say that the vector is a vector characteristic of , so we write:

3.2 Representation of 3D objects

Consider a 3D object represented by a set of points denoted with , arranged in a matrix , i.e: where and are the matrix and vector transposed and .

Under the action of an affine transformation, the coordinates of are transformed into other coordinates of by the following procedure: where and are scalar.

Let function defined as follows:

where is un 3D object , and are the mean and variance .

We have:

Then is called an invariant function.

Remarque:

(a)- If then.

(b)-We suppose: then . According to (a) we obtain: , thus is an invariant against affine transformation.

(c)- According to (2) we concluded that:

If is a vector characteristic of , i.e:

then is a descriptor of in the sense that the invariance check is only relative to the first component and the reconstitution requires the use of ,and as shown in equation (4).

3.3 Principle of description and recognition proposed method

3.3.1 Step 1: learning system

It can be decomposed into two phases: extraction of vector descriptor and recognition.

The role of the first phase is to associate each object to learn the vector descriptor

. This vector will be used later in the recognition system.

Registration vector descriptors are Phase 2. The diagram of learning system is shown in figure 5.

3.3.2 Step 2: Recognition system

For each characteristic vector (first component) of the object database vector descriptor, we calculate the error resulting from the difference between this vector and that of the object (query object) to recognize.
We recognize the object that produced the error is almost zero.

This operation is illustrated in figure 6.

3.4 Results and evaluation

Consider two 3D objects (object of a database) and (query object) related by an affine transformation ( figures 1 and 2).

After extraction of vector descriptorsofof we move to calculate the error vector

According to the graph of the error (figure 9) we found that , which verifies the invariant of this vectors as shown in figure 8 and figure 9.

So is an affine transformationof .

4. COMPARISON OF RESULTS

According to figures below we can see that the error1 - corresponds to the difference between the invariants of the object origin and its transformation by an affine transformation- calculated by our methods (figures 9) is smaller than those obtained by the methods of Fourier transform and Moments (figures 10 and 11).

In addition, the computing time of our method is less than the method of Fourier transform and Moments. This leads us to conclude that our method applied to these objects is more efficient than Fourier transform and Moments, in term of error.

5. CONCLUSION

In this work we presented two methods of invariant description and recognition of 3D objects based on statistical methods: analysis of data (AD) and the principal component analysis (PCA).

The firstmethod consists of calculating the canonical correlations coefficients vector from the canonical variables couples of the object origin and it’s transformed. The components of this vector are all equal to 1 and the canonical variables values are equal which leads us to conclude that the first object (origin) is an affine transformation of the second(its transformed).

In the second method, the vector descriptor is formed by the characteristic vector extracted using PCA from the object origin and its transformed, this vector is invariant against an affine transformation.

The recognition is doing by measuring the similarity between the descriptor vectors extracted from the two objects: the request object and those belonging to a database of objects using the metric euclidean distance as described above for each method.

Experimental results show the validity and utility of these methods.

REFERENCES

[1] A. El Oirrak, M. Daoudi, D.Aboutajdine: Affine invariant descriptors for color images using Fourier series. Pattern Recognition Letters 24(9-10): 1339-1348 (2003)

[2]A. El Oirrak, M. Daoudi, D.Aboutajdine: Estimation of general 2D affine motion using Fourier descriptors. Pattern Recognition 35(1): 223-228 (2002)

[3] A.El Oirrak, M. Daoudi, D.Aboutajdine: Affine invariant descriptors usingFourier series. Pattern Recognition Letters 23(10): 1109-1118 (2002)

[4]M. Petrou and A. Kadyrov. Affine invariant features from the trace transform. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(1):30{44, 2004.

[5]A. Choksuriwong, H. Laurent & B. Emile. A Comparative Study of Objects Invariant Descriptor. ORASIS, 2005.

[6] T. Murao, "Descriptors of polyhedral data for 313-shape similarity search", Proposal P177, MPEG-7 Proposal Evaluation Meeting, UK, Fév. 1999.

[7]M. Elad, A. Tal, S. Ar, "Directed search in a 3D objects database using SVM", Hewlett-Packard Research Report HPL-2000-20R1, 2000.

[8]C. Zhang, T. Chen, "Efficient feature extraction for 2D/3D objects in mesh representation", Proc. of the International Conference on Image Processing (ICIP 2001), 2001.

[9]T. Zaharia, F. Prêteux, "3D-shape-based retrieval within the MPEG-7 framework", Proc. SPIE Conf. On Nonlinear Image Processing and Pattern Analysis XII, Vol. 4304, pp. 133-145, San Jose, Etats-Unis, Janv. 2001.

[10]Taubin et D.B. Cooper, "Object recognition based on moment (or algebraic) invariants", J.L. Mundy and A. Zisserman, editors, Geometric Invariants in Computer Vision, pp. 375-397, MIT Press, 1992.

[11]S. J. Dickinson, D. Metaxas, A. Pentland, "The role of model-based segmentation in the recoveryof volumetric parts from range data", IEEE Trans. On PAMI, Vol. 19, No. 3, pp. 259-267, Mars 1997.

[12]S. Dickinson, A. Pentland, S. Stevenson, "Viewpoint-invariant indexing for content- based image retrieval", Proc. IEEE Int. Workshop on Content-Based Access of Image and VideoDatabase, pp. 20-30, Janv. 1998.

[13]J.W.H. Tangelder, R.C. Veltkamp, "Polyhedral model retrieval using weighted point sets", Rapport technique no UU-CS-2002-019, Universitd de Utrecht, Pays-Bas, 2002.

[14] P. V. C. Hough, "Method and means forrecognizing complex patterns", U.S. Patent 3069654, 1962.

[15] D. H. Ballard, "Generalizing the Hough transform to detect arbitrary shapes," Pattern Recognition, Vol. 13, No. 2, pp. 111-122, 1981.

[16] J. Illingworth et J. Kittler, "A survey of the Hough transform", Computer Vision,Graphics and Image Processing, Vol. 44, pp. 87-116, Oct. 1988.

[17]Bouroche, J.M. et G. Saporta (2006), L’analyse de données, Presses Universitaires de France, Collection Que sais-je ?, 9ème édition, 128p. 2006

[18]Saporta, G. (2006), Probabilités, analyse des données et statistiques, Techniques, 2ème édition, 622p, 2006