TY - GEN

T1 - An optimal shape encoding scheme using skeleton decomposition

AU - Wang, Haohong

AU - Schuster, Guido M.

AU - Katsaggelos, Aggelos K.

AU - Pappas, Thrasyvoulos N.

N1 - Publisher Copyright:
© 2002 IEEE.

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

KW - optimaL

KW - shape coding

KW - skeleton decomposition

UR - http://www.scopus.com/inward/record.url?scp=34248649949&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34248649949&partnerID=8YFLogxK

U2 - 10.1109/MMSP.2002.1203254

DO - 10.1109/MMSP.2002.1203254

M3 - Conference contribution

AN - SCOPUS:34248649949

T3 - Proceedings of 2002 IEEE Workshop on Multimedia Signal Processing, MMSP 2002

SP - 85

EP - 88

BT - Proceedings of 2002 IEEE Workshop on Multimedia Signal Processing, MMSP 2002

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2002 5th IEEE Workshop on Multimedia Signal Processing, MMSP 2002

Y2 - 9 December 2002 through 11 December 2002

ER -