Гаррісів афінний виявляч областей

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

Огляд

Гаррісів афінний виявляч може встановлювати подібні області зображень, пов'язані через афінні перетворення, і з різним освітленням. Ці афінноінваріантні (англ. affine-invariant) виявлячі повинні бути здатними встановлювати схожі області в зображеннях, зроблених з різних точок огляду, пов'язаних простим геометричним перетворенням: масштабуванням, повертанням і зміщенням. Ці виявляні області називали як інваріантними, так і коваріантними. З одного боку, ці області виявляються інваріантно щодо перетворення зображення, але вони коваріантно змінюються з перетворенням зображення. Не варто надто зациклюватися на цих двох угодах про іменування; важливо розуміти, що дизайн цих особливих точок робитиме їх сумісними між зображеннями, зробленими з кількох точок огляду. До інших афінноінваріантних виявлячів належать гессіанний афінний виявляч областей, максимально стабільні екстремумні області, ^[en], області на основі контурів (англ. edge-based regions, EBR), та області на основі екстремумів яскравості (англ. intensity-extrema-based regions, IBR).

Миколайчик та Шмід (2002) вперше описали гаррісів афінний виявляч, яким його використовують сьогодні, у статті «Афінноінваріантний виявляч особливих точок». До раніших праць у цьому напрямі належать застосування Ліндебергом і Гардінгом афінного пристосовування форми для обчислення афінноінваріантних описувачів зображень і зниження таким чином впливу перспективних деформацій зображень, використання Баумбергом точок афіннопристосованих ознак для стереозіставляння з широкою базою (англ. wide baseline matching), і перше використання Ліндебергом масштабоінваріантних точок ознак; для огляду теоретичної підоснови. Гаррісів афінний виявляч покладається на поєднання кутових точок, виявляних за допомогою гаррісового виявляння кутів, багатомасштабного аналізу через гауссів простір масштабів, та афінного унормовування за допомогою ітеративного алгоритму афінного пристосовування форми. Рекурсивний та ітеративний алгоритм використовує ітеративний підхід до виявлення цих областей:

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

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

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

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

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

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

${\displaystyle A(\mathbf {x} )=\sum _{p,q}w(p,q){\begin{bmatrix}I_{x}^{2}(p,q)&I_{x}I_{y}(p,q)\\I_{x}I_{y}(p,q)&I_{y}^{2}(p,q)\\\end{bmatrix}}}$

де ${\displaystyle I_{x}}$ та ${\displaystyle I_{y}}$ — похідні (яскравості пікселів) у напрямах ${\displaystyle x}$ та ${\displaystyle y}$ відповідно в точці (${\displaystyle p}$, ${\displaystyle q}$); ${\displaystyle p}$ та ${\displaystyle q}$ — параметри положення вагової функції w. Недіагональні елементи є добутком ${\displaystyle I_{x}}$ та ${\displaystyle I_{y}}$, тоді як діагональні елементи є квадратами відповідних похідних. Вагова функція ${\displaystyle w(x,y)}$ може бути рівномірною, але частіше ізотропна, кругова гауссова,

${\displaystyle w(x,y)=g(x,y,\sigma )={\frac {1}{2\pi \sigma ^{2}}}e^{\left(-{\frac {x^{2}+y^{2}}{2\sigma ^{2}}}\right)}}$

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

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

${\displaystyle R=\det(A)-\alpha \operatorname {trace} ^{2}(A)=\lambda _{1}\lambda _{2}-\alpha (\lambda _{1}+\lambda _{2})^{2}}$

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

${\displaystyle {\begin{aligned}\{x_{c}\}={\big \{}x_{c}\mid R(x_{c})>R(x_{i}),\forall x_{i}\in W(x_{c}){\big \}},\\R(x_{c})>t_{\text{threshold}}\end{aligned}}}$

де ${\displaystyle \{x_{c}\}}$ — множина всіх кутових точок, ${\displaystyle R(x)}$ — гаррісова міра, обчислена в ${\displaystyle x}$, ${\displaystyle W(x_{c})}$ — 8-сусідова множина з центром ${\displaystyle x_{c}}$, а ${\displaystyle t_{\text{threshold}}}$ — заданий поріг.

8-точковий окіл

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

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

${\displaystyle L(\mathbf {x} ,s)=G(s)\otimes I(\mathbf {x} )}$

де ${\displaystyle G(s)}$ — ізотропне, кругове гауссове ядро, як визначено вище. Згортка з гауссовим ядром згладжує зображення за допомогою вікна розміром з це ядро. Більший масштаб, ${\displaystyle s}$, відповідає гладшому отримуваному зображенню. Миколайчик та Шмід (2001) зазначають, що похідні та інші вимірювання мусить бути нормовано над масштабами. Похідну порядку ${\displaystyle m}$, ${\displaystyle D_{i_{1},...i_{m}}}$, необхідно нормувати коефіцієнтом ${\displaystyle s^{m}}$ у такий спосіб:

