Source: http://www.google.com/patents/US4953224?dq=5083039
Timestamp: 2014-03-09 19:53:09
Document Index: 366894384

Matched Legal Cases: ['art 14', 'art 4', 'art 6', 'art 14', 'art 4', 'art 6', 'art 14', 'art 4', 'art 6', 'art 4', 'art 6', 'art 6', 'art 1', 'art 4', 'art 14', 'art 1', 'art 4', 'art 6', 'art 14', 'art 1', 'art 4', 'art 6', 'art 14', 'art 14', 'art 4', 'art 6', 'art 4', 'art 6', 'art 14', 'art 4', 'art 6', 'art 14', 'art 14', 'art 6', 'art 14', 'art 6', 'art 1', 'art 4', 'art 6', 'art 14', 'in fine']

Patent US4953224 - Pattern defects detection method and apparatus - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsA pattern defect detecting method and apparatus are disclosed on a connectivity processor to input a binary picture signal pattern and a pad position coordinate and outputting connectivity data between pads. Here, the connectivity processing refers to a processing for giving the identical number to one...http://www.google.com/patents/US4953224?utm_source=gb-gplus-sharePatent US4953224 - Pattern defects detection method and apparatusAdvanced Patent SearchPublication numberUS4953224 APublication typeGrantApplication numberUS 07/158,125Publication dateAug 28, 1990Filing dateFeb 16, 1988Priority dateSep 27, 1984Fee statusPaidPublication number07158125, 158125, US 4953224 A, US 4953224A, US-A-4953224, US4953224 A, US4953224AInventorsToshiaki Ichinose, Yasuo Nakagawa, Takanori NinomiyaOriginal AssigneeHitachi, Ltd.Export CitationBiBTeX, EndNote, RefManPatent Citations (14), Referenced by (45), Classifications (6), Legal Events (4) External Links: USPTO, USPTO Assignment, EspacenetPattern defects detection method and apparatusUS 4953224 AAbstract A pattern defect detecting method and apparatus are disclosed on a connectivity processor to input a binary picture signal pattern and a pad position coordinate and outputting connectivity data between pads. Here, the connectivity processing refers to a processing for giving the identical number to one aggregation of connected or linked pads for the pads given to a serial pattern. In the connectivity processor wherein a plane on which the drawn pattern to be inspected is scanned by a linear sensor, the connectivity processing can be releazed almost concurrently with the scanning by driving a temporary memory.
What is claimed is: 1. An apparatus for detecting a defect of a pattern comprising:image pickup means for sensing an optical image of a pattern on an XY plane by scanning individual lines along the X-direction and line-by-line along a subscanning Y-direction for providing an electrical image signal; a binary digitizing circuit which transforms said electrical image signal into corresponding binary signals representing picture elements; a connection data generator including:a pad position table memory for storing pad position coordinates (Xi, Yi) with representative pad numbers Ni, line segment generation means for generating a start position u and an end position v, in the X coordinate, of a line segment of the pattern detected along a main scanning line, pad number assigning means for assigning said pad number Ni as labels to a line segment when said pad position coordinates (Xi, Yi) satisfy a condition u≦Xi≦v, labelling means for determining that a label representation M corresponds to the minimum label value representation of a first label value M.sub.0 and a second label value M.sub.1 when a corresponding first line segment is determined as being connected along the subscanning direction Y to a corresponding second line segment, said first label M.sub.0 and second label M.sub.1 correspond to the detection of line segments, as represented by pad numbers Ni, detected along respective adjacent scanning lines, and wherein said label representation M corresponds to a label value M.sub.2 when said first line segment is connected to said second line segment and one of said two line segments has the label value representation M.sub.2 and the other one of said line segments has no representative label value assigned, and assigning M to said first and second line segments, and a connectivity table memory for storing the connection data signals representative of a connectivity relationship expressed by said minimum label signal M as a data D(I) corresponding to address A(I) of said first and second label signals M.sub.0 and M.sub.1, respectively, showing said pad positions; and comparison means for comparing said connection data signals read out from said connectivity table memory of said connection data generator with design data signals expressed in the form of a cyclic list of symbols assigned to pads in the connectivity relationship, whereby a determination of a defect of the pattern is made based on the output of said comparison means. 2. An apparatus according to claim 1, wherein said pattern comprises a wiring pattern.
7. An apparatus for detecting a defect of a pattern comprising:image pickup means for sensing optical images of both a reference circuit pattern, being provided prior to effecting a defect detection process, and a corresponding circuit pattern for inspection on an XY plane by scanning individual lines along the X-direction and line-by-line along a subscanning Y-direction direction for providing electrical image signals representative of both said reference circuit pattern and said circuit pattern for inspection; a binary digitizing circuit which transforms said electrical image signals representative of both said reference circuit pattern and said circuit pattern for inspection into corresponding binary signals representing picture elements of both; a connection data generator including:a pad position table memory for storing pad position coordinates (Xi, Yi) with representative pad numbers Ni, line segment generation means for generating a start position u and an end position v, in the X coordinate, of a line segment detected along a main scanning line of both circuit patterns,pad number assigning means for assigning said pad number Ni as labels to a line segment of each of said circuit patterns when said pad position coordinates (Xi, Yi) satisfy a condition u≦Xi≦v and Yi=Y coordinate of said main scanning line, labeling means for determining that a label representation M corresponds to the minimum label value representation of a first label value M.sub.0 and a second label value M.sub.1 when a corresponding first line segment of each of said circuit patterns is determined as being connected along the subscanning direction Y to a corresponding second line segment of each of said circuit patterns, said first label M.sub.0 and second label M.sub.1 correspond to the detection of line segments as represented by pad numbers Ni, detected along respective adjacent scanning lines, and wherein said label representation M corresponds to a label value M.sub.2 when said first line segment is connected to said second line segment and one of said two line segments has the label value representation M.sub.2 and the other one of said line segments has no representative label value assigned, and assigning M to said first and second line segments of each of said circuit patterns, and a connectivity table memory for storing the connection data signals representative of a connectivity relationship expressed by said minimum label signal M as a data D(1) corresponding to address A(1) of said first and second label signals M.sub.0 and M.sub.1, respectively, showing said pad positions of each of said circuit patterns; design data generating means for converting said connection data signals read out from said connectivity table memory of said connection data generator and produced with respect to said reference circuit pattern, prior to said defect detection process, into corresponding design data expressed in the form of a circulation list of pad numbers Ni assigned to pads in the connectivity relationship representative of said reference circuit pattern; design data storing means for storing said design data; and comparison means for comparing said connection data signals read out from said connectivity table memory of said connection data generator and being produced with respect to said circuit pattern for inspection with said corresponding design data signals read out from said design data storing means which are representative of said reference circuit pattern, whereby a determination of the defect of the inspecting circuit pattern is made based on the output of said comparison means. Description
The theoretical basis will now be discussed for detailed description of the invention. &lt;Theoretical Basis&gt;
A connectivity table T for storing connectivities between specific points will now be described. The connectivity table T is stored in a connectivity table memory 12 in FIG. 1, and the table consists of an address part a data part, as shown in FIG. 5. Then the situation is such that a label data D(I) is given to the pattern of which address I and to which a pad number I belongs. In the case where reference character I is a pad number and D(I)=0, the specific point on the pad has not yet been found. In the case where reference character I is a temporary number and D(I)≠0, a label of the pattern to which the temporary number I belongs is data D(I). In the case where reference character I is a temporary number and D(I)=0, the temporary number has not yet been used a pattern with the tentative number I is D(I), and D(I)=0 represents the case where the grid has not yet been found when I is a grid and also the case where the tentative number has not yet been used when I is a tentative number. At that point in time of FIG. 4, no specific points I=1 to 6 are found, therefore the data D(I)=0, I=1 to 6 as shown in FIG. 5, and for address I=7, the branched patterns are still not concatenated with other patterns with labels, but concatenated with itself consequently to D(7)=7. Next, the assumption is that the detection proceeds to find a specific point 1 for the first time as shown in FIG. 6. In this case, the specific point 1 has been found but is not concatenated with a pattern having another label (pad number), therefore a label 1 is given to the pattern, and further the data D(1)=1 (FIG. 7) on the connectivity table T. Then, the detection proceeds to find a specific point 2 as shown in FIG. 8. In this case, the pattern in which the specific point 2 is found is labeled 2 and then the data at an address 2 of the connectivity table T is made to D(2)=2. At this point in time, the connectivity table T corresponds to that shown in FIG. 9. In this case, however, the pattern in which the specific point 2 has been found is already labeled 7 other than 0, therefore it is unified to one label for labeling with it to one connected pattern. Assuming now two labels α, β are assigned to the same pattern as described, a general method is such that a representative label α.sub.0, β.sub.0, respectively, should be selected. In the case shown in FIG. 9, 1, 2 and 7 are representative labels. That is, an address and the corresponding data correspond to the same numbers in a representative label.
A method of selecting a representative label α.sub.0 from a given label α is, as shown in FIG. 10, to repeat replacing α with D(α) until D(α)=α.
The operation is also executed on β to obtain β.sub.O, the pattern is only labeled with min (α.sub.0, β.sub.0) (or max (α.sub.0, β.sub.0) when a temporary number is smaller than the pad number at all times), and further D(α), D(β) of the connectivity table T are given at the value. In this case, α.sub.0 =2, β.sub.0 =7 to the labels 2,7 as will be apparent from FIG. 9, therefore the pattern is labeled 2, and D(2), D(7) of the table T are also given at 2 at the same time. The connectivity table T stands as FIG. 11 in this case.
Let it be assumed that the detection is furthered and thus the specific point 3 is found as shown in FIG. 12. As in the case where the specific point 2 was found, first the branched pattern on the right side is labeled 3 on table in FIG. 13 in this case, and D(3)=3 is also written; however, since the pattern is already labeled 7 on segment in FIG. 12, a processing for unification of the labels is carried out. In the processing α=3, β=7 and D(3)=3, therefore α.sub.0 =α=3. However, D(7)=2 to β=7 from FIG. 11; therefore, D(2) is checked consecutively as described in FIG. 10 and D(2)=2 (FIG. 11), so that β.sub.0 =2. Consequently, 2 of α.sub.0, β.sub.0, whichever is smaller is assigned to the pattern in which the specific point 3 is found as a label, and D(3) of the connectivity table T is also assigned at 2. The table T in this case becomes at last as shown in FIG. 13. Assuming that detection continues and proceeds downward and a specific point 4 is found as shown in FIG. 14, processing is performed in this case by exactly the same regulation as in the case of FIG. 12 obtained from FIG. 8, where the specific point 2 was found. A label for the pattern in which the specific point 4 was found and a value D(4) of the connectivity table T are both given at 1. FIG. 15 becomes at last the connectivity table T in this case. Then, specific points 5, 6 are found as shown in FIG. 16, however, processing in this case is exactly the same as in the case of the specific point 1, the patterns are labeled 5, 6, and D(5)=5, D(6)=6 (FIG. 17) in the connectivity table T. Let it be assumed that detection is furthered, and the pattern of the label 5 and a pattern of the label 6 join each other. In this case, two labels α=5, β=6 also appear on one pattern, therefore α.sub.0 =5, β.sub.0 =6 are obtained through the method described in FIG. 10, the label 5 of those whichever smaller is given to the pattern having joined as mentioned and rewritten as D(6)=5 (FIG. 19).
&lt;LABELING&gt; As described above, a label is assigned to a detected pattern, and the label is further rewritten to a normal processing, which is represented on the drawings, and a specific method for labeling the pattern will now be described.
Let it be assumed now that a binary picture image for one line which is detected on a linear sensor or the like at a scanning time t is as shown in FIG. 20. In the drawing, a pattern portion is given as a level 1 in binary logic at the thick line, and lines of intersection (thick lines) with the detection line are called segments S.sub.1.sup.t, S.sub.2.sup.t, S.sub.3.sup.t from left to right in that order. Further, from giving coordinates of start points of the segments as u.sub.1.sup.t &lt;u.sub.2.sup.t &lt; . . . and those of end points as v.sub.1.sup.t &lt;v.sub.2.sup.t &lt; . . . , since these can be detected, a line table LT1 having a leading address APi corresponding to each segment can be prepared as shown in FIG. 21. Further, 0 (virtual label) is set as an initial value in a label field of the table LT1, and, for example, if the specific point (the coordinate being input externally beforehand and given as a pad position on table memory 10) is found on a segment Si.sup.t at the time of scanning, the pad number N is written in a label Li.sup.t of the segment. It is evident that D(N) of the connectivity table T is also given as N at all times in this case as described hereinabove. Other labeling, rewriting and the like may be effected all in the label field on the line table LT1, however, such a line table is prepared line by line at each scann, therefore storing these all separately would require vast memory capacity. In the embodiment, therefore, only a memory for two lines of the line table LT1 created at the time t and a line table LT0 created at a time t-1 are used. The line table LT0 is also similar in construction to the table LT1 of FIG. 21, and where the segments are S.sub.1.sup.t-1, S.sub.2.sup.t-1, . . . , the start points are u.sub.1.sup.t-1 &lt;u.sub.2.sup.t-1 &lt; . . . , the end points are v.sub.1.sup.t-1 &lt;v.sub.2.sup.t-1 &lt; . . . , and the labels are L.sub.1.sup.t-1, L.sub.2.sup.t-1 . . . , the requirement for each segment Si.sup.t-1 and Sj.sup.t of the line tables LT0, LT1 to be included in the same pattern will be met by a presence of overlap when both segments are written on the same line, which may be represented apparently by:
vj.sup.t &#8807;ui.sup.t-1 and vi.sup.t-1 &#8807;uj.sup.t(1)
Accordingly, processing described in FIG. 3 to FIG. 19 are carried out sequentially on all sets of the segments Si.sup.t-1, sj.sup.t satisfying the expression (1) for these coming on the same pattern with reference to the line tables LT0, LT1, and when these are over, a content of the line table LT1 is transferred straight to the line table LT0, a scanning of the line at the next time t+1 ensues to update the content of the line table LT1, and the above-mentioned processing is then repeated. Thus, a memory control for pattern labeling will be achieved simply by preparing the line tables LT0, LT1 for two lines, and a small memory capacity is ready for working. Further, a data area for the number of pads must be secured for detecting connectivity between pads, so that the connectivity table T of the embodiment is arranged so as to cope therewith, however, a portion coordinated with a working temporary label, namely an extra data area of the temporary label when a pattern branches is also necessary. This may be necessary with the number dealing with the branch, and as compared with the conventional method of labeling all independent patterns on the detected image, a relatively small memory capacity will be available as a whole for the invention wherein specific points are inspected.
Then, if the number of branch patterns exceeds that which was originally present, so that a table for temporary labels becomes short, the following method is effective for restoration. That is, 1-bit flag is provided in area of the temporary number of the connectivity table T. The flags are all initialized to 0 during the state prior to starting the processing. When these are used one by one at the time of detecting the branch as shown in FIG. 4, a coordinated flag remains set to 1 to indicate the temporary number that is currently used. FIG. 22 shows an example of the connectivity table T having such flags, indicating the case where temporary numbers 5 to 8 have all been used. Where another branch arises which requires a temporary label in that state, the connectivity table T is searched first, the processing of FIG. 10 is executed to each tentative number J with J=α, and wherein the end result α.sub.0 obtained, it is applied as a value of D(J). When I=5 to 8 in FIG. 22 is executed, α.sub.0 =5 is obtained for all values of I, and a data field of the connectivity table T is rewritten as shown in FIG. 23. Then, the label field to segments of the line tables LT0, LT1 having temporary numbers of the connectivity table T thus obtained is rewritten to labels of the connectivity table T just rewritten. For example, if the label of a segment of the line table LT0 or LT1 is 6, it is then rewritten to 5 as the result of FIG. 22. Next, labels of the two line tables LT0, LT1 thus processed are searched, and temporary labels (5 to 8 here) are found. Then, "1" is assigned to flag of the temporary label (being 5 here) thus found and "0" is assigned to other flags. The result is shown in the flag field of FIG. 23.
&lt;EPTIOME OF CONSTRUCTION AND OPERATION OF THE APPARATUS&gt; Now, the connectivity detecting apparatus according to this invention will be described specifically. FIG. 1 represents a general construction given in one example. Detailed descriptions of the preferred embodiments and the operation thereof will now be described.
&lt;INITIALIZATION&gt; Prior to starting a process, specific point position coordinates (x.sub.i, y.sub.i) and a pad number Ni corresponding thereto are input to the pad position table memory 10 through the interface circuit 11. FIG. 24 shows the storing format of the specific point position coordinates (x.sub.i, y.sub.i) on the pad position table memory 10 and the grid number Ni. In this case, the order in which data is written into the pad position table memory 10 is y.sub.1 ≦y.sub.2 ≦. . .≦y.sub.i ≦y.sub.i+1. . . , and . . .&lt;x.sub.i &lt;x.sub.i+ &lt;. . . for the same y.sub.i. That is, the data of the specific point position is sorted in the order of picture detection. Next, the line buffer memories 3A, 3B (FIG. 1), the connectivity table memory 12, the flag memory 15, the switching circuits 2, 7 and the line table memories 8A to 8C are initialized, and further the number of lines according to the size of a processing area is set to the labeling part 14 externally through the interface circuit 11. A processing is started after the above initialization.
&lt;PARALLEL PROCESSING&gt; In accordance with a process start, a binary picture signal is input alternately to the two line buffer memories 3A, 3B as shown in TABLE 1, and the code conversion part 4 operates to detect a segment and addresses its start and end with the content of the line buffer memory to which a picture image is not input currently as an input. Then, in parallel with the above processings, the start point and end point addresses of the segment and the label are input cyclically to one of the three line table memories 8A to 8C from the pad number assigner part 6 as shown in TABLE 2, and the labeling part 14 operates for labeling with a content of the remaining two line buffer memories as an input. Accordingly, if the code conversion part 4 and the pad number assigner part 6 operate for the t-th line processing, then the picture input operates to the t+1-th line and the labeling part 14 operates to the t-2-th line. Thus, the above-mentioned three operations can be realized in parallel perfectly without being subjected to interference by changing the switching circuits 2, 7 at every boundary line of the input picture image, thereby ensuring high-speed processing. Then, since FIFO is provided between the code conversion part 4 and the pad number assigner part 6, code conversion and grid number assignment can be realized nonsynchronously and parallel in part, so that these portions can be processed at high speed. It is evident that, buffer memories 17A, 17B and a switching circuit 16 can be provided instead of FIFO as shown in FIG. 25, and from effecting input and output operations alternately as in the case of line buffer memories 3A, 3B, a perfect parallel processing of the code conversion part 4 and the pad number assigner part 6 can be realized. In this case, if the pad number assigner part 6 is in processing of the t-th line, then the picture input part 1, the code conversion part 4 and the labeling part 14 will be in processing of the t+2-th, t+1-th, t-1-th and t-2-th lines respectively.
&lt;RATE DETERMINING PROCESS&gt; A processing rate of the apparatus according to this invention is determined on the portion for which processing time is most required of those which operate in parallel with each other like the picture input part 1, the code conversion part 4, the pad number assigner part 6, the labeling part 14. Then, the picture input part 1 of those which are mentioned above is operable for real-time input at a specific rate determined only on a speed of the line buffer memories 3A, 3B and a speed of a peripheral circuit such as switching circuit 2 or the like. In the case of code conversion part 4, pad number assigner part 6, and lableing part 14, the processing time varies according to a complexity of the input binary picture pattern. As will be described later, processing is particularly complicated for labeling part 14 as compared with the code conversion part 4 and the pad number assigner part 6, therefore from interposing FIFO between the code conversion part 4 and the pad number assigner part 6 instead of buffer memories, the processing time per line at the portions will never be longer than the processing time per line at the labeling part 14 even if this processing is not carried out exactly in parallel. The matter on interposing FIFO of buffer memories selectively between the code conversion part 4 and the pad number assigner part 6 may depend on how to accelerate processing on the labeling part 14, which must be determined by simulation after specific circuit design.
≦COLLISION AVOIDANCE&gt; As will be described hereinlater, the labeling part 14 and the pad number assigner part 6 are capable of writing or reading concurrently to the same connectivity table memory 12. Consequently, collisions will be avoided by the access control circuit 13. The controlling process is shown in FIG. 26. That is, periods of accessible time from the labeling part 14 and the pad number assigner part 6 are provided alternately. In this case, it is necessary to design τ in FIG. 26 or a circuit so that the sum of access time of the connection table memory 12 and delay time of the peripheral circuit will be shorter than τ. This method is one of known memory access methods, however, a comparatively simple circuit configuration is effective enough to realize access control according to the method. Needless to say, and other methods known hitherto can be used otherwise.
&lt;CONSTRUCTION OF EACH PART&gt; Next, construction and operation of the picture input part 1, the code conversion part 4, the pad number assigner part 6, and the lableing part 14 will be described in detail.
FIG. 28 shows one example of construction of the code conversion part. As in the case of the picture input part, a clock pulse is input to an address counter 19, and an address of the line buffer memories 3A, 3B is generated, however, the clock pulse is not necessarily identified by the sample clock pulse in FIG. 27, and a shorter pulse (high frequency) can be used accordingly. The address signal is input to the one line buffer memory selected through the switching circuit 2, and from turning the WE signal of the selected line buffer memory to H (high level status), a binary picture signal input one cycle before the line beginning pulse is output from Dout. A rise (0→1) and a fall (1→0) of the signal are detected by a rise detection circuit 23 and a fall detection circuit 22 respectively, a starting address u.sub.i and an end address v.sub.i are obtainable through latching a value of the address counter 19; however, these are written in FIFO 5 as a pair.
FIG. 29 shows one example of construction of the pad number assigner part. The starting address u.sub.i and the end point address v.sub.i of a segment read out of FIFO 5 are compared with x.sub.j of data of the address indicated from the access controller 9 of the pad position table memory 10 on comparators 24, 25, and then a line counter 28 indicates which order of line is currently processed, it is compared with data y.sub.j from the pad position table memory 10 via access controller 9, on a comparator 26. The line counter 28 is initialized at the beginning of detection and incremented up (or decremented) whenever the line beginning pulse is input. When u.sub.i ≦x.sub.j ≦v.sub.i and y.sub.j =t as the result of comparison, the effect is detected by an AND gate 30, however, the detection output records a pads number Nj to FIFO (1) 33 through an OR gate 31. The count of the address counter 32 of the pads position table memory 10 is thus incremented simultaneously, and the next x.sub.j+1, y.sub.j+1, N.sub.j+1 are read out. In this case, if also u.sub.i ≦x.sub.j+1 ≦v.sub.i and y.sub.j+1 =t, N.sub.j+1 is recorded to FIFO (1) 33. When the above-mentioned comparison does not hold good from repeating such processing, u.sub.i, v.sub.i are written in the predetermined line table memory with the minimum value min Nj of Nj inputted to FIFO (1) 33 as a label. Then, min Nj is written in the connectivity table memory 12 with Nj written in FIFO (1) as an address, thus leaving FIFO (1) empty. If there is not specific point to hold the above-mentioned relation good to u.sub.i, v.sub.i, then u.sub.i, v.sub.i are written in the line table memory with a temporary label 0 given thereto. Then, the minimum value min Ni is detected by a minimum value detection circuit 34. When all specific points presents on one segment are detected, as well as the minimum value min Ni, Nj is read out of FIFO (1) 33 sequentially for the first time.
Meanwhile, when y.sub.j &gt;t and y.sub.j =t and v.sub.i &lt;x.sub.j proceed to the case mentioned above, the address counter 32 is incremented. A comparator 27, a one input NOT-AND gate 29 are provided for detecting the above-mentioned cases. A new specific point position and pad number are obtainable through the pad position table memory 10 whenever the address counter 32 is counted up.
Now, when u.sub.i, v.sub.i and the label of one segment are written in the line table memory, u.sub.i, v.sub.i of the next segment, they are read out of FIFO 5, and similar processing as above is carried out.
FIG. 30 represents a schematic construction of the labeling part. The labelinig part reads the starting and end addresses (u.sub.i.sup.t-1, v.sub.i.sup.t-1), (u.sub.j.sup.t-2, v.sub.j.sup.t-2) of segments Si.sup.t-1, Sj.sup.t-2 from the two line table selected by the switching circuit, and then detects the segment satisfying the expression (2).
u.sub.i.sup.t-1 &#8806;v.sub.j.sup.t-2 and u.sub.j.sup.t-2 &#8806;v.sub.i.sup.t-1                                   (2).
Such segments Si.sup.t-1, Sj.sup.t-2 will now be called connected segments. Let it be assumed that the segments Sj.sup.t-2 and Si.sup.t-1 are connected are labeled as L.sub.0, L.sub.1, respectively, and in which the following processing is carried out according to a value of (L.sub.0, L.sub.1):
(1) Where L.sub.0 =0 and L.sub.1 =0
(1A) When the segment Sj.sup.t-1 connected with the segment Sj.sup.t-2 numbers 2 or more, and labels of these Si.sup.t-1 are all 0, one J of temporary labels with the connectivity table memory flag 0 is selected to L.sub.1 =L.sub.0 =J. Then, the flag is made to be 1 with the data on address A(J) as J. This processing corresponds the time of a branch occurrence as shown in FIG. 4.
(2) Where L.sub.0 ≠0 and L.sub.1 ≠0:
The processing will be carried out so when two labels are assigned to an identical pattern, and first α.sub.0 obtained through carrying out the processing shown in FIG. 12, with L.sub.0 =α being represented by M.sub.0, α.sub.0 obtained likewise with L.sub.1 =α is represented by M.sub.1, then M=min (M.sub.0, M.sub.1) is obtained (where temporary number&gt;pad number&gt;temporary label; "min" being replaced by "max" from the symbols coming in&lt;all), and L.sub.0 =L.sub.1 =M on the line table memory. Rewritten as D (M.sub.0)=D (M.sub.1)=M on the table T, too. Thus, only the minimum pad number M is assigned to the identical pattern at all times.
(3) Where only one of L.sub.0, L.sub.1 is 0:
First, if a label other than 0 is L, the processing shown in FIG. 12 is carried out at L=α, and L.sub.0 =L.sub.1 =M when α.sub.0 thus obtained is represented by M. The same label is thus assigned to a segment connected with the segment labeled other than 0.
&lt;FIRST EMBODIMENT&gt; The most basic embodiment of the pattern defect inspecting art relating to this invention will be described according to FIG. 38.
&lt;SECOND EMBODIMENT&gt; A second embodiment according to the invention will be described next. A construction of the system for putting the embodiment into practice is shown in FIG. 41. What is different from the foregoing embodiment (FIG. 38) is that a contraction processor 29 is inserted between the binary-coding device 22 and the connectivity processor 23, and other construction remains exactly the same.
One example of the contraction processor 29 is shown in FIG. 42. The processor comprises n-bit shift register 31 in (m.sub.2 -1) pieces and m.sub.1 -bit shift register 32 in m.sub.2 pieces. These shift registers are driven by the identical sampling clock. The n is made to coincide with a horizontal sampling number of the pickup device 21. Then, m.sub.1, m.sub.2 are determined by sampling time interval, vertical resolution of the pickup device and size of a defect to be detected. If, for example, the sampling time interval and the vertical resolution correspond to 10 μm each and the size of a defect is 30 μm square, then m.sub.1 =m.sub.2 =3 (FIG. 43). Then, an output of the m.sub.1 register 32 (FIG. 42) is led to AND circuit 33 and output to the connectivity processor 23 (FIG. 41). In FIG. 42, outputs of all the shift registers are extracted, however, they can be extracted selectively according to a shape of the defect to be detected. A result obtained through subjecting the binary pattern shown in FIG. 43 to a contraction processing on the system of FIG. 42 is shown in FIG. 44. A square with the shortest segment as one side represents one picture element.
&lt;THIRD EMBODIMENT&gt; A third embodiment will be described next. A construction of the system for putting the embodiment into practice is shown in FIG. 47. As will be apparent from the drawing, this embodiment combines the first embodiment (FIG. 38) and the second embodiment (FIG. 41). An attribute data detected from the pattern to be inspected shown in FIG. 45, and a defect decision result are shown in TABLE 9 together with the design data.
&lt;FOURTH EMBODIMENT&gt; Next, a fourth embodiment according to the invention will be described. A construction of the system for putting this embodiment into practice is shown in FIG. 48. What is different from the first embodiment (FIG. 38) is that the expansion processor 30 is inserted between the binary-coding device 22 and the connectivity processor 23, and other construction remains exactly the same. One example of the expansion processor 30 is shown in FIG. 49. This processor comprises the n-bit shift register 31 in (m.sub.2 -1) pieces and the m.sub.1 -bit shift register 32 in 32 m.sub.2 pieces. These shift registers are driven by the identical sampling clock. The n is made to coincide with a horizontal sampling number of the pickup device. Then, m.sub.1, m.sub.2 are determined by sampling time interval, vertical resolution of the pickup device 21 and size of a defect to be detected. If, for example, the sampling time interval and the vertical resolution correspond to 10 μm each and the size of a defect is 30 μm square, then m.sub.1 =m.sub.2 =3 (FIG. 49). Then, an output of the m.sub.1 output to the connectivity processor 23 (FIG. 48). In FIG. 49, outputs of all the shift registers 32 are led to OR circuit 34, however, they can be extracted selectively according to a shape of the defect to be detected. A result obtained through expanding the binary pattern shown in FIG. 43 on the device of FIG. 49 is shown in FIG. 50. Further, a pattern obtained through expanding the pattern to be inspected which is shown in FIG. 45 is shown in FIG. 51, and a connectivity data created through connectivity processing is shown in TABLE 10. In addition, an attribute data created similarly to the first embodiment and a defect decision result are shown in TABLE 11 together with the design data. As will be apparent from the result, a small pattern interval at a specified value (30 μm in the example) or below will be shortened and so detected. However, small short-circuited pattern intervals cannot be detected, and a fine disconnection may be overlooked. As described, according to this embodiment, a pattern defect detecting apparatus can be realized through a relatively simple construction only for detecting a short circuit and a small pattern interval without distinction.
&lt;FIFTH EMBODIMENT&gt; Next, a fifth embodiment will be described. A construction of the system for putting this embodiment into practice is shown in FIG. 52. As will be apparent from the drawing, the embodiment combines the first embodiment (FIG. 38) and the fourth embodiment (FIG. 48). An attribute data detected from the pattern to be inspected which is shown in FIG. 45 and a defect decision result are shown in TABLE 12. The system shown in FIG. 52 is that for which the system of FIG. 38 and that of FIG. 48 are combined, like parts in each of the figures are identified by the common reference numeral, and "a" attached to the reference numeral indicates belonging to a sequence for processing a source pattern as in the case of FIG. 47, and "c" indicates belonging to a sequence for processing an expanded pattern. The processing in each sequence is exactly the same as the processing in the first and fourth embodiments, however, as in the case of third embodiment, a processing for judging synthetically a decision result obtained from the source pattern and a decision result obtained from the expanded pattern is added finally.
&lt;SIXTH EMBODIMENT&gt; Next, a sixth embodiment according to the invention will be described. A construction of the system for putting the embodiment into practice is shown in FIG. 53. As will be apparent from the drawing, this embodiment combines the second embodiment (FIG. 41) and the fourth embodiment (FIG. 48). An attribute data detected from the pattern to be inspected shown in FIG. 45, and a defect decision result are shown in TABLE 13 together with the design data. The processing in the embodiment is exactly the same as the second and fourth embodiments. However, a processing for deciding synthetically a decision result obtained from the contracted pattern and a decision result obtained from the expanded pattern is added finally. That is, as shown in TABLE 14, a small pattern interval and a fine short circuit, a small pattern width and a fine disconnection cannot be distinguished from the two decision results, however, others can perfectly be detected distinctively and also not overlooked. Thus, according to the embodiment, perfect short circuit, perfect disconnection, small pattern interval or fine short circuit, small pattern width or fine disconnection can be detected distinctively.
&lt;SEVENTH EMBODIMENT&gt; A seventh embodiment according to this invention will be described next. A construction of the system for putting the embodiment into practice is shown in FIG. 54. As will be apparent from the drawing, this embodiment combines the first (FIG. 38), second (FIG. 41) and fourth (FIG. 48) embodiments. An attribute data detected from the pattern to be inspected, shown in FIG. 45, and a defect decision result are shown in TABLE 15 together with the design data.
&lt;CONSIDERATION&gt; Next, a memory capacity and a processing time necessary for the above-described seven embodiments will be taken up for consideration.
Assuming the pad is present at 256 memory capacity is calculated, first. In this case, the pad number can be represented in 16 bits (2 bytes). If all the pads are detected on connectivity processing, a created connectivity data is: ##EQU1## Then, design data is: ##EQU2##
Then, with reference to the processing time, a conversion from the connectivity data into a cyclic list structure will be performed one time only before inspection, therefore it can be excluded from the processing time, and thus it will be appreciated according to a reference frequency of the design data. If an average pad number on one connected pattern is n, then, assuming that all patterns are free from defect, an average reference frequency necessary for finding the root pad at the time of attribute data creation will be: ##EQU4## Accordingly, ##EQU5## at the time of 256 root pad cannot be found, the reference frequency is n+1 from ##EQU6## therefore: ##EQU7## If n=4, then a reference must be made to the design data 165,478.4 times. Further, since the reference will be made to all design data one time only, the reference is necessary at:
Particularly, a list structure is employed for the design data indicating a connectivity, therefore as compared with a representation in a connection matrix, data compression from 256.sup.2 ≈2.56.times.10.sup.9 bits to 1.05.times.10.sup.6 bits can be realized in the case, for example, for a 256 time can also sharply be decreased.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4069411 *Jun 24, 1976Jan 17, 1978Bausch & Lomb IncorporatedImage analysis system and method for minimizing paralysis angleUS4183013 *Nov 29, 1976Jan 8, 1980Coulter Electronics, Inc.System for extracting shape features from an imageUS4189711 *Nov 8, 1977Feb 19, 1980Bell Telephone Laboratories, IncorporatedMultilevel processing of image signalsUS4504971 *Apr 21, 1982Mar 12, 1985Morton NadlerProcess and device for the automatic segmentation of a scanned image in an image pattern recognition systemUS4550434 *May 13, 1983Oct 29, 1985Hitachi, Ltd.Line recognitionUS4589140 *Mar 21, 1983May 13, 1986Beltronics, Inc.Method of and apparatus for real-time high-speed inspection of objects for identifying or recognizing known and unknown portions thereof, including defects and the likeUS4607385 *May 22, 1984Aug 19, 1986Kabushiki Kaisha ToshibaCharacter recognition apparatusUS4624013 *Mar 27, 1985Nov 18, 1986Kabushiki Kaisha ToshibaLinked component extraction circuit for image processorUS4630306 *Apr 17, 1984Dec 16, 1986National Research Development Corp.Apparatus and methods for coding and storing raster scan imagesUS4635289 *Jul 23, 1984Jan 6, 1987Lloyd Doyle LimitedMethod and apparatus for inspecting printed wiring boardsUS4654583 *Apr 16, 1984Mar 31, 1987Hitachi, Ltd.Method and apparatus for detecting defects of printed circuit patternsUS4718101 *Mar 22, 1985Jan 5, 1988Hitachi, Ltd.Image processing segmentation apparatusUS4791676 *Jan 22, 1988Dec 13, 1988International Business Machines CorporationMethod and means for efficiently handling boundary conditions in connected component labelingJPH05480A * Title not available* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS5253306 *Dec 31, 1990Oct 12, 1993Futec Inc.Method of matching patterns and apparatus thereforUS5872870 *Feb 16, 1996Feb 16, 1999Cognex CorporationMachine vision methods for identifying extrema of objects in rotated reference framesUS5909504 *Mar 15, 1996Jun 1, 1999Cognex CorporationMethod of testing a machine vision inspection systemUS5930382 *May 13, 1996Jul 27, 1999Hitachi, Ltd.Wiring pattern inspecting method and system for carrying out the sameUS5949900 *Mar 11, 1997Sep 7, 1999Nec CorporationFine pattern inspection device capable of carrying out inspection without pattern recognitionUS5949901 *Mar 21, 1996Sep 7, 1999Nichani; SanjaySemiconductor device image inspection utilizing image subtraction and threshold imagingUS5953130 *Jan 6, 1997Sep 14, 1999Cognex CorporationMachine vision methods and apparatus for machine vision illumination of an objectUS5960125 *Nov 21, 1996Sep 28, 1999Cognex CorporationNonfeedback-based machine vision method for determining a calibration relationship between a camera and a moveable objectUS5974169 *Mar 20, 1997Oct 26, 1999Cognex CorporationMachine vision methods for determining characteristics of an object using boundary points and bounding regionsUS5978080 *Sep 25, 1997Nov 2, 1999Cognex CorporationMachine vision methods using feedback to determine an orientation, pixel width and pixel height of a field of viewUS5978502 *Apr 1, 1996Nov 2, 1999Cognex CorporationMachine vision methods for determining characteristics of three-dimensional objectsUS6025854 *Dec 31, 1997Feb 15, 2000Cognex CorporationMethod and apparatus for high speed image acquisitionUS6026176 *Aug 31, 1995Feb 15, 2000Cognex CorporationMachine vision methods and articles of manufacture for ball grid array inspectionUS6067379 *Nov 12, 1996May 23, 2000Cognex CorporationMethod and apparatus for locating patterns in an optical imageUS6072899 *Jan 23, 1998Jun 6, 2000Hitachi, Ltd.Method and device of inspecting three-dimensional shape defectUS6075881 *Mar 18, 1997Jun 13, 2000Cognex CorporationMachine vision methods for identifying collinear sets of points from an imageUS6137893 *Oct 7, 1996Oct 24, 2000Cognex CorporationMachine vision calibration targets and methods of determining their location and orientation in an imageUS6141033 *May 15, 1997Oct 31, 2000Cognex CorporationBandwidth reduction of multichannel images for machine visionUS6215915Feb 20, 1998Apr 10, 2001Cognex CorporationImage processing methods and apparatus for separable, general affine transformation of an imageUS6236769Jan 28, 1998May 22, 2001Cognex CorporationMachine vision systems and methods for morphological transformation of an image with zero or other uniform offsetsUS6259827Mar 21, 1996Jul 10, 2001Cognex CorporationMachine vision methods for enhancing the contrast between an object and its background using multiple on-axis imagesUS6282328Jan 28, 1998Aug 28, 2001Cognex CorporationMachine vision systems and methods for morphological transformation of an image with non-uniform offsetsUS6285783 *Sep 25, 1997Sep 4, 2001Kabushiki Kaisha ToshibaPattern data generating apparatus and method for inspecting defects in fine patterns in a photomask or semiconductor waferUS6298149 *Aug 25, 1998Oct 2, 2001Cognex CorporationSemiconductor device image inspection with contrast enhancementUS6301396Dec 31, 1998Oct 9, 2001Cognex CorporationNonfeedback-based machine vision methods for determining a calibration relationship between a camera and a moveable objectUS6381366Dec 18, 1998Apr 30, 2002Cognex CorporationMachine vision methods and system for boundary point-based comparison of patterns and imagesUS6381375Apr 6, 1998Apr 30, 2002Cognex CorporationMethods and apparatus for generating a projection of an imageUS6396949Jun 15, 2000May 28, 2002Cognex CorporationMachine vision methods for image segmentation using multiple imagesUS6442291Dec 31, 1998Aug 27, 2002Cognex CorporationMachine vision methods and articles of manufacture for ball grid arrayUS6587582Aug 8, 2001Jul 1, 2003Cognex CorporationSemiconductor device image inspection with contrast enhancementUS6603875 *Mar 14, 2000Aug 5, 2003Fujitsu LimitedPattern inspection method, pattern inspection apparatus, and recording medium which records pattern inspection programUS6608647May 29, 1998Aug 19, 2003Cognex CorporationMethods and apparatus for charge coupled device image acquisition with independent integration and readoutUS6684402Dec 1, 1999Jan 27, 2004Cognex Technology And Investment CorporationControl methods and apparatus for coupling multiple image acquisition devices to a digital data processorUS6687402Oct 23, 2001Feb 3, 2004Cognex CorporationMachine vision methods and systems for boundary feature comparison of patterns and imagesUS6748104Mar 24, 2000Jun 8, 2004Cognex CorporationMethods and apparatus for machine vision inspection using single and multiple templates or patternsUS7006669Dec 31, 2000Feb 28, 2006Cognex CorporationMachine vision method and apparatus for thresholding images of non-uniform materialsUS7106895Nov 24, 1999Sep 12, 2006Kla-TencorMethod and apparatus for inspecting reticles implementing parallel processingUS7215808Jun 2, 2004May 8, 2007Kla-Tencor Technologies CorporationHigh throughout image for processing inspection imagesUS7365324 *Mar 20, 2006Apr 29, 2008Ebara CorporationTesting apparatus using charged particles and device manufacturing method using the testing apparatusUS7639861Sep 14, 2005Dec 29, 2009Cognex Technology And Investment CorporationMethod and apparatus for backlighting a wafer during alignmentUS7724939Aug 4, 2006May 25, 2010Kla-TencorMethod and apparatus for inspecting reticles implementing parallel processingUS7741601Mar 11, 2008Jun 22, 2010Ebara CorporationTesting apparatus using charged particles and device manufacturing method using the testing apparatusUS8111904Oct 7, 2005Feb 7, 2012Cognex Technology And Investment Corp.Methods and apparatus for practical 3D vision systemUS8162584Aug 23, 2006Apr 24, 2012Cognex CorporationMethod and apparatus for semiconductor wafer alignmentEP0437273A2 *Jan 11, 1991Jul 17, 1991Futec IncorporatedMethod of matching patterns and apparatus therefor* Cited by examinerClassifications U.S. Classification382/149, 348/125International ClassificationG06T7/00Cooperative ClassificationG06T7/0006, G06T2207/30141European ClassificationG06T7/00B1DLegal EventsDateCodeEventDescriptionJan 29, 2002FPAYFee paymentYear of fee payment: 12Feb 2, 1998FPAYFee paymentYear of fee payment: 8Jan 3, 1994FPAYFee paymentYear of fee payment: 4Apr 3, 1990ASAssignmentOwner name: HITACHI, LTD., 6, KANDA SURUGADAI 4-CHOME, CHIYODAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST.;ASSIGNORS:ICHINOSE, TOSHIAKI;NINOMIYA, TAKANORI;NAKAGAWA, YASUO;REEL/FRAME:005262/0588Effective date: 19850910RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google