Виявляння кутів

Вихід типового алгоритму виявляння кутів

Виявляння ознак
Виявляння контурів
Кенні Деріша Диференціальне Собеля Прюітт Робертса
Виявляння кутів
Гарріса Сі та Томазі Кривина ізоліній міри вираженості гессіанових ознак SUSAN FAST
Виявляння плям
Лапласіан гауссіана (ЛГ, LoG) Різниця гауссіанів (РГ, DoG) Визначник гессіана (ВГ, DoH) МСЕО (MSER) PCBR
Виявляння хребтів
Перетворення Гафа
Перетворення Гафа Узагальнене перетворення Гафа
Структурний тензор
Структурний тензор Узагальнений структурний тензор
Афінноінваріантне виявляння ознак
Афінне пристосовування форми Афінне Гарріса Афінне гесіанне
Опис ознак
SIFT SURF GLOH HOG
Простір масштабів
Масштабопросторові аксіоми Деталі втілення Піраміди

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

Формалізація

Кут можливо визначити як перетин двох контурів. Кут також можливо визначити як точку, для якої існують два панівних і різних напрями контуру в локальному околі цієї точки.

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

На практиці більшість так званих методів виявляння кутів виявляють особливі точки загалом, і насправді терміни «кут» (англ. "corner") та «особлива точка» (англ. "interest point") використовують у літературі більш-менш взаємозамінно. Як наслідок, якщо потрібно виявляти лише кути, необхідно робити локальний аналіз виявлених особливих точок, щоби визначати, які з них є справжніми кутами. Прикладами виявляння країв, які можливо використовувати з післяопрацюванням для виявляння кутів, є оператор Кірша та набір масок Фрая — Чена.

Терміни «кут», «особлива точка» й «ознака» (англ. "feature") використовують у літературі як синоніми, що заплутує питання. Зокрема, існує кілька виявлячів плям, які можливо називати «операторами особливих точок», але які іноді помилково називають «виявлячами кутів». Крім того, існує поняття виявляння хребтів для вловлювання наявності витягнутих об'єктів.

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

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

Простий підхід до виявляння кутів у зображеннях — використання кореляції, але це дуже обчислювально витратно й неоптимально. Часто вживаний альтернативний підхід ґрунтується на методі, запропонованому Гаррісом та Стівенсом (нижче), який, своєю чергою, є вдосконаленням методу Моравека.

Алгоритм Моравека виявляння кутів

Це один з найперших алгоритмів виявляння кутів, який визначає кут (англ. corner) як точку з низькою самоподібністю. Цей алгоритм перевіряє кожен піксель у зображенні на наявність кута, розглядаючи, наскільки фрагмент з центром у цьому пікселі схожий на сусідні фрагменти, що значною мірою перекриваються. Подібність вимірюється шляхом отримання суми квадратів різниць (СКР) між відповідними пікселями двох фрагментів. Менше число вказує на більшу схожість.

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

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

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

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

Алгоритми Гарріса й Стівенса / Сі — Томазі виявляння кутів

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

Без втрати загальності вважатимемо, що використовується двовимірне зображення у відтінках сірого. Нехай це зображення задано через $I$. Розгляньмо взяття фрагменту зображення над областю $(u,v)$, й зміщення його на $(x,y)$. Зважена сума квадратів різниць (СКР) між цими двома фрагментами, позначувана через $S$, задається як

$S(x,y)=\sum _{u}\sum _{v}w(u,v)\,\left(I(u+x,v+y)-I(u,v)\right)^{2}$

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

$I(u+x,v+y)\approx I(u,v)+I_{x}(u,v)x+I_{y}(u,v)y$

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

$S(x,y)\approx \sum _{u}\sum _{v}w(u,v)\,\left(I_{x}(u,v)x+I_{y}(u,v)y\right)^{2},$

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

$S(x,y)\approx {\begin{bmatrix}x&y\end{bmatrix}}A{\begin{bmatrix}x\\y\end{bmatrix}},$

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

$A=\sum _{u}\sum _{v}w(u,v){\begin{bmatrix}I_{x}(u,v)^{2}&I_{x}(u,v)I_{y}(u,v)\\I_{x}(u,v)I_{y}(u,v)&I_{y}(u,v)^{2}\end{bmatrix}}={\begin{bmatrix}\langle I_{x}^{2}\rangle &\langle I_{x}I_{y}\rangle \\\langle I_{x}I_{y}\rangle &\langle I_{y}^{2}\rangle \end{bmatrix}}$

Словами, ми знаходимо коваріацію частинної похідної яскравості зображення $I$ відносно осей $x$ та $y$.

Кутові дужки позначують усереднення (тобто підсумовування над $(u,v)$). $w(u,v)$ позначує тип вікна, що ковзає зображенням. При використанні коробкового фільтра відгук буде анізотропним, але при використані гауссового фільтра відгук буде ізотропним.

