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
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
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
2
2
2
2 max
D φ,0
)
+ min
D φ,0
)
)
n+1
ij
−x
ij
+x
ij
− y
ij
+ y
ij
φ
=φinj − Δt
(
max
(
D φ,0
)
+ min
D φ
)
(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
ij
−x
ij
D φ =
φi+1, j −φi, j
/
Δx
)
, D φ =
φi, j −φi−1, j
/
/
Δx
)
)
+ y
− y
D φ =
φi, j+1 − φi, j
/
Δy
)
, D φ =
φi, j − φi, j−1
Δy
ij
ij
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
Phöông phaùp Fast Marching
Trang 11
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].
max(D−xT,0)2 + min(D+ xT,0)2 + max(D− yT,0)2 + min(D+ yT,0)2
]
=
1
[
F 2
ij
ij
ij
ij
hoaëc coù theå vieát goïn hôn:
2
2
−x
ij
+x
ij
−y
ij
+ y
ij
1
max
(
max(D T,0),−min(D T,0)
)
+ max
max(D T,0),−min(D T,0
)
=
(1.3
F 2
.2)
2
n
⎛
⎞
∂u
∂xi
(1) phöông trình Eikonal:
= 1
⎜
⎜
⎟
⎟
∑
i=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 13
Tij −Ti−1, j
xi − xi−1
Ti+1, j −Ti, j
xi+1 − xi
Tij −Ti, j−1
y j − y j−1
Ti, j+1 −Tij
y j+1 − y j
−x
ij
+x
ij
− y
ij
+ y
ij
với D T =
;D T =
;D T =
;D T =
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.
1
(b) Ñaùnh daáu nhaõn trial vaø ñaët thôøi gian tieáp caän Tij =
cho taát
F
ij
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
2
2
−x
ij
+x
ij
−y
ij
+ y
ij
2
max
(max
(
D T,0
),−min
D T,0)) + max
max
D T,0
),−min
D T,0))
= fij
2
vôùi fij = 1/ Fij2
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 :
(Trecomputed-from-A – A)2 + ( Trecomputed-from-A – B)2=f2
2
Δ = 2 f − (TB −TA )2 > 0 do f > B − A
Choïn nghieäm lôùn:
TA + TB + 2 f − (TB −TA )2
2
Trecoputed− from−A
=
2
TA + TB + 2(TB −TA )2 − (TB −TA )2
>
> TB
2
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ø ñ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
)
}
Digitally signed by Phạm Thế
Bảo
DN: cn=Phạm Thế Bảo, c=VN,
o=Khoa Tóan- Tin học trường
Đại học khoa học Tp.HCM,
Vietnam, ou=NCLAB,
Phạm
Thế
Bảo
edu.vn
Reason: I am the author of this
document
Date: 2006.08.20 10:11:18
+07'00'
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 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
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
Tải về để xem bản đầy đủ
44 trang
19680
Free
Bạn đang xem 20 trang mẫu của tài liệu "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ải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- luan_van_phat_hien_va_dinh_vi_su_thay_doi_cua_doi_tuong_tron.pdf
