JPS60250480A - Method of detecting linkage relation - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed Description of the Invention] [Field of Application of the Invention] The present invention detects whether points at algebraic positions specified from the outside are connected by a pattern on a detected binary i'll1I image. The present invention relates to a method for detecting whether or not the object is connected, and particularly relates to a connection relationship detection power method suitable for detecting connection relationships based on complex shape patterns.

[Background of the invention]

In order to detect defects such as 6:j1 disconnections and short circuits in circuit pattern inspections, we scan the circuit pattern with a linear sensor, etc. to detect a binary image of 4-2 f1 μm, and then detect the specific It may be necessary to check whether the points are connected by a pattern on the detected image. Methods for investigating the connection relationship between the patterns of 21i-i and 21i-i are described in Japanese Patent Publication No. 58-16217 f Connected Area Detection Method” and “A Study on Filling in Connected Areas and Numbering” (IEICE Technical Report T 1r). , 7 g-9) was known. However, these methods
The purpose is to separate and extract all connected patterns among the patterns (parts with values of 1 or 00) in the detected binary image.

For this reason, for example, when five independent patterns (each closed area is a level 1 pattern) exist in the form of a binary image as shown in Figure 1, 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 necessarily necessary to separate the pattern at all f and f. For example, if only the connection relationship between the three points marked with X in Fig. 1 can be detected. For this purpose, the label 1,4°5 is not necessary. In addition, if the entire target pattern is very complex, a method is used in which a single nonia sensor is used to detect, for example, a linearized 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 check their connectivity, as shown in Figure 2, when we reach detection line L1, labels 1 and 2 are It has been determined that the numbered turn 4 is still 'AIJ'. When this progresses further and reaches the detection line 12, the patterns with labels I and 2 are connected, so this must be stored in a table in memory. Figure 3 shows the structure of the table, with each label 1, 2
Address 1゜2 (actually, this is considered to be a relative address)) is assigned to correspond to G), and the data of its contents is that the patterns of labels 1 and 2 are still isolated. When the judgment is being made, labels 1 and 2 are written as they are. However, when we found out that these numbers were consecutive, we determined that the value of 71% of the data was
11 can be changed. FIG. 3 shows the state after this rewriting, % 4 knee lJ-, 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. 2 has n branches in one direction, a table like the one shown in FIG. 3 with n addresses is required.

As described above, when detecting a binary image using a linear sensor or the like using the conventional method and extracting the connection relationships of all the patterns, the connection relationships existing on the two images explained in Figure 1 The number of labels is equal to the number of labels of the pattern, and the extra labels required in the case of a pattern with multiple branches in the upward direction as explained in Fig. 2 (n - 1 in the case of n branches). Memory capacity is required to store everything. However, if the pattern to be detected is not a simple one as shown in Figures 1 and 2, but an extremely complex and large-scale circuit pattern, the working memory capacity described above becomes extremely large. [Objective of the Invention] An object of the present invention is to detect a connection relationship between points at multiple positions based on a pattern of two detected images without using a large-scale memory. An object of the present invention is to provide a method for detecting connected relationships.

[Summary of the invention]

The present invention assigns a different number to each point to be detected and associates it with an address in memory, and when a certain point is found on any pattern, it is used as a label for that pattern. Attach a number to that point and write it as data to the address corresponding to the point, and when different labels are attached to the same pattern, rewrite these to one of them on the memory using a predetermined method, Thus, the present invention is characterized in that arbitrary two points are determined to have a connection relationship only when the labels stored in the addresses corresponding to the points are the same, and only then.

[Embodiments of the invention]

Hereinafter, the present invention will be explained in detail with reference to examples. Now target! It is assumed that the pattern to be used is shown in FIG. 4, and grid numbers 1 to 6 are assigned to the points (hereinafter referred to as "grid points") that are related to each other.

When patterns are detected sequentially from the upper line in Figure 4 using a linear sensor, etc., and no grid points have been detected yet, each pattern has a common label I as shown in Figure 5. O is asked. Here, "labeling a pattern" means creating an area for each detected pattern in memory and writing a label symbol (number) in the label field in that area. The specific method will be described later.The work area corresponding to this pattern is different from the concatenation table T, which will be explained immediately later.

The label for "Now" is not limited to "O" and may be any label that is not included in the grid number.This is called a virtual grid number, but in the following, number 0 will be used. Next, consider a case where the detection progresses further and the situation shown in FIG. 6 is reached. Either one pattern is starting to diverge into two, or no grid points have been detected yet. However, if this label 0 is left attached, label O is a common label to all patterns for which no grid has been detected, so when a grid point is found in a branch pattern later, it will be The pattern becomes indistinguishable. Therefore, when a branch occurs in the pattern of label O like this, a number that is not in the grid number or virtual grid number and is always a dog (or smaller) than the grid number (this is called a temporary number) is attached as a temporary label. . 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. 7, this table T means that if the content of address A (i) is data D (I), a label D (I) is attached to the pattern to which grid A1 belongs. However, when ■ is a temporary number, it means that the label of the pattern with that temporary number ■ is D (1), and l) (I) =
When O is a grid point, it means that the g11 throat point has not been found yet, and when 1 is a temporary number, it means that the temporary number is still in use. do. At the time of Fig. 6, no grid points I=1 to 6 have been found, so D(I)=0.I=1 to
6, and (for 1-7, this branched pattern is D (7) = 7 in the sense that it is not connected to other labels but is connected to itself. Next, suppose that the detection progresses further and grid point 1 is detected for the first time as shown in Figure 8.At this time, grid point 1
has been discovered, but it is not yet in a connected relationship with patterns with other labels, so this pattern is given a label 1 and D (1) = 1 on table T.

Next, it is assumed that the pattern detection progresses roughly and grid point 2 is discovered as shown in FIG. Let the data in (2) be D (2) = 2. At this point, the table T looks like the one shown in Figure 11. However, at this time, the pattern in which point 2 was found contains all non-zero values. Since the label 7 is attached, it is necessary to unify this into one label so that one label is attached to one pattern.The general method for this is to add the same label to the same pattern as described above. Assuming that there are 2' labels α and β, read out D(α)=α! from table T, and if α=α1, stop here and set α0;α1.α~α1
Then read D(αI)=α2, and if α1=α2 then α0;
Let it be α2. Otherwise, if we repeat the operation of not reading D(α2) = α3, the method of creating table T guarantees that there is αk such that D(αl<) = α, so α = α0. This operation is shown in a flowchart in FIG. Execute this operation for β as well, find β0, use m+i+(αO2β0) as the label of this pattern, and if the temporary signal is always smaller than the grid signal, take max (α0.β0)), and then D of table T. (α) and DIA are also set to this value. In this case label 2
, 7, α0; 2, β0= as seen from Figure 11
7, so this pattern is labeled 2, and at the same time, D (2) and D (7) in table T are also assigned 2.

The concatenation table at this time actually looks like the one shown in Figure 13. Assume that pattern detection further progresses and grid point 3 is discovered as shown in FIG. In this case as well, as in the case where Grino-do point 2 is found, it branches to 1. :(The pattern on the i side is given the label 3 and υ(,ya)=3 is inserted by 4, but since this pattern already had the vrni label 7, the label unification process is performed. In this process, α
=3゜β=7 'C' J5S I) (3) = 3, so α0; α=3, but for β = 7, D(7) = 2 from Figure 13, so I explained it in Figure 12.
) is searched for D(2) and D(21=2 (Figure 13)), so β0=2, therefore the smaller 2 of α0.β0 is attached as a label to the pattern that found the grid point 3, and the resulting table is created. D(3) of 1゛ is also assumed to be 2. The table T at this time is shown in Fig. 15. If the detection progresses gradually and grid point 4 is discovered as shown in the 16th point 1. , in this case, processing is performed according to exactly the same rules as in the case of Fig. 10 where grid point 2 was found, and grid point 4 is found.
The label of the pattern with the pattern and the value of D(4) in table T are both set to 1.

