2.5.1. Проблема выделения и группирования линейных признаков в настоящее время
В настоящее время существует множество наборов детекторов и дескрипторов, которые позволяют решить проблему описания объектов и сравнения изображений. Недостатки детектора Кенни, известного алгоритма выделения контуров в сочетании с преобразованием Хафа для получения прямых отрезков, обсуждались в существующем исследовании [24]. Алгоритм Хафа строит прямую линию на изображении в параметрическом пространстве без учета пространственной связи между точками. В результате такие детекторы часто дают фрагментацию не совсем ровных прямых кромок на короткие сегменты, что практически разрушает геометрическую составляющую объекта.
Чтобы получить четкие отрезки прямых линий в случае не совсем прямых линий на изображении, предлагается использовать пространственно ориентированные фильтры с последующим формированием профиля градиента в направлении, обеспечивающем максимум на выходе фильтра. В этом случае становится возможным выделение пересечений прямолинейных сегментов и их соединений, что не позволяет комбинация Кенни-Хафа.
Координаты отрезков в сочетании с углами ориентации и выходными значениями фильтра представляют самый низкий уровень описания для объектов [25]. Важным свойством каждого сегмента является наличие других пересекающих его линий, и эти линии также упорядочены по выходному сигналу фильтра.
Автор работы [26] предложил другой алгоритм получения отрезков прямых, основанный на выравнивании точек путем объединения пикселей в соответствие с локальными ориентациями вектора градиента и позволяющий контролировать обнаружение ложных границ. Алгоритм не дает фрагментации линий и обладает адаптивными свойствами при выборе границ разной длины. Однако на краях выделенных прямых сегментов границ наблюдается большой разброс локальных ориентаций, такие области не попадают в опорную линию и теряются. В результате алгоритм не позволяет выделить точки пересечения отрезков прямых.
Идея использования прямолинейных сегментов и геометрических соотношений между ними обсуждалась в исследовании [27]. Авторы использовали термин «антипараллелизм для линий», введенный Неватией и Бабу, и рассматривали антипараллельные пары. Такие пары имеют противоположную ориентацию линий, поскольку одна из них образована изменением интенсивности с черного на белый, а другая с белого на черный. Поиск таких парных линий, расположенных достаточно близко друг к другу, позволяет исключить из рассмотрения лишние линии, которые находятся в заданной области.
Группировка линейных сегментов для описания объектов рассмотрена в исследовании [28]. Изображение интерпретировалось как совокупность объектов и геометрических связей между ними. На самом низком уровне точки объединяются в линейные сегменты, которые могут образовывать узкие полосы, соединения, пересечения и кривые. Группировка линейных сегментов основана на некоторых геометрических ограничениях, например: непрерывность, параллельность, симметричность, перекрытие, совпадение и т. д. Чтобы построить связанные структуры из большого набора линейных сегментов, иерархическая система объединения линий и описания объектов разработана с использованием вышеуказанных свойств. В результате получается комбинация соединенных линейных сегментов, которая представляет собой описание объекта в выделенной области изображения. Такое описание представлено в виде графа. Таким образом, задача сравнения и распознавания объектов сводится к сравнению графов для выбранных объектов.
Авторы исследования[29] разработали новый алгоритм, названный кластером совпадающих линий. Он предназначен в основном для распознавания строений и включает в себя проверку ряда соотношений прямолинейных сегментов. В частности, проверяются перекрывающиеся сегменты и их пересечения. Предлагаемый алгоритм не позволяет решить более общие задачи выбора и распознавания объектов. Не ясно, как сгруппировать выбранные сегменты, чтобы сформировать элементы на верхнем уровне описания.
Поиск связанных пар линий проводился путем сравнения углов [25]. Предлагается мера такого отношения, включая взвешенное суммирование признаков. Однако из-за недостаточного количества применяемых ограничений метод дал низкую вероятность совпадений признаков. Другой набор ограничений на линейные отрезки был рассмотрен в исследовании [30]. Связывание прямолинейных сегментов одинаковой длины рассматривается как оригинальный метод группировки и получения структур [16]. Группировка смежных сегментов позволяет получить структуры с заданной сложностью, которая определяется количеством соединенных сегментов.
Другие подходы к группированию основаны на активных контурах, змеях, деревьях и графах [19]. Смежные области для этого исследования включают выделение значимых кривых на изображениях, формирование масштабно-инвариантных дескрипторов, обнаружение объектов, состоящих из отдельных частей, выбор текстурных особенностей для локальных областей и векторное представление формы объектов.
2.5.2. Алгоритмы Кэнни и Хафа для выделения прямолинейных сегментов кромок
Детектор Кэнни. Джон Кэнни описал алгоритмы обнаружения границ, которые с тех пор стали одним из наиболее широко используемых. Кэнни исходил из трех критериев, которым должен удовлетворять граничный детектор:
- хорошее обнаружение (Кэнни интерпретировал это свойство как увеличение отношения сигнал / шум);
- хорошая локализация (правильное позиционирование границы);
- единственный ответ на одну границу.
Из этих критериев была построена целевая функция весомости ошибок, минимизация которой является «оптимальным» линейным оператором для свертки с изображением.
Алгоритм Canny Boundary Detection не ограничивается вычислением градиента сглаженного изображения. В контуре границы остаются только максимальные точки градиента изображения, и не удаляются максимальные точки, лежащие рядом с границей. Он также использует информацию о направлении границы, чтобы убрать точки возле границы и не нарушать саму границу вблизи локальных максимумов градиента. Затем, используя два порога, слабые границы удаляются. Фрагмент границы рассматривается как единое целое. Если значение градиента где-то на прослеживаемом фрагменте превышает верхний порог, то этот фрагмент также остается «допустимой» границей в тех местах, где значение градиента падает ниже этого порога до тех пор, пока оно не упадет ниже нижнего порога. Если на всем фрагменте нет ни одной точки со значением, превышающим верхний порог, то она удаляется. Такой гистерезис уменьшает количество разрывов в выходных пределах. Включение шумоподавления в алгоритм Канни, с одной стороны, повышает стабильность результатов, а, с другой стороны, увеличивает вычислительные затраты и приводит к искажению и даже потере деталей границ. Так, например, такой алгоритм округляет углы объектов и разрушает границы в точках соединения. Далее рассмотрим работу алгоритма подробнее:
Чтобы уменьшить влияние шумовой составляющей, изображение предварительно сглаживается фильтром Гаусса. Затем, чтобы выделить контуры границы, вертикальный и горизонтальный градиент вычисляется с использованием вертикальной и горизонтальной маски Собеля. Величина и направление градиента в каждой точке определяются по формулам :
Полученные значения локальных направлений градиентов округляются до одного из углов от 0 с шагом в 45 градусов. После вычисления градиента на границе остаются только максимальные точки градиента изображения. Информация о направлении границы используется для удаления точек точно возле границы, избегая разрыва самой границы вблизи локальных максимумов градиента. Затем, используя два порога, слабые точки границы удаляются. Фрагмент границы рассматривается как единое целое. Если значение градиента в любой точке отслеживаемого фрагмента превышает верхний порог, тогда этот фрагмент также остается «приемлемой» границей в тех местах, где значение градиента падает ниже этого порога до тех пор, пока оно не опустится ниже нижнего порога. Если на всем фрагменте нет ни одной точки со значением выше верхнего порога, то данный фрагмент удаляется. Этот метод позволяет уменьшить количество разрывов в выходных границах. Включение шумоподавления в алгоритм повышает стабильность результатов, но приводит к искажению и потере «деталей» границ.
К достоинствам метода относятся низкая чувствительность к шуму и ориентация границ областей, тот факт, что он четко очерчивает контур и позволяет идентифицировать внутренние контуры объекта. Кроме того, он устраняет ошибочное обнаружение контура там, где нет объектов.
Недостатками этого способа являются скругление углов объектов и разрушение границ в местах соединения, что приводит к изменению параметров контура.
Сегодня детектор Кэнни является одним из лучших универсальных граничных детекторов и широко используется на практике.
Преобразование Хафа. Алгоритм Хафа был придуман американским ученым П. Хафом (R. Hough) в 1962 г. для аппроксимации набора точек на бинарном изображении прямыми линиями [19]. Он основан на использовании пространства параметров, в котором выполняется поиск прямых. Наиболее распространенные параметрические представления линий:
С помощью уравнения (2.3) невозможно описать вертикальную линию, поскольку параметр k стремится к бесконечности. Классическое преобразование Хафа использует отдельные параметры уравнения (2.4). Метод, разработанный Хаффом, используется для преобразования линий из декартовой системы координат в набор точек в полярной системе координат. Декартовые и полярные координаты точки связаны следующими формулами:
На рисунке 2.3 параметризация прямой линии (на рисунке 2.3 a — прямая линия в декартовой системе координат, на рисунке 2.3 b — отклик точек прямой линии в полярной системе координат).
Рисунок. 2.3 — Параметризация прямой
C помощью этого преобразования линия, определенная в декартовой системе координат, преобразуется в точку в полярной системе. Семейство линий, проходящих через одну точку, переводится в набор точек. Например, преобразование Хафа, примененное к семействам линий, проходящих через три коллинеарные точки, приводит к комбинации трех параметрических кривых в системе. Эти три кривые будут пересекаться в одной точке с начальными координатами точки, если они лежат на одной прямой в декартовых координатах(x, y).
Результаты преобразования аккумулируются. Значения в элементах аккумулятора — это число параметрических кривых, которые проходят через точку. Максимальное значение в ячейке соответствует наибольшему количеству точек, лежащих на одной прямой. По координатам этих максимумов в параметрическом пространстве можно определить угол и расстояние до линии на входном изображении.
Преобразование Хафа эффективно только при значительном количестве «попаданий» параметрических кривых в соответствующий элемент; только тогда можно с уверенностью определить линию, пренебрегав фоновым шумом. Следовательно, длина прямой не должна быть очень маленькой, в противном случае некоторые значения попадут в соседние шумовые элементы, уменьшая видимость желаемого элемента. Эффективность алгоритма во многом определяется качеством входных данных. Использовать преобразование Хафа на изображениях, которые сильно зашумлены, сложно, потому что это приводит к фрагментации прямой. На рисунке. 2.4, а — тестовое изображение с шумом, оно состоит из 4 строк квадратных объектов, слева –показано отношение сигнал / шум (с / ш) в каждой строке. На картинке. 2.4, б — результат использования детектора кромок Кэнни с дрожащими линиями, это обусловленно влиянием шума на выходные данные детектора. На картинке. 2,4, в — результат применения алгоритма Хафа. Из рисунка видно, что контуры Кэнни были фрагментированы на несвязанные короткие отрезки.
Рисунок. 2.4 – Применение алгоритма определения границ детектором Кэнни и преобразованием Хафа
2.5.3. Применение метода объединения пикселей (детектор Рендела) для выделения прямолинейных сегментов кромок
Детектор предназначен для выделения прямолинейных изменений яркости на изображениях на основе анализа градиентов [21].
В первую очередь рассчитываются вертикальные и горизонтальные градиенты. По формуле (2.1) рассчитывается значение градиента в каждой точке, а локальное направление в каждой точке — с помощью формулы (2.2).
На рисунке 2.5, а — является частью изображения с прямыми границами. На рисунке 2.5, б — изображение градиента, на котором линии показывают локальные ориентации. Из рисунка видно, что локальные ориентации в местах изменений яркости имеют устойчивые направления, где нет изменений яркости, изображение имеет характер шума, локальные ориентации в каждой точке градиента имеют случайное направление.
Следующем этапом формируется прямоугольная зона поддержки линии. (рис. 2.5, в). В область поддержки линии попадают только те точки градиента, которые соответствуют следующим условиям:
- Проходят через порог градиента.
- Иметь допустимый диапазон ориентаций.
Линия — это область градиента, в которой по меньшей мере шесть точек градиента попадают в область поддержки линии. На рисунке 2.5, г показана область поддержки линии, которая включает в себя восемь точек градиента.
На картинке. 2.6, а — тестовое изображение с шумом, состоящее из 4 строк объектов, справа — отношения сигнал / шум указан в каждом ряду соответственно. На картинке. 2.6, б — результат использования алгоритма Рендела.
Рисунок. 2.5 – Процесс обнаружения границы
Рисунок. 2.6 –Обнаружение границ с помощью детектора Рендела
В связи с тем, что на локальные направления шумы могут оказывать значительное влияние, получается много точек градиента, которые проходят по размеру области линии поддержки, но не проходят в ориентации. В результате границы при низких отношениях сигнала к шуму либо нарушаются, либо могут остаться не обнаруженными.
ГЛАВА 3. ВЫДЕЛЕНИЕ ПРЯМОЛИНЕЙНЫХ СЕГМЕНТОВ КРОМОК НА РАДИОЛОКАЦИОННЫХ ИЗОБРАЖЕНИЯХ.
- Описание реализации предлагаемого метода
Структурная схема предлагаемого алгоритма выделения прямолинейных сегментов кромок на радиолокационных изображениях изображена на рисунке 3.1.
Рисунок 3.1 – Структурная схема предлагаемого алгоритма
Первым делом происходит загрузка в программу оригинального изображения местности и преобразование его в полутоновое (см рис 3.2).
На рисунке 3.3 можно увидеть изображение после обработки фильтром гаусса
Рисунок 3.3 – Сглаженное изображение
Следующим шагом производится выделение границ. Сперва необходимо выделить точки границ. Для этого используются дифференцирующие операторы первого порядка. После применения таких операторов все точки изображения преобразуются в значения производных данной точки – градиент. Точки с ненулевым значением производной считаются точками границы. Двумерные производные содержат в себе информацию как об интенсивности границ, так и об их ориентации. Оператор дифференцирования двумерного изображения в определённой точке с координатами (x, y) — это вектор (3.4)по определению.
В случае дискретного сигнала, предполагается использование дискретного приближения. Стандартное решение, широко используемое на практике, — это вычисление градиента с использованием оператора Собела или Прювитта размером 3х3. При использовании оператора, имеющего размеры 2X2 (оператор Робертса), получаются ненадежные результаты из-за высокой чувствительности к шумовой составляющей. Более крупные операторы (5X5) делают линии толще, в результате чего разрешающая способность теряется, но так как они имеют большую устойчивость к шуму и естественному разрыву границ их использование также может быть оправдано. В данной работе применяется оператор Прювита, представляющий из себя окно фильтра 3х3. С помощью этого оператора вычисляется первая производная и при этом учитываются направления выделяемых линий. Всего используется 8 окон с шагом в 45 градусов, их направления 0, 45, 90 и т.д.
Результатом процедуры дифференцирования становятся 8 градиентных изображений, показанных на рисунке 3.4, на которых содержатся линии в местах резких изменений яркости. Получившиеся линии различаются интенсивностями, что связанно с различными значениями градиента.
Рисунок 3.4 – Градиентное изображение
Следующим шагом для выделения линий кромок производится свёртка градиентного изображения(фильтрация), с помощью фиксированного банка отдельно созданных фильтров. Данные фильтры пространственно ориентированны и настроены в скользящем, локальном окне, и каждый из них имеет собственное направление. Шаг поворота данных фильтров 3 градуса. Начальный фильтр имеет горизонтальное направление 0 градусов он выглядит так, как показано на рисунке 3.5.
Рисунок 3.5 – Начальный вид фильтра
Далее с помощью поворота с определённым, выше указанным шагом,данного фильтра в начальном виде, получаются все остальные фильтры. На рисунке 3.6 показан банк разработанных фильтров, применяемых при выполнении поставленной задачи. Всего имеется 60 фильтров в наборе, каждый из них повёрнут относительно предыдущего на 3 градуса.
Рисунок 3.6 – Банк фильтров
Применяя последовательную свёртку градиентного изображения с окнами фильтров, производим фильтрацию выделяющихся линий по всем направлениям. Все градиентные изображения фильтруются в своём секторе. Выбор сектора зависит от направления взятия градиента (см рис 3.7).
Рисунок 3.7 – Выбор секторов для фильтрации
Таким образом, к примеру, градиентg1(i, j)проходит обработку в угловом диапазоне от 23 градусов до 338 градусов (направление отсчёта по часовой стрелке), соответствующем окнам фильтров, сконфигурированному в угловом диапазоне от 23 градусов до -22 градусов. Градиентg6(i, j)проходит обработку в угловом диапазоне от 248 градусов до 203 градусов, соответствующих оконному фильтру, сконфигурированному в диапазоне углов от-113 градусов до -158 градусов . Градиент обрабатывается в диапазоне углов, соответствующих оконному фильтру, сконфигурированному в диапазоне углов. Фильтрацию осуществляют по формуле (3.6):
(3.6)
где k – номер градиентного изображения, a – угол направления фильтра.
При каждом угле фильтрации мы ищем максимальное значение в отфильтрованном изображении и заносим данное значение, и угол поворота в массив.
Следующим шагом будет нахождение максимума в массиве значений m. Далее извлекаем соответствующий данному максимуму угол из массива углов, следствием этого будет получение предварительной оценки направления границы, которая дала на выходе фильтра самый сильный отклик.
После этого проверяется поровое условиеTF> (Mmax)•tF, где Mmax – граница значения, которое накопит фильтр при выполнении условия, что граница включает единичный скачок и имеет длину не меньшую длины фильтра.
Следующий шаг – нахождение значения Mmax. На рисунке 3.8 показан вертикальный перепад яркости.
Рисунок 3.8 – Вертикальный перепад яркости.
Идеальная вертикальная граница представляет из себя резкий перепад по яркости:
График данного перепада показан на рисунке 3.9.
Рисунок 3.9 – График перепада яркости
На рисунке 3.10 показан график перепада после сглаживания по 3.3.
Рисунок 3.10 – Сглаженный перепад
На следующем рисунке 3.11 показан график перепада после дифференцирования с помощью 3.5
Рисунок 3.11 – Дифференцированный перепад
Фильтр, который производит свёртку по 3.6 может накопить Mmax = 1,64•17=27,9при условии размера маски [17х17].
Следующая задача в данном алгоритме выделить профиль градиента и получить оценку координат начальных и конечных точек линий кромок. Фильтр помещается под необходимым углом и обрабатывается соответствующий градиент. Находятся координаты максимума – строки и столбцы и . Берётся профиль градиента , под углом и идущий через координаты и . Берем профиль в соседней верхней и нижней строке с координатами +1 и –1 соответственно. Чтобы получить профиль, используется изображение включающее прямые линии, проходящие через координаты , +1, -1 под углом . После этого изображение с прямыми линиями сворачивается с градиентным, и мы получаем профиль в три строки.
Чтобы оценить начальную и конечную точки, максимальный коэффициент оценивается по общему градиенту в пределах максимальной оценочной области, поскольку на изображении, подвергнутом фильтрации, координата максимума может не соответствовать координате максимума на градиенте. Локальное максимальное значение ищется в пределах максимальной области оценки.
Выбирается область оценки максимума, равная стороне фильтрующего окна, в этом конкретном случае размер стороны окна 17, следовательно максимальная область оценки также равна 17. От значения локального максимума рассчитывается пороговое значение по градиенту:TG = MG•tG, где tG — значение порогового коэффициента 1>tG>0 .Пока импульс больше значения порога, осуществляется отсчёт от точки до начальной точки и вправо до конечной точки . Весь процесс можно увидеть на рисунке 3.12.
Важно заметить, что величина суммарного градиента в точке может оказаться ниже порога TG (см рис 3.13). В таком случае отсчёт начинается от в сторону до момента, пока не будет превышен уровень порога TG, та точка, в которой фиксируется момент превышения порога, становиться точкой начала . А точка, в которой превышение порога заканчивается, фиксируется как точка конца .
Рисунок 3.12 – Оценка точек начала и конца
Рисунок 3.13 – Провал градиента
Следующий шаг – это селекция границ по направлению. В процессе определения угла может появиться угловая ошибка из-за: 1) Конечного размера фильтрующей маски. 2) Дискретности настроек угла наклона фильтра. На рисунке 3.10 изображено градиентное представление наклонной границы, вблизи окна граничного фильтра, он представляет собой прямую линию, и максимум будет находиться под углом 0 градусов. Следствием этого будет неточность определения угла ошибки.
Рисунок 3.14 – Угол ошибки
Оценка угловой погрешности реализовывается с помощью корректировки области выбора профиля градиента кромки в пределах +6 градусов и -6 градусов, считая от угла фильтра, при этом используется шаг 0.25 градусов. На каждом шагу корректировки фиксируется параметр длины линии lвдоль порога TGи сумма градиента кромки по всей длинеl. На рисунке 3.15 изображены графики профилей по углам 6, 3, 0, -3, -6. На рисунке 3.16 на верхнем графике показана зависимость расчетной длины кромкиl от угла поворота ar.
Накопление градиента происходит суммированием на каждом шаге поворота ar значения кромки по всей расчетной длине границы, следовательно угловая ошибка будет соответственна углу, при котором значение накопленного градиента будет наибольшей.
Угол оценённый для кромки, изображённой на рисунке 3.14, показан на рисунке 3.16 на нижнем графике.
Оценённый угол кромки с поправкой:
Получаются координаты начальной и конечной точек линии под углом А и рассчитываются координаты вдоль осиy.
Рисунок 3.15 – Графики подстройки профиля
Рисунок 3.16 Селекция кромки по направлению
Следующим шагом необходимо удалить сегмент кромки на градиентах. Это необходимо для того, чтобы при последующем выполнении алгоритма координаты максимума снова не указали на неё. По этому формируется изображение единиц D(i, j) и нулей в удаляющей области. На градиенте анализируется ширина выделенной кромки на всех дискретных участках её длины l начиная от заканчивая . И учитывая порог
TGD = MG•tGD определяем координаты , .
Изображение с предполагаемой удаляемой кромкой попиксельно свёртывается с градиентным изображением, на котором был зафиксирован максимум, и с k+1и k-1градиентами. На других градиентных изображениях выделяемая кромка сильно ослабляется.
На рисунке 3.17 показано изображение с выделенной кромкой. А на рисунке 3.18 показан градиент с удалённой выделенной кромкой.
Рисунок 3.17 – Выделенный фрагмент.
Рисунок 3.18 – Выделенная кромка удалена.
Далее весь алгоритм повторяется для второй кромки и для последующих. Последовательность обнаружения и выделения зависит от интенсивности кромок. В первую очередь алгоритм выделяет самые интенсивные и большие по длине кромки.
За счёт использования накопления профилей градиентов в три строки и фильтра, который оценивает положение и угол кромок, алгоритм может работать даже при небольших отношения с/ш.