untitled

Size: px

Start display at page:

Download "untitled"

ゆきみやくぼ
5 years ago
Views:

1 17 2 Realization on the Direct Two-dimensional Wavelet Transform

2 2 JPEG JPEG2000 [1] X-Y X 1 Y 1 VGA 1 1MBte LSI LSI 2 2 5/3 [2][3] 2 5/3 9/7 7 7 N X M Y 32N M 10N M X-Y 9/ / i

3 2 9/7 12N M 5.5N M 2 9/7 37.5% 55% X-Y 9/7 50% 8% VGA 1 1MBte LSI 16bit SN SN 67 [db] 2 ii

4 Abstract Realization on the Direct Two-dimensional Wavelet Transform Akihiro CHIBA Recentl, various standards are proposed to improve compression efficienc of an image. In JPEG2000, which is the net generation standard of still picture compression, Discrete Wavelet Transform (DWT) is used for the transformation[1]. Transformation efficienc of DWT depend on image size, where the larger the size is, the higher the efficienc is. Consider a processing of X-Y separable DWT. First, it is one dimension transformed in X direction. Then, the transformed result is recorded to temporal memor. Second, Y direction DWT processing starts using the recorded results. Therefore, the temporal memor size becomes nearl 1M Bte in VGA size picture processing. If a X-Y separable DWT is implemented in a LSI chip, this large memor causes large LSI chip size. On the other hand, multi-core LSI can increase operating performance as well as loweritspowerdissipationinrecentlsis. Therefore, even if a number of DWT operations increases, a method of ecluding large capacit memor should be chosen. The reported Direct Two-dimensional 5/3 Wavelet Transform without memor (2D 5/3 wavelet)[2] is derived, based on this strateg[3]. However, 9/7 wavelet transform processing without memor on the structure of the reported 2D 5/3 wavelet leads to a huge number of operations. The reason is that 9/7 wavelet transform use 7 order filters instead of 3 order filters. When a picture has N piels in X direction and M piels in Y direction, a number of required additions iii

5 becomes 32N M, and that of multiplications becomes 10N M. Thisis4times additions and 1.6 times more multiplications, compared to those for X-Y separable 9/7 DWT. This thesis proposes a new Direct Two-dimensional Wavelet Transform. The new methodisbasedonemploing3orderfilters for the one dimensional 9/7 lifting structure. This strateg means that a higher order filter should be constructed b the combination of lower order filters. A high order filter is realized b a tandem connection of 3 order filters. This strateg leads a general method to construct Direct Two-dimensional Wavelet Transform without memor. For instance, this strateg can generate higher order filter than 9 order filter which is used to 9/7 wavelet transform. This strateg decreases a required number of operations for 2D 9/7 wavelet transform without memor. As a result, a number of additions becomes 12N M and that of multiplications becomes 5.5N M. This result shows that a total number of additions becomes 37.5% and that of multiplications becomes 55%, compare to reported 9/7 transform on the 5/3 transform structure. When these operations are compared to those for X-Y separated DWT, a number of additions increases 50% but that of multiplications decreases about 8%. Although the proposed method increases number of additions, the method enables ecluding temporal memor. As a result, required LSI size will be decreased. In addition, this method is simulated for LSI sstem implementation. This simulation verif that 16 bit operations generate a lot of noise b rounding errors. The obtained signal to noise ratio (S/N) becomes 67 [db]. ke words Direct 2-D wavelet transform Lifting structure iv

6 / / /3 2 9/ / / SN A 33 v

7 2.1 JPEG JPEG ( 2 ) ( 2 ) JPEG /3 (z ) /3 (z ) /7 ( ) /3 ( ) /3 HH / /3 (HL) /7 (HL) /7 (1 ) /7 ( ) A.1 1:Aerial A.2 2:Airplane A.3 3:Girl A.4 4:Mandrill A.5 5:Pepper vi

8 2.1 JPEG2000 5/ JPEG2000 9/ /7 (HPF ) SN vii

9 1 JPEG JPEG2000 [1] LSI X-Y 1 X Y 2 X-Y 1 2 LSI

10 2 2 JPEG2000 5/ /3 [2] 9/7 2 9/7 [3] 9/7 2 5/3 2 9/7 1 9/ /3 2 9/7 X-Y 9/7 N X M Y 32N M 4 10N M /3 2 9/7 1 9/7 2 2 [2] 5/3 1 9/ /7 2 5/3 2 9/7 37.5% 55% X-Y 9/7 2

