У галузях комп'ютерного бачення та га́ррісів афі́нний виявля́ч областе́й () належить до категорії виявляння ознак. Виявляння ознак — це етап попередньої обробки деяких алгоритмів, які покладаються на встановлювання характерних, або особливих точок, щоби встановлювати відповідності між зображеннями, розпізнавати текстури, категоризувати об'єкти, або створювати панорами.

Огляд

Гаррісів афінний виявляч може встановлювати подібні області зображень, пов'язані через афінні перетворення, і з різним освітленням. Ці афінноінваріантні () виявлячі повинні бути здатними встановлювати схожі області в зображеннях, зроблених з різних точок огляду, пов'язаних простим геометричним перетворенням: масштабуванням, повертанням і зміщенням. Ці виявляні області називали як інваріантними, так і коваріантними. З одного боку, ці області виявляються інваріантно щодо перетворення зображення, але вони коваріантно змінюються з перетворенням зображення. Не варто надто зациклюватися на цих двох угодах про іменування; важливо розуміти, що дизайн цих особливих точок робитиме їх сумісними між зображеннями, зробленими з кількох точок огляду. До інших афінноінваріантних виявлячів належать гессіанний афінний виявляч областей, максимально стабільні екстремумні області, , області на основі контурів (), та області на основі екстремумів яскравості ().

Миколайчик та Шмід (2002) вперше описали гаррісів афінний виявляч, яким його використовують сьогодні, у статті «Афінноінваріантний виявляч особливих точок».Mikolajcyk, K. and Schmid, C. 2002. An affine invariant interest point detector. In Proceedings of the 8th International Conference on Computer Vision, Vancouver, Canada. До раніших праць у цьому напрямі належать застосування Ліндебергом і Гардінгом афінного пристосовування форми для обчислення афінноінваріантних описувачів зображень і зниження таким чином впливу перспективних деформацій зображень,T. Lindeberg and J. Garding (1997). "Shape-adapted smoothing in estimation of 3-{D} depth cues from affine distortions of local 2-{D} structure". Image and Vision Computing 15: pp 415—434. використання Баумбергом точок афіннопристосованих ознак для стереозіставляння з широкою базою (),A. Baumberg (2000). "Reliable feature matching across widely separated views". Proceedings of IEEE Conference on Computer Vision and Pattern Recognition: pages I:1774—1781. і перше використання Ліндебергом масштабоінваріантних точок ознак;Lindeberg, Tony, Scale-Space Theory in Computer Vision, Kluwer Academic Publishers, 1994, T. Lindeberg (1998). "Feature detection with automatic scale selection". International Journal of Computer Vision 30 (2): pp 77—116. для огляду теоретичної підоснови. Гаррісів афінний виявляч покладається на поєднання кутових точок, виявляних за допомогою гаррісового виявляння кутів, багатомасштабного аналізу через гауссів простір масштабів, та афінного унормовування за допомогою ітеративного алгоритму афінного пристосовування форми. Рекурсивний та ітеративний алгоритм використовує ітеративний підхід до виявлення цих областей:

Визначити початкові точки областей за допомогою масштабоінваріантного виявляча Гарріса — Лапласа. Для кожної початкової точки унормувати область, щоби вона була афінноінваріантною, за допомогою афінного пристосовування форми. Ітеративно оцінити цю афінну область: обрати належний масштаб інтегрування, масштаб диференціювання, та визначити просторові положення особливих точок. Уточнити цю афінну область, скориставшись цими масштабами та просторовими положеннями. Повторити крок 3, якщо критерію зупинки не досягнуто.

Опис алгоритму

Виявляч Гарріса — Лапласа (початкових точок областей)

Гаррісів афінний виявляч значною мірою покладається як на гаррісову міру, так і на гауссове масштабопросторове подання. Тому далі буде короткий огляд обох. Вичерпніші виведення дивіться у виявлянні кутів та гауссовому просторі масштабів, або їхніх відповідних працях.C. Harris and M. Stephens (1988). "A combined corner and edge detector". Proceedings of the 4th Alvey Vision Conference: pages 147—151.

Гаррісова міра кута

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

де та  — похідні (яскравості пікселів) у напрямах та відповідно в точці (, ); та  — параметри положення вагової функції w. Недіагональні елементи є добутком та , тоді як діагональні елементи є квадратами відповідних похідних. Вагова функція може бути рівномірною, але частіше ізотропна, кругова гауссова,

яка діє як усереднення в локальній області, водночас заважуючи сильніше значення поблизу центру.

Як виявилося, ця матриця описує форму автокореляційної міри через зміщення розташування вікна. Таким чином, якщо та  — власні значення , то ці значення забезпечують кількісний опис того, як автокореляційна міра змінюється в просторі: її головні кривини. Як зазначають Гарріс та Стівенс (1988), матриця з центром у кутових точках матиме два великі додатні власні значення. Замість виділяння цих власних значень такими методами як сингулярний розклад матриці, використовують гаррісову міру на основі сліду та визначника:

де  — стала. Кутові точки мають великі додатні власні значення, й відтак матимуть велику гаррісову міру. Таким чином, кутові точки визначають як локальні максимуми гаррісової міри, що перевищують заданий поріг.

де  — множина всіх кутових точок,  — гаррісова міра, обчислена в ,  — 8-сусідова множина з центром , а  — заданий поріг.

Гауссів простір масштабів

Гауссове масштабопросторове подання зображення — це набір зображень, що є результатом згортання гауссового ядра різних розмірів із первинним зображенням. У загальному вигляді це подання можливо сформулювати так:

