JP3011733B2 - How to determine the contour of a picture - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Industrial Application Field] The present invention relates to a method for determining a contour of a picture, and more particularly, to a contour suitable for determining a contour of a picture when performing a process of clipping a picture from an image. It relates to a line determination method.

[Conventional technology]

When making a plate making film from a photo or other manuscript,
It is necessary to cut out only the necessary picture portions in the original image and remove unnecessary background portions. As a method of performing such image clipping processing, a method of image processing using a layout scanner or the like is known. In this clipping method, first, an image of a document is input as digital data by a layout scanner, and this is displayed on a monitor. Then, the contour position of the picture in the display image is designated using a pointing device such as a mouse or a light pen, and the contour of the picture is determined based on the coordinate data input by the pointing device. Finally, a clipping process is performed on the input image using the contour data, and the cutout image is output to a film by a layout scanner.

[Problems to be solved by the invention]

However, in the outline determination method performed in the above-described conventional image clipping process, the position of a plurality of points on the outline is determined by an operator using a pointing device.
It is necessary to specify each point. Therefore, there is a problem that the operation of the pointing device becomes complicated and the work efficiency is low.

Accordingly, an object of the present invention is to provide a method for determining a contour line of a picture that allows a computer to automatically predict the position of a point on the contour line and automatically determine the contour line without designating a point by an operator. I do.

[Means for solving the problem]

According to the present invention, in a method for determining an outline of a picture included in an image composed of a set of pixels having a predetermined pixel value, a first point and a second point on the outline are input as initial points. A step of determining a predetermined pixel on an extension of the line segment connecting the two initial points to the second point side as a starting pixel; and a step of determining a contour of each of a plurality of peripheral pixels existing around the starting pixel. Calculating a contour function value indicating a degree of property as a pixel on the line; obtaining a line segment connecting a certain surrounding pixel with the second point; The calculation of the average of the obtained contour function values is performed for all or some of the surrounding pixels, and a third point to be connected to the above-mentioned initial point on the contour is determined based on the average obtained for each surrounding pixel. Stage , And.

(Operation)

In the method for determining a contour line of a picture according to the present invention, when two points on the contour line are input, a prediction calculation is performed for a position of a third point that should follow the two points. That is, first, a starting point is obtained on an extended line of a line connecting two input points, an optimum pixel is selected from a plurality of pixels existing around the starting point, and the position of the optimum pixel is predicted for a third point. An operation to determine the position is performed. Since the optimal pixel is determined based on the contour function value, the optimal third point position along the original contour can be predicted. Since such a prediction operation is performed,
The position of a point on the contour is automatically predicted by a computer, and the contour can be automatically determined without designating a point by an operator, thereby greatly improving work efficiency.

〔Example〕

Hereinafter, the present invention will be described based on the illustrated embodiments.
Here, an image layout apparatus capable of performing an image clipping process using the picture contour line determining method according to the present invention will be described as an embodiment.

Overall Configuration of Apparatus FIG. 1 is a block diagram showing a basic configuration of an image layout apparatus according to this embodiment. The scanner device 1 has an input drum 1A and an output drum 1B. By setting a document 2 on the input drum 1A, an image of the document 2 is taken into the control device 3. A plotting machine 4 is connected to the control device 3, on which the layout sheet 5 is set.
The control device 3 further includes a display device 6, an input device 7,
The memory 8 is connected. The control device 3 is configured by a computer, and has a function of integrally controlling each connected device and a function of laying out images.

An image layout operation by this apparatus will be briefly described with reference to the flowchart of FIG. First, in step S1, allocation data is input. This is an operation of setting the layout sheet 5 on the drawing machine 4 and inputting layout data. The plotter 4 constitutes a digitizer, and by tracing the layout graphic on the layout board 5 with the pointing device 4A, it is possible to input layout data including information on the shape and position of the layout graphic. The plotter 4 is provided with a command instructing unit 4B, and can input various commands necessary for this input operation.

Subsequently, in step S2, an original is input. This is an operation of inputting an image from the original 2 by the input drum 1A. The original 2 is set on the input drum 1A at a predetermined angle and scanned, and the image is captured as digital data at a predetermined magnification. . This image data is stored in the memory 8
Is stored in

When image input has been completed for all originals, an image positioning operation is performed in step S3. That is, the layout graphic in the layout data input in step S1 and the image input in step S2 are displayed on the display device 6, and the two are aligned. At this time, scaling processing and rotation processing are added to the image data as necessary.

When the positioning for all the images is completed in this way, the image clipping process is performed in step S4. This work is to define the outline of the picture included in the image whose positioning has been completed, and to extract only the inside or outside of this outline. The present invention is to improve the work efficiency of this cutting work by a novel method, and the process of step S4 is a process which is a feature of the present invention. Therefore, the processing in step S4 will be described later in detail.

When the clipping operation for all the images is completed, a layout calculation process is performed in step S5. This is an arithmetic process executed in the control device 3. The portion surrounded by the layout graphic positioned in step S3 is extracted from the document image input in step S2, and the extracted portion is designated by the layout sheet 5. This is the process of arranging them at the exact positions. In the case where the clipping process is performed in step S4, only the portion of the picture clipped along the contour is arranged. The image data after such a layout calculation process is stored in the memory 8.

