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

• US 5,802,525 A
• Filed: 01/21/1997
• Issued: 09/01/1998
• Est. Priority Date: 11/26/1996
• Status: Expired due to Fees

• 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/787,658
• Time in Patent Office: 588 Days
• Field of Search: 707/1, 707/5, 707/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: Y10S 707/99944 Object-oriented database structure

Abstract

A uniform distribution of affine invariants is produced for a plurality of one or more two-dimensional objects. Each of the two-dimensional objects is defined by a set of object points selected from an object feature domain. By selecting one or more five-point tuples of the object points, three of the object points divide the object feature domain into a region arrangement of seven regions while the fourth point of the four-point tuple lies in one of the seven regions and each of the four-point tuples further defines each of the seven regions as one of four non convex quadrilateral arrangements or one of three convex quadrilateral arrangements. A four-point tuple is said to belong to class I if the fourth point of the tuple resides in the I-th of the 7 regions defined by the first three points. A tagger identifies each of the four-point tuples as having one of the arrangements with one of the regions containing the fourth point of the four-point tuple. During a knowledge accumulation mode, and using either synthetically generated or real data, an equalizer accumulates knowledge about occupancy patterns incurred by four-point tuples belonging to each of the 7 classes and then derives the necessary remappings that will result in an expected uniform distribution over the range of invariants for all produced invariants.

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 two-dimensional object points, the set of two-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 four-point tuples of four object points, three of the points in the four-point tuple being non collinear and dividing the object feature domain into seven regions, the fourth point of the four-point tuple being in one of the seven regions, and defining one of two types of quadrilateral arrangement of the four-point tuple that include a non-convex quadrilateral (NCQ) arrangement and a convex quadrilateral (CQ) arrangement, four of the seven possible regions corresponding to the NCQ arrangements and the remaining three of the regions corresponding to the CQ arrangements;

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

a tagger that identifies each of the four-point tuples as having one of the seven region arrangements and one of the two types of the quadrilateral arrangements; and

an equalizer, executing on one or more of the processors, that creates a remapping for the 2-tuples corresponding to each of the seven region arrangements by redistributing all of the 2-tuples to produce a new distribution that is uniform over the range of invariants, the redistributing determined by the region arrangement and the quadrilateral arrangement of the four-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 2-tuple, one or more information fields, each information field identifying one of the objects from which the invariant 2-tuple was generated and all of the objects from which the invariant 2-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 polygon (e.g. triangle, square, rectangle etc.), a circle, and a ellipse.

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

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

8. A system, as in claim 6, where the new location of some of the 2-tuples is line symmetrical to the original location of the respective 2-tuple.

9. A system, as in claim 6, where the new location of some of the 2-tuples is derived from the original location of the respective 2-tuple via rotation and translation.

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

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

space="preserve" listing-type="equation">u'"'"'=a.sub.1 a.sub.3 u+a.sub.4 a.sub.5 ((u-0.5).sup.5 +(0.5).sup.5 +2u(0.5).sup.5)/5+(a.sub.5 a.sub.6 +a.sub.7)(u-1)-a.sub.1 a.sub.2 ((u-1).sup.3 +u.sup.3 +1)/3

space="preserve" listing-type="equation">v'"'"'=a.sub.1 a.sub.3 v+a.sub.4 a.sub.5 ((v-0.5).sup.5 +(0.5).sup.5 +2v(0.5).sup.5)/5+(a.sub.5 a.sub.6 +a.sub.7)(v-1)-a.sub.1 a.sub.2 ((v-1).sup.3 +v.sup.3 +1)/3.

12. A system, as in claim 1, where the object is a two-dimensional representation.

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

a graphical image, a human fingerprint, a design, a contour, and any collection of two-dimensional points.

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

a. providing a set of two-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 four-point sets from the set of two-dimensional object points to generate one or more four-point-tuples, each of the four-point tuples dividing the object feature domain into a region arrangement with seven regions, the seven regions defined by the four-point tuple as one of four non convex quadrilateral arrangements and one of three convex quadrilateral arrangements;

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

d. tagging each of the four-point tuples as having one of the seven regions and one of any of the non convex quadrilateral arrangements and convex quadrilateral arrangements; and

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

15. A method, as in claim 14, 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.

16. A method for storing two-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 four-point tuples from the set of identified features, each of the four-point tuples dividing the object feature domain into a region arrangement with seven regions, the seven regions defined by the four-point tuple as one of four non convex quadrilateral arrangements and one of three convex quadrilateral arrangements;

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

e. tagging each of the four-point tuples as having one of the seven regions and one of any of the non convex quadrilateral arrangements and convex quadrilateral arrangements; and

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

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

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

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

18. A method, as in claim 16, 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.

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

a graphical image, a human fingerprint, a design, a contour, and any collection of two-dimensional points.

20. A method for accessing one or more two-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 four-point tuples from the set of identified features, each of the four-point tuples dividing the object feature domain into a region arrangement with seven regions, the seven regions defined by the four-point tuple as one of four non convex quadrilateral arrangements and one of three convex quadrilateral arrangements;

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

e. tagging each of the four-point tuples as having one of the seven regions and one of any of the non convex quadrilateral arrangements and convex quadrilateral arrangements; and

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

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

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

a graphical image, a human fingerprint, a design, a contour, and any collection of two-dimensional points.

22. 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 two-dimensional object points, the set of two-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 four-point tuple means of four object points for representing one or more object features, three of the points in the four-point tuple being non collinear and dividing the object feature domain into seven regions, the fourth point of the four-point tuple being in one of the seven regions, and defining one of two types of quadrilateral arrangement of the four-point tuple that include a non convex quadrilateral (NCQ) arrangement and a convex quadrilateral (CQ) arrangement, four of the seven possible regions corresponding to the NCQ arrangements and the remaining three of the regions corresponding to the CQ arrangements;

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

a tagger means for identifying each of the four-point tuples as having one of the seven region arrangements and one of the two types of the quadrilateral arrangements; and

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