Выделение углов — это подход, применяемый в системах компьютерного зрения для извлечения определённых типов признаков и понимания содержимого изображения. Выделение углов часто используется в датчиках движения, при регистрации изображений, видеотрекинге, для создания мозаичных изображений, для , трёхмерной реконструкции и для распознавания объектов. Выделение углов пересекается с темой распознавание точек интереса.

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

Точка интереса — это точка на изображении, имеющая чётко определённое положение и поддающаяся надёжному обнаруженнию. Это означает, что точка интереса может быть углом, но также может быть, например, изолированной точкой локального максимума или минимума интенсивности, концом линии или точкой на кривой, где кривизна локально максимальна.

На практике, большинство так называемых методов выделения углов, на самом деле, выявляют точки интереса, и, фактически, термины «угол» и «точка интереса» используются в литературе более или менее как взаимозаменяемые. Как следствие, если нужно выделить только углы, необходимо провести локальный анализ, какие из точек интереса действительно являются углами. Примерами детекторов краёв, которые могут быть использованы с последующим выявлением углов являются и набор масок Фрея – Чена.

В литературе термины «угол», «точка интереса» и «признак» используются как взаимозаменяемые, что вносит путаницу. В частности, имеются несколько детекторов пятен, которые можно назвать «операторами точек интереса», но иногда их ошибочно называют «детекторами углов». Кроме того, существует понятие «выделение гребней» для обнаружения вытянутых объектов.

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

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

Простой подход к выделению углов на изображениях заключается в использовании корреляции, но он очень затратен с вычислительной точки зрения и неоптимален. Часто используется альтернативный подход, основанный на методе, предложенном Харрисом и Стивенсом (см. ниже), который, в свою очередь, является улучшением метода Моравека.

Алгоритм Моравека выделения углов Это один из самых ранних алгоритмов выделения углов, который определяет угол как точку с низким самоподобием . Алгоритм проверяет каждый пиксель изображения на наличие угла, проверяя, насколько окрестность изображения (квадратное окно 3х3, 5х5 или 7х7 пикселей), центрированная в пикселе, похожа на соседние окрестности, в значительной мере перекрывающиеся (со сдвигом на один пиксель по восьми направлениям – горизонтально/вертикально и по диагонали). Подобие измеряется путём суммирования квадратов разностей (СКР) между соответствующими пикселями двух окрестностей изображения. Чем меньше число, тем выше подобие.

Если пиксель находится в области равномерной интенсивности, то соседние окрестности будут выглядеть похожими. Если пиксель находится на краю, то соседние окрестности в направлении, перпендикулярном краю, будут выглядеть совершенно по-разному, но соседние окрестности в направлении, параллельном краю, приведут лишь к небольшому изменению. Если пиксель находится на элементе с вариациями во всех направлениях, то ни одна из соседних окрестностей не будет выглядеть похожей.

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

Если значение силы угла вычисляется для всех местоположений, то его локальный максимум в определённой точке свидетельствует о наличии там точки интереса.

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

Алгоритмы выделения углов Харриса — Стивенса / Ши — Томаси

Харрис и Стивенс улучшили детектор углов Моравека, рассматривая дифференциальную оценку угла по отношению к направлению непосредственно, вместо использования сдвинутых окрестностей. (Эту оценку угла часто называют автокорреляционной, поскольку этот термин используется в том документе, в котором этот детектор описан. Однако с математической точки зрения используется метод суммы квадратов разностей.)

, будем считать, что используются 2-мерные изображения в оттенках серого. Пусть это изображение будет задано функцией . Рассмотрим вопрос о выделении области изображения и сдвига её на . Взвешенную сумму квадратов разностей (СКР) между этими двумя окрестностями обозначим :

может быть аппроксимирована рядом Тейлора. Пусть и будут частными производными от , такими, что

Это приводит к приближению

которое можно записать в матричном виде:

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

Другими словами, мы находим ковариацию частной производной яркости изображения по осям и .

Угловые скобки обозначают усреднение (то есть, суммирование по ), а означает тип окрестности, которая двигается по изображению. Если используется усредняющий фильтр (квадратный), ответ будет анизотропным, а если используется круглое окно (или округлые взвешенные окна, такие, как гауссовские), то ответ будет изотропным.

