Panagiotis Papadakis
email: ppapadak@iit.demokritos.gr

Ioannis Pratikakis

Theoharis Theoharis

Stavros Perantonis

PANORAMA: A 3D Shape Descriptor based on Panoramic Views for Unsupervised 3D Object Retrieval

Keywords: 3D object retrieval, cylindrical projection, panorama, local relevance feedback, unsupervised

We present a novel 3D shape descriptor that uses a set of panoramic views of a 3D object which describe the position and orientation of the object's surface in 3D space. We obtain a panoramic view of a 3D object by projecting it to the lateral surface of a cylinder parallel to one of its three principal axes and centered at the centroid of the object. The object is projected to three perpendicular cylinders, each one aligned with one of its principal axes in order to capture the global shape of the object. For each projection we compute the corresponding 2D Discrete Fourier Transform as well as 2D Discrete Wavelet Transform. We further increase the retrieval performance by employing a local (unsupervised) relevance feedback technique that shifts the descriptor of an object closer to its cluster centroid in feature space. The effectiveness of the proposed 3D object retrieval methodology is demonstrated via an extensive evaluation in standard benchmarks that clearly shows better performance against state-of-the-art 3D object retrieval methods.

Introduction

Content-based 3D object retrieval is an active research field that has attracted a significant amount of interest in recent years. This is due to the increasing availability of 3D objects through public or proprietary databases, as even novice users can create 3D models from scratch with easy to use modeling interfaces such as Teddy [START_REF] Igarashi | Teddy: a sketching interface for 3D freeform design[END_REF], Google SketchUp [START_REF]Google SketchUp[END_REF], ShapeShop [START_REF] Schmidt | Shapeshop: Sketch-based solid modeling with blobtrees[END_REF] and others [START_REF] Olsen | A taxonomy of modeling techniques using sketch-based interfaces[END_REF]. Applications such as CAD, computer games development, archaeology, bioinformatics, etc. are also playing a major role in the proliferation of 3D objects. A second source of 3D objects is 3D scanners, which are constantly gaining users as their price drops.

Already, 3D object search engines have been developed for commercial or research purposes that offer searching using 3D object queries or keyword based queries. The former approach, which is an instance of content-based retrieval (CBR) alleviates various limitations that are encountered in keyword based retrieval which become prohibitive as the number of 3D objects increases.

In CBR, each 3D object is represented by a shapedescriptor which is used to measure the similarity between two objects. The shape descriptor should capture the discriminative features of a 3D model, have a compact size and permit fast extraction and comparison time.

In this paper, we propose a novel 3D shape descriptor that exhibits top performance by using a set of features which are extracted from a set of panoramic views of a 3D object. The proposed descriptor is called PA-NORAMA which stands for PANoramic Object Representation for Accurate Model Attributing. The panoramic views are used to capture the position of the model's surface in 3D space as well as its orientation.

We obtain a panoramic view of a 3D object by projecting it to the lateral surface of a cylinder aligned with one of the object's three principal axes and centered at the centroid of the object. The object's principal axes are determined during the rotation normalization step. The object is projected onto three perpendicular cylinders, each one aligned with one of its principal axes in order to capture the global shape of the object. For each projection, we compute the corresponding 2D Discrete Fourier Transform as well as 2D Discrete Wavelet Transform. To further enhance the retrieval performance, we employ a local relevance feedback (LRF) technique [START_REF] Papadakis | Relevance feedback in content-based 3d object retrieval: A comparative study[END_REF] that shifts the descriptor of an object closer to its cluster centroid in feature space. The employed LRF technique is unsupervised and assumes that the k nearest neighbors of an object belong to the same class, without requiring any feedback from the user. We demonstrate the increased performance of the PANORAMA descriptor by comparing it to other stateof-the-art approaches in standard benchmarks and promote the application of the LRF technique by showing the performance gain that is obtained when it is combined with the PANORAMA descriptor.

The remainder of the paper is organized as follows: In Section 2, we provide an overview of the related work in the area of content-based 3D object retrieval (Section 2.1) and cite previous work that incorporates relevance feedback (Section 2.2). In Section 3, we give the detailed description for the extraction of the proposed 3D shape descriptor and in Section 4, we describe the procedure of the employed LRF technique. The results of an extensive evaluation of the proposed methodology are presented in Section 5 and conclusions are discussed in Section 6.

2 Related work

Shape descriptors

In this Section we provide an overview of the related work in the area of 3D shape descriptors for generic 3D object searching. 3D object retrieval methodologies that rely on supervision are beyond the scope of this review, since this paper focuses mainly on enhancing the effectiveness of retrieval by using discriminative shape features in an unsupervised context.

Content-based 3D object retrieval methods may be classified into two main categories according to the spatial dimensionality of the information used, namely 2D, 3D and their combination. In the following Sections, we review the state-of-the-art for each category.

Methods based on 2D representations

In this category, shape descriptors are generated from images-projections which may be contours, silhouettes, depth buffers or other kinds of 2D representations. Thus, similarity is measured using 2D shape matching techniques. Surprisingly, extended state-of-the-art reviews such as [START_REF] Shilane | The princeton shape benchmark[END_REF] and [START_REF] Bustos | Feature-based similarity search in 3d object databases[END_REF] show that descriptors belonging to this class exhibit better overall retrieval performance compared to descriptors that belong to the second class.

Chen et al. [START_REF] Chen | On visual similarity based 3D model retrieval[END_REF] proposed the Light Field descriptor, which is comprised of Zernike moments and Fourier coefficients computed on a set of projections taken from the vertices of a dodecahedron. Vranic [START_REF] Vranic | 3D Model Retrieval[END_REF] proposed a shape descriptor where features are extracted from depth buffers produced by six projections of the object, one for each side of a cube which encloses the object. In the same work, the Silhouette-based descriptor is proposed which uses the silhouettes produced by the three projections taken from the Cartesian planes. In [START_REF] Passalis | Ptk: A novel depth buffer-based shape descriptor for three-dimensional object retrieval[END_REF], Passalis et al. proposed PTK, a depth buffer based descriptor which uses parallel projections to capture the object's thickness and an alignment scheme that is based on symmetry. Shih et al. [START_REF] Shih | A new 3D model retrieval approach based on the elevation descriptor[END_REF] proposed the elevation descriptor where six depth buffers (elevations) are computed from the faces of the 3D object's bounding box and each buffer is described by a set of concentric circular areas that give the sum of pixel values within the respective areas. Ohbuchi et al. [START_REF] Ohbuchi | Retrieving 3D shapes based on their appearance[END_REF] proposed the Multiple Orientation Depth Fourier Transform (MODFT) descriptor where the model is projected from 42 viewpoints to cover all possible view aspects. Each depth buffer is then transformed to the r -θ domain and the Fourier transform is applied. To compare two objects, all possible pairs of coefficients are compared which inevitably increases comparison time. Zarpalas et al. [START_REF] Zarpalas | 3D model search and retrieval using the spherical trace transform[END_REF] introduced a 3D shape descriptor called the spherical trace transform, which is the generalization of the 2D trace transform. In this method, a variety of 2D features are computed for a set of planes intersecting the volume of a 3D model. A newly proposed method is the depth line descriptor proposed by Chaouch et. al [START_REF] Chaouch | 3D model retrieval based on depth line descriptor[END_REF] where a 3D object is projected to the faces of its bounding box giving 6 depth buffers. Each depth buffer is then decomposed into a set of horizontal and vertical depth lines that are converted to state sequences which describe the change in depth at neighboring pixels.

Methods based on 3D representations

In this category, shape descriptors are extracted from 3D shape representations and the similarity is measured using appropriate representations in the spatial domain or in the spectral domain. A set of subcategories can be identified here, namely, statistical, graph-based and spherical function-based descriptors.

Statistical descriptors use histograms to capture the distributions of shape features. They are compact and fast to compute but they have very limited discrimination ability since they fail to capture local details that are characteristic of the object's shape. In the Shape Histograms descriptor proposed by Ankerst et al. [START_REF] Ankerst | Nearest neighbor classification in 3D protein databases[END_REF], 3D space is divided into concentric shells, sectors, or both and for each part, the model's shape distribution is computed giving a sum of histograms bins. The shape distributions descriptor proposed by Osada et al. [START_REF] Osada | Matching 3D models with shape distributions[END_REF][START_REF] Osada | Shape distributions[END_REF] measures a set of shape characteristics for a random set of points belonging to the object, using appropriate shape functions, e.g. the D2 function which measures the distance between two random surface points. Ohbuchi et al. [START_REF] Ohbuchi | Shape-similarity search of 3D models by using enhanced shape functions[END_REF] proposed enhanced shape functions, namely the (absolute) angle distance histogram for inconsistently oriented meshes, which are extensions of the D2 shape distribution. Zaharia et al. [START_REF] Zaharia | 3D shape-based retrieval within the mpeg-7 framework[END_REF] presented the 3D shape spectrum descriptor which is the histogram that describes the angular representation of the first and second principal curvature along the surface of the 3D object. In [START_REF] Sundar | 3D shape matching with 3D shape contexts[END_REF] Koertgen et al. make use of 3D shape contexts which are histograms each one corresponding to a surface point and capturing the distribution of the relative coordinates of the remaining surface points.

Graph-based methods use hierarchical structures to represent 3D objects and the similarity is measured using graph-matching techniques. These methods are suited to intra-class search, i.e. searching within very similar objects at different poses (articulations) but they have limited discrimination ability in generic object retrieval. Hilaga et al. [START_REF] Hilaga | Topology matching for fully automatic similarity estimation of 3D shapes[END_REF] introduced the multi-resolution Reeb graph, which represents a 3D objects topology and skeletal structure at various levels of detail. In [START_REF] Zhang | Retrieving articulated 3-d models using medial surfaces and their graph spectra[END_REF] Zhang et al. consider the use of medial surfaces to compute an equivalent directed acyclic graph of an object. In the work of Sundar et al. [START_REF] Sundar | Skeleton based shape matching and retrieval[END_REF], the 3D object passes through a thinning process producing a set of skeletal points, which finally form a directed acyclic graph by applying the minimum spanning tree algorithm. Cornea et al. [START_REF] Cornea | 3D object retrieval using many-to-many matching of curve skeletons[END_REF] propose the use of curve skeletons produced by the application of the generalized distance field to the volume of the 3D object and similarity is measured using the earth mover's distance. The P3DS descriptor developed by Kim et al. [START_REF] Kim | A new mpeg-7 standard: Perceptual 3-d shape descriptor[END_REF] uses an attributed relational graph whose nodes correspond to parts of the object that are represented using ellipsoids and the similarity is computed by employing the earth mover's distance.

A plurality of methods exists that use spherical functions to parameterize the shape of a 3D object. These methods exhibit good discrimination ability in general but most of them cannot capture shape features uniformly. This happens when the longitude-latitude parameterization is adopted that results in non-uniform sampling between the poles of the spherical function. Vranic [START_REF] Vranic | 3D Model Retrieval[END_REF] proposed the Ray-based descriptor which characterizes a 3D object by a spherical extent function capturing the furthest intersection points of the model's surface with rays emanating from the origin. Spherical harmonics or moments can be used to represent the spherical extent function. A generalization of the previous approach [START_REF] Vranic | 3D Model Retrieval[END_REF] uses several spherical extent functions of different radii. The GEDT descriptor proposed by Kazhdan et al. [START_REF] Kazhdan | Rotation invariant spherical harmonic representation of 3D shape descriptors[END_REF] is a volumetric representation of the Gaussian Euclidean Distance Transform of a 3D object, expressed by norms of spherical harmonic frequencies. In [START_REF] Papadakis | Efficient 3D shape matching and retrieval using a concrete radialized spherical projection representation[END_REF], the CRSP descriptor was proposed which uses the Continuous PCA (CPCA) along with Normals PCA (NPCA) to alleviate the rotation invariance problem and describes a 3D object using a volumetric sphericalfunction based representation expressed by spherical harmonics. Yu et al. [START_REF] Yu | 3D model retrieval with morphing-based geometric and topological feature maps[END_REF] used spherical functions to describe the topology and concavity of the surface of a 3D object and the amount of effort required to transform it to its bounding sphere. Generalizing from 2D to 3D, Novotni et al. [START_REF] Novotni | 3d zernike descriptors for content based shape retrieval[END_REF] presented the 3D Zernike descriptor, Daras et al. [START_REF] Daras | Efficient 3-D model search and retrieval using generalized 3-D radon transforms[END_REF] introduced the generalized radon transform, Ricard et al. [START_REF] Ricard | Generalization of angular radial transform for 2D and 3D shape retrieval[END_REF] developed the 3D ART descriptor by generalizing the 2D angular radial transform and Zaharia et al. [START_REF] Zaharia | Shape-based retrieval of 3D mesh models[END_REF] proposed the C3DHTD descriptor by generalizing the 2D Hough Transform.

Hybrid methods

Besides the previous categories, combinations of different methods have been considered in order to enhance the overall performance, which comprise a third category.

Vranic developed a hybrid descriptor called DESIRE [START_REF] Vranic | Desire: a composite 3D-shape descriptor[END_REF], that consists of the Silhouette, Ray and Depth buffer based descriptors, which are combined linearly by fixed weights. The approach of Bustos et al. [START_REF] Bustos | Automatic selection and combination of descriptors for effective 3D similarity search[END_REF] assumes that the classification of a particular dataset is given, in order to estimate the expected performance of the individual shape descriptors for the submitted query and automatically weigh the contribution of each method. However, in the general case, the classification of a 3D model dataset is not fixed since the content of a 3D model dataset is not static. In the context of partial shape matching, Funkhouser et al. [START_REF] Funkhouser | Partial matching of 3D shapes with priority-driven search[END_REF] use the predicted distinction performance of a set of descriptors based on a preceeding training stage and perform a priority driven search in the space of feature correspondences to determine the best match of features between a pair of models. The disadvantages of this approach is its time complexity which is prohibitive for online interaction as well as the storage requirements for the descriptors of all the models in the database. Based on the idea of combining features obtained from 2D and 3D representations, Song et al. [START_REF] Song | Shape-based 3D model retrieval[END_REF] developed a descriptor that described an object by obtaining a set of orthogonal projections from different viewpoints and by measuring the curvature of the object's surface. Similar in spirit, Papadakis et al. [37] proposed a hybrid descriptor formed by combining features extracted from a depth-buffer and spherical-function based representation, with enhanced translation and rotation invariance properties. The advantage of this method over similar approaches is the top discriminative power along with minimum space and time requirements.

Relevance Feedback in 3D object retrieval

In order to enable the machine to retrieve information through adapting to individual categorization criteria, relevance feedback (RF) was introduced as a means to involve the user in the retrieval process and guide the retrieval system towards the target. Relevance feedback was first used to improve text retrieval [START_REF] Rochio | Relevance Feedback in Information Retrieval The SMART Retrieval System -Experiments in Automatic Document Processing[END_REF], later on successfully employed in image retrieval systems and lately in a few 3D object retrieval systems. It is the information that is acquired from the user's interaction with the retrieval system about the relevance of a subset of the retrieved results. Further information on relevance feedback methods can be found in [START_REF] Ruthven | A survey on the use of relevance feedback for information access systems[END_REF], [START_REF] Crucianu | Relevance feedback for image retrieval: a short survey[END_REF], [START_REF] Zhou | Exploring the nature and variants of relevance feedback[END_REF] and [START_REF] Papadakis | Relevance feedback in content-based 3d object retrieval: A comparative study[END_REF].

Local relevance feedback (LRF), also known as pseudo or blind relevance feedback, is different from the conventional approach in that the user does not actually provide any feedback at all. Instead, the required training data are obtained based only on the unsupervised retrieval result. The procedure comprises two steps. First, the user submits a query to the system which uses a set of low-level features to produce a ranked list of results which is not displayed to the user. Second, the system reconfigures itself by only using the top m matches of the list, based on the assumption that most likely they are relevant to the user's query.

LRF was first employed in the context of text retrieval, in order to extend the keywords comprising the query with related words from the top ranked retrieved documents. Apart from a few studies that incorporated RF in 3D object retrieval [START_REF] Elad | Content based retrieval of vrml objects: an iterative and interactive approach[END_REF], [START_REF] Bang | Feature space warping: An approach to relevance feedback[END_REF], [START_REF] Atmosukarto | Feature combination and relevance feedback for 3D model retrieval[END_REF], [START_REF] Lou | A reconfigurable 3D engineering shape search system part ii: Database indexing, retrieval and clustering[END_REF], [START_REF] Leifman | Semantic-oriented 3d shape retrieval using relevance feedback[END_REF], [START_REF] Akbar | Multifeature integration with relevance feedback on 3D model similarity retrieval[END_REF], [START_REF] Novotni | Evaluation of kernel based methods for relevance feedback in 3D shape retrieval[END_REF], LRF has only lately been examined in [START_REF] Papadakis | Relevance feedback in content-based 3d object retrieval: A comparative study[END_REF].

Computation of the PANORAMA descriptor

In this Section, we first describe the steps for the computation of the proposed descriptor (PANORAMA), namely: (i) pose normalization (Section 3.1), (ii) extraction of the panoramic views (Section 3.2) and (iii) feature extraction (Section 3.3). Finally, in Section 3.4 we describe a weighing scheme that is applied to the features and the procedure for comparing two PANO-RAMA descriptors.

Pose normalization

Prior to the extraction of the PANORAMA descriptor, we must first normalize the pose of a 3D object, since the translation, rotation and scale characteristics should not influence the measure of similarity between objects.

To normalize the translation of a 3D model we compute its centroid using CPCA [START_REF] Vranic | 3D Model Retrieval[END_REF]. In CPCA, the centroid of a 3D mesh model is computed as the average of its triangle centroids where every triangle is weighed proportionally to its surface area. We translate the model so that its centroid coincides with the origin and translation invariance is achieved as the centroids of all 3D models coincide.

To normalize for rotation, we use CPCA and NPCA [START_REF] Papadakis | Efficient 3D shape matching and retrieval using a concrete radialized spherical projection representation[END_REF] in order to align the principal axes of a 3D model with the coordinate axes. First, we align the 3D model using CPCA to determine its principal axes using the model's surface area distribution and then we use NPCA to determine its principal axes using the surface orientation distribution. Both methods use Principal Component Analysis (PCA) to compute the principal axes of the 3D model. The difference between the two methods lies in the input data that are used for the computation of the covariance matrix. In particular, in CPCA the surface area coordinates are used whereas in NPCA the surface orientation coordinates are used which are obtained from the triangles' normal vectors. The full detailed description regarding the formulation of CPCA and NPCA can be found in [START_REF] Vranic | 3D Model Retrieval[END_REF] and in our previous work [START_REF] Papadakis | Efficient 3D shape matching and retrieval using a concrete radialized spherical projection representation[END_REF], respectively. Thus, we obtain two alternative aligned versions of the 3D model, which are separately used to extract two sets of features that are integrated into a single feature vector (see Section 3.4).

The PANORAMA shape descriptor is rendered scale invariant, by normalizing the corresponding features to the unit L 1 norm. As will be later described in Sections 3.3.1 and 3.3.2, the features used by the PANORAMA descriptor are obtained from the 2D Discrete Fourier Transform and 2D Discrete Wavelet Transform. The respective coefficients are proportional to the object's scale, therefore by normalizing the coefficients to their unit L 1 norm we are in fact normalizing all objects to the same scale.

Extraction of panoramic views

After the normalization of a 3D model's pose, the next step is to acquire a set of panoramic views.

To obtain a panoramic view, we project the model to the lateral surface of a cylinder of radius R and height H = 2R, centered at the origin with its axis parallel to one of the coordinate axes (see figure 1). We set the value of R to 3 * d mean where d mean is the mean distance of the model's surface from its centroid. For each model, the value of d mean is determined using the diagonal elements of the covariance matrix used in CPCA that give the average distances of the model's surface from the coordinate axes. Setting R = 3 * d mean does not imply that a 3D model will necessarily lie completely inside the cylinder. However, this approach is better than using a bounding cylinder, that may contain the model in small scale in the presence of outlying parts of the model. The empirical value 3 * d mean enables the majority of 3D models to lie completely inside the cylinder, while having a suitable scale to produce a descriptive projection.

In the following, we parameterize the lateral surface of the cylinder using a set of points s(ϕ, y) where ϕ ∈ [0, 2π] is the angle in the xy plane,y ∈ [0, H] and we sample the ϕ and y coordinates at rates 2B and Fig. 1 The cylinder used for acquiring the projection of a 3D model. B, respectively (we set B = 64). We sample the ϕ dimension at twice the rate of the y dimension to account for the difference in length between the perimeter of the cylinder's lateral surface and its height. Although the perimeter of the cylinder's lateral surface is π 3 times its height, we set the sampling rates at 2B and B respectively, since it was experimentally found as the best trade-off between effectiveness and efficiency. Thus we obtain the set of points s(ϕ u , y v ) where

ϕ u = u * 2π/(2B), y v = v * H/B, u ∈ [0, 2B -1] and v ∈ [0, B -1]
. These points are shown in figure 2.

The next step is to determine the value at each point s(ϕ u , y v ). The computation is carried out iteratively for v = 0, 1, ..., B -1, each time considering the coplanar s(ϕ u , y v ) points i.e. a cross-section of the cylinder at height y v and for each cross-section we cast rays from its center c v in the ϕ u directions. In figure 3 we show the points s(ϕ u , y v ) of the top-most cross-section (v = B -1) of the projection cylinder along with the respective rays emanating from the center of the cross-section. The cylindrical projections are used to capture two characteristics of a 3D model's surface; (i) the position of the model's surface in 3D space and (ii) the orientation of the model's surface. To capture these characteristics we use two kinds of cylindrical projections s 1 (ϕ u , y v ) and s 2 (ϕ u , y v ). By default, the value of a point s k (ϕ u , y v ), k ∈ {1, 2} is set to zero.

