JPH0338624B2 - - Google Patents

Description

[Detailed Description of the Invention] [Summary] In a method for compressing the amount of information by approximating the outline of a pattern with a broken line, a straight line generation part that generates a straight line between two points, and a straight line generated from the outline of the original pattern are used. a contour cutting section that detects whether a straight line between points matches a contour line therebetween and extracts information on a bending point of the contour; and whether the extracted bending point is at a right angle and at a predetermined position. The contour line information is expressed using the corrected bending point information.

[Industrial application field]

The present invention extracts bending point information from outline information of pattern information such as character shapes, and then extracts bending point information based on whether or not the bending points are at right angles to each other and at predetermined positions. The present invention relates to a pattern information amount compression method configured to compress original pattern information by correcting the position to prevent excessive bending points at right angle portions of the original pattern.

[Conventional technology]

Conventionally, as a method for compressing pattern information, for example, as described in a patent application filed on March 12, 1985 (title of invention "Pattern information amount compression method"),
The amount of information is compressed by calculating an inflection point of contour information of a pattern and expressing the original pattern using this inflection point. 10th below
A description will be given of the principle of a conventional pattern information amount compression method shown in the drawings.

In FIG. 10a, after determining the pattern P _i (i=1 to 12), which is the contour information of the original pattern, for example, the pattern P ₁₂ is set as the starting point and the ending point is set as the pattern.
P ₁ is determined, and pattern P ₁₂ (starting point) is extracted as a bending point. And the ending pattern
A straight line point sequence L (P ₁ , P ₁₂ ) connecting P ₁ and the starting point pattern P ₁₂ is determined. Next, the pattern at the end point
A tracked contour coordinate string T (P ₁ , P _{2 .} . . P ₁₂ ) is obtained by sequentially tracing the pattern P _i that is the contour information in the counterclockwise direction from P ₁ , that is, in the direction of the starting point. In this case, since the straight line point sequence L (P ₁ , P ₁₂ ) and the tracking contour coordinate sequence T (P ₁ , P ₂ , ...P ₁₂ ) do not match, the pattern P ₂ next to the pattern P ₁ , A straight line point sequence L (P ₂ , P ₁ , P ₁₂ ) with the starting point pattern P ₁₂ is determined, and the contour information P _i is sequentially traced in the counterclockwise direction from the pattern P ₂ to obtain the traced contour coordinate sequence T. ( _P2 ,
P ₃ ...P ₁₂ ) is obtained. In this case as well, since the two do not match, the same process is performed thereafter. In pattern P ₉ , the straight line point sequence L (P ₉ to P ₁₂ ) matches the tracking contour coordinate sequence T (P ₉ to P ₁₂ ), so
This pattern P ₉ is detected as a bending point (P ₉ shaded in FIG. 10b).

Next, as shown in FIG. 10c, when similar processing is performed using pattern P ₉ detected as a bending point as a starting point, pattern P ₆ is detected as a bending point this time. Then, if similar processing is performed using pattern _P6 as a starting point, pattern _P3 will be detected as a bending point. Here, the straight line point sequence L
(P ₃ , P ₁₂ ) and clockwise tracking contour coordinate string T (P ₃ ,
P ₂ , P ₁ , P ₁₂ ) match, so the extraction process ends. The bending point (P ₁₂ ,
P ₉ , P ₆ , P ₃ ) can be used to express the outline of the original pattern in a compressed manner.

Similarly, if the bending point is calculated for the contour line of the original pattern shown in Figure 11a (the line represented using a "white circle" in the figure), it will be shown using a "black circle" in Figure 11b. .

[Problem that the invention seeks to solve]

In the conventional pattern information amount compression method, for example, the original pattern is expressed and compressed using the bending point information indicated by the "black circle" in Figure 11b.
With the bending points shown in FIG. 2a, there is a problem that there are a plurality of bending points in the right angle portion, and it is not possible to compress the material sufficiently.

[Means for solving problems]

In order to solve the above-mentioned problems, the present invention corrects the positions of the bending points extracted in a manner perpendicular to each other and in a predetermined positional relationship to eliminate the number of bending points. Compression is performed by reducing the number of bending points that represent the pattern.

FIG. 1 shows the basic configuration of the present invention. In the figure, 1
3 is an original pattern holding section provided in the magnetic disk device 9; 3 is a straight line generating section; 4 is a contour cutting section; 7 is a bending point position correction section; 8 is a compressed data holding section provided in the magnetic disk device 9. , 9 represents a magnetic disk device.

In FIG. 1, a straight line generation unit 3 reads out the original pattern stored in the original pattern holding unit 1, and generates a straight line connecting any two points among the dot information corresponding to the outline of this original pattern. It is something.

The contour line cutting section 4 extracts the contour line in which both the straight line generated by the straight line generation section 3 in a manner connecting two predetermined points on the contour line of the pattern and the contour line between these two points match. It cuts out the curve and extracts the bending point.

The bending point position correction unit 7 determines whether the bending point extracted by the contour cutting unit 4 is at a right angle and at a predetermined position, and corrects the position of the bending point based on the result of this determination. It is something to do. The position of the bending point is corrected, and the bending point information with the number of bending points reduced is stored in the compressed data holding section 8 provided in the magnetic disk device 9.

[Effect]

The operation and effect of the configuration shown in FIG. 1 will be explained using the principle explanation of the present invention shown in FIG.

P ₁ to P ₄ in FIG. 2A represent the bending points before the position correction, and P ₁ , P ₁₂ and P ₄ in FIG. 2B represent the bending points after the position correction.

In Figure 2a, among the patterns shown using "circles" corresponding to the outlines of the original patterns in the figure,
The inflection point is represented by a "black circle". This "black circle" is extracted by the contour cutout section 4.

Then, the following processing is performed by the bending point position correction section 7. That is, consecutive bending points P ₁ , P ₂ ,
A point N obtained by moving _the bending point _P2 by one dot in the direction of the bending point P2 from the bending point _P1 with respect to _P3 and _P4 ,
If the point obtained by moving the bending point P ₃ by one dot from the bending point P ₄ in the direction of the bending point P ₃ coincides with the point, and there is a contour point indicated by a "circle" at that point, the bending point P Replace the coordinates of ₂ with the coordinates of point N (Fig. 2b
In the figure, the bending point P ₁₂ ) and the bending point P ₃ are deleted. As a result, the pattern expressed using four bending points (P ₁ , P ₂ , P ₃ , P ₄ ) has changed to three bending points (P 1 , P ₄ ).
P ₁₂ , P ₄ ).

As explained above, the contour information of the pattern is expressed using the bending point information, and the number of bending points is reduced by integrating the bending points when the bending points are at right angles to each other and in a predetermined positional relationship. Since this configuration is adopted, it is possible to perform sufficient compression, and the pattern can be easily enlarged, reduced, and compressed.

〔Example〕

One embodiment of the present invention will be described based on FIGS. 3 to 9.

(a) Configuration of one embodiment of the present invention Fig. 3 is a configuration diagram of one embodiment of the present invention, Fig. 4 is an explanatory diagram of the straight line generation state of the straight line generation section, and Fig. 5 is an operation flowchart of the straight line generation section. show.

In FIG. 3, 1 is an original pattern holding section, 2 is a tracing section, 3 is a straight line generating section, 4 is a contour cutting section, 5 is a comparison section, 6 is a bending point generating section, and 7 is a bending point The position correction section 8 represents a compressed data holding section.

The original pattern holding section 1 stores and holds, for example, an original pattern of characters (original pattern) transmitted from an appropriate input means such as a CCD of a TV camera.

