Harrisův rohový detektor - Harris Corner Detector

Harrisův rohový detektor je detekce rohů operátor, který se běžně používá v počítačové vidění algoritmy pro extrakci rohů a odvození funkce obrázku. Poprvé ji představili Chris Harris a Mike Stephens v roce 1988 po vylepšení Moravecův rohový detektor.^[1] Ve srovnání s předchozím, Harrisův detektor rohů bere v úvahu rozdíl skóre rohu s přímým odkazem na směr, namísto použití posunovacích skvrn pro každých 45 stupňů, a ukázalo se, že je přesnější při rozlišování hran a rohů .^[2] Od té doby byl vylepšen a přijat v mnoha algoritmech k předzpracování obrázků pro následné aplikace.

Úvod

Roh je bod, jehož místní sousedství stojí ve dvou dominantních a odlišných směrech hran. Jinými slovy, roh lze interpretovat jako spojení dvou hran, kde hranou je náhlá změna jasu obrazu.^[3] Rohy jsou důležitými prvky obrazu a obecně se označují jako zájmové body, které jsou neměnné pro translaci, rotaci a osvětlení. Přestože rohy tvoří jen malé procento obrazu, obsahují nejdůležitější funkce při obnovování obrazových informací a lze je použít k minimalizaci množství zpracovaných dat pro sledování pohybu, šití obrazu, vytváření 2D mozaik, stereofonní vidění, obrazová reprezentace a další související oblasti počítačového vidění.

Aby bylo možné zachytit rohy z obrazu, vědci navrhli mnoho různých detektorů rohů, včetně Kanade-Lucas-Tomasi (KLT) operátor a operátor Harris, které jsou nejjednodušší, nejúčinnější a nejspolehlivější pro použití při detekci rohů. Tyto dvě populární metodiky jsou úzce spjaty s maticí místní struktury a jsou na ní založeny. Ve srovnání s rohovým detektorem Kanade-Lucas-Tomasi poskytuje Harrisův rohový detektor dobrou opakovatelnost při měnícím se osvětlení a rotaci, a proto se častěji používá při stereofonním porovnávání a načítání databáze obrázků. Ačkoli stále existují nevýhody a omezení, Harrisův detektor rohů je stále důležitou a základní technikou pro mnoho aplikací počítačového vidění.

Vývoj algoritmu Harris Corner Detection Algorithm ^[1]

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 pořízení obrazové opravy ${ displaystyle (x, y) ve W}$(okno) a posunutí o ${ displaystyle ( Delta x, Delta y)}$. The součet čtvercových rozdílů (SSD) mezi těmito dvěma opravami, označené ${ displaystyle f}$, je dána:

${ displaystyle f ( Delta x, Delta y) = { podmnožina {(x_ {k}, y_ {k}) v W} { součet}} vlevo (I (x_ {k}, y_ { k}) - I (x_ {k} + Delta x, y_ {k} + Delta y) vpravo) ^ {2}}$

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

${ Displaystyle I (x + Delta x, y + Delta y) cca I (x, y) + I_ {x} (x, y) Delta x + I_ {y} (x, y) Delta y}$

Tím se vytvoří aproximace

${ displaystyle f ( Delta x, Delta y) přibližně { podmnožina {(x, y) v W} { součet}} vlevo (I_ {x} (x, y) Delta x + I_ {y} (x, y) Delta y vpravo) ^ {2},}$

které lze zapsat v matici:

${ displaystyle f ( Delta x, Delta y) přibližně { begin {pmatrix} Delta x & Delta y end {pmatrix}} M { begin {pmatrix} Delta x Delta y end {pmatrix}},}$

kde M je strukturní tenzor,

${ displaystyle M = { underset {(x, y) in W} { sum}} { begin {bmatrix} I_ {x} ^ {2} & I_ {x} I_ {y} I_ {x } I_ {y} & I_ {y} ^ {2} end {bmatrix}} = { begin {bmatrix} { underset {(x, y) in W} { sum}} I_ {x} ^ { 2} & { underset {(x, y) in W} { sum}} I_ {x} I_ {y} { underset {(x, y) in W} { sum}} I_ {x} I_ {y} & { underset {(x, y) in W} { sum}} I_ {y} ^ {2} end {bmatrix}}}$

Proces algoritmu Harris Corner Detection Algorithm^[4][5][6]

Algoritmus Harrisova detektoru rohů lze běžně rozdělit do pěti kroků.

1. Barva ve stupních šedi
2. Výpočet prostorové derivace
3. Nastavení tenzoru struktury
4. Harrisův výpočet odezvy
5. Non-maximální potlačení

Barva ve stupních šedi

Pokud použijeme Harrisův rohový detektor v barevném obrazu, je prvním krokem jeho převedení na obraz ve stupních šedi, což zvýší rychlost zpracování.

Hodnotu pixelu šedé lze vypočítat jako vážený součet hodnot R, B a G barevného obrázku,

${ displaystyle sum _ {C , in , {R, B, G }} w_ {C} cdot C}$,

kde např.

${ displaystyle w_ {R} = 0,299, w_ {B} = 0,587, w_ {G} = 1- (w_ {R} + w_ {B}).}$

Výpočet prostorové derivace

Dále budeme počítat ${ displaystyle I_ {x} (x, y)}$ a ${ displaystyle I_ {y} (x, y)}$.

Nastavení tenzoru struktury

S ${ displaystyle I_ {x} (x, y)}$ , ${ displaystyle I_ {y} (x, y)}$, můžeme sestrojit tenzor struktury ${ displaystyle M}$.

Harrisův výpočet odezvy

Pro ${ displaystyle x ll y}$, jeden má ${ displaystyle { tfrac {x cdot y} {x + y}} = x { tfrac {1} {1 + x / y}} přibližně x.}$V tomto kroku vypočítáme nejmenší vlastní hodnotu tenzoru struktury pomocí této aproximace:

${ displaystyle lambda _ {min} přibližně { frac { lambda _ {1} lambda _ {2}} {( lambda _ {1} + lambda _ {2})}} = { frac { det (M)} { mathrm {tr} (M)}}}$

se stopou ${ displaystyle mathrm {tr} (M) = m_ {11} + m_ {22}}$.

Další běžně používaný výpočet Harrisovy odpovědi je uveden níže,

${ displaystyle R = lambda _ {1} lambda _ {2} -k cdot ( lambda _ {1} + lambda _ {2}) ^ {2} = det (M) -k cdot mathrm {tr} (M) ^ {2}}$

kde ${ displaystyle k}$ je empiricky určená konstanta; ${ displaystyle k in [0,04,0,06]}$ .

Non-maximální potlačení

Abychom získali optimální hodnoty pro označení rohů, najdeme lokální maxima jako rohy v okně, což je filtr 3 ku 3.

Zlepšení^[7][8]

1. Harris-Laplaceův rohový detektor^[9]
2. Rohový detektor založený na diferenciálním morfologickém rozkladu^[10]
3. Rohový detektor založený na víceúrovňovém dvoustranném strukturním tenzoru^[11]

Aplikace

1. Zarovnání obrazu, šití a registrace^[12]
2. Tvorba 2D mozaik^[13]
3. Modelování a rekonstrukce 3D scén^[14]
4. Detekce pohybu^[15]
5. Rozpoznávání objektů^[16]
6. Indexování obrázků a vyhledávání podle obsahu^[17]
7. Sledování videa^[18]

Viz také

• Tenzor struktury
• Harris detektor afinní oblasti
• Detekce rohů
• Detekce funkcí (počítačové vidění)
• Počítačové vidění
• Seznam témat počítačového vidění

Reference

externí odkazy

• „Naučte se OpenCV podle příkladů: Harris Corner Detection“
• „Harris Corner Detection - OpenCV Documentation“
• „Harris Corner Detection - OpenCV-Python Tutorials“
• Online implementace detektoru Harris Corner - IPOL