Smart Scribbles for Sketch Segmentation

• US 20130241934A1
• Filed: 03/19/2012
• Published: 09/19/2013
• Est. Priority Date: 03/19/2012
• Status: Active Grant

• Current Assignee: Disney Enterprises Incorporated (The Walt Disney Company)
• Original Assignee: Disney Enterprises Incorporated (The Walt Disney Company)
• Inventors: Shamir, Ariel, Hornung, Alexander, Sumner, Robert, Simmons, Maryann, Gross, Markus, Norris, Gioacchino, Sykora, Daniel, Coros, Stelian, Whited, Brian
• Granted Patent: US 9,082,005 B2
• Time in Patent Office: Days
• US Class Current: 345/442
• CPC Class Codes: G06F 18/2323 based on graph theory, e.g. minimum spanning trees [MST] or graph cuts
• CPC Class Codes: G06V 30/347 Sampling; Contour coding; Stroke extraction

Abstract

A method is provided for sketch segmentation via smart scribbles, the results of which are especially suitable for interactive real-time graphics editing applications. A vector-based drawing may be segmented into labels based on input scribbles provided by a user. By organizing the labeling as an energy minimization problem, an approximate solution can be found using a sequence of binary graph cuts for an equivalent graph, providing an optimized implementation in a polynomial time suitable for real-time drawing applications. The energy function may include time, proximity, direction, and curvature between strokes as smoothness terms, and proximity, direction, and oriented curvature between strokes and scribbles as data terms. Additionally, the energy function may be modified to provide for user control over locality control, allowing the selection of appropriately sized labeling regions by scribble input speed or scribble input pressure. Once the drawing is labeled, a wide range of drawing applications are enabled.

Claims

1. A method for providing sketch segmentation via smart scribbles, the method comprising:

retrieving user sketch data comprising a plurality of strokes;

receiving at least one input scribble for segmenting the user sketch data;

minimizing an energy function to assign a plurality of labels to the plurality of strokes, the energy function having;

a data term measuring an affinity between the plurality of strokes and the at least one input scribble; and

a smoothness term measuring a cost of selecting a label with respect to a similarity between two strokes within the plurality of strokes;

showing, on a display, the assigning of the plurality of labels to the plurality of strokes.

2. The method of claim 1, wherein the minimizing of the energy function assigns a portion of the plurality of strokes to a background label based on an input speed or an input pressure of the at least one input scribble.

3. The method of claim 1, wherein the minimizing is by a plurality of binary graph cuts.

4. The method of claim 1, wherein the user sketch data and the at least one input scribble are resampled into smaller segments prior to the minimizing.

5. The method of claim 1, wherein the smoothness term includes a time term between the two strokes.

6. The method of claim 1, wherein the smoothness term includes a proximity term between the two strokes.

7. The method of claim 1, wherein the smoothness term includes a direction term and a curvature term between the two strokes.

8. The method of claim 1, wherein the data term includes a proximity term between the plurality of strokes and the at least one input scribble.

9. The method of claim 1, wherein the data term includes a direction term between the plurality of strokes and the at least one input scribble.

10. The method of claim 1, wherein the data term includes an oriented curvature term between the plurality of strokes and the at least one input scribble.

11. A computing device providing sketch segmentation via smart scribbles, the computing device including a processor configured to:

retrieve user sketch data comprising a plurality of strokes;

receive at least one input scribble for segmenting the user sketch data;

minimize an energy function to assign a plurality of labels to the plurality of strokes, the energy function having;

a data term measuring an affinity between the plurality of strokes and the at least one input scribble; and

a smoothness term measuring a cost of selecting a label with respect to a similarity between two strokes within the plurality of strokes;

show, on a display, the assigning of the plurality of labels to the plurality of strokes.

12. The computing device of claim 11, wherein the processor is configured to minimize the energy function to assign a portion of the plurality of strokes to a background label based on an input speed or an input pressure of the at least one input scribble.

13. The computing device of claim 11, wherein the processor is configured to minimize by a plurality of binary graph cuts.

14. The computing device of claim 11, wherein prior to the minimizing the processor is configured to resample the user sketch data and the at least one input scribble into smaller segments.

15. The computing device of claim 11, wherein the smoothness term includes a time term, a proximity term, a direction term, and a curvature term between the two strokes.

16. The computing device of claim 11, wherein the data term includes a proximity term, a direction term, and an oriented curvature term between the plurality of strokes and the at least one input scribble.

17. A system for providing sketch segmentation via smart scribbles, the system comprising:

a display;

an input device;

a computing device having a processor configured to;

retrieve, from the input device, user sketch data comprising a plurality of strokes;

receive, from the input device, at least one input scribble for segmenting the user sketch data;

minimize an energy function to assign a plurality of labels to the plurality of strokes, the energy function having;

a data term measuring an affinity between the plurality of strokes and the at least one input scribble; and

a smoothness term measuring a cost of selecting a label with respect to a similarity between two strokes within the plurality of strokes;

show, on the display, the assigning of the plurality of labels to the plurality of strokes.

18. The system of claim 17, wherein the input device is a pen tablet.

19. The system of claim 17, wherein the smoothness term includes a time term, a proximity term, a direction term, and a curvature term between the two strokes.

20. The system of claim 17, wherein the data term includes a proximity term, a direction term, and an oriented curvature term between the plurality of strokes and the at least one input scribble.