JP2646475B2 - Character data input / output device and input / output method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention obtains character fonts (typefaces, brushstrokes, etc.) as binary data by an image reading device, compresses them while eliminating noise without losing the characteristics of the characters, and stores them. The character is reproduced from the compressed data. In particular, a character font is automatically converted to digital data from a character matrix, and is used to reproduce the digital data at an arbitrary size and at an arbitrary position, and can be easily used in a printing device, a word processor, and the like.

[0002] A character font is a group of characters having a prescribed shape. If the character font is to be freely reduced and enlarged, it must be stored not as the two-dimensional shape itself but as abstract data. . Since the number of characters including kanji is large, if the number of data for each character is large, it takes a long time to input and a large storage device is required. In addition, the output takes time and is not economical. It is better that the number of data per character is as small as possible.

Conventionally, there are two methods for storing data for each character in a storage device. A method of encoding character data as a sequence of binary data. In this method, a character is converted into a black-and-white binary image, an outline is extracted by differentiation or the like, a continuous direction of the outline is obtained and chain-coded, and a starting point and a code string are stored.

A method of extracting the outline of a character font, approximating the outline with a straight line or an arc, and storing the coordinates of the starting point and functions such as a straight line and an arc. This is a convenient method for input and output because data can be compressed.

The present invention is a method belonging to the latter category. If the outline of the character font is extracted and then chain-encoded, the quality of the reproduced character is inferior when enlarged since the outline point sequence coordinates are stored by the pixel which is the minimum unit of the image. Since the coordinates of the enlarged character are determined by multiplying the stored data by a certain multiplier, the outline point sequence is not smooth but jagged. Therefore, it is not possible to reproduce a magnified character with a desired magnification by the chain coding method. The contour is considered to be a combination of a straight line, an arc and the like, but may be a part of another shape. This could be represented by some function. Considering the ease of data handling, the smaller the number of data, the more convenient. In order to accurately represent a character font, data that can accurately approximate a contour line must be obtained. Therefore, there is a need for a method of approximating a contour line as accurately as possible by minimizing the number of data.

[0006]

2. Description of the Related Art Considering that the outline of a character font is a collection of straight lines, circular arcs, and other smooth curves, it is necessary to first detect those points where the curvature changes. The point at which the curvature changes is called the junction. Contour lines can be approximated by straight lines, arcs, or simple functions between adjacent junctions. Then, it is important to determine the joining point as accurately as possible. When the joining point is determined, a segment, such as a straight line, an arc, or a curve, representing between two adjacent joining points is obtained. This piece is represented by a piece function. In this way, the entire contour can be represented by a combination of the junction point and the piecewise function starting from the junction point. The approximation accuracy is determined by the accuracy of the junction and the accuracy of the piecewise function.

[0007] A character font is two-dimensional information. The prior art on this is poor. Japanese Patent Application No. 63-21948 discloses a data compression method for one-dimensional information. In this method, a continuous curve is approximated by a quadratic curve, and the curvature of each point is obtained from the approximate expression to obtain a differential discontinuous point.
It can be said that the differential discontinuity point corresponds to the junction.
Next, data between adjacent differential discontinuous points is approximated by a quadratic function and data is compressed. This quadratic function can be specified by simple parameters. Then, the one-dimensional data can be approximated by specifying the parameters of the differential discontinuous point and the quadratic function sequence.

[0008]

Conventionally, there has not been a technique capable of storing a character font with a small amount of data and reproducing a character of an arbitrary size. Since the above method is used when the independent variable is time and the dependent variable is displacement, the data is one-dimensional information. For example, when dealing with one variable such as sound.

This cannot be used for data compression of two-dimensional information like a character font. Since the character font can represent x as a function of x with the horizontal axis as x and the vertical axis as y, it seems that this method can be extended to two dimensions. But it is not. Since the outline of the character font is closed two-dimensional information, if the independent variable is x, y becomes a multivalent function of it, and it is not easy to use this method.

[0010] Further, since the object of the above-mentioned method is not two-dimensional information, it has no clear meaning such as a contour line or a joint point. The change in the variables is random, the meaning of the differential discontinuity is not yet clear, and it is not considered whether there is an error in determining this. However, in the case of a character, many straight line components are included, and many arc portions are included. It does not mean that the variables change randomly.

Considering an independent variable in order to apply the above-described method to two-dimensional information, it is conceivable that the x and y coordinates of the contour are set as dependent variables to the independent variable. However, in this case, it is not clear what represents the curvature. A junction point appears for the first time when dealing with two-dimensional information, but it is not simply obtained as a differential discontinuity point. The effects of noise must be considered.
It may appear as a junction due to noise. It is necessary to remove this and find the correct junction.

The present invention provides a character font data input / output device which reads a character font, automatically compresses and stores the data, and reproduces the character as an arbitrary size character at an arbitrary place. The goals can be summarized as follows.

(1) Efforts to create fonts are omitted. (2) Capable of handling high quality characters. (3) The amount of font data is small.

[0014]

The character data input / output device of the present invention optically reads character font data,
A character reading device that stores data corresponding to a finite number of pixels arranged vertically and horizontally, a contour extraction mechanism that extracts a contour of a character read in association with pixels arranged vertically and horizontally, and a two-dimensional extracted contour. A contour point sequence storage mechanism for storing coordinates (X, Y) for each continuous group, and a secondary function in which the X and Y coordinates of the contour point sequence for each group are t as an independent variable and x and y as dependent variables. A data approximation mechanism A for approximating by a piecewise polynomial of, repeating a least square approximation while increasing the number of dimensions of a quadratic piecewise polynomial until the approximation accuracy falls within a predetermined range, and obtaining an approximate polynomial for each group of contour point sequences; A curvature calculation mechanism for calculating a curvature at each point of the contour point sequence for each group in the x, y space from the approximation result;
A perfect circle extraction mechanism that extracts a perfect circle from the curvature data for each group, and temporarily joins points with a curvature that is infinite or greater than a certain value from the curvature data of the contour point sequence excluding the perfect circle A temporary joining point position extracting mechanism for extracting as a point, one of a predetermined number of preceding and succeeding points on an outline point sequence of one of the temporary joining points (first temporary joining point) as a first joining point candidate, One of a predetermined number of preceding and succeeding points on one of the other temporary joining points (neighboring joining points) on the same contour point sequence within a predetermined radius from one temporary joining point is set as a second joining point candidate. The first fixed point, the first temporary joint point, the neighboring joint point, and the second
Means for selecting the neighboring joint points, the first fixed points, and the second fixed points so that the fixed points are arranged in a line in this order; and all combinations of the first joint point candidates and the second joint point candidates. The degree of conformity of the first joint point candidate is determined based on the smoothness of a line connecting the four points of the first fixed point, the first joint point candidate, the second joint point candidate, and the second fixed point most smoothly. A means for determining, an optimal joint extracting mechanism having means for selecting the first joint candidate with the highest degree of fitness and selecting the optimal joint instead of the first temporary joint, and two or more continuous straight lines or Unnecessary joints are removed from the optimal joints, which are the starting points of two or more continuous arcs, that can maintain the approximation accuracy even if they are not found, and are removed to integrate straight lines or arcs. The mechanism and the optimal joint that has not been removed A final junction SL billion device that stores Te,
When a predetermined approximation accuracy cannot be obtained by approximating a straight line and an arc between adjacent final joining points in the same group of point sequences in the order of t, an independent variable and x and y as dependent variables are used. Approximate with the piecewise polynomial of the above, repeat the least squares approximation while increasing the number of dimensions of the quadratic piecewise polynomial until the approximation accuracy falls within a predetermined value, and make a straight line, circular arc, piecewise A data approximation mechanism B for approximating by a polynomial, a compressed data storage mechanism for storing the coordinates of the final joint point and a parameter of a function for approximating between adjacent final joint points for each group of the perfect circle data and the point sequence; A contour reproducing mechanism for inputting the stored compressed data and obtaining a parameter of a function approximating between the coordinates of the perfect junction data and the coordinates of the final joining point for each group of point sequences and an adjacent final joining point to reproduce the contour line; , The pixel inside the reproduced contour line and the pixel outside And character reproduction mechanism to associate a different value, characterized in that it comprises a reproduced data output mechanism for outputting the reproduced character font as a character.

[0015]

FIG. 1 is a table showing the entire configuration. Here, all the mechanisms are described in advance. A. Image storage device 1 B. Contour point sequence extraction device C. Outline point sequence storage device D. Data approximation mechanism AE Curvature calculation mechanism E '. Approximate curvature storage device F. Perfect circle extraction mechanism G. Perfect circular storage device H. Junction point position extraction mechanism I. Junction point position storage device Optimal junction extraction mechanism K. Optimal junction storage device L. Junction point removal mechanism Final junction storage device Data approximation mechanism B.O. Compressed data output mechanism Compressed data storage device Contour reproduction mechanism Character playback mechanism Reproduction data output mechanism U. Image storage device 2

For example, the procedure for the character "@" shown in FIG. 30 will be briefly described. FIG. 30 is described again. First, "ぱ" written on paper is read by an image scanner. This is the optical reading and input of characters.
When a contour point sequence, which is a set of contour lines, is extracted, white characters are obtained. In this example, there are five groups of contour point sequences. One vertical line on the left, two parts resembling “yo” in the center, and a circle on the right shoulder have two outline points inside and outside. Using the parametric representation, the X and Y coordinates are functions of t. Each contour point sequence group is approximated by a piecewise polynomial throughout. Since a piecewise polynomial becomes a continuous function, the curvature is obtained by performing second order differentiation on each contour point sequence. A contour point sequence having a constant curvature is a perfect circle. This is separated as a perfect circle. In this example, the circle on the right shoulder is removed. The rest is a group of three contour points in this example. The place where the curvature is large is the junction. In the fourth row, crosses and curved points of the outline point sequence are marked with a cross. This is the junction. The outline point sequence may be added later.

The outline point sequence is divided by the joining points. As the joining point, a primary joining point determined as having a large curvature (referred to as a temporary joining point) may be used. In the case of a character font, since a character which is clearly drawn from the beginning is targeted, it is difficult for noise to enter the character font. Therefore, the joining point can be accurately obtained only from the curvature. This greatly simplifies the calculation.

[0018] At the joining point, there is a case where the sculpture is further repeated. In this case, the joining point is corrected in consideration of the consistency with the nearby joining point. This will be described later as a temporary joining point and a joining point candidate. It is also effective to remove unnecessary joint points after correcting the positions of the joint points. In some cases, a new junction is added. In this way, noise or the like generated in optical reading or the like can be effectively removed.

When the joining points are determined, a straight line is drawn between the joining points.
Approximate by arc and free curve. The approximations are straight lines, arcs,
Perform in the order of free curves. Because it is a character font, there are many straight lines. Particularly in the case of kanji, the ratio of the straight line portion is extremely high. Arcs are most common after straight lines. In the case of kanji, it is considered that there are many in the order of straight line, arc, and free curve. However, the reason why the order of approximation is a straight line, a circular arc, and a free curve is not because the frequency of occurrence is in this order.

Instead, approximations are made in this order to improve the quality of the recorded data. If it is approximated as a free curve from the beginning, straight lines and arcs will be approximated by quadratic curves. A set of quadratic curves cannot accurately represent a straight line or an arc. When there is noise, it is approximated that the straight line and the arc are further deformed. Straight lines and circular arcs should exist, and in order to reliably extract them, approximation is performed in the order of straight line, circular arc, and free curve. In the case of a straight line, the time required for approximation is short. The amount of data is also small. The approximation of the arc is also easy. The coordinates, radius, and center angle of the center may be given.

When approximation cannot be made with a straight line or a circular arc, a free curve is approximated. In this case, the space between the joining points is divided into n subsections and approximated by a piecewise polynomial. If the number of subdivisions is increased, the approximation can be increased, so that an approximation with desired accuracy can be made.

In this way, the parameters of the joining point, the straight line, the arc, and the free curve are obtained, and these are stored as character font data. Although it depends on the number of strokes and the complexity, data of about 300 to 500 bytes per character is sufficient. If the image is still a black and white image, there is data for all pixels constituting the screen. For example, assuming 256 pixels vertically and horizontally, 8k
Although there are bytes, the present invention can greatly compress data. Conversely, the data can be read out to reproduce straight lines, arcs, and free curves with reference to the junction. It can be reproduced to any size and any position by calculation.

[0023]

【Example】

[A. Image storage device 1] This is a device which reads a character font written on paper or the like by optical means and stores it as information decomposed for each pixel. The characters may be colored but what is needed is a black and white binary image. For example, the colored portion is black, and the portion that does not form a character is white,
A value image is stored for each pixel.

For example, 256 × using an image scanner
It is input with an accuracy of 256 dots. Of course, the number of dots is arbitrary, and the higher the number of dots, the higher the quality of the character font stored should be.However, if the number of dots is large, the calculation time and storage capacity will be large. An image reading device may be used. For each dot (pixel), whether it is a white pixel or a black pixel is distinguished and temporarily stored. Hereinafter, one pixel may be referred to as a dot. A continuous black pixel row is referred to as a dot row. Horizontal number x of a pixel on the screen to indicate a point
And a coordinate (x, y) consisting of a vertical number y. Coordinate variables are distinguished by adding various suffixes.

[B. Contour Point String Extraction Apparatus] The contour point string extraction apparatus performs an operation for obtaining a contour line of a read character. The general flow is described first. The image data is scanned from upper left to lower right to find a contour point that has not been found yet (as shown in FIG. 4). The next contour point is searched until it goes around the contour line. The contour points are marked at 2. Check up to the lower right data of the image data.

In performing this operation, the definition will be described first. An image is represented by a collection of pixels. Pixels are indicated by coordinates on the screen. The coordinates of the pixel are x in the row (horizontal) direction and y in the column (vertical) direction. The coordinates at the upper left are x = 0 and y = 0. Assuming that there are pixels of X horizontally and Y vertically, x takes a value of 0 to X-1, and y takes a value of 0 to Y-1. The coordinate system is directed downward and to the right as shown in FIG.
Since the image itself is a character input, two black and white
There is only value. Specify black and white for each pixel.

