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

ПРЕОБРАЗОВАНИЕ КЛАСТЕРИЗАЦИИ ГЕНЕРАЛЬНОГО МНОЖЕСТВА ТОЧЕК ПРОСТРАНСТВЕННОЙ СЦЕНЫ 1

2

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

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

Описание проблемы и постановки задачи

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

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

Рис.1. Генеральное множество точек изображения пирамиды

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

Описанная выше процедура является кусочно-ломанной аппроксимацией поверхности сложной формы плоскими участками. В работе [2] предложен метод реализации такой аппроксимации, основанный на вычислении трехмерного градиента точечной сцены по результатам её фильтрации. Фильтр содержит трехмерное окно с элементами и при своем перемещении в пределах анализируемой сцены вычисляет компоненты и градиента яркости в каждом её пикселе (вокселе). Вектор градиента к плоскости имеет компоненты и . Поэтому компоненты вектора градиента определяют направление плоского участка поверхности объекта в каждой окрестности точечной сцены. Если окно фильтра движется в направлении, при котором вектор градиента сохраняет свои параметры , то этот вектор располагается в плоскости . В данной работе рассматривается преобразование КТМ (кластеризации точек множества) генерального множества точек трехмерной сцены. Оно позволяет разбить генеральное множество точечной сцены на подмножества по типу поверхности, на которой располагаются точки подмножества . Преобразование КТМ сегментирует точечную сцену так же, как и рассмотренный выше градиентный фильтр, но за счет кватернионной модели сцены реализуется проще, отсутствует эффект сглаживания на стыке между выделенными плоскостями и попутно является основой для получения аналитического описания визуализированной сцены.

Кватернионная модель точечной сцены

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

Мерой схожести векторов в кватернионном пространстве служит их скалярное произведение, являющееся разновидностью клиффордова произведения векторов [3]:

. (1)

Реальная часть этого произведения есть скалярное произведение векторов и в пространстве . В нормированном виде оно равно косинусу угла между векторами. Гиперкомплексная часть (1) представляет собой векторное произведение перемножаемых векторов, взятое с обратным знаком (рис.2):

. (2)

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

Рис.2 Геометрическая интерпретация скалярного произведения кватернионов и

Преобразование КТМ

В качестве общего информативного признака подмножеств , , на которые разбивается генеральное множество , примем степень взаимной близости значений нормалей к локальным плоскостям, образованными тремя, не лежащими на одной прямой, точками этого подмножества (рис. 3).

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

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

Рис. 4. Результат кластеризации сцены, представленной на рис. 1

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

Аналитическое представление преобразования КТМ

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

, , .

Рис. 5. Формирование нормали к плоскости, проходящей через точки и

В отличие от векторов, задаваемых исходными точками, разностные векторы , и являются компланарными.

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

, (3)

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

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

2.  екторная алгебра. М.: Мир, 1979

3.  Zucker S. W., Hummel R. A. Three Dimensional Enqe Operator, Intell, PAMI-3, N.3, pp.324-331, 1981.