To capture the position of the model's surface, for each cross-section at height y v we compute the distances from c v of the intersections of the model's surface with the rays at each direction ϕ u .

Let pos(ϕ u , y v ) denote the distance of the furthest from c v point of intersection between the ray emanating from c v in the ϕ u direction and the model's surface, then: Thus the value of a point s 1 (ϕ u , y v ) lies in the range [0,R], where R denotes the radius of the cylinder.

s 1 (ϕ u , y v ) = pos(ϕ u , y v ) (1)
A cylindrical projection can be viewed as a 2D grayscale image where pixels correspond to the s k (ϕ u , y v ) intersection points and their values are mapped to the [black, white] space in a manner reminiscent to cylindrical texture mapping, see [START_REF] Theoharis | Graphics and Visualization: Principles and Algorithms[END_REF]. In figure 4 (a), we show an example 3D model along with a projection cylinder aligned with the z-axis. In figure 4 (b) the unfolded visual representation of its respective cylindrical projection s 1 (ϕ u , y v ) is given.

To capture the orientation of the model's surface, for each cross-section at height y v we compute the intersections of the model's surface with the rays at each direction ϕ u and measure the angle between a ray and the normal vector of the triangle that is intersected. To determine the value of a point s 2 (ϕ u , y v ) we use the cosine of the angle between the ray and the normal vector of the furthest from c v intersected triangle of the model's surface.

Let ang(ϕ u , y v ) denote the above angle then the values of the s 2 (ϕ u , y v ) points are given by:

s 2 (ϕ u , y v ) = | cos(ang(ϕ u , y v ))| n (2)
In figure 4 (c) the unfolded visual representation of the cylindrical projection s 2 (ϕ u , y v ) is given for the model shown in figure 4 (a).

We take the n th power of | cos(ang(ϕ u , y v ))|, where n ≥ 2, since this setting enhances the contrast of the produced cylindrical projection which was experimentally found to be more discriminative. Setting n to any value within [START_REF] Olsen | A taxonomy of modeling techniques using sketch-based interfaces[END_REF][START_REF] Shilane | The princeton shape benchmark[END_REF] gave the best results while taking the absolute value of the cosine is necessary to deal with inconsistently oriented triangles along the object's surface. We do not enhance the contrast of the s 1 (ϕ u , y v ) projection since it was found to produce less discriminative features.

Although the cylindrical projection captures a large part of the shape of a model, a single cylindrical projection may not be able to capture concave parts. In figure 5 we show a typical example of this. Figure 5 (a) shows the 3D model of a cup and figure 5 (b) shows the produced cylindrical projection when using a projection cylinder that is aligned with the z axis. As can be observed, this projection cannot capture the interior part of the cup.

To alleviate this problem, we compute cylindrical projections from differently oriented cylinders, i.e. cylinders that are aligned with all coordinate axes in order to obtain a more informative 3D model representation. Thus, we project a 3D model to the lateral surfaces of three cylinders, each one aligned with a different coordinate axis as shown in figure 5 where t ∈ {x, y, z} denotes the axis that the cylinder is aligned with. For the cylindrical projections that are aligned with the x and y axes, the ϕ u variable is measured at the yz and zx planes respectively while all other notations remain the same.

Feature representation of panoramic views

In this Section, we detail the procedure for the generation of a set of features that describe a panoramic view. Toward this goal, we use the 2D Discrete Fourier Transform (Section 3.3.1) and 2D Discrete Wavelet Transform (Section 3.3.2).

2D Discrete Fourier Transform

For each cylindrical projection s k,t (ϕ u , y v ) (k ∈ {1, 2} and t ∈ {x, y, z}), we compute the corresponding 2D Discrete Fourier Transform (DFT), which is given by:

F k,t (m, n) = 2B-1 u=0 B-1 v=0 s k,t (ϕ u , y v ) • e -2jπ( mu 2B + nv B ) (3)
where m ∈ [0, 2B -1] and n ∈ [0, B -1]. Since s k,t (ϕ u , y v ) is a real-valued function, the Hermitian symmetry property holds for the Fourier coefficients, i.e. F k,t (u, v) = F * k,t (2B -u, B -v), where F * denotes the complex conjugate. Hence, the size of the non-redundant information is a set of ( 2B 2 + 1) * ( B 2 + 1) Fourier coefficients for each projection. Next, we store the absolute values of the real and imaginary part of each coefficient and normalize the coefficients to the unit L 1 norm, which ensures scaling invariance as explained in Section 3.1.

In practice, most of the energy of the Fourier coefficients is concentrated on the four corners of the image of the transform, as can be seen in figure 6 (a). Therefore, we only keep a subset of the full set of Fourier coefficients, i.e. those containing most of the energy. This can be straightforwardly done by considering an ellipse positioned at the center of the Fourier image and discarding all the coefficients that lie on the interior of the ellipse, as shown in figure 6 (b). The ratio of the width to the height of the ellipse is equal to the ratio of the width to the height of the Fourier image and the size of the ellipse is set so that the low energy coefficients that are discarded correspond to approximately 35% of the total number of coefficients per projection.

After the completion of all previous operations, the resulting coefficients are denoted by Fk,t . Thus, the final feature set s F of Fourier coefficients for a particular aligned version of a 3D object is denoted by:

s F = F1,x , F2,x , F1,y , F2,y , F1,z , F2,z (4)

2D Discrete Wavelet Transform

For each cylindrical projection s k,t (ϕ u , y v ) (k ∈ {1, 2} and t ∈ {x, y, z}), we compute the corresponding 2D Discrete Wavelet Transform (DWT), which is given by:

W ϕ k,t (j 0 , m, n) = 1 √ 2B • B • 2B-1 u=0 B-1 v=0 s k,t (ϕ u , y v ) • ϕ j0,m,n (u, v) (5)
W ψ k,t (j, m, n) = 1 √ 2B • B • 2B-1 u=0 B-1 v=0 s k,t (ϕ u , y v ) • ψ j,m,n (u, v) (6)
where m ∈ [0, 2B -1], n ∈ [0, B -1], j ≥ j 0 is the scale of the multi-level DWT, j 0 is the starting scale and ϕ j0,m,n (u, v), ψ j,m,n (u, v) is the scaling and wavelet function respectively. The W ϕ k,t (j 0 , m, n) approximationscaling coefficients correspond to the low-pass subband of the transform at the starting scale j 0 . The W ψ k,t (j, m, n) detail-wavelet coefficients correspond to the vertical, horizontal and diagonal subbands. We take the absolute values of the coefficients and normalize to their L 1 norm, which are now denoted as W ϕ k,t (j 0 , m, n) and W ψ k,t (j, m, n).

In figure 7, we show the image of a 2-level wavelet transformation of a cylindrical projection. The transform is shown in negative colors to better point out the detail coefficients.

In our implementation, we computed the DWT of each cylindrical projection up to the last level. In particular, since the dimensions of a cylindrical projection are (2B) • (B), the total number of levels of the DWT are log 2 B and thus j = 0, 1, ...log 2 B -1.

To compute the DWT we have used the Haar and Coiflet (C6) filters (basis functions), as they attained the best overall performance. Therefore, two distinctive DWTs are computed, the first using the Haar and the second using the Coiflet basis functions.

Instead of using directly the coefficients of the DWT as shape features, we compute a set of standard statistic image features that are listed below: where n x , n y are the dimensions of an image I(x,y).

In our case, the above features are computed for each sub-image of the DWT, i.e. for each subband in every level of the DWT. Therefore, I(x, y) is replaced by the W ϕ k,t (j 0 , m, n) and W ψ k,t (j, m, n) coefficients accordingly. Since we have log 2 B levels in the DWT, the total number of subbands per cylindrical projection is (3 * log 2 B + 1). Hence, since we use two wavelet basis functions and three statistic image features, we obtain a total of 2 * 3 * (3 * log 2 B + 1) features per cylindrical projection which are denoted as Ṽk,t and the final feature set s W for a particular aligned version of a 3D object is denoted as:

s W = Ṽ1,x , Ṽ2,x , Ṽ1,y , Ṽ2,y , Ṽ1,z , Ṽ2,z (10)

Features weighing and matching

The features that were generated for each panoramic view are weighed by a factor w t , according to the orientation of the cylinder (x,y or z) that was used to acquire the cylindrical projection. We apply this weighing based on the observation that not all cylindrical projections capture the same amount of information about the model's shape. The t-projection cylinder that is parallel to the t coordinate axis corresponds to one of the principal axes of the 3D model that were determined in the rotation normalization step. The amount of information that is captured by the t-cylindrical projection is directly related to the principal axes of the model's surface that are encoded, as is demonstrated in figure 8 for an example 3D model of a race car. In this example, the first, second and third principal axis of the object's surface is aligned with the x,y and z axis respectively, therefore the most informative cylindrical projection corresponds to the x-projection cylinder (figure 8 (d)), followed by the y-projection cylinder (figure 8 (c)) and the least informative z-projection cylinder (figure 8 (b)). We set the factors w t to fixed values that were determined experimentally as w x = 0.51, w y = 0.31 and w z = 0.18. To compute the distance between the same aligned version (CPCA or NPCA) of two 3D objects, we compute the distances between the corresponding sets of features. We denote the features set of a particular aligned version of an object by:

p l = (s F,l , s W,l ), l ∈ {cpca, npca} (11)
and the full PANORAMA descriptor of 3D object by:

P = (p cpca , p npca ) ( 12
)
Considering the features sets p l , ṕl of two 3D objects of the same aligned version l, the distance is computed by:

d l (p l , ṕl ) = L 1 (s F,l , śF,l ) + D can (s W,l , śW,l ) (13)
where L 1 (, ), D can (, ) denotes the Manhattan and the Canberra distance [START_REF] Kokare | Comparison of similarity metrics for texture image retrieval[END_REF] respectively, each one normalized to the [0,1] space. The overall similarity between two 3D objects is measured by computing the distance between the sets of features of the same aligned version and the comparison that gives the minimum distance between the two alignments, sets the final score. Thus the overall distance D(P, Ṕ) between two PANORAMA descriptors P and Ṕ is given by:

D(P, Ṕ) = min l d l (p l , ṕl ) ( 14
)

Local Relevance Feedback (LRF) technique

In this section, we outline the major points of the employed LRF method whose detailed description can be found in [START_REF] Papadakis | Relevance feedback in content-based 3d object retrieval: A comparative study[END_REF]. The method comprises two stages, the online and the off-line stage.

During the off-line stage, the descriptor of each stored object is updated using its k nearest neighbors in feature space. These are assumed to belong to the same class and the updated descriptor is the average of the original descriptor and a weighed centroid of the k nearest neighbors.

During the on-line stage, a user submits a query to the system which finds within the updated feature space its k nearest neighbors and updates its descriptor according to rule that was applied during the off-line stage. The updated descriptor of the query is then used to measure its similarity against every object of the database and display the results.

The relevance assumption for the k nearest neighbors is not always valid as irrelevant objects that may belong to the k nearest neighbors will be mistaken as relevant. This is known as query drift and implies the scenario where the retrieval system is misled by the irrelevant data and drawn away from the user's target. However, if the features that are used to compare two objects are discriminative enough to cluster most objects that belong to the same class, then the relevance assumption will be valid in the majority of cases and the average performance will be better.

In [START_REF] Papadakis | Relevance feedback in content-based 3d object retrieval: A comparative study[END_REF] it was shown that LRF increased the performance of the CRSP descriptor [START_REF] Papadakis | Efficient 3D shape matching and retrieval using a concrete radialized spherical projection representation[END_REF]. The PANORAMA descriptor is far more discriminative therefore reducing the negative effect of the query drift phenomenon and rendering LRF more applicable.

The number k of nearest neighbors that are considered as relevant to a query is determined by the expected recall of the employed shape features near the neighborhood of a query. In this case, setting k=4 gave the best results which amounts to approximately 30% of the objects of a class on average, for the datasets used in Section 5.

Results

We next present the results of an extensive evaluation of the proposed PANORAMA descriptor and LRF technique. We tested performance using the following standard 3D model datasets: Table 1 gives the characteristics of these datasets. To evaluate the performance we use precision-recall diagrams. Recall is the ratio of relevant to the query retrieved models to the total number of relevant models while precision is the ratio of relevant to the query retrieved models to the number of retrieved models. The evaluations were performed by using each model of a dataset as a query in the remaining set of models and computing the average precision-recall performance overall models.

Robustness

In this Section we test the robustness of the PANO-RAMA descriptor under the presence of noise. We have experimented with various degrees of Gaussian noise added along the surface of each 3D object as shown in figure 9. Apparently, adding Gaussian noise with σ > 0.01 has a destructive effect on the object's surface and most of the geometric details are lost. We believe that noisy 3D objects such as the ones shown in figure 9 (c)-(d) are rarely encountered and practically useless, thus we are more interested in the robustness of the PANORAMA descriptor with respect to levels of noise that compare to the examples shown in figure 9 (b). Since the PANORAMA descriptor is based on normalizing the rotation of a 3D object, we measured the effect of noise in the determination of the object's principal axes for CPCA and NPCA. The results of this experiment are shown in table 2 where we show the average angular perturbation of the object's principal axes after the addition of noise within the PSB dataset.

Table 2. Effect of noise in the determination of principal axes for the CPCA and NPCA rotation normalization methods within the PSB dataset.

Alignment method σ = 0.01 σ = 0.03 σ = 0.05 CPCA 6 • 6.6

• 7.4 • NPCA 10.4 • 14 • 16.8 •
It is easy to understand that a certain change in the coordinates of the vertices that comprise a polygon has a greater relative impact on the orientation of the polygon's normal vector. This can be demonstrated in figure 10 where we show the depth buffers that are obtained after adding the same degrees of Gaussian noise for the bunny 3D object of figure 9 (a). Apparently, the effect of noise is more clearly noticed in figure 9 in contrast to figure 10 where only the depth is used. Thus, the fact that the NPCA alignment method is affected by noise to a greater degree than CPCA is a reasonable result. Hence, we can say that CPCA is more robust than NPCA with respect to noise.

Nevertheless, a perturbation of the object's principal axes after the addition of noise does not necessarily mean that the alignment of 3D objects is worse and lead to reduced performance in 3D object retrieval. For example, if the principal axes of 3D objects are perturbed toward the same directions for objects of the same class, then we expect to attain similar retrieval performance.

In the sequel, we evaluate the performance of the PANORAMA descriptor before and after the addition of different levels of Gaussian noise along the surface of 3D objects as was performed previously. However, we should note that the performance of the descriptor is not only affected by the perturbed principal axes but also from the alternated surface of 3D objects after the addition of noise which would result in different cylindrical projections as well as features. In figure 11, we demonstrate the performance in terms of precision and recall within the PSB dataset. This experiment demonstrates that the PANORAMA descriptor is very robust with respect to reasonable levels of noise, as in the case where σ = 0.01. In this case, we can see that the performance of PANORAMA is totally unaffected while for greater levels of noise (σ = 0.03 and σ = 0.05) the performance decreases on a reasonable scale compared to the destructive effect of noise that is demonstrated in figure 9.

Justification of PANORAMA settings

In this Section we demonstrate the increase in retrieval performnace that is achieved due to specific settings of the PANORAMA descriptor. In particular, in figure 12 (a) we compare the performance when using s 1,t (ϕ u , y v ), s 2,t (ϕ u , y v ) or both and in figure 9 (b) we evaluate the performance between using a single and using three perpendicular cylinders aligned with the coordinate axes. The results clearly show that a significant increase in discriminative power is attained when capturing both the surface depth and orientation as well as using three perpendicular cylinders instead of one. In figure 13, we give the precision-recall diagrams comparing the proposed PANORAMA descriptor against the other descriptors and show the increase in performance when LRF is employed. It is evident that the PANORAMA descriptor attains a better overall performance compared to the other methods. Interestingly, although the LF descriptor uses a plurality of 2D images (100 orthogonal projections) it is outperformed by the PANORAMA descriptor which uses a total of 12 cylindrical projections that are acquired from just three perpendicular cylinders. In addition, the PA-NORAMA descriptor is more discriminative than the 2D/3D Hybrid descriptor which uses a total of 12 orthogonal projections combined with 48 spherical functions. This strongly suggests that the cylindrical projection is a more effective representation for the purpose of 3D object retrieval compared to the conventional orthogonal projection and spherical function based representation. This is also confirmed by comparing PANO-RAMA with the DESIRE descriptor that also uses 12 orthogonal projections (6 depth buffers and 6 silhouettes) as well as features extracted using a spherical function.

In addition, it is evident that LRF adds a major gain in the overall performance, particularly on the CCCC, WM-SHREC and PSB datasets. This indicates that the query drift phenomenon that comes with LRF is compensated for the increased precision of the PA-NORAMA descriptor within the top retrieved results. These results are coherent to those that were obtained using the CRSP descriptor in [START_REF] Papadakis | Relevance feedback in content-based 3d object retrieval: A comparative study[END_REF] and show that the employed LRF technique is general purpose and can be applied to any retrieval method as long as precision is high near the neighborhood of the query. It is also worth noticing that the LRF technique increases precision mainly at higher values of recall, as can be seen in figure [START_REF] Zarpalas | 3D model search and retrieval using the spherical trace transform[END_REF]. This implies that a user notices the increase in performance as he browses through the list of results until most or all models appear that belong to the query's class. It also implies that employing LRF more than once before showing the results to the user will not add any further gain in the retrieval performance. This is because the employed LRF technique uses the k nearest neighbors of a 3D model to update its descriptor but since precision is not increased at the early stages of recall, the k nearest neighbors of the model after employing LRF will mostly be the same as before employing LRF.

To further quantify the performance of the compared methods, we next employ the following measures:

-Nearest Neighbor (NN): The percentage of queries where the closest match belongs to the query's class. -First Tier (FT) : The recall for the (C -1) closest matches were C is the cardinality of the query's class. -Second Tier (ST) : The recall for the 2(C -1) closest matches were C is the cardinality of the query's class.

These measures range from 0%-100% and higher values indicate better performance. In table 2, we give the scores of each method for each measure for all datasets. Apparently, the PANORAMA descriptor consistently outperforms all compared methods with respect to these measures as well. We can also observe that the nearest neighbor score is not particularly affected by the application of LRF, compared to the first and second tier measures whose values are significantly increased after employing LRF. This confirms our earlier conclusion that LRF does not change the precision at the early stages of recall and therefore it does not add any further gain in performance if it is applied multiple times.

As described in Section 3.3, the PANORAMA descriptor uses two kinds of features, namely those coming from the 2D DFT (s F ) and the 2D DWT (s W ). Comparing the retrieval performance between the two kinds, the s F component was found to be more effective in most datasets than the s W part. In fact, the s W part had a slight advantage in retrieval performance within the WM-SHREC and ESB datasets. Overall however, the s F part is about 3% better in terms of average precision, which can be justified by the fact that s F has greater dimensionality than the s W part. In particular, the dimensionality of s F is 2 * ( 2B 2 + 1) * ( B 2 + 1) while for the s W component it is only 2 * 3 * (3 * log 2 B + 1). Since we set the bandwidth to B = 64, this amounts to a dimension of 4160 and 114 respectively. This implies, that we can attain comparable retrieval performance using just the s W part of the full descriptor. This is a significant advantage of the proposed method as it can be rendered much more efficient by reducing its storage requirements and time complexity, with negligible cost in discriminative power. Altogether, the PANORAMA descriptor is very efficient in computation and comparison time. On a standard contemporary machine, it takes less than one second to extract and pairwise comparison time is approximately 0.23 ms which enables real-time retrieval from large repositories. These are the average values over the total set of models from the datasets used in our evaluation.

In figure 14, we provide a few examples of queries and the respective top 5 retrieved models from the PSB dataset using the proposed PANORAMA descriptor.

Conclusions

In this paper, we presented a novel 3D shape descriptor called PANORAMA, that allows effective contentbased 3D model retrieval exhibiting superior performance, compared to other state-of-the-art approaches. PANORAMA is based on a novel 3D shape representation that uses a set of panoramic views of the 3D model which are obtained by projecting the model to the lateral surfaces of a set of cylinders that are aligned with the model's principal axes. A panoramic view is particularly descriptive of an object's shape as it cap-tures a large portion of the object that would otherwise require multiple orthogonal projections from different viewpoints. It is also beneficial compared to spherical function based representations as the underlying sampling is uniform in the Euclidean space.

The 2-dimensional parameterization of a cylindrical projection allows the application of a variety of 2D features used for 2D shape-matching to be directly applied in the context of 3D shape matching. In this paper we have used the 2D Discrete Fourier Transform together together with the 2D Discrete Wavelet Transform and their combination enables very effective and efficient 3D object retrieval. Using only the wavelet features part of the descriptor, we can greatly increase efficiency in terms of storage requirements and time complexity, with negligible cost in discriminative power.

Moreover, we have used the PANORAMA descriptor to examine the application of local relevance feedback in the context of content-based 3D object retrieval, using the method that was proposed in [START_REF] Papadakis | Relevance feedback in content-based 3d object retrieval: A comparative study[END_REF]. The results of the evaluation showed that this method can add a considerable gain in the overall retrieval performance and can be readily applied to other retrieval methods that exhibit high precision near the neighborhood of the query.

