Method and apparatus for indexing and retrieving images using visual keywords

• US 6,574,378 B1
• Filed: 07/08/1999
• Issued: 06/03/2003
• Est. Priority Date: 01/22/1999
• Status: Expired due to Fees

• Current Assignee: Kent Ridge Digital Labs
• Original Assignee: Kent Ridge Digital Labs
• Inventors: Lim, Joo Hwee
• Primary Examiner(s): COUSO, YON JUNG
• Application Number:
  US09/341,348
• Time in Patent Office: 1,426 Days
• Field of Search: 382/305, 382/306, 382/155, 382/156, 382/160, 382/224, 382/225, 382/226, 707/3, 707/102, 358/403
• US Class Current: 382/305
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]

Abstract

A method, an apparatus and a computer program product for indexing and retrieving image data using visual keywords (108) is disclosed. Visual keywords (108) are prototypical, visual tokens (104) and are extracted from samples of visual documents (100) in a visual-content domain via supervised and/or unsupervised learning processes. An image or a video-shot key frame is described and indexed by a signature (112) that registers the spatial distribution of the visual keywords (108) present in its visual content. Visual documents (100) are retrieved for a sample query (120) by comparing the similarities between the signature (112) of the query (120) and those of visual documents (100) in the database. The signatures (112) of visual documents (100) are generated based on spatial distributions of the visual keywords (108). Singular-value decomposition (114) is applied to the signatures (112) to obtain a coded description (116).

Claims

1. A method of indexing and retrieving a visual document using visual keywords, said method including the steps of:

providing a plurality of visual keywords derived using a learning technique from a plurality of visual tokens extracted across a predetermined number of visual elements;

each said visual token being a coherent unit of the visual document, and representing a visual content domain,

comparing a plurality of visual tokens of another visual document with said visual keywords, a comparison result being represented by a three-dimensional map of detected locations of said visual keywords; and

determining a spatial distribution of visual keywords dependent upon said comparison result to provide a visual-content signature for said visual document.

2. The method according to claim 1, further including the step of comparing two visual documents by matching said visual-content signatures of said visual documents.

3. The method according to claim 2, wherein said comparing step involves use of one or more predetermined similarity measures.

4. The method according to claim 1, wherein said visual content signature is a spatial aggregation map.

5. The method according to claim 1, further including the step of coding said visual-content signature to reduce the dimensionality of said visual-content signature to provide a coded description of said visual document.

6. The method according to claim 5, further including the step of comparing two visual documents by matching said coded descriptions.

7. The method according to claim 1, further including the step of extracting a plurality of visual tokens from the content of one or more visual documents, each visual token being represented by one or more predefined visual characteristics.

8. The method according to claim 7, wherein said extracting step is dependent upon predefined receptive fields and displacements.

9. The method according to claim 8, wherein said predefined receptive fields have a predetermined size.

10. The method according to claim 8, wherein said displacements have predetermined sizes.

11. The method according to claim 8, wherein two or more of said predefined receptive fields have different sizes.

12. The method according to claim 7, further including the step of generating said visual keywords using said learning technique from said visual tokens extracted across said predetermined number of said visual documents.

13. The method according to claim 12, wherein said learning technique is a supervised and/or unsupervised learning technique.

14. The method according to claim 1, further including the step of representing the outcome of said visual-token comparing step by a vector of real values, each corresponding to a visual keyword, to provide said three-dimensional map of said detected locations of said visual keywords.

15. The method according to claim 14, wherein said three-dimensional map is a type evaluation map.

16. The method according to claim 1, wherein said extracting step utilises a plurality of predefined receptive fields and displacements in horizontal and vertical directions to tessellate the two-dimensional visual content of said visual documents.

17. The method according to claim 16, wherein said extracting step includes the step of transforming a visual token, being the part of said visual content covered by a receptive field, into a vector of real values representing one or more visual characteristics of said visual token.

18. The method according to claim 12, wherein said generating step utilises a plurality of view-based recognisers and a supervised learning technique to train said view-based recognisers from positive and negative visual tokens of a view of an object, said trained view-based recognisers being said visual keywords.

19. The method according to claim 12, wherein said generating step utilises a plurality of cluster-based parameters and an unsupervised learning technique to modify said cluster-based parameters using a collection of said visual tokens, said trained cluster-based parameters being said visual keywords.

20. The method according to claim 12, wherein said comparing step further includes the step of estimating a confidence factor or set membership of said visual token to each of said visual keywords.

21. The method according to claim 20, wherein said comparing step further includes the step of iteratively computing said confidence factor or set membership for each of said visual tokens in a given visual content, resulting in said three-dimensional map of detected locations of said visual keywords.

22. The method according to claim 20, wherein said determining step includes the step of summarising said confidence factors or set memberships of said three-dimensional map of detected locations to provide a three-dimensional map regarding occurrences of said visual keywords.

23. The method according to claim 5, wherein said coding step utilises a singular-value decomposition transform to represent a matrix X formed by concatenating linearised visual content signatures of visual documents as column vectors such that X=USV^T of rank r and obtains an approximate representation X_k=U_kS_kV_k^T of rank k, where k≦

r.

24. The method according to claim 23, further including the step of transforming a visual content signature of a visual document D to generate a coded description D′

as D′

=D^TU_kS_k<sup>−

1</sup>.

25. The method according to claim 3, wherein a plurality of similarity matching functions are used, each for comparing the similarity between the visual-content signatures of two visual documents.

26. The method according to claim 25, further including the step of determining which similarity measure, among those produced by said plurality of similarity matching functions on pairs of said visual content signatures of said two visual documents, to use as a final similarity measure between said two visual documents.

27. An apparatus for indexing and retrieving a visual document using visual keywords, said apparatus including:

means for providing a plurality of visual keywords derived using a learning technique from a plurality of visual tokens extracted across a predetermined number of visual documents;

each said visual token being a coherent unit of the visual document, and representing a visual content domain,

means for comparing a plurality of visual tokens of another visual document with said visual keywords, a comparison result being represented by a three-dimensional map of detected locations of said visual keywords; and

means for determining a spatial distribution of visual keywords dependent upon said comparison result to provide a visual-content signature for said visual document.

28. The apparatus according to claim 27, further including means for comparing two visual documents by matching said visual-content signatures of said visual documents.

29. The apparatus according to claim 28, wherein said comparing means uses one or more predetermined similarity measures.

30. The apparatus according to claim 27, wherein said visual content signature is a spatial aggregation map.

31. The apparatus according to claim 27, further including means for coding said visual-content signature to reduce the dimensionality of said visual-content signature to provide a coded description of said visual document.

32. The apparatus according to claim 31, further including means for comparing two visual documents by matching said coded descriptions.

33. The apparatus according to claims 27, further including means for extracting a plurality of visual tokens from the content of one or more visual documents, each visual token being represented by one or more predefined visual characteristics.

34. The apparatus according to claim 33, wherein said extracting means is dependent upon predefined receptive fields and displacements.

35. The apparatus according to claim 34, wherein said predefined receptive fields have a predetermined size.

36. The apparatus according to claim 34, wherein said displacements have predetermined sizes.

37. The apparatus according to claim 34, wherein two or more of said predefined receptive fields have different sizes.

38. The apparatus according to claim 33, further including means for generating said visual keywords using said learning technique from said visual tokens extracted across said predetermined number of said visual documents.

39. The apparatus according to claim 38, wherein said learning technique is a supervised and/or unsupervised learning technique.

40. The apparatus according to claim 27, further including means for representing the output of said visual-token comparing means by a vector of real values, each corresponding to a visual keyword, to provide said three-dimensional map of said detected locations of said visual keywords.

41. The apparatus according to claim 40, wherein said three-dimensional map is a type evaluation map.

42. The apparatus according to claim 27, wherein said extracting means utilises a plurality of predefined receptive fields and displacements in horizontal and vertical directions to tessellate the two-dimensional visual content of said visual documents.

43. The apparatus according to claim 42, wherein said extracting means includes means for transforming a visual token, being the part of said visual content covered by a receptive field, into a vector of real values representing one or more visual characteristics of said visual token.

44. The apparatus according to claim 38, wherein said generating means utilises a plurality of view-based recognisers and a supervised learning technique to train said view-based recognisers from positive and negative visual tokens of a view of an object, said trained view-based recognisers being said visual keywords.

45. The apparatus according to claim 38, wherein said generating means utilises a plurality of cluster-based parameters and an unsupervised learning technique to modify said cluster-based parameters using a collection of said visual tokens, said trained cluster-based parameters being said visual keywords.

46. The apparatus according to claim 38, wherein said comparing means further includes means for estimating a confidence factor or set membership of said visual token to each of said visual keywords.

47. The apparatus according to claim 46, wherein said comparing means further includes means for iteratively computing said confidence factor or set membership for each of said visual tokens in a given visual content, resulting in said three-dimensional map of detected locations of said visual keywords.

48. The apparatus according to claim 46, wherein said determining means includes means for summarising said confidence factors or set memberships of said three-dimensional map of detected locations to provide a three-dimensional map regarding occurrences of said visual keywords.

49. The apparatus according to claim 31, wherein said coding means utilises a singular-value decomposition transform to represent a matrix X formed by concatenating linearised visual content signatures of visual documents as column vectors such that X=USV^T of rank r and obtains an approximate representation X_k=U_kS_kV_k^T of rank k, where k≦

r.

50. The apparatus according to claim 49, further means for transforming a visual content signature of a visual document D to generate a coded description D′

as D′