Кут (або особлива точка загалом) характеризується великою мінливістю $S$ у всіх напрямках вектора ${\begin{bmatrix}x&y\end{bmatrix}}$. Через аналіз власних значень $A$ цю характеристику можливо виразити наступним чином: для особливої точки $A$ повинен мати два «великі» власні значення. Виходячи з цього аргументу, на основі величини власних значень можливо робити наступні висновки:

1. Якщо $\lambda _{1}\approx 0$ і $\lambda _{2}\approx 0$, то цей піксель $(x,y)$ не має особливих ознак.
2. Якщо $\lambda _{1}\approx 0$, а $\lambda _{2}$ має деяке велике додатне значення, то знайдено контур.
3. Якщо $\lambda _{1}$ і $\lambda _{2}$ мають великі додатні значення, то знайдено кут.

Гарріс і Стівенс відзначають, що точне обчислення власних значень є обчислювально витратним, оскільки вимагає обчислення квадратного кореня, й натомість пропонують наступну функцію $M_{c}$, де $\kappa$ є налаштовуваним параметром чутливості:

$M_{c}=\lambda _{1}\lambda _{2}-\kappa \left(\lambda _{1}+\lambda _{2}\right)^{2}=\det(A)-\kappa \operatorname {trace} ^{2}(A)$

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

Алгоритм Сі — Томазі виявляння кутів обчислює $\min(\lambda _{1},\lambda _{2})$ безпосередньо, оскільки за певних припущень кути є стійкішими для відстежування. Зауважте, що цей метод іноді називають алгоритмом Канаде — Томазі виявляння кутів.

Значення $\kappa$ має визначатися емпірично, в літературі повідомляють, що придатними є значення в проміжку 0,04–0,15.

Можливо уникнути встановлювання параметра $\kappa$ шляхом використання кутової міри Нобла $M_{c}'$, що дорівнює середньому гармонійному власних значень:

$M_{c}'=2{\frac {\det(A)}{\operatorname {trace} (A)+\epsilon }},$

де $\epsilon$ — невелика додатна стала.

Якщо $A$ можливо інтерпретувати як матрицю прецизійності для положення кута, то коваріаційною матрицею для положення кута є $A^{-1}$, тобто

${\frac {1}{\langle I_{x}^{2}\rangle \langle I_{y}^{2}\rangle -\langle I_{x}I_{y}\rangle ^{2}}}{\begin{bmatrix}\langle I_{y}^{2}\rangle &-\langle I_{x}I_{y}\rangle \\-\langle I_{x}I_{y}\rangle &\langle I_{x}^{2}\rangle \end{bmatrix}}.$

Сума власних значень $A^{-1}$, яку в цьому випадку можливо інтерпретувати як узагальнену дисперсію (або «повну невизначеність») положення кута, пов'язана з кутовою мірою Нобла $M_{c}'$ наступним рівнянням:

