The Detection of Quartz that Based on the Improved Hough Transform

INTRODUCTION

---

During the detection of the quartz, in order to achieve the most accurate template matching, we should adjust the sample pictures to the required angle. Hough algorithm has great advantage in Robustness and anti-jamming capability, so it is widely used in the pictures’ angle detection. However, due to the calculation of the traditional Hough algorithm is requiring a large number, lower speed, thus preventing its further application on the product testing. A new method is proposed in this study. It can significantly lower the total amount of Hough transform and in the case of pixels allows, the slope of the straight line’s detection accuracy can be achieved a high degree. For its ultra-fast operation speed, it makes the industrialization of the Quartz wafer defect detection become possible. So, it has important value in use.

THE INTRODUCTION OF THE HOUGH ALGORITHM

Hough transform (Hough Transform, HT) is first proposed in the form of patent by P.V.C. Hough in 1962. It realized an image space to parameter space form the mapping, though the transforming problem of the image in the detection into the parameter space and complete the inspection by the simple accumulation of statistics in the Parameter space.

The basic idea of Hough transform is the duality between point and line. For one thing, the collinear points in image space corresponding to the intersection line that in parameter space. For another, the lines which intersect at the same point in the parameter space corresponds to the collinear points in the image space. So, Hough transform changes the problem of line detection in image space into the problem of point detection in the parameter space, it completes the detection task by a simple statistics cumulative in the parameter space. If the linear equation is used in parameter space, when the slope of the line in the image space is infinite, the size of the accumulator will become very large and the computational will become very complex. In order to solve the problem, we use the liner equation in polar coordinates. The transformation process is:

(1)

According to the Eq. 1, the point (x, y) in the original image space correspond a sine curve in the new parameter space, so, is the dual between the points to the sine curve. The specific process of the line detection is that make the θ taking over all the possible values and then compute the value of ρ and cumulative the array according to the values of θ and ρ, so, we can get the numbers of the collinear points. Here, we introduce how to determine the range of θ and ρ.

Assuming that the line that is detected is in the first quadrant and the upper right corner coordinates is (m, n), so, the location of the line in the first quadrant is shown like Fig. 1.

We can see clearly in Fig. 1, when the straight line rotation form the coincides with the x-axis in a counter-clockwise, the value of θ is changing and the range of θ is 0~180°. Form the polar equation of a straight line:

We can know that, if and only if x and y both achieve maximum and θ + θ = 90°, then, the value of ρ will get the maximum that is , form the resolution and the range of ρ and θ we can determine the size of the accumulator and then we can detection the straight line.

Fig. 1:	Normal linear equation

Fig. 2:	The simplified detection process of quartz wafer

We can seen from the upper that, the anti-noise performance of Hough transform is very strong, however, this approach also has obvious defects, that is it can not take both speed and accuracy into consider. If we increase the value of m and n or decrease the step length of angle detection, it will improve the computation greatly and reduce the efficiency of detection. As the traditional single test is Hough transform a whole image, if assume each array ρ, θ need 4 bytes of storage space, so, take an image of M x N pixels to say, if it has k slopes that is not repeat, it will require a computer’s memory S = 4 MNk. Take a larger image to say, S will be several gigabytes. Considering the large storage, it will not meet the requirements if we only use the physical memory (Chutatape and Guo, 1999).

THE IMPROVED HOUGH TRANSFORM

When we detect the defects of quartz (this study is just saying the rectangular quartz) and we use Hough transform to detect the deflection angle of the rectangular edge, it will cost us a lot of time if we use the traditional Hough transform and thus it will lost the possibility of real-time detection. In this case, this study takes the slope of the fractional look-up table into use. The probably algorithm flow is:

We should establish a form at the beginning, this process can be carried out in the program initialization (Qiu et al., 2003). Now let’s take the chips image (412x288) as the example to say.

•	First decompose 1~412 integer, the result are putted into the array g that has been set already
•	The integers are divided by each other form 1 to 412, simplify the results and get the most simple form of fraction, the results that have been simplified are set into the other array k , so we can get a table

When we detect the slope, we can check the table, simplify from the array k and then plus the accumulator value with 1 according to the results that have been obtained.

We can get the slope of crystal wafer edge at the end of the operation. During the experimental there may appear a straight slope of infinite, thus we can set a special array to account the straight slope of infinite in the structure array of parameter space.

The simplified detection process of quartz wafer is shown in Fig. 2.

THE EXPERIMENTAL RESULTS AND ANALYSIS

It is fast, precise to detection the deflection angle of quartz wafer edge as we use the slope of the fractional look-up table and thus it provide a good foundation for the rotation of the image and the follow-up process. Since the algorithm is greatly reduced the computing time, it provides a good theory foundation for the real-tine detection of the industry to determine the chips is good or bad.

Figure 3 has shown us the quartz sample picture that is taken under the normal conditions. Since the samples are placed random, we must deal with the photos that are taken. So we can match the samples to the template in the end and get ready for determining the chips are good or bad.

As we load the sample picture, the following steps are binarization, the detection of edge and so on, we can get the picture that has been processed, as shown in Fig. 4.

Fig. 3:	The sample picture of quartz

Fig. 4:	The picture that has been processed

The hardware and software environment that used by simulation are as following:

•	Hardware platform: CPU: Intel Core (TM) 2, the frequency is 2.00 GHz, the memory is 2GB
•	Software platform: The operating system is Windows XP, the algorithm language is C++, the compiler is Visual C++6.0

Take the picture (412x288) to say. The detection angle step is 0.05°, the process time is 27 ms. The result is obtained by the average of 10 simulations. When the picture that is needed to process is very large and the resolution is becoming further precision, the process time must be increase as corresponding. Comparing to the standard Hough transform, however, the time is very short.