Source-linked AI summary
Oriented Edge Forests for Boundary Detection
Sam Hallman, Charless C. Fowlkes
TL;DR
Boundary detection must remain useful when simple brightness and color gradients are disrupted by natural-scene texture. The paper uses oriented random forests with discretized local edge representations, calibrates their outputs across scales, and reports stronger benchmark performance alongside computational advantages.
Problem
Brightness and color gradients are insufficient for boundary detection in natural scenes dominated by fine-scale clutter and texture.
Method
The model trains a random forest to predict discretized oriented edge structures from image patches, then sharpens, calibrates, and combines predictions across scales.
Results
The model outperforms the best reported BSDS500 results, while voting matches averaging up to roughly 20% recall before falling behind.
Takeaways & Limitations
Structured outputs mainly help partition training data into simpler edge-specific learning problems rather than requiring the classifier to discover that structure from large datasets.
Takeaways & Limitations
The straight-line detector cannot directly predict detailed contour structure such as local curvature or pixel-scale wiggles, especially for large patches relative to objects.
Abstract
from arXiv · showhide
We present a simple, efficient model for learning boundary detection based on a random forest classifier. Our approach combines (1) efficient clustering of training examples based on simple partitioning of the space of local edge orientations and (2) scale-dependent calibration of individual tree output probabilities prior to multiscale combination. The resulting model outperforms published results on the challenging BSDS500 boundary detection benchmark. Further, on large datasets our model requires substantially less memory for training and speeds up training time by a factor of 10 over the structured forest model.
1. Introduction
Boundary detection is important for segmentation, detection, and object shape understanding, but brightness and color gradients fail in textured natural scenes. The paper proposes an oriented random-forest detector that predicts local straight-line boundaries, calibrates them across scales, and outperforms prior BSDS500 results.
- Boundary detection supports object segmentation, detection, and understanding of object shape and identity.
- Brightness and color gradients are insufficient when fine-scale clutter, texture, surface roughness, and varying albedo dominate local image variation.
- Modern detectors suppress these responses using oriented analysis of higher-order statistics and global normalization methods.
- The proposed model applies randomized decision forests to straight-line boundaries at candidate orientations and positions within small image patches.
- The model outperforms the best reported results on the BSDS500 boundary detection benchmark.
- Local edge predictions are calibrated and fused across an image pyramid to produce a final oriented boundary map.
2. Clustering Edges
The method represents local boundary patches in a two-dimensional space of signed distance and orientation, then discretizes that space into edge classes for supervised learning. Ground-truth processing and calibration support robust classification across candidate local edge structures.
- Each patch is labeled background when its center lies more than p/2 pixels from an edge; otherwise it receives an edge category.
- Non-background patches are represented by signed distance d and canonical orientation θ of the edge pixel nearest the patch center.
- The parameterization identifies equivalent line representations and forms a Möbius-strip topology with boundary |d| = p/2.
- Ground-truth orientations are estimated by fitting a polynomial to nearby linked edge pixels, using a fitting window of ±6 pixels.
- Short isolated spur edges are removed, while holes are filled and boundaries are thinned to one-pixel lines before labeling.
- Binning distances and orientations yields K = nm discrete edge labels that can be used with standard supervised learning algorithms.
- With 16 × 16 patches, 15 distance bins and 8 orientation bins produce K = 120 edge classes plus background.
- The detector does not explicitly model junctions or thin structures involving more than two segments, which are described as relatively rare in BSDS500 training patches.
3. Oriented Edge Forest
The model treats oriented edge detection as discrete classification with randomized forests, then improves predictions through ensemble combination and probability calibration. It also uses local image evidence to sharpen predicted edge patches.
- Randomized Decision Forests: The forest predicts a small discrete set of edge orientations and locations relative to the patch center, plus a background class.This output space is treated as a k-way classification problem.
- Image Features: Training uses color and gradient feature channels, with tree-node splits based on thresholding channel pixels or pixel differences.The feature channels are downsampled by a factor of 2.
- Ensemble Averaging: Tree outputs can be combined by averaging posterior distributions or by voting over the most probable class from each tree.Averaging retains full posterior information, while voting produces a sparse output vector.
- Ensemble Averaging: Averaging provides somewhat better detection accuracy than voting, but voting reduces memory and computation from O(KT) to O(T).The resulting sparse scores can also speed edge-fusion operations.
- Calibration: Calibration is used to make scores comparable across image scales and interpretable as posterior probabilities for edge labels.Calibration is evaluated on held-out patches by comparing predicted scores with empirical label frequencies in score bins.
- Calibration: Forest scores for non-background patches underestimated the true posterior, and a single scalar β per scale performed as well as the tested alternatives, typically ranging from 6 to 10.The authors fit the calibration function to binary label indicators and used distinct β values for different scales during multiscale fusion.
4. Edge Fusion
The detector fuses calibrated local boundary probabilities with sharpened masks, averaging overlapping patch predictions across orientations and scales. Coarse scales receive modest sharpening, while finer scales use more aggressive sharpening to combine broad structure with precise contour localization.
- Compositing: The composited output is an oriented signal E(x, y, θ) giving boundary probability at each location and binned direction.
- Edge sharpening: The oriented-line model cannot directly predict local curvature or small contour wiggles, motivating local segmentation-based edge sharpening.This limitation becomes more significant when the analyzed patch is large relative to the object.
- Compositing: The method combines calibrated forest scores with sharpened boundary masks by averaging predictions from all patches overlapping each image location.The masks provide precise boundary shapes, while the calibrated scores provide local likelihoods.
- Combining multiple scales: Predictions are composited separately at multiple image scales, with large-scale structure evaluated at s = 1/4 and 1/2 and finer structure at s = 1 and 2.The resulting multiscale estimates are averaged.
- Combining multiple scales: Heavy sharpening is less desirable at coarse scales, whereas more aggressive sharpening is preferred at finer scales.This scale-dependent choice balances coarse edge structure against finer edge detail.
- Combining multiple scales: Low-resolution outputs capture broad, blurry structure, so modest sharpening lets these responses align and combine with finely localized higher-scale edges.
5. Experiments
On BSDS500, the model outperforms existing methods at high precision and matches SE at high recall, while calibration improves low-recall performance. It also benefits from more training data, supports effective qualitative detections, and substantially reduces training resources relative to SE.
- The system outperforms existing methods in the high precision regime and is virtually identical to SE at high recall.
- Calibration improves performance below 50% recall, increasing average precision from 0.81 to 0.82.
- Voting matches averaging up to roughly 20% recall, then falls behind.
- The model benefits significantly from larger training datasets, with experiments spanning 5×10^4 to 4×10^6 examples.Performance was evaluated before and after calibration as training-set size increased.
- Although trained only on straight edges, the forest performs at corners and junctions as well as other methods.
- Monotonic output transformations make qualitative comparisons more meaningful without changing benchmark performance.The transformations align response distributions to a reference distribution while removing visualization differences caused by score scaling.
- Training takes about 5 minutes per tree and roughly 19 GB of memory for this model, versus over 3.25 hours and about 54 GB for SE.Both comparisons use 4×10^6 training patches per tree.
- Voting runs in about 0.7 seconds per image, while averaging takes 2 seconds; an optimization reduces runtime from 11 seconds to 2 seconds with ODS and AP drops below 0.003.
6. Discussion
The discussion positions oriented edge forests alongside related boundary detectors while emphasizing that offset-aware outputs and multiscale combination improve practical edge detection. It also argues that structured outputs primarily help partition training data, while complex local structures and patch-level predictions may be unnecessary.
- Model comparison: The d parameter lets the classifier make useful predictions when a patch is not centered directly over an edge.This addresses ambiguity in labeling points near boundaries as positive or negative examples.
- Scale combination: Multiscale combination greatly outperforms any fixed-scale model on BSDS without calibration.
- Output complexity: Including junctions or parallel edges is not necessary because such events are rare and complex patches provide insufficient training data.Training SE without patches containing more than two segments worked just as well.
- Interpretation: Structured outputs may matter mainly because edge clusters partition training data, letting trees learn each cluster separately rather than discover structure from undifferentiated patches.The authors hypothesize that additional supervisory information could further simplify forest learning.