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

Га́ррісів виявля́ч куті́в (Шаблон:Lang-en) — це оператор виявляння кутів, який зазвичай використовують в алгоритмах комп'ютерного бачення для виділяння кутів та висновування ознак зображення. Його вперше впровадили Кріс Гарріс та Майк Стівенс 1988 року через вдосконалення виявляча кутів Моравека. Порівняно з попереднім, гаррісів виявляч кутів враховує диференціал кутової оцінки (Шаблон:Lang-en) безпосередньо з напрямком, замість використовувати зміщувані фрагменти для кожного з 45-градусних кутів, і було доведено, що у розрізнюванні контурів та кутів він точніший. Відтоді його було вдосконалено та використано в багатьох алгоритмах попередньої обробки зображень для наступних застосувань.

Введення

Кут (Шаблон:Lang-en) — це точка, локальний окіл якої перебуває у двох переважних і різних напрямках контурів. Іншими словами, кут можливо інтерпретувати як з'єднання двох контурів, де контур (Шаблон:Lang-en) — це раптова зміна яскравості зображення. Кути — важливі ознаки на зображенні, і їх зазвичай називають особливими точками, інваріантними щодо переміщення, обертання та освітлення. Хоч кути й становлять лише невеликий відсоток зображення, вони містять найважливіші ознаки для відновлення інформації зображення, і їх можливо використовувати для мінімізування обсягу оброблюваних даних для відстежування руху, Шаблон:Нп, побудови двовимірних мозаїк, стереобачення, подання зображень та інших суміжних областей комп'ютерного бачення.

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

Розробка алгоритму Гарріса виявляння кутів

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

$f(\mathrm{\Delta }x,\mathrm{\Delta }y)=\sum (x_k,y_k)\in W{(I(x_k,y_k)-I(x_k+\mathrm{\Delta }x,y_k+\mathrm{\Delta }y))}^2$

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

$I(x+\mathrm{\Delta }x,y+\mathrm{\Delta }y)\approx I(x,y)+I_x(x,y)\mathrm{\Delta }x+I_y(x,y)\mathrm{\Delta }y$

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

$f(\mathrm{\Delta }x,\mathrm{\Delta }y)\approx \sum (x,y)\in W{(I_x(x,y)\mathrm{\Delta }x+I_y(x,y)\mathrm{\Delta }y)}^2,$

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

$f(\mathrm{\Delta }x,\mathrm{\Delta }y)\approx \left(\begin{array}{cc}\mathrm{\Delta }x& \mathrm{\Delta }y\end{array}\right)M\left(\begin{array}{c}\mathrm{\Delta }x\\ \mathrm{\Delta }y\end{array}\right),$

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

$M=\sum (x,y)\in W\left[\begin{array}{cc}{I}_x^2& I_x{I}_y\\ I_x{I}_y& I_y^2\end{array}\right]=\left[\begin{array}{cc}\sum (x,y)\in W{I}_x^2& \sum (x,y)\in W{I}_x{I}_y\\ \sum (x,y)\in W{I}_x{I}_y& \sum (x,y)\in W{I}_y^2\end{array}\right]$

Процес алгоритму Гарріса виявляння кутів

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

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

З кольору до відтінків сірого

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

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

$\sum _{C\in \{R,G,B\}}{w}_C\cdot C$ ,

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

$w_R=0.299,w_G=0.587,w_B=1-(w_R+w_G)=0.114.$

Обчислення просторової похідної

Далі ми знаходимо похідні за x та за y, $I_x(x,y)$ та $I_y(x,y)$.

Налаштування структурного тензора

Із $I_x(x,y)$ та $I_y(x,y)$ ми можемо побудувати структурний тензор $M$.

Обчислення гаррісового відгуку

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

${\lambda }_{\min }\approx \frac{{\lambda }_1{\lambda }_2}{({\lambda }_1+{\lambda }_2)}=\frac{\det (M)}{\mathrm{tr}(M)}$

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

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

$R={\lambda }_1{\lambda }_2-k({\lambda }_1+{\lambda }_2{)}^2=\det (M)-k\mathrm{tr}(M{)}^2$

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

Пригнічування немаксимумів

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

Вдосконалення

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

Застосування

1. Вирівнювання, Шаблон:Нп та зіставляння зображень
2. Створення двовимірних мозаїк
3. Моделювання та відбудова тривимірних сцен
4. Шаблон:Нп
5. Шаблон:Нп
6. Індексування та пошук зображень за вмістом
7. Відстежування у відео

Див. також

• Структурний тензор
• Гаррісів афінний виявляч областей
• Виявляння кутів
• Виявляння ознак (комп'ютерне бачення)
• Комп'ютерне бачення
• Шаблон:Нп

Посилання

• «Вивчення OpenCV на прикладах: Гаррісове виявляння кутів» Шаблон:Ref-en
• «Гаррісове виявляння кутів — документація OpenCV» Шаблон:Ref-en
• Шаблон:Cite web Шаблон:Ref-en
• Інтерактивне втілення гаррісового виявляча кутів — IPOL Шаблон:Ref-en