де  — ізотропне, кругове гауссове ядро, як визначено вище. Згортка з гауссовим ядром згладжує зображення за допомогою вікна розміром з це ядро. Більший масштаб, , відповідає гладшому отримуваному зображенню. Миколайчик та Шмід (2001) зазначають, що похідні та інші вимірювання мусить бути нормовано над масштабами.K. Mikolajczyk and C. Schmid. Indexing based on scale invariant interest points. In Proceedings of the 8th International Conference on Computer Vision, Vancouver, Canada, pages 525-531, 2001. Похідну порядку , , необхідно нормувати коефіцієнтом у такий спосіб:

Ці похідні, або будь-яку довільну міру, можливо пристосовувати до масштабопросторового подання шляхом рекурсивного обчислення цієї міри за допомогою набору масштабів, де -тий масштаб . Повніший опис див. у просторі масштабів.

Поєднання гаррісового виявляча над гауссовим простором масштабів

Виявляч Гарріса — Лапласа поєднує традиційний двовимірний гаррісів виявляч кутів з ідеєю гауссового масштабопросторового подання для створення масштабоінваріантного виявляча. Гаррісові кутові точки є гарними відправними точками, оскільки було показано, що вони, на додачу до визначання особливих точок зображення, мають добру інваріантність щодо обертання та освітлення.Schmid, C., Mohr, R., and Bauckhage, C. 2000. Evaluation of interest point detectors. International Journal of Computer Vision, 37(2):151-172. Проте ці точки не інваріантні щодо масштабу, і тому матрицю другого моменту необхідно видозмінити, щоби відтворити властивість масштабоінваріантності. Позначмо через масштабопристосовану матрицю другого моменту, яку використовують у виявлячі Гарріса — Лапласа.

Mikolajczyk, K. and Schmid, C. 2004. Scale & affine invariant interest point detectors. International Journal on Computer Vision 60(1):63-86.

де  — гауссове ядро масштабу , а . Подібно до гауссового простору масштабів,  — гауссового згладжене зображення. Оператор позначує згортку. та  — похідні у відповідних напрямках, застосовані до згладженого зображення, та обчислені з використанням гауссового ядра з масштабом . З точки зору нашої системи гауссового простору масштабів, параметр визначає поточний масштаб, на якому виявляються гаррісові кутові точки.

Створений на основі цієї масштабопристосованої матриці другого моменту, виявляч Гарріса — Лапласа становить подвійний процес: застосування гаррісового виявляча кутів у кількох масштабах, та автоматичне обирання характерного масштабу ().

Багатомасштабні гаррісові кутові точки

Цей алгоритм здійснює пошук над фіксованим числом наперед визначених масштабів. Набір масштабів задають наступним чином:

Миколайчик та Шмід (2004) використовують . Для кожного масштабу інтегрування , обраного з цього набору, відповідний масштаб диференціювання обирають як сталу пропорцію масштабу інтегрування: . Миколайчик та Шмід (2004) використовували . Використовуючи ці масштаби, особливі точки виявляють за допомогою міри Гарріса на матриці . Кутовість (), як і типову міру Гарріса, визначають як

Подібно до традиційного гаррісового виявляча, кутові точки — це ті локальні (у 8-точкових околах) максимуми кутовості, що перевищують заданий поріг.

Встановлювання характерного масштабу

Ітеративний алгоритм на основі Ліндеберга (1998) як просторово локалізує кутові точки, так й обирає характе́рний масшта́б (). Цей ітеративний пошук має три ключові кроки, виконувані для кожної з точок , які спершу було виявлено на масштабі багатомасштабним гаррісовим виявлячем ( вказує на -ту ітерацію):

Обрати масштаб , який максимізує лапласіан гауссіанів (ЛГ, ) над попередньо визначеним діапазоном сусідніх масштабів. Сусідні масштаби, як правило, вибирають із діапазону, що перебуває в околі двох масштабів простору (). Тобто, якщо вихідні точки було виявлено з використанням коефіцієнта масштабування між послідовними масштабами, то окіл двох масштабів простору — це проміжок . Таким чином, розглядають гауссові масштаби . Вимірювання ЛГ визначають як

де та  — другі похідні у своїх відповідних напрямках.Spatial Filters: Laplacian/Laplacian of Gaussian Коефіцієнт (як обговорювалося вище в гауссовому просторі масштабів) використовують для унормовування ЛГ над масштабами, роблячи ці вимірювання порівнянними, відтак роблячи максимум доречним. Миколайчик та Шмід (2001) показують, що міра ЛГ у порівнянні з іншими мірами обирання масштабу досягає найвищого відсотка правильно виявлених кутових точок. Масштаб, який максимізує міру ЛГ в околі двох масштабів простору, вважають характе́рним масшта́бом (), , і використовують у наступних ітераціях. Якщо екстремуму або максимуму ЛГ не знайдено, цю точку викидають із подальших пошуків.

Використовуючи характерний масштаб, локалізувати точки в просторі. Інакше кажучи, обирають таким чином, щоби вона максимізувала гаррісову кутову міру (кутовість, , як визначено вище) у локальному околі 8 × 8. Критерій зупинки: і .

Якщо критерію зупинки не досягнуто, алгоритм повторюється з кроку 1, використовуючи ці нові точки та масштаб . Коли критерію зупинки досягнуто, знайдені точки являють собою ті, які максимізують ЛГ над масштабами (обирання масштабу) й максимізують гаррісову кутову міру в локальному околі (просторове обирання).

Афінноінваріантні точки

Математична теорія

Точки виявляча Гарріса — Лапласа масштабоінваріантні, й добре працюють для ізотропних областей, які розглядають під однаковим кутом огляду. Щоби вона була інваріантною до довільних афінних перетворень (та точок огляду), цю математичну структуру необхідно переглянути. Матрицю другого моменту для анізотропних областей визначають загальніше: