How to convert raster images into vector images (algorithm)

This entry explain how P2VJ convert raster images to vector images.
I hope it will be helpful to programmers who are making painting or drawing softwares~('u')

Click the link to see it~

7/2 update: adding space cuz long formulas were not wrapped correctly.
1. Trace the boundary of colors.

2. Divide the line into 100 pieces. (there should be 101 points.)

To improve result... (click here)

3. Push the coordinates of 101 points into an array.

This time, I named it CP[].
Please assume CP as an array of Point objects which have two variables "x" and "y".
If you are using non-OOP langage, please make two arrays which store x coordinates and y coordinates separately.


4. Calculate following variables p1x, p1y, p2x, p2y, p1xb, p1yb, p2xb and p2yb with these formula.

double p1x = (-9*CP[50].x + 125*CP[10].x - 90*CP[0].x + CP[100].x)/27;

double p1y = (-9*CP[50].y + 125*CP[10].y - 90*CP[0].y + CP[100].y)/27;

double p2x = (81*CP[50].x + 81*CP[0].x - 10*CP[100].x - 125*CP[10].x)/27;

double p2y = (81*CP[50].y + 81*CP[0].y - 10*CP[100].y - 125*CP[10].y)/27;

double p1xb = (-1000*CP[90].x - 80*CP[0].x + 648*CP[100].x + 648*CP[50].x)/216;

double p1yb = (-1000*CP[90].y - 80*CP[0].y + 648*CP[100].y + 648*CP[50].y)/216;

double p2xb = (1000*CP[90].x + 8*CP[0].x - 720*CP[100].x - 72*CP[50].x)/216;

double p2yb = (1000*CP[90].y + 8*CP[0].y - 720*CP[100].y - 72*CP[50].y)/216;

Why? (click here)

5. p1x, p1y, p2x and p2y are the candidates of coordinates of control points of Bezier curve we want to calculate.
In the following figure, p1x and p1y are coordinates of P1.x and P1.y, respectively.
p2x and p2y are the coordinates of P2.x and P2.y.
P0 is the same with CP[0] and P3 is the same with CP[100].
Note that p1xb, p1yb, p2xb and p2yb are also the candidates of coordinates.
So, now we have two candidates of P1 and P2.

6. Calculate the distance between two P1 candidates; P1 made from p1x and p1y (name it P1a) and P1 made from p1xb and p1yb (name it P1b).
Calculate the distance of between two P2 candidates in the same way.


From version 0.9, P2VJ calculates distance between exact points and points estimated from constructed curve.
For example, t=0.9 point of the curve calculated from P1a and P2a should be close to the CP[90].
t=0.1 point of the curve calculated from P1b and P2b should be close to the CP[10].
I used only 4 points CP[30], CP[70], CP[10] and CP[90].
It looks working well.

7.If the distance is shorter than the threshold, it means calculated Bezier curve traces color boundary very well. Let's set the coordinates of P1 and P2 as the center of candidate points.

P1.x = (p1x + p1xb)/2;
P1.y = (p1y + p1yb)/2;
P2.x = (p2x + p2xb)/2;
P2.y = (p2y + p2yb)/2;

8. I think now you have all variables needed to generate Bezier curve.
For example, in GeneralPath object of java,


7b. If the distance is longer than the threshold, it means calculated curve does not trace the color boundary.
You have to shorten (break into some parts) the line and calculate again.


The threshold reflects quality of fitting. You can decide it arbitrary, but if the threshold is shorter, number of points will become big (wastes HDD space).
If it is long, number of points will become small, but the curve may not fit the original image very well.


In the real segments of bezier curve, distance between points are not equal.
In fact, you can choose CP[10] and CP[90] arbitrary.
P2VJ tries to use CP[7] - CP[13] as CP[10] and CP[87] - CP[93] as CP[90].
And checks the quality of all constructed curves and selects the best one.


テーマ : 雑記 - ジャンル : ブログ