JPH0786935B2 - Contour data compression method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION (Industrial field of application) The present invention relates to contour data by approximating a contour line formed by a plurality of contour points arranged on an image plane with a relatively small number of contour points. On how to compress.

(Prior Art) In image processing for creating a printing plate, a so-called cutout mask may be created in order to specify a desired graphic region in which images are combined.

The cutout mask is a film that is originally transparent only in the desired graphic region and opaque in the other parts,
It is used to photographically combine two images.

On the other hand, in an image processing apparatus such as a layout scanner, the cutout mask is configured as image data that expresses the contour of a desired graphic region with a plurality of contour points.

However, in general, when the contour of a figure is represented by a plurality of contour points, if the number of contour points becomes too large, the data amount of the contour data representing them becomes enormous. Therefore, as a method for compressing such contour data, the so-called polygonal line approximation method and the piecewise method described in "Basic techniques of image processing" (Hasegawa et al., Technical Review Co., Ltd.), pp. 80-81. A linear approximation method and the like are known.

(Problems to be Solved by the Invention) FIG. 11 is an explanatory diagram showing a procedure for approximating the contours represented by the contour points P _{n-1 to} P _{n + 6} by the polygonal line approximation method.

The polygonal line approximation method is a line segment that connects two points of a plurality of contour points.
L ₁ , L ₂ …, and the distances d ₁ , d ₂ …, to the other contour points between the respective 2 points are obtained, and the two points as far as possible such that the maximum distance is equal to or less than the threshold d _s1 are effective. It is a method of approximating a contour into a line segment by adopting it as a point.

In the example of FIG. 11, the distance d ₅ for the line segment L ₅
Since it becomes larger than _s1 , the end point P _{n + 4} of the line segment L ₄ in front of it is
Is adopted as an effective contour point. The contour point P _n-1 is an effective contour point fixed as a starting point. Therefore, point P
The data of contour points P _{n to} P _{n + 3} between _n-1 and P _{n + 4} are deleted. Of these, the contour point P _{n + 1} is a contour point located at a corner where the shape of the contour changes abruptly, but in the polygonal line approximation method,
Since the data of the contour points of such corners are deleted from the contour data, there is a problem that the corners cannot be accurately approximated.

FIG. 12 is an explanatory diagram showing a procedure for approximating the same contour points P _{n-1 to} P _{n + 6} as in FIG. 11 by the piecewise linear approximation method. In this method, first, a set of contour points P _n-1 and P _{n + 6 to be} subjected to approximation processing is
Is defined and the points P _n-1 and P _{n + 6} at both ends thereof are connected by a virtual line segment L ₆ . Then, the distance (maximum distance) d ₆ from the virtual line segment L ₆ to the furthest contour point P _{n + 1} is obtained. Then, when the maximum distance d ₆ is larger than the predetermined threshold value d _s2 , the contour point P _{n + 1} is regarded as valid. Then, next, virtual line segments are provided between the contour points P _n-1 and P _{n + 1} and between the points P _{n + 1} and P _{n + 6} , and effective contour points are obtained in the same procedure. Is the way. In this case, the threshold d
_{If s2 is set} to be sufficiently small, the contour point P _{n + 1} at the corner can be left as an effective point.

However, in the piecewise linear approximation method of FIG. 12, since virtual line segments are drawn from both ends of a set of contour points, the effective contour points may change depending on how the contour points are grouped. For example, if the contour points P _{n-1 to} P _{n + 3} are a set of contour points to be subjected to the approximation processing, then from the virtual line segment L ₃ connecting the points P _n-1 and P _{n + 3} at both ends thereof, The distance d ₃ to the farthest contour point P _{n + 1} is
It is smaller than the threshold value d _s2 . Therefore, at this time, the contour point P
_{n + 1} is not a valid point, and only the contour points P _n-1 and P _{n + 3 at} both ends are valid points. That is, when the contour line is approximated by the piecewise linear approximation method, there is a problem that the effective contour point changes depending on the way of dividing the contour points, and the approximate contour point approximated by the effective contour point also changes.

(Object of the Invention) The present invention is intended to solve the above-mentioned problems in the prior art, and it is possible to obtain compressed contour data capable of accurately approximating a corner portion of a contour line, and a contour point to be a target of approximation processing. It is an object of the present invention to provide a contour data compression method that can always obtain compressed contour data that represents the same approximate contour line, regardless of the number and the like.

(Means for Solving the Problems) In order to solve the above problems, in the present invention, an initial contour line formed by a plurality of contour points arranged in a predetermined order on an image plane is selected from the contour lines. A contour data compression method for compressing initial contour data representing the contour points to obtain compressed contour data representing the valid contour points by approximating the contour points by One is selected as a start contour point, the contour points arranged after the start contour point in the predetermined order are selected as the selected contour points in the predetermined order, and the following procedure is performed for each of the selected contour points. To execute.

(A-1) The start contour point and the selected contour point are connected by a line segment, and (a-2) the start contour line point and the selected contour point are arranged in the predetermined order. From each of the intermediate contour points that are contour points, the distance to the line segment is obtained, and the maximum distance that is the maximum value of the distance is obtained, and (a-3) when the maximum distance is smaller than a predetermined threshold value. Updates the selected contour points according to the predetermined order and repeats steps (a-1) and (a-2). On the other hand, (a-4) When the maximum distance is equal to or larger than the predetermined threshold value, the intermediate contour point that gives the maximum distance is determined as the effective contour point.

Then, (b) the starting contour point is updated using the effective contour point, and the (a) and (a-1) to (a-4) are updated.
The above steps are repeated and the compressed contour data is obtained based on the effective contour points.

The step (a-1) is indicated by (a-1a) a step of calculating an index value indicating the magnitude of the curvature of the initial contour line at the start contour point, and (a-1b) by the index value. And decreasing the predetermined threshold according to the increase in the curvature.

(Function) All of the plurality of contour points are selected contour points in a predetermined order,
Since the approximation processing is performed, the same contour point can always be determined as the effective contour point regardless of the number of contour points that are the target of the approximation processing.

Further, since the intermediate contour point that is separated from the line segment connecting the start contour point and the selected contour point by a predetermined threshold value or more is determined as the effective contour point, the contour points at the corners of the contour can be adopted as the effective contour point.

Further, if the predetermined threshold value is made to decrease as the curvature of the initial contour line increases, in a portion where the curvature is large,
It is possible to adopt many effective contour points.

(Embodiment) A. Schematic configuration and operation of apparatus FIG. 1 is a block diagram showing an image data processing system IPS for compressing contour data by applying an embodiment of the present invention. In the figure, image data processing system IPS
Includes an input device (for example, an input scanner) 1, an image processing device 2, and an output device (for example, an output scanner) 3. The image processing device 2 further includes a buffer memory 21, an arithmetic circuit 22 and a memory 23. In this embodiment, the image processing device 2 is configured as a cutout mask device for making a cutout mask, and is connected with a graphic display 4 and a mouse 5 for use in making the cutout mask.

B. Operation of the First Embodiment FIG. 2A is a flow chart showing the procedure of the first embodiment of the present invention.

In step S1, a predetermined original image is read by the input scanner 1 to obtain image data D ₀ . This image data D ₀ is given from the input scanner 1 to the image processing apparatus 2 and is sent to the buffer memory 21.
Stored in the memory 23 via.

In step S2, the image data D ₀ is given to the graphic display 4, and the original image is displayed. FIG. 3 is a conceptual diagram showing the image I ₀ displayed on the graphic display 4, and for simplification, only the initial contour line B of the figure is shown. This initial contour line B is a set of many contour points.

In step S3, the operator looks at this image I ₀ ,
Specify the starting contour point P ₀ . This designation is made, for example, by the operator moving the mouse 5 to align the cursor on the screen with the position of the starting contour point P ₀ in FIG.

