JP2015176484A - Method and system for three-dimensional model search - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a method and system for high-precision high-speed three-dimensional model search.SOLUTION: A search method searches for a three-dimensional model by comparing LBP (Local Binary Pattern) characteristic values of the three-dimensional model being searched (with those of a known three-dimensional model). The LBP characteristic values are obtained by generating depth buffer images of the known three-dimensional model at multiple viewpoints, generating multiple scale images with different image scales from each of the depth buffer images, and extracting an LBP histogram from each subdivided areas of each scaled images. Comparison of the LBP characteristic values involves assessing dissimilarity, in terms of sum of maximum values of the LBP histograms extracted from each scaled image, between the known three-dimensional model and the three-dimensional model being searched using all combinations of the multiple viewpoints as an index.

Description

The present invention relates to a method and a search system for searching a database of a three-dimensional object model.

  In the machine parts manufacturing industry represented by the automobile manufacturing industry, it is a common practice to manufacture a shape model of a three-dimensional object using a three-dimensional CAD / CAM system. Also, in the construction industry, it is widely used to create 3D building models, room models, furniture and tree models in order to simulate the exterior and interior of buildings and the surrounding landscape using CG before construction. Has been done. Furthermore, 3D CG technology is now indispensable for creating animation, movies, commercial films, and the like.

  However, in such an application field, when an elaborate three-dimensional model is first created, much more labor and time are required than two-dimensional drawing. Therefore, in these application fields, a 3D model that has been input and created once by an auxiliary means such as a human or a 3D scanner is stored in the 3D object model database, and a similar 3D object shape model is created. In this case, it is considered that a significant cost reduction can be achieved by reusing an object model having a similar shape.

  The technique described in Patent Document 1 is a method of dividing a polygon into a certain size and defining and searching for feature quantities from the areas of the divided polygons and normal vectors. Since this is an old method that does not perform the normal (normalization), the search depends on the position, orientation, and size, and there is a problem that the search cannot be performed even if the shapes are similar.

  The technique described in Patent Document 2 is a three-dimensional model similarity search method using a two-dimensional image as a search key, and calculates feature amounts based on projection images or cross-sectional images obtained from a plurality of two-dimensional images. Search based on. The feature amount in this patent is a histogram obtained by quantizing each color information value such as RGB, HSV, Lab, etc., which can be calculated for the texture actually attached to the object surface, a shape histogram obtained by quantizing the edge derivative, These include the volume, surface area, vertex distribution, and polygon distribution histogram of a three-dimensional object. For this reason, there is a problem that even if the shapes are similar, those having different colors cannot be searched. Also, as in Patent Document 1, there is a problem such as dependency on projection parameters (cross-section generation parameters) in that there is no facing (normalization) processing and spectrum in the frequency space is not used, and high search accuracy is high. It is thought that it does not come out.

  Non-Patent Document 1 proposes a plurality of methods, but the best search accuracy is Hybrid Descriptor. This is a two-dimensional Fourier transform of a depth buffer image in six directions to obtain a power spectrum, which is used as a feature value, and a two-dimensional Fourier transform of a silhouette image in three directions to obtain a power spectrum and characterize it. Amount. Then, a vector is emitted from the center until it touches the object surface in a radial manner, and this vector is used as a feature amount. It is a composite feature that combines spectral feature and geometric feature, and achieves high performance. From the system name DESIRE created by Mr. Vranic, it is often called a DESIRE feature (or a DSR472 feature from the published program name). However, the spectrum and geometric features are quite different, complicating index management, and the problem that the shape inside the object cannot be captured from depth buffer images and silhouette images remains. .

  In Non-Patent Document 2, a 256 × 256 silhouette image is generated from 100 or more different directions, 10 Fourier coefficients and 35 Zernike moment coefficients are obtained, and these are used as feature quantities. At the time of similarity calculation, parts of similar silhouette images are compared. This feature amount is referred to as a Light Field Descriptor (or LFD feature amount for short). Since rendering is performed from more than 100 directions, the creation time of the feature amount is extremely necessary. Since the shape is approximated only from the silhouette, there are problems such as being unable to find a fine shape and not being able to capture the features inside the object.

