PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Edge Detection Using Structured Forests

Piotr Dollár, C. Lawrence Zitnick

arXiv:1406.5549v2cs.CV

TL;DR

Edge detection requires recognizing structured local edge patterns efficiently, but conventional and learning-based approaches face challenges handling these dependencies. The paper applies structured learning to random forests by discretizing structured labels for information-gain evaluation, yielding realtime, state-of-the-art edge detection with cross-dataset generalization.

  • Problem

    Edge patches contain interdependent structures, making unified and computationally efficient edge detection difficult.

  • Method

    The method predicts local segmentation masks with structured random forests, mapping structured labels through an intermediate space into discrete labels for standard information-gain criteria.

  • Results

    The approach achieves state-of-the-art accuracy on BSDS500 and NYU Depth while running orders of magnitude faster than competing state-of-the-art methods.

  • Takeaways & Limitations

    Realtime inference and strong cross-dataset generalization indicate potential for video segmentation and time-sensitive recognition applications.

  • Takeaways & Limitations

    Predictions must be labels observed during training because the ensemble cannot synthesize novel structured labels without additional information.

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper develops a structured-learning edge detector that exploits interdependent patterns in local patches while remaining computationally efficient. Its Structured Edge models achieve realtime performance and state-of-the-art results across edge-detection datasets.

  • Motivation: Learning-based edge detectors address varied visual phenomena by using image patches and optionally combining local predictions with global reasoning.
  • Motivation: Edges in local patches form interdependent structures such as straight lines, parallel lines, T-junctions, and Y-junctions.
  • Results: Structured Edge variants trade accuracy against runtime, achieving realtime performance while attaining state-of-the-art results on BSDS500.
  • Approach: The proposed method predicts local segmentation masks with structured random forests, maps structured labels to discrete values for tree splitting, and aggregates patch predictions into edge maps.
  • Approach: The detector can optionally sharpen diffuse aggregated edge maps using local color and depth cues.
  • Related work: Unlike sketch-token methods, the approach avoids predefined edge-patch classes, allowing subtler edge-structure variations and a more accurate, efficient algorithm.

2 RANDOM DECISION FORESTS

This section reviews how random forests recursively split data, store predictions at leaves, and combine multiple trees. It then motivates extending information gain to structured outputs while preserving the diversity that makes forests effective.

  • Decision trees: A decision tree recursively applies binary split functions until a leaf stores either a target label or a label distribution.
  • Decision trees: Common computationally efficient splits compare one feature with a threshold or compare two features with a threshold.
  • Decision forests: A decision forest combines predictions from multiple independent trees using an ensemble model such as voting or averaging.
  • Decision forests: Because arbitrary outputs can be stored at leaves, decision trees can represent complex structured output spaces.
  • Training: Training structured forests is difficult because structured outputs are complex and information gain may be undefined or expensive to evaluate directly.
  • Training: Random forests improve generalization by combining decorrelated trees, with node-level randomness often producing higher-accuracy ensembles.

3 STRUCTURED RANDOM FORESTS

The paper extends random forests to structured outputs by mapping complex labels into spaces where similarity and information gain can be computed efficiently. For edge detection, this enables structured patch predictions while retaining efficient forest training and ensemble inference.

  • 3 STRUCTURED RANDOM FORESTS: Structured random forests address high-dimensional outputs and the difficulty of defining information gain directly over structured labels.The method targets general structured output spaces, including image patches paired with segmentation masks or semantic labels.
  • 3 STRUCTURED RANDOM FORESTS: Structured labels are mapped to discrete classes so standard information-gain criteria can serve as efficient proxies for structured-label information gain.Similar structured labels are assigned to the same discrete class, allowing existing random-forest training procedures to be reused.
  • 3.1 Intermediate Mapping Π: A two-stage mapping Y → Z → C makes dissimilarity measurable in an intermediate space before discretizing labels for tree-node splitting.For edge detection, Z encodes whether pixel pairs in 16 × 16 segmentation masks belong to the same or different segments.
  • 3.1 Intermediate Mapping Π: The intermediate representation can be computationally expensive because a 16 × 16 mask yields 32640 unique pixel pairs, motivating dimensionality reduction.The method samples dimensions of Z and can apply PCA; the described implementation uses 256 sampled dimensions followed by at most 5 PCA dimensions.
  • 3.2 Discretization: Discrete labels are formed independently at each node using clustering or PCA-based quantization, after which Shannon entropy or Gini impurity can evaluate splits.The labels may be binary or multiclass, and PCA quantization is slightly faster than K-means while producing similar performance.
  • 3.3 Ensemble Model: For combining predictions, the forest selects the observed label whose mapped representation is the medoid of the candidate labels.This medoid computation is typically applied to small sets of labels, such as leaf-node samples or outputs from multiple trees.
  • 3.3 Ensemble Model: A key limitation is that predictions must be labels observed during training, so the ensemble cannot synthesize novel structured labels.For edge detection, the method instead predicts patch-level edge maps independently and merges overlapping predictions by averaging.

