Data processing: database and file management or data structures – Database design – Data structure types
Patent
1997-01-21
1998-08-25
Black, Thomas G.
Data processing: database and file management or data structures
Database design
Data structure types
707530, 345423, 345424, G06F 1730
Patent
active
057993122
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.
REFERENCES:
patent: 5602979 (1997-02-01), Loop
patent: 5734384 (1998-03-01), Yanof et al.
Ambartzumian, R.V.,Factorization Calculus and Geometric Probabability. Cambridge University Press, 1990, pp. 82-99.
Califano A. et al., "FLASH: A Fast Look-Up Algorithm for String Homology" Computational Approaches Biological Systems. To Appear Feb. 1995.
Califano A. et al., "Multidimensional Indexing for Recognizing Visual Shapes" IEEE Trans. on Pattern Analysis & Machie Intel., 16:4, pp. 373-392, 1994.
Faloutsos C. et al., "Beyond Uniformity & Independence: Analysis of R-trees Using the . . . " Proceed. 1994 ACM PODS Conference on Principles of Database Systems, Minneapolis, MN, 1994.
Faloutsos, C., "Gray Codes for Partial Match and Range Queries" IEEE Transactions on Software Engineering, 14:10, 1987.
Flynn,P. et al., "3D Object Recognition Using Invariant Feature Indexing of Interpret . . . " Computer Visions,Graphics,& Image Processing:Image Understanding, 55:2, pp. 119-129, 1992.
Fisanick, W. et al., "Similarity Searching on CAS Registry Substances 1:Global . . . " Journal of Chemical Information & Computer Sciences, vol. 32,No. 6, pp. 664-674, 1992.
Fisanick,W. et al., "Similarity Search On CAS Registry Substances 2:2D Structural Simil . . . " Journal of Chemical Information & Computer Sciences, vol. 34, No. 1, pp. 130-140, 1994.
Gavrila D. et al., "3D Object Recognition From 2D Images Using Geometric Hashing" Pattern Recognition Letters, 13:4, pp. 263-278, 1992.
Guenther O. et al., "Research Issues In Spatial Databases" ACM Sigmod Record, 19:4, pp. 61-67, 1990.
Guttman A., "R-trees: A Dynamic Index Structure For Spatial Searching" Proceedings 1984 ACM Sigmod Conference, pp. 47-57, 1984.
Haralick R., et al., "Optimal Affine-Invariant Matching: Performance Characterization" Proceedings SPIE Conference On Image Storage & Retrieval, San Jose, CA, Jan., 1992.
Haralick, R. et al., "Optimal Affine-Invariant Point Matching" Proc. 6th Israeli Conf. On Artificial Intell. & Computer Vision, Tel Aviv, Isreal Dec. 1989.
Jagadish, H.V. "Linear Clustering of Objects with Multiple Attributes" Proceedings 1990 ACM Sigmod Conference on the Management of Data, Atlantic City, NJ 1990.
Knott, G., "Hashing Functions" The Computer Journal, 18:3, 1975.
Kroll B. et al., "Distributing A Search Structure Among A Growing Number of Processors" Proceedings 1994 ACM Sigmod Conference The Management of Data, pp. 265-276, 1994.
Lamdan Y. et al., "Geometric Hashing: A General & Efficient Model-based Recognition Scheme" Proceedings Int'l Conference on Computer Vision, pp. 238-249, 1988.
Matsliach G. et al., "An Efficient Method For Distributing Search Structures" Proc. First Int'l Conference on Parallel & Distributed Information Systems, pp. 159-166, 1991.
Press, W. et al., "Numerical Recipes in C: The Art of Scientific Computing" Cambridge University Press 1988, pp. 680-689.
Rigoutsos I. et al., "Searching In Parallel For Similar Strings" IEEE Computational Science & Engineering, pp. 60-75, Summer, 1994.
Rigoutsos I. et al., "A Bayesian Approach to Model Matching with Geometric Hashing" Computer Vision & Image Understanding, 61:7, Jul., 1995.
Rigoutsos I. et al., "Several Results on Affine Invariant Geometric Hashing" Proceed. 8th Int'l Conf. on Computer Vision & Artificial Intel., Tel Aviv, Isreal Dec. 1991.
Rigoutsos, I., "Massively Parallel Bayesian Object Recognition" PhD Thesis, New York University, Aug., 1992, pp. v-xii, 71-159, & 184-198.
Rigoutsos, I. et al., "Flexible Substructure Matching & Novel Conformer Generation For . . . " Submitted for Publication to Journal of Computer-Aided Molecular Design, Jun., 1996.
Salzberg, B., "Practical Spatial Database Access Methods" IEEE Symposium on Applied Computing, pp. 82-90, 1991.
Satoh, T. et al., "An Index Structure for Parallel Database Processing" Proceedings 2nd IEEE Workshop on Research Issues On Data Engineering, pp. 224-225, 1992.
Solomon, H. Geometric Probability. Society for Industrial & Applied Mathematics Philadelphia, Pennsylvania, 1978.
Stein F. et al., "Efficient Two-dimensional Object Recognition" Proceed. Int'l conference on Pattern Recognition, pp. 596-600, Atlantic City, NJ Jun., 1990.
Weinshall, D. et al. "3D Object Recognition By Indexing Structural Invariants From . . . " Proceed. Int'l Conference on Computer Vision, pp. 264-268, Berlin, Germany, May, 1993
Black Thomas G.
Ho Ruay Lian
International Business Machines - Corporation
Percello Louis J.
LandOfFree
Three-dimensional affine-invariant hashing defined over any thre does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Three-dimensional affine-invariant hashing defined over any thre, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Three-dimensional affine-invariant hashing defined over any thre will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-46945