THE INSTITUTE OF ELECTRONICS, INFORMATION AND COMMUNICATION ENGINEERS TECHNICAL REPORT OF IEICE. TV 367 0035 1011 A310 E-mail kawamura@suou.waseda.jp Total Variation Total Variation Total Variation Abstract A Study on Numerical Computation of Pseudo TV-norm and its Application to Image Segmentation Kei KAWAMURA, Daisuke ISHII, and Hiroshi WATANABE Graduate School of Global Information and Telecommunication Studies, Waseda University, A310, 1011 Nishi-Tomida, Honjo-shi, Saitama 367 0035, Japan. E-mail kawamura@suou.waseda.jp An image decomposition problem using a Total Variation norm is the object of this paper. In a conventional method, this problem was formulated by the dual problems. Dual variables in it are calculated by an iteration of the convex projection method. However, a role of each variable is implicit. Then, it is difficult to apply to another field. We propose a comprehensible discretization of the Total Variation and a differential manipulation as the operation. A direct calculation procedure of the structural image by the steepest descent method is described. Two comparisons of waveforms and similarities are shown. These experiments clarify that the proposed method maintains the performance of the conventional method with the explicit role of each variable. An example of application to the image segmentation is demonstrated. Key words Total Variation, Steepest Descent Method, Image Segmentation, Image Coding. 1. 2 u + v u v 3 u + v + w v w u + v RudinOsher Fatami Total Variation ROF [1]Mayer v [2]Vesa L [3] 0 Carter 0 [4]AujolAubertBlanc-Féraud Chambolle Total Variation [5] 1
2 Total Variation TV TV 2. TV 2. 1 u g λ R(u) S() Tikhonov u g 2 + R(u) (1) u S() 2λ Total VariationTVRudinOsherFatemi R(u) = T V (u) = u = [1] s «2 u + x u dxdy, (2) «2 u (3) y u 1 (u g) u 2 + u dxdy (4) 2λ [3] «u u g λ = 0 (5) u u = 0 β > 0! u u g λ p = 0 (6) u 2 + β β 2. 2 β TV T V (u) = max w < = 1 u( w)dxdy (7) [4]w u 1 (u g) u 2 max u( w) dxdy () 2λ w < = 1 = max (u g) 2 u( w) dxdy (9) w < = 1 u 2λ Ψ(u) Ψ(u) = 0 u = g + λ( w) (10) 10 9 g( w) + 3λ 2 ( w)2 dxdy (11) max w < = 1 w 2 β u = g + λ( w) 1 2. 3 N N 2 X R N N Y X X u, v X u, v X = X u i,j v i.j, (12) 1< = i,j< = N p = (p 1, p 2 ), q = (q 1, q 2 ) Y p, q Y = X (p 1 i,jqi,j 1 + p 2 i,jqi,j) 2 (13) 1< = i,j< = N 2 x 2 = x, x X X y = (y 1, y 2 ) Y y = p y 2 1 + y2 2 TV u X u Y ( u) i,j = `( u) 1 i,j, ( u) 2 i,j < u ( u) 1 i+1,j u i,j if i < N, i,j = 0 if i = N, < u ( u) 2 i,j+1 u i,j if j < N, i,j = 0 if j = N i, j = 1,..., N div Y (14) (15) (16) X div = p Y u X div p, u X = p, u Y div p = (p 1, p 2 ) Y p >< 1 i,j p 1 i 1,j if 1 < i < N, (div p) i,j = p 1 i,j if i = 1, > p 1 i 1,j if i = N, p >< 2 i,j p 2 i,j 1 if 1 < j < N, + p 2 i,j if j = 1, > if j = N p 2 i,j 1 (17) 2
2. 4 u TV J(u) = X 1< = i,j< = N [5] ( u) i,j (1) J 1 Legendre Fenchel J (u) = sup u, v X J(u) (19) u K < 0 if v K J (u) = χ K(v) = + if otherwise J = J (20) J(u) = sup u, v X (21) v K K J(u) = sup p, u Y (22) p sup i, j p i,j < = 1 p Y 22 K {div p p Y, p i,j < = 1, i, j = 1,..., N} (23) 1 g X λ > 0 u g 2 + J(u) (24) u X 2λ u g + λ J(u) 0 (25) J J v w J(u) J(v) > = J(u) + w, v u X (g u)/λ J(u) u J ((g u)/λ) g λ = g u + 1 λ λ J g u λ w = (g u)/λ (26) w (g/λ) 2 + 1 2 λ J (w) (27) J 19 w = π K (g/λ) u u = g π λk (g) (2) u π λk 2 π λk (g) { λ div p g 2 p Y, p i,j 2 1 < = 0, i, j = i,..., N} (29) Au g 2 + J(u) (30) u X 2λ A 3. 3. 1 u w p 2 u = 0 TV J(u) = P u u 4 u i,j = (u i,j, u i+1,j, u i,j+1, u i+1,j+1 ) t (31) ( u) i,j = u i+1,j+1 u i+1,j + u i,j+1 u i,j + u i+1,j+1 u i,j+1 + u i+1,j u i,j (32) = J i,j(u) (33) 4 ( u) i,j = (max(u i,j ) (u i,j )) 2 (34) TV Total Variation 34 ( u) i,j 0 4 ( u) i,j 0 4 J(u) = Ji,j(u) u i,j = Ji,j(u + ui,j) Ji,j(u) u i,j (35) u i,j 4 3
J(u) u i,j J i,j (u) u i,j = (u i,j u i,j, u i,j u i+1,j, u i,j u i,j+1, u i,j u i+1,j+1 ) t (36) 1 u 0 24 u n+1 i,j = u n i,j α(u n i,j g i,j + λ u i,j ) (37) n α J i,j (u) 0 J i,j (u) u n+1 i,j = u n i,j 1 3. 2 TV TV TV J i,j (u) < λ u i,j u n i,j D 1 (u) D 2 (g) 2 (3) D 1 D 2 u g < u n u n+1 i,j i,j = u n i,j α(u n i,j g i,j + λ u i,j ) 2 4. 4. 1 if J i,j(u) < λ (39) if otherwise u ROF Chambolle [5] 1 PSNR 2 PSNR λ p λ c λ c PSNR λ p 2 α 1.0/λ p 10 30 4. 2 Lenna 1 λ p = 32 2 3 λ c = 12 4 12 Barbara 5 λ p = 32 256 7 Lenna 12 Barbara 256 x 12 Lenna Barbara PSNR PSNR λ 4. 3 2 6 Barbara λ p = 32 1 5 λ p 2 Lenna Barbara λ 432 PSNR 910 1 23 2 PSNR Segmented Image CodingSIC[6] 5. TV TV u 4
1 λ p = 32 Fig. 1 Structural image by the proposed method. Fig. 2 2 Oscillating (residual) image by the proposed method. 3 λ c = 12 4 Lenna 12 Fig. 3 Structural image by the conventional method. Fig. 4 Input image Lenna with a white line at 12 rows. 5 1 λ p = 32 Fig. 5 Structural image by the proposed method one. 6 2 λ p = 32 Fig. 6 Structural image by the proposed method two. 5
300 250 Original 300 250 Original luance 200 150 100 luance 200 150 100 50 50 0 0 64 12 192 256 320 34 44 512 coordinates 0 0 64 12 192 256 320 34 44 512 coordinates 7 Lenna 12 Fig. 7 Waveform of Lenna at 12 rows. 1 Lenna PSNR [db] Table 1 Image Similarity (PSNR) on Lenna. [db] Cross λ p Proposed λ c Conventional 47.6 4 41.4 2 41.5 47.3 3.2 4 3.4 46.9 16 35.3 35.5 46.5 24 34.0 12 33. 45. 4 32.5 16 32.6 Barbara 256 Fig. Waveform of Barbara at 256 rows. 2 Barbara PSNR [db] Table 2 Image Similarity (PSNR) on Barbara. [db] Cross λ p Proposed λ c Conventional 47.6 4 39.9 2 40.1 46.4 35.1 4 35.4 45.2 16 30. 30.7 43.5 24 2. 12 2.1 44.1 4 26. 16 26.7 42 42 40 40 Distortion [db] 3 36 34 32 30 2 26 24 3 4 5 6 7 Bitrate [bpp] Proposed 2 Distortion [db] 3 36 34 32 30 2 26 24 3 4 5 6 7 Bitrate [bpp] Proposed 2 9 Lenna Fig. 9 Relation of border data and image quality on segmented image Lenna. 10 Barbara Fig. 10 Relation of border data and image quality on segmented image Barbara. 19 2363 [1] Leonid I. Rudin, Stanley J. Osher, and Emad Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, Vol. 60, pp. 259 26, 1992. [2] Yves Meyer, Oscillating Patterns in Image Processing and Nonlinear Evolution Equations The Fifteenth Dean Jacqueline B. Lewis Memorial Lectures, American Mathematical Society, 2001. [3] Luita A. Vese and Stanley J. Osher, Modeling Textures with Total Variation Minimization and Oscillating Patterns in Image Processing, Journal of Scientific Computing, Vol. 15, pp. 553 572, 2003. [4] Jamylle L. Carter, Dual Methods for Total Variation-based Image Restoration, Ph.D. thesis, U.C.L.A. (Advisor T.F. Chan), 2001. [5] Antonin Chambolle, An Algorithm for Total Variation Minimization and Applications, Journal of Mathematical Imaging and Vision, Vol. 20, pp.9 97, 2004. [6] C.A. Christopoulos, Segmented image coding Techniques and experimental results, Signal Processing Image Communication 11, pp.63 0, 1997. 6