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

СРАВНИТЕЛЬНАЯ ЭФФЕКТИВНОСТЬ МЕТОДОВ ТРЕХМЕРНОГО ГРАДИЕНТА И ПРЕОБРАЗОВАНИЕ КЛАСТЕРИЗАЦИИ ДЛЯ ВЫДЕЛЕНИЯ ПЛОСКИХ ФРАГМЕНТОВ, МЕТОДОВ ПОВЕРХНОСТЕЙ 3D ИЗОБРАЖЕНИЙ1

2

2 Марийский государственный технический университет, 424000, Йошкар-Ола,
пл. Ленина 3. Тел. [phone]. E-mail: *****@***mari. ru

Введение

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

Процедура визуализации часто направлена на представление сцены в том виде, в котором она наиболее просто понимается человеком, но одновременно формируется ее математическая модель [1].

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

В технических системах визуализация сцены, формируется с помощью технических датчиках. В таких системах трехмерная сцена формируется по координатам (x,y,z) точки поверхности объектов. Более информативные системы содержат информацию об интенсивности отраженного сигнала от каждой точке сцены.

Метод трехмерного градиента

Один из наиболее простых подходов для сегментации и опи­сания трехмерных структур с помощью координат точек (x, у,z) состоит в разбиении сцены на небольшие плоские «участки» с последующим их объединение в более крупные элементы поверхности в соответствии с некоторым критерием. Этот метод особенно удобен для идентификации многогранных объектов, поверхности которых достаточно гладкие относительно разрешающей способности приемника.

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

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

Градиент трехмерной функции f(x,y,z) в точке (x,y,z) определяется как

(1)

Величина (модуль) градиента равен

. (2)

Для упрощения вычислений величина градиента аппроксимируется абсолютными значениями компонент вектора:

(3)

Значения трехмерного градиента определяется масочным (оконным) 3x3x3 оператором. На рис. 1 приведен такой оператор и показан процесс вычисления компоненты Gx. Такой же оператор, ориентированный вдоль оси у, используется для вычисления Gy и ориентированный вдоль оси Z - для вычисления Gz. Эти операторы дают наилучший (по методу наименьших квадратов) плоский контур (скачок яркости) между двумя областями различной интенсивности в трехмерной окрестности.

Центр оператора перемещается от воксела к вокселу и результатом их действия в любой точке (x,y,z) являются компоненты Gx, Gy и Gz, вектора градиента. Если точки в области имеют одинаковую интенсивность, то рассматриваемый оператор выдает нулевое значение градиента.

Для разбиения сцены на плоские участки применяется основанная на методе трехмерного градиента следующая процедура. Если уравнение плоскости задано в виде ax+by+ cz = 0, то вектор градиента к этой плоскости имеет компоненты Gx = а, Gy =Ь и Gz =с. Поскольку рассмотренные выше масочные операторы дают оптимальный плоский участок в окрестности размерностью 3x3x3, то отсюда следует, что компоненты вектора G определяют направление нормали к этому участку

Рис. 1. Оператор размерностью 3x3x3 для вычисления составляющей градиента Gx [2]

в каждой окрестности, в то время как значения модуле G указывает на резкое изменение интенсивности в пределах плоского участка, т. е. она указывает на наличие границы (контура) изображения в пределах этого участка [2].

Преобразование кластеризации

Еще один из подходов к визуализации трехмерных объектов в трехмерной точечной сцене, использует преобразование кластеризации [5]. Этот метод основан на кватернионом анализе. Все генеральное множество точек, которое лежит на поверхности анализируемого объекта, определяется множеством точек А={av}0,s-1, в котором каждую точку av можно задать своими трехмерными координатами av,x, av,y , av,z в трехмерной декартовой системе координат, или соответствующим кватернионом av = av,xi+ av,yj+ av,z k ; v=0,1,…,s-1 [3,4]. В результате кластеризации это множество разбивается на подмножества точек с одинаковыми или очень близкими свойствами. В качестве общего информативного признака подмножества Аn = {an,m}0,sn-1, n = 0,1…l, -1, элементарной грани Gn выбран вектор нормали к ней [5].

(4)

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

Рис. 2. Вектор нормали к локальному участку плоскости, задаваемому тремя точками, как информационный признак всей плоскости

В результате сегментации генеральное множество А={av}0,s-1 представляется совокупностью подмножеств {Аn}0,l-1 относящихся к l элементарным граням {Сn}0,l-1, изображений объектов в многоградационной сцене.

Трудоемкость вычислений

Метод трехмерного градиента дает возможность четкого разделения границ фона и объекта. Значения трехмерного градиента определяется масочным 3x3x3 оператором [2].

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

Для расчета одной составляющей трехмерного градиента необходимо сделать 27 умножений и 29 сложений, итого 56 действий, а так как таких составляющих три, то для определения градиента одной точки, соответственно, необходимо совершить 168 действий.

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

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

Заключение

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

Список литературы

1.  Введение в контурный анализ и его приложение к обработке изображений и сигналов/Под ред. . – М.: Физматлит, 2002.

2.  Фу К., Гонсалес., Ли К. Робототехника: Пер. с англ.- М.: Мир, 1989,- 624 с.

3.  Комплекснозначные и гиперкомплексные системы в задачах обработки многомерных сигналов/ Под ред. . – М.: ФИЗМАТЛИТ, 2004.

4.  , Хафизов групповых точечных объектов в трехмерном пространстве// Автометрия, 2003. – № 1. – С. 3–18.