$\lambda _{1}(A^{-1})+\lambda _{2}(A^{-1})={\frac {\operatorname {trace} (A)}{\det(A)}}\approx {\frac {2}{M_{c}'}}.$

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

Виявлення кута за допомогою алгоритму Ферстнера

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

Рівняння дотичної $T_{\mathbf {x} '}(\mathbf {x} )$ в пікселі $\mathbf {x} '$ задається як

$T_{\mathbf {x'} }(\mathbf {x} )=\nabla I(\mathbf {x'} )^{\top }(\mathbf {x} -\mathbf {x'} )=0$

де $\nabla I(\mathbf {x'} )={\begin{bmatrix}I_{\mathbf {x} }&I_{\mathbf {y} }\end{bmatrix}}^{\top }$ — вектор градієнта зображення $I$ в $\mathbf {x'}$.

Точка $\mathbf {x} _{0}$, найближча до всіх дотичних у вікні $N$, це

$\mathbf {x} _{0}={\underset {\mathbf {x} \in \mathbb {R} ^{2\times 1}}{\operatorname {argmin} }}\int _{\mathbf {x'} \in N}T_{\mathbf {x'} }(\mathbf {x} )^{2}d\mathbf {x'}$

Відстань від $\mathbf {x} _{0}$ до дотичних $T_{\mathbf {x'} }$ зважується величиною градієнта, що надає більшого значення дотичним, які проходять через пікселі з сильними градієнтами.

Розв'язання для $\mathbf {x} _{0}$:

${\begin{aligned}\mathbf {x} _{0}&={\underset {\mathbf {x} \in \mathbb {R} ^{2\times 1}}{\operatorname {argmin} }}\int _{\mathbf {x'} \in N}\left(\nabla I\left(\mathbf {x'} \right)^{\top }\left(\mathbf {x} -\mathbf {x'} \right)\right)^{2}d\mathbf {x'} \\&={\underset {\mathbf {x} \in \mathbb {R} ^{2\times 1}}{\operatorname {argmin} }}\int _{\mathbf {x'} \in N}(\mathbf {x} -\mathbf {x'} )^{\top }\nabla I(\mathbf {x'} )\nabla I(\mathbf {x'} )^{\top }(\mathbf {x} -\mathbf {x'} )d\mathbf {x'} \\&={\underset {\mathbf {x} \in \mathbb {R} ^{2\times 1}}{\operatorname {argmin} }}\left(\mathbf {x} ^{\top }A\mathbf {x} -2\mathbf {x} ^{\top }\mathbf {b} +c\right)\end{aligned}}$

$A\in \mathbb {R} ^{2\times 2},{\textbf {b}}\in \mathbb {R} ^{2\times 1},c\in \mathbb {R}$ визначаються як:

${\begin{aligned}A&=\int \nabla I(\mathbf {x'} )\nabla I(\mathbf {x'} )^{\top }d\mathbf {x'} \\\mathbf {b} &=\int \nabla I(\mathbf {x'} )\nabla I(\mathbf {x'} )^{\top }\mathbf {x'} d\mathbf {x'} \\c&=\int \mathbf {x'} ^{\top }\nabla I(\mathbf {x'} )\nabla I(\mathbf {x'} )^{\top }\mathbf {x'} d\mathbf {x'} \\\end{aligned}}$

Мінімізувати це рівняння можливо диференціюванням за $x$ і прирівнюванням до 0:

$2A\mathbf {x} -2\mathbf {b} =0\Rightarrow A\mathbf {x} =\mathbf {b}$

Зауважте, що $A\in \mathbb {R} ^{2\times 2}$ — структурний тензор. Щоби це рівняння мало розв'язок, $A$ мусить бути оборотною, що означає, що $A$ мусить бути матрицею повного рангу (рангу 2). Таким чином, розв'язок

$x_{0}=A^{-1}\mathbf {b}$

існує лише там, де у вікні $N$ справді є кут.

Методологію виконання автоматичного обирання масштабу (англ. automatic scale selection) для цього методу визначення положень кутів було представлено Ліндебергом, через мінімізування нормованого залишку

${\tilde {d}}_{\min }={\frac {c-b^{T}A^{-1}b}{\operatorname {trace} A}}$

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

Примітки:

• $c$ можливо розглядати як залишок при обчисленні розв'язку методом найменших квадратів: якщо $c=0$, то похибки не було.
• цей алгоритм можливо видозмінити, щоби обчислювати центри кругових об'єктів, замінивши дотичні лінії на перпендикуляри.

Багатомасштабовий оператор Гарріса

Обчислення матриці другого моменту (яку іноді також називають структурним тензором) $A$ в операторі Гарріса вимагає обчислення похідних зображення $I_{x},I_{y}$ в області визначення зображення, а також підсумовування нелінійних комбінацій цих похідних по локальних околах. Оскільки обчислення похідних зазвичай включає етап просторово-масштабового згладжування, операційне визначення оператора Гарріса вимагає двох параметрів масштабу: (i) локального масштабу (англ. local scale) для згладжування перед обчисленням похідних зображення, та (ii) масштабу інтегрування (англ. integration scale) для накопичування нелінійних операцій над операторами похідних до інтегрованого описувача зображення.

Із позначенням первинної яскравості зображення через $I$, нехай $L$ позначує масштабопросторове подання $I$, отримане згорткою гауссовим ядром

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

з параметром локального масштабу $t$:

$L(x,y,t)\ =g(x,y,t)*I(x,y)$

і нехай $L_{x}=\partial _{x}L$ та $L_{y}=\partial _{y}L$ позначують частинні похідні від $L$. Крім того, введімо віконну гауссову функцію $g(x,y,s)$ з параметром масштабу інтегрування $s$. Тоді багатомасштабову матрицю другого моменту (англ. multi-scale second-moment matrix) можливо визначити через

$\mu (x,y;t,s)=\int _{\xi =-\infty }^{\infty }\int _{\eta =-\infty }^{\infty }{\begin{bmatrix}L_{x}^{2}(x-\xi ,y-\eta ;t)&L_{x}(x-\xi ,y-\eta ;t)\,L_{y}(x-\xi ,y-\eta ;t)\\L_{x}(x-\xi ,y-\eta ;t)\,L_{y}(x-\xi ,y-\eta ;t)&L_{y}^{2}(x-\xi ,y-\eta ;t)\end{bmatrix}}g(\xi ,\eta ;s)\,d\xi \,d\eta .$

Тоді ми можемо обчислити власні значення $\mu$ подібно до власних значень $A$, й визначити багатомасштабову кутову міру Гарріса (англ. multi-scale Harris corner measure) через

$M_{c}(x,y;t,s)=\det(\mu (x,y;t,s))-\kappa \,\operatorname {trace} ^{2}(\mu (x,y;t,s)).$

Щодо вибору параметра локального масштабу $t$ та параметру масштабу інтегрування $s$, ці параметри масштабу зазвичай пов'язано відносним параметром масштабу інтегрування $\gamma$ через $s=\gamma ^{2}t$, де $\gamma$ зазвичай обирають з проміжку $[1,2]$. Таким чином, ми можемо обчислювати багатомасштабову кутову міру Гарріса $M_{c}(x,y;t,\gamma ^{2}t)$ на будь-якому масштабі $t$ в просторі масштабів, щоб отримувати багатомасштабовий виявляч кутів, що реагує на кутові структури різних розмірів в області визначення зображення.

На практиці цей багатомасштабовий виявляч кутів часто доповнюють кроком обрання масштабу (англ. scale selection step), де нормований за масштабом оператор Лапласа

$\nabla _{\mathrm {norm} }^{2}L(x,y;t)\ =t\nabla ^{2}L(x,y,t)=t(L_{xx}(x,y,t)+L_{yy}(x,y,t))$

обчислюють на кожному масштабі в просторі масштабів, а масштабодопасовані кутові точки з автоматичним вибором масштабу (англ. scale adapted corner points with automatic scale selection, «оператор Гарріса — Лапласа», англ. "Harris-Laplace operator") обчислюють із точок, які є одночасно:

• просторовими максимумами багатомасштабової кутової міри $M_{c}(x,y;t,\gamma ^{2}t)$

  $({\hat {x}},{\hat {y}};t)=\operatorname {argmaxlocal} _{(x,y)}M_{c}\left(x,y;t,\gamma ^{2}t\right)$

• локальними максимумами або мінімуми за масштабами масштабонормованого оператора Лапласа $\nabla _{\mathrm {norm} }^{2}(x,y,t)$:

  ${\hat {t}}=\operatorname {argmaxminlocal} _{t}\nabla _{\mathrm {norm} }^{2}L({\hat {x}},{\hat {y}};t)$

Підхід кривини ізоліній

Один з раніших підходів до виявляння кутів полягає у виявлянні точок, де кривина ізоліній та величина градієнта високі одночасно. Диференціальним способом виявляння таких точок є обчислення перемасштабованої кривини ізоліній (англ. rescaled level curve curvature, добутку кривизни ізолінії та величини градієнта у третьому степені)

${\tilde {\kappa }}(x,y;t)=L_{x}^{2}L_{yy}+L_{y}^{2}L_{xx}-2L_{x}L_{y}L_{xy}$

і виявляння додатних максимумів та від'ємних мінімумів цього диференціального виразу в певному масштабі $t$ в масштабопросторовому поданні $L$ первинного зображення. Проте основна проблема при обчисленні сутності перемасштабованої кривини ізоліній в одному масштабі полягає в тому, що вона може бути чутливою до шуму та вибору рівня масштабу. Кращий метод — обчислювати $\gamma$-нормовану перемасштабовану кривину ізоліній

${\tilde {\kappa }}_{\mathrm {norm} }(x,y;t)=t^{2\gamma }(L_{x}^{2}L_{yy}+L_{y}^{2}L_{xx}-2L_{x}L_{y}L_{xy})$

з $\gamma =7/8$, і виявляти знакові масштабопросторові екстремуми цього виразу, тобто точки та масштаби, що є додатними максимумами та від'ємними мінімумами відносно як простору, так і масштабу,

$({\hat {x}},{\hat {y}};{\hat {t}})=\operatorname {argminmaxlocal} _{(x,y;t)}{\tilde {\kappa }}_{\mathrm {norm} }(x,y;t)$

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

Масштабопросторові особливі точки лапласіана гауссіана, різниці гауссіанів та визначника гессіана

ЛГ (англ. LoG) — це абревіатура, що означає лапласіан гауссіана (англ. Laplacian of Gaussian), РГ (англ. DoG) — абревіатура, що означає різницю гауссіанів (англ. difference of Gaussians, РГ — це наближення ЛГ), а ВГ (англ. DoH) — абревіатура, що означає визначник гессіана (англ. determinant of the Hessian). Усі ці масштабоінваріантні особливі точки виділяються виявлянням масштабопросторових екстремумів масштабонормованих диференціальних виразів, тобто точок у масштабопросторовому поданні, де відповідні масштабонормовані диференціальні вирази набувають локальних екстремумів як у просторі, так і серед масштабів.

$({\hat {x}},{\hat {y}};{\hat {t}})=\operatorname {argminmaxlocal} _{(x,y;t)}(D_{\mathrm {norm} }L)(x,y;t)$

де $D_{norm}L$ позначує відповідну масштабонормовану диференціальну сутність (визначену нижче).

Ці виявлячі повніше описано у виявлянні плям. Масштабонормовані ознаки лапласіана гауссіана та різниці гауссіанів (Ліндеберг 1994, 1998; Лоу 2004)

${\begin{aligned}\nabla _{\mathrm {norm} }^{2}L(x,y;t)&=t\,(L_{xx}+L_{yy})\\&\approx {\frac {t\left(L(x,y;t+\Delta t)-L(x,y;t)\right)}{\Delta t}}\end{aligned}}$

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

Масштабонормований визначник оператора Гессе (Ліндеберг 1994, 1998)

$\det H_{\mathrm {norm} }L=t^{2}(L_{xx}L_{yy}-L_{xy}^{2})$,

з іншого боку, є дуже вибірковим до добре локалізованих ознак у зображенні й реагує лише тоді, коли присутні значні мінливості рівня сірого в двох напрямках зображення, і в цьому та інших відношеннях є кращим виявлячем особливих точок, ніж лапласіан гауссіана. Визначник гессіана — афінний коваріантний диференціальний вираз, і має кращі властивості обирання масштабу за афінних перетворень зображення, ніж лапласіан (Ліндеберг 2013, 2015). Експериментально це означає, що особливі точки детермінанта гессіана мають кращі властивості повторюваності при локальній деформації зображення, ніж особливі точки лапласіана, що своєю чергою призводить до кращої продуктивності зіставляння на основі зображень з точки зору вищих показників ефективності (англ. efficiency) та нижчих оцінок 1−влучність (англ. 1−precision).

Властивості обирання масштабу, властивості афінного перетворення та експериментальні властивості цих та інших виявлячів масштабопросторових особливих точок докладно проаналізовано в (Ліндеберг 2013, 2015).

Масштабопросторові особливі точки на основі ліндебергових мір вираженості гессіанових ознак

Натхнений структурно подібними властивостями матриці Гессе $Hf$ функції $f$ та матриці других моментів (структурного тензора) $\mu$, що, наприклад, може проявлятися в термінах їхніх подібних властивостей перетворення при афінних деформаціях зображення

$(Hf')=A^{-T}\,(Hf)\,A^{-1}$ ,

$\mu '=A^{-T}\,\mu \,A^{-1}$ ,

Ліндеберг (2013, 2015) запропонував визначати чотири міри вираженості ознак з матриці Гессе подібним чином, як оператори Гарріса та Сі й Томазі визначаються зі структурного тензора (матриці других моментів). Зокрема, він визначив такі беззнакові й знакові міри вираженості гессіанових ознак:

• беззнакова міра вираженості гессіанової ознаки I:

  $D_{1,\mathrm {norm} }L={\begin{cases}t^{2}\,(\det HL-k\,\operatorname {trace} ^{2}HL)&{\mbox{якщо}}\,\det HL-k\,\operatorname {trace} ^{2}HL>0\\0&{\mbox{інакше}}\end{cases}}$

• знакова міра вираженості гессіанової ознаки I:

  ${\tilde {D}}_{1,\mathrm {norm} }L={\begin{cases}t^{2}\,(\det HL-k\,\operatorname {trace} ^{2}HL)&{\mbox{якщо}}\,\det HL-k\,\operatorname {trace} ^{2}HL>0\\t^{2}\,(\det HL+k\,\operatorname {trace} ^{2}HL)&{\mbox{якщо}}\,\det HL+k\,\operatorname {trace} ^{2}HL<0\\0&{\mbox{інакше}}\end{cases}}$

• беззнакова міра вираженості гессіанової ознаки II:

  $D_{2,\mathrm {norm} }L=t\,\min(|\lambda _{1}(HL)|,|\lambda _{2}(HL)|)$

• знакова міра вираженості гессіанової ознаки II:

  ${\tilde {D}}_{2,\mathrm {norm} }L={\begin{cases}t\,\lambda _{1}(HL)&{\mbox{якщо}}\,|\lambda _{1}(HL)|<|\lambda _{2}(HL)|\\t\,\lambda _{2}(HL)&{\mbox{якщо}}\,|\lambda _{2}(HL)|<|\lambda _{1}(HL)|\\t\,(\lambda _{1}(HL)+\lambda _{2}(HL))/2&{\mbox{інакше}}\end{cases}}$

де $\operatorname {trace} HL=L_{xx}+L_{yy}$ та $\det HL=L_{xx}L_{yy}-L_{xy}^{2}$ позначують слід і визначник матриці Гессе $HL$ масштабопросторового подання $L$ на будь-якому масштабі $t$, тоді як

$\lambda _{1}(HL)=L_{pp}={\frac {1}{2}}\left(L_{xx}+L_{yy}-{\sqrt {(L_{xx}-L_{yy})^{2}+4L_{xy}^{2}}}\right)$

$\lambda _{2}(HL)=L_{qq}={\frac {1}{2}}\left(L_{xx}+L_{yy}+{\sqrt {(L_{xx}-L_{yy})^{2}+4L_{xy}^{2}}}\right)$

позначують власні значення матриці Гессе.

Беззнакова міра вираженості гессіанової ознаки $D_{1,\mathrm {norm} }L$ реагує на локальні екстремуми додатними значеннями й не чутлива до сідлових точок, тоді як знакова міра вираженості гессіанової ознаки ${\tilde {D}}_{1,\mathrm {norm} }L$ додатково реагує на сідлові точки від'ємними значеннями. Беззнакова міра вираженості гессіанової ознаки $D_{2,\mathrm {norm} }L$ нечутлива до локальної полярності сигналу, тоді як знакова міра вираженості гессіанової ознаки ${\tilde {D}}_{2,\mathrm {norm} }L$ реагує на локальну полярність сигналу знаком свого результату.

У Ліндеберга (2015) ці чотири диференціальні сутності було об'єднано з локальним обиранням масштабу на основі або виявляння масштабопросторових екстремумів

$({\hat {x}},{\hat {y}};{\hat {t}})=\operatorname {argminmaxlocal} _{(x,y;t)}(D_{\mathrm {norm} }L)(x,y;t)$,

або зв'язування масштабів (англ. scale linking). Крім того, знакові та беззнакові міри вираженості гессіанової ознаки $D_{2,\mathrm {norm} }L$ та ${\tilde {D}}_{2,\mathrm {norm} }L$ було поєднано з додатковим порогуванням $D_{1,\mathrm {norm} }L>0$.

Шляхом експериментів із зіставляння зображень за масштабувальних перетворень на наборі даних з 12 плакатів із зіставлянням з декількох точок огляду над масштабувальними перетвореннями до коефіцієнта масштабування 6 і змінами напряму точки огляду до кута нахилу 45 градусів з локальними описувачами зображення, визначеними з переформулювань чистих описувачів зображення в операторах SIFT і SURF для вимірювання зображень у термінах операторів похідної гауссіана (Gauss-SIFT і Gauss-SURF) замість первинного SIFT, визначеного з піраміди зображення, або первинного SURF, визначеного з гаарових вейвлетів, було показано, що виявляння масштабопросторових особливих точок на основі беззнакової міри вираженості гессіанової ознаки $D_{1,\mathrm {norm} }L$ дозволили отримати найкращу продуктивність, і кращу продуктивність, ніж масштабопросторові особливі точки, отримувані з визначника гессіана $\det H_{\mathrm {norm} }L=t^{2}\left(L_{xx}L_{yy}-L_{xy}^{2}\right)$. Як беззнакова міра вираженості гессіанової ознаки $D_{1,\mathrm {norm} }L$, так і знакова міра вираженості гессіанової ознаки ${\tilde {D}}_{1,norm}L$ і визначник гессіана $\det H_{norm}L$ дозволили отримати кращу продуктивність, ніж лапласіан гауссіана $\nabla _{\mathrm {norm} }^{2}L=t\,(L_{xx}+L_{yy})$. У поєднанні зі зв'язуванням масштабів та додатковим порогуванням $D_{1,\mathrm {norm} }L>0$ знакова міра вираженості гессіанової ознаки ${\tilde {D}}_{2,\mathrm {norm} }L$ до того ж дозволила отримати кращу продуктивність, ніж лапласіан гауссіана $\nabla _{\mathrm {norm} }^{2}L$.

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

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

Оператори афіннопристосованих особливих точок

Особливі точки, отримувані багатомасштабовим оператором Гарріса з автоматичним обиранням масштабу, інваріантні відносно паралельних перенесень, поворотів і рівномірного масштабування в просторовій області. Проте зображення, що є вхідними для систем комп'ютерного зору, зазнають також і перспективних спотворень. Щоб отримати оператор особливих точок, стійкіший до перспективних перетворень, природним підходом є розробка виявляча ознак, інваріантного до афінних перетворень. На практиці афінноінваріантні особливі точки можливо отримувати, застосовуючи афінне пристосовування форми, коли форма ядра згладжування ітеративно деформується, щоби зіставитися з локальною структурою зображення навколо особливої точки, або, рівнозначно, локальний фрагмент зображення ітеративно деформується, тоді як форма ядра згладжування залишається обертово симетричною (Ліндеберг 1993, 2008; Ліндеберг та Гардінг 1997; Міколайчик та Шмід 2004). Отже, крім використовуваного зазвичай багатомасштабового оператора Гарріса, афінне пристосовування форми можливо застосовувати й до інших виявлячів кутів, перелічених у цій статті, а також до диференціальних виявлячів плям, таких як оператор лапласіана/різниці гауссіанів, визначник гессіана та гессіанно-лапласіанний оператор.

Алгоритм Вонга та Брейді виявляння кутів

Виявляч Вонга та Брейді розглядає зображення як поверхню й шукає місця великої кривини вздовж контуру в зображенні. Іншими словами, цей алгоритм шукає місця, де контур швидко змінює напрямок. Кутова оцінка (англ. corner score), $C$, задається як

$C=\left({\frac {\delta ^{2}I}{\delta \mathbf {t} ^{2}}}\right)^{2}-c|\nabla I|^{2},$

де ${\bf {t}}$ — одиничний вектор, перпендикулярний градієнтові, а $c$ визначає контурофобність виявляча. Автори також відзначають, що для зменшення шуму необхідне згладжування (радять гауссове).

Згладжування також призводить до зміщення кутів, тому автори виводять вираз для зміщення кута в 90 градусів, і застосовують його як поправковий коефіцієнт до виявлених кутів.

Виявляч кутів SUSAN

SUSAN — це абревіатура, що означає найменший однорідний сегмент, що уподібнюється ядру (англ. smallest univalue segment assimilating nucleus). Цей метод є предметом патенту Великої Британії 1994 року, який більше не діє.

Для виявляння ознак SUSAN розміщує кругову маску на пікселі, який потрібно перевірити (ядрі, англ. nucleus). Областю маски є $M$, а піксель у цій масці подається через ${\vec {m}}\in M$. Ядро перебуває в ${\vec {m}}_{0}$. Кожен піксель порівнюється з ядром за допомогою функції порівняння

$c({\vec {m}})=e^{-\left({\frac {I({\vec {m}})-I({\vec {m}}_{0})}{t}}\right)^{6}}$

де $t$ — поріг різниці яскравості, $I$ — яскравість пікселя, а степінь експоненти визначено емпірично. Ця функція виглядає як згладжений циліндр, або прямокутна функція. Площа SUSAN визначається через

$n(M)=\sum _{{\vec {m}}\in M}c({\vec {m}})$

Якщо $c$ — прямокутна функція, то $n$ — кількість пікселів у масці, що перебувають в межах $t$ від ядра. Відгук оператора SUSAN задається через

$R(M)={\begin{cases}g-n(M)&{\mbox{якщо}}\ n(M)<g\\0&{\mbox{інакше,}}\end{cases}}$

де $g$ називається «геометричним порогом». Іншими словами, оператор SUSAN дає додатну оцінку лише якщо площа досить мала. Найменший SUSAN локально можливо знаходити за допомогою придушування немаксимумів, і це повний оператор SUSAN.

Значення $t$ визначає, наскільки подібними до ядра мають бути точки, щоби вважатися частиною однорідного сегмента (англ. univalue segment). Значення $g$ визначає мінімальний розмір однорідного сегмента. Якщо $g$ достатньо велике, то це стає виявлячем контурів.

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

Виявляч кутів Трайковича та Гедлі

Подібно до SUSAN, цей виявляч безпосередньо перевіряє, чи є пляма під пікселем самоподібною, досліджуючи сусідні пікселі. ${\vec {c}}$ — піксель, який потрібно розглянути, а ${\vec {p}}\in P$ — точка на колі $P$ з центром у ${\vec {c}}$. Точка ${\vec {p}}'$ — діаметрально протилежна до ${\vec {p}}$.

Функцію відгуку визначають через

$r({\vec {c}})=\min _{{\vec {p}}\in P}\left(\left(I({\vec {p}})-I({\vec {c}})\right)^{2}+\left(I({\vec {p}}')-I({\vec {c}})\right)^{2}\right)$

Він буде великим, якщо немає напряму, в якому центральний піксель подібний до двох сусідніх пікселів по діаметру. $P$ — дискретизоване коло (коло Брезенгема), тому для проміжних діаметрів використовують інтерполяцію, щоб отримувати ізотропніший відгук. Оскільки будь-яке обчислення дає верхню межу для $\min$, спочатку перевіряють горизонтальний і вертикальний напрямки, щоби побачити, чи варто продовжувати повне обчислення $c$.

Виявлячі ознак на основі AST

AST — це абревіатура, що означає прискорену сегментну перевірку (англ. accelerated segment test). Ця перевірка — розслаблена версія кутового критерію SUSAN. Замість оцінювання кругового диска розглядають лише пікселі на колі Брезенгема радіуса $r$ навколо точки — кандидата. Якщо всі $n$ суміжних пікселів яскравіші за ядро принаймні на $t$, або всі темніші за ядро на $t$, то піксель під ядром вважають ознакою. Повідомляють, що цей критерій дає дуже стабільні ознаки. Вибір порядку, в якому перевіряються пікселі, є так званою задачею двадцяти запитань. Побудова коротких дерев рішень для цієї задачі призводить до обчислювально найефективніших доступних виявлячів ознак.

Першим алгоритмом виявляння кутів на основі AST є FAST (ознаки з прискореної сегментної перевірки, англ. features from accelerated segment test). Хоча $r$ може в принципі набувати будь-якого значення, FAST використовує лише значення 3 (що відповідає колу в 16 пікселів на ньому), а перевірки показують, що найкращі результати досягаються, коли $n$ становить 9. Це значення $n$ є найнижчим, за якого не виявляються контури. Порядок, у якому перевіряються пікселі, визначається алгоритмом ID3 з тренувального набору зображень. Як не дивно, назва цього виявляча дещо схожа на назву статті, яка описує виявляч Трайковича та Гедлі.

Автоматичне синтезування виявлячів

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

Виявлячі просторово-часових особливих точок

Лаптєв та Ліндеберг розширили оператор Гарріса до простору-часу. Нехай $\mu$ позначує просторово-часову матрицю других моментів, визначену через

$A=\sum _{u}\sum _{v}\sum _{w}h(u,v,w){\begin{bmatrix}L_{x}(u,v,w)^{2}&L_{x}(u,v,w)L_{y}(u,v,w)&L_{x}(u,v,w)L_{t}(u,v,w)\\L_{x}(u,v,w)L_{y}(u,v,w)&L_{y}(u,v,w)^{2}&L_{y}(u,v,w)L_{t}(u,v,w)\\L_{x}(u,v,w)L_{t}(u,v,w)&L_{y}(u,v,w)L_{t}(u,v,w)&L_{t}(u,v,w)^{2}\\\end{bmatrix}}={\begin{bmatrix}\langle L_{x}^{2}\rangle &\langle L_{x}L_{y}\rangle &\langle L_{x}L_{t}\rangle \\\langle L_{x}L_{y}\rangle &\langle L_{y}^{2}\rangle &\langle L_{y}L_{t}\rangle \\\langle L_{x}L_{t}\rangle &\langle L_{y}L_{t}\rangle &\langle L_{t}^{2}\rangle \\\end{bmatrix}}$

Тоді для придатного вибору $k<1/27$ просторово-часові особливі точки виявляються з просторово-часових екстремумів наступної просторово-часової міри Гарріса:

$H=\det(\mu )-\kappa \,\operatorname {trace} ^{2}(\mu ).$

Визначник гессіана було розширено до спільного простору-часу Віллемсом та ін., та Ліндебергом, що дало наступний масштабонормований диференціальний вираз:

$\det(H_{(x,y,t),\mathrm {norm} }L)=\,s^{2\gamma _{s}}\tau ^{\gamma _{\tau }}\left(L_{xx}L_{yy}L_{tt}+2L_{xy}L_{xt}L_{yt}-L_{xx}L_{yt}^{2}-L_{yy}L_{xt}^{2}-L_{tt}L_{xy}^{2}\right).$

У праці Віллемса та ін. було використано простіший вираз, що відповідає $\gamma _{s}=1$ та $\gamma _{\tau }=1$. У Ліндеберга було показано, що $\gamma _{s}=5/4$ та $\gamma _{\tau }=5/4$ дають кращі масштабообиральні властивості в тому сенсі, що обирані рівні масштабу, отримувані з просторово-часової гауссової плями з просторовою протяжністю $s=s_{0}$ й часовою тривалістю $\tau =\tau _{0}$, ідеально відповідатимуть просторовій протяжності та часовій тривалості цієї плями, з виконанням обирання масштабу шляхом виявляння просторово-часових масштабопросторових екстремумів цього диференціального виразу.

Ліндеберг розширив оператор Лапласа на просторово-часові відеодані, що дало наступні два просторово-часові оператори, які також становлять моделі рецептивних полів нейронів БКЯ без запізнювання і з запізнюванням:

$\partial _{t,\mathrm {norm} }(\nabla _{(x,y),\mathrm {norm} }^{2}L)=s^{\gamma _{s}}\tau ^{\gamma _{\tau }/2}(L_{xxt}+L_{yyt}),$

$\partial _{tt,\mathrm {norm} }(\nabla _{(x,y),\mathrm {norm} }^{2}L)=s^{\gamma _{s}}\tau ^{\gamma _{\tau }}(L_{xxtt}+L_{yytt}).$

Для першого оператора потрібні властивості вибору масштабу $\gamma _{s}=1$ і $\gamma _{\tau }=1/2$, якщо ми хочемо, щоби цей оператор набував свого максимального значення над просторово-часовими масштабами на рівні просторово-часового масштабу, який відображає просторову протяжність і часову тривалість гауссової плями, яка з'являється. Для другого оператора потрібні властивості вибору масштабу $\gamma _{s}=1$ і $\gamma _{\tau }=3/4$, якщо ми хочемо, щоби цей оператор набував свого максимального значення над просторово-часовими масштабами на рівні просторово-часового масштабу, що відображає просторову протяжність і часову тривалість гауссової плями, яка зблимує.

Колірні розширення виявлячів просторово-часових особливих точок було досліджено Евертсом та ін.

Еталонні втілення

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

• Виявляння РГ [Архівовано 14 лютого 2007 у Wayback Machine.] (як частина системи SIFT), виконувані файли Windows та x86 Linux
• Гарріса — Лапласа [Архівовано 5 лютого 2012 у Wayback Machine.], статичні виконувані файли Linux. Також містить виявлячі РГ та ЛГ й афінне пристосовування для всіх включених виявлячів.
• Виявляч FAST [Архівовано 17 березня 2022 у Wayback Machine.], первинний код C, C++, MATLAB, і виконувані файли для різних операційних систем та архітектур.
• lip-vireo [Архівовано 11 травня 2017 у Wayback Machine.], виконувані файли [ЛГ, РГ, Гарріса — Лапласа, гессіанний і гессіанно-лапласіанний], [SIFT, віддзеркалювально-інваріантний SIFT, PCA-SIFT, PSIFT, Steerable Filters, SPIN], виконувані файли [Linux, Windows та SunOS].
• Низькорівнева обробка зображень SUSAN [Архівовано 26 квітня 2022 у Wayback Machine.], первинний код C.
• Онлайн-втілення гаррісового виявляча кутів — IPOL [Архівовано 14 лютого 2022 у Wayback Machine.]

Див. також

• виявляння плям
• афінне пристосовування форми
• простір масштабів
• виявляння хребтів
• виявляння особливих точок
• виявляння ознак (комп'ютерне бачення)
• похідна зображення

Посилання

• Lindeberg, Tony (2001), Corner detection, у Hazewinkel, Michiel (ред.), Математична енциклопедія, Springer, ISBN 978-1-55608-010-4 (англ.)
• Brostow, "Corner Detection — UCL Computer Science" [Архівовано 8 березня 2022 у Wayback Machine.] (англ.)