Share Email Print

Proceedings Paper

Efficient coding of wavelet trees and its applications in image coding
Author(s): Bin Zhu; En-hui Yang; Ahmed H. Tewfik; John C. Kieffer
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper Abstract

We propose in this paper a novel lossless tree coding algorithm. The technique is a direct extension of the bisection method, the simplest case of the complexity reduction method proposed recently by Kieffer and Yang, that has been used for lossless data string coding. A reduction rule is used to obtain the irreducible representation of a tree, and this irreducible tree is entropy-coded instead of the input tree itself. This reduction is reversible, and the original tree can be fully recovered from its irreducible representation. More specifically, we search for equivalent subtrees from top to bottom. When equivalent subtrees are found, a special symbol is appended to the value of the root node of the first equivalent subtree, and the root node of the second subtree is assigned to the index which points to the first subtree, an all other nodes in the second subtrees are removed. This procedure is repeated until it cannot be reduced further. This yields the irreducible tree or irreducible representation of the original tree. The proposed method can effectively remove the redundancy in an image, and results in more efficient compression. It is proved that when the tree size approaches infinity, the proposed method offers the optimal compression performance. It is generally more efficient in practice than direct coding of the input tree. The proposed method can be directly applied to code wavelet trees in non-iterative wavelet-based image coding schemes. A modified method is also proposed for coding wavelet zerotrees in embedded zerotree wavelet (EZW) image coding. Although its coding efficiency is slightly reduced, the modified version maintains exact control of bit rate and the scalability of the bit stream in EZW coding.

Paper Details

Date Published: 27 February 1996
PDF: 12 pages
Proc. SPIE 2727, Visual Communications and Image Processing '96, (27 February 1996); doi: 10.1117/12.233266
Show Author Affiliations
Bin Zhu, Univ. of Minnesota/Twin Cities (United States)
En-hui Yang, Univ. of Minnesota/Twin Cities (United States)
Ahmed H. Tewfik, Univ. of Minnesota/Twin Cities (United States)
John C. Kieffer, Univ. of Minnesota (United States)

Published in SPIE Proceedings Vol. 2727:
Visual Communications and Image Processing '96
Rashid Ansari; Mark J. T. Smith, Editor(s)

© SPIE. Terms of Use
Back to Top