Search engine and method for image searching

• US 8,762,383 B2
• Filed: 08/04/2009
• Issued: 06/24/2014
• Est. Priority Date: 08/06/2008
• Status: Expired due to Fees

• Current Assignee: Obschestvo S Ogranichennoi Otvetstvennostiu "Kuznetch", Obschestvo S Ogranichennoi Otvetstvennostiu "Kuznetch\
• Original Assignee: Obschestvo S Organichennoi Otvetstvennostiu "Kuznetch"
• Inventors: Valencia-Campo, Alexander, Makalkin, Mikhail
• Primary Examiner(s): Perveen, Rehana
• Assistant Examiner(s): Waldron, Scott A
• Application Number:
  US12/535,626
• Publication Number:
  US 20100036818A1
• Time in Patent Office: 1,785 Days
• Field of Search: 707/711, 707/741, 382/171, 382/218, 382/305
• US Class Current: 707/741
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 18/2111 by using evolutionary computational techniques, e.g. genetic algorithms

Abstract

Registration and classification of non-textual information, such as digital images and video is described. Image searching and comparison of the images is also described. The digital images are indexed (i.e., each image is assigned a unique numerical parameter and/or a plurality of numerical parameters). The resulting index files are stored in a database that can be quickly searched because the index files are universal numerical files that are significantly smaller in size than their source images. Image search queries are also indexed to generate an index file, which is then compared with the stored index files. A similarity score is also calculated to rank the similar images based on the index file-to-index file comparison.

Claims

1. A computer-implemented method comprising:

gridding a digital image by dividing the digital image into a plurality of regions;

calculating a plurality of image metrics for each region of the gridded digital image;

generating an image index file for each region, each image index file comprising the plurality of image metrics for the region of the gridded digital image that the image index file is generated for;

storing the image index files in a database;

determining similarity between a first gridded digital image and a second gridded digital image by comparing image index files associated with corresponding regions of the first gridded digital and second gridded digital images;

assigning the image index files to a cluster; and

comparing the image index files to a cluster identifier, wherein the comparing the image index files to a cluster identifier comprises;

calculating similarity values by calculating a difference between each image metric of the image index and the cluster identifier;

multiplying the respective similarity values by a weighting factor for each image metric of the image index; and

summing the weighted similarity values.

2. The computer-implemented method of claim 1, wherein calculating the plurality of metrics for each region of the gridded digital image comprises calculating two or more of texture image metrics, color image metrics, intensity image metrics, shape metrics and salient point metrics for each region of the gridded digital image.

3. The computer-implemented method of claim 1, wherein generating the image index files comprises:

aligning each image metric for each region of the gridded digital image to generate an image metric vector for each of the plurality of image metrics.

4. The computer-implemented method of claim 3, wherein generating the image index files further comprises:

converting each image metric vector for each of the plurality of image metrics into a binary numerical descriptor.

5. The computer-implemented method of claim 3, wherein generating the image index files further comprises:

aligning each of the plurality of image metric vectors.

6. The computer-implemented method of claim 4, wherein generating the image index files further comprises:

aligning each of the plurality of binary numerical descriptors.

7. A computer-implemented method comprising:

locating a plurality of digital images at a plurality of websites;

storing the plurality of digital images in a first database with a link to the corresponding website of the plurality of websites from which each digital image of the plurality of digital images was located;

calculating an image index file for each of the stored digital images, each image index file comprising a plurality of image metrics representative of two or more regions of the corresponding stored digital image and comprising the link to the corresponding website from which the digital image was located;

storing the image index files in a second database;

deleting the plurality of stored digital images from the first database when the corresponding image index file of each of the plurality of digital images is stored in the second database; and

clustering the stored digital images, wherein clustering the stored digital images comprises;

dividing each stored digital image into a plurality of cells;

calculating a plurality of image metrics for each of the plurality of cells;

aligning the plurality of image metrics with the plurality of the cells to generate a plurality of numerical descriptors for the plurality of image metrics; and

grouping the digital image with other similar stored digital images based on a comparison of the numerical descriptors.

8. The computer-implemented method of claim 7, wherein calculating the image index file comprises calculating two or more of texture image metrics, color image metrics, intensity image metrics, shape metrics and salient point metrics.

9. The computer-implemented method of claim 7, wherein at least one of the image metrics is calculated from one of the plurality of the stored digital images and at least one of the image metrics is calculated from a generated representation of one of the plurality of the stored digital images.

10. The computer-implemented method of claim 9, wherein generating the representation of the stored digital image comprises resizing and reshaping the stored digital image.

11. The computer-implemented method of claim 9 further comprising storing the generated representation of the stored digital image in the first database.

12. The computer-implemented method of claim 7 further comprising normalizing the plurality of the stored digital images and assigning a mathematical descriptor to each of the normalized stored digital images.

13. The computer-implemented method of claim 7, wherein grouping the stored digital image with other similar stored digital images based on a comparison of the numerical descriptors comprises:

calculating similarity values by calculating a difference between each numerical descriptor of the image index file for each stored digital image and a cluster identifier;

multiplying the respective similarity values by a weighting factor for each numerical descriptor; and

summing the weighted similarity values.

14. The computer-implemented method of claim 7, wherein calculating the image index file for each of the stored digital images comprises:

dividing each stored digital image into a plurality of cells;

calculating a plurality of image metrics for each of the plurality of cells; and

aligning the plurality of image metrics with the plurality of cells to generate a plurality of numerical descriptors for the plurality of image metrics,

wherein each image index file further comprises the plurality of numerical descriptors.

15. The computer-implemented method of claim 7, wherein calculating the image index file for each of the stored digital images comprises calculating an image index file for a frame of a located video.

16. The computer-implemented method of claim 7, further comprising storing user-defined metadata with each image index file.

17. The computer-implemented method of claim 7, further comprising storing machine-generated metadata with each image index file.

18. The computer-implemented method of claim 7, further comprising storing a thumbnail version of each stored digital image with each image index file in the second database.

19. The computer-implemented method of claim 7, wherein locating the plurality of the digital images comprises crawling the plurality of websites.

20. The computer-implemented method of claim 7, wherein calculating the image index file comprises calculating a 2D color histogram.

21. The computer-implemented method of claim 7, wherein calculating the image index file comprises calculating a 4D color vector field.

22. A computer system comprising:

a hardware processor;

a crawler configured to locate a plurality of digital images on a plurality of websites;

a crawling data store configured to temporarily store the plurality of the digital images with a link to the corresponding website of the plurality of websites from which each digital image of the plurality of digital images was located;

an index data store configured to store a plurality of image index files, each image index file comprising a plurality of image metrics representative of two or more regions of the corresponding stored digital image and comprising the link to the corresponding website from which the digital image was located; and

an indexing engine configured to;

calculate the image index file for each of the stored digital images,

delete the plurality of the stored digital images from the crawling data store after the corresponding image index file for each of the plurality of digital images is calculated and stored in the index data store,

divide each stored digital image into a plurality of cells,

calculate a plurality of image metrics for each of the plurality of cells,

align the plurality of image metrics with the plurality of cells to generate a plurality of numerical descriptors for the plurality of image metrics, and

group the digital image with other similar digital images based on a comparison of the numerical descriptors.

23. The computer system of claim 22, wherein the indexing engine is further configured to cluster the plurality of image index files based on a similarity of the image index files.

24. The computer system of claim 23, wherein the indexing engine is further configured to calculate a similarity score between one of the plurality of the image index files and another image index file to cluster the plurality of the image index files.

25. The computer system of claim 22, wherein the indexing engine is further configured to divide each stored digital image into a plurality of cells, calculate a plurality of image metrics for each of the plurality of cells, and align the plurality of image metrics with the plurality of cells to generate a plurality of numerical descriptors for the plurality of image metrics, wherein each image index file further comprises the plurality of numerical descriptors.