Method and system for finding a document image in a document collection using localized two-dimensional visual fingerprints

1. An image management method for storing, indexing, searching, and/or retrieving image data comprising the steps of:

identifying keypoints in images, including keypoints in a query image of a query document and keypoints in potential target document images of a collection of potential target documents;

generating fingerprint information from the keypoints, wherein the fingerprint information and accompanying images are organized in a Fan Tree structure, which provides near neighbor searching in a high dimensional space, wherein the near-neighbor searching in the high dimensional space provided by the Fan Tree structure includes supporting looking up of near misses of fingerprints, including fingerprints which are less than identical fingerprints of the query image by a predetermined tolerance;

comparing the fingerprint information of the query image with fingerprint information of the potential target document images in the collection of potential target documents;

determining a best match between the fingerprint information of the query image and the potential target document images;

retrieving at least one target document image based on the determining step; and

at least one of displaying, printing, storing or transmitting the retrieved at least one target document image.

2. The method of claim 1 , wherein a keypoint comprises:

a consistently identifiable aspect of an image.

3. The method of claim 1 , further including generating a minimum necessary set of possible fingerprint permutations, and registering the minimum necessary set in the Fan Tree, wherein the minimum necessary set is defined as being those fingerprint permutations from which all other needed permutations can be derived.

4. The method according to claim 1 wherein a center of origin of an image is computed from a subset of a group of keypoints determined to be the closest keypoints in a localized fingerprint neighborhood of an image.

5. The method of claim 1 , wherein the image comprises text and one or more of handwritten text, symbols, line-art and graphic drawings, clip-art, charts, tables, spreadsheets, and document marks.

6. The method of claim 5 , wherein the text searching is performed through use of centroids which calculate the visual center of an image.

7. The method of claim 1 , wherein the fingerprints are computed using sequences of quantized transformation-invariant two-dimensional persistent ratios.

8. The method of claim 1 , wherein the fingerprints are computed from neighborhoods of keypoints based on a smallest least common quantization digit process applied to a sequence of digits representing the fingerprint, the least common quantization digit process including,

determining a value of the of the smallest least common digit in the fingerprint sequence,

scanning the sequence to determine positions of the smallest least common digit within the fingerprint sequence, and

permutating, for each position in the fingerprint sequence, a beginning portion of the fingerprint sequence up to the location of the smallest least common digit to the end of the fingerprint sequence, while keeping the internal sequence of the beginning and end portions unchanged.

9. The method of claim 1 , wherein the fingerprints are selected by measuring fingerprint strength based on analyzing fingerprint digit run-sequence.

10. An image management method for storing, indexing, searching, and/or retrieving image data comprising the steps of:

identifying keypoints in images, including keypoints in a query image of a query document and keypoints in potential target document images of a collection of potential target documents;

generating fingerprint information from the keypoints;

comparing the fingerprint information of the query image with fingerprint information of the potential target document images in the collection of potential target documents;

determining a best match between the fingerprint information of the query image and the potential target document images;

retrieving at least one target document image based on the determining step; and

at least one of displaying, printing, storing or transmitting the retrieved at least one target document image; and,

applying a weighted fingerprint scoring analysis, which includes processing counts of matching fingerprints in selected image zones of the query image and the target images.

11. An image management method for storing, indexing, searching, and/or retrieving image data comprising the steps of:

identifying keypoints in images, including keypoints in a query image of a query document and keypoints in potential target document images of a collection of potential target documents;

generating fingerprint information from the keypoints;

comparing the fingerprint information of the query image with fingerprint information of the potential target document images in the collection of potential target documents;

determining a best match between the fingerprint information of the query image and the potential target document images;

retrieving at least one target document image based on the determining step;

at least one of displaying, printing, storing or transmitting the retrieved at least one target document image; and,

applying a noise guard process in a candidate fingerprint selection process when one or more of determined triangle ratios in a fingerprint sequence of a query image falls within a predetermined tolerance level of quantization thresholds, wherein if a distance from a persistent ratio value to its nearest quantization threshold is below a pre-specified tolerance level, the noise guard generates each relevant quantization sequence of candidate fingerprints.

12. The method according to claim 11 , wherein the noise guard is applied during document collection pre-processing.

13. The method according to claim 11 , wherein the noise guard is applied during a query operation.

14. An image management system within a computer operable system for storing, indexing, searching, and/or retrieving image data comprising:

an identification module configured to identify keypoints in images, including keypoints in a query image of a query document and keypoints in potential target document images of a collection of potential target documents;

a fingerprint generation module configured to generate fingerprint information from the keypoints, wherein fingerprints of the fingerprint information are sequences of quantized transformation-invariant two-dimensional persistent ratios;

a comparison module configured to compare the fingerprint information of the query image with fingerprint information of the potential target document images in the collection of potential target documents;

a matching module configured to determine a best match between the fingerprint information of the query image and the potential target document images;

a retrieval module configured to retrieve at least one target document image based on the determining step; and

at least one of an electronic display, a printer, a memory storage or a computer network to display, print, store or transmit the retrieved at least one target document image;

wherein a noise guard method is employed to compensate for errors.

15. The system of claim 14 , wherein fingerprints and accompanying images are organized in a Fan Tree structure.

16. The system of claim 14 , wherein the image capture hardware comprises at least one of:

a digital camera, cell phone with a camera, a scanner or a computer generated electronic image.

17. The system of claim 14 , wherein the image comprises text and one or more of handwritten text, symbols, line-art and graphic drawings, clip-art, charts, tables, spreadsheets, and document marks.

18. The system of claim 17 , wherein the text searching is performed through use of centroids which calculate the visual center of an image.

19. The system of claim 14 , wherein the fingerprints are computed using sequences of quantized transformation-invariant two-dimensional persistent ratios.

20. The method of claim 1 , where the keypoints are identified in each image solely based on visual image properties, with no assumptions of belonging to an object type, and without requiring any training images or complex training systems for learning object keypoint properties from a given set of supervised training images.

21. The method of claim 1 , wherein the near-neighbor searching in the high dimensional space provided by the Fan Tree structure includes supporting looking up of near misses of fingerprints all by using a single image, no training images, and no preconceived notions of specific three-dimensional objects in computer vision.