JPS646511B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a line figure compression method, and particularly to a line figure compression method that is applied when two strokes have a common point or a common line segment and can be expressed as a single stroke in a line figure composed of a stroke series. The present invention relates to a line graphics compression method that compresses data from two strokes into one stroke.

For example, when there are two line figures such as the first stroke I (starting point 1 → 2 → 3 → ending point 4) and the second stroke (starting point A → B → C → ending point D) in Figure 1A, It is better to integrate and store the strokes as one stroke than to store them as separate strokes, since the data at points A and 4 can be omitted.
Data can be compressed.

Conventionally, when performing such an integration process of two strokes, a two-dimensional planar memory M is used, as shown in FIG. The strokes are expanded and converted into a pattern of "1" and "0" on this two-dimensional plane (in the figure, the black dots are "1" indicating the existence of each stroke). Then this "1",
This was re-extracted from the pattern "0" as one stroke (starting point 1→2→3→B→C→end point D). Therefore, when these strokes exist in a wide range, a two-dimensional planar memory M necessary for developing these strokes requires a large area. This has the disadvantage that a large amount of two-dimensional planar area must be reserved in the memory of the data processing device, and when such graphic processing is performed, it has a large influence on other objects and data processing efficiency is reduced.

Therefore, an object of the present invention is to store strokes in a memory when two consecutive strokes have a common point or a common line segment in a line figure composed of a stroke series and can be expressed as one stroke. To provide a line graphics compression method that compresses data by integrating two strokes into one stroke without expanding into a pattern of "1" and "0". For this purpose, the line figure compression method of the present invention includes an end point segment coincidence detection means for detecting whether the end point segments of the first stroke and the end point segments of the second stroke match;
end point coincidence detection means for detecting a state in which the end points of the first stroke and the end points of the second stroke match; and end point segment overlap state detection means for detecting a state in which end point segments of the first stroke and the second stroke overlap. , the first stroke and the second stroke according to the detection state of each of the detection means.
An integrated control means for instructing a manner of integration with the stroke, and an integrated means for integrating the first stroke and the second stroke based on an integrated control signal output from the integrated control means, whereby the first stroke and the second stroke are integrated. The present invention is characterized in that the second strokes are integrated.

Before describing the present invention in detail based on one embodiment, the principle thereof will be explained.

In the present invention, the overlapping relationship between the end points of two consecutive strokes is coded, and when there is overlap, the two strokes are combined into one stroke based on this code information and data compression is performed. . To this end, the overlapping relationship is encoded,
Then, stroke pair integration processing is performed for the types of duplicated chords. Next, the creation of stroke pair duplication codes for this purpose and the integration of stroke pairs will be explained with reference to FIGS. 2 and 3.

Creating stroke pair overlap codes Depending on the state of two strokes (a stroke is a series of coordinate points with direction), the overlap relationship between their end points (starting point and ending point) is determined by codes 1 to 1 in Figure 2.
It can be classified into nine types as shown in 8.0. So create stroke vs. overlap code depending on these conditions. Here, the starting point of the first stroke is S ₁ , the second point (inflection point) is S ₁ ',
Let the end point be E ₁ , the point before the end point be E ₁ ′, and let the straight line composed of this (S ₁ , S ₁ ′) be l ^S ₁ and composed of (E ₁ , E ₁ ′) Let the straight line be l ^E ₁ . Similarly, for the second stroke, S ₂ , S ₂ ′, E ₂ ,
Define E ₂ ′ and l ^S ₂ , l ^E ₂ .