=D^TU_kS_k<sup>−

1</sup>.

51. The apparatus according to claim 29, wherein a plurality of similarity matching functions are used, each for comparing the similarity between the visual-content signatures of two visual documents.

52. The apparatus according to claim 51, further including means for determining which similarity measure, among those produced by said plurality of similarity matching functions on pairs of said visual content signatures of said two visual documents, to use as a final similarity measure between said two visual documents.

53. A computer program product having a computer readable medium having a computer program recorded thereon for indexing and retrieving a visual document using visual keywords, said computer program product including:

means for providing a plurality of visual keywords derived using a leaming technique from a plurality of visual tokens extracted across a predetermined number of visual documents;

each said visual token being a coherent unit of the visual document, and representing a visual content domain,

means for comparing a plurality of visual tokens of another visual document with said visual keywords, a comparison result being represented by three-dimensional map of detected locations of said visual keywords; and

means for determining a spatial distribution of visual keywords dependent upon said comparison result to provide a visual-content signature for said visual document.

54. The computer program product according to claim 53, further including means for comparing two visual documents by matching said visual-content signatures of said visual documents.

55. The computer program product according to claim 54, wherein said comparing means uses one or more predetermined similarity measures.

56. The computer program product according to claim 53, wherein said visual content signature is a spatial aggregation map.

57. The computer program product according to claim 53, further including means for coding said visual-content signature to reduce the dimensionality of said visual-content signature to provide a coded description of said visual document.

58. The computer program product according to claim 57, further including means for comparing two visual documents by matching said coded descriptions.

59. The computer program product according to claim 53, further including means for extracting a plurality of visual tokens from the content of one or more visual documents, each visual token being represented by one or more predefined visual characteristics.

60. The computer program product according to claim 59, wherein said extracting means is dependent upon predefined receptive fields and displacements.

61. The computer program product according to claim 60, wherein said predefined receptive fields have a predetermined size.

62. The computer program product according to claim 60, wherein said displacements have predetermined sizes.

63. The computer program product according to claim 60, wherein two or more of said predefined receptive fields have different sizes.

64. The computer program product according to claim 59, further including means for generating said visual keywords using said learning technique from said visual tokens extracted across said predetermined number of said visual documents.

65. The computer program product according to claim 64, wherein said learning technique is a supervised and/or unsupervised learning technique.

66. The computer program product according to claim 53, further including means for representing the output of said visual-token comparing means by a vector of real values, each corresponding to a visual keyword, to provide said three-dimensional map of said detected locations of said visual keywords.

67. The computer program product according to claim 66, wherein said three-dimensional map is a type evaluation map.

68. The computer program product according to claim 53, wherein said extracting means utilises a plurality of predefined receptive fields and displacements in horizontal and vertical directions to tessellate the two-dimensional visual content of said visual documents.

69. The computer program product according to claim 68, wherein said extracting means includes means for transforming a visual token, being the part of said visual content covered by a receptive field, into a vector of real values representing one or more visual characteristics of said visual token.

70. The computer program product according to claim 64, wherein said generating means utilises a plurality of view-based recognisers and a supervised learning technique to train said view-based recognisers from positive and negative visual tokens of a view of an object, said trained view-based recognisers being said visual keywords.

71. The computer program product according to claim 64, wherein said generating means utilises a plurality of cluster-based parameters and an unsupervised learning technique to modify said cluster-based parameters using a collection of said visual tokens, said trained cluster-based parameters being said visual keywords.

72. The computer program product according to claim 64, wherein said comparing means further includes means for estimating a confidence factor or set membership of said visual token to each of said visual keywords.

73. The computer program product according to claim 72, wherein said comparing means further includes means for iteratively computing said confidence factor or set membership for each of said visual tokens in a given visual content, resulting in said three-dimensional map of detected locations of said visual keywords.

74. The computer program product according to claim 72, wherein said determining means includes means for summarising said confidence factors or set memberships of said three-dimensional map of detected locations to provide a three-dimensional map regarding occurrences of said visual keywords.

75. The computer program product according to claim 57, wherein said coding means utilises a singular-value decomposition transform to represent a matrix X formed by concatenating linearised visual content signatures of visual documents as column vectors such that X=USV^T of rank r and obtains an approximate representation X_k=U_kS_kV_k^T of rank k, where k≦

r.

76. The computer program product according to claim 75, further means for transforming a visual content signature of a visual document D to generate a coded description D′

as D′

D^TU_kS_k<sup>−

1</sup>.

77. The computer program product according to claim 55, wherein a plurality of similarity matching functions are used, each for comparing the similarity between the visual-content signatures of two visual documents.

78. The computer program product according to claim 77, further including means for determining which similarity measure, among those produced by said plurality of similarity matching functions on pairs of said visual content signatures of said two visual documents, to use as a final similarity measure between said two visual documents.