O Binary image input A characteristic function _gxy is defined as follows. (I) When a point (black pixel) exists at the coordinates (x, y) at O ≦ x <X−1 and O ≦ y <Y−1 g _xy = 1 (1) (ii) In other cases (the G _xy = 0 (2) This is a binary representation of the image, where white is 0 and black is 1.

Expression of a contour point sequence A contour point sequence is a sequence of black pixels on the outer periphery of a cluster of black pixels that are connected to the left, right, up, down, and diagonally. There is a contour point sequence not only on the outside but also on the inside. One closed point sequence is called a contour point sequence. Let U be the total number of contour point sequences. The U contour point sequences are numbered from 0 to U-1. The total number of contour points in the u-th contour point sequence is represented by N (u). A number k is assigned to consecutive points in one outline point sequence. k is 0 to N
(U) is an integer of -1.

[0029] expressed by the u th k-th coordinate of the contour points of the contour point sequence _{^{(x k u, y k u}} ). All contour points are represented by _{^{{(x k u, y k}} u)} k = 0 N u -1 u = 0 U-1 (3). _{k = 0} ^{N u -1} because the point sequence number k
Can take on values from 0 to N (u) -1. N (u) -1 includes parentheses, which cannot be made into a quarter-square, so when it becomes a variable suffix, the parentheses are removed and written as Nu-1. N u -1 = N (u)
It is -1. Since it is a suffix, it should be written on the top and bottom, but since this is not possible, it is divided into lower left and upper right.
_{u = 0} ^U-1 means that the number u of the contour point sequence group takes a value of _{0 to} ^U-1 . The number u of the contour point sequence should be indicated by adding parentheses to the right shoulder of the variable. However, since the parentheses cannot be formed into a quarter square, the parentheses are omitted. In fact, parentheses are attached as shown in the drawing. It is not a variable raised to the power of u. This is common to the parameter t and the independent variables x and y. u is a group number and is written as it is on the right shoulder of the variable, but the parenthesis is actually attached.

(Circle code) Around a certain pixel, the surrounding eight pixels are indicated by clockwise numbers 0-7. This is used to indicate the continuation of the point sequence at the contour points. It is also used to check the continuous state. The following functions α (c) and β (c) are defined using c as a chain code. The function α (c) is

When c = 3, 4, 5, α (c) = − 1 (4) When c = 2,6 α (c) = 0 (5) When c = 0,1,7, α ( c) = 1 (6)

And the function β (c) is

When c = 5,6,7 β (c) = − 1 (7) When c = 0,4 β (c) = 0 (8) When c = 1,2,3 β (c) ) = 1 (9)

Is as follows. An outline is extracted based on these definitions. As described above, as shown in FIG. 4, the entire image is scanned from upper left to right to find black pixels. The outline is a pixel on the outer periphery of the portion of the binary image where g _xy = 1, and the coordinates of the point sequence are stored while making a round around this. 1
The direction of rotation is clockwise when turning outside the area, and counterclockwise when turning inside. FIG. 5 shows the order of turning the contour points. Of course, it is possible to do the opposite, but here we will decide.

Now, it is assumed that a certain contour point in a certain contour point sequence is found. To find the next contour point, eight neighboring pixels are searched clockwise from the previous contour point around this contour point. FIG. 6 shows an example. Assume that the one marked with ☆ is the latest contour point. The next contour point is searched clockwise, but all the pixels up to the numbers 1, 2, 3, 4, and 5 are white pixels g _xy
Not applicable because = 0. The sixth pixel is a black pixel, and since g _xy = 1, it is a contour point. Since the next contour point has been obtained in this way, the next contour point is obtained centering on the sixth pixel.

Thereafter, contour points can be obtained one after another by the same procedure. Since the next contour point is obtained from eight neighboring pixels, a sequence of contour points is continuously obtained. For the contour point, the value of _gxy is set to 2. Thereby, it can be distinguished from the internal black pixel g _xy = 1. In addition, since the pixel of g _xy = 1 must be localized on the screen, the contour point is sequentially obtained, and returns to the first contour point. That is, the contour point sequence is annular. It is assumed that there are a total of U such contour point sequences. The number of the contour point sequence is indicated by u, but the point number in a certain contour point sequence u is k.

When one outline point sequence is determined, the scanning shown in FIG. 4 is restarted, and the next outline point is searched for. When this is understood, the coordinates of the contour point are determined in the same procedure. When there are a plurality of contour point sequences, these processes are performed from the upper left, and contour point sequence numbers of 0, 1,... (U-1) are assigned in order. Even when there is a hole inside, any point is detected in several scans as shown in FIG. A search for an adjacent point as shown in FIG. 6 is performed. In the case of a hole, a contour point is found counterclockwise as shown in FIG. In this manner, both the outer contour point sequence and the inner contour point sequence are searched, and the coordinates of the point sequence are stored. The value of these g _xy is 2.

Since the search for the contour point sequence is performed for the pixel of g _xy = 1, a problem arises a little if the width between the outer circumference and the inner circumference is only one pixel. FIG. 7 shows this. (A) is an annular pattern having a width of only one pixel. Pixels of g _xy = 1 are distributed in a square shape. If the width is 2 or more, the outer contour point sequence and the inner contour point sequence can be obtained without any problem by the above-described procedure. However, if the width is one pixel, g _xy = 2 since the pixel of g _xy = 1 is a contour point after the outline point sequence is first determined. The search for contour points is g _xy =
Since the processing is performed for one pixel, a contour point sequence is no longer obtained when g _xy = 2. The inner contour line is not recognized and the holes are ignored. Since this is not a good idea,
If the next contour point is below the current one, the mark (g
_xy → 2) is not performed. This point remains g _xy = 1. This is indicated by the fact that the value in the middle right is 1 in FIG. 7B. Since the value is 1, it is found as the starting point of the inner contour point. Starting from this point, an inner contour point sequence can be extracted. After all, the inner and outer contour point sequences can be extracted without ignoring the inner hole. FIG. 7C shows this.

Once the outline point sequence is determined, the inner black pixels surrounded by the outline point sequence are no longer required to define the area. Therefore, there is no need to store the internal black pixels. This can first reduce the amount of data to be stored.

[C. Contour Point Sequence Storage Device] The contour point sequence storage device is a device for storing the contour point sequence obtained in the preceding stage. (X
_k ^u, and stores this in the form of ^{_{y k u) k = 0 N}} u -1 u = 0 U-1. As described above, U is the number of all point sequences, and u is the number assigned to the point sequence. The number of points in the point sequence u is N (u)
And k is the point number assigned to this. Such things expressed by ^{_{k = 0 N u -1 u =}} 0 U-1. (X _k ^u, y _k
^u ) is the x, y coordinates of the kth point in the uth point sequence.
Again, if N (u) -1 is the suffix,
u -1 is written.

[D. Data approximation mechanism A] There are two data approximation mechanisms. This is the first one, but is appended with A to distinguish it. This is necessary for temporarily finding a place where the curvature of the outline point sequence is large and for finding a joint point. In order to determine the curvature, some of the discrete points can be adopted as data and can be determined from this. The present invention can be practiced even with such discrete curvatures. However, here, the data is approximated by a continuous function, and then the second order is differentiated to obtain the curvature. The approximation for this is the data approximation here.

Since the curvature is obtained, the usual method would be to obtain the second derivative of y with x using x as an independent variable and y as a dependent variable. But then x,
As for y, handling becomes asymmetric, which is not preferable. The present invention does not employ such a method.

In this case, the independent variable is t, the dependent variables are x and y, and the x and y coordinates of the contour point sequence for each of the continuous groups are t = independent variables and x and y are dependent variables. The approximation is performed using a statistical polynomial, and the least squares approximation is repeated until the approximation accuracy falls within a predetermined range to obtain an approximate polynomial for each group of contour point sequences. This is not for obtaining final data but for obtaining a junction point.

[0044] _{^{(x k u, y k u}} ) the coordinates of the points column k of the group u as previously described meantime. This is obtained from the outline point sequence storage mechanism described above. FIG. 9 shows the operation here. Read first from the contour point sequence storage of the contour point sequence _{^{(x k u, y k u}} ) all. This is decomposed into parameters. In other words, for each point,
Two _{^{(x k u, y k u}} ) is the corresponding common parameter t on. This also with a subscript and t _k ^u. Although it is two-dimensional information, it uses parametric variables to make this a one-dimensional problem. The second row in FIG. 9 illustrates this.

[0045] By using the parametric, (t _k ^u,
x _k ^u) and (t _k ^u, a combination of the two coordinate y _k ^u) corresponding to each point of each contour point sequence. Hereinafter, the same operation is performed for two variables, and only one of them will be described. Contour point sequence in the group ^{_{u (t k u, x k}} u) approximates the t function S _x
(T) is given as a linear combination based on a second-order full-energy function system { _m }. S _x (t) approximates x as a function of t in group u. Similarly, S _y
(T) approximates y in group u. The evaluation as to whether it is appropriate as an approximation function is made by checking whether the error is within a predetermined range by the least square method.

It should be noted that S _x (t), S _y
By (t), the entire closed curve of the outline point sequence group u is approximated at once. The whole is approximated by one function S _x (t) instead of connecting the joining points in the middle. This is because the junction has not been determined yet. As described above, there is a simpler method for determining the curvature without such approximation. This is a method of obtaining a discrete curvature by directly using data of a contour point sequence. In order to carry out the present invention, such a discrete curvature may be used. However, it is not described here, and the approximation function S _x
The generation of (t) and S _y (t) will be described.

S _x (t) is an aperiodic m-th order full-energy
Expand using the function 展開_k as a basis. _{S x (t) = Σ k} = -m M + m C k x ψ k (t) (10)

The full-function function is a function name named by the present inventor. The degree m corresponds to the degree of the polynomial. M is the number of dimensions. In general, the m-th order full-energy function has a domain of [0, T], a parameter of k,
This parameter is represented with a suffix. C _k ^x
Is the coefficient of linear linear combination. ψ _k itself is a polynomial having a value near k.

Ψ_k (T) = 3 (T / M)^-mΣ_{q = 0} ^{m + 1}(-1)^q {T- (k + q) (T / M)} ^m ₊ / ｛Q! (M + 1-q)! ｝ (11)

Where k = −m, −m + 1,..., 0,
1,2, ..., m + M

The plus added below the m-th power means that the value in the parenthesis is 0 when the value in the parenthesis is negative, and that the value is m-th when the value is positive, and is defined as follows.

(T−a) ^m ₊ = (t−a) ^m t> a, (12) 0 t ≦ a (13)

The basis function ψ _k is a chevron-shaped function having finite values from section numbers _{k to k} + m + 1 and having zero on both sides. This is 0 such as {t- (k + q) (T / M)} ^m ₊
The coordinates of the m-th order function rising from are shifted one by one (q is increased one by one), and these are superimposed. Must be equal to 0 when t> (k + m + 1) (T / M). Under this condition, the superimposition coefficient is (−1) ^q / ｛q! (M + 1-q)! It is determined as｝. The size T of the area is the number N of points in the outline point sequence group.
Although it is easy to make it equal to (u), it may be defined as being proportional. As described above, the contour point sequence is approximated by using the full-energy function. However, since there are many division points having a T / M interval, the contour point sequence can be approximated without a joint point. To increase the degree of approximation, the order m of the full-energy function may be increased. However, when the degree is high, the number of calculations increases, so that processing time is required.

The inventor's claim is that many functions representing variations in physical quantities in the natural world are expressed as linear combinations of first-order and second-order full-energy functions. The full-ency function is not a complete orthogonal normalization function. If a function up to ∞ is adopted as m and this is a linear combination, any function can be expressed. This is no doubt. However, the present inventor does not say so, but it is possible to write down the variation of the physical quantity in the natural world with a full-energy function having a small number of dimensions. Here, only m = 2 is adopted.
Thus, outlines of characters and the like can be expressed without excess and deficiency. Of course, the present invention can be configured using a full-energy function of m = 3 or more.

If the most appropriate function system is adopted and the variation of the physical quantity is expressed by the linear combination, an optimal approximation can be obtained with the fewest functions. If the function system is not good, you have to expand the expression of linear combinations based on many functions. In this case, a good approximation cannot be obtained, and the number of final data increases, resulting in a heavy load on the storage device. Also, it is not easy to read and use this. You should choose the optimal function system. The present inventor thinks that m = 2 is optimal.

The inventor uses a full-energy function of m = 2 here. FIG. 40 (a) shows the secondary full-energy
Here is an outline of the function. This is a quadratic curve over three sections. The rise and fall at both ends is a quadratic function. It is the maximum at the center point, but also a quadratic function in the vicinity. The zero-order full-energy function is a box-shaped function that takes a constant value only in one section as shown in FIG. The primary full-energy function is a triangular function extending over two sections as shown in FIG. The third-order full-energy function is a function over four intervals. Generally, the m-th order full-energy function is a smooth (m ≧ 2) function that exists over the (m + 1) section and has a maximum at the center. Both ends rise and fall to the m-th power. The function form at the center is m
It is a power. This means that the parameter _k of the base ψ _k has increased by one and the original one has been translated by one to the right. When some variation is approximated by an m-th order piecewise polynomial in a certain section, there are (m + 1) function bases having values in the section. Although m = 3 or more can be adopted, m = 2 here. That is, there is a value over three sections, and it is quadratic at the local maximum and the end point. The above equation is m = 2
When,

[0057] _{S x (t) = Σ k} = -2 M + 2 C k x ψ k (t) (14)

Ψ _k (t) = 3 (T / M) ⁻² Σ _{q = 0} ³ (−1) ^q ｛t− (k + q) (T / M)｝ ² ₊ / ｛q! (3-q)! ｝ (15)

Is as follows. The basis function is Δt− (k + q) (T
/ M)} is a superposition of the quadratic function rising from four 0-shifted laterally by T / M is the ^two _+. The number of subdivisions is a function with values from k to k + 3. k + 3
As described above, since the constant is 0, the superimposition coefficient becomes (−
1) ^q / ｛q! (3-q)! It becomes｝. The number of basis functions is M + 5. M is the number of divisions of all sections, and this is called an approximate dimension number. This should not be confused with the order m of the fluency function. This will be described with reference to FIG.
(A) shows the data points. The domain of the data is 0 to T. (B) shows a case where there are three basis functions and the number of dimensions M is one. In this case, since the number of basis functions is too small, the number of coefficients is too small to give a good approximation. However, as the number of dimensions M is increased, any complicated change can be approximated as shown in FIG. The degree of approximation can be judged by this how the original contour point sequence _{^{(x k u, y k u}} ) that is closer to. This is evaluated by the least squares method, which is

[0060] _{Q = Σ {S x (t} k u) -x k u} 2 + {S y (t k u) -y k u} 2 (16)

Is to be minimized. The range of integration is all points of the outline point sequence group u. Here, since the curvature is merely obtained, the accuracy need not be so high. A similar approximation is made in a second data approximation B described later. In that case, the accuracy is assumed to be higher. FIG. 10 is a flowchart of this part. Although determine the coefficient C _h, this rank is M. If we define a certain M,
Coefficient C _h ^x (10) is uniquely determined. However, this coefficient does not always satisfy the restriction by the least squares method. In this case, the number of dimensions M is increased by one. And this in determining the coefficient C _h of the dimension number M reaches to the desired approximation range.

In (10), S _x (t) on the left side is t
= When it is t _k, should be the _{S x (t) = x k} u. So, substituting this for (10),

[0063] ^{_{x k u = Σ h = -2}} M + 2 C h x ψ h (t k u) (17)

[0064] over this to the ψ _w (t _k ^u), adding the point sequence k.