${\displaystyle D_{i_{1},\dots ,i_{m}}(\mathbf {x} ,s)=s^{m}L_{i_{1},\dots ,i_{m}}(\mathbf {x} ,s)}$

Ці похідні, або будь-яку довільну міру, можливо пристосовувати до масштабопросторового подання шляхом рекурсивного обчислення цієї міри за допомогою набору масштабів, де ${\displaystyle n}$-тий масштаб ${\displaystyle s_{n}=k^{n}s_{0}}$. Повніший опис див. у просторі масштабів.

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

Виявляч Гарріса — Лапласа поєднує традиційний двовимірний гаррісів виявляч кутів з ідеєю гауссового масштабопросторового подання для створення масштабоінваріантного виявляча. Гаррісові кутові точки є гарними відправними точками, оскільки було показано, що вони, на додачу до визначання особливих точок зображення, мають добру інваріантність щодо обертання та освітлення. Проте ці точки не інваріантні щодо масштабу, і тому матрицю другого моменту необхідно видозмінити, щоби відтворити властивість масштабоінваріантності. Позначмо через ${\displaystyle M=\mu (\mathbf {x} ,\sigma _{\mathit {I}},\sigma _{\mathit {D}})}$ масштабопристосовану матрицю другого моменту, яку використовують у виявлячі Гарріса — Лапласа.

${\displaystyle M=\mu (\mathbf {x} ,\sigma _{\mathit {I}},\sigma _{\mathit {D}})=\sigma _{D}^{2}g(\sigma _{I})\otimes {\begin{bmatrix}L_{x}^{2}(\mathbf {x} ,\sigma _{D})&L_{x}L_{y}(\mathbf {x} ,\sigma _{D})\\L_{x}L_{y}(\mathbf {x} ,\sigma _{D})&L_{y}^{2}(\mathbf {x} ,\sigma _{D})\end{bmatrix}}}$

де ${\displaystyle g(\sigma _{I})}$ — гауссове ядро масштабу ${\displaystyle \sigma _{I}}$, а ${\displaystyle \mathbf {x} =(x,y)}$. Подібно до гауссового простору масштабів, ${\displaystyle L(\mathbf {x} )}$ — гауссового згладжене зображення. Оператор ${\displaystyle \mathbf {\otimes } }$ позначує згортку. ${\displaystyle L_{x}(\mathbf {x} ,\sigma _{D})}$ та ${\displaystyle L_{y}(\mathbf {x} ,\sigma _{D})}$ — похідні у відповідних напрямках, застосовані до згладженого зображення, та обчислені з використанням гауссового ядра з масштабом ${\displaystyle \sigma _{D}}$. З точки зору нашої системи гауссового простору масштабів, параметр ${\displaystyle \sigma _{I}}$ визначає поточний масштаб, на якому виявляються гаррісові кутові точки.

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

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

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

${\displaystyle {\sigma _{1}\dots \sigma _{n}}={k^{1}\sigma _{0}\dots k^{n}\sigma _{0}}}$

Миколайчик та Шмід (2004) використовують ${\displaystyle k=1.4}$. Для кожного масштабу інтегрування ${\displaystyle \sigma _{I}}$, обраного з цього набору, відповідний масштаб диференціювання обирають як сталу пропорцію масштабу інтегрування: ${\displaystyle \sigma _{D}=s\sigma _{I}}$. Миколайчик та Шмід (2004) використовували ${\displaystyle s=0.7}$. Використовуючи ці масштаби, особливі точки виявляють за допомогою міри Гарріса на матриці ${\displaystyle \mu (\mathbf {x} ,\sigma _{\mathit {I}},\sigma _{\mathit {D}})}$. Кутовість (англ. cornerness), як і типову міру Гарріса, визначають як

${\displaystyle {\mathit {cornerness}}=\det(\mu (\mathbf {x} ,\sigma _{\mathit {I}},\sigma _{\mathit {D}}))-\alpha \operatorname {trace} ^{2}(\mu (\mathbf {x} ,\sigma _{\mathit {I}},\sigma _{\mathit {D}}))}$

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

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

Ітеративний алгоритм на основі Ліндеберга (1998) як просторово локалізує кутові точки, так й обирає характе́рний масшта́б (англ. characteristic scale). Цей ітеративний пошук має три ключові кроки, виконувані для кожної з точок ${\displaystyle \mathbf {x} }$, які спершу було виявлено на масштабі ${\displaystyle \sigma _{I}}$ багатомасштабним гаррісовим виявлячем (${\displaystyle k}$ вказує на ${\displaystyle k}$-ту ітерацію):

