# Robust and Efficient Corner Detector Using Non-Corners Exclusion
## 3 Proposed Methods
### Non-Maximum Suppression  
NMS can be positively formulated as local maximum search [26]. In the original Harris corner detector, if the CRF of a pixel is the local maximum of its neighborhood and greater than a given threshold value, the pixel is considered to be a corner. The neighborhood is usually \((2k+1)\times(2k+1)\) region centered around the pixel under consideration. The NMS is performed at each pixel. However, there is one main problem with this approach. Once a local maximum is found, this would imply that we can skip all other pixels in the neighborhood of the maximum pixel point, because they must be smaller than the maximum point. For solving this problem, [PERSON] and [PERSON] proposed the efficient non-maximum suppression (E-NMS) method [26]. First, the algorithm partitions the input image into blocks of size \((k+1)\times(k+1)\). Then, it searches within each block for the greatest element. Finally, the full neighborhood of this greatest element is tested.Other pixels of each block can be skipped.  
There is one main problem with the E-NMS algorithm. The areas of non-corners also execute the NMS procedure. This will inevitably increase complexity because of none existing corners. So, this paper improves the E-NMS algorithm. As an example shown in Figure 3, let the neighborhood window be equal to \(3\times 3\). By employing the method in Section 3.1, we have already calculated the candidate corners. First, we take a candidate corner as the center pixel to form a block of size \(3\times 3\) as shown in Figure 2(a). Second, we search within the four candidate corners for the maximum element. Here, we assume that the p is the maximum element. The maximum of time complexity is O (\(9m\)) and the minimum is O (\(m\)). If the maximum of black blocks is not the center element P, the center pixel is abandoned and the next candidate corner is tested. Third, the full neighborhood is tested for the maximum element and the other three candidate corners in the block of size \(3\times 3\) will be skipped as shown in Figure 2(b). Here the time complexity also can be taken as O (\(9m\)). Finally, we continue to test until traversing all candidate corners which do not include the skipped candidate corners. This step can effectively solve the main problem and play a role in accelerating the proposed method. For the Harris, this step takes O (\(9n^{2}\)) owing to its operation for each pixel.  
If the size of an image is very large with n, the total time complexity of Harris is O (\(9n^{2}+n^{2}+9n^{2}\)). The RECD takes O (\(n^{2}+9m+9m+10m\)) or O (\(n^{2}+9m+9m+18m\)). Thus if m < \(4n^{2}/7\), the RECD has a faster speed. In fact, the m is far less than \(n^{2}\) for a realistic image because many non-corners are excluded. The proposed RECD can improve the detection efficiency.  
Figure 3: The improved efficient non-maximum suppression (E-NMS) algorithm. The black blocks are the candidate corners. The white blocks are the non-corners. The candidate corner p is the center pixel. (a) \(3\times 3\) block centered on candidate corner. (b) The neighborhood around that block.