11 150% 92% /3 2 5/3 2 9/ /7 2 9/ /7 6 3

12 2 2.1 [4] 2 0 JPEG MPEG DC [1] JPEG2000 JPEG

13 JPEG H 0 (z) HPF H 1 (z) LPF X(z) ( R0 (z) =H 0 (z)x(z) R 1 (z) =H 1 (z)x(z) (2.1) R 0 (z) R 1 (z) 1/2 S 0 (z) S 1 (z) ( S0 (z) ={H 0 (z 1/2 )X(z 1/2 )+H 0 ( z 1/2 )X( z 1/2 )}/2 S 1 (z) ={H 1 (z 1/2 )X(z 1/2 )+H 1 ( z 1/2 )X( z 1/2 )}/2 (2.2) 2.2 S 0 (z) S 1 (z) 5

14 JPEG2000 T 0 (z) T 1 (z) ( T0 (z) ={H 0 (z)x(z)+h 0 ( z)x( z)}/2 T 1 (z) ={H 1 (z)x(z)+h 1 ( z)x( z)}/2 (2.3) T 0 (z) T 1 (z) G 0 (z) G 1 (z) Y (z) Y (z) =T 0 (z)g 0 (z) T 1 (z)g 1 (z) =[{H 0 (z)g 0 (z) H 1 (z)g 1 (z)}x(z) +{H 0 ( z)g 0 (z) H 1 ( z)g 1 (z)}x( z)]/2 (2.4) (2.2) (2.3) (2.4) X( z) (2.5) ( G0 (z) =H 1 ( z) G 1 (z) =H 0 ( z) (2.5) 6

15 ( 2 ) 2.4 ( 2 ) JPEG2000 R 1 (z) JPEG

16 2.2 DCT [5] 2 2.5(a) 2.5(b) 2.5 (a) (b) (a) (b) /3 (a) 2 (b) 2 1 9/7 1 9/

17 JPEG /3 (z ) (a) z 2.5 (a) z X(z) A(z) B(z) X(z) 1/2 H(z) L(z) 9

18 A(z) B(z) A(z) = 1 2 {X(z 1 2 )+X( z 1 2 )} (2.6) B(z) = 1 2 {z 1 2 X(z 1 2 ) z 1 2 X( z 1 2 )} (2.7) 2.6 α β H(z) =α(1 + z 1 ) (2.8) L(z) =β(1 + z 1 ) (2.9) 1 5/3 1 5/3 H(z)X(z) H(z)X(z) =B(z)+α(1 + z 1 )A(z) (2.10) A(z) B(z) (2.6) (2.7) (2.10) H(z)X(z) = 1 2 {(α + z αz 1 )X(z 1 2 ) +(α z αz 1 )X( z 1 2 )} (2.11) (2.11) (α + z 1 + αz 2 )X(z) 1/2 (2.11) β H(z) =α + z αz 1 (2.12) L(z) =βh(z)+z 1 + βz 1 H(z) (2.13) L(z) L(z) =β{(α + z αz 1 )+z 1 (α + z αz 1 )} + z 1 = αβ + βz 1 2 +(2αβ +1)z 1 + βz αβz 2 (2.14) 10

19 /3 (z ) 2.1 JPEG2000 5/3 α β α β JPEG /3 1 5/3 2.5 (b) 2.5 (b) z HX(z) 2.5 (a) LX(z) H r (z) L r (z) Y (z) 2.5 (b) HX(z) LX(z) (b) 11

20 /7 (a) L r (z) = β + z 1 βz 1 (2.15) H r (z) = αl r (z)+z 3 2 αz 1 L r (z) (2.16) (2.12) (2.16) X(z) Y (z) 1 5/3 (2.13) (2.15) 2 JPEG2000 5/3 2.5 (a) (b) (a) (b) 1 1 5/ /7 1 5/3 1 5/3 JPEG2000 9/7 1 9/7 1 5/ / / (a1) (a2) 2.9 (a) (a) (2.12) (2.13) (a1) 1 9/7 1 12

21 / /7 ( ) (a2) (a1) 7 9 (a1) (a1) H 1 (z) α L 1 (z) β (a2) H 2 (z) γ L 2 (z) δ H 1 (z) =α + z αz 1 (2.17) L 1 (z) =βh 1 (z)+z 1 + βz 1 H 1 (z) (2.18) H 2 (z) =γz 1 L 1 (z)+z 3 2 H1 (z)+γz 2 L 1 (z) (2.19) L 2 (z) =δz 1 H 2 (z)+z 2 L 1 (z)+δz 2 H 2 (z) (2.20) (2.17) (2.19) (2.18) (2.20) z (a1) (a2) 13

22 / /3 ( ) 1 9/7 1 5/3 L 1r (z) = δ + z 1 δz 1 (2.21) H 1r (z) = γl 1r (z)+z 3 2 γz 1 L 1r (z) (2.22) L 2r (z) = βz 1 H 1r (z)+z 2 L 1r (z) βz 2 H 1r (z) (2.23) H 2r (z) = αz 1 L 2r + z 5 2 H1r (z) αz 2 L 2r (z) (2.24) JPEG2000 9/7 k k k k k (2.17) (2.24) JPEG2000 9/7 k 1 9/7 14

23 /7 2.2 JPEG2000 9/7 α β γ δ k /7 (2.17) (2.18) 9/7 JPEG2000 5/3 9/7 15

24 /3 1 2 X Y X Y X Y X Y X Y X Y X Y X Y X-Y z X z Y F (z,z ) 2 F (z) 1 F (z,z )=F(z )F (z ) X Y 1 2 X Y 2 HH(z,z ) 16

25 / /3 HH HH(z,z )=H(z )H(z ) =(α + z 1 2 =(α 2 + αz αz 1 )(α + z α 2 z 1 ) +(αz z 1 2 z 1 2 +(α 2 z αz 1 z 2 + αz αz 1 ) z 1 ) + α 2 z 1 z 1 ) (3.1) X Y α X Y α X Y 2 HL(z,z ) HL(z,z )=H(z )L(z ) =(α + z 1 2 =(α + z αz 1 ){αβ + βz αz 1 )[β{(α + z 1 2 +(2αβ +1)z 1 + βz αz 1 )+z 1 (α + z αβz 2 } + αz 1 )} + z 1 ] = βhh(z,z )+βz 1 HH(z,z )+z 1 H(z ) (3.2) (3.2) (3.1) Y HH(z,z ) β X 17

26 /3 X Y 2 LH(z,z ) (3.2) X Y LH(z,z )=βhh(z,z )+βz 1 HH(z,z )+z 1 H(z ) (3.3) (3.3) (3.2) (3.1) X HH(z,z ) β Y X Y 2 LL(z,z ) LL(z,z )=L(z )L(z ) = {αβ + βz 1 2 {αβ + βz 1 2 =[β{(α + z 1 2 [β{(α + z 1 2 = β 2 {HH(z,z )+z 1 +β{z 1 +(2αβ +1)z 1 + βz 3 2 +(2αβ +1)z 1 + βz αz 1 )+z 1 (α + z 1 2 H(z )+z 1 + αz 1 )+z 1 (α + 1 z 2 HH(z,z )+z 1 H(z )+z 1 z 1 + αβz 2 } + αβz 2 } + αz 1 )} + z 1 ] + αz 1 )} + z 1 ] HH(z,z )+z 1 z 1 HH(z,z )} H(z )+z 1 z 1 H(z )} + z 1 z 1 (3.4) (3.4) (3.1) (3.2) (3.3) β 2 β HL(z,z ) z 1 LH(z,z ) z 1 (3.4) LL(z,z )=β{hl(z,z )+z 1 HL(z,z )+LH(z,z )+z 1 LH(z,z )} β 2 {HH(z,z )+z 1 +z 1 z 1 HH(z,z )+z 1 HH(z,z )+z 1 z 1 HH(z,z )} (3.5) (3.1) (3.2) (3.3) (3.5) z 1 z

27 /3 2 9/ /3 z 1 z α β /3 [2] 1 5/3 2 5/ /3 2 9/7 2 5/ /7 [3] 2 5/3 19

28 /3 2 9/ /3 (HL) 3.4 9/7 (HL) 3.2 HL /3 2 9/7 1 N X M Y 10N M 32N M 1 9/7 6N M 8N M

29 4 2 9/ / /7 1 5/3 2 9/7 1 5/3 2 5/3 1 9/7 2 9/7 3.1 X-Y z X z Y F (z,z ) 2 F (z) 1 F (z,z )=F(z )F (z ) X Y (3.4) 3.1 (3.4) (3.2) (3.3) 1 9/7 2 9/

30 /7 (a1) (3.1) (3.4) (3.1) (3.1) (4.1) HH(z,z )=(α 2 + αz α 2 z 1 ) +(αz z 1 2 z 1 2 +(α 2 z αz 1 z 2 + αz 1 2 z 1 ) + α 2 z 1 z 1 ) (4.1) (3.2) (3.3) (3.4) (3.2) (3.3) (3.2) HL 1 (z,z ) (3.3) LH 1 (z,z ) HL 1 (z,z )=z 1 H(z ) (4.2) LH 1 (z,z )=z 1 H(z ) (4.3) 3.1 (3.4) (4.1) (4.2) (4.3) β (4.1) (4.2) (4.3) (3.4) (3.4) (4.4) LL(z,z )=β 2 {HH(z,z )+z 1 +β{z 1 H(z )+z 1 HH(z,z )+z 1 H(z )+z 1 z 1 HH(z,z )+z 1 z 1 HH(z,z )} H(z )+z 1 z 1 H(z )} + z 1 z 1 (4.4) (4.1) (4.4) (a1) X Y X Y 22

31 / /7 (1 ) 3.1 (3.2) (3.3) X Y X Y (3.2) (4.2) (3.3) (4.3) (4.2) HL 2 (z) (4.3) LH 2 (z) HL 2 (z) =HL 1 (z)+β{hh(z,z )+z 1 HH(z,z )} (4.5) LH 2 (z) =LH 1 (z)+β{hh(z,z )+z 1 HH(z,z )} (4.6) (4.1) (4.6) z 1 z 1 2 z 1 z (2.17) (2.20) (2.19) (2.20) (2.17) (2.18) 1 (2.17) (2.18) (2.19) (2.20) (2.17) (2.18) (2.19) (2.20) (4.4) (4.6) 1 9/7 1 23

32 /7 ( ) 2 X Y k 2 1/k 2 k 1/k 1 2 9/ / /3 α β HH HL LH HL LH LL HH HL 1 LH 1 24

33 4.2 LL HL 2 LH 2 1 CPU /7 2 9/7 2 9/7 JPEG2000 part2 25

34 / N X M Y HH / N M 5N M 2 9/ /7 X Y 2 X Y X Y X Y / N M 26

35 5.2 SN /7 (HPF ) HH (1 + 1/2+1/2)N M (1/4+1/4+1/4)N M HL 1 1/2N M 1/4N M LH 1 1/2N M 1/4N M 3N M 5/4N M 2 9/7 12N M 5.5N M 1 9/7 2 ( 8N M 6N M) 1.5 8% 2 9/7 LSI SN 2 9/7 JPEG2000 part1 LSI LSI bit 16bit 64bit SN 5.2 A 27

36 5.2 SN 5.2 SN SN (1) [db] SN (2) [db] Aerial Airplane Girl Mandrill Pepper piel 256piel bit X-Y 9/7 64bit 8bit 64bit bit 64bit S 0 X-Y 9/7 S 16bit S 00 S S 0 N S S 00 N 0 SN (1) 10log 10 (S 2 /N 2 ) 28

37 5.2 SN SN (2) 10log 10 (S 2 /N 02 ) 5 SN 67 [db] 64bit 11bit SN (2) X-Y 16bit 7[dB] 2 16bit 1 29

38 6 LSI 2 [2] 2 5/3 2 9/7 1 N X M Y 32N M 10N M X-Y 9/ /7 2 9/7 12N M 5.5N M X-Y 9/7 50% 8% 1 2 LSI 16bit 64bit 1 2 S N 67 [db] SN ALU SN 2 30

39 4 31

40 [1] JPEG [2] [3] Akihiro CHIBA Hiroshi SUZUKI and Takao NISHITANI Consideration on the Direct Two-dimensional Wavelet Transform (SJ- CIEE) [4] 1999 [5] Ingrid DAUBECHIES and Wim SWELDENS FACTORING WAVELET TRANSFORMS INTO LIFTING STEPS Journal of Fourier Analsis vol.4 Nr.3 pp ,

41 A A.1 1:Aerial A.2 2:Airplane 33

42 A.3 3:Girl A.4 4:Mandrill A.5 5:Pepper 34

Wavelet HSI / [1] JPEG2000 9/7Wavelet [2][6] 2:1 9/7Wavelet Wavelet 80 Wavelet i

17 Wavelet Image Enhancement by Wavelet Transform 1060326 2006 3 10 Wavelet HSI / [1] JPEG2000 9/7Wavelet [2][6] 2:1 9/7Wavelet Wavelet 80 Wavelet i Abstract Image Enhancement by Wavelet Transform Yuichi