Machine Vision Process and Apparatus for Reading a Plurality of Separated Figures

This invention relates to a machine vision process and apparatus, particularly, an apparatus which can photograph a plurality of separated figures on a plane diagram, and which can convert the figures into image signals to enter into an image processing unit for determining the center coordinates of the separated figures, and for analyzing the size, the shape, and the suitable connecting sequence of the separated figures.

In the conventional hole-position recognition procedures for a printed-circuit board, the speed, the precision and the reliability of the recognition operation are limited by manual operation; further, an expensive programming machine will increase a manufacturer's cost. Therefore, it is desirable to have a process and an apparatus which can recognize the hole position of a printed-circuit board at a high speed, with precision and reliability.

Generally, before drilling holes on a printed-circuit board provided by a customer, a manufacturer analyze the hole position and the size and shape of the holes on the hole-position diagram to find the best hole-drilling path, and will then set the operation procedures of the drilling machine. The conventional procedures for processing the hole-position diagram of a printed-circuit board are as follows:

1. The hole-position diagram is modified and photographed to make a transparent negative thereof.

2. The holes are classified with colors in accordance with their diameters (manual operation).

3. The holes of one class with one color are lined up (manual operation).

4. The coordinates of the holes are determined by using a programming machine (manual operation).

5. The coordinates of the holes are entered into a computer for obtaining the best permutation of hole-drilling path.

6. The data of the hole coordinates and the hole-drilling path are converted into a digital control program, and transmitted into a drilling machine.

In view of the aforesaid problems and demand, the inventor has developed a machine vision process and apparatus with an operation speed, precision and reliability desired.

A primary object of the present invention is to provide a horizontally movable X-Y table to carry a plane diagram having a plurality of separated figures in order to facilitate scanning the plane diagram by using a photographing device, such as a camera, whereby the image of the diagram is transmitted into an image processing unit to recognize the hole position, thereby replacing the manual processing procedures described above.

Another object of the present invention is to provide a first photographing device (e.g., a camera) for photographing a large area, and to provide a second photographing device (e.g., a camera) for photographing the detailed figures so as to facilitate a special image process and analysis procedure in order to obtain a high speed automatic diagram-reading method and apparatus.

A further object of the present invention is to provide a method of photographing the detailed figures, a method of auto-binary-thresholding, and a correction method for geometrical distortion so as to obtain an automatic diagram reading method and apparatus with a high precision.

FIG. 1 illustrates the structure of the apparatus according to the present invention.

FIG. 2 illustrates the grid-point-skipping state upon inspecting a figure in a large area by using the image processing unit according to the present invention.

FIG. 3 illustrates the theory of calculating the approximate center of a figure in a large area being photographed according to the present invention.

FIG. 4 illustrates an example of the sorting rule of the figures according to the present invention.

The present invention is described in detail with a preferred embodiment with reference to the accompanying drawings as follows:

FIG. 1 illustrates the structure of the present invention, which comprises: an X-Y table 1 to be controlled with a driving unit 11 to move and stop within a plane; the X-Y table 1 is used for supporting diagram 20, which may be a transparent diagram or a figure; under X-Y table 1, a light source is mounted for copying diagram 20. Camera 3 is fixedly mounted on a supporting frame 4 so as to photograph diagram 20 over a large area. Another camera 5 is also mounted on the supporting frame 4 for photographing the precision part of diagram 20;

An image processing unit 6 includes an image digitizing device, conventional picture analyzing software for processing the image and analyzing the diagram data, and

Further, the image processing unit 6 also conventional control software to control the operations of the X-Y table 1, the cameras 3 and 5, and image processing unit 6 itself. The image processing unit 6 is also connected with display unit 7 to display the image. The image processing unit 6 can also be connected with a tape puncher or a processing device 8 (not shown) for data output.

The operation procedures of the present invention may be summarized as follows:

1. The large area of diagram 20 is converted into an image a signal by means of camera 3 so as to find the approximate center of each figure on an image through image processing unit 6.

2. The image coordinates determined by image processing unit 6 of the approximate center of each figure are converted into the coordinates of the X-Y table (diagram).

3. The total figures of the digram 20 are arranged into a reasonable sequence so as to obtain a precision photographing path.

4. The camera 5 for photographing smaller area is used for taking a small picture along the photographing path selected by means of the step 3 above so as to calculate, on the image, the precise center position of a figure. The size and shape of the figure are also obtained.

5. The image coordinates of the precise center position of all figures and their sizes are converted into the coordinate system of the X-Y table.

6. The figures are classified and arranged in a ideal sequence in accordance with the size and shape thereof so as to provide the image processing device 6 with a real operation data.

The aforeasaid operation procedures are described in detail as follows:

1. The large area image processing: the camera 3 reads the image of a large area of diagram 20, i.e., the whole diagram being divided into several areas to be scanned in a sequence. The image is processed with an auto-binary-thresholding method (described below); the approximate center positions of all figures are determined and calculated by using the grid-point-skipping inspection method (described below).

1. Auto-binary-thresholding: since the images to be processed have a strong black-and-white contrast between the figures and background thereof, a corresponding binary threshold can quickly be estimated by using the calculation procedures described below in steps 1-4. An image captured by, for example, a TV camera, can be digitized by an A/D (analog/digital) converter and stored into a frame memory in a matrix form. Each element of the image matrix is called a pixel, and has a corresponding gray level stored in memory. The image having a multi-level gray scale (e.g., a plurality of gray level intensities representing the image) will then be converted into a bright black-and-white two level image in accordance with the threshold, i.e., the separated figures being black and the background portion being white, or vice versa.

1, For a digitized image, each of the various pixels has a corresponding gray level; the picture analyzing software will calculate the number of pixels n.sub.i with the corresponding gray level i, i=0, 1, 2, 3, . . . m,

where:

m=the maximum gray level, i.e., .SIGMA.n.sub.i =N,

N=the total number of pixels.

2, The binary threshold is determined by first finding the average gray level. To find the average gray level t: ##EQU1## in which G.sub.i =Gray level.

3, To find the values of N.sub.1, N.sub.2, t.sub.1 and t.sub.2 : ##EQU2## where N.sub.1 is the total number of pixels whose gray levels are to be less than or equal to the binary threshold; ##EQU3## where N.sub.2 is the total number of pixels whose gray levels are to be greater than or equal to the binary threshold;

where t.sub.1 is a left offset value;

where t.sub.2 is a right offset value;

4, To find the binary threshold T:

2. Grid-Point-Skipping Inspection Method (the method of locating a separated figure from a large area of image):

An ideal method of locating a separated figure should include the following major points:

1, Each figure should be processed only once.

2, A separated figure being processed should be removed from the image to avoid a duplicate process.

3, After a separated figure is processed, find the next separated figure quickly; do not omit any one separated figure.

4, Calculate the coordinates of a separated figure center quickly.

In order to satisfy the aforesaid four major points, a unique grid-point-skipping inspection method is developed in the present invention, and it is further described as follows:

1, Referring to FIG. 2, there is shown an image being divided into a plurality of grid points such as D.sub.11,, D.sub.12 . . . , D.sub.21 , D.sub.22 . . . , D.sub.31 . . . , etc. along the abscissa at a distaance .DELTA.X and the ordinate at a distance .DELTA.Y. D.sub.s indicates the diameter of a separated figure. The grid points are inspected in a regular sequence so as to find out, according to the brightness or darkness, whether a separated figure is present. Since the skipping inspection is limited to a given point (or points), the inspection speed can be greatly improved. The spaces of the grid points, .DELTA.X and .DELTA.Y are determined in accordance with width (such as the diameter of a figure Ds) of the smallest of a diagram so as to have the four grid points of a square lattice located within the minimum separated figure; consequently, a separated figure includes, at least, two grid points so as to prevent omitting any separated figure during grid-point inspection. For examples, to facilitate operation, let .DELTA.Y=Ds-C, and .DELTA.X=1/2.DELTA.Y, in which C=2 so as to adapt to the diameter Ds.ltoreq.18 of the general separated figure.

2, FIG. 3 illustrates the separated figure P (A.sub.1 being a dark point) being located at grid point A.sub.1. The scanning will be made from the mid-point D on a horizontal line BC including point A.sub.1 within the separated figure P downwards at a distance .DELTA.Y to point H. If the point H is within the scope of the separated figure P, a horizontal line KL including point H is drawn within the separated figure P, and the grid points A.sub.4 and A.sub.5 on the line KL are converted into bright points (denoting a non-separated figure) so as not to be processed again during the later inspection. After inspecting the point A.sub.1, the next point to be inspected is the grid point A.sub.3 following the point C; the grid point A.sub.2 between point A.sub.1 and point c will not be inspected.

3, FIG. 3 also illustrates the method of locating the center of a separated figure based on grid point A.sub.1, in which the mid-point D of line BC serves as a base point to draw an upward line to meet point E on the upper edge of the separated figure, and to then draw a downward line to meet point F on the lower edge of the separated figure; then, find a mid-point G on line EF as the center of the separated figure.

2. Conversion of the image coordinates of the center of the separated figure into the X-Y table (diagram) coordinates:

After the image coordinates of the center of the diagram are converted into the X-Y table coordinates, the geometrical deformation of the image is corrected by means of a mathematical method so as to minimize the conversion error of coordinates. The image deformation is usually caused by the lens aberration of the camera and electrical errors in the device; these errors affect the linear relation between a length in the image and the corresponding length of the real diagram. In order to precisely and quickly convert the coordinates of separate figure centers of the image into the coordinates on the X-Y table, a matrix conversion method or a specific gravity differential method according to the present invention is used, and they are described respectively as follows:

(1) The matrix conversion method:

The image coordinates of the aforesaid reference points on the image are determined by means of the several reference points of the known coordinates on the X-Y table, and a matrix T is derived from the aforesaid two sets of coordinates (the X-Y table coordinates and the image coordinates), so as to convert the coordinates between the image and the X-Y table; the matrix T is shown as follows: ##EQU4##

Once the coordinates (x, y) of any point in the image have been known, the corresponding coordinates (X, Y) on the X-Y table can be found with the following equation: ##EQU5##

The matrix T can be found by using the coordinates of the four reference points, i.e., the image coordinates (u.sub.j, v.sub.j), j=1,2,3,4 and the cooresponding X-Y table coordinates (U.sub.j, V.sub.j), j=1,2,3,4 as an example, which is described as follows: ##EQU6##

After being simplified: ##EQU7##

The matrix T can be solved by means of the following matrix equation: ##EQU8##

In real operation, an image can be divided into a plurality of rectangular districts in accordance with the precision; the four top points of each rectangular district are calculated too obtain a matrix [T] as to convert the coordinates.

(2) The specific gravity differential method:

1, A a given number of reference points (u.sub.i v.sub.i) in are set the image,

i=1,2,3, . . . n, n being an interger such as and the corresponding coordinates on the X-Y table are defined (U.sub.i, V.sub.i), i=1,2, . . . n.

2, To calculate K.sub.i, M.sub.i :

3, The coordinates of a given point in the image are defined as (x, y), and the distance d between the coordinates and the various reference points (u.sub.i, v.sub.i) is then calculated: ##EQU9##

4, To calculate the values of K, M: ##EQU10##

5, The corresponding coordinates (X, Y), on the X-Y table with respect to the image coordinate (x, y are determined):

3. Arrangement of the whole separated figures are arranged in a suitable sequence so as to obtain an effective path to photograph every details of the diagram:

The whole separated figures are arranged in sequence so as to facilitate photographing each of the separated figures. The ideal permutation principle is to set a separated figure being the nearest one to the first separated figure as the second separated figure, and to set a separated figure being most adjacent to the second separated figure as the third separated figure, and so on; however, in case of a diagram having a considerable number of separate figures, the aforesaid ideal permutation principle would require large calculation time, which would affect the operation speed.

In the present invention, a "district-dividing and direction-alternating permutation method" is developed, described as follows in the following two steps:

(1) District-dividing:

In order to improve the operation efficiency, the present invention has been so designed that the time for the X-Y table 1 to move from one separated figure to the next separated figure would not be longer than the time for the image processing unit 6 to calculate precisely the data of a separated figure. Since the moving speed of the X-Y table 1 is limited, a whole diagram 20 should be divided into a number of districts before the permutation sequence is performed. The principle of dividing a diagram into many districts is that the time for the X-Y table moving between two farthest separated figures in a district should be less than or equal to the time for the image processing unit 6 to calculate precisely the data of a separated figure; in that case, the calculation operation of the image processing unit 6 would not be interrupted upon each of the separated figures being photographed in detail.

(2) Permutation sequence:

As shown in FIG. 4, the image is divided into .DELTA.y*.DELTA.y square lattices in accordance with the value of .DELTA.y=Ds-C as mentioned above in the grid-point skipping inspection method: each square lattice corresponds to the center of a separated figure only, i.e, n separated figure center coordinates C.sub.i (u.sub.i, v.sub.i), i=1, 2 . . . n, are formed into n sets of numeral rows (a.sub.i, b.sub.i, i) so as to be used for making permutation sequence, where i denotes the series number of the separated figures, being integers from 1 to n; a is the rounded integer of (u.sub.i /.DELTA.y) which denotes the U-axial position of a separated figure C; and is the rounded integer of (v.sub.i /.DELTA.y) which denotes the V-axial position of the separated figure C.sub.i and i denotes the series number of a separated figure. As an example, the corresponding numeral row of the separated figure C.sub.1 in FIG. 4 is (2, 1, 1); the corresponding numeral row of the separated figure C.sub.2 is (9, 1, 2), and so on. In the aforesaid numeral row, the first value a.sub.i of the various numeral rows is arranged in a sequence from small to a large value. In the case where the first value a.sub.i of two or more than two numeral rows is the same, the sequence of the numeral rows will be determined by the quantity of the second value b.sub.i thereof; further, the permutation sequence of the b.sub.i value is also determined in accordance with whether the preceding a.sub.i numeral row exists or not. FIG. 4 describes the permutation sequence, in which the series of arrows P.sub.1, P.sub.2 . . . P.sub.9 denote the execution sequence to inspect whether a separated figure exists in each of the square lattices or not; for instance, in column P.sub.1 as shown by the arrow, there is no separated figure existing, and therefore the same inspection direction as that of column P is continued in column P.sub.2. Upon the separated figure C.sub.5 being detected in column P.sub.2, the series number "5" is recorded as the first separated figure in the permutation. In column P.sub.3, since the numeral row a.sub.2 is not empty, the inspection direction is reversed, and the separated figure C.sub.1 is detected. In column P.sub.4, the inspection direction is reversed to detect the separated figures C.sub.3 and C.sub.7, and so on; in other words, the various separated figures can be permuted into a series of Q photographing path, i.e., C.sub.5, C.sub.1, C.sub.3, C.sub.7, C.sub.6, C.sub.4 and C.sub.2. The aforesaid direction-changing permutation method can quickly obtain in effect the best (the shortest) path of permutation in comparison with the ordinal number permutation sequence, i.e., C.sub.1, C.sub.2, C.sub.3, . . . C.sub.7 so as to reduce the moving distance of the X-Y table and time, and to increase the operation efficiency.

4. Performing a precise photographing process for each separated figure:

By using camera 5 for a small area, the separated figures respectively on diagram 20 are photographed in accordance with the sequence determined in step 3 above; the photographing is made after the X-Y table (diagram 20) has moved to a given position. To confirm that the X-Y table has reached a given position, any conventional method may be used to whether the X-Y table or the driving device thereof has moved to the proper position. After one photograph is done, X-Y table 1 will be moved to the next position. the image processing unit 6 processes the image photographed simultaneously. The image is first processed with the auto-binary-thresholding processing step described above; since an image is photographed by aiming at the approximate center of a separated figure as obtained from step 1, the image center must be within the separated figure so that the edge points of the separated figure can be found in accordance with the center of the image, i.e., starting from the image center outwardly to find the contour of the figure. The precise center coordinate of a separated figure can be determined by averaging the coordinates of all the edge points. The shape and size of the separated figure can also be derived from its contour information.

5. Conversion of the precise image coordinates of the center of separated figures into the coordinates of the X-Y table, i.e., the coordinates of a diagram: the conversion method and steps are the same as those mentioned in 2 above.

6. Classifying and arranging the separated figures in a suitable sequence in accordance with the size and shape data obtained by means of the steps described in step 4 above: the method of permutation sequence is the same as the steps mentioned in step 3 above so as to provide the processing device with the necessary control data. The aforesaid control data can directly transmitted to the processing device, or indirectly transmitted to the processing device via a tape puncher by means of a conventional technique.

Therefore, according to the present invention two cameras are used for photographing a large area of a diagram and a single separated figure at a time upon the X-Y table being moved; the movement of the X-Y table and the image processing operation are made simultaneously; the image is processed through a auto-binary-thresholding processing technique so as to facilitate the image processing unit to analyze and to calculate the center position, the size and the shape of the various separated figures. The center positions are then converted into the corresponding coordinates of the X-Y table by means of the geometrical deformation-revising and coordinate conversion method; moreover, the aforesaid processing steps also include the district-dividing method to a diagram and the direction-changing permutation method for the separated figures so as to have the diagram reading operation done at a high speed and a high precision criteria. The aforesaid method and device according to the present invention are deemed valuable in the industrial field.