Виявля́ння куті́в (англ. corner detection) — це підхід, який використовують у системах комп'ютерного бачення для виділяння певних типів ознак і визначання вмісту зображення. Виявляння кутів часто використовують для виявляння руху, зіставляння зображень, відстежування у відео, [en], [en], тривимірної відбудови та [en]. Виявляння кутів перетинається з темою виявляння особливих точок.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpODFMelZtTDBOdmNtNWxjaTV3Ym1jdk16QXdjSGd0UTI5eWJtVnlMbkJ1Wnc9PS5wbmc=.png)
Формалізація
Кут можливо визначити як перетин двох контурів. Кут також можливо визначити як точку, для якої існують два панівних і різних напрями контуру в локальному околі цієї точки.
Особлива точка — це точка в зображенні, яка має чітко визначене положення, і її можливо надійно виявляти. Це означає, що особлива точка може бути кутом, але також може бути, наприклад, ізольованою точкою локального максимуму чи мінімуму яскравості, закінченнями лінії, або точкою на кривій, де кривина локально максимальна.
На практиці більшість так званих методів виявляння кутів виявляють особливі точки загалом, і насправді терміни «кут» (англ. "corner") та «особлива точка» (англ. "interest point") використовують у літературі більш-менш взаємозамінно. Як наслідок, якщо потрібно виявляти лише кути, необхідно робити локальний аналіз виявлених особливих точок, щоби визначати, які з них є справжніми кутами. Прикладами виявляння країв, які можливо використовувати з післяопрацюванням для виявляння кутів, є оператор Кірша та набір масок Фрая — Чена.
Терміни «кут», «особлива точка» й «ознака» (англ. "feature") використовують у літературі як синоніми, що заплутує питання. Зокрема, існує кілька виявлячів плям, які можливо називати «операторами особливих точок», але які іноді помилково називають «виявлячами кутів». Крім того, існує поняття виявляння хребтів для вловлювання наявності витягнутих об'єктів.
Виявлячі кутів зазвичай не дуже надійні й часто вимагають запровадження значного дублювання, щоби запобігати домінуванню окремих помилок в задачі розпізнавання.
Один з критеріїв якості виявляча кутів — його здатність виявляти один і той же кут на кількох подібних зображеннях в умовах різного освітлення, паралельного перенесення, повертання та інших перетворень.
Простий підхід до виявляння кутів у зображеннях — використання кореляції, але це дуже обчислювально витратно й неоптимально. Часто вживаний альтернативний підхід ґрунтується на методі, запропонованому Гаррісом та Стівенсом (нижче), який, своєю чергою, є вдосконаленням методу Моравека.
Алгоритм Моравека виявляння кутів
Це один з найперших алгоритмів виявляння кутів, який визначає кут (англ. corner) як точку з низькою самоподібністю. Цей алгоритм перевіряє кожен піксель у зображенні на наявність кута, розглядаючи, наскільки фрагмент з центром у цьому пікселі схожий на сусідні фрагменти, що значною мірою перекриваються. Подібність вимірюється шляхом отримання суми квадратів різниць (СКР) між відповідними пікселями двох фрагментів. Менше число вказує на більшу схожість.
Якщо піксель перебуває в області рівномірної яскравості, то найближчі фрагменти виглядатимуть подібно. Якщо піксель перебуває на контурі, то найближчі фрагменти в напрямку, перпендикулярному до контуру, виглядатимуть зовсім інакше, але найближчі фрагменти в напрямку, паралельному контуру, даватимуть лише незначні зміни. Якщо піксель перебуває на об'єкті зі змінами в усіх напрямках, то жоден із сусідніх фрагментів не буде схожим.
Вираженість кута визначається як найменша СКР між фрагментом та його сусідами (горизонтально, вертикально, та по двох діагоналях). Сенс у тому, що якщо це число велике, то мінливість вздовж усіх зміщень більше або дорівнює йому, вловлюючи, що всі найближчі фрагменти виглядають інакше.
Якщо значення вираженості кута обчислюється для всіх положень, то якщо воно локально максимальне для одного місця, це вказує на те, що в ньому присутня потрібна ознака.
Як зазначив Моравек, одна з головних проблем цього оператора полягає в його неізотропності: якщо присутній контур, що не перебуває в напрямку сусідів (горизонтально, вертикально чи діагонально), то найменша СКР буде великою, й цей контур буде неправильно обрано як особливу точку.
Алгоритми Гарріса й Стівенса / Сі — Томазі виявляння кутів
Гарріс і Стівенс вдосконалили виявляч кутів Моравека шляхом безпосереднього розгляду диференціалу кутової оцінки відносно напряму замість використання зміщених фрагментів. (Цю кутову оцінку часто називають автокореляцією, оскільки цей термін використовується в статті, в якій описано цей виявляч. Проте математика в статті чітко вказує, що використовується сума квадратів різниць.)
Без втрати загальності вважатимемо, що використовується двовимірне зображення у відтінках сірого. Нехай це зображення задано через . Розгляньмо взяття фрагменту зображення над областю
, й зміщення його на
. Зважена сума квадратів різниць (СКР) між цими двома фрагментами, позначувана через
, задається як
можливо наблизити розкладом Тейлора. Нехай
та
— частинні похідні
, такі, що
Це дає наближення
яке можливо записати в матричному вигляді:
де A — структурний тензор,
Словами, ми знаходимо коваріацію частинної похідної яскравості зображення відносно осей
та
.
Кутові дужки позначують усереднення (тобто підсумовування над ).
позначує тип вікна, що ковзає зображенням. При використанні [en] відгук буде анізотропним, але при використані гауссового фільтра відгук буде ізотропним.
Кут (або особлива точка загалом) характеризується великою мінливістю у всіх напрямках вектора
. Через аналіз власних значень
цю характеристику можливо виразити наступним чином: для особливої точки
повинен мати два «великі» власні значення. Виходячи з цього аргументу, на основі величини власних значень можливо робити наступні висновки:
- Якщо
і
, то цей піксель
не має особливих ознак.
- Якщо
, а
має деяке велике додатне значення, то знайдено контур.
- Якщо
і
мають великі додатні значення, то знайдено кут.
Гарріс і Стівенс відзначають, що точне обчислення власних значень є обчислювально витратним, оскільки вимагає обчислення квадратного кореня, й натомість пропонують наступну функцію , де
є налаштовуваним параметром чутливості:
Отже, цей алгоритм не має насправді обчислювати власний розклад матриці , а замість цього, щоби знаходити кути, а точніше особливі точки загалом, достатньо оцінювати визначник та слід
.
Алгоритм Сі — Томазі виявляння кутів обчислює безпосередньо, оскільки за певних припущень кути є стійкішими для відстежування. Зауважте, що цей метод іноді називають алгоритмом Канаде — Томазі виявляння кутів.
Значення має визначатися емпірично, в літературі повідомляють, що придатними є значення в проміжку 0,04–0,15.
Можливо уникнути встановлювання параметра шляхом використання кутової міри Нобла
, що дорівнює середньому гармонійному власних значень:
де — невелика додатна стала.
Якщо можливо інтерпретувати як [en] для положення кута, то коваріаційною матрицею для положення кута є
, тобто
Сума власних значень , яку в цьому випадку можливо інтерпретувати як узагальнену дисперсію (або «повну невизначеність») положення кута, пов'язана з кутовою мірою Нобла
наступним рівнянням:
Алгоритм Ферстнера виявляння кутів
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTgxTHpWaEwwTnZjbTVsY2w5a1pYUmxZM1JwYjI1ZmRYTnBibWRmUm05bGNuTjBibVZ5WDBGc1oyOXlhWFJvYlM1d2JtYz0ucG5n.png)
У деяких випадках може бути потрібно обчислювати розташування кута з субпіксельною точністю. Для отримання наближеного розв'язку алгоритм Ферстнера знаходить точку, найближчу до всіх дотичних ліній кута в даному вікні, і є розв'язком методом найменших квадратів. Цей алгоритм спирається на той факт, що для ідеального кута дотичні лінії перетинаються в одній точці.
Рівняння дотичної в пікселі
задається як
де — вектор градієнта зображення
в
.
Точка , найближча до всіх дотичних у вікні
, це
Відстань від до дотичних
зважується величиною градієнта, що надає більшого значення дотичним, які проходять через пікселі з сильними градієнтами.
Розв'язання для :
визначаються як:
Мінімізувати це рівняння можливо диференціюванням за і прирівнюванням до 0:
Зауважте, що — структурний тензор. Щоби це рівняння мало розв'язок,
мусить бути оборотною, що означає, що
мусить бути матрицею повного рангу (рангу 2). Таким чином, розв'язок
існує лише там, де у вікні справді є кут.
Методологію виконання автоматичного обирання масштабу (англ. automatic scale selection) для цього методу визначення положень кутів було представлено Ліндебергом, через мінімізування нормованого залишку
над масштабами. Таким чином, цей метод має здатність автоматично підганяти рівні масштабу для обчислення градієнтів зображення до рівня шуму в даних зображення, обираючи грубіші рівні масштабу для зашумлених даних зображення, й тонші рівні масштабу для майже ідеальних кутоподібних структур.
Примітки:
можливо розглядати як залишок при обчисленні розв'язку методом найменших квадратів: якщо
, то похибки не було.
- цей алгоритм можливо видозмінити, щоби обчислювати центри кругових об'єктів, замінивши дотичні лінії на перпендикуляри.
Багатомасштабовий оператор Гарріса
Обчислення матриці другого моменту (яку іноді також називають структурним тензором) в операторі Гарріса вимагає обчислення похідних зображення
в області визначення зображення, а також підсумовування нелінійних комбінацій цих похідних по локальних околах. Оскільки обчислення похідних зазвичай включає етап просторово-масштабового згладжування, операційне визначення оператора Гарріса вимагає двох параметрів масштабу: (i) локального масштабу (англ. local scale) для згладжування перед обчисленням похідних зображення, та (ii) масштабу інтегрування (англ. integration scale) для накопичування нелінійних операцій над операторами похідних до інтегрованого описувача зображення.
Із позначенням первинної яскравості зображення через , нехай
позначує масштабопросторове подання
, отримане згорткою гауссовим ядром
з параметром локального масштабу :
і нехай та
позначують частинні похідні від
. Крім того, введімо віконну гауссову функцію
з параметром масштабу інтегрування
. Тоді багатомасштабову матрицю другого моменту (англ. multi-scale second-moment matrix) можливо визначити через
Тоді ми можемо обчислити власні значення подібно до власних значень
, й визначити багатомасштабову кутову міру Гарріса (англ. multi-scale Harris corner measure) через
Щодо вибору параметра локального масштабу та параметру масштабу інтегрування
, ці параметри масштабу зазвичай пов'язано відносним параметром масштабу інтегрування
через
, де
зазвичай обирають з проміжку
. Таким чином, ми можемо обчислювати багатомасштабову кутову міру Гарріса
на будь-якому масштабі
в просторі масштабів, щоб отримувати багатомасштабовий виявляч кутів, що реагує на кутові структури різних розмірів в області визначення зображення.
На практиці цей багатомасштабовий виявляч кутів часто доповнюють кроком обрання масштабу (англ. scale selection step), де нормований за масштабом оператор Лапласа
обчислюють на кожному масштабі в просторі масштабів, а масштабодопасовані кутові точки з автоматичним вибором масштабу (англ. scale adapted corner points with automatic scale selection, «оператор Гарріса — Лапласа», англ. "Harris-Laplace operator") обчислюють із точок, які є одночасно:
- просторовими максимумами багатомасштабової кутової міри
- локальними максимумами або мінімуми за масштабами масштабонормованого оператора Лапласа
:
Підхід кривини ізоліній
Один з раніших підходів до виявляння кутів полягає у виявлянні точок, де кривина ізоліній та величина градієнта високі одночасно. Диференціальним способом виявляння таких точок є обчислення перемасштабованої кривини ізоліній (англ. rescaled level curve curvature, добутку кривизни ізолінії та величини градієнта у третьому степені)
і виявляння додатних максимумів та від'ємних мінімумів цього диференціального виразу в певному масштабі в масштабопросторовому поданні
первинного зображення. Проте основна проблема при обчисленні сутності перемасштабованої кривини ізоліній в одному масштабі полягає в тому, що вона може бути чутливою до шуму та вибору рівня масштабу. Кращий метод — обчислювати
-нормовану перемасштабовану кривину ізоліній
з , і виявляти знакові масштабопросторові екстремуми цього виразу, тобто точки та масштаби, що є додатними максимумами та від'ємними мінімумами відносно як простору, так і масштабу,
у поєднанні з доповняльним кроком локалізації для опрацювання збільшення похибки локалізації на грубіших масштабах. Таким чином, більші значення масштабу пов'язуватимуться із заокругленими кутами великої просторової простягненості, тоді як менші значення масштабу пов'язуватимуться з гострими кутами невеликої просторової простягненості. Цей підхід — перший виявляч кутів з автоматичним вибором масштабу (до «оператора Гарріса — Лапласа» вище), його використовували для відстежування кутів за великих мінливостей масштабу в області зображення, і для зіставляння кутових відгуків із контурами для обчислювання структурних ознак зображення для [en] розпізнавання об'єктів.
Масштабопросторові особливі точки лапласіана гауссіана, різниці гауссіанів та визначника гессіана
ЛГ (англ. LoG) — це абревіатура, що означає лапласіан гауссіана (англ. Laplacian of Gaussian), РГ (англ. DoG) — абревіатура, що означає різницю гауссіанів (англ. difference of Gaussians, РГ — це наближення ЛГ), а ВГ (англ. DoH) — абревіатура, що означає визначник гессіана (англ. determinant of the Hessian). Усі ці масштабоінваріантні особливі точки виділяються виявлянням масштабопросторових екстремумів масштабонормованих диференціальних виразів, тобто точок у масштабопросторовому поданні, де відповідні масштабонормовані диференціальні вирази набувають локальних екстремумів як у просторі, так і серед масштабів.
де позначує відповідну масштабонормовану диференціальну сутність (визначену нижче).
Ці виявлячі повніше описано у виявлянні плям. Масштабонормовані ознаки лапласіана гауссіана та різниці гауссіанів (Ліндеберг 1994, 1998; Лоу 2004)
не обов'язково створюють сильно вибіркові ознаки, оскільки ці оператори також можуть призводити до реакцій біля контурів. Для покращення здатності різниці гауссіанів виявляти кути, виявляч ознак, який використовують у системі SIFT, використовує додатковий етап післяобробки, на якому власні значення гессіана зображення на масштабі виявляння досліджують подібно до оператора Гарріса. Якщо відношення власних значень занадто високе, то локальне зображення розглядають як занадто контуроподібне, тож таку ознаку відкидають. Також, ліндебергів лапласіаново-гауссіановий виявляч ознак для придушення реакцій біля контурів можливо визначити з включенням додаткового порогування на додатковому диференціальному інваріанті.
Масштабонормований визначник оператора Гессе (Ліндеберг 1994, 1998)
,
з іншого боку, є дуже вибірковим до добре локалізованих ознак у зображенні й реагує лише тоді, коли присутні значні мінливості рівня сірого в двох напрямках зображення, і в цьому та інших відношеннях є кращим виявлячем особливих точок, ніж лапласіан гауссіана. Визначник гессіана — афінний коваріантний диференціальний вираз, і має кращі властивості обирання масштабу за афінних перетворень зображення, ніж лапласіан (Ліндеберг 2013, 2015). Експериментально це означає, що особливі точки детермінанта гессіана мають кращі властивості повторюваності при локальній деформації зображення, ніж особливі точки лапласіана, що своєю чергою призводить до кращої продуктивності зіставляння на основі зображень з точки зору вищих показників ефективності (англ. efficiency) та нижчих оцінок 1−влучність (англ. 1−precision).
Властивості обирання масштабу, властивості афінного перетворення та експериментальні властивості цих та інших виявлячів масштабопросторових особливих точок докладно проаналізовано в (Ліндеберг 2013, 2015).
Масштабопросторові особливі точки на основі ліндебергових мір вираженості гессіанових ознак
Натхнений структурно подібними властивостями матриці Гессе функції
та матриці других моментів (структурного тензора)
, що, наприклад, може проявлятися в термінах їхніх подібних властивостей перетворення при афінних деформаціях зображення
,
,
Ліндеберг (2013, 2015) запропонував визначати чотири міри вираженості ознак з матриці Гессе подібним чином, як оператори Гарріса та Сі й Томазі визначаються зі структурного тензора (матриці других моментів). Зокрема, він визначив такі беззнакові й знакові міри вираженості гессіанових ознак:
- беззнакова міра вираженості гессіанової ознаки I:
- знакова міра вираженості гессіанової ознаки I:
- беззнакова міра вираженості гессіанової ознаки II:
- знакова міра вираженості гессіанової ознаки II:
де та
позначують слід і визначник матриці Гессе
масштабопросторового подання
на будь-якому масштабі
, тоді як
позначують власні значення матриці Гессе.
Беззнакова міра вираженості гессіанової ознаки реагує на локальні екстремуми додатними значеннями й не чутлива до сідлових точок, тоді як знакова міра вираженості гессіанової ознаки
додатково реагує на сідлові точки від'ємними значеннями. Беззнакова міра вираженості гессіанової ознаки
нечутлива до локальної полярності сигналу, тоді як знакова міра вираженості гессіанової ознаки
реагує на локальну полярність сигналу знаком свого результату.
У Ліндеберга (2015) ці чотири диференціальні сутності було об'єднано з локальним обиранням масштабу на основі або виявляння масштабопросторових екстремумів
,
або зв'язування масштабів (англ. scale linking). Крім того, знакові та беззнакові міри вираженості гессіанової ознаки та
було поєднано з додатковим порогуванням
.
Шляхом експериментів із зіставляння зображень за масштабувальних перетворень на наборі даних з 12 плакатів із зіставлянням з декількох точок огляду над масштабувальними перетвореннями до коефіцієнта масштабування 6 і змінами напряму точки огляду до кута нахилу 45 градусів з локальними описувачами зображення, визначеними з переформулювань чистих описувачів зображення в операторах SIFT і SURF для вимірювання зображень у термінах операторів похідної гауссіана (Gauss-SIFT і Gauss-SURF) замість первинного SIFT, визначеного з піраміди зображення, або первинного SURF, визначеного з гаарових вейвлетів, було показано, що виявляння масштабопросторових особливих точок на основі беззнакової міри вираженості гессіанової ознаки дозволили отримати найкращу продуктивність, і кращу продуктивність, ніж масштабопросторові особливі точки, отримувані з визначника гессіана
. Як беззнакова міра вираженості гессіанової ознаки
, так і знакова міра вираженості гессіанової ознаки
і визначник гессіана
дозволили отримати кращу продуктивність, ніж лапласіан гауссіана
. У поєднанні зі зв'язуванням масштабів та додатковим порогуванням
знакова міра вираженості гессіанової ознаки
до того ж дозволила отримати кращу продуктивність, ніж лапласіан гауссіана
.
Крім того, було показано, що всі ці диференціальні виявлячі масштабопросторових особливих точок, визначені з матриці Гессе, дозволяють виявляти більшу кількість особливих точок та дають кращу продуктивність зіставляння порівняно з операторами Гарріса та Сі-й-Томазі, визначеними зі структурного тензора (матриці другого моменту).
Теоретичний аналіз властивостей обирання масштабу цих чотирьох мір вираженості гессіанової ознаки та інших диференціальних сутностей для виявляння масштабопросторових особливих точок, включно з лапласіаном гауссіана та визначником гессіана, наведено в Ліндеберга (2013), а аналіз їхніх властивостей афінного перетворення, а також експериментальних властивостей,— у Ліндеберга (2015).
Оператори афіннопристосованих особливих точок
Особливі точки, отримувані багатомасштабовим оператором Гарріса з автоматичним обиранням масштабу, інваріантні відносно паралельних перенесень, поворотів і рівномірного масштабування в просторовій області. Проте зображення, що є вхідними для систем комп'ютерного зору, зазнають також і перспективних спотворень. Щоб отримати оператор особливих точок, стійкіший до перспективних перетворень, природним підходом є розробка виявляча ознак, інваріантного до афінних перетворень. На практиці афінноінваріантні особливі точки можливо отримувати, застосовуючи афінне пристосовування форми, коли форма ядра згладжування ітеративно деформується, щоби зіставитися з локальною структурою зображення навколо особливої точки, або, рівнозначно, локальний фрагмент зображення ітеративно деформується, тоді як форма ядра згладжування залишається обертово симетричною (Ліндеберг 1993, 2008; Ліндеберг та Гардінг 1997; Міколайчик та Шмід 2004). Отже, крім використовуваного зазвичай багатомасштабового оператора Гарріса, афінне пристосовування форми можливо застосовувати й до інших виявлячів кутів, перелічених у цій статті, а також до диференціальних виявлячів плям, таких як оператор лапласіана/різниці гауссіанів, визначник гессіана та гессіанно-лапласіанний оператор.
Алгоритм Вонга та Брейді виявляння кутів
Виявляч Вонга та Брейді розглядає зображення як поверхню й шукає місця великої кривини вздовж контуру в зображенні. Іншими словами, цей алгоритм шукає місця, де контур швидко змінює напрямок. Кутова оцінка (англ. corner score), , задається як
де — одиничний вектор, перпендикулярний градієнтові, а
визначає контурофобність виявляча. Автори також відзначають, що для зменшення шуму необхідне згладжування (радять гауссове).
Згладжування також призводить до зміщення кутів, тому автори виводять вираз для зміщення кута в 90 градусів, і застосовують його як поправковий коефіцієнт до виявлених кутів.
Виявляч кутів SUSAN
SUSAN — це абревіатура, що означає найменший однорідний сегмент, що уподібнюється ядру (англ. smallest univalue segment assimilating nucleus). Цей метод є предметом патенту Великої Британії 1994 року, який більше не діє.
Для виявляння ознак SUSAN розміщує кругову маску на пікселі, який потрібно перевірити (ядрі, англ. nucleus). Областю маски є , а піксель у цій масці подається через
. Ядро перебуває в
. Кожен піксель порівнюється з ядром за допомогою функції порівняння
де — поріг різниці яскравості,
— яскравість пікселя, а степінь експоненти визначено емпірично. Ця функція виглядає як згладжений циліндр, або прямокутна функція. Площа SUSAN визначається через
Якщо — прямокутна функція, то
— кількість пікселів у масці, що перебувають в межах
від ядра. Відгук оператора SUSAN задається через
де називається «геометричним порогом». Іншими словами, оператор SUSAN дає додатну оцінку лише якщо площа досить мала. Найменший SUSAN локально можливо знаходити за допомогою придушування немаксимумів, і це повний оператор SUSAN.
Значення визначає, наскільки подібними до ядра мають бути точки, щоби вважатися частиною однорідного сегмента (англ. univalue segment). Значення
визначає мінімальний розмір однорідного сегмента. Якщо
достатньо велике, то це стає виявлячем контурів.
Для виявляння кутів використовують ще два кроки. По-перше, знаходять центроїд SUSAN. Правильний кут матиме центроїд далеко від ядра. Другий крок наполягає на тому, що всі точки на лінії від ядра через центроїд до краю маски перебувають у SUSAN.
Виявляч кутів Трайковича та Гедлі
Подібно до SUSAN, цей виявляч безпосередньо перевіряє, чи є пляма під пікселем самоподібною, досліджуючи сусідні пікселі. — піксель, який потрібно розглянути, а
— точка на колі
з центром у
. Точка
— діаметрально протилежна до
.
Функцію відгуку визначають через
Він буде великим, якщо немає напряму, в якому центральний піксель подібний до двох сусідніх пікселів по діаметру. — дискретизоване коло (коло Брезенгема), тому для проміжних діаметрів використовують інтерполяцію, щоб отримувати ізотропніший відгук. Оскільки будь-яке обчислення дає верхню межу для
, спочатку перевіряють горизонтальний і вертикальний напрямки, щоби побачити, чи варто продовжувати повне обчислення
.
Виявлячі ознак на основі AST
AST — це абревіатура, що означає прискорену сегментну перевірку (англ. accelerated segment test). Ця перевірка — розслаблена версія кутового критерію SUSAN. Замість оцінювання кругового диска розглядають лише пікселі на колі Брезенгема радіуса навколо точки — кандидата. Якщо всі
суміжних пікселів яскравіші за ядро принаймні на
, або всі темніші за ядро на
, то піксель під ядром вважають ознакою. Повідомляють, що цей критерій дає дуже стабільні ознаки. Вибір порядку, в якому перевіряються пікселі, є так званою задачею двадцяти запитань. Побудова коротких дерев рішень для цієї задачі призводить до обчислювально найефективніших доступних виявлячів ознак.
Першим алгоритмом виявляння кутів на основі AST є FAST (ознаки з прискореної сегментної перевірки, англ. features from accelerated segment test). Хоча може в принципі набувати будь-якого значення, FAST використовує лише значення 3 (що відповідає колу в 16 пікселів на ньому), а перевірки показують, що найкращі результати досягаються, коли
становить 9. Це значення
є найнижчим, за якого не виявляються контури. Порядок, у якому перевіряються пікселі, визначається алгоритмом ID3 з тренувального набору зображень. Як не дивно, назва цього виявляча дещо схожа на назву статті, яка описує виявляч Трайковича та Гедлі.
Автоматичне синтезування виявлячів
Трухільйо та Олагуе представили метод, в якому використовується генетичне програмування для автоматичного синтезування операторів над зображеннями, що можуть виявляти особливі точки. Набори листків і функцій містять примітивні операції, які є поширеними в багатьох раніше запропонованих штучних конструкціях. Допасованість вимірює стабільність кожного оператора через коефіцієнт повторюваності, та сприяє рівномірному розподілу виявлених точок у площині зображення. Продуктивність цих виведених операторів було підтверджено експериментально з використанням тренувальних та перевірних послідовностей поступово перетворюваних зображень. Таким чином, запропонований алгоритм ГП вважається для задачі виявляння особливих точок конкурентоспроможним відносно людини.
Виявлячі просторово-часових особливих точок
Лаптєв та Ліндеберг розширили оператор Гарріса до простору-часу. Нехай позначує просторово-часову матрицю других моментів, визначену через
Тоді для придатного вибору просторово-часові особливі точки виявляються з просторово-часових екстремумів наступної просторово-часової міри Гарріса:
Визначник гессіана було розширено до спільного простору-часу Віллемсом та ін., та Ліндебергом, що дало наступний масштабонормований диференціальний вираз:
У праці Віллемса та ін. було використано простіший вираз, що відповідає та
. У Ліндеберга було показано, що
та
дають кращі масштабообиральні властивості в тому сенсі, що обирані рівні масштабу, отримувані з просторово-часової гауссової плями з просторовою протяжністю
й часовою тривалістю
, ідеально відповідатимуть просторовій протяжності та часовій тривалості цієї плями, з виконанням обирання масштабу шляхом виявляння просторово-часових масштабопросторових екстремумів цього диференціального виразу.
Ліндеберг розширив оператор Лапласа на просторово-часові відеодані, що дало наступні два просторово-часові оператори, які також становлять моделі рецептивних полів нейронів БКЯ без запізнювання і з запізнюванням:
Для першого оператора потрібні властивості вибору масштабу і
, якщо ми хочемо, щоби цей оператор набував свого максимального значення над просторово-часовими масштабами на рівні просторово-часового масштабу, який відображає просторову протяжність і часову тривалість гауссової плями, яка з'являється. Для другого оператора потрібні властивості вибору масштабу
і
, якщо ми хочемо, щоби цей оператор набував свого максимального значення над просторово-часовими масштабами на рівні просторово-часового масштабу, що відображає просторову протяжність і часову тривалість гауссової плями, яка зблимує.
Колірні розширення виявлячів просторово-часових особливих точок було досліджено Евертсом та ін.
Бібліографія
- Andrew Willis and Yunfeng Sui (2009). An Algebraic Model for fast Corner Detection. 2009 IEEE 12th International Conference on Computer Vision. IEEE. с. 2296—2302. doi:10.1109/ICCV.2009.5459443. ISBN . (англ.)
- [en] and George C. Stockman (2001). Computer Vision, p. 257. Prentice Books, Upper Saddle River. . (англ.)
- H. Moravec (1980). . Tech Report CMU-RI-TR-3 Carnegie-Mellon University, Robotics Institute. Архів оригіналу за 12 жовтня 2016. Процитовано 18 квітня 2022. (англ.)
- Obstacle Avoidance and Navigation in the Real World by a Seeing Robot Rover, Hans Moravec, March 1980, Computer Science Department, Stanford University (Ph.D. thesis) (англ.)
- C. Harris and M. Stephens (1988). (PDF). Proceedings of the 4th Alvey Vision Conference. с. 147—151. Архів оригіналу (PDF) за 1 квітня 2022. Процитовано 18 квітня 2022. (англ.)
- Javier Sánchez, Nelson Monzón and Agustín Salgado (2018). . Image Processing on Line. 8: 305—328. doi:10.5201/ipol.2018.229. Архів оригіналу за 12 лютого 2022. Процитовано 18 квітня 2022. (англ.)
- J. Shi and C. Tomasi (June 1994). Good Features to Track. 9th IEEE Conference on Computer Vision and Pattern Recognition. Springer. с. 593—600. CiteSeerX 10.1.1.36.2669. doi:10.1109/CVPR.1994.323794. (англ.)
C. Tomasi and T. Kanade (1991). Detection and Tracking of Point Features (Технічний звіт). № CMU-CS-91-132. School of Computer Science, Carnegie Mellon University. CiteSeerX 10.1.1.45.5770. (англ.) - A. Noble (1989). (Ph.D.). Department of Engineering Science, Oxford University. с. 45. Архів оригіналу за 27 червня 2019. Процитовано 18 квітня 2022. (англ.)
- Förstner, W; Gülch (1987). A Fast Operator for Detection and Precise Location of Distinct Points, Corners and Centres of Circular Features (PDF). ISPRS.
{{}}
: Обслуговування CS1: Сторінки з параметром url-status, але без параметра archive-url () (англ.) - T. Lindeberg (1994). Junction detection with automatic selection of detection scales and localization scales. Proc. 1st International Conference on Image Processing. Т. I. Austin, Texas. с. 924—928. (англ.)
- Tony Lindeberg (1998). . International Journal of Computer Vision. Т. 30, № 2. с. 77—116. Архів оригіналу за 18 квітня 2022. Процитовано 18 квітня 2022. (англ.)
- T. Lindeberg (1994). . Springer. ISBN . Архів оригіналу за 30 листопада 2020. Процитовано 18 квітня 2022. (англ.)
- T. Lindeberg and J. Garding "Shape-adapted smoothing in estimation of 3-D depth cues from affine distortions of local 2-D structure". Image and Vision Computing 15 (6): pp 415–434, 1997. [ 14 лютого 2022 у Wayback Machine.] (англ.)
- T. Lindeberg (2008). Scale-Space. У Benjamin Wah (ред.). Wiley Encyclopedia of Computer Science and Engineering. Т. IV. John Wiley and Sons. с. 2495—2504. doi:10.1002/9780470050118.ecse609. ISBN . (англ.)
- K. Mikolajczyk, K. and C. Schmid (2004). (PDF). International Journal of Computer Vision. 60 (1): 63—86. doi:10.1023/B:VISI.0000027790.02288.f2. Архів оригіналу (PDF) за 7 січня 2018. Процитовано 18 квітня 2022. (англ.)
- L. Kitchen and A. Rosenfeld (1982). Gray-level corner detection. Pattern Recognition Letters. Т. 1, № 2. с. 95—102. (англ.)
- J. J. Koenderink and W. Richards (1988). Two-dimensional curvature operators. Journal of the Optical Society of America A. Т. 5, № 7. с. 1136—1141. (англ.)
- L. Bretzner and T. Lindeberg (1998). Feature tracking with automatic selection of spatial scales. Computer Vision and Image Understanding. Т. 71. с. 385—392. (англ.)
- T. Lindeberg and M.-X. Li (1997). . Computer Vision and Image Understanding. Т. 67, № 1. с. 88—98. Архів оригіналу за 18 квітня 2022. Процитовано 18 квітня 2022. (англ.)
- D. Lowe (2004). . International Journal of Computer Vision. 60 (2): 91. CiteSeerX 10.1.1.73.2924. doi:10.1023/B:VISI.0000029664.99615.94. Архів оригіналу за 10 травня 2008. Процитовано 18 квітня 2022. (англ.)
- T. Lindeberg ``Image matching using generalized scale-space interest points", Journal of Mathematical Imaging and Vision, volume 52, number 1, pages 3-36, 2015. (англ.)
- T. Lindeberg "Scale selection properties of generalized scale-space interest point detectors", Journal of Mathematical Imaging and Vision, Volume 46, Issue 2, pages 177-210, 2013. (англ.)
- Lindeberg, T. (1998). . International Journal of Computer Vision. 30 (2): 117—154. doi:10.1023/A:1008097225773. Архів оригіналу за 14 лютого 2022. Процитовано 18 квітня 2022. (англ.)
- H. Wang and M. Brady (1995). Real-time corner detection algorithm for motion estimation. Image and Vision Computing. 13 (9): 695—703. doi:10.1016/0262-8856(95)98864-P. (англ.)
- S. M. Smith and J. M. Brady (May 1997). . International Journal of Computer Vision. 23 (1): 45—78. doi:10.1023/A:1007963824710. Архів оригіналу за 29 серпня 2012. Процитовано 18 квітня 2022. (англ.)
S. M. Smith and J. M. Brady (January 1997), "Method for digitally processing images to determine the position of edges and/or corners therein for guidance of unmanned vehicle". UK Patent 2272285, Proprietor: Secretary of State for Defence, UK. (англ.) - GB patent 2272285, Smith, Stephen Mark, "Determining the position of edges and corners in images", published 1994-05-11, issued 1994-05-11, assigned to Secr Defence (англ.)
- . Архів оригіналу за 16 вересня 2017. Процитовано 18 квітня 2022. (англ.)
- M. Trajkovic and M. Hedley (1998). Fast corner detection. Image and Vision Computing. 16 (2): 75—87. doi:10.1016/S0262-8856(97)00056-5. (англ.)
- E. Rosten and T. Drummond (May 2006). . European Conference on Computer Vision. Архів оригіналу за 17 березня 2008. Процитовано 18 квітня 2022. (англ.)
- Leonardo Trujillo and Gustavo Olague (2008). (PDF). Evolutionary Computation. 16 (4): 483—507. doi:10.1162/evco.2008.16.4.483. PMID 19053496. Архів оригіналу (PDF) за 17 липня 2011. (англ.)
- Ivan Laptev and Tony Lindeberg (2003). . International Conference on Computer Vision. IEEE. с. 432—439. Архів оригіналу за 18 квітня 2022. Процитовано 18 квітня 2022. (англ.)
- Geert Willems, Tinne Tuytelaars and Luc van Gool (2008). An efficient dense and scale-invariant spatiotemporal-temporal interest point detector. European Conference on Computer Vision. Springer Lecture Notes in Computer Science. Т. 5303. с. 650—663. doi:10.1007/978-3-540-88688-4_48. (англ.)
- Tony Lindeberg (2018). Spatio-temporal scale selection in video data. Journal of Mathematical Imaging and Vision. Т. 60, № 4. с. 525—562. doi:10.1007/s10851-017-0766-9. (англ.)
- I. Everts, J. van Gemert and T. Gevers (2014). Evaluation of color spatio-temporal interest points for human action recognition. IEEE Transactions on Image Processing. Т. 23, № 4. с. 1569—1589. doi:10.1109/TIP.2014.2302677. (англ.)
Еталонні втілення
Цей розділ містить зовнішні посилання на еталонні втілення деяких з описаних вище виявлячів. Ці еталонні втілення надано авторами праці, в якій вперше описано виявляч. Вони можуть містити деталі, відсутні або неявні в працях, що описують їхні властивості.
- Виявляння РГ [ 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 (ред.), Математична енциклопедія, , ISBN (англ.)
- Brostow, "Corner Detection — UCL Computer Science" [ 8 березня 2022 у Wayback Machine.] (англ.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Viyavlya nnya kuti v angl corner detection ce pidhid yakij vikoristovuyut u sistemah komp yuternogo bachennya dlya vidilyannya pevnih tipiv oznak i viznachannya vmistu zobrazhennya Viyavlyannya kutiv chasto vikoristovuyut dlya viyavlyannya ruhu zistavlyannya zobrazhen vidstezhuvannya u video en en trivimirnoyi vidbudovi ta en Viyavlyannya kutiv peretinayetsya z temoyu viyavlyannya osoblivih tochok Vihid tipovogo algoritmu viyavlyannya kutivFormalizaciyaKut mozhlivo viznachiti yak peretin dvoh konturiv Kut takozh mozhlivo viznachiti yak tochku dlya yakoyi isnuyut dva panivnih i riznih napryami konturu v lokalnomu okoli ciyeyi tochki Osobliva tochka ce tochka v zobrazhenni yaka maye chitko viznachene polozhennya i yiyi mozhlivo nadijno viyavlyati Ce oznachaye sho osobliva tochka mozhe buti kutom ale takozh mozhe buti napriklad izolovanoyu tochkoyu lokalnogo maksimumu chi minimumu yaskravosti zakinchennyami liniyi abo tochkoyu na krivij de krivina lokalno maksimalna Na praktici bilshist tak zvanih metodiv viyavlyannya kutiv viyavlyayut osoblivi tochki zagalom i naspravdi termini kut angl corner ta osobliva tochka angl interest point vikoristovuyut u literaturi bilsh mensh vzayemozaminno Yak naslidok yaksho potribno viyavlyati lishe kuti neobhidno robiti lokalnij analiz viyavlenih osoblivih tochok shobi viznachati yaki z nih ye spravzhnimi kutami Prikladami viyavlyannya krayiv yaki mozhlivo vikoristovuvati z pislyaopracyuvannyam dlya viyavlyannya kutiv ye operator Kirsha ta nabir masok Fraya Chena Termini kut osobliva tochka j oznaka angl feature vikoristovuyut u literaturi yak sinonimi sho zaplutuye pitannya Zokrema isnuye kilka viyavlyachiv plyam yaki mozhlivo nazivati operatorami osoblivih tochok ale yaki inodi pomilkovo nazivayut viyavlyachami kutiv Krim togo isnuye ponyattya viyavlyannya hrebtiv dlya vlovlyuvannya nayavnosti vityagnutih ob yektiv Viyavlyachi kutiv zazvichaj ne duzhe nadijni j chasto vimagayut zaprovadzhennya znachnogo dublyuvannya shobi zapobigati dominuvannyu okremih pomilok v zadachi rozpiznavannya Odin z kriteriyiv yakosti viyavlyacha kutiv jogo zdatnist viyavlyati odin i toj zhe kut na kilkoh podibnih zobrazhennyah v umovah riznogo osvitlennya paralelnogo perenesennya povertannya ta inshih peretvoren Prostij pidhid do viyavlyannya kutiv u zobrazhennyah vikoristannya korelyaciyi ale ce duzhe obchislyuvalno vitratno j neoptimalno Chasto vzhivanij alternativnij pidhid gruntuyetsya na metodi zaproponovanomu Garrisom ta Stivensom nizhche yakij svoyeyu chergoyu ye vdoskonalennyam metodu Moraveka Algoritm Moraveka viyavlyannya kutivCe odin z najpershih algoritmiv viyavlyannya kutiv yakij viznachaye kut angl corner yak tochku z nizkoyu samopodibnistyu Cej algoritm pereviryaye kozhen piksel u zobrazhenni na nayavnist kuta rozglyadayuchi naskilki fragment z centrom u comu pikseli shozhij na susidni fragmenti sho znachnoyu miroyu perekrivayutsya Podibnist vimiryuyetsya shlyahom otrimannya sumi kvadrativ riznic SKR mizh vidpovidnimi pikselyami dvoh fragmentiv Menshe chislo vkazuye na bilshu shozhist Yaksho piksel perebuvaye v oblasti rivnomirnoyi yaskravosti to najblizhchi fragmenti viglyadatimut podibno Yaksho piksel perebuvaye na konturi to najblizhchi fragmenti v napryamku perpendikulyarnomu do konturu viglyadatimut zovsim inakshe ale najblizhchi fragmenti v napryamku paralelnomu konturu davatimut lishe neznachni zmini Yaksho piksel perebuvaye na ob yekti zi zminami v usih napryamkah to zhoden iz susidnih fragmentiv ne bude shozhim Virazhenist kuta viznachayetsya yak najmensha SKR mizh fragmentom ta jogo susidami gorizontalno vertikalno ta po dvoh diagonalyah Sens u tomu sho yaksho ce chislo velike to minlivist vzdovzh usih zmishen bilshe abo dorivnyuye jomu vlovlyuyuchi sho vsi najblizhchi fragmenti viglyadayut inakshe Yaksho znachennya virazhenosti kuta obchislyuyetsya dlya vsih polozhen to yaksho vono lokalno maksimalne dlya odnogo miscya ce vkazuye na te sho v nomu prisutnya potribna oznaka Yak zaznachiv Moravek odna z golovnih problem cogo operatora polyagaye v jogo neizotropnosti yaksho prisutnij kontur sho ne perebuvaye v napryamku susidiv gorizontalno vertikalno chi diagonalno to najmensha SKR bude velikoyu j cej kontur bude nepravilno obrano yak osoblivu tochku Algoritmi Garrisa j Stivensa Si Tomazi viyavlyannya kutivDokladnishe Algoritm Garrisa viyavlyannya kutiv Garris i Stivens vdoskonalili viyavlyach kutiv Moraveka shlyahom bezposerednogo rozglyadu diferencialu kutovoyi ocinki vidnosno napryamu zamist vikoristannya zmishenih fragmentiv Cyu kutovu ocinku chasto nazivayut avtokorelyaciyeyu oskilki cej termin vikoristovuyetsya v statti v yakij opisano cej viyavlyach Prote matematika v statti chitko vkazuye sho vikoristovuyetsya suma kvadrativ riznic Bez vtrati zagalnosti vvazhatimemo sho vikoristovuyetsya dvovimirne zobrazhennya u vidtinkah sirogo Nehaj ce zobrazhennya zadano cherez I displaystyle I Rozglyanmo vzyattya fragmentu zobrazhennya nad oblastyu u v displaystyle u v j zmishennya jogo na x y displaystyle x y Zvazhena suma kvadrativ riznic SKR mizh cimi dvoma fragmentami poznachuvana cherez S displaystyle S zadayetsya yak S x y u vw u v I u x v y I u v 2 displaystyle 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 displaystyle I u x v y mozhlivo nabliziti rozkladom Tejlora Nehaj Ix displaystyle I x ta Iy displaystyle I y chastinni pohidni I displaystyle I taki sho I u x v y I u v Ix u v x Iy u v y displaystyle I u x v y approx I u v I x u v x I y u v y Ce daye nablizhennya S x y u vw u v Ix u v x Iy u v y 2 displaystyle S x y approx sum u sum v w u v left I x u v x I y u v y right 2 yake mozhlivo zapisati v matrichnomu viglyadi S x y xy A xy displaystyle S x y approx begin bmatrix x amp y end bmatrix A begin bmatrix x y end bmatrix de A strukturnij tenzor A u vw u v Ix u v 2Ix u v Iy u v Ix u v Iy u v Iy u v 2 Ix2 IxIy IxIy Iy2 displaystyle A sum u sum v w u v begin bmatrix I x u v 2 amp I x u v I y u v I x u v I y u v amp I y u v 2 end bmatrix begin bmatrix langle I x 2 rangle amp langle I x I y rangle langle I x I y rangle amp langle I y 2 rangle end bmatrix Slovami mi znahodimo kovariaciyu chastinnoyi pohidnoyi yaskravosti zobrazhennya I displaystyle I vidnosno osej x displaystyle x ta y displaystyle y Kutovi duzhki poznachuyut userednennya tobto pidsumovuvannya nad u v displaystyle u v w u v displaystyle w u v poznachuye tip vikna sho kovzaye zobrazhennyam Pri vikoristanni en vidguk bude anizotropnim ale pri vikoristani gaussovogo filtra vidguk bude izotropnim Kut abo osobliva tochka zagalom harakterizuyetsya velikoyu minlivistyu S displaystyle S u vsih napryamkah vektora xy displaystyle begin bmatrix x amp y end bmatrix Cherez analiz vlasnih znachen A displaystyle A cyu harakteristiku mozhlivo viraziti nastupnim chinom dlya osoblivoyi tochki A displaystyle A povinen mati dva veliki vlasni znachennya Vihodyachi z cogo argumentu na osnovi velichini vlasnih znachen mozhlivo robiti nastupni visnovki Yaksho l1 0 displaystyle lambda 1 approx 0 i l2 0 displaystyle lambda 2 approx 0 to cej piksel x y displaystyle x y ne maye osoblivih oznak Yaksho l1 0 displaystyle lambda 1 approx 0 a l2 displaystyle lambda 2 maye deyake velike dodatne znachennya to znajdeno kontur Yaksho l1 displaystyle lambda 1 i l2 displaystyle lambda 2 mayut veliki dodatni znachennya to znajdeno kut Garris i Stivens vidznachayut sho tochne obchislennya vlasnih znachen ye obchislyuvalno vitratnim oskilki vimagaye obchislennya kvadratnogo korenya j natomist proponuyut nastupnu funkciyu Mc displaystyle M c de k displaystyle kappa ye nalashtovuvanim parametrom chutlivosti Mc l1l2 k l1 l2 2 det A ktrace2 A displaystyle M c lambda 1 lambda 2 kappa left lambda 1 lambda 2 right 2 det A kappa operatorname trace 2 A Otzhe cej algoritm ne maye naspravdi obchislyuvati vlasnij rozklad matrici A displaystyle A a zamist cogo shobi znahoditi kuti a tochnishe osoblivi tochki zagalom dostatno ocinyuvati viznachnik ta slid A displaystyle A Algoritm Si Tomazi viyavlyannya kutiv obchislyuye min l1 l2 displaystyle min lambda 1 lambda 2 bezposeredno oskilki za pevnih pripushen kuti ye stijkishimi dlya vidstezhuvannya Zauvazhte sho cej metod inodi nazivayut algoritmom Kanade Tomazi viyavlyannya kutiv Znachennya k displaystyle kappa maye viznachatisya empirichno v literaturi povidomlyayut sho pridatnimi ye znachennya v promizhku 0 04 0 15 Mozhlivo uniknuti vstanovlyuvannya parametra k displaystyle kappa shlyahom vikoristannya kutovoyi miri NoblaMc displaystyle M c sho dorivnyuye serednomu garmonijnomu vlasnih znachen Mc 2det A trace A ϵ displaystyle M c 2 frac det A operatorname trace A epsilon de ϵ displaystyle epsilon nevelika dodatna stala Yaksho A displaystyle A mozhlivo interpretuvati yak en dlya polozhennya kuta to kovariacijnoyu matriceyu dlya polozhennya kuta ye A 1 displaystyle A 1 tobto 1 Ix2 Iy2 IxIy 2 Iy2 IxIy IxIy Ix2 displaystyle 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 amp langle I x I y rangle langle I x I y rangle amp langle I x 2 rangle end bmatrix Suma vlasnih znachen A 1 displaystyle A 1 yaku v comu vipadku mozhlivo interpretuvati yak uzagalnenu dispersiyu abo povnu neviznachenist polozhennya kuta pov yazana z kutovoyu miroyu Nobla Mc displaystyle M c nastupnim rivnyannyam l1 A 1 l2 A 1 trace A det A 2Mc displaystyle lambda 1 A 1 lambda 2 A 1 frac operatorname trace A det A approx frac 2 M c Algoritm Ferstnera viyavlyannya kutivViyavlennya kuta za dopomogoyu algoritmu Ferstnera U deyakih vipadkah mozhe buti potribno obchislyuvati roztashuvannya kuta z subpikselnoyu tochnistyu Dlya otrimannya nablizhenogo rozv yazku algoritm Ferstnera znahodit tochku najblizhchu do vsih dotichnih linij kuta v danomu vikni i ye rozv yazkom metodom najmenshih kvadrativ Cej algoritm spirayetsya na toj fakt sho dlya idealnogo kuta dotichni liniyi peretinayutsya v odnij tochci Rivnyannya dotichnoyi Tx x displaystyle T mathbf x mathbf x v pikseli x displaystyle mathbf x zadayetsya yak Tx x I x x x 0 displaystyle T mathbf x mathbf x nabla I mathbf x top mathbf x mathbf x 0 de I x IxIy displaystyle nabla I mathbf x begin bmatrix I mathbf x amp I mathbf y end bmatrix top vektor gradiyenta zobrazhennya I displaystyle I v x displaystyle mathbf x Tochka x0 displaystyle mathbf x 0 najblizhcha do vsih dotichnih u vikni N displaystyle N ce x0 argminx R2 1 x NTx x 2dx displaystyle 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 Vidstan vid x0 displaystyle mathbf x 0 do dotichnih Tx displaystyle T mathbf x zvazhuyetsya velichinoyu gradiyenta sho nadaye bilshogo znachennya dotichnim yaki prohodyat cherez pikseli z silnimi gradiyentami Rozv yazannya dlya x0 displaystyle mathbf x 0 x0 argminx R2 1 x N I x x x 2dx argminx R2 1 x N x x I x I x x x dx argminx R2 1 x Ax 2x b c displaystyle begin aligned mathbf x 0 amp 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 amp 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 amp 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 R2 2 b R2 1 c R displaystyle A in mathbb R 2 times 2 textbf b in mathbb R 2 times 1 c in mathbb R viznachayutsya yak A I x I x dx b I x I x x dx c x I x I x x dx displaystyle begin aligned A amp int nabla I mathbf x nabla I mathbf x top d mathbf x mathbf b amp int nabla I mathbf x nabla I mathbf x top mathbf x d mathbf x c amp int mathbf x top nabla I mathbf x nabla I mathbf x top mathbf x d mathbf x end aligned Minimizuvati ce rivnyannya mozhlivo diferenciyuvannyam za x displaystyle x i pririvnyuvannyam do 0 2Ax 2b 0 Ax b displaystyle 2A mathbf x 2 mathbf b 0 Rightarrow A mathbf x mathbf b Zauvazhte sho A R2 2 displaystyle A in mathbb R 2 times 2 strukturnij tenzor Shobi ce rivnyannya malo rozv yazok A displaystyle A musit buti oborotnoyu sho oznachaye sho A displaystyle A musit buti matriceyu povnogo rangu rangu 2 Takim chinom rozv yazok x0 A 1b displaystyle x 0 A 1 mathbf b isnuye lishe tam de u vikni N displaystyle N spravdi ye kut Metodologiyu vikonannya avtomatichnogo obirannya masshtabu angl automatic scale selection dlya cogo metodu viznachennya polozhen kutiv bulo predstavleno Lindebergom cherez minimizuvannya normovanogo zalishku d min c bTA 1btrace A displaystyle tilde d min frac c b T A 1 b operatorname trace A nad masshtabami Takim chinom cej metod maye zdatnist avtomatichno pidganyati rivni masshtabu dlya obchislennya gradiyentiv zobrazhennya do rivnya shumu v danih zobrazhennya obirayuchi grubishi rivni masshtabu dlya zashumlenih danih zobrazhennya j tonshi rivni masshtabu dlya majzhe idealnih kutopodibnih struktur Primitki c displaystyle c mozhlivo rozglyadati yak zalishok pri obchislenni rozv yazku metodom najmenshih kvadrativ yaksho c 0 displaystyle c 0 to pohibki ne bulo cej algoritm mozhlivo vidozminiti shobi obchislyuvati centri krugovih ob yektiv zaminivshi dotichni liniyi na perpendikulyari Bagatomasshtabovij operator GarrisaObchislennya matrici drugogo momentu yaku inodi takozh nazivayut strukturnim tenzorom A displaystyle A v operatori Garrisa vimagaye obchislennya pohidnih zobrazhennya Ix Iy displaystyle I x I y v oblasti viznachennya zobrazhennya a takozh pidsumovuvannya nelinijnih kombinacij cih pohidnih po lokalnih okolah Oskilki obchislennya pohidnih zazvichaj vklyuchaye etap prostorovo masshtabovogo zgladzhuvannya operacijne viznachennya operatora Garrisa vimagaye dvoh parametriv masshtabu i lokalnogo masshtabu angl local scale dlya zgladzhuvannya pered obchislennyam pohidnih zobrazhennya ta ii masshtabu integruvannya angl integration scale dlya nakopichuvannya nelinijnih operacij nad operatorami pohidnih do integrovanogo opisuvacha zobrazhennya Iz poznachennyam pervinnoyi yaskravosti zobrazhennya cherez I displaystyle I nehaj L displaystyle L poznachuye masshtaboprostorove podannya I displaystyle I otrimane zgortkoyu gaussovim yadrom g x y t 12pte x2 y2 2t displaystyle g x y t frac 1 2 pi t e left x 2 y 2 right 2t z parametrom lokalnogo masshtabu t displaystyle t L x y t g x y t I x y displaystyle L x y t g x y t I x y i nehaj Lx xL displaystyle L x partial x L ta Ly yL displaystyle L y partial y L poznachuyut chastinni pohidni vid L displaystyle L Krim togo vvedimo vikonnu gaussovu funkciyu g x y s displaystyle g x y s z parametrom masshtabu integruvannya s displaystyle s Todi bagatomasshtabovu matricyu drugogo momentu angl multi scale second moment matrix mozhlivo viznachiti cherez m x y t s 3 h Lx2 x 3 y h t Lx x 3 y h t Ly x 3 y h t Lx x 3 y h t Ly x 3 y h t Ly2 x 3 y h t g 3 h s d3dh displaystyle mu x y t s int xi infty infty int eta infty infty begin bmatrix L x 2 x xi y eta t amp 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 amp L y 2 x xi y eta t end bmatrix g xi eta s d xi d eta Todi mi mozhemo obchisliti vlasni znachennya m displaystyle mu podibno do vlasnih znachen A displaystyle A j viznachiti bagatomasshtabovu kutovu miru Garrisa angl multi scale Harris corner measure cherez Mc x y t s det m x y t s ktrace2 m x y t s displaystyle M c x y t s det mu x y t s kappa operatorname trace 2 mu x y t s Shodo viboru parametra lokalnogo masshtabu t displaystyle t ta parametru masshtabu integruvannya s displaystyle s ci parametri masshtabu zazvichaj pov yazano vidnosnim parametrom masshtabu integruvannya g displaystyle gamma cherez s g2t displaystyle s gamma 2 t de g displaystyle gamma zazvichaj obirayut z promizhku 1 2 displaystyle 1 2 Takim chinom mi mozhemo obchislyuvati bagatomasshtabovu kutovu miru Garrisa Mc x y t g2t displaystyle M c x y t gamma 2 t na bud yakomu masshtabi t displaystyle t v prostori masshtabiv shob otrimuvati bagatomasshtabovij viyavlyach kutiv sho reaguye na kutovi strukturi riznih rozmiriv v oblasti viznachennya zobrazhennya Na praktici cej bagatomasshtabovij viyavlyach kutiv chasto dopovnyuyut krokom obrannya masshtabu angl scale selection step de normovanij za masshtabom operator Laplasa norm2L x y t t 2L x y t t Lxx x y t Lyy x y t displaystyle 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 obchislyuyut na kozhnomu masshtabi v prostori masshtabiv a masshtabodopasovani kutovi tochki z avtomatichnim viborom masshtabu angl scale adapted corner points with automatic scale selection operator Garrisa Laplasa angl Harris Laplace operator obchislyuyut iz tochok yaki ye odnochasno prostorovimi maksimumami bagatomasshtabovoyi kutovoyi miri Mc x y t g2t displaystyle M c x y t gamma 2 t x y t argmaxlocal x y Mc x y t g2t displaystyle hat x hat y t operatorname argmaxlocal x y M c left x y t gamma 2 t right lokalnimi maksimumami abo minimumi za masshtabami masshtabonormovanogo operatora Laplasa norm2 x y t displaystyle nabla mathrm norm 2 x y t t argmaxminlocalt norm2L x y t displaystyle hat t operatorname argmaxminlocal t nabla mathrm norm 2 L hat x hat y t Pidhid krivini izolinijOdin z ranishih pidhodiv do viyavlyannya kutiv polyagaye u viyavlyanni tochok de krivina izolinij ta velichina gradiyenta visoki odnochasno Diferencialnim sposobom viyavlyannya takih tochok ye obchislennya peremasshtabovanoyi krivini izolinij angl rescaled level curve curvature dobutku krivizni izoliniyi ta velichini gradiyenta u tretomu stepeni k x y t Lx2Lyy Ly2Lxx 2LxLyLxy displaystyle tilde kappa x y t L x 2 L yy L y 2 L xx 2L x L y L xy i viyavlyannya dodatnih maksimumiv ta vid yemnih minimumiv cogo diferencialnogo virazu v pevnomu masshtabi t displaystyle t v masshtaboprostorovomu podanni L displaystyle L pervinnogo zobrazhennya Prote osnovna problema pri obchislenni sutnosti peremasshtabovanoyi krivini izolinij v odnomu masshtabi polyagaye v tomu sho vona mozhe buti chutlivoyu do shumu ta viboru rivnya masshtabu Krashij metod obchislyuvati g displaystyle gamma normovanu peremasshtabovanu krivinu izolinij k norm x y t t2g Lx2Lyy Ly2Lxx 2LxLyLxy displaystyle 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 z g 7 8 displaystyle gamma 7 8 i viyavlyati znakovi masshtaboprostorovi ekstremumi cogo virazu tobto tochki ta masshtabi sho ye dodatnimi maksimumami ta vid yemnimi minimumami vidnosno yak prostoru tak i masshtabu x y t argminmaxlocal x y t k norm x y t displaystyle hat x hat y hat t operatorname argminmaxlocal x y t tilde kappa mathrm norm x y t u poyednanni z dopovnyalnim krokom lokalizaciyi dlya opracyuvannya zbilshennya pohibki lokalizaciyi na grubishih masshtabah Takim chinom bilshi znachennya masshtabu pov yazuvatimutsya iz zaokruglenimi kutami velikoyi prostorovoyi prostyagnenosti todi yak menshi znachennya masshtabu pov yazuvatimutsya z gostrimi kutami nevelikoyi prostorovoyi prostyagnenosti Cej pidhid pershij viyavlyach kutiv z avtomatichnim viborom masshtabu do operatora Garrisa Laplasa vishe jogo vikoristovuvali dlya vidstezhuvannya kutiv za velikih minlivostej masshtabu v oblasti zobrazhennya i dlya zistavlyannya kutovih vidgukiv iz konturami dlya obchislyuvannya strukturnih oznak zobrazhennya dlya en rozpiznavannya ob yektiv Masshtaboprostorovi osoblivi tochki laplasiana gaussiana riznici gaussianiv ta viznachnika gessianaLG angl LoG ce abreviatura sho oznachaye laplasian gaussiana angl Laplacian of Gaussian RG angl DoG abreviatura sho oznachaye riznicyu gaussianiv angl difference of Gaussians RG ce nablizhennya LG a VG angl DoH abreviatura sho oznachaye viznachnik gessiana angl determinant of the Hessian Usi ci masshtaboinvariantni osoblivi tochki vidilyayutsya viyavlyannyam masshtaboprostorovih ekstremumiv masshtabonormovanih diferencialnih viraziv tobto tochok u masshtaboprostorovomu podanni de vidpovidni masshtabonormovani diferencialni virazi nabuvayut lokalnih ekstremumiv yak u prostori tak i sered masshtabiv x y t argminmaxlocal x y t DnormL x y t displaystyle hat x hat y hat t operatorname argminmaxlocal x y t D mathrm norm L x y t de DnormL displaystyle D norm L poznachuye vidpovidnu masshtabonormovanu diferencialnu sutnist viznachenu nizhche Ci viyavlyachi povnishe opisano u viyavlyanni plyam Masshtabonormovani oznaki laplasiana gaussiana ta riznici gaussianiv Lindeberg 1994 1998 Lou 2004 norm2L x y t t Lxx Lyy t L x y t Dt L x y t Dt displaystyle begin aligned nabla mathrm norm 2 L x y t amp t L xx L yy amp approx frac t left L x y t Delta t L x y t right Delta t end aligned ne obov yazkovo stvoryuyut silno vibirkovi oznaki oskilki ci operatori takozh mozhut prizvoditi do reakcij bilya konturiv Dlya pokrashennya zdatnosti riznici gaussianiv viyavlyati kuti viyavlyach oznak yakij vikoristovuyut u sistemi SIFT vikoristovuye dodatkovij etap pislyaobrobki na yakomu vlasni znachennya gessiana zobrazhennya na masshtabi viyavlyannya doslidzhuyut podibno do operatora Garrisa Yaksho vidnoshennya vlasnih znachen zanadto visoke to lokalne zobrazhennya rozglyadayut yak zanadto konturopodibne tozh taku oznaku vidkidayut Takozh lindebergiv laplasianovo gaussianovij viyavlyach oznak dlya pridushennya reakcij bilya konturiv mozhlivo viznachiti z vklyuchennyam dodatkovogo poroguvannya na dodatkovomu diferencialnomu invarianti Masshtabonormovanij viznachnik operatora Gesse Lindeberg 1994 1998 detHnormL t2 LxxLyy Lxy2 displaystyle det H mathrm norm L t 2 L xx L yy L xy 2 z inshogo boku ye duzhe vibirkovim do dobre lokalizovanih oznak u zobrazhenni j reaguye lishe todi koli prisutni znachni minlivosti rivnya sirogo v dvoh napryamkah zobrazhennya i v comu ta inshih vidnoshennyah ye krashim viyavlyachem osoblivih tochok nizh laplasian gaussiana Viznachnik gessiana afinnij kovariantnij diferencialnij viraz i maye krashi vlastivosti obirannya masshtabu za afinnih peretvoren zobrazhennya nizh laplasian Lindeberg 2013 2015 Eksperimentalno ce oznachaye sho osoblivi tochki determinanta gessiana mayut krashi vlastivosti povtoryuvanosti pri lokalnij deformaciyi zobrazhennya nizh osoblivi tochki laplasiana sho svoyeyu chergoyu prizvodit do krashoyi produktivnosti zistavlyannya na osnovi zobrazhen z tochki zoru vishih pokaznikiv efektivnosti angl efficiency ta nizhchih ocinok 1 vluchnist angl 1 precision Vlastivosti obirannya masshtabu vlastivosti afinnogo peretvorennya ta eksperimentalni vlastivosti cih ta inshih viyavlyachiv masshtaboprostorovih osoblivih tochok dokladno proanalizovano v Lindeberg 2013 2015 Masshtaboprostorovi osoblivi tochki na osnovi lindebergovih mir virazhenosti gessianovih oznakNathnenij strukturno podibnimi vlastivostyami matrici Gesse Hf displaystyle Hf funkciyi f displaystyle f ta matrici drugih momentiv strukturnogo tenzora m displaystyle mu sho napriklad mozhe proyavlyatisya v terminah yihnih podibnih vlastivostej peretvorennya pri afinnih deformaciyah zobrazhennya Hf A T Hf A 1 displaystyle Hf A T Hf A 1 m A TmA 1 displaystyle mu A T mu A 1 Lindeberg 2013 2015 zaproponuvav viznachati chotiri miri virazhenosti oznak z matrici Gesse podibnim chinom yak operatori Garrisa ta Si j Tomazi viznachayutsya zi strukturnogo tenzora matrici drugih momentiv Zokrema vin viznachiv taki bezznakovi j znakovi miri virazhenosti gessianovih oznak bezznakova mira virazhenosti gessianovoyi oznaki I D1 normL t2 detHL ktrace2 HL yakshodetHL ktrace2 HL gt 00inakshe displaystyle D 1 mathrm norm L begin cases t 2 det HL k operatorname trace 2 HL amp mbox yaksho det HL k operatorname trace 2 HL gt 0 0 amp mbox inakshe end cases znakova mira virazhenosti gessianovoyi oznaki I D 1 normL t2 detHL ktrace2 HL yakshodetHL ktrace2 HL gt 0t2 detHL ktrace2 HL yakshodetHL ktrace2 HL lt 00inakshe displaystyle tilde D 1 mathrm norm L begin cases t 2 det HL k operatorname trace 2 HL amp mbox yaksho det HL k operatorname trace 2 HL gt 0 t 2 det HL k operatorname trace 2 HL amp mbox yaksho det HL k operatorname trace 2 HL lt 0 0 amp mbox inakshe end cases bezznakova mira virazhenosti gessianovoyi oznaki II D2 normL tmin l1 HL l2 HL displaystyle D 2 mathrm norm L t min lambda 1 HL lambda 2 HL znakova mira virazhenosti gessianovoyi oznaki II D 2 normL tl1 HL yaksho l1 HL lt l2 HL tl2 HL yaksho l2 HL lt l1 HL t l1 HL l2 HL 2inakshe displaystyle tilde D 2 mathrm norm L begin cases t lambda 1 HL amp mbox yaksho lambda 1 HL lt lambda 2 HL t lambda 2 HL amp mbox yaksho lambda 2 HL lt lambda 1 HL t lambda 1 HL lambda 2 HL 2 amp mbox inakshe end cases de trace HL Lxx Lyy displaystyle operatorname trace HL L xx L yy ta detHL LxxLyy Lxy2 displaystyle det HL L xx L yy L xy 2 poznachuyut slid i viznachnik matrici Gesse HL displaystyle HL masshtaboprostorovogo podannya L displaystyle L na bud yakomu masshtabi t displaystyle t todi yak l1 HL Lpp 12 Lxx Lyy Lxx Lyy 2 4Lxy2 displaystyle lambda 1 HL L pp frac 1 2 left L xx L yy sqrt L xx L yy 2 4L xy 2 right l2 HL Lqq 12 Lxx Lyy Lxx Lyy 2 4Lxy2 displaystyle lambda 2 HL L qq frac 1 2 left L xx L yy sqrt L xx L yy 2 4L xy 2 right poznachuyut vlasni znachennya matrici Gesse Bezznakova mira virazhenosti gessianovoyi oznaki D1 normL displaystyle D 1 mathrm norm L reaguye na lokalni ekstremumi dodatnimi znachennyami j ne chutliva do sidlovih tochok todi yak znakova mira virazhenosti gessianovoyi oznaki D 1 normL displaystyle tilde D 1 mathrm norm L dodatkovo reaguye na sidlovi tochki vid yemnimi znachennyami Bezznakova mira virazhenosti gessianovoyi oznaki D2 normL displaystyle D 2 mathrm norm L nechutliva do lokalnoyi polyarnosti signalu todi yak znakova mira virazhenosti gessianovoyi oznaki D 2 normL displaystyle tilde D 2 mathrm norm L reaguye na lokalnu polyarnist signalu znakom svogo rezultatu U Lindeberga 2015 ci chotiri diferencialni sutnosti bulo ob yednano z lokalnim obirannyam masshtabu na osnovi abo viyavlyannya masshtaboprostorovih ekstremumiv x y t argminmaxlocal x y t DnormL x y t displaystyle hat x hat y hat t operatorname argminmaxlocal x y t D mathrm norm L x y t abo zv yazuvannya masshtabiv angl scale linking Krim togo znakovi ta bezznakovi miri virazhenosti gessianovoyi oznaki D2 normL displaystyle D 2 mathrm norm L ta D 2 normL displaystyle tilde D 2 mathrm norm L bulo poyednano z dodatkovim poroguvannyam D1 normL gt 0 displaystyle D 1 mathrm norm L gt 0 Shlyahom eksperimentiv iz zistavlyannya zobrazhen za masshtabuvalnih peretvoren na nabori danih z 12 plakativ iz zistavlyannyam z dekilkoh tochok oglyadu nad masshtabuvalnimi peretvorennyami do koeficiyenta masshtabuvannya 6 i zminami napryamu tochki oglyadu do kuta nahilu 45 gradusiv z lokalnimi opisuvachami zobrazhennya viznachenimi z pereformulyuvan chistih opisuvachiv zobrazhennya v operatorah SIFT i SURF dlya vimiryuvannya zobrazhen u terminah operatoriv pohidnoyi gaussiana Gauss SIFT i Gauss SURF zamist pervinnogo SIFT viznachenogo z piramidi zobrazhennya abo pervinnogo SURF viznachenogo z gaarovih vejvletiv bulo pokazano sho viyavlyannya masshtaboprostorovih osoblivih tochok na osnovi bezznakovoyi miri virazhenosti gessianovoyi oznaki D1 normL displaystyle D 1 mathrm norm L dozvolili otrimati najkrashu produktivnist i krashu produktivnist nizh masshtaboprostorovi osoblivi tochki otrimuvani z viznachnika gessiana detHnormL t2 LxxLyy Lxy2 displaystyle det H mathrm norm L t 2 left L xx L yy L xy 2 right Yak bezznakova mira virazhenosti gessianovoyi oznaki D1 normL displaystyle D 1 mathrm norm L tak i znakova mira virazhenosti gessianovoyi oznaki D 1 normL displaystyle tilde D 1 norm L i viznachnik gessiana detHnormL displaystyle det H norm L dozvolili otrimati krashu produktivnist nizh laplasian gaussiana norm2L t Lxx Lyy displaystyle nabla mathrm norm 2 L t L xx L yy U poyednanni zi zv yazuvannyam masshtabiv ta dodatkovim poroguvannyam D1 normL gt 0 displaystyle D 1 mathrm norm L gt 0 znakova mira virazhenosti gessianovoyi oznaki D 2 normL displaystyle tilde D 2 mathrm norm L do togo zh dozvolila otrimati krashu produktivnist nizh laplasian gaussiana norm2L displaystyle nabla mathrm norm 2 L Krim togo bulo pokazano sho vsi ci diferencialni viyavlyachi masshtaboprostorovih osoblivih tochok viznacheni z matrici Gesse dozvolyayut viyavlyati bilshu kilkist osoblivih tochok ta dayut krashu produktivnist zistavlyannya porivnyano z operatorami Garrisa ta Si j Tomazi viznachenimi zi strukturnogo tenzora matrici drugogo momentu Teoretichnij analiz vlastivostej obirannya masshtabu cih chotiroh mir virazhenosti gessianovoyi oznaki ta inshih diferencialnih sutnostej dlya viyavlyannya masshtaboprostorovih osoblivih tochok vklyuchno z laplasianom gaussiana ta viznachnikom gessiana navedeno v Lindeberga 2013 a analiz yihnih vlastivostej afinnogo peretvorennya a takozh eksperimentalnih vlastivostej u Lindeberga 2015 Operatori afinnopristosovanih osoblivih tochokOsoblivi tochki otrimuvani bagatomasshtabovim operatorom Garrisa z avtomatichnim obirannyam masshtabu invariantni vidnosno paralelnih perenesen povorotiv i rivnomirnogo masshtabuvannya v prostorovij oblasti Prote zobrazhennya sho ye vhidnimi dlya sistem komp yuternogo zoru zaznayut takozh i perspektivnih spotvoren Shob otrimati operator osoblivih tochok stijkishij do perspektivnih peretvoren prirodnim pidhodom ye rozrobka viyavlyacha oznak invariantnogo do afinnih peretvoren Na praktici afinnoinvariantni osoblivi tochki mozhlivo otrimuvati zastosovuyuchi afinne pristosovuvannya formi koli forma yadra zgladzhuvannya iterativno deformuyetsya shobi zistavitisya z lokalnoyu strukturoyu zobrazhennya navkolo osoblivoyi tochki abo rivnoznachno lokalnij fragment zobrazhennya iterativno deformuyetsya todi yak forma yadra zgladzhuvannya zalishayetsya obertovo simetrichnoyu Lindeberg 1993 2008 Lindeberg ta Garding 1997 Mikolajchik ta Shmid 2004 Otzhe krim vikoristovuvanogo zazvichaj bagatomasshtabovogo operatora Garrisa afinne pristosovuvannya formi mozhlivo zastosovuvati j do inshih viyavlyachiv kutiv perelichenih u cij statti a takozh do diferencialnih viyavlyachiv plyam takih yak operator laplasiana riznici gaussianiv viznachnik gessiana ta gessianno laplasiannij operator Algoritm Vonga ta Brejdi viyavlyannya kutivViyavlyach Vonga ta Brejdi rozglyadaye zobrazhennya yak poverhnyu j shukaye miscya velikoyi krivini vzdovzh konturu v zobrazhenni Inshimi slovami cej algoritm shukaye miscya de kontur shvidko zminyuye napryamok Kutova ocinka angl corner score C displaystyle C zadayetsya yak C d2Idt2 2 c I 2 displaystyle C left frac delta 2 I delta mathbf t 2 right 2 c nabla I 2 de t displaystyle bf t odinichnij vektor perpendikulyarnij gradiyentovi a c displaystyle c viznachaye konturofobnist viyavlyacha Avtori takozh vidznachayut sho dlya zmenshennya shumu neobhidne zgladzhuvannya radyat gaussove Zgladzhuvannya takozh prizvodit do zmishennya kutiv tomu avtori vivodyat viraz dlya zmishennya kuta v 90 gradusiv i zastosovuyut jogo yak popravkovij koeficiyent do viyavlenih kutiv Viyavlyach kutiv SUSANSUSAN ce abreviatura sho oznachaye najmenshij odnoridnij segment sho upodibnyuyetsya yadru angl smallest univalue segment assimilating nucleus Cej metod ye predmetom patentu Velikoyi Britaniyi 1994 roku yakij bilshe ne diye Dlya viyavlyannya oznak SUSAN rozmishuye krugovu masku na pikseli yakij potribno pereviriti yadri angl nucleus Oblastyu maski ye M displaystyle M a piksel u cij masci podayetsya cherez m M displaystyle vec m in M Yadro perebuvaye v m 0 displaystyle vec m 0 Kozhen piksel porivnyuyetsya z yadrom za dopomogoyu funkciyi porivnyannya c m e I m I m 0 t 6 displaystyle c vec m e left frac I vec m I vec m 0 t right 6 de t displaystyle t porig riznici yaskravosti I displaystyle I yaskravist pikselya a stepin eksponenti viznacheno empirichno Cya funkciya viglyadaye yak zgladzhenij cilindr abo pryamokutna funkciya Plosha SUSAN viznachayetsya cherez n M m Mc m displaystyle n M sum vec m in M c vec m Yaksho c displaystyle c pryamokutna funkciya to n displaystyle n kilkist pikseliv u masci sho perebuvayut v mezhah t displaystyle t vid yadra Vidguk operatora SUSAN zadayetsya cherez R M g n M yaksho n M lt g0inakshe displaystyle R M begin cases g n M amp mbox yaksho n M lt g 0 amp mbox inakshe end cases de g displaystyle g nazivayetsya geometrichnim porogom Inshimi slovami operator SUSAN daye dodatnu ocinku lishe yaksho plosha dosit mala Najmenshij SUSAN lokalno mozhlivo znahoditi za dopomogoyu pridushuvannya nemaksimumiv i ce povnij operator SUSAN Znachennya t displaystyle t viznachaye naskilki podibnimi do yadra mayut buti tochki shobi vvazhatisya chastinoyu odnoridnogo segmenta angl univalue segment Znachennya g displaystyle g viznachaye minimalnij rozmir odnoridnogo segmenta Yaksho g displaystyle g dostatno velike to ce staye viyavlyachem konturiv Dlya viyavlyannya kutiv vikoristovuyut she dva kroki Po pershe znahodyat centroyid SUSAN Pravilnij kut matime centroyid daleko vid yadra Drugij krok napolyagaye na tomu sho vsi tochki na liniyi vid yadra cherez centroyid do krayu maski perebuvayut u SUSAN Viyavlyach kutiv Trajkovicha ta GedliPodibno do SUSAN cej viyavlyach bezposeredno pereviryaye chi ye plyama pid pikselem samopodibnoyu doslidzhuyuchi susidni pikseli c displaystyle vec c piksel yakij potribno rozglyanuti a p P displaystyle vec p in P tochka na koli P displaystyle P z centrom u c displaystyle vec c Tochka p displaystyle vec p diametralno protilezhna do p displaystyle vec p Funkciyu vidguku viznachayut cherez r c minp P I p I c 2 I p I c 2 displaystyle 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 Vin bude velikim yaksho nemaye napryamu v yakomu centralnij piksel podibnij do dvoh susidnih pikseliv po diametru P displaystyle P diskretizovane kolo kolo Brezengema tomu dlya promizhnih diametriv vikoristovuyut interpolyaciyu shob otrimuvati izotropnishij vidguk Oskilki bud yake obchislennya daye verhnyu mezhu dlya min displaystyle min spochatku pereviryayut gorizontalnij i vertikalnij napryamki shobi pobachiti chi varto prodovzhuvati povne obchislennya c displaystyle c Viyavlyachi oznak na osnovi ASTAST ce abreviatura sho oznachaye priskorenu segmentnu perevirku angl accelerated segment test Cya perevirka rozslablena versiya kutovogo kriteriyu SUSAN Zamist ocinyuvannya krugovogo diska rozglyadayut lishe pikseli na koli Brezengema radiusa r displaystyle r navkolo tochki kandidata Yaksho vsi n displaystyle n sumizhnih pikseliv yaskravishi za yadro prinajmni na t displaystyle t abo vsi temnishi za yadro na t displaystyle t to piksel pid yadrom vvazhayut oznakoyu Povidomlyayut sho cej kriterij daye duzhe stabilni oznaki Vibir poryadku v yakomu pereviryayutsya pikseli ye tak zvanoyu zadacheyu dvadcyati zapitan Pobudova korotkih derev rishen dlya ciyeyi zadachi prizvodit do obchislyuvalno najefektivnishih dostupnih viyavlyachiv oznak Pershim algoritmom viyavlyannya kutiv na osnovi AST ye FAST oznaki z priskorenoyi segmentnoyi perevirki angl features from accelerated segment test Hocha r displaystyle r mozhe v principi nabuvati bud yakogo znachennya FAST vikoristovuye lishe znachennya 3 sho vidpovidaye kolu v 16 pikseliv na nomu a perevirki pokazuyut sho najkrashi rezultati dosyagayutsya koli n displaystyle n stanovit 9 Ce znachennya n displaystyle n ye najnizhchim za yakogo ne viyavlyayutsya konturi Poryadok u yakomu pereviryayutsya pikseli viznachayetsya algoritmom ID3 z trenuvalnogo naboru zobrazhen Yak ne divno nazva cogo viyavlyacha desho shozha na nazvu statti yaka opisuye viyavlyach Trajkovicha ta Gedli Avtomatichne sintezuvannya viyavlyachivTruhiljo ta Olague predstavili metod v yakomu vikoristovuyetsya genetichne programuvannya dlya avtomatichnogo sintezuvannya operatoriv nad zobrazhennyami sho mozhut viyavlyati osoblivi tochki Nabori listkiv i funkcij mistyat primitivni operaciyi yaki ye poshirenimi v bagatoh ranishe zaproponovanih shtuchnih konstrukciyah Dopasovanist vimiryuye stabilnist kozhnogo operatora cherez koeficiyent povtoryuvanosti ta spriyaye rivnomirnomu rozpodilu viyavlenih tochok u ploshini zobrazhennya Produktivnist cih vivedenih operatoriv bulo pidtverdzheno eksperimentalno z vikoristannyam trenuvalnih ta perevirnih poslidovnostej postupovo peretvoryuvanih zobrazhen Takim chinom zaproponovanij algoritm GP vvazhayetsya dlya zadachi viyavlyannya osoblivih tochok konkurentospromozhnim vidnosno lyudini Viyavlyachi prostorovo chasovih osoblivih tochokLaptyev ta Lindeberg rozshirili operator Garrisa do prostoru chasu Nehaj m displaystyle mu poznachuye prostorovo chasovu matricyu drugih momentiv viznachenu cherez A u v wh u v w Lx u v w 2Lx u v w Ly u v w Lx u v w Lt u v w Lx u v w Ly u v w Ly u v w 2Ly u v w Lt u v w Lx u v w Lt u v w Ly u v w Lt u v w Lt u v w 2 Lx2 LxLy LxLt LxLy Ly2 LyLt LxLt LyLt Lt2 displaystyle A sum u sum v sum w h u v w begin bmatrix L x u v w 2 amp L x u v w L y u v w amp L x u v w L t u v w L x u v w L y u v w amp L y u v w 2 amp L y u v w L t u v w L x u v w L t u v w amp L y u v w L t u v w amp L t u v w 2 end bmatrix begin bmatrix langle L x 2 rangle amp langle L x L y rangle amp langle L x L t rangle langle L x L y rangle amp langle L y 2 rangle amp langle L y L t rangle langle L x L t rangle amp langle L y L t rangle amp langle L t 2 rangle end bmatrix Todi dlya pridatnogo viboru k lt 1 27 displaystyle k lt 1 27 prostorovo chasovi osoblivi tochki viyavlyayutsya z prostorovo chasovih ekstremumiv nastupnoyi prostorovo chasovoyi miri Garrisa H det m ktrace2 m displaystyle H det mu kappa operatorname trace 2 mu Viznachnik gessiana bulo rozshireno do spilnogo prostoru chasu Villemsom ta in ta Lindebergom sho dalo nastupnij masshtabonormovanij diferencialnij viraz det H x y t normL s2gstgt LxxLyyLtt 2LxyLxtLyt LxxLyt2 LyyLxt2 LttLxy2 displaystyle 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 U praci Villemsa ta in bulo vikoristano prostishij viraz sho vidpovidaye gs 1 displaystyle gamma s 1 ta gt 1 displaystyle gamma tau 1 U Lindeberga bulo pokazano sho gs 5 4 displaystyle gamma s 5 4 ta gt 5 4 displaystyle gamma tau 5 4 dayut krashi masshtaboobiralni vlastivosti v tomu sensi sho obirani rivni masshtabu otrimuvani z prostorovo chasovoyi gaussovoyi plyami z prostorovoyu protyazhnistyu s s0 displaystyle s s 0 j chasovoyu trivalistyu t t0 displaystyle tau tau 0 idealno vidpovidatimut prostorovij protyazhnosti ta chasovij trivalosti ciyeyi plyami z vikonannyam obirannya masshtabu shlyahom viyavlyannya prostorovo chasovih masshtaboprostorovih ekstremumiv cogo diferencialnogo virazu Lindeberg rozshiriv operator Laplasa na prostorovo chasovi videodani sho dalo nastupni dva prostorovo chasovi operatori yaki takozh stanovlyat modeli receptivnih poliv nejroniv BKYa bez zapiznyuvannya i z zapiznyuvannyam t norm x y norm2L sgstgt 2 Lxxt Lyyt displaystyle partial t mathrm norm nabla x y mathrm norm 2 L s gamma s tau gamma tau 2 L xxt L yyt tt norm x y norm2L sgstgt Lxxtt Lyytt displaystyle partial tt mathrm norm nabla x y mathrm norm 2 L s gamma s tau gamma tau L xxtt L yytt Dlya pershogo operatora potribni vlastivosti viboru masshtabu gs 1 displaystyle gamma s 1 i gt 1 2 displaystyle gamma tau 1 2 yaksho mi hochemo shobi cej operator nabuvav svogo maksimalnogo znachennya nad prostorovo chasovimi masshtabami na rivni prostorovo chasovogo masshtabu yakij vidobrazhaye prostorovu protyazhnist i chasovu trivalist gaussovoyi plyami yaka z yavlyayetsya Dlya drugogo operatora potribni vlastivosti viboru masshtabu gs 1 displaystyle gamma s 1 i gt 3 4 displaystyle gamma tau 3 4 yaksho mi hochemo shobi cej operator nabuvav svogo maksimalnogo znachennya nad prostorovo chasovimi masshtabami na rivni prostorovo chasovogo masshtabu sho vidobrazhaye prostorovu protyazhnist i chasovu trivalist gaussovoyi plyami yaka zblimuye Kolirni rozshirennya viyavlyachiv prostorovo chasovih osoblivih tochok bulo doslidzheno Evertsom ta in BibliografiyaAndrew Willis and Yunfeng Sui 2009 An Algebraic Model for fast Corner Detection 2009 IEEE 12th International Conference on Computer Vision IEEE s 2296 2302 doi 10 1109 ICCV 2009 5459443 ISBN 978 1 4244 4420 5 angl en and George C Stockman 2001 Computer Vision p 257 Prentice Books Upper Saddle River ISBN 0 13 030796 3 angl H Moravec 1980 Tech Report CMU RI TR 3 Carnegie Mellon University Robotics Institute Arhiv originalu za 12 zhovtnya 2016 Procitovano 18 kvitnya 2022 angl Obstacle Avoidance and Navigation in the Real World by a Seeing Robot Rover Hans Moravec March 1980 Computer Science Department Stanford University Ph D thesis angl C Harris and M Stephens 1988 PDF Proceedings of the 4th Alvey Vision Conference s 147 151 Arhiv originalu PDF za 1 kvitnya 2022 Procitovano 18 kvitnya 2022 angl Javier Sanchez Nelson Monzon and Agustin Salgado 2018 Image Processing on Line 8 305 328 doi 10 5201 ipol 2018 229 Arhiv originalu za 12 lyutogo 2022 Procitovano 18 kvitnya 2022 angl J Shi and C Tomasi June 1994 Good Features to Track 9th IEEE Conference on Computer Vision and Pattern Recognition Springer s 593 600 CiteSeerX 10 1 1 36 2669 doi 10 1109 CVPR 1994 323794 angl C Tomasi and T Kanade 1991 Detection and Tracking of Point Features Tehnichnij zvit CMU CS 91 132 School of Computer Science Carnegie Mellon University CiteSeerX 10 1 1 45 5770 angl A Noble 1989 Ph D Department of Engineering Science Oxford University s 45 Arhiv originalu za 27 chervnya 2019 Procitovano 18 kvitnya 2022 angl Forstner W Gulch 1987 A Fast Operator for Detection and Precise Location of Distinct Points Corners and Centres of Circular Features PDF ISPRS a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite journal title Shablon Cite journal cite journal a Obslugovuvannya CS1 Storinki z parametrom url status ale bez parametra archive url posilannya angl T Lindeberg 1994 Junction detection with automatic selection of detection scales and localization scales Proc 1st International Conference on Image Processing T I Austin Texas s 924 928 angl Tony Lindeberg 1998 International Journal of Computer Vision T 30 2 s 77 116 Arhiv originalu za 18 kvitnya 2022 Procitovano 18 kvitnya 2022 angl T Lindeberg 1994 Springer ISBN 978 0 7923 9418 1 Arhiv originalu za 30 listopada 2020 Procitovano 18 kvitnya 2022 angl T Lindeberg and J Garding Shape adapted smoothing in estimation of 3 D depth cues from affine distortions of local 2 D structure Image and Vision Computing 15 6 pp 415 434 1997 14 lyutogo 2022 u Wayback Machine angl T Lindeberg 2008 Scale Space U Benjamin Wah red Wiley Encyclopedia of Computer Science and Engineering T IV John Wiley and Sons s 2495 2504 doi 10 1002 9780470050118 ecse609 ISBN 978 0 470 05011 8 angl K Mikolajczyk K and C Schmid 2004 PDF International Journal of Computer Vision 60 1 63 86 doi 10 1023 B VISI 0000027790 02288 f2 Arhiv originalu PDF za 7 sichnya 2018 Procitovano 18 kvitnya 2022 angl L Kitchen and A Rosenfeld 1982 Gray level corner detection Pattern Recognition Letters T 1 2 s 95 102 angl J J Koenderink and W Richards 1988 Two dimensional curvature operators Journal of the Optical Society of America A T 5 7 s 1136 1141 angl L Bretzner and T Lindeberg 1998 Feature tracking with automatic selection of spatial scales Computer Vision and Image Understanding T 71 s 385 392 angl T Lindeberg and M X Li 1997 Computer Vision and Image Understanding T 67 1 s 88 98 Arhiv originalu za 18 kvitnya 2022 Procitovano 18 kvitnya 2022 angl D Lowe 2004 International Journal of Computer Vision 60 2 91 CiteSeerX 10 1 1 73 2924 doi 10 1023 B VISI 0000029664 99615 94 Arhiv originalu za 10 travnya 2008 Procitovano 18 kvitnya 2022 angl T Lindeberg Image matching using generalized scale space interest points Journal of Mathematical Imaging and Vision volume 52 number 1 pages 3 36 2015 angl T Lindeberg Scale selection properties of generalized scale space interest point detectors Journal of Mathematical Imaging and Vision Volume 46 Issue 2 pages 177 210 2013 angl Lindeberg T 1998 International Journal of Computer Vision 30 2 117 154 doi 10 1023 A 1008097225773 Arhiv originalu za 14 lyutogo 2022 Procitovano 18 kvitnya 2022 angl H Wang and M Brady 1995 Real time corner detection algorithm for motion estimation Image and Vision Computing 13 9 695 703 doi 10 1016 0262 8856 95 98864 P angl S M Smith and J M Brady May 1997 International Journal of Computer Vision 23 1 45 78 doi 10 1023 A 1007963824710 Arhiv originalu za 29 serpnya 2012 Procitovano 18 kvitnya 2022 angl S M Smith and J M Brady January 1997 Method for digitally processing images to determine the position of edges and or corners therein for guidance of unmanned vehicle UK Patent 2272285 Proprietor Secretary of State for Defence UK angl GB patent 2272285 Smith Stephen Mark Determining the position of edges and corners in images published 1994 05 11 issued 1994 05 11 assigned to Secr Defence angl Arhiv originalu za 16 veresnya 2017 Procitovano 18 kvitnya 2022 angl M Trajkovic and M Hedley 1998 Fast corner detection Image and Vision Computing 16 2 75 87 doi 10 1016 S0262 8856 97 00056 5 angl E Rosten and T Drummond May 2006 European Conference on Computer Vision Arhiv originalu za 17 bereznya 2008 Procitovano 18 kvitnya 2022 angl Leonardo Trujillo and Gustavo Olague 2008 PDF Evolutionary Computation 16 4 483 507 doi 10 1162 evco 2008 16 4 483 PMID 19053496 Arhiv originalu PDF za 17 lipnya 2011 angl Ivan Laptev and Tony Lindeberg 2003 International Conference on Computer Vision IEEE s 432 439 Arhiv originalu za 18 kvitnya 2022 Procitovano 18 kvitnya 2022 angl Geert Willems Tinne Tuytelaars and Luc van Gool 2008 An efficient dense and scale invariant spatiotemporal temporal interest point detector European Conference on Computer Vision Springer Lecture Notes in Computer Science T 5303 s 650 663 doi 10 1007 978 3 540 88688 4 48 angl Tony Lindeberg 2018 Spatio temporal scale selection in video data Journal of Mathematical Imaging and Vision T 60 4 s 525 562 doi 10 1007 s10851 017 0766 9 angl I Everts J van Gemert and T Gevers 2014 Evaluation of color spatio temporal interest points for human action recognition IEEE Transactions on Image Processing T 23 4 s 1569 1589 doi 10 1109 TIP 2014 2302677 angl Etalonni vtilennyaCej rozdil mistit zovnishni posilannya na etalonni vtilennya deyakih z opisanih vishe viyavlyachiv Ci etalonni vtilennya nadano avtorami praci v yakij vpershe opisano viyavlyach Voni mozhut mistiti detali vidsutni abo neyavni v pracyah sho opisuyut yihni vlastivosti Viyavlyannya RG 14 lyutogo 2007 u Wayback Machine yak chastina sistemi SIFT vikonuvani fajli Windows ta x86 Linux Garrisa Laplasa 5 lyutogo 2012 u Wayback Machine statichni vikonuvani fajli Linux Takozh mistit viyavlyachi RG ta LG j afinne pristosovuvannya dlya vsih vklyuchenih viyavlyachiv Viyavlyach FAST 17 bereznya 2022 u Wayback Machine pervinnij kod C C MATLAB i vikonuvani fajli dlya riznih operacijnih sistem ta arhitektur lip vireo 11 travnya 2017 u Wayback Machine vikonuvani fajli LG RG Garrisa Laplasa gessiannij i gessianno laplasiannij SIFT viddzerkalyuvalno invariantnij SIFT PCA SIFT PSIFT Steerable Filters SPIN vikonuvani fajli Linux Windows ta SunOS Nizkorivneva obrobka zobrazhen SUSAN 26 kvitnya 2022 u Wayback Machine pervinnij kod C Onlajn vtilennya garrisovogo viyavlyacha kutiv IPOL 14 lyutogo 2022 u Wayback Machine Div takozhviyavlyannya plyam afinne pristosovuvannya formi prostir masshtabiv viyavlyannya hrebtiv viyavlyannya osoblivih tochok viyavlyannya oznak komp yuterne bachennya pohidna zobrazhennyaPosilannyaLindeberg Tony 2001 Corner detection u Hazewinkel Michiel red Matematichna enciklopediya Springer ISBN 978 1 55608 010 4 angl Brostow Corner Detection UCL Computer Science 8 bereznya 2022 u Wayback Machine angl