Shape Segmentation Using Relaxation

Wallace S. Rutkowski, Shmuel Peleg, Azriel Rosenfeld

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


Relaxation is applied to the segmentation of closed boundary curves of shapes. The ambiguous segmentation of the boundary is represented by a directed graph structure whose nodes represent segments, where two nodes are joined by an arc if the segments are consecutive along the boundary. A probability vector is associated with each node; each component of this vector provides an estimate of the probability that the corresponding segment is a particular part of the object. Relaxation is used to eliminate impossible sequences of parts, or reduce the probabilities of unlikely ones. In experiments involving airplane shapes, this almost always results in a drastic simplification of the graph with only good interpretations surviving. The approach is also extended to include curve linking and gap filling. A chain coded input image is broken into segments based on a measure of local curvature. Gap completions linking pairs of segments are then proposed and represented in a graph structure. A second graph, whose nodes consist of paths in the above graph, is constructed, and the nodes of the second graph are probabilistically classified as various object parts. Relaxation is then applied to increase the probability of mutually supporting classifications, and decrease the probability of unsupported decisions. A modified relaxation process using information about the size, spatial position, and orientation of the object parts yielded a high degree of disambiguation.

Original languageEnglish (US)
Pages (from-to)368-375
Number of pages8
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Issue number4
StatePublished - Jul 1981
Externally publishedYes

All Science Journal Classification (ASJC) codes

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


  • Image processing
  • pattern recognition
  • relaxation
  • segmentation
  • shape


Dive into the research topics of 'Shape Segmentation Using Relaxation'. Together they form a unique fingerprint.

Cite this