Finally, in step S6, an image is output. This is a process of outputting the image after the layout calculation process from the output drum 1B to a film. In this manner, the layout work for arranging a desired pattern in a desired document image at a desired position is completed.

Image clipping processing Then, the image clipping processing (second
Step S4) will be described. In this processing, the display device 6
A screen as shown in FIG. 3 is displayed. This screen is
It is divided into an image display section 61 and a command display section 62. The image display section 61 displays an image including a picture to be cut out, and the command display section 62 displays various commands for performing the cut-out processing. In this example,
A pointing device such as a mouse is prepared as the input device 7, and any one point in the image display unit 61 can be designated, and any command displayed on the command display unit 62 can be selected and instructed. it can.

Now, the essential meaning of the clipping process will be described. Now, it is assumed that the picture Z is displayed on the image display section 61 as shown in FIG. In the figure, the inside of the pattern Z is hatched. In such a pattern Z, the position of the outline Zc is not necessarily recognized as data. As described above, the image data is raster data obtained by scanning the input drum 1A. In other words, it is represented as a set of a large number of pixels having a predetermined pixel value. Therefore, on the data:
The contour line Zc is not recognized. The clipping process performed here specifies pixels existing on the contour Zc, causes the contour Zc to be recognized as data, divides a large number of pixels into two groups with the contour Zc as a boundary, and assigns pixels belonging to one group. It is nothing but a process of extracting only. Conventionally, such cutout processing is performed by an operator designating points on the contour Zc at predetermined intervals while looking at the screen of the display device 6. For example, as shown in FIG. 4 (b), when points P1 to P6 on the contour Zc are designated on the image display unit 61, the contour Zc is determined by a line connecting these designated points. You. The designated point can be input by moving the cursor Cu on the screen with a mouse and pressing the mouse button when the cursor Cu is located at a desired position, thereby inputting that position as the designated point. Thus, sequentially the contour
By inputting points P1, P2,... On Zc as designated points, the contour line Zc is determined. However, the line segment connecting the designated points P1, P2,... Does not exactly match the outline Zc strictly. Therefore, the operator performs the designated point input at intervals at which the accuracy required for the cutting is sufficiently obtained.

Here, FIG. 3 is referred to again. Command A (in-vivo mask) and command B displayed in command area 62
(External mask) is a command for performing the above-described conventional clipping processing. When these command modes are selected, the designated points P1, P2, P3,
... can be sequentially input by a mouse. Thus, when a closed area is formed by many designated points,
In the command A mode, the inside of the closed area is extracted as a picture, and in the command B mode, the outside of the closed area is extracted as a picture. To delete a designated point that has been input once, a command C (designated point deletion) is input. As a result, the last input 1
The specified point is deleted. Command D (mask erase)
Is a command for erasing the specified closed area.

A feature of the apparatus of the present invention is that a mode of a command E (automatic cutout) and a mode of a command F (option) are further added. When the mode of the command E is selected, the input operation of the designated point becomes very efficient. As shown in FIG. 4 (b), the conventional method (operation in the mode of command A or B)
Then, the operator looks at the image
We have to move the Cu to the appropriate position on the contour line Zc and continue to press the mouse button. In the operation in the mode of the command E, the operation of moving the cursor Cu is greatly reduced. That is, when the input of a certain designated point is completed, the cursor is moved to an optimal position as the next designated point.
Cu moves automatically. This operation will be specifically described with reference to FIG.

Now, as shown in FIG. 5 (a), two designated points P1, P
It is assumed that up to 2 has been entered. In the mode of the command E, when the second designated point P2 is input, the control device 3 performs an operation for predicting the position of the third designated point P3, and automatically moves the cursor Cu to this predicted position. Fig. 5 (a)
Shows a state after the cursor Cu has moved from the position of the designated point P2 to the position of the prediction point. The operator determines whether the position of this prediction (that is, the position after the movement of the cursor Cu) is appropriate, and if so, presses the mouse button as it is and changes the current cursor position. The position is determined as the position of the third designated point P3. FIG. 5 (b) shows a state immediately after this. Third designated point
P3 is determined, and the cursor Cu is automatically moved to the position of the prediction point for the fourth designated point P4. If the operator subsequently presses the mouse button, the cursor position is determined as the designated point P4, and the cursor is automatically moved to the position of the predicted point for the fifth designated point P5. When the operator determines that the position of the prediction point is inappropriate, the position of the cursor Cu may be corrected to an appropriate position with a mouse, and the corrected position may be determined as a designated point by pressing a mouse button. .

As described above, in the mode of the command E, if two designated points P1 and P2 are input first, the designated point after the third designated point P3 is moved to the predicted point by the cursor Cu in advance. The input work becomes very easy. The predicted point is always at the appropriate position (the contour line connected to the last fixed point specified)
(Position on Zc), the operator can input each designated point after the third designated point P3 only by continuing to press and hold the mouse button. Also, even if the predicted point deviates from the contour line Zc, the operator can correct this to a position on the contour line Zc and input it as the next designated point by operating the mouse. Work can be performed. If necessary, by inputting the above-described command C, an operation of deleting the designated point once inputted can be performed. The command F (option) is a command for setting a parameter used in the calculation for obtaining the prediction point in the mode of the command E described above, and this parameter will be described later each time. When the cutout processing is completed, the operation is terminated by inputting the command G (operation end).

