An optimal shape encoding scheme using skeleton decomposition

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

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

4 Scopus citations

Abstract

This paper presents an operational rate-distortion (ORD) optimal approach for skeleton-based boundary encoding. The boundary information is first decomposed into skeleton and distance signals, by which a more efficient representation of the original boundary results. Curves of arbitrary order are utilized for approximating 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 and for all boundaries within a frame, so that the overall distortion is minimized. The problem is solved with the use of Lagrangian relaxation and a shortest path algorithm in a 4D directed acyclic graph (DAG) we propose. By defining a path selection pattern, we reduce the computational complexity of the 4D DAG shortest path algorithm from O(N/sup-5/) to O(N/sup-4/), where N is the number of admissible control points for a skeleton. A suboptimal solution is also presented for further reducing the computational complexity of the algorithm to O(N/sup-2/). The proposed algorithm outperforms experimentally other competing algorithms.

Original languageEnglish (US)
Title of host publicationProceedings of 2002 IEEE Workshop on Multimedia Signal Processing, MMSP 2002
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages85-88
Number of pages4
ISBN (Electronic)0780377133, 9780780377134
DOIs
StatePublished - 2002
Event2002 5th IEEE Workshop on Multimedia Signal Processing, MMSP 2002 - St. Thomas, United States
Duration: Dec 9 2002Dec 11 2002

Publication series

NameProceedings of 2002 IEEE Workshop on Multimedia Signal Processing, MMSP 2002

Other

Other2002 5th IEEE Workshop on Multimedia Signal Processing, MMSP 2002
CountryUnited States
CitySt. Thomas
Period12/9/0212/11/02

Keywords

  • optimaL
  • shape coding
  • skeleton decomposition

ASJC Scopus subject areas

  • Signal Processing
  • Media Technology

Fingerprint Dive into the research topics of 'An optimal shape encoding scheme using skeleton decomposition'. Together they form a unique fingerprint.

Cite this