An Efficient Rate-Distortion Optimal Shape Coding Approach Utilizing a Skeleton-Based Decomposition

Haohong Wang*, Guido M. Schuster, Aggelos K. Katsaggelos, Thrasyvoulos N. Pappas

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

17 Scopus citations


In this paper, we present a new shape-coding approach, which decouples the shape information into two independent signal data sets; the skeleton and the boundary distance from the skeleton. The major benefit of this approach is that it allows for a more flexible tradeoff between approximation error and bit budget. Curves of arbitrary order can be utilized for approximating both the skeleton and distance signals. For a given bit budget for a video frame, we solve the problem of choosing the number and location of the control points for all skeleton and distance signals of all boundaries within a frame, so that the overall distortion is minimized. An operational rate-distortion (ORD) optimal approach using Lagrangian relaxation and a four-dimensional Direct Acyclic Graph (DAG) shortest path algorithm is developed for solving the problem. To reduce the computational complexity from O(N5) to O(N3), where N is the number of admissible control points for a skeleton, a suboptimal greedy-trellis search algorithm is proposed and compared with the optimal algorithm. In addition, an even more efficient algorithm with computational complexity O(N2) that finds an ORD optimal solution using a relaxed distortion criterion is also proposed and compared with the optimal solution. Experimental results demonstrate that our proposed approaches outperform existing ORD optimal approaches, which do not follow the same decomposition of the source data.

Original languageEnglish (US)
Pages (from-to)1181-1193
Number of pages13
JournalIEEE Transactions on Image Processing
Issue number10
StatePublished - Oct 2003


  • Boundary coding
  • Object-based video compression
  • Rate-distortion optimization
  • Shape coding
  • Skeleton decomposition
  • Skeletonization

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'An Efficient Rate-Distortion Optimal Shape Coding Approach Utilizing a Skeleton-Based Decomposition'. Together they form a unique fingerprint.

Cite this