Next, the processing of the control device 3 in the mode of the command E, which is a feature of the present invention, will be described with reference to the flowchart of FIG. First, in step S11, a first point is input. That is, the first designated point P1 is input. Subsequently, in step S12, a second point is input. That is, the second designated point P2 is input. The feature of the present invention resides in that the position of the third designated point is predicted based on the two designated points that have already been determined in this way (this will be referred to as two initial points). Therefore, in step S13, the variable i is set to the initial value 2. The variable i indicates the number of the last specified point, and i = 2 indicates that up to the specified point P2 has been determined. In the following step S14, the (i + 1) -th point is predicted based on the (i-1) -th point and the i-th point.
That is, the position of the third designated point is predicted based on the two initial points. When i = 2, the first point P1 and the second point P1
Based on the point P2, the position of the third point P3 is predicted. Then, in step S15, a prediction point is displayed. In the example shown in FIG. 5 (a), the predicted point is indicated by the cursor Cu. Next step S1
In 6, the (i + 1) -th point is input. If i = 2, a third point is input. This input is performed using the city of the prediction point. That is, if it is determined that the position of the predicted point can be directly used as the position of the third point P3, the operator presses the mouse button as it is, and if it is determined that the position needs to be corrected,
The operator corrects the cursor position with the mouse and then presses the mouse button. In any case, the position of the third point P3 is determined at this stage. Next step S17
Then, i is updated. That is, i is increased by 1 and i = 3. Further, in step S18, it is determined whether or not to end the operation, and if the operation is to be continued, the procedure from step S14 is repeated again. This time, since i = 3, the second point P2 and the third point P3 are used as two initial points, and the position prediction of the fourth point P4 is performed. In step S15, a predicted point for the fourth point P4 is displayed, and in step S16, the position of the fourth point P4 is determined. The feature of the present invention is that, based on the two initial points of the (i−1) -th point and the i-th point, the (i +
1) The point is to perform the prediction. This step S1
A specific example of the prediction processing performed in 4 will be described in detail below.

Contour Prediction Processing In the above-described cutout processing, when a plurality of designated points P1, P2, P3,... Are input on the contour, if the designated points P1 and P2 are input as initial points, the designated point P3 From then on, it was stated that an operation for automatically predicting the position was possible. Here, an example of a specific method for predicting a third point based on two initial points will be described.

FIG. 7 is a flowchart showing the procedure of the prediction process. Now, this procedure will be described with reference to a specific example as shown in FIG. In FIG. 8, it is assumed that the contour line Zc is formed as shown in the figure. As described above, the contour Zc itself is not given as data, but is stored in the area Z1.
Is to be recognized as the boundary between and Z2. Provided as data are a pixel value for each pixel in the area Z1 and a pixel value for each pixel in the area Z2. Since there is a large difference between the pixel value of the pixel in the area Z1 and the pixel value of the pixel in the area Z2, the operator can visually recognize the outline Zc.

Here, a procedure for predicting the position of the third designated point Pi + 1 in a state where the first designated point Pi-1 and the second designated point Pi are fixed on the contour Zc will be described. This procedure consists of three steps as shown in the flowchart of FIG. That is, the starting pixel determination processing in step S21,
This is the outline function value calculation processing for the surrounding pixels in 22 and the optimum pixel determination processing in step S23. Hereinafter, each of these processes will be described in order.

(1) Determination of Origin Pixel In the above description, a description has been given of a case where a designated point is treated as a point. However, actually, the designated point corresponds to a pixel. For example, in FIG.
-1 or the designated point Pi corresponds to a pixel drawn as a square around this point (however, in FIG. 8, one pixel is drawn considerably enlarged for convenience of explanation). Since the contour line Zc in the strict sense is defined as a boundary between pixels, the size of one pixel when a smooth boundary line Zc as shown in FIG. Must be something). Therefore, in the following description, the designated point is expressed as Pi-1 and Pi, and the corresponding pixels are expressed as the pixels Pi-1 and Pi using the same reference numerals.

In FIG. 8, the starting point Pi + 1 'is first determined. The starting point Pi + 1 'is a point on an extension of the line connecting the first designated point Pi-1 and the second designated point Pi to the second designated point Pi side, and is a point from the second designated point Pi. It is determined as a point at the position of the distance di + 1 '. The distance di + 1 'is a parameter for determining an approximate distance between the prediction point as the third designated point Pi + 1 and the second designated point Pi. This distance di
+1 'may be set to a predetermined constant,
Can be set based on the distance di between the designated point Pi-1 and the second designated point Pi. For example, if di + 1 '= di is set, prediction is performed such that the designated points are arranged at substantially equal intervals, and di + 1' = 2d
If it is set to i, prediction will be made such that the designated point is arranged at a position where the interval gradually increases.
In this way, if the distance di + 1 'is set as a parameter, the starting point Pi + 1' is uniquely determined based on the first designated point Pi-1 and the second designated point Pi. The parameter Pi + 1 'is one of the parameters that can be set by the command E described in FIG. In addition, this starting point
A pixel having Pi + 1 'as a center point (shown by an enlarged square in FIG. 8) is referred to as a starting pixel Pi + 1' using the same reference numerals. The starting pixel determination processing in step S21 is processing for determining the starting pixel Pi + 1 'in this manner.

