Method of searching 3-Dimensional images

• US 6,631,364 B1
• Filed: 12/22/1999
• Issued: 10/07/2003
• Est. Priority Date: 03/26/1997
• Status: Expired due to Term

• Current Assignee: National Research Council Canada
• Original Assignee: National Research Council Canada
• Inventors: Rioux, Marc, Paquet, Eric
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): Veillard, Jacques
• Application Number:
  US09/469,472
• Time in Patent Office: 1,385 Days
• Field of Search: 707/2, 707/3, 707/4, 707/5, 382/107, 382/159, 382/190, 345/156
• US Class Current: 1/1
• CPC Class Codes: G06F 16/56 having vectorial format
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06F 16/5862 using texture
• CPC Class Codes: G06V 20/64 Three-dimensional objects
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

In the past, databases containing three dimensional images were searched by keywords and indexes. For such functionality a set of keywords must be associated with each image. This is not a dynamic method and is prone to errors. It has been found that searching of three-dimensional images stored electronically can be performed in dependence upon characteristics of the image such as colour, shape, size, scale, etc. A method is disclosed for searching three dimensional images in dependence upon image characteristics.

Claims

1. A method of searching 3-dimensional models in a database, each 3-dimensional model represented by a 2-dimensional depiction, said method comprising:

(a) obtaining a 3-dimensional search criteria model represented by a 2-dimensional depiction;

(b) determining characteristic descriptors for each of the 3-dimensional models in the database and the 3-dimensional search criteria model, comprising;

(bi) determining an orientation independent reference frame for each model;

(bii) generating surface characteristic descriptors for each model on the basis of the orientation independent reference frame, the surface characteristic descriptors describing visible surface properties of each model;

(biii) generating physical characteristic descriptors for each model on the basis of the orientation independent reference frame, the physical characteristic descriptors describing physical properties of each model;

(c) determining differences between the surface and physical characteristic descriptors of the 3-dimensional search criteria model and the surface and physical characteristic descriptors of each of the 3-dimensional models in the database;

(d) defining a variance range for the differences; and

(e) providing the 2-dimensional depiction of the 3-dimensional models from the database for which the differences are within the variance range.

2. The method according to claim 1 wherein the step of obtaining the 3-dimensional search criteria model includes:

providing a plurality of randomly selected 3-dimensional models from the database for selection of the 3-dimensional search criteria model.

3. The method according to claim 1 wherein the step of obtaining the 3-dimensional search criteria model includes:

receiving a user provided 3-dimensional model for the 3-dimensional search criteria model.

4. The method according to claim 1 wherein the step of obtaining the 3-dimensional search criteria model includes:

receiving indication of selection of a 3-dimensional model provided for which the difference is within the variance range from a previous search for the 3-dimensional search criteria model.

5. The method according to claim 1 wherein the step of obtaining the 3-dimensional search criteria model includes:

aggregating a plurality of 3-dimensional models to form the 3-dimensional search criteria model.

6. The method according to claim 1 wherein the step of determining the difference includes:

receiving a selected weight for each of surface and physical characteristic descriptors;

determining an individual difference between each of the surface and physical characteristic descriptors for the search criteria model and each of the surface and physical characteristic descriptors for each of the 3-dimensional models in the database; and

calculating a weighted sum difference for each of the 3-dimensional models in the database based on the selected weights and the individual differences to form the differences for each of the 3-dimensional models in the database.

7. The method according to claim 1 wherein the step of determining an orientation independent reference frame includes:

determining the tensor of inertia for each model;

determining eignvalues and eigenvectors of the tensor of inertia;

orienting each eigenvector according to the mass distribution of each model along each eigenvector; and

using the oriented eignevectors as the axes for the orientation independent reference frame.

8. The method according to claim 1 wherein at least one of the surface and physical characteristic descriptors for each model is a global characteristic descriptor describing the model as a whole.

9. A computer readable medium having stored therein computer-executable instructions for searching 3-dimensional models in a database, each 3-dimensional model being represented by a 2-dimensional depiction, said computer executable instructions comprising:

(a) obtaining a 3-dimensional search criteria model represented by a 2-dimensional depiction;

(b) determining characteristic descriptors for each of the 3-dimensional models in the database and the 3-dimensional search criteria model, comprising;

(bi) determining an orientation independent reference frame for each model;

(bii) generating surface characteristic descriptors for each model on the basis of the orientation independent reference frame, the surface characteristic descriptors describing visible surface properties of each model;

(biii) generating physical characteristic descriptors for each model on the basis of the orientation independent reference frame, the physical characteristic descriptors describing physical properties of each model;

(c) determining differences between the surface and physical characteristic descriptors of the 3-dimensional search criteria model and the surface and physical characteristic descriptors of each of the 3-dimensional models in the database;

(d) defining a variance range for the differences; and

(e) providing the 2-dimensional depiction of the 3-dimensional models from the database for which the differences are within the variance range.

10. The computer-executable instructions according to claim 9, wherein the step of obtaining the 3-dimensional search criteria model includes:

providing a plurality of randomly selected 3-dimensional models from the database for selection of the 3-dimensional search criteria model.

11. The computer-executable instructions according to claim 9 wherein the step of obtaining the 3-dimensional search criteria model includes:

receiving a user provided 3-dimensional model for the 3-dimensional search criteria model.

12. The computer-executable instructions according to claim 9 wherein the step of obtaining the 3-dimensional search criteria model includes:

receiving indication of selection of a 3-dimensional model provided for which the difference is within the variance range from a previous search for the 3-dimensional search criteria model.

13. The computer-executable instructions according to claim 9 wherein the step of obtaining the 3-dimensional search criteria model includes:

aggregating a plurality of 3-dimensional models to form the 3-dimensional search criteria model.

14. The computer-executable instructions according to claim 9 wherein the step of determining the difference includes:

receiving a selected weight for each of surface and physical characteristic descriptors;

determining an individual difference between each of the surface and physical characteristic descriptors for the search criteria model and each of the surface and physical characteristic descriptors for each of the 3-dimensional models in the database; and

calculating a weighted sum difference for each of the 3-dimensional models in the database based on the selected weights and the individual differences to form the differences for each of the 3-dimensional models in the database.

15. The computer-executable instructions according to claim 9 wherein the step of determining a plurality of characteristic descriptors includes:

determining the tensor of inertia for each model;

determining eignvalues and eigenvectors of the tensor of inertia;

orienting each eigenvector according to the mass distribution of each model along each eigenvector; and

using the oriented eignevectors as the axes for the orientation independent reference frame.

16. The computer-executable instructions according to claim 9 wherein at least one of the surface and physical characteristic descriptors for each model is a global characteristic descriptor describing the model as a whole.