Efficient Deformable Template Detection and Localization without User Initialization

James M. Coughlan, Alan L. Yuille, Camper English, Daniel SnowCVIU 2000 · DOI

TL;DR

This paper introduces a novel deformable template method for detecting and localizing hand shapes in images without requiring user input. It leverages dynamic programming with pruning techniques to achieve efficient and robust performance, even with occlusions and multiple hands.

What Problem Does This Paper Address?

Detecting and localizing flexible objects like hands in images is a challenging computer vision problem. Traditional methods often struggle with variations in shape, pose, and illumination. Furthermore, many existing deformable template approaches require manual initialization, which is impractical for real-time applications or large-scale analysis. This paper aims to overcome these limitations by developing an automated system that can reliably find hand shapes without any prior user guidance.

Methods

The core of the proposed method is a Bayesian deformable hand template model combined with a dynamic programming (DP) optimization algorithm.

  • Bayesian Model: This model consists of three main components:
  • Geometric Prior: This component defines the "hand-like" shapes and their variations probabilistically. It uses a chain of points and normal orientations to represent the hand contour and penalizes deviations from a learned prototype.
  • Imaging Model: This model describes how a given hand configuration appears in a grayscale image. It utilizes outputs from a corner/edge detector (edge map, cornerness map, gradient orientation map) rather than raw pixel intensities.
  • Occlusion Process: This is a Markov chain that models the possibility of parts of the hand being occluded. It introduces three states: unoccluded (0), triple point (1/2), and occluded (1), each with distinct image properties.
  • Dynamic Programming with Pruning: A DP algorithm is used to efficiently search for the most probable hand configuration (Maximum A Posteriori - MAP). To speed up this search, two pruning techniques are employed:
  • Relative Pruning: This method eliminates partial paths whose scores are significantly lower than the best score at a given stage.
  • Absolute Pruning: This technique prunes partial paths if their accumulated image evidence is inconsistent with them being part of a true hand.

The paper also discusses adaptive quantization of orientation angles to reduce the search space for the DP algorithm.

Datasets

The paper mentions using a "dataset of images (on which hand edges and triple points were selected manually)" for measuring probabilities in the imaging model. It also refers to using "images of birds in outdoor scenes (used as a consistency check)." No new benchmark datasets are introduced.

Key Insights and Ideas

  • Unsupervised Initialization is Key: The ability to detect hands without user input is a significant advancement, opening doors for more automated and scalable applications.
  • Bayesian Framework for Robustness: Combining geometric priors with an imaging model in a Bayesian framework allows the system to handle variations in shape, occlusion, and background clutter more effectively.
  • Occlusion Modeling is Crucial: Explicitly modeling occlusion states with distinct image properties significantly improves the system's ability to detect hands in challenging scenarios.
  • Dynamic Programming with Pruning for Efficiency: The combination of DP with relative and absolute pruning techniques is essential for making the computationally intensive search feasible in a reasonable amount of time.

Key Results

  • The algorithm can detect a hand in as little as 19 seconds on a Pentium 150 for simple images, and around 25 seconds when the occlusion process is enabled.
  • The system successfully handles significant shape deformation, occlusion, background clutter, and the presence of multiple hands.
  • The occlusion process allows for the identification of occlusion locations.
  • The method is demonstrated to be translation- and rotation-invariant.

Limitations and Future Work

  • Geometric Prior Limitations: The paper acknowledges that the first-order Markov geometric prior is the weakest component of the Bayesian model. It is insufficient to prevent problems like self-intersection and unrealistic deformations.
  • Limited Scale Variation: The current approach can only deal with limited scale variations.
  • Future Work: The authors suggest exploring more sophisticated representations involving symmetry axes and key features to address self-intersection and deformation issues. They also propose learning the prior systematically (rather than relying solely on sampling) and investigating other pruning techniques to further speed up the algorithm. The paper also outlines a method for detecting multiple hands by finding the top M non-overlapping DP paths.

Summary updated

BibTeX
@article{coughlan2000efficient,
  author = {James M. Coughlan and Alan L. Yuille and Camper English and Daniel Snow},
  title = {{Efficient Deformable Template Detection and Localization without User Initialization}},
  journal = {Comput. Vis. Image Underst.},
  year = {2000},
  doi = {10.1006/cviu.2000.0842},
}
Figure