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

Матеріал з Вікіпедії — вільної енциклопедії.
(Перенаправлено з Гаррісів кут)
Перейти до навігації Перейти до пошуку
Вихід типового алгоритму виявляння кутів

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

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

[ред. | ред. код]

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

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

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

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

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

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

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

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

[ред. | ред. код]

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

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

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

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

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

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

[ред. | ред. код]

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

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

можливо наблизити розкладом Тейлора. Нехай та  — частинні похідні , такі, що

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

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

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

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

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

Кут (або особлива точка загалом) характеризується великою мінливістю у всіх напрямках вектора . Через аналіз власних значень цю характеристику можливо виразити наступним чином: для особливої точки повинен мати два «великі» власні значення. Виходячи з цього аргументу, на основі величини власних значень можливо робити наступні висновки:

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

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

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

Алгоритм Сі — Томазі[7] виявляння кутів обчислює безпосередньо, оскільки за певних припущень кути є стійкішими для відстежування. Зауважте, що цей метод іноді називають алгоритмом Канаде — Томазі виявляння кутів.

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

Можливо уникнути встановлювання параметра шляхом використання кутової міри Нобла[8] , що дорівнює середньому гармонійному власних значень:

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

Якщо можливо інтерпретувати як матрицю прецизійності[en] для положення кута, то коваріаційною матрицею для положення кута є , тобто

Сума власних значень , яку в цьому випадку можливо інтерпретувати як узагальнену дисперсію (або «повну невизначеність») положення кута, пов'язана з кутовою мірою Нобла наступним рівнянням:

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

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

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

Рівняння дотичної в пікселі задається як

де  — вектор градієнта зображення в .

Точка , найближча до всіх дотичних у вікні , це

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

Розв'язання для :

визначаються як:

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

Зауважте, що  — структурний тензор. Щоби це рівняння мало розв'язок, мусить бути оборотною, що означає, що мусить бути матрицею повного рангу (рангу 2). Таким чином, розв'язок

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

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

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

Примітки:

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

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

[ред. | ред. код]

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

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

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

і нехай та позначують частинні похідні від . Крім того, введімо віконну гауссову функцію з параметром масштабу інтегрування . Тоді багатомасштабову матрицю другого моменту (англ. multi-scale second-moment matrix)[12][13][14] можливо визначити через

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

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

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

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

  • просторовими максимумами багатомасштабової кутової міри
  • локальними максимумами або мінімуми за масштабами масштабонормованого оператора Лапласа[11] :

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

[ред. | ред. код]

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

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

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

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

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

[ред. | ред. код]

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

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

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

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

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

,

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

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

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

[ред. | ред. код]

Натхнений структурно подібними властивостями матриці Гессе функції та матриці других моментів (структурного тензора) , що, наприклад, може проявлятися в термінах їхніх подібних властивостей перетворення при афінних деформаціях зображення[13][21]

,
,

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

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

де та позначують слід і визначник матриці Гессе масштабопросторового подання на будь-якому масштабі , тоді як

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

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

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

,

або зв'язування масштабів (англ. scale linking). Крім того, знакові та беззнакові міри вираженості гессіанової ознаки та було поєднано з додатковим порогуванням .

Шляхом експериментів із зіставляння зображень за масштабувальних перетворень на наборі даних з 12 плакатів із зіставлянням з декількох точок огляду над масштабувальними перетвореннями до коефіцієнта масштабування 6 і змінами напряму точки огляду до кута нахилу 45 градусів з локальними описувачами зображення, визначеними з переформулювань чистих описувачів зображення в операторах SIFT і SURF для вимірювання зображень у термінах операторів похідної гауссіана (Gauss-SIFT і Gauss-SURF) замість первинного SIFT, визначеного з піраміди зображення, або первинного SURF, визначеного з гаарових вейвлетів, було показано, що виявляння масштабопросторових особливих точок на основі беззнакової міри вираженості гессіанової ознаки дозволили отримати найкращу продуктивність, і кращу продуктивність, ніж масштабопросторові особливі точки, отримувані з визначника гессіана . Як беззнакова міра вираженості гессіанової ознаки , так і знакова міра вираженості гессіанової ознаки і визначник гессіана дозволили отримати кращу продуктивність, ніж лапласіан гауссіана . У поєднанні зі зв'язуванням масштабів та додатковим порогуванням знакова міра вираженості гессіанової ознаки до того ж дозволила отримати кращу продуктивність, ніж лапласіан гауссіана .

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

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

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

[ред. | ред. код]

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

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

[ред. | ред. код]

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

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

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

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

[ред. | ред. код]

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

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

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

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

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

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

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

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

[ред. | ред. код]

Подібно до SUSAN, цей виявляч[28] безпосередньо перевіряє, чи є пляма під пікселем самоподібною, досліджуючи сусідні пікселі.  — піксель, який потрібно розглянути, а  — точка на колі з центром у . Точка  — діаметрально протилежна до .

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

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

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

[ред. | ред. код]

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

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

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

[ред. | ред. код]

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

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

[ред. | ред. код]

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

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

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

У праці Віллемса та ін.[32] було використано простіший вираз, що відповідає та . У Ліндеберга[33] було показано, що та дають кращі масштабообиральні властивості в тому сенсі, що обирані рівні масштабу, отримувані з просторово-часової гауссової плями з просторовою протяжністю й часовою тривалістю , ідеально відповідатимуть просторовій протяжності та часовій тривалості цієї плями, з виконанням обирання масштабу шляхом виявляння просторово-часових масштабопросторових екстремумів цього диференціального виразу.

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

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

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