Угол (или, в общем, точка интереса) характеризуется большим изменением во всех направлениях вектора . На основе анализа собственных значений эта характеристика может быть выражена следующим образом: должна иметь два «больших» собственных значения для точек интереса. На основании величины собственных значений можно сделать следующие выводы на основе этих аргументов: Если и , то этот пиксель не имеет признака «точка интереса». Если и имеет некоторое большое положительное значение, то обнаружен край. Если и имеют большие положительные значения, то угол найден.

Харрис и Стивенс отметили, что точное определение собственных значений вычислительно затратно, так как требует вычисления квадратного корня, и предложили вместо этого функцию

где является настраиваемым параметром чувствительности.

Таким образом, алгоритм не должен на самом деле вычислять спектральное разложение матрицы матрицы , а вместо этого достаточно вычислить определитель и след матрицы , чтобы найти углы или, точнее, точки интереса.

Детектор углов Ши — Томаси вычисляет напрямую , поскольку при определённых допущениях углы более стабильны для отслеживания. Обратите внимание, что его также иногда называют детектором углов Канаде — Томаси.

Значение должно быть определено эмпирически и в литературе были представлены как возможные значения в диапазоне 0,04–0,15.

Можно избежать установку параметра , если использовать меру угла Нобла , которая вычисляет среднее гармоническое собственных значений:

где — маленькая положительная константа.

Если может быть интерпретирована как для позиции угла, ковариационная матрица для позиции угла равна , то есть

Сумма собственных значений матрицы , которая в этом случае может быть интерпретирована как (или «полная неопределённость») позиции угла, связана с мерой угла Нобла

Детектор углов Фёрстнера

В некоторых случаях может потребоваться определить положение угла с субпиксельной точностью. Для получения приближённого решения алгоритм Фёрстнера находит точку, наиболее близкую ко всем касательным линиям угла в заданном окне, и является решением методом наименьших квадратов. Алгоритм основан на том факте, что для идеального угла касательные линии пересекаются в одной точке.

Уравнение касательной линии в пикселе задается как:

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

Точка , наиболее близкая ко всем касательным линиям в окне определяется как:

Расстояние от до касательных линий взвешивается по величине градиента, тем самым придавая большее значение касательным, проходящим через пиксели с сильными градиентами.

Решение для :

определяется как:

Минимизация этого выражения может быть осуществлена путём дифференцирования по и приравнивания результата к 0:

Обратите внимание, что является структурным тензором. Чтобы уравнение имело решение, должна быть обратимой, что означает, что должна иметь полный ранг (ранг 2). Таким образом, решение

существует только там, где в окне действительно присутствует угол.

Методология автоматического выбора масштаба для этого метода локализации углов была представлена Линдебергом путём минимизации нормализованного остатка

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

Обратите внимание: можно рассматривать как остаток при вычислении решения методом наименьших квадратов: если , то ошибки не было. Этот алгоритм можно модифицировать для вычисления центров круговых объектов, заменив касательные линии на нормали.

Масштабируемый оператор Харриса

Вычисление матрицы второго момента (иногда также называют структурным тензором матрицы в операторе Харриса, требует вычисления производных изображения в области изображения, а также суммы нелинейных комбинаций этих производных по локальным окрестностям. Так как вычисление производных обычно включает этап сглаживания масштабного пространства, определение оператора требует двух параметров масштабирования: (i) локальный масштаб для сглаживания до вычисления производных изображения и (ii) интеграционный масштаб для накопления нелинейных операций по производным операторов в единый дескриптор изображения.

Если обозначает интенсивность оригинального изображения, пусть обозначает представление масштабного пространства , полученное путём свёртки с гауссовым ядром

с локальным параметром масштабирования :

и пусть и обозначают частные производные от . Кроме того, введём гауссовскую весовую функцию с интеграционным параметром масштабирования . Тогда, масштабная матрица второго момента может быть определена как

Теперь мы можем вычислить собственные значения таким же образом, как и для и определить масштабируемую меру углов Харриса

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

На практике этот масштабируемый детектор углов часто дополняется шагом выбора масштабирования, где масштаб-нормированный оператор Лапласа

рассчитывается в каждом масштабе в масштабном пространстве. Затем угловые точки, адаптированные к масштабу с автоматическим выбором масштаба («оператор Харриса-Лапласа») определяются из точек, которые одновременно являются:

пространственными максимумами многомасштабной меры углов

локальными максимумами или минимумами оператора Лапласа, нормализованного по масштабу, по всем масштабам :

Подход на основе кривизны изолиний

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