[0065] ^{_{Σ k = 0 N-1 ψ}} w (t k u) x k u = Σ k = 0 N-1 Σ h = -2 M + 2 C h x ψ h (t k u) ψ w (t _{^{k u) = Σ h = -2}} M + 2 Σ k = 0 N-1 ψ h (t k u) ψ w (t k u) C h x (18)

Here, the change from the second expression to the third expression replaces the order of integration. Since it is a finite sequence, the order of integration can be freely changed.

[0067] The left-hand side of this equation ^{_{Σ k = 0 N-1 ψ}} w (t k u) x k
^u has a suffix w (w = −2, −1, 0,.
.., M + 2) It can be considered to be a column vector of M + 5 elements. The preceding term on the right side is the sum of the products of the full-ency functions.
_{^{k = 0 N-1 ψ h}} (t k u) ψ w (t k u) in which M + 5 column,
It can be considered as a square matrix of M + 5 rows. The right term _Ch ^x on the right side is a column vector of M + 5 columns. Since → cannot be attached to a character, a symbol representing a vector below will be attached after the character. Vectors b _x →, c _x →

The vector c _x → = ^T ｛C ₋₂ ^x , C ₋₁ ^x ,..., C _{m + 2} ^x ｝ (19)

[0069] vector ^{_{b x → = T {Σ k}} = 0 N-1 ψ -2 (t k u) x k u, Σ k = 0 N-1 ψ -1 (t k u) x k u ··· ^{_{, Σ k = 0 N-1}} ψ M + 2 (t k u) x k u} (20)

Is defined by T indicates a transposed matrix. Matrix G

[0071] _{G = {G hw} = {} Σ k = 0 N-1 ψ h (t k u) ψ w (t k u)} (21)

Is defined by During this time,

B _x → = Gc _x → (22)

The following equation holds. This is the vector b
_x →

C _x → = G ⁻¹ b _x → (23)

[0076] coefficient for dimensionality M that is a C _h can be obtained. G ^-1 is the inverse of matrix G. This is a calculation for x. Similarly for y,

S _y (t) = Σ _{h = −2} ^{M + 2} C _h ^y ψ _h (t) (24)

[0078] ^{_{y k u = Σ h = -2}} M + 2 C h y ψ h (t k u) (25)

[0079] ^{_{Σ k = 0 N-1 ψ}} w (t k u) y k u = Σ k = 0 N-1 Σ h = -2 M + 2 C h y ψ h (t k u) ψ w (t _{^{k u) = Σ h = -2}} M + 2 Σ k = 0 N-1 ψ h (t k u) ψ w (t k u) C h y (26)

Is established, and the vectors b _y → and c _y → are

The vector c _y → = ^T ｛C ₋₂ ^y , C ₋₁ ^y ,..., C _{M + 2} ^y ｝ (26 ′)

[0082] vector ^{_{b y → = T {Σ k}} = 0 N-1 ψ -2 (t k u) y k u, Σ k = 0 N-1 ψ -1 (t k u) y k u, ·· ^{_{·, Σ k = 0 N-}} 1 ψ M + 2 (t k u) y k u} (27)

Defined by Similarly to (23), for the y component,

[0084] ^{_{c y → = G -1 b y}} → (28)

The coefficient _Ch ^y for a certain number of dimensions M can be obtained. G ^-1 is the inverse of the matrix G and is the same as that used in the calculation of x. FIG. 10 describes such a thing. First, the operation is performed for the group number u = 0. The order M of the approximation starts from 1. Thus the contour point sequence ^{_{u = 0 (x k u,}} y k u) approximating the S _x (t), S _y
Coefficient C _h ^x of (t), C _h ^y is obtained. And this, (x _k ^u,
to calculate the sum Q of the squares of the difference between the y _k ^u) point.

[0086] ^{_{Q = Σ k = 0 N-}} 1 {S x (t k u) -x k u} 2 + {S y (t k u) -y k u} 2 (29)

This is compared with a predetermined threshold value ε. This is a sufficiently small determined positive constant. Here, the distance for one pixel is set. If Q> ε, the approximation is insufficient. Therefore, in this case, the number of dimensions M is increased from 1 to 2. Then the number of C _h increases one.

The same is repeated in this state. Even this is Q
If> ε, M is further increased by one. Thereafter, the approximation is repeated in the same manner, so that Q <ε.
Here, M and { _Ch ^x }, { _Ch ^y } are determined. Approximate functions S _x (t) and S _y (t) are obtained. When the calculation can be performed for the contour point sequence group u = 0, the following is performed for the group of u = 1. Similarly, when a coefficient is determined for a certain value of u, the next u
The same calculation is performed for the +1 outline point sequence. And u =
Repeat until the U-1 group. This process will be described once again with reference to FIG. It is assumed that the character "Japanese" is input on the screen. When the contour point sequence is extracted, three contour point sequence groups are obtained. The left outline point sequence has u = 0, and the right “b” portion has an outer outline point sequence u = 1 and an inner outline point sequence u = 2. From the upper left point (0,0) on the screen, the pixel values are scanned one row at a time in the right direction. The point that first hits the contour line is (t ₀
⁰ , x ₀ ⁰ ) and (t ₀ ⁰ , y ₀ ⁰ ), and the coordinates of the outline point sequence are obtained using t as a parameter. The outline point sequence coordinates x (t) and y (t) are obtained as a function of t. Assuming that the approximation is performed by using a second-order full-energy function, first, M = 1. This treats all sections [0, 1] as one section. Three basis functions ψ _-2 , ψ _-1 and ψ ₀ have values in this section. The three values of the coefficient are appropriately selected. Then, the near-end curve shown in the middle is obtained. If you expand it,
It can be seen that the error from the data is large. The error is evaluated by the sum of the squares of the error. If the approximation is insufficient, M is increased by one. In the next stage, an example of M = 2 is shown. The number of basis functions increases to four. The bottom row shows the case where M = 10. The number of basis functions is twelve. As M increases, a complicated curve can be approximated more precisely. Although the approximation described above is for obtaining the curvature, such an operation is performed for each section in the approximation at the time of data compression described later. The above is the data approximation mechanism A.

[E. Curvature operation mechanism] Since the approximate function has been obtained for all the contour point sequence groups, this is second-order differentiated to obtain the curvature at each contour point sequence group and each point. FIG. 11 shows a flowchart of the curvature calculation. K-th point of the contour point sequence group ^{_{u (x k u, y k}} u) curvature at K (t _k ^u) is

K (t_k ^u ) = ｛S_x '(T_k ^u ) S_y '' (T_k ^u ) -S_x '' (T_k ^u ) S _y '(T_k ^u )｝ / ｛S_x '(T_k ^u )^Two + S_y '(T_k ^u )^Two ｝^3/2 (30)

Can be calculated by First u =
This calculation is started from the point k = 0 in the group of contour points 0. This calculation is performed for each point. That is, if the calculation can be performed for the k-th point, then the same calculation is performed for the (k + 1) -th point. When the calculation is completed for one outline point sequence group, the process moves to the next outline point sequence. Then, the curvatures are obtained for all the points in all the outline point sequences.

