Image search apparatus and method

• US 6,584,223 B1
• Filed: 03/31/1999
• Issued: 06/24/2003
• Est. Priority Date: 04/02/1998
• 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): Tran, Phuoc
• Assistant Examiner(s): Alavi, Amir
• Application Number:
  US09/281,783
• Time in Patent Office: 1,546 Days
• Field of Search: 382/164, 382/173, 382/180, 382/190, 382/192, 382/195, 382/203, 382/205, 382/209, 382/215, 382/218, 382/219, 382/305, 382/227, 382/306, 358/403, 707/3, 707/6
• US Class Current: 382/173
• CPC Class Codes: G06F 16/5838 using colour

Abstract

An image feature amount extraction unit and feature amount label matrix generation unit generate a label sequence from image data. An image management DB stores image data stored in an image storage unit and label sequences corresponding to the image data in correspondence with each other. A label sequence index registers, in units of labels, image data including the labels and the numbers of labels included in those image data. Upon search, a pattern matching unit extracts label sequences which are similar to the label sequence of a query image to some extent from the label sequence index, computes similarities between the extracted label sequences, and the label sequence of the query image, and outputs images, in which the computed similarities exceed a predetermined value, as search results.

Claims

1. An image search apparatus comprising:

generation means for generating label information by segmenting image data into a plurality of blocks, and assigning labels in correspondence with feature amounts acquired in units of blocks;

index means for readably holding, using each label included in the label information as a key, image data including that label and the number of labels included in the image data;

storage means for storing the label information in correspondence with the image data;

first extraction means for extracting image data having label information including at least a predetermined number of labels identical to or similar to labels included in label information of a query image, with reference to said index means and said storage means; and

second extraction means for extracting similar image data by computing similarities between the image data extracted by said first extraction means, and the query image,

wherein said generation means comprises assigning means for segmenting image data into a plurality of blocks, and assigning labels in correspondence with feature amounts acquired in units of labels, and generates a label sequence by arranging the labels assigned by said assigning means in a predetermined block order.

2. The apparatus according to claim 1, wherein the label information stored in said storage means is label sequence generated by said generation means, and

said second extraction means extracts similar image data by computing similarities between label sequences stored in said storage means of the image data extracted by said first extraction means, and a label sequence of the query image.

3. The apparatus according to claim 1, wherein image data registered in units of labels of said index means are sorted and registered on the basis of the numbers of labels included in those images.

4. The apparatus according to claim 1, wherein said index means registers image IDs which specify image data including a label of interest in units of labels.

5. The apparatus according to claim 1, wherein the labels are unique labels assigned to cells obtained by segmenting a multi-dimensional feature amount space into a plurality of cells, and

said assigning means computes a feature amount of each of the plurality of blocks, and assigns a label, assigned to the cell to which the computed feature amount belongs, to that block.

6. The apparatus according to claim 5, wherein the plurality of blocks are obtained by segmenting an image into a plurality of blocks in the vertical and horizontal directions, and the block order used in said generation means is an order for scanning the plurality of blocks obliquely.

7. The apparatus according to claim 5, wherein the plurality of blocks are obtained by segmenting an image into a plurality of blocks in the vertical and horizontal directions, and the block order used in said generation means is an order for scanning the plurality of blocks in the horizontal or vertical direction.

8. The apparatus according to claim 1, wherein said second extraction means comprises:

computation means for computing similarities between a label sequence of the query image and label sequences of image data extracted by said first extraction means; and

output means for outputting image data, in which similarities computed by said computation means exceed a predetermined value, as search results.

9. The apparatus according to claim 8, wherein said computation means has a penalty table for holding penalty values in correspondence with pairs of label values, and computes the similarities between the label sequence of the query image data and the label sequences of the extracted image data on the basis of the penalty table.

10. The apparatus according to claim 9, wherein the labels are unique labels assigned to cells obtained by segmenting a multi-dimensional feature amount space into a plurality of cells, and

each of the penalty values is set on the basis of a distance between the cells expressed by two labels.

11. The apparatus according to claim 9, wherein said computation means assigns a penalty value corresponding to overs/shorts of labels upon computing the similarity between a label sequence of a query image and an image to be compared.

12. The apparatus according to claim 11, wherein the penalty value corresponding to overs/shorts of the labels is acquired on the basis of a theory of automaton.

