Comparison of Image Decompositions Through Inverse Difference and Laplacian Pyramids

Comparison of Image Decompositions Through Inverse Difference and Laplacian Pyramids

Roumen Kountchev (Radiocommunications Department, Technical University of Sofia, Sofia, Bulgaria), Stuart Rubin (Space and Naval Warfare Systems Center, San Diego, CA, USA), Mariofanna Milanova (Department of Computer Science, University of Arkansas at Little Rock, Little Rock, AR, USA) and Roumiana Kountcheva (T & K Engineering, Sofia, Bulgaria)
DOI: 10.4018/ijmdem.2015010102
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

In this work, the Inverse Difference Pyramid (IDP) and its modification – the Reduced IDP (RIDP), are compared and evaluated with the famous Laplacian Pyramid (LP) for multi-level decomposition of digital images. The comparison comprises: the structures of LP and IDP, the image representation through LP and IDP in the pixel space and in the spectrum space of the Fourier transform, the efficiency of both transforms for the aims of the progressive image transfer, the LP and the IDP computation graphs and the evaluation of the computational complexity of the algorithms for the 3-level reduced LP and the 3-level reduced IDP. The influence of the quantization noise on both decompositions is also analyzed. On the basis of the comparison are outlined the basic advantages of the RIDP for pipeline image processing. The results obtained could be used for the design of coders for image compression, aimed at real-time applications, etc.
Article Preview

Introduction

Contemporary IT involves the management and processing of huge amounts of visual information: still images, video, and multimedia. The efficient storage and compression of this information requires the use of various techniques for image representation.

The primary form for digital image presentation, which is not compressed, is the matrix (Gonzalez & Woods). This approach ensures unchanged image quality, but, its storage and processing need significant resources and high computational power.

The aim of the image decomposition is to present the digital image in a compact (compressed) form, by limiting the number of decomposition components in correspondence to the permissible error value (Rao, Kim & Hwang, Pratt; Rosenfeld; Netravali & Haskell). The decomposition could be performed either using the well-known linear orthogonal transforms: the Karhunen-Loeve Transform (KLT), the Singular Value Decomposition (SVD), the Discrete Fourier Transform (DFT), the Discrete Cosine Transform (DCT), the Walsh-Hadamard Transform (WHT), etc. (Rao, Kim & Hwang, Pratt), or through some kind of pyramidal representation (Topiwala, Burt & Adelson, Bovik). The secondary forms for image representation are obtained from the primary and for this could be used pyramids, multi-dimensional vectors, linear orthogonal transforms, tree structures, algebraic models, models for visual information perception, etc.

The most famous approach for pyramidal image representation is based on the Laplacian pyramid. In general, the pyramidal representation (Netravali & Haskell, Burt & Adelson, Bovik, Liu et al.; Vaidyanathan) describes the image with progressively increased resolution, which corresponds to the layers of the Gaussian-Laplacian pyramid. Its derivatives are the Reduced Sum/Difference pyramid; the S-transform pyramid, the Hierarchy-Embedded Differential pyramid; the Least Squares pyramid, the Morphological pyramid, etc. This group of pyramids is called overcomplete (Goyal, Vetterli & Thao) because the needed memory is larger than that for the non-compressed image.

The general disadvantages of the Laplacian pyramids are:

  • For case of lossy coding, the quantization in the LP results in relatively high quantization noise.

  • The needed memory volume is about 33% larger than that of the original image. In order to make this volume smaller, several LP modifications had already been developed, such as the Reduced LP (RLP) (Velho et al., Aiazzi et al.); the pyramid based on reduced sums or reduced differences (Reduced-Sum/Reduced-Difference Pyramid, RSP/RDP); the S-Transform Pyramid (STP) (Rabbani & Jones, Woods), etc.

  • The principle of their creation: the LP base is calculated first and after that are calculated the higher levels (up to the pyramid top). This approach generates some difficulties because the progressive image data transfer requires the top of the pyramid (the highest layer) to be transferred first.

This paper presents an image decomposition method based on the Inverse Difference Pyramid (IDP) (Kountchev et al., 2005), which permits one to avoid the second disadvantage of the Laplacian pyramids, but unfortunately the needed memory volume size for the IDP is also about 33% larger than the original. The IDP modification - the Reduced Inverse Pyramid decomposition (Kountchev & Kountcheva, Kountchev (Ed.)] - overcomes this problem and permits a higher compression and better retained image quality. The quantization noise in IDP (RIDP) is also lower than that in LP. The structures of the IDP and RIDP successfully solve the problem with the progressive image transfer.

In this paper the IDP decomposition and its modification – the Reduced IDP - are compared with the Laplacian pyramid (LP) and the Reduced LP (RLP), because the LP (resp. the RLP) is the most famous fundamental technique in this area.

This paper comprises the comparison of the structures and the computation graphs of the LP and the IDP; the comparison of their representations in the image space and in the spectrum space of the Fourier transform; the evaluation of both transforms in respect to progressive image transfer; the recursive implementations of IPD and LP; the analysis of the quantization noise on the quality of the restored images, and the evaluation of the computational complexity of the algorithms (in detail is given the analysis for the 3-level reduced LP and the 3-level reduced IDP).

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing