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 - 9911191 Hoà Quang Thaùi

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

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.

lôøi caûm ô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

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.

Compotech).

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

Nhoùm thöïc hieän

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öû

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

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.

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.

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

TP Hoà Chí Minh, thaùng 7 naêm 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 5

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

Nhoùm thöïc hieän

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.

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

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)

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

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

φ(x(t), t) = 0. (1.2.1a)

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)

ñöôøng möùc goác

y

γ(0) x x

z = φ(x,y,t)

ñöôøng möùc goác

y

γ(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ù:

(1.2.1b) φt + ∇φ(x(t), t). x’(t) = 0

η

=

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 :

(1.2.1c) φt + F|∇φ | = 0

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

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

cong ñôn, vaø noù coù theå bò taùch ra hay gheùp laïi khi tieán trieån.

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öø

=n phöông trình Level Set φ. Vectô phaùp tuyeá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

2

2

2

1 +

t

max

0,

min

max

0,

min

0,

=

Δ−

x φ

+

y φ

+

y φ

( D

)

( D

) x φ

( D

)

( D

n φ ij

n φ ij

− ij

+ ij

− ij

+ ij

nhaát laø: [15]

(

) 2/12 )

(1.2.2)

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

Trong ñoù F = 1

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

D

−

=

)x

+ D ij

j

− ij

j

,1

D

D

−

−

=

,

) ( / Δ ) ( )y / Δ

+ ij