Then, as shown in the first linear example at the top of Fig. 2, the end point E ₁ of the first stroke and the second
When the starting point S ₂ of the stroke matches, and l ^E ₁ of the first stroke and l ^S ₂ of the second stroke do not match (l ^E ₁ ≠ l ^S ₂ ), that is, l ^E ₁ and l ^S ₂ are When there is no overlap, IN=1 is assigned as the stroke pair overlap code IN. Similarly, as in the second linear example,
If the end point E ₁ of the first stroke and the end point E ₂ of the second stroke match, and the l ^E ₁ of the first stroke and l ^E ₂ of the second stroke do not match, the stroke pair duplication code IN is IN = 2. Grant.
Then, as in the fifth linear example, l ^E ₁ of the first stroke and l ^S ₂ of the second stroke coincide, and the end point E ₁ of the first stroke is between the points (S ₂ , S ₂ ′). The starting point S ₂ of the second stroke is between the points (E _{1 ′} , _{E 1 )} and between the points (E ₁ ′, S ₂ ′). In this case, IN=5 is assigned as the stroke pair duplication code IN. Also, as in the sixth linear example, the first stroke
l ^E ₁ and l ^E ₂ of the second stroke match, and the end point E ₁ of the first stroke is between the points (E ₂ , E ₂ ′) and between the points (E ₁ ′, E ₂ ′) In addition, when the end point E ₂ of the second stroke is between the points (E ₁ , E ₁ ′) and between the points (E ₁ ′, E ₂ ′), IN=6 is assigned as the stroke pair overlap code IN. In this way, as shown in FIG. 2, when the start points or end points match in the states shown in linear examples 1 to 4, stroke overlap pair codes IN1 to IN4 are assigned. Then, if there is an overlapping line segment part in the state shown in linear examples 5 to 8, the overlapping pair code is
Give IN5-8. However, in other cases, it is assumed that there is no overlapping relationship and a stroke overlapping pair code IN0 is assigned. As an example of this other case, there are also cases where part of the line segments match,
As shown in linear example 8, l ^S ₁ and l ^S ₂ may match. However, in this case, as shown in FIG. 3A, the first stroke and the second stroke, which should not originally be integrated, are in an overlapping relationship at their starting portions, so they cannot be integrated. Of course, as shown in Figure 3 (b), cases where the first stroke and part of the second stroke that cannot be integrated are in an overlapping relationship are also included in this other example, and it is assumed that there is no overlapping relationship as a stroke pair overlapping code. IN=0 will be assigned.

Integration of stroke pairs If the stroke pair duplicate code IN is other than 0, it is a stroke pair that can be combined, so data compression is performed by creating an integrated stroke for each stroke pair duplicate code according to the consolidation rule shown in Figure 4. .

For example, in the case of linear example 1, the end point E ₁ of the first stroke and the start point S ₂ of the second stroke coincide, but the start point S ₂ of the second stroke is omitted and as shown in the integration rule (S ₁ ,…,E ₁ ,S ₂ ′,
..., E ₂ ) to create a new integrated stroke. This results in strokes vs. duplicate code
When IN is 1, data compression can be performed for the starting point _S2 . In addition, in the case of linear example 2, the end point E ₁ of the first stroke and the end point E ₂ of the second stroke coincide, but the end point E ₁ of the first stroke is omitted and as shown in the integration rule (S ₂ ...E ₂ , E ₁ ′...S ₁ ) to create this new integrated stroke. Thus, in the case of the stroke pair duplication code IN2, data can be compressed by the end point _E1 . In the case of linear example 5, the end point E ₁ of the first stroke and the start point S ₂ of the second stroke are omitted and a new integrated stroke is created as (S ₁ ...E ₁ ′, S ₂ ′ ...E ₂ ) So,
When the stroke pair duplication code IN is 5, data compression of E ₁ and S ₂ can be performed.
In this way the stroke vs. duplicate code IN is
When the starting points or ending points expressed as IN=1 to 4 match, only one point can be compressed, and when expressed as codes 5 to 8, only two points can be compressed.

Generally, the first stroke is (S ₁ , S ₁ ′…E ₁ ′,
E ₁ ), and the _second stroke is represented by (S ₂ , S ₂ ′...E ₂ ′,
E ₂ ) is represented by n ₂ points, and the integrated stroke is (a ₁ , a ₂ …a _o )
When represented by n points, n = (n ₁ + n ₂ -1) for IN = 1 to 4
Therefore, for IN=5 to 8, n=(n ₁ + n ₂ -2)
Depending on the type of stroke-to-duplicate code, it is possible to delete one or two coordinate points and obtain a data-compressed stroke.

Next, an embodiment of the present invention for performing data compression as described above will be explained based on FIGS. 5 and 6.

