SEARCHING A REPOSITORY OF DOCUMENTS USING A SOURCE IMAGE AS A QUERY

• US 20100185615A1
• Filed: 01/14/2009
• Published: 07/22/2010
• Est. Priority Date: 01/14/2009
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: MONGA, VISHAL
• Granted Patent: US 8,195,672 B2
• Time in Patent Office: Days
• US Class Current: 707/736
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content

Abstract

What is disclosed is a system and method for searching a repository of documents containing images using an image as a query. The present method enables the adjustment of a threshold level through a no-reference quality assessment of the query image which produces an estimated measure of quality for the image. For each image in each document in the repository, a distance is computed between a hash value of each image extracted from the document and the hash value of the query image. Documents are flagged as possible matches if the computed distance is less than the adjusted threshold. Documents flagged as a result of the search are retrieved and provided to the user. The present method can be used along or as an adjunct to text-based search techniques. Other embodiments are provided.

Claims

1. A method for searching a repository of documents using an image as a search query, the method comprising:

receiving a query image I* to be used to search a repository of documents;

hashing said query image to obtain a hash value h(I*) for said query image;

setting an initial threshold level τ

₀ for said search;

performing a no-reference quality assessment on said query image to estimate of a measure of quality Q(I*) for said query image e;

adjusting said initial threshold level by said measure of quality, said adjusted threshold defining a possible match for said search;

for each current document in said repository;

for each current image in said document;

extracting said current image I^(k) from said current document;

hashing said extracted current image to obtain a hash value h(I^(k) for said extracted current image;

computing a distance between said hash value h(l*) of said query image and said hash value h(I^(k) of said extracted current image;

comparing said computed distance against said adjusted threshold; and

flagging said current document as a possible match in response to said computed distance being less than said adjusted threshold; and

providing any of said flagged documents to a user in response to said search.

2. The method of claim 1, further comprising:

performing a text-based query on said repository of documents; and

extracting images only from documents matching said text-based query.

3. The method of claim 1, wherein said measure of quality is mapped to a measure of distortion D such that:

0≦

D≦

D_max.

4. The method of claim 3, further comprising producing a tolerance level τ

for said search by adjusting said initial threshold level by said measure of distortion D such that;

τ

=τ

₀+ƒ

(D),

where ƒ

(D) is a non-negative and monotonically increasing function of said measure of distortion D.

5. The method of claim 1, further comprising:

determining a delta value for said flagged document, said delta value being a difference between said computed distance and said adjusted threshold; and

sorting said flagged documents by an order of said delta values.

6. The method of claim 1, further comprising:

setting a termination threshold level with which to define a best match for said search, said termination threshold level being less than said adjusted threshold;

flagging said current document as a best match in response to said computed distance being less than said termination threshold level; and

terminating said search in response to said flagging.

7. The method of claim 1, further comprising modifying, based on a visual examination of said query image by said user, any of said initial threshold level and said adjusted threshold.

8. A computer system for searching a repository of documents using an image as a search query, the system comprising:

a display device and a user interface for entering an input;

a memory for storing machine executable instructions;

a storage device containing a repository of searchable document, at least a portion of said documents contain extractable images; and

a processor in communication with said display and user interface, said memory and said storage device, said processor executing said machine readable instructions for performing;

receiving a query image I* to be used to search a repository of documents;

hashing said query image to obtain a hash value h(I*) for said query image;

setting an initial threshold level τ

₀ for said search;

performing a no-reference quality assessment on said query image to estimate of a measure of quality Q(I*) for said query image;

adjusting said initial threshold level by said measure of quality, said adjusted threshold defining a possible match for said search;

for each current document in said repository;

for each current image in said document;

extracting said current image I^(k) from said current document;

hashing said extracted current image to obtain a hash value h(I^(k) for said extracted current image;

computing a distance between said hash value h(I*) of said query image and said hash value h(I^(k) of said extracted current image;

comparing said computed distance against said adjusted threshold; and

flagging said current document as a possible match in response to said computed distance being less than said adjusted threshold; and

providing any of said flagged documents to a user in response to said search.

9. The computer system of claim 8, further comprising:

performing a text-based query on said repository of documents; and

extracting images only from documents matching said text-based query.

10. The computer system of claim 8, wherein said measure of quality Q is mapped to a measure of distortion D such that:

0≦

D≦

D_max.

11. The computer system of claim 10, further comprising producing a tolerance level τ

for said search by adjusting said initial threshold level by said measure of distortion D such that;

τ

=τ

₀+ƒ

(D),

where τ

₀ is said initial threshold level, and ƒ

(D) is a non-negative and monotonically increasing function of said measure of distortion D.

12. The computer system of claim 8, further comprising:

determining a delta value for said flagged document, said delta value being a difference between said computed distance and said adjusted threshold; and

sorting said flagged documents by an order of said delta values.

13. The computer system of claim 8, further comprising:

setting a termination threshold level with which to define a best match for said search, said termination threshold level being less than said adjusted threshold;

flagging said current document as a best match in response to said computed distance being less than said termination threshold level; and

terminating said search in response to said flagging.

14. The computer system of claim 8, further comprising modifying, based on a visual examination of said query image by said user, any of said initial threshold level and said adjusted threshold.

15. A computer program product for decoding data embedded in a color barcode, the computer program product comprising:

a computer-usable data carrier storing instructions that, when executed on a computer, cause the computer to perform a method comprising;

receiving a query image I* to be used to search a repository of documents;

hashing said query image to obtain a hash value h(I*) for said query image;

setting an initial threshold level τ

₀ for said search;

performing a no-reference quality assessment on said query image to estimate of a measure of quality Q(I*) for said query image;

adjusting said initial threshold level by said measure of quality, said adjusted threshold defining a possible match for said search;

for each current document in said repository;

for each current image in said document;

extracting said current image I^(k) from said current document;

hashing said extracted current image to obtain a hash value h(I^(k) for said extracted current image;

computing a distance between said hash value h(I*) of said query image and said hash value h(I^(k) of said extracted current image;

comparing said computed distance against said adjusted threshold; and

flagging said current document as a possible match in response to said computed distance being less than said adjusted threshold; and

providing any of said flagged documents to a user in response to said search.

16. The computer program product of claim 15, further comprising:

performing a text-based query on said repository of documents; and

extracting images only from documents matching said text-based query.

17. The computer program product of claim 15, wherein said measure of quality Q is mapped to a measure of distortion D such that:

0≦

D≦

D_max.

18. The computer program product of claim 17, further comprising producing a tolerance level τ

for said search by adjusting said initial threshold level by said measure of distortion D such that;

τ

=τ

₀+ƒ

(D),

where τ

₀ is said initial threshold level, and ƒ

(D) is a non-negative and monotonically increasing function of said measure of distortion D.

19. The computer program product of claim 15, further comprising:

determining a delta value for said flagged document, said delta value being a difference between said computed distance and said adjusted threshold; and

sorting said flagged documents by an order of said delta values.

20. The computer program product of claim 15, further comprising:

setting a termination threshold level with which to define a best match for said search, said termination threshold level being less than said adjusted threshold;

flagging said current document as a best match in response to said computed distance being less than said termination threshold level; and

terminating said search in response to said flagging.