13. The apparatus according to claim 9, wherein said computation means computes the similarities by executing DP matching using the penalty values.

14. The apparatus according to claim 13, further comprising setting means for setting a width of a matching window of DP matching used in said computation means.

15. The apparatus according to claim 1, wherein the label sequence represents a two-dimensional label matrix that reflects positions of the plurality of blocks, and said second extraction means comprises:

first matching means for obtaining row sequences of image data extracted by said first extraction means by pairing label sequences in units of rows obtained from a label matrix of the query image data with label sequences in units of rows obtained from each of label matrices of the extracted image data by DP matching; and

second matching means for obtaining similarities between a row sequence of the label sequence of the query image data and the row sequences obtained by said first matching means by DP matching.

16. The apparatus according to claim 15, wherein the label sequences in units of rows are sequences corresponding to a horizontal direction of an image.

17. The apparatus according to claim 15, wherein the label sequences in units of rows are sequences corresponding to a vertical direction of an image.

18. The apparatus according to claim 15, further comprising output means for outputting images, similarities obtained by said second matching means of which exceed a predetermined value, as search results.

19. The apparatus according to claim 15, wherein said first matching means has a penalty table for holding penalty values in correspondence with pairs of labels, and computes distances between the label sequence of the query image and the label sequences of the extracted images using DP matching with reference to the penalty table.

20. The apparatus according to claim 15, wherein said second matching means has an inter-row penalty table for holding penalty values in correspondence with pairs of row numbers in the row sequence, and computes similarities between the row sequence of the query image data and row sequences of the extracted image data using DP matching with reference to the inter-row penalty table.

21. The apparatus according to claim 20, further comprising holding means for determining penalty values that pertain to pairs of rows on the basis of similarities of label sequences of individual rows of the query image data, and holding the penalty values as the inter-row penalty table.

22. The apparatus according to claim 15, wherein said first matching means gives a penalty and constraint corresponding to elasticity of a label sequence to be compared upon computing similarities between the label sequence of the query image data and label sequences stored in said storage means.

23. The apparatus according to claim 22, wherein the penalty and constraint corresponding to elasticity of the label sequence to be compared are acquired on the basis of a theory of DP matching.

24. The apparatus according to claim 15, further comprising first setting means for setting a width of a matching window of DP matching used in said first matching means.

25. The apparatus according to claim 15, further comprising second setting means for setting a width of a matching window of DP matching used in said second matching means.

26. The apparatus according to claim 1, wherein said storage means stores label histogram information representing a histogram of labels assigned to the respective blocks of the image data by said generation means.

27. The apparatus according to claim 26, wherein said second extraction means makes a similar image search on the basis of an inner product of the label histogram information between images extracted by said first extraction means, and the query image.

28. The apparatus according to claim 26, further comprising setting means for setting as a search condition, a label to be retrieved and a content range thereof on the basis of the label histogram information of the query image, and

wherein said first extraction means extracts images with reference to said index means under the search condition set by said setting means.

29. The apparatus according to claim 28, wherein said setting means sets only a label included in the query image as the label to be retrieved.

30. The apparatus according to claim 28, wherein said setting means sets as the label to be retrieved a label included in the query image, and a similar label, in which a penalty value with respect to that label is not more than a predetermined value.

31. The apparatus according to claim 30, wherein said first extraction means extracts images which include at least one of the labels to be retrieved set by said setting means within the content range.

32. The apparatus according to claim 30, wherein the penalty value is set in correspondence with a desirably set ambiguity level.

33. The apparatus according to claim 28, wherein said setting means sets as the content range a range defined by values respectively obtained by multiplying the number of labels to be retrieved included in the query image by first and second predetermined values.

34. The apparatus according to claim 28, further comprising control means for, when said first extraction means extracts images, the number of which exceeds a predetermined upper limit value, controlling said setting means and said first extraction means to repeat operations using another label in the query image.

35. The apparatus according to claim 34, wherein said control means selects a label to be used in turn from higher-rank labels in the label histogram information of the similarity search image.

36. An image search method comprising:

the generation step of generating label information by segmenting image data into a plurality of blocks, and assigning labels in correspondence with feature amounts acquired in units of blocks;

the step of providing index means for readably holding, using each label included in the label information as a key, image data including that label and the number of labels included in the image data;

the storage step of storing the label information in storage means in correspondence with the image data;