(2) Contour function value calculation for surrounding pixels If the contour line Zc is close to a straight line, the origin pixel Pi + 1 'is almost on the contour line. Therefore, the origin pixel Pi + 1' is used as a pixel for predicting the position of the third designated point Pi + 1. Can be used as it is. However, the contour line Zc is not always a straight line. In the example of FIG. 8, since the contour line Zc is curved, an optimal pixel as a pixel for predicting the position of the third designated point Pi + 1 is a hatched pixel in the figure. The preparation stage for determining such an optimal pixel is the contour function value calculation processing in step S22. Here, the outline function value is, in short, a value indicating the degree of the property as a pixel on the outline, and the starting point pixel Pi +
The processing of step S22 is to obtain the contour function value for each of the surrounding pixels existing around 1 '.
In the following step S23, an optimum pixel is determined based on each contour function value.

Now, let's give a theoretical explanation of this contour function value. Now, consider a pattern as shown in FIG. It is divided into two regions Z1 and Z2 by the contour line Zc. Here, a cut plane T (a plane standing perpendicular to the paper surface at the position of the dashed line in the figure) is formed in a direction perpendicular to the contour line Zc, and changes in pixel values on the cut plane T are examined. . In FIG. 10, the horizontal axis represents the horizontal position t on the cutting plane T, and the vertical axis represents the pixel value Q of the pixel existing at that position.
It is a graph which took (t). The pixel value Q (t) changes greatly around the contour line Zc. That is, in the graph of FIG. 10, the left half shows the pixel values of the pixels in the area Z1, and the right half shows the pixel values of the pixels in the area Z2. Here, based on the pixel value Q (t), a pixel value function f (t) as shown in FIG. 11 is obtained by the following equation (1).

f (t) = Q (t) -M (1) Here, M is the average value of the pixel value Q (t) in a predetermined section (for example, in the section shown on the horizontal axis in FIG. 10). It is. The pixel value function f (t) thus obtained is
As shown in FIG. 11, the function takes both positive and negative values around the value 0.

Now, subsequently, a contour model function fm as shown in FIG.
Let's define (t). This function is defined as fm (t) = (2u (t) -1) (2), and the function u (t) is expressed as u (t) = 1 (t ≧ 0) (3) u (t) = It is a step function defined as 0 (t <0). This contour model function fm (t) corresponds to the ultimate value of the pixel value function f (t) obtained when the contour Zc is considered as the most ideal contour. Next, a window function w (t) as shown in FIG. 13 is defined. This function is defined as, for example, w (t) = exp (−a | t |) (4). Then, the contour model function fm (t) defined by equation (2) and the window function w defined by equation (4)
As a product of (t), a contour extraction function g such as
(T) is defined.

g (t) = fm (t) .w (t) (5) The contour extraction function g (t) is a function as shown in FIG.

Here, attention is again paid to the pixel value function f (t) shown in FIG. The function f (t) is a function that can calculate an actual value for an image input as data. For example, if an image as shown in FIG. 9 is given as data, a pixel value Q (t) is obtained by defining a cut plane T, and a pixel value function f (t) is calculated from this. Is done. On the other hand, the contour extraction function g
(T) is a function that can be defined by appropriately setting the coefficient a in equation (4). Now, a predefined contour extraction function g (t) is superimposed on a pixel value function f (t) obtained from actual data. Contour extraction function g
FIG. 15 shows a state where the origin O of (t) is overlapped with the position of the point t1 on the horizontal axis of the pixel value function f (t), and FIG. 16 shows a state where it is overlapped with the position of the point t0. Show. In each of the graphs, the contour line extraction function g (t) is indicated by a broken line. Here, considering the degree of approximation of the superimposed functions, it can be said that the degree of approximation is larger in FIG. 16 than in FIG. That is, when the origin O is superimposed on the point t1, the function f (t) and the function g (t) are not very similar, but the origin O is
When overlaid on t0, both functions are fairly similar. A function defined as a function indicating the degree of this approximation is the contour function h (t). FIG. 17 shows this contour function h (t).
An example is shown below. The function value h (t0) at the position t0 has a peak value because the origin O of the function g (t) is
Both functions are most similar when they are superimposed on the point t0 of (t) (the state of FIG. 16). Although the value of the function value h (t1) at the position t1 is considerably low, this is because the origin O of the function g (t) is
This shows that the degree of approximation of both functions is reduced when they are overlaid on the point t1 of (t) (the state of FIG. 15). A contour function h (t) indicating the degree of such approximation
May be defined as:

Eventually, this contour function h (t) becomes the contour extraction function g
With the origin O of (t) superimposed on the position t on the horizontal axis of the pixel value function f (t), it is defined as a correlation function obtained by integrating the product of both functions. For example, the contour function value h (t1) at t = t1, as shown in FIG.
The origin O of (t) is defined as the position on the horizontal axis of the pixel value function f (t).
A value obtained by integrating the product of the two functions obtained in a state of being superimposed on t1 over the entire range (−∞ to ∞) of t.

As described above, the contour function h (t) indicates the correlation between the pixel value function f (t) and the contour extraction function g (t). In the first place, the contour extraction function g ( t)
Is a function defined based on the contour model function fm (t). The contour model function fm (t) corresponds to a pixel value function when an ideal contour is considered, and the origin O
Is the position of this ideal contour line.
Therefore, the essential meaning of the contour function h (t) can be said to be a numerical representation of the degree to which the position t exhibits the property as a contour line. The value becomes larger as the position t becomes closer to the contour. Conversely, the contour function h
It may be determined that a contour line exists at a position where the value of (t) has increased. Therefore, in the graph of FIG. 17, it can be determined that the position t0 where the contour function h (t) takes a peak value is the position of the contour line.

The above is the basic principle of the method for determining the position of the contour line according to the present invention. Once again, this method is organized. First, a cut plane T is determined for actual image data as shown in FIG. 9, and an axis t indicating a position is determined. Then, the pixel values of the pixels on the cut plane T are arranged on the t-axis,
A pixel value Q (t) as shown in FIG. 10 is obtained, and a pixel value function f (t) is obtained therefrom. On the other hand, a window function w (t) as shown in FIG. 13 is defined by setting the coefficient a, and the contour model function fm (t) and the window function w shown in FIG.
As a product of (t), a contour extraction function g (t) is obtained. Then, the contour function h (t) is calculated by an operation based on Expression (6).
And the position t0 of the peak value is set as the position of the contour line.

By the way, the role of the coefficient a set for defining the window function w (t) will be described. When the coefficient a is set small, the obtained contour function h (t) has a gentle curve as shown in FIG. 18 (a). Conversely, when the coefficient a is set to be large, the contour function h (t) obtained is as shown in FIG.
As shown in FIG. However, since the actual pixel value function f (t) includes a noise component, the actual contour function h (t) is as shown in FIG. If the coefficient a is set small, the contour extraction function g (t) functions as a low-pass filter to reduce noise. However, since the width near the peak value is widened, the error ε in determining the peak value increases as shown in FIG. 19 (a). Conversely, if the coefficient a is set to be large, the contour extraction function g (t) functions as a high-pass filter, so that the width around the peak value is narrowed, but noise cannot be reduced, and the peak value is also determined. Error ε
Becomes large. Eventually, it is necessary to select an appropriate value for the coefficient a, which takes a value between FIGS. 19 (a) and (b). In the case where the interval between the contour lines is small and a plurality of contour lines are included on the same cut plane, the contour function h (t) is as shown in FIG. In this case, if the coefficient a is set to be small, it becomes difficult to identify the contour position as shown in FIG. 20 (a), and if the coefficient a is set to be large,
As shown in FIG. 20 (b), noise increases. Therefore, it is necessary to set the coefficient a to an appropriate intermediate value between the two. This coefficient a is also one of the parameters that can be set by the command E described in FIG.

In the above, the theory for obtaining the contour function value has been described.
Next, an example of a specific calculation method according to this theory will be described. Now, as shown in FIG. 21, two pixels Pi-1 and Pi-1
It is assumed that the origin pixel Pi + 1 'is determined based on the above. Here, n × n pixels existing around the starting pixel Pi + 1 ′ are extracted as surrounding pixels. In this example, n = 5, that is, 5 × 5 = 25 pixels are extracted as surrounding pixels (indicated by broken lines in FIG. 21). The number n for determining the number of surrounding pixels is also determined by the command E described in FIG.
Is one of the parameters that can be set. Hereinafter, each pixel is represented by Pxy (x ≧ x), where x is the horizontal direction and y is the vertical direction.
0, y ≧ 0), and the surrounding pixels are represented by Pqr
(0 ≦ q ≦ n−1, 0 ≦ r ≦ n−1). For example, in FIG. 21, the five pixels in the top row are expressed as P00, P10, P20, P30, and P40, the pixel at the lower left corner is expressed as P04, and the pixel at the lower right corner is expressed as P44. Become.

Subsequently, the cut plane must be determined. Since the pixels are arranged vertically and horizontally, two directions, that is, the vertical direction and the horizontal direction, are advantageous from the viewpoint of data processing efficiency in determining the cut plane. As shown in FIG.
Is ideally defined in a direction orthogonal to the contour line Tc. Therefore, as shown in FIG.
A cross section is taken in a direction that intersects at a more nearly orthogonal angle with respect to a line connecting the pixel and the origin pixel Pi + 1 ′. In this example, the cutting plane is taken in the horizontal direction, and five cutting planes Y0 to Y4 are defined as shown by dashed lines.

