JPH0636191B2 - Two-dimensional line image data compression method - Google Patents

Description

Description: FIELD OF THE INVENTION The present invention relates to a data compression method for a two-dimensional input line image, and more particularly to a two-dimensional line input from a handwritten character / graphic recognition device, a screen writing device, or the like. The present invention relates to an image data compression method.

[Background of the Invention]

First, a conventional example of a data compression method of a two-dimensional line image used in a two-dimensional line image processing device, for example, a handwritten character / graphic recognition device and a copy writing device will be described.

As a conventional example, Japanese Patent Laid-Open No. 58-181180 discloses a line pattern recognition device.

The conventional arc / straight line separation method traces from the end point of the input line, takes sample points at a certain interval, and then
Obtain the estimated radius when a circle is approximated to several consecutive points. 1
The process of shifting the point and obtaining the estimated radius again is repeated until the end point of the line L. Then, the part where the distribution of these estimated radii is stable is a circular arc, while the fluctuating part contains the sample point that caused it, and it is estimated that it is the arc separation point. To do.

For example, in the curve of FIG. 12, four consecutive points S _{i + 1} :
Q _i , Q _{i + 1} . If the distribution of the estimated radius R _i when circle-approximated to Q _{i + 2} , Q _{i + 3} is shown in FIG. 13, R ₁ , R ₂ , R ₃ and R ₆ , R ₇ , R ₈ are stable. And each form an arc. On the other hand, the sequence of points _{S 4: Q 3, Q 4} , Q 5,
Q ₆ , S ₅ : Since the estimated radii of Q ₄ , Q ₅ , Q ₆ , and Q ₇ are changing, points Q ₄ , Q ₅ , and Q common to S ₄ and S ₅ are changed.
The point Q ₅ at the center of ₆ is defined as the boundary point between the two circular arcs. Through the above procedure, this curve is recognized as connecting two arcs.

When this method is applied to a handwriting input figure, even if the input person draws it as one arc, the curvature will be partially different. The radius length and the center coordinates tend to largely change due to a gradual change in curvature. In the conventional example, this point has not been taken into consideration.

[Object of the Invention]

An object of the present invention is to provide a data compression method for separating a two-dimensional line image into arc / straight line segment elements without being affected by a local change in curvature.

[Outline of Invention]

In the present invention, when a circular arc is approximated to a polygonal line, if the line segment length is adjusted to be long in a portion with a gentle curvature and short in a steep portion, the ratio between the line segment length and the radius of curvature center of the arc is set. Is
Since it is almost constant, based on this idea, after approximating the input stroke as a polygonal line as described above, the part where the ratio is within the preset allowable range is a circular arc, otherwise it is a straight line. It is to be separated into two types of line segment elements.

Example of Invention

An embodiment of the present invention will be described below with reference to FIGS. 1 to 11 by taking an input unit of a handwriting recognition device as an example.

FIG. 1 shows an example of the configuration of a device for separating a stroke (two-dimensional line image) handwritten by an input device such as a tablet into arc line segment elements and straight line segment elements. Tablet 1
The handwriting input stroke point sequence is read from the data reading unit 2 and sampled to obtain point sequence data by X and Y coordinates. The polygonal line approximation unit 3 smoothes this point sequence data and converts it into polygonal line data. To do. The line segment sequence approximated to the broken line is written in the file 9 with line segment numbers (m to n; m, n: integer). The cord difference check section 4 and the r / L check section 5 check whether or not every two adjacent line segment rows satisfy a preset arc condition. Here, r is the radius of the circumscribed circle of the three end points of two adjacent line segments, and L is the line segment length. The arc / straight line judging unit 6 judges from the results of the code difference check unit 4 and the r / L check unit 5 whether each line segment is a part of an arc or a straight line.
In the absorbing section 7 for a short straight arc, if the result of the arc / straight line determining section 6 is that a straight line that is sufficiently shorter than the circular arc is adjacent, the straight line is regarded as a part of the circular arc. Line element registration unit 8
Then, the start / end line segment numbers of the arc / straight line segment elements are registered in the file 9.

