Three-dimensional affine-invariant hashing defined over any three-dimensional convex domain and producing uniformly-distributed hash keys

• US 5,799,312 A
• Filed: 01/21/1997
• Issued: 08/25/1998
• Est. Priority Date: 11/26/1996
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Rigoutsos, Isidore
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): HO, RUAY L
• Application Number:
  US08/786,054
• Time in Patent Office: 581 Days
• Field of Search: 707/1-10, 707/100-104, 707/200-206, 707/530, 345/423, 345/424, 345/427
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06V 20/64 Three-dimensional objects
• CPC Class Codes: G06V 40/10 Human or animal bodies, e.g. vehicle occupants or pedestrians; Body parts, e.g. hands
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

A uniform distribution of affine invariants (3-tuples) is produced for a plurality of one or more three-dimensional objects. Each of the three-dimensional objects, capable of a plurality of affine transformations, is defined by a set of object points (feature points) selected from an object feature domain. By selecting one or more five-point tuples of the object points, four of the object points divide the object feature domain into a region arrangement of fifteen regions while the fifth point of the five-point tuple lies in one of the fifteen regions and each of the five-point tuples further defines each of the fifteen regions as one of five reentrant polyhedral (RP) arrangements or one of ten non-reentrant polyhedral (NRP) arrangements. A five-point tuple is said to belong to class i if the fifth point of the tuple resides in the i-th of the 15 regions defined by the first four points. A tagger identifies each of the five-point tuples as having one of the arrangements with one of the regions containing the fifth point of the five-point-tuple. During a knowledge accumulation mode, and using either synthetically generated (Monte-Carlo simulation) or real data, an equalizer accumulates knowledge about occupancy patterns incurred by five-point tuples belonging to each of the 15 classes and then derives the necessary remappings that will result in an expected uniform distribution over the range of invariants for all produced invariants. After the knowledge accumulation phase, the equalizer enters its redistribution mode the end-product of which is the creation of a new distribution of affine invariants (3-tuples) that is uniform over the range of invariants. A stacker then stacks the remapped regions to create a complete uniform distribution for all the affine invariants that the transformer produces. The system produces a table which associates combinations of object points (five-point tuples) to affine invariants (3-tuples); the table can be used as the core of an indexing-based store and retrieve system, it can be used to determine and identify over-represented constructs of object points, to determine potential interaction for ligand-receptor complexes, etc.

Claims

1. A computer system of one or more processors for producing a uniform distribution of affine invariants for a plurality of one or more objects, comprising:

a database of one or more objects, each of the objects identified by a set of three-dimensional object points, the set of three-dimensional object points uniformly selected from an object feature domain, each of the objects further capable of being transformed through zero or more affine transformations, the database being stored in one or more memories that are accessible by the processors;

one or more five-point tuples of five object points, four of the points in the five-point tuple being non-coplanar and dividing the object feature domain into fifteen regions, the fifth point of the five-point tuple being in one of the fifteen regions, and defining one of two types of polyhedral arrangement of the five-point tuple that include a non reentrant polyhedral (NRP) arrangement and a reentrant polyhedral (RP) arrangement, five of the fifteen possible regions corresponding to the RP arrangements and the remaining ten of the regions corresponding to the NRP arrangements;

a transformer for representing each of the five-point tuples by a 3-tuple that is invariant under any of the affine transformations, the transformer producing a range of invariants for all arrangements of the five-point-tuples,

a tagger that identifies each of the five-point tuples as having one of the fifteen region arrangements and one of the two types of the polyhedral arrangements; and

an equalizer, executing on one or more of the processors, that creates a remapping for the 3-tuples corresponding to each of the fifteen region arrangements by redistributing a plurality of the 3-tuples to produce a new distribution that is uniform over the range of invariants, the redistributing determined by the region arrangement and the polyhedral arrangement of the five-point tuple as identified by the tagger.

2. A system, as in claim 1, further comprising a stacker that stacks the new distributions to produce a uniform distribution for all the affine invariants produced by the transformer.

3. A system, as in claim 1, further comprising a table having a plurality of records, each record having an index defined by the invariant 3-tuple, one or more information fields, each information field identifying one of the objects from which the invariant 3-tuple was generated and all of the objects from which the invariant 3-tuple was generated being in one or more of the information fields, where the number of information fields is the same for all of the records within a tolerance.

