Гаррісів виявляч кутів

Кут (англ. corner) — це точка, локальний окіл якої перебуває у двох переважних і різних напрямках контурів. Іншими словами, кут можливо інтерпретувати як з'єднання двох контурів, де контур (англ. edge) — це раптова зміна яскравості зображення.^[3] Кути — важливі ознаки на зображенні, і їх зазвичай називають особливими точками, інваріантними щодо переміщення, обертання та освітлення. Хоч кути й становлять лише невеликий відсоток зображення, вони містять найважливіші ознаки для відновлення інформації зображення, і їх можливо використовувати для мінімізування обсягу оброблюваних даних для відстежування руху, зшивання зображень^[en], побудови двовимірних мозаїк, стереобачення, подання зображень та інших суміжних областей комп'ютерного бачення.

Щоби вловлювати кути на зображеннях, дослідники запропонували багато різних виявлячів кутів, у тому числі оператор Канаде — Лукаса — Томазі (КЛТ) та оператор Гарріса, що є найпростішими, найефективнішими та найнадійнішими для використання у виявлянні кутів. Ці обидві популярні методології тісно пов'язані з локальною структурною матрицею, та ґрунтуються на ній. Порівняно з виявлячем кутів Канаде — Лукаса — Томазі, Гаррісів виявляч кутів забезпечує добру повторюваність за змін освітлення та обертання, й відтак його частіше використовують для стереозіставляння та пошуку базами даних зображень. Незважаючи на все ще наявні недоліки та обмеження, Гаррісів виявляч кутів залишається важливою та фундаментальною методикою для багатьох застосунків комп'ютерного бачення.

Без втрати загальності, ми розглянемо використання двовимірного зображення у відтінках сірого. Нехай це зображення задано через ${\displaystyle I}$ . Розгляньмо взяття фрагменту зображення ${\displaystyle (x,y)\in W}$ (вікно, англ. window) та його зміщення на ${\displaystyle (\Delta x,\Delta y)}$ . Суму квадратів різниць (СКР) між цими двома фрагментами, позначувану через ${\displaystyle f}$ , задають як

${\displaystyle f(\Delta x,\Delta y)={\underset {(x_{k},y_{k})\in W}{\sum }}\left(I(x_{k},y_{k})-I(x_{k}+\Delta x,y_{k}+\Delta y)\right)^{2}}$

${\displaystyle I(x+\Delta x,y+\Delta y)}$ можливо наблизити розкладом Тейлора. Нехай ${\displaystyle I_{x}}$ та ${\displaystyle I_{y}}$  — частинні похідні ${\displaystyle I}$ , такі, що

${\displaystyle I(x+\Delta x,y+\Delta y)\approx I(x,y)+I_{x}(x,y)\Delta x+I_{y}(x,y)\Delta y}$

Це дає наближення

${\displaystyle f(\Delta x,\Delta y)\approx {\underset {(x,y)\in W}{\sum }}\left(I_{x}(x,y)\Delta x+I_{y}(x,y)\Delta y\right)^{2},}$

яке можливо записати у матричному вигляді:

${\displaystyle f(\Delta x,\Delta y)\approx {\begin{pmatrix}\Delta x&\Delta y\end{pmatrix}}M{\begin{pmatrix}\Delta x\\\Delta y\end{pmatrix}},}$

де M — структурний тензор,

${\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}}}$

Зазвичай алгоритм Гарріса виявляння кутів можливо розділити на п'ять кроків.

1. З кольору до відтінків сірого
2. Обчислення просторової похідної
3. Налаштування структурного тензора
4. Обчислення гаррісового відгуку
5. Пригнічення немаксимумів

Якщо ми використовуємо гаррісів виявляч кутів у кольоровому зображенні, першим кроком буде перетворити його на зображення у відтінках сірого, що підвищить швидкість обробки.

Значення пікселя у відтінках сірого можливо обчислювати як зважену суму значень R, B та G кольорового зображення,

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

де, наприклад,

${\displaystyle w_{R}=0.299,\ w_{G}=0.587,\ w_{B}=1-(w_{R}+w_{G})=0.114.}$

Далі ми знаходимо похідні за x та за y, ${\displaystyle I_{x}(x,y)}$ та ${\displaystyle I_{y}(x,y)}$ .

Із ${\displaystyle I_{x}(x,y)}$ та ${\displaystyle I_{y}(x,y)}$ ми можемо побудувати структурний тензор ${\displaystyle M}$ .

Для ${\displaystyle x\ll y}$ маємо ${\displaystyle {\tfrac {x\cdot y}{x+y}}=x{\tfrac {1}{1+x/y}}\approx x.}$ На цьому кроці ми обчислюємо найменше власне значення структурного тензора, використовуючи це наближення:

${\displaystyle \lambda _{\min }\approx {\frac {\lambda _{1}\lambda _{2}}{(\lambda _{1}+\lambda _{2})}}={\frac {\det(M)}{\operatorname {tr} (M)}}}$

де слід ${\displaystyle \mathrm {tr} (M)=m_{11}+m_{22}}$ .

Нижче наведено інше часто використовуване обчислення гаррісового відгуку,

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

де ${\displaystyle k}$  — емпірично встановлювана стала; ${\displaystyle k\in [0.04,0.06]}$ .

Щоби обирати оптимальні значення для вказування кутів, ми знаходимо локальні максимуми як кути в межах вікна, що є фільтром 3 на 3.

1. Виявляч кутів Гарріса — Лапласа^[9]
2. Виявляч кутів на основі диференціального морфологічного розкладу^[10]
3. Виявляч кутів на основі багатомасштабного двобічного структурного тензора^[11]

1. Вирівнювання, зшивання^[en] та зіставляння зображень^[12]
2. Створення двовимірних мозаїк^[13]
3. Моделювання та відбудова тривимірних сцен^[14]
4. Виявляння руху^[en][15]
5. Розпізнавання об'єктів^[en][16]
6. Індексування та пошук зображень за вмістом^[17]
7. Відстежування у відео^[18]

• Структурний тензор
• Гаррісів афінний виявляч областей
• Виявляння кутів
• Виявляння ознак (комп'ютерне бачення)
• Комп'ютерне бачення
• Перелік тем комп'ютерного бачення^[en]

• «Вивчення OpenCV на прикладах: Гаррісове виявляння кутів» (англ.)
• «Гаррісове виявляння кутів — документація OpenCV» (англ.)
• Гаррісове виявляння кутів — навчальні посібники Python OpenCV. Архів оригіналу за 7 травня 2021. (англ.)
• Інтерактивне втілення гаррісового виявляча кутів — IPOL (англ.)