Optimal lossy segmentation encoding scheme

Guido M. Schuster*, Aggelos K Katsaggelos

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations


In this paper, we present a fast and optimal method for the lossy encoding of object boundaries which are given as 8-connect chain codes. We approximate the boundary by a polygon and consider the problem of finding the polygon which can be encoded with the smallest number of bits for a given maximum distortion. To this end, we derive a fast and optimal scheme which is based on a shortest path algorithm for a weighted directed acyclic graph. We further investigate the dual problem of finding the polygonal approximation which leads to the smallest maximum distortion for a given bit rate. We present an iterative scheme which employs the above mentioned shortest path algorithm and prove that it converges to the optimal solution. We then extend the proposed algorithm to the encoding of multiple object boundaries and introduce a vertex encoding scheme which is a combination of an 8-connect chain code and a run-length code. We present results of the proposed algorithm using objects from the 'Miss America' sequence.

Original languageEnglish (US)
Title of host publicationProceedings of SPIE - The International Society for Optical Engineering
Number of pages12
StatePublished - Dec 1 1996
EventVisual Communications and Image Processing'96. Part 2 (of 3) - Orlando, FL, USA
Duration: Mar 17 1996Mar 20 1996

Publication series

NameProceedings of SPIE - The International Society for Optical Engineering
ISSN (Print)0277-786X


OtherVisual Communications and Image Processing'96. Part 2 (of 3)
CityOrlando, FL, USA

ASJC Scopus subject areas

  • Electronic, Optical and Magnetic Materials
  • Condensed Matter Physics
  • Computer Science Applications
  • Applied Mathematics
  • Electrical and Electronic Engineering


Dive into the research topics of 'Optimal lossy segmentation encoding scheme'. Together they form a unique fingerprint.

Cite this