the first extraction step of extracting image data having label information including at least a predetermined number of labels identical to or similar to labels included in label information of a query image, with reference to the index means and the storage means; and

the second extraction step of extracting similar image data by computing similarities between the image data extracted in the first extraction step, and the query image,

wherein the generation step comprises the assigning step of segmenting image data into a plurality of blocks, and assigning labels in correspondence with feature amounts acquired in units of labels, and includes the step of generating a label sequence by arranging the labels assigned in the assigning step in a predetermined block order.

37. The method according to claim 36, wherein the label information stored in said storage means is a label sequence generated in the generation step, and

the second extraction step includes the step of extracting similar image data by computing similarities between label sequences stored in said storage means of the image data extracted in the first extraction step, and a label sequence of the query image.

38. The method according to claim 36, wherein image data registered in units of labels of said index means are sorted and registered on the basis of the numbers of labels included in those images.

39. The method according to claim 36, wherein said index means registers image IDs which specify image data including a label of interest in units of labels.

40. The method according to claim 36, wherein the labels are unique labels assigned to cells obtained by segmenting a multi-dimensional feature amount space into a plurality of cells, and

the assigning step includes the step of computing a feature amount of each of the plurality of blocks, and assigning a label, assigned to the cell to which the computed feature amount belongs, to that block.

41. The method according to claim 40, wherein the plurality of blocks are obtained by segmenting an image into a plurality of blocks in the vertical and horizontal directions, and the block order used in the generation step is an order for scanning the plurality of blocks obliquely.

42. The method according to claim 40, wherein the plurality of blocks are obtained by segmenting an image into a plurality of blocks in the vertical and horizontal directions, and the block order used in the generation step is an order for scanning the plurality of blocks in the horizontal or vertical direction.

43. The method according to claim 36, wherein the second extraction step comprises:

the computation step of computing similarities between a label sequence of the query image and label sequences of image data extracted in the first extraction step; and

the output step of outputting image data, in which similarities computed in the computation step exceed a predetermined value, as search results.

44. The method according to claim 43, wherein the computation step has a penalty table for holding penalty values in correspondence with pairs of label values, and includes the step of computing the similarities between the label sequence of the query image data and the label sequences of the extracted image data on the basis of the penalty table.

45. The method according to claim 44, wherein the labels are unique labels assigned to cells obtained by segmenting a multi-dimensional feature amount space into a plurality of cells, and

each of the penalty values is set on the basis of a distance between the cells expressed by two labels.

46. The method according to claim 44, wherein the computation step includes the step of assigning a penalty value corresponding to overs/shorts of labels upon computing the similarity between a label sequence of a query image and an image to be compared.

47. The method according to claim 46, wherein the penalty value corresponding to overs/shorts of the labels is acquired on the basis of a theory of automaton.

48. The method according to claim 44, wherein the computation step includes the step of computing the similarities by executing DP matching using the penalty values.

49. The method according to claim 48, further comprising the setting step of setting a width of a matching window of DP matching used in the computation step.

50. The method according to claim 36, wherein the label sequence represents a two-dimensional label matrix that reflects positions of the plurality of blocks, and

the second extraction step comprises:

the first matching step of obtaining row sequences of image data extracted in the first extraction step by pairing label sequences in units of rows obtained from a label matrix of the query image data with label sequences in units of rows obtained from each of label matrices of the extracted image data by DP matching; and

the second matching step of obtaining similarities between a row sequence of the label sequence of the query image data and the row sequences obtained in the first matching step by DP matching.

51. The method according to claim 50, wherein the label sequences in units of rows are sequences corresponding to a horizontal direction of an image.

52. The method according to claim 50, wherein the label sequences in units of rows are sequences corresponding to a vertical direction of an image.

53. The method according to claim 50, further comprising the output step of outputting images, similarities obtained by said second matching means of which exceed a predetermined value, as search results.

54. The method according to claim 50, wherein the first matching step has a penalty table for holding penalty values in correspondence with pairs of labels, and includes the step of computing distances between the label sequence of the query image and the label sequences of the extracted images using DP matching with reference to the penalty table.

55. The method according to claim 50, wherein the second matching step has an inter-row penalty table for holding penalty values in correspondence with pairs of row numbers in the row sequence, and includes the step of computing similarities between the row sequence of the query image data and row sequences of the extracted image data using DP matching with reference to the inter-row penalty table.

