(DFT) 009 DFT: Discrete Fourier Transform N x[n] DFT N 1 X[k] = x[n]wn kn, k = 0, 1,, N 1 (6 ) n=0 1) W N = e j π N W N twidd

Transcription

1 (DFT) 6-1 DFT 6- DFT FFT 6-3 DFT c 011 1/(0)

2 (DFT) 009 DFT: Discrete Fourier Transform N x[n] DFT N 1 X[k] = x[n]wn kn, k = 0, 1,, N 1 (6 ) n=0 1) W N = e j π N W N twiddle factor DFT X[k] x[n] N x[n] DFT X[k] W N x[n] = 1 N N 1 X[k]WN nk, n = 0, 1,, N 1 (6 ) k=0 X[k] x[n] DFT IDFT: Inverse DFT 6 DFT N 1 x = [x(0), x(1),, x(n 1)] T X = [X(0), X(1),, X(N 1)] T DFT IDFT X = W N x x = 1 N W N X (6 3) (6 4) W N N N k n [W N ] k,n = WN kn W N W N W N = NI N DFT x[n] N DFS: Discrete Fourier Series 1) x[n] DTFT: Discrete-Time Fourier Transform 1 N X[k] = X(e jω ) ω= π N k 1) DFT N DTFT c 011 /(0)

3 6 DFT X[k], X 1 [k], X [k] x[n], x 1 [n], x [n] DFT a, b (( )) N N R{ } I{ } R N N DFT N ax 1 [n] + bx [n] ax 1 [k] + bx [k] X[n] Nx[(( k)) N ] x[((n m)) N ] WN kmx[k] W N lnx[n] N 1 X[((k l)) N] x 1 [m]x [((n m)) N ] X 1 [k]x [k] m=0 x 1 [n]x [n] 1 N 1 X 1 [l]x [((l k)) N ] N x [n] X [(( k)) N ] x [(( n)) N ] X [k] R {x[n]} X ep [k] = 1 {X[((k)) N] + X [(( k)) N ]} ji {x[n]} X op [k] = 1 {X[((k)) N] X [(( k)) N ]} x ep [k] = 1 {x[n] + x [(( n)) N ]} R {X[k]} x op [n] = 1 {x[n] x [(( n)) N ]} ji {X[k]} X[k] = X [(( k)) N ] R {X[k]} = R {X[(( k)) N ]} x[n] R ji {X[k]} = ji {X[(( k)) N ]} X[k] = X[(( k)) N ] X[k] = X[(( k)) N ] l=0 1) A.V. Oppenheim, R.W. Schafer, and J.R. Buck, Discrete-Time Signal Processing, nd ed, Prentice Hall, c 011 3/(0)

4 (FFT) 009 DFT DFT DFT FFT: Fast Fourier Transform N N DFT (N/) 1 X[k] = x[r]wn kr r=0 (N/) 1 + r=0 x[r + 1]W kr+k N = G[k] + W k N H[k], k = 0, 1,, N 1 (6 5) G[k] = (N/) 1 r=0 x[r]w kr N/ H[k] = (N/) 1 r=0 x[r + 1]W kr N/ WN = W N/ X[k] x[r] N/ DFT G[k] x[r + 1] N/ DFT H[k] WN k W N = e j π N W kn N = Wk(n+N) N = W (k+n)n N (6 6) G[k + N/] = G[k], H[k + N/] = H[k] (6 3) N N(N 1) (6 5) (N + N /) N / N > N (6 5) (6 5) FFT FFT(FFT: Decimation-in-time FFT) 1) (6 5) N DFT k = 0, 1,, N/ 1 X[k] = G[k] + W k N H[k], (6 7) X[k + N/] = G[k + N/] + W k+n/ N H[k + N/] = G[k] + W N/ N Wk NH[k] (6 8) W N/ N = e j π N N = e jπ = 1 WN k N = 8 = 3 FFT 3 N = v v 1 1 N = v c 011 4/(0)

