

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

Огляд

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

Миколайчик та Шмід (2002) вперше описали гаррісів афінний виявляч, яким його використовують сьогодні, у статті  «Афінноінваріантний виявляч особливих точок». До раніших праць у цьому напрямі належать застосування Ліндебергом і Гардінгом афінного пристосовування форми для обчислення афінноінваріантних описувачів зображень і зниження таким чином впливу перспективних деформацій зображень,{D} depth cues from affine distortions of local 2-{D} structure". Image and Vision Computing 15: pp 415—434.  використання Баумбергом точок афіннопристосованих ознак для стереозіставляння з широкою базою (), і перше використання Ліндебергом масштабоінваріантних точок ознак; для огляду теоретичної підоснови. Гаррісів афінний виявляч покладається на поєднання кутових точок, виявляних за допомогою гаррісового виявляння кутів, багатомасштабного аналізу через гауссів простір масштабів, та афінного унормовування за допомогою ітеративного алгоритму афінного пристосовування форми. Рекурсивний та ітеративний алгоритм використовує ітеративний підхід до виявлення цих областей:

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

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

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

Гаррісів афінний виявляч значною мірою покладається як на гаррісову міру, так і на гауссове масштабопросторове подання. Тому далі буде короткий огляд обох. Вичерпніші виведення дивіться у виявлянні кутів та гауссовому просторі масштабів, або їхніх відповідних працях.

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

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

: 

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

: 

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

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

: 

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

: 

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

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

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

: 

де  — ізотропне, кругове гауссове ядро, як визначено вище. Згортка з гауссовим ядром згладжує зображення за допомогою вікна розміром з це ядро. Більший масштаб, , відповідає гладшому отримуваному зображенню. Миколайчик та Шмід (2001) зазначають, що похідні та інші вимірювання мусить бути нормовано над масштабами. Похідну порядку , , необхідно нормувати коефіцієнтом  у такий спосіб:

: 

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

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

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

: 

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

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

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

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

: 

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

: 

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

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

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

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

:: 

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

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

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

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

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

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

: 

де  та  — коваріаційні матриці, що визначають диференціювальні та інтегрувальні масштаби гауссового ядра. Хоча вона може виглядати значно відмінною від матриці другого моменту у виявлячі Гарріса — Лапласа; насправді вона ідентична. Попередня матриця  була двовимірно ізотропною версією, в якій коваріаційні матриці  та  були одиничними матрицями 2 × 2, помноженими на коефіцієнти  та  відповідно. У новому формулюванні гауссові ядра можливо розглядати як багатовимірні гауссові розподіли, на відміну від однорідного гауссового ядра. Однорідне гауссове ядро можливо розглядати як ізотропну, кругову область. Подібно до цього, загальніше гауссове ядро визначає еліпсоїд. Фактично, власні вектори та власні значення коваріаційної матриці визначають кут повороту та розмір еліпсоїда. Таким чином, ми можемо легко побачити, що це подання дозволяє нам повністю визначити довільну еліптичну афінну область, над якою ми хочемо здійснювати інтегрування чи диференціювання.

Мета афінноінваріантного виявляча — встановлювати області зображень, пов'язані через афінні перетворення. Таким чином, ми розглядаємо точку  та перетворену точку , де A — афінне перетворення. У випадку зображень, як , так і  живуть у просторі . Матриці другого моменту пов'язано наступним чином:

: 

де  та  — коваріаційні матриці для системи відліку . Якщо ми продовжимо це формулювання й забезпечимо виконання

: 

де  та  — скалярні коефіцієнти, буде можливо показати, що коваріаційні матриці для відповідної точки пов'язані подібним чином:

: 

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

: 

Матрицю обертання можливо отримувати за допомогою градієнтних методів, таких як в описувачі SIFT. Як обговорювалося стосовно виявляча Гарріса, власні значення та власні вектори матриці другого моменту, , характеризують кривину та форму яскравостей пікселів. Тобто, власний вектор, пов'язаний із найбільшим власним значенням, вказує напрямок найбільшої зміни, а власний вектор, пов'язаний із найменшим власним значенням, визначає напрямок найменшої зміни. У двовимірному випадку власні вектори та власні значення визначають еліпс. Для ізотропної області область повинна мати круглу форму, а не еліптичну. Це той випадок, коли власні значення мають однакову величину. Таким чином, міра ізотропності навколо локальної області визначають наступним чином:

