JPH0325827B2 - - Google Patents

Description

[Detailed Description of the Invention] [Table of Contents] Overview Industrial Field of Application Conventional Technology Problems to be Solved by the Invention Means for Solving the Problems (Fig. 1) Working Examples (a) The present invention Configuration of one embodiment (FIGS. 2 to 5) (b) Operation of the present invention (FIGS. 2 to 7) Effects of the invention [Summary] Trace the line to obtain the contour data of the original pattern, and when extracting the bending point from there, for two points on the contour line, the contour line between these points and the curve that occurs between those points. When the straight lines match,
This point is detected as a bending point, and the outline of the pattern is expressed by a plurality of bending points of this pattern.

[Industrial application field]

The present invention relates to a pattern information compression method for compressing and retaining pattern information such as character shapes,
In particular, it is a pattern information compression method that generates compressed data that can completely faithfully restore the original pattern, has a large amount of compression, and can easily enlarge or reduce the original pattern.

It is not preferable to retain pattern information of characters and figures in the original state in memory because the amount of information is large and therefore a large capacity memory is required. Therefore, this is compressed and held.

[Conventional technology]

Conventional methods for compressing pattern information include a run-length method and a chain code method. The run-length method represents pattern information by the continuous length of black or white levels in the memory scanning direction. Also, the chain code method is 3×3
A mask is used, and the consecutive positions of the center point of the mask are indicated by the positions of eight points around it.

[Problem that the invention seeks to solve]

By the way, in the run-length method, it is difficult to perform conversions such as enlargement, reduction, rotation, etc. when restoring a pattern, and in the chain code method, it is difficult to perform conversions such as enlargement, reduction, etc., and rotation is also somewhat difficult when restoring a pattern. Both methods have the disadvantage that the amount of information compressed is not sufficient.

In order to solve these problems, the present invention makes it easy to enlarge, reduce, rotate, etc. when restoring a pattern.
Moreover, it is an object of the present invention to provide a pattern information amount compression method that allows a large amount of information to be compressed.

[Means for solving problems]

In order to solve the above object, in the present invention, as shown in FIG. 1a, pattern contour information Pi (i=1 to
12), and for example, set pattern P ₁₂ as the starting point and end point as P ₁ . (First, P ₁₂ (starting point) is extracted as the bending point) This starting point can be determined as appropriate. And end point P ₁ and start point P ₁₂
Find the straight line point sequence ₁ , ₁₂ (P ₁ , P ₁₂ ), then trace this contour information counterclockwise from the end point pattern P ₁ , that is, in the direction of the start point, to obtain the traced contour coordinate sequence (P ₁ , P 12 ). P ₂ , P ₃ ...P ₁₂ ) are obtained. In this case, the straight line point sequence _{1 , 12} ≠ coordinate sequence (P ₁ , P ₂ ... P ₁₂ ), so this time, the next pattern P ₂ of P ₁ and the straight line point sequence ₂ , ₁₂ (P ₂ , P ₁ , P ₁₂ ), and then traced contour coordinates (P _{2 ,} P ₃
...P ₁₂ ) is obtained and compared with the straight line point sequences ₂ and ₁₂ , but since they do not match in this case, the same process is performed from pattern P _3. In this way, patterns P ₃ , P ₄ , For P ₅ , P ₆ . . . P ₈ , the start point, straight line point sequence, and traced contour coordinate sequence are compared in the same way, but none of them match. In addition, pattern P ₅ ~
At _P8 , the straight line point sequence between each pattern and the starting point _P12 deviates from the contour pattern.

However, in pattern P ₉ , the straight line point sequence ₉ , ₁₂ (P ₉ ,
P ₁₀ , P ₁₁ , P ₁₂ ) and the tracking contour coordinate sequence (P ₉ , P ₁₀ ,
P ₁₁ , P ₁₂ ), this pattern P ₉ is detected as the bending point.

Next, as shown in FIG. 1c, if similar processing is performed using _P9 detected as a bending point as a starting point, pattern _P6 will be 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 sequences ₃ and ₁₂ match the clockwise tracking contour coordinate sequence (P ₃ , P ₂ , P ₁ , P ₁₂ ) _, so the extraction process is terminated.

Since the refraction points (P ₁₂ , P ₉ , P ₆ , P ₃ ,) are thereby obtained, the pattern outline can be expressed.

[Effect]

Since the contour information can be provided by a plurality of pieces of refraction point information, it is not only very easy to enlarge/reduce and compress the pattern, but also the amount of information can be significantly compressed.

