Determining and using geometric feature data

• US 8,000,536 B2
• Filed: 03/04/2005
• Issued: 08/16/2011
• Est. Priority Date: 03/08/2004
• Status: Expired due to Fees

• Current Assignee: Siemens Product Lifecycle Management Software Incorporated (Siemens AG)
• Original Assignee: Siemens Product Lifecycle Management Software Incorporated (Siemens AG)
• Inventors: Pötke, Marco
• Primary Examiner(s): Repko; Jason M
• Assistant Examiner(s): Thomas; Mia M
• Application Number:
  US10/598,448
• Publication Number:
  US 20070217681A1
• Time in Patent Office: 2,356 Days
• Field of Search: 382/103, 382/118, 382/203, 382/225, 382/159, 382/181, 702/19
• US Class Current: 382/203
• CPC Class Codes: G06V 10/507 Summing image-intensity values; Histogram projection analysis

Abstract

The invention concerns a method for determining feature data that represents information about the shape of an object. A partitioning scheme (RP) is determined that defines a plurality of cells (p) in the space in which the object is located such that at least some of the cells (p) each contain a respective portion of the object, and the feature data is determined for the object on the basis of at least one property of the respective portions of the object that are contained in the plurality of cells (p). According to a first aspect of the invention, at least two of the plurality of cells (p) overlap each other at least in part, and according to a second aspect of the invention, at least some of the boundaries of the cells (p) delimit a plurality of regions (r) in the space in which the object is located such that the respective portions of the object that are contained in the plurality of regions (r) are approximately equal to each other with respect to a predetermined measurement metric. The method may be used for performing a similarity search or for performing a similarity classification. A computer program product and an apparatus comprise corresponding features. The invention provides a technology for improving the accuracy and/or effectiveness and/or performance and/or usefulness of prior art methods for determining geometric feature data.

Claims

1. A method for determining feature data that represents information about the shape of an object, the object being located in a k-dimensional space, the method comprising the steps of:

determining, by a computer, a partitioning scheme that defines a plurality of cells in the space in which the object is located such that at least some of the cells each contain a respective portion of the object, wherein at least some of the cells defined by the partitioning scheme represent k-dimensional spheres, k-dimensional shells, sectors of k-dimensional spheres, or sectors of k-dimensional shells in the space in which the object is located; and

determining, by the computer, the feature data for the object on the basis of at least one property of the respective portions of the object that are contained in the plurality of cells, wherein at least two of the plurality of cells overlap each other at least in part.

2. The method of claim 1, wherein the plurality of cells comprises at least a first and a second group of cells such that the union of the cells in the first group of cells coincides with the union of the cells in the second group of cells, wherein each cell of the first group of cells overlaps at least in part with at least one respective cell of the second group of cells.

3. The method of claim 1 or claim 2, wherein the plurality of cells comprises at least a group of nested cells, wherein all cells of the group of nested cells are nested within each other.

4. The method of claim 3, wherein the cells of the group of nested cells form a sequence in which the k-dimensional volume of the respective portions of the object that are contained in the cells of the group of nested cells increases in a substantially regular manner.

5. The method of claim 1, wherein the feature data for the object is determined on the basis of the k-dimensional volume of each respective portion of the object contained in each cell of the plurality of cells and/or on the basis of data defining the k principal axes of each respective portion of the object contained in each cell of the plurality of cells.

6. The method of claim 1, wherein the determining steps are performed first for a first object and then also performed for a set of second objects to determine feature data for the first object and for each of the set of second objects, and further comprising performing a similarity search between the first object and the set of second objects based on a comparison of the determined feature data.

7. The method of claim 1, wherein the determining steps are performed to determine feature data for each object of a set of objects, and wherein the objects of the set of objects are grouped according to their respective similarities on the basis of a classification of the determined feature data.

15. A non-transitory computer-readable medium encoded with executable program instructions for execution by at least one processor, wherein the program instructions cause the at least one processor to perform a method according to claim 1 or claim 8.

16. An apparatus, comprising:

at least one processor, wherein the apparatus is configured to perform a method according to claim 1 or claim 8.

8. A method for determining feature data that represents information about the shape of an object, the object being located in a k-dimensional space, the method comprising the steps of:

determining, by a computer, a partitioning scheme that defines a plurality of cells in the space in which the object is located such that at least some of the cells each contain a respective portion of the object, and

determining, by the computer, the feature data for the object on the basis of at least one property of the respective portions of the object that are contained in the plurality of cells, wherein the partitioning scheme is determined such that at least some of the boundaries of the cells defined by the partitioning scheme are adapted to the individual shape of the object to delimit a plurality of regions in the space in which the object is located such that the respective portions of the object that are contained in the plurality of regions are approximately equal to each other with respect to a predetermined measurement metric.

9. The method of claim 8, wherein the plurality of cells comprises at least a first and a second group of cells such that the union of the cells in the first group of cells coincides with the union of the cells in the second group of cells, wherein each cell of the first group of cells overlaps at least in part with at least one respective cell of the second group of cells.

10. The method of claim 8 wherein at least one region of the plurality of regions contains at least two cells of the plurality of cells that overlap each other at least in part.

11. The method of claim 8, wherein all regions of the plurality of regions are disjoint with respect to each other.

12. The method of claim 8, wherein the measurement metric, for each region of the plurality of regions, is the k-dimensional volume of the respective portion of the object contained in this region.

13. The method of claim 8, wherein each region of the plurality of regions corresponds to the union and/or difference and/or intersection of at least two cells of the plurality of cells or to exactly one cell of the plurality of cells.

14. The method of claim 8, wherein at least some of the regions of the plurality of regions represent k-dimensional spheres and/or k-dimensional shells and/or sectors of k-dimensional spheres and/or sectors of k-dimensional shells in the space in which the object is located.