The tracing section 2 traces the outline of the original pattern to obtain coordinate string points on the outline. For this purpose, for example, the pattern is scanned in a 3 x 3 window to capture a point on the outline of the pattern, and from there the outline can be traced in 8 directions.
Obtain the coordinate string of points on the contour. Set the starting point of the contour line to S,
If the end point is E, a contour line as shown by the white circle in FIG. 6a, for example, will be obtained. Furthermore, the 6th
The * mark in figure a is a pattern inside the contour line.

The straight line generating section 3 is a means for generating a straight line between two given points, and any known type can be used.
An example is DDA (Digital Differential Analysis).
An example of using a digital differential analyzer (zer: digital differential analyzer) will be described with reference to FIGS. 4 and 5. As shown in Figure 4, when drawing a straight line between P ₁ (X ₁ , Y ₁ ) and P ₂ (X ₂ , Y ₂ ), the first step (shown in Figure 5) is to set the starting point at (X ₁ , Y ₁ ),
When the angle of this straight line is φ, the coefficient G ₁ = cosφ,
Find the coefficient G ₂ =sinφ and set the coordinates of the starting point (X, Y) to X=X ₁ and Y=Y ₁ . and,
Write the following data into the X coordinate register R ₁ and Y coordinate register R ₂ as initial values.

_{R 1 = _ _} Add the sinφ to the value of the Y coordinate register _R2 . This means that in Fig. 4, the unit length is 1 from the starting point P ₁ to P ₂ .
shows the values of the X and Y coordinates when a straight line is drawn. By the way, since the data set in the memory is usually in integer units, only the integer parts I ₁ and I ₂ of the value after the addition are taken out. In the second step of FIG. 5, int(R ₁ ) indicates that only the integer part is taken out from register _R1 , and int(R ₂ ) shows that only the integer part is taken out from register _R2 .
Here, int indicates a function that truncates the fraction below the decimal point.

As a third step (shown in Figure 5), the second
If the integer I ₁ obtained in the step is different from X in the first step, or if the integer _{I 2} is different from Y in the first step, then _set them as (X,
Plot Y). In this case, X=X ₂ ,
Repeat until Y= _Y2 . In this way,
Data on a straight line between P ₁ and P ₂ as shown by the mark ◎ in FIG. 4 is obtained.

The contour line cutting section 4 cuts out the contour lines as appropriate and outputs the coordinates between them.

The comparing section 5 compares whether the straight line generated by the straight line generating section 3 and the contour cut out by the contour cutting section 4 match.

The bending point generation section 6 generates a termination condition check signal, which will be described later, and determines whether or not to continue the bending point generation process.

The bending point position correction section 7 reduces the number of bending points generated by the bending point generating section 6, as explained using the principle explanatory diagram shown in FIG.

The compressed data holding unit 8 holds the bending points of the contour line after the correction unit 7 deletes the bending points that are perpendicular to each other.

(b) Operation of the present invention The present invention mainly uses three techniques: generating a straight line between two points, extracting a bending point from a contour line, and correcting the position of a bending point.

(b) Of these, the straight line generating section 3 in (a) was explained based on FIGS. 4 and 5, so it will be omitted, and and will be explained sequentially.
After that, the overall operation will be explained.

Figure 7 is a flowchart of the bending point detection operation;
The figure shows an example of extraction of bending points, and FIG. 9 shows a position correction sequence of bending points.

The bending points are extracted from the contour of the pattern by the following steps 1 to 5.

In the first step, for example, as shown in FIG. 6A, one point on the outline of the pattern is captured, and the outline is traced from there by eight connections to obtain a coordinate string of points on the outline as shown by white circles. Let S be the starting point of the contour line, and E be the ending point.

In the second step, first, the starting point S is set as _P1 , and this _P1 is unconditionally extracted as a bending point.

In the third step, while moving the point P on the contour from the end point E to the start point S, the straight line generator 3 generates a straight line between the points P and S, and the contour line in that section is generated. Obtained by the contour line cutting section 4,
The comparing section 5 calculates the difference between this straight line and the contour line. For example, when point P is located at the position of the star shown in Figure 6b, if we find a straight line between this star and the starting point S (X mark), (star mark, ◎, ◎, ◎, ) is obtained, and a contour line from the star mark to the X mark in the counterclockwise direction is obtained, but the two do not match and the difference between them is not zero. Therefore,
Next, a straight line is generated in the same way at the position _P1 , where the point P is moved one position closer to the S side than the star mark position, and the outline is cut out to check whether it matches. This is done by sequentially moving P ₁ and P ₂ toward the starting point S. Then, when performing P _V in Figure 6b, the
Since the straight line from P _V to the starting point S and the contour line of that section match and the difference becomes zero, this point P _V
is extracted as the bending point V.

In the fourth step, it is checked whether all bending points have been extracted. For this purpose, the contour line of the section from the bending point V obtained in the third step and the end point E to the starting point S (in this example, the contour line in the clockwise direction from the bending point V) and the bending point V Check whether the difference between the line and the straight line at the starting point S is zero. In this check, the straight line generating section 3 generates a straight line, the contour cutting section 4 cuts out the contour line, and the comparing section 5 checks whether the lines match or do not match according to instructions from the bending point generating section 6 in FIG. It is done by doing.
If this difference is zero as described later, the bending point extraction process ends, but in FIG. 6b,
Since the check at the inflection point P _V is inconsistent, we continue with the fifth step to find the next inflection point.

In the fifth step, start counterclockwise from the end point E, and similarly to the third step, detect a point where the straight line to the bending point V and the contour line to the bending point V match, and from this, the next point is detected. The inflection point V ₁ can be detected. Then, the end condition of the fourth step is checked, but since the end condition is not satisfied even for _V1 , the straight line and contour line for _V1 are compared again using E as the starting point. Thereby, the bending point _V2 can be detected next. The termination condition is checked here, and if the termination condition is not met,
The straight line and contour line from E to this bending point _V2 are sequentially compared. By sequentially performing such processing, bending points as shown by black circles in FIG. 6d are detected.

FIG. 7 is a flowchart illustrating the general operation for detecting the bending point. here,
Let the coordinate point sequence of the traced contour line be (P ₁ , P ₂ ...P _o ), and use the method described above (the straight line generation unit 3 of a) between the i-th point Pi and the j-th point Pj on the contour line. The point sequence (N ₁ , N ₂ ...N _L ) generated in the _explanation in
...P _j ), and if they are equal, YES,
Processing that returns NO if not equal SAME (i, j)
is defined.

In addition, regarding the position correction of the bending point, the second
As explained using the diagram, the pattern in Figure 2 a
Pattern P ₂ from P ₁ to P ₄ by one dot from P ₁
Point N moved in the direction of P ₂ and pattern P ₃ are 1
If it matches the point moved in the direction _{of P 3 by} a dot and there is a point on the contour at that position,
The coordinate values of pattern P ₂ are replaced with the coordinate values of point N, and pattern P ₃ is deleted to obtain a pattern and bending points P ₁ , P ₁₂ , and P ₄ as shown in FIG. 2b. As a result, the four bending points before the bending point position correction
P ₁ , P ₂ , P _{3 .} . . P ₄ have been reduced to three bending points P ₁ , P ₁₂ , P ₄ , and compression has been performed.

(b) Next, the overall operation of the present invention will be explained using FIG.

A character pattern input from an image input unit such as a TV camera (not shown) is held in the holding unit 1. The contour portion of this pattern is traced by the tracing section 2, and coordinate string points on the contour line as shown by white circles in FIG. 6a are obtained. The starting point of the contour obtained at this time is S, and the ending point is E. These data are held in the straight line generating section 3 and the contour cutting section 4.

First, the bending point generation unit 6 unconditionally extracts the starting point S as a bending point.

