Optimal decomposition for quad-trees with leaf dependencies

Guido M. Schuster; Aggelos K. Katsaggelos

doi:10.1117/12.263281

10 January 1997 Optimal decomposition for quad-trees with leaf dependencies

Guido M. Schuster, Aggelos K. Katsaggelos

Proceedings Volume 3024, Visual Communications and Image Processing '97; (1997) https://doi.org/10.1117/12.263281
Event: Electronic Imaging '97, 1997, San Jose, CA, United States

Abstract

We propose a fast and efficient algorithm which finds the optimal quad-tree (QT) decomposition with leaf dependencies in the rate distortion sense. The underlying problem is the encoding of an image by a variable block size scheme, where the block size in encoded using a QT, each block is encoded by one of the admissible quantizers and the quantizers are transmitted using a first order differential pulse code modulation (DPCM) scheme along the scanning path. First we define an optimal scanning path for a QT such that successive blocks are always neighboring blocks. Then we propose a procedure which infers such an optimal path from the QT-decomposition and introduce a special optimal path which is based on a Hilbert curve. Then we consider the case where the image is losslessly encoded using a QT- decomposition and the optimal quantizer selection. We then apply the Lagrangian multiplier method to solve the lossy case, and show that the unconstrained problem of the Lagrangian multiplier method can be solved using the algorithm introduced for the lossless case. Finally we present a mean value QT-decomposition example, where the mean values are DPCM encoded.

Citation Download Citation

Guido M. Schuster and Aggelos K. Katsaggelos "Optimal decomposition for quad-trees with leaf dependencies", Proc. SPIE 3024, Visual Communications and Image Processing '97, (10 January 1997); https://doi.org/10.1117/12.263281

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available

Members: $17.00

Non-members: $21.00 ADD TO CART

PROCEEDINGS
12 PAGES

DOWNLOAD PAPER SAVE TO MY LIBRARY

GET CITATION

RIGHTS & PERMISSIONS

Get copyright permission Get copyright permission on Copyright Marketplace

KEYWORDS

Distortion

Computer programming

Image segmentation

Algorithm development

Image compression

Raster graphics

Algorithms

Show All Keywords

Keywords/Phrases

Search In:

Publication Years