Curve generation for sketch vectorization

Patent metadata

Field	Value
Publication number	US-12333634-B2
Application number	US-202117519357-A
Country	US
Kind code	B2
Filing date	Nov 4, 2021
Priority date	Nov 4, 2021
Publication date	Jun 17, 2025
Grant date	Jun 17, 2025

Abstract

Generating a vector representation of a hand-drawn sketch is described. To do so, the sketch is segmented into different superpixel regions. Superpixels are grown by distributing superpixel seeds throughout an image of the sketch and assigning unassigned pixels to a neighboring superpixel based on pixel value differences. The border between each pair of adjacent superpixels is then classified as either an active or an inactive boundary, with active boundaries indicating that the border corresponds to a salient sketch stroke. Vector paths are generated by traversing edges between pixel vertices along the active boundaries. To minimize vector paths included in the vector representation, vector paths are greedily generated first for longer curves along active boundaries until each edge is assigned to a vector path. Regions encompassed by vector paths corresponding to a foreground superpixel are filled to produce a high-fidelity vector representation of the sketch.

First claim

What is claimed is:

1. A method implemented by at least one computing device, the method comprising:
receiving, by the at least one computing device, an input image;
distributing, by the at least one computing device, superpixel seeds throughout the input image;
growing, by the at least one computing device, superpixels from the superpixel seeds while maintaining a position of the superpixel seeds and a spacing between the superpixel seeds throughout the growing by assigning respective pixels in the input image to the superpixel seeds, pixels assigned to one of the superpixel seeds being separate from pixels assigned to other superpixel seeds throughout the growing;
classifying, by the at least one computing device, a border between adjacent said superpixels grown from the superpixel seeds as an active boundary representing a salient curve in the input image;
generating, by the at least one computing device, a vector path along the border; and
outputting, by the at least one computing device, the vector path as a vector representation of the input image.

2. The method of claim 1 , wherein, for each superpixel seed:
the superpixel seed is classified as a foreground superpixel seed or a background superpixel seed based on an underlying pixel value of a corresponding location in the input image for the superpixel seed.

3. The method of claim 2 , wherein, for each superpixel seed:
the classifying as the foreground superpixel seed occurs is in response to determining that the underlying pixel value is less than or equal to 0.5; and
the classifying as the background superpixel seed is in response to determining that the underlying pixel value is greater than 0.5.

4. The method of claim 2 , wherein distributing the superpixel seeds comprises spacing background superpixel seeds from other background superpixel seeds at a first distance, spacing foreground superpixel seeds from other foreground superpixel seeds at the first distance, and spacing background superpixel seeds from foreground superpixel seeds at least at a second distance, where the first distance is an exact number of pixels.

5. The method of claim 1 , wherein assigning respective pixels in the input image to the superpixel seeds comprises determining a cost associated with assigning one of the respective pixels to each neighboring pixel already assigned to one of the superpixel seeds and assigning the one of the respective pixels based on lowest associated cost.

6. The method of claim 5 , wherein determining the cost associated with assigning the one of the respective pixels to one of the neighboring pixels already assigned to one of the superpixel seeds comprises determining a pixel value difference between the one of the respective pixels and the one of the neighboring pixels already assigned to one of the superpixel seeds.

7. The method of claim 5 , further comprising designating the lowest associated cost as a cumulative cost for the one of the respective pixels responsive to assigning the one of the respective pixels to one of the superpixel seeds.

8. The method of claim 7 , wherein the cumulative cost further reflects one or more cumulative costs associated with one or more intervening pixels connecting the one of the respective pixels to the one of the superpixel seeds.

9. The method of claim 1 , wherein classifying the border between adjacent said superpixels as the active boundary comprises comparing a difference between cumulative costs associated with pixels along the border to a boundary threshold.

10. The method of claim 1 , further comprising identifying a region encompassed by the vector path as corresponding to a foreground superpixel and assigning a pixel value associated with the foreground superpixel to pixels included in the region.

11. The method of claim 1 , further comprising generating a grayscale version of the input image, the grayscale version of the input image including pixels having a first intensity representing one or more strokes in the input image and pixels having a second intensity representing a medium conveying the one or more strokes in the input image, wherein distributing the superpixel seeds comprises distributing the superpixel seeds throughout the grayscale version of the input image.

12. The method of claim 1 , wherein assigning respective pixels in the input image to the superpixel seeds comprises:
initializing a priority queue including entries representing costs for assigning the respective pixels to the superpixel seeds;
determining the costs for one or more of the respective pixels adjacent to the superpixel seeds and updating corresponding entries in the priority queue based on the costs;
ordering the entries in the priority queue to prioritize assignment of a first respective pixel of the respective pixels associated with an entry of the entries representing a lowest cost of the costs; and
assigning the first respective pixel to a first superpixel seed of the superpixel seeds.

13. The method of claim 12 , further comprising:
responsive to assigning the first respective pixel to the first superpixel seed:
determining a cost for assigning a second respective pixel to the first superpixel seed, the cost based at least in part on the assigning of the first respective pixel to the first superpixel seed;
updating the ordering of the entries in the priority queue based on the cost for assigning the second respective pixel to the first superpixel seed; and
assigning the second respective pixel or another respective pixel to one of the superpixel seeds based on the updated ordering.

14. The method of claim 1 , further comprising:
determining a contiguous plurality of pixels of the input image associated with the border and a plurality of vertices corresponding to the plurality of pixels, where each vertex of the plurality of vertices is at a corner of a corresponding pixel of the plurality of pixels, and each vertex is along the active boundary;
determining an endpoint vertex of the plurality of vertices, where the endpoint vertex is adjacent to a single other vertex of the plurality of vertices; and
generating the vector path along the border includes forming edges between pairs of adjacent vertices of the plurality of vertices along the active boundary, where forming the edges includes:
forming a first edge from the endpoint vertex to the single other vertex adjacent to the endpoint vertex along the active boundary; and
beginning from the single other vertex at the first edge, forming subsequent contiguous additional edges between subsequent pairs of adjacent vertices of the plurality of vertices along the active boundary, where, for each additional edge of the additional edges, a direction of the additional edge is selected to correspond to a direction of another edge adjacent to the additional edge and formed previously to the additional edge.

15. One or more computer-readable storage media storing instructions that are executable by a computing device to perform operations comprising:
receiving an input image segmented into a plurality of regions;
classifying a border between an adjacent pair of regions in the plurality of regions as an active boundary representing a transition between foreground content of the input image and background content of the input image;
generating at least one vector path using edges between pixel vertices disposed on the border while the border is classified as the active boundary; and
outputting the at least one vector path as a vector representation of the input image in an order of strokes of the input image.

16. The one or more com

Assignees

• Adobe Inc

Inventors

• Chandil Ashwani
• Batra Vineet
• Fisher Matthew David
• Aneja Deepali
• Phogat Ankit

Classifications

• G06T11/23 Primary

  using straight lines or curves · CPC title

• G06V10/457 Primary

  by analysing connectivity, e.g. edge linking, connected component analysis or slices · CPC title

• G06T7/12

  Edge-based segmentation · CPC title

• G06T7/181

  involving edge growing; involving edge linking · CPC title

• G06T7/194

  involving foreground-background segmentation · CPC title