A Comparison of Measures for Detecting Natural Shapes in Cluttered Backgrounds

Lance R. Williams, Karvel K. ThornberECCV 1998 · DOI

TL;DR

This paper introduces a novel measure for detecting natural shapes in cluttered backgrounds by analyzing the distribution of closed random walks through image edges. The proposed method, WT, significantly outperforms five existing saliency measures across various test patterns, demonstrating its superior ability to distinguish shapes from noise, especially in challenging scenarios.

What Problem Does This Paper Address?

The fundamental problem this paper tackles is image segmentation, specifically the challenge of identifying and isolating natural shapes from complex, cluttered backgrounds. This is often framed as the "saliency problem": assigning a value to each image edge that indicates whether it belongs to a shape or is background noise. Existing methods often struggle with this, especially when shapes are partially occluded, have irregular boundaries, or are embedded in noisy environments. The core difficulty lies in defining what makes a contour "salient" and developing computational models that capture this perceptual quality, often drawing inspiration from Gestalt principles like good continuation and proximity.

Methods

The paper proposes a new saliency measure, WT (Williams and Thornber), based on the concept of closed random walks. The saliency of an edge is defined as the relative number of closed random walks that visit that edge. These random walks are defined by a transition-probability matrix, P, derived from a stochastic motion model of natural shapes. This model incorporates concepts like constant speed and random changes in direction, reflecting Brownian motion.

The key novelty of WT lies in its explicit representation of two edge directions (forward and backward) and the use of a non-symmetric affinity matrix (P). This is contrasted with other measures that use symmetric matrices (A) and only consider edge orientations. The authors argue that this directional representation and non-symmetric matrix are crucial for enforcing tangent continuity, a property they believe is essential for accurate saliency detection and is often overlooked.

The paper also provides a comparative analysis of WT against five previously proposed saliency measures:

  • Shashua and Ullman (SU): Based on a local parallel network and a saliency measure related to the maximum of saliencies of all continuous curves.
  • Hérault and Horaud (HH): Casts segmentation as a quadratic programming problem solved by simulated annealing.
  • Sarkar and Boyer (SB): Uses the Raleigh Quotient to maximize saliency based on an affinity matrix.
  • Guy and Medioni (GM): Employs summation of vector voting patterns based on co-circularity and proximity.
  • Williams and Jacobs (WJ): Computes a stochastic completion field, related to illusory contours.

The comparison focuses on the saliency functions, using a single definition of affinity to ensure a fair evaluation.

Datasets

The paper uses several types of test patterns for evaluation:

  • Simple Patterns: Circles (30, 20, and 10 edges) and a 10-edge sine curve, embedded in backgrounds of randomly placed noise edges. These are used to assess performance under varying signal-to-noise ratios and noise densities.
  • Correlated Noise Patterns: Specifically, "dipole noise," where two collinear edges are separated by a gap. This tests the ability to distinguish shapes from structured noise.
  • "Real Images": Test patterns constructed by insetting silhouettes of fruits and vegetables into natural texture backgrounds (terrain, brick, water). This aims to bridge the gap between synthetic and real-world scenarios.

No new benchmarks are introduced; rather, existing datasets and synthetic patterns are used for comparative evaluation.

Key Insights and Ideas

  • Directionality is Crucial: The paper strongly argues that explicitly representing edge directions (not just orientations) and using non-symmetric affinity matrices are essential for enforcing tangent continuity. This prevents the model from creating "cusps" or reversals in direction, which can lead to misclassifications, especially in the presence of noise.
  • Closed Random Walks Capture Salience: The WT measure's definition of saliency based on the proportion of closed random walks visiting an edge provides a robust way to capture the idea of a complete, continuous contour.
  • WT Outperforms Existing Methods: The novel WT measure consistently shows superior performance across various challenging test cases, particularly in cluttered environments and with low signal-to-noise ratios.
  • Closure Matters: The WT measure's implicit reliance on closure (through closed random walks) contributes to its strong performance, especially compared to methods that do not enforce this property.
  • Limitations of Local Measures: The paper highlights how local measures struggle with correlated noise (dipole noise), where noise elements can have stronger local affinities than actual shape elements.

Key Results

  • Superior False-Positive Rates: Across multiple test scenarios (circles, sine curves, fruit/texture patterns), the WT measure consistently achieved significantly lower false-positive rates compared to the five other measures (SU, HH, SB, GM, WJ).
  • Performance in Challenging Scenarios: WT demonstrated remarkable performance on the 10-edge circle, a pattern that proved difficult for most other measures, achieving a false-positive rate under 5% even at high noise levels.
  • Robustness to Noise: WT showed better performance than other methods at higher noise levels and lower signal-to-noise ratios.
  • Qualitative Improvements: Visualizations of saliency maps show that WT assigns more uniform and higher saliencies to shape edges while effectively suppressing noise edges, leading to clearer segmentations.

Limitations and Future Work

  • Computational Cost: While not explicitly detailed as a limitation for WT, the paper mentions that the HH measure is significantly more expensive to compute than others, implying that computational efficiency might be a factor for some methods.
  • Parameter Sensitivity: The paper notes that the HH method is very sensitive to its parameter 'a', making fair comparison difficult. While WT uses a single definition of affinity to mitigate this, the underlying stochastic motion model might still have parameters that require tuning.
  • Future Work: The authors conjecture that their method's success is due to the explicit representation of two edge directions and the enforcement of contour closure, aligning with human perceptual preferences for smooth, closed contours. They suggest this points towards future research in modeling these perceptual phenomena more deeply. The appendix also provides an analytic expression for the affinity function, suggesting potential for further theoretical development.

Summary updated

BibTeX
@inproceedings{williams1998comparison,
  author = {Lance R. Williams and Karvel K. Thornber},
  title = {{A Comparison of Measures for Detecting Natural Shapes in Cluttered Backgrounds}},
  booktitle = {European Conference on Computer Vision},
  year = {1998},
  doi = {10.1007/bfb0054757},
}
Figure