5 G[k] X[k] H[k] W k N X[k + N/] 6 x[0] X[0] x[4] W 0 8 X[1] x[] W 0 8 X[] x[6] W 0 8 W 8 X[3] x[1] W 0 8 X[4] x[5] W 0 8 W 1 8 X[5] x[3] W 0 8 W 8 X[6] x[7] W 0 8 W 8 W 3 8 X[7] 6 FFT (N = 8 = 3 ) FFT 1 N/ v vn/ = (N/) log N ( N/) log N N log N N DFT FFT FFT Decimation-in-frequency FFT 1) FFT x[n] DFT X[k] DFT FFT Split-Radix FFT ) DFT N N prime factor FFT 1) DFT real-valued FFT, 3) prune 4) Winograd Winograd DFT 1) 1) A.V. Oppenheim, R.W. Schafer, and J.R. Buck, Discrete-Time Signal Processing, nd ed, Prentice Hall, c 011 5/(0)

6 ) S.G. Johnson and M. Frigo, A Modified Split-Radix FFT With Fewer Arithmetic Operations, IEEE Trans. on SP, vol.55, no.1, pp , ) H. Sorensen, D. Jones, M. Heideman, and C. Burrus, Real-valued Fast Fourier Transform Algorithms, IEEE Trans. on ASSP, vol.35, no.6, pp , ) H. Sorensen and C. Burrus, Efficient Computation of The DFT with Only A Subset of Input or Output Points, IEEE Trans. on SP, vol.41, no.3, pp , c 011 6/(0)

7 (Circular Convolution) 009 FFT DFT DFT N x 1 [n] x [n] x 1 [n], x [n] N 1 x 3 [n] = x 1 [n] N x [n] x 1 [((m)) N ]x [((n m)) N ], n = 0, 1,, N 1 m=0 1) (( )) N N x 1 [n], x [n] N x 3 [n] = x [n] N x 1 [n] (6 9) DFT x 3 [n] N N DFT N 1 X 3 [k] = x 3 [n]wn kn N 1 = m=0 N 1 = m=0 n=0 N 1 x 1 [((m)) N ]WN km N 1 x 1 [m]wn km l=0 N 1 N 1 = n=0 n=0 m=0 x 1 [((m)) N ]x [((n m)) N ]W kn N x [((n m)) N ]W k(n m) N x [l]wn kl, k = 0, 1,, N 1 ( W N ) (6 0) x 1 [n], x [n] N DFT X 1 [k], X [k] X 3 [k] = X 1 [k]x [k] DFT X 1 [k]x [k] = X [k]x 1 [k] x 1 [n], x [n] L, M x 1 [n] = 0, x [n] = 0, n < 0 N L + M 1 x [((l)) N ] = x [l] = 0, (L 1) l 1 x 1 [n], x [n] N 0 n < N L 1 L 1 x 1 [n] N x [n] = x 1 [m]x [((n m)) N ] = x 1 [m]x [n m] = x 1 [n] x [n] m=0 m=0 (6 1) DFT FIR 1) A.V. Oppenheim, R.W. Schafer, and J.R. Buck, Discrete-Time Signal Processing, nd ed, Prentice Hall, c 011 7/(0)

8 ) MRA Multi-Resolution Analysis V j j, k Z j, k 1. V j V j j Z V j = {0} j Z V j = L (R) 4. f (t) V j f (t) V j+1 5. f (t) V j f (t j k) V j 6. φ(t) V 0 {φ(t k) k Z} V 0 4 j j 1 V j+1 = V j W j, V j W j (6 ) W j L (R) = j Z W j (6 3) W 0 ψ(t k) V 0 φ(t k) MRA MRA 1) S. Mallat, A theory for multiresolution signal decomposition: the wavelet representation, IEEE Trans. Patt. Anal. Mach. Intell., vol.11, no.7, pp , c 011 8/(0)

9 PRFB {A(z), B(z)} {P(z), Q(z)} 1,, 3, 4, 5) x(n) A(z) x(n) B(z) c(n) P(z) y 1 (n) d(n) Q(z) y (n) A(z)P(z) + A( z)p( z) =, B(z) = P( z), Q(z) = A( z), (6 4) (6 5) (6 6) π z = z e j (6 7) y(n) = y 1 (n) + y (n) (6 8) y(n) x(n l) (6 9) PRFB l (6 4) A(z)P(z) A(z), P(z) PRFB A(z)P(z) p(n) q(n) 1 A 0 (z) = z 1 5, 6), P 0 (z) = 1 A 1 (z) = A 0 (z) + P 0 ( z)s (z ), (6 0) P 1 (z) = P 0 (z), (6 ) S (z) = 1 ( z + 9z z ) 16 (6 ) c 011 9/(0)

10 A 1 (z) P 1 (z) A 1 (z) z A 1 (z) A 1 (z) = 1 ( z 4 + 0z 3 + 9z + 16z 1 + 9z 0 + 0z 1 z ) (6 3) 16 P 1 (z) = 1 A 1 (z) z A 1 (z) (6 4) A 1 (z) = 1 ( z 3 + 0z + 9z z 1 + 0z z 3) (6 5) 16 H(z) = A 1 (z)p 1 (z) H(z) + H( z) H(z) + H( z) = (6 6) H(z) ( 3 A n ( 1) = 0 A n (z) ) z 1 A n+1 (z) = 1 P n+1 (z) = 1 A n (z) ( 1 + z 1 ), (6 7) ( 1 + z 1 ) P n (z) (6 8) A (z), P (z) A (z) = 1 ( z + z 1 + 8z 0 + 8z 1 + z z 3) 8 (6 9) P (z) = 1 ( ) 1 + z 1 (6 30) 4 A 3 (z), P 3 (z) A 3 (z) = 1 4 P 3 (z) = 1 4 ( z 1 + z 0 + 6z 1 + z z 3) (6 31) ( ) 1 + z 1 1 ( = 1 + z 1 + z ) (6 3) 4 c /(0)

11 5 A 4 (z), P 4 (z) A 4 (z) = 1 P 4 (z) = 1 8 ( z 0 + 3z 1 + 3z z 3) (6 33) ( ) 1 + z ( = 1 + 3z 1 + 3z + z 3) (6 34) 8 6 A 5 (z), P 5 (z) A 5 (z) = z 1 + 4z z 3 P 5 (z) = 1 16 (6 35) ( ) 1 + z ( = 1 + 4z 1 + 6z + 4z 3 + z 4) (6 36) 16 7 A 5 (z) A 5 (z) = z ( z + 3 ) ( z 3 ) (6 37) 8 H(z) = A 5 (z)p 5 (z) H(z) = A(z)P(z) P(z) = 1 ( ) 1 + z 1 { ( ) } z 1, 4 (6 38) A(z) = 1 ( ) 1 + z 1 { ( ) } z 1 z 3. 8 (6 39) ( 1 3 ) z 1 = z ( ) z = z ( ) ( z + 3 ), ( ) z 1 = z ( ) z = z ( ) ( z 3 ). 3 9 P(z) z z p(n) p(n) c /(0)

12 P(z) = 1 4 { ( ) + ( ) z 1 + ( 3 3 ) z + ( 1 3 ) z 3} (6 40) = p(0) + p(1)z 1 + p()z + p(3)z 3 (6 41) 0 lowpass p(n) highpass q(n) = ( 1) n p(3 n), n = 0, 1,, 3 q(0) 3 p(n k)q(n) = ( q(1) p(0) p(1) p() p(3) ) (6 4) q() n=0 q(3) k highpass Q(z) Q(z) = q(0) + q(1)z 1 + q()z + q(3)z 3 (6 43) = p(3) p()z 1 + p(1)z p(0)z 3 (6 44) = 1 4 { ( 1 3 ) ( 3 3 ) z 1 + ( ) z ( ) z 3} (6 45) k q(0) 3 p(n)q(n) = ( p(0) p(1) p() p(3) ) q(1) = 0 q() n=0 q(3) (6 46) q(0) 3 p(n )q(n) = ( 0 0 p(0) p(1) ) q(1) = 0 q() n=0 q(3) (6 47) q(0) 3 p(n + )q(n) = ( p() p(3) 0 0 ) q(1) = 0 q() n=0 q(3) (6 48) k = 0, ±1 k {p(n)} {q(n)} {p(n)} {q(n)} p(n), q(n) 4 7) c 011 1/(0)

