JP6942330B2 - Image features and 3D shape search system using them - Google Patents

Description

The present invention relates to a system for obtaining a feature amount from an image and using the feature amount to search for a three-dimensional object model having a similar shape. In particular, it relates to a method of obtaining a feature amount for searching a three-dimensional object model from a handwritten image such as a sketch.

In CAD / CAM (Computer-Aided Design / Computer-Aided Manufacturing), intuitive search by handwritten images such as sketches of machine parts models is required, and some conventional techniques have been proposed. Conventional techniques for searching a 3D object model from a handwritten image include 1) a method using a depth buffer of a 3D object model by Takuma et al. (See, for example, Patent Document 1), and 2) a method by Sang et al. (See, for example, Non-Patent Document 1), and 3) the OPHOG method of Takuma et al. (See, for example, Non-Patent Document 2).

In the 3D model search system using the 2D sketch image as the search question shown in 1), the depth buffer image of the 3D object model is processed and the 3D object model is projected in 2D. The feature quantity related to the histogram is calculated by comparison with, and the ranking of the search results is obtained.

2) In the method of Sang et al., HOG-DTF (Histogram of Oriented Gradients --Diffusion Tensor Fields) features are extracted from handwritten images such as sketches and contour line images generated from 3D object models, and the features are used as the features. It is reconstructed by sparse coding using a base composed of another feature extracted from the contour image. The weight obtained by the reconstruction is used as the similarity to search the three-dimensional object model. Sang et al. Use sparse coding to reconstruct the features of a handwritten image, that is, to approximate by a weighted linear sum. Therefore, when the number of dimensions of the search target and features increases, the weights of the sparse coding increase. There is a problem that the calculation becomes a load and the execution speed is reduced.

Finally, 3) In the OPHOG method, first, an edge image is generated from a plurality of viewpoints for a three-dimensional object model. After that, the handwritten image and the edge image are divided into small areas called overlapping cells. Next, the Histogram of Oriented Gradients (HOG) features are extracted for each created small area. Finally, a three-dimensional object model is searched using the Euclidean distance as the similarity between the handwritten image and the edge image.

JP-A-2015-201151

Yoon, Sang Min, Gang-Joon Yoon, and Tobias Schreck. “User-drawn sketch-based 3D object retrievalusing sparse coding.” Multimedia Tools and Applications, 74.13 (2015): 4707-4722. Li, Bo, et al. "A comparison of 3D shape retrieval methods based on a large-scale benchmark supporting multimodal queries." Computer Vision and Image Understanding 131 (2015): 1-27.

In the conventional 3D object model search method and 3D shape search system from handwritten images such as sketches, the search is performed based on the similarity with the image obtained by projecting the 3D object model in 2D, so the 3D object is searched. The 3D structure of the model is not considered and the overall shape of the 3D object model will be ignored. Therefore, even if the 3D object model has a shape similar to the 3D object model to be searched, which is desired by the searcher, the features of the image can be sufficiently captured by the conventional feature extraction from the handwritten image. Therefore, there is a problem that the search accuracy becomes low, so that the search result does not appear at the top of the search result list and the search result cannot be easily obtained.

The problem to be solved by the present invention has been made in view of the above-mentioned problems of the prior art, and defines a new feature amount of a handwritten image such as a sketch (hereinafter, may be simply referred to as a sketch image). However, by obtaining the feature amount, it is possible to provide a three-dimensional shape search system in which a handwritten image is used as a search question (hereinafter, may be referred to as a search query) with higher accuracy than in the prior art.

The image feature amount according to the present invention is an image feature amount in a handwritten image used as a search question in a three-dimensional shape database as a search target.
The image feature amount is constructed by multiplying the feature amount of the edge image generated for each three-dimensional object model stored in the three-dimensional shape database by a weight and approximating it as a linear sum of the feature amount multiplied by the weight. It is characterized by being done.

The three-dimensional shape search system according to the present invention is a three-dimensional shape search system that searches a three-dimensional shape database and uses a handwritten image as a search question.
The means for extracting the image feature amount according to claim 1 and
A means to calculate the weight of a 3D object model with a connection on a k-nearest neighbor graph that reflects the similarity between 3D object models,
A means of performing L2 normalization on the weights to avoid overfitting,
A means for calculating the weight at which the similarity is minimized by using the weight as the similarity is provided.
It is characterized in that a search is performed by sorting according to the value of the degree of similarity.

