JPH0721392A - Method for extracting contour line of input picture - Google Patents

Abstract

PURPOSE:To effectively extract a contour line faithful to an input derivative picture by selecting a picture element of interest as a component of the contour line when eight picture elements adjacent to a picture element of interest are extracted and the gradation value of each picture element located in at least two directions from among four directions is smaller than that of the picture element of interest. CONSTITUTION:A small area of 3X3 centered around a picture element of interest X0 is considered as the unit of processing. Adjacent picture elements X1-X8 located neaer the eight picture elements of interest are taken as the combination of four directions with the picture element of interest as a center X0 (X2 and X7, X4 and X5, X1 and X8, and X3 and X6). In short, when the eight picture elements adjacent to the picture element of interest X0 have four combinations (X2 and X7, X4 and X5, X1 and X8, and X3 and X6) in all directions and if more than two combinations with the gradation value smaller than the picture element of interest X0, the picture element of interest X0 is selected as a component of the contour line.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for extracting a contour line of an input image in the field of image processing, and more particularly to a method for extracting a contour line of an input image which extracts contour lines using multivalued information of a multivalued input image.

[0002]

2. Description of the Related Art Generally, a grayscale image input from a video camera or the like is a digital image having multivalued information for each pixel, and therefore a large memory capacity is required to store the grayscale image.

Therefore, in many cases, such a grayscale image is not stored as it is, but binarization processing for replacing multivalued information with binary information is performed to store an image with a reduced amount of information. At this time, it is difficult for the user or the like to recognize the image only by binarizing the grayscale image, and therefore the feature extraction of the image is also performed.

For example, when an image is taken into a document processing apparatus, a contour line is extracted as a binary image from a captured grayscale image, and then vectorization processing is performed to replace the binary image with direction data (segment data). Since it is often the case, how to extract a high-quality contour line which is a prerequisite for vectorization processing is an important issue.

In the conventional technique for extracting the contour line, smoothing processing for removing noise in the grayscale image and differentiation processing for emphasizing and outputting the contour portion of the grayscale image are performed as preprocessing, and then the differentiation is performed. The processed image (hereinafter referred to as “differential image”) may be binarized prior to thinning or may be binarized after thinning.

First, the method of performing binarization prior to thinning is to replace a multivalued image with a binary image that can be easily processed thereafter, and then perform thinning processing on this binary image. This is the most commonly used method. As a typical example of this thinning processing, there is a method in which the pixels located at the center of gravity of the line width are regarded as the constituent pixels of the contour line and the other pixels are successively erased.

On the other hand, in the method of performing binarization after thinning, attention is paid to the point that the edge portion of the gray value of the differential image corresponds to the contour line, and the pixel having the maximum gray value is the contour line. In this method, the pixels are regarded as the constituent pixels and stored as binary data.

[0008]

However, the former method has a problem that it is difficult to extract a contour line faithful to the original image because the differential image is replaced with the binary image before performing the thinning process. is there.

For example, when the pixels located at the center of gravity of the line width are regarded as the constituent pixels of the contour line, the position of the pixel extracted as the contour line is displaced from the original position of the contour pixel, as shown in FIG. More often.

That is, since the original constituent pixels of the contour line can be regarded as the pixels Xp corresponding to the ridge line portion (peak) of the gray value, they do not necessarily coincide with the pixel Xw located at the center of gravity of the line width. . Therefore, even if the pixel Xw
Even if is extracted, if the density distribution of the line width is not uniform, a deviation occurs between the two. Therefore, this method cannot guarantee that the contour line faithful to the original image is extracted.

Further, since the grayscale values of the constituent pixels of the contour line are not necessarily larger than the grayscale values of the other pixels, even if the threshold value is optimally selected during the binarization processing, the original contour line is selected. Often loses information.

In order to avoid this problem, Japanese Patent Laid-Open No. 62-2
Japanese Patent Laid-Open No. 19188 discloses "a binary image thinning processing device in which a determiner finds an isolated hole in a pixel in the process of thinning processing and complements the pixel by the output of a conversion output circuit". Although there is a technique for complementing the contour line of (1), it is not efficient because the processing time is delayed and a judgment image memory is required.

On the other hand, in the latter method of thinning the multi-valued image itself, since the pixel having the maximum gray value is extracted from the multi-valued differential image, it corresponds to the original contour line having a high gray value. The pixels to be extracted can be extracted.

However, since attention is paid only to the gray value of each pixel, even if it is a maximum point, it is extracted even if it is not a constituent pixel of the contour line, and there is a problem that a noisy image is output. is there.

In order to solve this problem, JP-A-64-6
In the "Method and apparatus for extracting a contour line of an input image using a logical product of an image obtained by binarizing a contour image and an image obtained by performing maximum point extraction processing on the contour image" disclosed in Japanese Patent No. 4080,
By the logical operation of the image with a lot of noise by the latter method and the image obtained by binarizing the differential image, the noise component is removed and the contour line is extracted.

However, such processing cannot be said to be efficient because it is necessary to perform mask processing on each of the image subjected to the maximum point extraction processing and the image subjected to the binarization processing of the differential image.

Therefore, an object of the present invention is to eliminate such a problem and to quickly and efficiently extract a contour line that is faithful to the input image and has good quality.

[0018]

In order to achieve the above object, the present invention provides a contour line extraction method for extracting a contour line by using multivalued information of a multivalued input image. , Lower left upper right, lower left upper right, eight pixels are extracted, and if the grayscale value of each pixel located in at least two of the four directions is smaller than the grayscale value of the pixel of interest, It is characterized in that a pixel is selected as a constituent pixel of the contour line.

[0019]

According to the present invention, when a contour line is extracted using multi-valued information of a multi-valued input image, eight pixels adjacent to a target pixel are combined in four directions of up, down, left and right, upper left lower right, upper right lower left. If there are two or more combinations of the four combinations whose gray values are smaller than the target pixel, the target pixel is selected as a constituent pixel of the contour line and Good quality contour lines
It can be extracted quickly and efficiently.

[0020]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of a method for extracting a contour line of an input image according to the present invention will be described below with reference to the drawings.

FIG. 1 is a block diagram showing the overall structure of the present invention.

According to the present invention, an input processing section 11 for inputting an original image 10 and a preprocessing section 12 for preprocessing the input image.
And a thin line binarization processing unit 13 that extracts a contour line from the preprocessed image as binary data and outputs it to the image memory 15.
Composed of and.

Here, the input processing section 11 inputs the original image 10 picked up by a CCD camera or the like as a digital image having multi-valued information.

Further, the preprocessing section 12 performs a smoothing process for removing noise and a differentiating process for extracting edges on the digital image. Therefore, the output from the pre-processing unit 12 is a differential image having multi-valued gray values in which noise is removed from the input image and edges are extracted.

In the present embodiment, the smoothing process uses a fast Fourier transform (FFT) method, and the differential process uses "RODuda and PEHar".
t, Pattern Classification and Scene Analysis, Wiley,
A typical 3 × 3 differential operator (SOBEL operator) described in 1971, pp.267-272 ”is used.

Next, the thin line binarization processing unit 13 selects, in the candidate pixel selection unit 13a, the pixels (candidate pixels) that are likely to be the constituent pixels of the contour line in the differential image, and for each selected pixel. Then, the thinning unit 13b performs thinning using the mask pattern 14, and the binarization output unit outputs the contour line to the image memory 15 as binary data (13c). It should be noted that in the present embodiment, 3 × centered on the pixel of interest.
Since the mask processing method of 3 is used, a 3 × 3 mask pattern is prepared in the thinning unit 13b.

In order to speed up the process and remove noise components, the candidate pixel selection unit 13a excludes pixels that have no apparent possibility of forming a contour line in advance, and may be a constituent pixel of the contour line. A process of narrowing down the candidate pixels of the contour line is performed so that the thinning can be performed only on the pixels having high property.

The thinning unit 13b applies the mask pattern 14 to the candidate pixel, compares the gray value of the target pixel (candidate pixel) with the adjacent pixel, and selects the target pixel as a constituent pixel of the contour line. It is to check whether or not each adjacent pixel has a condition.

Based on the result of the thinning section 13b, the binarization output section 13c selects "1" when it is selected as a constituent pixel of the contour line, and "0" when it is not selected as a constituent pixel of the contour line. Is output to the coordinate position of the image memory 15 corresponding to the pixel of interest.

That is, according to the present invention, similarly to the conventional method, from the grayscale image input through the input processing unit 11, the preprocessing unit 12 is executed.
After calculating the differential image using, the conventional method "thinning process using the center of gravity" and "thinning process using the maximum point"
Instead of the above, a configuration for performing contour line extraction processing using the thin line binarization processing unit 13 is used.

Next, the processing procedure of the thin line binarization processing unit 13 will be described with reference to the flowchart of FIG.

First, in the thin line binarization processing unit 13, in order to simplify the processing, a processing method in which the mask processing is repeated for all the pixels forming the differential image is adopted.

Therefore, as shown in FIG. 2, it is determined whether or not the pixel of interest is a pixel having a gray value of a certain threshold value or more (S201), and if it is the threshold value or more, a mask process (S202). ), And if it is less than the threshold value, '0' is stored in the corresponding pixel of the image memory 15 without selecting the pixel as a constituent pixel of the contour line (S2).
05) Perform processing.

Here, the threshold value used in S201 is 2 in order to prevent the loss of edge components in the differential image.
Set it lower than the threshold value used for digitization.

Thereafter, a mask process (S202) described later is performed.
Then, it is confirmed whether or not a predetermined judgment condition is satisfied (S203).

As a result, when the predetermined condition is satisfied, "1" is stored in the corresponding pixel of the image memory 15 by selecting it as a constituent pixel of the contour line (S204), and when the predetermined condition is not satisfied, Is displayed in the corresponding pixel of the image memory 15.
0'is stored (S205).

The above steps S201 to S205 are repeated for each pixel of the differential image (S206), and the processing ends when all the pixels have been processed.

In the candidate pixel selection unit 13a, S201
The thinning unit 13b performs the processing of S202 to S203, and the binarization output unit 13c performs the processing of S204 or S205.

Further, in the present embodiment, the candidate pixel selection unit 13
Although the determination of S201 performed by a is performed sequentially for each pixel, it may be replaced with a process of binarizing the differential image itself in advance.

Next, the thinning portion 13b forming the main axis of the present invention.
And the masking process performed by the thinning unit 13b (S
202) and condition determination (S203) will be described in detail with reference to FIGS.

As shown in FIG. 3A, in the present invention, a small region of 3 × 3 centered on the target pixel X0 is considered as a processing unit, and adjacent pixels X1 to X8 located in the vicinity of 8 of the target pixel are considered. ,
A combination of four directions centering on the pixel of interest X0 (X2 and X
7, X4 and X5, X1 and X8, X3 and X6).

That is, when attention is paid to a pixel in the differential image, if the pixel of interest X0 is a constituent pixel of a horizontal straight line (X4-X0-X5) forming a contour line (FIG. 3).
(b)), among the adjacent pixels of the target pixel X0 and the target pixel, the grayscale values of the two pixels (X4 and X5) corresponding to the contour are the grayscale values of the other adjacent pixels (X1 to X3, X6 to X8). Will be higher than.

Further, at a certain target pixel X0, two straight lines (X2-X0-X7 and X4-X0- that form the contour line are formed.
X5) also intersects (FIG. 3 (c)), the target pixel X
0 and four adjacent pixels (X2, X7,
The gray value of X4, X5 is the same as that of other adjacent pixels (X1, X3, X).
6 and X8) is higher than the gray value.

