Method and Apparatus for Automatically Focusing an Image-Acquisition Device

This invention relates to a method and apparatus for automatically focusing an image-acquisition device, such as a television camera, comprising part of a machine vision system.

Machine vision systems are used widely in industry for accomplishing automated visual inspection of many different types of articles. A typical machine vision system comprises a television camera, which carries a lens or a similar optical system, and a machine vision processor, (e.g., a microprocessor) for processing the output signal of the camera. In practice, the vision processor is programmed to examine certain attributes of the image of the article captured by the camera in order to detect a defect, such as the presence or absence of a particular feature.

To achieve high accuracy with present day machine vision systems, it is important that the image of the article captured by the camera be in sharp focus. The more sharply focused the image of the article, the higher the degree of contrast and the greater the accuracy of inspection. For those applications where the articles undergoing inspection are all the same type, it is usually only necessary to manually adjust the focus of the camera at the outset of inspection, either by adjusting the lens or the spacing between the camera and the article, in order to assure that the image of each article is sharply focused. However, if different articles are being inspected by the same machine vision system, it is often necessary to adjust the focus of the camera each time an article different from the previous one is undergoing inspection. To avoid the need for an operator to manually adjust the camera focus, autofocusing systems have been developed.

Present day autofocusing systems typically include a motor which drives either a focusing element on the lens of the camera or which drives a platform carrying the article to adjust spacing of the article from the camera. The focusing motor is controlled by the machine vision processor in accordance with a focus index value, typically obtained by the summing the intensity gradients of each of a plurality of small areas (pixels) comprising the entire image of the article. This approach generally yields relatively poor sensitivity because the focus index value is dependent on the complete range of intensity gradients.

Rather than establish the focus index value by summing all the pixel intensity gradients, another technique may be used. Those of the intensity gradients which are above a threshold value can be summed to obtain a measure of the sharpness of focus. This approach requires an a priori knowledge of the intensity gradients within the captured image, which is not often possible.

Thus, there exists a need for an autofocusing technique which is not subject to the foregoing shortcomings.

Briefly, in accordance with the invention, a method is provided for autofocusing of an image-acquisition device (e.g., a television camera) so that the image captured by the device is in sharp focus. The method is performed by first capturing the image of an article with the image-acquisition device and then processing the image to determine the gradient of the intensity of each of a plurality of small areas (pixels) within the captured image. Thereafter, a histogram of the pixel intensity gradients is established. From the histogram, a focus index value, determinative of the sharpness of focus of the captured image is derived. The just-established focus index value is compared to the previously established focus index value (initially set to zero), and the difference between them is employed to determine in which direction the focus should be incrementally adjusted or stepped, by adjusting the lens on the image-acquisition device, or the spacing of the image-acquisition device from the article, to more sharply focus the image of the article. The focus of the image-acquisition devices is then incrementally stepped in the direction determined to achieve a sharper focus. The process described above is repeated until the just-established focus index value no longer exceeds the value determined previously. Once this occurs, the step size required to step the focus to bring the image into the sharpest focus possible is computed, and the focus of the image-acquisition device is stepped accordingly in the opposite direction as before to bring the captured image into sharp focus.

FIG. 1 is a block schematic diagram of an apparatus for carrying out the method of the present invention;

FIG. 2 is a flowchart representation of an autofocusing method in accordance with the invention;

FIGS. 3A and 3B are photographic representations of the image of an article captured by an image-acquisition device of the apparatus of FIG. 1 for each of two separate focus adjustments;

FIGS. 4A and 4B are photographic representations of the gradient image obtained by substituting the intensity gradient for the actual intensity values for each of the small areas (pixels) in the images of FIGS. 3A and 3B, respectively;

FIGS. 5A and 5B are photographic representations of the upper portion of the histogram of the gradient intensities of the images of FIGS. 3A and 3B, respectively; and

FIG. 6 is a plot of the focus index value versus relative movement of the article and the image-acquisition device determined during execution of the method of FIG. 2.

