CCAAPP66441111 CCoommppuutteerr VViissiioonn SSyysstteemmss LLeeccttuurree 55 AAllppeerr YYiillmmaazz OOffffiiccee:: CCSSBB 225500 EEmmaaiill:: yyiillmmaazz@@ccss..uuccff..eedduu WWeebb:: hhttttpp::////wwwwww..ccss..uuccff..eedduu//ccoouurrsseess//ccaapp66441111//ccaapp66441111//sspprriinngg22000066 RReeccaapp IInntteerreesstt ppooiinntt ddeetteeccttiioonn 1 RReeccaapp PPoossssiibbllee AApppprrooaacchheess Based on brightness of images (cid:132) Usually image derivatives (cid:132) Based on boundary extraction (cid:132) First step edge detection (cid:132) Curvature analysis of edges (cid:132) RReeccaapp HHaarrrriiss CCoorrnneerr DDeetteeccttoorr CCoorrnneerr ppooiinntt ccaann bbee rreeccooggnniizzeedd iinn aa wwiinnddooww (cid:132)(cid:132) SShhiiffttiinngg aa wwiinnddooww iinn aannyy ddiirreeccttiioonn sshhoouulldd ggiivvee (cid:132)(cid:132) aa llaarrggee cchhaannggee iinn iinntteennssiittyy E(u,v)=∑ w(x,y) [ I(x,+u,y+v)−I(x,y)]2 14243 1442443 123 x,y window function shifted intensity intensity E(u,v)=(u v)M⎜⎛u⎟⎞ M =∑w(x,y)⎢⎡IxIx IxIy⎥⎤ ⎜ ⎟ I I I I ⎝v⎠ x,y ⎣ x y y y⎦ R = detM −k(traceM)2 C.Harris, M.Stephens. “A Combined Corner and Edge Detector”. 1988 2 SSUUSSAANN DDeetteeccttoorr PPrrooppoosseedd bbyy SSmmiitthh aanndd BBrraaddyy iinn 11999955 (cid:132)(cid:132) SSUUSSAANN ssttaannddss ffoorr SSmmaalllleesstt ““UUnniivvaalluuee (cid:132)(cid:132) SSeeggmmeenntt AAssssiimmiillaattiinngg NNuucclleeuuss ((UUSSAANN))”” IItt ddooeessnn’’tt uussee aannyy ddeerriivvaattiivveess (cid:132)(cid:132) IItt iiss bbaasseedd oonn tthhee ffaacctt tthhaatt eeaacchh ppooiinntt (cid:132)(cid:132) wwiitthhiinn aann iimmaaggee iiss aassssoocciiaatteedd wwiitthh iitt aa llooccaall aarreeaa ooff ccoommppaarraabbllee bbrriigghhttnneessss S.M. Smith. SUSAN -a new approach to low level image processing. Internal Technical Report TR95SMS1, DefenceResearch Agency, ChobhamLane, Chertsey, Surrey, UK, 1995. PPrriinncciippllee CCoonnssiiddeerreedd iinn aa cciirrccuullaarr mmaasskk aarroouunndd aa (cid:132)(cid:132) ppiixxeell CCoommppaarriissoonn ooff iinntteennssiittyy iinn aa (cid:132)(cid:132) nneeiigghhbboorrhhoooodd AArreeaa wwiitthh ssiimmiillaarr iinntteennssiittiieess iiss ccaalllleedd UUSSAANN (cid:132)(cid:132) RReeppeeaatt tthhee pprroocceedduurree ffoorr eeaacchh ppiixxeell (cid:132)(cid:132) 3 TThhee SSUUSSAANN DDeetteeccttoorr (cid:132)(cid:132) UUSSAANN aarreeaa vvaarriieess wwiitthh rreessppeecctt ttoo ffeeaattuurreessooff tthhee iimmaaggee (cid:132)(cid:132) UUSSAANN aarreeaa (cid:132)(cid:132) iiss mmaaxxiimmuumm wwiitthhiinn tthhee rreeccttaanngguullaarr aarreeaa (cid:132)(cid:132) ffaallllss ttoo aa mmiinniimmuumm aatt aann eeddggee (cid:132)(cid:132) ssmmaalllleerr vvaalluuee ccoorrrreessppoonnddiinngg ttoo aa llooccaall mmiinniimmuumm aatt aa ccoorrnneerr (cid:132)(cid:132) TThhiiss iiss tthhee pprrooppeerrttyy uuppoonn wwhhiicchh tthhee ccoorrnneerr ffiinnddeerr aallggoorriitthhmm iiss bbaasseedd AAllggoorriitthhmm DDeetteerrmmiinnee aa cciirrccuullaarr mmaasskk 11.. TTyyppiiccaallllyy 3377 ppiixxeellss aarroouunndd eeaacchh ppiixxeell ((nnuucclleeuuss)) (cid:132)(cid:132) CCaallccuullaattee tthhee bbrriigghhttnneessss ddiiffffeerreennccee bbeettwweeeenn 22.. eeaacchh ppiixxeell iinn tthhee mmaasskk wwiitthh iittss nnuucclleeuuss ⎧1 if I(r )−I(r ) ≤t c(r,r )= ⎨ 0 0 0 otherwise ⎩ SSuumm tthhee nnuummbbeerr ooff ppiixxeellss wwiitthh ssiimmiillaarr 33.. iinntteennssiittyy lleevveellss ttoo tthhaatt ooff tthhee nnuucclleeuuss n(r )= ∑c(r,r ) 0 0 r 4 AAllggoorriitthhmm CCoommppaarree nn wwiitthh gg,, tthhee ggeeoommeettrriicc tthhrreesshhoolldd 44.. wwhhiicchh iiss sseett ttoo hhaallff ooff tthhee mmaaxxiimmuumm vvaalluuee tthhaatt nn ccaann bbee ((nn //22)) mmaaxx AAtt aa ppeerrffeecctt ccoorrnneerr tthhee UUSSAANN aarreeaa wwiillll aallwwaayyss 55.. bbee lleessss tthhaann hhaallff tthhee ssiizzee ooff tthhee mmaasskk aarreeaa,, aanndd wwiillll bbee aa llooccaall mmiinniimmuumm ⎧g −n(r ) if n(r )< g R(r )= ⎨ 0 0 0 0 otherwise ⎩ PPrroobblleemmss SSttrroonngg eeddggeess aanndd nnooiissee rreessuullttss iinn ffaallssee ddeetteeccttiioonn (cid:132)(cid:132) ((LLeefftt ffiigguurree)) TThhee UUSSAANN iiss nnoott ccoonnttiinnuuoouuss.. OObbvviioouussllyy (cid:132)(cid:132) nnuucclleeuuss iiss nnoott aa ccoorrnneerr,, eevveenn tthhoouugghh tthhee ffuunnccttiioonn sshhoowwss iitt iiss tthhee llooccaall mmaaxxiimmaa.. ((RRiigghhtt ffiigguurree)) NNuucclleeuuss lliieess iinn aa lloonngg tthhiinn aarreeaa,, wwhhiicchh (cid:132)(cid:132) ddeeppiiccttss UUSSAANN iiss aallssoo vveerryy ssmmaallll.. HHoowweevveerr,, tthhee vvaalluuee iiss hhiigghh,, wwhhiicchh ccoonnttrraaddiiccttss tthhee ffaacctt tthhaatt tthhee ppooiinntt iinn qquueessttiioonn iiss nnoott aa ccoorrnneerr.. 5 IImmpprroovviinngg SSUUSSAANN DDeetteeccttoorr TTwwoo rruulleess (cid:132)(cid:132) FFiinndd cceennttrrooiidd ooff UUSSAANN aarreeaa aanndd ddiissttaannccee (cid:132)(cid:132) ffrroomm nnuucclleeuuss.. ppooiinntt ccaannnnoott bbeeccoommee aa ccoorrnneerr iiff tthhee ddiissttaannccee iiss ssmmaallll.. OOnnee ooff tthhee ppiixxeellss oonn tthhee lliinnee ccoonnnneeccttiinngg (cid:132)(cid:132) cceennttrrooiidd ttoo cceenntteerr ooff cciirrccuullaarr rreeggiioonn ccaann bbee aa ccoorrnneerr BBeenneeffiittss AAccccuurraaccyy,, ssppeeeedd aanndd llooccaalliizzaattiioonn (cid:132)(cid:132) Output of the SUSANcorner detector Output of the Plesseycorner detector (t=10) given the test image. (0.3 sec) (o=2.0) given the test image. (3.5 sec) 6 SSIIFFTT -- KKeeyy PPooiinntt EExxttrraaccttiioonn SSttaannddss ffoorr ssccaallee iinnvvaarriiaanntt ffeeaattuurree (cid:132)(cid:132) ttrraannssffoorrmm PPaatteenntteedd bbyy uunniivveerrssiittyy ooff BBrriittiisshh (cid:132)(cid:132) CCoolluummbbiiaa SSiimmiillaarr ttoo tthhee oonnee uusseedd iinn pprriimmaattee vviissuuaall (cid:132)(cid:132) ssyysstteemm ((hhuummaann,, aappee,, mmoonnkkeeyy,, eettcc..)) TTrraannssffoorrmmss iimmaaggee ddaattaa iinnttoo ssccaallee-- (cid:132)(cid:132) iinnvvaarriiaanntt ccoooorrddiinnaatteess D. Lowe. Distinctive image features from scale-invariant key points., International Journal of Computer Vision 2004. GGooaall EExxttrraaccttiinngg ddiissttiinnccttiivvee iinnvvaarriiaanntt ffeeaattuurreess (cid:132)(cid:132) CCoorrrreeccttllyy mmaattcchheedd aaggaaiinnsstt aa llaarrggee ddaattaabbaassee ooff (cid:132)(cid:132) ffeeaattuurreess ffrroomm mmaannyy iimmaaggeess IInnvvaarriiaannccee ttoo iimmaaggee ssccaallee aanndd rroottaattiioonn (cid:132)(cid:132) RRoobbuussttnneessss ttoo (cid:132)(cid:132) AAffffiinnee ddiissttoorrttiioonn,, (cid:132)(cid:132) CChhaannggee iinn 33DD vviieewwppooiinntt,, (cid:132)(cid:132) AAddddiittiioonn ooff nnooiissee,, (cid:132)(cid:132) CChhaannggee iinn iilllluummiinnaattiioonn.. (cid:132)(cid:132) 7 AAddvvaannttaaggeess LLooccaalliittyy:: ffeeaattuurreess aarree llooccaall,, ssoo rroobbuusstt ttoo (cid:132)(cid:132) oocccclluussiioonn aanndd cclluutttteerr DDiissttiinnccttiivveenneessss:: iinnddiivviidduuaall ffeeaattuurreess ccaann bbee (cid:132)(cid:132) mmaattcchheedd ttoo aa llaarrggee ddaattaabbaassee ooff oobbjjeeccttss QQuuaannttiittyy:: mmaannyy ffeeaattuurreess ccaann bbee ggeenneerraatteedd (cid:132)(cid:132) ffoorr eevveenn ssmmaallll oobbjjeeccttss EEffffiicciieennccyy:: cclloossee ttoo rreeaall--ttiimmee ppeerrffoorrmmaannccee (cid:132)(cid:132) EExxtteennssiibbiilliittyy:: ccaann eeaassiillyy bbee eexxtteennddeedd ttoo wwiiddee (cid:132)(cid:132) rraannggee ooff ddiiffffeerriinngg ffeeaattuurree ttyyppeess,, wwiitthh eeaacchh aaddddiinngg rroobbuussttnneessss IInnvvaarriiaanntt LLooccaall FFeeaattuurreess 8 SStteeppss ffoorr EExxttrraaccttiinngg KKeeyy PPooiinnttss SSccaallee ssppaaccee ppeeaakk sseelleeccttiioonn (cid:132)(cid:132) PPootteennttiiaall llooccaattiioonnss ffoorr ffiinnddiinngg ffeeaattuurreess (cid:132)(cid:132) KKeeyy ppooiinntt llooccaalliizzaattiioonn (cid:132)(cid:132) AAccccuurraatteellyy llooccaattiinngg tthhee ffeeaattuurree kkeeyy (cid:132)(cid:132) OOrriieennttaattiioonn AAssssiiggnnmmeenntt (cid:132)(cid:132) AAssssiiggnniinngg oorriieennttaattiioonn ttoo tthhee kkeeyyss (cid:132)(cid:132) KKeeyy ppooiinntt ddeessccrriippttoorr (cid:132)(cid:132) DDeessccrriibbiinngg tthhee kkeeyy aass aa hhiigghh ddiimmeennssiioonnaall vveeccttoorr (cid:132)(cid:132) BBuuiillddiinngg aa SSccaallee SSppaaccee AAllll ssccaalleess mmuusstt bbee eexxaammiinneedd ttoo iiddeennttiiffyy ssccaallee-- (cid:132)(cid:132) iinnvvaarriiaanntt ffeeaattuurreess AAnn eeffffiicciieenntt ffuunnccttiioonn iiss ttoo ccoommppuuttee tthhee LLaappllaacciiaann (cid:132)(cid:132) PPyyrraammiidd ((DDiiffffeerreennccee ooff GGaauussssiiaann)) ((BBuurrtt && AAddeellssoonn,, 11998833)) 9 BBuuiillddiinngg aa SSccaallee SSppaaccee 1 G(x,y,kσ)= e−(x2+y2)/2k2σ2 2π(kσ)2 kkiiss tthhee nnuummbbeerr ooff cchhoosseenn ssccaallee iinn eeaacchh ooccttaavvee SSccaallee SSppaaccee PPeeaakk DDeetteeccttiioonn CCoommppaarree aa ppiixxeell ((XX)) wwiitthh 2266 (cid:132)(cid:132) ppiixxeellss iinn ccuurrrreenntt aanndd aaddjjaacceenntt ssccaalleess ((GGrreeeenn CCiirrcclleess)) SSeelleecctt iiff llaarrggeerr//ssmmaalllleerr tthhaann aallll (cid:132)(cid:132) 2266 ppiixxeellss LLaarrggee nnuummbbeerr ooff eexxttrreemmaa,, (cid:132)(cid:132) ccoommppuuttaattiioonnaallllyy eexxppeennssiivvee DDeetteecctt tthhee mmoosstt ssttaabbllee ssuubbsseett (cid:132)(cid:132) wwiitthh aa ccooaarrssee ssaammpplliinngg ooff ssccaalleess 10