CCAAPP66441111 CCoommppuutteerr VViissiioonn SSyysstteemmss LLeeccttuurree 1144 AAllppeerr YYiillmmaazz OOffffiiccee:: CCSSBB 225500 EEmmaaiill:: yyiillmmaazz@@ccss..uuccff..eedduu WWeebb:: hhttttpp::////wwwwww..ccss..uuccff..eedduu//ccoouurrsseess//ccaapp66441111//ccaapp66441111//sspprriinngg22000066 PPaappeerr PPrreesseennttaattiioonnss (cid:132)(cid:132) VVeeeennmmaann,, CC..,, RReeiinnddeerrss,, MM..,, aanndd BBaacckkeerr,, EE.. 22000011.. RReessoollvviinngg mmoottiioonn ccoorrrreessppoonnddeennccee ffoorr ddeennsseellyy mmoovviinngg ppooiinnttss.. PPAAMMII 2233,, 11,, 5544––7722.. (cid:132)(cid:132) SShhii,, JJ.. aanndd TToommaassii,, CC.. 11999944.. GGoooodd ffeeaattuurreess ttoo ttrraacckk.. IInn CCVVPPRR.. 559933––660000.. (cid:132)(cid:132) PPaarraaggiiooss,, NN.. aanndd DDeerriicchhee,, RR.. 22000022.. GGeeooddeessiicc aaccttiivvee rreeggiioonnss aanndd lleevveell sseett mmeetthhooddss ffoorr ssuuppeerrvviisseedd tteexxttuurree sseeggmmeennttaattiioonn.. IIJJCCVV 4466,, 33,, 222233––224477.. (cid:132)(cid:132) RR.. VViiddaall,, YY.. MMaa aanndd SS.. SSaassttrryy,, 22000033,, GGeenneerraalliizzeedd PPrriinncciippaall CCoommppoonneenntt AAnnaallyyssiiss ((GGPPCCAA)).. CCVVPPRR,, 662211----662288 (cid:132)(cid:132) KKeennttaarrooTTooyyaammaa aanndd AAnnddrreeww BBllaakkee 22000011.. PPrroobbaabbiilliissttiicc TTrraacckkiinngg iinn aa MMeettrriicc SSppaaccee.. IICCCCVV ((MMaarrrr PPrriizzee)) 1 11.. FFuunnccttiioonnaall ( ) ( ) E ∂Γ(s) = ∫∫ h x(s), y(s) dxdy R h(x(s),y(s))=∫m ∫m logP (I(x+ f(s),y+g(s)))1∂Γdxdy R R −m −m R={object,background} 22.. GGrreeeenn’’ss TThheeoorreemm FFoorr aa ppllaannaarr rreeggiioonn RR==oobbjjeecctt ∪∪bbaacckkggrroouunndd (cid:132)(cid:132) ((PP((xx,,yy)),,QQ((xx,,yy))))iiss aannyy vveeccttoorr ffiieelldd wwiitthh ccoonnttiinnuuoouuss ffiirrsstt oorrddeerr ddeerriivvaattiivveess,, tthheenn ⎧ 1 x ∂Q ∂P Q(x,y)= ∫ h(t,y)dt h(x,y)= − example ⎪⎨ 2 0 ∂x ∂y 1 y ⎪P(x,y)=− ∫ h(x,t)dt ⎩ 2 0 ⎛∂Q ∂P⎞ ( ) ∫∫ h x,y dxdy = ∫∫ ⎜ − ⎟dxdy ⎜ ⎟ R R⎝ ∂x ∂y ⎠ 2 22..11.. DDeerriivvaattiioonn ⎛∂Q ∂P⎞ ∫∫ h(x,y)dxdy=∫∫ ⎜ − ⎟dxdy ⎜ ⎟ R R⎝ ∂x ∂y ⎠ ∂Q ∂P =∫∫ dxdy−∫∫ dydx R ∂x R ∂y =∫ Qdy−∫Pdx ∂Γ ∂Γ l l =∫ Px&ds+∫ Qy&ds change of variables 0 0 ∂x ∂y x&= y&= ∂s ∂s 33.. MMiinniimmiizzaattiioonn E(∂Γ(s))=∫∫ h(x,y)dxdy R =∫l(P(x,y)x&+Q(x,y)y&)ds 0 =∫lL(x,x&,y,y&)ds 0 Minimizing in the steepest descentresults in the following Euler-Lagrange equations. δE ∂L d ∂L δE ∂L d ∂L = − = − δx ∂x ds ∂x& δy ∂y ds ∂y& 3 33..11.. EEuulleerr--LLaaggrraannggee EEqquuaattiioonnss δE ∂L d ∂L δE ∂L d ∂L = − = − δx ∂x ds ∂x& δy ∂y ds ∂y& ∂L ∂Q(x,y) ∂P(x,y) = x&+ y& ∂x ∂x ∂x ∂L ∂Q(x,y) ∂P(x,y) = x&+ y& ∂y ∂y ∂y ∂L ∂L =Q(x,y) = P(x,y) ∂x& ∂y& 33..11.. EEuulleerr--LLaaggrraannggee EEqquuaattiioonnss δE ∂L d ∂L δE ∂L d ∂L = − = − δx ∂x ds ∂x& δy ∂y ds ∂y& d ∂L d ∂Q ∂x ∂Q ∂y ∂Q ∂Q = Q(x(s),y(s))= + = x&+ y& ds ∂x& ds ∂x ∂s ∂y ∂s ∂x ∂y dL d ∂L ⎛∂Q ∂P ⎞ ⎛∂Q ∂P ⎞ ⎛∂Q ∂P⎞ − =⎜ x&+ y&⎟−⎜⎜ x&+ y&⎟⎟ =⎜⎜ − ⎟⎟y& dx ds ∂x& ⎝ ∂x ∂x ⎠ ⎝ ∂x ∂y ⎠ ⎝ ∂x ∂y ⎠ 14243 h(x,y) δE δE =h(x,y)y& =−h(x,y)x& δx δy 4 44.. TThhee MMoottiioonn EEqquuaattiioonn δE δE =h(x,y)y& =−h(x,y)x& δx δy r Normal vector along the contour is n =(y&,−x&) δE r r Let v =(x,y) thus =h(x,y)n r δv 44.. TThhee MMoottiioonn EEqquuaattiioonn δE r = h(x,y)n r δv h(x(s),y(s))= ∫m ∫m logP (I(x+ f (s),y+g(s)))1∂Γdxdy R R −m −m δE = −∫m ∫m logP (I(x))1∂Γ{x}dxdynrx δv −m −m Robj obj obj −∫m ∫m logP (I(x))1∂Γ{x}dxdynrx R bck bck −m −m bck 5 CCoonnttoouurr RReepprreesseennttaattiioonnss LLeevveell sseettss 11.. FFlluuiidd DDyynnaammiiccss PPrreeddiicctt tthhee mmoottiioonn ooff fflluuiiddss (cid:132)(cid:132) FFllooww ooff hheeaatt (cid:132)(cid:132) MMaassss ttrraannssffeerrss ((ppeerrssppiirraattiioonn……)),, eettcc.. (cid:132)(cid:132) NNoonn--rriiggiidd ttrraannssffoorrmmaattiioonn ooff ppaarrttiicclleess (cid:132)(cid:132) MMaatthheemmaattiiccaall ffoorrmmuullaattiioonn (cid:132)(cid:132) SScciieennttiiffiicc kknnoowwlleeddggee?? (cid:132)(cid:132) NNuummeerriiccaall iimmpplleemmeennttaattiioonn (cid:132)(cid:132) AAccccuurraaccyy?? (cid:132)(cid:132) 6 22.. RReepprreesseennttaattiioonnss PPaarraammeettrriicc:: LLaaggrraannggiiaann aapppprrooaacchh hhaass (cid:132)(cid:132) pprroobblleemmss dduurriinngg eevvoolluuttiioonn IImmpplliicciitt:: EEuulleerriiaann aapppprrooaacchh.. (cid:132)(cid:132) MMaarrkkeerr ssttrriinngg mmeetthhooddss (cid:132)(cid:132) VVoolluummee fflluuiidd mmeetthhooddss (cid:132)(cid:132) LLeevveell sseett mmeetthhooddss (cid:132)(cid:132) LLeevveell sseett aapppprrooaacchh iiss nnuummeerriiccaallllyy mmoosstt (cid:132)(cid:132) ssttaabbllee iimmpplliicciitt rreepprreesseennttaattiioonn 33.. TTwwoo--ddiimmeennssiioonnaall CCoonnttoouurr CClloosseedd ffoorrmm ccoonnttoouurr eeqquuaattiioonn (cid:132)(cid:132) (cid:132)(cid:132) CC((xx,,yy))==00 PPaarraammeettrriicc ccoonnttoouurr eeqquuaattiioonn (cid:132)(cid:132) (cid:132)(cid:132) CC((ff((ss)),,gg((ss))))==00 FFoorr iinnssttaannccee cciirrccllee:: (cid:132)(cid:132) x2 + y2 −1=0 x= f(s)=coss⎫ ⎬ parametric form y = g(s)=sins⎭ 7 33..11.. FFaammiillyy ooff CCoonnttoouurrss FFaammiillyy ppaarraammeetteerr tt iiss iinnttrroodduucceedd (cid:132)(cid:132) CC ((xx,,yy))==CC((xx,,yy,,tt))==00 (cid:132)(cid:132) tt TThhee ppaarraammeettrriicc ffoorrmm iiss (cid:132)(cid:132) CC ((ff((ss,,tt)),,gg((ss,,tt))))==CC((xx((ss,,tt)),,tt))==00 (cid:132)(cid:132) tt FFoorr iinnssttaannccee ffoorr tthhee cciirrccllee (cid:132)(cid:132) x= f(s,t)=tcoss y= g(s,t)=tsins CCoonnttoouurr RReepprreesseennttaattiioonnss EExxpplliicciitt ““ppaarraammeettrriicc ffoorrmm”” (cid:132)(cid:132) EExxpplliicciitt ““mmaarrkkeerr--SSttrriinngg mmeetthhoodd”” (cid:132)(cid:132) IImmpplliicciitt ““vvoolluummee fflluuiidd mmeetthhoodd”” (cid:132)(cid:132) IImmpplliicciitt ““lleevveell--sseett mmeetthhooddss”” (cid:132)(cid:132) implicit curve φ(∂Γ(s,t),t)=0 surface gradient φ=F.|∇φ| + t t - ∂φ(∂Γ(s,t),t) curve motion =0 update φn =φn−1−∆t|∇φ|F ∂t t 8 TThhee LLeevveell SSeett MMeetthhoodd OOsshheerr--SSeetthhiiaann ((11998877)) (cid:132)(cid:132) EEaarrlliieerr:: DDeerrvviieeuuxx,, TThhoommaasssseetttt,, ((11997799,, 11998800)) (cid:132)(cid:132) IInnttrroodduucceedd iinn tthhee aarreeaa ooff fflluuiidd ddyynnaammiiccss (cid:132)(cid:132) VViissiioonn aanndd iimmaaggee sseeggmmeennttaattiioonn (cid:132)(cid:132) CCaasseelllleess--CCaattttee--ccoollll--DDiibbooss ((11999922)) (cid:132)(cid:132) MMaallllaaddii--SSeetthhiiaann--VVeerrmmuurrii ((11999944)) (cid:132)(cid:132) LLeevveell SSeett MMiilleessttoonneess (cid:132)(cid:132) FFaauuggeerraass--kkeerriivveenn ((11999988)) sstteerreeoo rreeccoonnssttrruuccttiioonn (cid:132)(cid:132) PPaarraaggiiooss--DDeerriicchhee ((11999988)),, aaccttiivvee rreeggiioonnss aanndd ggrroouuppiinngg (cid:132)(cid:132) CChhaann--VVeessee ((11999999)) mmuummffoorrdd--sshhaahh vvaarriiaanntt (cid:132)(cid:132) LLeevveennttoonn--GGrriimmssoonn--FFaauuggeerraass--eettaall((22000000)) sshhaappee pprriioorrss (cid:132)(cid:132) ZZhhaaoo--FFeeddkkiieeww--OOsshheerr((22000011)) ccoommppuutteerr ggrraapphhiiccss (cid:132)(cid:132) TThhee LLeevveell SSeett MMeetthhoodd LLeett uuss ccoonnssiiddeerr iinn tthhee mmoosstt ggeenneerraall ccaassee tthhee ffoolllloowwiinngg (cid:132)(cid:132) ffoorrmm ooff ccuurrvvee pprrooppaaggaattiioonn:: AAddddrreessssiinngg tthhee pprroobblleemm iinn aa hhiigghheerr ddiimmeennssiioonn…… (cid:132)(cid:132) TThhee lleevveell sseett mmeetthhoodd rreepprreesseennttss tthhee ccuurrvvee iinn tthhee ffoorrmm (cid:132)(cid:132) ooff aann iimmpplliicciitt ssuurrffaaccee:: 9 LLeevveell SSeett RReepprreesseennttaattiioonn CCoonnttoouurr iiss rreepprreesseenntteedd iinn ddiissccrreettee ggrriidd (cid:132)(cid:132) GGrriidd vvaalluueess aarree ddiissttaanncceess ffrroomm tthhee ccoonnttoouurr (cid:132)(cid:132) CCoonnttoouurr iinnssiiddee iiss nneeggaattiivvee (cid:132)(cid:132) CCoonnttoouurr oouuttssiiddee iiss ppoossiittiivvee (cid:132)(cid:132) C(x(s,t),t)=0 + - LLeevveell SSeett RReepprreesseennttaattiioonn aanndd CCoonnttoouurr EEvvoolluuttiioonn 10