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

Abstract

PURPOSE:To perform reproduction so as to connect a vertical/horizontal line to a curve stroke linked smoothly to the line smoothly, by providing the unifying means of the vertical/horizontal line and the curve stroke linked smoothly to the line, and an n-degree spline function approximating means for a unified stroke. CONSTITUTION:The vertical/horizontal line of a character or a graphic and the curvature point data with attribute of the curve stroke are inputted to the unifying means 10 of the vertical/horizontal line and the curve stroke, and the unifying means 10 performs the unification of the vertical/horizontal line and the curve stroke linked smoothly to the line by remarking the vertical/ horizontal line and the curvature point with the attribute of the curve stroke. The spline function approximating means 12 generates a spline function being approximated to the unified stroke, and performs the approximation of the vertical/horizontal line of the character or the graphic and the data of the curve stroke as the spline function. Therefore, smooth continuity can be attached on the reproduced connection part of the vertical/horizontal line and the curve stroke.

Description

[Detailed Description of the Invention] [Summary] In a pattern data compression method that approximates the outline of a pattern using straight lines and curved lines, a means for integrating vertical/horizontal lines and curved strokes, and a means for approximating the integrated strokes with a spline function are provided. It is characterized by having

[Industrial application field]

The present invention relates to a pattern data compression method that expresses patterns such as characters and figures using straight lines and curved lines that approximate the contours of the patterns.

Writing characters and figures in memory in a tondo pattern ↑a requires a large memory capacity, but if the contours of the characters and figure patterns are approximated by straight lines and curves, and the straight lines are written as vectors and the curves are written as functions ↑,a, It becomes possible to significantly reduce the amount of stored data, and it becomes easy to enlarge or reduce the data at the time of restoration.

[Conventional technology]

The present inventors have proposed various pattern data compression methods that approximate the contours of character and graphic patterns using straight lines and curved lines.
(Patent Application No. 6L-118920), “Pattern Compression Method Using R-Curve Approximation” (Patent Application No. 6L-220400),
``r-curve approximation section setting method'' are two or three examples. In this method, the contours of characters and figures are first vectorized by linear approximation, and then vertical/horizontal lines, decorations, diagonal lines/curved strokes are extracted based on information such as the direction and length of the vector, and the Stroke B
− Approximate with spline function.

[Problem that the invention seeks to solve]

The problem with this method is that the vertical/horizontal line β road, which is often seen in alphabetical characters as shown in Figure 4, and the curve i! There is a problem in that it is not possible to reproduce with high quality a scale consisting of 2 blocks (in this example, a frame). FIG. 7 is an example of this. In the reproduced character "Nigiri", the arrow F1. The connection between the vertical line and the diagonal curve indicated by F2 is not smooth.

The reason why the connection between vertical/horizontal lines and curved strokes becomes uneven is that vertical/horizontal lines are approximated by straight lines, curved strokes are approximated by curved lines, and so on.
This is because they are performed separately, and only the continuity of the zero-order derivative is guaranteed at such connection points.

The present invention improves this point and allows vertical/horizontal lines and curved strokes connected to them to be recreated from compressed data. The aim is to create a smooth connection even between rough edges.

[Means for solving problems]

As shown in Figure 1, in the present invention, vertical/horizontal lines and 1%
A means 10 for integrating curved strokes that continues smoothly, and a means 1 for approximating an nth-order spline function for the integrated strokes.
2 will be provided.

[Effect]

The bending point data with attributes of vertical/horizontal lines of characters, figures, decorations, and curved strokes is input to the vertical/horizontal line and curved stroke integration means 10, and the integration means Focusing on the bending point, the vertical/horizontal line and the curved stroke that smoothly follows it are integrated.

A means 12 generates a spline function that approximates this integrated stroke, and data of this portion (vertical/horizontal lines and curved strokes) of characters and figures is held as the spline function.

The first derivatives and the like are also continuous within the same function, so through the above processing, the connection between the reproduced vertical/horizontal line and the curved stroke becomes smooth and continuous. Next, each of the processes will be explained.

Integration of vertical/horizontal lines and curved strokes: Extraction of curved strokes that smoothly connect with vertical/horizontal lines is performed by checking the continuity of the slope of the connection between vertical/horizontal lines and adjacent curved strokes.

The positional relationship between two straight lines that make up the vertical/horizontal lines of a character or figure and two pairs of adjacent curved lines (outline lines) that make up a curved stroke is determined by the order of contour tracing (in the direction of the arrow in Figure 4 or this Conversely, the tracing direction is predetermined to be clockwise or counterclockwise), there are cases where a curved stroke outline follows a straight line, and there are cases where a curved stroke outline precedes a straight line. Below, the third line has a straight line followed by a curved line.
This will be explained using the example shown in the figure, but the same applies when there is a curved line in front of the straight line.

In FIG. 3, the mouth indicates the end point or bending point of a straight line representing the outline of the vertical/horizontal line of a character or figure, and the circle indicates the bending point of a curved line representing the outline of the curved stroke of the character or figure. The vector connecting these nodes or bending points is P i−P 1+l
, P i+2 + . . . Here, the contour vector Pi is a component of a vertical line, and the contour vector P i+ l + P i+ 2 is a component of a curve stroke.

