Skip to main content
SpringerLink
Log in

A Survey on Lifting-based Discrete Wavelet Transform Architectures

  • Published:
Journal of VLSI signal processing systems for signal, image and video technology Aims and scope Submit manuscript

Abstract.

In this paper, we review recent developments in VLSI architectures and algorithms for efficient implementation of lifting based Discrete Wavelet Transform (DWT). The basic principle behind the lifting based scheme is to decompose the finite impulse response (FIR) filters in wavelet transform into a finite sequence of simple filtering steps. Lifting based DWT implementations have many advantages, and have recently been proposed for the JPEG2000 standard for image compression. Consequently, this has become an area of active research and several architectures have been proposed in recent years. In this paper, we provide a survey of these architectures for both 1-dimensional and 2-dimensional DWT. The architectures are representative of many design styles and range from highly parallel architectures to DSP-based architectures to folded architectures. We provide a systematic derivation of these architectures along with an analysis of their hardware and timing complexities.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. S. Mallat, “A Theory for Multiresolution Signal Decomposition: The Wavelet Representation,” IEEE Trans. Pattern Analysis And Machine Intelligence, vol. 11, no. 7, 1989, pp. 674–693.

    Article  MATH  Google Scholar 

  2. T. Acharya and P. S. Tsai, JPEG2000 Standard for Image Compression: Concepts, Algorithms and VLSI Architectures. John Wiley & Sons, Hoboken, New Jersey, 2004.

  3. W. Sweldens, “The Lifting Scheme: A Custom-Design Construction of Biorthogonal Wavelets,” Applied and Computational Harmonic Analysis, vol. 3, no. 15, 1996, pp. 186–200.

    Article  MathSciNet  MATH  Google Scholar 

  4. I. Daubechies and W. Sweldens, “Factoring Wavelet Transforms into Lifting Schemes,” The J. of Fourier Analysis and Applications, vol. 4, 1998, pp. 247–269.

    Article  MathSciNet  MATH  Google Scholar 

  5. M.D. Adams and F. Kossentini, “Reversible Integer-to-Integer Wavelet Transforms for Image Compression: Performance Evaluation and Analysis,” IEEE Trans. on Image Processing, vol. 9, 2000, pp. 1010–1024.

    Article  MathSciNet  MATH  Google Scholar 

  6. C.C. Liu, Y.H. Shiau, and J.M. Jou, “Design and Implementation of a Progressive Image Coding Chip Based on the Lifted Wavelet Transform,” in Proc. of the 11th VLSI Design/CAD Symposium, Taiwan, 2000.

  7. J.M. Jou, Y.H. Shiau, and C.C. Liu, “Efficient VLSI Architectures for the Biorthogonal Wavelet Transform by Filter Bank and Lifting Scheme,” in IEEE International Symposium on Circuits and Systems, Sydney, Australia, 2001, pp. 529–533.

  8. C.J Lian, K.F. Chen, H.H. Chen, and L.G. Chen, “Lifting Based Discrete Wavelet Transform Architecture for JPEG2000,” in IEEE International Symposium on Circuits and Systems, Sydney, Australia, 2001, pp. 445–448.

  9. P.-Y. Chen, “VLSI Implementation for One-Dimensional Multilevel Lifting-Based Wavelet Transform,” IEEE Transactions on Computers, vol. 53, no. 4, 2004.

  10. W.H. Chang, Y.S. Lee, W.S. Peng, and C.Y. Lee, “A Line-Based, Memory Efficient and Programmable Architecture for 2D DWT Using Lifting Scheme,” in IEEE International Symposium on Circuits and Systems, Sydney, Australia, 2001, pp. 330–333.

  11. C.T. Huang, P.C. Tseng, and L.G. Chen, “Flipping Structure: An Efficient VLSI Architecture for Lifting-Based Discrete Wavelet Transform,” in IEEE Transactions on Signal Processing, 2004, pp. 1080–1089.

  12. K. Andra, C. Chakrabarti, and T. Acharya, “A VLSI Architecture for Lifting-Based Forward and Inverse Wavelet Transform,” IEEE Trans. of Signal Processing, vol. 50, no. 4, 2002, pp. 966–977.

    Article  Google Scholar 

  13. M. Vishwanath, “The Recursive Pyramid Algorithm for the Discrete Wavelet Transform,” in IEEE Transactions on Signal Processing, vol. 42, 1994, pp. 673–676.

    Article  Google Scholar 

  14. H. Liao, M.K. Mandal, and B.F. Cockburn, “Novel Architectures for Lifting-Based Discrete Wavelet Transform,” in Electronics Letters, vol. 38, no. 18, 2002, pp. 1010–1012.

    Article  Google Scholar 

  15. H. Liao, M.K. Mandal, and B.F. Cockburn, “Efficient Architectures for 1-D and 2-D Lifting-Based Wavelet Transform,” IEEE Transactions on Signal Processing, vol. 52, no. 5, 2004, pp. 1315–1326.

    Article  MathSciNet  Google Scholar 

  16. G.C. Jung, D.Y. Jin, and S.M. Park, “An Efficient Line Based VLSI Architecture for 2-D Lifting DWT,” in The 47th IEEE International Midwest Symposium on Circuits and Systems, 2004.

  17. M. Martina, G. Masera, G. Piccinini, and M. Zamboni, “Novel JPEG 2000 Compliant DWT and IWT VLSI Implementations,” Journal of VLSI Signal Processing, vol. 34, 2003, pp. 137–153.

    Article  Google Scholar 

  18. C. Chrysafis and A. Ortega, “Line-Based, Reduced Memory, Wavelet Image Compression,” IEEE Trans. on Image Processing, vol. 9, no. 3, 2000, pp. 378–389.

    Article  MathSciNet  MATH  Google Scholar 

  19. J. Reichel, M. Nadenau, and M. Kunt, “Row-Based Wavelet Decomposition Using the Lifting Scheme,” Proceedings of the Workshop on Wavelet Transforms and Filter Banks, Brandenburg an der Havel, Germany, March 5–7, 1999.

  20. W. Jiang and A. Ortega, “Lifting Factorization-Based Discrete Wavelet Transform Architecture Design,” IEEE Trans, on Circuits and Systems for Video Technology, vol. 11, 2001, pp. 651–657.

    Article  Google Scholar 

  21. M. Ferretti and D. Rizzo, “A Parallel Architecture for the 2-D Discrete Wavelet Transform with Integer Lifting Scheme,” Journal of VLSI Signal Processing, vol. 28, 2001, pp. 165–185.

    Article  MATH  Google Scholar 

  22. M.Y. Chiu, K.-B. Lee, and C.-W. Jen, “Optimal Data Transfer and Buffering Schemes for JPEG 20000 Encoder,” in Proceedings of the IEEE Workshop on Design and Implementation of Signal Processing Systems, 2003, pp. 177–182.

  23. C.-T. Huang, P.-C. Tseng, and L.-G. Chen, “Memory Analysis and Architecture for Two-Dimensional Discrete Wavelet Transform,” in Proceedings of the IEEE Int. Conf. on Acoustics, Speech and Signal Processing, 2004, pp. V13–V16.

  24. P.-C. Tseng, C.-T. Huang, and L.-G. Chen, “Generic RAM-Based Architecture for Two-Dimensional Discrete Wavelet Transform with Line-Based Method,” in Proceedings of the Asia-Pacific Conference on Circuits and Systems, 2002, pp. 363–366.

