JPH0444985B2 - - Google Patents

Description

[Detailed description of the invention]

[Field of Application of the Invention] The present invention relates to a connection method for quickly detecting whether or not the points are connected by a pattern when a plurality of points are specified on a pattern of a detected binary image. The present invention relates to a relationship detection device. [Background of the Invention] In circuit pattern inspection, etc., in order to detect defects such as wire breaks and shorts, the circuit pattern is imaged with a linear sensor, etc., and the image is converted into a binary image to obtain a binary image. It may be checked whether the spaces are connected by a pattern on the detected image. Methods for investigating the connection relationship between patterns in binary images include Japanese Patent Publication No. 58-16217 ``Method for Detecting Connected Areas'' and ``A Study on Filling in Connected Areas and Numbering'' (IEICE Technical Report IE78-
9) is known. but,
These methods aim to separate and extract all connected patterns among the patterns (portions where the value is 1 or 0) of the detected binary image. For this reason, for example, when five independent patterns (each closed region is a level 1 pattern) exist in the form of a binary image as shown in Figure 31, when these are processed using the above method, they are called labels. Numbers 1 to 5 are assigned to all patterns, and these are stored on memory in a table format. However, in order to inspect circuit patterns for disconnections, etc., it is not necessary to separate all such patterns.
For example, there may be a case where it is only necessary to detect the connection relationship between the three points marked with an x in FIG. 1, and in such a case, labels 1, 4, and 5 are unnecessary. If the entire target pattern is very complex, a method is used in which a linear sensor is used to detect the binarized image line by line in the horizontal direction while simultaneously detecting continuity. At this time, for example, if we sequentially detect the binarized images using horizontal detection lines from above and examine their connectivity, as shown in Fig. 32, when we reach detection line l ₁ , labels 1 and 2 are The attached pattern has been determined to be different. When this progresses further and reaches the detection line _l2 , it can be seen that the patterns with labels 1 and 2 are connected, so this must be stored in a table in memory. Figure 33 is a diagram showing the structure of the table, in which addresses 1 and 2 (which can actually be considered relative addresses) are assigned to each label 1 and 2, and the content data is In this case, when it is determined that the patterns of labels 1 and 2 are still isolated, labels 1 and 2 are written as they are. However, if it is found that these data are continuous, the data is rewritten to the smaller value. FIG. 33 shows the state after this rewriting, and it can be seen that the patterns with labels 1 and 2 are connected because their data are the same. If the pattern shown in FIG. 32 has n branches upward, a table with n addresses as shown in FIG. 33 is required. As described above, when extracting the connection relationships of all putters while detecting a binary image with a linear sensor etc. using the conventional method, it is necessary to The number of labels equal to the number of connected patterns and the extra labels required in the case of a pattern with multiple branches in the upward direction as explained in FIG.
-1 item) is required. However, the pattern to be detected is not as simple as in Figures 31 and 32;
In the case of extremely complex and large-scale circuit patterns, there is a problem in that the memory capacity for working as described above becomes extremely large. [Object of the Invention] An object of the present invention is to reduce the memory capacity by determining whether or not the points are connected by the pattern when a plurality of points are specified from the outside on a pattern of a detected binary image. Therefore, it is an object of the present invention to provide a connected relationship detection device that can detect connections at high speed. [Summary of the Invention] For this purpose, the present invention assigns a different number to each point whose connected relationship is to be detected and associates each point with an address in memory, so that when a certain point is found on any pattern, When issued, the number of the point is attached as a label of the pattern and written as data to the address corresponding to the point, and when different labels are attached to the same pattern, these are written in a predetermined method. This is done so that it can be determined that two arbitrary points are connected only when the labels stored in the addresses corresponding to the points are the same, by rewriting one of them on the memory. Specifically, it includes an image input section that preprocesses binary image signals, a code conversion section that detects pixel change addresses, a grid number assignment section that detects whether a specified point exists between pixel change addresses, and a pixel change address. It consists of a labeling processing section that detects connections on adjacent lines from addresses, etc., but a line buffer memory is installed between the image input section and the code conversion section, and a grid number assignment section and the code conversion section. By interposing a FIFO between the grid number assignment section and the labeling processing section, and a line table memory between the grid number assignment section and the labeling processing section, each section can perform parallel processing operations. . [Embodiments of the Invention] Hereinafter, the present invention will be described in detail after explaining its theoretical background. First, the theoretical background is that the target pattern is as shown in Figure 2, and the points (hereinafter referred to as grid points) whose connectivity is to be examined are assigned grid numbers 1 to 6. do. In a situation where no grid point has been detected when patterns are sequentially detected from the upper line in Figure 2 using a linear sensor, etc.,
A common label 0 is attached to each pattern as shown in FIG. "Label the pattern" here
This means that an area is created for each detected pattern in the memory, and a label symbol (number) is written in the label field in that area.The specific method will be described later. This pattern-compatible work area is different from the concatenation table T, which will be explained shortly. Now, the above label is not limited to 0, but can be any label that is not included in the grid number, and is called a virtual grid number, but below we will use the number 0. Next, consider a case where the detection progresses further and the situation shown in FIG. 4 is reached. One pattern has begun to diverge into two, but no grid points have been detected yet. However, if label 0 is left as it is, label 0 is a common label for all patterns for which no grid points have been detected, so when grid points are found in a branch pattern later, those and other It becomes impossible to distinguish between patterns. Therefore, when a branch occurs in the pattern with label 0 like this, a number that is not in the grid number or virtual grid number and is always larger (or smaller) than the grid number (this is called a temporary number) is used as a temporary label. attach Here, this temporary label is set to 7. Now, a connection table T for storing connection relationships between grid points will be described. As shown in FIG. 5, the concatenation table T has address A(I)
If the content of is data D(I), it means that the label D(I) is attached to the pattern to which grid point I belongs. However, when I is a temporary number, it means that the label of the pattern with that temporary number I is D(I), and D(I) = 0 means that when I is a grid point, that grid point is It means that it has not been found yet, and when I is a temporary number, it means that the temporary number has not been used yet. At the time of Fig. 4, no grid points I = 1 to 6 have been found, so as shown in Fig. 5, D(I) = 0, I = 1 to 6, and I =
For label 7, D(7)=7 means that this branched pattern is not yet connected to other labels but is connected to itself. Next, it is assumed that the detection progresses further and grid point 1 is detected for the first time as shown in FIG. At this time, grid point 1 has been found, but it is not yet connected to patterns with other labels, so this pattern is given a label of 1, and furthermore, it is written as D(1) on the connection table T.
= 1 (Figure 7). Next, it is assumed that the pattern detection progresses further and grid point 2 is discovered as shown in FIG. In this case, the label of the pattern in which point 2 was found is set to 2, and the data at address A(2) of the concatenation table T is set to D(2)=2. At this point, the concatenation table T is as shown in FIG. However, at this time, the pattern in which grid point 2 was found has already been assigned a label 7 other than 0, so it is possible to unify these labels into one label and assign one label to one pattern. Make it. The general method for this is to assume that the same pattern has two labels α and β as shown above, read D(α)=α ₁ in the concatenation table T, and α
If = α ₁ , stop here and set α ₀ = α ₁ . If α≠ then D
Read out (α ₁ ) = α ₂ and if α ₁ = α ₂ then set α ₀ = α ₂ .
Otherwise, if we repeat the operation of reading D(α ₂ ) = α ₃ , the method of creating table T guarantees that there will always be αk such that D(αk) = αk, so
Let αk= _α0 . This operation is shown in a flowchart in FIG. Execute this operation for β to find β ₀ , and set min (α ₀ , β ₀ ) as the label of this pattern (if the temporary signal is always smaller than the grid number, take max (α ₀ , β ₀ )) , Furthermore, D(α) and D(β) of the concatenation table T are also set to these values. In this case, α ₀ for labels 2 and 7 as shown in Figure 9.
=2, β ₀ =7, so this pattern is labeled 2, and at the same time D(2) and D(7) of table T are also assigned 2. The concatenation table T at this time becomes as shown in FIG. Assume that the pattern detection progresses further and grid point 3 is discovered as shown in FIG. In this case, as in the case where grid point 2 is discovered, the label 3 is attached to the pattern on the right side of the branch, and D(3)=3 is written, but since this pattern already had a label 7, the label A process of unification is performed. In this process, α = 3, β = 7, and D(3) = 3, so α ₀ = α = 3, but for β = 7, D(7) = 2 from Figure 11, so continue. As explained in Figure 10, D(2) is examined and D(2)
= 2 (Fig. 11), so β ₀ = 2, so the smaller 2 of α ₀ and β ₀ is attached as a label to the pattern that found grid point 3, and D(3) of the concatenation table T is also 2. At this time, table T is the 13th
As shown in the figure. If the detection progresses further and grid point 4 is discovered as shown in Fig. 14, in this case processing is performed according to exactly the same rules as in the case of Fig. 8 where grid point 2 was found, and grid point 4 is found.
Both the label of the pattern and the value of D(4) in the concatenation table T are set to 1. FIG. 15 shows the concatenation table T at this time. Next, grid points 5 and 6 are discovered as shown in Figure 16.
The processing at this time is exactly the same as that for grid point 1, in which labels 5 and 6 are attached to each pattern, and D(5)=5, D(6)=
6 (Figure 17). Suppose that the detection progresses further and the pattern of label 5 and the pattern of label 6 merge as shown in FIG. In this case, 1
Two patterns also have two labels α=5, β=
6 appears, so find α ₀ = 5 and β ₀ = 6 using the method explained in Figure 10, and label 5, the smaller of these, is attached to this merged pattern, and write D(6) = 5. It hatches (Figure 19). The concatenation table T in FIG. 19 obtained for the pattern in FIG. 2 as described above is Points are connected, otherwise they are not connected. In the above, the process of attaching a label to the detected pattern and furthermore rewriting the label is always performed, and for the purpose of explanation this is represented on the drawing, but here we will explain the specifics of labeling this pattern. I will explain the method. Assume that the binary image for one line detected by a linear sensor or the like at a certain scanning time point t is as shown in FIG. However, the pattern portion is defined as a level 1 by a thick line, and the intersection lines (thick lines) between this and the detection line are called segments S ₁ ^t , S ₂ ^t , and S ₃ ^t in order from the left. Furthermore, if the coordinates of the starting points of these segments are u ₁ ^t < u ₂ ^t <... and the coordinates of the end points are v ₁ ^t < v ₂ ^t <..., then since these can be easily detected, the beginning of each segment Line table LT1 with address API
can be made as shown in Figure 21. Furthermore, this table
The initial values for the labels of LT1 are all 0.
For example, if a grid point (this assumes that the coordinates have been input from the outside and given as a grid point position table) is found on a segment Si ^t during scanning, that segment will be displayed. Write the number N of the grid point in the label ^Lit. Of course, at this time, D(N) of the concatenation table T is also always set to N as described above. All other labeling, rewriting, etc. can be done using the labels on line table LT1, but since one line table like this can be created for each scan, it is best to store them all separately. That would require a huge amount of memory. Therefore, in this embodiment, line table LT1 created at time t
Then, only the memory for two lines of the line table LT0 created at t-1, one time before, is used. Of course, this line table LT0 has the same configuration as table LT1 in Fig. 21, and its segments
S ₁ ^t-1 , S ₂ ^t-1 ,…, starting point u ₁ ^t-1 < u ₂ ^t-1 <…, ending point
If v ₁ ^t-1 < v ₂ ^t-1 <..., and the labels are L ₁ ^t-1 , L ₂ ^t-1 ..., etc., each segment Si ^t-1 and Sj ^t-1 of line tables LT0 and LT1 A necessary and sufficient condition for these segments to be included in the same pattern is that when both segments are written on the same line, there is an overlapping part, and this can be easily seen if vj ^t ≥ ui ^t-1 and vi ^t-1 ≧uj ^t ……………(1). Therefore, with reference to line tables LT0 and LT1, all pairs of segments Si ^t-1 and Sj ^t that satisfy equation (1) are explained in FIGS. 3 to 19 assuming that they are on the same pattern. Processing like above is performed sequentially, and when it is completed, the line table LT
Transfer the contents of 1 to line table LT0,
The process moves on to scanning the line at the next time point t+1, creates new contents of the line table LT1, and repeats the above process. In this way, it is sufficient to prepare only the line tables LT0 and LT1 for two lines for storage management for labeling patterns, and the work can be done with a small memory capacity. In addition, in order to detect the connection relationship between grid points, it is necessary to secure a data area for the number of grid points.
This is also the case with the concatenated table T of this embodiment, but an extra portion corresponding to the working temporary label, that is, an extra data area for the temporary label when a branch occurs in the pattern is required. This requires a certain number of branches if there are branches, but overall the present invention, which focuses on grid points, requires significantly less memory capacity than the conventional method of labeling all independent patterns on the detected image. become. Note that if the number of patterns with branches is larger than expected and the temporary label table is insufficient, recovery can be performed using the following method. That is, a 1-bit flag is provided in the temporary number area of the concatenation table T. These flags are all initialized to 0 before starting processing. When these numbers are used one by one at the time of branching as shown in FIG. 4, the corresponding flag is set to 1 to indicate that the used temporary number is currently in use. FIG. 22 shows an example of a concatenation table T having such flags, and shows a case where all temporary numbers 5 to 8 have been used. If a new branch occurs in this situation and a temporary label is required,
First, the concatenation table T is searched, and the process shown in FIG. 10 is executed for each temporary number J with J=α, and the resultant α ₀ is taken as the value of D(J). I= in Figure 22
5 to 8, α ₀ =5 is obtained for all I, and the data row of the concatenation table T is rewritten as shown in FIG. Next, the labels for the segments of line tables LT0 and LT1 that have the provisional numbers of the concatenation table T obtained in this way are rewritten to the labels of the concatenation table T that have just been rewritten. For example, line table LT0 or
If the label of a certain segment of LT1 is 6, this is rewritten to 5 from the result of FIG. 22. Next, the labels of the two line tables LT0 and LT1 processed in this way are searched for temporary labels (5 to 8 in this case). The flag of the discovered temporary label (5 in this case) is set to 1, and the other flags are set to 0. This result is shown in the flag box in FIG. With the above process, the number of temporary labels in use has changed from 4 to 1.
By selecting the temporary label whose flag is 0 again, it becomes possible to assign a new temporary label. The above process means that among the temporary labels assigned to the area that has already been processed, temporary labels (6 to 8 in the present example) that are unrelated to the subsequent process can be reused. Now, the connection relationship detection device according to the present invention will be specifically explained. FIG. 1 shows the overall configuration of one example. To explain the outline of its configuration and operation, a serial binary image signal from an image detection device, for example a linear sensor, is sent via an image input section 1 and a switching circuit 2 to line buffer memories 3A and 3B alternately. , and is temporarily stored line by line. Table 1
is the operation of the switching circuit 2, that is, which of the line buffer memories 3A and 3B receives the binary image signal from the image input section, and from which the binary image signal is read out is determined in relation to the line position. This is what is shown.

