We propose a structured learning approach to edge detection that leverages random decision forests with a novel framework for predicting structured outputs — specifically, local segmentation masks that encode edge patterns. Our key insight is that edges in a local patch are highly interdependent: they form structured patterns like straight lines, parallel lines, T-junctions, and curves. By predicting these structured patterns rather than independent per-pixel edge labels, we achieve state-of-the-art accuracy on the BSDS500 and NYU Depth benchmarks while running at real-time speed — orders of magnitude faster than competing methods such as gPb and SCG.

Edge detection is one of the most fundamental operations in computer vision, serving as a building block for object recognition, segmentation, and image understanding. Classical approaches like the Canny detector rely on local gradient computation, which fails to detect edges lacking strong color gradients — such as texture boundaries and illusory contours. Modern learning-based methods like gPb (global probability of boundary) achieve high accuracy by integrating local and global cues, but are prohibitively slow — requiring minutes per image. Recent approaches using Sketch Tokens speed up processing by learning pre-defined edge patch classes, but the fixed set of patch prototypes limits expressiveness. We address this challenge with a general structured forest framework that naturally handles the full diversity of edge patterns without pre-defined prototypes.

Structured prediction methods in machine learning learn to predict complex, interdependent outputs. Traditional approaches like structured SVMs and CRFs require expensive inference at test time. Random forests are efficient and highly parallelizable, but are designed for independent scalar or categorical outputs. Our contribution bridges this gap: we show that random forests can be extended to predict structured outputs by storing arbitrary output structures at tree leaves, with fast, straightforward inference comparable to standard random forests. The key technical challenge is defining appropriate split criteria for structured labels during tree construction.

A standard random forest splits data at each node by maximizing information gain over scalar labels. For structured outputs (in our case, 16x16 segmentation masks), we need to compute information gain over a high-dimensional label space. Our solution proceeds in two stages: (1) a mapping function maps structured labels to an intermediate space where distance is easily measured — specifically, we use pairwise pixel membership features that encode whether pairs of pixels belong to the same segment, yielding an m=256 dimensional representation; (2) PCA reduces this to 5 dimensions, followed by k-means clustering into k=2 discrete classes. Standard information gain (entropy or Gini impurity) can then be applied to the discrete labels to guide tree splits.

At prediction time, each tree in the forest routes an input patch to a leaf node that stores a set of training segmentation masks. The final prediction is obtained by selecting the medoid — the training example whose distance to all other stored examples is minimized in the reduced space. Crucially, any prediction must have been observed during training; the forest does not hallucinate novel edge patterns but retrieves the most representative one from its memory. The ensemble prediction from multiple trees is averaged to produce a soft edge probability map.

For edge detection, input features are computed from 32x32 patches with 13 channels (3 color, 2 gradient magnitude, 8 gradient orientation) plus pairwise difference features totaling approximately 7,200 candidate features. The structured labels are 16x16 segmentation masks derived from ground truth. Two key enhancements improve results: (1) multi-scale processing (SE+MS) applies the model at original, half, and double resolution; (2) edge sharpening (SE+SH) realigns predicted masks to image edges via iterative segment reassignment based on color and depth similarity. These enhancements bring the final system to ODS=0.75, OIS=0.77, AP=0.80 on BSDS500.

On the BSDS500 benchmark, our full model (SE+MS+SH) achieves ODS=0.75, OIS=0.77, AP=0.80, R50=0.93, outperforming gPb (ODS=0.73), Sketch Tokens (ODS=0.73), and SCG (ODS=0.74). Critically, our method runs at 2.5 FPS for the full model and 12.5 FPS for the sharpened-only variant (SE+SH), compared to gPb at approximately 240 seconds per image. On the NYU Depth dataset, using RGBD features, we achieve ODS=0.69, OIS=0.71, AP=0.72. Cross-dataset experiments show that models trained on BSDS generalize well to NYUD (within ~1 point), suggesting potential as a general purpose edge detector. Comprehensive parameter sweeps confirm robustness across intermediate dimensions (m >= 64), discrete label counts (k=2 optimal), and tree parameters.

We have presented Structured Edge (SE) detection, a method that achieves state-of-the-art edge detection accuracy at real-time speed using structured random forests. The general framework of predicting structured outputs with random forests — via mapping to an intermediate space, discretization, and medoid retrieval — is applicable beyond edge detection to other structured output problems in vision. The dramatic speed advantage over gPb and other methods opens the door to applications in video processing and time-sensitive recognition tasks. Future work includes integrating global context and extending to semantic edge detection.