JP2011180793A - System, method and program for searching three-dimensional object, and computer-readable recording medium with the program recorded - Google Patents

Abstract

A three-dimensional object search system and a three-dimensional object capable of efficiently searching for a large number of three-dimensional objects published on the WEB by a commonly used keyword search and accurately obtaining a desired three-dimensional object. Provide search methods.
A three-dimensional object search system includes a keyword acquisition unit that acquires a keyword for searching for a three-dimensional object, and a three-dimensional object that is searched by searching for a three-dimensional object related to the keyword acquired by the keyword acquisition unit. 3D object retrieval means for acquiring an object, shape feature amount extraction means for extracting a shape feature amount of the 3D object acquired by the 3D object search means, and each shape feature acquired by the shape feature amount extraction means Similarity calculating means for calculating the degree of similarity; ranking generating means for ranking each of the three-dimensional objects acquired by the three-dimensional object search means based on the similarity calculated by the similarity calculating means; It is comprised.
[Selection] Figure 1

Description

  The present invention relates to a three-dimensional object search system, a three-dimensional object search method, a three-dimensional object search program, and a computer reading recording the program, which can efficiently search a large number of three-dimensional objects disclosed on the WEB. The present invention relates to a possible recording medium.

  In recent years, the use of three-dimensional objects has been increasing and is used in various situations such as CG movies and games. In addition, a method for obtaining a three-dimensional shape of a real object has made great progress, and various scanning methods have been developed. From such a background, it is considered that a mechanism for searching many 3D objects published on the WEB will be required in the future. For example, Patent Literature 1 discloses a search for providing a user with an image of a product as 3D data. A system is disclosed.

JP-A-2005-78621

  However, in the conventional three-dimensional object search method, many recognition and identification methods using three-dimensional data as input have been proposed, but acquisition of the three-dimensional object by keyword search has not been discussed so far. Is the actual situation. In addition, in the case of a search method based on matching between 3D objects, there is a problem that the user needs to have 3D data and that only the same shape as the 3D object that the user has can be searched. .

  The present invention has been made to solve such a conventional problem, and efficiently searches a large number of three-dimensional objects published on the WEB by a commonly used keyword search to obtain a desired It is an object of the present invention to provide a three-dimensional object search system and a three-dimensional object search method that can accurately acquire a three-dimensional object.

  The present invention provides a keyword acquisition means for acquiring a keyword for searching for a three-dimensional object, a three-dimensional object for searching for a three-dimensional object related to the keyword acquired by the keyword acquisition means, and acquiring the searched three-dimensional object. Based on the search means, the shape feature quantity extraction means for extracting the shape feature quantity of the three-dimensional object acquired by the three-dimensional object search means, and the plurality of shape feature quantities acquired by the shape feature quantity extraction means, Similarity calculation means for calculating the similarity of the shape feature quantity, and ranking generation means for ranking each of the three-dimensional objects acquired by the three-dimensional object search means based on the similarity calculated by the similarity calculation means Is a three-dimensional object search system, characterized in that .

  The present invention also provides a keyword acquisition step for acquiring a keyword for searching for a three-dimensional object, a three-dimensional object related to the keyword acquired in the keyword acquisition step, and acquiring the searched three-dimensional object. Based on the three-dimensional object search step, the shape feature amount extraction step for extracting the shape feature amount of the three-dimensional object acquired in the three-dimensional object search step, and the plurality of shape feature amounts acquired in the shape feature amount extraction step, A similarity calculation step for calculating the similarity of each shape feature amount, and a ranking for ranking each of the three-dimensional objects acquired by the three-dimensional object search means based on the similarity calculated in the similarity calculation step And a generation step. To a three-dimensional object search method.

  According to the three-dimensional object search system and the three-dimensional object search method according to the present invention, a number of three-dimensional objects published on the WEB are efficiently searched by a commonly used keyword search, and a desired three-dimensional object is obtained. It can be acquired accurately. This is realized by the three-dimensional shape feature quantity independent of the viewpoint and scale of the three-dimensional shape according to the present invention.