First, five pixels P00, P10, P20, P30, and P40 on the cutting plane Y0
, The contour function value will be obtained for each. First, a pixel value function f (x) is determined (since the cut plane Y0 is in the x-axis direction, in this specific example, x is used instead of t as a variable indicating an image cut plane position). This is easily obtained based on the pixel value actually given for each pixel, and for example, it is assumed that a function f (x) as shown in FIG. 22 is obtained. That is, five pixels P00, P10, P20, P30, P4
X0, x1, x2, x3, x
If it is 4, the values of the pixel value function will be f00, f10, f20, f30, f40. The pixel value function f (x) shown in FIG. 22 corresponds to the pixel value function f (t) shown in FIG. Subsequently, the contour extraction function g (x) is defined, for example, as shown in FIG. This corresponds to the contour extraction function g (t) shown in FIG. In the example of FIG. 23, since the base of the window function w (x) used to define the function g (x) is changed from “exp” to “2”, the function values g1, g2, g3, g4 Have a relationship of decreasing by 1/2 each. The function value is x
Both the positive and negative directions of the axis are m-th (in this example, m =
The values up to 4) are defined. The value m indicating the width in which the function value is defined is also one of the parameters that can be set by the command E described with reference to FIG. When the two functions f (x) and g (x) are determined in this way, the contour function h (x) can be obtained by calculation from these two functions. The specific arithmetic expression is as follows.

However, the value of f (x) outside the range of the peripheral pixel Pqr is 0. This equation (7) is an equation corresponding to the above-mentioned equation (6), and includes five pixels P00, P10, P20, 38, P on the cut plane Y0.
For 40, the contour function values h (X0), h (X1), h
(X2), h (X3), h (X4). Here, this is further extended to two dimensions. That is, if the same operation as the operation performed on the cut plane Y0 is also performed on the cut planes Y1 to Y4, the contour function value hxy for an arbitrary pixel Pxy is calculated as follows.
It can be obtained by the following equation using the pixel function value fxy.

In this way, as shown in FIG. 24, a table is obtained in which the contour function values hxy for each of the 25 surrounding pixels are obtained. If this contour function value is a certain value or more, it can be determined that the pixel is a pixel on the contour line.
In order to obtain the contour function value hxy, Pi + 1 ', a, n,
Although each parameter such as m is used, these parameters are set to optimal values by the command E described in FIG. 3 according to the fineness of the picture to be cut out.

(3) Determination of Optimal Pixel By the above operations, the processing up to the contour function value calculation processing in step S22 in the flowchart shown in FIG. 7 has been completed. Therefore, finally, the optimum pixel determination processing in step S23 is performed. This is a process for determining an optimum pixel from among the 25 surrounding pixels in this case based on the obtained contour function value hxy. That is, as shown in FIG. 25, it can be said that a process of determining an optimal pixel as a predicted pixel to be a third pixel on a contour line connected to the first pixel Pi-1 and the second pixel Pi. . As described above, the contour function value hxy is a value indicating the degree of property as a pixel on the contour line. If this value is large, the pixel exists at a position close to the contour line. Therefore,
If the contour function value is equal to or greater than a predetermined value, it may be determined that the pixel exists on the contour line. However, in general, there are a plurality of pixels determined to exist on the contour line among the surrounding pixels. Therefore, from these pixels, based on the following two conditions, the optimum pixel Po + 1 is set as the third pixel Pi + 1.
Determine pt.

<Condition 1> The distance between the second pixel Pi and the optimum pixel Popt is as long as possible.

<Condition 2> A line connecting the second pixel Pi and the optimum pixel Popt is as co-linear as possible with the contour line.

These two conditions have the following meanings. First, condition 1 is
This is a condition for improving the efficiency of the cutting operation. When performing a cutting operation as shown in FIG. 4 (b), the designated points P1, P
2,... Are sequentially input, but when the distance between adjacent designated points is as long as possible, the number of designated points required to designate one closed curve is reduced. In other words,
The efficiency is better if the distance between the i-th designated point Pi and the (i + 1) -th designated point Pi + 1 is as far as possible. Therefore, the condition 1 is set such that the distance between the second pixel Pi and the optimum pixel Popt as the third pixel is as long as possible. This can be easily understood by considering an example as shown in FIG. In FIG. 26, the first point P1 and the second point P2 on the contour Zc have already been determined, and the third point P3
Consider the case where the optimal point is determined. Here, assuming that two candidates of the points P3a and P3b are selected as the optimum points, it is more efficient to select a point P3b farther from the point P2 as the optimum point.

However, the longer this distance is, the better. If the optimal pixel Popt is determined at a position far away, if the contour line is bent in the middle,
The result is a deviation from the contour. This can be easily understood by considering an example as shown in FIG. In FIG. 27, a case is considered where the first point P1 and the second point P2 on the contour line Zc are already determined, and the optimum point as the third point P3 is determined. Here, it is assumed that two candidates, a point P3a and a point P3b, have been selected as optimal points. In this case, if a point P3b further away from the point P2 is selected as the optimum point, the integration P2P3b
(Indicated by a broken line in the drawing) is deviated from the bent portion of the contour Zc in the section k. Therefore, in this case, the point P3a should be selected as the optimum point. Line segment P2P3a is substantially on the same straight line as contour line Zc. This is the meaning of condition 2.