〔Example〕

An embodiment of the present invention will be described based on FIGS. 2 to 7.

(a) Configuration of an embodiment of the present invention Fig. 2 is a configuration diagram of an embodiment of the present invention, Fig. 3 is an explanatory diagram of the operation of the straight line generation section, Fig. 4 is the operation flow of the straight line generation section, and Fig. 5 is an explanatory diagram of the bending point generation state, Fig. 6 is the operation flow of bending point generation, and Fig. 7 is an explanatory diagram of the bending point generation state.
The figure is an example of extraction of bending points.

In FIG. 2, 1 is a pattern holding section, 2 is a tracking section, 3 is a straight line generation section, 4 is a contour cutting section,
5 is a comparison section, 6 is a bending point generation section, and 7 is a compressed data storage section.

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

The tracing section 2 traces the outline of the pattern to obtain coordinate string points on the outline. To do this, for example, a pattern is scanned in a 3x3 window to capture a point on the outline of the pattern, and from there, the outline can be traced in 8 directions and this is traced to obtain the coordinate string of the points on the outline. . If the starting point of the contour line is S and the end point is E, the contour line will be obtained, for example, as shown by the white circle in FIG. 5a. Note that the * mark in FIG. 5a 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).
An example of using a digital differential analyzer (analyzer) will be explained with reference to FIGS. 3 and 4. As shown in Figure 3, P ₁ (X ₁ , Y ₁ ) and P ₂
When drawing a straight line between (X ₂ , Y ₂ ), the first step is to plot the starting point at (X ₁ , Y ₁ ), and if the angle of this straight line is φ, then the coefficient G ₁ =cosφ,
Find the coefficient G ₂ = sinφ and find the starting point (X, Y)
Set the coordinates of X=X ₁ and Y=Y ₁ . Then, the following data is written into the X coordinate register R ₁ and Y coordinate register R ₂ as initial values.

_{R 1 = _ _ _} Add the above sinφ to the value of . This shows the X and Y coordinates when a straight line is drawn by unit length 1 from the starting point P ₁ toward P ₂ in FIG. By the way, since the data set in memory is usually in integer units, the integer part I ₁ of the value after the addition is
Take out only I ₂ . Note that in the second step of FIG. 4, int(R ₁ ) indicates that only the integer part is extracted from register R ₁ , and int(R ₂ ) indicates that only the integer part is extracted from register R ₂ .
Indicates that only the integer part is extracted. here
int indicates a function that truncates the number below the decimal point.

As a third step, if the integer I ₁ obtained in the second step is different from the first step X ₁ or the integer I ₂ is different from Y ₁ in the first step,
= I ₁ and Y = I ₂ and plot them on (X, Y). In this way, X=X ₂ , Y=Y ₂
Repeat until. In this way, data of a straight line between P ₁ and P ₂ as shown by the circle in FIG. 3 is obtained.

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

The comparing section 5 compares the straight line generated by the straight line generating section 3 and the contour line cut out by the contour line cutting section 4 to see if they are equal.

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

The compressed data holding unit 7 holds bending points in the contour line.

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

(a) These are omitted because they have been explained with reference to FIGS. 3 and 4 for the straight line generating section 3 in (a), but will be explained first, and then the overall operation will be explained.

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. 5A, a point on the outline of the pattern is set, and from there the outline is traced in 8-connection 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, the starting point S is set to P ₁ ,
This P ₁ is unconditionally extracted as an inflection point.

In the third step, point P is moved from end point E to start point S.
A straight line is generated by the straight line generation section 3 in a manner between points P and S while moving on the contour toward the point, the contour line in that section is obtained by the contour line cutting section 4, and the comparison section 5 calculates this straight line. Find the difference between the straight line and the contour line. For example, point P is
If you find the straight line between this star and the starting point S (X mark) when you are at the position of the star shown in (star mark, ◎,
Straight lines such as ◎, ◎, X marks) are obtained, and a contour line from the star mark to the X mark in the counterclockwise direction is obtained, but these two do not match and the difference is not zero. Therefore, next, a straight line is generated in the same way at the position P', which is moved one point closer to the S side than the position of the star, and the contour line is cut out to check whether it matches. This is done by sequentially moving P' and P'' in the direction of the starting point S. Then, when doing this at Pv in Figure 5b, the straight line from Pv to the starting point S and the outline of that section match. Since the difference becomes zero, this point
Pv 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 outline of the section from the bending point V obtained in the third step to the starting point S via the end point E (in this example, the contour line in the clockwise direction from the bending point V)
Then, it is checked whether the difference between the bending point V and the straight line at the starting point S is zero. This check is performed by having the straight line generating section 3 generate a straight line, the contour cutting section 4 cutting out the contour line, and the comparing section 5 checking whether they match or do not match based on instructions from the bending point generating section 6 shown in FIG. This is done by If this difference is zero, as will be described later, the bending point extraction process ends, but in FIG. Follow the steps.

