Document and/or Image Retrieval Method, Program Therefor, Document and/or Image Storage Apparatus, and Retrieval Apparatus

• US 20080177764A1
• Filed: 02/15/2006
• Published: 07/24/2008
• Est. Priority Date: 03/01/2005
• Status: Active Grant

• Current Assignee: Osaka Prefcture University
• Original Assignee: Osaka Prefcture University
• Inventors: Iwamura, Masakazu, Kise, Koichi, Nakai, Tomohiro
• Granted Patent: US 8,036,497 B2
• Time in Patent Office: Days
• US Class Current: 707/100
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06V 30/40 Document-oriented image-based pattern recognition
• CPC Class Codes: G06V 30/418 Document matching, e.g. of document images

Abstract

A document/image retrieval method for retrieving a document/image corresponding to a captured digital image from a database by comparing features calculated based on feature points of the captured digital image with features preliminarily calculated based on feature points of each of documents and/or images stored in the database, the method comprising: extracting the feature points from the captured digital image; defining a local set of feature points for each of the extracted feature points; selecting feature points from the defined local set to define a feature point subset of the local set; determining invariant values as values characterizing the defined subset for combinations of the feature points in the subset, the invariant values being invariant to a geometric transformation; calculating a feature by combining the determined invariant values; and performing a voting process on the documents and/or images in the database based on the preliminarily calculated features of the documents and/or images; whereby the document/image corresponding to the captured digital image is retrieved from the database.

Claims

1-22. -22. (canceled)

23. A document and/or image retrieval method for retrieving a document and/or image corresponding to a captured digital image from a database by comparing features calculated based on feature points of the captured digital image with features calculated based on feature points of each of documents and/or images stored in the database, the method comprising:

extracting the feature points from the captured digital image;

defining a local set of feature points for each of the extracted feature points;

selecting subsets of feature points from the defined local set;

determining invariant values as values characterizing each selected subset for combinations of the feature points in the subset, the invariant values being invariant to a geometric transformation;

calculating a feature by combining the determined invariant values; and

performing a voting process on the documents and/or images in the database based on the preliminarily calculated features of the documents and/or images;

so that the document and/or image corresponding to the captured digital image is retrieved from the database.

24. A document and/or image retrieval method according to claim 23, wherein the invariant values are cross-ratios.

25. A document and/or image retrieval method according to claim 23, wherein the invariant values are invariant to an affine transformation.

26. A document and/or image retrieval method according to claim 23, wherein the invariant values are invariant to a similarity transformation.

27. A document and/or image storage method, which causes a computer to execute the steps of:

inputting a document and/or image;

assigning an ID to the input document and/or image;

extracting feature points defining an image arrangement from the input document and/or image; and

performing a predetermined process on each of the extracted feature points;

the predetermined process comprising the steps of;

(1) selecting n feature points which are nearest to a feature point p of interest; and

(2) performing a predetermined process on each of all possible sets of m feature points (m<

n) selected from the selected n feature points;

the predetermined process in the step (2) comprising the steps of;

(a) determining features for all possible sets of d points (wherein d is a number not greater than a predetermined number m) selected from an m-point set of interest;

(b) determining an index of a hash table based on the determined features through a predetermined computation; and

(c) storing the features in relation to a point ID and a document ID in the hash table, the features being determined in the step (a) using the determined hash index, the point ID being assigned to the feature point p and the document ID being assigned to the document and/or image from which the feature point p is extracted.

28. A document and/or image retrieval method for retrieving a document and/or image stored by a storage method as recited in claim 27, the retrieval method causing a computer to execute the steps of:

reading a captured image;

extracting feature points defining an image arrangement from the read image;

performing a predetermined process on each of the extracted feature points;

the predetermined process comprising the steps of;

(1) selecting n feature points which are nearest to a feature point p of interest; and

(2) performing a predetermined process on each of all possible sets of m feature points (m<

n) selected from the selected n feature points;

the predetermined process in the step (2) comprising the steps of;

(a) determining features for all possible sets of d points (wherein d is a number not greater than a predetermined number m) selected from an m-point set of interest;

(b) determining an index of a hash table based on the determined features through a predetermined computation; and