• Обрати масштаб ${\displaystyle \sigma _{I}^{(k+1)}}$, який максимізує лапласіан гауссіанів (ЛГ, англ. LoG) над попередньо визначеним діапазоном сусідніх масштабів. Сусідні масштаби, як правило, вибирають із діапазону, що перебуває в околі двох масштабів простору (англ. two scale-space). Тобто, якщо вихідні точки було виявлено з використанням коефіцієнта масштабування ${\displaystyle 1.4}$ між послідовними масштабами, то окіл двох масштабів простору — це проміжок ${\displaystyle t\in [0.7,\dots ,1.4]}$. Таким чином, розглядають гауссові масштаби ${\displaystyle \sigma _{I}^{(k+1)}=t\sigma _{I}^{k}}$. Вимірювання ЛГ визначають як

${\displaystyle |\operatorname {LoG} (\mathbf {x} ,\sigma _{I})|=\sigma _{I}^{2}\left|L_{xx}(\mathbf {x} ,\sigma _{I})+L_{yy}(\mathbf {x} ,\sigma _{I})\right|}$

де ${\displaystyle L_{xx}}$ та ${\displaystyle L_{yy}}$ — другі похідні у своїх відповідних напрямках. Коефіцієнт ${\displaystyle \sigma _{I}^{2}}$ (як обговорювалося вище в гауссовому просторі масштабів) використовують для унормовування ЛГ над масштабами, роблячи ці вимірювання порівнянними, відтак роблячи максимум доречним. Миколайчик та Шмід (2001) показують, що міра ЛГ у порівнянні з іншими мірами обирання масштабу досягає найвищого відсотка правильно виявлених кутових точок. Масштаб, який максимізує міру ЛГ в околі двох масштабів простору, вважають характе́рним масшта́бом (англ. characteristic scale), ${\displaystyle \sigma _{I}^{(k+1)}}$, і використовують у наступних ітераціях. Якщо екстремуму або максимуму ЛГ не знайдено, цю точку викидають із подальших пошуків.

• Використовуючи характерний масштаб, локалізувати точки в просторі. Інакше кажучи, ${\displaystyle \mathbf {x} ^{(k+1)}}$ обирають таким чином, щоби вона максимізувала гаррісову кутову міру (кутовість, англ. cornerness, як визначено вище) у локальному околі 8 × 8.
• Критерій зупинки: ${\displaystyle \sigma _{I}^{(k+1)}==\sigma _{I}^{(k)}}$ і ${\displaystyle \mathbf {x} ^{(k+1)}==\mathbf {x} ^{(k)}}$.

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

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

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

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

${\displaystyle \mu (\mathbf {x} ,\Sigma _{I},\Sigma _{D})=\det(\Sigma _{D})g(\Sigma _{I})*(\nabla L(\mathbf {x} ,\Sigma _{D})\nabla L(\mathbf {x} ,\Sigma _{D})^{T})}$

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

Мета афінноінваріантного виявляча — встановлювати області зображень, пов'язані через афінні перетворення. Таким чином, ми розглядаємо точку ${\displaystyle \mathbf {x} _{L}}$ та перетворену точку ${\displaystyle \mathbf {x} _{R}=A\mathbf {x} _{L}}$, де A — афінне перетворення. У випадку зображень, як ${\displaystyle \mathbf {x} _{R}}$, так і ${\displaystyle \mathbf {x} _{L}}$ живуть у просторі ${\displaystyle R^{2}}$. Матриці другого моменту пов'язано наступним чином:

${\displaystyle {\begin{aligned}\mu (\mathbf {x} _{L},\Sigma _{I,L},\Sigma _{D,L})&{}=A^{T}\mu (\mathbf {x} _{R},\Sigma _{I,R},\Sigma _{D,R})A\\M_{L}&{}=\mu (\mathbf {x} _{L},\Sigma _{I,L},\Sigma _{D,L})\\M_{R}&{}=\mu (\mathbf {x} _{R},\Sigma _{I,R},\Sigma _{D,R})\\M_{L}&{}=A^{T}M_{R}A\\\Sigma _{I,R}&{}=A\Sigma _{I,L}A^{T}\\\Sigma _{D,R}=A\Sigma _{D,L}A^{T}\end{aligned}}}$

де ${\displaystyle \Sigma _{I,b}}$ та ${\displaystyle \Sigma _{D,b}}$ — коваріаційні матриці для системи відліку ${\displaystyle b}$. Якщо ми продовжимо це формулювання й забезпечимо виконання

