Tài liệu Nghiên cứu phương pháp phát hiện đối tượng chuyển động trong video và ứng dụng

NG I H C KHOA H C T NHIÊN KHOA CÔNG NGH THÔNG TIN B MÔN CÔNG NGH TRI TH C K H TN TR CAO CHÁNH NGUYÊN HI N – KH NG TR NG GIANG C N TT – Đ H NGHIÊN C U PH NG PHÁP PHÁT HI N I T NG CHUY N NG TRONG VIDEO VÀ NG D NG K H O A LU N V N C NHÂN TIN H C TP. HCM, 2004 NG I H C KHOA H C T NHIÊN KHOA CÔNG NGH THÔNG TIN B MÔN CÔNG NGH TRI TH C - 0012551 - 0012537 Đ H CAO CHÁNH NGUYÊN HI N KH NG TR NG GIANG K H TN TR K H O A C N TT – NGHIÊN C U PH NG PHÁP PHÁT HI N I T NG CHUY N NG TRONG VIDEO VÀ NG D NG LU N V N C NHÂN TIN H C GIÁO VIÊN H NG D N T.S NGUY N ÌNH THÚC Th.s PH M PH M TUY T TRINH NIÊN KHÓA 2000 - 2004 L IC M N Chúng em xin chân thành cám n khoa Công ngh Thông tin, tr ng i K H TN h c Khoa h c T nhiên TP. HCM ã t o i u ki n t t cho chúng em th c hi n tài lu n v n t t nghi p này. Chúng em xin chân thành cám n quý Th y Cô trong khoa ã t n tình gi ng d y, trang b cho chúng em nh ng ki n th c quý báu trong nh ng n m h c v a qua. em trong su t th i gian th c hi n ng d n, ch b o và óng góp ý ki n cho chúng Đ Ph m Tuy t Trinh ã t n tình h ình Thúc và Cô Ph m H Chúng em xin chân thành cám n Th y Nguy n tài. – Chúng con xin nói lên lòng bi t n sâu s c ã i. C N TT ch m sóc, nuôi d y chúng con thành ng i v i Ông Bà, Cha M Xin chân thành cám n các anh ch và b n bè ã ng h , giúp và ng viên chúng em trong th i gian h c t p và nghiên c u. M c dù chúng em ã c g ng hoàn thành lu n v n trong ph m vi và kh n ng cho phép nh ng ch c ch n s không tránh kh i nh ng thi u sót. Chúng em kính mong nh n !c s c m thông và t n tình ch b o c a quý Th y Cô và các K H O A b n Sinh viên Cao Chánh Nguyên Hi"n – Kh Tháng 07/ 2004 Trang 1 ng Tr ng Giang M CL C CH NG 1. GI I THI U VÀ NG C 1.2. T ng quan v các nghiên c u tr 1.3. Các v n 1.4. CH TÀI. ...........................5 c ây .......................................................6 c n gi i quy!t ..............................................................................9 K H TN 1.3.1 1.3.2 1.3.3 TH C HI N Phân o n c nh theo tr#c th i gian........................................................... 10 Phân o n i t !ng Video ...................................................................... 11 T o ch m#c và tìm ki m Video................................................................ 12 Phác th o lu"n v#n.......................................................................................12 NG 2. PHÁT HI N CHUY N C NH B$NG T%NG H P &C TR NG..14 Gi i thi'u......................................................................................................14 2.2. M(t s) * t ng h+p nhi u ,c tr ng tr-c quan..........................................17 2.3. Rút trích ,c tr ng trong mi n nén MPEG................................................19 2.4. Phát hi'n ch p sáng .....................................................................................20 C N TT – Đ H 2.1. 2.5. Phát hi'n chuy.n c nh .................................................................................22 2.5.1 T$ng h!p các c tr ng dùng cây quy t nh ........................................... 23 2.5.2 Phát hi n chuy"n c nh tr c ti p ................................................................ 24 2.5.3 Phát hi n chuy"n c nh chuy"n ti p d n .................................................... 28 CH NG 3. PHÂN O N NH VIDEO. ................................................................31 K H O A 3.1. Gi i thi'u......................................................................................................31 3.1.1 Các k% thu t phân o n nh ...................................................................... 32 3.1.2. Phân o n và theo v t các vùng Video ..................................................... 34 3.2. Phân vùng và theo v!t b/ng t ng h+p ,c tr ng ........................................36 3.2.1. Khái quát chung ........................................................................................ 36 3.2.2. C&u trúc d li u theo không gian và th i gian .......................................... 38 3.2.3. Gán các i"m m#c tiêu.............................................................................. 39 3.2.3.1. Phân b 'ng u các m#c tiêu............................................................ 39 3.2.3.2. Các i"m có l !ng Gradient nh nh&t .................................................. 39 3.2.4. Quá trình n( volume ................................................................................. 41 3.2.4.1. N( volume d a vào liên k t h ng tâm............................................ 41 3.2.4.2. Các cách th c n( volume.................................................................. 44 3.2.4.3. Tinh l c l i các volume..................................................................... 46 3.2.5. S phân tích volume ................................................................................. 49 Trang 2 3.2.5.1. S rút trích qu% o........................................................................... 49 3.2.5.2. Các mô t nh l !ng........................................................................ 51 3.2.6. ) c l !ng chuy"n ng trên c s( c tr ng........................................... 53 3.2.6.1. Các i"m c tr ng ........................................................................... 54 3.2.6.2. ) c l !ng chuy"n ng dùng t ng quan pha................................. 54 3.2.6.4. Áp mô hình lên các vector chuy"n ng........................................... 55 CH NG 4. PHÂN TÁCH VÀ TÌM KI M IT K H TN 3.3. Xây d-ng th vi'n ,c tr ng.......................................................................56 3.3.1 Quan sát m t s k t qu phân o n .......................................................... 56 3.3.2. Trích ch n c tr ng tr c quan................................................................. 58 3.3.3. Tìm ki m n i dung Video theo không gian và th i gian .......................... 58 3.3.4. Mô hình truy v&n....................................................................................... 59 NG VIDEO ........................60 Gi i thi'u......................................................................................................60 4.2. Các mô t quan h'........................................................................................62 H 4.1. – Đ 4.3. H' th0ng t- (ng tách 0i t +ng có ngh1a ..................................................64 4.3.1. M t s khái ni m ...................................................................................... 65 4.3.2. Phân c&p fine-to-coarse............................................................................. 65 4.3.3. Phân c&p Coarse-to-fine............................................................................ 69 5.1. NG 5. XÂY D NG NG D NG 2NH V2 M&T NG C N TT CH I............................72 Gi i thi'u: ....................................................................................................72 K H O A 5.2. Các khái ni'm: .............................................................................................73 5.2.1. *nh d ng tính: ........................................................................................ 73 5.3.2. *nh âm tính : ............................................................................................ 73 5.2.3. C+a s$ con: ............................................................................................... 73 5.2.4. c tr ng: ................................................................................................. 73 5.2.5. *nh tích h!p: ............................................................................................. 74 5.3. Gi i thu"t h3c phân l p:..............................................................................76 5.4. Mô hình Phân t ng: .....................................................................................78 5.5. Hu n luy'n b( phân t ng: ...........................................................................79 5.6. K!t qu 4nh v4 m,t .....................................................................................82 Trang 3 CH NG 6. K T LU N VÀ H NG PHÁT TRI N . ..........................................83 6.1. K!t lu"n. .......................................................................................................83 6.2. H ng phát tri.n..........................................................................................84 K H O A C N TT – Đ H K H TN THAM KH O. ............................................................................................................85 Trang 4 tài V n t5o ch6 m7c và tìm ki!m Video – 1.1. Đ H Gi i thi'u và (ng c) th-c hi'n K H TN Ch )ng 1. Ngày nay, v i s phát tri"n c a các k% thu t nén nh Video và truy n thông, ta hoàn toàn C N TT có th" g+i tr c tuy n m t l !ng l n nh Video s . R&t nhi u các nhà cung c&p n i dung truy n thông ang phân ph i Video theo yêu c u qua m ng Internet. Ng ang có các i dùng t i nhà ng truy n b ng thông r ng ho c k t n i DSL " xem các hình nh Video ch&t l !ng cao. Trong khi l !ng d li u Video ang t ng lên nhanh chóng, các ng d#ng a truy n thông v n còn b gi i h n trong nh ng kh n ng qu n lý n i dung. Do v y ngày K H O A càng òi h i các k% thu t m i có th" x+ lý hi u qu , mô hình hoá và qu n lý n i dung Video. M t k ch b n i"n hình trong t o ch m#c và tìm ki m n i dung Video di n trong hình 1.1. Tr c tiên, các Video và nh v theo không gian và th i gian thích h!p. Các các u vào !c bi"u !c phân o n thành các c tr ng tr c quan sau ó !c rút ra t n v này " t o ch m#c và tóm l !c. Và cu i cùng, nh ng Video và nh này a ra và tìm ki m d a trên các c&u trúc và n !c c tr ng ( trên. Trong k ch b n v a nêu, k% thu t trên c s( n i dung là m t thành ph n quan tr ng cung c&p các cách tìm ki m d a vào tính t ãh ng t c tr ng. G n ây, nhi u nghiên c u ng t i l,nh v c này. M t s ví d# bao g'm QBIC, PhotoBook, VisualSeek, MARS Trang 5 và VideoQ [79,85,99,81,21]. M#c tiêu là nh-m cung c&p kh n ng tìm ki m tr c quan h n và t ng hoá quá trình chú gi i nh Video theo l i truy n th ng. Thêm vào ch m#c c tr ng, m t lo i k% thu t khác nh m t i phân tích và khai phá các c&u trúc cú pháp [129,116,104] và các tình hu ng ng ngh,a (semantic even) [83,59] trong x+ lý Video s+ d#ng tri th c !c dùng " sinh ra các tóm l !c ( m c ng ngh,a ho c có c&u trúc. C N TT – Đ H K H TN tích này có th" c thù và các mô hình. Nh ng k t qu c a các phân Hình 1.1: Quá trình phân o5n và tìm ki!m nh Video Lu n v n này ch y u trình bày nghiên c u c a chúng tôi v t m#c các c tr ng tr c quan và n i dung ng ngh,a trên d li u Video. C# th" là chúng K H O A tôi phát tri"n các công c# và ph 1.2. ng rút ra và t o ch ng pháp " gi i quy t các v&n sau. • Phát hi n chuy"n c nh nhanh và chính xác. • T ng phân vùng và t o ch m#c cho vi c tìm nh Video. • T ng phát hi n i t !ng chuy"n T ng quan v các nghiên c u tr ng trên nh Video. c ây Hình nh và Video là nh ng bi"u di n tr c quan c a thông tin. Trong nh ng n m g n ây, nhi u ph ng pháp ã !c phát tri"n nh-m tìm ki m nh và Video trên c s( c tr ng tr c quan c a chúng. Màu s c, vân nh, chuy"n Trang 6 ng và c&u t o không gian- th i gian là các [79]. Hai ph c tr ng ph$ bi n nh&t !c dùng trong so kh p tính t ng t tr c quan ng th c truy v&n ph$ bi n là truy v&n m u và truy v&n b-ng phác th o [21]. M t s nghiên c u ã t p trung vào tìm ki m nh t,nh. S phát tri"n ã lan t i các l,nh v c nh trích ch n c tr ng [20], ot ng t , ch m#c vector [29,31] và h c ng ngh,a [74]. Các nghiên c u v tìm ki m Video trên c s( c tr ng b gi i h n trong Phát [69,122]. Khi mà các k% thu t tìm nh có th" K H TN hi n chuy"n c nh (scene cut), trích khoá frame, gom nhóm và duy t qua (browsing) !c áp d#ng cho tìm ki m Video, các tr ng duy nh&t c a d li u Video òi h i nh ng gi i pháp cho nhi u v&n thách th c. So v i nh t,nh, Video là d li u m t cách liên t#c trên m t t c ng v i tr#c th i gian. *nh Video nh&t m i c y !c bi"u di n nh. M t nh Video có ch&t l !ng t t bao g'm 25 H n 30 frame trên m t giây. Bên c nh ó, nh Video c n l !ng l u tr l n và b ng thông Chính c c a m t gi Video MPEG-1 là h n 500 MB. Đ r ng. Kích th c tính liên t#c và l !ng d li u l n làm cho Video tr( nên thách th c h n chuy"n – khi x+ lý và qu n lý. Nói cách khác, khi nhi u thông tin h n, c bi t là theo th i gian và ng, ta l i có thêm nhi u c h i " phân tích các n i dung tr c quan trong nh ng ti n truy n thông liên t#c, n i dung ch a trong C N TT Video. H n n a, m c dù Video là ph nó có d ng phân c&p theo t nhiên. M t o n phim Video chuy n, shot, frame và ngay c các Video hi u qu i t !ng và hành òi h i toàn b ch m#c c a t&t c các t !ng h!p thành và khám phá c&u trúc bên d !c. Tóm t t các h ng ti p c n K H O A quy t ng. Nh ng h th ng tìm ki m n v này. S trích ch n các i là m t ch !c trình bày d !c chia thành các câu c n thi t nh ng ch a gi i i ây. Là m t khâu c b n c a t o ch m#c Video, các thu t toán c t c nh ã c u r ng rãi nh-m chia nh Video ban u ra thành các tr ng ( m c th&p nh màu s c, c nh, chuy"n i !c nghiên n v c b n (vd. shot ). Các ng ã ch ng t !c là úng c n cho phát hi n các thay $i theo th i gian [70,123]. D a trên các phân o n theo th i gian, d li u Video có th" ã !c bi"u di n m t cách hi u qu theo các d ng tóm t t. Nhi u k% thu t !c phát tri"n " làm ch m#c cho các shot ã M th ng ti p c n ph$ bi n khác !c phân o n. !c dùng trong nhi u h th ng là tr m t hay nhi u khoá frame cho m.i shot, và sau ó dùng các c h t ch n c tr ng nh nh màu s c, hình d ng hay vân nh " t o ch m#c các khoá frame này. Làm sao " ch n và t$ ch c Trang 7 khoá frame là v&n ti n b c/ng v nb n l n ( ây. Ngoài các ph ng pháp l&y m u n gi n, các thu t toán !c phát tri"n " dùng các thay $i v màu s c, chuy"n !c nhúng và các m t ng ng c a camera, i [111] " ch n l a các frame có th" truy n t nhi u thông tin nh&t c a m t shot. Vi c ch dùng khoá frame " t o ch m#c b qua thông tin chuy"n !c phân chia thành các shot riêng l0, m i quan h th i gian và các tình hu ng gi a các shot liên t#c không hu ng và hành chuy"n ng, m t s ph K H TN Tuy nhiên, khi Video ng trong Video. !c khai thác. Nh-m có th" tìm ki m tình ng pháp ã xu&t " bao hàm c thông tin v !c ng và th i gian vào các mô hình n i dung Video. Trong [14,23], nhi u mô t hình th c " bi"u di n m i quan h th i gian (vd. tr c, sau,…) và có th" so kh p và truy v&n nh ng c&u trúc theo th i gian nh v y. ) c l !ng chuy"n i t !ng và theo v t là m t s k% thu t chính ã H không gian-th i gian, phân o n Đ áp d#ng trong nhi u mô hình x+ lý. c tr ng tr c quan ch a ít thông tin ng ngh,a, và trong nhi u tr không thu n l!i và hi u qu cho ng !c ng h!p, i dùng khi tìm ki m Video mong mu n. Các tóm t t – Các ng, các lô gíc theo ( m c cao h n nh câu chuy n, c nh, ho c hành ng cho phép ng i dùng tìm ki m và C N TT duy t qua nhi u Video t i m c hi u qu và có tính tr c giác h n. Xem hình 1.2 ta th&y, m t câu chuy n tin t c t CNN !c chia phân c&p thành các o n, câu chuy n và các shot riêng l0 [129]. C&u trúc phân c&p này cung c&p m t tóm l !c nhi u t ng giúp ng i dùng duy t qua h t chi u dài o n Video. Thêm vào các c&u trúc th i gian ã phát hi n, nhi u s n. l c ã !c th c hi n nh-m rút ra nhi u o n có ngh,a t các shot. K H O A Trong [122], m t c&u trúc không gian quan tr ng. M t ch ng trình dài !c dùng " phát hi n các c nh có nhân v t !c chia thành các câu chuy n d a trên nh ng c nh có nhân v t quan tr ng. Trong [117], m t ' th chuy"n ti p c nh c n i dung và lu'ng th i gian c a Video. Nó ã cu c i tho i, hành ng và các !c báo cáo là có th" phát hi n các n v câu chuy n. Nói chung, không gi ng nh ng shot có th" !c nh ngh,a theo các m c th&p, các th c th" ( m c cao nh c nh hay câu chuy n khó có các !c dùng " ch n b t c tr ng ( !c n u ch d a vào c tr ng ( m c th&p. Nh quan sát trong [117], " gom chính xác ho c phân lo i các shot, nhi u mô hình ph c t p c n !c xây d ng d a vào các bi"u di n trung gian ho c Trang 8 tu1 thu c l,nh v c nh vùng nh và các i t !ng, Trong các nghiên c u g n ây, vài mô hình bi"u di n Video n$i b t nh MPEG-4 ho c MPEG-7 ã Tóm l i, khi s phát tri"n !c ch&p nh n. !c th c hi n trên nhi u l,nh v c t o ch m#c và tóm t t nh Video, nhi u thách th c v n còn là v&n c n gi i quy t. Do ó, nhi u k% thu t h n C N TT – Đ H K H TN !c yêu c u khi xây d ng h th ng tìm ki m Video hi u qu . Hình 1.2: C u trúc phân c p c8a m(t ch )ng trình tin t c 1.3. K H O A Các v n Nh c n gi i quy!t ã th o lu n ( trên, vi c t o ch m#c Video liên quan n các x+ lý phân o n, phân tích và tóm t t n i dung Video. Phân o n theo th i gian chia lu'ng Video dài thành các n v nh nh shot (thay vì dùng các frame riêng l0). Phân o n theo không gian rút ra các i t !ng ch a trong Video shot. Nh ng phân o n này làm ta có th" phân tích và mô hình hoá n i dung Video, xây d ng các c&u trúc nhi u m c mà ng i dùng có th" tìm ki m và duy t qua m t cách hi u qu nh&t, nh trình bày trong hình 1.3. Nhi u v&n d a trên thách th c t'n t i khi phân o n các i t !ng này. K ti p, ta s khái quát các ch Trang 9 i t !ng và xây d ng bi"u di n chính s !c c p trong lu n v n này. Chúng bao g'm phân o n c nh, phân o n i t !ng, t o ch m#c c – Đ H K H TN tr ng. 1.3.1 C N TT Hình 1.3: Bi.u di9n Video d-a trên 0i t +ng Phân o5n c nh theo tr7c th:i gian M c dù nhi u x+ lý ã !c th c hi n nh-m phát hi n c nh, các h th ng v n còn thi u nh ng kh n ng sau: 1) phát hi n s chuy"n ti p d n m t cách tin c y; 2) x+ lý c n th i gian th c; 3) gi i quy t các tình hu ng t ng t. K H O A sáng c bi t nh ch p sáng ho c thay $i ánh " xây d ng m t h th ng phân tích và tóm t t Video ( th i gian th c, chúng tôi phát tri"n m t s ' sao cho t$ng h!p các các k% thu t máy h c. Trong s ng dùng ' này, chúng tôi thông qua m t mô hình phát hi n s chuy"n ti p d n b-ng cách xem xét các th c. Chúng tôi c/ng gi i quy t c tr ng màu s c, c nh, chuy"n !c v&n c i"m c a nh ng giai o n kh(i u và k t ch p sáng và thay $i m( (aperture). Trang 10 Phân o5n 0i t +ng Video Các i t !ng Video là các thông tin rõ ràng nh&t trong d li u Video, và là tiêu chu2n cho các nh n th c tr c quan c a con ng mô t ho c ghi chú m t c nh quay ho c ã nh&n m nh v&n c p và tác i t !ng. Có th" hình dung là ta !c phép truy i t !ng m t cách tr c ti p t chu.i Video ã !c mã hoá. i u này ã cung c&p m t ti m n ng r&t l n cho các ng d#ng t ng tác a truy n thông. Chu2n MPEG-7, m t giao di n mô t n i dung a truy n thông, c/ng ' có th" t ng tác v i các c nh và i t !ng. nh ngh,a m t s C hai chu2n MPEG-4 và MPEG-7 không tiêu chu2n hoá các ph công c# rút trích i t !ng hay c tr ng [66]. Khi Video i t !ng và thông tin ch a trong nó ph i !c bi"u di n d !c rút trích tr tr( thành nh ng chu2n qu c t , các công c# phân o n i t !ng Video và – còn thi u. Ngày nay, các thu t toán phân o n t$ng quát và linh ho t ó cho th&y h th ng th giác con ng C N TT công trình. T thu c tính nào [63]. M t v&n nh c tr ng chuy"n !c nghiên c u trong i không tính các biên trên b&t c t p i"n hình v i các h th ng hi n nay là ch m t t p c !c dùng. M t ph n t nh ng i dùng " nh n d ng K H O A không có m t mô hình c tr ng ph$ bi n nh màu s c, c nh và i t !ng c/ng r&t quan tr ng. M t v&n i t !ng th t t t, s khó khi k t h!p nhi u vào quá trình phân o n i t !ng. Nhi u i t !ng khác nhau. i mà khác là n u c tr ng khác nhau c tr ng khác nhau có th" cho ra các phép n i " tho mãn nh ng yêu c u này, chúng tôi ã phát tri"n m t mô hình phân c&p nh-m bi"u di n nhi u c tr ng v n ng, các c&u trúc không gian-th i gian c/ng nh nh ng quy lu t bên d con ng suy i d ng pixel i t !ng. Trong khi MPEG-4 và MPEG-7 ang Đ b&t c mô hình n i dung nào trên c s( ng pháp và c khi xây d ng H thô nh ng i dùng i t !ng. Các nghiên c u g n ây trên MPEG-4 nén nh trên c s( ng t i các i. Nó thu c v tr c giác " ng K H TN 1.3.2 i t !ng và m t s ' phân o n và theo v t k t h!p c tr ng tr c quan. S ' này bao g'm hai ph n có quan h v i nhau. Tr m t thu t toán t c nh và chuy"n th&y là s t c h t, chúng tôi phát tri"n ng phân o n và theo v t vùng nh d a vào s k t h!p c a màu s c, ng. K t h!p v i quá trình bù tr chuy"n ng rút ra các vùng Video có th" Video. D a trên ph n ng toàn c#c, chúng tôi nh n !c dùng " ph#c h'i các u tiên, chúng tôi phát tri"n m t h th ng t Trang 11 i t !ng ng phân o n i t !ng Video có ngh,a. M t i t !ng có ngh,a th gi i th c. Nhi u i t !ng có ngh,a c thù. Các i t !ng này và bao g'm t p các vùng v i các x m i !c phát tri"n " thu ng theo v t. S ph#c h'i ng ng v i m t a ra b(i ng !c i dùng ho c d a trên !c mô hình hoá nh m t c&u trúc nhi u m c c tr ng k t h!p. M t ph !c các i t !ng ( th ng pháp gom nhóm và ánh i t !ng có ngh,a t các vùng nh ã !c t i t !ng t i các m c vùng và ng ngh,a cho ta nhi u c K H TN m t s tri th c nh ngh,a ng t tr ng d'i dào và m m d0o nh&t " mô t n i dung Video trong nhi u ng d#ng liên quan. 1.3.3 T5o ch6 m7c và tìm ki!m Video Bi"u di n Video d a trên shot và i t !ng cung c&p m t n n t ng linh ho t cho m#c hi n t i ch y u d a vào các H vi c t o ch m#c và tìm ki m Video (video indexing and retrieval). Các k% thu t t o ch c tr ng tr c quan t các khoá frame. Nh ng ng vào i t !ng. B-ng cách nh n d ng m i quan h gi a các các shot khác nhau, ta c/ng có th" i t !ng trong nh ngh,a nhi u tình hu ng ngang qua các shot ó. S i t !ng và c i"m c a nó giúp ta có th" tóm t t o n C N TT phát hi n các c nh có ngh,a, ng – và hành Đ t !ng Video cho phép ta mô t n i dung hi u qu h n. Ta d dàng k t h!p chuy"n i Video dài t i m c cao h n, ng n g n h n. Trong lu n v n này, chúng tôi nghiên c u các k% thu t t o ch m#c hi u qu và nh ng ph ng pháp tìm ki m dùng t p nhi u nh. M t mô hình truy v&n các c tr ng t i c hai m c i t !ng Video d a trên vùng !c i t !ng và vùng xu&t nh-m k t h!p c tr ng toàn c#c và t ng ph n l i, c/ng nh so sánh các c&u trúc không gian-th i K H O A gian khác nhau. 1.4. Phác th o lu"n v#n Trong ph n còn l i c a lu n v n, ta nghiên c u các k% thu t phân o n Video t$ng quát (bao g'm c không gian và th i gian), c/ng nh so kh p ' tìm ki m. Các ch ng k ti p c tr ng t ng ng và s !c t$ ch c nh sau ây. Trong Ch )ng 2, chúng tôi trình bày các thu t toán c t c nh quay. Các công trình tr c ây và các v&n ' t$ng h!p các m( r ng !c xem xét tr c tr ng màu s c, c nh, chuy"n Trang 12 c. Sau ó chúng tôi trình bày m t s ng cho vi c phát hi n chuy"n c nh ( th i gian th c. Các k% thu t máy h c, c bi t là cây quy t nh c/ng c p. Chúng !c tôi c/ng trình bày các thu t toán phát hi n các c nh thay $i d n, và m t s tình hu ng c bi t nh ch p sáng. Cu i cùng, m t s k t qu !c trình bày. Trong Ch )ng 3, chúng tôi trình bày m t h th ng tìm ki m Video dùng các vùng !c t ng theo v t. Tr c h t chúng tôi gi i thi u m t h th ng t phân o n và theo v t có k t h!p nhi u c tr ng " có các k t qu theo v t chính xác và áng tin c y. Sau ó, chúng tôi th o lu n c&u trúc c a th vi n trình bày các k% thu t truy v&n hi u qu trên các vùng nh ã Cu i cùng, m t s k t qu truy v&n !c trình bày. Trong Ch )ng 4, chúng tôi trình bày m t s ng ngh,a và tìm ki m i t !ng trên c s( t c tr ng tr c quan và !c t ng t d a trên mô hình H i t !ng i t !ng nhi u i t !ng trong th i t !ng chuy"n Đ c h t, chúng tôi trình bày các k% thu t phát hi n dùng các thông tin v chuy"n ng phân o n. ' k t h!p cho phân o n m c. 3 ay, chúng tôi dùng c#m t “ i t !ng ng ngh,a” " ch các gi i th c. Tr ng và vùng nh. Nh ng vùng nh này ã – t !ng. Cu i cùng, m t s k t qu th c hi n ng !c rút ra t ng t Ch )ng 3. Sau ó chúng tôi trình bày m t công c# tìm ki m Video d a trên i !c trình bày. C N TT Trong Ch )ng 5, chúng tôi s trình bày m t k% thu t d#ng c a nó vào h th ng ch m#c ng K H TN Video ã i t !ng chuy"n nh v m t ng i và ng ng. M t s gi i thu t m i s trình bày nh gi i thu t ADABoost…M t s k t qu cung s !c !c trình bày. Ch )ng 6 k t lu n v công vi c ã th c hi n và c/ng bàn v các ng d#ng và các ng phát tri"n trong t ng lai. K H O A h Trang 13 K H TN Ch )ng 2. – Đ H Phát hi'n chuy.n c nh b/ng t ng h+p nhi u ,c tr ng Gi i thi'u. C N TT 2.1. Các k% thu t t o ch m#c d a trên shot ã !c s+ d#ng r ng rãi " t$ ch c d li u Video. Phát hi n chuy"n c nh là m t trong các ph o n Video thành các frame liên t#c ng pháp ph$ bi n nh&t " chia n v nh nh&t nh-m t o ch m#c. M t shot bao g'm chu.i các !c ghi t Camera. Thông th ng, m t hành ng liên t#c di n ra bên K H O A trong m t shot v i i u ki n là c nh không thay $i quá l n. Tuy nhiên, v n có nhi u thay $i trong m t nh Video (vd chuy"n chuy"n ng c a ng c a camera), vi c phát hi n chính xác s chuy"n c nh quay không ph i d dàng. H n n a, các k% thu t i n nh !c dùng trong c nh nh tan bi n, m d n và co l i, ã sinh ra các thay $i khó mà phát hi n Các thu t toán c t c nh ã !c. !c nghiên c u t nh ng n m 90. Ph b n là o s khác bi t i"m nh gi a các frame d s l !ng các i"m nh khác nhau nh&t i t !ng, thay $i ánh sáng, và nh m t c nh camera và c a !c !c xu&t ra. Ph ng pháp c i d ng giá tr màu [126]. Trong [126], m và n u nó v !t qua m t giá tr ph n tr m ng pháp này không m nh do chuy"n i t !ng có th" gây ra khác bi t giá tr Trang 14 i"m nh qúa l n. ng c a Histogram màu ã !c dùng " gi i quy t !c v&n gi a các frame liên t#c không b nh h (ng nhi u b(i chuy"n t !ng [121]. Gi s+ Hi là m t histogram N-màu !c Di = ng c a camera và c a i !c rút ra t frame th i, khác bi t nh ngh,a nh sau: n j =1 | H i ( j ) − H i +1 ( j ) | n u Di l n h n m t ng ng cho tr hi u qu h n, χ 2 -test, nghi m so v i các c, m t c nh !c phát hi n t i frame i+1. M t !c gi i thi u trong [78], và o khác. Trong χ 2 -test, kho ng cách gi a hai Histogram 0 H n u H i ( j ) ≠ 0hayH i +1 ( j ) ≠ 0 n u ng !c l i Đ j =1 !c cho – χ i2 = ( H i ( j ) − H i +1 ( j )) 2 max( H i ( j ), H i +1 ( j )) o !c trình bày là t t h n khi thí b(i công th c sau: n K H TN frame này, nh phân b màu M c dù so sánh tr c ti p màu s c gi a các frame th c hi n r&t t t khi phát hi n hi n chính xác. C N TT c nh, các chuy"n ti p nh nh fade-in và fade-out, tan d n và co l i không !c phát Nh trình bày trong hình 2.1, s khác bi t màu s c qua các frame trong m t c nh thay $i d n nh h n so v i c nh quay tr c ti p. Trong lúc ó, chuy"n ti p d n tr h n so K H O A v i chuy"n c nh tr c ti p (h n 1 giây). Trang 15 K H TN Đ H Hình 2.1: So sánh c nh tr-c ti!p và c nh chuy.n ti!p Do s khác bi t giá tr màu nh c a c nh thay $i ít, m t ng này, m t thu t toán so sánh kép h i hai ng ng i t !ng. " gi i quy t ng pháp này òi ng ng t, m t l n h n cho chuy"n tr c ti p và m t ng ng nh h n cho ng bé h n ng viên ng c a n không th" xu&t trong [121]. Ph chuy"n d n. Ng !c C N TT v&n ng c a camera hay chuy"n – phân bi t gi a chuy"n ng ng l n h n !c áp d#ng tr c. N u không có c nh quay tr c ti p thì !c dùng " phát hi n c nh chuy"n ti p d n. Khi m t c nh chuy"n ti p !c phát hi n, khác bi t qua các frame Trong [119], m t h ng ti p c n d a trên c nh !c tích tr cho các frame liên t#c. !c xu&t " phát hi n các c nh tr c K H O A ti p và các c nh chuy"n ti p 'ng th i. Ph n tr m c nh i vào và thoát ra gi a hai frame !c tính. Biên c a c nh !c phát hi n b-ng cách so sánh hai ph n tr m này. S phát hi n chuy"n c nh th ng bao g'm trích ch n c tr ng và so sánh cho các c p frame liên t#c. ây là m t quá trình c n nhi u th i gian, và không th" th c hi n ( th i gian th c trên máy PC. H u h t nh Video chuy"n c nh tr c ti p t các vùng nén ã u !c nén v i chu2n MPEG, phát hi n !c nghiên c u trong nhi u công trình ã t i m c thi hành ( th i gian th c. Trong [69], các th ng kê vector chuy"n ng t !c dùng " phát hi n chuy"n c nh. Cho m t P-frame, t l gi a các kh i intra-code và s kh i inter-code !c tính. V i B-frame, t l s vector chuy"n Trang 16 ng ng !c l i và s vector chuy"n ng t i !c tính. T l cao ch ra r-ng chuy"n c nh t i B-frame ho c P- frame. Nói cách khác, t l th&p trên B-frame ch ra r-ng có m t c nh t i I-frame tr ng này, chúng tôi s trình bày m t s s t$ng h!p c a nhi u th c hi n • M ts ' phát hi n chuy"n c nh m i v i c tr ng tr c quan trong c mi n nén và không nén. Công vi c !c bao g'm các v&n sau ây. ' hi u qu t$ng h!p chuy"n ng và các c tr ng màu trong c mi n nén K H TN Trong ch và không nén. • M t thu t toán m i phát hi n chuy"n ti p d n, nh là ch p sáng, thay $i ho c chuy"n 2.2. c nó. ng c a camera. sáng, M(t s) * t ng h+p nhi u ,c tr ng tr-c quan t ng t ã !c nghiên c u nhi u trong các công trình hi n H M c dù chuy"n c nh thách th c. Trong [143], m t so sánh gi a nhi u thu t toán phát hi n chuy"n c nh ã !c th c hi n. Kho ng 90 ph n tr m chính xác Đ nay, s phát hi n chuy"n ti p d n v n còn là m t v&n !c báo cáo cho phát hi n chuy"n c nh. V i các chuy"n ti p d n, – chính xác v n trong kho ng t 70-80 ph n tr m. Trong khi xây d ng m t mô hình phân C N TT tích Video ( th i gian th c mà có th" áp d#ng cho các Video s ng g p ph i các thách th c khác. Tr ng, ta có th" c/ng s c h t, yêu c u c n th i gian th c th chính xác cao. Thêm vào ó, nhi u c tr ng ph c t p ng xung !c dùng " rút ra các c nh quay chính xác l i khó có th" tính ( th i gian th c. H n th n a, thay $i èn ch p th ng xu&t hi n nhi u trong các Video gia ình, K H O A th" gây ra k t qu phát hi n sai. Trang 17 tv i a n m t v&n sáng, vd.., khác có K H TN n nh ng v&n này và xa h n là t ng chính xác phát hi n Đ " nh&n m nh H Hình 2.2 Mô hình c;t c nh quay t ng h+p nhi u ,c tr ng chuy"n c nh, chúng tôi phát tri"n m t mô hình phát hi n c nh có t$ng h!p chuy"n t t v n là m t v&n ng. Các c tr ng thu c mi n nén !c áp d#ng tr t i th i gian th c. Chúng tôi c/ng thi t k các module thay $i ánh sáng. Bi"u ' cho toàn b mô hình qua mô hình c tr ng " th c hi n c t c nh m(. Chúng tôi dùng máy h c (cây quy t C N TT o và ng – màu s c, và thông tin v c nh. Làm sao " t$ng h!p các !c trình bày d ng, nh) " tìm ki m các c mi n không nén " t c bi t " phát hi n èn ch p và !c trình bày trong hình 2.2. Khái quát i ây. Chi ti t v các thu t toán s !c trình bày trong các ph n ti p theo. c h t, các K H O A Tr tính t các lo i chuy"n s c !c tính t c tr ng thu c mi n nén !c rút ra. Th ng kê chuy"n ng khác nhau trong B-frame ho c P-frame. ng !c khác bi t màu nh DC c a I ho c P-frame. M t yêu c u là gi i mã t ng ph n mà không th c hi n phép bi n $i ng !c DCT " rút ra các c tr ng này và do ó x+ lý s nhanh h n. Module ti p theo phát hi n các ch p sáng n u có. i u này th c hi n !c là nh so sánh khác nhau màu s c gi a các frame và khác bi t màu s c theo th i gian dài. N u m t ch p sáng !c phát hi n t i m t frame, không th c hi n phát hi n c nh trên frame này và ng !c l i. Do chuy"n c nh tr c ti p có th" !c phát hi n m t cách chính xác, tr c h t ta ki"m tra xem có m t c nh tr c ti p hay không. N u không có c nh tr c ti p, ta s ki"m Trang 18