Abstract: For the year of past most three-dimensional objects are represented and mapped with spherical function. Since the mapping preserves the important criteria of a 3D object, the representation of 3D shape in a suitable way is an important matter for 3D object retrieval. In many circumstances, spherical surface fitting to a 3D shape does not approximate very well because of their limited degree of divergence by their radius only. Whereas in the case of ellipsoid definition we get three axis, which gives us a free mapping along each of x, y and z axis. Ellipsoid gives better approximation for a given 3D shape than sphere which leads to a less error and higher discriminant shape descriptor for retrieval of 3D shape. In this study, we describe 3D shape representation method based on ellipsoid for the purpose of 3D shape retrieval. And we demonstrate the experimental result tested on standard 3D shape Princeton Shape Benchmark (PSB) database, inferring new wavelet shape descriptor of the represented 3D shape function on ellipsoid. The experimental results proof the expectation of proposed hypothesis.

INTRODUCTION

In the digital era 3D shape retrieval continues to be one of the most exciting and fastest growing research areas in the field of computer vision, molecular biology, computer graphics, CAD/CAM engineering system, car industry, entertainment even in digital arts and a variety of other fields. A challenge is to find a suitable 3D shape retrieval technique with highly and unique discriminating between similar and dissimilar shapes. Shape representation technique is an important issue for the purpose of retrieving the 3D shape since it preserves important attribute.

However, existing research are mostly based on function representing on sphere for the purpose of 3D shape retrieval. Vranic and Saupe (2002), Vranic (2003), Novotni and Klein (2003), Kazhdan et al. (2003) and Mousa et al. (2007) are the examples of 3D shape descriptor that has been used sphere for the 3D shape representation. Their aim was to estimate feature vector of spherical harmonic coefficient of a 3D triangular mesh model representing shape function on sphere. There also another shape feature vector of spherical wavelet coefficient. Laga et al. (2007), representing 3D shape function on sphere. However, feature vector approaches are more effective due to higher discrimination. Still we found that sampling is irregular for spherical harmonics. Additionally, spherical shape functions have poor controlling of coefficient due to higher divergence and lower degree of freedom and the shape approximation is not closure which contributes more error prone shape descriptor. There are also another works in this research area that compare graphs for recognition of 3D shape retrieval or represent histogram of shape variation or shape distribution. Directional Histogram Model (DHM) proposed by Liu et al. (2003) represents histogram of thickness distribution of two points on the object surface. Another Osada et al. (2002) represents histogram of shape distribution of some geometric property such as D2, represents distance between two random points on the surface.

These methods are easy to compute but are less efficient in respect to discriminative ability. Skeletal graph by Sundar et al. (2003) stores the skeletal node information to connect it as a graph and Multiresolution Reeb Graphs (MRGs) by Hilaga et al. (2001) are most common technique for measuring shape dissimilarity comparing as a graph. Another Sketelon, defined by Reeb (1946) formed by continuous scalar function used as height function, distribution of geodesic distance on the object. However, these graphical methods are more suitable for the shapes which are segmented joint but these schemes are usually much more computationally expensive and thus not suitable for real application. Whereas Reeb (1946) graph is not robust in respect of feature extraction performance. Large graph size decrease efficiency.

The main goal of the research is to find a suitable 3D shape representation scheme to estimate high discriminating and less error prone shape descriptor. Here, we have proposed a new ellipsoidal wavelet descriptor representing shape function based on ellipsoid of a 3D shape model. The advantage is that, ellipsoid gives more closure approximation and degree freedom of a given 3D shape rather than sphere. The approach represents 3D shape model (triangular model) on the ellipsoid to approximate and mapped into a square image for further step. Finally, an ellipsoidal wavelet transform is computed to obtain the shape descriptor of wavelet coefficient. As a result we get more high discrimination and accurate feature vector of ellipsoidal shape function since approximation method gives more controlling of coefficients.

MATERIALS AND METHODS