In step S4, the next contour point P ₁ is similarly designated. The data indicating the positions of the designated contour points P ₀ and P ₁ are stored in the buffer memory 21 every time the designation is made.
Since the coordinate data of the start contour point P ₀ is used as a part of the compressed contour data, it is also stored in the memory 23.
At the time when the first two contour points P ₀ and P ₁ are designated, it is not necessary to approximate the contour line, so that data compression described later is not performed.

In step S5, the next contour point P ₂ is further designated.

After the three contour points P _{0 to} P ₂ are designated, the data compression processing (contour line approximation processing) in step S6 is executed. Second B
The figure is a flowchart showing the procedure of the contour line approximation processing in step S6. Further, FIG. 4A is an explanatory diagram showing the procedure of the approximation processing for the contour points P _{0 to} P ₂ designated up to this point.

In the approximation of the contour line, first, in step S61, one contour point designated after the start contour point P ₀ is selected in the designated order. However, the contour point P ₁ adjacent to the start contour point P ₀ is not selected. This is the starting contour point
This is because there is no other contour point between P ₀ and the contour point P _1, and an effective contour point as described later cannot be determined.

Note that the contour point P ₁ is actually selected as the selected contour point, and as a result, the effective contour point cannot be determined and the next contour point is determined.
P ₂ may be the selected contour point. That is, the procedure in which the contour point P ₁ is not the selected contour point is substantially equivalent to the procedure in which the contour point P ₁ is selected as the selected contour point. In step S62, a virtual line segment L ₀₂ is drawn between the selected contour point (hereinafter, simply referred to as “selected contour point”) P ₂ and the start contour point P ₀ .

Then, in step S63, the end points of the virtual line segment L ₀₂
A distance d ₂₁ from another contour point (hereinafter, referred to as “intermediate contour point”) P ₁ arranged between P ₀ and P ₂ to the virtual line segment L ₀₂ is calculated. At this time, when there are a plurality of intermediate contour points, the distance from each intermediate contour point to the virtual line segment is obtained.

FIG. 5 is an explanatory diagram showing a method of calculating the distance from the virtual line segment to the intermediate contour point. Here, in general, it is considered to find the distance d _ni from the virtual line segment L _0n connecting the two contour points P ₀ and P _n to the intermediate contour point P _i . It is assumed that the coordinates of the three contour points P ₀ , P _n , and P _i are given by (0, 0), (x _n , y _n ), and (x _i , y _i ), respectively.

The length l _0n virtual line L _0n is given ^{_{by: l 0n = (x n 2}} + y n 2) 1/2 ... (1) distance d _ni is the angle the contour point P _i in the clockwise θ Equal to the y coordinate value y _ia of the point P _ia rotated by. The distance d _ni is obtained by the following equation using a well-known coordinate transformation equation (affine transformation).

d _ni = y _ia = y _i cos θ−x _i sin θ = (x _n y _i −x _i y _n ) / l _0n (2) In step S64, when there are a plurality of intermediate contour points, the intermediate contour points are separated from the virtual line segment. The maximum value of the distance to ( _destination is called "maximum distance") d _max is calculated. In the case of FIG. 4A, since there is only one intermediate contour point (P ₁ ), d _max = d ₂₁ .

In step S65, the maximum distance d _max is compared with a predetermined threshold d _s . When the maximum distance d _max is smaller than the threshold d _s as in the case of the 4A, step S66 is executed, and this step will be described later.

On the other hand, when the maximum distance d _max is greater than or _equal to the threshold d _s , the step
In S67, the intermediate contour point that gives the maximum distance d _max is adopted as the effective contour point. Such a case will be described with reference to FIG. 4B. When the contour points P _{0 to} P ₅ are designated, the distance of each intermediate contour point from the virtual line segments L ₀₃ and L ₀₄ is smaller than the threshold value d _s . Therefore, next, a virtual line segment L ₀₅ is drawn between the start contour point P ₀ and the last designated contour point P ₅ . At this time, the distance d ₅₂ between the intermediate contour point P ₂ and the virtual line segment L ₀₅ is the maximum distance d _max . The maximum distance d _max = d ₅₂ is larger than the threshold d _s . Therefore, step S67 is executed and the intermediate contour point P ₂ is set as the effective contour point.

