Examples of Discrete Transforms (779442), страница 3
Текст из файла (страница 3)
. , N- 1.(4.72)k , n = 0 , 1 , ..., N - l .(4.73)DCT-IV:cLV(n) =pNcos ( ( 5 + t , cN. + i ) " ) ,The constants yj in (4.70) - (4.72) are given byfor j = 0 or j = N ,Tj =1(4.74)otherwise.The coefficients ck(n) are the elements of the orthonormal basis vectorsck(n) = [ck(o),ck(l),. . .lT.In order to point out clearly how (4.70) - (4.73) are to be understood, let usconsider the forward and inverse DCT-11:N-landN-lEspecially the DCT-I1 is of major importance in signal coding because itis close to the KLT for first-order autoregressive processes with a correlationcoefficient that is close to one.' To illustrate this, we consider the inverse ofthe correlation matrix of an A R ( 1 ) process, which is given bylSee Section 5.3 for the definition of an AR process.4.5.
Discrete CosineTransforms95(4.77)with P = p / ( l + p’)). The basis vectors of the DCT-I1 are the eigenvectors oftridiagonal symmetric matricesof the formQ=- ( l - a) -a-a1-a---a..(4.78)1-a-a(1-a)-We see that Q approaches R;: for p + 1. Since the eigenvectors of R,,are equal to those of R;: the DCT-I1 approaches the KLT for p + 1. Thismeans that the DCT-I1 has good decorrelation properties when the processwhich is to be transformed has high correlation ( p + 1).This is the case formost images, which explains why most image coding standards (e.g.
JPEG,MPEG [79, 157, 108, 561) are based on the DCT-11. Compared to the KLT,the DCT-I1 has the advantage that fast implementations based on the FFTalgorithm exist [122].Application in Image Coding. In most standards for transform coding ofimages, the two-dimensional cosine transform is used [79,157,108,56].Figure4.6gives an example. First, the two-dimensional signal is decomposed intonon-overlapping blocks. Each of these blocks is then transformed separately.This operation can be written as YNXN= UT X N ~ UN, where X N ~ isNsuch a signal block and U is the DCT-I1 transform matrix whose columnscontain the basis vectors of the DCT-11. Instead of the original X , therepresentation Y is quantized and coded. From the quantized representationY ’ = Q ( Y ) an approximation of the original is finally reconstructed.InFigure 4.6 we see that most of the energy of the transformedsignal isconcentrated in the top left sub-image.
Such a concentration of signal energyin a few coefficients is the key to efficient compression. If we were to simplytransmit the top left sub-image and neglect the others, we already couldachieve drastic compression, while the reconstructedsignal would still berelatively close to the original.TransformsChapterDiscrete4. ofExamples96IFigure 4.6. Transform coding of images; (a) original, divided into N(b) transformed image after rearranging the pixels.4.6XN blocks;DiscreteSineTransformsThe discrete sine transforms (DSTs) are classified as follows [122]:DST-I:k , n = 1 , 2 ,..., N - l .s : ( n ) = g sin($),(4.79)DST-11:, k , n = 0,1, ..., N - l .N(4.80)DST-111:N,k , n = 0 , 1 , ..., N - l .(4.81)DST-IV:siv(.)=J"N sin ( ( k + f ) (Nn + i ) a ) ,-*k , n = 0 , 1 , ..., N - l .(4.82)The constants ^/j in (4.79) - (4.81) arefor j = o or j = N ,^/j=1otherwise.(4.83)974.7.
The Discrete Hartley TransformTo be explicit, the forward and the inverse DST-I1 are given byN-lx;'(~c)=C z ( n )sf'cn)n=O(4.84)N-l=y k + l gC x(n) sin ( ( k + 1)N( n+;IT),n=OandN-lz(n) =C x;'(~c)sf'cn)k=O-gyx;~(lc)yk+1sin ( ( k + 1)N( n+t,.)(4.85)k=OThe DST-I1 is related to the KLT by the fact that the KLT for an AR(1)process with correlation coefficient y + -1 approaches the DST-11. Thus, theDST-I1 has good compaction propertiesfor processes with negative correlationof adjacent samples.4.7 The DiscreteHartleyTransformThe Hartley transform discussedasin Section 2.3 received little attention untilits discrete version, the discrete Hartley transform (DHT), was introduced inthe early 1980sby Wang [158, 159, 1601 and Bracewell [13, 14, 151.Likeother discrete transforms such as the DFT or the DCT, the DHT can beimplemented efficiently through a factorization of the transform matrix.
Thisresults in fast algorithms that are closely related to the FFT,and in fact, thefast Hartley transform (FHT) can be computed via the FFT, and vice versa,the FFT can be implemented via the FHT [161, 14, 1391.For example, in[l391 a split-radix approach for the FHT has been proposed.The forward and inverse discrete Hartley transform pair is given byN-lXH(IC)=27rnlcC z ( n )cas Nn=O(4.86)z(n) =1 N-lCk=OxH(L)21rnlccas N 798Chapter 4. Examples o f Discrete Transforms+where cas 4 = cos 4 sin 4.
The signal z ( t )is considered to be real-valued, sothat also the transform is real-valued. As with the DFT, the sequence X H ( S )is periodic with period N .Note that apart from the prefactor 1/N the DHT is self-inverse, whichmeans that the same computer programor hardware can be usedfor theforward and inverse transform. This is not the case for the DFT, where areal-valued signal is transformed into a complex spectrum.We may interpret thebasis sequences cas (27rnklN)as sample values of thebasis functions cas w k t with wk = 27rk/N. The basis function with the highestfrequency then occurs for k = N / 2 .
The kth and the ( N - k)th frequency arethe same.The relationships between the DHT and the DFT areeasily derived. Usingthe fact that1-je j 4 = -cas 4 cas ( - 4 )(4.87)22and the periodicity in N , we get+’+L(4.88)where X ( k ) denotes the DFT. The DHT can be expressed in terms of theDFT asX H ( 5 ) = ?J?{X(k))- S ( X ( 5 ) ) .(4.89)Theproperties of theDHT can easily be derived from the definition(4.86). Like in the continuous-time case, most of them are very similar to theproperties of the Fourier transform.
We will briefly discuss the most importantones. The proofs are essentially the same as for the continuous-time case andare omitted here.Time Inversion. From (4.86) we see thatz ( N - n) t)X H ( N - n).Shifting. A circular time shift by p yieldsz( (n+ p ) mod N )(4.90)4.7. The DiscreteTransformHartley99Circular Convolution. The correspondence for a circular convolution oftwo time sequences ~ ( nand) y(n) is(4.92)Multiplication. The correspondence for products z(n)y(n)iswhere the convolutions have to be carried out in a circular manner.
Forexample an expression ZH( k ) = XH(L)* YH( - k ) meansRemarks. The question of whether the DFT or the DHT should be usedin an application very much depends on the application itself. As mentionedearlier, fast algorithms exist for both transforms, and one fast transform canbe used in order to implement the other transform in an efficientway.Forboth the FFT and the FHT thecomplexity is Nlog, N . An advantage ofthe DHT is the fact that the DHT is self-inverse, so that only one softwareroutine or hardware device is needed for the forward and inverse FHT.
Forthe forward and inverse FFT of a real signal, two different routines or devicesare required. The DHT is somehow conceptually simpler than the DFTif theinput signal is real, but all operations can be carried out with the FFT andthe FHT with the same complexity.1004.8Chapter 4. Examples o f Discrete TransformsThe Hadamardand Walsh-HadamardTransformsThe basis vectors of the discrete Hadamard and the discrete Walsh-Hadamardtransforms consist of the values fa;just like the Walsh functions discussedin Section 3.2.6. Both transforms are unitary.Basically they differ only in theorder of the basis vectors.We havey=Hx,X= Hy,(4.95)where X denotes the signal, y the representation, andH the transform matrixof the Hadamard transform.
H is symmetric and self-inverse:H T = H = H-l.(4.96)The transform matrix of the 2x2-Hadamard transform is given by(4.97)From this, all transform matrices H ( n )of size2 n = 2 k , k E IN can be calculated recursively [133]:(4.98)The Walsh-Hadamardtransform is obtained by takingtheHadamardtransform and rearranging the basis vectors according to the number of zerocrossings [66]. Somehow,this yields an order of the basis vectors with respectto their spectral properties.2There exist Hadamard matrices whose dimension is not a power of two..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
