Five corner detection algorithms have been implemented and tested. One of them is the proposed algorithm, IPAN99, while the other four are those listed in section 2. The test shapes were taken from the paper [4]. The printed images of [4] were scanned, which introduced some noise into the original noise-free pictures. In addition, limited random noise was added to the scanned images to better test the robustness of the algorithms. The eight resulting, noisy test shapes are shown in figure 2.
From the practical point of view, the following performance evaluation criteria are applicable to corner detectors. (1) Selectivity: The rate of the correct detections should be high, the rate of the wrong ones should be low. (2) Single response: Each corner should be detected only once. (3) Precision: The positions of the detected corners should be precise. (4) Robustness to noise. (5) Easy setting of parameters: Given a new task, it should be easy to tune the parameters to this task. Ideally, different categories of shapes should be correctly processed with no need to significantly modify the parameters. (6) Robustness to parameters: Minor changes in parameters should not cause drastic changes in performance. (7) Speed.
Similar criteria are often used to characterize edge detectors. To empirically evaluate most of the criteria, one needs a large reference database with ground truth. Such a database is available for edge detection. Unfortunately, to our best knowledge, no ground-truthed database has been created for corner detection. Partially, this is because the notion of a corner seems to be more task-dependent and subjective than the notion of an intensity edge. Traditionally, certain `standard' collections of shapes have been used to compare corner detectors. The one we use has also appeared in several studies, including that by Liu and Srinath [4].
However, Liu and Srinath have less noisy images and tune the parameters of an algorithm to each of the shapes, so as to obtain the best possible result for each particular shape. In practice, there is usually no way to manually tune the parameters to each particular input. For this reason, we decided to concentrate on the default parameter values, as those values that provide the best overall performance for the whole set of input shapes. These default values are given in sections 2 and 3. Only when the defaults yielded a poor result they were modified until an acceptable result was obtained. Because of the lack of ground truth, a subjective judgment of the detection quality was applied.
The main pictorial results are shown in figures 3-7. IPAN99 distinguishes convex and concave corners which are marked differently. The parameter values for which the results were obtained are summarized in table 1. (Deviations from the default values D are only shown.) The proposed algorithm yields reasonable results at the default values for all the 8 shapes. For 3 of them, somewhat better results can be obtained when the parameters are slightly modified, as shown in the bottom row of figure 7. For stable performance, FD77 and BT87 need more frequent modification of their parameters. (In case of BT87, only needed to be varied.) Because of the higher level of noise and due to different settings of parameters, the overall performance of the four alternative algorithms is worth than that reported in [4].
Table 2 shows average CPU times per shape, in milliseconds, used by the algorithms for 4 typical shapes of different complexity. The algorithms were run 100 times on a 333 MHz PC using the default parameters. Clearly, execution time depends on implementation and parameter values. Some general conclusions can still be drawn. Contour 4 is much shorter than the other seven, so the processing times are the smallest in this case. RJ73, RW75 and IPAN99 depend on the number of corners more strongly than FD77 and BT87. The difference in processing times is significant for complex shapes.