Fast Edge Detection by Center of Mass

Bo Li, Aleksandar Jevtić, Ulrik Söderström, Shafiq ur Réhman, Haibo Li2013 · DOI

Abstract

In this paper, a novel edge detection method that computes image gradient using the concept of Center of Mass (COM) is presented. The algorithm runs with a constant number of operations per pixel independently from its scale by using integral image. Compared with the conventional convolutional edge detector such as Sobel edge detector, the proposed method performs faster when region size is larger than 9×9. The proposed method can be used as framework for multi-scale edge detectors when the goal is to achieve fast performance. Experimental results show that edge detection by COM is competent with Canny edge detection.

Introduction

Edge detection is a fundamental task in computer vision, yet it often faces a trade-off between detail preservation and noise robustness. While small filters capture fine details, they are susceptible to noise; conversely, large filters are robust but computationally expensive. Traditional methods like the Sobel operator rely on convolution, where computational cost typically scales linearly ($O(n)$) or quadratically ($O(n^2)$) with the filter width $n$. This scaling makes multi-scale edge detection—essential for robust feature extraction—prohibitively slow for real-time applications. This paper introduces a method to estimate image gradients where processing time remains constant regardless of filter size.

Methodology

The Center of Mass Concept

The core of the proposed method is estimating the image gradient by calculating the Center of Mass (COM) of pixel intensities within a local window. In a region of uniform intensity, the COM coincides with the geometric center. However, the presence of an edge causes the COM to shift toward the higher-intensity side.

Illustration of Center of Mass (COM) shift in response to a step edge.

As shown in Figure 1, the distance of this shift ($X_{COM}$) indicates the gradient's magnitude. To ensure accuracy across varying brightness levels, the authors utilize a linear equation that scales the COM shift by the total intensity (mass) of the region, effectively normalizing the gradient estimate.

Efficient Computation via Integral Images

To achieve high performance, the algorithm leverages Integral Images (Summed-Area Tables). By pre-calculating three specific integral images—representing raw intensity, intensity weighted by x-coordinates, and intensity weighted by y-coordinates—the sum of any rectangular area can be computed in just four array references.

Calculation of a rectangular sum using an integral image.

This technique, illustrated in Figure 4, allows the calculation of the COM for a window of any size (e.g., $3 \times 3$ or $31 \times 31$) in constant time ($O(1)$). The "expensive" step of building the integral images is performed only once, after which multi-scale calculations become extremely efficient.

Experimental Results

The algorithm was evaluated using standard benchmarks, including the "Lena," "Cameraman," and "Peppers" images.

Execution Speed

The COM method demonstrates a significant speed advantage for large kernels. On a $512 \times 512$ image with a $31 \times 31$ filter, the COM method requires approximately 15ms (constant time), compared to 46ms for a separable Sobel filter. For multi-scale detection across four scales ($3 \times 3, 7 \times 7, 15 \times 15, 31 \times 31$), the COM method was twice as fast as the Sobel approach (43ms vs 86ms). The crossover point where COM becomes more efficient than Sobel is approximately a $9 \times 9$ pixel region.

Visual Quality

Qualitative analysis indicates that the COM-based detector produces edge maps comparable in detail and accuracy to the industry-standard Canny edge detector. Results on the "Lena" benchmark show that the method is "competent" in capturing complex edge structures.

Conclusion

The proposed Center of Mass edge detector breaks the convolution barrier by reframing gradient estimation as a mass distribution problem. While traditional Sobel filters remain faster for very small kernels (under $9 \times 9$), the COM method offers superior efficiency for large-scale and multi-scale applications. Future work will focus on a more rigorous quantitative evaluation of edge accuracy to further validate the method's performance.

Summary updated

Abstract

In this paper, a novel edge detection method that computes image gradient using the concept of Center of Mass (COM) is presented. The algorithm runs with a constant number of operations per pixel independently from its scale by using integral image. Compared with the conventional convolutional edge detector such as Sobel edge detector, the proposed method performs faster when region size is larger than 9×9. The proposed method can be used as framework for multi-scale edge detectors when the goal is to achieve fast performance. Experimental results show that edge detection by COM is competent with Canny edge detection.
BibTeX
@misc{li2013fast,
  author = {Bo Li and Aleksandar Jevtić and Ulrik Söderström and Shafiq ur Réhman and Haibo Li},
  title = {{Fast Edge Detection by Center of Mass}},
  year = {2013},
  doi = {10.12792/icisip2013.024},
}
Figure