JPS5929908B2 - Broken line approximation device for accumulated point sequence data - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a polygonal line approximation device for accumulated point sequence data that obtains a polygonal line figure that approximates a locus given as a coordinate sequence of discrete points.

Points can be two-dimensional, three-dimensional, and further expanded to include n-dimensional points for any natural number n, 2, 3, and n, respectively.
One point can be specified by providing coordinate components.

Although this invention can be applied to point sequence data of any number of dimensions, in order to simplify the explanation and facilitate understanding, the following description will be limited to two-dimensional point sequence data. Two-dimensional point sequence data (hereinafter simply referred to as point sequence data; an example of E is a point sequence obtained when drawing a line figure on a data tablet, for example).

When inputting such a point sequence to an information processing device such as a computer and processing it, if you try to treat it as point sequence data, you will have to store a huge amount of point sequence data, and the computer etc. It is uneconomical because it requires a large storage capacity. Therefore, by approximating the line figure represented by these point sequence data, which is generally a curve, with several broken lines, and newly storing only the coordinates of both end points of the obtained broken lines. Then, the original point sequence data is substituted. According to such a method, by increasing the number of broken lines, the degree of approximation to the original figure can be increased as necessary. Conventionally, such polygonal line approximation processing of point sequence data has been performed by computer software.

However, when the number of processing points is large and the processing must be performed in real time, such as when processing handwritten line drawings, the computer should not give this approximation processing the highest priority; Because it occupies a lot of time for
Unable to allocate computer processing power to other processes,
Therefore, there was a problem in that the usage efficiency of expensive computers was reduced. Furthermore, in the conventional broken line approximation method, for example, as point sequence data is input, the direction of a minute line segment connecting adjacent points is calculated, and the direction of this minute line segment is determined in advance. For example, as long as a point falls within one of the fan-shaped regions created by dividing the circumference into eight equal parts, it is considered to be a point that forms the same polygonal line, but if it deviates from that fan-shaped region, it moves to the next polygonal line. The approximation was made by considering the

However, with this conventional approximation method, when the primitive figure is mainly composed of straight lines, especially near the cusp where the angle changes sharply,
Unnecessarily short line segments that erase acute angle changes often appear, and this tendency becomes especially severe when the spacing of point sequence data is coarse relative to the size of the line shape, making it difficult to create accurate polygonal line shapes. There was also the problem that it was difficult to obtain. The purpose of this invention is to obtain high approximation accuracy by applying a large number of relatively short line segments to parts of accumulated point sequence data where the line shape changes significantly, and to obtain high approximation accuracy even near cusps that change sharply. It is an object of the present invention to provide a broken line approximation device for accumulated point sequence data that can perform approximation processing at high speed based on a new approximation method in which no extra line segments appear.

By using the broken line approximation device for accumulated point sequence data according to the present invention, in a usage where point sequence data representing a line figure is approximated by a broken line figure, the process of the broken line approximation can be performed without burdening the computer with the process. It is possible to allocate the processing power of the computer to other more complex processing, and it is also possible to improve the overall utilization efficiency of the information processing system. Next, the present invention will be explained with reference to the drawings.

Referring to FIG. 1, there is shown an example for explaining the broken line approximation method of the "broken line approximation device for accumulated point sequence data" of the present invention. Here, a part of the point sequence data to be approximated by a broken line is called a point sequence. For example, a graphic drawn with a single stroke on a data tablet is a series of points. one point series to 2
Even when divided into two series, each can become a point series. FIG. 1a displays point sequence data of sufficiently fine sampling representing the number [2], one point sequence named S. Let L1 be a straight line connecting the starting points Ps and Pe of the point series S. When expressing the straight line L1 as Ax+By+c=0, if the straight line L1 and any one point on the point series S (x'
, y') is expressed as .

Now, among the points on the point series S, find the point where this distance d is maximum, and set this point as P1.

Next, by using the point P1 obtained as shown in Fig. 1a, as shown in Figs. 1b and 1c, the point series S = (Ps, Pe)
are two point sequences S, = (Ps, Pl) and S2 = (Pl,
Pe). Next, as shown in Figure 1b, the point series S
, the same processing as that for the point sequence S in FIG. 1a is performed. That is, with respect to the straight line L2 connecting the starting point Ps and the ending point P1 of S, find the point P2 that has the maximum distance from L2 on the point series S, and further divide the point series S into two point series. do. This process is repeated by repeating the division of the point series until the distance Di (1=1, 2, . . . ) becomes smaller than a predetermined value D. 1st
The same process is repeated for the point series shown in figure c. As a result, if only the starting point and ending point of the large number of points finally obtained are left, these become the end points of each line segment of the sought polygonal line approximation, and a polygonal line figure as shown in FIG. 1d, for example, can be obtained.

Referring to FIG. 2, one embodiment according to the invention is illustrated in block form.

The storage device 10 is, for example, a magnetic core storage device with a capacity of 20 bits per word and 512 words, and stores point sequence data applied from the input line 11. For example, if the input data is a string of coordinate data obtained from a data tablet when drawing a character with a pen, the point sequence information of a line figure drawn with the pen, that is, a stroke, is stored sequentially, with the starting point at address O, the next point, and so on. The coordinates of the point are stored in a memory location starting from address 1 and increasing sequentially. As for the data tablet, for example, the one described in Patent Publication No. 4,3-7649 can be used. When a series of point sequence data to be approximated is stored in the storage device 10, a start signal is applied to the control device 50 from the signal line 14, and the approximation process is started.

As the start signal 14, the pen signal of the data tablet can be used, and the change from the lower 2 state when the pen is attached to the screen to the upper 2 state when the pen is removed from the screen can be used. When the approximation process is started, the control device 50 sends address information for specifying one point series to the storage device 10 from the signal line 51. According to this address information, the storage device 10 outputs the coordinates of the designated point to the signal line 12. At the same time, a control signal 53, which is a set of timing signals, is applied to the farthest point determining device 20. The farthest point determination device 20 is
Point information is taken in from the signal line 12 according to the series of control signals 53. The coordinates sent from the storage device 10 to the farthest point determination device 20 are both end points of the point series and the constituent points of the point series that are sent sequentially thereafter.

For each constituent point, the distance between the straight line determined by both end points of the point series and each constituent point is calculated in the farthest point determining device 20, and the maximum distance (actually equivalent to D) is calculated in the farthest point determination device 20. To simplify the device configuration, if the square of the maximum distance instead of the maximum distance is greater than the predetermined value D2, the farthest point determination device 20 will perform the following as explained in FIG.
Divide the initial point series into two point series, save both end points of one point series, and repeat the same process as before for the other point series. If the square of the maximum distance is smaller than D2, it is no longer necessary to divide this point series, so a signal is sent from the signal line 21 to the control device 50, and one of the point series read out into the control device 50 is divided. The address information of the two end points is stored in the corner storage device 90 via the signal line 54. As the corner storage device 90, a magnetic core storage device similar to the storage device 10 can be used, and its capacity may be about 64 words with 9 bits per word. The control device 50 checks whether there is still point series information to be processed, and if there is a point series, it repeats the approximation process, and if not, it stores the final point from the signal line 54 into the break point storage device 90. I will send it to you so that you can remember it,
An approximation processing paper completion signal is output to the signal line 52. When the approximation processing end signal 52 is output, the following information is stored in the corner storage device 90.
In the form of address information in the storage device 10, end points of broken lines that approximate the point series given to the storage device 10 are stored.

This breaking point information is output information of the broken line approximation device according to the present invention, and can be read and used by another information processing device. If the information processing device used has a suitable storage device, the corner storage device 90 may be omitted. Referring to FIG. 3, the farthest point determining device 20 shown in FIG.
The detailed configuration of is shown.

In order to control the operating order and timing of the farthest point determining device 20, timing signals t1-T, are applied from lines 531-539, respectively. Pi=(Xi, yi),
To control the approximation process for one point series with both endpoints Pj = (Xj, yj), Tl, t2, and t3 are each added once in this order, and then T4 to T7 are added multiple times in this order. times, that is, a number of times equal to the number of points making up this point sequence. Finally T8
, t, are added once to this order and the process ends. When timing signal T is applied, 10-bit signals representing the X and Y coordinates of point Pj (7) applied in parallel from input line 122 are stored in latch 22 and latch 23, respectively. Next, timing signal T2 is applied to line 532.
latches 24 and 25 in the same way.
In addition, Xi and yi added from line 121 are stored respectively. By the way, Pi=(Xi, yi), Pj-(
The equation of the straight line passing through Xj,yj) is (y-Yi)(X
j−Xi)−(x−Xi·)(Yj−Yi)=0.

Rearranging this, (Yi-Yj)x+(Xj-Xi)y
+(Xiyj−Xiyi)=0.

a=Yi-Yj, b=Xj-Xi, c=Xiyj-Xj
If we set yi, the equation of the straight line is Ax+By+c=
0, and the distance d between this straight line and point P(X, y) is.

It will be explained below that these calculations are sequentially performed in the farthest point determination device 20.

When timing signal T3 is applied to line 533, subtracter 2
6, b=XJ-Xi is obtained at the output 260 of the subtracter 27, a=Yi-Yj is obtained from the output 270 of the subtracter 27, XiyJ is obtained from the output 280 of the multiplier 28, and Xjyj is obtained from the output 290 of the multiplier 29. Each output information is held until it changes.

When timing signal T4 is applied to line 534, multiplier 3
By is output to the output 300 of 0, and A is output to the output 310 of the multiplier 31.
x, B2 to the output 320 of the multiplier 32, A2 to the output 330 of the multiplier 33, and c=X to the output 340 of the subtracter 34.
iyj−Xjyi are obtained, respectively.

When the timing signal T5 is applied to the line 535, the output 350 of the absolute value adder 35 outputs Ax+By+cl=1, and the output 360 of the adder 36 outputs A2+B2.

The l output 350 is set to an initial value of 0 in advance by the timing signal T.
The maximum register 37 that can be set to
It has been added to 8.

The other input to compare subtracter 38 is the output 370 of max register 37, which is compared when timing signal T6 is applied from line 536. When the value of the output 370 is expressed as LM, when LM<2, the output 380 of the comparison subtracter 38 is 1.
'', otherwise the output 380 will be ``0''.
Therefore, when timing signal T, is applied from line 537,
The output 380 of the comparison subtractor 38 is '1'', that is, LM<
A maximum point set pulse occurs at the output 211 of AND gate 39 only when 1, strobing the maximum register 37 and inputting the input from line 350! The value of is stored in the maximum register 37. The output maximum point set pulse 211 of the AND gate 39 is sent to the control device 5 as one of the control signals 21.
Also sent to 0. The sequence of timing signals T4 to T is
As the process is repeated, the process of determining the maximum value of 2 is repeated for a new (X, y) in the point series by fixing the three constants A, b, and c. Since the value of A2+B2 is constant, instead of finding the maximum value of the distance d between the straight line Ax+By+c=0 and each point P, a method of finding the maximum value of 2 is used. After completing this calculation for all points in the point series, timing signal T8 is applied from line 538,
The value of LM2 is output to the output 400 of the multiplier 40, and the multiplier 41 outputs the product D of the constant D2 preset in the constant unit 42 and (A2+B2) added from the output 360.
2(A2+B2) is output to output line 410.

The constant device 42 is actually a plurality of signal lines connected to give a certain set of 'O' or '1' in order to represent the numerical value of D2. When a timing signal T, is applied from line 539, the two inputs of compare-subtractor 43 are compared;
Only when MM2≦D2 (A2+B2), comparison subtractor 4
The ゜11 signal is output to the distance determination output 212 of No. 3, and when this is not the case, the ゜0'' signal is output.

This condition is equivalent to LM/A2+B2≦D, that is, DM≦D for the maximum distance DM between a straight line connecting both end points of a given point series and each point in the point series.

Referring to FIG. 4, the detailed configuration of the control device 50 shown in FIG.
0 is shown.

The series of timing signals t1 to T output by the control circuit 50 are generated using the start signal applied from the line 14 as a trigger. When the pen signal of the data tablet used as a start signal changes from 2 down to 2 up, a pulse signal is first generated by the monostable multivibrator 55, passes through the 0R gate 59, and passes through the delay circuit 551. Timing signal t1 is output to output line 531. t
1 signal delay circuits 552 and 553,
Timing signals T2 and T2 are applied to output lines 532 and 533, respectively.
t3 is output. The T3 signal resets a flip-flop (hereinafter abbreviated as FF) 57.

At this time, ``1'' is output to the output line 571 of the FF 57, and ``0'' is output to the output line 572, respectively. On the other hand, the T3 signal passes through the 0R gate 561, enters the delay circuit 554, and connects to the output line 53.
4 to output the timing signal T4. The T4 signal is sequentially delayed by delay circuits 555, 556, and 557, and outputs timing signals T5, t6, and t7 to output lines 535, 536, and 537, respectively. The T7 signal is sent to the delay circuit 55
8, it becomes a belief 567 and becomes an input to an AND gate 565 and another AND gate 562. , if FF5 and FF7 are in the set state, the AND gate 565 opens, so
Signal 567 passes through AND gate 565 and 0R gate 561, and is again applied to delay circuit 554.

Due to this loop, the timing signals T4 to T7 are repeatedly generated as long as the FF 57 is in the reset state. When the FF 57 is set by the signal from the signal line 580, the output line 571 becomes '02' and the output line 572 becomes '1'.

In this state, the output 567 of the delay circuit 558 is outputted as a timing signal T8 to the output line 538 via the AND gate 562, and then sequentially passes through delay circuits 559, 563, and 564, and is sent as the timing signal T8 to the signal lines 539, 569, and 5C6, respectively. ,,tlO,tl,.
Delay circuits 551 to 559, 563, and 564 each have 1
It has μs delay time and waveform shaping functions, and is realized by a combination of monostable multivibrators.
At the time when the start signal 14 is applied, as explained earlier with reference to FIG. 60 is reset to the empty state.

The stack 60 has a capacity of, for example, 64 words with 8 bits per word, and stores input information sequentially as write commands are added, but in response to read commands, it stores the last written word of information. It is a storage device in which the memory of the read information disappears as soon as the information is read out. However, even without adding a read command, the information to be read next can be detected from the outside. When there is no more information to be read in the stack as a result of adding a read command, an empty status indication is output. Such a stack can be easily constructed using shift registers or magnetic core storage. When the start signal 14 is applied to the stack control circuit 61, the address information of the start point and end point of the point series stored in the storage device 10 is written into the stack 60 in this order.

Timing signal t1 is applied to stack control path 61 as a read command, and the 1 word is read from stack 60 onto signal line 601.

This word is the address information of the final point of the point series to be evaluated, and is designated as Aj. In the initial state A
j is the address itself of the end point of the stroke. After execution of this readout command, the next readout candidate externally detectable in the stack 60 is the address of the starting point of the point sequence to be evaluated, and is labeled Ai. The address information AJ read out from the stack 60 onto the signal line 601 is set in the address counter 64 and the end point register 63 by the timing signal T, respectively. Timing signal t1 is stored in storage device 1
0 and is strobed by t1 and appears at the output 640 of the address counter 64.
The coordinate information Pj = (Xj, yj) of j is stored in parallel in the storage device 1.
0 output line 122. Next, the timing signal T2
is added to the storage device 10, and one word of the address Ai specified by the signal line 601, that is, the coordinate information Pi=(Xi,
yi) is read out to the output line 121. timing signal T4
When added to the storage device 10, the information at the specified address is read out from the address counter 64 via the signal line 640 and appears on the output line 123.

The coordinate information read out to the output lines 122, 121, and 123 was explained earlier with reference to FIG. 3 (Xj, y
j), (Xi, yi), (X, y).
The initial value of the address counter 64 was Aj, but when the pulse signal 567 generated by delaying the T7 signal is added, the content is subtracted by 1.

In this way, when the sequence of timing signals T4 to T7 is repeated, the timing signal T4 is
Each time information is read out, the content of the address counter 64 is decremented by 1 by the subsequent timing signal T7, and the coordinates in the address counter 64 are decremented by 1 starting from the end point of the target point series. The information will be read and added to the farthest point determining device 20. The contents of the address counter 64 are transferred to the comparator circuit 58 via a signal line 640.
This is one input.

The other input of the comparison circuit 58 is the output 601 of the stack 60, and when the two inputs of the comparison circuit 58 match, the signal line 5
A 1" signal is output to the stack 80. When the signal on the signal line 580 changes from SO" to S1", the FF 57 is set. The output 601 of the stack 60 contains the address of the starting point of the point series currently being processed. Since it is appearing, the address counter 6
The contents of 4 are subtracted by one from the end point address of the point series,
It changes up to the address of the starting point of the point series. When the maximum point set pulse 211 described above with reference to FIG. 3 is output during one period of the timing signals T4 to T7,
Farthest point address register 62 is strobed to accumulate output information 640 of address counter 64.

The farthest point address register 62 is updated every time the maximum point set pulse 211 is applied, and eventually stores the address information of the farthest point in the target point series. FF57 is set and the timing signal T8,t,,tlO,tl
The operation at the stage when 1 is generated differs depending on whether the distance determination output 212 described above with reference to FIG. 3 is 1'' or 0''.

First, when the distance determination output 212 is S1'', LM2
Since ≦D2 (A2+B2), there is no need to divide the point series that has just been examined. Furthermore, this point series has been processed and there is no need to check it later, and it is sufficient to record only the end point of this point series in the break point storage device 90. Therefore, when the distance determination output 212 is '1'', the corner point storage device 90 stores
When the timing signal TlO is applied, the output information 630 of the end point register 63 is stored, and in preparation for the next input,
The internally held write address is advanced by one address. When the distance judgment output 212 is 02, LM2>D2(
A2+B2), it is necessary to further divide the point series that has just been investigated.

Since the two point series created by the division need to be further investigated, they are written into the stack 60 while maintaining the order of the end points of the point series. For this purpose, when the distance judgment output 212 is 0I and the timing signal TlO is applied, the stack control circuit 61 writes the contents of the farthest point address register 62 to the stack 60, and then when the timing signal Tll is applied. If so, the contents of the end point register 63 are written to the stack 60. Therefore, the information that is read out the earliest in the stack 60 is the end point of the point series just examined, the farthest point at which this point series is divided, and the starting point of this point series that was previously in the stack 60. In order,
Each address will be stored in the form of address information. Timing signal T,l becomes one input of AND gate 595.

When the stack 60 is not empty, '0' is output on the signal line 602, which is inverted by the inverter 65 and becomes A.
It is added to ND gate 595. Therefore, at this time, the timing signals T and l pass through the AND gate 595, pass through the 0R gate 59, and become inputs to the delay circuit 551, and the operation process described above is restarted. At the time when the timing signal T, , appears, at least one word is stored in the stack 60, but when the last point sequence of one stroke has been processed, there is no longer one word in the stack 60. Only one word is graded. This one word is the address information of the starting point of the stroke. When the next timing signal t1 is generated in this state, it acts as a read command to the stack control circuit 61 as before and reads the last word from the stack 60, indicating an empty state on the signal line 602. A '1'' signal is output.

Empty signal 602 opens AND gate 66 and timing signal t1 appears as output 52. When the signal 52 is applied, the corner memory 90 writes the information at the output 601 of the stack 60, that is, the address of the starting point of the stroke. As a result, in the break point storage device 90, for a given stroke, the end point sequence of the break line approximation explained using FIG.
Each is stored in the form of an address of a corresponding point in the storage device 10. The signal 52 is used by an external information processing device as an approximation processing end signal.

In this embodiment, an independent break point storage device 90 is provided, but it can easily be omitted by recording the output break point information in the storage device.

Moreover, part or all of the apparatus of the present invention can be easily realized by firmware by referring to the operation process described in detail in this specification.

[Brief explanation of the drawing]

FIG. 1 is a diagram for explaining the method of line approximation, and includes an input figure a and a resultant line figure d. FIG. 2 is a block diagram showing one embodiment according to the present invention, which includes a storage device 10, a farthest point determination device 20, a control device 50, and a corner point storage device 90. FIG. 3 is a diagram showing a detailed configuration of the farthest point determination device 20 in FIG.
2, 33, 40, 41, and a maximum register 37. FIG. 4 is a diagram mainly showing the detailed configuration of the control device 50 in FIG.
64, stack 60, stack control circuit 61, farthest point address register 62, end point register 63, address counter 64
, a storage device 10, and a corner storage device 90.

Claims (1)

[Claims] 1. Stored in the storage device such that the distance between a storage device that stores point coordinates and a straight line defined by two specific points stored in the storage device with the output of the storage device as input is the maximum. a farthest point determination device that determines the farthest point determined by the device; and a farthest point determination device that is connected to the storage device and the farthest point determination device, specifies two points to be read from the storage device, and calculates the maximum distance calculated using those two points. , a control device for repeatedly operating the furthest point determination device by sequentially changing the two points until the two points become smaller than one predetermined reference value; and corner information output by the control device. 1. A broken line approximation device for accumulated point sequence data, comprising a breaking point storage device for accumulating.