The image feature amount of the handwritten image according to the present invention and the three-dimensional shape search system using the same are used to search the three-dimensional object model from the handwritten image with high accuracy in consideration of the shape of the three-dimensional object model to be searched. It is possible to present a desired three-dimensional object model at the top of the search result list.

It is a conceptual diagram explaining the reconstruction of the image feature quantity by the approximation of the linear sum which concerns on this invention. It is a schematic diagram which shows the outline of the processing flow about the 3D shape search which concerns on this invention. It is a graph which shows the image feature amount which concerns on this invention, and the search result (Precision-Recall curve) by the three-dimensional shape search system using it.

The image feature amount and three-dimensional shape search system according to the present invention appropriately controls the hardware of the computer to which the arithmetic unit, the memory, the external storage device, the display device and the input device are electrically connected, and C. It is built and executed using a programming language such as a language.

In the present invention, the image features extracted from a handwritten image such as a sketch, which is a search question, are approximated and reconstructed by a weighted linear sum of the features of the edge image generated from the three-dimensional object model to be searched. By setting the weight as the similarity, a search based on the reconstruction error of the feature amount is performed.

As one of the methods for searching a 3D object model from a handwritten image such as a sketch, an edge image is generated from a plurality of viewpoints from the 3D object model, and the same feature extraction process is performed on the edge image and the handwritten image. There is a method of obtaining search results by calculating the distance between the extracted features and sorting them in ascending order.

In the search by the above method, a three-dimensional object model similar to a handwritten image can be obtained, but since the search is performed based on the image obtained by projecting the three-dimensional object model in two dimensions, the three-dimensional structure of the three-dimensional object model is taken into consideration. Instead, the overall shape of the model will be ignored.

Further, as a method of searching a three-dimensional object model from a handwritten image such as the sketch, the feature amount of the handwritten image is re-reproduced with the feature amount of the edge image generated from the three-dimensional object model by using the concept of sparse coding. There is a method of improving the search accuracy by considering the configuration and setting the weight required at that time as the similarity.

In the present invention, unlike the above method, the linear sum of the features extracted from the handwritten image such as a sketch is multiplied by the features of the edge image generated from the three-dimensional object model (hereinafter, weights). By approximating with (sometimes called an attached linear sum) and using the weight at that time as the similarity, the search accuracy is improved (Fig. 1). At that time, a neighborhood graph is created from the similarity between the three-dimensional object models, a regularization term is added so that the neighborhoods have similar weights, and the similarity between the three-dimensional object models is reflected.

FIG. 2 shows an outline of a processing flow related to a three-dimensional shape search according to the present invention. In the present invention, the feature amount extracted from the handwritten image is approximated by the weighted linear sum with the feature amount extracted from the edge image generated from the three-dimensional object model, and the reconstruction error is calculated and searched.

The calculation of the weighted linear sum is realized by minimizing the square error (hereinafter, may be referred to as a reconstruction error) between the feature amount of the handwritten image and the edge image to which the weight is added. At this time, an L2 regularization term is added to prevent overfitting of the weight.

Further, the shape feature amount of the three-dimensional object model is extracted separately from the feature amount of the generated edge image, and a regularization term considering the adjacency matrix of the neighborhood graph created from the similarity of the shape feature amount is added. ..

Then, the search is performed using the weight obtained when the reconstruction error with the regularization term is minimized as the similarity.

In the present invention, first, the image feature amount is extracted from the edge image and the handwritten image given as a search question by the OPHOG method, and the feature amount q and n three-dimensional object models {M _i } are extracted from the handwritten image. ^The _{features {m ij} } ^{n, p} _{i = 1, j = 1} are obtained from the images generated p by p from _{n i = 1.}

Then, by calculating the Euclidean distance between the feature amount q and the feature amount {m _ij } ^{n, p} _{i = 1, j = 1} , the latest feature amount q of the handwritten image is calculated for each three-dimensional object model. Find out the neighboring image features and create a matrix X in which they are arranged.

Next, from each 3D object model, apart from the image features, the MRLBP method (for example, Sanada et al., "Searching for shape similarity of 3D objects by Local Binary Pattern of multiple scale representation" (Refer to Shu, vol.2014, No.86, 2014) to extract the _{shape features Y = {y 1} , ···, y _n}.

Then, the Euclidean distance between each element of the shape feature amount Y is calculated, and a k-nearest neighbor graph is created from the distance relationship. From there, an adjacency matrix A that represents the similarity between the three-dimensional object models is created. The element of A is represented as 1 if the 3D object models are adjacent to each other, and 0 otherwise.

After that, the reconstruction error with the regularization term shown in Equation 3 is minimized. Then, the weight W = {w ₁ , ···, w _n } ^T obtained at that time is defined as the similarity of each three-dimensional object with respect to the handwritten image. At that time, the objective function J is represented by the equation 3.

In Equation 3, the first term indicates that the features obtained from the handwritten image are reconstructed by the weighted linear sum of the features obtained from the three-dimensional object model. The weight value becomes larger as the three-dimensional object model has a feature amount similar to the feature amount of the handwritten image.

The second term shows that the weight reflects the similarity between the three-dimensional object models. The weights of the 3D object models connected on the k-nearest neighbor graph have similar values.

The third term is the L2 regularization term commonly used to avoid overfitting.

In order to obtain the optimum weight W that minimizes Equation 3, the partial differential with W is set to 0, and the equation is summarized as Equation 4.

ここで、L=D-Aであり、Dは対角行列であり、その要素は、

Where L = DA, D is a diagonal matrix, and its elements are:

である。

Is.

Equation 4 gives the similarity W corresponding to each three-dimensional object model. Finally, search results are created by arranging the 3D object models in descending order of W.

In the embodiment according to the present invention, the OPHOG method is used for extracting the feature amount of the handwritten image and the MRLBP method is used for extracting the feature amount of the three-dimensional object model, but the feature amount of the handwritten image according to the present invention is a search target. If the feature amount of the three-dimensional object model can be extracted in the same manner as the feature amount of the handwritten image, the feature amount is not limited to the extraction method of the feature amount.

Engineering Shape Benchmark (ESB), which is a data set consisting of 3D object models of mechanical parts, was used as the data of the 3D object model to be searched. The ESB consists of 42 classes and 867 3D object models. In addition, the handwritten images used as search questions were created by handwriting a total of 420 handwritten images, 10 for each class, according to the ESB's 3D object data.

Precision-Recall curve, Nearest Neighbor (NN), First Tier (FT), Second Tier (ST), E-measure (E), Discounted Cumulative Gain (DCG), Average Precision (AP) was used. For the conventional method, we used the OPHOG method, which evaluates the similarity based on the Euclidean distance of Tachima et al., And the method of using the weight by the weighted linear sum with only L2 regularization as the similarity. The parameters of the present invention were k = 10, α = 0.4, β = 7.5. The parameter for weight calculation only for L2 regularization was β = 9.

Table 1 summarizes the values of NN, FT, ST, E, DCG, and AP for each method. It can be seen that the present invention has the best search performance on all evaluation scales.

On the other hand, FIG. 3 shows the Precision-Recall curve of each method. It can be seen that in all Precision-Recall combinations, the present invention surpasses the conventional method and has the best search performance.

Claims (1)

A 3D shape search system that searches a 3D shape database and uses handwritten images as search questions.
A means for extracting image features of handwritten images used as search questions,
When the image feature amount of the edge image generated for each three-dimensional object model stored in the three-dimensional shape database is multiplied by a weight, the image feature amount of the handwritten image is multiplied by the weighted image of the edge image. A means of reconstructing by approximating the linear sum of the features,
A means for extracting shape features for each 3D object model stored in the 3D shape database, and
A means for creating a k-nearest neighbor graph from the shape features of the three-dimensional object models and reflecting the relationship between the three-dimensional object models connected on the graph in the weights.
A means of performing L2 normalization on the weights to avoid overfitting,
The weight after the normalization as the similarity between the handwritten image and the three-dimensional object model, and means for calculating the weight to which the similarity is minimized,
A three-dimensional shape search system characterized in that a search is performed by sorting according to the value of the degree of similarity.

Images