${\displaystyle {\begin{aligned}\Sigma _{I,L}=\sigma _{I}M_{L}^{-1}\\\Sigma _{D,L}=\sigma _{D}M_{L}^{-1}\end{aligned}}}$

де ${\displaystyle \sigma _{I}}$ та ${\displaystyle \sigma _{D}}$ — скалярні коефіцієнти, буде можливо показати, що коваріаційні матриці для відповідної точки пов'язані подібним чином:

${\displaystyle {\begin{aligned}\Sigma _{I,R}=\sigma _{I}M_{R}^{-1}\\\Sigma _{D,R}=\sigma _{D}M_{R}^{-1}\end{aligned}}}$

Завдяки вимозі до коваріаційних матриць задовольняти ці умови виникає кілька приємних властивостей. Одна з них полягає в тому, що квадратний корінь матриці другого моменту, ${\displaystyle M^{\tfrac {1}{2}}}$, перетворюватиме первинну анізотропну область в ізотропні області, пов'язані просто через чисту матрицю повертання ${\displaystyle R}$. Ці нові ізотропні області можливо розглядати як унормовану систему відліку. Наступні рівняння формулюють співвідношення між унормованими точками ${\displaystyle x_{R}^{'}}$ та ${\displaystyle x_{L}^{'}}$:

${\displaystyle {\begin{aligned}A=M_{R}^{-{\tfrac {1}{2}}}RM_{L}^{\tfrac {1}{2}}\\x_{R}^{'}=M_{R}^{\tfrac {1}{2}}x_{R}\\x_{L}^{'}=M_{L}^{\tfrac {1}{2}}x_{L}\\x_{L}^{'}=Rx_{R}^{'}\\\end{aligned}}}$

Матрицю обертання можливо отримувати за допомогою градієнтних методів, таких як в описувачі SIFT. Як обговорювалося стосовно виявляча Гарріса, власні значення та власні вектори матриці другого моменту, ${\displaystyle M=\mu (\mathbf {x} ,\Sigma _{I},\Sigma _{D})}$, характеризують кривину та форму яскравостей пікселів. Тобто, власний вектор, пов'язаний із найбільшим власним значенням, вказує напрямок найбільшої зміни, а власний вектор, пов'язаний із найменшим власним значенням, визначає напрямок найменшої зміни. У двовимірному випадку власні вектори та власні значення визначають еліпс. Для ізотропної області область повинна мати круглу форму, а не еліптичну. Це той випадок, коли власні значення мають однакову величину. Таким чином, міра ізотропності навколо локальної області визначають наступним чином:

${\displaystyle {\mathcal {Q}}={\frac {\lambda _{\min }(M)}{\lambda _{\max }(M)}}}$

де ${\displaystyle \lambda }$ позначують власні значення. Ця міра має діапазон ${\displaystyle [0\dots 1]}$. Значення ${\displaystyle 1}$ відповідає ідеальній ізотропії.

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

Використовуючи цю математичну структуру, алгоритм гаррісового афінного виявляча ітеративно виявляє матрицю другого моменту, яка перетворює анізотропну область на унормовану, в якій міра ізотропності достатньо близька до одиниці. Алгоритм використовує цю матрицю пристосовування форми (англ. shape adaptation matrix), ${\displaystyle U}$, щоби перетворювати зображення до унормованої системи відліку. В цьому внормованому просторі параметри особливих точок (просторове розташування, масштаб інтегрування та масштаб диференціювання) уточнюють за допомогою методів, подібних до виявляча Гарріса — Лапласа. Матриця другого моменту обчислюється в цій унормованій системі відліку, й на останній ітерації повинна мати міру ізотропності, близьку до одиниці. На кожній ${\displaystyle k}$-тій ітерації кожна особлива область визначається декількома параметрами, які має встановлювати алгоритм: матрицею ${\displaystyle U^{(k)}}$, положенням ${\displaystyle \mathbf {x} ^{(k)}}$, масштабом інтегрування ${\displaystyle \sigma _{I}^{(k)}}$, та масштабом диференціювання ${\displaystyle \sigma _{D}^{(k)}}$. Оскільки цей виявляч обчислює матрицю другого моменту в перетвореній області, це перетворене положення зручно позначувати через ${\displaystyle \mathbf {x} _{w}^{(k)}}$, де ${\displaystyle U^{(k)}\mathbf {x} _{w}^{(k)}=\mathbf {x^{(k)}} }$.

1. Виявляч встановлює простір пошуку в початковий стан точками, виявленими виявлячем Гарріса — Лапласа.

   ${\displaystyle U^{(0)}=}$ одинична, а ${\displaystyle \mathbf {x} ^{(0)}}$, ${\displaystyle \sigma _{D}^{(0)}}$ та ${\displaystyle \sigma _{I}^{(0)}}$ — з виявляча Гарріса — Лапласа.

2. Застосувати матрицю пристосовування форми з попередньої ітерації, ${\displaystyle U^{(k-1)}}$, щоби породити унормовану систему відліку, ${\displaystyle U^{(k-1)}\mathbf {x} _{w}^{(k-1)}=\mathbf {x} ^{(k-1)}}$. Для першої ітерації ви застосовуєте ${\displaystyle U^{(0)}}$.
3. Обрати масштаб інтегрування, ${\displaystyle \sigma _{I}^{(k)}}$, використовуючи метод, подібний до виявляча Гарріса — Лапласа. Цей масштаб обирають як такий, що максимізує лапласіан гауссіана (ЛГ). Простір пошуку масштабів лежить у межах двох масштабів простору масштабу попередньої ітерації.

   ${\displaystyle \sigma _{I}^{(k)}={\underset {\sigma _{I}=t\sigma _{I}^{(k-1)} \atop t\in [0.7,\dots ,1.4]}{\operatorname {argmax} }}\,\sigma _{I}^{2}\det(L_{xx}(\mathbf {x} ,\sigma _{I})+L_{yy}(\mathbf {x} ,\sigma _{I}))}$

   Важливо зазначити, що масштаб інтегрування в просторі ${\displaystyle U-}$нормований значно відрізняється від невнормованого простору. Тому важливо шукати масштаб інтегрування, а не використовувати масштаб у невнормованому просторі.
4. Обрати масштаб диференціювання, ${\displaystyle \sigma _{D}^{(k)}}$. Щоби звузити простір пошуку та ступені вільності, покладають, що масштаб диференціювання пов'язано з масштабом інтегрування через сталий коефіцієнт: ${\displaystyle \sigma _{D}^{k}=s\sigma _{I}^{k}}$. Зі зрозумілих міркувань цей сталий коефіцієнт менший за одиницю. Миколайчик та Шмід (2001) зауважують, що занадто малий коефіцієнт робитиме згладжування (інтегрування) занадто значним у порівнянні з диференціюванням, а занадто великий коефіцієнт не дозволятиме інтегруванню усереднювати коваріаційну матрицю. Зазвичай обирають ${\displaystyle s\in [0.5,0.75]}$. Масштаб, обраний з цієї множини, максимізуватиме ізотропну міру ${\displaystyle {\mathcal {Q}}={\frac {\lambda _{min}(\mu )}{\lambda _{max}(\mu )}}}$.

   ${\displaystyle \sigma _{D}^{(k)}={\underset {\sigma _{D}=s\sigma _{I}^{(k)},\;s\in [0.5,\dots ,0.75]}{\operatorname {argmax} }}\,{\frac {\lambda _{\min }(\mu (\mathbf {x} _{w}^{(k)},\sigma _{I}^{k},\sigma _{D}))}{\lambda _{\max }(\mu (\mathbf {x} _{w}^{(k)},\sigma _{I}^{k},\sigma _{D}))}}}$

   де ${\displaystyle \mu (\mathbf {x} _{w}^{(k)},\sigma _{I}^{k},\sigma _{D})}$ — матриця другого моменту, оцінена в унормованій системі відліку. Цей процес максимізування призводить до збігання власних значень до одного й того ж значення.
5. Просторове локалізування: Обрати таку точку ${\displaystyle \mathbf {x} _{w}^{(k)}}$, що максимізує гаррісову міру кутовості (${\displaystyle {\mathit {cornerness}}}$), в межах 8-точкового околу навколо попередньої точки ${\displaystyle \mathbf {x} _{w}^{(k-1)}}$.

   ${\displaystyle \mathbf {x} _{w}^{(k)}={\underset {\mathbf {x} _{w}\in W(\mathbf {x} _{w}^{(k-1)})}{\operatorname {argmax} }}\,\det(\mu (\mathbf {x} _{w},\sigma _{I}^{k},\sigma _{D}^{(k)}))-\alpha \operatorname {trace} ^{2}(\mu (\mathbf {x} _{w},\sigma _{I}^{k},\sigma _{D}^{(k)}))}$

   де ${\displaystyle \mu }$ — матриця другого моменту, визначена як вище. Вікно ${\displaystyle W(\mathbf {x} _{w}^{(k-1)})}$ — це множина 8-найближчих сусідів точки з попередньої ітерації в нормованій системі відліку. Оскільки нашу просторову локалізацію було здійснено в ${\displaystyle U}$-нормованій системі відліку, новообрану точку необхідно перетворити назад до первинної системи відліку. Цього досягають шляхом перетворення вектору зміщення, та додавання його до попередньої точки:

   ${\displaystyle \mathbf {x} ^{(k)}=\mathbf {x} ^{(k-1)}+U^{(k-1)}\cdot (\mathbf {x} _{w}^{(k)}-\mathbf {x} _{w}^{(k-1)})}$

6. Як зазначено вище, квадратний корінь матриці другого моменту визначає матрицю перетворення, яка породжує нормовану систему відліку. Відтак нам треба зберегти цю матрицю: ${\displaystyle \mu _{i}^{(k)}=\mu ^{-{\tfrac {1}{2}}}(\mathbf {x} _{w}^{(k)},\sigma _{I}^{(k)},\sigma _{D}^{(k)})}$. Матриця перетворення ${\displaystyle U}$ уточнюється: ${\displaystyle U^{(k)}=\mu _{i}^{(k)}\cdot U^{(k-1)}}$. Щоби забезпечити коректне дискретування зображення, і що ми розширюємо зображення в напрямку найменшої зміни (найменшого власного значення), ми фіксуємо максимальне власне значення: ${\displaystyle \lambda _{max}(U^{(k)})=1}$. Використовуючи цей метод уточнення, можливо легко побачити, що остаточна матриця ${\displaystyle U}$ набуває наступного вигляду:

   ${\displaystyle U=\prod _{k}\mu _{i}^{(k)}\cdot U^{(0)}=\prod _{k}(\mu ^{-{\tfrac {1}{2}}})^{(k)}\cdot U^{(0)}}$

7. Якщо критерію зупинки не досягнуто, перейти до наступної ітерації на кроці 2. Оскільки цей алгоритм ітеративно шукає розв'язок для матриці ${\displaystyle U-}$нормування, яка перетворює анізотропну область на ізотропну, має сенс зупинитися, коли міра ізотропності, ${\displaystyle {\mathcal {Q}}={\frac {\lambda _{\min }(\mu )}{\lambda _{\max }(\mu )}}}$, стала достатньо близькою до свого максимального значення, 1. Достатньо близька означає наступну умову зупинки:

   ${\displaystyle 1-{\frac {\lambda _{\min }(\mu _{i}^{(k)})}{\lambda _{\max }(\mu _{i}^{(k)})}}<\varepsilon _{C}}$

   Миколайчик та Шмід (2004) мали добрий успіх з ${\displaystyle \epsilon _{C}=0.05}$.

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

Обчислювальну складність гаррісового афінного виявляча розбито на дві частини: початкове виявляння точок, та афінне унормовування областей. Алгоритм початкового виявляння точок, Гарріса — Лапласа, має складність ${\displaystyle {\mathcal {O}}(n)}$, де ${\displaystyle n}$ — число пікселів у зображенні. Алгоритм афінного унормовування області автоматично виявляє масштаб та оцінює матрицю пристосовування форми, ${\displaystyle U}$. Цей процес має складність ${\displaystyle {\mathcal {O}}((m+k)p)}$, де ${\displaystyle p}$ — кількість початкових точок, ${\displaystyle m}$ — розмір простору пошуку для автоматичного обирання масштабу, а ${\displaystyle k}$ — число ітерацій, необхідних для обчислення матриці ${\displaystyle U}$.

Існують деякі методи зменшення складності цього алгоритму ціною точності. Одним із методів є усунення пошуку на кроці масштабу диференціювання. Замість обирати коефіцієнт ${\displaystyle s}$ з набору коефіцієнтів, прискорений алгоритм обирає масштаб, який буде сталим для всіх ітерацій та точок: ${\displaystyle \sigma _{D}=s\sigma _{I},\;s=constant}$. Хоч це скорочення простору пошуку й може зменшувати складність, ця зміна може серйозно впливати на збіжність матриці ${\displaystyle U}$.

Аналіз

Збіжність

Можливо уявити, що цей алгоритм може встановлювати ідентичні особливі точки в різних масштабах. Оскільки гаррісів афінний алгоритм розглядає кожну початкову точку, задану виявлячем Гарріса — Лапласа, незалежно, розрізнення ідентичних точок немає. На практиці було показано, що всі ці точки зрештою збігатимуться до однієї й тієї ж особливої точки. Після завершення встановлювання всіх особливих точок алгоритм враховує дублікати шляхом порівнювання просторових координат (${\displaystyle \mathbf {x} }$), масштабу інтегрування ${\displaystyle \sigma _{I}}$, міри ізотропності ${\displaystyle {\tfrac {\lambda _{\min }(U)}{\lambda _{\max }(U)}}}$, та скосу. Якщо ці параметри особливих точок схожі в межах заданого порогу, їх позначають як дублікати. Алгоритм відкидає всі ці дубльовані точки, за винятком особливої точки, найближчої до усереднення цих дублікатів. Зазвичай 30 % гаррісових афінних точок є достатньо відмінними та несхожими, щоб не бути відкинутими.

Миколайчик та Шмід (2004) показали, що початкові точки часто (40 %) не збігаються. Цей алгоритм виявляє цю розбіжність, зупиняючи ітеративний алгоритм, якщо обернення міри ізотропності перевищує заданий поріг: ${\displaystyle {\tfrac {\lambda _{\max }(U)}{\lambda _{\min }(U)}}>t_{\text{diverge}}}$. Миколайчик та Шмід (2004) використовують ${\displaystyle t_{diverge}=6}$. Для тих, які дійсно збігалися, типове число необхідних ітерацій становило 10.

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

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

${\displaystyle R_{\text{score}}={\frac {C(A,B)}{\min(n_{A},n_{B})}}}$

де ${\displaystyle C(A,B)}$ — число відповідних точок у зображеннях ${\displaystyle A}$ та ${\displaystyle B}$. ${\displaystyle n_{B}}$ та ${\displaystyle n_{A}}$ — число виявлених точок у відповідних зображеннях. Оскільки кожне зображення подає тривимірний простір, може ставатися так, що одне зображення містить об'єкти, відсутні в другому зображенні, й відтак особливі точки яких не мають шансів мати відповідні. Щоби зробити міру повторюваності чинною, ці точки усувають, і мусять враховувати лише точки, що лежать на обох зображеннях; ${\displaystyle n_{A}}$ та ${\displaystyle n_{B}}$ враховують ці точки так, що ${\displaystyle x_{A}=H\cdot x_{B}}$. Для пари з двох зображень, пов'язаних через матрицю ^[en] ${\displaystyle H}$, кажуть, що дві точки ${\displaystyle \mathbf {x_{a}} }$ та ${\displaystyle \mathbf {x_{b}} }$ відповідні, якщо

Область перекриття двох еліптичних областей.

1. Похибка в положеннях пікселів менша за 1,5 пікселі: ${\displaystyle \|\mathbf {x_{a}} -H\cdot \mathbf {x_{b}} \|<1.5}$
2. По́хибка перекриття́ (англ. overlap error) цих двох афінних точок (${\displaystyle \epsilon _{S}}$) мусить бути меншою за вказаний поріг (зазвичай 40 %). Для афінних областей ця похибка перекриття така:

   ${\displaystyle \epsilon _{S}=1-{\frac {\mu _{a}\cap (H^{T}\mu _{b}H)}{\mu _{a}\cup (H^{T}\mu _{b}H)}}}$

   де ${\displaystyle \mu _{a}}$ та ${\displaystyle \mu _{b}}$ — встановлені еліптичні області, чиї точки задовольняють ${\displaystyle \mu ^{T}\mathbf {x} \mu =1}$. По суті, ця міра бере відношення двох площ: площі перекриття (перетину), та загальної площі (об'єднання). Ідеальне перекриття матиме одиничне відношення, і матиме ${\displaystyle \epsilon _{S}=0}$. Різні масштаби впливають на область перекриття, й відтак мусять враховуватися унормовуванням площ кожної з особливих областей. Області з похибкою перекриття до 50 % — придатні виявлячі для зіставляння їх із добрим описувачем.

   Друга міра, оці́нка збі́гу (англ. matching score), оцінює здатність виявляча встановлювати відповідні точки між зображеннями практичніше. Для встановлювання відповідних точок Миколайчик та Шмід (2005) використовують описувач SIFT. На додачу до того, щоби бути найближчими точками в просторі SIFT, дві відповідні точки також мусять мати достатньо малу похибку перекриття (як визначено в мірі повторюваності). Оцінка збігу — це відношення числа зіставлених точок та мінімуму всіх виявлених точок у кожному зображенні:

   ${\displaystyle M_{score}={\frac {M(A,B)}{\min(n_{A},n_{B})}}}$,

   де ${\displaystyle M(A,B)}$ — число зіставлених точок, а ${\displaystyle n_{B}}$ та ${\displaystyle n_{A}}$ — числа виявлених областей у відповідних зображеннях.

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

Миколайчик зі співавт. (2005) провели ретельний аналіз кількох афінних виявлячів областей рівня останніх досягнень: гаррісового афінного, гессіанного афінного виявлячів, МСЕО, областей на основі екстремумів яскравості (англ. IBR) та на основі контурів (англ. EBR), та ^[en] виявляча. У ході свого оцінювання Миколайчик зі співавт. аналізували як структуровані, так і текстуровані зображення. Двійкові файли цих виявлячів для Лінукс та їхні перевірні зображення доступні вільно на їхній вебсторінці. Далі йде короткий підсумок результатів Миколайчика зі співавт. (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 року.
• [2] — Лабораторія комп'ютерного бачення Корделії Шмід
• [3] — код, перевірні зображення, бібліографія афінних коваріантних ознак, які ведуть Крістіан Миколайчик та Група візуальної геометрії з Групи робототехніки Оксфордського університету.
• [4] — бібліографія виявлячів ознак (і плям), підтримувана Інститутом робототехніки та інтелектуальних систем Університету Південної Каліфорнії
• [5] — Цифрове втілення лапласіана гауссіана

Див. також

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

Примітки

1. K. Mikolajczyk, T. Tuytelaars, C. Schmid, A. Zisserman, J. Matas, F. Schaffalitzky, T. Kadir and L. Van Gool, A comparison of affine region detectors. In IJCV 65(1/2):43-72, 2005 (англ.)
2. Mikolajcyk, K. and Schmid, C. 2002. An affine invariant interest point detector. In Proceedings of the 8th International Conference on Computer Vision, Vancouver, Canada. [ 2004-07-23 у Wayback Machine.] (англ.)
3. 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. (англ.)
4. A. Baumberg (2000). "Reliable feature matching across widely separated views". Proceedings of IEEE Conference on Computer Vision and Pattern Recognition: pages I:1774—1781. (англ.)
5. Lindeberg, Tony, Scale-Space Theory in Computer Vision, Kluwer Academic Publishers, 1994, (англ.)
6. T. Lindeberg (1998). "Feature detection with automatic scale selection". International Journal of Computer Vision 30 (2): pp 77—116. (англ.)
7. Lindeberg, T. (2008). Scale-space. У Wah, Benjamin (ред.). Encyclopedia of Computer Science and Engineering. Т. IV. John Wiley and Sons. с. 2495—2504. doi:10.1002/9780470050118.ecse609. ISBN . (англ.)
8. C. Harris and M. Stephens (1988). "A combined corner and edge detector". Proceedings of the 4th Alvey Vision Conference: pages 147—151. [ 2007-09-16 у Wayback Machine.] (англ.)
9. 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. [ 2012-02-09 у Wayback Machine.] (англ.)
10. Schmid, C., Mohr, R., and Bauckhage, C. 2000. Evaluation of interest point detectors. International Journal of Computer Vision, 37(2):151-172. (англ.)
11. Mikolajczyk, K. and Schmid, C. 2004. Scale & affine invariant interest point detectors. International Journal on Computer Vision 60(1):63-86. (англ.)
12. Spatial Filters: Laplacian/Laplacian of Gaussian [ 2007-11-20 у Wayback Machine.] (англ.)
13. C. Schmid, R. Mohr, and C. Bauckhage. Comparing and evaluating interest points. In International Conference on Computer Vision, pp. 230-135, 1998. (англ.)
14. J.Matas, O. Chum, M. Urban, and T. Pajdla, Robust wide baseline stereo from maximally stable extremal regions. In BMVC p. 384-393, 2002. (англ.)
15. T. Tuytelaars and L. Van Gool, Matching widely separated views based on affine invariant regions. In IJCV 59(1):61-85, 2004. (англ.)
16. T. Kadir, A. Zisserman, and M. Brady, An affine invariant salient region detector. In ECCV p. 404-416, 2004. (англ.)
17. http://staff.science.uva.nl/~gevers/pub/overview.pdf (англ.)
18. R. Datta, J. Li, and J. Z. Wang, “Content-based image retrieval - Approaches and trends of the new age,” In Proc. Int. Workshop on Multimedia Information Retrieval, pp. 253-262, 2005.IEEE Transactions on Multimedia, vol. 7, no. 1, pp. 127-142, 2005. [ 2007-09-28 у Wayback Machine.] (англ.)
19. J. Sivic and A. Zisserman. Video google: A text retrieval approach to object matching in videos. In Proceedings of the International Conference on Computer Vision, Nice, France, 2003.^{[недоступне посилання]} (англ.)
20. J. Sivic and A. Zisserman. Video data mining using configurations of viewpoint invariant regions. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Washington DC, USA, pp. 488-495, 2004.^{[недоступне посилання]} (англ.)
21. G. Dorko and C. Schmid. Selection of scale invariant neighborhoods for object class recognition. In Proceedings of International Conference on Computer Vision, Nice, France, pp. 634-640, 2003. (англ.)
22. Beril Sirmacek and Cem Unsalan (January 2011). A probabilistic framework to detect buildings in aerial and satellite images (PDF). IEEE Transactions on Geoscience and Remote Sensing. 49 (1): 211—221. Bibcode:2011ITGRS..49..211S. doi:10.1109/TGRS.2010.2053713. S2CID 10637950. (англ.)