JPH01184586A - System for compressing pattern data by curve approximation - Google Patents

Abstract

PURPOSE:To generate a recovery pattern with high quality by extracting curvature part ornament to be connected to a curve stroke, and setting a curve approximation section optimum for a curvature part. CONSTITUTION:A curvature part ornament extraction means 12 extracts the curvature part ornament 18 to be connected to an oblique line/curve stroke 17 based on an inflection point 15, a horizontal/vertical stroke 16, and the oblique line/curve stroke 17. Next, at an optimum curve approximation section setting means 13, the curvature part ornament 18 extracted at the curvature part ornament extraction means 12 is separated from the oblique line/curve stroke 17 to be connected to the means 12 completely, and the curve approximation section is set on them, respectively. Curve approximation by an (n)th-order spline function is applied on a set curve approximation section at a curve approximation means 14, respectively, then, corresponding compression data is outputted.

Description

[Detailed Description of the Invention] cii Essential] This invention relates to a pattern data compression method that compresses pattern data by approximating the contour lines of patterns such as characters and figures using straight lines and curves, and particularly relates to a method for extracting decorative parts. The aim is to obtain a high-quality restored pattern by extracting the curve and setting an appropriate curve approximation section for that part. Horizontal/vertical strokes and diagonal lines from contour vectors/
In a pattern data compression method that compresses pattern data by approximating the contour line with a straight line and a curved line after extracting a curved stroke, a curved part decoration extraction means for extracting a curved part decoration connected to the curved stroke; The present invention is configured to include an optimum curve approximation section setting means for separating the extracted curve part ornament and the curve stroke connected thereto and setting an optimum curve approximation section.

Further, the present invention is configured to include curve approximation means for performing curve approximation using an n-th order spline function to a curve stroke within the curve approximation section set by the optimum curve approximation section setting means.

[Industrial application field]

The present invention relates to a pattern data compression method for compressing pattern data by approximating the contour lines of patterns such as characters and figures using straight lines and curves, and particularly relates to a method for extracting decorative parts.

[Conventional technology]

When inputting patterns such as characters and figures, the inputted patterns are stored in the memory, and when outputting, the pattern data from the memory is retrieved and recorded or displayed.

When storing such patterns, it is desirable to use as little memory capacity as possible. For this reason, instead of storing characters and figures as full dots, some kind of data compression is performed and stored, and the data is restored when outputting. method is used.

One such data compression method is to focus on the outline of a pattern and store the pattern as outline data. This method not only reduces the amount of data, but also provides a high-quality restoration pattern, so it is expected to be applicable to electronic publishing systems and high quality printers.
It is attracting attention.

In particular, when data is compressed by approximating the outline of a pattern using straight lines and curves, diagonal lines and curved strokes are generated more smoothly even when enlarged or reduced during restoration, compared to methods where the outline is approximated using only straight lines. As a result, high-quality restoration patterns can be obtained.

In such a data compression method, it is desired that a smoother and higher quality restoration pattern can be obtained even when the data is expanded. In order to meet these demands, the present applicant has published Japanese Patent Application Laid-Open No. 61-208184 entitled "Pattern Information m Compression Method".
, Japanese Patent Application Laid-Open No. 62-063384 "Pattern Similarity Transformation Method", Japanese Patent Application Laid-Open No. 62-1401824 "Pattern Similarity Transformation Method", Japanese Patent Application No. 1987-118920 "
"Compression method for pattern data", patent application No. 61-11748
No. 5 “Diagonal line and curved stroke extraction method”, patent application 1986
Proposed conventional methods such as No. 1-220400 "Pattern Compression Method Using Curve Approximation", Japanese Patent Application No. 1982-091805 "Pattern Data Compression Method", and Japanese Patent Application No. 139117-1983 "Pattern Data Compression Method Using Curve Approximation"I've done it.

The overall operation of each of the above methods is as follows: First, the contour of one turn of dots is vectorized by linear approximation, and then horizontal/! r! This method extracts straight strokes, ornaments, and diagonal/curved strokes, and then approximates the contours of the extracted diagonal/curved strokes using a B-spline function.

Here, we pay particular attention to the decoration extraction method. Figure 1θ (a
) shows an example of the outline of a character dot pattern. In this case, in addition to the straight part 3.4 and the curved part 5.6, there is a straight part decoration 1 sandwiched between the straight part 3.4 and a curved part decoration 2 sandwiched between the curved part 5.6 and the straight part 3. . As shown in FIG. 11, the conventional method for extracting straight line decoration 1 is to obtain horizontal strokes E+, E2 and vertical stroke E3 from bending points P1 to P7 extracted from the contour line in FIG. For the contour structure connected to the stroke, horizontal /! I!
Find the bending point P2 farthest from the end point of the direct stroke,
If the distance is within a certain darkness value, the surrounding bend/point P
The part consisting of +=P3 was extracted as a decoration.

[Problem to be solved by the invention]

However, in the conventional example described above, the curved part ornament 2 shown in FIG. 10(a) could not be extracted. Also, the 10th
The curved part decoration 7 sandwiched between the curved parts 8 and 9 as shown in Figure 7 cannot be extracted in the same way, so the 12th
As shown in Figure (a) or (b), each part consisting of a curved part 5 and a curved part ornament 2 (as shown in the figure (a)) or a curved part 8 and a curved part ornament 7 (as shown in the figure) is one curve approximation interval lO
Or, if you apply B-spline function approximation to this, the curve approximation interval is not appropriate, so
For example, as shown by arrow A2 in FIG. 9(b), decorations connected to curved parts in the restored pattern disappear, making it impossible to obtain a high-quality restored pattern, especially when the pattern is enlarged. It had a point.

An object of the present invention is to obtain a high-quality restoration pattern by extracting a curved part ornament and making it possible to set an appropriate curve approximation section for that part.

[Means to solve the problem]