Бібліографія

[ред. | ред. код]
  1. 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 978-1-4244-4420-5. (англ.)
  2. Shapiro, Linda[en] and George C. Stockman (2001). Computer Vision, p. 257. Prentice Books, Upper Saddle River. ISBN 0-13-030796-3. (англ.)
  3. H. Moravec (1980). Obstacle Avoidance and Navigation in the Real World by a Seeing Robot Rover. Tech Report CMU-RI-TR-3 Carnegie-Mellon University, Robotics Institute. Архів оригіналу за 12 жовтня 2016. Процитовано 18 квітня 2022. (англ.)
  4. 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) (англ.)
  5. C. Harris and M. Stephens (1988). A combined corner and edge detector (PDF). Proceedings of the 4th Alvey Vision Conference. с. 147—151. Архів оригіналу (PDF) за 1 квітня 2022. Процитовано 18 квітня 2022. (англ.)
  6. Javier Sánchez, Nelson Monzón and Agustín Salgado (2018). An Analysis and Implementation of the Harris Corner Detector. Image Processing on Line. 8: 305—328. doi:10.5201/ipol.2018.229. Архів оригіналу за 12 лютого 2022. Процитовано 18 квітня 2022. (англ.)
  7. 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. (англ.)
  8. A. Noble (1989). Descriptions of Image Surfaces (Ph.D.). Department of Engineering Science, Oxford University. с. 45. Архів оригіналу за 27 червня 2019. Процитовано 18 квітня 2022. (англ.)
  9. 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.{{cite journal}}: Обслуговування CS1: Сторінки з параметром url-status, але без параметра archive-url (посилання) (англ.)
  10. а б в 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. (англ.)
  11. а б в г д е ж и к л м Tony Lindeberg (1998). Feature detection with automatic scale selection. International Journal of Computer Vision. Т. 30, № 2. с. 77—116. Архів оригіналу за 18 квітня 2022. Процитовано 18 квітня 2022. (англ.)
  12. а б в г д е ж и T. Lindeberg (1994). Scale-Space Theory in Computer Vision. Springer. ISBN 978-0-7923-9418-1. Архів оригіналу за 30 листопада 2020. Процитовано 18 квітня 2022. (англ.)
  13. а б в г 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.] (англ.)
  14. а б в 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 978-0-470-05011-8. (англ.)
  15. а б в K. Mikolajczyk, K. and C. Schmid (2004). Scale and affine invariant interest point detectors (PDF). International Journal of Computer Vision. 60 (1): 63—86. doi:10.1023/B:VISI.0000027790.02288.f2. Архів оригіналу (PDF) за 7 січня 2018. Процитовано 18 квітня 2022. (англ.)
  16. L. Kitchen and A. Rosenfeld (1982). Gray-level corner detection. Pattern Recognition Letters. Т. 1, № 2. с. 95—102. (англ.)
  17. J. J. Koenderink and W. Richards (1988). Two-dimensional curvature operators. Journal of the Optical Society of America A. Т. 5, № 7. с. 1136—1141. (англ.)
  18. L. Bretzner and T. Lindeberg (1998). Feature tracking with automatic selection of spatial scales. Computer Vision and Image Understanding. Т. 71. с. 385—392. (англ.)
  19. T. Lindeberg and M.-X. Li (1997). Segmentation and classification of edges using minimum description length approximation and complementary junction cues. Computer Vision and Image Understanding. Т. 67, № 1. с. 88—98. Архів оригіналу за 18 квітня 2022. Процитовано 18 квітня 2022. (англ.)
  20. а б в D. Lowe (2004). Distinctive Image Features from Scale-Invariant Keypoints. 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. (англ.)
  21. а б в г д е ж и T. Lindeberg ``Image matching using generalized scale-space interest points", Journal of Mathematical Imaging and Vision, volume 52, number 1, pages 3-36, 2015. (англ.)
  22. а б в г 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. (англ.)
  23. Lindeberg, T. (1998). Edge detection and ridge detection with automatic scale selection. International Journal of Computer Vision. 30 (2): 117—154. doi:10.1023/A:1008097225773. Архів оригіналу за 14 лютого 2022. Процитовано 18 квітня 2022. (англ.)
  24. 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. (англ.)
  25. S. M. Smith and J. M. Brady (May 1997). SUSAN – a new approach to low level image processing. 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. (англ.)
  26. 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  (англ.)
  27. The SUSAN Edge Detector in Detail. Архів оригіналу за 16 вересня 2017. Процитовано 18 квітня 2022. (англ.)
  28. 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. (англ.)
  29. а б E. Rosten and T. Drummond (May 2006). Machine learning for high-speed corner detection. European Conference on Computer Vision. Архів оригіналу за 17 березня 2008. Процитовано 18 квітня 2022. (англ.)
  30. Leonardo Trujillo and Gustavo Olague (2008). Automated design of image operators that detect interest points (PDF). Evolutionary Computation. 16 (4): 483—507. doi:10.1162/evco.2008.16.4.483. PMID 19053496. Архів оригіналу (PDF) за 17 липня 2011. (англ.)
  31. Ivan Laptev and Tony Lindeberg (2003). Space-time interest points. International Conference on Computer Vision. IEEE. с. 432—439. Архів оригіналу за 18 квітня 2022. Процитовано 18 квітня 2022. (англ.)
  32. а б 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. (англ.)
  33. а б в 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. (англ.)
  34. 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. (англ.)

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

[ред. | ред. код]

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

Див. також

[ред. | ред. код]

Посилання

[ред. | ред. код]