Sketch segmentation

• US 9,183,467 B2
• Filed: 05/03/2013
• Issued: 11/10/2015
• Est. Priority Date: 05/03/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Wang, Changhu, Zhang, Lei, Sun, Zhenbang
• Primary Examiner(s): Chu, Randolph I
• Application Number:
  US13/886,862
• Publication Number:
  US 20140328540A1
• Time in Patent Office: 921 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06V 30/274 Syntactic or semantic context, e.g. balancing
• CPC Class Codes: G06V 30/422 Technical drawings; Geographical maps

Abstract

Some examples of a sketch-based image segmentation system may segment a hand-drawn sketch based on proximity, intuitive clues and semantic information. For instance, the system may cluster line segments of the sketch if the line segments are within a threshold distance. Further, the system may cluster line segments of the sketch based on a set of intuitive clues. In some implementations, a sketch-based search engine may be utilized to search an image collection to identify images with shape features similar to the sketch and to segment the sketch based on the semantic information associated with the identified images.

Claims

1. A system comprising:

one or more input interfaces for receiving a sketch including at least one object;

one or more processors; and

a computer-readable storage media storing instructions, which when executed by the one or more processors, cause the one or more processors to segment the sketch into objects by;

selecting a line segment from a plurality of line segments as a first line segment of a cluster of line segments;

selecting a second line segment from the plurality of line segments and merging the second line segment with the cluster of line segments when the second line segment is less than a threshold distance from the line segments of the cluster;

comparing unmerged line segments according to rules and merging the unmerged line segments with the cluster of line segments when the unmerged line segments satisfy at least one of the rules;

searching for images similar to the cluster of line segments from a collection of identified images;

calculating an entropy value for the cluster of line segments based at least in part on identified images; and

classifying the cluster of line segments as an object of the sketch based at least in part on the entropy value and the identified images.

2. The system of claim 1, wherein the identified images include associated text and the entropy value is based at least in part on a word score determined from the associated text.

3. The system of claim 1, wherein images within the collection of images are retrieved by a web-crawler.

4. The system of claim 1, wherein the collection of images is accessed via one or more communication interfaces.

5. The system of claim 1, wherein the rules comprise at least one of:

analyzing similarity between strokes of the line segments of the cluster of line segments and strokes of the unmerged line segments;

comparing a direction of the line segments of the cluster and a direction of the unmerged line segments;

comparing a symmetry value of the cluster of line segments without the unmerged line segments to a symmetry value of the cluster of line segments including at least one of the unmerged line segments;

determining if the cluster of line segments encloses at least one of the unmerged line segments;

determining if merging at least one of the unmerged line segments increases closure of the cluster of line segments;

comparing a compactness value of the cluster of line segments without the unmerged line segments to a compactness value of the cluster of line segments including at least one of the unmerged line segments;

comparing a length of the line segments of the cluster and a length of the unmerged line segments;

comparing a convex hull value of the cluster of line segments without the unmerged line segments to a convex hull value of the cluster of line segments including at least one of the unmerged line segments; and

comparing the unmerged line segments based a bounding box formed around the cluster of line segments.

6. The system of claim 1, further comprising one or more output interfaces for providing the object to a user.

7. A method comprising:

receiving a sketch including a plurality of line segments;

generating combinations of line segments from the plurality of line segments and for at least one of the combinations of line segments;

querying a collection of images using the combination of line segments as an input and receiving a set of images in response, at least one image of the set of images including associated text identifying objects in the images;

calculating an entropy value for the combination of line segments based at least in part the set of images and the associated text; and

determining if the combination of line segments is an object based on the entropy value.

8. The method of claim 7, further comprising:

calculating a word score based at least in part on the associated text; and

wherein the entropy value is based at least in part on the word score.

9. The method of claim 7, wherein the set of images are clipart images.

10. The method of claim 7, wherein the combination of line segments is the object if the entropy value is less than a threshold.

11. The method of claim 7, wherein the combination of line segments is the object if the combination of line segments has a lowest entropy value out of at least one of the combination of line segments.

12. The method of claim 7, wherein the calculating the entropy value for the combination of line segments includes adjusting the entropy value based on a length of at least one of the line segments.

13. The method of claim 7, wherein the querying the collection of images includes submitting the combination of line segments to a sketch-based search engine.

14. The method of claim 7, wherein the combination of line segments is generated by merging line segments within a threshold distance of the cluster into the combination of line segments.

15. The method of claim 7, wherein the combination of line segments is generated by selecting line segments according to at least one of similarity in stroke, continuity of direction, symmetry, closure, compactness, similarity in lengths or bounding boxes.

16. A computer-readable storage media storing instructions that, when executed by one or more processors, cause the one or more processors to perform operations comprising:

receiving one or more line segments corresponding to a sketch;

segmenting at least a portion of the sketch into an object by merging the one or more line segments of the sketch into the object based at least in part on comparing the line segments of the object and a line segment to be merged;

calculating an entropy value for the one or more merged line segments based at least in part on identified images; and

classifying the one or more merged line segments as an object of the sketch based at least in part on the entropy value and the identified images.

17. The computer-readable storage media of claim 16, wherein the comparing further comprises:

selecting a plurality of sub-strokes from the line segments of the object and the line segment to be merged;

determining an orientation of at least one of the sub-strokes;

calculating a feature vector based on the orientations; and

determining a similarity feature value based on the feature vectors.

18. The computer-readable storage media of claim 16, wherein the comparing further comprises:

selecting a first point on the object that is closest to the line segment to be merged;

selecting a second point on the line segment to be merged;

determining an orientation at the first point and the second point; and

comparing the orientations.

19. The computer-readable storage media of claim 16, wherein the comparing is based on at least one of comparing:

a similarity in strokes of the line segments of the object and the line segment to be merged;

a continuity of directions between the line segments of the object and the line segment to be merged;

symmetry of the object including the line segments of the object and the line segment to be merged;

closure of the object including the line segments of the object and the line segment to be merged;

compactness of the object including the line segments of the object and the line segment to be merged;

or

similarity in lengths of the line segments of the object and the line segment to be merged.