JPH07111737B2 - Thinning device - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention In order to measure the width of a binary pattern and to recognize the connection relationship, such as in the case of defect inspection of a circuit pattern, the present invention thins the pattern from the background side by layer to obtain a core wire. , A thinning processing apparatus for giving a distance value to pixels to obtain a distance image.

[0002]

2. Description of the Related Art Since thinning is frequently used in line figure processing and is an important preprocessing for figure recognition, many methods have been proposed historically. , “Information Processing Society of Japan Image Processing Research Institute, 1-1 (1975)”, a comparative study of various methods. In the above comparative study, the serialization type and the parallel type are listed as the thinning processing formats. The former is a computer-friendly method because the processing conditions are complicated but the calculation time is fast, and the latter is inferior in the calculation time to the former. It is said that it is suitable for the case where it is implemented as hardware because the position of the core wire easily comes to the center position of the pattern and it is excellent in isotropy and noise resistance. In parallel processing, in order to prevent disappearance of even-width lines, pixel erasing of one layer is usually divided into four erasing cycles, which is a factor of increasing the calculation time. Therefore, in recent years, a method of reducing the number of erase cycles of parallel processing has been proposed. As an example, Holt.
CM etal, "An improved parallel thinning algorith
m ", Comm. ACM 30,3 (Feb. 1987), pp.156-160), etc. The specific processing of this method will be described below.
The pixel values in the vicinity of × 3 are defined as shown in FIG. First, when (Equation 1) and (Equation 2) are both true, it is determined that the target pixel d0 is an erasable edge.

[0003]

[Equation 1]

[0004]

[Equation 2]

However, in (Equation 2),-indicates logical product, and-indicates negation. Next, all erasable edges except (Equation 3) or (Equation 4) are erased.

[0006]

[Equation 3]

[0007]

[Equation 4]

That is, in the above method, an erasable edge is determined in advance in the first half process, and pixels are erased by the odd / odd judgment using the edge in the second half process. Thus, one layer of pixel erasure is realized. Therefore, the calculation time is shortened as compared with the conventional 4-cycle parallel processing.

[0009]

However, in the above method, an unwanted core wire may remain even if slight irregularities around the pattern are left. FIG. 15 shows an example thereof, and shows that when there is a minute protrusion at the corner of the pattern, the core wire remains in that direction. However, the numbers attached to the pixels in FIG. 15 indicate the order in which the pixels are erased by thinning.
Indicates that they are pixels forming the core line. The cause of the unnecessary core wire remaining in FIG. 15 is that pixels 61 and 62 are each 1
This is because the condition of (Equation 2) is not satisfied in the second processing and the second processing, so that there is a problem that unnecessary core wires are likely to remain due to the influence of noise. Pixels satisfying (Equation 1) and (Equation 2) are limited to 8-connected edge positions, and the 8-connected edges of the pattern are erased by thinning as shown in FIG. There is a problem that the vertical direction is erased quickly, and the number given to each pixel does not always become the shortest distance value to the background.

The present invention solves the above-mentioned problems of the prior art by reducing the erase cycle for thinning one layer,
A good quality core wire that satisfies noise resistance, isotropy and stability is obtained, and the pattern is thinned in all directions at a uniform speed to obtain a distance image in which the numbered pixels have the shortest distance value from the background. An object of the present invention is to provide a thinning processing device capable of performing the above.

[0011]

In order to achieve this object, the present invention provides a first peripheral point detecting means for detecting 8-connected edges of an input pattern and a 4-connected edge or 8-connected edges of an input pattern. Second peripheral point detecting means,
Referring to the edge information from the first peripheral point detection means,
Of the pixels at the edge position, the sum of the values of pixels near 8 is 2 or more and the sum of the values of pixels near 4 is 2 or less .
3x3 of the input image and the edge image selected as the pixel of interest
When the nearby pattern meets the specified condition, the first target image
A first removal determination means for erasing the element, with reference to the edge information from the second peripheral point detecting means and the input pattern Tokoro
When the specified condition is satisfied, the specified data of the edge information
Peripheral edge correction means for correcting the edge position by rewriting, and the edge information by the peripheral point correction means for the image data from the first erasure determination means,
Of the pixels at the edge position, the pixels in which the total of 8 neighborhoods is 2 or more
When the pattern in the vicinity of 3 × 3 of the input image and the edge image is selected as the second pixel of interest and satisfies a predetermined condition, the second pixel is selected .
The second erasure determination means for erasing the pixel of interest, the corrected edge information from the peripheral point correction means, the distance image from the memory are referred to, the distance value D is referred to, and a predetermined condition is satisfied.
When the distance value D is updated to D + 1,
It is composed of distance conversion means for writing in the memory .

[0012]

According to the present invention, since the edge position detected by the second peripheral point detecting means is corrected and thinned by the peripheral point correcting means in the above structure, not only the horizontal / vertical / 45 ° directions but also the interval therebetween. It is possible to reduce the distance in the direction at a constant speed, and by performing the thinning numbering in the distance converting means, it is possible to obtain a highly accurate distance image having the shortest distance value from the background. Further, since the peripheral point correction means and the distance conversion means can perform processing in parallel with the first erasure determination means and the second erasure determination means, respectively, when the processing is pipelined, the core lines are simultaneously formed without increasing the delay. A range image can be obtained.

[0013]

【Example】

(Embodiment 1) An embodiment of the present invention will be described below with reference to the drawings.

FIG. 1 is a block diagram of a thinning processing apparatus according to an embodiment of the present invention. In FIG. 1, 101 is an image memory in which binary images are stored, and 102 is an image memory 1.
01 first peripheral point detecting means for detecting 8 connected edges of the binary image from 01, 103 a second peripheral point detecting means for detecting 4 connected edges or 8 connected edges of the binary image from the image memory 101, Reference numeral 104 is a first peripheral point storage means for storing 2-bit edge information from the first and second peripheral point detection means 102 and 103, and 105 is an image memory 101.
The sum of the values of the eight neighboring pixels among the pixels at the edge positions with reference to the binary image from the first peripheral point storage means 104 and the edge information detected by the first peripheral point detection means 102. A first erasure determination means for erasing the pixel of interest when the sum of the values of the pixels in the vicinity of 2 and 4 and the sum of the values in the vicinity of 4 is selected and the pattern in the vicinity of 3 × 3 of the input image edge image satisfies a predetermined condition. , 106 is the first erasure determination means 10
5, an auxiliary storage unit for storing the binary image from 5 stores the binary image from the image memory 101 and the edge information detected by the second peripheral point detection unit 103 from the first peripheral point storage unit 104. Reference is made to the peripheral point correcting means for correcting the edge position, and reference numeral 108 denotes the peripheral point correcting means 107.
Second peripheral point storage means for storing the value image, 109 refers to the binary image from the auxiliary storage means 106 and the edge information from the second peripheral point storage means 108, and refers to eight neighborhoods of pixels at the edge position. Second erasure determination means for erasing the pixel of interest when a pixel having a total sum of the pixel values of 2 or more is selected and the pattern in the vicinity of 3 × 3 of the input image and the edge image satisfies a predetermined condition, and 110 is a second An image memory for storing the binary image from the erasure determination means 109, 111 refers to the edge information from the second peripheral point storage means 108 and the distance value from the distance image memory 112, and distance conversion for updating the distance value It is a means.