FIG. 1 illustrates a machine vision system 10 on which the autofocusing technique of the present invention is practiced. The vision system 10 comprises an image-acquisition device 12, typically, a television camera, which is trained on a platform 14 on which an article 16 is placed. The camera 12 is provided with a set of optics 18, in the form of a lens provided with rotatable focusing ring 20 about its exterior for adjusting the focus of the image captured by the camera. The focusing ring 20 about the lens 18 is in meshing engagement with, so as to be driven by, an electric motor 21 carried by the lens. Rotation of the focusing ring 20 by the motor 21 serves to control the focusing of the camera 12. Alternatively, focusing of the camera 12 could be controlled by driving the camera 12 or the platform 14, relative to each other, along the camera's optical axis (not shown). In the illustrated example, the article 16 takes the form of a semiconductor chip whose size has been greatly exaggerated for purposes of illustration. Typically, the chip 16 is illuminated by a bright field illumination, using a beam splitter (not shown) to direct light onto the chip coaxial with the optical axis of the camera 12.

The machine vision system 10 also includes a machine vision processor 22 for processing the output signal of the camera 12 to detect certain attributes in the image captured by the camera. For example, the vision processor 22 may be programmed to inspect the chip 16 for defects such as scratches and stains in the manner taught in U.S. patent application Ser. No. 259,640, filed on Oct. 18, 1988, in the name of C. B. Bose et al., and assigned to AT&T. In the illustrated example, the vision processor 22 takes the form of a model P256 vision processor, manufactured by IRI Corporation, Carlsbad, Calif.

In order for the vision processor 22 to accurately detect the scratches and stains on the surface of the chip 16, or any other such attributes, the image of the chip captured by the television camera 12 should be sharply focused. To assure that the image captured by the camera 12 is sharply focused, the motor 21, which drives the focusing ring 20 on the lens 18, is controlled by the vision processor 22 pursuant to a unique autofocusing technique, developed in accordance with the invention. The details of the autofocusing technique are illustrated in flowchart form in FIG. 2.

Referring to FIG. 2, the first step (step 23) in the autofocusing method of the invention is to initialize a pair of variables M.sub.-1 and M.sub.0 to zero. The next step (step 24) is to capture the image of the chip 16 with the camera 12 of FIG. 1. Referring now to FIG. 3A, there is shown a photographic reproduction of the image of the chip 16 captured by the camera 12. To appreciate the operation of the autofocusing technique of the invention, it is assumed that the lens 18 on the camera is initially out of focus, and for this reason, the image of the chip 16 shown in FIG. 3A is blurred.

Referring to FIG. 2, following step 24, the captured image is then processed (step 26) by the machine vision processor 22 of FIG. 1 to establish the intensity of each of a plurality of small areas (pixels) within the image. The intensity is measured on a gray scale, typically 0-255, with 255 representing the highest possible intensity. For purposes of the invention, the machine vision processor 22 needs only to establish the intensity of the pixels in a small portion of the image captured by the television camera 12, rather than all the pixels in the image. Once the intensity of the pixels in the small portion of the image is established, then the gradient of the intensity within a small neighborhood about each pixel is established, using a well-known technique, such as the Sobel or Roberts method (step 28). If the intensity gradient at every pixel in the image of FIG. 3A were substituted for the pixel intensity, the resultant image would appear as seen in FIG. 4A. The image shown in FIG. 4A is usually referred to as a "gradient" image.

Following step 28, a histogram, that is, a plot of the frequency or number of pixels having a particular intensity gradient value between 0 and 255 is then established (step 30) for the gradient image of FIG. 4A. Referring to FIG. 5A, there is shown the upper portion of the histogram of the pixel intensity gradients, showing N frequency values (where N is an integer, typically .ltoreq.35), representing the pixels having an intensity exceeding a noise threshold of N.sub.0 and lying within the range of g.sub.max and g.sub.max -h, where g.sub.max is the maximum pixel intensity gradient .ltoreq.255 and h is a fixed integer .gtoreq.N.

