Luận văn Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp

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 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 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 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 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. Moät tröôøng hôïp khaùc cuûa baøi toaùn vôùi 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 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 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 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 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 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 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 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 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 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 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 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 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ø ñ