[Table] As can be seen from Table 1, the binary image signals of the previous line are serially read out alternately from the line buffer memories 3A and 3B via the switching circuit 2 to the code converter 4, and From the value image signal, the addresses (coordinate positions) of segments on the line and their starting and ending points are detected. That is, in the code converter 4, the binary image signal is 0.
The segment, its start point, and end point address are detected, with the address at the time it changes from 1 to 1 as the start point address of that segment, and the address at the time it changes from 1 to 0 for the first time after this as the end point address. It is. The start point address and end point address corresponding to a segment are paired and stored for temporary storage each time a segment is detected.
The data is sequentially written into a FIFO (First In First Out) 5, and the starting point address and ending point address are read out as a pair from the FIFO 5 in a first-in, first-out format to the grid number allocating unit 6. The grid number assignment unit 6 detects whether or not a grid point exists on the segment defined by the start point address and the end point address. The grid points are detected by referring to the grid point position coordinates from the memory 10. If a grid point exists in this detection, a label is attached to that segment, and the label is written alternately to any one of the line table memories 8A to 8C via the switching circuit 7 along with the start point address and end point address. It is. Table 2
Depending on the operation of the switching circuit 7, that is, the line position, the output of the grid number allocating section 6 is inputted to any of the line table memories 8A to 8C, and the labeling processing section 14 is inputted to any of the line table memories 8A to 8C.
This shows whether the read output from any of the 8C is input.