Therefore, as the optimal point (optimal pixel), a point (pixel) that satisfies both the above conditions 1 and 2 is selected from a plurality of pixels determined to exist on the contour line. To find a pixel that satisfies both conditions, consider the following processing. First, a first parameter Nxy is obtained for all surrounding pixels. This parameter Nxy
Is defined as “the total number of surrounding pixels existing on a line segment connecting the second pixel Pi and the pixel”. This will be described with reference to FIG. For example, let's find the parameter N00 for the pixel P00. In this case, an arrow is drawn from the second pixel Pi to the pixel P00 (strictly speaking, an arrow connecting the center of each pixel is drawn), and the number of peripheral pixels existing on the arrow may be counted. In the example of FIG. 25, two of the pixels P00 and P10, which are hatched, correspond to this. Therefore, the value of the first parameter N00 for the pixel P00 is 2. Also, the parameter N22 for the pixel P22
Is obtained by drawing an arrow from the second pixel Pi to the pixel P22, and counting the number of surrounding pixels (pixels P30, P21, P31, P22 with hatched dots) existing on the arrow, N22 = 4 .
Thus, when the first parameter Nxy is obtained for all the surrounding pixels (25 in this example), for example, a table as shown in FIG. 28 is obtained. Next, the second parameter Axy is defined as "the total of the contour function values of the surrounding pixels existing on the line segment connecting the second pixel Pi and the pixel". This will be described again with reference to FIG. For example, let's find the parameter A00 for the pixel P00. In this case, the sum of the contour function values for the surrounding pixels on the arrow drawn from the second pixel Pi to the pixel P00 (pixels P00 and P10 hatched with diagonal lines) may be obtained. That is, A00 = h00 + h10. The parameter A22 for the pixel P22 is obtained by drawing an arrow from the second pixel Pi to the pixel P22, and defining the outline of the surrounding pixels (dot-hatched pixels P30, P21, P31, and P22) on the arrow. What is necessary is just to find the sum of the function values. That is, A22 = h30 + h21 + h
31 + h22. Thus, when the second parameter Axy is obtained for all the surrounding pixels (25 in this example), for example, a table as shown in FIG. 29 is obtained.

Then, from the table of FIG. 29, the second parameter Ax
Extract surrounding pixels where y is relatively large. For example, it is possible to adopt a method of extracting surrounding pixels in which the value of the parameter Axy falls within the upper 10% as candidates. In this case,
In the case of this example, three surrounding pixels P13, P04, and P14 hatched in FIG. 29 are extracted. When performing such extraction, it is preferable not to perform extraction unless the absolute value of Axy is equal to or greater than a predetermined value, even if it falls within the top 10%. Thus, it is possible to prevent pixels that are not on the outline from being erroneously extracted. Such an extraction operation is nothing less than an operation of extracting a pixel satisfying the above condition 1. Because the second parameter Axy takes a larger value as the arrow drawn from the second pixel Pi to the pixel is longer, the larger the Axy is,
It can be said that the pixel is a pixel located at a position distant from the second pixel Pi.

Now, when candidates satisfying the condition 1 are determined, the values of Axy / Nxy are calculated for these candidates. As a result:

Axy Nxy Axy / Nxy pixel P13 30 65 pixel P04 32 8 4 pixel P14 31 7 4.43 Here, Axy / Nxy is defined as “the outline of a peripheral pixel existing on a line connecting the second pixel Pi and the pixel. Average Function Value "
It turns out that. The pixel having the largest average value is the pixel that satisfies the condition 2, and is the optimal pixel finally obtained. Because, as described above, since the contour function value hxy indicates the degree of the property as a pixel on the contour line, a path in which the average value of the contour function value hxy is large follows the contour line. This is because the route can be determined. Thus, the optimal pixel is the pixel P13 having the largest Axy / Nxy. The theory for Condition 2 should be better understood with reference to the example of FIG. In FIG. 27, comparing the value of Axy / Nxy for the pixel at the position of point P3a with the value of Axy / Nxy for the pixel at the position of point P3b, the former is larger than the latter. Should be. This is because, in the latter case, the value of the contour function value hxy becomes smaller in the section k, so that the average value decreases. Thus, also in the example of FIG. 27, of the two candidate points P3a and P3b, the point that satisfies the condition 2, that is, the point P3a having a larger value of Axy / Nxy is determined as the optimum point.

In the above-described embodiment, the first parameter Axy and the second parameter Nxy are obtained for all surrounding pixels (in this case, 25), but the contour function value hxy as shown in FIG. At the time point when the table is obtained, only the pixels for which the contour function value hxy is equal to or greater than a predetermined value (that is, the pixels that can be determined to be on the contour) are extracted.
The calculation for obtaining Axy and Nxy may be performed. However,
As described above, since the contour function value hxy includes a noise component, performing the calculation for obtaining both parameters Axy and Nxy for all surrounding pixels as in the above-described embodiment reduces the error. Is preferred. Also, the parameter Axy
After several candidates are extracted according to the size of the candidate, in the above-described embodiment, Axy / Nxy is calculated for this candidate, and the pixel having the largest value is determined as the optimal pixel. When the values of Axy are substantially equal, a good result can be obtained even if a method of determining the pixel with the smallest Nxy as the optimum pixel without performing the operation of Axy / Nxy. Also,
The present invention is also applicable to a color image having a plurality of color plates. In this case, the parameter Axy
May be obtained, and the optimum pixel may be determined on the color plate in which the largest value of Axy is obtained.