(1) First, a contour vector with a vertical/horizontal line attribute whose length IPil of the contour vector Pi is greater than a certain threshold Lth is extracted.

■Next, the contour vector Pi of the vertical/horizontal line and the contour vector P1+1 of the following curved stroke (this length is L
th)). Contour heta 1-
Let the angle between Pi and Pl, 1 be ν, if cosν is larger than a certain threshold cosvth, it is assumed that there is continuity (smooth continuity) and proceed to the next ①, and if it is smaller, it is assumed that there is no continuity and the angle between the Pi and P1+1 is There will be no integration.

(2) Furthermore, the continuity of the slope between the contour vector Pi and the contour vector P1+2 of the curved stroke next to the above-mentioned P1+1 is checked. Let the angle formed by the contour vectors Pi and P, +2 be τ, and if cosτ is larger than a certain threshold cost th, it is assumed that there is continuity, and the contour vectors Pi and P i+ 1
Attach the attribute of integrating straight lines and curves to , and thus perform the integration of straight lines and curves.

FIG. 5 shows an example of integrating vertical/horizontal lines and curved strokes.

(al is the conventional example, Pi and P i + l + P i
+ 21... are treated separately (not integrated)
However, in the present invention, this is integrated as shown in (bl), and P!+
P i+I I P H+2+...is 1
Let there be two consecutive contour vectors. This vector is shown by a thick line in the figure, and extends from Zl through 72 to 23 as shown. The outer contour vectors are similarly integrated into Z3
It continues from to Za.

Approximation using spline function: The section represented by each contour of the integrated stroke is defined as a curve approximation section (referred to as a segment), and this is approximated using the node addition method of the B-spline function shown in equation (1) below.

In this method, the reference point and the curve 5f The coefficient cj is determined so that the error is within a certain dark value as shown in equation (2). If the error does not fall within the dark value, the section is divided into two and nodes are automatically added.

However, nj is the number of nodes, cj is the coefficient, Nj, a is the 4th order difference (basis function), however, δ2 is the sum of squared residuals, δ2th is the threshold of δ2, xl
.

y is the X and Y coordinate value of the i-th reference point, σ1 is the observation error, n is the total number of reference points The resulting spline function 5tX1 (or 5(y)) guarantees the continuity of the derivative at the nodes at both ends. However, even if it is divided at an added node, the derivative at that node has the property of being continuous. Therefore, the derivatives are continuous at all points other than both endpoints within the l segment.

In the above equation, conventionally only the X (or Y) coordinate values of both end points were given as the initial value of the node, but in the present invention, the connection point Z2 of the vertical straight line and the curved stroke outline in FIG. Also give the nodal coordinates. That is, the initial value of the number of nodes n is set to 3 only for the outline of a stroke that is a combination of vertical/horizontal lines and curved strokes, and both end points and the connection point (Z2) of the combined stroke are given as the initial values of the nodes. Other ways to give initial values, such as how to select X and YO monovalent functions, observation error σ,
The method of giving is the same as before. By doing this, vertical/
The continuity of the derivative at the connection point between the horizontal line and the curved stroke is preserved, and the stroke can be generated with high quality.

〔Example〕

FIG. 2 shows an embodiment of the method of the present invention. The input is a character (figure) dot pattern 20, which is sent to the bending point extractor 2.
2 or the like, and the obtained compressed data is stored in the storage unit 46. The present invention is implemented by a curve approximation section setting section 32 and a polynomial coefficient calculation section 34.

Briefly explaining each process, the bending point extracting section 22 converts the contour of the character dot pattern into a vector by linear approximation, and extracts the bending point which is the end point of the contour vector. For this extraction process, for example, Japanese Patent Application Laid-Open No. 61-208184 r
Pattern information compression method j can be used. The extracted bending points are stored in the bending point attribute table 30 together with attributes to be described later.

Next, the horizontal/vertical line recognition unit 24 and decoration extraction unit 26 use information such as the direction and length of contour vectors and the distance between contour vectors to identify horizontal and vertical lines, that is, vertical/horizontal lines, and decorations (Mincho The starting and ending points of Chinese characters in the body, protrusions at bends, etc. are recognized, and (attribute) information indicating this is added to contour vectors and indented points. For this process, for example, Japanese Patent Application No. 60-182251 "R-pattern Similarity Transformation Method" can be used.

Next, in the diagonal line/curve stroke extraction unit 28, for vertical/horizontal lines and contour vectors without decorative attributes, first, the contour vectors are classified in four directions, and the directional attributes are added to the contour vectors. By integrating contour vectors with , two pairs of contour line candidates constituting a curved stroke are extracted. 4-way classification means checking which of the 1st to 4th quadrant the vector is located at, with the starting end of the contour vector at the origin of the A-D is assigned and codes A-D are added to the vector depending on the quadrant in which it exists. Next, correspondence is made using information on the four-directional correspondence of the integrated contour vectors, the length, and the distance between the contour vectors, and a pair of contour lines forming a curved stroke is extracted. Extraction of diagonal lines and curved strokes is possible, for example, in ``Character pattern enlargement/reduction method with diagonal line width control function'' (Japanese Patent Application No. 6O-282271) and ``Diagonal lines and curve strokes''.
"Heroku's Extraction Method" (Patent Application 1986-
) can be used.

The contour line of the curved stroke is a line segment of a single-valued function of X and Y, and for the curve of this one-stroke function that consists of kanji and katakana characters, the contour line is approximated by a spline function. For multivalued function curves that are often found in hiragana and alphanumeric characters, the multivalued function is extracted by integrating the −valued function line segments, and a new curve approximation interval is set to approximate the spline function. .

The curve approximation section setting section 32 performs a process of directly setting the contour line of the single-valued function obtained by the diagonal line/curve stroke extraction section 28 as a curve approximation section, and a process of integrating the -valued function to extract a multivalued function. Furthermore, three processes are performed: a process for resetting the curve approximation section (such as a process for the outline of the hiragana "no"), and a process for integrating the vertical/horizontal lines and curve strokes performed in the present invention.

The polynomial coefficient calculating section 34 and the residual sum of squares determining section 36 first calculate the average slope of the curve approximation section from the slope of the contour vector, and then calculate the average slope of the curve approximation section from the slope of the contour vector.
, S (yl) to be approximated.

The coefficient CjO of the equation (1) is calculated based on the error evaluation of the equation (2), and there are two types of reference points: when only the bending points are used and when all contour points are used. If the resolution of the character dot pattern is high, a high-quality pattern can be generated using the compressed data obtained from only the bending points, and the compressed data can be generated in less calculation time than when all contour points are used. If the resolution is low, the quality of the reproduced pattern will not be sufficient if compressed data is created using only bending points, so all contour points are used.

The contour restoration unit 40 for diagonal lines and curved strokes performs a process of restoring contour points from bending points.

The observation error σ1 in equation (2) above is set using the slope of the contour vector so that the error between the reference point and the obtained spline curve is equal to the distance (length in the normal direction from the curve to the reference point). do. (The way to give the initial nodes in Equation 11 is vertical/
In the case of a stroke that integrates a horizontal line and a curved stroke (
In the case of the present invention) gives the x (or Y) coordinates of both end points and the X (or Y) coordinate of the connection point of the vertical/horizontal line and the curved stroke, and in the case of other strokes, the X (or Y) coordinates of both end points Give the coordinates.

In this way, the coefficient Cj of the spline function is determined to be one based on the error evaluation, and then it is determined whether the obtained spline curve is oscillating or not (it is not a simple curved curve but may have small undulations). The vibration determination unit 38 determines the coefficient Cj to be appropriate, and uses this (Cj) as compressed data by curve approximation. This compressed data is stored in the storage section 44.

For strokes other than diagonal/curved strokes, bend points, horizontal and
Attribute data of vertical lines (vertical/horizontal lines) and decorations are compressed data by linear approximation, and this is stored in the storage unit 42. Further, these compressed data are read out from the storage units 44 and 42 and stored in the storage unit 46.

A curve approximation section setting section 32, a contour restoration section 40 for diagonal lines and curve strokes, a polynomial coefficient calculation section 34, a residual sum of squares judgment section 36. ``Method'' (Patent Application Sho 6l-118920)
, Pattern Compression Method Using R-Curve Approximation” (Patent Application Sho 6l
-220400), and “Curve approximation interval setting method”
(Special application 1986=) can be used.

[Effects of the Invention] As explained above, the conventional method cannot generate curved strokes that smoothly connect vertical/horizontal lines with high quality, but according to the present invention, curved strokes that smoothly connect vertical/horizontal lines and curved strokes cannot be generated with high quality. A continuous high-quality pattern of derivatives can be generated. FIG. 6 shows a character reproduced by the method of the present invention, in which straight line/curve connection portions Fl and F2 are smoother than in the conventional method shown in FIG. These are enlarged patterns generated from compressed data.

[Brief explanation of drawings]

Fig. 1 is a block diagram showing the principle of the method of the present invention, Fig. 2 is a block diagram showing an embodiment of the invention, Figs. 3 and 4 are explanatory diagrams showing examples of curves following straight lines, Fig. 5 6 is an explanatory diagram showing an example of integrating straight lines and curved lines, and FIGS. 6 and 7 are diagrams showing examples of reproduced characters. FIG. 6 is the method of the present invention, and FIG. 7 is the conventional method.

Claims (1)

[Claims] A compression method for pattern data expressed by vectors and functions, in which vertical/horizontal lines and decorative parts of the outlines of characters and graphic patterns are approximated by straight lines, and diagonal lines/curved stroke parts are approximated by curves, Compression of pattern data by curve approximation, characterized by comprising means (10) for integrating vertical/horizontal lines and curved strokes smoothly connected thereto, and means (12) for applying n-th order spline function approximation to the integrated strokes. method.