http://wwwieice-hbkborg/ 2 2 4 2 -- 2 4 2010 9 3 3 4-1 Lucas-Kanade 4-2 Mean Shift 3 4-3 2 c 2013 1/(18)
http://wwwieice-hbkborg/ 2 2 4 2 -- 2 -- 4 4--1 2010 9 4--1--1 Optical Flow t t + δt 1 Motion Field 3 3 1) 2) 3) Lucas-Kanade 4) 1 t (x, y) I(x, y, t) (x, y) t + δt (δx, δy) I(x, y, t) = I(x + δx, y + δy, t + δt) I(x, y, t) I(x + δx, y + δy, t + δt) = I(x, y, t) + I x δx + I y I δy + δt + HOT t HOT I δx x δt + I δy y δt + I δt t δt = 0, I x u x + I y u y + I t = 0 u x, u y x y u x = δx δt, u y = δy δt or (4 1) c 2013 2/(18)
http://wwwieice-hbkborg/ 2 2 4 (4 1) I x = I x, I x = I y, I t = I t (4 1) I x u x + I y u y = I t or Iu = I t (4 2) I = [I x I y ] u = [u x u y ] T (x, y) 2 aperture problem 4 1 4 1 4 2 4 1 4 2 E(u) = E data (u) + α E smooth (u) (4 3) c 2013 3/(18)
http://wwwieice-hbkborg/ 2 2 4 α E data (u) = I x u x + I y u y + I 2 t dx Ω (4 4) Ω x = [x y] T 2 L2 E smooth (u) = u x 2 + uy 2 dx = Ω Ω ( ) 2 ux + x ( ) 2 ux + y ( ) 2 uy + x ( ) 2 uy y dx (4 5) (4 3) x = ū k x I x[i x ū k x + I y ū k y + I t ], α 2 + Ix 2 + Iy 2 u k+1 u k+1 y = ū k y I y[i x ū k x + I y ū k y + I t ] α 2 + Ix 2 + Iy 2 k u 0 x, u 0 y ūk x, ū k y u x, u y 2 Horn Schunck 2) 3) E data (u) = Ω N γ i D i (I, u, x)dx i=1 (4 6) D i γ i N (4 6) N = 1 D 1 (4 4) E data c 2013 4/(18)
N E data (u) = Ψ γ i D i (I, u, x) dx Ω i=1 http://wwwieice-hbkborg/ 2 2 4 Ψ( ) E smooth (u) = Ψ( u x 2 + u y 2 )dx Ω (4 7) (4 5) (4 7) D 1 a D 2 (I, u, x) := I(x + u) I(x) 2 = 0 b D 3 (I, u, x) := H 2 I(x + u) H 2 I(x) 2 = 0 H 2 c D 4 (I, u, x) := I(x + u) I(x) 2 = 0, where = 2 x 2 + 2 y 2 d D 5 (I, u, x) := ( I(x + u) I(x) ) 2 = 0 c 2013 5/(18)
http://wwwieice-hbkborg/ 2 2 4 coarse-to-fine strategy coarse-to-fine warping techniques 3 Lucas-Kanade Lucas-Kanade 4) m m (4 2) I x1 u x + I y1 u y = I t1 I x2 u x + I y2 u y = I t2 (4 8) I xn u x + I yn u y = I tn n n = m m 1,, n (4 8) Au = b, where A = I x1 I x2 I y1 I y2, u = u x u, b = y I t1 I t2 (4 9) I xn I yn I tn u E = Au + b 2 A T Au = A T ( b), u = (A T A) 1 A T ( b) 1) JL Barron, DJ Fleet, and S Beauchemin, Performance of optical flow techniques, International Journal of Computer Vision, vol12, no1, pp43-77, 1994 c 2013 6/(18)
http://wwwieice-hbkborg/ 2 2 4 2) B Horn and B Schunck, Determining optical flow, Artificial Intelligence, vol17, pp185-203, 1981 3) A Bruth, T Brox, S Didas, and J Weickert, Highly accurate optic flow computation with theoretically justified warping, International Journal of Computer Vision, vol67, no2, pp141-158, 2006 4) B Lucas and T Kanade, An iterative image registration technique with an application to stereo vision, In Proc Seventh International Conference on Artificial Intelligence, pp674-479, 1981 c 2013 7/(18)
http://wwwieice-hbkborg/ 2 2 4 2 -- 2 -- 4 4--2 2010 9 4 3(a) x 0 x 4 3(b) 2)3) x 0 x 0,, x n 4 3 4--2--1 4 4 c 2013 8/(18)
http://wwwieice-hbkborg/ 2 2 4 4) 4 4 Mean Shift 1) 5) Mean Shift 4--2--2 4) p q S p,q I S p,q = min(p u, q u ) u=1 (4 10) u p u, q u u S p,q 0 1 4 5 A B A B c 2013 9/(18)
http://wwwieice-hbkborg/ 2 2 4 4 5 4 5 A B M S AM A M S BM B M A B A B A B A B A A A B S AM = min(s BM B, B A ) + A B A (4 11) S BM S AM 4 6 4 6 4--2--3 Mean Shift Mean Shift 1) Comaniciu Mean c 2013 10/(18)
http://wwwieice-hbkborg/ 2 2 4 Shift y Bhattacharyya B(p(y), q) = pu (y)q u (4 12) u U (4 12) (4 13) 1 B(p(y), q) pu (y 0 )q u + 1 qu p u (y) 2 2 p u U u U u (y 0 ) (4 13) (4 13) 2 Bhattacharyya Mean Shift vector Bhattacharyya Bhattacharyya Mean Shift vector y j+1 = w i = ( ni=1 y x i w i g j x i 2) h ( ni=1 y g j x i 2) h m δ[b(x i ) u] u=1 qu p u (y j ) (4 14) (4 15) t p 1 w 0 q t 1 4 7 Mean Shift h g(x) x i b(x i ) (4 15) w i t c 2013 11/(18)
http://wwwieice-hbkborg/ 2 2 4 t + 1 4 7 t t + 1 Mean Shift vector Bhattacharyya 4--2--4 5) Condensation t p(x t z t ) x N s (i) t = {x (i) t, π (i) t }(i = 1,, N) (4 16) t i x (i) t π (i) t t z t x t p(x t z t ) p(x t z t ) p(x t z t ) = αp(z t x t )p(x t z t 1 ) (4 17) α 4 8 4 8 Step1 N Step2 c 2013 12/(18)
http://wwwieice-hbkborg/ 2 2 4 Step3 Step4 L (i) t Step5 Step6 N Step7 t + 1 Step2 1) D Comaniciu, V Ramesh, and P Meer, Real-time tracking of non-rigid objects using mean shift, In Proceedings of the IEEE Computer Science Conference on Computer Vision and Pattern Recognition(CVPR-00), vol2, pp142-149, 2000 2) J Sun, W Zhang, X Tang, and H Shum, Bi-directional tracking using trajectory segment analysis, In Proceedings of the Tenth IEEE International Conference on Computer Vision (ICCV 05), vol1, pp717-724, 2005 3) Y Boykov and G Funka-Lea, Graph cuts and efficient n-d image segmentation, Int J Comput Vision, vol70, no2, pp109-131, 2006 4), V Vinod, :, D-II, vol81, no9, pp2035-2042, 1998 5) P Brasnett, L Mihaylova, D Bull, and N Canagarajah, Sequential Monte Carlo tracking by fusing multiple cues in video sequences, Image Vision Comput, vol25, no8, pp1217-1227, 2007 c 2013 13/(18)
http://wwwieice-hbkborg/ 2 2 4 2 -- 2 -- 4 4--3 3 2010 9 3 4 9 3 3 3 t = [t X t Y t Z ] T 3 R 6 3 N M i = [X i Y i Z i ] T (i = 1, 2,, N) f m i, f = [u i, f v i, f ] T t f = [t X, f t Y, f t Z, f ] T, R f A m i, f M i sm i, f = A[R f t f ] (4 18) m i, f, m i, f, M i 3 3 m i, f t f R f A 3 4 10 4 9 3 4 10 3 4--3--1 3 3 M i = [X i Y i Z i ](i = 1, 2,, N) 3 M i m i, f P f c 2013 14/(18)
http://wwwieice-hbkborg/ 2 2 4 sm i, f = P f (4 19) P f = A[R f t f ] (4 19) p 11 p 12 p 13 p 14 a 11 a 12 a 13 R 11 R 12 R 13 t X p 21 p 22 p 23 p 24 = k 0 a 22 a 23 R 21 R 22 R 23 t Y (4 20) p 31 p 32 p 33 1 0 0 a 33 R 31 R 32 R 33 t Z A R P 3 3 QR A R p 11 p 12 p 13 a 11 a 12 a 13 R 11 R 12 R 13 p 21 p 22 p 23 = 0 a 22 a 23 R 21 R 22 R 23 (4 21) p 31 p 32 p 33 0 0 a 33 R 31 R 32 R 33 t A t X a 11 a 12 a 13 p 14 t Y = 0 a 22 a 23 p 24 1 t Z 0 0 a 33 1 (4 22) 4--3--2 2 3 2 m T 1 F m 2 = 0 (4 23) F 8 1) 2 A 1, A 2 E E = A T 1 FA 2 (4 24) m 1 x 1 m 1 = A 1 x 1 = A 1 [R 1 t 1 ] M 1 (4 23) x T 1 E x 2 = 0 (4 25) E = [t ] R R = R 1 1 R 2 2 t = R 1 1 (t 2 t 1 ) 2 [t ] t E t R 2 c 2013 15/(18)
http://wwwieice-hbkborg/ 2 2 4 2) t 2 2 x t T Ex = 0 (4 26) E T t = 0 t st = t, t = 1 E T t 2 t t EE T t + λ(1 t T t) (4 27) λ t 0 2EE T t 2λt = 0 EE T t EE T E = [t ] R EE T = [t ] R R T [t ] T = [t ] [t ] T = t T t I t t T st = t t s R E = [t ] R t R = argmin E [t ] R 2 R (4 28) 4--3--3 N F 3 3 3) 3 M i = [X i Y i Z i ] T f m i, f = [u i, f v i, f ] u i, f v = s f r1 T X i i, f i, f r 2 T Y i i, f Z i (4 29) s f f r 1 T f, r 2 T f f R f 1 2 1 s 1 = 1, r 1 f = [1 0 0] T, r 2 f = [0 1 0] T N F c 2013 16/(18)
http://wwwieice-hbkborg/ 2 2 4 u 1,1 u i,1 u N,1 u 1, f u i, f u N, f u 1,F u i,f u N,F v 1,F v i,f v N,F v 1, f v i, f v N, f v 1,F v i,f v N,F = s 1 r 1 T 1 s f r 1 T f s f r 1 T F s 1 r 2 T 1 s f r 2 T f s f r 2 T F X 1 X i X F Y 1 Y i Y F Z 1 Z i Z F (4 30) D, M, S D = MS M S 3 D M S 3 3 M 3 2F S N 3 D 3 D D = VΣU T (4 31) Σ V U D 3 0 D 4 4 D = V ΣU T M = V (Σ ) 1 2, S = (Σ ) 1 2 U T D = M S 3 2F M N 3 S 3 3 Q D = (M Q)(Q 1 S ) (4 32) M r 1 T f r 1 f = 1, r 2 T f r 2 f = 1, r 1 T f r 2 f = 0 M = M Q Q 4--3--4 2 2 c 2013 17/(18)
http://wwwieice-hbkborg/ 2 2 4 3 3 4) 3 3 f P f = A f [R f t f ] i 3 M i = [X i Y i Z i ] T m i, f = [u i, f v i, f ] T s m i, f = P f P f = [p 1 f p 2 f p 3 f ]T su i, f p 1 T f sv i, f = p 2 T f s p 3 T f u p 1 T f i, f v = p 3 T f p i, f 2 T f p 3 T f E = 1 F N NF u i, f p1 T 2 f f =1 i=1 p 3 T f M + v i, f p2 T f i p 3 T f M 2 i (4 33) (4 34) (4 35) (4 36) E 3 M i P f ( ˆM 1,, ˆM N, ˆp 1 1, ˆp2 1, ˆp3 1,, ˆp1 F, ˆp2 F, ˆp3 F ) = argmin E (M 1,,M N,p 1 1,p 2 1,p 3 1,,p 1 F,p 2 F,p 3 F) (4 37) 1) G Xu and Z Zhang, Epipolar Geometry in Stereo, Motion and Object Recognition, A Unified Approach Kluwer Academic Publishers, 1996 2) OD Faugeras, Three-Dimensional Computer Vision, A Geometric Viewpoint MIT Press, Cambridge, MA, 1993 3) C Tomasi and T Kanade, Shape and motion from image streams under orthograph : a factorization method, International Journal of Computer Vision, vol9, no2, pp137-154, 1992 4) R Szeliski and SB Kang, Recovering 3d shape and motion from image streams using nonlinear least squares, Journal of Visiual Communication and Image Representation, vol5, no1, pp10-28, 1994 c 2013 18/(18)