بازیابی مدل 3D با استفاده از تجزیه و تحلیل هواپیمای اصلی و برنامه ریزی پویا

Three dimensional models play an important role in many applications; the problem is how to select the appropriate models from a 3D database rapidly and accurately. In recent years, a variety of shape representations, statistical methods, and geometric algorithms have been proposed for matching 3D shapes or models. In this paper, we propose a 3D shape representation scheme based on a combination of principal plane analysis and dynamic programming. The proposed 3D shape representation scheme consists of three steps. First, a 3D model is transformed into a 2D image by projecting the vertices of the model onto its principal plane. Second, the convex hall of the 2D shape of the model is further segmented into multiple disjoint triangles using dynamic programming. Finally, for each triangle, a projection score histogram and moments are extracted as the feature vectors for similarity searching. Experimental results showed the robustness of the proposed scheme, which resists translation, rotation, scaling, noise, and destructive attacks. The proposed 3D model retrieval method performs fairly well in retrieving models having similar characteristics from a database of 3D models.

In recent years, three-dimensional (3D) geometric models have been widely used in computer vision, mechanical engineering, and biology. The reasons to explain the wide applications of 3D models include (1) there are many improved modeling tools and scanning devices for making acquisition of 3D models easier and cheaper; (2) the virtual reality modeling language (VRML) makes World Wide Web can access 3D models constructing by people all over the world; (3) the personal computers including 3D graphics hardware and CPUs have become fast enough and cheap enough to processing 3D data and displayed quickly [1] and [2]. Generally, 3D models can be described in terms of color, texture, function, material and geometric shape, etc., so that development of the technology for effective content-based search and retrieval of 3D models has become an important issue. The methods for matching 3D model can be categorized into four major approaches including geometry-based approach, statistics-based approach, topology-based approach, and image-based approach. The 3D models can be described by some global geometric properties, such as inertial moment, curvature, volume, surface area, concentricity, etc. Accordingly, the similarity among arbitrary models can be measured by computing the distance among these feature vectors. For the geometry-based approach, Elad et al. [3] describe shape features using moments that can be used for similarity measure among 3D models. The disadvantage of using moments is sensitivity to the position state of models, such as translation, scaling and rotation. Zhang et al. [4] use a new set of region-based features for 3D models. Each model is treated like a solid volume with a uniform density. Features such as the volume-surface ratio, the moment invariants, and the Fourier transform coefficients are efficiently calculated directly from the mesh model. Motofumi [5] proposes a web-based retrieval system for 3D polygonal models, such that the 3D polygonal model is described by the combination of several features. These feature descriptors include tensors, normals, volumes, polygonal vertices, and polygonal faces. The disadvantage of method is that, when a large number of feature descriptors are used for the query, the system may not be able to respond quickly because many computations are needed. Vranic et al. [6] describe a method whereby the feature vector can be obtained by forming a complex function on the sphere and that is used to describe the shape of the 3D object. Kazhdan et al. [7] represent a 3D model's shape feature using a new reflective symmetry descriptor having the advantage that it can describe the global properties of a 3D shape. Osada et al. [1] represent the object's shape signature as a shape distribution sampled from a shape function measuring global geometric properties of arbitrary 3D polygonal models. The key idea for this approach is to reduce the matching problem to the comparison of probability distributions, which is simpler than traditional shape matching methods that require pose registration, feature correspondence, or model fitting. Furthermore, there exist some other methods that use high-level shape features such as generalized cylinders [8], super-quadrics [9], geons [10] and non-overlapping volumes [11] to represent 3D shape. The geometry-based approach requires a lot of computing resources to describe the property of the 3D shape, while the statistics-based methods have no such restriction. Its viewpoint is to consider the features of the 3D shape as a computable distribution. Mihael et al. [12] characterizes the method of intersection area with a collation of concentric spheres. The distribution of areas is normalized so that the overall volume is 1 and computing their L2 difference compares two distributions. In this way, the shape matching process can be carried out. Horn et al. [13] characterize a 3D model in terms of its distribution of surface normal vectors. They aligned the EGI (extended Gaussian images) for each model based on its principal axes, and then compared two aligned EGIs by computing their L2 difference. Osada et al. [2] propose a new method for computing shape features of any 3D polygonal model. The key idea is to use a shape function measuring the global geometric properties of an object to simplify its distribution of shape features. Their objective is to reduce the probability distribution problems in shape matching comparisons, which is simpler than other shape matching methods that require registration, feature correspondence, or model fitting. In comparison with other methods, the statistical method is not only fast and also easy to implement, also desired properties for practical applications, such as robustness and invariance. However, these methods cannot clearly depict the ability to distinguish local shape features between similar classes of objects. In addition to geometric and physical properties, topology structure is another important information for 3D shape description, and, among these approaches, only topology-based matching methods can handle highly deformable models in which, for example, the same objects are represented in different positions. Hilaga et al. [14] propose a topology matching method, in which automatically calculated by comparisons of multiresolutional Reeb graphs (MRGs) allow one to obtain quick and accurate similarity between polyhedral models. The MRG is a search key for 3D shape, and it is constructed by using a continuous function such as geodesic distance. Su et al. [15] also use geodesic distance to determine Reeb graph, and use the concept of matching significant nodes in Reeb graphs. Siddiqi et al. [16] propose a shape description based on shock graph. The scope of all such graphs can be characterized by the rules of shock graph grammar, which permit the reduction of a shock graph to a unique rooted shock tree. In this way, they use a tree-matching algorithm to find the best set of corresponding nodes between two shock trees. Sundar et al. [17] present a method that encodes geometric and topological information in the form of a skeletal graph and use graph-matching techniques to match the skeletons and compare them. Topology-based methods have many good properties. First, it is easy to build up the association between skeleton and 3D shapes from the visual appearance of the skeleton. Second, it is invariance and no affine transformation, such as translation, scaling, and rotation, which can lead to changes in skeleton structures. Finally, the generality of skeleton is good, not only to use in global features but also depicting local features to represent a 3D model in the form of a skeleton. It is suitable for users to specify the desired part that they would like to match. In this way, similarity matching can be done both globally and locally. However, they require a consistent model of the object's boundary and interior, and a large computation capability is needed to compute the skeleton. The image-based approach is based on the human visual system [18], [19] and [20], which has an uncanny ability to recognize objects from a single view. Christopher et al. [18] adopt a concept named “aspect graph” to group all views and represent a 3D object with a minimal set of 2D views. In this concept, the 3D problems can be transformed to 2D problems. The aspect graph represents the relationship between specified regions of the viewing sphere where “equivalent views” and their neighboring views on the viewing sphere generate a graphical structure of views. Each node of the aspect graph is presented in the “general view” or the 3D objects of maximally connected regions on the viewing sphere. However, it is necessary to establish view transitions, named visual events, otherwise a large number of views are needed. Thomas et al. [19] propose an algorithm that matches 2D sketches to 3D objects. The 2D sketches are drawn with a pixel paint program, while 3D objects are represented by a series of 2D projections. They compare sketches and rendered views with an image matching method. This operation makes it robust to small variations in the positions of lines. For cases where 3D models are arbitrarily oriented, they employ a 2D analog of the spherical harmonics method. A typical method for shape similarity search of 3D geometric models consists of three steps: (1) the computation of a set of shape features from a given model; (2) the computation of distance between pairs of shape features; and (3) retrieval of the model based on the distance values, e.g., k-nearest neighbors. In this paper, we propose a 3D shape representation scheme based on the combination of principal plane analysis and dynamic programming. The proposed 3D shape representation scheme consists of three steps. First, a 3D model is transformed into a 2D image by projecting the vertices of the model onto its principal plane. Second, the convex hall of the 2D shape of the model is further segmented into multiple disjoint triangles using dynamic programming. Finally, for each triangle, a projection score histogram and moments are extracted as the feature vectors for similarity searching. Experimental results showed the robustness of the proposed scheme which resists translation, rotation, scaling, noise and destruction attacks. The proposed 3D model retrieval method performs fairly well in retrieving models having similar models from a database of 3D models. The remainder of this paper is organized as follows. Section 2 presents the proposed principal plane analysis for 3D models. Section 3 presents the proposed retrieval strategy. Section 4 shows the experimental results. Finally, conclusions are drawn in Section 5.

In this paper, we propose a 3D model similarity search and retrieval system based on the combination of the projection score histograms using principal component analysis and the 3D moment features on the principal plane. A practical retrieval system that includes 907 models of the Princeton shape benchmark database is available on the web. The contributions of the proposed method include: (1) a closed-form solution to derive the principal plane of a 3D model; (2) the combination of the projection score histograms obtained from principal component analysis and the 3D moment features obtained from the principal plane analysis as the features for 3D model matching; (3) an optimal triangulation process using dynamic programming is implemented; (4) the way to represent a 3D model as an ATS. Experimental results show the robustness of the proposed scheme to resist model translation, rotation, scaling, noise and destructive attacks. Our approach significantly outperforms the D2D2, mD2mD2, AAD and 3D3Dshape descriptor methods. The computational complexity is still too high for real-time applications. Further work should be done to overcome this problem.