FIG. 1 is a diagram explaining the principle of the present invention. First, the curved part decoration extraction means 12 extracts a curved line based on the bending point 15, horizontal/vertical stroke 16, and diagonal line/curved stroke 17 (hereinafter simply referred to as the curved stroke 17) extracted from the outline of the pattern in advance. The curved part ornament 18 connected to 17 is extracted. This operation is realized, for example, by examining the structure of the contour pattern located between the horizontal/vertical stroke 16 and the curved stroke 17 or the structure of the contour pattern added to the curved stroke 17. As the structure information of the contour pattern, for example, the length of the contour line connecting the bending points 15 and the direction of the contour vector toward the adjacent bending points are used.

Next, the optimum curve approximation section setting means 13 completely separates the curve section decoration 18 extracted by the curve section decoration extraction means 12 and the curve stroke 17 connected thereto, and assigns a curve approximation section 19.2 to each of them. Set.

The curve approximation means 14 performs curve approximation using a zero-order spline function for each of the curve approximation sections 19 and 20 set in this way, and outputs the corresponding compressed data.

[For production]

By using the above method, if there is a pattern having a curved part decoration 18 as shown in FIG. 1(a), first, as shown in FIG.
15) and the curved stroke pair S1 and 32 (corresponding to the same <17) are extracted. On the contrary,
The curved part decoration extracting means 12 of FIG. 1(a) extracts the curved part decoration 18 in the following manner, for example.

First, among curved stroke pairs, we focus on curved strokes whose contour vectors (pect vectors connecting adjacent bending points) point to the third quadrant on the x-y coordinates with each bending point as the origin. , extract its initial bending point. Figure 1 (
In C), each contour vector on the curved stroke S1 satisfies the above conditions, and its first bending point P2 is extracted.

Next, similarly to the fist, we focus on the curved stroke in which each contour vector points to the first quadrant, and extract the bending point at the end of the curved stroke. 1st
In the diagram (C), each contour vector on the curved stroke s2 satisfies the above conditions, and the final bending point P+ is extracted.

If the length of the contour line (contour vector) connecting the above two bending points is shorter than a certain dark value (and if any of the contour vectors composing it indicates the fourth quadrant, then the contour The part is extracted as a curved part decoration.In FIG. 1(C), the contour vector connecting the two bending points P1 and P2 corresponds to it, and this part is the curved part decoration 18 in FIG. 1(b).
is extracted as

Next, the optimal curve approximation section setting means 13 of FIG. 1(a) separates the curve part decoration 18 and the curve stroke to which it is connected, and sets a curve approximation section, for example, in the following manner.

That is, each curve stroke S l % S in FIG. 1(C)
2, examine the angles formed by each contour vector to find discontinuous bending points. In Fig. 1(C), the bending point P
3 corresponds to that. As a result, the curve stroke S1 in FIG. 1(C) is changed from the curved stroke S1 in FIG.
bl into two curve approximation sections 19 and 20.

Once the optimal curve approximation section 19.20 is determined in the above manner, the curve approximation means 14 of FIG. 1(a) calculates
By performing curve approximation using a linear spline function for each section, corresponding compressed data can be obtained.

If a restoration pattern is created based on this, Figure 1 (b
) can be obtained.

〔Example〕

Embodiments of the present invention will be described in detail below.

(A) Overall configuration of an embodiment of the present invention First, FIG. 2 is an overall configuration diagram of an embodiment of the present invention. After extracting the contour line from the character dot pattern stored in the character dot pattern storage 21, the bending point extraction section 22 extracts the bending point and stores it in the bending point attribute table 23 along with the respective coordinates.

Horizontal/! ! ! The straight stroke recognition unit 24 extracts horizontal strokes and vertical stroke parts from the contour vector of the character dot pattern obtained by connecting adjacent bending points on the bending point attribute table 23, and adds a horizontal stroke to each corresponding bending point in the table 23. Add stroke and vertical stroke attributes. The decoration extraction section 25 extracts the decoration parts connected to the horizontal/vertical strokes of the pattern from the contour vector of the character dot pattern, and adds the attributes of the decoration to each corresponding bending point in the table 23.

The diagonal line/curve stroke extraction unit 26 extracts diagonal line/curve strokes of a single-valued function from the horizontal/vertical strokes and the contour vector without the decoration attribute using four-way classification, which will be described later.

The curve approximation section setting section 27 performs two steps: 1. Setting the contour of the single-valued function obtained in the diagonal line/curve stroke extraction section as a curve approximation section; Then, the process of resetting the curve approximation section,
■Processing for integrating horizontal/vertical strokes and curved strokes, and ■Processing for setting curve approximation sections corresponding to curved part decorations (including processing for extracting curved part decorations). be.

In the polynomial coefficient calculation section 2, the curve approximation section setting section 27
For the diagonal line/curve stroke extracted in each curve approximation section set in , each coefficient of the contour approximation polynomial (n-th order spline function) is calculated using the bending point.

The residual sum of squares determination section 30 determines the sum of squares of the coefficients calculated by the polynomial number calculation section 28, and determines whether the coefficients are appropriate.

The vibration determination unit 31 determines whether the obtained polynomial is vibrating.

The contour restoration unit 29 for diagonal lines and curved strokes uses the residual 2
If the multiplicative sum conditions and vibration judgment conditions are not satisfied, the resolution of the character dot pattern is small and the number of bending points is small.
If the quality is not sufficient when compressed data is created using only bending points, DDA (Digital Differential
tial analyzer) to perform linear approximation to increase the number of reference points for calculating the number of polynomial coefficient calculation units 28.

The compressed data creation unit 33 by curve approximation obtains the coefficients of the obtained polynomial and the coordinate values of both end points of the curve-approximated section,
The data is stored in the compressed data storage unit 34.

A compressed data creation unit 32 using linear approximation obtains compressed data in which horizontal/vertical strokes and decorations are linearly approximated, and stores it in a compressed data storage unit 34 .

In the above configuration, each processing section 22 and 24 to 33 is realized as a program executed by a computer system or dedicated hardware, and also includes a character pattern storage section 21, a bending point attribute table 23, and compressed data. The storage unit 34 is provided on a storage medium such as a disk device.

The operation of the embodiment having the above configuration will be described in detail below. The process explained based on the embodiment shown in FIG.
B) Bend point extraction processing, (C) Horizontal/! r! It consists of direct stroke recognition and decoration extraction processing, (D) diagonal line/curved stroke extraction processing, (E) curve approximation section setting processing, CF) processing for compressed data creation, and CG) data restoration processing, and especially (E). This is a part related to the present invention. A step-by-step explanation will be given below.