Download references

Author information

Authors and Affiliations

  1. Department of Electrical Engineering, Arizona State University, Tempe, Arizona, 85287-5706

    Tinku Acharya & Chaitali Chakrabarti

Authors
  1. Tinku Acharya
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Chaitali Chakrabarti
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tinku Acharya.

Additional information

Tinku Acharya received his B.Sc. (Honors) in Physics, B.Tech. and M.Tech. in Computer Science from University of Calcutta, India, and the Ph.D. in Computer Science from University of Central Florida, USA, in 1984, 1987, 1989, and 1994, respectively. He is currently the Chief Technology Officer of Avisere Inc., Tucson, Arizona, USA. Dr. Acharya is also an Adjunct Professor in the Department of Electrical Engineering, Arizona State University, Tempe, USA.

Before joining Avisere, Dr. Acharya served in Intel Corporation (1996–2002), where he led several R&D teams toward development of algorithms and architectures in image and video processing, multimedia computing, PC-based digital camera, reprographics architecture for color photo-copiers, 3G cellular telephony, analysis of next-generation microprocessor architecture, etc. Before Intel, Dr. Acharya was a consulting engineer at AT&T Bell Laboratories (1995–1996), a research faculty at the Institute of Systems Research, Institute of Advanced Computer Studies, University of Maryland at College Park (1994–1995), and held visiting faculty positions at Indian Institute of Technology, Kharagpur. He served as Systems Analyst in National Informatics Center, Planning Commission, Government of India (1988–1990). He collaborated in research and development with Xerox Palo Alto Research Center (PARC), Eastman Kodak Corporation, and many other institutions worldwide.

Dr. Acharya is inventor of 88 US patents and 14 European patents. He authored over 80 technical papers and four books—Image Processing: Principles and Applications (Wiley, New Jersey, 2005), JPEG2000 Standard for Image Compression: Concepts, Algorithms, and VLSI Architectures (Wiley, 2004), Information Technology: Principles and Applications (Prentice-Hall India, 2004), and Data Mining: Multimedia, Soft Computing and Bioinformatics (Wiley, 2003).

Dr. Acharya is a Fellow of the National Academy of Engineers (India), Life Fellow of the Institution of Electronics and Telecommunication Engineers (FIETE), and Senior Member of IEEE. His current research interests are in computer vision, image processing, multimedia data mining, bioinformatics, and VLSI architectures and algorithms.

Chaitali Chakrabarti received the B.Tech. degree in electronics and electrical communication engineering from the Indian Institute of Technology, Kharagpur, India in 1984, and the M.S. and Ph.D degrees in electrical engineering from the University of Maryland at College Park, USA, in 1986 and 1990 respectively. Since August 1990, she has been with the Department of Electrical Engineering, Arizona State University, Tempe, where she is now a Professor. Her research interests are in the areas of low power embedded systems design including memory optimization, high level synthesis and compilation, and VLSI architectures and algorithms for signal processing, image processing and communications.

Dr. Chakrabarti is a member of the Center for Low Power Electronics, the Consortium for Embedded Systems and Connection One. She received the Research Initiation Award from the National Science Foundation in 1993, a Best Teacher Award from the College of Engineering and Applied Sciences, ASU, in 1994, and the Outstanding Educator Award from the IEEE Phoenix section in 2001. She has served on the program committees of ICASSP, ISCAS, SIPS, ISLPED and DAC. She is currently an Associate Editor of the IEEE Transactions on Signal Processing and the Journal of VLSI Signal Processing Systems. She is also the TC Chair of the sub-committee on Design and Implementation of Signal Processing Systems, IEEE Signal Processing Society.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Acharya, T., Chakrabarti, C. A Survey on Lifting-based Discrete Wavelet Transform Architectures. J VLSI Sign Process Syst Sign Image Video Technol 42, 321–339 (2006). https://doi.org/10.1007/s11266-006-4191-3

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11266-006-4191-3

Keywords:

Search

Navigation