As described above, in the small area of 3 × 3, the contour line can be regarded as a combination of straight lines in four directions. Therefore, according to the present invention, eight adjacent pixels are combined into four combinations (X2).
And X7, X4 and X5, X1 and X8, X3 and X6).

Further, at a certain pixel of interest X0, three or more straight lines forming the contour line may intersect, but in such a case, it is often appropriate not to regard it as a pixel constituting the contour line. For this reason, when many of the adjacent pixels have the same gray value, it is not considered as a contour line.

For example, when the adjacent pixels are shown in FIG. 3 (d), the target pixels are X1-X0, X2-X0, X4-X0, X3.
It is not appropriate to regard it as an intersection of four contour lines (straight lines) -X0-X6, and it should be regarded as pixels forming the outer edge of the contour. At this time, the contour line is considered to pass through the adjacent pixel X1 having a gray value higher than that of the target pixel.

Therefore, in this embodiment, the pixel of interest X0 is
If it is on one straight line (contour line) or is the intersection of two straight lines (contour lines) in different directions, it is regarded as a constituent pixel of the constituent pixel of the contour line, otherwise it is other than the contour line. The constituent pixels of

Further, the fact that the target pixel is the intersection of two straight lines (contour lines) means that no contour line is formed in the other directions (two directions). "It is on one straight line (contour line) or is an intersection of straight lines (contour lines) in two different directions", and "at least two directions among four straight lines passing through the target pixel X0". Is not on the straight line of. "

Therefore, in this embodiment, the condition for considering the target pixel as a constituent pixel of the contour line is that "the gray value of the target pixel is at least two sets of adjacent pixel values among four sets of adjacent pixels. If it is greater than either, "

Based on the above concept, mask processing (S20
In 2), the density difference (Yi = X0−Xi, i = 1 to 8) between the target pixel X0 and each adjacent pixel is obtained, and the vertical combination (X2
And X7), the horizontal combination (X4 and X5), and the diagonal combination (X1 and X8, X3 and X6), the target pixel X
The number of combinations in which the density difference Yi with 0 is positive (Yi ≧ 0) is calculated.

Then, in the condition determination (S203), it is determined whether or not the number of sets calculated in the masking process (S202) is two or more, and only when the condition is satisfied, the target pixel X0 is configured as a contour line. It will be regarded as a pixel.

As described above, the thin line binarization processing unit 1 according to the present invention.
The operation concept of No. 3, the mask processing (S202) and the condition determination (S203) have been described in detail.

Next, FIG. 4 shows a result of performing each processing of the thin line binarization processing unit 13 (S201 to S206) on the differential image.

FIG. 4A is a differential image having multi-value grayscale values input to the thin line binarization processing unit 13.

FIG. 4 (b) is a binarized version of FIG. 4 (a) with the threshold value of gray value '65'. That is,
In FIG. 4 (b), the threshold value processing of S201 is performed on each pixel of the differential image, and the pixels that are candidates for the contour line to be transferred to the mask processing of S202 are extracted and represented by "1". Is.

Further, in FIG. 4C, the processing of S202 to S205 is performed for each pixel of FIG. 4A located at the same coordinates as the pixel having "1" in FIG. 4B. It is the result.

Therefore, as shown in FIG. 4 (c), as shown in FIG.
It can be seen that, in the differential image shown in (3), the ridge line portion having a high gray value can be extracted as one contour line. On the contrary,
In FIG. 4B in which the threshold processing is simply performed, the contour having a thickness can be extracted, but it cannot be extracted as a line drawing.

In this embodiment, it is not necessary to create the binary image shown in FIG. 4 (b), but it is shown for convenience of explanation by comparing FIGS. 4 (b) and 4 (c). did.

Further, in FIG. 5, for the entire differential image with the wristwatch as a subject, (a) when the differential image is simply binarized, (b) the conventional method of thinning after binarization is used. In the case of the following, processing results in the case of (c) binarization after the conventional thinning, and (d) the case of applying the present invention are shown.