( x φφ = ,1 φ − i j i , + ( y φφ = i ,

φ i ,

j

j

− ij

( x , φφφ i i j − ( y , φφφ i i j ,

j

1 +

) ( )x / Δ ) ( )y /1 Δ −

,

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á.

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

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.

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.

yxFF

,(

yx ,(

)

yxF ,(

yx ,(

)

=

0) >

∀

0) <

∀

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

(hoaëc ). 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

,

0

φ

φ =∇

noùng. Phöông trình Level Set :

)

( zyxFt , +

(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

F=1

chieàu ta coù

dT dx

(1.3.1b)

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ø

∇ FT

1=

phöông trình (1.3.1b) trôû thaønh

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

(1.3.1c)

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

2

2

2

2

1

)0,

min(

)0,

max(

)0,

min(

)0,

+

+

+

=

2

[ max(

]

x − TD ij

x + TD ij

y − TD ij

y + TD ij

F

vò cuûa phöông trình [9].

2

2

1

max

),0,

min(

)0,

max

),0,

min(

0,

−

+

−

=

(1.3

2

( max(

)

( max(

)

x − TD ij

x + TD ij

y − TD ij

y + TD ij

hoaëc coù theå vieát goïn hôn:

]

[

F

.2)

2

n

1

(1) phöông trình Eikonal: ∑

i

1 =

u ∂ ix ∂

⎞ =⎟⎟ ⎠

⎛ ⎜⎜ ⎝

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

j

,1

j

,1 −

1 −

1 +

với

x − TD ij

x + TD ij

y − TD ij

y + TD ij

, ji x

, ji y

, ji y

i

i

i

i

j

j

j

j

1 −

1 +

1 −

1 +

T T T − − − − T ij ; ; ; = = = = T ij x T i x T i + x T ij y y − − − −

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û

1

caùc ñieåm thuoäc veà ñoái töôïng, vaø ñöa vaøo taäp hôïp A.

ijF

cho taát (b) Ñaùnh daáu nhaõn trial vaø ñaët thôøi gian tieáp caän Tij =

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

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

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.

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

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

ñieåm trial naøo nöõa.

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:

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

(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.

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

max

min

0,

max

min

0,

f

−

+

−

=

( max

) ,0,

) )

( max

) ,0,

) )

( x − TD ij

( x + TD ij

( y − TD ij

( y + TD ij

2 ij

[

]

/1

2 f = ij

2 F ij

vôùi

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.

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

(1) A, B, C, vaø D laø trial, A nhoû nhaát

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

f

( T

T

)

0

do

f

=Δ

−

−

>

>

AB −

B

A

(Trecomputed-from-A – A)2 + ( Trecomputed-from-A – B)2=f2

2

2

T

T

f

T

2

T (

)

+

+

−

−

A

B

B

A

T

recoputed

from

−

=− A

2

2

2

T

T

(2

T

T

)

( T

T

)

+

+

−

−

−

A

B

B

A

B

A

T

>

>

B

2

Choïn nghieäm lôùn:

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

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

sang neân A khoâng gaây aûnh höôûng ñeán ñieåm giöõa.

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

}

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ø

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

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

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

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

hoaëc Gauss.

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û

)

,( yxdl

|)

)

)

,(( yxdp

,( yx

l

Θ

=

=

thieát H0, H1 :

λ−λ el 2

vôùi l∈ {0,1} (2.2.1a)

p

d )(

P

p

(

d

|

stactic

)

p

(

d

|

mobile

)

=

⋅

+

⋅

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 :

D

static

D

|

static

P 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

x

,( xf

e

, ) θλ

=

(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:

θλλ − − 2

Caùc ñaëc tröng soá: Kyø voïng EX = θ, Phöông sai DX =

vôùi λ > 0, θ laø tham soá cho tröôùc

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

1 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 23

ñöôïc choïn baèng 1E-7). Do söû duïng phaân phoái Laplace, neân ngöôõng cheânh

ln

=

leäch möùc xaùm cho nhaõn ñoäng coù ñöôïc choïn nhö sau:

T 1

1 λ

0

1 FP

Mobile

:)

yxd ,(

)

=

>

⇒ Taäp maãu caùc nhaõn ñoäng:

{ yx ,(

}1 T

(2.2.2.1)

Ñ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

w

w

B

:)

xd (

yk ,

l

)

w

.7,...2

=

+

+

<

=

caùc oâ coù chæ soá w.

w

∑ ∑

k

l w

w

−=

−=

γ l λ 1

⎧ yx ,( ⎨ ⎩

⎫ , ⎬ ⎭

(2.2.2.2)

Vôùi γw laø caùc giaù trò thu ñöôïc töø thöïc nghieäm.

w 2 3 4 5 6 7

γw

6

Static

=

⇒Taäp maãu caùc pixel tónh :

wB

Υ

w

2

=

0.4 1.6 3.5 7.0 12.0 20.0

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

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

ñònh ñöôïc nhaõn.

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

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)}

=

=

sv )( l

sdp sl (|)(( )) sdp sk |)(( (

Pr ))

{l(s)} Pr

{k(s)}

∑

1

+

k

∑

1 sk |)(( ( )) sdp sdp sl )(|)((

Pr Pr

{k(s)} {l(s)}

lk ≠

Coù thể viết lại như sau:

(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

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

viết lại như sau

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

)

=

,( yxv 0

)

yxd ,(

)

1

1

+

,( yxQ ,( yxQ

0

1 ) λ − ( λλ 1 e 1 0 ) λ 0

)

yxd ,(

)

−

0

( − λλ 1 0

1

) = ,( yxv 1 1 e + ,( yxQ ,( yxQ 1 ) λ 0 ) λ 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

)ˆ ˆ(4 PP + 1 0

=β

ˆ PP 10 ˆ PP 01

⎛ ⎜ ⎜ ⎝

⎞ ⎟ ⎟ ⎠

1

+

=

tham số β đñể ño sự khaùc nhau của hai phaân phối xaùc suất như sau :

ˆ P 0

ˆ ˆ uPP + 1

uPˆ laø phần trăm caùc pixel chưa ñöôïc gaùn nhaõn. Trong trường

với .

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

1

yx ,(

)

)

yx ,(

))

+

−

αθ e ( −

ζ

0

η 0

=

yxQ ,( ) ,( yxQ )

yx ,( η 1 β

1

yx ,(

)

yx

α

=

,(2ln( δ

)1) −

trước cũng ñöôïc ñöa vaøo cho việc tính toaùn.

, 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.

1

)

=

yxv ,( 0

)|

,( yxd

)|

,( yx

)

,( yx

))

ζ

( − λλ 0 1

( + − ηθ 0

0

− η 1

1

e

+

β

λ 1 λ 0

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

Cuối cuøng, tốc đñộ loang chính xaùc của nhaõn tónh laø:

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ø:

=

)|

,( yxd

)|

,( yx

)

,( yx

)

,( yx

))

ζ

−

( − λλ 0 1

( −+ αθ 1

− η 0

+ η 1

+

λ 0 λ 1

1 ) ,( yxv 1 1 e 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

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

ñ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.

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ø

ttC ,(

)1

iO ,({

tj ),

iO ,(

tj ,

)}1

+

=

∪

+

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ø:

tC (

t ),1

iO ,({

tj ,

iO ,(

tj )},

−

=

)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.

tC (

t ),1

ttC ,(

)1

iO ,({

tj )},

({

iO ,(

tj ,

iO ,({

tj ,

)})1

−

∩

+

=

∪

)}1 ∩−

+

Töông töï ta coù :

Neân

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á

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

tröôøng hôïp thì

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

iO ,({

tj )},

({

iO ,(

tj ,

iO ,({

tj ,

)})1

⊃

)}1 ∩−

+

iO ,({

tj )},

ttC ,(

ttC ,(

)1

=

)1 ∩+

−

Neáu ñieàu naøy xaûy ra thì :

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.

2σ , ñoàng thôøi ñieàu kieän naøy cuõng thoaû

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ø

) μ

1

( x −− 22 σ

e

xf )(

=

2 πσ

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ø

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.

v

=

b

- Ñoái vôùi ñöôøng bieân trong :

(4

I

)

1 −

μ− 2

σ

1

+

ec b

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

Nhö vaäy ta coù ñöôïc vaän toác môû roäng cuûa hai ñöôøng bieân laø :

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

v

v

−= 1

o

b

- Ñoái vôùi ñöôøng bieân ngoaøi:

=

bP ,

oP laàn löôït laø xaùc suaát cuûa pixel naèm treân

b

Π

c . Trong ñoù haèng soá P Δ b 2σo P

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

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

(SRG) ñeå xaùc ñònh bieân cuûa ñoái töôïng.

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

n

n

T

| xNA )(

0

≠

i

A i

Υ

ΥΙ

1

1

⎫ ⎬ ⎭

⎧ x ∉= ⎨ ⎩

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ì:

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 )(

|

xI )(

meanAi

:

Ai

xN )(

|0

δ

=

−

Ι

≠

:

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

Trong ñoù I(x) laø cöôøng ñoä cuûa pixel x trong frame aûnh ñang xeùt.

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

)(xδ . Caùch giaûi quyeát toát nhaát laø

min{

i )}(

)( x δ =

δ

phaûi quyeát ñònh taäp naøo ñeå coù ñöôïc giaù trò cuûa

. choïn taäp thöù i thoaû :

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.

(.,.)δ cuûa taát caû caùc laân caän cuûa taäp ban ñaàu vaø ñöa

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ò

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:

(.,.)δ cuûa caùc pixel naøy vaø insert chuùng vaøo trong SSL.

Böôùc 4.3.1: neáu pixel chöa coù maët trong SSL thì tính giaù trò

(.,.)δ .

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

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

Böôùc 5: Keát thuùc.

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

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

Hình 13: Keát quaû sau khi söû duïng thuaät toaùn SRG

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

AÛnh 1

AÛnh 2

xaùm hoùa

xaùm hoùa

AÛnh xaùm 2

AÛnh xaùm 1

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

Moâ hình thöïc hieän:

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

- 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

chính vôùi caùc chöùc naêng nhö sau:

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

- SeedRegionGrowing.java: phaùt hieän bieân ñoái töôïng söû duïng thuaät toaùn

laàn thuaät toaùn Fast Marching.

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

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

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…

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

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

Baûn Khoa Hoïc vaø Kyõ Thuaät 1999.

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:

http://www.adobe.com/support/techguides/ color/

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

http://www.iva.cs.tut.fi/COST211

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).

n

L

,..,

x

)

( xf

,( θ

=

) , θ

x 1

n

k

∏

k

1 =

Ta xeùt haøm

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ù

arg

,..,

)

ˆ θ

=

L θ ,(

x 1

nx

max θ

trò cöïc ñaïi, nghóa laø:

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öû

x

( xf

,

duïng ôû phaàn 3.1)

) λ

i

λλ − e 2

n

x

n

i

− ∑

i

1

=

L

x

,..,

)

xf (

,

=

=

,( λ

) λ

=

n

i

x 1

∏

i

1 =

n λλ ⎞ e ⎟ 2 ⎠

⎛ ⎜ ⎝

(*)

ln

,..,

)nx

( , x 1λ

,..,

)

,( L λ

L thay vì xeùt haøm Vì haøm ln(x) laø haøm ñoàng bieán, neân ta xeùt

nx

n

. x 1

ln

,..,

)

ln

,( λ

λ

n

i

∑

i

1 =

λ ⎞ −⎟ 2 ⎠

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

L x n x = x 1 ⎛ ⎜ ⎝

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

,..,

)

nx

0

,( x λ 1 λ ∂

n

L ∂ =

0

ix

i

1 =

1 ˆ λ

n = ⇔ − ∑

n

ix

∑

i

1 =

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

n ˆλ = ⇔

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

ixP ( )| xeáp vaøo lôùp i laø . 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

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

luaät phaân phoái Laplace vôùi caùc tham soá ñöôïc öôùc löôïng ôû treân.

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

n

no

Hình 15: Phaân lôùp ñoäng vaø tónh

n

max

n

0

|

d

|

0

label

l

df ,(

)

=

=

∑ niλ =

∑ i ==λ

id |)( | id |)(

1

0

λλ − l le 2

max

0

0

, n n 1 | 1 += 0 − − n

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

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

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.

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

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

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

Chuaån hoùa XYZ

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

1

3

Z = Z / Z0

16

a = 500.0*(fX-fY)

b = 200.0*(fY-fZ)

− L = Y Y > ≤ . 008856 0 . 008856 0 Y*. 0 Y*. 3 ⎧ ⎪ 116 ⎨ ⎪⎩ 903

1

3

vôùi

1

3

= fX . > 0X 008856 . ≤ 0X 008856 * + X ⎧ X ⎪ ⎨ . 7 787 ⎪ ⎩ 16 116

3

=

fZ

> ≤

Z Z

0.008856 0.008856

+

Z*

= fY . > 0Y 008856 . ≤ 0Y 008856 * + Y 16 116

16 116

⎧ Y ⎪ ⎨ . 7 787 ⎪ ⎩ 1 ⎧ Z ⎪ ⎨ 7.787 ⎪ ⎩

GVHD: ThS Phaïm Theá Baûo

SVTH: Huyønh Leâ Taán Taøi, Hoà Quang Thaùi

Ta nhaän ñöôïc caùc giaù trò cuûa L, a, b trong heä maøu CieLab.