JPH05290159A - Method for approximating position data - Google Patents

Abstract

PURPOSE:To smoothly connect approximate position data of adjacent sections by dividing an approximation section into a straight approximation section and a curves approximation section by using the values of inner products at respective points of the contour of position data when the approximation section is divided, and further dividing the curves approximation section into a straight approximation section and a curves approximation section according to the value of the curvature. CONSTITUTION:The point on the contour where the value of the inner product is <=-0.99 is regarded as the start point of the straight line and when >=33 points where the values of the inner products are <=-0.99 succeed from the start point of the straight point, the section is extracted as a 1st straight section and the remaining section is extracted as a 1st curves section. Then the point in the 1st curved section where the value of the curvature is <=+ or -0.05 is regarded as the start point of a 2nd straight line and when >=33 points where the values of the curvature are <=+ or -0.05 succeed from the start point of the straight line, this section is extracted as a 2nd straight section. Approximation process is performed with the approximation sections which are thus obtained, so an approximated figure which is obtained has extremely smooth connection states between straight lines and curved lines.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a position data approximation method for approximating point sequence shape position data using a function.

[0002]

2. Description of the Related Art Generally, shapes such as characters and figures are read by an image scanner, taken as image data into a computer or the like, reproduced by an output device such as a CRT or a printer, or recorded in a storage medium such as an FD. There are a lot of things to do.

In this case, it is called an outline font,
It has been practiced to read the position data of only the outline portion of characters, figures, etc. and reproduce the portion surrounded by the outline portion as characters, figures, etc.

Graphic processing using such an outline font captures the contours of characters, graphics, etc. as a point sequence shape and reads or reproduces it, but today, the position data of the original graphic is used as it is. Don't
Approximate position data obtained by approximating this using an arbitrary function is used. This is because the position data of the original figure generally requires a large capacity to be stored in the memory because of a large change, a long time is required for various data processing, and a long time is required for reproduction. By approximating this using, for example, an arbitrary cubic function, the position data can be compressed, the storage capacity can be reduced, various data processing can be speeded up, and the reproduction time can be shortened. It is possible to reproduce the reproduced figure of.

In the conventional position data approximation method,
As shown in FIG. 6, the contour points of the original figure are evenly divided for each desired number of points to form an approximate section, and an arbitrary function is used for each of the divided sections. The data were close.

[0006]

However, in the above-mentioned conventional position data approximation method, when determining the section to be approximated by using a function, the contour points of the original figure are set for each desired number of points. Since it was done by dividing it evenly, there are both straight and curved parts in the section,
When the approximated position data is reproduced, the joining condition at the connection points of the adjacent sections is not theoretically smooth, and the reproduction quality of the position data is extremely inferior to the original figure.

The present invention has been made in view of these points, and overcomes the above-mentioned problems in the conventional ones.
It is an object of the present invention to provide a position data approximation method capable of smoothly joining the approximate position data of adjacent sections and improving the approximation accuracy of the position data of the original figure.

[0008]

In order to achieve the above-mentioned object, the position data approximation method of the present invention is a method for approximating position data in which a point sequence shape position data is divided into approximation intervals and a function is used for approximation. In the method, after dividing the point sequence shape position data into two approximation sections, a linear approximation section and a curve approximation section, based on the value of the inner product at each point of the position data, the curve approximation section is divided into the curve approximation section. It is characterized in that it is further divided into a linear approximation section and a curve approximation section based on the value of the curvature at each point inside, and is divided into two approximation sections, a linear approximation section and a curve approximation section, for approximation. ..

[0009]

According to the position data approximating method of the present invention having the above-described configuration, when dividing the approximating section, the value of the inner product of each point of the contour with respect to the position data is used to form a linear approximating section and a curve approximating section. Further, the curve approximation section is divided into a straight line approximation section and a curve approximation section based on the value of the curvature at each point in the curve approximation section. The approximate position data approximated based on the section and the curve approximation section are joined very smoothly, and the accuracy of the approximate position data reproduced with respect to the position data of the original figure can be made to have a desired content.

[0010]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the present invention will be described below with reference to FIGS.

FIGS. 1 and 2 show a continuous flow chart showing a position data approximation method according to the present invention, and FIG. 3 shows a case where contour points are divided by the position data approximation method according to the present invention. It is a figure.

As shown in FIG. 1, when the position data approximation method is started, the value of the inner product at each point of the contour is calculated in step ST10.

Next, in step ST11, a point whose inner product value is -0.99 or less is searched for. This point is the starting point of the straight line.

Next, in step ST12, it is judged whether the value of the inner product of the point next to the start point of the straight line (end point of the straight line) is -0.99 or less, and if the judgment in step ST12 is YES, step The process proceeds to ST13, the end point of the straight line is extended (the point next to the start point of the straight line), the process returns to step ST12, and the end point of the straight line is sequentially extended and repeated until the determination in step ST12 is NO. In addition, the step ST
If the determination in 12 is NO, the process proceeds to step 14.

In step 14, the value of the inner product is -0.
It is determined whether or not the points 99 or less are 33 points or more in succession, and if the determination in step 14 is YES, step S
The process proceeds to T15a, is extracted as the first straight line section, and proceeds to the next step ST16. If the determination in step ST14 is NO (the continuation of the inner product value of -0.99 or less is 32 points or less), the process proceeds to step ST15b to make a curve section, and the process proceeds to the next step ST16.

Next, in step ST16, it is judged whether or not the judgment is completed for all the points of the contour,
If the determination in step ST16 is no, step ST
The process returns to step 11 and is repeated until the determination in step ST16 is YES. When the determination in step ST16 is YES, the process proceeds to the next step ST17, and the remaining sections (the section where the curve section and the inner product value are not less than -0.99) except the first straight section are set. All are extracted as the first curve section, each point of the contour is divided into the first straight line section and the first curve section, and the process proceeds to the next step ST18.

Next, in step ST18, it is judged whether or not it is the first straight line section, and if YES, the symbol A in FIG. 1 is connected to the portion indicated by the same symbol A in FIG. 2 and the process proceeds to step ST27. .. If the determination in step ST18 is NO (first curve section), the symbol B in FIG. 1 is connected to the portion indicated by the same symbol B in FIG.
Proceed to.

Next, as shown in FIG.
At 19, the value of the curvature at each point of the first curve section is calculated.

Next, in step ST20, a point whose curvature value is within ± 0.05 is searched for. This point becomes the starting point of the straight line to be extracted which is included in the first curve section.

Next, in step ST21, it is determined whether the curvature value at the point next to the start point of the straight line (end point of the straight line) is within ± 0.05, and if the determination in step ST21 is YES, step The process proceeds to ST22, the end point of the straight line is extended (the point next to the start point of the straight line), the process returns to step ST21, and the end point of the straight line is sequentially extended and repeated until the determination in step ST21 is NO. In addition, the step ST
If the determination at 21 is NO, the process proceeds to step 23.

Next, at step 23, the curvature value is ±
It is determined whether there are 33 points or more consecutively within 0.05, and if the determination in step 23 is YES, the process proceeds to step ST24a and is extracted as the second straight line section,
Then, the process proceeds to next step ST25. If the determination in step ST23 is NO (the continuity of curvature values within ± 0.05 is 32 points or less), the process proceeds to step ST24b to make a curved section, and the process proceeds to the next step ST25.

Next, in step ST25, it is determined whether or not the determination has been completed for all points in the first curve section. If the determination in step ST25 is NO,
Return to step ST20, and the determination in step ST25 is YES.
Repeat until. If the determination in step ST25 is YES, the process proceeds to next step ST26,
All the remaining sections (the curved section and the section where the curvature exceeds ± 0.05) excluding the second straight section are extracted as the second curved section, and all the points in the first curved section are extracted as the second section. It is divided into a straight section and a second curved section, and the process proceeds to the next step ST27.

Next, in step ST27, the attributes of the start points of the straight line section formed by the first straight line section and the second straight line section and the curved section formed by the second curved line section are determined and the processing is terminated.

That is, in the present embodiment, in step ST11, the point whose inner product value of the contour points is -0.99 or less is set as the starting point of the straight line, and the inner product value from the starting point of this straight line is-.
When 33 or more points of 0.99 or less are consecutive, the first straight line section is extracted, and the remaining section is extracted as the first curve section. Then, in step ST20, a point within the first curve section has a curvature value within ± 0.05 as the starting point of the second straight line, and the curvature value from the starting point of this straight line is ± 0.
When the points within 05 are continuous for 33 points or more, it is extracted as the second straight line section, and the remaining section is extracted as the second curve section.

In the present embodiment, when the inner product value of -0.99 or less is continuous for 33 points or more, ± 0.05.
The case where the curvature values within 33 points or more are continuous is defined as a straight line section, but the value of the inner product, the value of curvature and the number of continuous points may be determined by the design concept, and are particularly limited to the present embodiment. Not a thing.

In this way, after the contour points are divided into the straight line section consisting of the first straight line section and the second straight line section and the curved section consisting of the second curved section, the contour points are predetermined as in the conventional case. The approximate position data is obtained by approximating with the function of.

Next, the method of calculating the value of the inner product at each point of the contour will be described in detail.

In general, the shape of binary data can be held by a closed loop of one or more aligned point sequences. Then, the point sequences P1, P2, ..., Pn on the contour have coordinates (X1, Y1), (X2, Y2), ... (Xn, Yn), respectively.
Corresponding to, a certain point Pi (Xi, Yi)
The value of the inner product at the point of (n = 1, 2, ..., N) is an arbitrary number k, for example, two points Pi-k (Xi-k, Y
ik), Pi + k (Xi + k, Yi + k) and using two vectors Pi-k Pi, Pi Pi + k formed by these three points Pi, Pi-k, Pi + k Can be obtained from the following equation 1.

[0029] The value of the arbitrary number k may be determined according to the design concept and is not particularly limited to this embodiment.

Further, the method of calculating the curvature value in the first curve section will be described in detail.

In general, the curvature R at the point (x, y) on the curve represented by y = f (x) can be obtained from the following equation 2.

[0032] However, since the point sequence takes a discrete direction for every 45 degrees, a good result cannot be obtained even if the differential value of Expression 2 is approximated only by the left and right adjacent points. Therefore, using the concept of averaging, it was decided to consider an average of k neighboring point sequences. Now, a differential value is calculated as follows when an average of k points adjacent to the left and right of the point (xi, yi) whose curvature is to be obtained is considered.

[0033] As a result of various studies, the present inventor preferably uses at least three parameters of curvature value, inner product value, and Hesse distance for segmentation using curvature. As shown in FIG. 3, the curvature at each point of the section is 16 degrees to the left and right from the target point for which the curvature is calculated.
The curvature is calculated from three ranges of 16 dots across the dot (point) and the target point, and the curvature value is ± 0.0 as described above.
Detect points that are within 5 and if 512 mesh,
The section length is 32 dots or more, and the inner product value of each point is -0.9
It is smaller than 9 and is extracted as the second straight line (diagonal line) section when the Hesse distance does not exceed 1.4142. By using the Hessian distance in determining the second straight line section, the bulge from the center line of the section at the target point can be regulated, and the accuracy of the linearity as the second straight line section is held at a desired value. Can be done easily.

The number of dots from the target point for which the curvature is to be calculated, the value of the curvature, the value of the inner product, the value of the Hessian distance, etc. may be determined by the design concept, and is not particularly limited to this embodiment. Absent.

As described above, according to the present embodiment, the value of the inner product of the points of the contour is calculated, and the point smaller than the predetermined value among the values of the inner product is first used to determine the first straight line section and the first curved section. Then, the first curved section is divided into a second straight section and a second curved section by using a curvature, and then a straight section and a second curved section which are composed of the first straight section and the second straight section as a whole. It is to be separated from the curved section. Further, since the approximation is performed by using the approximation section obtained in this way, the reconstructed approximate figure has a very smooth connection between the straight line and the curve, and the approximation accuracy in each approximation section is improved. Can be improved.

FIG. 5 shows a specific example according to the method of the present invention. The original figure of FIG. 5A is reproduced approximately by the method of the present invention, and the figure of FIG. It can be seen that the reproduction accuracy is extremely superior to the figure shown in FIG.

In the above embodiment, when the first straight line section is divided into the second straight line section and the second curve section, the division is performed by using the curvature value of each point. However, after obtaining the value of the curvature of each point, the difference between the absolute values of the adjacent point curvatures is taken, and the value of this difference is used to divide the second straight line section and the second curved section, It is possible to reduce the fluctuation of the curvature in ± as shown in FIG. 4, and it is possible to further improve the approximation accuracy.

That is, after the step ST19 in FIG. 2, a step of "taking the difference in absolute value of curvature between adjacent points at all points in the curve section" is added, and then the value of curvature in steps ST20 and ST21. May be replaced with the value of this difference to perform the processing. Then, this step ST20 and step ST
For example, a value of ± 0.000002 is used as the value of the difference that serves as a criterion for determination in 21, and processing may be performed so as to search for points within this value.

As described above, after the curvature value is calculated, the difference between the absolute values of the curvatures of adjacent points is calculated and the difference value is used to reduce the fluctuation of the curvature to ±. Therefore, the approximation accuracy can be further improved.

The present invention is not limited to the above embodiment, but can be modified as necessary.

[0041]

As described above, according to the position data approximating method of the present invention, the reproduced approximate figure has a very smooth connection state between the adjacent approximating sections, and the approximation in each approximating section is made. It has an extremely excellent effect of improving accuracy.

[Brief description of drawings]

FIG. 1 is a flowchart showing a method of approximating position data according to the present invention.

FIG. 2 is a flowchart showing a method for approximating position data according to the present invention.

FIG. 3 is an explanatory diagram illustrating a range for obtaining a curvature.

FIG. 4 is an explanatory diagram for explaining ± deflection of curvature.

5A is an original figure to be an approximate reproduction target, b is an approximate reproduction figure by the method of the present invention, and c is an approximate reproduction figure by a conventional method.

FIG. 6 is a diagram showing a case where contour points are divided by a conventional method.

Claims (1)

[Claims] 1. A method for approximating position data in which point position shape position data is divided into approximation intervals and is approximated using a function, based on the value of the inner product at each point of the position data, the point sequence shape position data Is divided into two approximation sections, a linear approximation section and a curve approximation section, and then the inside of the curve approximation section is further divided into a linear approximation section and a curve approximation section based on the value of the curvature at each point in the curve approximation section. A method for approximating position data, which is characterized by dividing into two and approximating as a whole into a linear approximation section and a curve approximation section.