1.

Introduction

The SUSAN edge detector is a popular edge detection technique for its good performance in localization of edges, connectivity at junctions, and noise suppression effect.¹ Many authors have presented various improved algorithms of SUSAN edge detectors^{2, 3} from different perspectives. To the best of the authors’ knowledge, however, no work on the acceleration of a SUSAN edge detector has been presented in the literature. Although acceleration algorithms for bilateral filter^{4, 5} may be applied to the SUSAN edge detector analogously because of their similarity, the speed-up is only obvious for large kernel size which is not the case for the SUSAN edge detector. In this letter, we propose an acceleration algorithm for the SUSAN edge detector based on random sampling, an idea which has been successfully applied in several image processing algorithms.^{6, 7} Instead of sliding the mask pixel by pixel on an image as the SUSAN edge detector does, the proposed scheme places the mask randomly on pixels to find edges in the image; we hereby name it the randomized SUSAN edge detector (R-SUSAN).

2.

SUSAN Edge Detector

The SUSAN edge detector is implemented by sliding a circular mask with radius of 3.4 pixels pixel by pixel through an image. For each pixel in the raster scan order, an intensity threshold t defines the range of intensities for pixels around it in the circular mask which form the so-called SUSAN area:

3.

Randomized SUSAN Edge Detector

The R-SUSAN edge detector is implemented by placing the circular mask randomly on pixels of an image and taking different actions according to its position to improve efficiency.

3.1.

Random Placing of the Mask

Randomly placing the circular mask on a pixel [TeX:] $\vec r_0 = \left( {i,j} \right)$ ${\vec{r}}_0=\left(i,j\right)$ , the SUSAN area n(i, j) is first computed using Eqs. 1, 2. Based on n(i, j), three different cases corresponding to where the mask is placed are considered: edge region, homogeneous region, and near-edge region, as shown in Fig. 1. Accordingly, different acting rules are taken as follows.

Fig. 1

Different positions the mask is placed. (a) Edge region; (b) homogeneous region; (c) homogeneous region corrupted by noise, and (d) near-edge region.

3.1.1.

Case 1

If n(i, j) < g, then the nucleus is in the edge region, see Fig. 1. In this case, we slide the mask along the edge until it reaches the ends. For each point in the scanning order, neighborhood pixels in the direction perpendicular to the edge (pixels in the dashed rectangle) are checked to get their IRC, and the one with the highest IRC is chosen as the candidate edge point while others are suppressed. After this edge is detected, the mask is then placed randomly on another unprocessed pixel.

3.1.2.

Case 2

If n(i, j) = N_max, then the nucleus is situated in homogeneous region, see Fig. 1. In this case, neither the nucleus nor the surrounding pixels in the circular mask are edge pixels. Therefore, the IRC for the surrounding pixels in the mask are redundant and can be skipped. However, for avoidance of a saw-tooth effect on the edges, we only disable the pixels in the dashed square instead of the whole mask and thus save IRC for them, as shown in Fig. 1. Since no edge information is provided in this case, the mask is then placed on another unprocessed pixel randomly.

3.1.3.

Case 3

If g ⩽ n(i, j) < N_max, then the nucleus may lie in a homogeneous region corrupted by noise [Fig. 1] or near-edge region [Fig. 1]. To differentiate the two situations from each other, we partition the circular mask into four quadrants and compute their USANs, and then find the maximum value n_max and the minimum value n_min among the four USANs. The nucleus lies in the near-edge region if the following condition is satisfied:

Eq. 4

[TeX:] \documentclass[12pt]{minimal}\begin{document}\begin{equation} n_{\max } - n_{\min } \ge \frac{{N_{\max } - n\left( {i,j} \right)}}{2}.\end{equation}\end{document} $$n_{\max }-n_{\min }\ge \frac{N_{\max }-n\left(i,j\right)}{2}.$$

Otherwise, we think the nucleus lies in the homogeneous region corrupted by noise and processes it as in Case 2. For the situation that the nucleus is situated in the near-edge region, we disable the pixels in the dashed square of the quadrant whose SUSAN is equal to n_max to save IRC for these pixels, and then slide the mask by one pixel toward the quadrant whose SUSAN equals n_min where it is nearer to the edge [Fig. 1].

Generally, the process of random sampling should be repeated until all the pixels in the image are processed (including the disabled pixels hereafter). However, since edges usually cover up a small portion of an image and due to the strategy we adopt to find edges, we can terminate the process earlier without accessing all the pixels in the image. In Sec. 3.2, we develop an early termination condition for the algorithm to further save computation cost.

3.2.

Early Termination Condition