[E '. Approximate curvature memory] curvature K obtained in the previous stage of (t _k ^u) point (edge point sequence group u, the point number k) is a device for storing for each.

[F. Perfect circle extraction mechanism] This is to determine whether a certain contour point sequence is a perfect circle or not based on the approximate curvature and extract a perfect circle. There are quite a few circles in the letters. The characteristics of such a character font are used. Extracting this has the following advantages. In the first case, even if a circle that is originally a circle is slightly distorted due to noise, the data is converted into a true circle, so that the noise drops and the shape can be determined more accurately. Since a circle can be specified only by the coordinates of the radius and the center, it is extremely effective in data compression.

A perfect circle means that the curvatures at each point in the outline point sequence are all equal. A perfect circle can be extracted using such a property. FIG. 12 is a flowchart. First de about the curvature K (t _k ^u) - read the data. Then, it is checked whether or not each contour point sequence group u forms a circle.
An average curvature Ku for the contour point sequence group ^u is determined. It simply averages the curvature. The group number u should be parenthesized (u), but since it cannot be included in the suffix, it is simply u. Parentheses are attached in the drawings.

[0095] _{^{K u = {Σ k = 0}} N-1 K (t k u)} / N (31)

This is the average curvature. Previously determined upper limit epsilon ₁ of curvature, the contour point row group u When the average curvature more is not a perfect circle.

| K ^u |> ε ₁ (32)

This is a case where a point having an extremely large curvature is included.
It corresponds not to a circle but to a dot that cannot be differentiated. In this case, Circle (u) = 0 indicating that the group u is not a perfect circle. If less than ₁ mean curvature ε On the contrary, the group u
May be a perfect circle. Therefore the curvature K at the point near the point of ^{_{k = 0 (t k u)}} , the absolute value of the difference between the mean curvature K ^u investigate whether this is a certain threshold epsilon ₂ smaller.

| K ^u −K (t _k ^u ) | <ε ₂ (33)

If so, this could be part of a circle. Therefore, the absolute value of the difference from the average curvature is similarly obtained for the curvature at the next point k = 1 and compared with ε ₂ . In this way, the comparison is sequentially performed for all points of the group u. As long as this inequality holds, these points are on the arc. No difference curvature and mean curvature at a point is greater than epsilon ₂ which on longer arc. The outline point sequence group including this point no longer forms a perfect circle. Circ indicating that this group is not a perfect circle
le (u) = 0.

[0102] If the difference between curvature and average curvature epsilon ₂ smaller than for all points in the group, the contour point sequence is a perfect circle. Therefore, the display Circle (u) = 1, which is a perfect circle, is given. The extraction of such a perfect circle is performed for all contour point sequence groups from 0 to U-1. Finally, it is checked whether Circle (u) = 0 for the group from the group u = 0.
If Circle (u) = 0 for all contour point sequence groups u, there is no perfect circle in this character font. If there is a circle (u) = 1, this group is a perfect circle, the center coordinates (X, Y) and the radius r are obtained, and these are input and stored in the perfect circle storage device G.

[G. Perfect circle storage device] Stores the center coordinates and radius r of the perfect circle obtained in the previous stage. Thus, the data of the group u can be described by three values. Since the character font is targeted, all contour point sequences are closed curves.
In the case of a single perfect circle, this is an isolated circle point because the entire inside is a circle filled with black pixels. In the case of a double perfect circle, the circle between the double circles corresponds to a circle (ぱ ぴ ぷ ぺ ぽ) filled with black pixels.

[H. Joining Point Position Extraction Mechanism] The joining points include a joint between a straight line and a straight line, a joint between a curve and a curve, a joint between a straight line and a curve, and the like. Since the lines with different gradients come into contact, this is called a junction. The junction plays a very important role when approximating a character font by function. Therefore, it is necessary to have a clear idea about the role of the junction, the significance of the junction, and the extraction of the junction. The present invention minimizes the amount of data while maintaining high quality character fonts through accurate and proper determination of junctions.

FIG. 13 shows an outline of the junction extraction procedure. A character is input, the image is converted into an image, and a binary image is extracted to extract a contour point sequence forming an outer periphery. A joint point is extracted for each group of contour points obtained as described above. First, obvious joint points are extracted. This can be determined as a point having a large curvature. This is a temporary junction and not optimal. Also, this alone does not find all the junctions. Conversely, those unnecessary as junctions are also included.

Therefore, it is necessary to correct the designation of the joining point. After that, a junction at the right angle portion is extracted. This is to smooth the connection at the intersection when two straight lines of the character intersect, as will be described later. The joining points of the straight lines are the starting point and the ending point, and add joining points that are thin lines and do not appear under the condition that the curvature is large. This is rarely needed for letters.

On the contrary, since there are unnecessary junction points, it is necessary to remove them. One is a junction in a straight line. When the joining point is in the middle of the straight line and the distance from the straight line is small, the straight line may be maintained even if this is removed. Since this is a junction point caused by noise, it is removed. The other is the junction of the arcs. What is supposed to be a single arc may appear as two arcs separated by two junctions due to the large number of joints. This also removes intermediate junctions and combines the arcs into a single arc.

When the joining point is determined, each section is approximated by a piecewise polynomial. The approximation of this piecewise polynomial is the same as that described above for the data approximation mechanism A, but in the previous one the approximation interval spanned the entire contour point sequence group. This time, instead, a piecewise polynomial approximation is performed for each junction.

First, the extraction of the temporary junction will be described. The curvature is large because the gradient changes at the junction. The junction determines the domain of the function when the function is approximated next. A straight line or a curve whose gradient changes smoothly between the joining points. The approximation function between the junctions can be expressed in a simple form. Therefore, if the approximate function between the coordinates of the joint point and the joint point is obtained, all the data for this character font has been obtained.

However, if the joining points are not properly selected and the joining points are too far apart, the number of data increases because the adjacent joining points cannot be represented by a simple approximation function. . On the other hand, if there are too many joints, the data relating to the coordinates of the joints increases, so that the data cannot be sufficiently compressed. Thus, the choice of junction is important. The method of extracting the joint position will be described with reference to the flowchart of FIG. Since the approximate curvature has already been obtained for all contour point sequences, this is used.

The curvature is read from the approximate curvature storage device E '. Is ^{_{{K (t k u)}}} . From these data, the group u
It is sequentially checked whether or not the curvature is larger than a certain value δ for all the points k = 0 to N−1.

[0111] ^{_{| K (t k u) |}} > δ (34)

The junction point is a point where the curvature is large to some extent when the gradient changes suddenly, and can be obtained by such a method. The value of δ can be appropriately determined depending on the purpose.

Further, since the contour point sequence forming a perfect circle has already been removed, a point that the curvature is large in a part of the arc (this cannot be a junction point) cannot be obtained by this calculation. Therefore, a point where the curvature exceeds δ is defined as a temporary joining point. Then the coordinate _{^{(x k u, y k u}} ) is stored in the junction position the storage device I a. Let the number of the temporary joining point be i. Thus, the i-th temporary junction can be written as d _i (x _i ^u , y _i ^u ). The number k in the outline point sequence is replaced with the junction point number i. Such comparison and extraction of the junction are performed for each point k. After doing this for the group u, we do the same for u + 1. Thus, the coordinates of all the temporary joining points in each group are obtained.

The joining point will be described intuitively. FIG. 15 shows the original characters of hiragana "a" and katakana "po". This is input to the image processing apparatus to extract a sequence of contour points, and to extract junction points, as shown in FIG. The places marked with “x” are the joining points. In order to extract this without error, several calculations are performed thereafter.

[I. Joining point position storage device] This is the number of the temporary joining point and the coordinates ｛d _i (x _i ^u , y
_i ^u )｝. It is more accurate to say a temporary junction. There are three types of joining points: a temporary joining point selected because of the large curvature, a joining point candidate and an optimum joining point to be described below. Don't confuse this.

[J. Optimal Joint Point Extraction Mechanism] What has been obtained so far is a temporary joint point determined only by the magnitude of the curvature. These may not be actual junctions. Since an image obtained by optically reading a character font has noise due to reflection and scattering of light from a lens or glass, disturbance light, and the like, the curvature of the junction between two straight lines and two curves may actually be small. Therefore, it may not be left as a joining point in the preceding process. Conversely, due to noise, the curvature may be large despite the midpoint between the straight line and the curve, and it may be seen as a joint.

Therefore, it is necessary to find an optimum junction. The optimal junction should be near the junction candidate determined by the method described above. As described above, the optimum joining point is a point unique to a character because it is an intersection or a bending point between straight lines. Because of this noise, it cannot be found accurately only by the magnitude of the curvature.

FIG. 17 shows a flowchart of the mechanism for extracting the optimum junction. Temporary junction d _i from the joining point position storage device I
^{_{(X i u, y i u}} ) read _{i = 0 ^I-1.} Here, u is the group number of the outline point sequence, i is the number of the temporary junction in this group, and I is the number of temporary junctions in this group. It is called a temporary junction because it is not the final junction. The remarkable feature of the present invention is also here, and it is important in the present invention to repeat the sculpture for the position of the joint.

Consider several junction candidates near the temporary junction. Let this be λ _o ⁱ , add coordinates and λ _o
Write ⁱ ( _xio , _yio ). i is the number of the temporary junction and should be put in parentheses and raised to the suffix.
It is omitted because it does not become a quarter angle. In the drawing, the suffix (i) is correctly written. The display of the group u is omitted. Of course, it is a junction candidate near the i-th temporary junction in the group u. The number of the joining point candidates is set to O. This is the same number for every temporary junction. FIG. 18 illustrates this.

The center x _i is a temporary junction selected by curvature, and α before and after this are junction candidates. Here, x _i is written as d _i (x _i ^u , y _i ^u )
Which means both the x coordinate and the y coordinate. d _i
However, here, it is simply written as x _i to clearly show that it is a position coordinate. The same applies to the notation of the next neighboring junction.

There are splice point candidates up to o = 0, 1,... O-1. This is determined by _{di +} α or di _- α. This means that a sequence of α contour points before and after the temporary joining point is set as a joining point candidate. O = 2
α + 1. One of these is the optimal junction. The magnitude of α is determined from the evaluation of the magnitude of the deviation between the temporary joining point and the optimal joining point. If this deviation is large, it is necessary to increase α. However, increasing this will increase the number of subsequent calculations. An appropriate number should be determined in consideration of both.

Next, the near junction ｛d _j (x _j ^u ,
y _j ^u )｝. Near junction a temporary junction within a circle of radius ρ around the temporary bonding points x _i, contour surrounded ones are connected by a continuous contour point sequence and by the contour point sequence containing the temporary junction It is in the sequence of points. For example, in the case of the character "ha", the outline point sequence inside the circle at the lower right is also a joint point near the outer temporary joint point.
The number assigned to the nearby junction is j. The temporary junctions x _i to be considered in the previous discussion have i as numbers and are distinguished by these numbers. Being within the radius ρ means that

{(X _i −x _j ) ² + (y _i −y _j ) ² } ^1/2 <ρ (35)

It can be represented by the following conditions. The reason why the condition of being connected by the contour point sequence is necessary is that
This is because the extraction of the optimum joint point is to smoothly connect the joint points sandwiching the intersection at the intersection of the lines. The relative relationship between the joining points that are not connected by the contour point sequence does not matter. In addition, the condition of connection (connection of black pixels) by the outline point sequence is x
Whether or not _j is in the same outline point sequence group as x _i can be easily checked.

[0125] near the junction is precisely ^{_x j} _(x j u, y
_It should be written as _j ^u ), but since it is tedious, it will be simply written as x _j hereinafter. This includes the y coordinate as well as the x coordinate

Let J be the number of nearby junctions. J can be 0 or 1 or more. J = 0 means that there is no nearby junction. J being greater than or equal to 1 means that there are several nearby junctions. The processing is different for the two cases. J ≧ 1 and J
<1 (that is, J = 0) will be described separately.

When J ≧ 1, two more cases are distinguished. The tracking of the contour point sequence is clockwise when there is an external contour point sequence, and counterclockwise when it is inside. Therefore, from the temporary bonding points x _i that are the subject of discussion, and when there is near the junction x _j above, there may be near the junction x _j before x _i. We have to distinguish between them.

[0128] near the junction x _j, which is before the temporary joining point x _i selected in curvature of input vicinity. This is shown in FIG.
Near junction x _j which is after the temporary bonding points x _i is that the output near. That from the temporary junction x _i, it is the vicinity of the output near the junction in the destination out of the vector emitted in the direction of scanning of the contour point sequence. Conversely, the temporary connection point into which the vector generated in the scanning direction from the nearby connection point is the input vicinity. The determination of the vicinity of the output and the vicinity of the input will be described later.

[CASE 1 (in the case of J ≧ 1 and near the input)] First, referring to FIG. 19, a near junction point near the input will be considered. This can be a number of ideas. here,
Consider the vicinity of four temporary junctions. Then, on the condition that the curve connecting these four points is the smoothest, the optimum one of the candidate λ ₀ ⁽ⁱ⁾ (x _i0 , y _i0 ) near the temporary connection point is determined.

In FIG. 19, the tentative junction selected first by curvature is x _i (near C). The neighboring junction is x _j (near B). For input vicinity is considered as the next temporary joining points x _{i + 1} of the provisional junction (near D), the previous temporary joining point x _j-1 of the temporary junction x _j a (near A) . This 4
Try to pass these points so that the curve passing through the points is the smoothest. A, D on both sides of these four temporary junctions
Is fixed, and only the middle B and C are moved to obtain the adaptation coefficient. Points B and C have 2α + 1 junction point candidates. Therefore, a piecewise polynomial approximation of (2α + 1) ² combinations is performed. Among them, the approximation connecting the four points most smoothly gives the highest matching coefficient.

How to express the condition of smoothness? There are a number of them, but here we will evaluate under the condition that the curve has the fewest inflection points. The successive approximation is increased, and the number of approximations is represented by t.

[0132] end point A of the curve, x _j-1 of any of the junction point candidate ^{_{λ l j-1 (x j}} -1l, y j-1l) is. Here, the suffix of the joining point candidate is l ', but since "'" cannot be reduced to 1/4 picture, it is written as l here. Actually l '
It is.

The intermediate point B is a candidate λ _l ^j (x _jl , y _jl ) of one of the neighboring junctions x _j . The number of the joining point candidate is represented by l. 1 becomes a parameter and the same calculation is repeated many times while changing l.

The intermediate point C is one of the candidate junction points λ _o ⁱ (x _io , y _io ) of the original temporary connection point x _i . The number of the joining point candidate is represented by o. The parameter o is changed and the same calculation is repeated many times.

[0135] Other end points D curves, one of the junction point candidates ^{_{x i + 1 λ o i +}} 1 (x io, y io) is. In this case, however, the suffix of the joining point candidate is o ', but it is simply written as o because it cannot be made into "'" 1/4 image. Actually, it is o 'as shown in FIG.

In the calculation order, the points A and D at both ends are fixed points (in the t-th approximation), and the candidate λ _l ^(j) (x _jl , y _jl ) Candidate λ for joining point C
_{For o} ⁽ⁱ⁾ (x _io , y _io ), the calculation is repeated by changing the parameters l and o one by one. In this calculation, the suitability as the junction is calculated as a probability function. The probability function has a coefficient r _ij (ol) based on the smoothness of the curve. This coefficient can be referred to as a matching coefficient. i and j are the signs of the temporary junction _xi and the neighboring junction _xj .

O and l are the numbers of the joining point candidates to which these temporary joining points belong. Since this coefficient is a value determined for each of the parameters o and l, such subscripts are required. This is 1 when the curve ABCD is sufficiently smooth and less than 1 when it is not smooth. Therefore, it can be a parameter that determines the suitability of the curve.

FIG. 20 shows a case where a neighboring junction exists (J ≧
This is a flowchart showing the method of determining the adaptation coefficient r _ij (ol) in 1). First, a parameter range is specified. i
There because I-1 0, such calculate the temporary joining points x _i obtained by the curvature is that repeated from 0 to I-1.

The fact that o is from 0 to 2α means that there are 2α + 1 joint point candidates at the target temporary joint point x _i , and all of them are calculated one by one. The fact that j ranges from 0 to J-1 means that if there are a plurality of neighboring junction points x _j, this calculation is repeated as much as possible. This is necessary because J> 1.

The fact that l is from 0 to 2α means that since there are 2α + 1 joint point candidates at the neighboring joint point x _j , these are all calculated one by one.
Such calculations are performed for the parameters i, o, j, and l, but are written out of order here, and do not constitute a larger loop than the first one. However, in the following description, these parameter changes are uniquely given.

The points A, B, C and D are approximated by a full-energy function in the same manner as the data approximation at first. That is, it is approximated by a piecewise polynomial. The order of the approximation function may be second order. In the above expression, m = 2
And

S _x (t) = Σ _{k = −2} ^{M + 2} C _k ^x ψ _k (t) (36)

S _y (t) = Σ _{k = −2} ^{M + 2} C _k ^x ψ _k (t) (37)

Ψ _k (t) = 3 (T / M) ⁻² Σ _{q = 0} ³ (−1) ^q ｛t− (k + q) (T / M)｝ ² ₊ / ｛q! (3-q)! ｝ (38)

K = −2, −1, 0, 1, 2,..., M + 2 (39)

Here, the parameter t is t representing a continuous amount. This is different from t which indicates the approximation stage described above. Since there are not enough characters, different things are expressed with the same t. At the time of the first data approximation, the range T was determined for all the contour point sequences, and one approximation was performed for all the contour point sequences. Therefore, the coordinate data of all the contour points must be referred to.

However, this is not the case here, and four points A, B,
What is necessary is to connect C and D. Only the coordinates of four points are needed, and the coordinates of many contour point sequences between the four points are no longer needed. Since it suffices to connect four points, AD is approximated by a piecewise polynomial. Section T corresponds to curve AD. The calculation shown in FIG. 10 is performed, but since the number of points is extremely small, this approximation is simple. The same is true for determining coefficients by the least squares method. An approximation curve ABCD passing through four points is created by such approximation.

The curvature at each contour point of the curve ABCD is calculated. Since there are approximation functions S _x (t) and S _y (t),

K (t_w ^u ) = ｛S_x '(T_w ^u ) S_y '' (T_w ^u ) -S_x '' (T_w ^u ) S _y '(T_w ^u )｝ / ｛S_x '(T_w ^u )^Two + S_y '(T_w ^u )^Two ｝^3/2 (40) Here, w = A, B, C, and D.

This is also simple, since it is sufficient to calculate only four points instead of calculating the curvature over the entire curve AD.
Determine the number n _c of the inflection point by the number of inversions of curvature. The number of inflection points is naturally three or less. Figure 21 is a diagram showing an example of a number n _c of schematic type and inflection point of the curve. The inflection point is represented by a cross. (A) is a case where the number of inflection points is three. Meandering is severe. (B) is a case where the number of inflection points is two.
(C) is a case where the number of inflection points is one. (D) is a case where the number of inflection points is zero. This connects the four points most smoothly. It is desirable to employ this. In this case, r _ij (o
Determine l) to be 1. For example, by using a number of inflection points n _c,

R _ij (ol) = min {1 / c ₂ (nc− _{c 1} ), 1} (41) (c ₁ and c ₂ are constants)

The decision is made as follows. In this example, when the number of inflection points is 3, r _ij (ol) = 1/3. This is _{one where} c ₁ = −1 and c ₂ = 3/4. In this case, 4/9 when n _c = 2, 2/3 when n _c = 1, and n _c = 0.
And becomes 1. Of course, these constants may be determined as appropriate.
1 and to min operations, but to prevent this because too large when a small number of inflection points, r _ij (o
There is no requirement that the upper limit of l) be one.
It is also possible to simply set r _ij (ol) = 1 / c ₂ (n _c −c ₁ ).

The above calculation is repeated several times. The number of approximation calculations is represented by t. This is a calculation for probability. The approximate calculation will be described later. Here, only the determination of the adaptation coefficient r _ij (ol) has been described.

[CASE 2 (when J <1: there is no neighboring junction)] FIG. 22 is a flowchart showing the processing when J <1 or when there is no neighboring junction. FIG. 23 shows an example of the position of the joining point in this case. This provisional junction x _i-1 of the previous temporary joining point x _i, temporary bonding points after x _{i + 1} and 3
The connection of points matters. In the flowchart of FIG. 22, the range of the parameter is first defined.

I is 0 to I-1, which is the number of the temporary junction. That is, the calculation is performed for all the temporary joining points. o is a joint point candidate λ of the temporary joint point x _i
o ⁽ⁱ⁾ is the number of ( _xio , _yio ). 1 is the number of the candidate λ _l ^(j) (x _jl , y _jl ) of the connection point candidate of the temporary connection point x _i-1 before x _i . Calculate for all junction candidates. j is i
−1 to i−1, that is, only j = i−1.

Let A, B, and C be the candidate junctions of the respective temporary junctions x _i−1 , x _i , and x _{i + 1} . Point A is λ _l ^(i-1) (x
_i-1l , _yi-1l ), where l is a parameter. Point B is λ _o ⁽ⁱ⁾
In ( _xio , _yio ), the parameter is o. Point C is x _{i + 1}
In the junction point candidate lambda _h of _{^{(i + 1) (x i}} + 1h, y i + 1h), max h
(P _{i + 1h} ^t-1 ). max _h indicates the maximum among the parameters h.

These three points are interpolated by a fluency function. This is performed by a method as shown in FIG. 10, but there are only three points, which is extremely simple. However, this also increases the approximation, and the number of approximations is represented by t. And error to approximate until the ε _max by the least squares method. The number of dimensions of the approximation at this time is M. r _ij (ol) is min ｛1 /
(C ₃ M + c ₄ ε), determined by 1 °. ε is the final error and M is the final dimension.

That is, a point which can be approximated with as few dimensions as possible and with a small error is obtained. Such a point can provide the smoothest curve among the joining point candidates of the temporary joining points to which each point belongs. t is the number of approximations, and is increased from 0. As in the case of J ≧ 1 described above, t is set to 0 to 4, and approximation is stopped four times.

[0159] [(For output near at J ≧ 1) CASE 3] that shown in FIG. 19 is when near the junction x _j is the input vicinity for temporary joining points x _i in J ≧ 1. The same calculation is performed when J ≧ 1 and the neighboring junction point x _j is near the output, but in this case, the way of obtaining the four points is slightly different.

FIG. 24 shows the vicinity junction point x _j near the output.
The following shows how to score 4 points. Near junction x _j is in among the radius ρ centered at x _i. Moreover, this is ahead of the original temporary junction point x _{i in} the scanning direction. The four points are a temporary junction point x _i-1 before the target temporary junction point x _i and a temporary junction point x _{j + 1} next to the neighboring junction point x _j . Four points are taken out of 2α joining point candidates near these.

A is a junction point candidate λ of x _{j + 1
l} ^{(j + 1)} (x _{j + 1l} , y _{j + 1l} ). However, here, l has "'", but since it cannot be made into a 1/4 square, "'" is omitted. This is determined as the maximum value given in the previous probability calculation, and is a fixed value.

B is a candidate λ of the junction of the neighboring junction x _j
l ^(j) (x _jl , y _jl ). C is one of the junction point candidate lambda _o of the temporary junction x _i as an object _{^{(i) (x io, y}} io).

D is a candidate for a joining point of x _i-1 λ _o ^i-1 (x
_i-1o , _yi-1o ). This also gives the maximum value in the previous probability calculation and is a fixed value. Although it is actually o 'as shown in the figure,' is omitted here because 'does not become a quarter-angle. As described above, four points are determined. The calculation after this is the same as in the case 1 described above.

[Method of Determining Near Output and Near Input] The temporary joining point is a contour point having a large curvature, and is typically an intersection where two lines intersect at an angle close to a right angle.
In order to accurately determine an intersection, two outlines passing through the intersection must be accurately determined, and the intersection must be determined. 1
The outline of the book passes through the intersection and one nearby junction, and another
The book outline passes through the intersection and other nearby junctions.

Since the junction has two neighboring junctions in this way, the temporary junction d _i (x _i ,
near junction d _j (x _j of y _i), as y _j), it must be distinguished with respect to the output near the input vicinity. The smoothest line passing through the junction and the vicinity of the input and the smoothest line passing through the junction and the vicinity of the output are obtained, and the correct intersection is reproduced from the intersection of these lines.

[0166] temporary bonding point _{d i (x i, y i} ) through the two points and the previous temporary joining point _{d i-1 (x i-} 1, y i-1), the direction of scanning of the contour point sequence When the vector (d _i−1 → d _i ) along the line goes to the neighboring junction d _j (x _j , y _j ), the neighboring junction d _j (x
_j , y _j ) are called output neighborhoods. Conversely, the nearby junction d
_j (x _j , y _j ) and the temporary joint point d _j-1 (x _j-1 ,
through the two points y _j-1), when the vector along the direction of scanning of the contour point sequence _{(d j-1 → d j} ) is directed to the temporary junction _{d i (x i, y i} ), inputs the It is called the neighborhood. FIG. 25 is a flowchart for determining an input / output proximity junction. First, all the joining point candidates λ _o ⁽ⁱ⁾ (x _io , y _io ) are inputted.

[0167] i temporary joining point serving as a calculation target d _i (x _i,
y _i ), which are I (0 to I−1) for one outline point sequence group u. We start with i = 0 for this. j is the number of the neighboring junction, but it is not known from the beginning whether or not it is nearby. At first, all the temporary joining points _dj ( _xj , _yj ) are taken. “o” is the number of the junction candidate included in 2α pieces near the temporary junction. Although o is overlined in the figure, it is omitted in the specification because it cannot be overlined. Only the i of the temporary junction point d _i (x _i , y _i ) is fixed, and a nearby junction point is determined.

[0168] ^{_{d j (x j u, y}} j u) is the coordinates of the j-th temporary joint point, I wrote simply d _j for simplicity. This is λ _o ⁽ⁱ⁾ (x _io , y _io ) (written as λ _o ⁽ⁱ⁾ for simplicity)
To determine if it is within a radius ρ centered at. This is the condition shown in (35).

{(X _io −x _j ) ² + (y _io −y _j ) ² } ^1/2 <ρ (42)

Is obtained. (35) the coordinates (x _i, y _i) of the temporary bonding points are used as the uses a coordinate bonding point candidates d _i here. If d _j is within radius ρ, this may be a near junction. Then d
_It is checked whether _j and λ _o ⁽ⁱ⁾ are in the same outline point sequence. If they are in different outline point sequences, they are not neighboring junction points.

If they are in the same outline point sequence, d _j is λ _o
⁽ⁱ⁾ is near the junction of the temporary junction x _i belongs. In the temporary junction d _i of interest, coordinates of a point before the predetermined number beta that can be expressed by (not necessarily junction candidates) d _i-beta. The vector (d _i−β → d _i ) has a direction along the scanning direction at the temporary joining point. Whereas coordinates of the point after only a certain number beta than this near the junction d _j can be written as d _{j + beta.} The vector (d _j → d _{j + β} ) has a direction along the scanning direction immediately after the neighboring junction.

[0172] temporary bonding point d _i toward the vicinity of the junction point d _j from the vector (d _i → d _j) is the contour point sequence along the direction of scanning toward the temporary joining point d _i vector (d _i-beta → d _i ) is substantially parallel to the vector (d _j → d _{j + β} ) emerging from the neighboring junction along the scanning direction of the outline point sequence, the neighboring junction _dj is provisional. in the vicinity the output of junction d _i.
That is,

(D _i−β → d _i ) // (d _i → d _j ) // (d _j → d _{j + β} ) (43)

That is, the above condition is almost satisfied, and the expression of the inner product and the outer product of the vectors is as follows.

| (D _i−β → d _i ) × (d _i → d _j ) | <ε | (d _i → d _j ) × (d _j → d _{j + β} ) | <ε (44)

(D _i−β → d _i ) · (d _i → d _j )> 0 (d _i → d _j ) · (d _j → d _{j + β} )> 0 (45)

That is, all the conditions hold. However, ε is an appropriate small value. That is, the vector (d
_{When i-β} → d _i ), (d _i → d _j ), and (d _j → d _{j + β} ) all face in substantially the same direction, four points d _i−β , d _i ,
d _j and d _{j + β} are almost aligned. In this case, _dj is near the output. So this is _dj ^output
Register as (i).

[0178] coordinates of a point earlier by a predetermined number beta than this in other near the junction d _j can be written as d _j-beta. The vector (d _j−β → d _j ) has a direction along the scanning direction immediately before the neighboring junction. Coordinate of a point after only a certain number beta than this in the temporary junction d _i can be written as d _{i + beta.} The vector (d _i → d _{i + β} ) has a direction along the scanning direction immediately after the temporary joining point. A vector (d _j → d _i ) from the neighboring junction d _j to the temporary junction d _i is a vector (d _i → d _{i + β} ) emerging from the temporary junction d _i along the scanning direction of the outline point sequence. When a substantially forward parallel, toward the vicinity of the junction point d _j along the direction of scanning of the contour point sequence vectors (d
_j−β → d _j ), the near junction d _j is near the input of the temporary junction d _i . That is,

(D _j−β → d _j ) // (d _j → d _i ) // (d _i → d _{i + β} ) (46)

That is, the condition is almost satisfied, and the expression of the inner product and the outer product of the vectors is as follows.

| (D _j−β → d _j ) × (d _j → d _i ) | <ε | (d _j → d _i ) × (d _i → d _{i + β} ) | <ε (47)

(D _{j −β} → d _j ) · (d _j → d _i )> 0 (d _j → d _i ) · (d _i → d _{i + β} )> 0 (48)

That is, all the conditions hold. However, ε is an appropriate small value. That is, the vector (d
_{When j-β} → d _j ), (d _j → d _i ), and (d _i → d _{i + β} ) are almost in the same direction, four points d _j−β , d _j , d _i , d
_{i + β} is almost aligned. In this case, _dj is near the input. Therefore, this is registered as d _j ^input (i).

[Calculation of Probability] In order to obtain the optimum junction, the following calculation is performed for the junction candidates to select the optimum one. FIG. 26 is a flowchart showing this calculation.
What to enter

Λ _o ⁱ (x _io , y _io ), _dj ^input (i), _dj ^output (i) (49)

Is as follows. ^{_{λ o (i) (x io}} , y io) is close to the junction point candidates temporary joining points x _i selected by the curvature. o is the number assigned to the junction candidate. i means that it relates to x _i . d _j ^input (i) is the temporary junction x
_This is the position coordinates of the input neighborhood junction among the neighborhood junctions of _i . d _j ^output (i) among the neighboring junction of x _i, the position coordinates of the output near the junction.

[0187] This is input first. The order of the probability calculation is denoted by t. This is not stopped when the error becomes small to some extent by the least square method, but the number of times is determined from the beginning. For example, four times (t = 0 to
4). Of course, five or more times may be used depending on the purpose.

A random variable P _i ^t (o) is defined. This is the t-th probability of an inner o of 2α + 1 of the (x _i including itself) junction point candidate in the vicinity of the temporary joining point x _i. Parentheses should be added because it is the t-th time, not the t-th power, but since the parentheses cannot be included in the suffix, it is simply written as t. What is the probability is the probability as the optimal junction. The highest one of the 2α + 1 junction points is selected. Every time the number of times t of the probability calculation is increased, the probability variable more suitable as a junction increases. Determine the random variables in that way. Of course, many definitions are possible. Here, it is determined as follows.

Consider the complementary random variable Q _i ^t (o). This also gives the t-th probability of the joint point candidate o. This is the sum of the contribution q _i ^input (o) from the input neighborhood and the contribution q _i ^output (o) from the output neighborhood. This also includes the number of times t, but is omitted here.

Q _i ^t (o) = q _i ^input (o) + q _i ^output (o) (50)

Q _i ^input (o) and q _i ^output (o) are defined as follows.

Q _i ^input (o) = max ｛r _ij (ol) × P _j ^{t −1} (l)｝ (51) (junction point candidate of λ _l ^j ∈ ｛d _j ^input (i)｝) (52) )

[0193] However the calculation is the junction of max candidate λ _i ^j is d _j
^The maximum value is obtained under the condition that the ^input (i) belongs to the junction candidate. Here, l is a changing parameter. The fit coefficient r _ij (ol) has been given earlier. Similarly,

Q _i ^output (o) = max ｛r _ij (ol) × P _j ^{t -1} (l)｝ (53) (junction point candidate λ _l ^j ∈ ｛d _j ^output (i)｝) (54) )

Max indicates that the junction candidate λ _l ^j is ^{equal to} d _j ^output
(I) takes the maximum value under the condition that it belongs to the junction candidate. The t + 1 random variable is t
It is defined as follows using a random variable of the second time, a complementary random variable, and the like.

[0196] For ^{_{P i t + 1 (o)}} = P i t (o) Q i t + 1 (o) / {ΣP i t (o) Q i t + 1 (o)} (Σ is λ _o ⁱ Do) (55)

Such calculation is performed from t = 0 to 4. However, this cannot be calculated unless the initial (t = 0) random variable is known. The initial probability P _i ⁽⁰⁾ (o) may be given in any way, but here, a larger value is given closer to x _i . This is because the optimal joint point is considered to be near the temporary joint point x _i , and the convergence of the random variable is considered to be faster if the initial probability of x _i is increased.

FIG. 28 illustrates the setting of the initial value. The joint point candidates λ _o ⁱ have 0 to 2α + 1 o. o = α is x
_i own. The initial value P _i ′ (o) takes the maximum value K when o = α. o = α-1, α + 1 is (K−2).
Hereinafter, it is assumed that the distance decreases by 2 as the distance from α increases. At o = 0 and 2α, the initial value is 1. Initial probability P
_i ⁽⁰⁾ (o) is the initial value,

P _i ⁰ (o) = P _i ′ (o) / ΣP _i ′ (o) (56)

Is as follows. The integration of Σ is performed for o. Given the initial probabilities in this way, the fit coefficient r _ij (ko)
And q _i ^input (o) at t = 1 and q
_i ^output (o) can be calculated. The complementary random variable Q _i ^t (o) is calculated as the sum of the above, and the (t + 1) -th random variable P _i ^t (o) can be calculated. This is repeated until t = 4. The junction candidate having the highest random variable at t = 4 is the optimum junction. The output here is _Pi ⁴
(O) _{i = 0} ^I-1 _{o = 0} ^O-1 . This is shown in FIG.

In this manner, the optimum joining point can be obtained from the joining point candidates near the temporary joining point obtained from the curvature. It is one of the remarkable features of the present invention that, although a temporary joint point is obtained first, the range is further extended to a contour point sequence near this to be used as a joint point candidate and an optimum joint point is obtained therefrom. This is based on the inventor's discovery that a point having a maximum curvature is not always optimal as a joining point.

[Other Definitions of Fitting Coefficient] The condition of the optimum joining point was that in the method described above, the inflection point of the curve connecting the four points was the least. In other words, the smoothest connection is made. This besides counting the number of inflection points,
It is also possible to directly target the curvature of the curve. FIG.
Numeral 7 is a flowchart showing how to find a matching coefficient of a joint point candidate under such other conditions.

The first condition J> 1 is a condition that a nearby junction exists. In this case, considering the input neighborhood and output neighborhood,
Consider a curve passing through four points A, B, C, and D (FIGS. 19 and 24). At this time, a curvature is obtained instead of an inflection point. K
_{The input} is the maximum curvature of a curve connecting four points near the input. A curve where this becomes smaller is desirable. K
_output is the maximum curvature of the curve connecting the four points near the output. This is also better if it is smaller. Therefore, the sum of the two is taken to find the point that gives the minimum. Therefore, the adaptation coefficient

R _ij (ol) = min {γ (K _input + K _output ) ⁻¹ , 1} (57)

Is defined as γ is a constant. This is determined so that the sum of the curvatures becomes approximately γ at the optimal time.

FIG. 29 shows that the calculation of the random variable is repeated and t =
4 to a random variable P _i ⁴ obtained in this stop repeatedly when it becomes this calculated number o junctions candidates (o) is maximized, the junction point candidate tentative junction x _i of the belongs Is the optimum junction point λ _o ⁱ . This is input to the optimum junction storage device K. Such an operation is performed for all the temporary joining points of the outline point sequence group, and joining point candidates of each category are determined.

[Optimal junction storage device] This is an apparatus for storing all the optimal junctions obtained by the above operation. As shown at the bottom of FIG. 29, the optimum joining point is stored as (x _i ^u , y _i ^u ). u is the number of the contour point sequence. i is the number assigned to the junction in group u. In the above, the temporary joining point is given the number x _i (which also represents the y coordinate), and the number i is the same, but this is not a problem. This is because one optimal joining point corresponds to one temporary joining point, and the optimal joining point is the same as or very close to the temporary joining point obtained earlier.

The operations up to this point have been described in order, but in order to make it easy to understand the course, the operations up to this point will be briefly reviewed using the character “ぱ” as an example. In FIG. 30, there is a black character "@". This is read by an image scanner to form an image. Image processing is performed to extract a contour point sequence. This is represented by white letters. The circle on the right shoulder is extracted by the perfect circle extraction and stored by the perfect circle storage mechanism.

