Sketch-based image search

• US 9,449,026 B2
• Filed: 08/31/2010
• Issued: 09/20/2016
• Est. Priority Date: 08/31/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Wang, Changhu, Li, Zhiwei, Zhang, Lei
• Primary Examiner(s): KINSAUL, DANIEL W
• Application Number:
  US12/873,007
• Publication Number:
  US 20120054177A1
• Time in Patent Office: 2,212 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/532 Query formulation, e.g. graphical querying
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06V 30/32 Digital ink

Abstract

Sketch-based image search may include receiving a query curve as a sketch query input and identifying a first plurality of oriented points based on the query curve. The first plurality of oriented points may be used to locate at least one image having a curve that includes a second plurality of oriented points that match at least some of the first plurality of oriented points. Implementations also include indexing a plurality of images by identifying at least one curve in each image and generating an index comprising a plurality of oriented points as index entries. The index entries are associated with the plurality of images based on corresponding oriented points in the identified curves in the images.

Claims

1. A system comprising:

a processor in communication with computer-readable storage media;

a down-sampling component to reduce resolution of a plurality of images to generate a plurality of down-sampled images;

an index maintained in the computer-readable storage media, the index comprising a first set of direction-oriented points associated with a subset of image curves detected for the plurality of down-sampled images, individual of the direction-oriented points specifying a position of a particular point of an image and a direction from which an associated image curve passes the position, wherein the subset of image curves for a particular down-sampled image includes one or more salient curves identified by filtering the image curves detected for the particular down-sampled image to remove image curves having a length less than a predetermined threshold;

a user interface component to receive a query curve as a search query input; and

a salient curve component to;

determine that a length of the query curve is above a threshold length; and

in response to determining that the length of the query curve is above the threshold length, divide the query curve into a plurality of sub-query curves, each of the plurality of sub-query curves being treated as the sketch query input.

2. The system according to claim 1, further comprising:

a matching component, maintained in the computer-readable storage media and executed on the processor, for matching a subset of a second set of direction-oriented points based at least in part on the query curve with the first set of direction-oriented points associated with the plurality of down-sampled images, the matching component configured for identifying images of the plurality of down-sampled images based at least in part on the matching, wherein the matching component generates a distance map for the query curve, the distance map representing the query curve as the second set of direction-oriented points.

3. The system according to claim 2, wherein the distance map generated for the query curve includes a tolerance value that specifies a predetermined range of oriented points in an area around the query curve to be used in the matching.

4. The system according to claim 1, wherein:

the user interface component is configured to receive at least one of a text-based query or a color-based query in conjunction with the query curve as the search query input; and

the matching component is configured to identify one or more additional images based on at least one of the text-based query or the color-based query, and combine a ranking score of the one or more additional images with a ranking score of a plurality of images identified based on the query curve to identify a plurality of ranked images as a search result.

5. The system according to claim 1, further comprising an indexing component for generating the index based, at least in part, on the plurality of down-sampled images, the indexing component generating the index by relating the first set of direction-oriented points with image identifiers based at least in part on the one or more salient image curves.

6. The system of claim 1, further comprising:

a color index maintained in the computer-readable storage media, the color index providing a plurality of colors as color index entries, wherein one or more down-sampled images of the plurality of down-sampled images are associated with at least one color index entry based at least in part on one or more dominant colors detected in the one or more down-sampled images;

wherein the user interface component is further configured to receive a color query input; and

wherein the matching component is further configured for identifying the down-sampled images based at least in part on matching a color specified by the color query input with the color index.

7. The system of claim 1, further comprising:

a text index maintained in the computer-readable storage media, the text index providing a plurality of keywords as text index entries, wherein one or more down-sampled images of the plurality of down-sampled images are associated with at least one text index entry based at least in part on text detected in the one or more down-sampled images;

wherein the user interface component is further configured to receive a text query input; and

wherein the matching component is further configured for identifying the down-sampled images based at least in part on matching the text query input with the text index.

8. A method comprising:

receiving a first continuous curve;

receiving a second continuous curve;

determining that a length of the first continuous curve is less than a threshold length; and

in response to the determining that the length of the first continuous curve is less than the threshold length, including the first continuous curve with the second continuous curve to create a query curve as a sketch query input;

