US6574378B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for indexing and retrieving images using visual keywords
Assignee: National University of Singapore
•
Filing: 1999-01-22
•
Granted: 2003-06-03
•
Expires: 2019-01-22
Abstract
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).
Inventors
- 👤 Joo Hwee Lim
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 10:39
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/50; G06F16/58; G06F16/583; G06F16/5854; G06V; G06V10/00; G06V10/40; G06V10/46; G06V10/462
Claims Analysis
Total Claims: 81
Claim 1
Independent Claim
113 words
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.
Claim 2
Independent Claim
113 words
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.
Claim 3
Dependent Claim
25 words
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.
Claim 4
Dependent Claim
20 words
The method according to claim 2 , wherein said comparing step involves use of one or more predetermined similarity measures.
Claim 5
Dependent Claim
17 words
The method according to claim 1 , wherein said visual content signature is a spatial aggregation map.
Claim 6
Dependent Claim
33 words
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.
Claim 7
Dependent Claim
21 words
The method according to claim 5 , further including the step of comparing two visual documents by matching said coded descriptions.
Claim 8
Dependent Claim
39 words
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.
Claim 9
Dependent Claim
19 words
The method according to claim 7 , wherein said extracting step is dependent upon predefined receptive fields and displacements.
Claim 10
Dependent Claim
16 words
The method according to claim 8 , wherein said predefined receptive fields have a predetermined size.
Claim 11
Dependent Claim
13 words
The method according to claim 8 , wherein said displacements have predetermined sizes.
Claim 12
Dependent Claim
19 words
The method according to claim 8 , wherein two or more of said predefined receptive fields have different sizes.
Claim 13
Dependent Claim
33 words
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.
Claim 14
Dependent Claim
18 words
The method according to claim 12 , wherein said learning technique is a supervised and/or unsupervised learning technique.
Claim 15
Dependent Claim
45 words
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.
Claim 16
Dependent Claim
16 words
The method according to claim 14 , wherein said three-dimensional map is a type evaluation map.
Claim 17
Dependent Claim
35 words
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.
Claim 18
Dependent Claim
47 words
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.
Claim 19
Dependent Claim
47 words
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.
Claim 20
Dependent Claim
42 words
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.
Claim 21
Dependent Claim
33 words
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.
Claim 22
Dependent Claim
47 words
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.
Claim 23
Dependent Claim
40 words
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.
Claim 24
Dependent Claim
60 words
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 k S k V k T of rank k, where k≦r.
Claim 25
Dependent Claim
37 words
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 T U k S k −1 .
Claim 26
Dependent Claim
29 words
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.
Claim 27
Dependent Claim
50 words
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.
Claim 28
Independent Claim
116 words
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.
Claim 29
Independent Claim
116 words
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.
Claim 30
Dependent Claim
24 words
The apparatus according to claim 27 , further including means for comparing two visual documents by matching said visual-content signatures of said visual documents.
Claim 31
Dependent Claim
18 words
The apparatus according to claim 28 , wherein said comparing means uses one or more predetermined similarity measures.
Claim 32
Dependent Claim
17 words
The apparatus according to claim 27 , wherein said visual content signature is a spatial aggregation map.
Claim 33
Dependent Claim
32 words
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.
Claim 34
Dependent Claim
20 words
The apparatus according to claim 31 , further including means for comparing two visual documents by matching said coded descriptions.
Claim 35
Independent Claim
38 words
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.
Claim 36
Dependent Claim
19 words
The apparatus according to claim 33 , wherein said extracting means is dependent upon predefined receptive fields and displacements.
Claim 37
Dependent Claim
16 words
The apparatus according to claim 34 , wherein said predefined receptive fields have a predetermined size.
Claim 38
Dependent Claim
13 words
The apparatus according to claim 34 , wherein said displacements have predetermined sizes.
Claim 39
Dependent Claim
19 words
The apparatus according to claim 34 , wherein two or more of said predefined receptive fields have different sizes.
Claim 40
Dependent Claim
32 words
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.
Claim 41
Dependent Claim
18 words
The apparatus according to claim 38 , wherein said learning technique is a supervised and/or unsupervised learning technique.
Claim 42
Dependent Claim
44 words
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.
Claim 43
Dependent Claim
16 words
The apparatus according to claim 40 , wherein said three-dimensional map is a type evaluation map.
Claim 44
Dependent Claim
35 words
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.
Claim 45
Dependent Claim
46 words
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.
Claim 46
Dependent Claim
47 words
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.
Claim 47
Dependent Claim
42 words
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.
Claim 48
Dependent Claim
32 words
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.
Claim 49
Dependent Claim
46 words
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.
Claim 50
Dependent Claim
39 words
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.
Claim 51
Dependent Claim
60 words
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 k S k V k T of rank k, where k≦r.
Claim 52
Dependent Claim
35 words
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 T U k S k −1 .
Claim 53
Dependent Claim
29 words
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.
Claim 54
Dependent Claim
49 words
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.
Claim 55
Dependent Claim
130 words
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.
Claim 56
Dependent Claim
130 words
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.
Claim 57
Dependent Claim
26 words
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.
Claim 58
Dependent Claim
20 words
The computer program product according to claim 54 , wherein said comparing means uses one or more predetermined similarity measures.
Claim 59
Dependent Claim
19 words
The computer program product according to claim 53 , wherein said visual content signature is a spatial aggregation map.
Claim 60
Dependent Claim
34 words
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.
Claim 61
Dependent Claim
22 words
The computer program product according to claim 57 , further including means for comparing two visual documents by matching said coded descriptions.
Claim 62
Dependent Claim
40 words
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.
Claim 63
Dependent Claim
21 words
The computer program product according to claim 59 , wherein said extracting means is dependent upon predefined receptive fields and displacements.
Claim 64
Dependent Claim
18 words
The computer program product according to claim 60 , wherein said predefined receptive fields have a predetermined size.
Claim 65
Dependent Claim
15 words
The computer program product according to claim 60 , wherein said displacements have predetermined sizes.
Claim 66
Dependent Claim
21 words
The computer program product according to claim 60 , wherein two or more of said predefined receptive fields have different sizes.
Claim 67
Dependent Claim
34 words
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.
Claim 68
Dependent Claim
20 words
The computer program product according to claim 64 , wherein said learning technique is a supervised and/or unsupervised learning technique.
Claim 69
Dependent Claim
46 words
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.
Claim 70
Dependent Claim
18 words
The computer program product according to claim 66 , wherein said three-dimensional map is a type evaluation map.
Claim 71
Dependent Claim
37 words
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.
Claim 72
Dependent Claim
48 words
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.
Claim 73
Dependent Claim
49 words
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.
Claim 74
Dependent Claim
44 words
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.
Claim 75
Dependent Claim
34 words
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.
Claim 76
Dependent Claim
48 words
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.
Claim 77
Dependent Claim
41 words
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.
Claim 78
Dependent Claim
62 words
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 k S k V k T of rank k, where k≦r.
Claim 79
Dependent Claim
37 words
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 T U k S k −1 .
Claim 80
Dependent Claim
31 words
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.
Claim 81
Dependent Claim
51 words
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.
References Cited (Backward Citations)
US4944023A
Cited
US4839859A
Cited
US4839853A
Cited
US5226175A
Cited
US5751286A
Cited
US5802361A
Cited
US5781899A
Cited
US5655117A
Cited
US5710877A
Cited
US5911139A
Cited
US5751852A
Cited
US5878425A
Cited
US5819288A
Cited
US5845009A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-06-02 | 2006-12-02 | 2007-06-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-06-02 | 2010-12-02 | 2011-06-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-06-02 | 2014-12-02 | 2015-06-03 | $7700.00 | Window Closed / Lapsed |