13 3 p(n k)p(n) = δ(k), for k n=0 3 q(n k)q(n) = δ(k), for k n=0 1, for k = 0 δ(k) = 0, (6 49) (6 50) lowpass filter {p(n)} highpass filter {q(n)} 7, 4 8) 5/3 (6 31) (6 3) 4 p 0 p 1 p p p 0 p 1 p p L = (6 51) p 0 p 1 p p 3 p p p 0 p 1 p 3 p p 1 p p 3 p p 1 p H = (6 5) p 3 p p 1 p 0 p 1 p p 3 p T = 1 L H TT t = I T (6 46) TT t 5 TT t /1 9, 10) x(t) coarse c(t) detail d(t) c /(0)

14 c(t) = x(t) d(t) = x(t + 1) (6 53) (6 54) A(z) P(z) 1/1 1 = x(t) floor + 1 (dc gain) 1 55 d(t) JPEG000 / d(t) d(t) c(t) 3 /3 (6 55) = x(t + 1) x(t)) (6 56) c(t) + c(t + 1) d(t) d(t) x(t) + x(t + ) = x(t + 1) 4 / ( Haar ) (6 57) (6 58) d(t) d(t) c(t) (6 59) = x(t + 1) x(t) (6 60) c(t) c(t) + 1 d(t) = x(t) + 5 /6 ( S+P 11) ) x(t + 1) x(t) x(t) + x(t + 1) (6 61) (6 6) c /(0)

15 d(t) d(t) c(t) (6 63) = x(t + 1) x(t) (6 64) c(t) c(t) + d(t) (6 65) x(t + 1) x(t) x(t) + x(t + 1) = x(t) + (6 66) c(t) c(t + ) d(t) d(t + 1) (6 67) x(t) + x(t + 1) x(t + 4) + x(t + 5) x(t + 3) x(t + ) (6 68) 11) S+P x(t) + x(t + 1) c(t) c(t) + 4x(t + ) 4x(t + 3) + c(t + ) d(t) 4 (6 69) (6 70). d(t) d(t) d(t) d(t) + c(t) (6 71) (6 7) c(t) c(t) d(t) (6 73) c(t) c(t + ) d(t) d(t + 1) (6 74) { 1, 1, 8, 8, 1, 1} S+P { 1, 1, 8, 8, 1, 1} S +P 6 5/3 ( 5/3-SSKF, 1) CDF(,)) JPEG000/Lossless c(t) + c(t + 1) d(t) d(t) (6 75) x(t) + x(t + 1) x(t + ) (6 76) d(t) + d(t + 1) c(t) c(t + 1) (6 77) x(t) + x(t + 1) + 6x(t + ) + x(t + 3) x(t + 4) 8 (6 78) c /(0)

16 13) 7 5/11 5/3 (,) c(t) + c(t + 1) d(t) d(t) (6 79) x(t) + x(t + 1) x(t + ) (6 80) d(t) + d(t + 1) c(t) c(t + 1) (6 81) x(t) + x(t + 1) + 6x(t + ) + x(t + 3) x(t + 4) 8 (6 8) c(t ) c(t 1) c(t) + c(t + 1) d(t) d(t) (6 83) x(t 4) + x(t 3) + 7x(t ) 136x(t) 56 56x(t + 1) 136x(t + ) + 7x(t + 4) + x(t + 5) x(t + 6) + 56 (6 84) Calderbank, Daubechies, and Sweldens 10) (4, ) 5/ /7 (transform gain) 5/3 14) (4, ) c(t 1) + 9c(t) + 9c(t + 1) c(t + ) d(t) d(t) (6 85) x(t ) 9x(t) + 16x(t + 1) 9x(t + ) + x(t + 4) (6 86) 16 d(t 1) + d(t) c(t) c(t) (6 87) x(t 4) 8x(t ) + 16x(t 1) 64 46x(t) + 16x(t + 1) 8x(t + ) + x(t + 4) + (6 88) 64 c /(0)