Then, in step S68, the coordinate data of the effective contour point P ₂ is stored in the memory 23 as a part of the compressed contour data. After the effective contour point P ₂ is obtained, the coordinate data of the contour points P ₀ and P ₁ arranged before that are not necessary for the data compression processing, and are deleted from the buffer memory 21. As described above, since it is not necessary to store the data of the contour points before the new effective contour point in the buffer memory 21, even when processing a large number of contour points as a whole, the buffer memory 21 and the memory 23 Need only have a relatively small storage capacity. The first start contour point P ₀
The coordinate data of is stored in the memory 23 in advance and is used as a part of the compressed contour data as described above. It should be noted that the term "effective contour point" means the meaning including the first start contour point.

In step S70, the effective contour point P ₂ selected in step S67
Is regarded as a new starting contour point.

After step S70, the based on the new starting contour point P _2,
Step S61 and subsequent steps are executed. That is, first, the contour point P
₄ is selected in step S61, and the virtual line segment L is selected in step S62.
₂₄ is drawn. The distance between the virtual line segment L ₂₄ and the intermediate contour point P ₃ is clearly smaller than the threshold value d _s , as can be seen from FIG. 4B. Therefore, step S66 is executed according to the determination in step S655.

In step S66, it is determined whether or not there remains a contour point to be the selected contour point. In the case of FIG. 4B, the contour points
P ₅ can be the selected contour point. Therefore, the process returns to step S61, the contour point P ₅ is selected as the selected contour point, and step S62
The subsequent steps are executed.

If it is determined in step S66 that no contour point to be the selected contour point remains, step S7 of FIG. 2A is executed.

In step S7, the operator determines whether or not to end the process, and when the process is ended, the operator inputs data to that effect using a keyboard or the like not shown. The process is completed at a point P _f (see FIG. 3) sufficiently close to the first starting contour point P ₀ .
It is usually performed after executing steps S5 and S6. On the other hand, if the processing is to be continued, the process returns to step S5 to specify the next contour point.

By repeating steps S1 to S7 as described above,
The coordinate data of the contour points P ₀ , P ₂ , ... Which are adopted as the effective contour points are stored in the memory 23 and remain. FIG. 4C is a conceptual diagram showing a part of the contour line B _S approximated by these effective contour points P ₀ , P ₂ , ... Thus, the effective contour points P ₀ , P ₂ , ...
In the contour line B _s approximated by, the contour points P ₂ and P _{6 at} the corners of the original contour line are left as valid points, and the shape of the corners is accurately approximated. Note that other contour points in the figure
The coordinate data of P ₁ , P ₃ , P ₄ , P ₅ , and P ₇ are not included in the compressed contour data, but are shown for reference.

Comparing the initial contour data representing the coordinates of all the specified contour points P ₀ , P ₁ , P ₂ , ... With the compressed contour data representing the coordinates of only the valid contour points P ₀ , P ₂ ,. Since the data amount of the compressed contour data is much smaller than that of the initial contour data, it can be understood that the data is substantially compressed in step S6.

In this embodiment, the image processing device 2 is constructed as a cutout mask device. Therefore, the compressed contour data finally obtained as described above is given to the output scanner 3 from the image processing device 2 as, for example, cutout mask data D _m , and is used for producing a halftone film serving as a cutout mask. It Of course, it goes without saying that the present invention is not limited to the production of a cutout mask, and can generally be applied to the case where the contour needs to be approximated.

C. Operation of Second Embodiment FIG. 6 is an explanatory diagram showing the concept of the second embodiment of the present invention. In the figure, points BP _i-1 and BP _i (= P _n ) indicate contour points that have already been made effective contour points. On the other hand, the contour points P _{n + 1} , P
_{n + 2} indicates a contour point that is specified after that and is to undergo approximation processing.

