Xem mẫu
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
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
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
nguon tai.lieu . vn
Ñ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
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
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