SEARCH ENGINE AND METHOD FOR IMAGE SEARCHING

• US 20100036818A1
• Filed: 08/04/2009
• Published: 02/11/2010
• Est. Priority Date: 08/06/2008
• Status: Active Grant

• Current Assignee: Obschestvo S Ogranichennoi Otvetstvennostiu "Kuznetch", Obschestvo S Ogranichennoi Otvetstvennostiu "Kuznetch\
• Original Assignee: Obschestvo S Ogranichennoi Otvetstvennostiu "Kuznetch"
• Inventors: Valencia-Campo, Alexander, Makalkin, Mikhail
• Granted Patent: US 8,762,383 B2
• Time in Patent Office: Days
• US Class Current: N/A
• 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;

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

generating an image index file from the plurality of metrics for each region; and

storing the image index file in a database.

2. The computer-implemented method of claim 1, wherein gridding the digital image comprises dividing the digital image into a plurality of cells.

3. The computer-implemented method of claim 1, wherein calculating the plurality of metrics comprises calculating two or more of texture image metrics, color image metrics, intensity image metrics, shape metrics and salient point metrics.

4. The computer-implemented method of claim 1, wherein generating the image index file 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.

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

converting each image metric vector into a binary numerical descriptor.

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

aligning each of the plurality of image metric vectors.

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

aligning each of the plurality of binary numerical descriptors.

8. The computer-implemented method of claim 1, further comprising assigning the image index file to a cluster.

9. The computer-implemented method of claim 8, wherein assigning the image index file to a cluster comprises comparing the image index file of digital image to a cluster identifier.

10. The computer-implemented method of claim 9, comparing the image index file of digital image to the cluster identifier comprises:

calculating the difference for each image metric between the image index file and the cluster identifier;

multiplying the difference by a weighting factor for each image metric; and

summing the weighted similarity values.

11. A computer-implemented method comprising:

locating a plurality of digital images at websites;

storing the digital images in a first database with a link to the website on which the digital image was located;

calculating an image index file for each of the located images, the image index file representative of the located images;

storing the image index file with the link in a second database; and

deleting the digital images from the first database when the image index file of that image is stored in the second database.

12. The computer-implemented method of claim 11 wherein calculating the image index file comprises calculating a plurality of image metrics.

13. The computer-implemented method of claim 12 wherein calculating the plurality of metrics comprises calculating two or more of texture image metrics, color image metrics, intensity image metrics, shape metrics and salient point metrics.

14. The computer-implemented method of claim 12 wherein at least one of the image metrics is calculated from the original image and at least one of the image metrics is calculated from a representation of the image.

15. The computer-implemented method of claim 14 further comprising generating the representation of the image.

16. The computer-implemented method of claim 15 wherein generating the representation comprises resizing and reshaping the image.

17. The computer-implemented method of claim 11 further comprising normalizing the image before assigning the mathematical descriptor.

18. The computer-implemented method of claim 15 further comprising storing the representation in the database.

19. The computer-implemented method of claim 11 further comprising clustering the digital images.

20. The computer-implemented method of claim 19 wherein clustering the digital images comprises:

dividing each 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 to generate a plurality of numerical descriptors for the plurality of image metrics; and

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

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

calculating the difference for each numerical descriptor between the image index file and the cluster identifier;

multiplying the difference by a weighting factor for each numerical descriptor; and

summing the weighted similarity values.

22. The computer-implemented method of claim 11 wherein calculating the image index file for each of the located images comprises:

dividing each 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 to generate a plurality of numerical descriptors, the image index file comprise the plurality of numerical descriptors.

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

24. The computer-implemented method of claim 11, further comprising storing user defined metadata with the image index files for each image.

25. The computer-implemented method of claim 11, further comprising storing machine generated metadata with the image index files for each image.

26. The computer-implemented method of claim 11, further comprising storing a thumbnail version of the image with the image index files for each image.

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

28. The computer-implemented method of claim 12 wherein calculating the plurality of image metrics comprises calculating a 2D color histogram.

29. The computer-implemented method of claim 12 wherein calculating the plurality of image metrics comprises calculating a 4D color vector field.

30. A computer system comprising

a crawling data store to temporarily store digital images;

an index data store comprising a plurality of image index files representation of the digital images; and

an indexing engine to calculate the image index files for each digital image, each image index file comprising a plurality of image metrics, and provide a request to delete each digital image from the crawling data store after the image index file for the digital image is calculated.

31. The computer system of claim 30 further comprising a crawler to locate digital images on webpages and store the digital images in the crawling data store.

32. The computer system of claim 30 wherein the image index file further comprises a link to a webpage where the digital image is located.

33. The computer system of claim 30 wherein the indexing engine is further configured to cluster the image index files based on a similarity of the image index files.

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

35. The computer system of claim 30 wherein the indexing engine is further configured to divide each 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 to generate a plurality of numerical descriptors, and group the digital image with other similar digital images by comparing the numerical descriptors.

36. The computer system of claim 30 wherein the indexing engine is further configured to divide each 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 to generate a plurality of numerical descriptors, the image index file comprising the plurality of numerical descriptors.

37. A computer-implemented method comprising:

providing a structured database having a plurality of clusters, each cluster having a plurality of image index files representative of digital images, and each cluster having a cluster identifier;

receiving a search query, the search query being a digital image;

calculating the image index file of the search query; and

comparing the image index file of the search query with each cluster identifier to identify a cluster to search;

comparing the image index file of the search query with each of the plurality of image index files in the identified cluster; and

determining a similarity of the search query with the images in the identified cluster.

38. The computer-implemented method of claim 37, wherein calculating the image index files comprises calculating a plurality of image metrics.

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

40. The computer-implemented method of claim 37, wherein the digital image comprises a video and further comprising selecting one or more frames of the video for comparison.

41. The computer-implemented method of claim 37, wherein determining the similarity comprises calculating a similarity score between the image index file of the search query and each of the plurality of image index files in the cluster.

42. The computer-implemented method of claim 41, further comprising ranking the images according to the calculated similarity score.

43. The computer-implemented method of claim 41, wherein calculating the similarity score comprises calculating a scalar value.

44. The computer-implemented method of claim 41, wherein calculating a similarity score between the image index file of the search query and each of the plurality of image index files in the cluster comprises:

calculating a similarity value for each image metric in the image index files;

multiplying the similarity value by a weighting factor for each image metric; and

summing the weighted similarity values.

45. The computer-implemented method of claim 37, further comprising splitting the search query into logical components of the digital image and calculating an index file for each of the logical components.

46. The computer-implemented method of claim 37, further comprising normalizing the search query image before calculating the image index file.

47. The computer-implemented method of claim 37, further comprising transmitting search results corresponding to the search query.

48. The computer-implemented method of claim 47, wherein the search results comprise an array of images corresponding to the images represented by the image descriptors in the cluster that are similar to the search query.

49. The computer-implemented method of claim 47 further comprising generating a web page based on the search results and transmitting the web page.

50. A computer system comprising

an index data store comprising a plurality of image index files representative of digital images;

a search portal to receive an image query; and

an indexing engine to calculate the image index files for each digital image, calculate an image index file for the image query, identify a searchable cluster for the digital image and compare the image index file for the digital image with the plurality of image index files in the cluster.

51. The computer system of claim 50 further comprising a crawler to locate digital images on webpages.

52. The computer system of claim 50 wherein the search portal further comprises a user interface.