FIG. 5A is an example of a stroke pair duplication code generation circuit, FIG. 5B is an explanatory diagram of its operating state, and FIG. 6 is an example of a stroke integration circuit.

In FIG. 5A, 1 is a one-end point segment equation parameter calculation circuit, which calculates the starting point S ₁ of the first stroke $ ₁ , the second point S ₁ ′, the point E ₁ ′ one place before the end point, and the end point. Based on E ₁ , the equations of the endpoint segments l ^S ₁ and l ^E ₁ are calculated, and the parameters of each of these straight lines are calculated. 2 is a second end point segment equation parameter calculation circuit, which calculates the starting point S ₂ of the second stroke $ ₂ and the second point
Based on S ₂ ′, the point E ₂ ′ just before the end point, and the end point E ₂ , the equations of the end point segments l ^S ₂ and l ^E ₂ are calculated, and the parameters of each of these straight lines are calculated.

3 is an equation coincidence detection circuit, which detects each equation of the endpoint segments l ^S ₁ and l ^E ₁ calculated by the first endpoint segment equation parameter calculation circuit 1 and the equations calculated by the second endpoint segment equation parameter calculation circuit 2. It compares the equations of the end point segments l ^S ₂ and l ^E ₂ to detect whether these end point segments match or not, and outputs the following code L depending on the state of match or mismatch. be.
(Note that this code L corresponds to the stroke pair overlap code IN shown in Figures 2 and 4.) When l ^E ₁ = l ^S ₂ Code L = 5 l ^E ₁ = l ^E ₂ When code L = 6 When l ^S ₁ = l ^S ₂ Code L = 7 When l ^S ₁ = l ^E ₂ Code L = 8 When none of the above, code L = 0 4 is an end point coincidence detection circuit. This detects the matching relationship between the two sets of end points (S ₁ , E ₁ ) and (S ₂ , E ₂ ), and outputs the following code P depending on the matching/mismatching state. (Note that this code P corresponds to the stroke pair overlap code IN shown in Figures 2 and 4.) When E ₁ = S ₂ Code P = 1 When E ₁ = E ₂ Code P = 2 When S ₁ = S ₂ Code P = 3 When S ₁ = E ₂ Code P = 4 When none of the above, code P = 0 5 is an end point segment duplication detection circuit, and the end point segment l ^S ₁ , l Each point ^S ₁ , S ₁ ′, _{E 1} ′,
E ₁ and each point S ₂ , which constitutes the end point segment l ^S ₂ , l ^E ₂ ,
The following code S is output depending on the relationship with S ₂ ′, E ₂ ′, and E ₂ . (Note that this code S corresponds to the stroke pair overlap code IN shown in Figure 2, and therefore also to those in Figure 4.) E ₁ is (S ₂ , S ₂ ′) and (E ₁ ′, S ₂ ′), and S ₂ is between (E ₁ ′, E ₁ ) and (E ₁ ′, S ₂ ′) Code S=5 E ₁ is between (E ₂ , E ₂ ′) and (E ₁ ′, S ₂ ′), and E ₂ is between (E ₁ , E ₁ ′) and (E ₁ ′, E ₂ ′), then code S=6 S ₁ is between (S ₂ , S ₂ ′) and (S ₁ ′, S ₂ ′), and S ₂ is (S ₁ , S ₁ ′) and between (S ₁ ′, S ₂ ′) Code S=7 S ₁ is between (E ₂ , E ₂ ′) and between (S ₁ ′, E ₂ ′) and E ₂ is between (S ₁ , S ₁ ′) and (S ₁ ′, E ₂ ′) Code S = 8 If none of the above Code = 0 6 is the above equation Whether or not the first stroke $1 and the second stroke $ ₂ can be integrated based on the code L, code P, and code S output from the match detection circuit 3, end point match detection circuit 4, and end point segment duplication detection circuit ₅ , respectively. If it is possible to identify and integrate the
It determines which one is shown in the figure and outputs a corresponding stroke pair overlap code. In this case, if code L=code S,
This corresponds to linear examples 5 to 8 above, and outputs code L as the stroke pair overlap code IN (that is, stroke pair overlap code IN=code L). When code L=0 and code P is 1 to 4, this corresponds to linear examples 1 to 4, and code P is output as the stroke vs. overlap code IN (i.e., stroke vs. overlap code IN). Code IN = Code P). In other cases, these two strokes cannot be integrated, and 0 is output as the stroke pair overlap code IN. The operating states of the code integration circuit 6 of FIG. 5A are collectively illustrated in FIG. 5B.