4. A system, as in claim 3, further comprising a loader, that loads each of the processors with part of the records so that the burden induced on each of the processors by a task that operates on the table is balanced.

5. A system, as in claim 1, where the object points are uniformly selected from the object feature domain, the domain being any one of the following:

a convex polyhedron (e.g. cube, parallelepiped, etc.), a sphere, and a ellipsoid.

6. A system, as in claim 1, where the polyhedral arrangement is RP and the equalizer redistributes the 3-tuples by moving each 3-tuple from an original location to a new location that is dependent on the original location of the 3-tuple.

7. A system, as in claim 6, where the new location (u'"'"',v'"'"',w'"'"') is given by

8. A system, as in claim 6, where the new location of some of the 3-tuples is derived from the original location of the respective 3-tuple via reflection.

9. A system, as in claim 1, where the polyhedral arrangement is NRP and the equalizer redistributes the 3-tuples by moving each 3-tuple from an original location to a new location that is dependent on the original location of the 3-tuple.

10. A system, as in claim 9, where the object feature domain is a cube and the redistribution can be approximated by:

space="preserve" listing-type="equation">u'"'"'=(0.00625+0.2 (u-0.5).sup.5)a.sub.1 +(0.41666+0.33333(u-0.5).sup.3)(a.sub.4 +0.08333(a.sub.7 +a.sub.8))+(0.00625+0.01250 (u-0.5))(150.60800+a.sub.2 +a.sub.3 +6.66666(a.sub.5 +a.sub.6)+0.55555 a.sub.9)

space="preserve" listing-type="equation">v'"'"'=(0.00625+0.2(v-0.5).sup.5)a.sub.2 +(0.41666+0.33333(v-0.5).sup.3)(a.sub.5 +0.08333(a.sub.7 +a.sub.9))+(0.00625+0.01250(v-0.5))(150.60800+a.sub.1 +a.sub.3 +6.66666(a.sub.4 +a.sub.6)+0.55555 a.sub.8) 14

space="preserve" listing-type="equation">w'"'"'=(0.00625+0.2 (w-0.5).sup.5)a.sub.3 +(0.41666+0.33333(w-0.5).sup.3)(a.sub.6 +0.08333(a.sub.8 +a.sub.9))+(0.00625+0.01250(w-0.5))(150.60800+a.sub.1 +a.sub.2 +6.66666 (a.sub.4 +a.sub.5)+0.55555 a.sub.7).

11. A system, as in claim 1, where the object is a three dimensional representation.

12. A system, as in claim 11, where the three-dimensional representation is any one of the following:

a three-dimensional curve, a surface patch, depth measurements, range data, and any collection of three-dimensional points.

13. A method for producing a set of 3-tuple affine invariants with a range, the affine invariants being distributed over the range, comprising the steps of:

a. providing a set of three-dimensional object points that describe an object feature domain of an object in an object set of one or more objects, the object points being uniformly distributed over a convex domain, each of the objects being capable of being transformed through one or more affine transformations;

b. selecting one or more five-point sets from the set of three-dimensional object points to generate one or more five-point-tuples, each of the five-point tuples dividing the object feature domain into a region arrangement with fifteen regions, the fifteen regions defined by the five-point tuple as one of five reentrant polyhedral arrangements and one of ten non-reentrant polyhedral arrangements;

c. transforming each of the five-point tuples by affine transformation to produce a 3-tuple affine invariant representing each of the five-point-tuples;

d. tagging each of the five-point tuples as having one of the fifteen regions and one of any of the reentrant and non-reentrant polyhedral arrangements; and

e. remapping the 3-tuple affine invariants corresponding to each of the fifteen regions by redistributing all of the 3-tuple affine invariants to produce a new distribution of 3-tuple affine invariants that is uniform within tolerance over the range, the redistributing determined by the region arrangement and the polyhedral arrangement of the respective five-point-tuple to cause a frequency of occurrence of each of the new 3-tuple affine invariants to be the same within a tolerance.

14. A method, as in claim 13, further comprising the step of:

f. stacking all the new distributions to produce a uniform within the tolerance distribution for all the new affine invariants.

15. A method for storing three-dimensional objects in a database, comprising the steps of:

a. selecting an object from the set of objects;

b. identifying a set of feature points in the selected object;

c. producing one or more sets of five-point tuples from the set of identified features, each of the five-point tuples dividing the object feature domain into a region arrangement with fifteen regions, the fifteen regions defined by the five-point tuple as one of five reentrant polyhedral arrangements and one of ten non-reentrant polyhedral arrangements;

d. transforming each of the five-point tuples by affine transformation to produce a 3-tuple affine invariant representing each of the five-point-tuples;

e. tagging each of the five-point tuples as having one of the fifteen regions and one of any of the reentrant and non-reentrant polyhedral arrangements; and

f. generating a new 3-tuple affine invariant corresponding to each of the fifteen regions by repositioning the 3-tuple affine invariant to produce a new distribution of 3-tuple affine invariants that is uniform within a tolerance over the range;

g. associating and storing the new 3-tuple affine invariant with the respective five-point tuple from which the new 3-tuple affine invariant was generated.

16. A method, as in claim 15, further comprising the steps of:

h. establishing a predicate about the database based on the labeling of one or more selected new 3-tuple affine invariants.

17. A method, as in claim 15, further comprising the steps of:

h. qualitatively assessing information about one or more of the objects in the database by examining the size of the tolerance and one or more locations where deviations occur.

18. A method, as in claim 15, where the three-dimensional objects include any one of the following:

a three-dimensional curve, a surface patch, depth measurements, range data, and any collection of three-dimensional points.

19. A method for accessing one or more three-dimensional objects from a database, using a query set of one or more objects, the method comprising the steps of:

a. selecting an object from the query set of objects;

b. identifying a set of feature points in the selected object;

c. producing one or more sets of five-point tuples from the set of identified features, each of the five-point tuples dividing the object feature domain into a region arrangement with fifteen regions, the fifteen regions defined by the five-point tuple as one of five reentrant polyhedral arrangements and one of ten non-reentrant polyhedral arrangements;

d. transforming each of the five-point tuples by affine transformation to produce a 3-tuple affine invariant representing each of the five-point-tuples;

e. tagging each of the five-point tuples as having one of the fifteen regions and one of any of the reentrant and non-reentrant polyhedral arrangements; and

f. generating a new 3-tuple affine invariant corresponding to each of the fifteen regions by repositioning the 3-tuple affine invariant to produce a new distribution of 3-tuple affine invariants that is uniform within tolerance over the range;

g. using the new 3-tuple affine invariant to access a memory containing a plurality of associations between one or more stored 3-tuple affine invariants and respective information about one or more stored objects.

20. A method, as in claim 19, where the three-dimensional objects include any one of the following:

a three-dimensional curve, a surface patch, depth measurements, range data, and any collection of three-dimensional points.

21. A computer system of one or more processors for producing a distribution of affine invariants for a plurality of one or more objects, comprising:

a database means for storing one or more objects, each of the objects identified by a set of three-dimensional object points, the set of three-dimensional object points uniformly selected from an object feature domain, each of the objects further capable of being transformed through zero or more affine transformations, the database being stored in one or more memories that are accessible by the processors;

one or more five-point tuple means of five object points for representing one or more object features, four of the points in the five-point tuple being non coplanar and dividing the object feature domain into fifteen regions, the fifth point of the five-point tuple being in one of the fifteen regions, and defining one of two types of polyhedral arrangement of the five-point tuple that include a reentrant polyhedral (RP) arrangement and a non-reentrant polyhedral (NRP) arrangement, five of the fifteen possible regions corresponding to the RP arrangements and the remaining ten of the regions corresponding to the NRP arrangements;

a transformer means for representing each of the five-point tuples by a 3-tuple that is invariant under any of the affine transformations, the transformer producing a range of invariants for all arrangements of the five-point-tuples;

a tagger means for identifying each of the five-point tuples as having one of the fifteen region arrangements and one of the two types of the polyhedral arrangements; and

an equalizer means, executing on one or more of the processors, for creating a remapping for the 3-tuples corresponding to each of the fifteen region arrangements by redistributing all of the 3-tuples to produce a new distribution that is uniform over the range of invariants, the redistributing determined by the region arrangement and the polyhedral arrangement of the five-point tuple as identified by the tagger.