(c) acquiring features of a preliminarily input document and/or image from the hash table based on the determined hash index, comparing the features determined in the step (a) with the acquired features, and voting for a document ID having matching features; and

after the steps (1) and (2), specifying a document ID of a document and/or image which matches the captured image based on a voting result.

29. A document and/or image storage program, which causes a computer to execute the steps of:

inputting a document and/or image;

assigning an ID to the input document and/or image;

extracting feature points defining an image arrangement from the input document and/or image; and

performing a predetermined process on each of the extracted feature points;

the predetermined process including the steps of;

(1) selecting n feature points which are nearest to a feature point p of interest; and

(2) performing a predetermined process on each of all possible sets of m feature points (m<

n) selected from the selected n feature points;

the predetermined process in the step (2) including the steps of;

(a) determining features for all possible sets of d points (wherein d is a number not greater than a predetermined number m) selected from an m-point set of interest;

(b) determining an index of a hash table based on the determined features through a predetermined computation; and

(c) storing the features in relation to a point ID and a document ID in the hash table, the features being determined in the step (a) using the determined hash index, the point ID being assigned to the feature point p and the document ID being assigned to the document and/or image from which the feature point p is extracted.

30. A document and/or image retrieval program for retrieving a document and/or image input employing a storage program as recited in claim 29, the retrieval program causing a computer to execute the steps of:

reading a captured image;

extracting feature points defining an image arrangement from the read image;

performing a predetermined process on each of the extracted feature points;

the predetermined process including the steps of;

(1) selecting n feature points which are nearest to a feature point p of interest; and

(2) performing a predetermined process on each of all possible sets of m feature points (m<

n) selected from the selected n feature points;

the predetermined process in the step (2) including the steps of;

(a) determining features for all possible sets of d points (wherein d is a number not greater than a predetermined number m) selected from an m-point set;

(b) determining an index of a hash table based on the determined features through a predetermined computation; and

(c) acquiring features of a preliminarily input document and/or image from the hash table based on the determined hash index, comparing the features determined in the step (a) with the acquired features, and voting for a document ID having matching features; and

after the steps (1) and (2), specifying a document ID of a document/image which matches the captured image based on a voting result.

31. A document and/or image storage apparatus comprising:

an input section which inputs a document and/or image;

a feature point extracting section which extracts feature points defining an image arrangement from the input document and/or image;

a feature point selecting section which selects n feature points nearest to an extracted feature point p of interest; and

a feature storing section which performs a predetermined process on each of all possible sets of m feature points (m<

n) selected from the selected n feature points;

the predetermined process including the steps of;

(a) determining features for all possible sets of d points (wherein d is a number not greater than a predetermined number m) selected from an m-point set of interest;

(b) determining an index of a hash table based on the determined features through a predetermined computation; and

(c) storing the features in relation to a point ID and a document ID in the hash table, the features being determined in the step (a) using the determined hash index, the point ID being assigned to the feature point p and the document ID being assigned to the document and/or image from which the feature point p is extracted.

32. A document and/or image storage apparatus, which stores a document and/or image stored by a storage apparatus as recited in claim 31.

33. A document and/or image retrieval apparatus for retrieving a document and/or image stored in a document and/or image storage apparatus as recited in claim 32, the retrieval apparatus comprising:

a reading section which reads a captured image;

a feature point extracting section which extracts feature points defining an image arrangement from the read image;

a feature point selecting section which selects n feature points nearest to an extracted feature point p of interest; and

a voting section which performs a predetermined process on each of all possible sets of m feature points (m<

n) selected from the selected n feature points;

the predetermined process including the steps of;

(a) determining features for all possible sets of d points (wherein d is a number not greater than a predetermined number m) selected from an m-point set of interest;

(b) determining an index of a hash table based on the determined features through a predetermined computation; and

(c) acquiring features of a preliminarily input document and/or image from the hash table based on the determined hash index, comparing the features determined in the step (a) with the acquired features, and voting for a document ID having matching features; and

a document ID specifying section which specifies a document ID of a document/image which matches the captured image based on a voting result determined by votes corresponding to the respective feature points.