(B) Bend Point Extraction Process The bend point extraction process is performed in the bend point extraction unit 22 shown in FIG. 2, FIG. 3 is an explanatory diagram of the operation of this embodiment, and FIG. It is.

The processing for the character dot pattern shown in FIG. 10(a) will be described below with reference to FIG. 4(a) as an example.

First, as shown in FIG. 3, the bending point attribute table 23 (corresponding to FIG. 2) contains extracted bending points (including coordinates) and line group numbers (horizontal/!I!direct stroke pairs) as their attributes. ), position (where the bending point is on the left, right, top, or bottom of the horizontal/vertical stroke), decoration (indicates whether it is a decoration of the character extracted by the decoration extraction unit 25), curve attributes (bending point The results of four-way classification of the contour vector formed by P1 and Pnl), the curve approximation section (the curve approximation section where the bending point bends), and the curve group number (representing a curve/diagonal line pair) are provided as a table.

Then, the bending point of the outline is extracted from the character dot pattern in the character dot pattern storage unit 21 (FIG. 2) by the bending point extraction unit 2.
Extract with 2. The bending point is a point corresponding to the bending part of the contour line, and in this example, as shown in FIG. Find the point of inflection.

As a method for determining the inflection point, for example, the "pattern information amount compression method" published by the present applicant (Japanese Patent Application Laid-open No. 61-2
08184) can be used.

In other words, since the character contour line forms a closed loop, two adjacent points of the contour line represented by a group of dots are set as the first bending point, which is the starting point Ps.
In addition, the end point is Pe, and the point P is traced on the contour line while detouring from the end point to the start point, and D D A (Dig
Ital Differential Analyze
A straight line connecting points P and Ps is generated at point P and Ps, and the deviation between the straight line and the contour line is examined. Assuming that point P3 is at a corner, when point P comes to one corner in front of it, the above deviation disappears, so the position of point P at that time is set as the second bending point. Next, by making this second bending point equivalent to Ps and performing the same process, you can find the third bending point one place before the second bending point. You can ask for it.

In this way, in the character dot pattern of FIG. 10(a), bending points P1 to P15 are extracted as shown in FIG. 4(a), and the bending point number and its coordinates are stored in the bending point attribute table 23 of FIG. (not specifically shown) is stored.

(C) zk: Uta Oto Tori Mino Trok Certification and Decoration Lottery Office Etsuji Horizontal/! I! A straight stroke recognition unit 24 and a decoration extraction unit 25 (FIG. 2) extract horizontal strokes, vertical strokes, and decorations connected to these strokes.

From the coordinates of each bending point on the bending point attribute table 23 (Fig. 2), these are lines that are a straight line approximation between each bending point (a straight line approximation of the contour of the striking pattern) as shown in Fig. 4 (a). (contour vector) and extract it.

This method includes, for example, the "pattern similarity conversion method" (Japanese Patent Application Laid-Open No. 62-063384, published by the present applicant).
(No. Publication) technology can be used.

That is, first, the horizontal/vertical stroke recognition unit 2A determines the direction of the line segment between each bending point, and gives a contour number such as EISE2 to a horizontal line segment and E to a vertical line segment. . Contour numbers are not assigned to items that are not in the horizontal/vertical direction (those that do not meet the predetermined rules). Next, E
For contours marked with i (i=1.2, . . . ), pairs are determined from the degree of overlap and distance, and line group G is determined.

Detection of horizontal strokes and vertical strokes can be easily performed using the coordinate values of bending points. For example, if the bending points at both ends of a line segment are Pi (Xi, Yi), Pj (Xj, Yj), then if X1=Xj, Yi#Yj then it is a vertical line, Yi=
Y J s X If i≠Xj, it is a horizontal line.

In this example, as shown in FIG. 4(a), the bending point P4,
P5, P+a, and P+5 (the bending points indicated by the "mouth" in the figure) are recognized as the bending points of the horizontal stroke or vertical stroke, and rGJ is entered in the line group number column of the bending point attribute table 23.
is attached, and the same number is attached to the target line group.

For example, the horizontal stroke of bending points P4 and P5 and the bending point P1
4, P+5 horizontal strokes are labeled G1 at each bending point as a pair of line groups, as shown in FIG. Also, the position of each line group from the center of the pattern is written in the position column. That is, the bending points P4 and Pj are located above the line group G+, and P141P1
Information that 5 is located under the line group GI is given to the bending point attribute table 23 in FIG.

Next, the decoration extraction unit 25 (FIG. 2) extracts the decorations connected to the horizontal/vertical strokes using a certain threshold value from the end point of the line group (G + in this case) on the bending point attribute table 23 of FIG. In other words, in Fig. 4(a), the bending points P+, P
The portions t and P3 are extracted as decorations.

Next, for each bending point extracted in this way, information about the fact that they are ornaments as an attribute, the number of the corresponding line group, and the positional relationship in either the upper, lower, left, or right direction with respect to the line group is added to the bending point attribute. It is given to table 23. That is, in FIG. 4(a), the bending points P1, P2, and P3 are decorations, and information that they are located above the line group G1 is added to the bending point attribute table in FIG. 3.

CD) Diagonal line/curve stroke extraction process Next, diagonal line/curve stroke extraction processing
A curved stroke extraction unit 26 (FIG. 2) extracts diagonal lines/curved strokes.

This method includes, for example, the "diagonal line and curved stroke extraction method" (Japanese Patent Application No. 1988-1-1), which has already been filed by the present applicant.
17485) can be used. The procedure is shown below.