We use ellipsoid to approximate the 3D shape model in the proposed shape representation method. The reason of choosing ellipsoid is as follows: in general 3D shapes are irregular in nature. All existing methods are suitable for near spherical bodies not for non-spherical bodies which create problem to compute expansion close to the surface of the bodies. The approximation of a 3D shape with a sphere expose to be intensely high, Fig. 1 shows the smallest sphere enclosing the whole body. But for the case of ellipsoid, it can be easily shown that the uniform fitting approximate more closure to the body of the shape of the given 3D shape in Fig. 2.

Moreover ellipsoidal mapping surface don’t have any pole like spherical mapping surface which have singularity problem to the North and South Pole which affect to the sampling. Spherical mapping used for texture mapping often does not fit in the surface very well because they have limited degree of freedom within which they are approximated. One notable benefit is that ellipsoids are defined by three axis, one along each of the x, y and z axis and this is why ellipsoid gives more accurate representation to the body of the shape.

Fig. 1:	A 3D shape model enclosed with sphere

Fig. 2:	A 3D shape model enclosed with ellipsoid

Fig. 3:	Different ellipsoid (a, b, c) along their axis and sphere and (d) with radius (r)

Whereas a sphere only altered by its radius, Fig. 3 shows the different ellipsoid of these three axis definition. Forming multilevel resolution Wavelet based descriptor is more suitable on image. The ellipsoidal model has advantage to construct large-scale detail since texture mapping is also affected by the way of approximation to the shape model. And obviously, the computation error will be lower as well as higher accuracy in case of ellipsoid due to aforementioned advantages of ellipsoidal shape function.

The method consists of two steps and is described follows. The first step is the process of shape representation method approximated by ellipsoid of a 3D triangular model. Second step describes shape recognition process which extract wavelet coefficient for estimating unique feature vector. And ultimate we get a new shape descriptor of a 3D shape function based on ellipsoid.

To measure the similarity of two shape descriptor we use Euclidian norm. The whole procedure of the proposed method has been detailed following:

3D object representation: Representing 3D shape is an essential stage and important goal to preserve the important chracteristics for the purpose of 3D recognition purpose in computer vision. As it was earliar mentioned that the major problem to estimate high discrimintive shape information. Here we present a new geometric descriptor representing shape function on ellipsoid. Already we mentioned the reason behind using ellipsoid as a primitive. The another major contribution of the proposed shape representation are the following.

Ellipsoidal mapping of 3D object: We estimate the ellipsoidal parameterized approximation by mapping the 3D triangular shape model radially from the shape to the vertices of the unit ellipsoid centre. The ellipsoid mapping is defined by the Eq. 1:

(1)

where semi axis a, b, c ≠ 0. And the sampling vertices are defined to ellipsoid as:

(2)

Where (X₁, Y₁, Z₁) is ellipsoidal mapped parameter and f_v defined the sampled vertices with radii a, b and c and the centre (x_c, y_c, z_c) and x, y, z are the spherical coordinate with θ {0, π} and φ {0, 2π}.

Since the ellipsoid sampling is more uniform to the shape than sphere, the proposed approach avoids the practical limitation of measuring similarity of same object in different polygon connectivity.

As a preprocessing technique we applied Principal Component Analysis (PCA) Jolliffe (1986) on a 3D model on each of its vertices. This method consists of set of transformation such as translation, rotation and etc.

Shape recognition
Ellipsoid to planar map: It is suitable to estimate wavelet coefficient on the 2D image. So, we simply map the approximated shape function to a square image I with size m x m (for the case m is 64) taking into account that each point on the surface map to a unique point on the texture square.

Here also we benefited that Ellipsoidal projection mapping does not have any pole like spherical projection map and for spherical the small areas around the poles map in a highly distorted manner all over the top and bottom of the square.

Wavelet transform: The wavelet was introduced by Morlet and Grossman as a time-scale analysis tool for non-stationary signals. It was further developed by many researchers and rapidly found application in many areas.