identifying a first plurality of direction-oriented points based at least in part on the query curve, wherein each direction-oriented point of the first plurality of direction-oriented points specifies a position of a particular point of the sketch query input and a direction from which the query curve passes the position; and

using, by a processor, the first plurality of direction-oriented points to locate at least one down-sampled image having a salient curve that includes a second plurality of direction-oriented points that match a portion of the first plurality of direction-oriented points based at least in part on the query curve, wherein one or more salient curves for a particular down-sampled image are identified by filtering image curves detected for the particular down-sampled image to remove image curves having a length less than a predetermined threshold.

9. The method according to claim 8, wherein a plurality of down-sampled images is located based on the first plurality of direction-oriented points, the method further comprising:

generating one or more distance maps for image curves in individual down-sampled images of the plurality of down-sampled images;

calculating a similarity between the query curve and the generated distance maps; and

ranking the individual down-sampled images of the plurality of down-sampled images based at least in part on the calculated similarity.

10. The method according to claim 8, wherein a first plurality of images is located in a database of images based on the first plurality of direction-oriented points, the method further comprising:

matching the query curve with distance maps generated for image curves identified in individual images in the database of images to obtain a second plurality of images; and

identifying a third plurality of images from the first plurality of images and the second plurality of images as results in response to the sketch query input.

11. The method according to claim 8, wherein identifying a first plurality of direction-oriented points based on the query curve further comprises generating one or more distance maps for the query curve, each distance map representing a curve portion having a determined direction, the distance map identifying a subset of the first plurality of direction-oriented points having the determined direction, the distance map including a tolerance radius in an area around the curve portion for identifying a group of direction-oriented points in a vicinity of the curve included in the first subset.

12. The method according to claim 8, further comprising:

determining that a length of the query curve is above a threshold length; and

in response to determining that the length of the query curve is above the threshold length, dividing the query curve into a plurality of sub-query curves, each of the plurality of sub-query curves being treated as the sketch query input.

13. The method according to claim 12, wherein the dividing is based at least in part on distinguishable strokes made when drawing the query curve.

14. The method according to claim 8, wherein using the first plurality of direction-oriented points to locate at least one down-sampled image further comprises employing an index including the second plurality of direction-oriented points as index entries associated with a plurality of down-sampled images based on the images containing salient curves having corresponding direction-oriented points.

15. The method according to claim 14, further comprising generating the index to include the second plurality of direction-oriented points as index entries, wherein the second plurality of direction-oriented points corresponds to points of resolution of an input panel of a user interface configured for receiving a sketched curve as the query curve.

16. The method according to claim 8, further comprising:

providing the at least one located down-sampled image as feedback in response to the sketch query input;

receiving a modification to the query curve;

providing different images as feedback in response to the modification to the query curve.

17. One or more computer storage media storing computer-executable instructions that, when executed on one or more processors, cause the one or more processors to perform acts comprising:

receiving a query curve as a sketch query input;

determining that a length of the query curve is greater than a threshold;

in response to determining that the length of the query curve is greater than the threshold, identifying a first portion of the query curve as a first query curve and a second portion of the query curve as a second query curve;

identifying a first plurality of direction-oriented points based at least in part on the first query curve, wherein each direction-oriented point of the first plurality of direction-oriented points specifies a position of a particular point of the sketch query input and a direction from which the first query curve passes the position; and

identifying a down-sampled image having a salient curve that includes a second plurality of direction-oriented points that match a subset of the first plurality of direction-oriented points, wherein one or more salient curves for the down-sampled image are identified by filtering image curves detected for the down-sampled image to remove image curves having a length less than a predetermined threshold.

18. The one or more computer storage media of claim 17, wherein the first plurality of direction-oriented points correspond to points of resolution of an input panel of a user interface configured to receive a sketched curve as the query curve.

19. The one or more computer storage media of claim 17, wherein the acts further comprise:

receiving at least one of a text-based query or a color-based query in conjunction with the query curve as the search query input;

identifying one or more additional images based on at least one of the text-based query or the color-based query; and

combining a ranking score of the one or more additional images with a ranking score of a plurality of images identified based on the query curve to identify a plurality of ranked images as a search result.