(i) First, in the bending point attribute table, with respect to bending points without horizontal/vertical strokes and decorative attributes, the direction of the contour vector between each bending point is classified. For that reason, the fifth
As shown in the figure (, the origin O is set as the bending point P+ and the next bending point P
It is determined in which of the first to fourth quadrants the direction of the contour vector toward ++r lies, and curve attributes A to D are added to the bending point attribute table 23.

For example, in the example of FIG. 4(a), the contour vector from the bending point P5 to the bending point Ps is in the first quadrant, so the curve attribute rAJ is written at the starting point P5 of the contour vector as shown in FIG. .

(ii) Next, for each bending point in (i), consecutive bending point sequences having the same curve illumination are integrated and grouped, and diagonal lines and curved strokes of the monovalent function are extracted. The stroke number is then assigned to the curve approximation section column of the bending point attribute table 23.

For example, in FIG. 4(a), the bending point P 71 P 8
1Ps, Pto are continuous and because of the same curve illumination "C" are integrated and grouped to extract diagonal line/curve strokes. In this example, Figures 3 and 4 (a)
As shown in S t HS 21 S 38Sa,
The diagonal line/curve stroke of Ss is extracted. In addition, S
6. S? This will be discussed later.

(in) Next, a contour pair of the extracted diagonal line/curved stroke is extracted.

That is, for each extracted contour line, the direction of the contour line, the length of the contour line, and the distance between each contour line are used to create a correspondence between each contour line, and a diagonal line/curved stroke is created. A pair of contour lines constituting the image is extracted.

Now, when there are N groups of bending point sequences representing outlines in a character pattern, the total number of bending points in group j is set as nj (j=+1.2....N), and each group in group j Let the bending point be Pj,i (j=1.2.
..., N; i=1.2. --・, nj), and the x, y coordinates of each bending point in group j are X(Pj, i), Y
As (Pj, i), the next step knob 1 to step 5
By performing the processing described above, pairs of contour lines forming diagonal lines and curved strokes are extracted.

Step 1: First, as a contour line length calculation process, using the following equation (1),
Calculate the length of the outline of each group.

(1) Here, Lj (j-1, 2, . . . , N) is the length of the contour line of group j. Also, the end point of the outline of group j is the next bending point after the bending points Pj, nj. For example, when group j and group (j+1) are adjacent, the end point of the outline of group j is the next bending point of the bending point Pj, nj. This is the starting point of the contour line of (j+1), so X (Pj, nj+1)=X (Pj+1.1)Y (
Pj, nj+1)-Y (Pj+1.1) holds true.

As is clear from equation (1), the length Lj of the contour line represents the length of the locus of the contour line of group j.

In the case of FIG. 4(a), group S I+ S 21
S31S4. Lj for SS (j-1 to 5)
is calculated.

Step 2: Also, in the contour line length calculation process, each group satisfying L th<L j is extracted for the set threshold Lth. This allows regular diagonal lines/
Groups for contours of small length that cannot be contours forming a curved stroke are removed.

This threshold Lth is experimentally determined from various contour length values of many character and graphic patterns.

Next, the curve attribute (AT
R(j)), the attribute ATR(
k) sets all groups k that satisfy the correspondence shown in Table 1 as matching candidates for group j.

Table 1 Arrows indicate the directions of the groups, and as is clear from Table 1, the direction of ATR(k) for groups that are matching candidates for group j is equal to ATR(j
) is set in the opposite direction.

This is due to the fact that the attributes of a pair of contour lines that can be constituent elements of a diagonal line/curved stroke have attributes in opposite directions.

In the case of FIG. 4(a), the matching candidates for group S+ are group S3. S4, and the matching candidate for group S2 is group S5.

Step 3: Next, as an inter-contour distance calculation process, the inter-contour distances dj,k are calculated using the following equation (2) for all groups k that are matching candidates for group j.

Here, Mjx= (X (Pj, 1) +X (P j, n j+1) ) /2Mj)'
= (Y (Pj, 1) +Y (Pj, nj÷1) ) /2 Mkx= (X (Pk, 1) +x (Pk, nk+1)) /2 Mk7= (Y (Pk, 1) +Y (Pk, nk+1))/where Pj, nj+1 (or pi(, nk+1) is the next bending point of Pj, nj (or Pk, nk),
When group j and group (j+1) are adjacent to each other, P
j, nj+1 becomes the starting point of group (j+1).

That is, the distance between group j and the contour line of group %1
ldj, here, the midpoints Mj (Mjx, Mjy) and Mk (Mkx, M
ky) is used.

Step 4: Next, as a contour pair identification process, group j is determined based on each contour length information calculated in the contour length calculation process and each contour line distance information calculated in the inter-contour distance calculation process.
The discrimination amount DJk expressed by the following equation (3) is calculated for all groups k that are matching candidates.

D jk-d j, k+ l L j-Lk l...
・(3) Here, a3. h is the distance between group j and the contour lines of the group, which is determined by equation (2).

Lj and Lk are the contour lengths of group j and the group determined by equation (1), and 1Lj-Lkl indicates the absolute value of the difference between the two contour lengths.

Group j is munched with the group that minimizes the discrimination mD3k and paired with the contour of group j.

Step 5: For all j, perform steps 2 to 4 described above to obtain contour pairs for all groups.

This result is written to the bending point attribute table 23. In FIG. 4(a), for example, a curve stroke S3 of bending points P7 to P++ and a curve stroke S4 of bending points P++ to P13 are paired, and "Fl" is assigned as the curve group number for these bending points. is written to the bending point attribute table 23 in FIG.

With the above operations, the extraction of the diagonal line/curve stroke of the monovalent function is completed.

The contents of the bending point attribute table 23 after this extraction is shown in FIG. 3, for example, and FIG. 4(a) shows this as a pattern. However, Sa.

S7 will be described later. In FIG. 4(a), rOJ is the bending point on the curved (diagonal line) stroke, "mouth" is the bending point on the horizontal/vertical stroke, and "Δ" is the horizontal/!
r! This is the bending point of the decorative part that connects to the straight stroke.

In this example, the character dot pattern in Figure 10(a) is 5
Book diagonal line/curved stroke (section) S+=35 and 1
This is approximated by a pair of horizontal/vertical strokes G-.

Through the processing described above, horizontal/vertical strokes and diagonal/curved strokes are appropriately extracted for the character dot pattern shown in FIG.
Linear decorations connected to horizontal/vertical strokes as shown in 1 of a) are extracted. However, in the case of FIG. 10(a), the curved part decoration 2 connected to the straight part 3 and the curved part 5°6
is not extracted as a decoration, and as shown in FIG. 4(a), the bending point P7 to P++ is expressed by one curved stroke S3. Therefore,
If the character dot pattern is restored as it is, as mentioned above, it will not be possible to express the curved part decoration as shown by arrow A2 in FIG. 9(b). This is the 10th
In a character dot pattern as shown in FIG.