In this embodiment, the last two effective contour points at the present time
An angle formed by a line segment connecting BP _i-1 and BP _i (hereinafter, referred to as “preceding contour line segment”) L _Bi and a virtual line segment L connecting between the contour points P _n and P _{n + 2} Find φ. Then, the threshold d _s for the maximum distance d _{max is} a function according to the value of the angle φ: d _s = f (φ) (3) FIG. 7 is a diagram showing an example of the function f (φ). is there. In this example, the function f (φ) is a step-up function in which the maximum distance threshold d _s decreases for each of the plurality of angle thresholds φ _{1 to} φ ₄ . In this way, if the threshold d _s is made smaller as the angle φ is larger, when the contour line is curved with a large curvature, it is approximated by a relatively large number of effective contour points, and the shape of the contour line is Has the advantage that it can be approximated more faithfully.

The second embodiment is the same as the first embodiment except that the threshold value d _s is changed according to the angle φ, and the procedure is the same as that shown in FIGS. 2A and 2B.

FIGS. 8A and 8B are conceptual diagrams showing the results of approximation of the initial contour line B ₁ by the first and second embodiments, respectively.
In these figures, approximated contour lines (hereinafter referred to as “approximated contour lines”) L _B1 , L _B2, ... Are indicated by alternate long and short dash lines. In the portion having a small curvature (the portion having a large radius of curvature) in the initial contour line B ₁ , the first embodiment (FIG. 8A) and the second embodiment (FIG. 8B) are used.
Then, the same approximate contour lines L _{B1 to} L _B5 are obtained in both cases.
On the other hand, in the portion having a large curvature (the portion having a small radius of curvature) of the initial contour line B ₁ , the second embodiment (rather than the approximate contour lines L _{B6 to} L _{B8 of} the first embodiment (FIG. 8A)) The number of approximate contours L _{B6a to} L _B9a in FIG. 8B) is larger. From these figures, it can be understood that the shape of the contour line can be more faithfully approximated in the portion having the larger curvature in the second embodiment.

At the start of the approximation process of the second embodiment, and when a valid contour point is not obtained at the first start contour point, the angle φ cannot be defined because there is no preceding contour line segment. Therefore, a threshold value d _s having a constant value is used at the start of such an approximation process.

However, as shown in FIG. 9, the contour point P ₁ arranged next to the first start contour point P ₀ may always be regarded as an effective contour point. In this way, the contour points P ₂ , P
₃ is the preceding contour line segment L _B1 connected between the contour points P ₀ and P _1.
The threshold value d _s (= f
(Φ)) is determined, and it is determined whether or not it is an effective contour point. With this processing, the threshold value is always based on the angle φ.
It is possible to change the value of d _s .

Further, the distance between the contour points P ₀ and P ₁ may be several tens of μm, which means that the effective contour point P ₁ is increased by 1 as compared with the case where the processing of FIG. 9 is not performed. This increase is negligible compared to the number of valid contour points.

In the second embodiment described above, the function f (φ) that determines the value of the threshold value d _s is a step function, but of course it may be a continuous function with respect to the angle φ. However, the function f (φ) at that time is also a function that monotonically decreases as the angle φ increases. The angle φ is an index value indicating the magnitude of curvature of the initial contour line B ₁ , and the larger the angle φ, the greater the curvature. That is, in the second embodiment, the value of the threshold value d _s may be set so as to decrease as the curvature of the initial contour line increases. However, the term “decrease” as used herein is a term that includes the case where the threshold value d _s takes a constant value in a range of a certain angle φ (that is, a range of a certain curvature) as shown in FIG. 7.

D. Modifications The present invention is not limited to the above embodiments, and the following modifications are possible, for example.

The initial contour data is not limited to being given to the buffer memory 21 one by one each time one contour point is designated by the operator. For example, initial contour data representing a large number of contour points is stored in advance in some storage means (for example, the memory 23).
Alternatively, only the data representing some of the contour points may be sequentially transferred to the buffer memory 21, and the data compression in step S6 may be performed.

The approximation process may be performed according to the procedure shown in FIG. 10 instead of the procedure shown in FIG. 2B. In this procedure, step S71 is inserted between steps S65 and S66 in FIG. 2B. According to this procedure, the maximum distance d _max is the threshold d _s.
If the length l of the virtual line segment at that time is longer than the predetermined allowable value l _s , the intermediate contour point that gives the maximum distance at that time is set as the effective contour point and a new start contour point is set. It is what