FIG. 2 is a block diagram of a thinning processing apparatus that repeats the above thinning processing by using a CPU system to narrow the pattern to one pixel width and convert a binary pattern into a distance image. In FIG. 2, reference numeral 202 stores a control program of a thinning process including the first and second peripheral point detection, the first and second erasure determination, the peripheral point correction and the distance conversion. ROM, 203 is a main memory into which the program is loaded, 201 is a CPU for executing the program on the main memory 203, 204 and 2
Reference numeral 05 is an image memory for storing input / output binary images in thinning processing, 206 is a range image memory for storing range images, and 207 is 2-bit edge information detected by the first and second peripheral point detection. A memory for storing edge information, 208 denotes a corrected edge information storage memory for storing the edge position corrected by the peripheral point correction, 209
Is an auxiliary memory for storing the output image by the first erasure determination. The operation of the thinning process in the CPU system of FIG. 2 will be briefly described below. The CPU 201 reads the image data from the image memory 204 in which the input image corresponding to the image memory 101 of FIG. 1 is stored, performs the calculation in the first and second peripheral point detecting means 102 and 103, and outputs the calculation result as an edge. It is stored in the information storage memory 207. Next, the image data at the same position is simultaneously read from the image memory 204 and the edge information storage memory 207,
The first erasing judgment means 105 performs the erasing judgment calculation and stores the calculation result in the auxiliary memory 209. Next, the image data at the same position is read from the image memory 204 and the edge information storage memory 207 at the same time, the correction determination of the peripheral point correction means 107 is performed, and the corrected edge information is stored in the corrected edge information storage memory 208. Next, the image data from the corrected edge information storage memory 208 and the auxiliary memory 209 is read, the erasure judgment calculation is performed in the second erasure judgment means 109, and the calculation result is stored in the image memory 205 corresponding to the image memory 108 in FIG. Store. Further, the corrected edge information storage memory 208 and the range image memory 20
The image data of No. 6 is read, the distance value is updated, and the distance image memory 206 is written again. With the above operation, the image memory 2
The binary pattern 04 is thinned by one layer from the background side and stored in the image memory 205 and the distance image memory 206.
The distance value is updated by 1 above. The second thinning is performed on the binary image in the image memory 205, and the binary image further thinned by one layer is stored in the image memory 204 through the above procedure.
Similarly, the thinning of the nth time is performed on the (n-1) th thinned image, and the iterative process is repeated until the pattern has a width of 1 pixel.

With respect to the thinning processing apparatus configured as described above, the specific thinning processing will be described with reference to the flow charts shown in FIGS. In the figure, 301 is the second
This is a step of reading the thinning control table in which the connectivity of the edges to be detected by the peripheral point detection 303 and the presence / absence of the necessity of the edge correction are registered. In this table, for example, the data shown in (Table 1) is registered, and it is determined for each repetition of the narrowing process whether to detect 4 connected edges or 8 connected edges by the second peripheral point detection 303. It This
Here, at least 4 connected edges are in the vicinity of 8 from the pixel of interest.
Each edge is a contour line with 0, and 8 connected edges are the target pixel.
There are at least one 0 in 4 neighborhoods of up, down, left and right
It is a contour line. That is, 8 connected edges are 4 connected edges
include. In addition, the connection of edges described in (Table 1)
The order is as follows:
Erase either 4 or 8 connected edges
It shows whether or not it is in 8 directions by a series of thinning processing.
The aim is to reduce the ratio evenly in these directions.
For example, a series of thinning processes erases 4 connected edges each time.
If you do, the target figure will be
It is more narrowed, and on the contrary, it is 8 linked edges each time.
When you erase the
Is made thinner. Therefore, in the order shown in (Table 1)
If you control the erasure of edges, it will
Can be evenly thinned. This is the thinning odor
One thinning process is the result of the outline of the figure and the thinning process.
This is equivalent to shortening the distance from the core wire by 1.
The distance to narrow in 5 ° direction and the distance to narrow in up / down / left / right directions
In order to make it even, it should be
The connected state of pixels with the same distance and erase with each thinning process
You just have to match the connection state of the edges to be destroyed.
If you think in that way, you will be able to erase with each thinning process.
The connection state of the dice is determined as shown in (Table 1). Also (table
In 1) decide whether to correct the second peripheral point
What's more, add a narrowing distance of 45 ° diagonally and vertically and horizontally.
Direction between them, for example, 22.5 ° direction or 67.5 ° direction
This is also done for equality. 45 ° direction
22.5 ° and 67.5 ° directions with the equidistant lines connected in the same direction
No correction is required if the equidistant lines in the same direction are connected.
However, if they are different, correction is necessary. For example,
Write a distance of horizontal and vertical sides 6 pixels direction (Other terms that
For the pixel at the position after the decimal point)
If you think about it, there are 4 connections in the 45 ° direction, but 22.5 °
And 67.5 °, there are 8 connections. This is the sixth time
When 4 connected edges are deleted in the thinning processing of 22.
In the directions of 5 ° and 67.5 °, the distance is further reduced.
22.5 ° to prevent this.
And the sixth thinning process is performed in the 67.5 ° direction.
You have to be careful not to. For 9 pixels
The opposite is true when you think about it. As mentioned above (Table 1)
The correction of the second peripheral point is in the directions of 22.5 ° and 67.5 °.
Even if it is 4 connected edges, it is corrected in order to narrow it to the same distance.
Removed as a candidate for erasure by 8 edges
Indicates that it will be taken as a candidate for elimination by correction.
are doing.