It is a block diagram which shows the internal structure and application example of the three-dimensional object search system which concern on this embodiment. It is a schematic flow which shows the flow of each process which a three-dimensional object search system performs. It is the figure which showed a mode that the three-dimensional object is observed from several viewpoints. It is the figure which showed an example of the gypsum image searched by the three-dimensional object search system which concerns on this embodiment. It is the figure which showed an example of the toy of the duck searched by the three-dimensional object search system which concerns on this embodiment.

  Hereinafter, the three-dimensional object search system according to the present embodiment will be described in detail with reference to the drawings.

  <Overall configuration>

  First, the overall configuration of the three-dimensional object search system 10 according to the present embodiment will be described with reference to FIG. FIG. 2 is a block diagram showing an internal configuration and an application example of the three-dimensional object search system 10 according to the present embodiment.

  The three-dimensional object search system 10 includes a keyword acquisition unit 12, a three-dimensional object search unit 14, a shape feature amount extraction unit 16, a similarity calculation unit 18, a ranking generation unit 20, a search result output unit 22, It is comprised. The three-dimensional object search system 10 is communicably connected to an unspecified number of terminals represented by the user terminal 30 and the WEB server 40 via the Internet. As such a three-dimensional object search system 10, for example, a server machine or a PC can be applied.

  Next, processing performed by the respective means 12, 14, 16, 18, 20, and 22 of the three-dimensional object search system 10 will be described in detail with reference to FIG. The figure is a schematic flow showing the flow of each process performed by the three-dimensional object search system 10.

  <Keyword acquisition means>

  First, the keyword acquisition unit 12 will be described. The keyword acquisition unit 12 is a unit that acquires a keyword (search key) for searching for a three-dimensional object.

  The keyword acquisition unit 12 is configured by, for example, software (program) for acquiring (receiving) a keyword transmitted to the three-dimensional object search system 10 via a WEB browser installed in the user terminal 30. A keyword (for example, character information such as “cop”) serving as a search key for a dimension object is acquired.

  <Three-dimensional object search means>

  Next, the three-dimensional object search means 14 will be described. The three-dimensional object search unit 14 is a unit that searches for a three-dimensional object related to the keyword acquired by the keyword acquisition unit 12 and acquires image information of the searched three-dimensional object.

  For example, the three-dimensional object search unit 14 accesses a terminal such as the WEB server 40 connected via the Internet using the keyword acquired by the keyword acquisition unit 12 as a search key, and provides the WEB provided by the WEB server 40. Software (program for acquiring image information of a three-dimensional object (for example, image information of a three-dimensional object of a cup) associated with character information (for example, character information of “cop”) included in the HTML of the site ) Etc.

  For example, if the HTML of the WEB site contains a description such as “This is <IMG SRC =“ Image information of a three-dimensional object of a cup ”> a cup”, the three-dimensional object search means 14 uses the word “cop”. Based on the SRC of the <IMG> tag described in front of the information, the image information of the three-dimensional object of the cup is acquired.

  <Shape feature extraction means>

  Next, the shape feature quantity extraction unit 16 will be described. The shape feature amount extraction unit 16 generates a two-dimensional image obtained by observing the three-dimensional object from a plurality of viewpoints based on the image information of the three-dimensional object acquired by the three-dimensional object search unit 14 described above, and generates each two-dimensional This is means for extracting the shape feature amount of the image, and is configured by software (program), for example.

  In the present embodiment, the shape feature amount extraction unit 16 performs two-dimensional fitting on the image information of the three-dimensional object acquired from the WEB server 40, and calculates the maximum curvature and the minimum curvature of each three-dimensional object.

  Subsequently, the shape feature amount extraction unit 16 calculates a shape index value using the calculated maximum curvature and minimum curvature, normalizes these, and then shapes a shape index image which is a gray scale image arranged two-dimensionally. (Image representing unevenness information of a three-dimensional object) is created. Here, in order to eliminate the viewpoint dependency that occurs when converting image information from three dimensions to two dimensions, as shown in FIG. Shape index images obtained by observing the target three-dimensional object from a plurality of viewpoints (for example, viewpoints corresponding to all (or part of) vertices of the regular icosahedron) are respectively created. When the target three-dimensional object is a single viewpoint (distance image), a single viewpoint Shape index image is applied.

  Subsequently, the shape feature quantity extraction unit 16 applies SIFT (Scale Invariant Feature Transpose) to each of the plurality of created shape index images, and the number of SIFT corresponding points between each shape index image and each shape index image. The shape feature amount is extracted by calculating the number of SIFT feature points.

  <Similarity calculation means>

  Next, the similarity calculation means 18 will be described. The similarity calculation unit 18 is configured to obtain each shape feature amount of the two-dimensional image acquired by the shape feature amount extraction unit 16 (in this embodiment, the number of SIFT corresponding points between each shape index image and the shape index image). Is a means for calculating the similarity of each Shape index image based on the number of SIFT feature points), and is configured by software (program), for example.

  In the present embodiment, the similarity calculation unit 18 specifies and specifies the shape index image having the largest number of SIFT correspondence points among the SIFT correspondence points between the shape index images calculated by the shape feature amount extraction unit 16. The similarity is calculated by generating an adjacency matrix using the number of SIFT corresponding points of the shape index image and the number of SIFT feature points. For example, when the number of SIFT corresponding points between each shape index image is Mij, and the number of SIFT feature points of each shape index image is Ti and Tj, the similarity Cij can be calculated as Mij / ((Ti + Tj) / 2). .

  <Ranking generation means>

  Next, the ranking generation unit 20 will be described. The ranking generation means 20 is a means for ranking (determining the ranking) each of the three-dimensional objects acquired by the three-dimensional object search means 14 based on the similarity calculated by the similarity calculation means 18 described above. For example, it is configured by software (program).

  As an algorithm for determining such ranking, for example, Visual Rank, which is a well-known technique, can be applied. By using the above-mentioned similarity instead of the hyperlink in Visual Rank, the order of higher similarity is increased. The three-dimensional objects can be rearranged in the order of high relevance with other three-dimensional objects. As a result, the ones having high importance (three-dimensional objects having a representative shape) among the three-dimensional objects are ranked higher. As for Visual Rank, Y. Jing, and S. Baluja, "Visual Rank: Applying Page Rank to large-scale image search" IEEE Transaction on Pattern Analysis and Machine Intelligence, vol.30, no.11, pp.1877 See -1890, Nov. 2008, etc.

  <Search result output means>

  Next, the search result output unit 22 will be described. The search result output unit 22 is a unit that outputs the image information of the three-dimensional object acquired by the three-dimensional object search unit 14 based on the rank given by the ranking generation unit 20 described above. The search result output unit 22 is configured by, for example, software (program) that outputs the image information of the three-dimensional objects rearranged in descending order by the ranking generation unit 20 to the browser of the user terminal 30.

  <Experimental result>

  Next, a description will be given of experimental results of a search performed using the three-dimensional object search system 10 according to the present embodiment.

  FIG. 4 is a diagram illustrating an example of a gypsum image searched by the three-dimensional object search system 10 according to the present embodiment. In this example, among a plurality of types of three-dimensional objects searched using “gypsum image” as a keyword, No. The three-dimensional object indicated by 15 is ranked first, and this three-dimensional object has the most representative shape in the gypsum image (the highest similarity in shape among the three-dimensional objects). ). From the second place onwards, No. No. 9, a three-dimensional object, No. 9 No. 6 three-dimensional object, No. 6 No. 4 three-dimensional object, No. 4 They are ranked in the order of three-dimensional objects indicated by 2. In addition, Shape Rank in a figure has shown expanding the above-mentioned Visual Rank to the three-dimensional object.

  FIG. 5 is a diagram showing an example of a duck toy searched by the three-dimensional object search system 10 according to the present embodiment. In this example, among a plurality of types of three-dimensional objects searched using “duck toy” as a keyword, No. The three-dimensional object indicated by 20 is ranked first, and this three-dimensional object has the most representative shape among duck toys (the most similar similarity between the three-dimensional objects). High). From the second place onwards, No. 17, a three-dimensional object indicated by No. 17 No. 10 three-dimensional object, No. 10 No. 9, a three-dimensional object, No. 9 They are ranked in the order of three-dimensional objects indicated by 16.

  As described above, the three-dimensional object search system 10 according to this embodiment includes the keyword acquisition unit 12 that acquires a keyword for searching for a three-dimensional object, and the 3 related to the keyword acquired by the keyword acquisition unit 12. A three-dimensional object search means 14 for searching for a three-dimensional object and acquiring the searched three-dimensional object; a shape feature quantity extraction means 16 for extracting a shape feature quantity of the three-dimensional object acquired by the three-dimensional object search means 14; Based on the plurality of shape feature amounts acquired by the shape feature amount extraction unit 16, the similarity calculation unit 18 that calculates the similarity of each shape feature amount, and the similarity calculated by the similarity calculation unit 18 The three-dimensional objects retrieved by the three-dimensional object search means 14 are ranked. That the ranking generation unit 20, characterized in that it is configured to have a, a three-dimensional object search system.

  According to the three-dimensional object search system 10 according to the present embodiment, a large number of three-dimensional objects published on the WEB are efficiently searched by a commonly used keyword search, and a desired three-dimensional object is accurately acquired. be able to.

  The shape feature amount extraction unit generates a two-dimensional image from the three-dimensional object acquired by the three-dimensional object search unit, and uses the feature amount extracted from the generated two-dimensional image as the shape feature amount of the three-dimensional object. Also good.

  With such a configuration, the shape feature amount of the three-dimensional object can be quickly extracted, and the search speed of the three-dimensional object can be increased.

  The shape feature amount extraction unit generates a two-dimensional image obtained by observing the three-dimensional object acquired by the three-dimensional object search unit from a plurality of viewpoints, and extracts the feature amount extracted from the generated two-dimensional image. It may be a shape feature amount of the object.

  With such a configuration, the shape feature amount of the three-dimensional object can be quickly extracted, and the search speed of the three-dimensional object can be increased.

  In addition, the shape feature amount extraction unit is a two-dimensional image having pixel values calculated from the curvature of the three-dimensional object acquired by the three-dimensional object search unit, and the three-dimensional object is observed from a plurality of viewpoints. A generated two-dimensional image (for example, a shape index image) may be generated, and a feature amount extracted from the generated two-dimensional image may be used as the shape feature amount of the three-dimensional object.

  With such a configuration, the shape feature amount of the three-dimensional object can be quickly extracted, and the search speed of the three-dimensional object can be increased.

  Further, the shape feature quantity extraction unit may extract the feature quantity by applying SIFT to the two-dimensional image.

  With such a configuration, the shape feature amount of the three-dimensional object can be quickly extracted, and the search speed of the three-dimensional object can be increased.

  The shape feature quantity extraction unit generates a second three-dimensional object having a different level of detail from the three-dimensional object acquired by the three-dimensional object search unit, and performs two-dimensional processing on each of the generated second three-dimensional objects. A common shape feature amount may be extracted from a three-dimensional object having a different level of detail by generating an image and extracting the feature amount from each of the generated two-dimensional images.

  With such a configuration, the shape feature amount of the three-dimensional object can be quickly extracted, the search speed of the three-dimensional object can be increased, and the change in the scale of the three-dimensional object can be further detailed. Can respond.

  In addition, the similarity calculation unit acquires the number of corresponding points between the two-dimensional images using the feature amounts of the respective two-dimensional images calculated by the shape feature amount extraction unit, and uses the acquired corresponding points to determine the similarity. A degree matrix (for example, an adjacency matrix) may be generated, and the importance between the shapes may be calculated from the generated similarity matrix.

  With such a configuration, the importance of the three-dimensional object can be quickly calculated, and the search speed of the three-dimensional object can be increased.

  The ranking generation means may rank each of the three-dimensional objects acquired by the three-dimensional object search means in a higher order as the importance calculated by the similarity calculation means is higher.

  With such a configuration, it is possible to specify a three-dimensional object having the most representative shape among a plurality of types of three-dimensional objects hit by the keyword search, and to provide a search result useful to the user. it can.

  A means for generating a two-dimensional image using a value calculated from the curvature of the three-dimensional object as a pixel value; a means for generating a two-dimensional image by observing the three-dimensional object from a plurality of viewpoints; When a three-dimensional shape feature quantity that does not depend on the direction of the viewpoint at the time of measuring the three-dimensional object is obtained, the image information is converted from three dimensions to two dimensions. A feature quantity having a three-dimensional shape can be obtained while eliminating the generated viewpoint dependency.

  The three-dimensional object search system and the three-dimensional object search method according to the present invention are not limited to the above-described embodiments, and various changes can be made without departing from the scope of the present invention. It is.

  Therefore, for example, although the Visual Rank algorithm is applied in the ranking generation means 40, other algorithms may be applied. Further, the shape feature quantity extraction unit 16 extracts the shape features by applying SIFT, but the shape features may be extracted by other methods.

  In addition, for example, instead of SIFT, if three-dimensional objects with different degrees of detail are generated, their shape index images are generated, and image feature quantities are extracted and used from these, the details can be accommodated by changes in scale. Can do. At that time, the feature amounts of all the details may be saved, or only the feature amount of the most characteristic scale may be used in consideration of the scale space like SIFT.

  In addition, as a response to multiple viewpoints, the feature values of all viewpoints may be saved, or changes in the feature values when the viewpoint is slightly changed are examined, and the change is small and robust to viewpoint changes. You may save only things. Alternatively, in order not to affect the viewpoint change, for example, a viewpoint from the direction of the direction of the 3D object surface corresponding to a certain pixel of the 2D image is set, and a Shape index image is generated from that viewpoint. The amount may be recalculated. Then, since the same shape index image is obtained from any viewpoint, the feature amount is completely independent of the viewpoint, which is preferable.

  The three-dimensional object search system and the three-dimensional object search method according to the present invention can be applied to a search service provided by an Internet service provider, a WEB service provider, or the like.

