Systems, methods, and devices for image matching and object recognition in images

Abstract

An image matching technique locates feature points in a template image such as a logo and then does the same in a test image. Feature points from the template image are then matched to the feature points in the test image. An additional matching technique boosts the number of points that match each other. The additional points improve the match quality and help discriminate true from false positive matches.

We claim: 
     
         1 . A computer-implemented method for determining whether a portion of a first image is located within a second image, the method, implemented by hardware in combination with software, the method comprising:
 (A) determining a set of candidate matching feature points from a first set of feature points associated with said first image and a second set of feature points associated with said second image;   (B) selectively producing a transformed image by transforming one of: (i) said first image into a coordinate system of said second image, and (ii) said second image into a coordinate system of said first image, said transforming being based on a relationship of said candidate matching feature points; and   (C) attempting to boost said set candidate matching feature points to include additional candidate feature points associated with said first image and said second image, said attempting being based on (i) said candidate matching feature points and (ii) said transformed image; and then (D) determining whether said portion of said first image is located within said second image based on a size of said set candidate matching feature points.   
     
     
         2 . The method of  claim 1  wherein the determining in (A) eliminates at least some actual matching feature points and wherein the attempting to boost in (C) reestablished at least one of the at least some actual matching feature points that were eliminated in (A). 
     
     
         3 . The method of  claim 1  wherein said first set of feature points was determined from multiple versions of said first image. 
     
     
         4 . The method of  claim 1  further comprising:
 (E) repeating act (B) after said determining in (D), when said determining in (D) does not determine that said portion of said first image is located within said second image. 
 
     
     
         5 . The method of  claim 4  further comprising:
 repeating act (D) after act (E). 
 
     
     
         6 . The method of  claim 1  wherein said determining of said set of candidate matching feature points in (A) comprises:
 (A)(1) attempting to match feature points in said first set of feature points with feature points in said second set of feature points to determine a first set of matching feature points; and 
 (A)(2) attempting to match feature points in said second set of feature points with feature points in said first set of feature points to determine a second set of matching feature points. 
 
     
     
         7 . The method of  claim 6  wherein said determining of said set of candidate matching feature points in (A) further comprises, upon completion of acts (A)(1) and (A)(2):
 (A)(3) determining said set of candidate matching feature points as feature points that are common to both said first set of matching feature points and said second set of matching feature points. 
 
     
     
         8 . The method of  claim 1  wherein said acts (B)-(C) are selectively performed based on a size of the set of candidate matching feature points determined in (A). 
     
     
         9 . The method of  claim 1  wherein the attempting to boost in (C) is also based on (iii) said first set of feature points associated with said first image, and (iv) said second set of feature points associated with said second image. 
     
     
         10 . The method of  claim 1  wherein said attempting to boost in (C) is performed in the coordinate system of the second image, and wherein the selectively producing a transformed image in (B) comprises:
 (B)(1) if necessary, converting feature points associated with said first image to the coordinate system of the second image; and 
 (B)(2) for each transformed feature point associated with said first image attempting to find at least one feature point associated with the second image that has a distance to the transformed feature point of less than a first particular threshold and a Euclidian distance to the transformed feature point of less than a second particular threshold. 
 
     
     
         11 . The method of  claim 1  wherein said attempting to boost in (C) is performed in the coordinate system of the first image, and wherein the selectively producing a transformed image in (B) comprises:
 (B)(1) if necessary, converting feature points associated with said second image to the coordinate system of the first image; and 
 (B)(2) for each transformed feature point associated with said first second attempting to find at least one feature point associated with the first image that has a distance to the transformed feature point of less than a first particular threshold and a Euclidian distance to the transformed feature point of less than a second particular threshold. 
 
     
     
         12 . The method of  claim 1  wherein said first image is a template image and wherein said second image is a test image. 
     
     
         13 . The method of  claim 12  comprising:
 repeating the method for multiple template images and multiple test images. 
 
     
     
         14 . The method of  claim 12  wherein said template image is associated with a particular entity and wherein said determining in (D) is used to provided targeted advertising on behalf of said particular entity. 
     
     
         15 . A computer-implemented method for determining whether a portion of a first image is located within a second image, the method, implemented by hardware in combination with software, the method comprising:
 (A) determining a set of candidate matching feature points from a first set of feature points associated with said first image and a second set of feature points associated with said second image;   (B) selectively producing a transformed image by transforming one of: (i) said first image into a first different coordinate system, and (ii) said second image into a second different coordinate, said transforming being based on a relationship of said candidate matching feature points; and   (C) attempting to boost said set candidate matching feature points to include additional candidate feature points associated with said first image and said second image, said attempting being based on (i) said candidate matching feature points and (ii) said transformed image; and then   (D) determining whether said portion of said first image is located within said second image based on a size of said set candidate matching feature points.   
     
     
         16 . The method of  claim 15  wherein, when said first different coordinate system is the coordinate system of said second image. 
     
     
         17 . The method of  claim 15  wherein, when said second different coordinate system is the coordinate system of said first image. 
     
     
         18 . A computer-implemented method for determining whether a portion of a first image is located within a second image, the method, implemented by hardware in combination with software, the method comprising:
 (A) determining a set of candidate matching feature points from a first set of feature points associated with said first image and a second set of feature points associated with said second image;   (B) selectively transforming one of: (i) said set of candidate matching feature points into a first different coordinate system, and (ii) said second set of feature points into a second different coordinate, said transforming being based on a relationship of said candidate matching feature points; and   (C) attempting to boost said set candidate matching feature points to include additional candidate feature points associated with said first image and said second image, said attempting being based on (i) said candidate matching feature points and (ii) said transformed image; and then   (D) determining whether said portion of said first image is located within said second image based on a size of said set candidate matching feature points.   
     
     
         19 . The method of  claim 18  wherein, when said first different coordinate system is the coordinate system of said second image. 
     
     
         20 . The method of  claim 18  wherein, when said second different coordinate system is the coordinate system of said first image.