Structured Forests for Fast Edge Detection

Piotr Dollár, C. Lawrence ZitnickICCV 2013 · OpenReview

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 real time 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 is a foundational low-level task in computer vision, yet it has long been plagued by a trade-off between speed and accuracy. Simple gradient-based filters, such as the Canny detector, offer high-speed processing but often fail to distinguish between meaningful object boundaries and high-frequency textures. Conversely, state-of-the-art methods like gPb achieve high accuracy through complex features and global reasoning but are computationally expensive, often requiring minutes to process a single image.

This paper introduces Structured Forests, an algorithm that bridges this gap. By treating edge detection as a structured learning problem—predicting local $16 \times 16$ segmentation masks rather than single pixel labels—the authors capture the inherent "grammar" of local edges (such as lines and junctions) to create a detector that is both accurate and fast enough for real-time video applications.

Methodology

The core innovation of this work is the application of Random Decision Forests to structured labels. Unlike standard decision trees that split data based on simple categorical labels, Structured Forests predict a $16 \times 16$ mask for each image patch.

Qualitative comparison of original images (top), human annotations (middle), and Structured Forest edge maps (bottom).

The Mapping Trick

To calculate information gain on complex $16 \times 16$ masks during training, the authors utilize a "mapping trick." High-dimensional masks are mapped into a low-dimensional discrete space using a two-stage approach:

  1. Binary Encoding: Masks are converted into long binary vectors that encode whether pairs of pixels belong to the same segment.
  2. Dimensionality Reduction: PCA is used to reduce these vectors, which are then quantized into a small set of discrete IDs. This allows the forest to evaluate splits using standard information theory measures without losing critical structural information.

Features and Ensemble

The model utilizes 13 information channels: 3 color channels (CIE-LUV), 2 gradient magnitudes, and 8 orientations. Because the forest predicts overlapping patches, the final edge map is an ensemble average of many local predictions, which naturally smooths the output and improves robustness.

Experimental Evaluation

The authors evaluated the Structured Edge (SE) detector on the BSDS500 (Berkeley Segmentation Dataset) and the NYU Depth v2 dataset.

Edge detection results on a sample image showing the trade-off between detection speed (Hz) and accuracy (ODS).

Key Results

  • Accuracy: On BSDS500, the SE detector achieved an Optimal Dataset Scale (ODS) score of 0.74, matching the performance of much slower state-of-the-art methods like SCG and gPb.
  • Speed: The single-scale version of the detector runs at 60 FPS, making it 1,000 to 10,000 times faster than gPb. Even the high-accuracy multi-scale version maintains a usable speed of 6 FPS.
  • Generalization: Models trained on natural outdoor scenes (BSDS) performed remarkably well on indoor depth images (NYU), suggesting the model learns general properties of edges rather than dataset-specific features.

Discussion and Conclusion

Structured Forests demonstrate that local pixel dependencies are a powerful cue for efficient edge detection. By approximating complex label spaces, the model achieves state-of-the-art precision at real-time speeds. While the current approach is limited by a "medoid" synthesis—meaning it can only output edge structures seen during training—the success of this structured learning framework suggests it could be extended to other dense prediction tasks, such as semantic labeling or optical flow, where local structure is paramount.

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 real time 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
@inproceedings{dollar2013structured,
  author = {Piotr Dollár and C. Lawrence Zitnick},
  title = {{Structured Forests for Fast Edge Detection}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2013},
  url = {https://openreview.net/forum?id=r1-Bv-zd-H},
}
Figure