Fast Edge Detection Using Structured Forests

Piotr Dollár, C. Lawrence Zitnick

Abstract: Edge detection is a critical component of many vision systems, including object detectors and image segmentation algorithms. Patches of edges exhibit well-known forms of local structure, such as straight lines or T-junctions. In this paper we take advantage of the structure present in local image patches to learn both an accurate and computationally efficient edge detector. We formulate the problem of predicting local edge masks in a structured learning framework applied to random decision forests. Our novel approach to learning decision trees robustly maps the structured labels to a discrete space on which standard information gain measures may be evaluated. The result is an approach that obtains realtime performance that is orders of magnitude faster than many competing state-of-the-art approaches, while also achieving state-of-the-art edge detection results on the BSDS500 Segmentation dataset and NYU Depth dataset. Finally, we show the potential of our approach as a general purpose edge detector by showing our learned edge models generalize well across datasets.

Introduction

Edge detection—identifying the boundaries of objects in an image—is a fundamental "low-level" task that feeds into "high-level" tasks like object recognition and image segmentation. Historically, researchers faced a frustrating trade-off between speed and accuracy. Simple methods like the Canny detector (1986) are fast but struggle with texture-heavy regions or "illusory" contours. Conversely, state-of-the-art methods like gPb use sophisticated global reasoning but can take several minutes to process a single image, precluding real-time application.

Furthermore, most learning-based methods historically predicted edges pixel-by-pixel, ignoring the inherent "structure" of edges. In a small patch, edges are not random; they form predictable patterns like straight lines or junctions. This paper, published in 2014 by Piotr Dollár and C. Lawrence Zitnick, addresses these issues by treating edge detection as a structured learning problem.

Methodology: Structured Random Forests

The core innovation is the Structured Random Forest, which predicts local 16x16 edge patches rather than individual pixels. This approach inherently captures local connectivity and structure.

Training via Label Mapping

Standard decision trees use Information Gain to split data, which is straightforward for simple labels but difficult for complex 16x16 binary masks. The authors introduced a two-step mapping process:

  1. $Y \to Z$: The 16x16 mask ($Y$) is mapped to a long binary vector ($Z$) describing whether every pair of pixels in the patch belongs to the same segment.
  2. $Z \to C$: PCA is used to reduce the dimensionality of $Z$, followed by quantization into a small set of discrete classes ($C$).

This allows the use of standard Shannon entropy or Gini impurity on these discrete classes to train the trees effectively.

Features and Datasets

The model utilizes 13 channels of information: 3 color channels (CIE-LUV), 2 gradient magnitudes, and 8 orientations. It also includes "pairwise differences" between pixels to capture local contrast. The approach was evaluated on the BSDS500 (natural images) and NYU Depth (RGB-D) datasets, demonstrating strong cross-dataset generalization.

Key Results and Discussion

The Structured Edge (SE) detector achieved state-of-the-art accuracy while maintaining exceptional speed. On the BSDS500 benchmark, it reached an ODS (Optimal Dataset Scale) score of 0.75, outperforming the popular gPb detector (0.73) while being orders of magnitude faster.

Comparison of edge detection results on a complex scene. The model allows for a trade-off between speed (Hz) and accuracy (ODS).

A key insight is that the model's efficiency stems from overlapping patch predictions. With a stride of only 2 pixels, every pixel receives "votes" from up to 256 different trees, leading to robust, smooth edge maps. As shown in the figure above, the framework allows for a flexible trade-off: achieving real-time performance at 30Hz with high accuracy, or even higher accuracy (0.75 ODS) at a lower frame rate.

Conclusion

The Structured Forest framework provides a powerful, general-purpose tool for edge detection that bridges the gap between real-time performance and high accuracy. While it has limitations—such as being constrained to edge structures seen during training (the "medoid" constraint)—it represents a significant leap forward. The authors suggest this framework could be extended to other tasks like semantic labeling or object detection.

Summary updated

Abstract

Edge detection is a critical component of many vision systems, including object detectors and image segmentation algorithms. Patches of edges exhibit well-known forms of local structure, such as straight lines or T-junctions. In this paper we take advantage of the structure present in local image patches to learn both an accurate and computationally efficient edge detector. We formulate the problem of predicting local edge masks in a structured learning framework applied to random decision forests. Our novel approach to learning decision trees robustly maps the structured labels to a discrete space on which standard information gain measures may be evaluated. The result is an approach that obtains realtime performance that is orders of magnitude faster than many competing state-of-the-art approaches, while also achieving state-of-the-art edge detection results on the BSDS500 Segmentation dataset and NYU Depth dataset. Finally, we show the potential of our approach as a general purpose edge detector by showing our learned edge models generalize well across datasets.
BibTeX
@article{dollar2015fast,
  author = {Piotr Dollár and C. Lawrence Zitnick},
  title = {{Fast Edge Detection Using Structured Forests}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2015},
  url = {https://openreview.net/forum?id=fNXzKsMnG3-},
}

Loading related content...

Figure