The rest is "ha". There are three independent groups of contour points. Piecewise polynomial approximation is performed over these entire lengths. Then, the curvature is calculated to determine a temporary joining point. This is written in the third row. Temporary junctions appear at seams of line segments. In the fourth row, the temporary joining points are indicated by crosses. Since it is selected by curvature, the lower right part of "ha" may not appear as a temporary junction. In this case, it is added so that this point becomes a joining point. Next, joint point candidates are obtained. Further, near junctions are extracted at intersections below “ha”. The above description has made it clear so far.

[L. Junction point removal mechanism] Here, unnecessary junction points are removed from the junction points extracted so far.
FIG. 31 is a flowchart showing this. The final junction is read from the optimal junction storage. ｛Λ _o ⁱ ｝ ＝
{(X _i ^u , y _i ^u )} _{i = 0} ^I−1 . u is the group number, i
Is the number of the junction in the group. Thereafter, redundant junction removal in the linear approximation is performed.

Further, redundant junction points in the arc approximation are removed. The final joining point is defined by coordinates (x _i ′ ^u
, Y _i ′ ^u ) and the number i ′.

The joint points determined so far are obtained by approximating the contour with a piecewise polynomial, determining the curvature, determining the temporary joint points, and determining the final joint points from the candidate joint points. Therefore, there should be almost no unnecessary junctions, but there is still a possibility that there are unnecessary junctions due to the influence of image noise. It is the junction of a straight line and the junction of an arc.

[Removal of Joint Point of Straight Line] The example of the outline point sequence in FIG. 32 shows a case where there is a joint point in a line segment. These coordinates are represented by (X _i4 ^B , Y _i4 ^B ). The joint points are sequentially evaluated, and when there is a section in which two or more straight line joint points are continuous, a sequence of three consecutive points is taken out of these.
Let i ₄ = ns, ns + 1, ns + 2. (X _ns on both sides
^B , Y _ns ^B ) and (X _{ns + 2} ^B , Y _{ns + 2} ^B ) are connected by a straight line. Let L _{ns + 1} be the length of a perpendicular line drawn from the intermediate junction (X _{ns + 1} ^B , Y _{ns + 1} ^B ) to this straight line. When this is smaller than the constant K ₇ that defines pre

L _{ns + 1} <K ₇ (58)

This junction is removed. FIG. 33 shows a state where such joints are removed and the joints on both sides are connected. Conversely, when the perpendicular leg L _{ns + 1} is greater than the constant K ₇

L _{ns + 1} ≧ K ₇ (59)

This junction is maintained. Such an evaluation is performed for all joint points.

[Removal of Arc Joints] A plurality of joints may be continuous among the arc joints extracted up to the previous stage. In this case, if the data quality is maintained even if the intermediate junction is removed, the junction is removed. The possibility of removal is determined as follows.
As shown in FIG. 34, the joining points of the arcs are represented by (X _i4 ^B ,
Y _i4 ^B ). i ₄ is a sequential number.

As shown in FIG. 34, three junctions (X _ns ^B , Y
^{_{ns B), (X ns +}} 1 B, Y ns + 1 B), (X ns + 2 B, Y ns + 2
^Suppose that ^B ) exists continuously. At this time (X _ns ^B , Y _ns
^The arc (me) starting from ^B ) and (X _{ns + 1} ^B , Y _{ns + 1} ^B )
Attention is focused on an arc (mi) starting from. As shown in FIG. 35, let the radii of both arcs be r _ns and r _{ns + 1} . The center coordinates are (x _ns , y _ns ) and (x _{ns + 1} , y _{ns + 1} ), respectively.
An arc is considered a single arc when the following conditions are met:

| R _{ns + 1} −r _ns | <K ₈ (60)

｛(X _{ns + 1} −x _ns ) ² + (y _{ns + 1} −y _ns ) ² ｝ ^1/2 <K ₉ (61)

That is, if the center coordinates are substantially the same and the radii are substantially the same, the two arcs M and M are regarded as a part of the same arc. In this case, the intermediate junction (X _{ns + 1} ^B , Y
_{ns + 1} ^B ) are removed as unnecessary. Otherwise, this junction is maintained.

The above-described judgment, removal, and maintenance operations are sequentially performed on all arc junctions. The threshold values of the radius difference and the center difference should be appropriately determined. For example, K ₈ =
It is convenient to set 1, K ₉ = 2.

With the above operation, in the straight line and the circular arc,
Unnecessary joints are eliminated. This is effective in compressing data. In addition, since it is necessary to correct what should be a straight line or a circular arc into a desired shape, it has a positive significance of improving the quality of data. The junction selected in this way is referred to as a final junction.

[M. Final Junction Storage] The final junction obtained by removing unnecessary junctions is stored in the final junction storage. This is as shown in the last stage of FIG. 31, the coordinates _{^{(x i u, y i u}} ) is a i _{= 0} ^I-1. However, in the drawings, 'is added to distinguish it from the optimum junction. 'Is 1/4
'Is omitted in the specification because it cannot be cornered. Actually '
It is with.

[N. Data approximation mechanism B] This is a mechanism for approximating data from data such as a contour point sequence, a final joint point, and a perfect circle obtained so far. It is a central part of the present invention. The input from each storage device is as shown in FIG.

[0227] contour point string storage .... contour point sequence ^{_{{(x k u, y k}} u)} k = 0 N (u) -1 u = 0 U-1 final junction memory ... Last Junction point (x _i ^u , y _i ^u ) _{i = 0} ^I-1 perfect circle storage device ... circle Circle (u)

Is as follows. The suffix u of the outline point sequence is the number of the outline point sequence group. k is a contour point sequence number in the contour point sequence group u. N (u) (represented by N u) is the number of contour point sequences in the group u. i is the final junction in group u. Although it is simply written as i, it is actually i 'as shown in FIG. 'Cannot be a quarter-angle, so here
Is omitted. Although the final joint point is obtained, a straight line, a circular arc, and a free curve approximation are made between two adjacent joint points (between the joint points). Using the parameter t in the approximation, convert the x component to s
_{With x} (t), the y component is represented by _sy (t).

First, the entire contour point sequence is set to the parameter t.
This is the same method as expressed in. But this time the area
Because it is between the confluence points, the range of t and t and s_x 
(T), s _x The response of (t) is different from the previous one
You. The section starting from a certain junction is a straight section
Or a section of an arc or a section of a free curve.
Is determined when the curvature is calculated at each point.
I'm sorry.

When this is recorded, it can be distinguished from the beginning whether it is a straight line, an arc or a free curve. That is, if the curvatures at all points in the section are 0, this is a straight line. If the curvature in that section is a constant value, this is an arc. If the curvature further changes, this is a free curve. If the sections can be distinguished in this way, it is easy to determine the parameters for the approximate calculation.

However, on the contrary, even if the result of the curvature calculation is not stored, it is possible to check whether a straight line, a circular arc, or a free curve is present at this stage. The approximation may be made after the distinction.
The present invention can be applied to both cases. First, the former case will be described.

[Approximation of Straight Line Section] The approximation of the section starting from the joining point of the straight lines will be described. It is determined to be a straight line in the extraction stage of the joint point. At this time, the approximate curve s _x (t) in the x direction becomes a linear function connecting the start point x ₁ and the end point x _n3 . The approximate curve s _y (t) in the y direction is a linear function connecting the start point y ₁ and the end point y _n3 . In this case, both x and y are linear functions with respect to the parameters.

The proportional constant between the parameter t and s _x (t), s _y (t) becomes a parameter. However, this proportionality constant does not need to be stored. Start point (x ₁ , y ₁ ) if it is a straight section
If the end point ( _xn3 , _yn3 ) is known, a straight line may be drawn between them. The end point (x _n3 , y _n3 ) is given as the start point of the next section, and need not be stored here.

[Approximation of Arc Section] The approximation of the section starting from the junction of the arcs will be described. This section is determined to be a circular arc at the point of joint point extraction. The approximate curves s _x (t) and s _y (t) representing the arc are expressed by the following linear combination of trigonometric functions. If the observation interval is t 区間 [0, T],
s _x (t) and s _y (t) are

S_x (T) = A_xcos (2πt / (T / n_arc )) + B_x sin (2πT / (T / n _arc )) + C_x (62)

S_y (T) = A_ycos (2πt / (T / n_arc )) + B_y sin (2πT / (T / n _arc )) + C_y (63)

Is represented by n _arc is the ratio of the arc to the total circle. That is, it is a value obtained by dividing the central angle of the arc by 360 degrees. For example, in the case of a _quadrant , n _arc is 1/4
It is. Therefore, 2πn _arc is the central angle of this arc. The variable 2πt / (T / n _arc ) is the central angle from the starting point of the arc to the point corresponding to the parameter t. (C _x , C
_y ) is the coordinates of the center of the arc. At this time,

A _x ² + B _x ² = A _y ² + B _y ² (64)

[0239] _{B y / A y = B x} / A x (65)

If the above holds, the approximation function becomes an arc. In this case, parameter defines an arc - data each coefficient A _x of the function, B _x, is _{C x, A y, B y} , C y, n arc. If it is known from the beginning that this section is a circular arc, such parameters can be uniquely determined from the coordinates of the start and end points, the curvature and the coordinates of one point in the middle.

[Approximation of Free Curve] Even at the junction of straight lines,
A section starting from a junction that is not a junction of arcs is approximated by a free curve. Although represented by the parameter t, the outline point sequence is (x _i3
^u , y _i3 ^u ), and corresponding to t,
(T _i3 ^u , x _i3 ^u ) and (t _i3 ^u , y _i3 ^u ) are used as parameters. Until now, the suffix of the contour point sequence was k. However, since k is used as the section number of the section, i3 is used as the contour point sequence number instead of k. Then, the total number of contour point sequences is set to n3.

Then, s _x (t) and s _y (t) are developed using the second-order fluency function ψ _k as the base. The fluency function is as shown in FIG. This is a function that has values only in three subdivisions. The interval is [0,
T], the quadratic fluency function ψ _k is an M-dimensional functional system

{ _K (t) = 3 (T / M) ⁻² _{} q = 0} ³ (−1) ^q (t−ξ _{k + q} ) ² ₊ / {(q! (3-q)!)} (66) (k = −2, −1, 0, 1, 2,..., M + 2)

Is as follows. Using this as the base, s _x (t _i3 ), s _y
(T _i3 ) is calculated using the coefficients c _k ^x and c _k ^y .

S _x (t _i3 ) = Σ _{k = −2} ^{M + 2} c _k ^x ψ _k (t _i3 ) (67)

S _y (t _i3 ) = Σ _{k = −2} ^{M + 2} c _k ^y ψ _k (t _i3 ) (68)

Are expressed as follows. here,

When t> ξ _{k + q} (t−ξ _{k + q} ) ² ₊ = (t−ξ _{k + q} ) ² (69)

When t ≦ ξ _{k + q} (t−ξ _{k + q} ) ² ₊ = 0 (70)

Is defined. ξ _{k + q} is _defined as
It is a subdivision when divided equally.

Ξ _{k + q} = (k + q) T / M (71)

The coefficients c _k ^x and c _k ^y are calculated as the values (x _i3
^u , y _i3 ^u ) and the values of s _x (t _i3 ) and s _y (t _i3 ) are determined to be similar. Determine the value of the coefficient by the least squares method. 2
The squared error Q is

Q = Σ _{i3 = 1} ⁿ³ | x _i3 ^u −s _x (t _i3 ) | ² + Σ _{i3 = 1} ⁿ³ | y _i3 ^u −s _y (t _i3 ) | ² (72)

Is defined by To minimize this,

Σ _{k = −2} ^{M + 2} _ck ^x ｛Σ _{i3 = 1} ⁿ³ ψ _k (t _i3 ) ψ _w3 (t _i3 )｝ = Σ _{i3 = 1} ⁿ³ x _i3 ψ _w3 (t _i3 ) (73)

[0256] ^{_{Σ k = -2 M + 2 c}} k y {Σ i3 = 1 n3 ψ k (t i3) ψ w3 (t i3)} = Σ i3 = 1 n3 y i3 ψ w3 (t i3) (74) (M = −2, −1, 0, 1,..., M + 2) (75)

Is determined by By solving this, the coefficients c _k ^x and c _k ^y can be obtained. In order to evaluate whether this coefficient is appropriate, the maximum value ε of the error at each point is determined as follows.

Ε = max _{i3 = 0} ⁿ³ ｛(x _i3 ^u− s _x (t _i3 )) ² + (y _i3 ^u− s _y (t _i3 )) ² ｝ ^1/2 (76)

However, in the max operation, the range of i3 is 0
To n3-1. This means finding the maximum in this range. When ε becomes smaller than a certain number, it is determined that the approximation has been completed. For example, it is determined whether ε <0.9. If ε is larger than a certain number, the same calculation is performed by increasing the number of dimensions M by one. As the number of dimensions increases, the number of sections increases, and the accuracy of approximation improves. When calculating the same error, sometime ε
<0.9. At this time, the approximation calculation is completed.

[O. Compressed data output mechanism] The outline of a character font is separated into straight lines (line segments), perfect circles, arcs, and free curves by the above procedure. These have a starting point and an ending point, and have parameters such as inclination, center, and radius. The data to be stored differs depending on the type.

In the case of straight line data, a flag indicating a straight line and the coordinates of the start point of the straight line are stored as data. Since the end point coordinates are given as the start point of the next section, there is no need to store them here. Although the slope of the straight line is a parameter that defines the straight line, a straight line can be formed by connecting the coordinates of the start point and the coordinates of the next junction, so that the slope is unnecessary. This is not stored either.

In the case of the perfect circle data, the data can be obtained directly from the perfect circle storage device G. This has already been selected by the first data approximation mechanism A. In the case of a perfect circle, a flag indicating the perfect circle, the center coordinates of the circle, and the radius of the circle are stored as data.

As the arc data, a flag indicating an arc, the coordinates of the starting point of the arc, the arc division length (arc length / perimeter),
Stores the number of contour points and function coefficients. As the data of the free curve, the number of dimensions of the function, the number of contour points, the midpoint of the variation of the contour point sequence, and the coefficient of the function are stored.

[P. Compressed data storage device] Stores data such as straight lines, perfect circles, circular arcs, and free curves output from the compressed data output mechanism. This is output at an appropriate time after being stored. Up to this point, the data is compressed and generated and stored. Hereinafter, an apparatus for reproducing characters from the stored data will be described. Table 1 shows the data structure stored in the compressed data storage device P.

[0265]

[Table 1]

The outline reproduction mechanism R, character reproduction mechanism S, and reproduction data output mechanism T described below constitute a reproduction data generation device for reproducing a character font to an arbitrary size.

[R. Contour Reproducing Mechanism] This is a mechanism for reproducing a contour to be a skeleton of a character font from stored compressed data. The contour may be a straight line, a perfect circle, an arc, or a free curve.

