Efficient image matching for large sets of images

• US 9,275,311 B2
• Filed: 11/11/2014
• Issued: 03/01/2016
• Est. Priority Date: 05/07/2013
• Status: Active Grant

• Current Assignee: PicScout (Israel) LTD. (Getty Images Incorporated)
• Original Assignee: PicScout (Israel) LTD. (Getty Images Incorporated)
• Inventors: Lavi, Uri, Goz, Eli, Begelman, Gregory
• Primary Examiner(s): HEIDEMANN, JASON E
• Application Number:
  US14/538,689
• Publication Number:
  US 20150071552A1
• Time in Patent Office: 476 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/152 using file content signatures, e.g. hash values
• CPC Class Codes: G06F 16/162 Delete operations erasing in storage systems G06F3/0652
• CPC Class Codes: G06F 16/51 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/532 Query formulation, e.g. graphical querying
• CPC Class Codes: G06F 16/535 Filtering based on additional data, e.g. user or group profiles
• CPC Class Codes: G06F 16/55 Clustering; Classification
• CPC Class Codes: G06F 16/56 having vectorial format
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• CPC Class Codes: G06V 2201/11 Technique with transformation invariance effect
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches

Abstract

A system and method to detect similarities between images. The system and method allow comparisons between a query image and one or more catalog images in a manner that is resilient to scanning, scaling, rotating, cropping and other distortions of the query image. The system includes an image processing module that determines and/or calculates principle features of a catalog image and constructs a feature vector using one or more of the principle features. The system also includes a matching module that matches a query image to one or more catalog images. The system finds matches based on a distance measure of features present in the query image and features present in the catalog images.

Claims

1. A method in a computing system for matching a query image against a catalog of images to identify semi-identical images, the method comprising:

maintaining a catalog of images, each image in the catalog of images characterized by vectors associated with principle feature points of the image, the catalog of images being further processed to remove certain principle feature points associated with one or more images;

maintaining an inverted index to the catalog of images, the inverted index comprised of hash values of the vectors associated with each image;

receiving a query image that is to be searched against the catalog of images;

characterizing the received query image by;

extracting principal feature points from the query image;

creating vectors characterizing the extracted principal feature points; and

generating hash values for each of the vectors characterizing the query image; and

searching the catalog of images to find semi-identical images to the query image by;

comparing the query image hash values with the inverted index to the catalog of images;

identifying a set of catalog images having a predetermined number of hash values in common with the query image hash values;

identifying a number of geometric inliers in each image in the identified set of catalog images; and

identifying, from the set of catalog images, a set of near-identical images based on images that have a total number of geometric inliers that exceed a threshold value.

2. The method of claim 1, wherein the hash value of vectors are calculated using a k-d tree.

3. The method of claim 2, wherein the k-d tree has a predetermined number of vectors.

4. The method of claim 1, wherein the number of hash values characterizing a catalog image is less than the number of hash values characterizing the query image.

5. The method of claim 1, wherein the set of near-identical images is further based on normalizing the total number of geometric inliers for an image by the number of hash values characterizing the image.

6. The method of claim 1, wherein the geometric inliers are identified by a random sample consensus (RANSAC) algorithm.

7. The method of claim 1, wherein processing the catalog of images is performed using a support vector machine (SVM).

8. The method of claim 1, wherein the certain principle feature points removed by processing the catalog of images is based on a comparison with a catalog of unwanted features to remove unwanted features from an image.

9. A non-transitory computer-readable medium containing instructions that, when executed on a processor, cause the processor to implement a method for matching a query image against a catalog of images to identify semi-identical images, the method comprising:

maintaining a catalog of images, each image in the catalog of images characterized by vectors associated with principle feature points of the image, the catalog of images being further processed by removing certain principle feature points associated with one or more images;

maintaining an inverted index to the catalog of images, the inverted index comprised of hash values of the vectors associated with each image;

receiving a query image that is to be searched against the catalog of images;

characterizing the received query image by;

extracting principal feature points from the query image;

creating vectors characterizing the extracted principal feature points; and

generating hash values for each of the vectors characterizing the query image; and

searching the catalog of images to find semi-identical images to the query image by;

comparing the query image hash values with the inverted index to the catalog of images;

identifying a set of catalog images having a predetermined number of hash values in common with the query image hash values;

identifying a number of geometric inliers in each image in the identified set of catalog images; and

identifying, from the set of catalog images, a set of near-identical images based on images that have a total number of geometric inliers that exceed a threshold value.

10. The non-transitory computer-readable medium of claim 9, wherein the number of hash values characterizing a catalog image is less than the number of hash values characterizing the query image.

11. The non-transitory computer-readable medium of claim 9, wherein the set of near-identical images is further based on normalizing the total number of geometric inliers for an image by the number of hash values characterizing the image.

12. The non-transitory computer-readable medium of claim 9, wherein the geometric inliers are identified by a random sample consensus (RANSAC) algorithm.

13. The non-transitory computer-readable medium of claim 9, wherein processing the catalog of images is performed using a support vector machine (SVM).

14. The non-transitory computer-readable medium of claim 9, wherein the certain principle feature points removed by processing the catalog of images is based on a comparison with a catalog of unwanted features to remove unwanted features from an image.