Исследование и разработка методов нефотореалистичной визуализации для реализации графической библиотеки реального времени Часть 3

Методы выделения границ

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

Вполне естественно, что зашумленность измерений яркости ограничивает возможность выделить информацию о краях. Мы обнаруживаем противоречие между чувствительностью и точностью, и приходим к выводу, что короткие края должны обладать большей контрастностью, чем длинные, чтобы их можно было распознать. Выделение краев можно рассматривать как дополнение к сегментации изображения, поскольку края можно использовать для разбиения изображений на области, соответствующие различным поверхностям [7].

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

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

• изменения глубины;
• изменения ориентации поверхностей;
• изменения в свойствах материала;
• различие в освещении сцены.

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

Существует множество подходов к выделению границ, но практически все можно разделить на две категории: методы, основанные на поиске максимумов, и методы, основанные на поиске нулей. Методы, основанные на поиске максимумов, выделяют границы с помощью вычисления «силы края», обычно выражения первой производной, такого как величина градиента, и затем поиска локальных максимумов силы края, используя предполагаемое направление границы, обычно перпендикуляр к вектору градиента. Методы, основанные на поиске нулей, ищут пересечения оси абсцисс выражения второй производной, обычно нули Лапласиана или нули нелинейного дифференциального выражения, как будет описано далее.

Описанные далее методы выделения границ отличаются применяемыми фильтрами сглаживания и способами, как считается сила края. Хотя многие методы выделения границ основываются на вычислении градиента изображения, они отличаются типами фильтров, применяемых для вычисления градиентов в x- и y-направлении.

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

Рисунок 13. Выбор окрестности элемента для обработки

Одной из центральных задач в обработке изображений является построение пространственного фильтра. Фильтр позволяет усилить или ослабить компоненты различной частоты. Пространственный фильтр – процесс, который способен выделить (подчеркнуть) компоненты определенной частоты. Двумерный фильтр устроен следующим образом. Берется матрица размером 3х3, 5х5, 7х7 и т.д. и на ней определяется некоторая функция. Упомянутая матрица называется окном или апертурой, а заданная на нем функция – весовой или функцией окна. Каждому элементу окна соответствует число, называемое весовым множителем. Совокупность всех весовых множителей и составляет весовую функцию. Нечетные размеры апертуры объясняются однозначностью определения центрального элемента. Фильтрация осуществляется перемещением окна (апертуры) фильтра по изображению. В каждом положении апертуры выполняются однотипные действия, которые определяют так называемый отклик фильтра [13]. Весовая функция в процессе перемещения остается неизменной. В каждом положении окна происходит операция свертки – линейная комбинация значений элементов изображения:

,            (13)

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

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

Метод Лапласса

Метод выделения края по Лапласу осуществляет домножение каждого элемента двумерной апертуры 3х3 на соответствующий элемент так называемой матрицы Лапласа. Дискретный лапласиан определяется как сумма вторых производных и вычисляется как сумма перепадов на соседях центрального пиксела. Для одномерных(14), двухмерных(15-16) и трёхмерных(17) сигналов дискретный лапласиан можно задать как свёртку со следующими ядрами:

(14)

(15)

или с диагоналями:

(16)

для первой плоскости = ;         (17)

для второй ; для третьей

Эти ядра выводятся с помощью дискретных частных производных.

После перемножения все полученные значения элементов суммируются, при необходимости повышается порог яркости сложением, например, с числом 100, и результат помещается в центр апертуры [4]. Затем рабочее окно сдвигается на один элемент вправо (далее – слева направо и сверху вниз). Как видно из описания, метод Лапласа не зависит от направления краев, и на итоговом изображении будут все направления границ.

Метод Собеля

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

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

Математически, градиент функции двух переменных для каждой точки изображения (которой и является функция яркости) — двумерный вектор, компонентами которого являются производные яркости изображения по горизонтали и вертикали. В каждой точке изображения градиентный вектор ориентирован в направлении наибольшего увеличения яркости, а его длина соответствует величине изменения яркости. Это означает, что результатом оператора Собеля в точке области постоянной яркости будет нулевой вектор, а в точке, лежащей на границе областей различной яркости — вектор, пересекающий границу в направлении увеличения яркости [10].

Строго говоря, оператор использует ядра 3×3, с которыми свёртывают исходное изображение для вычисления приближенных значений производных по горизонтали и по вертикали. Пусть A исходное изображение, а Gx и Gy — два изображения, где каждая точка содержит приближенные производные по x и по y. Они вычисляются следующим образом:

(18)
(19)

где * обозначает двумерную операцию свертки.

Координата x здесь возрастает «направо», а y — «вниз». В каждой точке изображения приближенное значение величины градиента можно вычислить, используя полученные приближенные значения производных:

(20)

Используя эту информацию, мы также можем вычислить направление градиента:

(21)

где, к примеру, угол равен нулю для вертикальной границы, у которой тёмная сторона слева.

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