US6502105B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Region-based image archiving and retrieving system
Assignee: Uniloc 2017 LLC
•
Filing: 1999-01-15
•
Granted: 2002-12-31
•
Expires: 2019-01-15
Abstract
Abstract The system disclosed herein builds a database of image-related data by inputting a plurality of images, and for each image: dividing the image into N 1 (N 1 ≧1) regions which are substantially homogenous with respect to at least one attribute of the image, generating a graph based on M 1 (M 1 ≧1) of the N 1 regions, and storing data for the graph in the database. The database may then be used to determine whether a query image is similar to one or more of the plurality of images. To this end, the system inputs the query image, and divides the query image into N 2 (N 2 ≧1) regions which are substantially homogenous with respect to at least one attribute of the query image. The system then generates a graph based on M 2 (M 2 ≧1) of the N 2 regions, and compares the generated graph to other graphs in the database that correspond to the plurality of images. Thereafter, an image is retrieved from memory that has a graph that is substantially similar to the generated graph.
Inventors
- 👤 Yong Yan
- 👤 Cedric Y. Caron
- 👤 Kiran Challapali
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 22:22
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/50; G06F16/58; G06F16/583; G06F16/5854; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99944; Y10S707/99945; Y10S707/99948
Claims Analysis
Total Claims: 44
Claim 1
Independent Claim
104 words
A method of building a database of image-related data, the method comprising the steps of: inputting a plurality of images; and for each image: dividing the image into N (N≧1) regions which are substantially homogenous with respect to at least one attribute of the image; generating a graph based on M (M≧1) of the regions; and storing data for the graph in the database by forming groups of images primarily based on graphs of the images and storing the groups of images into sub-databases, wherein the forming step forms the groups based on images having graphs with at least a predetermined number of similarities.
Claim 2
Independent Claim
104 words
A method of building a database of image-related data, the method comprising the steps of: inputting a plurality of images; and for each image: dividing the image into N (N≧1) regions which are substantially homogenous with respect to at least one attribute of the image; generating a graph based on M (M≧1) of the regions; and storing data for the graph in the database by forming groups of images primarily based on graphs of the images and storing the groups of images into sub-databases, wherein the forming step forms the groups based on images having graphs with at least a predetermined number of similarities.
Claim 3
Dependent Claim
44 words
A method according to claim 1 , wherein the inputting step comprises the steps of: inputting frames of video data; and extracting key frames from the video data; wherein the dividing, generating and storing steps are performed for each extracted key frame of video.
Claim 4
Dependent Claim
20 words
A method according to claim 1 , wherein the at least one attribute comprises textures and/or colors in the image.
Claim 5
Dependent Claim
31 words
A method according to claim 1 , further comprising, between the generating and storing steps, the step of assigning labels to regions of the graph based on contents of the regions.
Claim 6
Dependent Claim
29 words
A method according to claim 4 , wherein the assigning step assigns at least one region in the graph a label based on its position in a color space.
Claim 7
Dependent Claim
40 words
A method accordingly to claim 1 , wherein the step of dividing the image into N (N≧1) regions comprises dividing the image into N (N≧1) regions which are substantially homogenous with respect to at least two attributes of the image.
Claim 8
Independent Claim
92 words
A method of using graphs corresponding to a plurality of images as a primary type of interest to determine whether a query image is similar to one or more of the plurality of images, the method comprising the steps of: inputting the query image; dividing the query image into N (N≧1) regions which are substantially homogenous with respect to at least one attribute of the query image; generating a graph based on M (M≧1) of the regions; and comparing the generated graph to other graphs that correspond to the plurality of images.
Claim 9
Independent Claim
92 words
A method of using graphs corresponding to a plurality of images as a primary type of interest to determine whether a query image is similar to one or more of the plurality of images, the method comprising the steps of: inputting the query image; dividing the query image into N (N≧1) regions which are substantially homogenous with respect to at least one attribute of the query image; generating a graph based on M (M≧1) of the regions; and comparing the generated graph to other graphs that correspond to the plurality of images.
Claim 10
Dependent Claim
29 words
A method according to claim 7 , further comprising the step of retrieving an image from memory that has a graph that is substantially similar to the generated graph.
Claim 11
Dependent Claim
39 words
A method according to claim 7 , wherein the inputting step comprises the steps of: inputting frames of video; and extracting a key frame from the video, the query image corresponding to at least part of the key frame.
Claim 12
Dependent Claim
67 words
A method according to claim 7 , further comprising, between the generating and comparing steps, the step of assigning labels to regions of the generated graph based on contents of the regions; wherein the comparing step determines which, if any, regions of the generated graph to compare to the other graphs based on the labels assigned to the generated graph and labels included on the other graphs.
Claim 13
Dependent Claim
40 words
A method according to claim 7 , further comprising the step of pruning the generated graph prior to comparing it to the other graphs; wherein pruning comprises removing at least one of vertices, labels and edges from the generated graph.
Claim 14
Dependent Claim
30 words
A method according to claim 11 , wherein the pruning step removes vertices, labels and/or edges from the generated graph that correspond to homogeneous image regions having a predetermined attribute.
Claim 15
Dependent Claim
127 words
Computer-executable process steps stored on a computer-readable medium, the computer-executable process steps to build a database of image-related data, the computer-executable process steps comprising: code to input a plurality of images; and code, for each image, (i) to divide the image into N (N≧1) regions which are substantially homogenous with respect to at least one attribute of the image, (ii) to generate a graph based on M (M≧1) of the regions, and (iii) to store data for the graph in the database by forming groups of images primarily based on graphs of the images and storing the groups of images into sub-databases, wherein the code for forming the groups of images forms the groups based on images having graphs with at least a predetermined number of similarities.
Claim 16
Dependent Claim
127 words
Computer-executable process steps stored on a computer-readable medium, the computer-executable process steps to build a database of image-related data, the computer-executable process steps comprising: code to input a plurality of images; and code, for each image, (i) to divide the image into N (N≧1) regions which are substantially homogenous with respect to at least one attribute of the image, (ii) to generate a graph based on M (M≧1) of the regions, and (iii) to store data for the graph in the database by forming groups of images primarily based on graphs of the images and storing the groups of images into sub-databases, wherein the code for forming the groups of images forms the groups based on images having graphs with at least a predetermined number of similarities.
Claim 17
Dependent Claim
46 words
Computer-executable process steps according to claim 13 , wherein the inputting code comprises: code to input frames of video data; and code to extract key frames from the video data; wherein the dividing, generating and storing code is executed for each extracted key frame of video.
Claim 18
Dependent Claim
21 words
Computer-executable process steps according to claim 13 , wherein the at least one attribute comprises textures and/or colors in the image.
Claim 19
Dependent Claim
25 words
Computer-executable process steps according to claim 13 , further comprising code to assign labels to regions of the graph based on contents of the regions.
Claim 20
Dependent Claim
30 words
Computer-executable process steps according to claim 16 , wherein the assigning code assigns at least one region in the graph a label based on its position in a color space.
Claim 21
Dependent Claim
35 words
Computer-executable process steps according to claim 13 , wherein the storing code comprises: code to form groups of images based on graphs of the images; and code to store the groups of images into sub-databases.
Claim 22
Dependent Claim
28 words
Computer-executable process steps according to claim 17 , wherein the forming code forms the groups based on images having graphs with at least a predetermined number of similarities.
Claim 23
Dependent Claim
104 words
Computer-executable process steps stored on a computer-readable medium, the computer executable process steps using graphs corresponding to a plurality of images to determine whether a query image is similar to one or more of the plurality of images, the computer-executable process steps comprising: code to input the query image; code to divide the query image into N (N≧1) regions which are substantially homogenous with respect to at least one attribute of the query image; code to generate a graph based on M (M≧1) of the regions; and code to primarily compare the generated graph to other graphs that correspond to the plurality of images.
Claim 24
Dependent Claim
104 words
Computer-executable process steps stored on a computer-readable medium, the computer executable process steps using graphs corresponding to a plurality of images to determine whether a query image is similar to one or more of the plurality of images, the computer-executable process steps comprising: code to input the query image; code to divide the query image into N (N≧1) regions which are substantially homogenous with respect to at least one attribute of the query image; code to generate a graph based on M (M≧1) of the regions; and code to primarily compare the generated graph to other graphs that correspond to the plurality of images.
Claim 25
Dependent Claim
29 words
Computer-executable process steps according to claim 20 , further comprising code to retrieve an image from memory that has a graph that is substantially similar to the generated graph.
Claim 26
Dependent Claim
41 words
Computer-executable process steps according to claim 20 , wherein the inputting code comprises: code to input frames of video; and code to extract a key frame from the video, the query image corresponding to at least part of the key frame.
Claim 27
Dependent Claim
61 words
Computer-executable process steps according to claim 20 , further comprising code to assign labels to regions of the generated graph based on contents of the regions; wherein the comparing code determines which, if any, regions of the generated graph to compare to the other graphs based on the labels assigned to the generated graph and labels included on the other graphs.
Claim 28
Dependent Claim
40 words
Computer-executable process steps according to claim 20 , further comprising code to prune the generated graph prior to comparing it to the other graphs; wherein pruning comprises removing at least one of vertices, labels and edges from the generated graph.
Claim 29
Dependent Claim
31 words
Computer-executable process steps according to claim 24 , wherein the pruning code removes vertices, labels and/or edges from the generated graph that correspond to homogeneous image regions having a predetermined attribute.
Claim 30
Independent Claim
127 words
An apparatus for building a database of image-related data, the apparatus comprising: a memory which stores computer-executable process steps; and a processor which executes the process steps so as to input a plurality of images, and for each image: (i) to divide the image into N (N≧1) regions which are substantially homogenous with respect to at least one attribute of the image, (ii) to generate a graph based on M (M≧1) of the regions, and (iii) to store data for the graph in the database by forming groups of images primarily based on graphs of the images and storing the groups of images into sub-databases, wherein the forming groups of images forms the groups based on images having graphs with at least a predetermined number of similarities.
Claim 31
Independent Claim
127 words
An apparatus for building a database of image-related data, the apparatus comprising: a memory which stores computer-executable process steps; and a processor which executes the process steps so as to input a plurality of images, and for each image: (i) to divide the image into N (N≧1) regions which are substantially homogenous with respect to at least one attribute of the image, (ii) to generate a graph based on M (M≧1) of the regions, and (iii) to store data for the graph in the database by forming groups of images primarily based on graphs of the images and storing the groups of images into sub-databases, wherein the forming groups of images forms the groups based on images having graphs with at least a predetermined number of similarities.
Claim 32
Dependent Claim
47 words
An apparatus according to claim 26 , wherein the processor inputs the plurality of images by (i) inputting frames of video data, and (ii) extracting key frames from the video data, wherein the dividing, generating and storing steps are performed for each extracted key frame of video.
Claim 33
Dependent Claim
20 words
An apparatus according to claim 26 , wherein the at least one attribute comprises textures and/or colors in the image.
Claim 34
Dependent Claim
33 words
An apparatus according to claim 26 , wherein the processor, between the generating and storing steps, executes process steps to assign labels to regions of the graph based on contents of the regions.
Claim 35
Dependent Claim
29 words
An apparatus according to claim 29 , wherein the assigning step assigns at least one region in the graph a label based on its position in a color space.
Claim 36
Dependent Claim
34 words
An apparatus according to claim 26 , wherein the processor stores the data by (i) forming groups of images based on graphs of the images, and (ii) storing the groups of images into sub-databases.
Claim 37
Dependent Claim
27 words
An apparatus according to claim 31 , wherein the forming step forms the groups based on images having graphs with at least a predetermined number of similarities.
Claim 38
Independent Claim
114 words
An apparatus for using graphs corresponding to a plurality of images as a primary type of interest to determine whether a query image is similar to one or more of the plurality of images, the apparatus comprising: a memory which stores computer-executable process steps; and a processor which executes the process steps so as (i) to input the query image, (ii) to divide the query image into N (N≧1) regions which are substantially homogenous with respect to at least one attribute of the query image, (iii) to generate a graph based on M (M≧1) of the regions, and (iv) to compare the generated graph to other graphs that correspond to the plurality of images.
Claim 39
Independent Claim
114 words
An apparatus for using graphs corresponding to a plurality of images as a primary type of interest to determine whether a query image is similar to one or more of the plurality of images, the apparatus comprising: a memory which stores computer-executable process steps; and a processor which executes the process steps so as (i) to input the query image, (ii) to divide the query image into N (N≧1) regions which are substantially homogenous with respect to at least one attribute of the query image, (iii) to generate a graph based on M (M≧1) of the regions, and (iv) to compare the generated graph to other graphs that correspond to the plurality of images.
Claim 40
Dependent Claim
32 words
An apparatus according to claim 33 , wherein the processor further executes process steps to retrieve an image from memory that has a graph that is substantially similar to the generated graph.
Claim 41
Dependent Claim
41 words
An apparatus according to claim 33 , wherein the processor inputs the query image by (i) inputting frames of videos and (ii) extracting a key frame from the video, the query image corresponding to at least part of the key frame.
Claim 42
Dependent Claim
69 words
An apparatus according to claim 33 , wherein the processor executes, between the generating and comparing steps, process steps to assign labels to regions of the generated graph based on contents of the regions; wherein the comparing step determines which, if any, regions of the generated graph to compare to the other graphs based on the labels assigned to the generated graph and labels included on the other graphs.
Claim 43
Dependent Claim
44 words
An apparatus according to claim 33 , wherein the processor executes process steps so as to prune the generated graph prior to comparing it to the other graphs; wherein pruning comprises removing at least one of vertices, labels and edges from the generated graph.
Claim 44
Dependent Claim
30 words
An apparatus according to claim 37 , wherein the pruning step removes vertices, labels and/or edges from the generated graph that correspond to homogeneous image regions having a predetermined attribute.
References Cited (Backward Citations)
US5751286A
Cited
US5544267A
Cited
US5893095A
Cited
US5751852A
Cited
US5974201A
Cited
US6121969A
Cited
US6240424B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-12-30 | 2006-07-01 | 2006-12-31 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-12-30 | 2010-07-01 | 2010-12-31 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-12-30 | 2014-07-01 | 2014-12-31 | $7700.00 | Window Closed / Lapsed |