The straight line between the end point E and the start point S is the straight line generator 3
and sends the coordinates of the straight line to the comparing section 5. In addition, the contour line cutting unit 4 calculates the coordinates (E, P ₁ ,
P ₂ ...S) is sent to the comparison section 5. Comparison unit 5 compares this straight line with the contour line coordinates and outputs a mismatch signal to bending point generation unit 6 when they do not match.
The bending point generation unit 6 thereby causes the straight line generation unit 3 and the contour cutout unit 4 to perform the same processing on the point P ₁ on the contour line next to the end point E (the point on the opposite side to the starting point S). to command. As a result, the straight line generating section 3 generates a straight line between P ₁ and S, and the contour cutting section 4 sends out (P ₁ , P ₂ ...S),
Comparison is performed in the comparator 5. Since they do not match at this time as well, next a comparison is made between the straight line from point _P2 to S and the contour line. These steps are performed sequentially, and a matching signal is output from the comparing section 5 at point P _V.

As a result, the bending point generating section 6 in turn causes the contour line cutting section 4 to output a contour line from the point P _V to the starting point S via the clockwise end point E, and the straight line generating section 3 Output a straight line between P _V and S,
compare. Since the comparison section 5 sends out a mismatch signal, the inflection point generation section 6 recognizes that the termination condition is not satisfied, and this time the same control as described for the fifth step in A above is performed. In this way, each bending point is detected in sequence. Then, each bending point shown as a black circle in FIG. 6d is notified to the bending point position correction unit 7.

When the adjacent bending points are perpendicular to each other and have a predetermined positional relationship, the bending point position correction unit 7 that has received the notification of the bending point information of the contour line corrects one of the bending points as explained using FIG. Replace the coordinates of the bend point and delete other bend points. Then, the information on each bending point subjected to this position correction is held in the compressed data holding unit 8.

In this way, for example, the "black square" in Figure 8
The position indicated using
Extracted by. Further, among these extracted bending points, those whose positions have been corrected by the bending point position correction section 7 are shown in FIG. “*” in the diagram
indicates a position where the bending points are corrected by the bending point position correction unit 7 and the number of bending points is reduced. In this way, as shown in FIG. 9, the original pattern can be compressed and expressed using the bending point information after the bending point position correction has been performed.

〔Effect of the invention〕

As explained above, according to the present invention, original pattern information is expressed using bending point information, and
Since we have adopted a configuration in which position correction is performed to reduce the number of bending points when the bending point information is at right angles to each other and in a predetermined positional relationship, the bending point information is used to generate the original in a highly compressed manner. Pattern information can be expressed. Furthermore, since the bending point is provided as coordinate information, various transformations such as enlargement, reduction, rotation, etc. can be easily performed. Therefore, compared to devices that have conventionally stored patterns using full dots, it is possible to achieve extremely small size and high performance.

[Brief explanation of drawings]

FIG. 1 is a diagram showing the basic configuration of the present invention, FIG. 2 is a diagram explaining the principle of the invention, FIG. Flowchart of the operation of the straight line generation section, FIG. 6 is an explanatory diagram of the bending point detection state, FIG. 7 is a flowchart of the bending point detection operation, FIG. 8 is an example of extracting the bending point, and FIG. 9 is an example of correcting the position of the bending point. , FIG. 10 is a diagram explaining the principle of a conventional pattern information amount compression method, and FIG. 11 shows an example of extraction of bending points. In the figure, 1 is an original pattern holding section, 3 is a straight line generation section, 4 is a contour cutting section, 7 is a bending point position correction section,
8 represents a compressed data holding unit, and 9 represents a magnetic disk device.

Claims (1)

[Claims] 1. In a pattern information compression method that compresses the amount of information by approximating the outline of a pattern with a broken line, the method comprises: a straight line generation unit 3 that generates a straight line between two points; a contour line cutting unit 4 that detects whether or not a straight line between two points matches a contour line therebetween and extracts information on bending points of the contour line;
and a bending point position correction for determining whether or not the bending point extracted by the contour cutout section 4 exists at a right angle and at a predetermined position, and correcting the position of the bending point based on the determination result. 7. A pattern information amount compression method characterized in that the contour information is expressed using the bending point information corrected by the bending point position correcting section 7.