Image retrieval apparatus and method

• US 6,400,853 B1
• Filed: 03/17/1998
• Issued: 06/04/2002
• Est. Priority Date: 03/19/1997
• Status: Expired due to Term

• Current Assignee: Canon Ayutthaya Limited (Canon Inc.)
• Original Assignee: Canon Ayutthaya Limited (Canon Inc.)
• Inventors: Shiiyama, Hirotaka
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Sherali, Ishrat
• Application Number:
  US09/042,692
• Time in Patent Office: 1,540 Days
• Field of Search: 382/305-306, 382/209, 382/173-180, 382/215, 382/218, 382/195, 382/164, 382/190, 707/1-6, 707/500, 707/104.1, 358/403-404
• US Class Current: 382/305
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

An image feature amount extraction unit segments an image into a plurality of blocks and calculates the feature amount of each block. A feature amount label string generation unit adds a label to each block in accordance with the feature amount acquired for the block and arranges the labels on the basis of a predetermined block sequence to generate a label string. In retrieval, the similarity between the label string of a specified image and that of an image to be compared is calculated, and an image whose similarity exceeds a predetermined value is output as a retrieval result. In this way, similar image retrieval can be performed in consideration of the arrangement of feature amounts of images, and simultaneously, similar image retrieval can be performed while absorbing any difference due to a variation in photographing condition or the like.

Claims

1. An image retrieval apparatus comprising:

a storage adapted to store a label string which represents a two dimensional label matrix in correspondence with an image;

a specifying unit, adapted to specify an image;

an acquiring unit, adapted to acquire the label matrix of the specified image from said storage; and

a retrieval unit adapted to perform image retrieval on the basis of the label matrix stored in said storage, said retrieval unit including;

a first matching unit adapted to compare a label string extracted from the label matrix of the specified image in units of rows with a label string extracted from the label matrix of an image to be compared in units of rows by dynamic programming matching to obtain a row array indicating to which row of the image to be compared each row of the specified image is similar; and

a second matching unit adapted to obtain, by dynamic programming matching, a similarity between a row array of the image to be compared and the row array obtained by said first matching unit.

2. The apparatus according to claim 1, wherein

the label string extracted in units of rows has an array in the horizontal direction of the image.

3. The apparatus according to claim 1,

wherein the label string extracted in units of rows has an array in the vertical direction of the image.

4. The apparatus according to claim 1, further comprising an output unit adapted to output, as a retrieval result, an image whose similarity obtained by said second matching unit exceeds a predetermined value.

5. The apparatus according to claim 1, wherein said first matching unit has a table which holds a penalty value for a pair of labels, and refers to the table in calculating a distance between the label string of the retrieval specified image and the label string of the image to be compared using DP matching.

6. The apparatus according to claim 5, wherein

the label is unique to each cell obtained by segmenting a multidimensional feature amount space into a plurality of cells, and

the penalty value is set on the basis of a distance between cells represented by two labels.

7. The apparatus according to claim 1, wherein said second matching unit has a table which holds a penalty value for a pair of row numbers of the row array and refers to the table in calculating the similarity between the row array of the retrieval specified image and the row array of the image to be compared using DP matching.

8. The apparatus according to claim 1, further comprising

a holding unit adapted to determine a penalty value associated with a pair of rows on the basis of the similarity between label strings in a row direction of the retrieval specified image and holding the penalty value, and

wherein said second matching unit refers to the penalty value held by said holding unit in calculating the similarity between the row array of the retrieval specified image and the row array of the image to be compared using DP matching.

9. The apparatus according to claim 5, wherein said first matching unit applies a penalty and constraint according to system expansion/contraction in label comparison in calculating the similarity between the label string of the retrieval specified image and the label string stored in said storage.

10. The apparatus according to claim 9, wherein

the penalty and constraint according to system expansion/contraction in label comparison are acquired on the basis of a DP matching theory.

11. The apparatus according to claim 5, further comprising

a first table for registering an image ID group having label strings generated by said generation unit as keys, and

wherein said output unit acquires a label string whose similarity calculated by said retrieval unit exceeds a predetermined value, extracts an image corresponding to the acquired label string with reference to the first table, and outputs the image as a retrieval result.

12. The apparatus according to claim 11, wherein

the label matrix subjected to similarity calculation by said retrieval unit is a key in the first table.

13. The apparatus according to claim 11, wherein

the label matrix subjected to similarity calculation by said retrieval nit is one of label matrixes stored in said storage, which includes a predetermined number or more labels similar to those in the label matrix of the retrieval specified image.

14. The apparatus according to claim 13, further comprising

a second table for registering a label matrix group of label matrixes stored in said storage, which includes labels as keys, and

wherein a label matrix including a predetermined number or more labels similar to those included in the specified image is acquired with reference to the second table and subjected to similarity calculation by said arithmetic unit.