JP 2002-41530 A JP 2004-164503 A

D. Vranic, 3D Model Retrieval. Ph.D. thesis, University of Leipzig, 2004. D-Y. Chen, X-P. Tian, Y-T. Shen, M. Ouhyoung, On Visual Similarity Based 3D Model Retrieval.Computer Graphics Forum (2003), 223-232.

In the feature quantity of the three-dimensional model, as in Non-Patent Documents 1 and 2 in the above prior art, a technique for analyzing a two-dimensional image generated from a three-dimensional model from a plurality of viewpoints has obtained excellent search performance. In particular, the analysis of the depth buffer image in which the unevenness of the shape of the 3D model is expressed by the shading of the image is suitable for capturing the shape of the 3D model. However, in Non-Patent Document 1 that deals with depth buffer images, analysis is performed only from a depth buffer image of a single resolution, so that the outline is similar, but is different when the details are different. May be determined.

There are also problems with the solution to the arbitrary rotation of the 3D model. In Non-Patent Document 1, the principal axis is obtained by principal component analysis or singular value decomposition, and the rotation of the three-dimensional model is uniquely determined. This method has a problem that even if the shape is similar, the main axis changes due to noise such as a defect. Non-Patent Document 2 relaxes the arbitraryness of rotation by comparing feature quantities of two-dimensional images generated from a large number of viewpoints. When comparing feature amounts, the Euclidean distance of the feature amounts is calculated for the image pair, and the minimum value is set as the distance between the three-dimensional models. As a result, the comparison is made from a single viewpoint, and the arbitraryness of rotation can be solved, but the shapes of the three-dimensional models cannot be accurately compared.

The present invention has been made in order to solve the problems of the prior art described above.

  The three-dimensional model search method according to claim 1, for a known three-dimensional model, a local binary pattern (LBP) feature amount of a multi-scale image in a depth buffer image at a plurality of viewpoints is databased in advance, and the three-dimensional model to be searched A search method for searching a three-dimensional model by comparing LBP feature values of models, wherein the LBP feature value generates a depth buffer image at a plurality of viewpoints from a known three-dimensional model, and an image for each depth buffer image Multiple scale images having different scales are generated, and LBP histograms are extracted for a plurality of small regions divided for each scale image. The comparison of LBP feature values is the sum of the maximum values of the LBP histograms extracted for each scale image. Search target using all combinations of multiple viewpoints as indexes And characterized in that to determine the degree of difference between the three-dimensional model.

  The 3D model retrieval method according to claim 2, wherein the depth buffer image has a predetermined pixel size at a predetermined number of viewpoints after performing singular value decomposition on a known 3D model and performing posture normalization. It is generated.

  The three-dimensional model search method according to claim 3 is characterized in that the multi-scale image is generated by applying a Gaussian filter changed in a plurality of stages.

  The three-dimensional model search method according to claim 4, wherein the degree of difference is obtained by calculating a matrix of sums of maximum values of LBP histograms of each scale image at the number of viewpoints, and obtaining the matrix by the Hungarian method. It is characterized by the difference in the minimum sum of combinations.

  The three-dimensional model search system according to claim 5, with respect to a known three-dimensional model, an LBP feature quantity of a multiscale image in a depth buffer image at a plurality of viewpoints stored in advance in a database and an LBP of a three-dimensional model to be searched A search system for searching a three-dimensional model by comparing feature quantities, means for generating a depth buffer image at a plurality of viewpoints from a three-dimensional model to be searched, and multiple scales having different image scales for each depth buffer image Means for generating an image, means for extracting an LBP histogram for a plurality of small regions divided for each scale image, and the sum of the maximum values of the LBP histogram extracted for each scale image as an index for all combinations of a plurality of viewpoints. Between the 3D model and the 3D model to be searched Characterized in that it comprises a means for determining degrees.

By the above means, a high-precision and high-speed 3D model search method and 3D model search system can be realized.

