T-1 http://adapt.cs.tsukuba.ac.jp/moodle263/course/view.php?id=7 (Keisuke.Kameyama@cs.tsukuba.ac.jp) 29 10 11 1 ( ) (a) (b) (c) (d) SVD Tikhonov 3 (e) 1: ( ) 1
Objective Output s Known system p(s) b = p(s)+n noise n 2: 2 / 2.1 2 2 s(i, j) (0 i<m,0 j<n) = s MN 2 s p p(s) n p(s)+n s p CCD A/D n ( ) p(s)+n 2.2 s(x, y) (Point Spread Function : PSF) k(x, y) b(x, y) =k(x, y) s(x, y) = k(x u, y v)s(u, v)dudv = k(u, v)s(x u, x v)dudv (1) 2
(1) b(i, j) = k(p, q)s(i p, j q) (2) p q k(x, y) s R MN PSF k(x, y) P R MN MN b R MN b = P s (3) b = P s + n (4) n 2.3 (4) P, s = P 1 b = s + P 1 n (5) P (3) ŝ = argmin P s b 2 (6) s P P (3) ŝ = P b (7) ( ) P P = P 1 ŝ = ŝ + P n (8) 3
2 P n P n ( ) (Ill-posed inverse problem) (8) 2.4 P (Singular Value Decomposition : SVD) P R p q P = UΣV T (9) U =[u 1 u p ] R p p, V =[v 1 v q ] R q q (10) U T U = I p, V T V = I q Σ ( ) σ 1 σ 2... σ r 0, (r = min(p, q)) (11) ( ) σ 1 0 0 0 0 0 σ Σ= 2 0 0 0....... 0 0 σ p 0 0 Rp q (p<q ) (12) P σ 1 0 0 0 0 0 σ P =[u 1 u q ] 2 0 0 0....... 0 0 σ p 0 0 v 1. v q = p σ i u i v T i (13) σ i u i v T i P U V P =(UΣV T ) =(V T ) Σ U =(V T ) 1 Σ U 1 = V Σ U T (14) 4
Σ 1/σ 1 0 0 0 1/σ 2 0..... Σ = 0 0 1/σ p R q p (p<q ) (15) 0 0 0... 0 0 0 P (13) P = r v i u T i σ i (r = min(p, q)) (16) v i u T i (8) ŝ ŝ = ŝ + r u T i n σ i v i (r = min(p, q)) (17) (11) (17) P cond(p )=σ 1 /σ r (18) 2.5 (Truncated Singular Value Decomposition : TSVD ) TSVD θ>0 k P σ 1... σ k θ σ k+1...σ r (19) P k = k v i u T i σ i (20) 5
ŝ k = P k b = P k (P s + n) (21) k +1 2.6 Tikhonov Tikhonov ( (6)) ( ) E(s) = 1 2 P s b 2 + λ2 2 s 2 (22) ŝ = argmin E(s) (23) s λ (22) 2 ( 1 ) (23) ŝ E(s) (gradient) 0 n ( σ 2 ) ŝ λ = argmin E(s) = i vi u T i s σi 2 + b = VT 1 Σ U T b (24) λ2 σ i U V P P = UΣV T T 1+ λ2 0 σ 1 2 T =... (25) 0 1+ λ2 σn 2 ( ) Tikhonov ŝ λ (24) σ2 i σi 2+λ2 σ i >> λ 1 σ i << λ 0 λ 6
2.7 E D (s) = 1 2 P s b 2 2 + λ2 2 Ds p p (26) p p- (2- ) x p =( i x i p ) 1/p (27) D s 1 ( ) 2 D 1 ( ) p =1 Total Variation (TV) E D (s) s ( B ) 3 web (Moodle) Moodle B(T-1) http://adapt.cs.tsukuba.ac.jp/moodle263/course/view.php?id=7 ( ) t1@adapt.cs.tsukuba.ac.jp ( A-F) ( G-I J-L) 3 10/11, 13 7
10/18 (3F902) 11/1 1 A, B (manaba) 12/8 2 C, D, E (manaba) 2/14 3 F (manaba) 3.1 OpenCV OpenCV[1-4] OpenCV - GUI OpenCV Macintosh Moodle OpenCV 3.2 C or C++? OpenCV C C++ OpenCV C version 2 C++ C C C C, C++ C C++ 3.3 OpenCV 8 PNG PGM(Portable Gray Map) JPEG GIMP netpbm 8
[1] OpenCV ( http://opencv.org/) [2] OpenCV OpenCV [3]G.Bradski,A.Kaehler: OpenCV - [4] OpenCV ( http://opencv.jp) 4 4.1 OpenCV A OpenCV Moodle 2 (sample1.c, sample2.c) 2 (1) (2) (3) ( 2 ) (4) (5) OpenCV OpenCV (1) (2) (3) (4) (5) (1) (4) (6) (4) PNG PGM 4.2 B s(x) s(x) (Signal to Noise Ratio : SNR) Peak Signal to Noise Ratio : PSNR ( ) M 2 PSNR(dB) =10log 10 1 N x s(x) (28) s (x) 2 M, N 9
$ psnr < > < > 2 PSNR GIMP 4.3 C ( ) PSF OpenCV 0 PSF (1) (2) 2 D PSF p(x) = p 11 p 12 p 13 p 21 p 22 p 23 p 31 p 32 p 33 R 3 3 1. s(x) b(x) M N =3 3(pixel) (3) s R 9, b R 9 PSF P R 9 9 PSF P 0 2. PSF ( ) C 4.4 E PSF PSF n (n =1...7) 0 10
$ degrade < > <PSF > <0 (1-7)> < > PSF PSF 4.5 A-E F P F 32 32(pixel) 2 1 2 PSF n =0, 1, 4 3 (n =0 ) 6 P ( (8)) PSNR PSF PSF ( ) 1 ( ) ( ) OpenCV G P (MN) 2 A PSF 1,2 100 100 (pixel) 6 PSF A 11
A PSNR H TSVD θ PSNR PSNR PSNR θ (k) PSF 2 θ F G PSF I Tikhonov λ PSNR PSNR λ PSF 2 λ F G PSF ( ) J ( PSF ) ( ) K L Total Variation PSNR B 12
A PSF M,N P (MN) 2 M = N = 50(pixel) ( ) PSF k(x, y) =r(x)c(y) (29) PSF K = cr T = c 1 c 2. c m [ ] r 1 r 2 r n (K R m n, c R m, r R n ) (30) PSF K = cr T = c 1 c 2 c 3 [ r 1 r 2 r 3 ] = c 1 r 1 c 1 r 2 c 1 r 3 c 2 r 1 c 2 r 2 c 2 r 3 c 3 r 1 c 3 r 2 c 3 r 3 (31) PSF S R M N r c N N M M (Toeplitz) r 2 r 1 c 2 c 1 r 3 r 2 r 1 c 3 c 2 c 1 r 3 r 2 r 1 c 3 c 2 c 1 A r =......... R N N, A c =......... R M M r 3 r 2 r 1 c 3 c 2 c 1 r 3 r 2 r 1 c 3 c 2 c 1 r 3 r 2 c 3 c 2 (32) PSF (c 2, r 2 ) PSF ( ) B R M N B = A c SA T r (33) 13
(33) SVD Ŝ = A 1 c B(A T r ) 1 = V c Σ 1 c Uc T BU r Σ 1 r Vr T (34) SVD A c = U c Σ c V T c, A r = U r Σ r V T r (3) PSF (34) TSVD Tikhonov Σ c Σ r B Total Variation H Total Variation B.1 Total Variation (26) p =1 E D (s) = 1 2 P s b 2 2 + λ2 2 Ds 1 (35) s Tikhonov (1) E D (s) (2) s (1) s s(t +1)=s(t) η E D(s) (36) s η s B.2 Ds 1 D 14
s(x, y) d(x, y) =[ x s(x, y), y s(x, y)]t =[s x (x, y),s y (x, y)] T (37) Ds 1 d(x, y) 1 Ds 1 = s x (x, y) + s y (x, y) (38) x y x y s x (x, y) = s(x +1,y) s(x, y) s y (x, y) = s(x, y +1) s(x, y) [ ] [ 1, 1], 1 1 (PSF) L x, L y Ds 1 = L x s 1 + L y s 1 (39) E D (s) = 1 2 P s b 2 2 + λ2 2 L xs 1 + λ2 2 L ys 1 (40) E PSF L x, L y B.3 s Ds 1 s s E d (s) = s E d(s) 2 2 Tikhonov 1 s R { s s = 1 (s>0) 1 (s<0) = sign(s) (41) sign(s) s ±1 s R, a R s as = a (s >0) (a >0) a (s <0) (a >0) a (s >0) (a <0) a (s <0) (a <0) = a sign(as) (42) 15
s R n [ s s 1 = s 1 n s i... s n T n s i ] =[sign(s 1 )... sign(s n )] T = Sign(s) (43) Sign(s) s ±1 Sign([3 4] T )=[+1 1] T. s R n, A =[a ij ] R m n s As 1 = = m ( s 1 n a ij s j )... j=1 [ m a i1 sign(a i1 s 1 )... s n ( m n a ij s j ) j=1 m a in sign(a in s n ) = A T Sign(As). (44) T ] T B.4 s E D (s) s E D (s) =P T P s P T b + λ2 2 (LT x Sign(L xs)+l T y Sign(L ys)) (45) Total Variation TSVD Tikhonov 16