The total number of pixels processed, q, will be sufficient if the probability of sampling all edges present in the image at least once is high. We can write down this probability if we have some idea of the number and length of the edges in the image. Consider K edges of the same length L distributed randomly in an image of size M × N, accounting for 0.1% of the total number of pixels in the image, i.e., KL = 0.1 MN. Let p₀ be the probability of placing the mask on an edge, then p₀ = L/(MN). Given that we think an edge is detected once a point on it is sampled, the probability of having detected all edges after q pixels are processed is:

Eq. 5

[TeX:] \documentclass[12pt]{minimal}\begin{document}\begin{equation} Pr = 1 - \sum\limits_{i = 1}^K {\left( { - 1} \right)^{i - 1} \left( {\begin{array}{*{20}c} K \\ i \\ \end{array}} \right)\left( {1 - ip_0 } \right)^q }, \end{equation}\end{document} $$Pr=1-\sum _{i=1}^K{\left(-1\right)}^{i-1}\left(\begin{array}{c}K\\ i\end{array}\right){\left(1-i{p}_0\right)}^q,$$

where i stands for the i’th edge. This probability can be plotted as a function of q and can then be used to gauge which value would constitute a reasonable threshold, as shown in Fig. 2. We can see that, the longer the edge, the earlier the probability reaches 1, which means that the lower the termination threshold can be set. The value q_TH = 0.8 MN, which guarantees the probability is 1 for edges longer than 5 and almost 0.9753 for edges with length of 5, would be a reasonable threshold. In fact, too short edges make little sense and will be removed eventually in the final edge map.

Fig. 2

Probability of detecting all edges after q pixels are processed.

4.

Experimental Results

The images used for the performance evaluation of the proposed method were gray scale images of various sizes, such as 256×256, 512×512, and 1024×1024, and were numbered from 1 to 6 according to their complexity, as shown in Fig. 3. The Gaussian noise was also added to test their performance in noisy environment. Parameters setup, noise level, and post-processing procedures were the same for both detectors: t = 10 for synthetic images and t = 20 for natural images. The early termination threshold for R-SUSAN was set to q_TH = 0.8 MN and q_TH = MN, corresponding to cases with and without early termination, respectively. The performance of R-SUSAN and SUSAN is compared in terms of figure of merit (FM):⁸

Fig. 3

Test Images: (a) Image No. 1; (b) Image No. 2; (c) Image No. 3; (d) Image No. 4; (e) Image No. 5; and (f) Image No. 6.

The detection performance comparison of the two detectors using FM for all six images are given in Fig. 4 for q_TH = 0.8 MN and Fig. 4 for q_TH = MN, where the detection result of the SUSAN edge detector for noiseless image is regarded as ideal edge map and detection results in other circumstances are considered as actual edge points. The two algorithms programmed in VC++ language were executed 50 times on a 2.5-GHz PC with 1024 Mbytes of memory and their average run time were measured. The average speedup of R-SUSAN over SUSAN detector is shown in Fig. 5 for q_TH = 0.8 MN and Fig. 5 for q_TH = MN, respectively.

Fig. 4

Detection performance comparison using FM. (a) q_TH = 0.8 MN. (b) q_TH = MN.

Fig. 5

Average speedup of R-SUSAN over SUSAN. (a) q_TH = 0.8 MN. (b) q_TH = MN.

From the results, we can see that the R-SUSAN edge detector accelerates the SUSAN edge detector effectively while achieving similar detection performance. The speedup is more obvious for simple images with a large portion of homogeneous regions (Image Nos. 1–3) than that for complex images with less homogeneous regions (Image Nos. 4–6). This is due to a different amount of IRC savings: for simple images with more homogeneous regions, more IRCs are saved by the pixel-disabling procedure during the random sampling process; while for complex images with fewer homogeneous regions, the amount of IRC savings is less. This also explains why the speedup is better in a noiseless environment than that in a noisy environment. As for the early termination threshold q_TH, comparing the FM in Figs. 4, 4 and the speedup in Figs. 5, 5, we can see that q_TH = MN does not bring significant improvement in detection performance but leads to an obvious decrease in speedup. Therefore, it is unnecessary to access all pixels in the framework of random sampling and an early termination strategy can further save computational cost without spoiling its detection performance much.

5.

Conclusions

A random sampling scheme for fast implementation of SUSAN edge detector named R-SUSAN was presented in this work. In the framework of placing the mask randomly, the R-SUSAN edge detector increases the computation efficiency of SUSAN edge detector via approaches such as procedure integration of IRC computation and nonmaxima suppression, reduction of unnecessary IRC for obvious nonedge pixels, and early termination strategy. It was shown experimentally that the proposed R-SUSAN edge detector successfully reduce the time requirement of the SUSAN edge detector while keeping its detection performance almost unspoiled.