As shown in FIG. 5A, the differential image is simply 2
It can be seen that when the value is converted, the edge portion is well represented as a line segment having a thickness.

However, it can be seen that when the conventional method of thinning after binarization shown in FIG. 5B is applied, the alphabet in the figure is broken and the output is made in the form of bubbles.

Further, it can be seen that a large amount of noise is included when the conventional method of binarizing after thinning shown in FIG. 5 (c) is applied.

On the other hand, in the method according to the present invention shown in FIG. 5D, the contour line can be extracted as a line segment in comparison with the processing results of the conventional method (FIGS. 5B to 5C). I understand.

As described above, in this embodiment, when extracting a contour line from an input image having multi-valued gray values, eight pixels adjacent to the target pixel are vertically, horizontally, upper right lower left, upper left. In the case of the four combinations at the lower right, when the grayscale value of the pixel of interest is greater than the grayscale value of any of the four pixels forming the at least two combinations, the pixel of interest is Select it as a constituent pixel,
In other cases, by not selecting the target pixel as a constituent pixel of the contour line, a contour line faithful to the input differential image and of good quality can be extracted quickly and efficiently.

Further, the mask processing is not performed on all the pixels of the differential image, but is limited to the pixels having a threshold value or more, so that the processing can be speeded up.

Furthermore, since it is not necessary to perform post-processing on the output image, high quality contour lines can be efficiently extracted.

In the present embodiment, the case of 3 × 3 mask processing is shown, but the present invention is not limited to mask processing, and various methods using the relationship between the pixel of interest and the adjacent pixel can be used. Can be applied to

[0068]

As described in detail above, according to the present invention, when a contour line is extracted by using multi-valued information of a multi-valued input image, upper and lower sides, right and left sides, lower right and lower left, and upper left and right adjacent to a pixel of interest. When eight pixels in the downward direction are extracted and the grayscale value of each pixel located in at least two directions among the four directions is smaller than the grayscale value of the target pixel, the target pixel is defined as a pixel constituting the contour line. By selecting as, it is possible to quickly and efficiently extract a contour line that is faithful to the input differential image and has good quality.

Further, since thinning is not performed on all the pixels of the differential image but thinning is performed on the pixel candidates calculated in advance, there is also an advantage that the processing speed can be increased.

[Brief description of drawings]

FIG. 1 is a block diagram showing the overall configuration of the present invention.

FIG. 2 is a flowchart showing a processing procedure of a thin line binarization processing unit shown in FIG.

FIG. 3 is an explanatory diagram of mask processing and determination conditions shown in FIG.

FIG. 4 is a diagram showing a result of performing thin line binarization processing shown in FIG. 2 on a differential image.

FIG. 5 is a diagram showing an example of the processing result shown in FIG.

FIG. 6 is a diagram showing a difference between a pixel forming a contour line according to a conventional method and an original pixel forming a contour line.

[Explanation of symbols]

10 original image, 11 input processing unit, 12 pre-processing unit,
13 thin line binarization processing unit, 13a candidate pixel selection unit,
13b thinning unit, 13c binarization output unit, 1
4 mask patterns, 15 image memory

 ─────────────────────────────────────────────────── ─── Continuation of the front page (72) Inventor Seiji Yajima 3-2-1 Sakado, Takatsu-ku, Kawasaki City, Kanagawa Prefecture KSP R & D Business Park Building Fuji Xerox Co., Ltd.

Claims (1)

[Claims] 1. A contour line extraction method for extracting a contour line by using multi-valued information of a multi-valued input image, wherein eight pixels adjacent to a pixel of interest are extracted vertically, left and right, upper right lower left, upper left lower right. When the grayscale value of each pixel located in at least two of the four directions is smaller than the grayscale value of the target pixel, the target pixel is selected as a constituent pixel of the contour line. A method for extracting contour lines of an input image.