: 

де  позначують власні значення. Ця міра має діапазон . Значення  відповідає ідеальній ізотропії.

Ітеративний алгоритм

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



Обчислення та втілення

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

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

Аналіз

Збіжність

Можливо уявити, що цей алгоритм може встановлювати ідентичні особливі точки в різних масштабах. Оскільки гаррісів афінний алгоритм розглядає кожну початкову точку, задану виявлячем Гарріса — Лапласа, незалежно, розрізнення ідентичних точок немає. На практиці було показано, що всі ці точки зрештою збігатимуться до однієї й тієї ж особливої точки. Після завершення встановлювання всіх особливих точок алгоритм враховує дублікати шляхом порівнювання просторових координат (), масштабу інтегрування , міри ізотропності , та скосу. Якщо ці параметри особливих точок схожі в межах заданого порогу, їх позначають як дублікати. Алгоритм відкидає всі ці дубльовані точки, за винятком особливої точки, найближчої до усереднення цих дублікатів. Зазвичай 30 % гаррісових афінних точок є достатньо відмінними та несхожими, щоб не бути відкинутими.

Миколайчик та Шмід (2004) показали, що початкові точки часто (40 %) не збігаються. Цей алгоритм виявляє цю розбіжність, зупиняючи ітеративний алгоритм, якщо обернення міри ізотропності перевищує заданий поріг: . Миколайчик та Шмід (2004) використовують . Для тих, які дійсно збігалися, типове число необхідних ітерацій становило 10.

Кількісна міра

Кількісний аналіз афінних виявлячів областей враховує як точність розташування точок, так і перекриття областей на двох зображеннях. Миколайчик та Шмід (2004) розширюють мі́ру повто́рюваності () Шмід зі співавт. (1998) як відношення точкових відповідностей до мінімуму виявлених точок двох зображень.

: 

де  — число відповідних точок у зображеннях  та .  та  — число виявлених точок у відповідних зображеннях. Оскільки кожне зображення подає тривимірний простір, може ставатися так, що одне зображення містить об'єкти, відсутні в другому зображенні, й відтак особливі точки яких не мають шансів мати відповідні. Щоби зробити міру повторюваності чинною, ці точки усувають, і мусять враховувати лише точки, що лежать на обох зображеннях;  та  враховують ці точки так, що . Для пари з двох зображень, пов'язаних через матрицю  , кажуть, що дві точки  та  відповідні, якщо
Область перекриття двох еліптичних областей.



Стійкість щодо афінних та інших перетворень

Миколайчик зі співавт. (2005) провели ретельний аналіз кількох афінних виявлячів областей рівня останніх досягнень: гаррісового афінного, гессіанного афінного виявлячів, МСЕО, областей на основі екстремумів яскравості () та на основі контурів (), та  виявляча. У ході свого оцінювання Миколайчик зі співавт. аналізували як структуровані, так і текстуровані зображення. Двійкові файли цих виявлячів для Лінукс та їхні перевірні зображення доступні вільно на їхній  вебсторінці. Далі йде короткий підсумок результатів Миколайчика зі співавт. (2005); кількісніший аналіз див у  Порівнянні афінних виявлячів областей .

