A Sublinear Approach to Curved Edge Detection
Edge detection is fundamental to image analysis and many algorithms have been developed for this task over the past few decades. In this work we assume the classical model of piecewise constant images and focus on detecting edges with step discontinuity. One of the most widely used algorithms for detecting step edges is  , which runs in linear time in the image size. The more recent Line Segment Detector (LSD)  , aimed specifically at detecting straight edges, has similar runtime complexity. In addition, both methods were designed to perform well only at low noise levels.
Various practical applications, however, require edge detection under very restrictive conditions.
For instance, cameras mounted on cars or drones for avoiding crashes should be able to detect lanes or power lines under poor visibility conditions, such as the extreme fog shown in Fig. 1.
Furthermore, images are typically acquired and stored by hardware,
such as a CCD camera, and
the requirement of processing them in real time may limit their transfer from memory to CPU
and subsequent analysis to only a fraction of all image pixels.
This motivates the following question:
How well can one detect edges in noisy images under severe computational constraints?
The problem was partially treated in  where the authors focused on detecting long and straight step edges. Their key idea was that, to detect long edges, it is not necessary to process all image pixels, but rather only a small subset. We extend their work and present a novel algorithm for detecting long and possibly curved edges, again with runtime sublinear in the total number of image pixels.
Let be a noise-free function defined on a rectangular domain .
As a simple image formation model, let be the discrete image of size pixels,
obtained by ideal sampling of (with a point spread function) on a uniform rectangular grid, and corrupted by additive noise
For simplicity, we assume that the noise is i.i.d. Gaussian, with known variance , and independent of .
When is unknown, it can be estimated from the image (see
For simplicity, we assume that the noise is i.i.d. Gaussian, with known variance , and independent of . When is unknown, it can be estimated from the image (see , for a review of noise estimation methods). Finally, in what follows, for notational clarity we consider square images with .
The key question is detecting possibly curved edges with sublinear time complexity. We study this problem under the following simplified image model: the noise-free function is piecewise constant, with constant values in different regions . The boundaries between adjacent regions delineate long and potentially curved edges . Note that we make no assumptions on the sizes or shapes of the regions . Fig. 2 shows such an image with 3 regions.
Given the noisy image , our goal is to detect and localize the long and smooth edges in it, with a time complexity sublinear in the image size. In particular, analogous to , our algorithm initially samples only of all image pixels for some . Specifically, we detect edges in a few strips extracted from the input image.
Since we aim to detect general-shaped smooth edges, matching detected edges in adjacent strips, as done in , is no longer a viable strategy. Instead, we propose to track the detected edges outside the strips (see Fig. 3 for an illustration). Here we only outline the algorithm. For more details on advanced issues such as non-maximal suppression and improved edge localization, see sections 5.4 of .
We first compared our algorithm to the Canny Edge Detector  and the Line Segment Detector (LSD)  (implementation available at ) on a synthetic image (see Fig. 4). Noise was added to generate two test cases with SNR equal to 2 (top row) and 1 (bottom row) respectively. The results show that our algorithm (3rd column) was less prone to false alarm than Canny (5th column) and was more robust, compared to LSD (4th column), for detecting particularly curved edges.
Next, we show some results on natural images. For details on the parameters used to produce these results, see section 6 of .
Finally, the runtime of three algorithms were compared on two sequences of synthetic square images of increasing sizes. The first sequence contained pure noise and as a result, the tracking algorithm did not run. In the second sequence, however, the images contained one step edge, both detection and tracking would run. The two figures below thus show that (a) tracking is significantly faster than detection and (b) our algorithm ran indeed in sublinear time, both in agreement with our theoretical analysis in .
A matlab implementation of our method can be found here.
The zip-file contains the following directories:
See demo.m and the help of the routine itself for instructions how to use it.
I. Horev, B. Nadler, E. Arias-Castro, M. Galun and R. Basri, Detection of Long Edges on a Computational Budget: A Sublinear Approach , SIAM Journal of Imaging Sciences, vol. 8, no. 1., pp. 458-483, 2015.
J. Canny, A computational approach to edge detection , IEEE Trans. Pattern Anal. Mach. Intell., 8 (1986), pp. 679-698.
R.G. von Gioi, J. Jakubowicz, J.M. Morel, and G. Randall, LSD: A fast line segment detector with a false detection control , IEEE Trans. Pattern Anal. Mach. Intell., 32 (2010), pp. 722-732.
R.G. von Gioi, J. Jakubowicz, J.M. Morel, and G. Randall, LSD: A Line Segment Detector , IPOL, 2 (2012), pp. 35-55; available online at http://dx.doi.org/10.5201/ipol.2012.gjmr-lsd.
M. Lebrun, M. Colom, A. Buades, and J.M. Morel, Secrets of image denoising cuisine , Acta Numer., 21 (2012), pp. 475-576.
C. Liu, W. T. Freeman, R. Szeliski, and S. B. Kang, Noise estimation from a single image, , Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2006, pp. 901-908.