Fig. 2

 2 Fig.2The discretization of the lateral surface of the projection cylinder (points in orange) to the set of points s(ϕu, yv).

Fig. 3

 3 Fig.3The top-most cross section of the cylinder along with the corresponding rays emanating from the center of the cross-section c B-1 .

Fig. 4

 4 Fig. 4 (a) Pose normalized 3D model, (b) the unfolded cylindrical projection of the 3D model capturing the position of the surface (c) the unfolded cylindrical projection of the 3D model capturing the orientation of the surface.

Fig. 5 (

 5 Fig. 5 (a) A 3D model of a cup and (b)-(d) the corresponding cylindrical projections s 1,t (ϕu, yv) using three cylinders each one aligned with the z,y and x coordinate axis respectively.

Fig. 6 (

 6 Fig. 6 (a) A typical 2D Fourier transform of a cylindrical projection; (b) The Fourier coefficients that lie inside the green-colored area are discarded to reduce dimensionality.

Fig. 7 2

 7 Fig. 7 2-level wavelet transformation of a cylindrical projection of an airplane (the image is shown in negative colors).

Fig. 8 (

 8 Fig. 8 (a) A 3D model of a car and (b)-(d) the respective cylindrical projections s 1,t (ϕu, yv) and s 2,t (ϕu, yv) for t = z, t = y and t = x respectively.

  (i.) The classified dataset of CCCC [9]. (ii.) The classified dataset of the National Taiwan University Benchmark (NTU, http://3d.csie.ntu.edu.tw/). (iii.) The dataset of the Watertight Models track of SHape REtrieval Contest 2007 (WM-SHREC) [51]. (iv.) The MPEG-7 dataset (http://www.chiariglione.org/mpeg/). (v.) The test dataset of the Princeton Shape Benchmark (PSB) [6]. (vi.) The dataset of the Engineering Shape Benchmark (ESB) [52].

Fig. 9

 9 Fig. 9 Demonstration of the effect of different degrees of additive Gaussian noise on the surface of the original 3D object (a).

Fig. 10

 10 Fig. 10 Demonstration of the effect of different degrees of additive Gaussian noise on a depth buffer.

Fig. 11

 11 Fig. 11 Demonstration of the effect of different degrees of additive Gaussian noise on the retrieval performance of the PANO-RAMA descriptor.

Fig. 12

 12 Fig. 12 Performance evaluation of the PANORAMA descriptor when using: (a) s 1,t (ϕu, yv) (PANORAMA→Pos), s 2,t (ϕu, yv) (PANORAMA→Ori) or both (PANORAMA); (b) a single cylinder aligned with the z coordinate axis (PANORAMA→zprojection) and a set of three perpendicular cylinders aligned with the object's principal axes (PANORAMA).

Fig. 13

 13 Fig. 13 Precision-recall plots comparing the proposed PANORAMA descriptor against the 2D/3D Hybrid, DESIRE, LF and SH-GEDT descriptor in various 3D model datasets. The comparison includes the combination of the PANORAMA descriptor with local relevance feedback (LRF).

5. 3

 3 Comparative Evaluation We next compare the PANORAMA descriptor against the following state-of-the-art methods: -The 2D/3D Hybrid descriptor developed by Papadakis et al. [37]. -The DESIRE descriptor developed by Vranic et al. [33]. -The Light Field descriptor (LF) developed by Chen et al. [8]. -The spherical harmonic representation of the Gaussian Euclidean Distance Transform descriptor (SH-GEDT) developed by Kazhdan et al. [26].

Fig. 14

 14 Fig. 14 Examples of queries within the PSB dataset and the respective top 5 retrieved models using the PANORAMA descriptor. The retrieved objects are ranked from left to right in decreasing order of similarity.

Table 1 .

 1 Characteristics of the evaluation datasets.

	Dataset	#models #classes	type
	CCCC	472	55	generic
	NTU	549	47	generic
	WM-SHREC	400	20	generic
	MPEG-7	1300	135	generic
	PSB	907	92	generic
	ESB	866	48	CAD

Table 2 .

 2 Quantitative measures scores for the proposed PANORAMA, 2D/3D Hybrid, DESIRE, LF and SH-GEDT methods for the CCCC, NTU, WM-SHREC, MPEG-7, PSB and ESB datasets.

		CCCC
	Method	NN (%) FT (%) ST (%)
	PANORAMA+LRF	87.4	70.3	86.6
	PANORAMA	87.9	66.3	81.2
	2D/3D Hybrid	87.4	60.2	75.8
	DESIRE	82.8	55.6	70.0
	LF	79.8	50.2	63.1
	SH-GEDT	75.7	45.9	59.9
		NTU
	Method	NN (%) FT (%) ST (%)
	PANORAMA+LRF	79.1	51.6	64.3
	PANORAMA	78.6	49.0	61.5
	2D/3D Hybrid	76.2	46.6	59.1
	DESIRE	71.9	42.7	55.4
	LF	70.0	39.0	50.1
	SH-GEDT	58.8	33.9	46.3
	WM-SHREC
	Method	NN (%) FT (%) ST (%)
	PANORAMA+LRF	95.7	74.3	83.9
	PANORAMA	95.7	67.3	78.4
	2D/3D Hybrid	95.5	64.2	77.3
	DESIRE	91.7	53.5	67.3
	LF	92.3	52.6	66.2
	SH-GEDT	87.0	44.7	58.5
		MPEG-7
	Method	NN (%) FT (%) ST (%)
	PANORAMA+LRF	87.2	65.5	75.9
	PANORAMA	87.2	61.8	73.1
	2D/3D Hybrid	86.1	59.6	70.7
	DESIRE	86.4	57.7	67.7
	LF	80.2	51.7	61.9
	SH-GEDT	83.7	50.3	59.4
		PSB
	Method	NN (%) FT (%) ST (%)
	PANORAMA+LRF	75.2	53.1	65.9
	PANORAMA	75.3	47.9	60.3
	2D/3D Hybrid	74.2	47.3	60.6
	DESIRE	65.8	40.4	51.3
	LF	65.7	38.0	48.7
	SH-GEDT	55.3	31.0	41.4
		ESB
	Method	NN (%) FT (%) ST (%)
	PANORAMA+LRF	87.0	49.9	65.8
	PANORAMA	86.5	49.4	64.1
	2D/3D Hybrid	82.9	46.5	60.5
	DESIRE	82.3	41.7	55.0
	LF	82.0	40.4	53.9
	SH-GEDT	80.3	40.1	53.6


P Papadakis

I Pratikakis

T Theoharis

G Passalis

S Perantonis

3D Object Retrieval using an Efficient and Compact Hybrid Shape Descriptor

Keywords: (according to ACM CCS): I, 5, 4 [Pattern Recognition]: Computer Vision, H, 3, 3 [Information Storage and Retrieval]: Information Search and Retrieval

We present a novel 3D object retrieval method that relies upon a hybrid descriptor which is composed of 2D features based on depth buffers and 3D features based on spherical harmonics. To compensate for rotation, two alignment methods, namely CPCA and NPCA, are used while compactness is supported via scalar feature quantization to a set of values that is further compressed using Huffman coding. The superior performance of the proposed retrieval methodology is demonstrated through an extensive comparison against state-of-the-art methods on standard datasets.

Introduction

In order to efficiently search and retrieve 3D models, content-based retrieval methods are necessary that use information extracted from the shape of a 3D model. In particular, the search process is initiated by a query 3D model provided by a user and the system retrieves 3D models that are considered similar to the query. The information that is used to represent each 3D model is encoded in a signature known as shape descriptor. The shape descriptor should capture the shape of the model in a discriminative way in order to support effective comparison against models of the database. To this effect, it should be insensitive to variations in scale, translation and rotation (similarity transformations) of a 3D model which are not considered to affect the measure of similarity. Moreover, it should have a compact structure to reduce storage requirements and support fast computation of the similarity measure between models.

In this paper, we focus on the development of a 3D object retrieval methodology that is based upon a hybrid shape descriptor that provides top discriminative power and has minimal storage requirements. Based on the previous work of Passalis et al. [START_REF] Passalis | Ptk: A novel depth buffer-based shape descriptor for three-dimensional object retrieval[END_REF], we extract 2D features from a depth-buffer based representation of a model and 3D features (spherical harmonic coefficients) from a spherical function based representation as in the work of Papadakis et al. [START_REF] Papadakis | Efficient 3D shape matching and retrieval using a concrete radialized spherical projection representation[END_REF]. The novelty of our approach consists of: (i) The two kinds of features combined to produce an integrated hybrid 3D shape descriptor; (ii) Invariance to similarity transformations achieved using CPCA and NPCA [START_REF] Papadakis | Efficient 3D shape matching and retrieval using a concrete radialized spherical projection representation[END_REF], where the two methods are employed in parallel to alleviate the rotation invariance problem, for both 2D and 3D features; (iii) To reduce the size of the descriptor, scalar quantization is applied to the set of coefficients and the resulting set of symbols is Huffman coded, producing a highly compact descriptor. We demonstrate the increased performance of the proposed method through a comparison against state-of-the-art approaches on standard benchmarks that clearly indicates its superior overall performance.

Related Work

In this section, we give a brief description of the related work in the area of content-based 3D object retrieval methods. Extended state-of-the-art surveys can be found in [START_REF] Tangelder | A survey of content based 3d shape retrieval methods[END_REF], [BKS * 05], [IJL * 05] and [START_REF] Shilane | The princeton shape benchmark[END_REF].

Content-based 3D model retrieval methods may be classified into three main categories according to the spatial di- mensionality of the information used, namely 2D, 3D and their combination (2D/3D).

In the first category, shape descriptors are generated from images-projections which may be contours, silhouettes, depth buffers or other kinds of 2D information. Thus similarity is measured using 2D matching techniques used for 2D shape search. Chen et al. [START_REF] Chen | On visual similarity based 3D model retrieval[END_REF] proposed the Light Field descriptor, which is comprised of Zernike moments and Fourier coefficients computed on a set of projections taken from the vertices of a dodecahedron. Vranic [START_REF] Vranic | 3D Model Retrieval[END_REF] proposed a shape descriptor where features are extracted from depth buffers produced by six projections of the model, one for each side of a cube which encloses the model. In the same work, the Silhouette-based descriptor is proposed which uses the silhouettes produced by the three projections taken from the Cartesian planes. Zarpalas et al.

[ZDA * 07] introduce the Spherical Trace Transform descriptor, which is an extension to 3D shape matching of the 2D Trace Transform. Among a variety of 2D features which are computed over a set of planes intersecting the model, one of the components of the shape descriptor are 2D Krawtchouk moments which significantly improve the overall performance. In [PTK07], Passalis et al. proposed PTK, a depth buffer based descriptor which uses parallel projections to capture the model's thickness and an alignment scheme that is based on symmetry.

In the second category, shape descriptors are extracted from the 3D shape-geometry of the 3D model and the similarity is measured using appropriate representations in the spatial domain or in the spectral domain. Ankerst et al. [START_REF] Ankerst | Nearest neighbor classification in 3D protein databases[END_REF] proposed the Shape Histograms descriptor where 3D space can be divided into concentric shells, sectors, or both and for each part the model's shape distribution is computed, giving a sum of histograms bins. Vranic [START_REF] Vranic | 3D Model Retrieval[END_REF] proposed the Ray-based descriptor which characterizes a 3D model by a spherical extent function capturing the furthest intersection points of the model's surface with rays emanating from the origin. Spherical harmonics or moments can be used to represent the spherical extent function. A generalization of the previous approach is also described in [START_REF] Vranic | 3D Model Retrieval[END_REF], that uses several spherical extent functions of different radii. The GEDT descriptor proposed by Kazhdan et al. [START_REF] Kazhdan | Rotation invariant spherical harmonic representation of 3D shape descriptors[END_REF] is a volumetric representation of the Gaussian Euclidean Distance Transform of the 3D model's volume, expressed by norms of spherical harmonic frequencies. Shape distributions proposed by Osada et al. [START_REF] Osada R | Matching 3D models with shape distributions[END_REF], is a class of methods where several features can be computed for a random set of points belonging to the model, according to the selection of an appropriate function. In [START_REF] Papadakis | Efficient 3D shape matching and retrieval using a concrete radialized spherical projection representation[END_REF], the CRSP descriptor was proposed which uses a combination of CPCA and NPCA to alleviate the rotation invariance problem and describes a 3D model using an alternative spherical function based representation which is expressed by spherical harmonics.

Besides the previous categories, combinations of different methods have been considered in order to enhance the overall performance, which comprise a third category. Vranic developed a hybrid descriptor called DSR472 [START_REF] Vranic | 3D Model Retrieval[END_REF][START_REF] Vranic | Desire: a composite 3d-shape descriptor[END_REF], that consists of the Silhouette, Ray and Depth buffer based descriptors, which are combined linearly by fixed weights. The approach of Bustos et al. [BKS * 04] assumes that the classification of a particular dataset is given, in order to estimate the expected performance of the individual shape descriptors for the submitted query and automatically weigh the contribution of each method. However, in the general case, the classification of a 3D model dataset is not fixed since the content of a 3D model dataset is not static. In the context of partial shape matching, Funkhouser et al. [START_REF] Funkhouser | Partial matching of 3D shapes with priority-driven search[END_REF] use the predicted distinction performance of a set of descriptors based on a preceding training stage and perform a priority driven search in the space of feature correspondences to determine the best match of features between a pair of models. The disadvantages of this approach is its time complexity which is prohibitive for online interaction as well as the storage requirements for the descriptors of all the models in the database.

Hybrid 3D Shape descriptor extraction

In this Section, we describe the distinct stages for the extraction of the proposed hybrid 3D shape descriptor, namely: (i) pose normalization; (ii) 2D feature extraction; (iii) 3D feature extraction; (iv) feature compression.

Pose Normalization

Before the extraction of the hybrid features, it is necessary to normalize the pose of a 3D model as the position, orientation and size parameters of a 3D model are arbitrarily set. Thereupon, the final 3D shape descriptor should be invariant under translation, rotation and scaling.

First, we normalize each 3D model for translation by computing its centroid using CPCA [START_REF] Vranic | 3D Model Retrieval[END_REF] and translating the model so that the centroid coincides with the origin.

We address the rotation invariance problem, by following the same approach as in [START_REF] Papadakis | Efficient 3D shape matching and retrieval using a concrete radialized spherical projection representation[END_REF] where two alignment methods are used, namely CPCA and NPCA. This is a meaningful choice, since by using CPCA and NPCA we consider both the surface area distribution and the surface orientation distribution that both characterize the rotation of a model's surface and as mentioned in [START_REF] Papadakis | Efficient 3D shape matching and retrieval using a concrete radialized spherical projection representation[END_REF], there are cases where one method performs better than the other and vice versa. In particular, NPCA works better for objects with well defined flat surfaces while CPCA is better at aligning objects where their surface area distribution better discriminates the principal axes of the object. which produces two sets of hybrid features that comprise the hybrid shape descriptor. In Section 3.4 we explain how these sets are used to measure the similarity between two models.

Scaling invariance is achieved by normalizing the 3D and 2D features respectively to their unit L 1 norm since the computed features are proportional to the model's scale. Therefore, by normalizing the scale of the features we are in fact normalizing the scale of the corresponding model. The advantage is that this approach does not depend on the polygonal resolution of the 3D model but on the number of features which is set to a fixed value for all models.

2D Feature Extraction

Based on the work of [START_REF] Passalis | Ptk: A novel depth buffer-based shape descriptor for three-dimensional object retrieval[END_REF], we use a depth-buffer based representation of a 3D model to compute a set of 2D features. In Figure 1, the main steps for the computation of the 2D features are depicted.

A depth buffer is a regular grid of scalar values that holds the distance between the model's surface and a given clipping plane. Using as clipping planes the faces of a cube having constant size and center at the origin, we acquire six depth buffers by rendering the model using an orthographic projection. In Figure 1 (b), the six depth buffers of a 3D model are shown.

Using a constant sized cube means that the 3D model may not necessarily lie completely inside the cube. However, this approach is better than using the bounding cube that may contain the model in small resolution in the presence of outlying parts of the model. Thereupon, the edge of the cube E, is set empirically to a fixed value such that the majority of 3D models lies completely inside the cube, while having large enough scale to produce descriptive depth buffers. The value of E is set to E = 6 * dmean where dmean is the average distance of the model's surface from its centroid and it is easily computed using the diagonal elements of the CPCA covariance matrix as in [START_REF] Papadakis | Efficient 3D shape matching and retrieval using a concrete radialized spherical projection representation[END_REF].

Instead of storing the back D b and front D f depth buffers along each direction, we store their difference D di f =D f -D b and their sum Dsum=D f +D b (Figure 1 (c)). The two new depth buffers (D di f , Dsum) require the same storage space as the original two (D f , D b ) and there is no information loss since we can produce the one pair from the other. The difference lies in the fact that D di f holds the thickness of the model at each pixel, which is a characteristic of the model. This value is insensitive to errors in the translation of the model along the direction of projection, thus alleviating errors introduced in the translation normalization step. Dsum has no physical meaning and it is used only as a complement to D di f and therefore is considered less important. This is reflected on the weight selection as shown later.

To produce the 2D features, a spectral transformation is applied to each pair of depth buffers along each direction. The discrete 2D Fourier transform (DFT) of a depth buffer D of size S denoted as (F d ) is given by:

F d (m, n) = S-1 ∑ x=0 S-1 ∑ y=0 D(x, y) • exp -2 jπ mx + ny S (1)
To reduce the computational cost, we implement the DFT, by using the Fast Fourier Transform algorithm. As shown in Figure 1 (d) most information is concentrated on the four corners of the image. For an SxS depth buffer, we keep KxK coefficients as follows:

F(m, n) = |F d (m, n)| + |F d (m, S -n -1)| + |F d (S -m -1, n)| + |F d (S -m -1, S -n -1)| (2)
for m, n = 0, 1, ..., K -1 where we sum the norm of the coefficients from all four corners to have a reflection invariant representation. In our implementation we use depth buffers of resolution S=128 and set K=48. In the sequel, we normalize the coefficients to the unit L 1 norm and weigh the F(m,n) coefficients inversely proportionally to their degree, since lower frequency coefficients are considered to have more information compared to higher frequency coefficients, which are more sensitive to noise.

A final weighting is applied to the coefficients, based on the following observation. Each pair of depth buffers is perpendicular to a specific coordinate axis and encodes information from two of the principal directions of the 3D model which are computed from the rotation normalization step. Since the principal directions are sorted according to their degree of significance, we can intuitively assert that a pair of buffers encodes an amount of information proportional to the principal directions that it encodes, thus the coefficients of the corresponding depth buffers are weighted according to this idea. The respective weights are set to fixed values that were determined empirically. In particular, if w i j is the weight applied to the coefficients encoding the i th and j th principal direction then w 12 =3, w 13 =2 and w 23 =1 for the D di f coefficients and w 12 =1, w 13 =0.7 and w 23 =0.3 for the Dsum coefficients. The final 2D feature set is the concatenation of the coefficients of the six depth buffers. The 2D features set of model i that is aligned either by CPCA or NPCA, is denoted as 2D f j i where j ∈ {CPCA, NPCA}.

3D Feature Extraction

Based on the work of [START_REF] Papadakis | Efficient 3D shape matching and retrieval using a concrete radialized spherical projection representation[END_REF] we extract the 3D features using a spherical function-based representation of the 3D model and compute the spherical harmonics transform for each spherical function. In Figure 2, the overall procedure for the extraction of the 3D features of the hybrid 3D shape descriptor is depicted.

A spherical function describes a bounded area of the model, defined by a lower and an upper radius which delimit a spherical shell. This shell is the area in which the underlying surface of the model is represented by the equivalent spherical function points. The region corresponding to the r th spherical function is the spherical shell defined in the interval [lr,l r+1 ) where the lr boundary is given by:

lr = 0 , r = 1 r-1/2 N • M , 1 < r ≤ N + 1 (3)
where M is a weighting factor that determines the radius of the largest sphere and N is the number of spherical functions.

Multiplying by M in Eq. (3) ensures that the majority of 3D models lies completely inside the sphere with the largest radius while having large enough scale to give descriptive 3D features. Therefore, the value of M is set to half the length of the edge of the cube which was used in the 2D features extraction step, thus M = E/2.

The representation of a 3D model as a set of spherical functions is similar to projecting approximately equidistant parts of the 3D model to concentric spheres of increasing radius. This is done by computing the intersections of the surface of the model with rays emanating from the origin in the (θ j , ϕ k ) directions, denoted as ray(θ j , ϕ k ), where θ j denotes the latitude and ϕ k denotes the longitude coordinate, j, k=0,1,...2B-1 and B is the sampling bandwidth. In the direction of ray(θ j , ϕ k ) inside the spherical shell r(r ≤ N), we compute all the intersections of the model's surface with this ray. The value of the corresponding spherical function point is set to the distance of the furthest intersection point within the boundaries of the r th spherical function, or to zero if there is no intersection. Thus, if I(r, θ j ϕ k ) denotes the distance of the furthest intersection point along ray(θ j , ϕ k ) within the boundaries of the r th spherical function, then the N spherical functions representing the 3D model are given by:

fr(θ j , ϕ k ) = I(r, θ j , ϕ k ) (4)
where fr : S 2 → [lr, l r+1 ) {0}, r = 1, 2, ..., N and S 2 denotes the points (θ j ,ϕ k ) on the surface of a sphere with unit radius. These functions are shown in Figure 2 (b) for the "helicopter" example model, wherein the corresponding intersections are depicted as black dots.

Practically, if the model is viewed from the (θ j ,ϕ k ) direction then the part of the model along ray(θ j ,ϕ k ) which is closer to the origin than I(D, θ j , ϕ k ) is occluded by the intersection point corresponding to I(D, θ j , ϕ k ). As shown in [START_REF] Papadakis | Efficient 3D shape matching and retrieval using a concrete radialized spherical projection representation[END_REF], including the occluded points into the spherical functions increases discriminative power significantly. Thus, we take into account a modified version of the spherical functions fr. In particular, let I(D, θ j , ϕ k ), corresponding to the furthest intersection point on ray(θ j ,ϕ k ), be assigned to the spherical function point f D (θ j , ϕ k ). Then all fr(θ j , ϕ k ), where r < D are assigned values by setting:

fr(θ j , ϕ k ) = r • M N , ∀r < D (5)
which stands for the intersections of the ray(θ j , ϕ k ) with all the spheres of radius less than D. Thus, we get a set of modified spherical functions f r , shown in Figure 2 formally denoted as:

f r (θ j , ϕ k ) =    I(r, θ j , ϕ k ) , I(D, θ j , ϕ k ) = 0 and r = D r • M N , I(D, θ j , ϕ k ) = 0 and r < D 0 , otherwise (6)
At the final step we compute the 3D features as the spherical harmonic coefficients of each spherical function. The spherical harmonic coefficients can be computed using the spherical harmonics transform (SHT) [START_REF] Rockmore | Ffts for the 2-sphere -improvements and variations[END_REF]. We compute the SHT at constant bandwidth B = 40 for all models and choose to store only the coefficients up to the L th degree (we set L=16), since spherical harmonics of higher degree are more sensitive to noise. Using properties of spherical harmonics we can ensure axial flipping invariance. Flipping a model with respect to an axis may only change the sign of the real or the imaginary part of a coefficient thus we use their absolute values. After normalizing the coefficients to the unit L 1 norm, each coefficient is weighted inversely proportionally to its degree. The final 3D feature set is the concatenation of the spherical harmonic coefficients of the N spherical functions. The 3D features set of model i that is aligned either by CPCA or NPCA, is denoted as 3D f j i where j ∈ {CPCA, NPCA}.

Similarity in the Hybrid Scheme

As explained at Section 3.1, the 2D and 3D features are computed for two alternative rotation normalized versions of a model. Thus, the final hybrid 3D shape descriptor s i of a model i is the concatenation of the 2D and 3D features for each aligned version of the 3D model, giving:

s i = 2D f CPCA i , 2D f NPCA i , 3D f CPCA i , 3D f NPCA i (7)
To compare the descriptors s 1 and s 2 of two models we adopt the following schema to compute their distance:

Dist(s 1 , s 2 ) = dist 2D f + dist 3D f (8)
where dist 2D f and dist 3D f is the distance between the 2D and 3D features, respectively, denoted as:

dist 2D f = min j L 1 2D f j 1 , 2D f j 2 dist 3D f = min j L 1 3D f j 1 , 3D f j 2 (9)
where j ∈ {CPCA, NPCA} and L 1 is the Manhattan distance between the corresponding features.

Feature Compactness

Using two kinds of features (2D and 3D), as well as two different aligned versions of a 3D model for each kind, the issue of the descriptor's storage requirements is raised.

In Since both 2D and 3D features are normalized to their respective unit L 1 norm, the values of the hybrid features lie within the [0,1] space. We apply uniform scalar quantization and divide the [0,1] space to 2 16 = 65536 intervals of size ∆ = 1/65536. The i th interval, i = 1, 2, ..., 65536 corresponds to the [(i -1)∆, i∆) space and is represented by the mean value of the lower and upper bound of the interval. Thus, each floating point number is represented by the closest quantized value (symbol), according to the nearest neighbor rule. Figure 3 shows the probabilities P i of appearance in the hybrid 3D shape descriptor, of the first 1024 symbols.

The probability of each symbol was computed by counting its frequency from the set of descriptors of the datasets used in the experiments shown in Section 5. The overall probability of a coefficient to be quantized to one of the first 1024 symbols is more than 99,9%, while the probability of each remaining symbol is less than P 0 = 10 -6 . Thereupon, we use only 10 bits to encode 2 10 quantized symbols and the last symbol (i=1024) is used to cover the [1023∆, 1] space. After this, the hybrid descriptor requires 40704 * 10 8 * 1024 50 Kbytes.

While scalar quantization is a lossy compression method, the employed quantization scheme does not affect the discrimination ability of the hybrid descriptor. In particular, by evaluating the performance of the hybrid descriptor with and without scalar quantization the difference in average precision was less than 0.5%, which is negligible taking into account the achieved reduction in storage requirements.

To further reduce the size of the hybrid descriptor, we code the selected symbols using Huffman coding [START_REF] Proakis | Communication Systems Engineering[END_REF] which considers the probability of each symbol in order to assign a bit sequence whose length is inversely proportional to the symbol's probability. In Table 1, the Huffman codes for the first and last 3 symbols are shown. Using the computed Huffman codes, we take 2, 373 bits per coefficient on average, or equivalently, 11,79 KBytes per descriptor. Thus, we achieve an average compression ratio c = (159 -11, 79)/159 92, 6%.

Huffman coding is a lossless compression method, nevertheless, coding and decoding the symbols adds computational cost. In our case, the overall cost of employing Huffman coding was dominated by the hard disk access time, therefore, the overall time complexity of object retrieval is not considerably affected.

Experimental Evaluation

In this section, we give the results of an extensive evaluation of the proposed Hybrid descriptor and compare it against other state-of-the-art methods. We tested the performance using the following 3D model datasets:

(i.) The test set of the Princeton Shape Benchmark (PSB) (907 models) [START_REF] Shilane | The princeton shape benchmark[END_REF]. (ii.) The classified set of the National Taiwan University Benchmark (NTU) (549 models) (http://3D.csie. ntu.edu.tw/). (iii.) The classified set of the CCCC set (472 models) (http://merkur01.inf.uni-konstanz.de/CCCC/). (iv.) The MPEG-7 set (1300 models) (http://merkur01.

inf.uni-konstanz.de/CCCC/). (v.) The Engineering Shape Benchmark (ESB) set (866 models) [START_REF] Jayanti | Developing an engineering shape benchmark for cad models[END_REF].

The datasets (i)-(iv) are generic while the last dataset is a domain specific case consisting only of engineering models.

To depict the performance we use precision-recall diagrams. Recall is the ratio of relevant to the query retrieved models to the total number of relevant models while precision is the ratio of relevant to the query retrieved models to the number of retrieved models.

In Figure 4, we show the increased performance of the 2D features when using both CPCA and NPCA to alleviate the rotation invariance problem compared to using either one of the two alignment methods.

In Figure 5 we show the complementarity in the discrimination power between the selected 2D and 3D features. In Figure 5 (a), the vertical axis shows the difference between the Discounted Cumulative Gain (DCG) score of the 3D and 2D features for the NTU dataset. The DCG score is a commonly used quantitative performance measure [START_REF] Shilane | The princeton shape benchmark[END_REF] which is computed by weighing correct results according to their position in the retrieval list (the maximum score is 100%). The horizontal axis is an id-number corresponding to a specific class of 3D models as shown in Figure 5 (b). From Figure 5, we can conclude that the chosen 2D and 3D features have a complementary behavior, that is, there are classes where the 3D features are more discriminative than the 2D features and vice versa. This is also true for the rest of the datasets. Therefore, using both the selected 2D and 3D features is a meaningful choice that produces an effective hybrid descriptor.

We compare the proposed hybrid descriptor against the following state-of-the-art descriptors:

1. The Light Field (LF) descriptor [START_REF] Chen | On visual similarity based 3D model retrieval[END_REF].

The spherical harmonic representation of the Gaussian

Euclidean Distance Transform (SH-GEDT) descriptor [START_REF] Kazhdan | Rotation invariant spherical harmonic representation of 3D shape descriptors[END_REF]. 3. The DSR472 descriptor [START_REF] Vranic | 3D Model Retrieval[END_REF].

Each descriptor was computed using the executables that the authors provide at their web-pages. In Figure 6 (a), we give the precision-recall diagrams comparing the proposed Hybrid descriptor against the other descriptors in the generic datasets and in Figure 6 (b) we show the performance for the case of engineering models. It is evident that the average precision of the proposed Hybrid descriptor is significantly higher compared to the other methods in all generic datasets as well as in the ESB dataset.

To further quantify the performance of the compared methods, we use the following quantitative measures:

• Nearest Neighbor (NN): The percentage of queries where the closest match belongs to the query's class. • First Tier (FT) : The recall for the (k -1) closest matches were k is the cardinality of the query's class. • Second Tier (ST) : The recall for the 2(k -1) closest matches were k is the cardinality of the query's class.

The above measures range from 0%-100% and higher values indicate better performance.

In table 2, we give the respective scores of each method for the datasets of Figure 6. Apparently, the proposed Hybrid descriptor outperforms all compared methods with respect to the quantitative measure scores as well.

The proposed Hybrid descriptor has the additional advantage of short extraction and comparison times. Using a 2.0 Ghz AMD CPU, the average extraction and one-to-one comparison time is 1.05 s and 0.17 ms, respectively.

Conclusions

In this paper, a 3D object retrieval method is proposed that uses 2D features extracted from a depth buffer-based representation and 3D features from the spherical harmonics transformation of a spherical functions-based representation. The 3D model is normalized for rotation using two alternative alignment methods, namely CPCA and NPCA. The hybrid features are compressed using scalar quantization and Huffman coding. The result is a highly compact descriptor that achieves top performance as demonstrated through an extensive evaluation against state-of-the-art descriptors on standard datasets.

Acknowledgement

This research was supported by the Greek Secretariat of Research and Technology (PENED "3D Graphics search and retrieval" 03 E∆ 520).

  Thus, given a translation normalized 3D model we compute the CPCA and NPCA aligned version of the model c The Eurographi cs Association 2008.

Figure 1 :

 1 Figure 1: Stages of the 2D feature extraction procedure.

Figure 2 :

 2 Figure 2: Stages of the 3D feature extraction procedure.

  particular, the 2D features is a set of KxK = 48 * 48 = 2304 coefficients for each of the six depth buffers, for each aligned version of the model. Thus the 2D features component consists of 2 * 6 * 2304 = 27648 floating point numbers. The 3D features is a set of L * (L+1) 2 * 2 = 272 floating point numbers for each of the N=24 spherical functions, for each aligned version of the model. Thus the 3D features component consists of 272 * 24 * 2 = 13056 floating point numbers. In total, the hybrid descriptor consists of 40704 floating point numbers that require 159 Kbytes of storage (4 bytes each).

Figure 3 :

 3 Figure 3: Probabilities P i of quantized values of the hybrid features (Po = 10 -6 ).

Figure 4 :

 4 Figure 4: Precision-recall plot showing the perfomance of the 2D features when using either CPCA or NPCA for rotation normalization compared to the usage of both methods.

Figure 5 :

 5 Figure 5: (a) Difference between the DCG of the 3D (3df) and 2D (2df) features, among the classes of the NTU dataset; (b) The correspondence between class ids and class names.

Figure 6 :

 6 Figure 6: Precision-recall plots of the proposed Hybrid, DSR472, LF and SH-GEDT descriptors for: (a) The MPEG-7, PSB, CCCC and NTU datasets and (b) the ESB dataset.

Table 1 .

 1 Huffman codes of the first and last 3 symbols of the hybrid descriptor.

	Symbol i Computed Huffman code
	1	1
	2	00
	3	0110
	. . .	. . .
	1022	0100100000010111110
	1023	0101010101111000010
	1024	0111110011

Table 2 .

 2 Quantitative measures scores of the proposed Hybrid, DSR472, LF and SH-GEDT method for the MPEG-7, PSB, CCCC, NTU and ESB dataset.

	Dataset	Method	NN (%) FT (%) ST (%)
	MPEG-7 Hybrid	86.1	59.6	70.7
		DSR472	86.4	57.7	67.7
		LF	86.0	53.8	63.8
		SH-GEDT	83.7	50.3	59.4
	PSB	Hybrid	74.2	47.3	60.6
		DSR472	65.8	40.4	51.3
		LF	64.2	37.5	48.4
		SH-GEDT	55.3	31.0	41.4
	CCCC	Hybrid	87.4	60.2	75.8
		DSR472	82.8	55.6	70.0
		LF	79.8	50.2	63.1
		SH-GEDT	75.7	45.9	59.9
	NTU	Hybrid	76.2	46.6	59.1
		DSR472	71.9	42.7	55.4
		LF	70.0	39.0	50.1
		SH-GEDT	58.8	33.9	46.3
	ESB	Hybrid	82.9	46.5	60.5
		DSR472	82.3	41.7	55.0
		LF	82.0	40.4	53.9
		SH-GEDT	80.3	40.1	53.6


Theoharis Theoharis

Georgios Passalis
email: passalis@di.uoa.gr

Keywords: H, 3, 3 [Information Search and Retrieval]: -

. Our method is based on a hybrid scheme where 2D features as well as 3D features are extracted from a 3D model which has been previously normalized for rotation using two alternative alignment techniques. The alignment methods that are used are CPCA and NPCA. The 2D features are Fourier coefficients extracted from a set of depth buffers and the 3D features are spherical harmonic coefficients extracted from a spherical function-based representation of a 3D model.

INTRODUCTION

The 3D object retrieval methodology that we employ is based upon a hybrid shape descriptor. Based on the previous work of Passalis et al. [START_REF] Passalis | Ptk: A novel depth buffer-based shape descriptor for three-dimensional object retrieval[END_REF], we extract 2D features from a depth-buffer based representation of a model and 3D features (spherical harmonic coefficients) from a spherical function based representation as in the work of Papadakis et al. [START_REF] Papadakis | Efficient 3D shape matching and retrieval using a concrete radialized spherical projection representation[END_REF]. In the hybrid scheme, the two kinds of features are linearly combined to produce an integrated hybrid 3D shape descriptor. Invariance to similarity transformations is achieved using CPCA and NPCA [START_REF] Papadakis | Efficient 3D shape matching and retrieval using a concrete radialized spherical projection representation[END_REF], where the two methods are employed in parallel to alleviate the rotation invariance problem, for both 2D and 3D features. In the following, we briefly describe the stages for the extraction of the hybrid shape descriptor.

POSE NORMALIZATION

First, we normalize each 3D model for translation by computing its centroid using CPCA [START_REF] Vranic | 3D Model Retrieval[END_REF] and translating the model so that the centroid coincides with the origin.

We address the rotation invariance problem, by following the same approach as in [START_REF] Papadakis | Efficient 3D shape matching and retrieval using a concrete radialized spherical projection representation[END_REF] where two alignment methods are used, namely CPCA and NPCA. This is a meaningful choice, since by using CPCA and NPCA we consider both the surface area distribution and the surface orientation distribution that both characterize the rotation of a model's surface. As discussed in [START_REF] Papadakis | Efficient 3D shape matching and retrieval using a concrete radialized spherical projection representation[END_REF], there exist cases where one method performs better than the other. Scaling invariance is achieved by normalizing the features to their unit L 1 norm since the selected 2D and 3D features are proportional to the models scale. Therefore, by normalizing the scale of the features we are in fact normalizing the scale of the corresponding model.

FEATURE EXTRACTION

2D feature extraction

Based on the work of [START_REF] Passalis | Ptk: A novel depth buffer-based shape descriptor for three-dimensional object retrieval[END_REF], we use a depth buffer-based representation of a 3D model to compute a set of 2D features. In Figure 1, the main steps (a)-(d) for the extraction of the 2D features are shown.

From a pose normalized 3D model, we acquire a set of six depth buffers by projecting the model to the faces of a cube which is centered at the origin and whose size is proportional to the model's scale. For each set of parallel depth buffers, we compute the difference D di f between the front D f and back D b depth buffer to capture the model's thickness. To avoid information loss, the sum D sum of the front and back depth buffer is also computed. In the following, we compute the Discrete Fourier Transform of each D di f and D sum buffer and normalize the coefficients to their unit L 1 norm.

Finally, two weighting schemes are applied to the coefficients. First, the coefficients are weighed inversely proportionally to their degree since lower frequencies are considered to have more information compared to higher frequencies, which are more sensitive to noise and after the coefficients are weighed proportionally to the ranks of the principal directions that are encoded by the respective depth buffer.

The final 2D feature set is the concatenation of the coefficients of the six depth buffers. The 2D features set of model i that is aligned either by CPCA or NPCA, is denoted as 2D f j i where j ∈ {CPCA, NPCA}.

3D feature extraction

Based on the work of [START_REF] Papadakis | Efficient 3D shape matching and retrieval using a concrete radialized spherical projection representation[END_REF] we extract the 3D features using a spherical function-based representation of the 3D model and compute the spherical harmonics transform for each spherical function. In First, we represent the surface of a 3D model using a set of spherical functions, by projecting approximately equidistant parts of the 3D model to concentric spheres of increasing radius. This is done by computing the intersections of the surface of the model with rays emanating from the origin at the (θ , ϕ) directions, where θ corresponds to the longitude and ϕ to the latitude coordinate. In the following, we modify the spherical functions to include every point that is closer to the origin than the furthest intersection point on the corresponding ray. Thus, we obtain a volumetric representation of the 3D model and for each spherical function we compute the spherical harmonics transform [START_REF] Papadakis | Efficient 3D shape matching and retrieval using a concrete radialized spherical projection representation[END_REF], store the spherical harmonic coefficients and normalize them to their unit L 1 norm.

Finally, spherical harmonic coefficients are weighed inversely proportionally to their degree similarly to the 2D features set.

The final 3D feature set is the concatenation of the spherical harmonic coefficients of the N spherical functions. The 3D features set of model i that is aligned either by CPCA or NPCA, is denoted as 3D f j i where j ∈ {CPCA, NPCA}.

SIMILARITY MEASURE

The 2D and 3D features are computed for two alternative rotation normalized versions of a model. Thus, the final hybrid 3D shape descriptor s i of a model i is the concatenation of the 2D and 3D features for each aligned version of the 3D model, resulting in

s i = (2D f CPCA i , 2D f NPCA i , 3D f CPCA i , 3D f NPCA i ).
To compare the descriptors s 1 and s 2 of two models we compute Dist(s 1 , s 2 ) = dist 2D f + dist 3D f , where dist 2D f and dist 3D f is the distance between the 2D and 3D features, respectively, denoted as

dist 2D f = min j (L 1 (2D f j 1 , 2D f j 2 )) and dist 3D f = min j (L 1 (3D f j 1 , 3D f j 2 ))
, where j ∈ {CPCA, NPCA}, L 1 is the Manhattan distance and dist 2D f , dist 3D f are normalized to [0, 1].

SHREC 2008 EVALUATION RESULTS

Since our method does not employ any form of learning it is comparable with the following methods: YamanasA UL, YamanasB UL, Napoleon UL and CCECg UL. We submitted one runfile, i.e. one parameter setting of our method, to give a view of the performance of our method in a general rather in a particular context. Therefore, in order to ensure a fair comparison, our method should be compared against the others by computing the average performance from the set of runfiles of each participant.

Under the previous premises, our method exhibits the 2nd best overall performance among the participants for the 1st query set. Regarding the evaluation using the 2nd query set, we believe that it is inappropriate to draw conclusions regarding the overall performance of any method regardless of its ranking. The reason for this is that a large portion of the 2nd query set comprises models that belong to the smallest classes within the test dataset, in contrast to the 1st query set which is more representative of the content of the dataset. In particular, the sum of all relevant models for the 1st query set is 1876 whereas for the 2nd query set it is 892. This means that the evaluation using the 1st query set is statistically much more significant than the evaluation using the 2nd query set that cover less than half of the content of the test dataset (1814 models). Inevitably, this rises the question of what would be the performance of the participating methods in a 3rd query set that would cover that part of the dataset that is not covered by the 2nd set.

Our method shows inferior performance in the 2nd query set. However, this should not be considered as a disadvantage, since we want our method to exhibit top discrimination power overall for the plurality of models within a dataset, which is demonstrated from the evaluation of the 1st query set.

In Figure 3, we show a set of example queries and the respective top 10 retrieved models using the proposed hybrid method. Through the opportunity to participate in the track, we would also like to demonstrate a prototype 3D model search engine (CIL3D) which uses the proposed hybrid method and is publicily available through the internet, by following the next link: http://emedi3.emedi.iit.demokritos.gr/cil3d/ Currently, CIL3D enables content-based 3D model search within the Princeton Shape Benchmark dataset. Please note that CIL3D should not be used to verify the retrieval results of our participation in SHREC 2008, since the search engine employs a lossy compression scheme for the hybrid features and in some cases the retrieval results may not exactly match those that are evaluated in the track.

Last but not least, we would like to congratulate the winner of the track Kunio Osada (Univ. of Yamanashi) and thank Ryutarou Ohbuchi (Univ. of Yamanashi), organizer of the track, for giving the opportunity to evaluate the effectiveness of 3D shape retrieval algorithms within generic 3D model datasets.

ACKNOWLEDGEMENT

This research was supported by the Greek Secretariat of Research and Technology (PENED "3D Graphics search and retrieval" 03 E∆ 520).

Figure 1 :

 1 Figure 1: Consecutive stages for the extraction of the 2D features.

  Figure 2, the main steps (a)-(e) for the extraction of the 3D features are shown.

Figure 2 :

 2 Figure 2: Consecutive stages for the extraction of the 3D features.

Figure 3 :

 3 Figure 3: Example queries and the respective top 10 retrieved models using the proposed hybrid method.