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.
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:
- Binary Encoding: Masks are converted into long binary vectors that encode whether pairs of pixels belong to the same segment.
- 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.
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
SCGandgPb. - 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