It is explanatory drawing which showed the production | generation of the multiscale Local Binary Pattern histogram from the depth buffer image. It is a flowchart of the three-dimensional model search method and search system concerning this invention. It is explanatory drawing of attitude | position normalization (step 1). It is explanatory drawing of the production | generation (step 2) of a depth buffer image. It is explanatory drawing of the production | generation (step 3) of multiscale expression (image). It is explanatory drawing which determines the feature-value of a local binary pattern (step 4). It is explanatory drawing of a binary code structure (step 4). It is explanatory drawing of the multiscale local binary pattern which is the feature-value concerning this invention. It is a graph of the Recall-Precision curve of each feature-value in PSB. It is a graph of the Recall-Precision curve of each feature-value in ESB.

Embodiments of the present invention will be described with reference to the drawings. The embodiment of the present invention is configured on a computer and executed by causing hardware such as a CPU and a memory to function.

  In the technology of the present invention, a feature value of a three-dimensional model is obtained by analyzing a depth buffer image generated from a plurality of viewpoints from a three-dimensional model (hereinafter also referred to as a three-dimensional shape model or a three-dimensional object). When analyzing the depth buffer image, a multiscale representation is generated by applying Gaussian filters having different sizes, and a Local Binary Pattern (LBP) histogram is calculated with each scale representation. By using multiple scale representations with different levels of detail, it captures from rough shapes to detailed shapes. The LBP histogram of each scale expression is integrated by taking the maximum value for each element of the histogram. It is possible to capture the shape that appears most strongly in shape representations with different levels of detail.

  First, posture normalization of the three-dimensional model is performed by Point SVD. Point SVD normalizes the posture of a three-dimensional object using a randomly generated point on the surface of the three-dimensional object as a sample point. First, using the average of the sample points as the center of gravity of the three-dimensional model, translation is performed so that the center of gravity is the origin of the three-dimensional space. Second, the principal point of the three-dimensional model is obtained by performing singular value decomposition on the sample points, and the principal axis rotates along the x-axis, y-axis, and z-axis of the three-dimensional space. Finally, by dividing the coordinate axis of each vertex by the maximum distance between the vertex and the center of gravity of the 3D model, the 3D model is placed in the unit sphere.

Next, a depth buffer image is generated with a size of M × M (for example, 256 × 256) pixels from a plurality of viewpoints N _v (for example, 38 viewpoints with each vertex of the geosphere sphere as a viewpoint). As shown in FIG. 1, each depth buffer image is subjected to a gas filter whose size is changed in L steps (for example, 5 steps) to obtain a multi-scale expression. Furthermore, an LBP histogram of D bins (for example, 64 bins) is created in a small area obtained by dividing each scale into four. By creating an LBP histogram from the divided small areas, position information indicating what shape is located is captured. The LBP histogram of each scale expression is a concatenation of histograms created for each small area. Then, the LBP histogram of each scale expression is integrated by taking the maximum value for each element of the histogram. The size of the multiscale representation LBP histogram created for each depth buffer is 4 × D bins. Each multiscale representation LBP histogram is normalized by the sum of the elements.

  A flow (hereinafter also referred to as a flow) of a three-dimensional model search method and search system according to the present invention is shown in FIG. It consists of six steps, and each step is explained according to the processing procedure. A large number of three-dimensional shape models are stored in the database, and six steps are repeated for each shape model.

<Step 1>
Posture normalization is applied to each three-dimensional shape model in the database to eliminate the arbitraryness of “position”, “rotation”, and “size”. The posture-normalized three-dimensional shape model is arranged so that the center of gravity is at the center of a sphere having a radius of 1 (FIG. 3).

<Step 2>
A depth buffer image is generated from each of multiple viewpoints (for example, 38 viewpoints). The posture normalized sphere processed in step 1 is approximated by a triangular patch having 38 vertices, projected onto a plane perpendicular to the vector from each vertex toward the center of the sphere, and a depth buffer image (depth buffer image) Is generated (FIG. 4).

<Step 3>
A multiscale representation (image) is generated from each depth buffer image in step 2. At this time, a multiscale expression (image) is generated by applying Gaussian filters (for example, five types of scales) having different scales (ie, kernel sizes) (FIG. 5).