DESCRIPTION OF SYMBOLS 10 3D object search system 12 Keyword acquisition means 14 3D object search means 16 Shape feature quantity extraction means 18 Similarity calculation means 20 Ranking generation means 22 Search result output means 30 User terminal 40 WEB server

Claims (12)

Keyword acquisition means for acquiring a keyword for searching for a three-dimensional object;
3D object search means for searching for a 3D object related to the keyword acquired by the keyword acquisition means and acquiring the searched 3D object;
Shape feature amount extraction means for extracting shape feature amounts of the three-dimensional object acquired by the three-dimensional object search means;
Similarity calculation means for calculating the similarity of each shape feature quantity based on the plurality of shape feature quantities acquired by the shape feature quantity extraction means;
And ranking generating means for ranking each of the three-dimensional objects acquired by the three-dimensional object search means based on the similarity calculated by the similarity calculating means. ,
3D object search system. The shape feature amount extraction means includes:
A two-dimensional image is generated from the three-dimensional object acquired by the three-dimensional object search means, and a feature amount extracted from the generated two-dimensional image is used as a shape feature amount of the three-dimensional object;
The three-dimensional object search system according to claim 1. The shape feature amount extraction means includes:
A two-dimensional image obtained by observing the three-dimensional object acquired by the three-dimensional object retrieval unit from a plurality of viewpoints is generated, and a feature amount extracted from the generated two-dimensional image is used as a shape feature amount of the three-dimensional object. And
The three-dimensional object search system according to claim 2. The shape feature amount extraction means includes:
A two-dimensional image having a value calculated from the curvature of the three-dimensional object acquired by the three-dimensional object search means as a pixel value, and a two-dimensional image obtained by observing the three-dimensional object from a plurality of viewpoints, is generated. A feature amount extracted from a two-dimensional image is used as a shape feature amount of the three-dimensional object.
The three-dimensional object search system according to claim 3. The shape feature amount extraction means includes:
Applying the SIFT to the two-dimensional image to extract the feature quantity;
The three-dimensional object search system according to claim 4. The shape feature amount extraction means includes:
A second 3D object having a different level of detail is generated from the 3D object acquired by the 3D object search means, a 2D image is generated for each of the generated second 3D objects, and the generated 2D image A common shape feature amount is extracted from a three-dimensional object having a different level of detail by extracting the feature amount from each of
The three-dimensional object search system according to claim 4. The similarity calculation means includes:
Using the feature quantity of each two-dimensional image calculated by the shape feature quantity extraction unit, the number of corresponding points between the two-dimensional images is acquired, and the similarity matrix is generated using the acquired number of corresponding points. Calculating the importance between each shape from the degree matrix,
The three-dimensional object search system according to any one of claims 2 to 6. The ranking generation means includes
Each of the three-dimensional objects acquired by the three-dimensional object search means is ranked higher as the importance calculated by the similarity calculation means is higher.
The three-dimensional object search system according to claim 7. A keyword acquisition step of acquiring a keyword for searching for a three-dimensional object;
A three-dimensional object search step of searching for a three-dimensional object related to the keyword acquired in the keyword acquisition step and acquiring the searched three-dimensional object;
A shape feature amount extracting step of extracting a shape feature amount of the three-dimensional object acquired in the three-dimensional object search step;
Based on the plurality of shape feature amounts acquired in the shape feature amount extraction step, a similarity calculation step for calculating the similarity of each shape feature amount;
And a ranking generation step for ranking each of the three-dimensional objects acquired by the three-dimensional object search means based on the similarity calculated in the similarity calculation step. ,
3D object search method. Keyword acquisition means for acquiring a keyword for searching for a three-dimensional object;
3D object search means for searching for a 3D object related to the keyword acquired by the keyword acquisition means and acquiring the searched 3D object;
Shape feature amount extraction means for extracting shape feature amounts of the three-dimensional object acquired by the three-dimensional object search means;
Similarity calculation means for calculating the similarity of each shape feature quantity based on the plurality of shape feature quantities acquired by the shape feature quantity extraction means;
The computer is caused to function as a ranking generation unit that ranks each of the three-dimensional objects acquired by the three-dimensional object search unit based on the similarity calculated by the similarity calculation unit.
3D object search program. The three-dimensional object search program according to claim 10 is recorded.
Computer-readable recording medium. Means for generating a two-dimensional image using pixel values as values calculated from the curvature of the three-dimensional object, means for generating a two-dimensional image by observing the three-dimensional object from a plurality of viewpoints, and each of the two-dimensional images Characterized in that it comprises means for extracting a feature value from a three-dimensional shape feature value independent of the direction of the viewpoint at the time of measuring the three-dimensional object,
3D shape feature extraction system.