Therefore, in the embodiment of the present invention, the above (13)
After each process of (D), the process of extracting the curved part decoration as described above is performed.

This process is realized as part of the process of the curve approximation section setting section in FIG. Specifically, as shown in FIG. 6, it consists of a curve section decoration extraction section 35 and an optimal curve approximation section setting section 36. Below, the m-function block diagram in Figure 6, Figures 3 and 4 are shown below.
This will be explained using diagrams.

First, the curved part decoration extraction section 35 extracts the curved part decoration. This processing is realized by examining the structure of the contour pattern located between the horizontal stroke and the curved stroke and the structure of the contour pattern added to the curved stroke. The outline length and the direction of the outline vector are used as the structure information of the outline pattern. The algorithm is shown below.

Step 1; First, in the bending point attribute table 23 (Fig. 2),
Among a pair of contour lines for which a curve approximation section is set, that is, a curve stroke and a group of curves, attention is paid to a bending point where the curve attribute is "C", that is, the third quadrant.

In the example of FIGS. 4(a) and 3 corresponding to FIG. 1θ(a), the bending point P7. P8. T'9. PI o corresponds to this. Also, FIG. 4(C) corresponding to FIG. 10(b)
In the example, the bending point P2. P3. P turtle and P5 correspond to it.

Step 2: Next, in the curved stroke (curve approximation section) that includes the curved point of interest (indicating the third elephant urine), extract the first curved point of the curved stroke and set it as Sl. This processing occurs at block 37 in FIG. In the example of FIGS. 3 and 4(a), the bending point P7 is set to SZ.

Moreover, in the example of FIG. 4(C), the bending point P2 is SI! It is said that

Also, from the bending point attribute table 23 (Fig. 2), in the curve stroke (curve approximation section) corresponding to the bending point where the curve attribute is "A", that is, pointing to the first quadrant, the final bending point is extracted. , it is E.

shall be. This process is also performed in block 37 of FIG.
In the example of FIGS. 3 and 4(a), the bending point P13 is E.

It is said that Moreover, in the example of FIG. 4(C), the bending point P1 is E. It is said that

Next, if there is an inflection point E− next to the inflection point En, then En
The process branches to either Step 3.4 or Step 5 depending on whether or not the attribute of at least one of and E n@ is horizontal stronic. This processing is performed at block 38 in FIG. 3 and 4 (in the example 810, the attribute of the bending point P+a=E It can be identified by the attribute "upper" or "lower" being assigned to the position column of the attribute table 23 and the fact that the curve attribute column is blank.

Further, since there is no bending point next to the bending point En in the ClO example shown in FIG. 4, the process branches to step 5.

Step 3; If there is a horizontal stroke, the bending point En or Enn
is located on the lower contour of the horizontal stroke, and the bending point attribute table 23 (FIG. 2) is checked to extract the bending point PK, which is the end point of the upper contour of the horizontal stroke. This is done in block 39 of FIG. In the example of FIGS. 3 and 4(a), the bending point P5 is PK
It is said that This is a bending point that has the same line group number G1 as the bending point corresponding to the horizontal stroke in the bending point attribute table 23 of FIG. 3, and has "above" in the position column.
All you have to do is look for one that has the attribute .

Step 4: After the bending point PK is found through the above processing, the structure of the contour line between the bending point P Extract that.

(I) The length of the contour line between the bending points PK and se is shorter than a certain threshold Th.

(■) Among the bending points between the bending point Pt and 81, there is a curve whose attribute is "D", that is, indicates the fourth quadrant.

In the above, the process (I) is the process (1) of the process (D).
) and is performed in block 40 of FIG. Further, since the threshold Th differs depending on the size of the character pattern, it is determined accordingly by referring to a table (not shown).

The condition determination (1) is then performed in block 43 of FIG. Further, the process (If) can be performed by referring to the bending point attribute table 23, and is performed in block 42 of FIG.

In the example of FIG. 3 and FIG. 4(a), since the above conditions (I) and (If) are satisfied at the bending point PK=P5 and the bending point Sε=P7, this part, that is, the bending points P5, P6, P7
The part is extracted as a curved part decoration.

Step 5; If it is determined in step 2 that there is no horizontal stroke, steps 3 and 4 are not performed;
Perform this step 5. Here, the inflection points E l'l and S
The structure of the contour line between J is examined, and when the following line types are satisfied, it is extracted that the part is a curved part decoration.

(1) The length of the contour line between the bending point En and 81 is shorter than a certain threshold Th.

(II) Among the bending points between E n and 84, there is a curve whose attribute is "D" and indicates the fourth quadrant.

In the above, the process (1) is performed in step 4 (1).
) and is performed in block 41 of FIG. The conditional judgment (I) is performed in block 43 of FIG. 6 in the same manner as described above.

Further, the process (II) is also performed in block 42 of FIG. 6 in the same manner as described above.

In the example of FIG. 4(C), the bending point E. =P+ and bending point 5R
In order to satisfy the conditions (1) and (IF) above at P2, this portion, that is, the bending point P1. The part P2 is extracted as a curved part decoration.

As described above, once the curved part decoration has been extracted by the process in the curved part decoration extracting unit 35 of FIG. Move.

Here, we examine the slope of each contour vector of the curved stroke that connects to the curved part decoration (strictly speaking, a part of it), and as a result, as shown in Figure 4 (in Figure 4) or Figure 1), the curved part decoration is The curve approximation section 46 or 19 and the curve approximation section 47 or 20 of the curve stroke are set completely separate, so that spline function approximation (described later) can be applied to each. To do so, perform the following two steps.

Step 6: First, calculate the angle formed by the contour vector between each bending point on the curved stroke connected to the curved part ornament, and extract the bending point corresponding to the contour vector with discontinuous slope. For that, the contour vector p, p, ;+.

