›
›

Luận văn tốt nghiệp - Đề tài: "Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp" - Đại học Quốc gia TP.HCM-Trường Đại học Khoa học Tự nhiên - Năm 2003

pdf 44 trang phuongnguyen 2530
Download
Bạn đang xem 20 trang mẫu của tài liệu "Luận văn tốt nghiệp - Đề tài: "Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp" - Đại học Quốc gia TP.HCM-Trường Đại học Khoa học Tự nhiên - Năm 2003", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfluan_van_tot_nghiep_de_tai_phat_hien_va_dinh_vi_su_thay_doi.pdf

Nội dung text: Luận văn tốt nghiệp - Đề tài: "Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp" - Đại học Quốc gia TP.HCM-Trường Đại học Khoa học Tự nhiên - Năm 2003

  1. BOÄ GIAÙO DUÏC VAØ ÑAØO TAÏO ÑAÏI HOÏC QUOÁC GIA THAØNH PHOÁ HOÀ CHÍ MINH TRÖÔØNG ÑAÏI HOÏC KHOA HOÏC TÖÏ NHIEÂN KHOA TOAÙN - TIN HOÏC BOÄ MOÂN ÖÙNG DUÏNG TIN HOÏC LUAÄN VAÊN TOÁT NGHIEÄP: PHAÙT HIEÄN VAØ ÑÒNH VÒ SÖÏ THAY ÑOÅI CUÛA ÑOÁI TÖÔÏNG TRONG DAÕY AÛNH LIEÂN TIEÁP GVHD : Th.S Phaïm Theá Baûo SVTH : Huyønh Leâ Taán Taøi - 9911178 Hoà Quang Thaùi - 9911191 Thaønh phoá Hoà Chí Minh 07 - 2003
  2. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 2 lôøi caûm ôn Chuùng em xin chaân thaønh caûm ôn Ban giaùm hieäu, caùc thaày coâ giaûng daïy tröôøng Ñaïi Hoïc Khoa Hoïc Töï Nhieân cuøng caùc thaày coâ trong khoa Toaùn – Tin hoïc ñaõ taän tình höôùng daãn, truyeàn ñaït kieán thöùc cho chuùng em trong nhöõng thaùng naêm ôû giaûng ñöôøng Ñaïi Hoïc. Chuùng em xin chaân thaønh caûm ôn Th.S Phaïm Theá Baûo, laø ngöôøi tröïc tieáp höôùng daãn, taïo ñieàu kieän vaø giuùp ñôõ chuùng em trong suoát thôøi gian thöïc hieän luaän vaên. Chuùng em cuõng xin ghi nhaän söï giuùp ñôõ cuûa Prof. Sethian (University of Berkeley, America), Ph.D Grinas (University of Crete, Greece), Ph.D Sifakis (University of Stanford, America) vaø anh Voõ Tröôøng Tieàn (Coâng ty TNHH Compotech). Vaø cuoái cuøng, xin caûm ôn gia ñình vaø beø baïn ñaõ ñoäng vieân vaø giuùp ñôõ trong suoát con ñöôøng hoïc vaán. TP Hoà Chí Minh , thaùng 7 naêm 2003 Nhoùm thöïc hieän GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  3. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 3 MUÏC LUÏC LÔØI MÔÛ ÑAÀU 3 CHÖÔNG 1 LEVEL SET & FAST MARCHING 6 1.1 Giới thiệu 6 1.2 Phöông phaùp Level Set 7 1.2.1 Phöông trình Level Set 7 1.2.2 Nghieäm xaáp xæ cuûa phöông trình Level Set 9 1.2.3 Kyõ thuaät Narrow Band 10 1.3 Phöông phaùp Fast Marching 11 1.3.1 Phöông trình Eikonal 11 1.3.2 Nghieäm xaáp xæ cuûa phöông trình Eikonal 12 1.3.3 Thuaät toaùn Fast Marching Level Set (FMLS) 13 1.3.4 Chi tieát caùc böôùc trong thuaät toaùn FMLS 15 1.4 Thuaät toaùn Multi - Class Fast Marching 18 CHÖÔNG 2 PHAÙT HIEÄN SÖÏ THAY ÑOÅI TRONG DAÕY AÛNH LIEÂN TIEÁP 20 2.1 Toùm taét phöông phaùp söû duïng FM LS vaø SRG 20 2.2 Phaùt hieän ñoái töôïng chuyeån ñoäng 21 2.2.1 Thieát laäp moâ hình thoáng keâ 21 2.2.2 Gaùn nhaõn khôûi taïo ban ñaàu 22 2.2.3 Lan truyeàn nhaõn 25 2.3 Ñònh vò ñoái töôïng 28 2.3.1 Khôûi taïo 28 2.3.2 Taïo vuøng chöùa bieân 29 2.3.3 Loïc bieân ñoái töôïng 30 CHÖÔNG 3 KEÁT QUAÛ VAØ HÖÔÙNG PHAÙT TRIEÅN 34 3.1 Thöïc hieän 34 3.2 Keát quaû thöïc nghieäm 35 3.3 Höôùng phaùt trieån 35 TAØI LIEÄU THAM KHAÛO 36 PHUÏ LUÏC 38 Öôùc löôïng tham soá baèng phöông phaùp hôïp lyù cöïc ñaïi 38 Giaûi thuaät phaân lôùp baèng phöông phaùp xaùc suaát 40 Heä maøu CieLab 43 LÔØI MÔÛ ÑAÀU Trong thôøi ñaïi buøng noå thoâng tin nhö hieän nay, maùy tính ngaøy caøng ñöôïc söû duïng roäng raõi trong caùc lónh vöïc nghieân cöùu khoa hoïc vaø trong ñôøi soáng haøng ngaøy. GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  4. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 4 Caùc öùng duïng töø vieäc nghieân cöùu söû duïng maùy tính mang laïi nhöõng lôïi ích thieát thöïc voâ cuøng lôùn cho con ngöôøi, trong ñoù phaûi keå ñeán nhöõng öùng duïng trong lónh vöïc thò giaùc maùy tính, xöû lyù aûnh . Vaø moät öùng duïng thöôøng gaëp trong lónh vöïc naøy laø caùc heä thoáng camera theo doõi, quan saùt söû duïng trong an ninh, quoác phoøng, maø maáu choát cuûa caùc heä thoáng naøy laø nhaän bieát söï thay ñoåi cuûa caùc frame aûnh lieân tieáp. Ta coù theå hình dung moät heä thoángï theo ñôn giaûn nhö sau: cöù sau moät chu kì hôïp lyù (khoaûng 2 – 3 giaây), camera seõ cho ta moät aûnh chuïp töø khoâng gian ñang caàn theo doõi. Vaø muïc tieâu ñaët ra laø heä thoáng phaûi baùo ñoäng khi phaùt hieän söï thay ñoåi giöõa caùc frame aûnh ñoù. Coâng vieäc naøy neáu thöïc hieän ñöôïc seõ laøm giaûm bôùt khoâng gian löu tröõ, chæ löu laïi nhöõng aûnh khaùc nhau trong heä thoáng thay vì phaûi löu laïi toaøn boä aûnh chuïp ñöôïc. Ngoaøi ra, neáu xaùc ñònh ñöôïc chính xaùc caùc ñoái töôïng thay ñoåi trong caùc frame aûnh lieân tieáp, ta seõ taïo ñöôïc moät tieàn ñeà lôùn cho caùc heä thoáng môû roäng sau naøy nhö : neùn aûnh video (chuaån MPEG), heä thoáng nhaän daïng ñoái töôïng ñoäng online, caùc kyõ thuaät phaân tích vaø öôùc löôïng chuyeån ñoäng Coù raát nhieàu phöông phaùp ñeå giaûi quyeát baøi toaùn treân. Ñôn giaûn thì coù kyõ thuaät tröø aûnh treân töøng pixel, hoaëc treân töøng khoái pixel. Phöùc taïp hôn thì coù caùc kyõ thuaät söû duïng loïc Kalman, moâ hình Markov aån, Trong ñeà taøi, chuùng em seõ trình baøy moät phöông phaùp môùi vaø hieäu quaû hôn nhöõng phöông phaùp treân, chuû yeáu döïa treân lyù thuyeát Level Set, thuaät toaùn Fast Marching vaø thuaät toaùn Seeded Region Growing. Caáu truùc ñeà taøi ñöôïc phaân thaønh caùc chöông nhö sau - Chöông 1: Phöông phaùp Level Set vaø phöông phaùp Fast Marching - Chöông 2: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa caùc ñoái töôïng trong daõy aûnh lieân tieáp döïa treân thuaät toaùn Fast Marching vaø Seeded Region Growing. - Chöông 3: Keát quaû vaø höôùng phaùt trieån. TP Hoà Chí Minh, thaùng 7 naêm 2003 GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  5. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 5 Nhoùm thöïc hieän GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  6. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 6 LEVEL SET & Fast Marching Phöông phaùp Fast Marching1 vaø phöông phaùp Level Set2 laø nhöõng phöông phaùp soá hoïc coù theå theo doõi ñöôïc söï tieán trieãn cuûa ñöôøng cong chuyeån ñoäng töøng phaàn. Ñöôøng cong naøy coù theå coù nhöõng goùc nhoïn, coù theå taùch ra thaønh nhieàu ñöôøng cong rieâng bieät cuõng nhö coù theå hôïp laïi thaønh moät ñöôøng cong lôùn hôn. Ñaây cuõng laø hai kyõ thuaät ñöôïc aùp duïng roäng raõi trong nhieàu ngaønh khoa hoïc nhö : Hình hoïc tính toaùn, Thò giaùc maùy tính, Cô hoïc chaát loûng, Cheá taïo chip, Giới thiệu Phöông phaùp Fast Marching [3, 13, 14] (Sethian – 1996) vaø phöông phaùp Level Set [3, 15] (Osher vaø Sethian – 1988) laø nhöõng kyõ thuaät soá hoïc ñöôïc thieát laäp ñeå theo doõi söï tieán trieån cuûa ñöôøng cong, nhaèm giaûi quyeát baøi toaùn sau: Xeùt moät ñöôøng cong kín trong maët phaúng 2 chieàu (maët kín trong khoâng gian 3 chieàu), chia maët phaúng (khoâng gian) thaønh hai vuøng taùch bieät laãn nhau. Ta töôûng töôïng ñöôøng cong (maët) ñoù chuyeån ñoäng töøng phaàn theo höôùng phaùp tuyeán cuûa noù vôùi moät vaän toác F. Muïc tieâu ñaët ra laø laøm sao taïi moãi thôøi ñieåm baát kyø, ta phaûi xaùc ñònh vò trí cuûa ñöôøng cong töông öùng vôùi thôøi ñieåm ñoù. Ñieåm chuù yù ôû ñaây laø ta chæ xeùt caùc chuyeån ñoäng theo höôùng phaùp tuyeán. Ñeå deã töôûng töôïng hôn, ta haõy nghó ñeán vieân nöôùc ñaù khi boû vaøo chaäu nöôùc noùng. Vieân nöôùc ñaù naøy seõ nhoû daàn theo thôøi gian, hay ñöôøng bao quanh cuïc ñaù naøy seõ chòu moät löïc töông töï moät löïc keùo vaøo taâm. Ñaây laø moät tröôøng hôïp cuûa baøi toaùn treân vôùi vaän toác F 0 laø khi ta bôm moät quaû boùng, vaø quaû boùng ñoù seõ lôùn daàn theo thôøi gian. 1 Fast Marching Methods: phöông phaùp lan truyeàn nhanh (taïm dòch) 2 Level Set Methods: phöông phaùp tieáp caän döïa treân ñöôøng möùc (taïm dòch) GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  7. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 7 t Hình 1: Söï tieán trieån cuûa ñöôøng cong Thoaït nhìn, yù töôûng ñôn giaûn ñeå giaûi quyeát baøi toaùn naøy laø ta seõ bieåu dieãn ñöôøng cong thoâng qua moät soá ñieåm ñònh vò. Khi ñöôøng cong chuyeån ñoäng vôùi vaän toác F, thì nhöõng ñieåm ñònh vò naøy cuõng chuyeån ñoäng cuøng vôùi vaän toác ñoù. Baèng moät soá coâng thöùc vaät lyù, ta coù theå deã daøng xaùc ñònh vò trí môùi cuûa nhöõng ñieåm naøy, vaø töø ñoù xaây döïng laïi ñöôøng cong. Hieån nhieân, soá ñieåm ñònh vò ñöôïc choïn caøng nhieàu thì ñöôøng cong ñöôïc xaây döïng caøng chính xaùc. Tuy nhieân, phöông phaùp treân seõ khoâng thöïc hieän ñöôïc khi caùc ñieåm ñònh vò naøy chuyeån ñoäng ngang qua nhau, hay ñöôøng cong bò taùch ra thaønh nhieàu phaàn. Caùc phöông phaùp xöû lyù hieäu quaû tröôøng hôïp phöùc taïp treân chính laø phöông phaùp Level Set vaø phöông phaùp Fast Marching maø ta seõ xeùt ñeán trong phaàn keá tieáp. Phöông phaùp Level Set Phöông trình Level Set Cho vò trí ban ñaàu cuûa ñöôøng cong Γ trong R2, vaø haøm vaän toác F bieåu thò chuyeån ñoäng cuûa Γ theo phöông phaùp tuyeán. Ñaët φ(x, t = 0) = ±d, vôùi d laø khoaûng caùch töø ñieåm x ñeán Γ, daáu coäng (hay tröø) bieåu thò x naèm ngoaøi (hay trong) Γ. Ta deã daøng nhaän thaáy raèng: {x | φ(x(t), t = 0) = 0} ≡ Γ vaø vò trí cuûa Γ taïi thôøi ñieåm t laø taäp hôïp x sao cho φ(x(t), t) = 0. (1.2.1a) GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  8. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 8 z = φ(x,y,t) y ñöôøng möùc goác γ(0) x x z = φ(x,y,t) y ñöôøng möùc goác γ(t) x Hình 2: Söï tieán trieån cuûa ñöôøng troøn theo phöông phaùp Level Set Töø coâng thöùc (2.1), ta ñi tìm söï töông quan giöõa φ(x, t) vaø φ(x, t = 0) Ñaïo haøm coâng thöùc (2.1), vaø theo tính chaát ñaïo haøm haøm hôïp, ta coù: φt + ∇φ(x(t), t). x’(t) = 0 (1.2.1b) Do F laø vaän toác cuøng chieàu vôùi vector phaùp tuyeán, neân x’(t).η = F, vôùi η laø vector ∇φ phaùp tuyeán η = . ∇φ Vì vaäy, phöông trình (2.2) trôû thaønh : φt + F|∇φ | = 0 (1.2.1c) Phöông trình (2.3) ñöôïc gọi laø phöông trình Level Set. Lôøi giaûi cuûa baøi toaùn ñöôïc ñaët ra ban ñaàu cuõng laø nghieäm cuûa phöông trình Level Set. Caùc lôøi giaûi soá hoïc khi “rôøi raïc hoùa” phöông trình naøy ta seõ trình baøy ôû phaàn sau. Moät vaøi tính chaát cuûa phöông phaùp Level Set 1. Phöông phaùp Level Set giaûi quyeát hieäu quaû nhöõng bieán ñoåi topology treân ñöôøng cong Γ. Vò trí ñöôøng cong taïi thôøi ñieåm t ñöôïc cho bôûi taäp möùc goác (zero level set) φ(x, t) = 0. Taäp hôïp naøy khoâng nhaát thieát phaûi laø moät ñöôøng cong ñôn, vaø noù coù theå bò taùch ra hay gheùp laïi khi tieán trieån. GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  9. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 9 Hình 3 : Söï tieán trieån cuûa hai ñöôøng troøn 2. Caùc ñaëc tính hình hoïc cuûa ñöôøng cong coù theå ñöôïc deã daøng xaùc ñònh töø ∇φ phöông trình Level Set φ. Vectô phaùp tuyeán n = vaø ñoä cong cuûa moãi ∇φ ∇φ taäp ñoàng möùc laø κ = ∇ . ∇φ 3. Moâ hình Level Set khoâng thay ñoåi trong tröôøng hôïp nhieàu chieàu. 4. Döïa treân nghieäm maïnh cuûa phöông trình ñaïo haøm rieâng Level Set ñeå ñaûm baûo tính duy nhaát, vaø söï hôïp leä cuûa nghieäm yeáu. 5. Nghieäm xaáp xæ cuûa phöông trình Level Set coù ñöôïc nhôø moâ hình tính toaùn döïa treân luaät baûo toaøn hyperbolic. Nghieäm xaáp xæ cuûa phöông trình Level Set Nhö ñaõ ñeà caäp ôû treân, ta caàn moät nghieäm xaáp xæ cho phöông trình Level Set ñeå chuyeån baøi toaùn töø lieân tuïc sang rôøi raïc, vaø moät trong nhöõng nghieäm ñôn giaûn nhaát laø: [15] 1/ 2 n+1 n −x 2 + x 2 − y 2 + y 2 φij = φij − Δt()max()Dij φ,0 + min(Dij φ) max(Dij φ,0) + min(Dij φ,0) (1.2.2) Trong ñoù F = 1 GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  10. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 10 + x −x Dij φ = (φi+1, j −φi, j )/(Δx), Dij φ = (φi, j − φi−1, j )/(Δx) + y − y Dij φ = (φi, j+1 − φi, j )/(Δy), Dij φ = (φi, j − φi, j−1 )/(Δy) Kyõ thuaät Narrow Band Phöông phaùp ñöa treân phuï thuoäc vaøo vieäc tính toaùn söï tieán trieån cuûa taát caû caùc ñöôøng möùc, chöù khoâng chæ rieâng ñöôøng möùc goác (zero level set) töông xöùng. Ñieàu naøy ñoøi hoûi moät söï tính toaùn phöùc taïp, vaø caøng phöùc taïp hôn khi phöông phaùp Level Set chuyeån baøi toaùn hôn moät chieàu so vôùi baøi toaùn goác (chieàu thôøi gian). Ñeå caûi tieán phöông phaùp, ta caàn coù moät söï thay ñoåi trong kyõ thuaät duyeät, töùc laø chæ tính toaùn trong laân caän cuûa ñöôøng möùc goác. Kyõ thuaät naøy ñöôïc goïi laø phöông phaùp daûi heïp (Narrow Band). Ñoä phöùc taïp tính toaùn cuûa kyõ thuaät naøy trong khoâng gian 3 chieàu cho N3 ñieåm treân löôùi giaûm töø O(N3) xuoáng coøn O(kN2), vôùi k laø soá löôïng oâ trong Narrow Band. Daãn ñeán chi phí tính toaùn ñöôïc ruùt goïn ñaùng keå. YÙ töôûng cô baûn cuûa phöông phaùp naøy laø ñaùnh daáu caùc ñieåm treân löôùi vôùi moät trong caùc nhaõn alive3 , land mines4 hoaëc far away5, phuï thuoäc vaøo chuùng naèm trong, naèm treân, hoaëc naèm ngoaøi band. ÔÛ moãi böôùc tieán trieån, moät ñieåm land mines seõ trôû thaønh alive, vaø band ñöôïc caäp nhaät trôû laïi vôùi nhöõng laân caän cuûa ñieåm land mines vöøa tìm. alive land mines far away Hình 4 Kyõ thuaät ñaùnh daáu ñieåm trong phöông phaùp Narrow Band Kyõ thuaät Narrow Band laø tieàn ñeà cuûa moät thuaät toaùn hieäu quaû hôn, ñoù laø thuaät lan truyeàn nhanh (Fast Marching Level Set) seõ ñöôïc trình baøy trong phaàn keá. 3 alive : bieåu dieãn nhöõng ñieåm ñaù thuoäc veà ñöôøng cong 4 land mines hay trial : bieåu dieãn nhöõng ñieåm seõ ñöôïc choïn gaàn nhaát ñeà gheùp vaøo ñöôøng cong 5 far away : bieåu dieãn nhöõng ñieåm chöa ñöôïc xeùt ñeå gheùp vaøo ñöôøng cong, hay ñöôøng cong seõ phaûi caàn moät khoaûng thôøi gian khaù lôùn môùi ñeán ñöôïc caùc ñieåm naøy. GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  11. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 11 Phöông phaùp Fast Marching Phöông trình Eikonal Baây giôø, chuùng ta tieáp tuïc tìm hieåu phöông phaùp Fast Marching Level Set [3], moät lôøi giaûi hieäu quaû cho baøi toaùn ñöôøng cong chuyeån ñoäng trong tröôøng hôïp vaän toác F khoâng ñoåi daáu. Cuõng xeùt baøi toaùn nhö treân nhöng ñöôøng cong chuyeån ñoäng vôùi vaän toác F = F(x, y) > 0 ∀(x, y) (hoaëc F(x, y) < 0 ∀(x, y) ). Vôùi vaän toác luoân döông ñöôøng cong seõ luoân “phình ra” nhö trong ví duï bôm quaû boùng, vaø vôùi vaän toác luoân aâm ñöôøng cong seõ luoân “co laïi” nhö trong ví duï vieân nöôùc ñaù boû vaøo chaäu nöôùc noùng. Phöông trình Level Set : φt + F(x, y, z)∇φ = 0 (1.3.1a) Giôùi haïn baøi toaùn trong tröôøng hôïp 2 chieàu, vaø ta bieåu dieãn söï tieán trieån cuûa ñöôøng cong treân löôùi ñieåm N*N. Goïi T(x, y) laø thôøi ñieåm maø ñöôøng cong ñi qua ñieåm (x, y). Ta coù theå xaùc ñònh ñöôïc haøm T(x, y) do tính chaát ñöôøng cong “phình ra” hoaëc “co laïi” neân noù luoân ñi qua moãi ñieåm treân löôùi ñieåm chæ moät laàn duy nhaát. Töø coâng thöùc : “ñöôøng ñi = vaän toác * thôøi gian”. Khi xeùt baøi toaùn moät chieàu ta coù dT 1 = F (1.3.1b) dx T(x) dT dx Hình 5: quaõng ñöôøng = vaän toác * thôøi gian Coøn trong tröôøng hôïp nhieàu chieàu, ∇T vuoâng goùc vôùi ñöôøng möùc thôøi ñieåm T, vaø phöông trình (1.3.1b) trôû thaønh ∇T F = 1 (1.3.1c) GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  12. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 12 Phöông trình (1.3.1c) laø moät daïng cuûa phöông trình Eikonal (1). Hình 6: Bieåu dieãn maët noùn T Moät vaøi tính chaát cuûa phöông phaùp Fast Marching - Chuyeån baøi toaùn töø moâ hình ñoäng sang moâ hình tónh, ñöôøng cong ñöôïc caäp nhaät theo chieàu taêng töø giaù trò nhoû nhaát ñeán giaù trò lôùn nhaát cuûa T. - Töông töï phöông phaùp Level Set : khoâng thay ñoåi tính chaát trong tröôøng hôïp nhieàu chieàu, coù theå thu ñöôïc nghieäm xaáp xæ baèng caùch “rôøi raïc hoùa” vaø giaûi nghieäm yeáu cho phöông trình Eikonal. Nghieäm xaáp xæ cuûa phöông trình Eikonal Ta xeùt baøi toaùn hai chieàu giôùi haïn trong oâ [0, 1] x [0, 1] vaø töôûng töôïng ñöôøng cong ban ñaàu naèm treân truïc y = 0, vaø vaän toác F laøm ñoái töôïng chuyeån ñoäng treân truïc x. Söû duïng phöông phaùp xaáp xæ gradient, ta tìm moät nghieäm trong oâ ñôn vò cuûa phöông trình [9]. −x 2 + x 2 − y 2 + y 2 1 []max(D T,0) + min(D T,0) + max(D T,0) + min(D T,0) = 2 ij ij ij ij F hoaëc coù theå vieát goïn hôn: −x +x 2 − y + y 2 1 max()max(D T,0),− min(D T,0) + max(max(D T,0),− min(D T,0) = 2 (1.3 [ ij ij ij ij ] F .2) 2 n (1) ⎛ ∂u ⎞ phöông trình Eikonal: ∑⎜ ⎟ = 1 i=1 ⎝ ∂xi ⎠ GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  13. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 13 −x Tij − Ti−1, j +x Ti+1, j − Ti, j − y Tij − Ti, j−1 + y Ti, j+1 − Tij với Dij T = ; Dij T = ; Dij T = ; Dij T = xi − xi−1 xi+1 − xi y j − y j−1 y j+1 − y j Thuaät toaùn Fast Marching Level Set (FMLS) Ñieåm maáu choát ñeå xaây döïng thuaät toaùn FMLS laø ta seõ ñöa baøi toaùn lan truyeàn veà moät chieàu theo T, taêng daàn töø giaù trò thaáp nhaát ñeán giaù trò cao nhaát. YÙ töôûng chính ôû ñaây laø ta seõ ñaùnh daáu taát caû caùc ñieåm trong löôùi töông töï phöông phaùp Narrow Band. ÔÛ moãi böôùc, ta tìm moät vò trí trong caùc laân caän cuûa ñöôøng cong taïi böôùc ñoù, coù giaù trò thôøi ñieåm ñöôøng cong ñi qua T(x,y) laø nhoû nhaát ñeå gheùp vaøo ñöôøng cong môùi. Hay noùi caùch khaùc, ta seõ choïn nôi maø ñöôøng cong ñeán sôùm nhaát ñeå taïo thaønh ñöôøng cong môùi. Vì lyù do naøy thuaät toaùn Fast Marching coøn coù moät teân goïi khaùc laø “Dijkstra like Marching” (töïa Dijkstra6). Thuaät toaùn Fast Marching ñöôïc moâ taû nhö sau: 1. Khôûi taïo (a) Ñaùnh daáu nhaõn alive vaø ñaët thôøi gian tieáp caän Tij = 0 cho taát caû caùc ñieåm thuoäc veà ñoái töôïng, vaø ñöa vaøo taäp hôïp A. (b) Ñaùnh daáu nhaõn trial vaø ñaët thôøi gian tieáp caän Tij = 1 cho taát Fij caû caùc ñieåm laân caän A, vaø ñöa vaøo taäp hôïp Narrow Band. (c) Ñaùnh daáu nhaõn far away vaø ñaët thôøi gian tieáp caän Tij = ∞ cho taát caû caùc ñieåm coøn laïi vaø ñöa vaøo taäp hôïp Far Away. 2. Lan truyeàn (a) Baét ñaàu böôùc laëp: Ñaët minTrial = (imin, jmin) laø ñieåm trong Narrow Band coù thôøi gian tieáp caän nhoû nhaát, neáu khoâng toàn taïi thì keát thuùc thuaät toaùn. (b) Theâm ñieåm (imin, jmin) vaøo A, vaø xoùa noù trong Narrow Band (c) Kieåm tra 4 laân caän cuûa minTrial: (imin – 1, jmin), (imin, jmin – 1), (imin + 1, jmin), (imin , jmin + 1) thuoäc taäp hôïp Far Away hay 6 Dijkstra: laø thuaät toaùn tìm ñöôøng ñi ngaén nhaát töø moät ñænh ñeán caùc ñænh khaùc trong ñoà thò coù troïng soá khoâng aâm. GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  14. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 14 Narrow Band. Neáu laân caän thuoäc Far Away, xoùa noù trong Far Away vaø theâm vaøo Narrow Band. (d) Caäp nhaät laïi thôøi gian tieáp caän Tij cho caùc laân caän cuûa minTrial töø phöông trình (2.6) vôùi nghieäm lôùn nhaát. (e) Quay laïi böôùc laëp. a) b) c) d) e) f) Hình 7: Minh hoïa thuaät toaùn Fast Marching. Ta xeùt ví duï minh hoïa ñeå hieåu roõ thuaät toaùn Fast Marching. Giaû söû ñöôøng cong ban ñaàu laø ñöôøng troøn ñieåm maøu ñen trong hình a). Böôùc khôûi taïo, ñieåm naøy ñöôïc gaùn nhaõn alive, vaø caùc laân caän A,B,C vaø D xung quanh noù ñöôïc gaùn nhaõn trial. Böôùc laëp, ta choïn ñieåm mang nhaõn trial coù giaù trò thôøi ñieåm tieáp caän T(x,y) nhoû nhaát, giaû söû ta choïn ñöôïc ñieåm A. Caäp nhaät ñieåm A vaøo ñöôøng cong (ñaùnh daáu alive), caäp nhaät caùc laân caän cuûa noù vaøo Narrow Band vaø tieáp tuïc böôùc laëp (hình c). Giaû söû ñieåm trial coù giaù trò T nhoû nhaát trong 5 ñieåm trial laø D. Ta ñaùnh daáu D nhaõn alive, ñöôøng cong baây giôø ñöôïc môû roäng thaønh 3 ñieåm, vaø Narrow Band cuõng taêng kích thöôùc leân thaønh 6 ñieåm (hình d) Vaø böôùc laëp ñöôïc tieáp tuïc khi khoâng coøn ñieåm trial naøo nöõa. GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  15. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 15 Ñeán ñaây ta seõ nghó ngay ñeán caâu hoûi : taïi sao thuaät toaùn treân hoaït ñoäng vaø ñem laïi keát quaû ? Vaø caâu traû lôøi laø: ñöôøng cong luoân luoân tieán ra taïi vò trí nhoû nhaát trong Narrow Band, nhöõng ñieåm khaùc trong Narrow Band vaø trong Far Away coù thôøi gian tieáp caän nhoû hôn khoâng gaây aûnh höôûng gì ñeán ñieåm naøy. Böôùc caäp nhaät thôøi gian tieáp caän cho caùc ñieåm laân caän seõ taïo moät thôøi gian môùi luoân lôùn hôn thôøi gian tieáp caän cuûa caùc ñieåm alive, bôûi vì ta ñaõ choïn thôøi gian caäp nhaät laø nghieäm lôùn cuûa phöông trình Eikonal. Do ñoù ta coù theå lan truyeàn ñöôøng cong roäng daàn ra, choïn ñieåm trial coù thôøi gian tieáp caän nhoû nhaát vaø ñieàu chænh laïi laân caän cuûa noù, cöù tieáp tuïc nhö vaäy maø khoâng caàn phaûi quay laïi caùc ñieåm ñaõ xeùt tröôùc. Phöông phaùp Fast Marching cuõng töông töï nguyeân lyù Huygens trong vaät lyù, moãi ñieåm alive vaø ñieåm minTrial xem nhö moät nguoàn soùng vaø soùng seõ lan truyeàn sang caùc ñieåm laân caän vaø caùc ñieåm naøy trôû thaønh nguoàn soùng môùi. Chi tieát caùc böôùc trong thuaät toaùn FMLS Xaùc ñònh minTrial ÔÛ böôùc 2a) cuûa thuaät toaùn ta caàn phaûi xaùc ñònh vò trí coù thôøi gian tieáp caän nhoû nhaát trong Narrow Band. Ñeå taêng hieäu quaû hôn cho vieäc tìm kieám, ta toå chöùc Narrow Band theo caáu truùc Heap(1)goàm 3 chöùc naêng: theâm, xoùa phaàn töû nhoû nhaát, vaø caäp nhaät giaù trò. Chöùc naêng xoùa phaàn töû ñöôïc thöïc hieän trong thôøi gian tính toaùn haèng O(1), coøn theâm vaø caäp nhaät ñöôïc thöïc hieän vôùi ñoä phöùc taïp O(logN) vôùi N laø soá phaàn töû trong Heap. Nhö vaäy böôùc xaùc ñònh giaù trò nhoû nhaát trong Narrow Band töø ñoä phöùc taïp tìm kieám thoâng thöôøng O(N), ta ñaõ giaûm xuoáng coøn O(logN). Caäp nhaät thôøi gian tieáp caän ÔÛ ñaây, chuùng ta chöùng toû raèng thuaät toaùn FMLS ñöa ra moät keát quaû maø taát caû caùc ñieåm ñeàu thoûa phöông trình Eikonal rôøi raïc: (1) Heap: (coøn goïi Priority Queue) laø moät haèng ñôïi coù giaù trò cuûa phaàn töû i luoân nhoû hôn taïi giaù trò cuûa phaàn töû 2*i vaø 2*i+1, vaø do ñoù phaàn töû 0 laø phaàn töû coù giaù trò nhoû nhaát trong haèng ñôïi. GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  16. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 16 −x +x 2 − y + y 2 2 [max()max()Dij T,0 ,− min(Dij T,0) + max(max(Dij T,0),− min(Dij T,0)) ]= f ij 2 2 vôùi f ij = 1/ Fij Do tính chaát lan truyeàn theo chieàu taêng daàn cuûa thôøi ñieåm ñöôøng cong tieáp caän T(x, y), chuùng ta chæ caàn chæ ra raèng baát moät vò trí trial naøo ñöôïc chuyeån thaønh alive thì seõ khoâng coù ñieåm naøo trong caùc laân caän cuûa noù coù thôøi gian tieáp caän ñöôïc tính laïi nhoû hôn baát kyø thôøi gian tieáp caän naøo cuûa caùc ñieåm alive. Chuùng ta seõ kieåm ñònh keát quaû naøy trong khoâng gian hai chieàu, khoâng gian ba chieàu ñöôïc chöùng minh töông töï. B A ? C D Hình 8: Caäp nhaät thôøi gian tieáp caän Xeùt löôùi ñieåm treân. Chuùng ta caàn öôùc tính giaù trò môùi T taïi ñieåm taâm cuûa löôùi ñeå thay theá vaøo giaù trò ?, döïa vaøo giaù trò cuûa caùc ñieåm laân caän. Khoâng maát tính toång quaùt, ta giaû söû raèng giaù trò A taïi ñieåm traùi cuûa löôùi laø nhoû nhaát trong taát caû caùc giaù trò trial, vaø caàn chæ ra raèng khi ta tính laïi giaù trò cuûa ñieåm taâm cuûa löôùi(Trecomputed-from-A), thì noù khoâng theå nhoû hôn A. Coù taát caû boán tröôøng hôïp (1) khoâng coù vò trí naøo trong caùc laân caän B,C hoaëc D laø alive (2) moät trong caùc laân caän naøy laø alive (3) hai trong caùc laân caän naøy laø alive (4) taát caû caùc laân caän nayø laø alive. (1) A, B, C, vaø D laø trial, A nhoû nhaát GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  17. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 17 Trong tröôøng hôïp naøy, taát caû caùc laân caän quanh taâm ñeàu hoaëc laø trial hoaëc laø far away. Khi A laø giaù trò nhoû nhaát, chuùng ta chuyeån giaù trò ñoù thaønh alive vaø tính laïi giaù trò taâm. Ta chöùng minh A ≤ Trecomputed-from-A ≤ A+f. 1. Tröôøng hôïp A+f ≤ min(B, D). ⇒ Trecomputed-from-A = (A+f) (thoûa) 2. Tröôøng hôïp A+f > min(B, D) = B. (khoâng maát tính toång quaùt, giaû söû B ≤ D. Phöông trình trôû thaønh : 2 2 2 (Trecomputed-from-A – A) + ( Trecomputed-from-A – B) =f 2 2 Δ = 2 f − (TB − TA ) > 0 do f > B − A Choïn nghieäm lôùn: T + T + 2 f 2 − (T − T ) 2 T = A B B A recoputed − from− A 2 T + T + 2(T − T ) 2 − (T − T ) 2 > A B B A B A > T 2 B Nhö vaäy, ta ñaõ chöùng minh ñöôïc raèng A ≤ Trecomputed-from-A ≤ A+f. (2) B laø “alive”, A, C vaø D laø “trial”, A laø giaù trò trial nhoû nhaát Trong tröôøng hôïp naøy, A vöøa ñöôïc caäp nhaät bôûi vì noù laø giaù trò trial nhoû nhaát. Chuùng ta seõ chöùng minh raèng khi chuùng ta tính laïi Trecomputed-from-A , giaù trò môùi cuûa noù vaãn phaûi lôùn hôn A. Trong vaøi böôùc tröôùc, khi B ñöôïc chuyeån töø trial sang alive, caùc giaù trò A, C, D ñeàu laø trial, do ñoù phaûi lôùn hôn. Ñieàu naøy coù nghóa laø khi B ñöôïc chuyeån töø trial sang alive thì B ≤ Trecomputed-from-B ≤ B+f (theo tröôøng hôïp (1)), hôn nöõa khi giaù trò taâm khoâng ñöôïc choïn laø giaù trò trial nhoû nhaát, chuùng ta phaûi coù A ≤ B+f. Töø treân, ta coù theå coù ñöôïc B ≤ A ≤ Trecomputed-from-A ≤ B + f (3) C laø “alive”, A, C vaø D laø “trial”. A laø giaù trò trial nhoû nhaát. Trong tröôøng hôïp naøy, do ta ñang xeùt baøi toaùn theo chieàu taêng töø traùi sang neân A khoâng gaây aûnh höôûng ñeán ñieåm giöõa. GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  18. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 18 Vaäy ta ñaõ chöùng minh xong, khi caäp nhaät moät giaù trò T môùi thì noù seõ khoâng nhoû hôn taát caû caùc giaù trò alive vaø ñieåm minTrial, ñieàu naøy ñaûm baûo söï lan truyeàn seõ taêng daàn theo chieàu T(x,y), thôøi gian ñöôøng cong tieáp caän ñeán ñieåm (x,y). Thuaät toaùn Multi - Class Fast Marching Baây giôø ta xeùt ñeán moät bieán theå cuûa thuaät toaùn Fast Marching, thuaät toaùn Multi-Class Fast Marching [4, 5, 6, 10] ñöôïc Sifakis vaø Tziritas ñöa ra naêm 2001, nhaèm thöïc hieän phöông phaùp lan truyeàn Fast Marching treân nhieàu ñöôøng cong cuøng luùc. YÙ töôûng caûi tieán ôû ñaây laø moãi ñieåm thay vì neáu ñöôïc gaùn nhaõn trial thì noù mang theo moät danh saùch caùc ñöôøng cong maø noù tieáp caän ñeán, goïi laø TrialList, vaø thôøi gian tieáp caän baây giôø laø thôøi gian tieáp caän cuûa ñöôøng cong ñeán noù sôùm nhaát. Thuaät toaùn ñöôïc moâ taû nhö sau: Khôûi taïo thôøi gian tieáp caän T(x, y) Khôûi taïo danh saùch caùc nhaõn Trial List (x, y, ci) ∈ {alive, trial, far away} Trong khi (Narrow Band chöa roãng) { Choïn (imin, jmin) laø ñieåm coù giaù trò Tmin trong Narrow Band Ñaùnh daáu nhaõn (imin, jmin) laø alive cho ñöôøng cong ñeán noù sôùm nhaát. Theâm caùc laân caän cuûa (imin, jmin) vaøo Narrow Band Caäp nhaät thôøi gian tieáp caän cho caùc laân caän (imin, jmin) } GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  19. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 19 Moät minh hoïa cho thuaät toaùn Multi-Class Fast Marching. Töø caùc ñöôøng cong ban ñaàu, chuyeån ñoäng vôùi vaän toác haèng F = 1, thuaät toaùn chaïy ôû caùc buôùc 5%, 10%, 30%, 60% vaø 100%. Keát quaû thu ñöôïc laø löôïc ñoà Voronoi. Hình 9: Thuaät toaùn Multi-Class Fast Marching GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  20. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 20 PHAÙT HIEÄN SÖÏ THAY ÑOÅI CUÛA ñoái TöôïNG TRONG DAÕY AÛNH LIEÂN TIEÁP “Phaùt hieän vaø ñònh vò ñoái töôïng thay ñoåi trong daõy aûnh lieân tieáp” laø moät trong nhöõng vaán ñeà chuû yeáu trong phaân tích chuyeån ñoäng video, cuõng nhö nhöõng öùng duïng theo doõi ñoái töôïng di chuyeån, öôùc löôïng chuyeån ñoäng hoã trôï caùc heä thoáng an ninh, quoác phoøng. Vaán ñeà naøy cuõng ñöôïc söû duïng nhieàu trong vieäc neùn video, nhaát laø theo chuaån MPEG, hoaëc trong caùc kyõ thuaät “blue-screening”. Trong tröôøng hôïp aûnh ñöôïc chuïp töø moät camera tónh, thì cô sôû chung ñeå phaùt hieän chuyeån ñoäng laø phaân tích söï thay ñoåi maøu saéc giöõa hai frame aûnh lieân tieáp vaø töø ñoù seõ ñöa ra keát luaän veà ñoái töôïng ñang thay ñoåi giöõa hai frame aûnh naøy. Phöông phaùp ñôn giaûn nhaát laø kyõ thuaät tröø aûnh (hay xor aûnh). Neáu söï khaùc bieät giöõa hai frame aûnh lôùn hôn moät ngöôõng naøo ñoù thì ta seõ baùo ñoäng coù söï thay ñoåi giöõa chuùng. Phöông phaùp naøy ñaëc bieät toái öu veà toác ñoä nhöng cho keát quaû khoâng toát trong tröôøng hôïp aûnh bò nhieãu vaø khoâng xaùc ñònh ñöôïc ñoái töôïng chuyeån ñoäng moät caùch chính xaùc. Caùc kyõ thuaät phöùc taïp hôn laø söû duïng boä loïc Kalman, söû duïng moâ hình Markov aån cuõng coù ñöôïc keát quaû khaû quan nhöng toác ñoä khoâng ñöôïc cao laém. Tröôøng hôïp aûnh ñöôïc chuïp töø moät camera di chuyeån, vaán ñeà seõ trôû neân khoù hôn. Ta caàn phaûi xeùt ñeán vector chuyeån ñoäng cuõng nhö heä soá phoùng to thu nhoû cuûa maùy aûnh. Trong phaàn naøy chuùng em xin trình baøy moät trong nhöõng phöông phaùp phaùt hieän ñoái töôïng thay ñoåi döïa treân thuaät toaùn Fast Marching Level Set vaø Region Growing, giaûi quyeát töông ñoái hieäu quaû vaán ñeà treân trong tröôøng hôïp camera tónh. Toùm taét phöông phaùp söû duïng FM LS vaø SRG Ban ñaàu töø caùc kieåm ñònh thoáng keâ vaø nguyeân lyù hôïp lyù cöïc ñaïi ta seõ ñaùnh daáu nhaõn nhöõng pixel chaéc chaén thuoäc veà ñoái töôïng (ñaùnh daáu nhaõn ñoäng), vaø nhöõng pixel chaéc chaén thuoäc veà neàn (ñaùnh daáu nhaõn tónh). Böôùc tieáp theo, thuaät GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  21. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 21 toaùn Fast Marching Level Set ñöôïc söû duïng ñeå lan truyeàn hai taäp hôïp pixel ñaõ ñaùnh daáu nhaõn ôû treân sang nhöõng pixel chöa ñöôïc gaùn nhaõn, vaø hình thaønh ñoái töôïng ñaõ thay ñoåi giöõa hai aûnh. Do böôùc naøy chæ quan troïng hoùa veà maët toác ñoä thuaät toaùn vaø chæ söû duïng ñoä cheânh leäch cöôøng ñoä xaùm neân keát quaû seõ khoâng vöøa vaën hoaøn toaøn ñoái töôïng. Keát quaû chính xaùc seõ coù ñöôïc ôû böôùc keá tieáp. Töø ñöôøng bieân cuûa ñoái töôïng coù töø böôùc treân, ta söû duïng thuaät toaùn Fast Marching hai laàn ñeà tieán noù theo hai höôùng ñoái nghòch: vaøo trong vaø ra ngoaøi, taïo thaønh hai ñöôøng cong naèm haún beân trong vaø beân ngoaøi ñoái töôïng. Cuoái cuøng, aùp duïng thuaät toaùn taêng vuøng (SRG) vôùi vuøng ñöôïc taïo töø hai ñöôøng cong treân, ta seõ ñöôïc keát quaû nhö yù. Phaùt hieän ñoái töôïng chuyeån ñoäng Thieát laäp moâ hình thoáng keâ Ñaët d(x,y) = I(x,y,t+1) – I(x,y,t) bieåu dieãn ñoä cheânh leäch cöôøng ñoä xaùm taïi pixel (x,y), vôùi I(x,y,t) vaø I(x,y,t+1) laàn löôït laø cöôøng ñoä xaùm cuûa pixel (x,y) trong frame taïi hai thôøi ñieåm t vaø t+1. Ñaët D = {d(x,y), (x,y) ∈ [0, chieàu daøi aûnh] x [0, chieàu roäng aûnh]}. Moãi pixel ñöôïc ñaùnh daáu bôûi moät trong hai nhaõn: ñoäng (mobile) hoaëc tónh (static). Vôùi Θ(x,y) laø nhaõn cuûa pixel (x,y), theo quy öôùc thoáng keâ ta vieát: H0 : Θ(x,y) = static H1 : Θ(x,y) = mobile Ñaët pD|static(d|static) vaø pD|mobile(d|mobile) laàn löôït laø haøm maät ñoä xaùc suaát cuûa ñoä cheânh leäch cöôøng ñoä xaùm döôùi hai giaû thuyeát H0 vaø H1. Caùc haøm maät ñoä xaùc suaát naøy ñoäc laäp vôùi vò trí cuûa pixel, vaø luoân tuaân theo luaät phaân phoái Laplace hoaëc Gauss. GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  22. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 22 Ta söû duïng haøm phaân phoái Laplace(1) vôùi kyø voïng baèng 0 ñeå moâ taû söï töơng quan thoáng keâ cuûa caùc pixel ñoái vôùi hai giaû thuyeát treân. Ñeå ñôn giaûn ta söû duïng kyù hieäu 0 vaø 1 cho nhaõn tónh vaø ñoäng. Do vaäy, haøm maät ñoä xaùc suaát cuûa ñoä cheânh leäch cöôøng ñoä xaùm döôùi hai giaû thieát H0, H1 : λ − λ d(x, y) p(d(x, y) | Θ(x, y) = l) = l e l vôùi l∈ {0,1} (2.2.1a) 2 vaø haøm maät ñoä xaùc suaát toång hôïp cuûa ñoä cheânh leäch cöôøng ñoä xaùm : pD (d) = Pstatic ⋅ pD|static (d | stactic) + Pmobile ⋅ pD|mobile (d | mobile) (2.2.1b) Trong hai haøm phaân phoái treân, {Pl , λl ; l∈{static, mobile}} laø caùc tham soá chöa bieát. Ta seõ söû duïng nguyeân lyù hôïp lyù cöïc ñaïi vaø giaûi thuaät keát nhoùm Bayes ñeå öôùc löôïng chuùng (phuï luïc). Gaùn nhaõn khôûi taïo ban ñaàu Caùc nhaõn khôûi taïo ban ñaàu coù ñöôïc töø caùc kieåm ñònh thoáng keâ vôùi ñoä tin caäy cao nhaát. Kieåm ñònh ñaàu tieân seõ xaùc ñònh caùc pixel ñoäng vaø sau ñoù caùc kieåm ñònh tieáp theo seõ xaùc ñònh caùc pixel tĩnh. Thuaät toaùn Fast Marching seõ lan truyeàn tieáp tuïc vôùi caùc nhaõn ñaõ ñaùnh daáu tröôùc. Neân ñeå haïn cheá sai soá cho söï lan truyeàn naøy, caùc nhaõn ñoäng ñöôïc kieåm ñònh treân töøng pixel vaø caùc nhaõn tónh ñöôïc kieåm ñònh treân caùc khoái pixel. Ñieàu naøy giuùp caùc pixel ñoäng vaø tónh khoâng theå gaàn nhau, taïo ñieàu kieän toát cho vieäc lan truyeàn sau naøy. Ñaùnh daáu nhaõn ñoäng Kieåm ñònh ñaàu tieân xaùc ñònh caùc nhaõn ñoäng vôùi ñoä tin caäy cao nhaát. Xaùc suaát baùo ñoäng loãi ñöôïc ñaët raát nhoû, goïi laø PFA (trong phaàn caøi ñaët, PF (1) Luaät phaân phoái Laplace: laø phaân phoái cuûa ñaïi löôïng ngaãu nhieân X coù haøm maät ñoä phaân phoái: λ −λ x−θ f (x,λ,θ ) = e vôùi λ > 0, θ laø tham soá cho tröôùc 2 1 Caùc ñaëc tröng soá: Kyø voïng EX = θ, Phöông sai DX = λ2 GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  23. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 23 ñöôïc choïn baèng 1E-7). Do söû duïng phaân phoái Laplace, neân ngöôõng cheânh leäch möùc xaùm cho nhaõn ñoäng coù ñöôïc choïn nhö sau: 1 1 T1 = ln (2.2.2.1) λ0 PF ⇒ Taäp maãu caùc nhaõn ñoäng: Mobile = {(x, y) : d(x, y) > T1} Ñaùnh daáu nhaõn tónh Caùc kieåm ñònh tieáp theo ñöôïc söû duïng vôùi muïc ñích tìm ra caùc vò trí tónh vôùi ñoä tin caäy cao nhaát. Xeùt moät daõy 6 oâ kích thöôùc (2w+1)2, w = 2, ,7, vaø caùc ngöôõng töông öùng cho nhaõn tónh ñöôïc thieát laäp theo λ1. Ñaët Bw laø taäp hôïp caùc pixel ñöôïc ñaùnh daáu nhaõn tónh khi kieåm ñònh caùc oâ coù chæ soá w. w w ⎧ γ l ⎫ Bw = ⎨(x, y) : ∑∑d(x + k, y + l) < ⎬, w = 2, 7. (2.2.2.2) ⎩ k =−−wl= w λ1 ⎭ Vôùi γw laø caùc giaù trò thu ñöôïc töø thöïc nghieäm. w 2 3 4 5 6 7 γw 0.4 1.6 3.5 7.0 12.0 20.0 6 ⇒Taäp maãu caùc pixel tónh : Static = ΥBw w=2 Ví duï: Keát quaû cuûa quaù trình ñaùnh daáu nhaõn cho hai frame aûnh lieân tieáp. Trong hai böùc aûnh naøy maøu xanh bieåu thò caùc ñieåm ñaùnh daáu tĩnh, maøu vaøng bieåu thò caùc ñieåm ñaùnh daáu ñoäng vaø maøu xaùm laø caùc ñieåm chöa xaùc ñònh ñöôïc nhaõn. GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  24. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 24 Hình 10: Ñaùnh daáu caùc maãu ban ñaàu GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  25. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 25 Lan truyeàn nhaõn Thuật toaùn Fast Marching Level Set đñược aùp dụng với hai tập pixel mẫu: ñoäng vaø tĩnh tìm ñược ở phần treân. Đường bieân của mỗi taäp pixel sẽ ñược mở rộng với một vận tốc rieâng tuøy thuoäc mỗi loại nhaõn vaø ñoä cheânh lệch cöôøng ñoä xaùm. Vận tốc lan truyeàn đñược thiết lập dựa treân nguyeân lyù xaùc suất Bayes Vôùi vị trí s coù nhaõn l vaø ñộ cheânh lệch cöôøng ñoä xaùm d, vận tốc lan truyền sẽ laø: vl(s) = Pr{l(s), d(s)} Coù thể viết lại như sau: p(d(s) | l(s)) Pr{l(s)} 1 v (s) = = l p(d(s) | k(s)) Pr{k(s)} p(d(s) | k(s)) Pr{k(s)} ∑ 1+ k ∑ k≠l p(d(s) | l(s) Pr{l(s)} (2.2.3) Vì thế tốc ñoä lan truyeàn dựa treân caùc tỉ lệ hợp lyù (likelihood) vaø caùc xaùc suất tieân nghiệm (priori). Tỉ lệ hợp lyù coù thể được ñaùnh giaù döïa vaøo tính chất dữ liệu, coøn xaùc suất tieân nghiệm coù thể ước lượng treân toaøn ảnh hoặc đñơn giản hơn cho tất cả bằng nhau (P0 = P1 = ½). Trong trường hợp quyết ñònh lựa chọn giữa nhaõn ñoäng vaø nhaõn tĩnh theo phaân phối Laplace, tỉ lệ hợp lyù laø haøm exp của ñoä cheânh lệch cöôøng ñoä xaùm d(x,y). Trong caùch tổ chức theo pixel, xử lí caùc quyết ñònh naøy rất phức tạp. Hơn nữa, vật thể chuyển ñoäng khoâng theo khuoân maãu naøo caû, caùc thaønh phaàn khaùc nhau của noù di chuyển cũng khaùc nhau. Trong caùc vuøng coù cuøng cường ñoä xaùm, sự khaùc nhau của frame ảnh rất nhỏ khi ñoái tượng chuyển ñoäng. Vì vậy, taäp hôïp ñoái töôïng ñộng của frame trước neân ñöôïc sử dụng trong việc xaùc ñịnh xaùc suất tieân nghieäm trong quaù trình lan truyeàn. Theo phương trình (2.2.1a) vaø (2.2.1b) hai tốc ñoä lan truyeàn coù thể đñược viết lại như sau GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  26. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 26 1 v (x, y) = 0 Q (x, y)λ 1+ 1 1 e(λ0 −λ1 ) d ( x, y) Q0 (x, y)λ0 1 v (x, y) = 1 Q (x, y)λ 1+ 0 0 e −(λ0 −λ1 ) d ( x, y) Q1 (x, y)λ1 với tham số λ0 vaø λ1 ñaõ đñược ước lượng trước đñoù. Từ caùc phaân tích thống keâ của sự phaân phối dữ liệu hỗn hợp, chuùng ta coù sự ước lượng xaùc suất tieân nghieäm cho hai loaïi nhaõn. Ñaây chỉ laø sự ước lượng chứ khoâng phải laø coâng thức chính xaùc cuûa xaùc suất tieân nghieäm. Tuy nhieân, caùc pixel ñaõ gaùn nhaõn ban ñaàu khoâng cần thiết tuaân theo phaân phối xaùc suất như vậy, bởi vì sự nhận dạng ban ñầu dựa vaøo lượng chuyển ñộng coù theå laø biến ñổi khoâng gian hoặc thời gian. Chuùng ta ñịnh nghĩa tham số β đñể ño sự khaùc nhau của hai phaân phối xaùc suất như sau : 4(Pˆ +Pˆ ) ⎛ Pˆ P ⎞ 0 1 β = ⎜ 0 1 ⎟ ⎜ ˆ ⎟ ⎝ P1P0 ⎠ ˆ ˆ ˆ ˆ với P0 + P1 + Pu = 1. Pu laø phần trăm caùc pixel chưa ñöôïc gaùn nhaõn. Trong trường hợp ñoù β sẽ laø tỉ lệ của xaùc suất tieân nghiệm. Theâm vaøo ñoù, v1(x,y) trong frame trước cũng ñöôïc ñöa vaøo cho việc tính toaùn. Q (x, y) eθ1 − (α(x, y) +η (x, y) −η (x, y))ζ 0 = 1 0 Q1 (x, y) β α(x, y) = ln(2δ (x, y) −1) , với δ(x,y) laø khoảng caùch từ ñiểm (x,y) ñeán vuøng ñoäng trong frame trước, vaø n1(x,y), n2(x,y) laø số pixel laân cận (x,y) ñaõ ñöôïc gaùn nhaõn ñộng vaø tĩnh. Cuối cuøng, tốc đñộ loang chính xaùc của nhaõn tónh laø: 1 v (x, y) = 0 λ 1+ β 1 e(λ0 −λ1 )|d (x, y)|+θ0 −(η0 (x, y)−η1 ( x, y))ζ λ0 GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  27. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 27 vaø cuûa nhaõn ñoäng laø: 1 v (x, y) = 1 1 λ 1+ 0 e −(λ0 −λ1 )|d ( x, y)|+θ1 −(α ( x, y)−η0 (x, y)+η1 (x, y))ζ β λ1 Caùc tham số coøn laïiđñược thiết lập theo thực nghiệm: ζ = 0.1T1, θ0 = 4ζ, θ1 = 5ζ+4 Chuùng ta sử dụng thuật toaùn Fast Marching đñể mở rộng caùc ñường bieân sang những vuøng chöa ñöôïc gaùn nhaõn. Ñể coùđñược đñường bieân chính xaùc, vaø coù ñöôïc moät tieâu chuaån döøng toát ta sử dụng caùch tiếp cận Level Set kiềm chế caùc ñiểm bieân. Caùch tiếp cận naøy khoâng chuù troïng ñến söï meàm maïi cuûa ñöôøng bieân, maø chæ chuù troïng ñeán hieäu quaû tính toaùn. Vì vaäy toác ñoä lan truyeàn phuï thuoäc vaøo nhöõng ñaëc tính rieâng cuûa ñieåm aûnh, chöù khoâng phụ thuộc vaøo ñoä cong cuûa ñöôøng bieân. GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  28. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 28 Hình 11: Keát quaû quaù trình lan truyeàn nhaõn bôûi thuaät toaùn Fast Marching Ñònh vò ñoái töôïng Khôûi taïo Giai ñoaïn phaùt hieän thay ñoåi ñöôïc söû duïng ñeå khôûi taïo cho quaù trình xaùc ñònh bieân ñoái töôïng. Chuùng ta coù nhaän xeùt raèng vuøng thay ñoåi “lyù töôûng” chính laø vuøng thuoäc veà ñoái töôïng taïi hai thôøi ñieåm lieân tieáp. Chuùng ta ñaët vuøng naøy laø: C(t,t +1) = {O(i, j,t) ∪ O(i, j,t +1)} trong ñoù O(i,j,t) laø taäp caùc pixel thuoäc veà ñoái töôïng taïi thôøi ñieåm t. Töông töï ta coù : C(t −1,t) = {O(i, j,t −1) ∪ O(i, j,t)} Neân C(t −1,t) ∩ C(t,t +1) = {O(i, j,t)}∪ ({O(i, j,t −1)}∩{O(i, j,t +1)}) Qua ñoù chuùng ta thaáy raèng phaàn giao cuûa 2 vuøng thay ñoåi lieân tieáp seõ laø söï khôûi taïo toát hôn töøng vuøng trong quaù trình ñònh vò ñoái töôïng. Tuy nhieân trong moät soá tröôøng hôïp thì GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  29. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 29 {O(i, j,t)} ⊃ ({O(i, j,t −1)} ∩{O(i, j,t +1)}) Neáu ñieàu naøy xaûy ra thì : {O(i, j,t)} = C(t,t +1) ∩ C(t,t −1) Nhö vaäy chuùng ta seõ söû duïng phaàn giao naøy ñeå khôûi taïo cho quaù trình xaùc ñònh bieân cuûa ñoái töôïng. Taïo vuøng chöùa bieân Trong phaàn naøy ta seõ tìm moät vuøng ñuû lôùn ñeå chöùa bieân cuûa ñoái töôïng. Ñeå ñaït ñöôïc yeâu caàu naøy ta seõ duøng ñöôøng bieân ban ñaàu (coù ñöôïc töø phaàn tröôùc) môû roäng veà hai phía ñeå coù ñöôïc ñöôøng bieân trong naèm treân ñoái töôïng vaø ñöôøng bieân ngoaøi naèm treân neàn. Trong moïi tröôøng hôïp, ñöôøng bieân cuûa ñoái töôïng naèm giöõa 2 ñöôøng bieân naøy. Ta coù nhaän xeùt raèng khi taïo ñöôøng bieân trong thì nhöõng ñieåm treân neàn seõ tieán nhanh, coøn nhöõng ñieåm treân ñoái töôïng seõ tieán chaäm hôn ñeå coù ñöôïc keát quaû chính xaùc. Ñoái vôùi ñöôøng bieân ngoaøi thì ngöôïc laïi. Chuùng ta giaû söû raèng cöôøng ñoä aûnh treân neàn ñöôïc moâ taû baèng phaân phoái Gauss vôùi kì voïng laø ⁄μ vaø phöông sai laø σ 2 , ñoàng thôøi ñieàu kieän naøy cuõng thoaû trong cuïc boä. Khi ñoù haøm maät ñoä phaân phoái xaùc suaát cuûa thoáng keâ naøy laø −( x−μ ) 1 2 f (x) = e 2σ σ 2π Vaän toác ñeå taïo hai ñöôøng bieân ñöôïc xaùc ñònh döïa vaøo nguyeân lyù xaùc suaát tieân nghieäm vaø ñöôïc xaùc ñònh döïa vaøo söï cheânh leäch giöõa giaù trò ⁄μ vaø Ι (Ι − μ) 2 σ 2 trong ñoù Ι laø giaù trò trung bình cuûa cöôøng ñoä trong cuûa soå 3x3 vôùi ñieåm ñang xeùt laø taâm. Giaù trò cuûa thoáng keâ naøy caøng nhoû nghóa laø phuø hôïp vôùi neàn. Nhö vaäy ta coù ñöôïc vaän toác môû roäng cuûa hai ñöôøng bieân laø : 1 v = - Ñoái vôùi ñöôøng bieân trong : b − 4 ( I − μ ) σ 2 1 + cb e GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  30. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 30 - Ñoái vôùi ñöôøng bieân ngoaøi: vo = 1 − vb Pb Δ Trong ñoù haèng soá cb = . Pb , Po laàn löôït laø xaùc suaát cuûa pixel naèm treân Poσ 2Π neàn vaø treân ñoái töôïng. Chuùng ta cuõng giaû söû raèng cöôøng ñoä caùc pixel treân ñoái töôïng phaân phoái trong khoaûng Δ (töø 0 ñeán 255). μ vaø σ laø nhöõng giaù trò ñaõ ñöôïc ñeà caäp trong phaàn treân. Trong nhöõng tröôøng hôïp vuøng neàn khoâng ñoàng nhaát, vuøng chöùa bieân ñoái töôïng ñöôïc xaùc ñònh baèng vieäc thieát laäp caùc vaän toác laø haèng soá. Khi caøi ñaët chöông trình, hai vaän toác nhaän giaù trò baèng 0.5. Ñoä lôùn cuûa vuøng “khoâng chaéc chaén“ - vuøng chöùa bieân ñoái töôïng - ñöôïc xaùc ñònh baèng vieäc ñaët ngöôõng cuûa thôøi gian tieáp caän trong thuaät toaùn FMLS maø giaù trò ngöôõng naøy phuï thuoäc vaøo ñoä lôùn vaø chuyeån ñoäng cuûa ñoái töôïng. Sau giai ñoaïn naøy chuùng ta coù ñöôïc ba vuøng trong frame aûnh caàn phaân ñoaïn, cuï theå nhö sau: vuøng thuoäc veà neàn, vuøng thuoäc veà ñoái töôïng caàn tìm bieân, vuøng chöùa bieân cuûa ñoái töôïng vaø ta goïi vuøng naøy laø vuøng khoâng chaéc chaén . Hình 12: Keát quaû khi taïo vuøng chöùa bieân ñoái töôïng Vuøng chöùa bieân ñoái töôïng ñöôïc minh hoaï baèng maøu thöïc cuûa aûnh trong khi neàn vaø ñoái töôïng coù maøu xanh vaø ñoû. Loïc bieân ñoái töôïng Trong phaàn naøy chuùng ta seõ söû duïng thuaät toaùn Seeded Region Growing (SRG) ñeå xaùc ñònh bieân cuûa ñoái töôïng. GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  31. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 31 SRG laø moät trong nhöõng phöông phaùp ñöôïc söû duïng trong quaù trình phaân ñoaïn aûnh. Phöông phaùp naøy yeâu caàu chuùng ta phaûi cung caáp moät hay moät soá vuøng ñaõ coù nhaõn ban ñaàu vaø caùc vuøng naøy ñöôïc coi nhö laø taäp “maàm” cuûa giaûi thuaät. Giaûi thuaät phaùt trieån caùc taäp naøy cho tôùi khi taát caû caùc pixel cuûa frame aûnh ñöôïc xöû lyù heát. Thuaät toaùn Seeded Region Growing ban ñaàu ñöôïc giôùi thieäu bôûi Rolf Adams vaø Leanne Bischof[7] vaøo naêm 1994 döïa treân khaùi nieäm naøy. Ñaàu tieân ta seõ xaùc ñònh nhöõng thaønh phaàn noái keát vôùi vuøng “khoâng chaéc chaén” thuoäc veà neàn vaø ñoái töôïng. Treân bieân cuûa hai vuøng naøy chuùng ta seõ ñaët nhöõng ñieåm ñaïi dieän maø nhöõng ñieåm naøy seõ ñöôïc söû duïng ñeå tính vector maøu trung bình cuïc boä trong heä maøu CIE Lab. Söï khaùc bieät veà tính chaát maøu cuûa pixel öùng vieân vôùi vuøng ñaõ coù nhaõn döïa vaøo caùc vector maøu naøy vaø khoaûng caùch Euclidean. Cuï theå ta ñaët T laø taäp cuûa nhöõng pixel khoâng thuoäc veà caùc taäp maàm nhöng coù caùc laân caän cuûa noù thuoäc veà moät trong caùc taäp naøy. Theo ñònh nghóa treân thì: ⎧ nn⎫ T = ⎨x ∉ΥΥAi | N(x) Ι Ai ≠ 0⎬ ⎩ 11⎭ ta coù N(x) laø taäp caùc laân caän cuûa x. Chuùng ta xeùt 8 laân caän cuûa moãi pixel x. Taïi moãi böôùc cuûa giaûi thuaät ta laáy 1 pixel töø taäp T-pixel naøy chöa coù nhaõn- vaø ñöa vaøo moät trong nhöõng taäp Ai maø N(x) coù phaàn giao, gaùn nhaõn noù nhö nhaõn cuûa taäp naøy. Tuy nhieân thuaät toaùn naøy laïi phuï thuoäc vaøo thöù töï cuûa pixel ñöôïc laáy ra bôûi vì thöù töï caùc pixel ñöôïc laáy ra khaùc nhau seõ cho ta keát quaû khaùc nhau. Vaán ñeà naøy ñöôïc giaûi quyeát bôûi Andrew Mehnert and Paul Jackway [8] khi hoï ñöa ra caùch giaûi quyeát laø choïn phaàn töû coù ñoä cheânh leäch veà tính chaát maøu töø caùc taäp maàm laø nhoû nhaát. Sau ñoù chuùng ta caäp nhaät laïi tính chaát maøu cuûa taäp naøy ñoàng thôøi ñöa caùc laän caän cuûa noù vaøo taäp T. Thuaät toaùn keát thuùc khi taát caû caùc pixel ñaõ coù nhaõn. Ñeå xaùc ñònh ñoä cheânh leäch veà cöôøng ñoä töø 1 pixel ñeán 1 taäp hôïp ta duøng coâng thöùc : δ (x) =| I (x) − meanAi : Ai Ι N (x) ≠ 0 | Trong ñoù I(x) laø cöôøng ñoä cuûa pixel x trong frame aûnh ñang xeùt. GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  32. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 32 Neáu pixel ta ñang xeùt coù N(x) coù phaàn giao hôn moät taäp hôïp thì chuùng ta phaûi quyeát ñònh taäp naøo ñeå coù ñöôïc giaù trò cuûa δ (x) . Caùch giaûi quyeát toát nhaát laø choïn taäp thöù i thoaû :δ (x) = min{δ (i)}. Sau khi moãi pixel ñöôïc gaùn nhaõn, vector maøu töông öùng seõ ñöôïc caäp nhaät ñeå coù ñöôïc giaù trò môùi phuø hôïp vôùi vuøng maø noù ñaïi dieän. Khi giaûi thuaät keát thuùc, moãi pixel cuûa frame aûnh ñöôïc gaùn moät trong hai nhaõn: thuoäc veà neàn hay thuoäc veà ñoái töôïng. Khi thöïc hieän giaûi thuaät SRG chuùng ta caàn moät caáu truùc döõ lieäu ñeå löu tröõ caùc pixel trong quaù trình xöû lyù vaø caáu truùc naøy ñöôïc goïi laø Sequentially Sorted List (SSL). Thuaät toaùn: Böôùc 1: Ñaùnh daáu nhaõn cho taäp hôïp ban ñaàu theo töøng nhoùm cuûa chuùng. Böôùc 2: Tính vector maøu cuûa caùc taäp hôïp naøy trong moät heä maøu nhaát ñònh. Böôùc 3: Tính giaù trò δ (.,.) cuûa taát caû caùc laân caän cuûa taäp ban ñaàu vaø ñöa chuùng vaøo trong SSL. Böôùc 4: Trong khi (SSL chöa roãng) thì: Böôùc 4.1: choïn pixel ñaàu tieân Y trong SSL vaø gaùn nhaõn cho noù nhö nhaõn cuûa taäp hôïp maø noù “giaùp ranh”. Ñoàng thôøi cuõng loaïi pixel naøy ra khoûi SSL. Böôùc 4.2: caäp nhaät vector maøu cuûa taäp hôïp maø pixel Y giaùp ranh. Böôùc 4.3: kieåm tra caùc laân caän cuûa Y ñeå caäp nhaät SSL: Böôùc 4.3.1: neáu pixel chöa coù maët trong SSL thì tính giaù trò δ (.,.) cuûa caùc pixel naøy vaø insert chuùng vaøo trong SSL. Böôùc 4.3.2: neáu pixel ñaõ coù maët trong SSL thì caäp nhaät laïi giaù trò cuûa δ (.,.) . Böôùc 5: Keát thuùc. GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  33. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 33 Hình 13: Keát quaû sau khi söû duïng thuaät toaùn SRG GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  34. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 34 Keát quaû vaø höôùng phaùt trieån Thöïc hieän Moâ hình thöïc hieän: AÛnh 1 AÛnh 2 xaùm xaùm hoùa hoùa AÛnh xaùm 1 AÛnh xaùm 2 Cheânh leäch möùc xaùm Phaân lôùp ML Fast Marching Ñoái töôïng thay ñoåi Trích vuøng chöùa bieân Seeded Region Growing Keát quaû chính xaùc Hình 14: Moâ hình thöïc hieän Chöông trình minh hoïa ñöôïc caøi ñaët baèng ngoân ngöõ Java döïa treân caùc lôùp chính vôùi caùc chöùc naêng nhö sau: - VideoSegmentation.java: thöïc hieän toaøn boä thuaät toaùn. - ChangDetect.java: thöïc hieän böôùc phaùt hieän caùc ñoái töôïng. - Localization.java: thöïc hieän böôùc ñònh vò ñoái töôïng. - MLClassify.java: phaân lôùp Bayes vaø öôùc löôïng Maximum Likelihood. GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  35. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 35 - FastMarching.java: thuaät toaùn Multi-Class Fast Marching. - CreateUncertaintyZone.java: taïo vuøng chöùa bieân ñoái töôïng söû duïng 2 laàn thuaät toaùn Fast Marching. - SeedRegionGrowing.java: phaùt hieän bieân ñoái töôïng söû duïng thuaät toaùn taêng vuøng. Keát quaû thöïc nghieäm Chöông trình ñöôïc thöïc hieän treân daõy aûnh 320*240 24 bit maøu, vaø coù ñöôïc nhöõng keát quaû nhö sau: Caáu truùc Soá ñoái töôïng Möùc ñoä Thôøi gian Thôøi gian file aûnh chuyeån ñoäng chính trung bình cao nhaát xaùc Hall Monitor JPG 2 98% 1.5 giaây 2.0 giaây Höôùng phaùt trieån Ñeà taøi “Phaùt hieän vaø ñònh vò ñoái töôïng trong daõy aûnh lieân tieáp baèng söû duïng thuaät toaùn Fast Marching vaø Seed Region Growing” laø moät ñeà taøi môû. Neáu coù ñöôïc cô hoäi tieáp tuïc thöïc hieän, chuùng em hy voïng seõ môû roäng vaán ñeà sang daõy aûnh ñöôïc chuïp töø moät camera di ñoäng hoaëc cao hôn laø moät ñoaïn film baát kyø. Ñeà taøi ñöôïc öùng duïng trong vieäc neùn video theo daïng MPEG, heä thoáng theo doõi töø xa, hoaëc keát hôïp vôùi caùc phöông phaùp nhaän daïng ñeà thaønh heä thoáng phoøng choáng troäm GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  36. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 36 taøi lieäu tham khaûo [1] R.Duda, P.Hart. Pattern Classification and Scence Analysis. New York: Willey- Interscience, 1973. [2] G.McLachlan, D. Peel vaø W. Whiten. Maximum likelihood clustering via normal mixture model. Signal Processing: Image Communication, 8:105-111, 1996. [3] J.Sethian. Level Set Methods and Fast Marching Methods. Cambridge University Press, 1999. [4] E.Sifakis, G.Tziritas. Fast marching to moving object location, in: Proceed-ings of the Second International Conference on Scale-Space Theories in Computer Vision, Corfou, Greece, 1999. [5] E.Sifakis, I.Grinias vaø G.Tziritas. Video segmentation using Fast Marching and Region Growing algorithms. EURASIP Journal on Applied Signal Processing, pages 379-388, April 2002. [6] E.Sifakis, G.Tziritas. Moving object localisation using a Fast Marching algorithms. Signal Processing: Image Communication, 16:963 – 976, [7] R.Adams, L.Bischof, Seeded region growing, IEEE Trans. on PAMI, Vol. 16, No. 6, June 1994, pp. 641 –647 [8] A.Mehnert, P.Jackway, An improved seeded region growing algorithm, Pattern Recognition Letters, Vol. 18, 1997, pp. 1065-1071 [9] E. Rouy, A. Tourin, A Viscosity Solutions Approach to Shape From Shad-ing, SIAM J.Num, Anal, 29, 3.pp.867-884, 1992. [10] E.Sifakis, C.Garcia, vaø G.Tziritas, Bayesian Level Set for Image Segment- ation. J.of Visual Communication and Image Representation, 13:44-64, March/June 2002 [11] Löông Maïnh Baù - Nguyeãn Thanh Thuyû: Nhaäp moân Xöû Lyù Aûnh Soá - Nhaø Xuaát Baûn Khoa Hoïc vaø Kyõ Thuaät 1999. GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  37. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 37 [12] R.Gonzalez, E.Woods: Digital Image Processing, Addison Wesley Publish-ing Company, 1997 [13] J.Sethian. Fast MarchingMethods. SIAM Review, 41:199-235, 1999. [14] J.Sethian. A Fast Marching Level Set method for monotonically advancing fronts. Proc. Nat. Acad. Sci, 93:1591 – 1595, 1996. [15] J.Sethian. Theory, algorithms, and application of level set methods for pro- pagation interfaces. Acta Numerica, pages 309-395, 1996. [16] Vaø moät soá website: color/ GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  38. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 38 phuï luïc Öôùc löôïng tham soá baèng phöông phaùp hôïp lyù cöïc ñaïi Giaû söû ñaùm ñoâng coù moät hoaëc nhieàu caùc ñaëc tröng chöa bieát (chaúng haïn θ). Ta caên cöù vaøo maãu quan saùt ñöôïc maø öôùc löôïng moät giaù trò hôïp lyù cho ñaëc tröng ˆ naøy (goïi laøθ ). Giaû söû ta tieán haønh n maãu quan saùt ñoäc laäp (X1, , Xn) ñöôïc keát quaû laø (x1, , xn). Ta xeùt haøm n L(θ , x1 , , xn ) = ∏ f (xk ,θ ) k=1 laø xaùc suaát ñeå ta nhaän ñöôïc maãu cuï theå ñang xeùt vaø goïi laø haøm hôïp lyù, trong ñoù f(x, θ) laø haøm maät ñoä cuûa X vôùi tham soá θ. ˆ Ta seõ ñi tìm öôùc löôïng cuûa θ laø θ sao cho haøm hôïp lyù L(θ, x1, , xn) ñaït giaù trò cöïc ñaïi, nghóa laø: ˆ θ = arg max L(θ , x1 , , xn ) θ Nhö vaäy öôùc löôïng hôïp lyù nhaát cuûa θ laø giaù trò laøm cho xaùc suaát nhaän ñöôïc maãu ñang xeùt laø lôùn nhaát. ÖÙng duïng trong ñeà taøi: Öôùc löôïng giaù trò λ trong phaân phoái Laplace kyø voïng 0 (söû duïng ôû phaàn 3.1) λ f (x ,λ) = e −λ x i 2 n n n −λ ∑ xi ⎛ λ ⎞ i=1 L(λ, x1 , , xn ) = ∏ f (xi ,λ) = ⎜ ⎟ e (*) i=1 ⎝ 2 ⎠ Vì haøm ln(x) laø haøm ñoàng bieán, neân ta xeùt ln L(λ, x1 , , xn ) thay vì xeùt haøm L(λ, x1 , , xn ) . ⎛ λ ⎞ n ln L(λ, x1 , , xn ) = nln⎜ ⎟ − λ ∑ xi ⎝ 2 ⎠ i=1 GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  39. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 39 Giaù trò öôùc löôïng λˆ laø giaù trò laøm (*) ñaït cöïc ñaïi, neân seõ laø nghieäm cuûa phöông trình: ∂ ln L(λ, x , , x ) 1 n = 0 ∂λ 1 n ⇔ n − ∑ xi = 0 λˆ i=1 n ⇔ λˆ = n ∑ xi i=1 GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  40. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 40 Giaûi thuaät phaân lôùp baèng phöông phaùp xaùc suaát Phaân lôùp laø moät trong nhöõng giai ñoaïn môû ñaàu vaø quan troïng trong nhieàu laõnh vöïc nhaän daïng, xöû lyù aûnh. Khoaûng caùch luoân laø coâng cuï thöôøng duøng ñeå phaân lôùp, moät phaàn töû ñöôïc xeáp vaøo lôùp maø noù coù ñoä ño khoaûng caùch ñeán lôùp ñoù nhoû nhaát. ÔÛ ñaây, ta xeùt moät phöông “töï nhieân” hôn döïa vaøo xaùc suaát Bayes vaø phöông phaùp hôïp lyù cöïc ñaïi. Giaû söû taäp hôïp X caàn ñöôïc phaân thaønh k lôùp. Xaùc suaát ñeà phaàn töû x ñöôïc xeáp vaøo lôùp i laø P(x | i) . Vaø moät caùch raát töï nhieân ta choïn nhoùm caàn xeáp cho x laø nhoùm ix sao cho xaùc suaát x rôi vaøo nhoùm ix laø cao nhaát. Thuaät toaùn coù theå ñöôïc moâ taû nhö sau: Böôùc khôûi taïo: - Phaân X ngaãu nhieân thaønh k lôùp. - Tính xaùc suaát ñeå phaàn töû x rôi vaøo lôùp i: P(x|i) Böôùc laëp: - Vôùi moãi phaàn töû x ta choïn lôùp ix coù P(x|xi) cao nhaát - Tính laïi xaùc suaát - Tieáp tuïc thöïc hieän cho ñeán khi khoâng coøn söï thay ñoåi naøo. ÖÙng duïng trong ñeà taøi: Taïi böôùc öôùc löôïng caùc tham soá (phaàn 3.1) ta chæ caàn phaân taäp hôïp caùc cheânh leäch möùc xaùm thaønh 2 lôùp : “ñoäng” vaø “tónh”. Ta caûi tieán thuaät toaùn treân ñeå thôøi gian phaân lôùp ñöôïc nhanh hôn. Ban ñaàu saép xeáp caùc cheânh leäch möùc xaùm |d(n)| taêng daàn vaø choïn moät ngöôõng (no, |do|) laø ranh giôùi cuûa hai lôùp. Böôùc tieáp theo ta vieát haøm phaân phoái xaùc suaát bieåu dieãn khaû naêng cuûa moät ñieåm thuoäc veà vuøng “ñoäng” hay “tónh”, tuaân theo luaät phaân phoái Laplace vôùi caùc tham soá ñöôïc öôùc löôïng ôû treân. GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  41. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 41 |d(n)| |d0| tónh ñoäng no n Hình 15: Phaân lôùp ñoäng vaø tónh n n0 max | d(i) | ∑| d(i) | λ ∑ l −λl |d| i=0 i=n0 +1 f (d,label = l) = e λ0 = , λ1 = 2 n0 nmax − n0 −1 Tieáp ñoù trong böôùc laëp thay vì phaûi caäp nhaät toaøn boä, ta chæ caàn dòch chuyeån no qua phaûi hoaëc qua traùi tuøy theo noù ñöôïc phaân phoái vaøo vuøng naøo. GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  42. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 42 Hình 16: Keát quaû phaân lôùp baèng phöông phaùp xaùc suaát GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  43. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 43 Heä maøu CieLab Heä maøu Cie Lab bieåu dieãn maøu thoâng qua 3 giaù trò L, a, b ñöôïc CIE giôùi thieäu vaøo naêm 1976. Ta coù theå bieåu dieãn heä maøu naøy baèng heä truïc sau: Hình 17: Heä maøu CIE Lab Trong ñoù truïc ñöùng L* bieåu dieãn ñoä saùng cuûa maøu, mang giaù trò töø 0 (ñen) ñeán 100 (traéng). Hai truïc coøn laïi coù caû giaù trò aâm vaø döông(trong khoaûng töø -120 ñeán +120). Treân truïc a, giaù trò döông treân chæ saéc ñoä ñoû, giaù trò aâm chæ saéc ñoä xanh luïc. Treân truïc b, giaù trò döông chæ saéc ñoä vaøng, giaù trò aâm chæ saéc ñoä xanh döông. Coâng thöùc chuyeån ñoåi töø CIE Lab Tröôùc tieân, chuyeån töø RGB sang CIE XYZ XYZ cuûa maøu traéng (255, 255, 255) X0 = 0.607 * 255 + 0.174 * 255 + 0.200 * 255 Y0 = 0.299 * 255 + 0.587 * 255 + 0.114 * 255 Z0 = 0.000 * 255 + 0.066 * 255 + 1.116 * 255 XYZ cuûa maøu caàn chuyeån (R, G, B) X = 0.607 * R + 0.174 * G + 0.200 * B Y = 0.299 * R + 0.587 * G + 0.114 * B Z = 0.000 * R + 0.066 * G +1.116 * B Chuaån hoùa XYZ GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi
  44. Tieåu luaän: Phaùt hieän vaø ñònh vò söï thay ñoåi cuûa ñoái töôïng trong daõy aûnh lieân tieáp Trang 44 X = X / X0 Y = Y / Y0 Z = Z / Z0 1 ⎪⎧116.0* Y 3 −16 Y > 0.008856 L = ⎨ ⎩⎪903.3* Y Y ≤ 0.008856 a = 500.0*(fX-fY) b = 200.0*(fY-fZ) vôùi 1 ⎧ 3 ⎪X X > 0.008856 fX = ⎨ 16 ⎪7.787*X + X ≤ 0.008856 ⎩ 116 1 ⎧ 3 ⎪Y Y > 0.008856 fY = ⎨ 16 ⎪7.787*Y + Y ≤ 0.008856 ⎩ 116 1 ⎧ 3 ⎪Z Z > 0.008856 fZ = ⎨ 16 ⎪7.787*Z+ Z ≤ 0.008856 ⎩ 116 Ta nhaän ñöôïc caùc giaù trò cuûa L, a, b trong heä maøu CieLab. GVHD: ThS Phaïm Theá Baûo SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi