Illesztés Digitális képelemzés alapveto˝ algoritmusai
1
Megfeleltetés és illesztés a számítógépes latásban Megfeleltetést igénylo˝ képelemzési feladatok Megfeleltetés kritikus problémái
2
Mintaillesztés Eltérési mértékek Hasonlósági mértékek
3
Robusztusság és lokalizációs pontosság
4
Invariancia, robusztusság, sebesség Mintaillesztés felgyorsítása ˝ Az illesztési konzisztencia ellenorzése
Csetverikov Dmitrij Eötvös Lóránd Egyetem, Budapest
[email protected] http://vision.sztaki.hu
Informatikai Kar
Adatregistráció és -fúzió 1/2
˝ Különbözo˝ érzékelokkel képeket készítünk ugyanarról a ˝ színtérrol. pl. emberi testról MRI, PET, röntgen képeket
A különbözo˝ fizikai eredetu˝ képeket össze kell illeszteni, megfeleltetni. orvosi képalkotásban az ilyen képeket modalitásoknak hívják
Ez multimodális képregisztráció. illesztés = matching megfeleltetés = search for correspondence megfeleltetni = find correspondence
Adatregistráció és -fúzió 2/2
Ha nem képi, hanem más mérési adatokról, pl. 3D-s ponthalmazokról van szó, akkor adatregistrációról beszélünk. pl. az angol 3D data registration kifejezés gyakran a mért ˝ illesztését jelenti felületek vagy pontfelhok
Ha különbözo˝ adatstruktúrájú adatokat illesztünk össze, akkor inkább az adatfúzió szót használjuk. ⇒ video és hang adatfúziója, regisztrációja ⇒ kép és ponthalmaz adatfúziója, regisztrációja
Mozgáselemzés
˝ Különbözo˝ idopontokban képeket készítünk változó, ˝ mozgó színtérrol. például arcmozgást, -kifejezést vizsgálunk vagy térmegfigyelést végzünk
Ilyenkor kereshetünk egymásnak megfelelo˝ pontokat (correspondences) elmozdulásokat (displacements) változásokat
Ez mozgáselemzés. Tipikus példák: mozgáskövetés (motion tracking) optikai áramlás becslése (optical flow estimation)
Mintaillesztés
Olyan kisebb képrészeket keresünk, amelyek egy adott mintára hasonlítanak. ˝ vagy egy másik képbol ˝ A mintát mágából a képbol, vehetünk. sztereóillesztésnél is lokális mintát keresünk, amikor pontokat (pontkörnyezeteket) megfeleltetünk, korrelálunk mozgáskövetés is gyakran mintaillesztéssel történik kereshetünk minta szerint egy képi adatbázisban is
Mintaillesztés egy alapveto˝ felismerési probléma, számtalan feladatban jelenik meg. ˝ ˝ ˝ lesz szó ⇒ az eloadásban elsosorban mintaillesztésrol
Sztereó látás
˝ képeket készítünk egy Különbözo˝ szemszögbol ˝ és keresünk egymásnak megfelelo˝ képpontokat. színtérrol Ez a sztereó látás. Az illesztés biztosítja a diszparitásokat. a két felvétel közötti pontelmozdulásokat
Diszparitás és bázistávolság alapján triangulációval meghatározzuk a mélységet. bázistávolság (baseline) a kamerák közötti távolság mélység (depth) a kamera és a 3D-s pont közötti távolság
Klasszikus sztereó: kalibrált kamerapár (stereo rig). Általános eset: 3D-s rekonstrukció több felvétel alapján.
Megfeleltetés nehézségei A megfeleltetési probléma sikeres megoldása kritikus kérdés a számítógépes látásban. megnyítja az utat további problémák megoldása felé de több elvi nehézséget kell leküzdeni
Képalkotási változásokkal szembeni robusztusság ˝ távolság, perspektíva) térbeli (látószog, ˝ fotometrikus (világítás, fényvisszaverodés)
˝ Más tényezokkel szembeni robusztusság zaj, képtorzítás takarás (occlusion): nem minden pontnak van megfelelóje, és nem tudjuk, hogy melyiknek nincs ⇒ láthatóság (visibility ) problémája
A következo˝ változásokat fogjuk vizsgálni:
Mintaillesztés fogalma
Geometriai transzformációk 2D-s eltolás és elforgatás
Fotometrikus transzformációk intenzitás-skálázás és -eltolás ⇒ I ′ = aI + b
Az intenzitás-skálázás és -eltolás jelentése ˝ a: a direkt megvilágítás erossége ⇒ az objektumra irányított, közvetlen megvilágítás ˝ b: a szórt fény (ambient light) erossége ⇒ a színtér globális fényessége ⇒ minden irányból érkezo˝ fény
Négyzetes különbségek összege o2 Xn ′ ′ ′ ′ SSD(x, y ) = f (x + x , y + y ) − w(x , y ) , ahol az egyszeruség ˝ kedvéért X =
X
(x ′ ,y ′ )∈W
(x+x ′ ,y +y ′ )∈F
SSD a Sum of Squared Differences rövidítése. W a lokális pozíciók halmaza a w mintán belül F a globális pozíciók halmaza az f képen belül
SSD(x, y ) nem invariáns 2D-s elforgatásra ⇒ nem talál meg elforgatott mintát intenzitás-változásokra ⇒ nem kezel változó világítást
Minden lehetséges (x, y ) pozícióban összehasonlítjuk a w(x ′ , y ′ ) képmintát (részképet) az f (x ′ , y ′ ) képpel más szóval, minden (x, y ) pontban illesztjük a w(x ′ , y ′ )-t az f (x + x ′ , y + y ′ )-hez
Mintaillesztés: olyan (x, y ) helyeket keresünk, ahol kicsi az eltérés a minta és a kép között, vagy nagy a hasonlóság a minta és a kép között angolul: low dissimilarity, high similarity
Intenzitás-eltolásra korrigált SSD
SSDSC (x, y ) =
i h io2 Xnh f (x +x ′ , y +y ′ )−f (x, y ) − w(x ′ , y ′ )−w
f (x, y ) az intezitás-átlag az aktuális képrészen. minden (x, y ) pozícióban kell kiszámítani ˝ ⇒ hasznaljuk a futó dobozszur ˝ ot!
w a minta átlaga. csak egyszer kell kiszámítani
SSDSC (x, y ) segítségével kompenzálhatjuk az intenzitás-eltolást kezeli a szórt fény változását nem kezeli a direkt megvilágítás változását
Nemnormalizált kereszt-korreláció CC(x, y ) =
X
f (x + x ′ , y + y ′ ) · w(x ′ , y ′ )
A kereszt-korreláció és a konvolúció tulajdonságait már ismerjük. CC(x, y ) formailag ugyanaz, mint az f kép a w maszkkal való szurése. ˝ ˝ tudunk, itt is alkalmazható: normalizálás, ⇒ amit szurésr ˝ ol szeparábilitás, futószurés ˝
Normalizált kereszt-korreláció
NCC(x, y ) =
i h i 1 Xh f (x + x ′ , y + y ′ ) − f (x, y ) · w(x ′ , y ′ ) − w , N1
ahol p Sf (x, y ) · Sw , i2 Xh Sf (x, y ) = f (x + x ′ , y + y ′ ) − f (x, y ) , i2 X h Sw = w(x ′ , y ′ ) − w . N1 =
(x ′ ,y ′ )∈W
CC(x, y ) nem invariáns intenzitás-eltolásra és -skálázásra. Amikor w > 0 és f nagy, CC(x, y ) is nagy, függetlenül attól, hogy w és f hasonlítanak-e. ⇒ ezt normalizálással korrigáljuk
Módosított normalizált kereszt-korreláció MNCC(x, y ) =
Sf (x, y )-t sokszor kell kiszámítani, SW -t csak egyszer. NCC(x, y ) invariáns minden lineáris intenzitás-változásra
Mintaillesztés példája
i h i 1 Xh f (x +x ′ , y +y ′ )−f (x, y ) · w(x ′ , y ′ )−w , N2
ahol N2 = Sf (x, y ) + Sw
bal kép
minta, kinagyítva
jobb kép
Az MNCC és az NCC közöttp a különbség csak a normalizálásban van: N1 = Sf (x, y ) · Sw . MNCC-vel elkerülheto˝ a numerikus instabilitás, amikor Sf (x, y ) kicsi. kis képváltozás
Elméletileg, az MNCC csak eltolás-korrigált. a gyakorlatban, kevésbé érzékeny skálázásra is: Sf (x, y ) + Sw ∝ Sf (x, y ), közelítve
NCC kép
NCC felület
SDD kép
SDD felület
A jobb képen levo˝ mintán a bal képen keressük. NCC a normalizált kereszt-korreláció SSD a négyzetes különbségek
Numerikus példa mintaillesztésre minta 0 0 0 1 1 1 0 0 0
Területilleztés vagy kontúrillesztés? 1/2
input kép 0 0 0 1 1 1 0 0 0
CC eredménye
NCC eredménye
1 2 3 2 1
1.0 1.4 1.7 1.4 1.0
1 1 1 1 1 1 1 1 1
1 2 3 2 1 1 2 3 2 1 1 2 3 2 1
1.0 1.2 1.0 1.0 1.0 1.2 1.0
(N)CC: (normalizált) keresz-korreláció az input képet 0-ák veszik körül az eredményekben az 1 alatti értékeket nem mutatjuk
Ideális illeszkedés nem sokkal jobb, mint közeli értékek ⇒ az illesztés nem elég éles
minta 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0
0 0 0 0 0
1 1 1 1 1 1 1 1 1
0 0 0 0 0
0 1 1 1 0
0 0 0 0 0
1 1 1 1 0 1 1 1 1
0 1 0 1 0
0 1 1 1 0
input kép
NCC eredménye 1.2 1.3 2.0 1.3 1.2 2.0 3.0 2.0 1.2 1.3 2.0 1.3 1.2 1.3 1.4 1.3 1.4 2.8 1.4 1.3 1.4 1.3
Kontúrillesztés élesebb eredményt ad. területilleztés: ideális illesztés és közeli értékek aránya 1.5 kontúrillesztés: az arány 2
Területilleztés vagy kontúrillesztés? 2/2 szagg. vonal: minta folyt. vonal: objektum körök: átfedo˝ pontok
ideális objektum
0 0 0 0 0
eltorzított objektum
Ideális objektum esetén a minta kis eltolására a kontúrátfedés drasztikusan csökken a területátfedés alig csökken ⇒ kontúrillesztés élesebb
Eltorzított vagy elforgatott objektum esetén a kontúrátfedés kicsi ⇒ elveszíthetjük az objektumot a területátfedés nagy ⇒ megtaláljuk az objektumot ⇒ kontúrillesztés kevésbé robusztus
Robusztusság és lokalizációs pontosság
Kontúrillesztés élesebb illesztés: jobb lokalizáció kevésbé robusztus: elveszíthetünk objektumokat gyorsabb
Területilleztés kevésbé éles illesztés robusztusabb lassúbb
Más detektálási feladatoknál is van hasonló kapcsolat. jobb lokalizációs pontosság ⇒ gyengébb robusztusság ha megtaláljuk, megmondjuk a pontos helyét, vagy megtaláljuk, de nem tudjuk a pontos helyét
Mintaillesztés kritikus problémái
Méretváltozás és elforgatás kezelése Képnormalizálás
Méret-változásokra és elforgatásra való invariancia ˝ és/vagy elforgatva látjuk például, közelebbrol
Képtorzítással szembeni robusztusság
Adaptív megoldások
például, perpektív torzítás
minden pozícióban variáljuk a minta méretét és orientációját kiválasztjuk a legjobban illeszkedo˝ méretet és orientációt nagyon lassú ha a méretek és szögek száma nagy ⇒ csak kisszámú méret és szög esetén használjuk!
"Zajos" illeszkedésekkel szembeni robusztusság ˝ nem keresett képrészek váratlanul jól illeszkedo, ⇒ hasonlósági mértékeink nem ideálisak!
Invariáns megoldások
Számításigény
méret- és elforgatás-invariáns leírást használunk nem képeket, hanem képleírásokat hasonlítunk össze
Torzítástur ˝ o˝ illesztés
Képnormalizálás méretre és orientációra
A A A
A A A
A A
template
a képet standard méretre és orientációra transzformáljuk ⇒ feltételezi, hogy képen belül nincs méret- vagy orientáció-változás ⇒ képorientációt kell definíálni
original image
A
A A
normalised image
A jobb felso˝ sorokban levo˝ A betu˝ mérete és orientációja ˝ eltér a többiétol. ⇒ ez a betu˝ nem fog illeszkedni
A többi négy betu˝ illeszkedni fog. Hogyan definíáljuk a képorientációt?
Rugalmas mintákat használunk. rugalmasan összekötött alminták
˝ teszik a minta A "rugók" lehetové kisebb változtatását bevezetünk egy célfüggvényt, amely büntet nagyobb változtatásokat ⇒ nagyobb változtatásnak nagyobb a költsége
Akkor muködik ˝ jól, amikor az alminták elég jellegzetesek megbízható illesztéshez.
Arcminta mint rugalmasan összekötött alminták rendszere.
˝ Mintaillesztés felgyorsítása jellemzopontokkal
Nem képekkel és mintákkal dolgozunk, hanem lokális ˝ jellemzopontjaikkal. például élekkel, sarkokkal
Akkor hasznos, amikor a képi sajátságok viszonylag ritkák, de megbízhatóak. Másfelöl, ez a megoldás torzításérzékeny lehet. emlékezzünk vissza kontúrillesztésre!
Mintaillesztés felgyorsítása FFT-vel
Nagy minták esetén a kereszt-korrelációt célszeru˝ Gyors Fourier Transzformációval, FFT-vel implementálni. h ∗ i f ⊗ w = IFFT FFT f (x, y ) · FFT w(x, y ) IFFT az inverz FFT X ∗ az X komplex konjugáltja
N × N-es képre az FFT muveletigénye ˝ O(N 2 log N) a direkt implementáció muveletigénye ˝ O(N 4 )
Ökölszabály "nagy mintára": nagyobb mint 13 × 13 pixel.
Nem illeszkedo˝ régiók gyors kiszurése: ˝ alapötlet
1
Gyorsan kiszurjük ˝ a nyilvánvalóan nem illeszkedo˝ régiokat.
2
Csak a megmaradt, válogatott régiókat, jelölteket vizsgáljuk meg alaposan. Azért hatékony, mert a mintára egyáltalán nem hasonló régióból gyakran sokkal több van, mint a hasonlóból. De vigyázni kell vele, mert elveszíthetünk igazi, keresett régiókat. ⇒ ha ügyetlenül szur ˝ unk ˝
Gyors kiszurés ˝ ritkított mintavételezéssel
˝ Eloször nem minden pontban illesztünk, hanem nagyobb lépéssel mozgatjuk a mintát. Kiszurjük ˝ a nyilvánvalóan nem illeszkedo˝ helyeket, aztán csak a megmaradt helyekkel foglalkozunk. Ezt egy képpiramissal is meg lehet csinálni. Gyakorlatilag, a keresztkorrelációs függvény egyre ˝ van szó. finomabb mintavételezésérol ⇒ elveszíthetünk nagyon keskeny csúcsokat, maximumokat!
Gyors kiszurés ˝ más módszerekkel
Az oda-vissza illesztés Hamis illeszkedések kiszurésére ˝ alkalmazott módszer.
Kiszámítjuk minta és régió egyszeru˝ tuljadonságait.
Csak akkor fogadunk el illesztést, ha fordítva is érvényes.
kiszurjük ˝ a régiót, ha a tulajdonságok nagyon eltérnek
Kisebb almintákat használunk. kiszurjük ˝ a régiót, ha az alminták nem illeszkednek
˝ eltérési Küszöböt szabunk kumulatív (összegzo) mértékre. kiszurjük ˝ a régiót, ha a mérték eléri a küszöböt ⇒ nem kell végig számolni az eltérést! de a küszöb jó beállítása nem egyszeru˝ dolog ⇒ legyen inkább óvatos, viszonylag magas érték!
bal kép
jobb kép
eredet IH
konzistens IH
Takart pontok kiszurése ˝ sztereóillesztésben. Illesztési Hiba: világosabb pixel → nagyobb hiba ˝ konzisztencia-ellenorzés kiszuri ˝ a takart pontokat
