THE INSTITUTE OF ELECTRONICS, INFORMATION AND COMMUNICATION ENGINEERS TECHNICAL REPORT OF IEICE. TV A310

Size: px

Start display at page:

Download "THE INSTITUTE OF ELECTRONICS, INFORMATION AND COMMUNICATION ENGINEERS TECHNICAL REPORT OF IEICE. TV A310"

あゆみおえづか
4 years ago
Views:

1 THE INSTITUTE OF ELECTRONICS, INFORMATION AND COMMUNICATION ENGINEERS TECHNICAL REPORT OF IEICE. TV A310 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 , Japan. 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 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 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) 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 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

3 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/λ) λ 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 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

4 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 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 ) 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 Lenna 1 λ p = λ c = Barbara 5 λ p = Lenna 12 Barbara 256 x 12 Lenna Barbara PSNR PSNR λ Barbara λ p = λ p 2 Lenna Barbara λ 432 PSNR PSNR Segmented Image CodingSIC[6] 5. TV TV u 4

3 Structural image by the conventional method. Fig.

5 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

6 Original Original luance luance coordinates 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 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 Distortion [db] Bitrate [bpp] Proposed 2 Distortion [db] 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 [1] Leonid I. Rudin, Stanley J. Osher, and Emad Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, Vol. 60, pp , [2] Yves Meyer, Oscillating Patterns in Image Processing and Nonlinear Evolution Equations The Fifteenth Dean Jacqueline B. Lewis Memorial Lectures, American Mathematical Society, [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 , [4] Jamylle L. Carter, Dual Methods for Total Variation-based Image Restoration, Ph.D. thesis, U.C.L.A. (Advisor T.F. Chan), [5] Antonin Chambolle, An Algorithm for Total Variation Minimization and Applications, Journal of Mathematical Imaging and Vision, Vol. 20, pp.9 97, [6] C.A. Christopoulos, Segmented image coding Techniques and experimental results, Signal Processing Image Communication 11, pp.63 0,

THE INSTITUTE OF ELECTRONICS, INFORMATION AND COMMUNICATION ENGINEERS TECHNICAL REPORT OF IEICE.

THE INSTITUTE OF ELECTRONICS, INFORMATION AND COMMUNICATION ENGINEERS TECHNICAL REPORT OF IEICE. E-mail: {ytamura,takai,tkato,tm}@vision.kuee.kyoto-u.ac.jp Abstract Current Wave Pattern Analysis for Anomaly