Next, the above operation will be described in detail.

FIG. 2 shows the flow chart. Hereinafter, it is assumed that the processing numbers correspond to the processing numbers in the figure, and the terminal figure of FIG. 3 is taken as an input example for description.

In process 1, the tablet 1 and the data reading unit 2
A handwriting stroke as shown in FIG. 3 is read.

In the process 2, the stroke is made longer by the polygonal line approximation unit 3 in a portion having a gentle curvature, as shown in FIG.
It is approximated by a polygonal line so that it becomes shorter at a steep part. At this time,
In the file 9, line segment numbers, start point / end point information, and angle information of each line segment are stored along the input direction, for example, in the form shown in FIG. Here, the angle information is 2π
Is divided into 32 directions, and the area numbers 0 to 3 to which the line segment belongs
It will be represented by 2, and will be referred to as a code hereinafter.

In process 3, after this, each line segment is shifted one by one in the input direction, and every two adjacent line segments are subjected to the arc condition check described below to see if they are satisfied twice in succession. The result of the arc condition check of two lines, that is, the arc candidate flag COND, is set to the previous arc candidate flags PRE and CON.
Save it in D.

The arc condition check is performed as follows for every two adjacent line segments.

In process 4, first, the code difference between adjacent line segments is checked. For example, the allowable angle range is minimum 1 and maximum 4
Then, in FIG. 4, regarding the two line segments L ₁ and L ₂ ,
Since the code difference θ ₁ = 6 between the two line segments in FIG. 5 exceeds the angle allowable range, the arc candidate flag COND is set to FACSE in process 7. In the same figure, regarding the two line segments L ₂ and L ₃ , since the code difference θ ₂ = 1 is in the above-mentioned angle allowable range circle, the following arc condition check is received.

In process 5, the r / L check unit 5 performs an arc condition check. Two adjacent line segments L _i , L _j ; i, j = 1,
A circumscribed circle R _{i at} the three end points of 2, ..., Radius r of i = 1, 2 ,.
_ij ; i, j = 1, 2, ... It is checked whether or not the ratio between the radius r _ij and the length of each line segment L _i , L _j is within a preset condition range.

For example, the condition range of the ratio is set to 1.0 to 5.0, each circumradius R _i and the line segment L _i in FIG. _6, the ratio of L i + _1, when graphed in Figure 7, L ₂ , L ₃ for two line segments, r ₂₃ / L ₂ and r ₂₃ / L ₃ both fall within the above condition range and satisfy the arc condition. In this case, the arc candidate flag COND is set to TRUE in the process 6.

In process 8, the arc / straight line determination unit 6 checks whether or not the arc candidate has continued twice. Two consecutive times means that PRE, COND and COND are both T
In the case of RUE, that is, the arc condition check is satisfied for three consecutive line segments, and it is determined that these three line segments are a part of the arc.

In FIG. 7, the combination of L _{1 to} L ₃ is not a circular arc because the code difference θ ₁ between L ₁ and L ₂ is outside the angle allowable range, but L _{2 to} L ₄ and L _{3 to} L _{5 are not formed.} Is a part of the arc. However, it is determined that L _{4 to} L ₆ do not form an arc because r ₅₆ / L ₅ exceeds the condition range of the ratio.

In process 9, the arc / straight line information is registered in the file 9 with the three line segments satisfying the condition in process 8 as one part of the arc. At this time, if the first two lines of the three line segments already form an arc with other line segments, the two arcs are a series of arcs. For example, in FIG. 6, L _{2 to} L ₄ , L _{3 to} L ₅
Are each considered to be part of an arc. In this case, L ₂
~L ₅ is treated as an arc of a series, as in FIG. 8 A column, the file 9, an arc / linear information is written.
The meaning of each number is 2; the beginning of the arc, 1; the middle of the arc,
3; It is the end of the arc.

