Detekce rohů - Corner detection

Výstup typického algoritmu detekce rohů

Detekce rohů je přístup používaný uvnitř počítačové vidění systémy pro extrakci určitých druhů funkce a odvodit obsah obrázku. Detekce rohů se často používá v detekce pohybu, registrace obrázku, sledování videa, obrazová mozaika, panorama šití, 3D rekonstrukce a rozpoznávání objektů. Detekce rohů se překrývá s tématem detekce zájmových bodů.

Formalizace

Roh lze definovat jako průsečík dvou hran. Roh lze také definovat jako bod, pro který existují dva dominantní a různé směry hran v místním sousedství bodu.

Zájmový bod je bod v obraze, který má dobře definovanou polohu a lze jej důkladně detekovat. To znamená, že zájmovým bodem může být roh, ale může to být také například izolovaný bod maximální nebo minimální lokální intenzity, konce čar nebo bod na křivce, kde je lokálně maximální zakřivení.

V praxi většina takzvaných metod detekce rohů detekuje zájmové body obecně a ve skutečnosti se výrazy „roh“ a „zájmový bod“ v literatuře používají víceméně zaměnitelně.^[1] V důsledku toho, pokud mají být detekovány pouze rohy, je nutné provést lokální analýzu detekovaných bodů zájmu a určit, které z nich jsou skutečné rohy. Příklady detekce hran, které lze použít při následném zpracování k detekci rohů, jsou Operátor Kirsch a maskovací sada Frei-Chen.^[2]

„Roh“, „zájmový bod“ a „rys“ jsou v literatuře zaměnitelně zaměňovány. Konkrétně jich je několik detektory blobů které lze označit jako „operátory zájmových bodů“, ale které se někdy chybně označují jako „detektory rohů“. Navíc existuje představa detekce hřebene zachytit přítomnost podlouhlých předmětů.

Rohové detektory nejsou obvykle příliš robustní a často vyžadují velké propouštění, aby se zabránilo efektu jednotlivých chyb v dominování úlohy rozpoznávání.

Jedním z určujících kvality detektoru rohů je jeho schopnost detekovat stejný roh v několika podobných obrazech za podmínek odlišného osvětlení, translace, rotace a dalších transformací.

Používá se jednoduchý přístup k detekci rohů na obrázcích korelace, ale toto je výpočetně velmi nákladné a neoptimální. Často používaný alternativní přístup je založen na metodě navržené Harrisem a Stephensem (níže), což je zase zdokonalení metody od Moravce.

Algoritmus detekce rohu Moravec

Toto je jeden z prvních algoritmů detekce rohů a definuje a roh být bodem s nízkou podobností sebe sama.^[3] Algoritmus testuje každý pixel v obraze, aby zjistil, zda je přítomen roh, a to tak, že vezme v úvahu, jak podobný je patch vycentrovaný na pixelu blízkým, do značné míry překrývajícím se patche. Podobnost se měří pomocí součtu čtvercových rozdílů (SSD) mezi odpovídajícími pixely dvou oprav. Nižší číslo znamená větší podobnost.

Pokud je pixel v oblasti jednotné intenzity, budou blízké opravy vypadat podobně. Pokud je pixel na hraně, pak blízké záplaty ve směru kolmém na hranu budou vypadat úplně jinak, ale blízké záplaty ve směru rovnoběžném s hranou způsobí jen malou změnu. Pokud je pixel na prvku se změnami ve všech směrech, pak žádná z blízkých oprav nebude vypadat podobně.

Síla rohu je definována jako nejmenší SSD mezi patchem a jeho sousedy (horizontální, vertikální a na dvou úhlopříčkách). Důvodem je, že pokud je toto číslo vysoké, pak je variace podél všech směn buď stejná, nebo větší než ona, takže zachycení, že všechny blízké opravy vypadají jinak.

Pokud je číslo síly rohu vypočítáno pro všechna umístění, znamená to, že je lokálně maximální pro jedno umístění, znamená, že je v něm přítomna zájmová vlastnost.

Jak zdůraznil Moravec, jedním z hlavních problémů tohoto operátora je, že tomu tak není izotropní: Pokud je k dispozici hrana, která není ve směru sousedů (horizontální, vertikální nebo diagonální), bude nejmenší SSD velký a hrana bude nesprávně zvolena jako bod zájmu.^[4]

Harris & Stephens / Shi – Tomasi algoritmy detekce rohů

Vidět Harrisův rohový detektor.

Harris a Stephens^[5] vylepšil Moravecův rohový detektor tím, že místo použití posunutých záplat zvážil rozdíl skóre v rohu s ohledem na směr přímo. (Toto rohové skóre se často označuje jako autokorelace, protože tento výraz se používá v článku, ve kterém je tento detektor popsán. Matematika v článku však jasně naznačuje, že se používá součet čtvercových rozdílů.)

Bez ztráty obecnosti budeme předpokládat, že se použije 2-dimenzionální obraz ve stupních šedi. Nechť je tento obrázek dán ${displaystyle I}$. Zvažte převzetí obrazové záplaty přes oblast ${displaystyle (u, v)}$ a posunutí o ${displaystyle (x, y)}$. Vážený součet čtvercových rozdílů (SSD) mezi těmito dvěma opravami, označené ${displaystyle S}$, darováno:

${displaystyle S (x, y) = součet _ {u} součet _ {v} w (u, v), doleva (I (u + x, v + y) -I (u, v) ight) ^ {2 }}$

${displaystyle I (u + x, v + y)}$ lze aproximovat pomocí a Taylor expanze. Nechat ${displaystyle I_ {x}}$ a ${displaystyle I_ {y}}$ být částečný deriváty z ${displaystyle I}$, takový, že

${displaystyle I (u + x, v + y) cca já (u, v) + I_ {x} (u, v) x + I_ {y} (u, v) y}$

Tím se vytvoří aproximace

${displaystyle S (x, y) přibližný součet _ {u} součet _ {v} w (u, v), levý (I_ {x} (u, v) x + I_ {y} (u, v) yight) ^ {2},}$