56. The method according to claim 55, further comprising the holding step of determining penalty values that pertain to pairs of rows on the basis of similarities of label sequences of respective rows of the query image data, and holding the penalty values as the inter-row penalty table.

57. The method according to claim 50, wherein the first matching step includes the step of giving a penalty and constraint corresponding to elasticity of a label sequence to be compared upon computing similarities between the label sequence of the query image data and label sequences stored in said storage means.

58. The method according to claim 57, wherein the penalty and constraint corresponding to elasticity of the label sequence to be compared are acquired on the basis of a theory of DP matching.

59. The method according to claim 50, further comprising the first setting step of setting a width of a matching window of DP matching used in the first matching step.

60. The method according to claim 50, further comprising the second setting step of setting a width of a matching window of DP matching used in the second matching step.

61. The method according to claim 36, wherein said storage means stores label histogram information representing a histogram of labels assigned to the respective blocks of the image data in the generation step.

62. The method according to claim 61, wherein the second extraction step includes the step of making a similar image search on the basis of an inner product of the label histogram information between images extracted in the first extraction step, and the query image.

63. The method according to claim 61, further comprising the setting step of setting as a search condition, a label to be retrieved and a content range thereof on the basis of the label histogram information of the query image, and

wherein the first extraction step includes the step of extracting images with reference to said index means under the search condition set in the setting step.

64. The method according to claim 63, wherein the setting step includes the step of setting only a label included in the query image as the label to be retrieved.

65. The method according to claim 63, wherein the setting step includes the step of setting as the label to be retrieved a label included in the query image, and a similar label, in which a penalty value with respect to that label is not more than a predetermined value.

66. The method according to claim 65, wherein the first extraction step includes the step of extracting images which includes at least one of the labels to be retrieved set in the setting step within the content range.

67. The method according to claim 65, wherein the penalty value is set in correspondence with a desirably set ambiguity level.

68. The method according to claim 63, wherein the setting step includes the step of setting as the content range a range defined by values respectively obtained by multiplying the number of labels to be retrieved included in the query image by first and second predetermined values.

69. The method according to claim 63, further comprising the control step of controlling the setting step and the first extraction step to repeat operations using another label in the query image, when images, the number of which exceeds a predetermined upper limit value, are extracted in the first extraction step.

70. The method according to claim 69, wherein the control step includes the step of selecting a label to be used in turn from higher-rank labels in the label histogram information of the similarity search image.

71. A storage medium that stores a control program for making a computer implement an image search process, said control program comprising:

a program code of the generation step of generating label information by segmenting image data into a plurality of blocks, and assigning labels in correspondence with feature amounts acquired in units of blocks;

a program code of the step of providing index means for readably holding, using each label included in the label information as a key, image data including that label and the number of labels included in the image data;

a program code of the storage step of storing the label information in storage means in correspondence with the image data;

a program code of the first extraction step of extracting image data having label information including at least a predetermined number of labels identical to or similar to labels included in label information of a query image, with reference to the index means and the storage means; and

a program code of the second extraction step of extracting similar image data by computing similarities between the image data extracted in the first extraction step, and the query image,

wherein the generation step comprises the assigning step of segmenting image data into a plurality of blocks, and assigning labels in correspondence with feature amounts acquired in units of labels, and includes the step of generating a label sequence by arranging the labels assigned in the assigning step in a predetermined block order.

72. A control program for making a computer implement an image search process, said control program comprising:

a program code of a generation step of generating label information by segmenting image data into a plurality of blocks, and assigning labels in correspondence with feature amounts acquired in units of blocks;

a program code of a step of providing index means for readably holding, using each label included in the label information as a key, image data including that label and the number of labels included in the image data;

a program code of a storage step of storing the label information in storage means in correspondence with the image data;

a program code of a first extraction step of extracting image data having label information including at least a predetermined number of labels identical to or similar to labels included in label information of a query image, with reference to the index means and the storage means; and

a program code of a second extraction step of extracting similar image data by computing similarities between the image data extracted in the first extraction step, and the query image,

wherein the generation step comprises the assigning step of segmenting image data into a plurality of blocks, and assigning labels in correspondence with feature amounts acquired in units of labels, and includes the step of generating a label sequence by arranging the labels assigned in the assigning step in a predetermined block order.