As described above, the prediction processing shown in the flowchart of FIG. 7 is completed. Thus, an optimal position as the third point Pi + 1 can be predicted based on the first point Pi and the second point Pi. Such a prediction process has been described as an example of the process of step S14 in the procedure of the image clipping process shown in FIG. 6, but may be used for various other purposes. In short, this prediction process can automatically determine the contour of the picture included in the image composed of a set of pixels having a predetermined pixel value. That is, the first point and the second point on the contour
If a point is given as an initial point, the position of the third point can be automatically predicted and determined, so that the fourth and subsequent points can be predicted and determined recursively. Therefore, the present invention can be applied to various processes that require automatic determination of a contour line, such as automatic cutting processing along a contour line.

〔The invention's effect〕

As described above, in the pattern outline determination method according to the present invention, the prediction calculation is performed on the position of the third point that should follow the two points based on the two points on the outline.
The position of a point on the contour is automatically predicted by a computer, and the contour can be automatically determined without designating a point by an operator, thereby greatly improving work efficiency.

[Brief description of the drawings]

FIG. 1 is a block diagram showing a basic configuration of an image layout apparatus having an image clipping function using a contour line determining method according to the present invention, and FIG. 2 shows a procedure of an image layout process by the image layout apparatus shown in FIG. FIG. 3 is a view showing a display screen when an image cutting operation is performed by the apparatus shown in FIG. 1, FIG. 4 is a display screen view in a general outline determination work, and FIG. 5 is an outline according to the present invention. FIG. 6 is a flowchart showing a procedure of an image clipping process using the contour line determining method of the present invention.
FIG. 9 is a flowchart showing an example of a prediction process which is the basis of the contour determination method of the present invention. FIG. 8 is a diagram for explaining the principle of the prediction process shown in FIG. 7, and FIG. 9 is a prediction process shown in FIG. FIG. 10 is a graph showing the pixel value Q (t) of the contour portion obtained based on the image shown in FIG. 9, and FIG. 11 is a graph shown in FIG. FIG. 12 is a graph showing a contour model function fm (t) used for prediction processing, and FIG. 13 is a window function w (t) used for prediction processing. FIG. 14 is a graph showing a contour extraction function g (t) used in the prediction processing;
FIG. 15 is a graph showing a state where the origin O of the contour extraction function g (t) is superimposed on the point t1 in the pixel value function f (t).
The figure shows the origin O of the contour extraction function g (t) as the pixel value function f
FIG. 17 is a graph showing a state superimposed on a point t0 in (t), FIG. 17 is a graph showing a contour function h (t) used for prediction processing, and FIG.
FIGS. 18 (a) and (b) are graphs showing a state in which the contour function h (t) changes depending on the magnitude of the coefficient a. FIGS. 19 (a) and (b) and FIGS. b) is a graph showing a state in which the contour function h (t) including a noise component changes depending on the magnitude of the coefficient a. FIG. 21 is a diagram for explaining a method of performing prediction processing on actual pixels. Is a graph showing a pixel value function f (x) applied to an actual pixel, and FIG.
FIG. 24 is a graph showing a contour extraction function g (x) applied to actual pixels. FIG. 24 is a table showing contour function values hxy obtained for all surrounding pixels. FIG. FIG. 26 is a diagram for explaining condition 1 for determining an optimum pixel, FIG. 27 is a diagram for explaining condition 2 for determining an optimum pixel, and FIG. 28 is obtained for all surrounding pixels. Table showing the parameter Nxy, the second
FIG. 9 is a table showing parameters Axy obtained for all surrounding pixels. 1 ... Scanner, 1A ... Input drum, 1B ... Output drum, 2 ... Document, 3 ... Control device, 4 ... Drawing machine, 4A ...
... Pointing device, 4B ... Command menu, 5 ...
... Mounting mount, 6 ... Display device, 61 ... Image display unit, 62 ...
... Command display section, 7 ... Input device, 8 ... Memory, Cu
…… Cursor, T …… Cutting plane, Z …… Picture, Z1, Z2 ……
Area, Zc ... Outline line.

────────────────────────────────────────────────── ─── Continuation of the front page (56) References JP-A-2-101456 (JP, A) JP-A-58-176638 (JP, A) (58) Fields investigated (Int. Cl. ⁷ , DB name) G03F 1/00-1/16

Claims (1)

(57) [Claims] 1. A method for determining an outline of a picture included in an image composed of a set of pixels having a predetermined pixel value, wherein a first point and a second point on the outline are initially set. Inputting as a point; determining a predetermined pixel on an extension of the line connecting the two initial points to the second point side as a starting pixel; and a plurality of surroundings existing around the starting pixel. Calculating, for each of the pixels, a contour function value indicating a degree of property as a pixel on the contour line; and obtaining a line segment connecting a certain surrounding pixel and the second point,
An operation for calculating the average of the contour function values given for the surrounding pixels located on this line segment is performed for all or some of the surrounding pixels, and based on the average obtained for each surrounding pixel, Determining a third point to be connected to the initial point in the step (a).