<Step 4>
Each multi-scale expression (image) is divided into four, a local binary pattern (histogram) is generated from each, and the local binary patterns are arranged and used as feature quantities of the target three-dimensional model (FIG. 6). Note that, as shown in FIG. 7, the local binary pattern creates a binary code from luminance differences with eight neighboring pixels surrounding the pixel of interest, and expresses the appearance rate as a histogram.

<Step 5>
A histogram of the quadrant image generated in the step 4 is generated from each of the multiscale images obtained in the step 3, and the maximum value of the histogram of the quadrant image is taken to obtain a multiscale local binary pattern ( Multi-scale Representation Local Binary Pattern (referred to as MRLBP) is generated (FIG. 8).

<Step 6>
The feature value obtained by applying the MRLBP feature value obtained in step 5 to all the depth buffers applied in step 2 is used as a shape feature value of the three-dimensional model and used as an index in the search. . In this embodiment, the viewpoint is 38, and the data of 4 * 64 dimensions (where 4 is a 4-division and 64 is the number of dimensions determined from the bit pattern) is obtained in step 5, so the total dimension of the shape feature amount Becomes 9728 dimensions.

  At the time of a three-dimensional model search, the steps 1 to 6 are applied to the three-dimensional model serving as a query (search question) to convert it into a feature amount, and the distance between the feature amount and the feature amount stored in the database is calculated. What is calculated using (Equation 1) and sorted in ascending order of distance is the order of similar shapes.

  The numerical parameter in the example of the present invention is merely an example of the embodiment, and the flow does not depend on the numerical parameter.

  In order to confirm the effectiveness of the 3D model retrieval system based on MRLBP features, a comparison experiment with a conventional method was performed.

First, the dissimilarity is calculated for all combinations of the boundary pixel histograms of a plurality of viewpoints _Nν , and a dissimilarity matrix having a size of _Nν × _Nν is calculated. Then, the difference of the minimum sum of combinations obtained by applying the Hungarian method to the difference matrix is set as the difference of the three-dimensional model. As a result, it is possible to realize the solution of the arbitrary rotation of the 3D model and the shape comparison of the 3D model from a plurality of viewpoints.

  The present invention is applied to a shape similarity search of a three-dimensional model. A comparison experiment was conducted with typical ones of the three-dimensional model.

  The conventional methods include Shape Distribution D2 (D2), Spherical Harmonics Descriptor (SHD), Light Field Descriptor (LF), Local Binary Pattern (LBP), DE RD Is used. D2 analyzes the feature quantity from points randomly generated on the surface of the three-dimensional object. SHD analyzes a feature quantity by converting a three-dimensional object into a voxel representation. These are feature quantities based on a three-dimensional representation. LFD is a representative feature amount method based on a two-dimensional image, and analyzes a feature amount from silhouette images generated from all directions. LBP calculates a histogram from a single depth buffer image. DESIRE is a composite of feature quantities analyzed from depth-buffer images, silhouette images, and vectors generated radially from the center of gravity of a three-dimensional object. MFSD is a composite of a three-dimensional object with four types of Fourier spectra.

  Princeton Shape Benchmark (PSB) and Engineering Shape Benchmark (ESB) were selected as the three-dimensional model data set. PSB consists of three-dimensional models in various fields such as dogs and airplanes, and can evaluate general search accuracy. The PSB is divided into training sets used for training and test sets used for evaluation. The ESB is composed of a three-dimensional object of mechanical parts such as gears and pipes, and can evaluate a search accuracy assuming a part search in product design by 3D CAD.

  As evaluation scales for search accuracy, First Tier (FT), Second Tier (ST), Nearest Neighbor (NN), Disclosed Cumulative Gain (DCG), recall (Recall), and precision (Precision) were used. FT and ST are the search accuracy at the top of the search results, and NN is the search accuracy at the top of the search results. DCG is a value representing the search accuracy of the entire search result. FT, ST, NN, and DCG have higher search accuracy as the value increases, and the recall-matching rate curve has higher search accuracy as the curve approaches the upper right.

  Each evaluation scale is represented by a micro average that uses an average of the evaluation scales of each query (search question) three-dimensional model as an overall average evaluation scale. In the macro average, which calculates the average of the evaluation scales for each class and uses these averages as the overall average evaluation scale, when each class is composed of a small number of three-dimensional models, the value of the evaluation scale is biased. I know. Since PSB and ESB used in the comparative experiment are composed of a small number of three-dimensional models, the micro average is used.

  Table 1 shows FT, ST, NN, and DCG of each feature amount in PSB. The inventive technique (MRLBP) has the best search performance in FT and NN. This indicates that the inventive technique can present more conforming three-dimensional models than the prior art in the higher search results. It can also be seen that the search accuracy is higher than that of LFD, which is a representative feature amount based on a two-dimensional image. In addition, since MRLBP has a higher search accuracy than LBP representing the feature amount of a single scale image, it can be seen that multi-scale representation is effective. In addition, even when compared with feature quantities based on voxel representations such as D2 and SHD and three-dimensional representations of point groups, MRLBP has the highest search accuracy in all evaluation scales.

  FIG. 9 is a Recall-Precision curve (reproduction rate-matching rate curve) of each feature amount in PSB. The inventive technique has a search performance comparable to that of the prior art MFSD. It can be seen that MRLBP (invention) is superior to other feature quantities in almost all recall-matching rate curve combinations. It can be seen that MRLBP has a high basic search accuracy regardless of a specific field.

  Table 2 shows FT, ST, NN, and DCG of each feature amount in ESB. It can be seen that MRLBP (invention technology) has the highest search accuracy on the evaluation scale excluding NN. As with the PSB, since high search accuracy is obtained, it can be seen that the multi-scale representation is also effective for the three-dimensional model of the machine part.

FIG. 10 is a Recall-Precision curve (reproduction rate-matching rate curve) of each feature amount in ESB. It can be seen that MRLBP (the present invention) outperforms other feature quantities in almost all recall-matching ratio combinations. It can be seen that MRLBP can obtain high search accuracy even in a shape similarity search for a three-dimensional model of a machine part.

Claims (5)

For a known three-dimensional model, a local binary pattern (LBP) feature quantity of a multi-scale image in a depth buffer image at a plurality of viewpoints is stored in a database in advance, and the three-dimensional model is compared by comparing the LBP feature quantity of the three-dimensional model to be searched. A search method for searching,
The LBP feature value is obtained by generating a depth buffer image at a plurality of viewpoints from a known three-dimensional model, generating a multi-scale image having different image scales for each depth buffer image, and generating an LBP histogram for a small region divided into a plurality for each scale image. Extracted from
The comparison of the LBP feature values is to determine the degree of difference from the three-dimensional model to be searched using the sum of the maximum values of the LBP histogram extracted for each scale image as an index for all combinations of a plurality of viewpoints. 3D model search method characterized by   2. The three-dimensional image according to claim 1, wherein the depth buffer image is generated with a predetermined pixel size at a predetermined number of viewpoints after performing singular value decomposition and posture normalization of a known three-dimensional model. How to search for models.   The three-dimensional model search method according to claim 1, wherein the multiscale image is generated by applying a Gaussian filter changed in a plurality of stages.   The dissimilarity is a dissimilarity of a minimum sum of combinations obtained by calculating a matrix of sums of maximum values of LBP histograms of each scale image at the number of viewpoints and using the Hungarian method for the matrix. The search method of the three-dimensional model in any one of. For a known three-dimensional model, a three-dimensional model is searched by comparing the LBP feature value of the multiscale image in the depth buffer image at a plurality of viewpoints stored in advance in the database with the LBP feature value of the three-dimensional model to be searched. A search system,
Means for generating a depth buffer image in a plurality of viewpoints from a three-dimensional model to be searched;
Means for generating multiple scale images of different image scales for each depth buffer image;
Means for extracting an LBP histogram for a small region divided into a plurality of scale images;
Means for determining the degree of difference between a known three-dimensional model and a three-dimensional model to be searched, using the sum of the maximum values of the LBP histogram extracted for each scale image as an index for all combinations of a plurality of viewpoints. 3D model search system characterized by

Images