[0017]

[Table 1]

Reference numeral 302 denotes a process for detecting a first peripheral point, in which the input image is scanned with a 3 × 3 window, 8 connected edges are detected using the values of pixels in 8 neighborhoods shown in FIG.
Give bell e. The 8-connected edge has a target pixel d0 of 1
If there is at least one 0 in the four neighboring pixels on the bottom left and right
Since it is good , the label e is given to the position of interest when the logical expression shown in (Equation 5) is true, and 0 is given when it is false. However, -is the logical product and ^- is the negation.

[0019]

[Equation 5]

Reference numeral 303 denotes a process for detecting the second peripheral point. When the 8-connected edge is detected according to the order of (Table 1), the operation of (Equation 5) is performed. Also detects 4 connected edges
In this case, the pixel of interest d0 is 1 and there are at least 8 neighboring pixels.
Since it suffices that there is one 0, the calculation of (Equation 6) is performed.
As a result of the calculation , the label k is given to the position of interest when the value of the expression is true, and 0 is given when it is false. Processes 302 and 303
Therefore, the label k is also added to the pixel position given the label e.
It is given at the same time, but conversely even if the label k is given
The label e is not always given. Given the label e
The determined pixel position is the first erasure determination in 308 described later.
And the label k
The obtained pixel position is used for the second erasing in 312 described later.
It means that the pixel is a determination target.

[0021]

[Equation 6]

The above procedure is continued until the scanning of the image is completed, and the detected edge information is output to the edge information storage memory 207 of FIG.

Reference numerals 304 and 305 denote processes for correcting the position of the label k detected as the second peripheral point, and the same position of the input image and the edge image on the memory 207 are 3 ×.
Scanning is performed in three windows to make correction determination. However, the presence / absence of correction in the thinning control table is referred to, and if there is no correction, no correction is performed and the contents of the memory 207 are directly stored in the memory 20.
Write to 8. When correction is required, correction determination is performed in 304, and the corrected edge information is written in 305. The correction conditions will be described below with reference to FIG. The same figure (a)
From (h) to (h) are shown patterns in the vicinity of 3 × 3 of the position to be corrected. In the figure, the position of 1 or 0 is referred to the input image to determine pattern matching, the position of k is referred to the edge image, and it is determined that the position is labeled k. If the pattern matches any one of (a) to (h), the edge information of the pixel of interest * is corrected at 305. That is, when the label k is attached to the position of the pixel of interest * in the edge image, the label k is removed,
On the contrary, when the label k is not attached, the label k is given to correct the edge position. When 4 or 8 connected edges are erased according to the order of the thinning control table, the pattern can be thinned at the same ratio in the horizontal / vertical / 45 ° directions.
The direction of 2.5 ° is narrowed faster or slower than the above direction. The correction processing is to control the erasing position of thinning so that the direction is also thinned in the direction of 22.5 °.

Reference numerals 307 to 314 are processes for determining whether or not thinning is to be performed. In step 306, a flag F indicating the presence or absence of erased pixels is reset in advance. At 307, the edge image from the edge information storage memory 207 is referred to,
If the label e is given as the edge information to the position of interest, the process of 308 is performed, and if the label e is not given, the next pixel is referred to and the determination of 307 is performed again. 308
Is a process of making an actual erasure decision with respect to the pixel detected as the first peripheral point. Image memory 20 of FIG.
4 and edge information storage memory 207, data in the vicinity of 3 × 3 of the pixel of interest is read out, and erase determination is performed.
The pixel of interest is erased when (Equation 7) is true using Condition 1, Condition 2 and Condition 3 shown below.

[0025]

[Equation 7]

Condition 1 is a condition for selecting a pixel in which the sum of 8 neighborhoods is 2 or more and the sum of 4 neighborhoods is 2 or less among the edge positions detected in 302, and the data from the image memory 204 (Equation 8) is selected. The truth of the expression shown in is judged. In condition 1, the sum of 8 neighborhoods is set to 2 or more in order to prevent the core wire from degenerating.

[0027]

[Equation 8]

The condition 2 is a condition for preserving the connectivity of the pattern, and the position without branch is selected in the 3 × 3 area.
In order to do so, the truth of the expression shown in (Equation 9) is judged for the data from the image memory 204.

