Flexible matching with combinational similarity

• US 8,184,911 B2
• Filed: 04/22/2011
• Issued: 05/22/2012
• Est. Priority Date: 05/02/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ofek, Eyal, Mishra, Pragyana, Wexler, Yanatan
• Primary Examiner(s): CHAWAN, SHEELA C
• Application Number:
  US13/092,416
• Publication Number:
  US 20110200252A1
• Time in Patent Office: 396 Days
• Field of Search: 382/209, 382/164, 382/171, 382/173, 382/190, 382/219, 382/305, 382/154, 382/214, 382/218, 382/220, 382/227, 382/278, 382/270, 382/180, 382/304, 382/168.19, 715/835, 435/7.93, 436/501, 436/518, 359/561, 707/E17.058, 707/E17.005, 707/999.006, 707/E17.023, 707/E17.024, 707/E17.025, 707/E17.021, 707/999.003
• US Class Current: 382/209
• CPC Class Codes: G06V 10/50 by performing operations within image blocks; by using histograms, e.g. histogram of oriented gradients [HoG]; by summing image-intensity values; Projection analysis

Abstract

Computer-readable media, systems, and methods for flexible matching with combinational similarity are described. In embodiments, an object image is received, a query image is received, and the query image is compared with the object image. In various embodiments matching information is determined based upon combinational similarity and the matching information is presented to a user. In various embodiments, comparing the query image with the object image includes dividing the object image into agents, creating a gradient histogram for the agents, determining map areas for the query image, creating a gradient histogram for the map areas, and creating a similarity array for each of the agents. Further, in various embodiments, determining matching information includes creating a combinational array by combining the similarity arrays for each agent and determining whether the combinational array includes a peak value.

Claims

1. A computer-implemented method for flexible matching with combinational similarity, comprising:

receiving an object image;

receiving a query image including one or more pixels;

comparing the query image with the object image;

determining one or more matching information based upon combinational similarity, the combinational similarity being a combination of one or more similarity arrays created by comparing one or more gradient histogram information associated with the object image to the one or more gradient histogram information associated with the query image; and

presenting the one or more matching information to a user.

2. The method of claim 1, wherein comparing the query image with the object image using combinational similarity comprises:

dividing the object image into one or more agents;

creating a gradient histogram for the one or more agents;

determining one or more map areas, each map area corresponding to each of the one or more pixels of the query image;

creating a gradient histogram for the one or more map areas; and

creating a similarity array for each of the one or more agents.

3. The method of claim 2, wherein creating a similarity array for each of the one or more agents comprises:

for each agent, comparing the gradient histogram for one of the one or more agents to the gradient histogram for each of the one or more map areas;

wherein the similarity array includes one or more elements, each element associated with a corresponding pixel of the one or more pixels, and

wherein each element of the similarity array represents a similarity between the gradient histogram for the one of the one or more agents and the gradient histogram for the corresponding pixel.

4. The method of claim 2, wherein the gradient histogram for the one or more agents include one or more bin values based upon the properties of the one or more agents.

5. The method of claim 4, wherein the gradient histogram for the one or more map areas include one or more bin values based upon the properties of the one or more map areas.

6. The method of claim 5, wherein the gradient histogram for the one or more agents and the gradient histogram for the one or more map areas include five bin values.

7. The method of claim 1, wherein the object image includes a logo.

8. A computerized system for flexible matching with combinational similarity, the system including one or more processors and comprising:

a receiving component configured to receive an object image and a query image;

a dividing component configured to divide the object image into one or more agents;

a map area component configured to determine one or more map areas, each map area corresponding to a pixel of the query image;

a histogram component configured to create a gradient histogram for the one or more agents and a gradient histogram for the one or more map areas;

a comparing component configured to compare the query image with the object image;

a determining component configured to determine one or more matching information based upon combinational similarity; and

a database for storing information associated with the object image and the query image.

9. The system of claim 8, wherein the comparing component is further configured to create a similarity array for each of the one or more agents by, for each agent, comparing the gradient histogram for one of the one or more agents to the gradient histogram for each of the one or more map areas.

10. The system of claim 9, further comprising:

a combinational component configured to combine the similarity array for each of the one or more agents; and

a peak value component configured to determine whether an instance of the object image exists in the query image.

11. The system of claim 10, further comprising a presentation component configured to present the one or more matching information to a user.

12. The system of claim 11, wherein if the peak value component determines an instance of the object image exists in the query image, the presentation component will present to the user an indication that the object image exists within the query image and the presentation component will further present to the user the location of the object image within the query image.

13. The system of claim 11, wherein if the peak value component determines that no instance of the object image exists in the query image, the presentation component will present to the user an indication that the object image does not exist within the query image.

14. One or more computer storage media, the computer storage media not being a signal per se, having instructions embodied thereon that, when executed, perform a method for flexible matching with combinational similarity, the method comprising:

receiving one or more object images;

receiving one or more query images; and

processing the one or more object images and the one or more query images using combinational similarity,

wherein processing the one or more object images and the one or more query images using combinational similarity comprises combining one or more similarity arrays created by comparing one or more gradient histogram information associated with the one or more object images to one or more gradient histogram information associated with the one or more query images.

15. The one or more computer storage media of claim 14, wherein processing the one or more object images and the one or more query images using combinational similarity comprises:

dividing the one or more object images into one or more agents;

creating a gradient histogram for the one or more agents;

determining one or more map areas, each map area corresponding to each of one or more pixels of the one or more query images;

creating a gradient histogram for the one or more map areas; and

creating a similarity array for each of the one or more agents.

16. The one or more computer storage media of claim 15, wherein creating a similarity array for each of the one or more agents comprises:

for each agent, comparing the gradient histogram for one of the one or more agents to the gradient histogram for each of the one or more map areas;

wherein the similarity array includes one or more elements, each element associated with a corresponding pixel of the one or more pixels, and

wherein each element of the similarity array represents a similarity between the gradient histogram for the one of the one or more agents and the gradient histogram for the corresponding pixel.

17. The one or more computer storage media of claim 16, wherein processing the one or more object images and the one or more query images using combinational similarity further comprises:

creating a combinational array by combining the similarity array for each of the one or more agents; and

determining whether the combinational array includes a peak value indicating an instance of the object image in the query image.

18. The one or more computer storage media of claim 14, wherein the gradient histogram for the one or more agents include one or more bin values based upon the properties of the one or more agents, and wherein the gradient histogram for the one or more map areas include one or more bin values based upon the properties of the one or more map areas.

19. The one or more computer storage media of claim 14,

wherein the one or more object images include one or more input images submitted to an image search,

wherein the one or more query images include one or more search images stored in association with a image search index, and

wherein processing the one or more object images and the one or more query images using combinational similarity further comprises searching for an instance of the one or more input images in the one or more search images.

20. The one or more computer storage media of claim 14,

wherein the one or more query images include one or more frames of video data, and

wherein processing the one or more object images and the one or more query images using combinational similarity further comprises tracking the one or more object images through a video stream by identifying the one or more object images in the one or more frames of video data.