DETERMINING AND USING GEOMETRIC FEATURE DATA

• US 20070217681A1
• Filed: 03/04/2005
• Published: 09/20/2007
• Est. Priority Date: 03/08/2004
• Status: Active Grant

• Current Assignee: Siemens Product Lifecycle Management Software Incorporated (Siemens AG)
• Original Assignee: Siemens Product Lifecycle Management Software Incorporated (Siemens AG)
• Inventors: Potke, Marco
• Granted Patent: US 8,000,536 B2
• Time in Patent Office: Days
• US Class Current: 382/190
• 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 (o), the object (o) being located in a k-dimensional space, the method comprising the steps of:

determining a partitioning scheme (RE, RP) that defines a plurality of cells (p) in the space in which the object (o) is located such that at least some of the cells (p) each contain a respective portion of the object (o), and

determining the feature data for the object (o) on the basis of at least one property of the respective portions of the object (o) that are contained in the plurality of cells (p),

the method being characterized in that

at least two of the plurality of cells (p) overlap each other at least in part.

2. The method of claim 1, characterized in that the plurality of cells (p) comprises at least a first and a second group of cells (gi₁, gi₂;

go₁, go₂) such that the union of the cells in the first group of cells (gi₁;

go₁) coincides with the union of the cells in the second group of cells (gi₂;

go₂), wherein each cell of the first group of cells (gi₁;

go₁) overlaps at least in part with at least one respective cell of the second group of cells (gi₂;

go₂).

3. The method of claim 1 or claim 2, characterized in that the plurality of cells (p) comprises at least a group of nested cells (gn), wherein all cells of the group of nested cells (gn) are nested within each other.

4. The method of claim 3, characterized in that the cells of the group of nested cells (gn) form a sequence in which the k-dimensional volume of the respective portions of the object (o) that are contained in the cells of the group of nested cells (gn) increases in an at least approximately regular manner.

6. The method of claim 5 and one of claims 1 to 4.

12. The method of one of claims 1 to 11, characterized in that at least some of the cells (p) defined by the partitioning scheme (DP, RE, RP) 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 (o) is located.

13. The method of one of claims 1 to 12, characterized in that the feature data for the object (o) is determined on the basis of the k-dimensional volume of each respective portion of the object (o) contained in each cell (p) of the plurality of cells (p) and/or on the basis of data defining the k principal axes of each respective portion of the object (o) contained in each cell (p) of the plurality of cells (p).

14. Use of a method according to one of claims 1 to 13 for performing a similarity search between a first object and a set of second objects, wherein feature data for the first object and for each of the set of second objects is determined according to the method according to one of claims 1 to 13, and wherein the similarity search is performed on the basis of a comparison of the determined feature data.

15. Use of a method according to one of claims 1 to 13 for performing a similarity classification of a set of objects, wherein feature data for each object of the set of objects is determined according to the method according to one of claims 1 to 13, 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.

16. Computer program product comprising program instructions for execution by at least one processor, wherein the program instructions cause the at least one processor to perform or use a method according to one of claims 1 to 15.

17. Apparatus comprising at least one processor, wherein the apparatus is adapted for performing or using a method according to one of claims 1 to 15.

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

determining a partitioning scheme (DP, RP) that defines a plurality of cells (p) in the space in which the object (o) is located such that at least some of the cells (p) each contain a respective portion of the object (o), and

determining the feature data for the object (o) on the basis of at least one property of the respective portions of the object (o) that are contained in the plurality of cells (p),

the method being characterized in that

the partitioning scheme (DP, RP) is determined such that at least some of the boundaries of the cells (p) defined by the partitioning scheme (DP, RP) are adapted to the individual shape of the object (o) to delimit a plurality of regions (r) in the space in which the object (o) is located such that the respective portions of the object (o) that are contained in the plurality of regions (r) are approximately equal to each other with respect to a predetermined measurement metric.

7. The method of claim 5 or claim 6, characterized in that at least one region (r) of the plurality of regions (r) contains at least two cells (p) of the plurality of cells (p) that overlap each other at least in part.

8. The method of one of claims 5 to 7, characterized in that all regions (r) of the plurality of regions (r) are disjoint with respect to each other.

9. The method of one of claims 5 to 8, characterized in that the measurement metric, for each region (r) of the plurality of regions (r), is the k-dimensional volume of the respective portion of the object (o) contained in this region (r).

10. The method of one of claims 5 to 9, characterized in that each region (r) of the plurality of regions (r) corresponds to the union and/or difference and/or intersection of at least two cells (p) of the plurality of cells (p) or to exactly one cell (p) of the plurality of cells (p).

11. The method of one of claims 5 to 10, characterized in that at least some of the regions (r) of the plurality of regions (r) 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 (o) is located.