15. The apparatus according to claim 1, wherein said retrieval unit utilizes a DP-matching method,

and further comprising:

a setting unit adapted to set width of a matching window of the DP-matching performed by said retrieval, and

a controller adapted to control ambiguity of said retrieval unit by changing the width of the matching window based on the width set by said setting unit.

16. An image retrieval method, comprising:

a storage step, of storing, in a storage, a label string which represents a two dimensional label matrix, in correspondence with an image;

a specification step, of specifying an image;

an acquisition step, of acquiring the label matrix of the specified image from the storage; and

an image retrieval step, of performing image retrieval on the basis of the label matrix stored in the storage, the image retrieval including;

a first matching step, of comparing a label string extracted from the label matrix of the specified image in units of rows with a label string extracted from the label matrix of an image to be compared in units of rows by dynamic programming matching to obtain a row array indicating to which row of the image to be compared each row of the specified image is similar; and

a second matching step, of obtaining, by dynamic programming matching, a similarity between a row array of the image to be compared and the row array obtained in said first matching step.

17. The method according to claim 16, wherein the label string extracted in units of rows has an array in the horizontal direction of the image.

18. The method according to claim 16, wherein

the label string extracted in units of rows has an array in the vertical direction of the image.

19. The method according to claim 16, further comprising an output step, of outputting, as a retrieval result, an image whose similarity obtained in said second matching step exceeds a predetermined value.

20. The method according to claim 16, wherein said first matching step uses a table which holds a penalty value for a pair of labels, and includes referring to the table in calculating a distance between the label string of the retrieval specified image and the label string of the image to be compared using DP matching.

21. The method according to claim 20, wherein

the label is unique to each cell obtained by segmenting a multidimensional feature amount space into a plurality of cells, and

the penalty value is set on the basis of a distance between cells represented by two labels.

22. The method according to claim 16, wherein the second matching step uses a table which holds a penalty value for a pair of row numbers of the row array and includes referring to the table in calculating the similarity between the row array of the retrieval specified image and the row array of the image to be compared using DP matching.

23. The method according to claim 16, further comprising

a holding step, of determining a penalty value associated with a pair of rows on the basis of the similarity between label strings in a row direction of the retrieval specified image and holding the penalty value, and

wherein said second matching step includes referring to the penalty value held in the holding step in calculating the similarity between the row array of the retrieval specified image and the row array of the image to be compared using DP matching.

24. The method according to claim 20, wherein

the first matching step includes applying a penalty and constraint according to system expansion/contraction in label comparison in calculating the similarity between the label string of the retrieval specified image and the label string stored in the storage step.

25. The method according to claim 24, wherein

the penalty and constraint according to system expansion/contraction in label comparison are acquired on the basis of a DP matching theory.

26. The method according to claim 20,

wherein a first table is used for registering an image ID group having label strings generated in the generation step as keys, and

wherein the output step includes acquiring a label string whose similarity calculated in the retrieval step exceeds a predetermined value, extracting an image corresponding to the acquired label string with reference to the first table, and outputting the image as a retrieval result.

27. The method according to claim 26, wherein

the label matrix subjected to similarity calculation in the retrieval step is a key in the first table.

28. The method according to claim 26, wherein

the label matrix subjected to similarity calculation in the retrieval step is one of label matrixes stored in the storage step, which includes a predetermined number or more labels similar to those in the label matrix of the retrieval specified image.

29. The method according to claim 28, further comprising

a second table for registering a label matrix group of label matrixes stored in the storage step, which includes labels as keys, and in that

wherein a label matrix including a predetermined number or more labels similar to those included in the specified image is acquired with reference to the second table and subjected to similarity calculation in the arithmetic step.

30. The method according to claim 16, wherein DP-matching method is utilized in said retrieval step,

and further comprising:

a setting step, of setting width of a matching window of the DP-matching performed in said retrieval step, and

a controlling step, of controlling ambiguity in said retrieval step by changing the width of the matching window based on the width set in said setting step.

31. A memory medium storing computer-executable instructions for performing an image retrieval method, comprising:

a storage step, of storing, in a storage, a label string which represents a two dimensional label matrix, in correspondence with an image;

a specification step, of specifying an image;

an acquisition step, of acquiring the label matrix of the specified image from the storage; and

an image retrieval step, of performing image retrieval on the basis of the label matrix stored in the storage, the image retrieval including;

a first matching step, of comparing a label string extracted from the label matrix of the specified image in units of rows with a label string extracted from the label matrix of an image to be compared in units of rows by dynamic programming matching to obtain a row array indicating to which row of the image to be compared each row of the specified image is similar; and

a second matching step, of obtaining, by dynamic programming matching, a similarity between a row array of the image to be compared and the row array obtained in said first matching step.