〔Effect of the invention〕

As explained above, in the case of the present invention, the image input section, code conversion section, grid number assignment section, and labeling processing section are divided into an image input section, a code conversion section, a grid number assignment section, and a labeling processing section. Since the data processing is performed via the link table memory, there is an effect that the memory capacity of the concatenated table memory can be reduced and processing can be performed at high speed.

[Brief explanation of drawings]

FIG. 1 is a diagram showing the overall configuration of an example of the connection relationship detection device according to the present invention, and FIGS. 2, 3, 4, 5, 6, 7, and 8 , 9th
Figure, Figure 10, Figure 11, Figure 12, Figure 13,
Figure 14, Figure 15, Figure 16, Figure 17, Figure 1
Figure 8, Figure 19, Figure 20, Figure 21, Figure 22
23 are diagrams for explaining the connection relationship detection method according to the present invention, and FIG. 24 is a diagram showing the storage of grid point position coordinates and corresponding grid numbers on the grid point position table memory according to the present invention. FIG. 25 is a diagram showing the format, and FIG. 25 is a diagram showing a circuit consisting of buffer memory and a switching circuit in place of FIFO. FIG. 26 is a diagram for explaining the access control method to the concatenated table memory.
28, 29, and 30 respectively show an image input section, a code conversion section, a grid point number assignment section,
FIG. 3 shows the configuration of an example of the labeling processing unit.
FIG. 1, FIG. 32, and FIG. 33 are diagrams for explaining the conventional connection relationship detection method. 1... Image input section, 2, 7... Switching circuit, 3A, 3
B...Line buffer memory, 4...Code converter,
5...FIFO, 6...Grid number assignment section, 8A, 8
B, 8C... Line table memory, 10... Grid point position table memory, 12... Connection table memory, 14... Labeling processing unit.

Claims (1)

[Claims] 1 An image input section that generates a write address for each pixel included in each line-corresponding binary image signal input serially, and an image input section that generates a write address for each pixel included in each line-corresponding binary image signal that is input serially, and that temporarily temporarily writes the binary image signal from the input section alternately every time a line is updated. A two-sided line buffer memory in which binary image signals corresponding to the previous line are stored and read out alternately each time a line is updated; A code conversion unit that detects pixel change addresses from 0 to 1 and from 1 to 0 from the image signal, and a line buffer for binary image signals, which is interposed between the image input unit, line buffer memory, and code conversion unit. A switching circuit that switches and controls temporary storage in the memory and readout from the memory, a FIFO that temporarily stores the pixel change addresses from 0 to 1 and 1 to 0 from the code conversion section as a pair, and The grid point position table memory, in which the position addresses of multiple points are stored in advance, and the grid point position table memory are referred to to determine whether or not the specified point exists between the pixel change addresses as a pair from the FIFO. a grid number allocating unit that detects the pixel change address as a pair and attaches a label to the pixel change address in a predetermined manner; A three-sided line table memory in which pixel change addresses and labels attached to the addresses are read out alternately as pairs corresponding to lines and lines before the previous line, and pixel change addresses on adjacent lines are read out in pairs based on the pixel change addresses from the memory. A labeling processing section detects the connection relationship between the pixel change address and the labeling processing section, which changes the label to a predetermined value, and the grid number allocation section, the line table memory, and the labeling processing section. Temporary storage of labeled labels in line table memory,
a switching circuit that switches and controls reading from the memory;
A connection relationship detecting device comprising: a connection table memory in which the labels corresponding to the plurality of points are stored in an updatable manner by the grid number allocating section and the labeling processing section.