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

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

Введення

Кут (англ. corner) — це точка, локальний окіл якої перебуває у двох переважних і різних напрямках контурів. Іншими словами, кут можливо інтерпретувати як з'єднання двох контурів, де контур (англ. edge) — це раптова зміна яскравості зображення. Кути — важливі ознаки на зображенні, і їх зазвичай називають особливими точками, інваріантними щодо переміщення, обертання та освітлення. Хоч кути й становлять лише невеликий відсоток зображення, вони містять найважливіші ознаки для відновлення інформації зображення, і їх можливо використовувати для мінімізування обсягу оброблюваних даних для відстежування руху, ^[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. Виявляч кутів Гарріса — Лапласа
2. Виявляч кутів на основі диференціального морфологічного розкладу
3. Виявляч кутів на основі багатомасштабного двобічного структурного тензора

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

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

Див. також

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

Примітки

1. Chris Harris and Mike Stephens (1988). A Combined Corner and Edge Detector. Alvey Vision Conference. Т. 15. (англ.)
2. Dey, Nilanjan та ін. (2012). A Comparative Study between Moravec and Harris Corner Detection of Noisy Images Using Adaptive Wavelet Thresholding Technique. arXiv:1209.1558 [cs.CV]. (англ.)
3. Konstantinos G. Derpanis (2004). The harris corner detector. York University. (англ.)
4. Harris Operator Corner Detection using Sliding Window Method - Google Scholar. scholar.google.com. Процитовано 29 листопада 2015. (англ.)
5. The Comparison and Application of Corner Detection Algorithms - Google Scholar. scholar.google.com. Процитовано 29 листопада 2015. (англ.)
6. Javier Sánchez, Nelson Monzón and Agustín Salgado (2018). An Analysis and Implementation of the Harris Corner Detector. Image Processing on Line. 8: 305—328. doi:10.5201/ipol.2018.229. (англ.)
7. Bellavia, F.; Tegolo, D.; Valenti, C. (1 березня 2011). Improving Harris corner selection strategy. IET Computer Vision. 5 (2): 87. doi:10.1049/iet-cvi.2009.0127. (англ.)
8. Rosten, Edward; Drummond, Tom (7 травня 2006). Leonardis, Aleš; Bischof, Horst; Pinz, Axel (ред.). Machine Learning for High-Speed Corner Detection. Lecture Notes in Computer Science (англ.). Springer Berlin Heidelberg. с. 430—443. CiteSeerX 10.1.1.64.8513. doi:10.1007/11744023_34. ISBN . (англ.)
9. A Comparison of Affine Region Detectors - Google Scholar. scholar.google.com. Процитовано 29 листопада 2015. (англ.)
10. Gueguen, L.; Pesaresi, M. (2011). Multi scale Harris corner detector based on Differential Morphological Decomposition. Pattern Recognition Letters. 32 (14): 1714—1719. doi:10.1016/j.patrec.2011.07.021. (англ.)
11. A Multi-scale Bilateral Structure Tensor Based Corner Detector - Google Scholar. scholar.google.com. Процитовано 29 листопада 2015. (англ.)
12. Kang, Juan; Xiao, Chuangbai; Deng, M.; Yu, Jing; Liu, Haifeng (1 серпня 2011). Image registration based on harris corner and mutual information. Т. 7. с. 3434—3437. doi:10.1109/EMEIT.2011.6023066. ISBN . S2CID 17367248. {{}}: Проігноровано |journal= () (англ.)
13. Underwater Mosaic Creation using Video sequences from Different Altitudes - Google Scholar. scholar.google.com. Процитовано 2 грудня 2015. (англ.)
14. Automated reconstruction of 3D scenes from sequences of images - Google Scholar. scholar.google.com. Процитовано 2 грудня 2015. (англ.)
15. Liu, Meng; Wu, Chengdong; Zhang, Yunzhou (1 липня 2008). Multi-resolution optical flow tracking algorithm based on multi-scale Harris corner points feature. с. 5287—5291. doi:10.1109/CCDC.2008.4598340. ISBN . S2CID 8085227. {{}}: Проігноровано |journal= () (англ.)
16. Object Recognition from Local Scale-Invariant Features - Google Scholar. scholar.google.com. Процитовано 29 листопада 2015. (англ.)
17. Salient Points for Content Based Retrieval - Google Scholar. scholar.google.com. Процитовано 2 грудня 2015. (англ.)
18. Tracking and Recognition of Objects using SURF Descriptor and Harris Corner Detection - Google Scholar. scholar.google.com. Процитовано 2 грудня 2015. (англ.)

Посилання

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