4 EDGE DETECTION

The structured edge detector predicts segmentation masks from image patches, maps structured labels into a discrete comparison space, and aggregates overlapping predictions into edge maps. Multiscale processing and sharpening improve localization, while structured outputs reduce computation for realtime detection.

  • Structured edge prediction: The method labels pixels in image patches using binary edge variables, while exploiting the strong interdependence among labels within each small patch.It predicts a structured 16×16 segmentation mask from a larger 32×32 image patch.
  • Input features: The detector uses 13 color and gradient channels plus pixel-lookups and pairwise-difference features computed from image patches.The channels include CIE-LUV color, gradient magnitude at two scales, and orientation-specific gradient channels.
  • Structured label mapping: Structured labels encode whether pairs of mask pixels belong to the same segment, enabling approximate distances in a discrete space for tree splitting.The full mapping has 32640 unique pixel pairs for a 16×16 mask, but training uses a sampled subset of dimensions.
  • Multiscale detection: A multiscale variant averages edge maps from the original, half, and double resolution images, noticeably improving edge quality.The resulting detector is called SE+MS.
  • Edge sharpening: Sharpening aligns predicted segmentation masks to local image color and depth before averaging, producing sharper edge maps, although improvement is not guaranteed.Experiments found the first sharpening step produced the largest gains, and two steps generally sufficed.

5 RESULTS

Experiments show that Structured Edges achieves strong accuracy across BSDS500 and NYUD while supporting real-time or near-real-time processing. Parameter sweeps and modality studies identify robust settings, accuracy–runtime tradeoffs, and cross-dataset generalization.

  • 5.1 Parameter Sweeps: Parameter sweeps found that large structured-label discretizations and small codebooks improve splitting, while performance remains robust to discretization and information-gain choices.Feature-channel performance was relatively insensitive across a broad parameter range.
  • 5.1 Parameter Sweeps: 32 × 32 image patches and 16 × 16 label patches performed best, while more patches and training images improved accuracy.Sampling about half positive patches was best, and using a fraction of features reduced memory with negligible accuracy impact.
  • 5.2 Structured Edge Variants: SE+MS+SH achieved an ODS of .75, compared with .73 for SE and .74 for SE+MS or SE+SH.OIS was about 2 points higher than ODS across variants.
  • 5.2 Structured Edge Variants: SE+SH increased R50 from .90 to .93, while multiscale detection improved low-recall precision; together they achieved an AP of .80.The results indicate complementary effects: sharpening improves recall and multiscale detection improves precision.
  • 5.3 BSDS500 Results: SE+MS+SH outperformed competing state-of-the-art methods on BSDS500, improving ODS/OIS by 1 point and AP/R50 by 2 points.The detector was particularly effective in the high-recall regime.
  • 5.3 BSDS500 Results: SE ran at 30hz, while SE+SH ran above 12hz and improved speed fivefold over SE+MS+SH with only minor accuracy loss and no recall loss.SE+MS+SH was orders of magnitude faster than nearly all comparably accurate edge detectors.
  • 5.4 NYUD Results: On NYUD, combining intensity and depth substantially improved results, and SE+SH slightly outperformed SE+MS+SH.The approach outperformed nearly all competing methods despite treating depth naively like intensity.
  • 5.5 Cross-Dataset Generalization: Using BSDS-trained models on NYUD reduced scores by about 1 point, while precision–recall curves remained closely aligned across training datasets.The authors interpret these experiments as evidence that retraining may not be necessary for general-purpose edge detection.

6 DISCUSSION

The approach combines structured random forests with fast inference to deliver state-of-the-art edge detection accuracy at realtime speed. Its computational efficiency may support time-sensitive vision applications and broader structured-data problems.

  • Realtime, high-quality edge detection may enable applications such as video segmentation and time-sensitive object recognition.
  • The structured decision-tree learning approach may apply to other problems containing structured data.
  • The method achieves state-of-the-art accuracies on two edge detection datasets while being orders of magnitude faster than most competing state-of-the-art methods.
  • Source code is available online.
Loading 1406.5549v2…