Coordinated piecewise Bezier vectorization

Patent metadata

Field	Value
Publication number	US-10743035-B2
Application number	US-201916279856-A
Country	US
Kind code	B2
Filing date	Feb 19, 2019
Priority date	Nov 17, 2015
Publication date	Aug 11, 2020
Grant date	Aug 11, 2020

Abstract

This application is directed to vectoring a raster image in which an electronic device detects a contour of a component in the raster image, builds tangent vectors for each point of the contour and identifies a plurality of segmentation points on the contour. One or more points of sharp angle are identified on the contour in accordance with a determination that each point of sharp angle corresponds to two distinct tangent vectors and that an angle between the two distinct tangent vectors falls below a predefined threshold. A respective one of the segmentation points is positioned at each identified point of shape angle. The electronic device approximates a piecewise smooth fitting curve (e.g., a piecewise Bezier curve) having two or more fitting segments to connect the plurality of segmentation points on the contour. The piecewise smooth fitting curve is thereby provided to vectorize the raster image.

First claim

What is claimed is:

1. A method of vectorizing a raster image, comprising:
at an electronic device including one or more processors and memory:
detecting a contour of a component in the raster image;
building tangent vectors for each point of the contour;
identifying a plurality of segmentation points on the contour, the plurality of segmentation points including one or more first segmentation points, including:
identifying one or more points of sharp angle on the contour in accordance with a determination that each of the one or more points of sharp angle has two distinct left and right tangent vectors originating from the respective point of sharp angle and that an angle between the two distinct left and right tangent vectors of each of the one or more points of sharp angle falls below a first predefined threshold; and
positioning a respective one of the one or more first segmentation points at each identified point of sharp angle, each point of sharp angle connecting two first segments on the contour;

approximating a piecewise smooth fitting curve to connect the plurality of segmentation points on the contour, the piecewise smooth fitting curve including two or more fitting segments each of which is configured to connect two neighboring points of the plurality of segmentation points; and
in accordance with the piecewise smooth fitting curve, providing a vectorization of the raster image.

2. The method of claim 1 , wherein the plurality of segmentation points including one or more second segmentation points, and identifying the plurality of segmentation points on the contour further includes:
identifying one or more locations of high curvature in accordance with a determination that a change of direction of the tangent vectors at each location of high curvature exceeds a second predefined threshold;
for each of the one or more locations of high curvature, positioning two second segments proximal to each location of high curvature to connect the respective location of high curvature to second segmentation points on the contour.

3. The method of claim 2 , wherein the second predefined threshold corresponds to an angle between two tangent vectors of points on each location of high curvature that are twenty pixels apart, the angle being greater than 90 degrees.

4. The method of claim 1 , further comprising:
in accordance with a determination that the piecewise smooth fitting curve does not match the contour, adding one or more segmentation points to create additional segments.

5. The method of claim 4 , further comprising:
determining that the piecewise smooth fitting curve does not match the contour in accordance with a determination determining a deviation of the piecewise smooth fitting curve from the contour exceeds a predefined deviation threshold.

6. The method of claim 5 , wherein the predefined deviation threshold corresponds to a root mean square of the deviation of the piecewise smooth fitting curve being greater than two pixels.

7. The method of claim 1 , further comprising:
minimizing a root-mean square deviation of the piecewise smooth fitting curve from the contour; and
providing continuity and smooth conjugation of adjacent ones of the fitting segments, of the piecewise smooth fitting curve, that are not connected to any of the one or more points of sharp angle on the contour.

8. The method of claim 1 , further comprising:
providing a root-mean square deviation of the piecewise smooth fitting curve from the contour, wherein the root-mean square deviation is minimized using a formula of:

∑

i
,
j

⁢



B
⁡

(

t
j
i

)

-

C
⁡

(

t
j
i

)



2

+

∑
i
1

⁢



∂

B
⁡

(

t
n
i

)

∂
t

-

∂

B
⁡

(

t
1

i
+
1

)

∂
t



2

->
min

where ⋅ • ⋅ is a Euclidean distance,
t is a pixel count on a segment of the contour,
t j i is a j-th count of an i-th segment of the contour,
t n i is a symbolic notation for a last count of an i-th segment and t 1 i +1 is a symbolic notation for a first count of a next i+1-st segment, and
B(t j i ), C(t j i ),

∂

B
⁡

(
t
)

∂
t

are respectively coordinates

Assignees

• Evernote Corp

Inventors

• Livshitz Eugene
• Buriak Ilia
• Galaktionova Natalia
• Pashintsev Alexander
• Gorbatov Boris

Classifications

• G06T11/23 Primary

  using straight lines or curves · CPC title

• G06T7/12

  Edge-based segmentation · CPC title

• G06T5/20

  using local operators · CPC title

• H04N19/94 Primary

  Vector quantisation · CPC title

• G06T3/4023

  based on decimating pixels or lines of pixels; based on inserting pixels or lines of pixels · CPC title