After step 30, step 32 is executed, whereupon a focus index value, M.sub.new, is computed. The focus index value M.sub.new represents a measure of the sharpness of focus of the image captured during step 24. In practice, M.sub.new is computed in accordance with the formula: ##EQU1## where A is a constant, g.sub.i represents a successive one of N pixel gradient intensity values, each above a noise threshold n.sub.0 and each lying in the range between g.sub.max, the maximum pixel intensity gradient, and g.sub.max -h, h being an integer greater than N. When computed in this fashion, M.sub.new will be inversely proportional to the degree of blur caused by the lens 18 being out of focus. Therefore, when M.sub.new is a maximum, the image captured by the camera 12 will be sharply focused.

Alternatively, the focus index M.sub.new can be computed using the formula: ##EQU2## where B is a constant and n.sub.i is the pixel intensity frequency for each of N corresponding pixel intensity gradient g.sub.i having a value above a noise threshold n.sub.0, and lying between g.sub.max -h and g.sub.max. When the focus index value M.sub.new is computed in accordance with equation (2), it will be inversely proportional to the square of the degree of blur, and thus, when M.sub.new is a maximum, the captured image will be in sharp focus. In practice, it has been observed that equation (1) provides a more robust measure of the focus index value M.sub.new than equation (2).

Once the focus index M.sub.new is computed during step 32, either in accordance with equations (1) or (2), then the value of M.sub.new is compared to the value of M.sub.0 during step 34. Initially, M.sub.0 is zero so that M.sub.new, which, in practice, is always non-zero, will be greater than M.sub.0 during the initial execution of step 32. As a consequence, step 36 is then executed, whereupon the variable M.sub.-1 is assigned the current value of M.sub.0, which, as will be recalled, was initially set to zero. The variable M.sub.0 is then set to the current value of M.sub.new. Also during step 36, the lens 18 is "stepped", that is, the focus ring 20 of FIG. 1 is rotated through a small arc S in a first direction, (e.g., clockwise). The size of the "step" S determines the degree of change of the focus of the lens 18 when the lens is stepped.

Following step 36, the steps 24-34 are executed again, in the same manner as before. When step 34 is re-executed, the value of M.sub.new, just computed during the subsequent execution of step 32, is compared to the current value of M.sub.0, which has now been assigned the value of M.sub.new computed during the previous execution of step 32. In other words, during each subsequent execution of step 34, the focus index value M.sub.new obtained after incrementally stepping the lens 18 in the first direction by the step S is compared to the focus index value existing immediately prior to stepping the lens.

Whether the newly computed value of M.sub.new is greater or less than M.sub.0 (the previously calculated focus index value) will depend on whether stepping of the lens 18 in the first direction causes the image captured during subsequent execution of step 24 to be more or less sharply focused. Assuming that after stepping of the lens 18, the captured image is more sharply focused, as seen in FIG. 3B, then the gradient image, of FIG. 3B, which is shown in FIG. 4B, will have higher gradient values. The histogram obtained from the pixel intensity gradients for the image of FIG. 3B, the upper portion of which histogram is seen in FIG. 5B, will have its peak shifted rightward, as compared to the histogram portion of FIG. 5A, indicating the image is now more sharply focused. Accordingly, the histogram portion shown in FIG. 5B will yield a larger focus index value M.sub.new, as a direct consequence of equation 1.