které lze zapsat v matici:

${displaystyle S (x, y) cca {egin {pmatrix} x & yend {pmatrix}} A {egin {pmatrix} x yend {pmatrix}},}$

kde A je strukturní tenzor,

${displaystyle A = součet _ {u} součet _ {v} w (u, v) {egin {bmatrix} I_ {x} (u, v) ^ {2} & I_ {x} (u, v) I_ {y } (u, v) I_ {x} (u, v) I_ {y} (u, v) & I_ {y} (u, v) ^ {2} konec {bmatrix}} = {egin {bmatrix} jazyk I_ {x} ^ {2} úhel a jazyk I_ {x} I_ {y} úhel jazyk I_ {x} I_ {y} úhel a jazyk I_ {y} ^ {2} konec úhlu {bmatrix}}}$

Slovy najdeme kovariance částečné derivace intenzity obrazu ${displaystyle I}$ s respektem k ${displaystyle x}$ a ${displaystyle y}$ sekery.

Úhlové závorky označují průměrování (tj. Součet za ${displaystyle (u, v)}$). ${displaystyle w (u, v)}$ označuje typ okna, které se posouvá přes obrázek. Pokud Boxový filtr je použita odpověď bude anizotropní, ale pokud a Gaussian se použije, pak bude odpověď izotropní.

Roh (nebo obecně zajímavý bod) se vyznačuje velkou variací ${displaystyle S}$ ve všech směrech vektoru ${displaystyle {egin {pmatrix} x & yend {pmatrix}}}$. Analýzou vlastních čísel ${displaystyle A}$, tuto charakteristiku lze vyjádřit následujícím způsobem: ${displaystyle A}$ by měl mít dvě „velká“ vlastní čísla pro bod zájmu. Na základě velikostí vlastních čísel lze na základě tohoto argumentu učinit následující závěry:

1. Li ${displaystyle lambda _ {1} přibližně 0}$ a ${displaystyle lambda _ {2} přibližně 0}$ pak tento pixel ${displaystyle (x, y)}$ nemá žádné zajímavé vlastnosti.
2. Li ${displaystyle lambda _ {1} přibližně 0}$ a ${displaystyle lambda _ {2}}$ má nějakou velkou kladnou hodnotu, pak je nalezena hrana.
3. Li ${displaystyle lambda _ {1}}$ a ${displaystyle lambda _ {2}}$ mají velké kladné hodnoty, pak je nalezen roh.

Harris a Stephens poznamenávají, že přesný výpočet vlastních čísel je výpočetně nákladný, protože vyžaduje výpočet odmocnina a místo toho navrhnout následující funkci ${displaystyle M_ {c}}$, kde ${displaystyle kappa}$ je nastavitelný parametr citlivosti:

${displaystyle M_ {c} = lambda _ {1} lambda _ {2} -kappa, (lambda _ {1} + lambda _ {2}) ^ {2} = operatorname {det} (A) -kappa, operatorname { trace} ^ {2} (A)}$

Proto algoritmus^[6] nemusí skutečně vypočítat rozklad vlastních čísel matice ${displaystyle A}$ a místo toho stačí vyhodnotit určující a stopa z ${displaystyle A}$ najít rohy, nebo spíše zajímavé body obecně.

Shi-Tomasi^[7] rohový detektor přímo počítá ${min. zobrazení (lambda _ {1}, lambda _ {2})}$ protože za určitých předpokladů jsou rohy pro sledování stabilnější. Všimněte si, že tato metoda se také někdy označuje jako rohový detektor Kanade – Tomasi.

Hodnota ${displaystyle kappa}$ musí být stanoveno empiricky a v literatuře byly hodnoty v rozsahu 0,04–0,15 uváděny jako proveditelné.

Lze se vyhnout nastavení parametru ${displaystyle kappa}$ pomocí Noble's^[8] rohové opatření ${displaystyle M_ {c} '}$ což činí harmonický průměr vlastních čísel:

