An optimal polygonal boundary encoding scheme in the rate distortion sense

Guido M. Schuster*, Aggelos K. Katsaggelos

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

79 Scopus citations

Abstract

In this paper, we present fast and efficient methods for the lossy encoding of object boundaries that are given as eight-connect chain codes. We approximate the boundary by a polygon, and consider the problem of finding the polygon which leads to the smallest distortion for a given number of bits. We also address the dual problem of finding the polygon which leads to the smallest bit rate for a given distortion. We consider two different classes of distortion measures. The first class is based on the maximum operator and the second class is based on the summation operator. For the first class, we derive a fast and optimal scheme that is based on a shortest path algorithm for a weighted directed acyclic graph. For the second class we propose a solution approach that is based on the Lagrange multiplier method, which uses the above-mentioned shortest path algorithm. Since the Lagrange multiplier method can only find solutions on the convex hull of the operational rate distortion function, we also propose a tree-pruning-based algorithm that can find all the optimal solutions. Finally, we present results of the proposed schemes using objects from the Miss America sequence.

Original languageEnglish (US)
Pages (from-to)13-26
Number of pages14
JournalIEEE Transactions on Image Processing
Volume7
Issue number1
DOIs
StatePublished - 1998

Keywords

  • Boundary encoding
  • Dynamic programming
  • Min-max optimization
  • Object-oriented video compression
  • Operational rate distortion theory
  • Shape encoding
  • Tree pruning

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design

Fingerprint

Dive into the research topics of 'An optimal polygonal boundary encoding scheme in the rate distortion sense'. Together they form a unique fingerprint.

Cite this