* Зміна кута точки огляду: гаррісів афінний виявляч має достатню (середню) стійкість щодо цих типів змін. Він підтримує оцінку повторюваності понад 50 % до кута огляду понад 40 градусів. Цей виявляч схильний виявляти велике число повторюваних і відповідних областей навіть за великої зміни точки огляду.
* Зміна масштабу: гаррісів афінний виявляч за змін масштабу лишається дуже стабільним. Незважаючи на те, що число точок значно зменшується за великих змін масштабу (понад 2,8), оцінки повторюваності (50—60 %) та збігу (25—30 %) лишаються дуже сталими, особливо для текстурованих зображень. Це узгоджується з високою продуктивністю ітеративного алгоритму автоматичного обирання масштабу.
* Розмиті зображення: гаррісів афінний виявляч за розмивання зображення лишається дуже стабільним. Оскільки він не покладається на сегментування зображень чи межі областей, оцінки повторюваності та збігу лишаються сталими.
* Артефакти JPEG: гаррісів афінний виявляч гіршає подібно до інших афінних виявлячів: оцінки повторюваності та збігу значно падають при стисненні понад 80 %.
* Зміни освітленості: гаррісів афінний виявляч, як й інші афінні виявлячі, дуже стійкий щодо змін освітленості: оцінки повторюваності та збігу за зниження освітленості залишаються незмінними. Цього слід очікувати, оскільки ці виявлячі значною мірою покладаються на відносні яскравості (похідні), а не на абсолютні.

Загальні схильності

* Точки гаррісових афінних областей, як правило, малі та численні. Як гаррісів афінний, так і гессіанний афінний виявлячі стабільно встановлюють вдвічі більше повторюваних точок, аніж інші афінні виявлячі: ~1000 областей для зображення 800x640. Невеликі області рідше бувають затуленими, але мають менший шанс перекривати сусідні області.
* Гаррісів афінний виявляч добре реагує на текстуровані сцени, в яких багато кутоподібних частин. Проте для деяких структурованих сцен, як-от будівель, дуже добре працює гессіанний афінний виявляч. Це доповнюють МСЕО, які працюють краще з добре структурованими (сегментованими) сценами.
* Загалом гаррісів афінний виявляч працює дуже добре, але все ж відстає від МСЕО та гессіанного афінного у всіх випадках, крім розмитих зображень.
* Гаррісів афінний та гессіанний афінний виявлячі менш точні, ніж інші: їхня оцінка повторюваності зростає зі збільшенням порогу перекриття.
* Виявлені афінноінваріантні області все ще можуть відрізнятися своїм повертанням та освітленням. Будь-який описувач, що використовує ці області, повинен забезпечувати таку інваріантність при використанні цих областей для зіставлення або інших порівнянь.

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

* Пошук зображень за вмістом
* Розпізнавання на основі моделей
* Пошук об'єктів у відео
* Візуальний аналіз даних: встановлювання важливих об'єктів, персонажів та сцен у відео
* Розпізнавання та категоризування об'єктів
* Аналіз зображень дистанційного зондування: виявляння об'єктів у зображеннях дистанційного зондування

Програмні пакети

*  Affine Covariant Features: К. Миколайчик підтримує вебсторінку, яка містить двійкові файли для Linux гаррісового афінного виявляча, на додачу до інших виявлячів та описувачів. Також доступний код Matlab, який можливо використовувати для ілюстрації та обчислення повторюваності різних виявлячів. Код і зображення також доступні для дублювання результатів, отриманих у праці Миколайчика зі співавт. (2005).
*  lip-vireo — двійковий код для Linux, Windows та SunOS від дослідницької групи VIREO, див. більше на їхній  домашній сторінці

Посилання

*  — слайди презентації Миколайчика зі співавт. до їхньої праці 2005 року.
*  — Лабораторія комп'ютерного бачення Корделії Шмід
*  — код, перевірні зображення, бібліографія афінних коваріантних ознак, які ведуть Крістіан Миколайчик та  Група візуальної геометрії з Групи робототехніки Оксфордського університету.
*  — бібліографія виявлячів ознак (і плям), підтримувана Інститутом робототехніки та інтелектуальних систем Університету Південної Каліфорнії
*  — Цифрове втілення лапласіана гауссіана

Див. також

* Гессіанний афінний виявляч
* МСЕО
* 
* Простір масштабів
* Ізотропія
* Виявляння кутів
* Виявляння особливих точок
* Афінне пристосовування форми
* Похідна зображення
* Комп'ютерне бачення
*  ASIFT -> Affine-Sift (повністю афінноінваріантний алгоритм зіставляння зображень)

Примітки


