# Robust and Efficient Corner Detector Using Non-Corners Exclusion
## 3 Proposed Methods
### Non-Corners Exclusion  
The FAST theory has good robustness for transformations, especially for rotation, owing to the use of a circular template. A corner is generally at the vertex of a sharp angle on the image edge. Transformations change the structure of an angle to some extent. But the continuity of an edge is relatively robust. The FAST can detect out those structural corners and retain those uncertain corners from a transformed image. By contrast with the FAST, the Harris corner detector directly conducts gradient computation with a small window of \(3\times 3\) on the whole image. So the uncertain corners can be detected further with the Harris detector. If an uncertain corner is also validated by the Harris, it is a real corner.  
The key step of the FAST detector is that a circle of 16 pixels (a Bresenham circle of radius 3) is examined surrounding the point P as shown in the Figure 2. The point P is classified as a corner if the intensities of at least \(N\) contiguous pixels in the circle are all brighter (darker) than the intensity of the point plus (minus) a threshold \(t\). \(N\) is actually a scale to judge the corners. Too large an \(N\) can lead to several missed corners and the small \(N\) will bring about too many weak corners. To ensure the accuracy and stability of the algorithm, \(N\) is generally set to 12.  
Figure 1: The images used for the performance test are block (\(256\times 256\)), flower (\(1024\times 576\)), house (\(256\times 256\)), airplane (\(331\times 361\)) and lab (\(512\times 512\)).  
In this paper, fast corner detection theory is applied to the first step: corner pre-detection. Three of the four pixels 1, 5, 9 and 13 certainly exist in these 12 contiguous pixels. We first examine the pixels 1 and 9. If both of the intensities of the two pixels are in a range of \(t\) of the intensity of the point P, then P is excluded to be a corner and the computation for current pixel is terminated. If not, we examine the pixels 5 and 13. If at least three of the four pixels are all brighter (darker) than the intensity of the point plus (minus) a threshold \(t\), the point P is a corner. This is because 12 contiguous pixels are bound to include three of the pixels which will be examined. Note that if only two nearest neighborhood pixels in the four pixels, for example pixels 1 and 5, are both extremely brighter or darker than P, then P still can be a corner. We called these uncertain corners candidate corners. For an image of \(n\times n\) pixels, the time complexity of this step is O(\(n^{2}\)). Using this method can reject most non-corners, so that the computational complexity is reduced to a great extent for the next step gradient calculation. The FAST principle can only detect those obvious corners when there are 12 contiguous pixels in the circle of radius 3. For the situation of contiguous pixels less than 12, it does not perform well. This method can also detect some corners adjacent to one another. The pixels can be divided into three types by the FAST: non-corners, uncertain corners and strong corners. Therefore, we use this principle to exclude those non-corners and mark those strong corners as real corners. The uncertain pixels are all considered candidate corners to be detected further with Harris. In this case, almost all of the real corners are retained in the set of candidate corners and strong corners.