System for retrieving images using a database

• US 6,226,636 B1
• Filed: 11/20/1998
• Issued: 05/01/2001
• Est. Priority Date: 11/20/1998
• Status: Expired due to Term

• Current Assignee: Uniloc 2017 LLC (FIG LLC (d/b/a Fortress Investment Group LLC))
• Original Assignee: Philips Electronics North America Corporation (Koninklijke Philips N.V.)
• Inventors: Krishnamachari, Santhana, Abdel-Mottaleb, Mohamed
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): PARDO, THUY N
• Application Number:
  US09/197,315
• Time in Patent Office: 893 Days
• Field of Search: 707/4, 707/5, 707/101, 707/102, 382/140, 382/226, 382/103, 382/118, 382/199, 382/236, 382/128, 382/240, 358/455, 358/447, 358/296, 395/131, 348/413
• US Class Current: 1/1
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

The system builds a database which stores data corresponding to a plurality of images. To begin, the system divides each image into N (N≧1) regions. Then, for each of the N regions, the system calculates a histogram of the region, generates a binary representation of the histogram, and stores data corresponding to the image in a binary tree based on the binary representation. The database may then be used to determine images which are similar to a query image. To do this, the system divides the query image into N regions, each of which corresponds to one of the binary trees in the database. Data corresponding to one or more images in the database is then retrieved from the binary trees based on the N regions. The system then determines which of these images is similar to the query image based on the retrieved data.

Claims

1. A method of building a database which stores data corresponding to a plurality of images, wherein for each image, the method comprises the steps of:

dividing the image into N (N≧

1) regions; and

for each of the N regions;

calculating a histogram of the region;

generating a binary representation of the histogram; and

storing data corresponding to the image in a binary tree based on the binary representation.

2. A method according to claim 1, wherein the data corresponding to the image comprises a pointer to the image in memory.

3. A method according to claim 1, wherein the calculating step calculates the histogram for the region based on color image data in the region.

4. A method according to claim 1, wherein the generating step comprises:

performing a Haar transform on the histogram to generate wavelet coefficients therefor; and

quantizing the coefficients to generate the binary representation.

5. A method according to claim 1, wherein the storing step comprises:

traversing the binary tree using the binary representation; and

storing the data corresponding to the image at an end point of the binary tree.

6. A method according to claim 5, wherein the traversing step comprises comparing each bit in the binary representation to a corresponding node in the binary tree, and branching left or right in the binary tree based on whether a match is achieved until reaching the end point.

7. A method according to claim 1, wherein the storing step comprises:

comparing at least some bits in the binary representation to corresponding nodes up to a current node in the binary tree; and

determining whether the current node in the binary tree stores data for more than a predetermined number of images;

wherein, in a case that the current node in the binary tree stores data for more than the predetermined number of images, the storing step splits the current node into two subsequent nodes, and stores the data in the subsequent nodes; and

wherein, in a case that the current node in the binary tree stores data for less than or equal to the predetermined number of images, the storing step stores the data at the current node in the binary tree.

8. A method according to claim 1, wherein the storing step stores data corresponding to the image in N separate binary trees, one binary tree for each of the N regions of the image.

9. A method according to claim 1, wherein the N regions comprise N contiguous rectangular regions of the image.

10. A method of determining which images in a database are similar to a query image, where the database is comprised of N (N≧

1) binary trees, and where each of the N binary trees stores data corresponding to one or more predetermined images, the method comprising the steps of;

dividing the query image into N regions, each of the N regions corresponding to one of the N binary trees;

retrieving data corresponding to one or more predetermined images from binary trees corresponding to the N regions; and

determining which of the predetermined images is similar to the query image based on the data retrieved in the retrieving step.

11. A method according to claim 10, wherein the retrieving step comprises, for each of the N regions of the query image:

calculating a histogram of the region;

generating a binary representation of the histogram; and

retrieving data corresponding to one or more predetermined images by traversing a binary tree that corresponds to the region using the binary representation of the histogram.

12. A method according to claim 11, wherein the calculating step calculates the histogram based on color image data in the region.

13. A method according to claim 11, wherein the generating step comprises:

performing a Haar transform on the histogram to generate wavelet coefficients therefor; and

quantizing the coefficients to generate the binary representation.

14. A method according to claim 10, wherein the data corresponding to the one or more predetermined images comprises pointers to the predetermined images in memory;

and

wherein the determining step determines which of the predetermined images is similar to the query image based on which pointers were retrieved by the retrieving step.

15. A method according to claim 14, wherein a predetermined image for which a most number of pointers was retrieved by the retrieving step is determined to be most similar to the query image.

16. A method according to claim 10, wherein the determining step comprises:

identifying candidate images among the predetermined images that could correspond to the query image;

