Dynamic Programming for Detecting, Tracking, and Matching Deformable Contours

Davi Geiger, Alok Gupta, John Vlontzos, Luiz A. Costa

Research output: Contribution to journalLetterpeer-review


The problem of segmenting an image into separate regions and tracking them over time is one of the most significant problems in vision. Terzopoulos et al have proposed an approach to detect the contour regions of complex shapes, assuming a user selected initial contour not very far from the desired solution. We propose to further explore the information provided by the user's selected points and apply, an optimal method to detect contours which allows a segmentation of the image. The method is based on dynamic programming (DP), and applies to a wide variety of shapes. It is exact and not iterative. We also consider a multiscale approach capable of speeding up the algorithm by a factor of 20, although at the expense of losing the guaranteed optimality characteristic. The problem of tracking and matching these contours is addressed. For tracking, the final contour obtained at one frame is sampled and used as initial points for the next frame. Then, the same DP process is applied. For matching, a novel strategy is proposed where the solution is a smooth displacement field in which unmatched regions are allowed while cross vectors are not. The algorithm is again based on DP and the optimal solution is guaranteed. We have demonstrated the algorithms on natural objects in a large spectrum of applications, including interactive segmentation and automatic tracking of the regions of interest in medical images.

Original languageEnglish (US)
Pages (from-to)294-302
Number of pages9
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Issue number3
StatePublished - Mar 1995


  • Dynamic programming
  • contour segmentation
  • deformable contours
  • matching
  • optimal solutions
  • snakes
  • tracking

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition
  • Computational Theory and Mathematics
  • Artificial Intelligence
  • Applied Mathematics


Dive into the research topics of 'Dynamic Programming for Detecting, Tracking, and Matching Deformable Contours'. Together they form a unique fingerprint.

Cite this