17 c(t) = x(t) d(t) = x(t 1) (6 89) (6 90) c(t + 1) + 9c(t) + 9c(t 1) c(t ) d(t) d(t) (6 91) x(t + ) 9x(t) + 16x(t 1) 9x(t ) + x(t 4) (6 9) 16 d(t + 1) + d(t) c(t) c(t) (6 93) x(t + 4) 8x(t + ) + 16x(t + 1) 64 46x(t) + 16x(t 1) 8x(t ) + x(t 4) + (6 94) 64 9 d(t) { } { } d(t) c(t l) c(t) { } { } c(t) + d(t l) Sweldens 9) (6 ) S (z) FIR in-place 0 4/4 ( CDF(3,1)) ) a k = A(1) = 3 k b k = B( 1) = 3 k (6 95) (6 96) a k, b k lowpass filter highpass filter c /(0)

18 A(z) B(z) c(t) c(t) d(t) 3 (6 97) x(t + 1) x(t) 3 (6 98) 3c(t) 9c(t + 1) d(t) d(t) 8 (6 99) 3x(t) x(t + 1) 9x(t + ) + 3x(t + 3) x(t + 1) 8 (6 00) 3x(t) + 9x(t + 1) 9x(t + ) + 3x(t + 3) = 8 (6 01) c(t) c(t + 1) d(t) x(t) + 3x(t + 1) + 3x(t + ) x(t + 3) 6 (6 0) (6 03) 11 m/n m A(z) n P(z) 5/3 3/5 CDF (m, n) ( ) 1 + z 1 m A(z) = A (z), (6 04) ( ) 1 + z 1 n P(z) = P (z) (6 05) z = 1 Admissibility A(z), P(z) z = LOT (lapped orthogonal transforms) DCT QMF z = 1 (checker-board artifact) LL, HL, LH, HH 4 quadrature-mirror filter bank, c /(0)

19 6 3 8) 5 Haar 7) 1/1 15) 16, 17) 1) D. Esteban and C. Galand, Application of quadrature mirror filters to split-band voice coding schemes, Proc. IEEE ISCAS 1977, vol., pp , ) M.J.T. Smith and T.P. Barnwell, Exact reconstruction techniques for tree-structured subband coders, IEEE Trans. ASSP, vol.34, pp , ) M. Vetterli, Filter banks allowing perfect reconstruction, Signal Proc., vol.10, pp.19-44, ) P.P. Vaidyanathan, Theory and design of M channel maximally decimated quadrature mirror filters with arbitrary M, having the perfect reconstruction property, IEEE Trans. ASSP, vol.35, pp , ) G. Strang and T.Q. Nguyen, Wavelets and Filter Banks, Wellesley-Cambridge Press, MA, c /(0)

20 6) H. Kiya, M. Yae, and M. Iwahashi, A linear-phase two-channel filter bank allowing perfect reconstruction, Proc. IEEE ISCAS, pp , ) I. Daubechies, Orthonormal bases of compactly supported wavelets, Comm. Pure Appl. Math., vol.41, pp , ) I. Daubechies, Ten Lectures on Wavelets, SIAM, ) W. Sweldens, The lifting scheme: A new philosophy in biorthogonal wavelet constructions, Proc. SPIE, vol.569, pp.68-79, ) A. Calderbank, I. Daubechies, W. Sweldens, and B.L. Yeo, Lossless image compression using integer to integer wavelet transforms, Proc. IEEE Int. Conf. on Image Proc., Washington, DC, USA, vol.1 of 3, pp , ) A. Said and W.A. Pearlman, An image multiresolution representation for lossless and lossy compression, IEEE Trans. Image Proc., vol.5, pp , ) D. Le Gall and A. Tabatabai, Sub-band coding of digital images using symmetric short kernel filters and arithmetic coding techniques, Proc. IEEE Int. Conf. Acoust., Speech, Signal Proc., New York, vol., pp , ) M.D. Adams and F. Kossentini, Reversible integer-to-integer wavelet transforms for image compression: performance evaluation, IEEE Trans. Image Proc., vol.9, no.6, pp , ) K. Shinoda, H. Kikuchi, and S. Muramatsu, Lossless-by-lossy coding for scalable lossless image compression, IEICE Trans. Fundamentals, vol.e91-a, no.11, pp , ),,,, ECG,, vol.j79-d-ii, no.8, pp , ),, Total-Variation,, vol.41, no.11, pp , ) T. Saito, N. Fujii, and T. Komatsu, Iterative soft color-shrinkage for color-image denoising, Proc. IEEE ICIP 009, Cairo, 009. c 011 0/(0)