When the lens 18 is stepped by an amount S in the first direction upon the initial execution of step 36, it is possible that the image may not become more sharply focused but, indeed, may become even more blurred. This is because the lens 18 is being stepped in the "wrong" direction. When the lens 18 has been initially stepped in the wrong direction following execution of step 36 for the first time, the subsequently obtained value of M.sub.new will be less that of M.sub.0. When M.sub.new is less than M.sub.0, then after step 34, step 38 rather than step 36 is executed. During step 38, the current value of the variable M.sub.-1 is compared to zero. Since M.sub.-1 had been set to the value of M.sub.0 (zero) upon the initial execution of step 36, then M.sub.-1 will be found equal to zero when step 38 is executed for the very first time. Under these conditions, step 40 is executed immediately following step 38. During execution of step 40, the variable M.sub.0 is accorded the current value of M.sub.new. Also, the direction in which the lens 18 is stepped is reversed before stepping the lens by an amount S. Since the lens 18 had initially been stepped clockwise, now the lens will be stepped counterclockwise each time step 36 is re-executed. Following step 40, there is a branch to step 24 which is re-executed, together with steps 26-34, in sequence.

The purpose in comparing the variable M.sub.-1 to zero during step 38 is to detect whether the captured image becomes more blurred after the lens 18 is initially stepped by an amount S following the initial execution of step 36. Under these circumstances, the direction in which the lens 18 is stepped must be reversed, which is exactly the action that is taken during step 40. By stepping the lens 18 in the opposite direction as before, the captured image will become more sharply focused.

The steps 24-36 are repeatedly re-executed for as long as the newly computed value of M.sub.new exceeds the value of M.sub.0, which, as will be recalled, is successively assigned the focus index value computed during the previous execution of step 32. Ultimately, after the lens 18 has been cumulatively stepped a certain amount, the captured image will no longer be more sharply focused than before the lens was stepped. Referring now to FIG. 6, there is shown the relationship between the focus index value M.sub.new versus S, the incremental step distance. The curve in FIG. 6 can be approximated by a second order polynomial, so that depending on the cumulative amount by which the lens is stepped, the focus index value M.sub.new obtained after the lens has been incrementally stepped may fall below the peak focus index value (M.sub.final) on the curve.

Referring to FIG. 2, if, after the last iteration of executing steps 24-34, the value of M.sub.new is now less than M.sub.0, then step 38 is executed as described previously. When step 38 is executed after steps 24-36 have been executed more than once, the value of M.sub.-1 will no longer equal zero, but will now equal the third most recent value of M.sub.new which is invariably greater than zero.

When M.sub.-1 is found to be greater than zero during step 38, then step 42, rather than step 40, is subsequently executed. During step 42, a step interval, .DELTA.S, is established in accordance with the relationship. ##EQU3## The quantity .DELTA.S is a "signed" quantity in that it may have a positive or negative value. The difference between S and .DELTA.S represents the absolute distance the lens 18 must be stepped in the opposite direction as before so the focus index value M.sub.new is at the peak value, M.sub.final, assuring the sharpest possible focus.

Following computation of .DELTA.S during step 42, the lens 18 is then stepped during step 44 by the amount S-.DELTA.S in the opposite direction as before in order bring the captured image into the sharpest focus possible.

The step size S, that is, the degree to which the lens ring 20 on the lens 18 is rotated during each execution of steps 36 and 40, determines the accuracy and speed of the autofocusing technique of the invention. By making the step size S large, the number of iterations, that is the number of times steps 24-36 are repeated, will be less than if the step size is small. However, there will be some sacrifice in the focusing accuracy. Conversely, if the step size is small, the accuracy will be higher, yet more iterations will be required.

The foregoing describes a technique for achieving autofocusing of an image which relies on a histogram of the intensity gradients of each of a plurality of small areas (pixels) within the image to establish a measure of the sharpness of focus. The use of the histogram to establish the sharpness of focus renders the present technique more sensitive than prior art techniques which rely on the full range of pixel intensity gradient values and more robust than techniques which rely on a fixed intensity gradient. Moreover, the technique can be executed quite rapidly on present day machine vision systems since most machines have electronic circuitry for automatically calculating histograms. Alternatively, the focus index value calculation may be performed quite rapidly within a small area in the field of view of the camera 12, even using a general purpose computer.

It is to be understood that the above-described embodiments are merely illustrative of the principles of the invention. Various modifications and changes may be made thereto by those skilled in the art which will embody the principles of the invention and fall within the spirit and scope thereof.