FIG. 17 shows the table T at this time. Next, grid points 5 and 60 are found. The division process is exactly the same as that for grid point 1, and labels 5 and 6 are printed on each pattern. ) (i91'; S+). Suppose that the detection progresses further and the pattern of label 5 and the pattern of label 6 merge as shown in Fig. 2υ.

Hello @Ki, one high 4-tone has two labels α=5. Since β==6 appears, αO;5. After β0=6, the smaller 10,000 label 5 is added to this merged pattern and rewritten as p(ci),=5 (211th).

The concatenation table T shown in FIG. 21 obtained for the pattern shown in FIG.
．． If D (I) = D (,T) for J, then those grid points are connected, otherwise it shows that they are not connected.

In the above, the process of attaching a label to the detected pattern or rewriting the label is always performed, and for the purpose of explanation this has been expressed on the drawing, but here we will explain how to label this pattern. We will explain the specific method.

Assume that the binary image for one line detected by a linear sensor or the like at a current scanning time t is as shown in FIG. However, the pattern part is defined as level 1 by a thick line, and the intersection line (thick line) between this and the detection line is segmented from the left) Sl,
82, called Sa.

Furthermore, the starting point S of these segments is wt'〈Juku2t
〈... What are the coordinates of the end point? 1' (p2t(...
Since these can be easily detected, a line table LT1 having a leading address APb corresponding to each segment can be created as shown in FIG. Furthermore, all the labels in this table LTI are set to 0 (virtual labels) as initial values, and for example, when scanning, grid points (the coordinates of which are input in advance and given as a grid point position table) are set as initial values. segment S with
= above), write the number N of the grid point in the label 1 of that segment. Of course, in this case, the concatenation table Tl7)D(N) is always set to N as described above. All other labeling, rewriting, etc. can be done using the labels on this line table LTl, but since one line table like this can be created for each scan, all of these are stored separately. This results in a huge memory capacity. Therefore, in this embodiment, only two lines of memory are used: the line table LTI created at time t, and the line table LTO created at t-1, one time before. Of course, this table LTO has the same configuration as the table Ljl in FIG.
-1゜B2t-1,..., start point is u, s '-' (
u2 t-' (,・, , set the end point to 21"-" (y2
'-' (..., label Lt'-', L2'''1
..., etc., the line table LTo,,LT,,
A necessary and sufficient condition for each segment 3pt-1 and SI of 1 to be segments of the same pattern is that there is an overlapping part when both segments are written on the same line, and this is easily understood. □ ,1≧υ,ノ,′−1andyjJl−1≧pu ・・
- (1). Therefore line table LTO, LT
1, the segment 5zt-1, S7 that satisfies the formula (ri)
For all sets of t', they are sequentially processed as explained in Figs. transfer, next time point t+
The process moves to line scanning in step 1, creates new contents of table LTI, and repeats the above process. In this way, it is sufficient to store and manage the storage for labeling patterns by preparing only the line tables LTO and LTI for two lines.
You can work with a small amount of memory.

In order to detect connection relationships between grid points, it is necessary to secure a data area for the number of grids.
Although the concatenation table T of this embodiment is also complete, 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 is necessary for the number of patterns with branches, but overall it requires significantly less memory capacity than the conventional method of labeling all independent patterns on the detected image.

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. 6, the corresponding flag is set to 1 to indicate that the used temporary number is currently in use. FIG. 24 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.

When this happens, if a new branch occurs and the temporary label becomes 91, first search table T and 6 temporary 11
'Execute the process in Figure 12 for issue J with J=α17
, the resulting α0 is taken as the value of D(J). 202
When this is executed for i=5 to 8 in FIG. 4, α0=5 is obtained for all I, and the data range of the connected chifur T is rewritten as shown in FIG. 25. Next, line table LTO with the temporary number of table T obtained in this way
, rewrite the label for the segment of LT1 to the label of the rewritten daple T. For example, if the label of a segment in line table LTO or LTI is 6
Assuming that, from the result in Figure 24, this becomes 5 ■-
Can be replaced. Next, the labels of the two line tables LT O and L T 1 processed in this manner 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 processing, the number of temporary labels in use is reduced from 4 to 1, and a new temporary label can be assigned by selecting a temporary label whose flag is O again. The above processing corresponds to making the temporary labels (6 to 8 in the present example) that are unrelated to the subsequent processing, among the temporary labels assigned to the area that has already been processed, available for reuse.

FIG. 26 is a diagram showing an example of the configuration of an apparatus for concretely implementing the connection relationship detection method described above. Become.

First, in the pattern detection section, a pattern 2 illuminated by a light source 3 is photoelectrically converted using a combination lens 4 and a linear sensor 5, and after being amplified by an amplifier 6, a binarization circuit 7
and digital signal input interface 87.
Each detection line is input to the processing device 9 via i-.

In addition, in order to synchronize the detection of the two-dimensional pattern and the processing of each detection line, a signal is sent from the processing device 9 to the motor control circuit 11 via the interface circuit 10 every time the processing of each detection line is completed. When feeding, the sweater 12 moves the tiple 1 by a distance Wt in the feeding direction. On the other hand, the connection relationship detection processing is performed by the processing device 111''9゛C''.
The present invention is used in this processing method. The processing device 9 may be a microcomputer, a minicomputer, etc. equipped with software for executing the processing of the present invention, a device in which the software is converted into firmware and incorporated into a bit slice microcomputer, or a completely hardware-based processing device. There are various types available, including those that do. The processing by this processing device 9 is as described above, but to summarize, first, the number of the grid point to be detected and its coordinates are input into the processing device 9 from the keyboard 13 in advance, and a grid point position table is created inside the processing device 9. I'll keep it. Next, a concatenation table T and a line table t
, 'ro, i, and 'ri (labels, data, flags, etc. are all set to O), and scanning by the sensor is started. After scanning one line, creating a line full LTI, and writing to table T when there is a grid, line table L E) 0, J-L
Examine the connection relationship of the segments of T1. f l, Segment Sb of table LTO
Assuming that 8 units of segment 1 are connected and the labels of Sowa, et al. are LO, Ll, the following processing is performed according to the value of (LO, Ll).

(1) When t, o = o and L1 = 0 (IA) There are two or more segments 3, r (on table LTI connected to segment 3Lt-1 and l, N), and it is the label of SI Select one of the temporary labels whose flag is O in the concatenation table T and set L1=Lo=J. Further, the data at address A(J) is set to J, and the flag is set to 1.0 This is the processing when a branch occurs as shown in FIG.

(IB) If the multiplication condition in (IA) above does not hold, do nothing. Since there are no grid points yet and no branches have occurred, the virtual label 0 is left attached.

(In the case of false LO~0 and Ll-40, in this case, adding two labels to the same pattern is the processing of II;'i, which was performed by force, and first set Lo = α and ID in Fig. 12, J
41! Let α0, which was removed by going to k, be MO, and then ((L1
= α, αO obtained in the same way as C is Ml, and MG) is M = Wu) + (Mo, public) (this is a temporary number>grid point street number>virtual color If the inequality sign is reversed, set +3 [: min is set to max), and Lo=L1=M on the line tables LTO, L, and TI. Also, replace the table T as D (Mo) = D (Ml) = M. As a result, only the minimum number M is always found in the same pattern.

(3) If only one of lio and L 1 is 00, first O
Let L be the label that is not the same, then perform the processing in Figure 12 with L = α, and let the obtained α0 be M: Lo =
Let L1=M. As a result, segments connected to segments that already have a non-zero label are given the same label.

The embodiment shown in FIG. 26 above is an example of an apparatus in which the method of the present invention is utilized most effectively. This has the effect of being able to be detected.

FIG. 27 shows another configuration example of an apparatus using the method of the present invention, in which a TV camera 15 is used for pattern detection,
After storing the binary jiji image for one screen in the memory 16,
It reads and processes one line at a time. That is, the linear sensor 5, table 15, motor 1 of the device shown in FIG.
2. The TV camera 15 is used instead of the Tanabata control circuit 110, and therefore the entire device has -j>31. However, as mentioned in L, it requires an image memory of 6, and the memory capacity increases accordingly. Others are 1)
It is almost the same as the device u, and similar effects can be obtained.

〔Effect of the invention〕

According to the method of the present invention, labeling a pattern can be performed by
Because the inspection is limited to when a grid point is passed through, and when the pattern branches, connections between specific points on a large screen using balloons can be detected using a small operation memory. There is an effect that it can be done.

[Brief explanation of drawings]

Figures 1 to 3 are explanatory diagrams of the conventional connection relationship detection method;
The figure shows an example of a target pattern for detailed explanation of the present invention, and Figs. 5 to 21 show the process of detecting the connection relationship of back and -n in Fig. 4 by the method of the present invention. figure,
Figure 22 is an explanatory diagram of one detection line, the upper pattern segment and its coordinates, Figure 23 is an explanatory diagram of the line table, and Figures 24 and 25 are used temporary numbers that can be detected and reused. FIGS. 26 and 27, which are explanatory diagrams of a method for performing this, are diagrams each showing an example of the configuration of a detection device using the method of the present invention. 2... Pattern 5... Linear sensor 7... Binarization circuit 9... Processing device 15... TV camera 16
...Image memory T...Concatenation table LTO, LTI...Line table Jie I Closed No. 2 Figure box, 30th No. 4 Fat No. 1, S Figure No. Otsu Min 1 Construction γ Figure No. 60? Figure 70 Figure /4 - Figure 15 Figure 77 m, /l Figure /q Figure 20 Figure 2f Figure 22 Figure 23 Field 24 Figure 25 UEJ Figure 2

Claims (1)

[Claims] 1. In a connection relationship detection power method for detecting whether or not grid points to be detected are connected by a pattern while sequentially scanning a target pattern on a screen line by line, Grid position information for storing in advance different ordered grid codes and screen coordinates for each of the grid points, and a certain scanning point and one scanning point before that. a first line table and a second line table for storing, in association with each segment of each pattern detected as an intersection line between the growth line and the pattern, the coordinates of both ends thereof and the label of the pattern to which the segment belongs; Each of the above grid codes,
and a concatenation table for storing each of a plurality of mutually ordered provisional codes having a lower order than any of the grid codes in association with labels of patterns to which these codes belong; One of the grid codes or provisional codes is used as an input code on the concatenation table, and if the label corresponding to that input code is not equal to the input code, change that label and search for the corresponding label as the input code, and repeat this process. Label processing means extracts the code when the input code and the corresponding label are equal as the output code, and also sets the values of the labels in the first and second line tables and the concatenation table to either the grid code or the provisional code. Scanning is started by initializing a different virtual label, and at each scanning time point, if there is a grid point stored in the grid position table on the detected segment of the first line table, the code of the grid point is changed. is written as the label corresponding to the segment in the first line table and the label corresponding to the grid point in the concatenation table, and then
By comparing each segment locus m on the second line table, pairs of segments that are determined to belong to the same pattern are sequentially extracted, and if the segments have the same number turn as the segment on the second line table that has a virtual label, When there are a plurality of segments on the first line table that belong to the first line table, and each of them has a virtual label, one of the above unused temporary codes is assigned to the plurality of segments on the first line table. The first step is to write the corresponding label and the label corresponding to the temporary code on the concatenation table.
If only one of the segments of the first and second line tables belonging to the same pattern has a grid code or provisional code as a label, that code is used as an input code (°C) by the label processing means described above. If both the segments of the first and second line tables belonging to the same pattern are grid codes or temporary When the code has a label as a label, the negative output code is determined by the label processing means as all input codes for each code, and the code having a higher order than the two output codes is stored in the deep 1 and second line tables. 111 as the label of the segment and the label of the grid code or temporary code in the concatenation table.
Perform the third process of injecting, and if the above moxibustion! If any of the conditions of 1, 2nd or 3rd processing is met, no processing is performed.Thus, when all pairs of segments belonging to the same pattern are completed, the first line is completed. The area within the circle is transferred to the second line table and the next scan is started, and at the end of the scan, there are grid points with the same label on the connection table, and only those grid points are connected by the same pattern. ! knee fl+
2. A flag corresponding to each temporary code on the Maeden connection table is set to 1 when the temporary code is in use, and 0 when it is not used; 4. In general, when all the cough flags become l/:, each provisional code is input as an input code ♂ to activate the flag processing means, and if the resulting code is a provisional code, the corresponding output code is obtained. Out of all the temporary codes checked by the flag processing means so far, the corresponding flag of only the above output code is set to 1 and the other corresponding flags are set to 0, so that the used temporary code can be reused. A method for detecting a connected relationship according to item 1 of the scope of Patent H1s 51, characterized in that: