.TH QCCWAVWAVELETREDUNDANTDWT2D 3 "QCCPACK" "".SH NAMEQccWAVWaveletRedundantDWT2D, QccWAVWaveletInverseRedundantDWT2D,QccWAVWaveletRedundantDWT2DSubsample \- redundant discrete wavelet transform and inverse transform for a 2D signal.SH SYNOPSIS.B #include "libQccPack.h".sp.BI "int QccWAVWaveletRedundantDWT2D(const QccMatrix " input_matrix ", QccMatrix *" output_matrices ", int " num_rows ", int " num_cols ", int " num_scales ", const QccWAVWavelet *" wavelet );.br.BI "int QccWAVWaveletInverseRedundantDWT2D(const QccMatrix *" input_matrices ", QccMatrix " output_matrix ", int " num_rows ", int " num_cols ", int " num_scales ", const QccWAVWavelet *" wavelet );.br.BI "int QccWAVWaveletRedundantDWT2DSubsample(const QccMatrix *"  input_matrices ", QccMatrix " output_matrix ", int " num_rows ", int " num_cols ", int " num_scales ", int " subsample_pattern_row ", int " subsample_pattern_col ", const QccWAVWavelet *" wavelet );.br.BI "QccMatrix *QccWAVWaveletRedundantDWT2DAlloc(int " num_rows ", int " num_cols ", int " num_scales );.br.BI "void QccWAVWaveletRedundantDWT2DFree(QccMatrix *" rdwt ", int " num_rows ", int " num_scales );.SH DESCRIPTION.B QccWAVWaveletRedundantDWT2D()performs a redundantdiscrete wavelet transform (RDWT) of a two-dimensional matrix..I num_scalesgives the number of scales, or levels, of the decomposition..BR QccWAVWaveletRedundantDWT2D()implements a dyadic decomposition of.IR input_matrix with oversampling;that is, the lowpass subband is recursively decomposed into lowpass andhighpass bands for each level of decomposition.Unlike the usual critically sampled DWT(as implemented by.BR QccWAVWaveletDWT2D (3)),each subband has the same size as the original.IR input_matrix ;i.e., .I num_rowsrows and.I num_colscolumns..LPDuring each level or scale of decomposition, a baseband, a horizontal, avertical, and a diagonal subband are produced. The basebandsubband is then recursively decomposed. Consequently,the 2D RDWT produces.I "num_scales * 3"highpass subbands and one final baseband subband,for a total of.I "num_scales * 3 + 1"subbands.These subbands are returned in.I output_matriceswhich is an arrayof .I "num_scales * 3 + 1"matrices each of which having size.I num_rowsrows and .I num_colscolumns.The first entry in the.I output_matricesarray is the baseband matrix;subsequent entriescontain highpass bands of decreasing scale (increasingspatial resolution) in the order horizontal, vertical, anddiagonal.Sufficient storage space for.IR output_matrices must be allocated prior to calling.BR QccWAVWaveletRedundantDWT2D() ..LP.I waveletcan be either a filter-bank or lifting-schemeimplementation.In either case,the 2D RDWT is implemented as a separable transform in that eachrow is decomposed in a fashion similar to the 1D RDWT implemented by.BR QccWAVWaveletRedundantDWT1D (3)followed by a similar 1D decomposition along each column..LP.B QccWAVWaveletInverseRedundantDWT2D()performs the inverse RDWT of.IR input_matrices .Sufficient space for.I output_matrixmust be allocated prior to calling.BR QccWAVWaveletInverseRedundantDWT2D() ..LP.BR QccWAVWaveletRedundantDWT2DAlloc()allocates .I "num_scales * 3 + 1"subband matrices, each of size.I num_rowsby.IR num_cols ,returning the allocated subbands..BR QccWAVWaveletRedundantDWT2DFree()frees the matrices allocated via.BR QccWAVWaveletRedundantDWT2DAlloc() ..LPThe RDWT produces an oversampled wavelet transform; that is,an overcomplete expansion of the original signal.However,the coefficients of the usual critically sampled DWTare amongst the RDWT coefficients.More accurately, there exist.I 4 ^ num_scalessets of RDWT coefficients that are identical to a critically sampled,dyadic DWT. Each one of these.I 4 ^ num_scalesDWTs differs from the others in the subsampling phase choice(one can choose even or odd for both rows and columns) at each levelof the transform..BR QccWAVWaveletRedundantDWT2DSubsample()subsamples the coefficients output from.BR QccWAVWaveletRedundantDWT2D()to obtain the coefficients for a critically sampled DWT.Together,.IR subsample_pattern_rowand.IR subsample_pattern_colindicate which of the .I 4 ^ num_scalesDWT-coefficient sets to choose;the resulting critically sampled DWT then consists of the samecoefficients that would have been produced by a call to.BR QccWAVWaveletDWT2D (3)with these particular.IR subsample_pattern_rowand.IR subsample_pattern_colvalues..IR subsample_pattern_rowand.IR subsample_pattern_colboth can take on values 0 to.I "(2 ^ num_levels) - 1"(see.BR QccWAVWaveletDWT2D (3))..I num_scalesgives the number of levels of decomposition that exist in.IR input_matrices ,which is assumed to be an array of.I "num_scales * 3 + 1"matricesas produced by.BR QccWAVWaveletRedundantDWT2D() .The output of .BR QccWAVWaveletRedundantDWT2DSubsample()is a matrix of nested subbands as is present in the.BR QccWAVSubbandPyramid (3)structure.Sufficient space for.I output_matrixmust be allocated prior to calling.BR QccWAVWaveletInverseRedundantDWT2DSubsample() ..LP.BR QccWAVWaveletInverseRedundantDWT2D() is the "proper" procedure for inverting the RDWT.That is,.BR QccWAVWaveletInverseRedundantDWT2D() performs inverse filtering as wellas weighted "averaging" of the transform redundancies to properly reconstruct the original signal from theRDWT coefficients.A "quick and dirty" reconstruction is possible, however,by subsampling and then inverting using thecritically sampled inverse DWT, i.e., by calling.BR QccWAVWaveletRedundantDWT2DSubsample()and then.BR QccWAVWaveletInverseDWT2D() .Both these approaches to inverting the RDWT will producethe same results on unaltered RDWT coefficients; however,should the RDWT coefficients be processed in some fashion, say,through quantization, then.BR QccWAVWaveletInverseRedundantDWT2D()should be used to invert the transform.Additionally, this subsampling approach to inverting the RDWTworks only for.I subsample_pattern= 0, which is the only subsampling pattern whose phase choicesmatch those assumed by.BR QccWAVWaveletInverseDWT2D() ..SH NOTESThe notion of an RDWT apparently dates back to the work of Holschneider.IR "et al".and Dutilleux who devised a redundant transform implemented via the so-called.IR "algorithme a trous" .This filter-bank algorithm is similar to the usual Mallat algorithmfor the critically sampled DWT in that it implementsthe wavelet transform with filter banks. The key difference betweenthe two approaches is thatthe subsampling at the end of every scale of the transform as used inthe Mallat algorithm is not performed in the.IR "algorithm a trous" ,and the filters, which are the same at every scale in the Mallatalgorithm, change for every scale.Specifically, the.IR "algorithm a trous"calls for the insertion of "holes" ("trous" in French)between each filter tap; that is, the filters used in eachscale of the.IR "algorithm a trous"decompositionare the filters of the previous scale upsampled by a factor of 2..LPShensa points out that the Mallat and .I "a trous"implementations are very closely related; in fact, it is possible to obtain the coefficients for the Mallatalgorithm by subsampling, or decimating, the coefficientsresulting from the.IR "algorithm a trous" ,except possibly at the matrix boundaries when symmetric extension is used.This observation leadsto an "alternative" implementation of the.IR "algorithm a trous" ,and it is this implementation that is used here in.BR QccWAVWaveletRedundantDWT2D() .This alternative implementation of the.IR "algorithm a trous" eliminates the above-mentioned symmetric-boundary inconsistencies;in addition, the alternative implementationpermits the direct use of lifting instead of filter banks for improvedcomputation efficiency..SH "RETURN VALUES"These routinesreturn 0 on success and 1 on error..SH "SEE ALSO".BR QccWAVWaveletRedundantDWT1D (3),.BR QccWAVWaveletDWT2D (3),.BR QccWAVWaveletInverseDWT2D (3),.BR QccPackWAV (3),.BR QccPack (3).LPM. Holschneider, R. Kronland-Martinet, J. Morlet, andP. Tchamitchian,"A Real-Time Algorithm for Signal Analysis with the Helpof the Wavelet Transform," in.IR "Wavelets: Time-Frequency Methods and Phase Space",Berlin: Springer-Verlag, pp. 286-297, 1989..LPP. Dutilleux,"An Implementation of the Algorithm A Trous to Compute the Wavelet Transform,"in.IR "Wavelets: Time-Frequency Methods and Phase Space",Berlin: Springer-Verlag, pp. 298-304, 1989..LPM. J. Shensa,"The Discrete Wavelet Transform: Wedding the A Trous and Mallat Algorithms,".IR "IEEE Trans. Signal Processing" ,vol. 40, no. 10, pp. 2464-2482, Oct. 1998..SH AUTHORCopyright (C) 1997-2005  James E. Fowler.\"  The programs herein are free software; you can redistribute them an.or.\"  modify them under the terms of the GNU General Public License.\"  as published by the Free Software Foundation; either version 2.\"  of the License, or (at your option) any later version..\"  .\"  These programs are distributed in the hope that they will be useful,.\"  but WITHOUT ANY WARRANTY; without even the implied warranty of.\"  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the.\"  GNU General Public License for more details..\"  .\"  You should have received a copy of the GNU General Public License.\"  along with these programs; if not, write to the Free Software.\"  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.