Технические науки / 11. Робототехника

К.т.н. Колдаев В.Д.

Национальный исследовательский университет МИЭТ, Россия

Сегментация изображений с использованием алгоритма иерархического тайлинга полигонов

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

Алгоритм иерархического деления полигонов на тайлы позволяет производить разбиение отображаемого пространства, посещая при этом только те участки изображения, которые содержат видимые края поверхностей. Участки изображения, в которых видимость определена, больше не обрабатываются алгоритмом, и информация о них остается неизменной вплоть до окончательного формирования кадра. Тайлинг и формирование изображения с разрешением 512×512 требует столько же времени, как и традиционный метод сканирования, но при большем разрешении (4096×4096) алгоритм оказывается на порядок быстрее, делая его удобным для решения таких задач, как сглаживание и линейная фильтрация. Для сложных сцен с большим количеством перекрывающихся полигонов можно комбинировать иерархический тайлинг с другими иерархическими алгоритмами определения видимости, производя отброс невидимой геометрии и в объектном пространстве.

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

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

а

б

_{Рис.1. Матрица локальных весов (а) и накопленных весов (б)}

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

Наиболее простой и распространенный алгоритм тайлинга полигонов – это алгоритм преобразований по линии сканирования или инкрементальное сканирование. На первой стадии алгоритма, линия сканирования, пересекая периметр полигона, определяет два крайних пикселя. Эти два пикселя обозначат прямоугольное пространство внутри полигона, которое далее будет просчитываться попиксельно, позволяя осуществлять инкрементальное обновление оттенка цвета и значение глубины, в случае с Z-буфером. Видимость пикселей можно определить одним из следующих методов: используя Z-буфер, путем сравнения значений глубины, обрабатывая полигоны в порядке от дальнего к ближнему, каждый раз переписывая значения параметров пикселя, либо обрабатывая полигоны в порядке от ближнего к дальнему и обновляя только вакантные пиксели. Алгоритм эффективно использует когерентность изображения при нахождении краев полигонов и просчете параметров пикселей, однако вынужден сканировать пиксели на каждом примитиве, затрачивая время на обработку невидимой геометрии. В идеале, время работы совершенного алгоритма прямо пропорционально сложности видимой геометрии сцены и не зависит от общей сложности сцены и количества невидимых глазу полигонов.

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

Литература

1. Колдаев В.Д. Основы алгоритмизации и программирования: учебное пособие [Текст] / Колдаев В.Д. / Под ред. Л.Г. Гагариной. – М.: ИД «ФОРУМ» – ИНФРА-М, 2006. – 416 с.