A wavelet function is a function that is well localized in the space and frequency domains. Nowadays wavelet basis are becoming the foundation for the most popular techniques for signal processing and image processing in a wide range of applications. We applied 3-level Haar wavelet transform on the image I in order to generate unique characteristics vector. A two-dimensional image signal is wavelet-transformed in horizontal and vertical directions and the image is divided into four regions LL, HL, LH and HH after the wavelet transform has been performed once as shown in Fig. 4. The LL region contains only low frequency components (the approximation function component) and HH region contains high frequency component. Once we have performed a 1-level Haar transform, then it is easy to repeat the process and perform multiple level transform.

Fig. 4:	1-level 2D wavelet decomposition

The first level Haar transform of an image f is defined by:

(3)

where, h¹, v¹, d¹ is the first horizontal, vertical and diagonal fluctuation, respectively and a¹ is the approximation imge.

Descriptor extraction: We estimated feature vector collecting the wavelet detail coefficient. We processed the value as a binary value for making feature vector. It is expensive to work with all coefficients, so we collected 256 data coefficient for feature vector.

Similarity measure and error estimation: If F₁ and F₂ are two feature vectors of two 3D objects O₁ and O₂, the distance between two descriptor of L₂ norm is:

(4)

We measure the approximation error by the distance between the surface X and ellipsoid O as:

(5)

where, v (P_o) means to radial projection of vertices on ellipsoid O.

RESULTS AND DISCUSSION

To evaluate the accuracy of proposed approach extensive experiments on well known database PSB [17] are performed. We collected database from a standard database Princeton Shape Benchmark (PSB) in 3D (OFF) file format.

Fig. 5:	(a) Comparison of approximation error for dog and human model and (b) Comparison of approximation error for shark and tree model

We measure the approximation error of the 3D models representing function on ellipsoid. We compare the approximation error of our method with spherical representation function.

The comparison of approximation error is with dog and human presented in Fig. 5a and with shark and tree in Fig. 5b. Some of tested models are shown in Fig. 6. In order to evaluate the measurement of retrieval performance, we examine precision/recall diagram for the shape descriptor of 3D objects.

Briefly, recall is the proportion of the relevant models actually retrieved and precision is proportion of retrieved models that is relevant.

And we next show the comparison of the retrieval performance between spherical based wavelet shape descriptor and the proposed ellipsoid based shape descriptor in Fig. 7. Another precision/recall diagram (Fig. 8) compares for the fish and shark model tested from the Princeton Shape Benchmark database (PSB). From the experiment, we can demonstrate that the proposed approach reduce approximation error definitely.

Fig. 6:	Some of models used for testing

Fig. 7:	Precision/recall diagram for 3D models of PSB database

For example the human model, error falls to 30 from 60%. This provides greater accuracy for estimating shape descriptor for similarity measure according to the results.

Fig. 8:	Precision/recall diagram for fish and shark model

CONCLUSION

A 3D model retrieval based on ellipsoidal wavelet is proposed. We approximate 3D model on ellipsoid in order to extract feature vector for any 3D model using wavelet transform. The proposed descriptor is compared to existing descriptor based on spherical function with respect to the accuracy and approximation error. The approach shows greature accurcy in terms of retrieval performance. There are some factors to consider incase of approximation of 3D object with any function such as sphere or ellipsoid or any other:

In the proposed approch we satisfy with first factor fully. But in contrary, it is very difficult to cover exactly the 3D shape with a closest fitting by the proposed shape representation sceme.

RECOMMENDATION

The further research is continuing considering with the before mentioned limitation. A possible way to solve this problem is to represent a 3D shape in a tree structure or graph structure to cover the joint part. So the next aim is to find any possibility to produce hybridization method with the method. One possible way is to create a tree structure of the 3D shape with a no. of node and to approximate with ellipsoid. But the problem is that it will be very complex with can not be applied in a real application since it require many hundreds of node. Is it possible to come up with less complex manner?

ACKNOWLEDGEMENT

The research is supported by Universiti Malaysia Sarawak under the scheme of postgraduate scholarship.