By processing in this way, contour points in an excessively long range are not approximated by one straight line, and the contour line can be approximated more accurately. Further, the amount of data stored in the buffer memory 21 is small, and the storage capacity can be reduced. Furthermore, since the number of intermediate contour points for which the distance should be calculated from one virtual line segment does not increase excessively, the calculation time for data compression can be shortened.

(Effect of the Invention) As described above, according to the present invention, the approximation processing is performed while selecting all of the plurality of contour points as the selected contour points in a predetermined order. The same contour point can always be determined as an effective contour point regardless of the number and range of points, and compressed contour data representing the same approximate contour line can always be obtained.

Further, since an intermediate contour point that is separated from the line segment connecting the start contour point and the selected contour point by a predetermined threshold value or more is determined as the effective contour point, the contour points at the corners of the contour can be adopted as the effective point, and the contour line There is an effect that it is possible to obtain compressed contour data that can accurately approximate the angle of.

Furthermore, if the predetermined threshold value is decreased in accordance with the increase in the curvature of the initial contour line, many effective contour points can be adopted in the portion having a large curvature, and thus the effect that the initial contour line can be approximated more accurately There is.

[Brief description of drawings]

FIG. 1 is a block diagram showing a configuration of an apparatus to which an embodiment of the present invention is applied, FIGS. 2A and 2B are flow charts showing procedures of the embodiment, and FIG. 3 is an image displayed on a graphic display. 4A, 4B, and 4C are explanatory diagrams showing the procedure of the approximation processing in the embodiment, and FIG. 5 is an explanation showing the method of calculating the distance between the virtual line segment and the intermediate contour point. FIG. 6, FIG. 6 and FIG. 9 are explanatory diagrams showing a method of calculating the angle φ in the embodiment, FIG. 7 is a diagram showing a function for determining the threshold value of the maximum distance, and FIGS. 8A and 8B are FIG. 10 is a conceptual diagram showing a result of approximation processing according to the embodiment, FIG. 10 is a flowchart showing another procedure in the embodiment, and FIGS. 11 and 12 are explanatory diagrams showing a conventional contour approximation method. 2 ...... image processing apparatus, the virtual B, B ₁ ...... initial contour line, P ₀ to P ₇ ...... contour points, L _02, L ₀₅ ...... imaginary segment from d _21, d ₅₂ ...... intermediate contour point Distance to line segment, d _max …… maximum distance, d _s …… threshold

Claims (2)

[Claims] 1. A contour point is represented by approximating an initial contour line formed by a plurality of contour points arranged in a predetermined order on an image plane with an effective contour point selected from the contour lines. A contour data compression method for compressing initial contour data to obtain compressed contour data representing the effective contour point, comprising: (a) selecting one of the contour points as a starting contour point, and performing the predetermined order. In the above, the contour points arranged after the start contour point are selected as the selected contour points in the predetermined order, and (a-1) the start contour point and the selected contour point are selected for each of the selected contour points. (A-2) Distance from each of the intermediate contour points which are the contour points arranged between the start contour point and the selected contour point in the predetermined order to the line segment And the distance The maximum distance, which is the maximum value of the separation, is obtained. (A-3) When the maximum distance is smaller than a predetermined threshold value, the selected contour point is updated in accordance with the predetermined order to obtain the (a-1). (A-2) is repeated, (a-4) when the maximum distance is equal to or greater than the predetermined threshold value, the intermediate contour point that gives the maximum distance is determined as the effective contour point, and (b) The starting contour point is updated using the valid contour point, and the steps (a) and (a-1) to (a-4) are repeated, and the compressed contour data is obtained based on the valid contour point. A method for compressing contour data, which is characterized by being obtained. 2. The step (a-1) according to claim 1, wherein (a-la) a step of calculating an index value indicating a magnitude of curvature of the initial contour line at the start contour point; -1b) Decreasing the predetermined threshold value according to the increase in the curvature indicated by the index value, the contour data compressing method.