[0029]

[Equation 9]

However, N4 is the number of 4 connections, N8 is the number of 8 connections, and the number of 4 connections and the number of 8 connections are 4 connections respectively.
The number of connections and the number of connections in the case of 8 connections are shown. What is the number of connections?
Commonly used in classifying pixel states in binary images
5 is a feature amount that is a neighboring area excluding the pixel of interest d0 in FIG.
A single connection that can be connected to d0 in d1 to d8 (Euler
It is the number of connected components in (Equation 1), and is generally expressed by (Equation 10).
It is known that ("Mori Sakakura: The basis of image recognition
Foundation [I], p. 53-56, published by Ohmsha (1986) "
In other words, the number of connections is centered on the target pixel d0.
When tracing the perimeter of a figure with a value of 1 in a 3x3 area
It shows the number of times the eye pixel d0 is reached, and naturally, four consecutive
There may be different results for the case of 8 and the case of 8
It Therefore, as shown in (Equation 9), the number of 4 connections is 8
The number of connections is also one, which means that even if one follows four connected pixels
Even if the 8-connected pixels are traced, when the circle goes around the periphery of the figure.
This is equivalent to hitting the eye pixel d0 only once.
Therefore, there is no branching in the 3 × 3 area as seen from the pixel of interest.
It will be good.

[0031]

[Equation 10]

Condition 3 is a condition for preventing disappearance of an isolated 2 × 2 pixel pattern, and refers to data from the edge information storage memory 207 and the image memory 204,
Whether or not the 3 × 3 neighborhood matches any of FIGS. 7A and 7B is determined. In the figure, the position of 1 or 0 refers to the input image to determine pattern matching, the position of e refers to the edge image, and the position of the label e
It is determined that is attached, and the blank position is undefined.

In the judgment of 307, it is detected in 306 whether or not the pixel of interest has been erased, and in the case of erasing, the erase flag F is set in 310. The above procedure is continued until the end of scanning, and the processing result is stored in the auxiliary memory 209 in FIG. The second erase determination will be described below. In 311 the edge image from the corrected edge information storage memory 208 is referred to, and a label k is added to the target position as edge information.
Is given, the processing of 312 is performed, and if the label k is not given, the next pixel is referred to and the determination of 311 is performed again. In 312, using the following condition 4, condition 5, condition 6 and condition 7, if (Equation 11) is true,
Erase the pixel of interest.

[0034]

[Equation 11]

Condition 4 is a condition for selecting a pixel having a total sum of 2 or more in 8 neighborhoods of the corrected edge position k, and it is determined whether the data from the auxiliary memory 209 is true or false in the equation shown in (Equation 12). To do. Under condition 4, the sum of 8 neighborhoods is 2
The above is to prevent the contraction of the core wire, for example, 8
It is also possible to describe by adding a new condition for preventing degeneracy to the condition that the total sum of neighborhoods is 1 or more.

[0036]

[Equation 12]

The condition 5 is a condition for preserving the connectivity of the pattern, and selects a position having no branch in the 3 × 3 area. Whether the data in the auxiliary memory 209 is true or false is determined in (Equation 9).

Condition 6 is a condition for preventing the disappearance of a line having a width of 2 pixels, and referring to the data from the auxiliary memory 209 and the memory 208 for storing the correction edge information, the vicinity of 3 × 3 is shown in FIG. Whether or not it matches any of the values shown in b) is determined. In the figure, the position of 1 or 0 refers to the input image to determine the pattern match, the position of k refers to the edge image, and it is determined that the label k is attached to the position, and the blank position is undefined. And Figure 8 here
The condition (a) is a condition for selecting the upper line of the horizontal 2 pixel width lines, and the condition of FIG. 8B is the condition for selecting the left side line of the vertical 2 pixel width lines. It is a condition to do.

The condition 7 is a condition for preventing a line having a width of 2 pixels in the diagonal direction from being degenerated, and is the auxiliary memory 209 and the memory 2.
Referring to the data from 08, 3 × 3 neighborhood is shown in FIG. 9 (a).
Whether or not it matches any of the items shown in (b) is determined. However, in FIG. 9, either X1 or X2 is 1.

In the judgment of 313, it is detected in 312 whether or not the pixel of interest is erased, and in the case of erasing, the erasure flag F is set in 314. The above procedure is continued until the end of scanning, and the processing result is stored in the image memory 205 of FIG.

Reference numeral 315 refers to the range image memory 206,
In the step of updating the distance value, in step 311, it is determined whether the pixel position without the label k is updated. No determination is made for pixels with label k. In the update determination, the number n indicating the thinning order is compared with the distance value D, and D = n is newly added to the pixel having the distance value D = n.
Give a distance value of (n + 1). However, when performing the first thinning (n = 1), the distance image memory 206 stores
It is assumed that the data of the pattern part "01" and the background "00" are prepared. The above process increments the distance value at the internal point of the pattern by 1, and can give the correct distance value to the pixel at the skeleton position.

Reference numeral 316 is a step for checking the thinning end condition. If the erasure flag F is 0, the thinning is finished. If it is not 0, the image in the image memory 205 is input and the thinning process is performed again from the step 302. Is executed and the processing result is stored in the image memory 204. That is, the memories 204 and 205 are used as an input image for each iteration of thinning.
Images are alternately input, the processing result is stored in the other image memory, and the process is repeated until the image does not change.

FIG. 10 shows an example of thinning a binary pattern having irregularities at the boundary by the thinning processing apparatus configured as described above. The numbers attached to the pixels in Figure 10 are smaller
The order in which they are erased by the processing is shown. Furthermore, the figure
The position of the labels e and k in each thinning process
It is shown that the label e has 8 rows for the figure.
It is given to the position of the connecting edge, and the label k is defined in (Table 1).
It is given to the position of the edge of the connected state. (Tsuma
1st time is 4 connected edges, 2nd time is 8 connected edges, 3
8th connection edge for the 4th time, 4th connection edge for the 4th time ...)
As shown in FIG. 3, the thinning process is performed once in step 30.
Label at candidate pixel positions to be deleted in 2 and 303
e and k, then in step 308 the label e
Is set as the pixel of interest in the first cycle
The erasure judgment is performed, and further, in step 312, the label is
The second cycle with the pixel for which k is given as the position of interest
The erasure judgment of Image with ◯ in Figure 10
A pixel is a pixel erased by the erase determination in the first cycle.
Pixels not marked with ◯ are erased in the second cycle.
This indicates that the pixel has been erased. Of the figure shown in FIG.
In this case, the core wire (image marked with ●
The core wire is obtained, and the core wire can be
Does not change. As is apparent from FIG. 10, the thinning processing apparatus according to the present embodiment can extract a good-quality core line without being affected by a pattern having irregularities at the boundary. Further, FIG. 11 shows a distance image of the pattern of FIG. 10, and shows that each pixel is given the shortest distance value to the background.

As described above, according to the present embodiment, the first erasure judging means 105 is provided for the edge position detected by the first peripheral point detecting means 102 so that the minute unevenness of the pattern boundary portion is formed in advance. The second peripheral point detecting means 103 controls and detects the 4-connected edge and the 8-connected edge according to the thinning order, and further, the peripheral point correcting means 107 is provided to detect the edge position in the predetermined thinning order. Since the position to be erased is controlled in the second erasure determination means 109 by the correction, the pattern can be thinned at an equal distance from the background in any direction of the pattern, and the distance conversion means 111 is provided to determine the internal point of the pattern. By updating the distance value, it is possible to obtain the core line and at the same time obtain the distance image having the shortest distance value to the background.

An example of measuring the width of the pattern using the core wire and the distance image thus obtained will be described with reference to FIG. In order to obtain the width W of the pattern, the distance image is referred to at the skeleton position, and the distance value of the 3 × 3 window is used to perform the calculation according to (Equation 13). The distance value of the pixel of interest is D0,
If the distance value of 8 neighborhoods is Di (i = 1 to 8)

[0046]

[Equation 13]

However, [j] int indicates an integer by truncating j. For example, W = 9 at the position 55 in FIG. 12, and a circle 56 inscribed in the pattern centered at the position 55 is shown.
The diameter can be measured, and if this process is applied to the inspection of the circuit pattern, it becomes possible to detect defects such as line thinning by comparison with the reference width.

An example of a hardware configuration for processing the above thinning at high speed will be described below with reference to the drawings.
13 and 14 are hardware configuration diagrams of the thinning processing apparatus according to the present invention, FIG. 13 is a block configuration diagram of the thinning processing apparatus, and FIG. 14 is a circuit configuration diagram of one thinning processing block in FIG. . In FIG. 13, 401 and 40
5 is an input and output image memory, 406 and 407, respectively.
Is a range image memory, and 402 to 404 are first to n-th thinning means. In the figure, it is assumed that the image memory 401 stores a binary pattern to be thinned, and the distance image memory 406 stores a distance image having a background of "00" and a pattern of "01". The present configuration differs from the embodiment of FIG. 2 in that in order to realize the thinning processing n times, one thinning processing is cascaded in n stages, and the edge information storage memories 206 and 20 in FIG.
7 and the storage capacity of the auxiliary memory 208 are reduced. FIG. 14 shows the configuration of a specific process in the one-step thinning process. In FIG. 14, 502 is a first peripheral point detecting means, 503 is a second peripheral point detecting means, and 504 is a first peripheral point detecting means.
Erasing determination means 505, second erasing determination means 506
Is a peripheral point correction means, and 507 is a distance conversion means. The above is the same as the processing configuration shown in FIG. The circuit configuration shown in FIG. 14 is characterized in that the image scanning method is one-way raster scanning, and a 3 × 3 scanning window is used to obtain data in the vicinity of 3 × 3 used in the processing of 502, 503, 504, and 505. The point is that pipeline processing is performed by providing We, Wb, Wf, Wk, Ws, and Wh, and connecting a 2-line buffer required for each window scan. In FIG. 14, 508 is a peripheral point detection storage means, 509 is a first peripheral point storage means, 510 is a first erasure determination storage means, and 511 is a second.
Peripheral point storage means 512, erase determination storage means 51,
3 is a peripheral point correction storage means, each of which is configured by using a line memory. Since window scanning using a line memory and a shift register is a general technique, detailed description of signal processing will be omitted, and the data processing operation in the circuit configuration of FIG. 14 will be described below. The image data from the input port 501 is written in the latest position of the scanning window We, and thereafter stored in the peripheral point detection storage means 508.
First peripheral point detecting means 502 and second peripheral point detecting means 5
Reference numeral 03 refers to the 3 × 3 neighborhood data 520 from the scanning window We and outputs edge data 521 and 522, respectively. The edge data 521 is read into the latest position of the scanning window Wb, and thereafter stored in the first peripheral point storage means 509. The edge data 522 is written in the latest position of the scanning window Wh, and thereafter stored in the peripheral point correction storage means 513. Next, the first erasure determination means 504 determines the edge data 523 from the scanning window Wb and the image data 5 from the scanning window Wf.
24, the erase determination of the first cycle is performed, the determination result data 526 is written in the latest position of the scanning window Ws,
After that, it is stored in the second erasure determination storage means 512. The peripheral point correction means 506 refers to the edge data 525 from the scanning window Wh and the image data 524 from the scanning window Wf,
The determination of the peripheral point correction is performed, the determination result data 527 is written in the latest position of the scanning window Wk, and thereafter stored in the second peripheral point storage unit 511. Further, the second erasure determination means 5
Reference numeral 05 refers to the edge data 528 from the scan window Wk and the image data 529 from the scan window Ws, performs the erase determination in the second cycle, and outputs the determination result data from the output port 541. The distance conversion means 507 is the distance data from the input port 540 and the peripheral point correction means 5.
The edge value 526 from 06 is referred to, the distance value is updated with respect to the internal point of the pattern, and the output port 5
Output from 41.

The above series of processing operations are performed in synchronization with a pixel clock (not shown). By connecting the processing blocks shown in FIG. 14 in an n-stage cascade connection, it is possible to speed up the thinning process n times and reduce the data storage capacity.

[0050]

As described above, according to the present invention, the first erasure determining means removes minute unevenness in the pattern boundary portion in advance from the edge position detected by the first peripheral point detecting means,
The second peripheral point detecting means controls and detects the 4-connected edge and the 8-connected edge according to the order of thinning, and further the peripheral point correcting means detects the 4 connected or 8 in the predetermined thinning order.
Since the connection edge position is corrected and the erasing position is controlled by the second erasing determination means, it is possible to make the distance equal to the background in any direction of the pattern. By updating the distance value, it is possible to obtain the core line and at the same time obtain the distance image having the shortest distance value to the background.

[Brief description of drawings]

FIG. 1 is a block connection diagram of a thinning processing apparatus according to an embodiment of the present invention.

FIG. 2 is a block connection diagram of a thinning processing device using a CPU according to an embodiment of the present invention.

FIG. 3 is an operation flowchart of the thinning processing apparatus.

FIG. 4 is an operation flowchart of the thinning processing apparatus.

FIG. 5 is a diagram showing a pixel arrangement in the vicinity of 3 × 3 by the thinning processing apparatus.

FIG. 6 is a diagram showing correction conditions in peripheral point correction by the thinning processing apparatus.

FIG. 7 is a diagram showing a judgment condition in condition 3 by the thinning device.

FIG. 8 is a diagram showing a judgment condition in condition 6 by the thinning device.

FIG. 9 is a diagram showing a judgment condition in Condition 7 by the thinning device.

FIG. 10 is a view showing an unevenness 2 at the boundary in the thinning device.
Value line thinned diagram

FIG. 11 is a conceptual diagram showing a distance image by distance conversion in the thinning device.

FIG. 12 is a conceptual diagram showing a method of measuring a pattern width from a core wire and a distance image by the thinning device.

FIG. 13 is a block connection diagram of a thinning processing apparatus according to another embodiment of the present invention.

FIG. 14 is a circuit diagram of one thinning processing block of the thinning device.

FIG. 15 is a conceptual diagram showing a core wire by a conventional thinning process.

[Explanation of symbols]

 101 Input Image Memory 102 First Peripheral Point Detection Means 103 Second Peripheral Point Detection Means 104 First Peripheral Point Storage Means 105 First Erasure Determination Means 106 Auxiliary Storage Means 107 Peripheral Point Correction Means 108 Second Peripheral Points Storage unit 109 Second erasure determination unit 110 Output image memory 111 Distance conversion unit 112 Distance image memory 201 CPU 202 ROM 203 Main memory 204 Image memory 205 Image memory 206 Distance image memory 207 Edge information storage memory 208 Corrected edge information storage Memory 209 Auxiliary memory 402 First thinning means 403 Second thinning means 404 nth thinning means 501 Input port 508 Peripheral point detection storage means 509 First peripheral point storage means 510 For first erasure determination Storage means 511 Second peripheral point storage means 512 second erasure determination storage means 513 peripheral point correction storage means 550 delay memory

Claims (1)

[Claims] 1. A thinning processing device which repeats a process of thinning a binary pattern of 1s and 0s from the background side by one layer and converts the binary pattern into a pattern having a width of 1 pixel . Peripheral point detection means and a predetermined order
A second peripheral point detecting means for detecting a 4-connected or 8-connected edge incidentally input image, a first peripheral point memory for storing two bits of edge information from the first and second peripheral point detecting means Means, the input image and the edge information detected by the first peripheral point storage means are referred to, and among the pixels at the edge position, the sum of the values of the eight neighboring pixels is 2 or more and the sum of the four neighboring pixel values. There were selected <br/>-option 2 following pixel as a first target pixel, first erase 3 × 3 neighborhood pattern of the input image and the edge image to erase the first target pixel when the predetermined condition is satisfied The determination means, the input image, and the edge information detected by the second peripheral point detection means are referenced to satisfy a predetermined condition.
When adding, rewrite the specified data of the edge information
Thus, the peripheral point correction means for correcting the edge position, the auxiliary storage means for storing the image data from the first erasure determination means, and the second peripheral point storage for storing the image data from the peripheral point correction means Means, the image data from the auxiliary storage means, and the edge information stored in the second peripheral point storage means are referred to, and a pixel having a sum total of 2 or more in eight neighborhoods of pixels at the edge position is a second target. select a pixel, storing a second removal determination means 3 × 3 neighborhood pattern of the input image and the edge image to erase the second target pixel when a predetermined condition is satisfied, a distance image with distance values from the background The distance image memory, the edge information stored in the second peripheral point storage means, and the distance value D from the distance image memory.
When the predetermined condition is satisfied, the distance value D is updated to D + 1.
A thinning processing apparatus comprising a distance conversion unit that is newly written again in the distance image memory .