The angle formed by the contour vector PJ+IPunyu is set to a certain threshold T
Evaluated by hθ1, same (PJP trace and P, 1-a P 4
Evaluate the angle formed by Thθ2, and calculate Pa-t P j and P
, IN P4tλ is evaluated by Thθ3 to find a point where the slope is discontinuous.

If the above process does not find a discontinuity point,
Find the horizontal contour vector P4P,;,+ and find the inflection point P
Let j◆1 be the discontinuous point.

The above processing is performed in block 44 of FIG. As a result, as shown in FIGS. 3 and 4 (in the 810 example, the bending point P s
In the example of FIG. 4(C), the bending point P3 is extracted as a discontinuous point.

Step 7: When a discontinuous bending point is found as described above, the corresponding curve stroke is divided at the bending point, and the contents of the curve approximation section on the bending point attribute table 23 (FIG. 2) are corrected. This processing occurs at block 45 in FIG.

That is, in the example of FIG. 3 corresponding to FIG. 4+8), the curve approximation section indicated by S3 is divided into S6 and 87.

Through step 6.7 above, it becomes possible to set the optimal curve approximation section as shown in Figure 4 (b) or Figure 1), and when curve approximation is performed using the B-spline function described later. , can express that part clearly.

(E-21 Other curved sections/similar section setting processing and above CB
) to (D] and (E-1) for each curve approximation section (see FIG. 3) on the bending point attribute table 23 (FIG. 2) using the B-spline function described later. In addition to performing curve approximation, the curve approximation section setting unit 27 in FIG. 2 also performs the following two main processes. Note that the following processes are not directly related to the present invention. 7 and does not appear in the example in Figure 4.
A brief explanation will be given using the diagram and the explanatory diagram of FIG. 8.

Process 1: This process is a technique described in the previously published "Pattern Data Compression Method" (Japanese Patent Application No. 1983-091805) by the present applicant.

Now, for example, as shown in l) in FIG. 7, there is a bending point P3 of the vertical stroke GI indicated by "mouth" and a curved stroke S1 of the monovalent function indicated by "○". S2 bending point P1. P
2. If there is a contour line pattern consisting of Pa, Ps, and P6, the vertical stroke G1 is approximated by a straight line, the curved strokes S+ and Sz are approximated by a B-spline function to create compressed data, and a restored pattern is obtained from this. In this case, only a restored pattern without smoothness is obtained as shown in FIG. 7(b). This is especially common in hiragana patterns.

Therefore, by integrating the curved strokes St and S2 of the monovalent function and the vertical stroke C+ (or horizontal stroke),
Extract curve strokes of multivalued functions.

Then, new strokes are divided into curved strokes of the multivalued function so as to maintain smoothness, and as shown in FIG. 7 (Lz), the curved strokes of the monovalent function S3.
It is divided into St and S5. And according to this division result,
The contents of the curve approximation section in the bending point attribute table 23 (FIG. 2) are rewritten.

By creating compressed data by approximating the curve approximation section newly set as described above using a B-spline function, the resulting restoration pattern is as shown in Figure 7(d). You can get something smooth.

Processing 2: This process is based on the previously filed “Pattern Data Compression Method by Curve Approximation” (Patent Application No. 1391/1986) filed by the present applicant.
This is the technology described in No. 17).

Now, for example, as shown in FIG. 8(a), the bending points PI, P7°P8 of the vertical stroke group G1 indicated by "mouth", and "
The bending point P2 of the curve strokes Sl and S2 of the monovalent function indicated by ``○''. P3. 'P4. If there is a contour line pattern consisting of P5°P6, the sub-straight stroke group G+ is approximated by a straight line, the curved strokes Sl and S2 are approximated by a B-spline function to create compressed data, and a restored pattern is obtained from this. Then, as shown in FIG. 8(b), only a restored pattern without smoothness is obtained. This often appears in kanji patterns such as ``harai''.

Therefore, the curve stroke S1 of the monovalent function! ! ! Direct stroke group CI and S2 and 01 are integrated, and Fig. 8(C)
The inflection point p +, P2 . P3+ p,.

P5 is a curve stroke (curve approximation section) S3, and bending points Ps, Pb, P7 . Let pH be a curve stroke (curve approximation section) Sa. Then, in accordance with this, the contents of the curve approximation section in the bending point attribute table 23 (FIG. 2) are rewritten.

By creating compressed data by approximating the curve approximation section newly set as described above using a B-spline function, the resulting restoration pattern is as shown in Figure 8(d). You can get something smooth.

CF) Compressed data creation process The contents of the bending point attribute table 23 (see Fig. 3) in Fig. 2 created as described above, especially the bending point coordinates and their attributes (line group number, decoration, curve attributes, Create compressed data using the curve group number and curve approximation section.

In the above extraction, horizontal strokes, vertical strokes, and decorations connected to these are extracted as straight lines and subjected to straight line approximation, and only diagonal lines/curved strokes are extracted so as to be subjected to curve approximation.

Therefore, when the character pattern extracted in this manner is enlarged or reduced, long curved strokes or diagonal lines with noticeable irregularities can be reproduced as beautiful patterns.

In addition, the approximation interval for the diagonal line/curve stroke is set as a curve of a monovalent function, and there are no local maximums or minimum values, so it is possible to verify the presence or absence of vibration phenomena in the obtained curve.
A suitable curve is obtained. First, data creation for the curve approximation section will be explained.

Once the curve approximation interval is determined, there are various methods for approximating and finding an appropriate curve. Here, we will discuss the "Pattern Data Compression Method" (Patent Application No. 61-118), which has already been filed by the present applicant.
A smoothing method using an nth-order spline function, particularly a method using a numerically stable B-spline function, as shown in No. 920) is used.

This method only requires storing polynomial coefficients instead of the many bending points of a curved section, and can significantly compress data.

Curve approximation; As is well known, B-spline smoothing methods include a fixed node method that provides a node string from the outside, a node addition method that adaptively provides a node string internally, or a sequential division method. There are many ways to give , and it depends on the shape of the curve, so here we will use the latter method of adding nodes.

Smoothing method using B-spline function (node addition method)
The general formula S (x) is shown in equation (4).