${displaystyle M_ {c} '= 2 {frac {operatorname {det} (A)} {operatorname {trace} (A) + epsilon}},}$

${displaystyle epsilon}$ být malou pozitivní konstantou.

Li ${displaystyle A}$ lze interpretovat jako přesná matice pro rohovou pozici, kovarianční matice pro rohovou pozici je ${displaystyle A ^ {- 1}}$, tj.

${displaystyle {frac {1} {langle I_ {x} ^ {2} úhel langle I_ {y} ^ {2} úhel-úhel I_ {x} I_ {y} úhel ^ {2}}} {egin {bmatrix} langle I_ {y} ^ {2} úhel & -langle I_ {x} I_ {y} úhel -langle I_ {x} I_ {y} úhel & langle I_ {x} ^ {2} konec úhlu {bmatrix}}. }$

Součet vlastních čísel ${displaystyle A ^ {- 1}}$, které lze v takovém případě vykládat jako a generalizovaná odchylka (nebo „celková nejistota“) polohy rohu, souvisí s Nobleovou mírou rohu ${displaystyle M_ {c} '}$ následující rovnicí:

${displaystyle lambda _ {1} (A ^ {- 1}) + lambda _ {2} (A ^ {- 1}) = {frac {operatorname {trace} (A)} {operatorname {det} (A)} } přibližně {frac {2} {M_ {c} '}}.}$

Förstnerův detektor rohů

Detekce rohů pomocí Förstnerova algoritmu

V některých případech si můžete přát vypočítat polohu rohu s přesností subpixelů. K dosažení přibližného řešení je Förstner^[9] Algoritmus řeší bod nejblíže ke všem tečným čarám rohu v daném okně a je řešením s nejméně čtverci. Algoritmus se spoléhá na skutečnost, že pro ideální roh se tečné čáry protínají v jednom bodě.

Rovnice tečny ${displaystyle T_ {mathbf {x '}} (mathbf {x})}$ na pixel ${displaystyle mathbf {x '}}$ darováno:

${displaystyle T_ {mathbf {x '}} (mathbf {x}) = abla I (mathbf {x'}) ^ {op} (mathbf {x} -mathbf {x '}) = 0}$

kde ${displaystyle abla I (mathbf {x '}) = [I_ {mathbf {x}}, I_ {mathbf {y}}] ^ {op}}$ je vektor přechodu obrázku ${displaystyle I}$ na ${displaystyle mathbf {x '}}$.

Bod ${displaystyle mathbf {x} _ {0}}$ nejblíže ke všem tečným čarám v okně ${displaystyle N}$ je:

${displaystyle mathbf {x} _ {0} = {underset {mathbf {x} in mathbb {R} ^ {2 imes 1}} {operatorname {argmin}}} int _ {mathbf {x '} in N} T_ { mathbf {x '}} (mathbf {x}) ^ {2} dmathbf {x'}}$

Vzdálenost od ${displaystyle mathbf {x} _ {0}}$ k dotyčnicím ${displaystyle T_ {mathbf {x '}}}$ je vážena velikostí přechodu, což dává větší důležitost tečnám procházejícím pixely se silnými přechody.

Řešení pro ${displaystyle mathbf {x} _ {0}}$:

${displaystyle {egin {aligned} mathbf {x} _ {0} & = {underset {mathbf {x} in mathbb {R} ^ {2 imes 1}} {operatorname {argmin}}} int _ {mathbf {x ' } v N} (abla I (mathbf {x '}) ^ {op} (mathbf {x} -mathbf {x'})) ^ {2} dmathbf {x '} & = {podmnožina {mathbf {x} v mathbb {R} ^ {2 imes 1}} {operatorname {argmin}}} int _ {mathbf {x '} v N} (mathbf {x} -mathbf {x'}) ^ {op} abla I (mathbf {x '}) abla I (mathbf {x'}) ^ {op} (mathbf {x} -mathbf {x '}) dmathbf {x'} & = {underset {mathbf {x} v mathbb {R} ^ {2 imes 1}} {operatorname {argmin}}}, (mathbf {x} ^ {op} Amathbf {x} -2mathbf {x} ^ {op} mathbf {b} + c) konec {zarovnáno}}}$

${displaystyle Ain mathbb {R} ^ {2 imes 2}, {extbf {b}} in mathbb {R} ^ {2 imes 1}, cin mathbb {R}}$ jsou definovány jako:

${displaystyle {egin {aligned} A & = int abla I (mathbf {x '}) abla I (mathbf {x'}) ^ {op} dmathbf {x '} mathbf {b} & = int abla I (mathbf { x '}) abla I (mathbf {x'}) ^ {op} mathbf {x '} dmathbf {x'} c & = int mathbf {x '} ^ {op} abla I (mathbf {x'}) abla I (mathbf {x '}) ^ {op} mathbf {x'} dmathbf {x '} end {zarovnáno}}}$

Minimalizace této rovnice může být provedena diferenciací s ohledem na ${displaystyle x}$ a nastavení rovné 0:

${displaystyle 2Amathbf {x} -2mathbf {b} = 0 Rightarrow Amathbf {x} = mathbf {b}}$

Všimněte si, že ${displaystyle Ain mathbb {R} ^ {2 obrázky 2}}$ je strukturní tenzor. Aby rovnice měla řešení, ${displaystyle A}$ musí být invertibilní, z čehož vyplývá, že ${displaystyle A}$ musí být celé pořadí (pořadí 2). Tedy řešení

${displaystyle x_ {0} = A ^ {- 1} mathbf {b}}$

existuje pouze tam, kde v okně existuje skutečný roh ${displaystyle N}$.

Metodika provádění automatický výběr stupnice pro tuto metodu lokalizace rohu představil Lindeberg^[10][11] minimalizací normalizovaného zbytku

${displaystyle {ilde {d}} _ {min} = {frac {c-b ^ {T} A ^ {- 1} b} {{mbox {trace}} A}}}$

přes váhy. Metoda tak má schopnost automaticky přizpůsobit úrovně měřítka pro výpočet gradientů obrazu podle úrovně šumu v obrazových datech výběrem hrubších úrovní měřítka pro hlučná obrazová data a jemnějších úrovní měřítka pro téměř ideální rohové struktury.

Poznámky:

• ${displaystyle c}$ lze zobrazit jako reziduum ve výpočtu nejmenších čtverců: pokud ${displaystyle c = 0}$, pak nedošlo k žádné chybě.
• tento algoritmus lze upravit tak, aby spočítal středy kruhových prvků změnou tečných čar na normální.

Víceúrovňový operátor Harris

Výpočet druhé momentové matice (někdy také označované jako strukturní tenzor ) ${displaystyle A}$ v operátoru Harris vyžaduje výpočet obrazové deriváty ${displaystyle I_ {x}, I_ {y}}$ v doméně obrazu, stejně jako součet nelineárních kombinací těchto derivátů přes místní sousedství. Protože výpočet derivací obvykle zahrnuje fázi vyhlazení rozsahu-prostoru, vyžaduje provozní definice Harrisova operátoru dva parametry měřítka: (i) a místní měřítko pro vyhlazení před výpočtem obrazové deriváty a (ii) an stupnice integrace pro akumulaci nelineárních operací s derivovanými operátory do integrovaného deskriptoru obrazu.

S ${displaystyle I}$ označující původní intenzitu obrazu, let ${displaystyle L}$ označit měřítko prostorové reprezentace z ${displaystyle I}$ získané konvolucí s Gaussovým jádrem

${displaystyle g (x, y, t) = {frac {1} {2 {pi} t}} e ^ {- (x ^ {2} + y ^ {2}) / 2t}}$

s parametrem místního měřítka ${displaystyle t}$:

${displaystyle L (x, y, t) = g (x, y, t) * I (x, y)}$

a nechte ${displaystyle L_ {x} = částečné _ {x} L}$ a ${displaystyle L_ {y} = částečné _ {y} L}$ označit částečné deriváty ${displaystyle L}$Dále zavést funkci Gaussova okna ${displaystyle g (x, y, s)}$ s parametrem stupnice integrace ${displaystyle s}$. Poté multi-scale sekundární matice ^[12][13][14] lze definovat jako

${displaystyle mu (x, y; t, s) = int _ {xi = -infty} ^ {infty} int _ {eta = -infty} ^ {infty} {egin {bmatrix} L_ {x} ^ {2} (x-xi, y-eta; t) & L_ {x} (x-xi, y-eta; t), L_ {y} (x-xi, y-eta; t) L_ {x} (x- xi, y-eta; t), L_ {y} (x-xi, y-eta; t) & L_ {y} ^ {2} (x-xi, y-eta; t) end {bmatrix}} g ( xi, eta; s), dxi, podrobně}$

Poté můžeme vypočítat vlastní hodnoty ${displaystyle mu}$ podobným způsobem jako vlastní čísla ${displaystyle A}$ a definovat víceúrovňová Harrisova rohová míra tak jako

${displaystyle M_ {c} (x, y; t, s) = operatorname {det} (mu (x, y; t, s)) - kappa, operatorname {trace} ^ {2} (mu (x, y; t, s))}$.

Pokud jde o výběr parametru místního měřítka ${displaystyle t}$ a parametr měřítka integrace ${displaystyle s}$, tyto parametry měřítka jsou obvykle spojeny s parametrem měřítka relativní integrace ${displaystyle gamma}$ takhle ${displaystyle s = gamma ^ {2} t}$, kde ${displaystyle gamma}$ se obvykle volí v intervalu ${displaystyle [1,2]}$.^[12][13] Můžeme tedy vypočítat víceúrovňovou Harrisovu míru ${displaystyle M_ {c} (x, y; t, gama ^ {2} t)}$ v jakémkoli měřítku ${displaystyle t}$ in scale-space to obtain a multi-scale corner detector, which responds to corner structures of varying sizes in the image domain.

V praxi je tento víceúrovňový detektor rohů často doplněn a krok výběru měřítka, kde je stupnice normalizovaný laplaciánský operátor^[11][12]

${displaystyle abla _ {norm} ^ {2} L (x, y; t) = tabla ^ {2} L (x, y, t) = t (L_ {xx} (x, y, t) + L_ { yy} (x, y, t))}$

se počítá v každém měřítku v měřítkovém prostoru a rohové body přizpůsobené měřítku s automatickým výběrem měřítka („Harris-Laplaceův operátor“) se počítají z bodů, které jsou současně:^[15]

• prostorová maxima víceúrovňové rohové míry ${displaystyle M_ {c} (x, y; t, gama ^ {2} t)}$

${displaystyle ({hat {x}}, {hat {y}}; t) = operatorname {argmaxlocal} _ {(x, y)} M_ {c} (x, y; t, gamma ^ {2} t) }$

• lokální maxima nebo minima na stupnicích stupnice normalizovaného laplaciánského operátora^[11] ${displaystyle abla _ {norm} ^ {2} (x, y, t)}$:

${displaystyle {hat {t}} = operatorname {argmaxminlocal} _ {t} abla _ {norm} ^ {2} L ({hat {x}}, {hat {y}}; t)}$

Přístup křivkou úrovně křivky

Dřívější přístup k detekci rohů je detekovat body, kde zakřivení úrovňových křivek a velikosti gradientu jsou zároveň vysoký.^[16][17] Diferenciální způsob detekce takových bodů spočívá ve výpočtu zakřivení křivky úrovně se změněnou stupnicí (součin zakřivení křivky úrovně a velikosti gradientu zvýšeného na sílu tří)

${displaystyle {ilde {kappa}} (x, y; t) = L_ {x} ^ {2} L_ {yy} + L_ {y} ^ {2} L_ {xx} -2L_ {x} L_ {y} L_ {xy}}$

a detekovat pozitivní maxima a negativní minima této diferenciální exprese v určitém měřítku ${displaystyle t}$ v měřítko prostorové reprezentace ${displaystyle L}$ původního obrázku.^[10][11] Hlavním problémem při výpočtu entity zakřivení křivky úrovně se změněnou stupnicí v jediném měřítku však je, že může být citlivá na hluk a na volbu úrovně měřítka. Lepší metodou je výpočet ${displaystyle gamma}$- normalizované zakřivení křivky úrovně se změněnou stupnicí

${displaystyle {ilde {kappa _ {norm}}} (x, y; t) = t ^ {2gamma} (L_ {x} ^ {2} L_ {yy} + L_ {y} ^ {2} L_ {xx } -2L_ {x} L_ {y} L_ {xy})}$

s ${displaystyle gamma = 7/8}$ a zjistit podepsané extrémy v měřítku a prostoru tohoto výrazu, to jsou body a měřítka, která jsou kladnými maximy a zápornými minimy s ohledem na prostor i měřítko

${displaystyle ({hat {x}}, {hat {y}}; {hat {t}}) = operatorname {argminmaxlocal} _ {(x, y; t)} {ilde {kappa}} _ {norm} ( x, y; t)}$

v kombinaci s doplňkovým krokem lokalizace ke zvládnutí nárůstu chyby lokalizace u hrubších měřítek.^[10][11][12] Tímto způsobem budou větší hodnoty měřítka spojeny se zaoblenými rohy velkého prostorového rozsahu, zatímco menší hodnoty měřítka budou spojeny s ostrými rohy s malým prostorovým rozsahem. Tento přístup je prvním rohovým detektorem s automatickým výběrem měřítka (před výše uvedeným „operátorem Harris-Laplaceovým“) a byl použit ke sledování rohů při velkém rozsahu změn v doméně obrazu^[18] a pro přizpůsobení odezev rohů hranám pro výpočet vlastností strukturálního obrazu pro geon - rozpoznávání objektů na základě.^[19]

Laplacian z Gaussian, rozdíly Gaussians a determinant hesenských úrokových bodů v měřítku a prostoru

LoG^[11][12][15] je zkratka pro Laplacian z Gaussian, Pes^[20] je zkratka pro rozdíl Gaussianů (DoG je přibližná hodnota LoG) a DoH je zkratka pro zkratku determinant pytloviny.^[11] Všechny tyto úrokově invariantní zájmové body jsou extrahovány detekcí extrémů škálovaného prostoru měřítkových normalizovaných diferenciálních výrazů, tj. Bodů v měřítkovém prostoru, kde odpovídající škálované normalizované diferenciální výrazy předpokládají lokální extrémy s ohledem na prostor i měřítko^[11]

${displaystyle ({hat {x}}, {hat {y}}; {hat {t}}) = operatorname {argminmaxlocal} _ {(x, y; t)} (D_ {norm} L) (x, y ; t)}$

kde ${displaystyle D_ {norm} L}$ označuje příslušnou stupnici normalizovanou diferenciální entitu (definovanou níže).

Tyto detektory jsou podrobněji popsány v detekce blob. Škálově normalizovaný laplacián gaussovských a rozdílových gaussovských znaků (Lindeberg 1994, 1998; Lowe 2004)^[11][12][20]

${displaystyle {egin {aligned} abla _ {norm} ^ {2} L (x, y; t) = t, (L_ {xx} + L_ {yy}) & cca {frac {tleft (L (x, y; t + Delta t) -L (x, y; t) ight)} {Delta t}} konec {zarovnaný}}}$

nemusí nutně vytvářet vysoce selektivní funkce, protože tito operátoři mohou také vést k reakcím blízko okrajů. Chcete-li zlepšit schopnost detekce rohů u rozdílů Gaussianova detektoru, použijte detektor vlastností použitý v PROSÍT^[20] systém proto používá další fázi následného zpracování, kde vlastní čísla z Hesián obrazu v detekční stupnici jsou zkoumány podobným způsobem jako v Harrisově operátoru. Pokud je poměr vlastních čísel příliš vysoký, pak je místní obraz považován za příliš podobný okraji, takže je funkce odmítnuta. Lze také definovat Lindebergův Laplacianův Gaussův detektor vlastností, který zahrnuje doplňkové prahové hodnoty na komplementárním diferenciálním invariantu k potlačení odpovědí blízko okrajů.^[21]

Škálově normalizovaný determinant hesenského operátora (Lindeberg 1994, 1998)^[11][12]

${displaystyle operatorname {det} H_ {norm} L = t ^ {2} (L_ {xx} L_ {yy} -L_ {xy} ^ {2})}$

je na druhé straně vysoce selektivní pro dobře lokalizované obrazové funkce a reaguje pouze v případě, že existují výrazné variace úrovně šedé ve dvou směrech obrazu^[11][14] a je v tomto a dalších ohledech detektorem zajímavějších bodů než Laplacian z Gaussian. Hessianův determinant je afinní kovariantní diferenciální výraz a má lepší vlastnosti výběru měřítka při afinních transformacích obrazu než laplaciánský operátor (Lindeberg 2013, 2015).^[21][22] Experimentálně z toho vyplývá, že determinant hesenských zájmových bodů má lepší vlastnosti opakovatelnosti při lokální deformaci obrazu než laplaciánské zájmové body, což vede k lepšímu výkonu shody na základě obrazu, pokud jde o vyšší skóre účinnosti a nižší skóre s 1 přesností.^[21]

Vlastnosti výběru měřítka, afinní transformační vlastnosti a experimentální vlastnosti těchto a dalších detektorů zájmových bodů v měřítku a prostoru jsou podrobně analyzovány v (Lindeberg 2013, 2015).^[21][22]

Scale-space interest points based on the Lindeberg Hessian feature measures measures

Inspirováno strukturně podobnými vlastnostmi hesenské matice ${displaystyle Hf}$ funkce ${displaystyle f}$ a matice druhého momentu (tenzor struktury) ${displaystyle mu}$, jak může např. se projeví podobnými transformačními vlastnostmi při deformacích afinního obrazu^[13][21]

${displaystyle (Hf ') = A ^ {- T}, (Hf), A ^ {- 1}}$,

${displaystyle mu '= A ^ {- T}, mu, A ^ {- 1}}$,

Lindeberg (2013, 2015)^[21][22] navrhl definovat čtyři míry síly rysů z hesenské matice souvisejícími způsoby, protože operátoři Harris a Shi-and-Tomasi jsou definováni z tenzoru struktury (matice druhého momentu). Konkrétně definoval následující nepodepsaná a podepsaná měření síly hesenu :

• nepodepsaný hesenský znak míry síly I:

${displaystyle D_ {1, norm} L = {egin {Bmatrix} t ^ {2}, (operatorname {det} HL-k, operatorname {trace} ^ {2} HL) & {mbox {if}}, operatorname { det} HL-k, operatorname {trace} ^ {2} HL> 0 0 & {mbox {jinak}} konec {Bmatrix}}}$

• podepsané měření hesenské funkce I:

${displaystyle {ilde {D}} _ {1, norm} L = {egin {Bmatrix} t ^ {2}, (operatorname {det} HL-k, operatorname {trace} ^ {2} HL) & {mbox { if}}, operatorname {det} HL-k, operatorname {trace} ^ {2} HL> 0 t ^ {2}, (operatorname {det} HL + k, operatorname {trace} ^ {2} HL) & {mbox {if}}, operatorname {det} HL + k, operatorname {trace} ^ {2} HL <0 0 & {mbox {jinak}} konec {Bmatrix}}}$

• nepodepsané hesenské opatření míry síly II:

${displaystyle D_ {2, norm} L = t, operatorname {min} (| lambda _ {1} (HL) |, | lambda _ {2} (HL) |)}$

• podepsané hesenské opatření síly II:

${displaystyle {ilde {D}} _ {2, norm} L = {egin {Bmatrix} t, lambda _ {1} (HL) & {mbox {if}}, | lambda _ {1} (HL) | < | lambda _ {2} (HL) | t, lambda _ {2} (HL) & {mbox {if}}, | lambda _ {2} (HL) | <| lambda _ {1} (HL) | t, (lambda _ {1} (HL) + lambda _ {2} (HL)) / 2 a {mbox {jinak}} konec {Bmatrix}}}$

kde ${displaystyle operatorname {trace} HL = L_ {xx} + L_ {yy}}$ a ${displaystyle operatorname {det} HL = L_ {xx} L_ {yy} -L_ {xy} ^ {2}}$ označit stopu a determinant hesenské matice ${displaystyle HL}$ reprezentace měřítka-prostoru ${displaystyle L}$ v jakémkoli měřítku ${displaystyle t}$, zatímco

${displaystyle lambda _ {1} (HL) = L_ {pp} = {frac {1} {2}} vlevo (L_ {xx} + L_ {yy} - {sqrt {(L_ {xx} -L_ {yy}) ) ^ {2} + 4L_ {xy} ^ {2}}} vpravo)}$

${displaystyle lambda _ {2} (HL) = L_ {qq} = {frac {1} {2}} vlevo (L_ {xx} + L_ {yy} + {sqrt {(L_ {xx} -L_ {yy}) ) ^ {2} + 4L_ {xy} ^ {2}}} vpravo)}$

označit vlastní čísla hesenské matice.^[23]

Nepodepsaný hesenský znak míry síly ${displaystyle D_ {1, norma} L}$ reaguje na lokální extrémy kladnými hodnotami a není citlivý na sedlové body, zatímco míra síly podepsaného hesenského znaku ${displaystyle {ilde {D}} _ {1, norma} L}$ reaguje navíc na sedlové body zápornými hodnotami. Nepodepsaný hesenský znak míry síly ${displaystyle D_ {2, norma} L}$ je necitlivý na místní polaritu signálu, zatímco podepsaný hesenský znak měří sílu ${displaystyle {ilde {D}} _ {2, norm} L}$ reaguje na místní polaritu signálu znaménkem jeho výstupu.

In Lindeberg (2015)^[21] tyto čtyři diferenciální entity byly kombinovány s výběrem lokálního měřítka na základě detekce extrémů měřítka-prostoru

${displaystyle ({hat {x}}, {hat {y}}; {hat {t}}) = operatorname {argminmaxlocal} _ {(x, y; t)} (D_ {norm} L) (x, y ; t)}$

nebo měřítkové propojení. Podepsaná a nepodepsaná hesenská funkce navíc obsahují míry síly ${displaystyle D_ {2, norma} L}$ a ${displaystyle {ilde {D}} _ {2, norm} L}$ byly kombinovány s doplňkovým prahováním na ${displaystyle D_ {1, norma} L> 0}$.

Experimenty s párováním obrázků při transformacích škálování na datové sadě plakátů s 12 plakáty s vícepohledovým přizpůsobováním transformací škálování až do faktoru změny měřítka 6 a variací směru prohlížení až do úhlu sklonu 45 stupňů s místními deskriptory obrazu definovanými z přeformulování čisté deskriptory obrazu v operátorech SIFT a SURF k měření obrazu pomocí operátorů Gaussových derivátů (Gauss-SIFT a Gauss-SURF) namísto původního SIFT definovaného z obrazové pyramidy nebo původního SURF definovaného z vln Haar, bylo ukázáno že detekce zájmového bodu v měřítku a prostoru na základě nepodepsaného měření síly hesenské funkce ${displaystyle D_ {1, norma} L}$ umožnil nejlepší výkon a lepší výkon než úrokové body v měřítku a prostoru získané z determinantu pytloviny ${displaystyle operatorname {det} H_ {norm} L = t ^ {2}, (L_ {xx} L_ {yy} -L_ {xy} ^ {2})}$. Měření síly nepodepsaného hesenské funkce ${displaystyle D_ {1, norma} L}$, podepsané měření hesenské funkce ${displaystyle {ilde {D}} _ {1, norma} L}$ a Hessianův determinant ${displaystyle operatorname {det} H_ {norm} L}$ umožnil lepší výkon než Laplacian z Gaussian ${displaystyle abla _ {norm} ^ {2} L = t, (L_ {xx} + L_ {yy})}$. V kombinaci s škálováním a doplňkovým prahováním ${displaystyle D_ {1, norma} L> 0}$, podepsané měření hesenské funkce ${displaystyle {ilde {D}} _ {2, norm} L}$ navíc umožnil lepší výkon než Laplacian z Gaussian ${displaystyle abla _ {norm} ^ {2} L}$.

Dále se ukázalo, že všechny tyto diferenciální detektory zájmových bodů v měřítku a prostoru definované z hesenské matice umožňují detekci většího počtu zájmových bodů a lepší shodu výkonu ve srovnání s operátory Harris a Shi-and-Tomasi definovanými ze struktury tensor (sekundární matice).

Teoretická analýza vlastností pro výběr měřítka těchto čtyř měřítek hesenské funkce a dalších diferenciálních entit pro detekci zájmových bodů měřítko-prostor, včetně Laplaciána z Gaussova a determinantu Hessiana, je uvedena v Lindebergovi (2013)^[22] a analýza jejich afinních transformačních vlastností a experimentálních vlastností v Lindeberg (2015).^[21]

Provozovatelé zájmových bodů přizpůsobení afinitě

Zájmové body získané od operátora Harris s více měřítky s automatickým výběrem měřítka jsou invariantní k překladům, rotacím a jednotným změnám měřítka v prostorové doméně. Obrazy, které tvoří vstup do systému počítačového vidění, však také podléhají perspektivním zkreslením. Chcete-li získat operátora zájmového bodu, který je robustnější vůči perspektivním transformacím, přirozeným přístupem je navrhnout detektor funkcí, který je invariantní k afinním transformacím. V praxi lze afinní neměnné úrokové body získat aplikací afinní tvarová adaptace kde je tvar vyhlazovacího jádra iterativně deformován tak, aby odpovídal místní struktuře obrazu kolem zajímavého bodu nebo ekvivalentně lokální obrazová oprava, je iterativně deformován, zatímco tvar vyhlazovacího jádra zůstává rotačně symetrický (Lindeberg 1993, 2008; Lindeberg a Garding 1997; Mikolajzcyk a Schmid 2004).^{[12][13][14][15]} Kromě běžně používaného víceúrovňového operátoru Harris lze tedy použít afinní tvarovou adaptaci na další detektory rohů, jak jsou uvedeny v tomto článku, stejně jako na detektory diferenciálních blobů jako je Laplacian / rozdíl Gaussova operátoru, determinant Hessianu^[14] a operátor Hessian – Laplace.

Algoritmus detekce rohů Wang a Brady

Wang a Brady^[24] detektor považuje obraz za povrch a hledá místa, kde je velký zakřivení podél okraje obrazu. Jinými slovy, algoritmus hledá místa, kde hrana rychle mění směr. Rohové skóre, ${displaystyle C}$, darováno:

${displaystyle C = left ({frac {delta ^ {2} I} {delta {f {{t} ^ {2}}}}} ight) ^ {2} -c | abla I | ^ {2},}$

kde ${displaystyle {f {t}}}$ je jednotkový vektor kolmý k přechodu a ${displaystyle c}$ určuje, jak je hranní fobický detektor. Autoři také poznamenávají, že ke snížení hluku je nutné vyhlazení (doporučuje se Gaussian).

Vyhlazení také způsobí posunutí rohů, takže autoři odvozují výraz pro posunutí 90stupňového rohu a použijí to jako korekční faktor pro detekované rohy.

Rohový detektor SUSAN

SUSAN^[25] je zkratka pro nejmenší jednohodnotový segment asimilující jádro. Tato metoda je předmětem patentu Spojeného království z roku 1994, který již není v platnosti.^[26]

Pro detekci funkcí umístí SUSAN kruhovou masku nad testovaný pixel (jádro). Oblast masky je ${displaystyle M}$, a pixel v této masce je reprezentován ${displaystyle {vec {m}} v M}$. Jádro je v ${displaystyle {vec {m}} _ {0}}$. Každý pixel je porovnán s jádrem pomocí funkce porovnání:

${displaystyle c ({vec {m}}) = e ^ {- vlevo ({frac {I ({vec {m}}) - I ({vec {m}} _ {0})} {t}} vpravo ) ^ {6}}}$

kde ${displaystyle t}$ je mezní hodnota rozdílu jasu,^[27] ${displaystyle I}$ je jas pixelu a síla exponenta byla stanovena empiricky. Tato funkce má vzhled vyhlazeného cylindr nebo obdélníková funkce. Plocha SUSANu je dána:

${displaystyle n (M) = součet _ {{vec {m}} v M} c ({vec {m}})}$

Li ${displaystyle c}$ je tedy pravoúhlá funkce ${displaystyle n}$ je počet pixelů v masce, které jsou uvnitř ${displaystyle t}$ jádra. Odpověď operátora SUSAN je dána:

${displaystyle R (M) = {egin {cases} g-n (M) & {mbox {if}} n (M)$

kde ${displaystyle g}$ se nazývá „geometrický práh“. Jinými slovy, operátor SUSAN má kladné skóre pouze v případě, že je oblast dostatečně malá. Nejmenší lokálně SUSAN lze najít pomocí maximálního potlačení a toto je úplný operátor SUSAN.

Hodnota ${displaystyle t}$ určuje, jak podobné body musí být s jádrem, než se považují za součást jednohodnotového segmentu. Hodnota ${displaystyle g}$ určuje minimální velikost segmentu bez hodnoty. Li ${displaystyle g}$ je dostatečně velký, pak se stane detektor hran.

Pro detekci rohů se používají dva další kroky. Za prvé těžiště SUSAN je nalezen. Správný roh bude mít těžiště daleko od jádra. Druhý krok trvá na tom, že všechny body na linii od jádra přes těžiště k okraji masky jsou v SUSANU.

Detektor rohů Trajkovic a Hedley

Podobným způsobem jako SUSAN, tento detektor^[28] přímo testuje, zda je oprava pod pixelem podobná zkoumáním blízkých pixelů. ${displaystyle {vec {c}}}$ je uvažovaný pixel a ${displaystyle {vec {p}} v P}$ je bod na kruhu ${displaystyle P}$ soustředěný kolem ${displaystyle {vec {c}}}$. Bod ${displaystyle {vec {p '}}}$ je opačný bod než ${displaystyle {vec {p}}}$ podél průměru.

Funkce odezvy je definována jako:

${displaystyle r ({vec {c}}) = min _ {{vec {p}} v P} quad ((I ({vec {p}}) - I ({vec {c}}))) {2 } + (I ({vec {p '}}) - I ({vec {c}})) ^ {2})}$

To bude velké, když neexistuje žádný směr, ve kterém je středový pixel podobný průměru dvou blízkých pixelů. ${displaystyle P}$ je diskretizovaný kruh (a Bresenhamský kruh ), tak interpolace se používá pro střední průměry, aby poskytla isotropnější odezvu. Protože jakýkoli výpočet dává horní hranici na ${min. styl zobrazení}$, nejprve se zkontroluje vodorovný a svislý směr, aby se zjistilo, zda má smysl pokračovat v úplném výpočtu ${displaystyle c}$.

Detektory funkcí založené na AST

AST je zkratka, která znamená zrychlený segmentový test. Tento test je uvolněnou verzí rohového kritéria SUSAN. Namísto vyhodnocení kruhového disku se zobrazí pouze pixely v a Bresenhamský kruh poloměru ${displaystyle r}$ kolem kandidátského bodu. Li ${displaystyle n}$ souvislé pixely jsou minimálně jasnější než jádro ${displaystyle t}$ nebo všechny tmavší než jádro o ${displaystyle t}$, pak je pixel pod jádrem považován za prvek. Uvádí se, že tento test poskytuje velmi stabilní funkce.^[29] The choice of the order in which the pixels are tested is a so-called Twenty Questions problem. Building short decision trees for this problem results in the most computationally efficient feature detectors available.

The first corner detection algorithm based on the AST is FAST (features from accelerated segment test ).^[29] Ačkoli ${displaystyle r}$ can in principle take any value, FAST uses only a value of 3 (corresponding to a circle of 16 pixels circumference), and tests show that the best results are achieved with ${displaystyle n}$ being 9. This value of ${displaystyle n}$ is the lowest one at which edges are not detected. The order in which pixels are tested is determined by the Algoritmus ID3 from a training set of images. Confusingly, the name of the detector is somewhat similar to the name of the paper describing Trajkovic and Hedley's detector.

Automatic synthesis of detectors

Trujillo and Olague^[30] introduced a method by which genetic programming is used to automatically synthesize image operators that can detect interest points. The terminal and function sets contain primitive operations that are common in many previously proposed man-made designs. Zdatnost measures the stability of each operator through the repeatability rate, and promotes a uniform dispersion of detected points across the image plane. The performance of the evolved operators has been confirmed experimentally using training and testing sequences of progressively transformed images. Hence, the proposed GP algorithm is considered to be human-competitive for the problem of interest point detection.

Spatio-temporal interest point detectors

The Harris operator has been extended to space-time by Laptev and Lindeberg.^[31]Nechat ${displaystyle mu}$ denote the spatio-temporal second-moment matrix defined by

${displaystyle A=sum _{u}sum _{v}sum _{w}h(u,v,w){ egin{bmatrix}L_{x}(u,v,w)^{2}&L_{x}(u,v,w)L_{y}(u,v,w)&L_{x}(u,v,w)L_{t}(u,v,w)L_{x}(u,v,w)L_{y}(u,v,w)&L_{y}(u,v,w)^{2}&L_{y}(u,v,w)L_{t}(u,v,w)L_{x}(u,v,w)L_{t}(u,v,w)&L_{y}(u,v,w)L_{t}(u,v,w)&L_{t}(u,v,w)^{2}end{bmatrix}}={ egin{bmatrix}langle L_{x}^{2}angle &langle L_{x}L_{y}angle &langle L_{x}L_{t}angle langle L_{x}L_{y}angle &langle L_{y}^{2}angle &langle L_{y}L_{t}angle langle L_{x}L_{t}angle &langle L_{y}L_{t}angle &langle L_{t}^{2}angle end{bmatrix}}}$

Then, for a suitable choice of ${displaystyle k<1/27}$, spatio-temporal interest points are detected from spatio-temporal extrema of the following spatio-temporal Harris measure:

${displaystyle H=operatorname {det} (mu )-kappa ,operatorname {trace} ^{2}(mu ).}$

The determinant of the Hessian operator has been extended to joint space-time by Willems et al ^[32] and Lindeberg,^[33] leading to the following scale-normalized differential expression:

${displaystyle operatorname {det} (H_{(x,y,t),norm}L)=,s^{2gamma _{s}} au ^{gamma _{ au }}left((L_{xx}L_{yy}L_{tt}+2L_{xy}L_{xt}L_{yt}-L_{xx}L_{yt}^{2}-L_{yy}L_{xt}^{2}-L_{tt}L_{xy}^{2}ight).}$

In the work by Willems et al,^[32] a simpler expression corresponding to ${displaystyle gamma _{s}=1}$ a ${displaystyle gamma _{ au }=1}$ byl použit. In Lindeberg,^[33] it was shown that ${displaystyle gamma _{s}=5/4}$ a ${displaystyle gamma _{ au }=5/4}$ implies better scale selection properties in the sense that the selected scale levels obtained from a spatio-temporal Gaussian blob with spatial extent ${displaystyle s=s_{0}}$ and temporal extent ${displaystyle au = au _{0}}$ will perfectly match the spatial extent and the temporal duration of the blob, with scale selection performed by detecting spatio-temporal scale-space extrema of the differential expression.

The Laplacian operator has been extended to spatio-temporal video data by Lindeberg,^[33] leading to the following two spatio-temporal operators, which also constitute models of receptive fields of non-lagged vs. lagged neurons in the LGN:

${displaystyle partial _{t,norm}(abla _{(x,y),norm}^{2}L)=s^{gamma _{s}} au ^{gamma _{ au }/2}(L_{xxt}+L_{yyt}),}$

${displaystyle partial _{tt,norm}(abla _{(x,y),norm}^{2}L)=s^{gamma _{s}} au ^{gamma _{ au }}(L_{xxtt}+L_{yytt}).}$

For the first operator, scale selection properties call for using ${displaystyle gamma _{s}=1}$ a ${displaystyle gamma _{ au }=1/2}$, if we want this operator to assume its maximum value over spatio-temporal scales at a spatio-temporal scale level reflecting the spatial extent and the temporal duration of an onset Gaussian blob. For the second operator, scale selection properties call for using ${displaystyle gamma _{s}=1}$ a ${displaystyle gamma _{ au }=3/4}$, if we want this operator to assume its maximum value over spatio-temporal scales at a spatio-temporal scale level reflecting the spatial extent and the temporal duration of a blinking Gaussian blob.

Colour extensions of spatio-temporal interest point detectors have been investigated by Everts et al.^[34]

Bibliografie

Referenční implementace

This section provides external links to reference implementations of some of the detectors described above. These reference implementations are provided by the authors of the paper in which the detector is first described. These may contain details not present or explicit in the papers describing the features.

• DoG detection (jako součást SIFT Systém), Okna a x86 Linux executables
• Harris-Laplace, statické Linux spustitelné soubory. Also contains DoG and LoG detectors and affine adaptation for all detectors included.
• FAST detector, C, C++, MATLAB source code and executables for various operating systems and architectures.
• lip-vireo,[LoG, DoG, Harris-Laplacian, Hessian and Hessian-Laplacian],[SIFT, flip invariant SIFT, PCA-SIFT, PSIFT, Steerable Filters, SPIN][Linux, Windows and SunOS] executables.
• SUSAN Low Level Image Processing, C source code.
• Online Implementation of the Harris Corner Detector - IPOL

Viz také

• blob detection
• affine shape adaptation
• měřítko prostoru
• detekce hřebene
• interest point detection
• feature detection (computer vision)
• obrazové deriváty

externí odkazy

• Lindeberg, Tony (2001) [1994], "Corner detection", Encyclopedia of Mathematics, Stiskněte EMS
• Brostow, "Corner Detection -- UCL Computer Science"