In process 10, among the three line segments that did not satisfy the condition in process 8, the last line segment is assumed to have not formed an arc,
Register in File 9. For example, L ₆ is separated from the arcs up to L ₅ , and 0 is written in the file 9 as a straight line as shown in the column A of FIG.

In process 11, the above 3 to 10 are applied to all line segments.
When the above process is performed, the terminal figure shown in FIG.
It is divided into arc / straight line segment elements as shown in the figure.

In the process 12, when the arc and the straight line are adjacent to each other, if the straight line is sufficiently shorter than this arc, the straight line is included in the arc, and the arc / straight line information is stored in the file 9
Register again. By this operation, it is possible to deal with a situation such as a hand shake that is likely to occur in handwriting input, which is contrary to the intention of the person who made the input and a straight line is mixed in one arc.

For example, if a straight line that is less than 1/2 of the total length of the arc is absorbed by the arc, the straight line element ₁ is the arc line segment element in FIG.
Since less than ₂ 1/2, it is absorbed by the _2. on the other hand,
The straight line element ₃ is not shorter than the circular arc elements ₂ and _4, and ₃ is left as a straight line element. As a result, the arc / straight line information in the file 9 is re-registered from column A in FIG. 8 to column B.

In process 13, based on the arc / straight line information in the file 9, the start line segment number mi and the end line segment number ni; i = 1, 2, ... Of each line segment element are registered as shown in FIG.

As a result of the above processing, the terminal figure of FIG. 3 is separated into two straight lines and two arcs as shown in FIG.

According to this embodiment, a two-dimensional line image captured as a handwriting stroke can be separated into a straight line and a circular arc,
It is possible to effectively compress the data.

〔The invention's effect〕

According to the present invention, a two-dimensional line image approximated to a polygonal line is not affected by the magnitude of its curvature and a local change in curvature,
Since it can be easily separated into an arc and a straight line by a constant parameter, there is generally a data compression effect of one tenth to several tenths.

[Brief description of drawings]

FIG. 1 is an overall configuration diagram according to an embodiment of the present invention, and FIG.
The figure is the same flow chart, Fig. 3 is a diagram showing an example of handwriting input stroke, Fig. 4 is a state diagram after broken line approximation of Fig. 3, and Fig. 5 is an information list in the file for Fig. 4. FIG. 6 is a diagram showing a part of FIG. 4, FIG. 7 is a graph of parameters obtained from FIG. 6, FIG. 8 is a diagram showing arc / straight line information in the file, and FIG. FIG. 10 is a diagram showing line segment element separation in the figure, FIG. 10 is a diagram showing line segment element information in the file, and FIG. 11 is a final diagram showing line segment element separation in FIG. 3, FIG. 12, and FIG. The figure is a diagram for explaining a conventional arc / straight line separation method. 4 ... Code difference check section, 5 ... r / L check section,
6 ... Arc / straight line determination part, 7 ... Absorption part of short straight line arc, 8 ... Line segment element registration part.

Claims (3)

[Claims] 1. A two-dimensional line image is sampled by a data reading unit and converted into point sequence data, and the point sequence data is converted into polygonal line data composed of a plurality of line segments by a polygonal line approximation unit,
In the data compression method of separating the polygonal line data into at least one or more arcs or straight lines and compressing the information amount of the two-dimensional line image, the point sequence data is long in a portion having a gentle curvature and short in a steep portion. To calculate the radius of the circumscribed circle of two adjacent line segments in the polygonal line data, and obtain the ratio between the obtained radius and each line segment length, A data compression method for a two-dimensional line image, wherein the polygonal line data is separated into an arc when the ratio is within a predetermined allowable range and a straight line when the ratio is outside the allowable range. 2. In the description of claim 1, when there are straight lines adjacent to each other in the separated arc, when the line segment length of the straight line is shorter than the circumferential length of the arc, the straight line is A method for compressing data of a two-dimensional line image, characterized by absorbing as a part of an arc. 3. The data compression method for a two-dimensional line image according to claim 1, wherein the ratio is obtained only when the angle change of line segments of adjacent polygonal line data is within a certain range. .