However, m is the order, nt is the number of nodes, c3 is the coefficient, Nj, m
+1 is the (m+1)th order difference quotient. The coefficient Cj of equation (4) is obtained from the least squares approximation condition. Specifically, it satisfies the evaluation formula (5)...
・ ・ ・(5) However, δ2 is the sum of squared residuals, δ'th is the dark value of the sum of squared residuals,
yi is the y-coordinate value of the i-th reference point, σ' is the observation error, n
is the total number of reference points, and observation error σI2 is a coefficient representing the weight of the reference points and which point is given importance. Here, the order m of the spline function is set to 3, and the observation error σ1' is set to the minimum at the reference points at both ends, and that at other reference points is set according to the slope of the curve.

Also, depending on the slope of the curve, it is approximated not only by the 1 (West function S (x)) of X shown in equation (4) but also by the monovalent function S (y) of Y. For example, in Fig. 4 (al), the curve approximation Section S2,
35.36 is approximated by a monovalent function of X, and S+,
Sa, S? is approximated by a monovalent function of Y. The above processing is carried out by the polynomial coefficient calculation unit 28 and the residual 2
This is performed in the sum-of-multiplies determining section 30.

Vibration determination: As mentioned above, in the present invention, the number of local maximum values and local minimum values that exist in each segment (line segment) that is the target of curve approximation is known in advance, so by checking the number after curve approximation, vibration can be detected. You can determine whether you are awake or not.

Normally, for a curve stroke of a monovalent function, there are no local maximum values or local minimum values within each segment to be approximated, so by examining these, it can be determined whether vibration is occurring. This process is performed by the vibration determination section 31 in FIG. 2 as follows.

First, a method for checking the presence or absence of vibration in a curved stroke that is originally a monovalent function will be explained. The presence or absence of local maximum values and local minimum values is
This can be found by dividing the obtained curve into small pieces and checking the sign of the differential coefficient at each point, but to save the effort of calculating the differential coefficient, this is done as follows.

Each segment is determined based on the attributes of the contour vectors between bending points classified into four directions at 90° intervals.
By examining the attributes of each divided section, the presence or absence of local maximum values and local minimum values can be determined, and the presence or absence of vibration can be determined. Assuming that the X coordinate of the first divided point is Xl and the y coordinate is 5 (XL),
The attribute can be determined by checking the sign of (XL?l +X L ) and the sign of (S (x, n) −3(XL)) in the interval between (j2jl) and l. Next, processing steps for vibration determination will be described.

Step l--- Curve is divided into N3 division points (N
Divide into f-1) pieces.

Step 2 - Find the attribute of division point 2=1.

The attributes shown in Table 2 are determined by determining whether (N2-x+) and (S (N2) S (XI)) are positive or negative.

Step 3-1 Find the attribute of the division point x=2 in the same way, and check whether it matches the attribute of x=i twice.

Step 4--If the attributes match, determine the attributes for β=3 as well, and check the match/mismatch of Wb with ρ=1. If the attributes do not match, it is determined that vibration is present, and the process is terminated.

Step Knob 5 ----1 = 4 to J=N, -1, and if the attribute matches are confirmed up to fi-Ns-1, tlii! It is determined that there is no II.

Next, a method of checking the presence or absence of vibration in a curved stroke originally generated from a curved stroke of a multivalued function will be explained. An example of this is, for example, 34 in FIG. 7(C). Each segment of the curve stroke of the multivalued function is
As explained in E-2), since it is determined by the integration and re-curve division of the curve stroke of a single-value function, each segment of the curve stroke of a multi-value function is determined from the attribute of the direction of the curve stroke of a single-value function. The attribute of direction is clear.

The processing steps for vibration determination for a curved stroke of a multivalued function will be described below.

Step 1' - Check the curve attributes for a certain curve approximation section from the bending point attribute table 23 (FIG. 2). If all the curves in the section have the same attributes, it is regarded as a section in which no maximum value or minimum value exists, and the above-mentioned steps 1 to 5 are performed to determine vibration. Otherwise, two types of attributes are stored in AT (1) and AT (2).

Step 2' -Curve with N8 dividing points (N
, -1) (divide into Im.

Step 3' ---CXi+ at each division point by -x
+) and (S (x匈) S (x I)) The attributes shown in Table 2 are determined by determining the sign of S (x I).

Step 4' - Examine the attributes of all division points, set the number of attribute types to NATR, and set each of the NA3 attributes to AT'
(1) - Store in AT' (NATR).

Step 5'...--If NAIK≠2, it is assumed that vibration is occurring and the process is terminated.

Step 6'...-AT (1)=AT' (1
) and AT (2)=AT' (2), it is determined that there is no vibration; otherwise, it is determined that there is vibration.

Table 2 The contour restoring unit 29 for diagonal lines and curved strokes in FIG. 2 performs the calculation using the equation (4) above. Note that if there are few bending points, the reliability of the error obtained by equation (5) is low, and vibration phenomena are likely to occur, making it difficult to obtain an appropriate curve. Therefore, if there are few bending points, D
The lines are connected by straight lines generated by DA, and the number of reference points is increased to perform curve approximation. Further, even if there are many bending points, if the error condition of equation (5) and the vibration determination condition described above are not satisfied, the bending points are connected by DDA, the number of reference points is increased, and curve approximation is performed.

First, the polynomial coefficient calculation unit 28 in FIG. 2 obtains the coordinates of the bending point of each curve approximation section from the bending point attribute table 23,
The contour restoring unit 29 for diagonal lines and curved strokes generates a nodal sequence, and the coefficient Cj is calculated using equation (4).

S (x) is calculated, and the residual sum of squares judgment unit 30 calculates the residual sum of squares for S (x) obtained by equation (4), and the residual sum of squares is
(4), that is, the coefficient C so that the sum of the products satisfies the equation (5).
j is recalculated, and the vibration determination unit 31 further performs vibration determination. If the vibration determination condition is not satisfied, the coefficient calculation is performed again to find a coefficient Cj that satisfies both the residual sum of squares condition and the vibration determination condition. .