ranking the candidate images in order from an image most likely to correspond to the query image to an image least likely to correspond to the query image; and

displaying a list of the ranked candidate images.

17. A method according to claim 16, wherein the ranking step ranks the candidate images based on the data retrieved by the retrieving step.

18. A method according to claim 10, wherein the data retrieved in the retrieving step comprises pointers to images in memory;

and

further comprising the step of retrieving at least one predetermined image that is similar to the query image based on a retrieved pointer.

19. Computer-executable process steps stored on a computer-readable medium, the computer-executable process steps to build a database which stores data corresponding to a plurality of images, the computer-executable process steps comprising:

code which divides each image into N (N≧

1) regions; and

code which, for each of the N regions, (i) calculates a histogram of the region, (ii) generates a binary representation of the histogram, and (iii) stores data corresponding to the image in a binary tree based on the binary representation.

20. Computer-executable process steps according to claim 19, wherein the data corresponding to the image comprises a pointer to the image in memory.

21. Computer-executable process steps according to claim 19, wherein the calculating code calculates the histogram for the region based on color image data in the region.

22. Computer-executable process steps according to claim 19, wherein the generating code comprises:

code which performs a Haar transform on the histogram to generate wavelet coefficients therefor; and

code which quantizes the coefficients to generate the binary representation.

23. Computer-executable process steps according to claim 19, wherein the storing code comprises:

code which traverses the binary tree using the binary representation; and

code which stores the data corresponding to the image at an end point of the binary tree.

24. Computer-executable process steps according to claim 23, wherein the traversing code compares each bit in the binary representation to a corresponding node in the binary tree, and branches left or right in the binary tree based on whether a match is achieved until reaching the end point.

25. Computer-executable process steps according to claim 19, wherein the storing code comprises:

code which compares at least some bits in the binary representation to corresponding nodes up to a current node in the binary tree; and

code which determines whether the current node in the binary tree stores data for more than a predetermined number of images;

wherein, in a case that the current node in the binary tree stores data for more than the predetermined number of images, the storing code splits the current node into two subsequent nodes, and stores the data in the subsequent nodes; and

wherein, in a case that the current node in the binary tree stores data for less than or equal to the predetermined number of images, the storing code stores the data at the current node in the binary tree.

26. Computer-executable process steps according to claim 19, wherein the storing code stores data corresponding to the image in N separate binary trees, one binary tree for each of the N regions of the image.

27. Computer-executable process steps according to claim 19, wherein the N regions comprise N contiguous rectangular regions of the image.

28. Computer-executable process steps stored on a computer-readable medium, the computer-executable process steps to determine which images in a database are similar to a query image, where the database is comprised of N (N≧

1) binary trees, and where each of the N binary trees stores data corresponding to one or more predetermined images, the computer-executable process steps comprising;

code to divide the query image into N regions, each of the N regions corresponding to one of the N binary trees;

code to retrieve data corresponding to one or more predetermined images from binary trees corresponding to the N regions; and

code to determine which of the predetermined images is similar to the query image based on the data retrieved by the retrieving code.

29. Computer-executable process steps according to claim 28, wherein the retrieving code comprises code which, for each of the N regions of the query image, calculates a histogram of the region, generates a binary representation of the histogram, and retrieves data corresponding to one or more predetermined images by traversing a binary tree that corresponds to the region using the binary representation of the histogram.

30. Computer-executable process steps according to claim 29, wherein the calculating code calculates the histogram based on color image data in the region.

31. Computer-executable process steps according to claim 29, wherein the generating code comprises:

code which performs a Haar transform on the histogram to generate wavelet coefficients therefor; and

code which quantizes the coefficients to generate the binary representation.

32. Computer-executable process steps according to claim 28, wherein the data corresponding to the one or more predetermined images comprises pointers to the predetermined images in memory;

and

wherein the determining code determines which of the predetermined images is similar to the query image based on which pointers were retrieved by the retrieving code.

33. Computer-executable process steps according to claim 32, wherein a predetermined image for which a most number of pointers was retrieved by the retrieving code is determined to be most similar to the query image.

34. Computer-executable process steps according to claim 28, wherein the determining code comprises:

code to identify candidate images among the predetermined images that could correspond to the query image;

code to rank the candidate images in order from an image most likely to correspond to the query image to an image least likely to correspond to the query image; and

code to display a list of the ranked candidate images.

35. Computer-executable process steps according to claim 34, wherein the ranking code ranks the candidate images based on the data retrieved by the retrieving code.

36. Computer-executable process steps according to claim 28, wherein the data retrieved by the retrieving code comprises pointers to images in memory;

and

further comprising code to retrieve at least one predetermined image that is similar to the query image based on a retrieved pointer.