In the fifth step, start counterclockwise from the end point E, and similarly to the third step, detect the 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 bending point is detected. V ₁
can be detected. Then, the end condition of the fourth step is checked, but since the end condition is not satisfied even at _V1 , this time the straight line and contour line for _V1 are compared using E as the starting point (not the starting point S). This allows the next bending point _V2 to be detected. Here, the termination condition is checked, 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, each bending point is detected as shown by the black circle in FIG. 5d.

FIG. 6 is a flowchart illustrating the general operation for detecting the bending point. Here, the coordinate point sequence of the traced contour is {P ₁ , P ₂
...Pn}, and the i-th point Pi and j on the contour line
The point sequence {N ₁ ,
Assume that a process SAME (i, j) is defined that compares _N2 ...NL} and {Pi...Pj} and returns yes if they are equal, and no if they are not equal.

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

A character pattern input from an image input unit such as a TV camera (not shown) is stored in the holding unit 1.
is maintained. 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. 5a 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 3. Further, the contour line cutting section 4 sends the coordinates (E, P ₁ , P ₂ . . . S) of the contour line from the end point E to the starting point S in a counterclockwise direction to the comparison section 3. The comparator 3 compares the straight line and the contour line coordinates, and outputs a mismatch signal to the bending point generator 6 when they do not match. The bending point generation unit 6 thereby instructs the straight line generation unit 3 and the contour generation unit 4 to perform the same process on the point P ₁ on the contour line next to the end point E (the point on the opposite side from the start point S). do. As a result, the straight line generating section 3 becomes P ₁
The contour generating section 4 sends out (P ₁ , P ₂ . . . S), and the comparison section 5 compares them. Since they do not match at this time as well, the straight line and outline of points _P2 and S are compared next. These things are done sequentially,
A matching signal is output from the comparing section 5 at point Pv.

As a result, the bending point generating section 6 in turn causes the contour line cutting section 4 to output a contour line clockwise from Pv to the starting point S via the terminal point E, and also causes the straight line generating section 3 to output the contour line from Pv to the starting point S. Output a straight line with and 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 performs the same control as described for the fifth step in A above. In this way, each bending point is sequentially detected. Then, each bending point shown as a black circle in FIG. 5d is held in the compressed data holding unit 7.

In this way, for example, the pattern information in FIG. 7a can be compressed and held using the coordinate information of the bending point indicated by the black dot in FIG. 7b.

〔Effect of the invention〕

According to the present invention, original pattern information is held using bending point information, so that it is possible to hold a highly compressed amount of information. In addition, since a bending point is detected by detecting a partial match or mismatch with the original pattern, compressed data that can completely restore the original pattern is generated. Furthermore, since the bending points are used as coordinate information, each pattern that has been subjected to transformations such as enlargement, reduction, rotation, etc. can be easily generated. Therefore, it will be useful not only for downsizing devices that have until now memorized patterns using full dots, but also for increasing their performance.

[Brief explanation of the drawing]

Fig. 1 is an explanatory diagram of the principle of the present invention, Fig. 2 is a configuration diagram of an embodiment of the present invention, Fig. 3 is an explanatory diagram of a straight line generation state, Fig. 4 is an operation flow of the straight line generating section, and Fig. 5 is a bending diagram. An explanatory diagram of a point detection state, FIG. 6 shows a bending point detection operation flow, and FIG. 7 shows an example of extracting a bending point. 1... Pattern holding section, 2... Tracking section, 3...
Straight line generation section, 4... Contour cutting section, 5... Comparison section, 6... Bend point generation section, 7... Compressed data holding section.

Claims (1)

[Claims] 1. In a pattern information amount 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 generating section that generates a straight line between two points; and a contour line between the two points. and a matching detection means for detecting whether or not a straight line between two points matches a contour line between two points, and a straight line between two points extracted from the outline of a pattern, A pattern information amount compression method characterized in that information on bending points of the contour is extracted by detecting whether or not the contour lines match, and the contour information is expressed using the bending point information. .