In FIG. 6, 7 is a first stroke rearrangement circuit, and each point (S 1 _{, S 1 ,}
S ₁ ′…E ₁ ′, E ₁ ) are being transmitted. The state of each point is used to delete the overlapping points of the first stroke from the stroke pair overlapping code IN outputted from the integration circuit 6 and rearrange the order.
For example, if the stroke pair overlap code IN=2 is applied, the end point E ₁ of the first stroke $ ₁ is deleted, and the start point S ₁ of the first stroke becomes the end point of the new integrated stroke $, so the array The fourth
It is necessary to rearrange the integration rules as shown in the latter half of the ( ) in the figure. Therefore, this first stroke $ ₁ = (S ₁ , S ₁ ′...E ₁ ′, E ₁ ) is defined as stroke $ ₁ ′=
(E ₁ ′,...S ₁ ′, S) (here, S is arranged last because it is the end point of the integrated stroke). Similarly, when the stroke pair overlap code IN=6 is transmitted, the first stroke $ ₁ is its end point E ₁
is deleted and its array is changed.

8 is a second stroke rearrangement circuit;
Each point (S ₂ , S ₂ ′...E ₂ ′, E ₂ ) of stroke $ ₂ is being transmitted. The state of each point is the stroke pair overlap code output from the integrated circuit 6.
Delete the duplicate point of the second stroke for IN,
It rearranges the order and converts it into a stroke $ ₂ ', and performs the same operation as the first stroke rearrangement circuit 7.

9 is a stroke combination circuit which combines the strokes $ ₁ ' and $ ₂ ' output from the first stroke rearrangement circuit 7 and the second stroke rearrangement circuit 8 based on the stroke pair duplication code IN,
As shown in the integration rule shown in FIG. 4, each point is arranged and output as an integrated stroke. For example, in the case of stroke pair duplication code IN2, the rearranged stroke $ ₂ ' of the second stroke $ ₂ becomes the start point side, and the deleted stroke $ ₁ ' of the first stroke $ ₁ becomes the end point side. Therefore, each point is output from the stroke coupling circuit 9 in a state as shown in FIG. Further, in the case of stroke pair duplication code IN5, the first stroke array circuit 7 and the second stroke array circuit delete the end point _E1 from the first stroke $ ₁ and delete _the start point _S2 from the second stroke $2. Converted stroke from 8$
₁ ' and $ ₂ ' are output from the stroke coupling circuit 9 as an integrated stroke such that the stroke $ ₁ ' is on the starting point side and the stroke $ ₂ ' is on the end point side. As is clear from Figure 4, the first
The converted strokes $ ₁ , $ ₂ transmitted from the stroke reordering circuit 7 and the second stroke reordering circuit 8 are outputted from the stroke combination circuit 9 as an integrated stroke $ according to whether the stroke pair duplication code IN is odd or even. It is combined and output as shown below.

Stroke vs. Duplicate Code When IN is an odd number $
= ($ ₁ ′, $ ₂ ′) Stroke versus duplicate code $ when IN is even number
= ($ ₂ ′, $ ₁ ′).

Next, we will discuss the operations in Figures 5 and 6.
This will be explained with reference to FIGS.

(1) In FIG. 5, the first stroke $ ₁ to be integrated is applied to the first endpoint segment equation parameter calculation circuit 1, and the second stroke $ ₂ is applied to the second endpoint segment equation parameter calculation circuit 2. , the equations for the endpoint segments l ^S ₁ , l ^E ₁ , l ^S ₂ , l ^E ₂ are determined, respectively. Then, each of these equations is transmitted to the equation coincidence detection circuit 3, and the coincidence or mismatch of each equation is determined by comparing each of these parameters, and the code L is determined accordingly. At this time, when the first stroke $ ₁ and the second stroke $ ₂ are in the state shown in linear example 5 in FIG. 2, l ^E ₁ =l ^S ₂ and code L=5 is output.

