B-term approximation using tree-structured Haar transforms

Hsin-Han Ho; Karen O. Egiazarian; Sanjit K. Mitra

doi:10.1117/12.816680

Translator Disclaimer

10 February 2009 B-term approximation using tree-structured Haar transforms

Hsin-Han Ho; Karen O. Egiazarian; Sanjit K. Mitra

Author Affiliations +

Proceedings Volume 7245, Image Processing: Algorithms and Systems VII; 724505 (2009) https://doi.org/10.1117/12.816680
Event: IS&T/SPIE Electronic Imaging, 2009, San Jose, California, United States

Abstract

We present a heuristic solution for B-term approximation using Tree-Structured Haar (TSH) transforms. Our solution consists of two main stages: best basis selection and greedy approximation. In addition, when approximating the same signal with different B constraint or error metric, our solution also provides the flexibility of having less overall running time at expense of more storage space. We adopted lattice structure to index basis vectors, so that one index value can fully specify a basis vector. Based on the concept of fast computation of TSH transform by butterfly network, we also developed an algorithm for directly deriving butterfly parameters and incorporated it into our solution. Results show that, when the error metric is normalized ℓ₁-norm and normalized ℓ₂-norm, our solution has comparable (sometimes better) approximation quality with prior data synopsis algorithms.

Citation Download Citation

Hsin-Han Ho, Karen O. Egiazarian, and Sanjit K. Mitra "B-term approximation using tree-structured Haar transforms", Proc. SPIE 7245, Image Processing: Algorithms and Systems VII, 724505 (10 February 2009); https://doi.org/10.1117/12.816680

ACCESS THE FULL ARTICLE