When the coefficient Cj of the B-spline function is found in this way, the compressed data creation unit 23 by curve approximation encodes this coefficient Cj and the start and end points of the curve approximation section as compressed data, and stores it in the compressed data storage unit 34. do.

Further, for horizontal strokes, vertical strokes, and decorations connected to these, a compressed data creation unit 32 uses straight line approximation to encode end points of straight lines as compressed data, and stores the encoded data in a compressed data storage unit 34.

(G) Data Restoration Process Regarding the restoration of the compressed data of the character dot pattern obtained through the processing of (B) to (F) above and the pattern generation,
“Pattern data compression method” already filed by the applicant
(Japanese Patent Application No. 61-118920), so the details will be omitted, but as a general outline, from the bending point attribute table 23 in FIG. 2 and the contents of the compressed data storage section 34,
Linear transformation of bending points for horizontal/vertical strokes and ornaments connected to them, contour restoration using DDA, linear transformation of polynomials for diagonal lines/curved strokes, function value calculation, contour restoration, connection of straight line approximation part and curve approximation part , and processing such as filling.

FIG. 9 shows the enlarged character pattern restored by this embodiment in comparison with the conventional example. As shown by the arrows A+ ((a) in the same figure) and A2 ((b) in the same figure), it can be seen that in this example, the curved part decoration, which could not be reproduced in the conventional example, can be clearly reproduced. This is because, for example, the curved part decoration 2 and curved part 5 in FIG. 10(a) can be extracted as separate curve approximation sections 46 and 47 as shown in FIG. 4).

This makes it possible to obtain a restored character pattern of higher quality.

Note that the present invention is applicable not only to character patterns (but also to extraction of curved decorations of other graphic patterns).

〔Effect of the invention〕

According to the present invention, it is possible to extract a curved part decoration connected to a curved stroke and set an optimal curve approximation section for the curved part, so that it is possible to generate a high-quality restoration pattern.

[Brief explanation of the drawing]

FIGS. 1(a) to (C) are diagrams explaining the principle of the present invention, FIG. 2 is a diagram showing the overall configuration of an embodiment of the invention, FIG. 3 is a diagram explaining the bending point attribute table 23, and FIG. Figure (1m1~(C) is
5 is an explanatory diagram of the four-direction classification of contour vectors; FIG. 6 is a functional block diagram of the curved part decoration extracting unit and the optimal curve approximation section setting unit according to the present invention; FIG.
Figures (a) to (d) are operation explanatory diagrams of process 1, and Figure 8 (a)
) to (d) are operation explanatory diagrams of process 2, FIG. 9(a),
(bl is a diagram showing the restored patterns of this embodiment and the conventional example, Figures 10(a) and (b) are diagrams showing an example of the outline of a character dot pattern, Figure 11 is a straight line decoration 12(a) and 12(b) are explanatory diagrams of the problems of the conventional example. 12... Curved portion decoration extraction means 13... rIt regular curve curve approximation section Setting means 4...
Curve approximation means, 15...Bending point, 16...Horizontal/vertical stroke, 17...Diagonal line/curve stroke, 18...Curve part decoration, 19.20...Curve approximation section, Patent application People Fujitsu Ltd. Contour Vectre's 4-direction 4-direction M ■ 4 Fig. 5 (0) (b) (C) (d) b) (C)
(d) 1st work of point part 2 ヱ ■Figure 8 Figure 8 Riichi Kinjoshi Retsuhon Daisei 1h4 & Kari 11 No. 9 Conventional 4'111 (b) Restoration of ＼゛Cuso display l: Diagram Character dot pattern @Ja no 4 717 Figure 10 Name shown/Figure 2 Problems with conventional 4 columns due to curved part Figure 12 Hll Ming year continuation amendment book 1986 7theta month sunset 3, correction. Patent applicant address 1015 Kamiodanaka, Nakahara-ku, Yozaki-shi, Kanagawa Name (522) Fujitsu Limited Representative Takuma Yamamoto 4 Sub-agent Postal code 102 Address Kojimachi, Chiyoda-ku, Tokyo 6-1-18
Section 6, “3. Detailed Description of the Invention” column of the specification to be amended and Figure 7, Contents of the amendment 1) In the 15th line of page 5 of the specification, the phrase “1 turn” has been replaced with “pattern”. Correct it with "No." In the 18th line of page 11 of the 1st book, the words ``ta character donto patano'' are corrected to ``areru''. In the 3rd line of page 13 of the specification, ``Ring approximation polynomial'' is corrected to ``approximate polynomial''. ] In the 5th line of page 13 of Hosojo, the phrase ``calculating the number of cases'' has been corrected to ``calculating the coefficient.'' 5) In the 13th page, line 16 of the specification, the phrase "count calculation" should be corrected to "coefficient calculation." 6) On page 15, lines 1 and 2 of the specification, it says "Figure 3 is an explanatory diagram of the operation of this embodiment, and Figure 4 is the bending point attribute table 2.
FIG. 3 is an explanatory diagram of No. 3. ” has been corrected to read “FIG. 3 is an explanatory diagram of the bending point attribute table 23, and FIG. 4 is an explanatory diagram of the operation of this reference example.” Figure 3 on page 1 is corrected as shown in the attached sheet.

Claims (1)

[Claims] 1) Extract the bending points (15) of the contour of the pattern, and extract horizontal/vertical strokes (16) and diagonal/curved strokes (17) from the contour vector between the extracted bending points (15). )
In a pattern data compression method that compresses pattern data by approximating the contour line with a straight line and a curved line after extracting the contour line, a curved part decoration (18) connected to a curved stroke (17) is used.
a curved part decoration extracting means (12) for extracting the curved part decoration (12), and separates the curved part decoration (18) extracted by the means and the curved stroke (17) connected thereto, and extracts the optimal curve approximation section (19, 20). ). A method for compressing pattern data by curve approximation, characterized in that the method comprises: optimal curve approximation section setting means (13) for setting the following: 2) It has a curve approximation means (14) that performs curve approximation by an n-th order spline function to the curve stroke within the curve approximation section (19, 20) set by the optimal curve approximation section setting means (13). 2. A pattern data compression method using curve approximation according to claim 1.