JPH07111736B2 - Thinning device - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention scrapes a pattern from the background side one layer at a time as a pre-processing for recognizing a binary pattern such as recognition of characters, drawings, fingerprints or defect inspection of a circuit pattern. The present invention relates to a thinning processing device for narrowing the width to one pixel.

[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. 11 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. 11 indicate the order in which the pixels are erased by thinning.
Indicates that they are pixels forming the core line. The reason why the unnecessary core line remains in FIG. 11 is that the pixels 121 and 122 do not satisfy the condition of (Equation 1) in the first and second processes, respectively, and are not selected as erasable peripheral points. There is a problem that unnecessary core wires are likely to remain under the influence of the noise of.

The present invention solves the above-mentioned problems of the prior art by reducing the erase cycle for thinning one layer,
It is an object of the present invention to provide a thinning processing apparatus that extracts a high-quality core wire that is less susceptible to noise around the pattern and that satisfies isotropicity and stability.

[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 .
A first erasure determining unit that erases the first target pixel when the pattern of 3 × 3 neighborhood is selected as the target pixel and satisfies a predetermined condition; By referring to the edge information obtained by the two peripheral point detecting means, a pixel having a total of 2 or more in 8 neighborhoods is selected as a second pixel of interest among the pixels at the edge position, and a 3 × 3 neighborhood pattern satisfies a predetermined condition. And a second erasure determination means for erasing the second pixel of interest .

[0012]

According to the present invention, in the above-mentioned structure, the sum of the pixels in the vicinity of 8 is 2 or more and the sum of the pixels in the vicinity of 4 is determined by the first erasure judging means with respect to the edge position detected by the first peripheral point detecting means. In order to select and erase not more than 2 pixels, the pixels that form the irregularities around the pattern are removed in advance, and in the second erasure determination means, the neighborhood of 8 with respect to the edge position detected by the second peripheral point detection means. All the erasable pixels having a total pixel count of 2 or more are erased, and the edge positions left uncut by the first erasure determination means are erased, so that thinning is performed uniformly without being affected by noise around the pattern. be able to. In the second peripheral point detecting means,
As the peripheral points to be detected, either the 4-connected edge or the 8-connected edge of the pattern is switched and detected in accordance with a predetermined order each time the thinning is repeated, so that the pattern is thinned equally in the horizontal / vertical direction and the diagonal direction. It is possible to obtain a core wire having no directivity.

[0013]

(Embodiment 1) A first 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 denotes a peripheral point storage unit that stores the edge information from the first and second peripheral point detection units 102 and 103, and 105 denotes a binary image from the image memory 101 and a first peripheral inspection from the peripheral point storage unit 104. Output means 10
With reference to the edge information detected by 2, the pixel whose sum of the values of the pixels in the neighborhood of 8 is 2 or more and the sum of the values of the pixels in the neighborhood of 4 is 2 or less is selected, and 3 ×
First erasure determination means for erasing the pixel of interest when patterns in the vicinity of three satisfy a predetermined condition, 106 is auxiliary storage means for storing the binary image from the first erasure determination means, 107 is auxiliary storage means 106. Binary image and peripheral point storage means 1
04, the edge information detected by the second peripheral point detection means 103 is referred to, and a pixel whose sum of the values of the eight neighboring pixels is 2 or more is selected, and 3 ×
A second erasure determination means for erasing the pixel of interest when the patterns in the vicinity of 3 satisfy a predetermined condition, and 108 is an image memory for storing the binary image from the second erasure determination means 107.

FIG. 2 is a block diagram of a thinning processing device using a CPU that repeats the above thinning processing to narrow the pattern to one pixel width. In FIG. 2, 202 is the first and second
, A ROM storing a control program for a thinning process including the peripheral point detection and the operation of 3 × 3 neighboring pixels in the first and second erasure determinations, 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 205 are image memories for storing input and output binary images in the thinning process, and 206 is an input detected by the first and second peripheral point detection. An edge information storage memory that stores image edge information, and an auxiliary memory 207 that stores an output image according to the first erasure determination. The operation of the thinning process in the CPU system of FIG. 2 will be briefly described below. C
The PU 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. The data is stored in the information storage memory 206. Next, the image data at the same position is read from the image memory 204 and the edge information storage memory 206 at the same time, the erasure judgment calculation is performed by the first erasure judgment means 105, and the calculation result is stored in the auxiliary memory 20.
Store in 7. Further, the image data from the edge information storage memory 206 and the auxiliary memory 207 is read, and the second data is read.
The erasure determination means performs the erase determination calculation, and the calculation result is the image memory 205 corresponding to the image memory 108 in FIG.
To store. By the above operation, the binary pattern of the image memory 204 is thinned by one layer from the background side and stored in the image memory 205. 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 core line of the pattern is extracted by repeating the process until the pattern has a width of one pixel.

With respect to the thinning processing apparatus configured as described above, the specific thinning processing will be described with reference to the flowcharts shown in FIGS. In the figure, 301 is the second
This is a step of reading the peripheral point detection control table in which the connection of edges to be detected in the peripheral point detection 303 is 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 Here, the 4-connected edge is the pixel of interest
Contour line with at least one 0 in 8 neighborhoods
Then, the 8 connected edges are 4 neighborhoods on the top, bottom, left and right as seen from the pixel
There is at least one 0 in the contour line. That is,
The 8-connected edge is included in the 4-connected edge. Also, (table
The order of edge connection described in 1) is one layer by thinning.
When erasing one edge, 4 connected edges and 8 connected edges
Edge of the edge to be erased.
Equalized in all 8 directions by thinning
The purpose is to narrow it down. For example, with a series of thinning processing
When 4 connected edges are deleted every time, the target figure becomes
The slanted direction is made thinner than the up, down, left, and right directions.
If you delete 8 connected edges every time,
Is narrower in the vertical and horizontal directions than in the horizontal direction.
It Therefore, edge erasure is controlled in the order shown in (Table 1).
Then, thin it evenly in all directions, vertically and horizontally.
You can This is because one thinning process in thinning is
Reduce the distance between the outline of the figure and the core that remains as a result of the thinning processing by 1
Since it is equivalent to tilting, the distance to be slanted in the direction of 45 °
In order to make the distance from the top and bottom and the left and right directions even,
Pixels with the same distance from the core in the diagonal 45 ° direction
The connection state and the connection of the edge that disappears with each thinning process
You just have to match the states and think like that
And the connection state of the edges to be erased in each thinning process is (Table
It is determined as in 1).

[0017]

[Table 1]

Reference numeral 302 denotes a process for detecting the first peripheral point, which is an 8-connected error using the values of pixels in the vicinity of 3 × 3 shown in FIG.
Edge is detected and a label e is given to the edge position. 8 connection d
In this case, the target pixel d0 is 1 and the number of pixels in
Since at least one 0 is required, if the logical expression shown in (Equation 5) is true, the label e is given to the target position, and if false, 0 is given. However, · is a logical product ^– indicates 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 erase determination in 306 described later.
And the label k
The determined pixel position is used for the second erasing in 310 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 206 of FIG. Further, at 304, the flag F indicating whether or not there is a pixel erased by the thinning of that time is reset in advance before performing the erase determination. Then 3
In 05, the edge image from the edge information storage memory 206 is referred to, the process of 306 is performed when the label e is provided as the edge information at the position of interest, and the next pixel is referred when the label e is not provided. 305 again
Is determined. 306 is a process of actually erasing the pixel detected as the first peripheral point. From the image memory 204 and the edge information storage memory 206 shown in FIG. 2, data in the vicinity of 3 × 3 of the pixel of interest is read out and an erase determination is performed. In 306, the following condition 1,
If (Equation 7) is true using Condition 2 and Condition 3, the pixel of interest is erased.

[0023]

[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). The truth of the expression shown in is judged. In condition 1, the reason why the sum total of 8 neighborhoods is 2 or more is to prevent the core wire from degenerating. For example, the condition that the sum total of 8 neighborhoods is 1 or more can be described by adding a new condition to prevent degeneracy. is there.

[0025]

[Equation 8]

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

[0027]

[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 circumference of a figure with a value of 1 in a 3x3 area
It indicates the number of times the pixel d0 is reached, and naturally 4 connections
There may be different results in case of 8 and in case of 8 connection.
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.

[0029]

[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 206 and the image memory 204,
Whether or not the 3 × 3 neighborhood matches any of FIGS. 6A and 6B is determined. In FIG. 6, the position of the label e refers to the data from the edge information storage memory 206, and the other positions refer to the data from the image memory 204. Blanks are 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 erasing flag F is set in 308. The above procedure is continued until the end of scanning, and the processing result is stored in the auxiliary memory 207 of FIG. The second erase determination will be described below. In 309, the edge image from the edge information storage memory 206 is referred to, the process of 310 is performed when the label k is provided as the edge information at the position of interest, and the next pixel is referred to when the label k is not provided. Then, the determination of 309 is performed again. In 310, if (Equation 11) is true using the following condition 4, condition 5, condition 6, and condition 7, the pixel of interest is erased.

[0032]

[Equation 11]

Condition 4 is a condition for selecting a pixel whose sum total of 8 neighborhoods is 2 or more among the edge positions detected in 303, and judges the truth or falseness of the formula shown in (Equation 12) for the data from the auxiliary memory 207. To do. In condition 4, the sum total of 8 neighborhoods is set to 2 or more in order to prevent the core wire from degenerating. For example, the condition that the sum total of 8 neighborhoods is 1 or more can be described by adding a new condition to prevent degeneracy. is there.

[0034]

[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 207 is true or false in (Equation 9) is determined.

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 207 and the edge information storage memory 206, 3 × 3 neighborhood is shown in FIG.
(A) A true / false decision is made as to whether or not it matches any of the cases shown in (b). In FIG. 7, the position of the label k refers to the data from the edge information storage memory 206, and the other positions refer to the data from the auxiliary memory 207. Here, the condition of FIG. 7A is a condition for selecting the upper line of the lines having a width of 2 pixels in the horizontal direction.
The condition (b) is a condition for selecting the line on the left side of the lines having a width of 2 pixels in the vertical direction.

The condition 7 is a condition for preventing the line of 2 pixels width in the diagonal direction from being degenerated, and the data from the auxiliary memory 207 and the memory 206 for storing edge information is referred to and 3 ×
True / False determination is performed as to whether or not the three neighborhoods match any of those shown in FIGS. However, in FIG. 8, X1 and X
Either 2 is 1.

In the judgment of 311, it is detected in 310 whether or not the pixel of interest has been erased, and in the case of erasing, the erasing flag F is set in 308. 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 313 is a step of checking the end condition of thinning. If the erasure flag F is 0, the thinning is finished, and if it is not 0, the image of the image memory 205 is input and 3
The thinning process is executed again from step 02, and the processing result is stored in the image memory 204. That is, the images in the memories 204 and 205 are alternately input as an input image for each repetition of thinning, the processing result is stored in the other image memory, and the process is repeated until the image does not change.

If the condition 3'is newly set in step 306 and the erasing condition (Equation 13) is true, the protrusion of 2 × 2 pixels at the pattern boundary portion as a result of the thinning process is the core line. Is saved as.

[0040]

[Equation 13]

The condition 3'refers to the data from the memory 206 for storing edge information and the data from the image memory 204, and the neighborhood of 3 × 3 is one of FIGS. 9 (a) (b) (c) (d). This is a condition for determining whether or not they match. In FIG. 9, the position of the label e refers to the data from the edge information storage memory 206, and the other positions refer to the data from the image memory 204.

FIG. 10 shows an example of thinning a binary pattern having irregularities at the boundary with 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 306 the label e
Is set as the pixel of interest in the first cycle
The erasure judgment is performed, and the label is added
The second cycle with the pixel for which k is given as the position of interest
The erasure judgment of In Figure 10, the image with a circle
A pixel is a pixel erased by the erase determination in the first cycle.
Pixels not marked with a circle are judged by the erase judgment 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. As shown in FIG. 11, in the conventional example, the pixel 121 is stored under the condition of the connectivity preservation (Equation 2) at the time of the first thinning processing. Since it is erased, the pixel 121
The pixel 91 corresponding to is erased without being affected by the connectivity preservation condition (Equation 9) and does not remain as an unnecessary core line. The equations (9) and (2) are equivalent conditions for preserving connectivity, but since the number of connections is generally used when analyzing a binary image, the number of connections is used in this embodiment. I used the notation. Further, as shown in FIG. 11, in the conventional example, the eight connected edges of the pattern are erased as the thinning process progresses, so that the horizontal and vertical directions are first thinned with respect to the diagonal direction. As shown in FIG. 10, the edge is erased according to the peripheral point detection control table (Table 1), so that the pattern can be thinned uniformly without directionality.

As described above, according to the present embodiment, the edge position detected by the first peripheral point detecting means 102 is 8
By providing the first erasure determination unit 105 that selects pixels whose total sum of neighborhoods is 2 or more and 4 whose total sum of neighborhoods is 2 or less, the pixels forming the irregularities of the pattern boundary portion are erased in advance, and the second In the erasure determination means 107, the edge position detected by the second peripheral point detection means 103 is
Pixels having a total sum of 2 or more in the vicinity of 8 are erased, so that a good-quality core line can be extracted without being affected by the unevenness of the pattern boundary portion. The second peripheral point detecting means 103 detects 4 connected edges and 8 connected edges in a predetermined order as peripheral points to be detected each time the thinning is repeated, so that the pattern is evenly distributed in the diagonal and vertical and horizontal directions. The core wire can be centered in the pattern.

An example of a hardware configuration for processing the above thinning at high speed will be described below with reference to the drawings.
12 and 13 are hardware configuration diagrams of the thinning processing apparatus according to the present invention, FIG. 12 is a block configuration diagram of the thinning processing apparatus, and FIG. 13 is a circuit configuration diagram of one thinning processing block in FIG. . In FIG. 12, 401 and 40
Reference numeral 5 denotes an input and output image memory, and 402 to 404.
Are first to nth thinning means. In this configuration, the difference from the embodiment of FIG. 2 is that, in order to realize thinning processing n times, one thinning processing is cascaded in n stages, and the edge information storage memory 206 and the auxiliary memory in FIG. This is a point to reduce the storage capacity of 207. 13 in FIG.
The structure of a specific process in the step thinning process is shown. Figure 1
3, 502 is a first peripheral point detecting means, 503 is a second peripheral point detecting means, 504 is a first erasing determination means,
Reference numeral 505 denotes a second erasing determination means, which has the same processing configuration as that shown in FIG. The circuit configuration shown in FIG. 13 is characterized in that the image scanning method is one-direction raster scanning, and 3 × used in the processing of 502, 503, 504, and 505.
3 × 3 scanning windows We, Wb,
The point is that pipeline processing is performed by providing Wf, Wk, and Ws, and connecting a 2-line buffer required for each window scan. In FIG. 13, 508 is a peripheral point detection storage means, 509 is a first peripheral point storage means, 510 is a first erasure determination storage means, 511 is a second peripheral point storage means, 5
Reference numeral 12 is an erasing determination 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 data processing operation in the circuit configuration of FIG. 13 will be described below. The image data from the input port 501 is read into the latest position of the scanning window We, and thereafter stored in the peripheral point detection storage means 508. The first peripheral point detecting means 502 and the second peripheral point detecting means 503 are 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. Further, the edge data 522 is delayed by two lines by the delay 507, read into the latest position of the scanning window Wk, and thereafter stored in the second erasure determination storage means 511. 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 525 is written in the latest position of the scanning window Ws,
After that, it is stored in the second erasure determination storage means 512. Further, the second erasure determination unit 505 uses the edge data 526 from the scanning window Wk and the image data 527 from the scanning window Ws.
The erasure judgment of the second cycle is carried out with reference to, and the judgment result data 528 is outputted from the output port 506. The above series of processing operations are performed in synchronization with a pixel clock (not shown). By connecting the processing blocks shown in FIG. 13 in an n-stage cascade connection, it is possible to speed up the thinning process n times and reduce the data storage capacity.

[0045]

As described above, the present invention is provided with the first and second peripheral point detecting means and the first and second erasing determining means, and the first erasing determining means detects the first peripheral point. With respect to the edge position detected by the means, a pixel having a sum total of 8 neighborhoods of 2 or more and a sum total of 4 neighborhoods of 2 or less is selected and an erasing determination is performed, and pixels forming unevenness of the pattern boundary are erased in advance, In the erasure determination means of No. 2, the pixels whose total sum of eight neighborhoods is two or more with respect to the edge position detected by the second peripheral point detection means are erased, so that it is not affected by the unevenness of the pattern boundary portion and is of good quality. The core line of can be extracted. Further, in the second peripheral point detecting means, by detecting 4 connected edges and 8 connected edges in a predetermined order as peripheral points to be detected at each repetition of thinning, the pattern can be thinned uniformly without directionality. Yes, you can bring the core to the center of the pattern.

[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.

FIG. 6 is a diagram showing a determination condition in a first erase determination by the device.

FIG. 7 is a diagram showing a determination condition in a second erase determination by the device.

FIG. 8 is a diagram showing a determination condition in a second erase determination by the device.

FIG. 9 is a diagram showing a determination condition in a first erase determination by the device.

FIG. 10 is a conceptual diagram showing a core wire by a thinning process in the same device.

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

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

FIG. 13 is a circuit diagram of a single thinning processing block of the device.

[Explanation of symbols]

 101 Input Image Memory 102 First Peripheral Point Detection Means 103 Second Peripheral Point Detection Means 104 Peripheral Point Storage Means 105 First Erasure Determination Means 106 Auxiliary Storage Means 107 Second Erasure Determination Means 108 Output Image Memory 201 CPU 202 ROM 203 Main memory 206 Edge information storage memory 207 Auxiliary memory 402 First thinning means 403 Second thinning means 404 nth thinning means 501 Input port 506 Output port 507 Delay memory 508 Peripheral point detection memory Means 509 First peripheral point storage means 510 First erasure determination storage means 511 Second peripheral point storage means 512 Second erasure determination storage means

Claims (1)

[Claims] 1. A 1 and repeat one layer by make narrow narrowing process from the background side binary pattern of 0, the thinning processing apparatus for converting a pattern of one pixel width, the detecting 8-connected edge of the input image 1 Peripheral point detection means and the thinning processing
The second peripheral point detecting means for detecting 4-connected or 8-connected edges of the input image and the edge information from the first and second peripheral point detecting means are stored in a predetermined order for each repetition of By referring to the peripheral point storage means, the input image, and the edge information by the first peripheral point detection means stored in the peripheral point storage means, the sum of the values of the eight neighboring pixels among the pixels at the edge position is 2 A pixel whose sum of the values of the pixels above and in the vicinity of 4 is 2 or less is selected as the first pixel of interest , and 3 ×
When the patterns in the vicinity of 3 satisfy a predetermined condition, the first
The first erasure determination means for erasing the pixel of interest, the auxiliary storage means for storing the image data from the first erasure determination means, the image data from the auxiliary storage means and the peripheral point storage means are stored. By referring to the edge information by the second peripheral point detection means, a pixel having a total sum of 2 or more in 8 neighborhoods is selected as a second pixel of interest among the pixels at the edge position, and a pattern of 3 × 3 neighborhoods meets a predetermined condition. When meeting the second attention
A thinning processing apparatus comprising: a second erasing determination means for erasing pixels .