Виявля́ння куті́в () — це підхід, який використовують у системах комп'ютерного бачення для виділяння певних типів ознак і визначання вмісту зображення. Виявляння кутів часто використовують для виявляння руху, зіставляння зображень, відстежування у відео, , , тривимірної відбудови та . Виявляння кутів перетинається з темою виявляння особливих точок.
Формалізація
Кут можливо визначити як перетин двох контурів. Кут також можливо визначити як точку, для якої існують два панівних і різних напрями контуру в локальному околі цієї точки.
Особлива точка — це точка в зображенні, яка має чітко визначене положення, і її можливо надійно виявляти. Це означає, що особлива точка може бути кутом, але також може бути, наприклад, ізольованою точкою локального максимуму чи мінімуму яскравості, закінченнями лінії, або точкою на кривій, де кривина локально максимальна.
На практиці більшість так званих методів виявляння кутів виявляють особливі точки загалом, і насправді терміни «кут» () та «особлива точка» () використовують у літературі більш-менш взаємозамінно. Як наслідок, якщо потрібно виявляти лише кути, необхідно робити локальний аналіз виявлених особливих точок, щоби визначати, які з них є справжніми кутами. Прикладами виявляння країв, які можливо використовувати з післяопрацюванням для виявляння кутів, є оператор Кірша та набір масок Фрая — Чена. and George C. Stockman (2001). Computer Vision, p. 257. Prentice Books, Upper Saddle River. .
Терміни «кут», «особлива точка» й «ознака» () використовують у літературі як синоніми, що заплутує питання. Зокрема, існує кілька виявлячів плям, які можливо називати «операторами особливих точок», але які іноді помилково називають «виявлячами кутів». Крім того, існує поняття виявляння хребтів для вловлювання наявності витягнутих об'єктів.
Виявлячі кутів зазвичай не дуже надійні й часто вимагають запровадження значного дублювання, щоби запобігати домінуванню окремих помилок в задачі розпізнавання.
Один з критеріїв якості виявляча кутів — його здатність виявляти один і той же кут на кількох подібних зображеннях в умовах різного освітлення, паралельного перенесення, повертання та інших перетворень.
Простий підхід до виявляння кутів у зображеннях — використання кореляції, але це дуже обчислювально витратно й неоптимально. Часто вживаний альтернативний підхід ґрунтується на методі, запропонованому Гаррісом та Стівенсом (нижче), який, своєю чергою, є вдосконаленням методу Моравека.
Алгоритм Моравека виявляння кутів
Це один з найперших алгоритмів виявляння кутів, який визначає кут () як точку з низькою самоподібністю. Цей алгоритм перевіряє кожен піксель у зображенні на наявність кута, розглядаючи, наскільки фрагмент з центром у цьому пікселі схожий на сусідні фрагменти, що значною мірою перекриваються. Подібність вимірюється шляхом отримання суми квадратів різниць (СКР) між відповідними пікселями двох фрагментів. Менше число вказує на більшу схожість.
Якщо піксель перебуває в області рівномірної яскравості, то найближчі фрагменти виглядатимуть подібно. Якщо піксель перебуває на контурі, то найближчі фрагменти в напрямку, перпендикулярному до контуру, виглядатимуть зовсім інакше, але найближчі фрагменти в напрямку, паралельному контуру, даватимуть лише незначні зміни. Якщо піксель перебуває на об'єкті зі змінами в усіх напрямках, то жоден із сусідніх фрагментів не буде схожим.
Вираженість кута визначається як найменша СКР між фрагментом та його сусідами (горизонтально, вертикально, та по двох діагоналях). Сенс у тому, що якщо це число велике, то мінливість вздовж усіх зміщень більше або дорівнює йому, вловлюючи, що всі найближчі фрагменти виглядають інакше.
Якщо значення вираженості кута обчислюється для всіх положень, то якщо воно локально максимальне для одного місця, це вказує на те, що в ньому присутня потрібна ознака.
Як зазначив Моравек, одна з головних проблем цього оператора полягає в його неізотропності: якщо присутній контур, що не перебуває в напрямку сусідів (горизонтально, вертикально чи діагонально), то найменша СКР буде великою, й цей контур буде неправильно обрано як особливу точку.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)
Алгоритми Гарріса й Стівенса / Сі — Томазі виявляння кутів
Гарріс і Стівенс вдосконалили виявляч кутів Моравека шляхом безпосереднього розгляду диференціалу кутової оцінки відносно напряму замість використання зміщених фрагментів. (Цю кутову оцінку часто називають автокореляцією, оскільки цей термін використовується в статті, в якій описано цей виявляч. Проте математика в статті чітко вказує, що використовується сума квадратів різниць.)
Без втрати загальності вважатимемо, що використовується двовимірне зображення у відтінках сірого. Нехай це зображення задано через . Розгляньмо взяття фрагменту зображення над областю , й зміщення його на . Зважена сума квадратів різниць (СКР) між цими двома фрагментами, позначувана через , задається як
можливо наблизити розкладом Тейлора. Нехай та — частинні похідні , такі, що
Це дає наближення
яке можливо записати в матричному вигляді:
де A — структурний тензор,
Словами, ми знаходимо коваріацію частинної похідної яскравості зображення відносно осей та .
Кутові дужки позначують усереднення (тобто підсумовування над ). позначує тип вікна, що ковзає зображенням. При використанні відгук буде анізотропним, але при використані гауссового фільтра відгук буде ізотропним.
Кут (або особлива точка загалом) характеризується великою мінливістю у всіх напрямках вектора . Через аналіз власних значень цю характеристику можливо виразити наступним чином: для особливої точки повинен мати два «великі» власні значення. Виходячи з цього аргументу, на основі величини власних значень можливо робити наступні висновки:
Якщо і , то цей піксель не має особливих ознак. Якщо , а має деяке велике додатне значення, то знайдено контур. Якщо і мають великі додатні значення, то знайдено кут.
Гарріс і Стівенс відзначають, що точне обчислення власних значень є обчислювально витратним, оскільки вимагає обчислення квадратного кореня, й натомість пропонують наступну функцію , де є налаштовуваним параметром чутливості:
Отже, цей алгоритм не має насправді обчислювати власний розклад матриці , а замість цього, щоби знаходити кути, а точніше особливі точки загалом, достатньо оцінювати визначник та слід .
Алгоритм Сі — Томазі виявляння кутів обчислює безпосередньо, оскільки за певних припущень кути є стійкішими для відстежування. Зауважте, що цей метод іноді називають алгоритмом Канаде — Томазі виявляння кутів.
Значення має визначатися емпірично, в літературі повідомляють, що придатними є значення в проміжку 0,04–0,15.
Можливо уникнути встановлювання параметра шляхом використання кутової міри Нобла , що дорівнює середньому гармонійному власних значень:
де — невелика додатна стала.
Якщо можливо інтерпретувати як для положення кута, то коваріаційною матрицею для положення кута є , тобто
Сума власних значень , яку в цьому випадку можливо інтерпретувати як узагальнену дисперсію (або «повну невизначеність») положення кута, пов'язана з кутовою мірою Нобла наступним рівнянням:
Алгоритм Ферстнера виявляння кутів
У деяких випадках може бути потрібно обчислювати розташування кута з субпіксельною точністю. Для отримання наближеного розв'язку алгоритм Ферстнера знаходить точку, найближчу до всіх дотичних ліній кута в даному вікні, і є розв'язком методом найменших квадратів. Цей алгоритм спирається на той факт, що для ідеального кута дотичні лінії перетинаються в одній точці.
Рівняння дотичної в пікселі задається як
де — вектор градієнта зображення в .
Точка , найближча до всіх дотичних у вікні , це
Відстань від до дотичних зважується величиною градієнта, що надає більшого значення дотичним, які проходять через пікселі з сильними градієнтами.
Розв'язання для :
визначаються як:
Мінімізувати це рівняння можливо диференціюванням за і прирівнюванням до 0:
Зауважте, що — структурний тензор. Щоби це рівняння мало розв'язок, мусить бути оборотною, що означає, що мусить бути матрицею повного рангу (рангу 2). Таким чином, розв'язок
існує лише там, де у вікні справді є кут.
Методологію виконання автоматичного обирання масштабу () для цього методу визначення положень кутів було представлено Ліндебергом, через мінімізування нормованого залишку
над масштабами. Таким чином, цей метод має здатність автоматично підганяти рівні масштабу для обчислення градієнтів зображення до рівня шуму в даних зображення, обираючи грубіші рівні масштабу для зашумлених даних зображення, й тонші рівні масштабу для майже ідеальних кутоподібних структур.
Примітки:
можливо розглядати як залишок при обчисленні розв'язку методом найменших квадратів: якщо , то похибки не було. цей алгоритм можливо видозмінити, щоби обчислювати центри кругових об'єктів, замінивши дотичні лінії на перпендикуляри.
Багатомасштабовий оператор Гарріса
Обчислення матриці другого моменту (яку іноді також називають структурним тензором) в операторі Гарріса вимагає обчислення похідних зображення в області визначення зображення, а також підсумовування нелінійних комбінацій цих похідних по локальних околах. Оскільки обчислення похідних зазвичай включає етап просторово-масштабового згладжування, операційне визначення оператора Гарріса вимагає двох параметрів масштабу: (i) локального масштабу () для згладжування перед обчисленням похідних зображення, та (ii) масштабу інтегрування () для накопичування нелінійних операцій над операторами похідних до інтегрованого описувача зображення.
Із позначенням первинної яскравості зображення через , нехай позначує масштабопросторове подання , отримане згорткою гауссовим ядром
з параметром локального масштабу :
і нехай та позначують частинні похідні від . Крім того, введімо віконну гауссову функцію з параметром масштабу інтегрування . Тоді багатомасштабову матрицю другого моменту () можливо визначити через
Тоді ми можемо обчислити власні значення подібно до власних значень , й визначити багатомасштабову кутову міру Гарріса () через
Щодо вибору параметра локального масштабу та параметру масштабу інтегрування , ці параметри масштабу зазвичай пов'язано відносним параметром масштабу інтегрування через , де зазвичай обирають з проміжку . Таким чином, ми можемо обчислювати багатомасштабову кутову міру Гарріса на будь-якому масштабі в просторі масштабів, щоб отримувати багатомасштабовий виявляч кутів, що реагує на кутові структури різних розмірів в області визначення зображення.
На практиці цей багатомасштабовий виявляч кутів часто доповнюють кроком обрання масштабу (), де нормований за масштабом оператор Лапласа
обчислюють на кожному масштабі в просторі масштабів, а масштабодопасовані кутові точки з автоматичним вибором масштабу (, «оператор Гарріса — Лапласа», ) обчислюють із точок, які є одночасно:
просторовими максимумами багатомасштабової кутової міри
локальними максимумами або мінімуми за масштабами масштабонормованого оператора Лапласа :
Підхід кривини ізоліній
Один з раніших підходів до виявляння кутів полягає у виявлянні точок, де кривина ізоліній та величина градієнта високі одночасно. Диференціальним способом виявляння таких точок є обчислення перемасштабованої кривини ізоліній (, добутку кривизни ізолінії та величини градієнта у третьому степені)
і виявляння додатних максимумів та від'ємних мінімумів цього диференціального виразу в певному масштабі в масштабопросторовому поданні первинного зображення. Проте основна проблема при обчисленні сутності перемасштабованої кривини ізоліній в одному масштабі полягає в тому, що вона може бути чутливою до шуму та вибору рівня масштабу. Кращий метод — обчислювати -нормовану перемасштабовану кривину ізоліній
з , і виявляти знакові масштабопросторові екстремуми цього виразу, тобто точки та масштаби, що є додатними максимумами та від'ємними мінімумами відносно як простору, так і масштабу,