37. An apparatus for building a database which stores data corresponding to a plurality of images, the apparatus comprising:

a memory which stores computer-executable process steps; and

a processor which executes the process steps so as to divide each image into N (N≧

1) regions, and for each of the N regions, (i) to calculate a histogram of the region, (ii) to generate a binary representation of the histogram, and (iii) to store data corresponding to the image in a binary tree based on the binary representation.

38. An apparatus according to claim 37, wherein the data corresponding to the image comprises a pointer to the image in memory.

39. An apparatus according to claim 37, wherein the processor calculates the histogram for the region based on color image data in the region.

40. An apparatus according to claim 37, wherein the processor generates the binary representation of the histogram by (i) performing a Haar transform on the histogram to generate wavelet coefficients therefor, and (ii) quantizing the coefficients.

41. An apparatus according to claim 37, wherein the processor stores the data by (i) traversing the binary tree using the binary representation, and (ii) storing the data corresponding to the image at an end point of the binary tree.

42. An apparatus according to claim 41, wherein the processor traverses the binary tree by (i) comparing each bit in the binary representation to a corresponding node in the binary tree, and (ii) branching left or right in the binary tree based on whether a match is achieved.

43. An apparatus according to claim 37, wherein the processor stores the data by (i) comparing at least some bits in the binary representation to corresponding nodes up to a current node in the binary tree, and (ii) determining whether the current node in the binary tree stores data for more than a predetermined number of images;

wherein, in a case that the current node in the binary tree stores data for more than the predetermined number of images, the processor splits the current node into two subsequent nodes, and stores the data in the subsequent nodes; and

wherein, in a case that the current node in the binary tree stores data for less than or equal to the predetermined number of images, the processor stores the data at the current node in the binary tree.

44. An apparatus according to claim 37, wherein the processor stores data corresponding to the image in N separate binary trees, one binary tree for each of the N regions of the image.

45. An apparatus according to claim 37, wherein the N regions comprise N contiguous rectangular regions of the image.

46. An apparatus according to claim 37, further comprising:

a network interface which interfaces the apparatus to a network; and

a server which stores the database, the server being located remotely from the apparatus on the network.

47. An apparatus for determining which images in a database are similar to a query image, where the database is comprised of N (N≧

1) binary trees, and where each of the N binary trees stores data corresponding to one or more predetermined images, the apparatus comprising;

a memory which stores computer-executable process steps; and

a processor which executes the process steps so as (i) to divide the query image into N regions, each of the N regions corresponding to one of the N binary trees, (ii) to retrieve data corresponding to one or more predetermined images from binary trees corresponding to the N regions, and (iii) to determine which of the predetermined images is similar to the query image based on the retrieved data.

48. An apparatus according to claim 47, wherein for each of the N regions of the query image, the processor retrieves the data by (i) calculating a histogram of the region, (ii) generating a binary representation of the histogram, and (iii) retrieving data corresponding to one or more predetermined images by traversing a binary tree that corresponds to the region using the binary representation of the histogram.

49. An apparatus according to claim 48, wherein the processor calculates the histogram based on color image data in the region.

50. An apparatus according to claim 48, wherein the processor generates the binary representation of the histogram by (i) performing a Haar transform on the histogram to generate wavelet coefficients therefor, and (ii) quantizing the coefficients to generate the binary representation.

51. An apparatus according to claim 47, wherein the data corresponding to the one or more predetermined images comprises pointers to the predetermined images in memory;

and

wherein the processor determines which of the predetermined images is similar to the query image based on which pointers were retrieved.

52. An apparatus according to claim 51, wherein a predetermined image for which a most number of pointers was retrieved by the processor is determined to be most similar to the query image.

53. An apparatus according to claim 47, wherein the processor determines which of the predetermined images is similar to the query image by (i) identifying candidate images among the predetermined images that could correspond to the query image, (ii) ranking the candidate images in order from an image most likely to correspond to the query image to an image least likely to correspond to the query image, and (iii) displaying a list of the ranked candidate images.

54. An apparatus according to claim 53, wherein the processor ranks the candidate images based on the retrieved data corresponding to the one or more predetermined images.

55. An apparatus according to claim 47, wherein the data retrieved by the processor comprises pointers to images in memory;

and

wherein the processor further executes process steps so as to retrieve at least one predetermined image that is similar to the query image based on a retrieved pointer.

56. An apparatus according to claim 47, wherein the apparatus is a personal computer.

57. An apparatus according to claim 47, wherein the apparatus is a photocopier.

58. An apparatus according to claim 47, wherein the apparatus is a digital television.

59. An apparatus according to claim 47, further comprising:

a network interface which interfaces the apparatus to a network; and

a server on the network which stores the database, the server being located remotely from the apparatus on the network.