[Reproduction of Straight Line] Reproduction of a straight line is performed by connecting a straight line from the coordinates of the starting point to the coordinates of the joining point in the next section. No data regarding the inclination of the straight line is required. [Reproduction of Perfect Circle] Reproduction of a perfect circle is performed by drawing a circle having a given radius around the center coordinates from data of the coordinates and the radius of the center. [Reproduction of circular arc] Reproduction of circular arc is performed by substituting each stored data (A _x , B _x ,...) Into the following equation.

S _x (t) = A _x cos ｛2πt / (T / n _arc )｝ + B _x sin ｛2πt / (T / n _arc )｝ + C _x (77)

S _y (t) = A _y cos ｛2πt / (T / n _arc )｝ + B _y sin ｛2πt / (T / n _arc )｝ + C _y (78)

The x and y coordinates are obtained from S _x (t) and S _y (t) by varying the parameter t in the interval [0 to T].

[Reproduction of Free Curve] The value of the basis ψ _k of the approximation function at each sample point t _i is such that the sample point t _i is in the interval [(L + 2) (T / M, L (L + 3) (T /
M)] when in (1 ≦ L ≦ M), p = L + 3-t i ×
Using M / T,

Ψ _k (t _i ) = 0.5 p ² k = L (79) ψ _k (t _i ) = p (1−p) +0.5 k = L + 1 (80) ψ _k (t _i ) = 0 0.5 (p−1) ² k = L + 2 (81) ψ _k (t _i ) = 0 k ≦ L−1, L + 3 ≦ k (82) Here, L is a natural number of dimensions M or less. It should be written as M 'because they have the same property, but since' does not become a quarter angle, it is represented by L.

Using such a base ψ _k , the approximate function value S (t _i ) at each sample point is

[0275] _{S (t i) = Σ k} = L L + 2 C k ψ k (t i) (83)

Is determined by

[S. Character reproducing mechanism] Since the outline is obtained, a portion surrounded by the outline is set as a black pixel, and a black and white binary image is reproduced in a character shape. Or, conversely, the portion surrounded by the outline can be white pixels, and the rest can be black pixels. In addition, the part surrounded by the outline is a certain color,
Other parts can be of other colors. In short, it suffices that the inside and outside of the contour can be distinguished.

[T. Reproduction data output mechanism] In order to reproduce an image from the coefficient of the function, for example, the size of the reproduced image is set to 1
Use a layout editor that can specify from mm square to A3 size large. The reproduced image is printed by using a laser printer having an accuracy of 300 DPI or a laser printer having an accuracy of 600 DPI. Further, it can be output by a 3000 DPI electroplanter (printing device), a 400 DPI postscript compatible printer, a laser cutter, or the like.

The character font is stored in the form of a coefficient of a function, and can be scaled to an arbitrary magnification. Also, the center can be arbitrarily specified for the coordinates. For this reason, an arbitrary design character can be type-set at an arbitrary position in an arbitrary size.

The above mechanism can be implemented by a program using the C language in a PC-9801DA equipped with a numerical processor for floating-point arithmetic.

In order to confirm the effects of the present invention, data was compressed according to the present invention with respect to "Mincho""Min" and "Body" Gothic "words" and JIS first-level characters. Table 2 shows the results. In addition, three of these “akira”, “body”, and “word”
37 to 39 show the original image and the reproduced image according to the present invention (by a 300 DPI laser printer) for characters. It can be seen that the reproduction was almost faithful.

[0282]

[Table 2]

Table 2 shows the data amount (byte), compression ratio (%), and compression time (second) after each character is subjected to data compression by the method of the present invention. Here, the compression ratio is obtained by dividing the data amount (byte) of the font compressed according to the method of the present invention by the data amount (about 8 kbytes) of the original image and multiplying by 100 and expressing it as%. Although the original image has a data amount of about 8 kbytes,
When compressed by the method of the present invention, the data amount is reduced to 300 to 500 bytes.

The compression ratio is about 2 to 6%, and can be reduced to an extremely small amount of data. The compression time per character is about several seconds, which is extremely short. Here, the compression time is a CPU time, and also includes a time required for processing for dividing and combining data contained in one word and a graphic time.

The reason why the processing time is short and the amount of data is small is that many characters in the typeface are composed of straight portions,
This is because the number of joint points obtained by iterative approximation in the second step is small because the joint points are extracted as obvious joint points in the first stage.

[U. Image storage device 2] Stores the reproduced character font as it is. It means any mechanical device that stores characters printed by the printer as it is. A video camera or the like can also be used.
This includes the printed page. The image storage device may be omitted.

[0287]

According to the present invention, it is possible to read a basic character font and store and store it with a small amount of data. Also, the processing time per character is short. Therefore, even when a new character font of thousands of kanji is created, it can be stored as data in a short time. It's not just stored, it's easy to play. Using the stored data, characters of any size can be reproduced.

Conventionally, enlargement and reduction of characters have not been easy, and there has been no means other than enlargement or reduction by optical means.
If the image is optically enlarged or reduced, noise is introduced and the quality is reduced. Also, the degree of freedom is low and it takes time.

According to the present invention, since data is accumulated as joint points and coefficients of a piecewise polynomial, enlargement and reduction of the character scale can be performed by calculation. Therefore, enlargement / reduction movement of characters can be performed quickly and freely. These operations do not degrade character quality. The present invention can further improve the quality of character fonts through the removal of junctions.

[Brief description of the drawings]

FIG. 1 is an overall configuration diagram showing an overall mechanism of a character font data input / output device of the present invention.

FIG. 2 is a diagram showing an X, Y coordinate system defined for pixels in an image obtained by reading characters.

FIG. 3 is a diagram showing a chain code around one pixel.

FIG. 4 is a diagram showing a scanning direction for searching for a contour point in image data.

FIG. 5 is a diagram showing a search direction for finding a next contour point when one contour point is found.

FIG. 6 is a diagram showing a contour point when a black pixel and a white pixel exist and a contour point next thereto.

FIG. 7 is a diagram showing a state in which an outer contour line and an inner contour line are extracted from square-shaped image data and a pixel is assigned a value of 2;

FIG. 8 is a flowchart showing the configuration of a contour point sequence extraction device.
G.

FIG. 9 is a flowchart of a data approximation mechanism for approximating a contour point sequence and obtaining a curvature.

FIG. 10 is a flow chart showing a process of determining a coefficient which is a part of the data approximation mechanism and approximates the entire contour point sequence by a piecewise polynomial.

FIG. 11 is a flowchart for calculating a curvature at each point of a contour point sequence approximated in the preceding stage.

FIG. 12 is a flowchart showing a mechanism for extracting a perfect circle based on data approximated by a piecewise polynomial.

FIG. 13 is a flowchart showing an outline of a joining point extraction technique.

FIG. 14 is a flowchart showing a mechanism for extracting a position of a joining point from a curvature calculated previously.

FIG. 15 is a diagram showing an example of original characters “A” and “Po” for creating a character font.

FIG. 16 is a diagram showing an example in which a sequence of outline points of “A” and “Po” is obtained, and a joint point is further extracted.

FIG. 17 is a schematic flowchart of an optimum joint extracting mechanism;
G.

FIG. 18 is a diagram showing temporary junction points selected based on curvature and numbers of candidate junction points in the vicinity thereof.

FIG. 19 is a diagram showing numbers assigned to respective points in the case where a temporary junction selected by curvature has a nearby junction near the output.

FIG. 20 is a flowchart for determining an adaptation coefficient when there are neighboring junctions.

FIG. 21 shows a junction candidate C near the temporary junction selected by the curvature, a junction B near the output, a junction D next to the temporary junction, and a junction A immediately before the junction near the output. The figure which shows the example of the approximate curve which connects and the number of inflection points.

FIG. 22 is a flowchart for calculating an adaptation coefficient when there is no neighboring joint at a temporary joint selected by curvature.

FIG. 23 is a diagram showing a connection point candidate B of the temporary connection point, connection point candidates A and C of the temporary connection points before and after the temporary connection point, and a curve connecting these points when there is no nearby connection point at the temporary connection point; The figure for clarifying the number attached to.

FIG. 24 shows a candidate joint C near a temporary joint selected by curvature, a candidate B near a nearby joint near input, and a candidate D of a temporary joint immediately before the temporary joint. The figure for demonstrating a definition and a code | symbol.

FIG. 25 is a flowchart for determining a neighboring junction which is an input neighborhood and an output neighborhood of one temporary junction.

FIG. 26 is a flowchart showing the definition of a random variable indicating which of the junction candidates is the optimum junction and the repetitive operation.

FIG. 27 is a flow chart showing how to give another adaptation coefficient.
G.

FIG. 28 is a diagram showing an initial probability given to 2α + 1 joint point candidates with a temporary joint point as a center.

FIG. 29 is a diagram showing that a random variable is calculated for all temporary junctions, and a junction candidate that gives the maximum probability is stored as an optimum junction in the optimum junction storage device.

FIG. 30 is a diagram briefly showing the procedure up to this point by taking “ぱ” as an example.

FIG. 31 is a flowchart for explaining an operation of removing an unnecessary joint point from an optimum joint point and obtaining a final joint point.

FIG. 32 is a diagram showing signs of intermediate junctions and junctions at both ends which are objects to be determined whether or not to be removed when a plurality of straight junctions are continuously present.

FIG. 33 is a view showing removal of the intermediate junction when the length of a perpendicular foot descending from the intermediate junction to the straight line connecting the junctions at both ends in the arrangement of FIG. 35 is smaller than a certain threshold;

FIG. 34 is a view showing intermediate joint points to be determined whether or not to be removed when a plurality of arc joint points are continuously present, and the signs of the joint points at both ends.

FIG. 35 is a diagram showing the radius and center of an arc starting from a first junction, and the radius and center of an arc starting from a second junction in FIG. 37;

FIG. 36 is a view for explaining an operation of approximating data from data such as a contour point sequence, a final joint point, and a perfect circle, and expressing the contour point sequence by an approximation function.

FIG. 37 is a diagram of an original image of the character “body” and an image obtained by compressing and reproducing the original image by the method of the present invention.

FIG. 38 is a view showing an original image of a word character and an image obtained by data compression and reproduction of the original image by the method of the present invention.

FIG. 39 is a view of an original image of the word “bright” and an image obtained by data compression and reproduction of the original image by the method of the present invention.

FIG. 40 shows a quadratic full-energy function and 0th, 1st and 3rd order
Schematic diagram of the next full-energy function.

FIG. 41 is a schematic diagram showing that approximation can be increased by increasing the number of dimensions even when data is not sufficiently approximated when the number of basis functions is small when a quadratic full-energy function is employed. FIG.

FIG. 42 is a diagram showing a procedure for approximating the whole contour point sequence piecewise by a piecewise polynomial using the character “sum” as an example.

 ──────────────────────────────────────────────────続 き Continuation of the front page (56) References JP-A-60-49483 (JP, A) JP-A-57-159363 (JP, A) JP-A-62-274372 (JP, A) JP-A-61-274 221979 (JP, A) IEICE Transactions D VOL. J70-D NO. 6P. 1164-1172 (June 1987) IEICE Transactions D-II VOL. J73-D-II NO. 9 P. 1448-1457 (September 1990)

Claims (7)

(57) [Claims] 1. A character reading device that optically reads character font data and stores the character font data in correspondence with a finite number of pixels arranged vertically and horizontally, and (b) a character reading device that associates characters read in association with pixels arranged vertically and horizontally. A contour line extraction mechanism for extracting a contour line; (c) a contour point sequence storage mechanism for storing two-dimensional coordinates (X, Y) of the extracted contour line for each continuous group; X contour point sequence for each independent variable Y coordinates t, approximated by a quadratic piecewise polynomial that the dependent variable x and y, dimensions quadratic piecewise polynomial until the approximation accuracy is within a predetermined range A data approximation mechanism A that repeats least-squares approximation while increasing the number to obtain an approximate polynomial for each group of contour point sequences; and (e) contour points for each group in x, y space from the approximation result.
A curvature calculation mechanism for finding a curvature at each point in the sequence ; (f) a perfect circle extraction mechanism for extracting a perfect circle from the curvature data for each group; and (g) a curvature data of a contour point sequence excluding the perfect circle. A temporary junction position extraction mechanism for extracting a point having a curvature of infinity or a value larger than a certain value as a temporary junction, and (h ) a contour of one of the temporary junctions (first temporary junction). Dot sequence
One of the predetermined number of points before and after the above is regarded as a first joining point candidate,
Others on the same contour point sequence within a predetermined radius from the first temporary joint point
Before and after on the outline point sequence of one of the temporary joint points (neighboring joint points)
One of the fixed points is regarded as a second joint point candidate, and on the same contour point sequence.
And the first fixed point, the first temporary joining point, and the
So that the neighboring junction and the second fixed point are arranged in a line in this order.
A method for selecting the near junction, the first fixed point, and the second fixed point
A step, and all of the first junction candidate and the second junction candidate
For all combinations, the first fixed point and the first joint point
The four points of the candidate, the second joint point candidate, and the second fixed point are
The first joint point based on the smoothness of the line connecting
Means for determining the degree of complementarity of the complement;
Optimum connection alternative to the first temporary connection point by selecting a connection point candidate
Maintained and optimal junction extraction mechanism having a means to consent, is (i) approximation accuracy without it from the optimum junction is two or more arc start point to the straight line or a continuous two or more consecutive An unnecessary joint removal mechanism that finds unnecessary unnecessary joints and removes them and integrates a straight line or a circular arc; and (j) a final joint notation that stores the optimal joints left unremoved as final joints. billion devices and, (k) a straight line between the adjacent final junction point in point sequence of the same group, independent variable t when is approximated by an arc of the order which at a predetermined approximation accuracy is not obtained, x, y between the final junction point approximating approximation accuracy in quadratic piecewise polynomial that is a dependent variable are adjacent repeat the least square approximation with increasing number of dimensions of the second-order piecewise polynomial to within a predetermined value Data approximator for approximating by linear, arc, piecewise polynomial And B, the compressed data storage mechanism for storing the parameters of the function that approximates between the final junction adjacent to (l) the final junction point coordinates for each group of circularity data and point sequence, (m) a contour reproducing mechanism for reproducing the contour to obtain the parameters of the function that approximates between the final junction point and the adjacent final junction point coordinates for each group of inputs the stored compressed data has been perfect circle data and a sequence of points, (N) a character reproducing mechanism for associating pixels inside the reproduced contour line with different values for external pixels; and (o) a reproduction data output mechanism for outputting the reproduced character font as characters. Character data input and output device. (A) a character reading device that optically reads character font data and stores the character font data in correspondence with a finite number of pixels arranged vertically and horizontally; and (b) a character reading device that associates characters read in association with the pixels arranged vertically and horizontally. A contour line extraction mechanism for extracting a contour line; (c) a contour point sequence storage mechanism for storing two-dimensional coordinates (X, Y) of the extracted contour line for each continuous group; X contour point sequence for each independent variable Y coordinates t, approximated by a quadratic piecewise polynomial that the dependent variable x and y, dimensions quadratic piecewise polynomial until the approximation accuracy is within a predetermined range A data approximation mechanism A that repeats least squares approximation while increasing the number to obtain an approximate polynomial for each group of contour point sequences; and (e) the curvature at each point of the point sequence for each group in x, y space from the above approximation results. And (f) extracting a perfect circle from the curvature data for each group. To a perfect circle extraction mechanism, (g) temporary joining point position extraction for extracting a point having a curvature of constant value greater than the value in either infinity from the data of the curvature of the contour point sequence except true circle as a temporary junction (H ) a contour point sequence of one of the temporary joint points (first temporary joint point)
One of the predetermined number of points before and after the above is regarded as a first joining point candidate,
Others on the same contour point sequence within a predetermined radius from the first temporary joint point
Before and after on the outline point sequence of one of the temporary joint points (neighboring joint points)
One of the fixed points is regarded as a second joint point candidate, and on the same contour point sequence.
And the first fixed point, the first temporary joining point, and the
So that the neighboring junction and the second fixed point are arranged in a line in this order.
A method for selecting the near junction, the first fixed point, and the second fixed point
A step, and all of the first junction candidate and the second junction candidate
For all combinations, the first fixed point and the first joint point
The four points of the candidate, the second joint point candidate, and the second fixed point are
The first joint point based on the smoothness of the line connecting
Means for determining the degree of complementarity of the complement;
Optimum connection alternative to the first temporary connection point by selecting a connection point candidate
The optimum junction extraction mechanism having a means for the consent, not a straight line between the optimum junction, is approximated by an arc of the order which at a predetermined approximation accuracy obtained adjacent in (k) point sequence of the same group At this time, least square approximation is performed while increasing the number of dimensions of the second-order piecewise polynomial until the approximation accuracy falls within a predetermined value by approximating the quadratic piecewise polynomial with t as an independent variable and x and y as dependent variables. between the optimum junction to repeatedly adjacent straight, adjacent arc, a data approximation mechanism B approximated by piecewise polynomial, and (l) said optimum bonding point coordinates for each group of circularity data and point sequence a compressed data storage mechanism for storing the parameters of the function that approximates between the optimum junction, adjacent (m) and the stored optimal junction of the coordinates of each group enter the compressed data perfect circle data and point sequence to obtain the parameters of the function that approximates between the optimum junction contour lines (N) a character reproducing mechanism for associating pixels inside the reproduced outline with different values for external pixels; and (o) reproducing a reproduced character font as a character. A character data input / output device comprising a data output mechanism. (A) a character reading device that optically reads character font data and stores the character font data in correspondence with a finite number of pixels arranged vertically and horizontally, and (b) a character reading device that associates characters read in association with the pixels arranged vertically and horizontally. A contour line extraction mechanism for extracting a contour line; (c) a contour point sequence storage mechanism for storing two-dimensional coordinates (X, Y) of the extracted contour line for each continuous group; X contour point sequence for each independent variable Y coordinates t, approximated by a quadratic piecewise polynomial that the dependent variable x and y, dimensions quadratic piecewise polynomial until the approximation accuracy is within a predetermined range A data approximation mechanism A that repeats least squares approximation while increasing the number to obtain an approximate polynomial for each group of contour point sequences; and (e) the curvature at each point of the point sequence for each group in x, y space from the above approximation results. And (f) extracting a perfect circle from the curvature data for each group. A perfect circle extraction mechanism, and (g) the junction position extraction mechanism for extracting the junction point having a curvature of constant value greater than the value from the data of the curvature of the contour point sequence is either infinity except circularity , (k) a straight line between adjacent bonding points in the point sequence of the same group, independent variables <br/> is t when the approximated by an arc of the order which at a predetermined approximation accuracy is not obtained, x, y junctions approximating approximation accuracy in quadratic piecewise polynomial that is a dependent variable are adjacent repeat the least square approximation with increasing number of dimensions of the secondary <br/> piecewise polynomial to within a predetermined value function that approximates between, lines, arcs, and the data approximation mechanism B approximated by piecewise polynomial, between the junction and the adjacent (l) of the junction points for each group of circularity data and dot sequence coordinates And (m) inputting the stored compressed data and storing the compressed data. A contour reproducing mechanism for reproducing the contour to obtain the parameters of the function that approximates between junction adjacent to the circle data and the point junction of the coordinate of each group of columns, the internal (n) reproduced contour A character data input / output device comprising: a pixel and a character reproduction mechanism for making different values correspond to external pixels; and (o) a reproduction data output mechanism for outputting a reproduced character font as a character. 4. A character reading device that optically reads character font data and stores the character font data in correspondence with a finite number of pixels arranged vertically and horizontally, and (b) a character reading device that reads characters associated with the pixels arranged vertically and horizontally. a contour line extraction mechanism for extracting a contour line, and輸郭line series of points storage mechanism for storing for each group successive (c) 2-dimensional coordinates of the extracted contour lines (X, Y), (e ) X, A curvature calculating mechanism for obtaining a discrete curvature at each point of a point sequence for each group in the Y space; (f) a perfect circle extracting mechanism for extracting a perfect circle from the curvature data for each group; and (g) a perfect circle. A temporary junction position extraction mechanism for extracting a point having a curvature of infinity or a value larger than a certain value as a temporary junction from the data of the curvature of the contour point sequence to be removed , and (h) one of the temporary junctions (First temporary joining point) outline point sequence
One of the predetermined number of points before and after the above is regarded as a first joining point candidate,
Others on the same contour point sequence within a predetermined radius from the first temporary joint point
Before and after on the outline point sequence of one of the temporary joint points (neighboring joint points)
One of the fixed points is regarded as a second joint point candidate, and on the same contour point sequence.
And the first fixed point, the first temporary joining point, and the
So that the neighboring junction and the second fixed point are arranged in a line in this order.
A method for selecting the near junction, the first fixed point, and the second fixed point
A step, and all of the first junction candidate and the second junction candidate
For all combinations, the first fixed point and the first joint point
The four points of the candidate, the second joint point candidate, and the second fixed point are
The first joint point based on the smoothness of the line connecting
Means for determining the degree of complementarity of the complement;
Optimum connection alternative to the first temporary connection point by selecting a connection point candidate
Maintained and optimal junction extraction mechanism having a means to consent, is (i) approximation accuracy without it from the optimum junction is two or more arc start point to the straight line or a continuous two or more consecutive An unnecessary joint removal mechanism that finds unnecessary joints that are unnecessary and removes them and integrates a straight line or an arc; and (j) a final joint storage that stores the remaining optimal joints that have not been removed as final joints. a device, the independent variable, x, y and t is the time is not obtained straight line approximated by an arc of the order which at a predetermined approximation accuracy between adjacent final junction point in the point sequence of (k) the same group between the final junction point dependent variable and the second-order approximated by piecewise polynomial approximation accuracy is adjacent repeated a least squares approximation with increasing number of dimensions of the second-order piecewise polynomial to within a predetermined value, A data approximator that approximates straight lines, circular arcs, and piecewise polynomials And B, the compressed data storage mechanism for storing the parameters of the function that approximates between the final junction adjacent to (l) the final junction point coordinates for each group of circularity data and point sequence, (m) a contour reproducing mechanism for reproducing the contour to obtain the parameters of the function that approximates between the final junction point and the adjacent final junction point coordinates for each group of inputs the stored compressed data has been perfect circle data and a sequence of points, (N) a character reproducing mechanism for associating pixels inside the reproduced contour line with different values for external pixels; and (o) a reproduction data output mechanism for outputting the reproduced character font as characters. Character data input and output device. 5. A character font data is optically read, and data is stored in correspondence with a finite number of pixels arranged vertically and horizontally. (B) An outline of a character read in association with pixels arranged vertically and horizontally. (C) storing the two-dimensional coordinates (X, Y) of the extracted contour line for each continuous group; and (d) setting the X and Y coordinates of the contour point sequence for each group to t independently. Approximate by a quadratic piecewise polynomial with variables x and y as dependent variables, and repeat least-squares approximation while increasing the number of dimensions of the piecewise polynomial until approximation accuracy is within a predetermined range. A polynomial is obtained; (e) a curvature at each point of a point sequence for each group in the x, y space is obtained from the approximation result; (f) a perfect circle is extracted from the curvature data for each group; (g) From the curvature data of the contour point sequence excluding the perfect circle, calculate the curvature that is infinite or larger than a certain value. The point having extracted as junction, (k) in the point sequence identical grouping straight line between adjacent junction points, independent variable t when is approximated by an arc of the order which at a predetermined approximation accuracy is not obtained , x, junctions approximation accuracy is approximated by a quadratic piecewise polynomial that is a dependent variable y are adjacent repeat the least square approximation with increasing number of dimensions of the second-order piecewise polynomial to within a predetermined value between, lines, arcs, and approximated by a piecewise polynomial, stores the parameters of the function that approximates between junction adjacent to (l) the junction points of the coordinates for each group of circularity data and point sequence (M) When outputting the other character, output the stored perfect circle data, the coordinates of the junction point for each group of point sequences, and the parameters of a function that approximates the adjacent junction point. Then, the outline of the character font is reproduced, and (n) reproduction A character data input / output method characterized in that a character is reproduced by associating a different value with a pixel inside the reproduced contour line and an external pixel, and (o) outputting the reproduced character font as a character. 6. A character font data is optically read, data is stored in correspondence with a finite number of pixels arranged vertically and horizontally, and a contour line of a character read in association with the pixels arranged vertically and horizontally. (C) storing the two-dimensional coordinates (X, Y) of the extracted contour line for each continuous group; and (d) setting the X and Y coordinates of the contour point sequence for each group to t independently. Approximate by a quadratic piecewise polynomial with variables x and y as dependent variables, and repeat least-squares approximation while increasing the number of dimensions of the piecewise polynomial until approximation accuracy is within a predetermined range. A polynomial is obtained; (e) a curvature at each point of a point sequence for each group in the x, y space is obtained from the approximation result; (f) a perfect circle is extracted from the curvature data for each group; (g) From the curvature data of the contour point sequence excluding the perfect circle, calculate the curvature that is infinite or larger than a certain value. (H ) a contour point sequence of one of the temporary connection points (first temporary connection point)
One of the predetermined number of points before and after the above is regarded as a first joining point candidate,
Others on the same contour point sequence within a predetermined radius from the first temporary joint point
Before and after on the outline point sequence of one of the temporary joint points (neighboring joint points)
One of the fixed points is regarded as a second joint point candidate, and on the same contour point sequence.
And the first fixed point, the first temporary joining point, and the
So that the neighboring junction and the second fixed point are arranged in a line in this order.
Select the neighboring junction, the first fixed point, and the second fixed point, and
All combinations of the first junction candidate and the second junction candidate
The first fixed point, the first junction candidate,
The four points of the second joint point candidate and the second fixed point are the most smooth.
Of the first candidate junction based on the smoothness of the line connecting
Of the first junction point with the highest degree of fitness
(I) Approximation accuracy is maintained even if there is no optimum joining point, which is the starting point of two or more continuous straight lines or two or more continuous arcs, instead of the first temporary joining point. Unnecessary optimal joints such as sagging are found and removed, and a straight line or an arc is integrated. (J) The optimal joints remaining without being removed are stored as final joints. (K) Point sequence of the same group between adjacent final junction point of the inner straight line approximated by an arc of the order independent variable t when not obtained predetermined approximation accuracy in this, x, in second-order piecewise polynomial as the dependent variable y between the final junction approximation to the approximation accuracy is adjacent repeated a least squares approximation with increasing number of dimensions of the second-order piecewise polynomial to within a predetermined value, approximate straight lines, arcs, piecewise polynomial, (L) The coordinates of the above-mentioned final junction point and the neighborhood for each group of perfect circle data and point sequence Enter the character font data by storing the parameters of the function that approximates between the final junction point that, (m) when outputting the other characters, final for each group of the stored circularity data and point sequence outputting the parameters of the function that approximates between the final junction point and the adjacent junction points coordinates, from which reproduces the outline of the character font, different inside the pixels and external pixels (n) reproduced contour A character data input / output method, wherein a character is reproduced by associating values, and (o) the reproduced character font is output as a character. 7. A character font data is optically read, and data is stored in correspondence with a finite number of pixels arranged vertically and horizontally. (B) A contour line of a character read in association with pixels arranged vertically and horizontally. (C) storing the two-dimensional coordinates (X, Y) of the extracted contour line for each continuous group; and (e) discrete values at each point of a point sequence for each group in the X, Y space. The curvature is obtained. (F) A perfect circle is extracted from the curvature data of each group. (G) The curvature data of the contour point sequence excluding the perfect circle has a curvature that is infinite or larger than a certain value. (H ) a contour point sequence of one of the temporary connection points (first temporary connection point)
One of the predetermined number of points before and after the above is regarded as a first joining point candidate,
Others on the same contour point sequence within a predetermined radius from the first temporary joint point
Before and after on the outline point sequence of one of the temporary joint points (neighboring joint points)
One of the fixed points is regarded as a second joint point candidate, and on the same contour point sequence.
And the first fixed point, the first temporary joining point, and the
So that the neighboring junction and the second fixed point are arranged in a line in this order.
Select the neighboring junction, the first fixed point, and the second fixed point, and
All combinations of the first junction candidate and the second junction candidate
The first fixed point, the first junction candidate,
The four points of the second joint point candidate and the second fixed point are the most smooth.
Of the first candidate junction based on the smoothness of the line connecting
Of the first junction point with the highest degree of fitness
(I) Approximation accuracy is maintained even if there is no optimum joining point, which is the starting point of two or more continuous straight lines or two or more continuous arcs, instead of the first temporary joining point. Unnecessary optimal joints such as sagging are found and removed, and a straight line or an arc is integrated. (J) The optimal joints remaining without being removed are stored as final joints. (K) Point sequence of the same group between adjacent final junction point of the inner straight line approximated by an arc of the order independent variable t when not obtained predetermined approximation accuracy in this, x, in second-order piecewise polynomial as the dependent variable y between the final junction approximation to the approximation accuracy is adjacent repeated a least squares approximation with increasing number of dimensions of the second-order piecewise polynomial to within a predetermined value, approximate straight lines, arcs, piecewise polynomial, (L) The coordinates of the above-mentioned final junction point and the neighborhood for each group of perfect circle data and point sequence Enter the character font data by storing the parameters of the function that approximates between the final junction point that, (m) when outputting the other characters, final for each group of the stored circularity data and point sequence outputting the parameters of the function that approximates between the final junction point and the adjacent junction points coordinates, from which reproduces the outline of the character font, the inner pixels of (n) reproduced contours, the outside of the pixel A character data input / output method characterized by reproducing characters by associating different values, and (o) outputting the reproduced character font as characters.