(2) Also, the starting point S ₁ and the ending point of the first stroke $ ₁
E ₁ and the start point S ₂ and end point E ₂ of the second stroke $ ₂ are respectively applied to the end point coincidence detection circuit 4, and their coincidence or mismatch is detected.
In this case, the code P=
0 is output.

(3) Moreover, the starting point S ₁ of the first stroke $ ₁ , the next point S ₁ ′ after the starting point, the point E ₁ ′ before the ending point, and the ending point
E ₁ and the second stroke $ ₂ also S ₂ , S ₂ ′,
Each of the points E ₂ ' and E ₂ is applied to the end point segment duplication detection circuit 5, and the code S as described above is created based on the positional relationship of each point. And in this case the end point segment l ^E ₁ of the first stroke $ ₁
Since the end point segment l ^S ₂ of the second stroke $ ₂ is in the state shown in linear example 5 in FIG. 2, the code S=5 is output.

(4) And these code L=5, code P=
0, code S=5 is transmitted to the code integration circuit 6, resulting in stroke versus duplicate code IN=5
is output and transmitted to the first stroke rearrangement circuit 7, second stroke rearrangement circuit 8, and stroke combination circuit 9 in FIG.

(5) By the way, since the first stroke $1 is input to the first stroke rearrangement circuit 7 and the second stroke $ ₁ is input to the second stroke rearrangement circuit ₈ , the integration rule in FIG. According to
The first stroke $ ₁ is output from the first stroke rearrangement circuit 7 as a stroke $ ₁ ′ with its end point E ₁ deleted, and the second stroke $ ₂ is a stroke $ ₂ ′ with its start point S ₂ deleted. This is output from the second stroke rearrangement circuit 8.
These strokes $ ₁ ′, $ ₂ ′ are input to the stroke combination circuit 9, and are arranged in the form (S ₁ ...E ₁ ′, S ₂ ′ ...E ₂ ) as shown in the integration rule in Figure 4. Output as integrated stroke $. In this way, the end point E ₁ of the first stroke $ ₁ and the second
Stroke $ ₂ and starting point _S2 are deleted to obtain a new compressed stroke.

As explained above, according to the present invention, an overlapping code expressing the overlapping relationship between end points of two consecutive strokes is created, and when an overlapping relationship exists, the overlapping point is excluded according to the overlapping code, 2
Data can be compressed from two strokes into one stroke. Therefore, according to the present invention, it is possible to integrate stroke patterns without developing them in memory, so that memory occupancy can be greatly reduced, and it is freed up for other processing. Memory can be used more efficiently, resulting in much more efficient data processing.

[Brief explanation of drawings]

Figure 1 is an explanatory diagram of conventional stroke integration processing;
Figures 2 to 4 are explanatory diagrams of the operating state of the present invention;
Figure A is an example of the stroke pair duplication code generation circuit in the present invention, Figure 5B is an explanatory diagram of its operating state,
FIG. 6 shows an example of the stroke integration circuit of the present invention. In the figure, 1 is a first end point segment equation parameter calculation circuit, 2 is a second end point segment equation parameter calculation circuit, 3 is an equation match detection circuit, 4 is an end point match detection circuit, 5 is an end point segment duplication detection circuit, and 6 is a code. integrated circuit, 7 is a first stroke reordering circuit, 8 is a second stroke reordering circuit, 9
indicate stroke coupling circuits, respectively.

Claims (1)

[Claims] 1 End point segment coincidence detection means for detecting whether an end point segment of a first stroke and an end point segment of a second stroke match; and an end point for detecting a state where the end point of the first stroke and the end point of the second stroke match. a coincidence detection means; and the first
end point segment overlapping state detection means for detecting an overlapping state of end point segments of a stroke and the second stroke; and integration for instructing an integration mode of the first stroke and the second stroke according to the detection state of each of the detection means. A control means and an integration means for integrating the first stroke and the second stroke based on an integrated control signal output from the integrated control means, thereby integrating the first stroke and the second stroke. This is a line graphics compression method that is characterized by the following.