Система распознавания трехмерных моделей из облаков точек

(Решетневскце чтения

УДК 004. 932

А. А. Николаев

Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева, Россия, Красноярск

СИСТЕМА РАСПОЗНАВАНИЯ ТРЕХМЕРНЫХ МОДЕЛЕЙ ИЗ ОБЛАКОВ ТОЧЕК

Рассмотрены два метода классификации трехмерных облаков точек путем сравнения их с эталонными моделями.

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

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

В основе деформационных моделей лежит задача соотношения контуров. Эта задача распадается на два направления: разметку - соотношение контура, полученного из среза, и контура, взятого из модели; регистрацию - соотношение контуров, полученных из двух разных срезов [1]. Решение вышеприведенных задач обычно выполняется путем построения структурированного описания контуров и последующего «эластичного» соотношения описаний. Под структуризацией описания понимается поиск в контуре характерных точек, элементарных кривых и других элементов, которые будут сравниваться. «Эластичное» соотношение строится на основе метода деформационных моделей, известного также под названием «геометрические деформированные контуры». Сущность данного метода заключается в том, что контур или его элемент испытывает итерационную деформацию до тех пор, пока не достигнет максимально возможного соответствия с другим контуром или элементом. Изменение поверхности (деформация) происходит исходя из того, что искомый контур испытывает изменения под воздействием двух энергий: внутренней и внешней. На каждом шаге алгоритма отыскивается контур, для которого имеется баланс энергий, т. е. минимальная деформация. Уточнение происходит до тех пор, пока не будет достигнут критерий соответствия искомого и эталонного контуров.

Еще одной методикой сопоставления двух облаков является метод построения поверхностных сплайнов и дальнейший статистический анализ коэффициентов полученных полиномиальных трехмерных функций.

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

симирует хорда, соединяющая две соседние точки. На практике это условие выполняется далеко не всегда. Результат будет более точным, если через заданные точки провести как можно более плавную кривую, без изломов. Тогда значение функции y(x) для значения x = ? можно будет просто считать с графика. Конечно, такой способ интерполирования опирается скорее на интуицию, чем на строгую математику, но, тем не менее, это лучше, чем линейное интерполирование. Особенно хороший результат будет получен в случае применения функциональных шкал, когда кривая зависимости y от x спрямлена.

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

Алгоритм сравнения путем построения деформационных моделей выполняется достаточно долго: для каждой точки распознаваемого облака рассчитывается энергия, с которой в нее будет деформирована каждая точка эталонного облака. Исходное облако составляют n точек, а эталонное - т. Если предположить что n приблизительно равно т, то сложность алгоритма можно оценить, как O(n2). Кроме того, построение деформационной модели - процесс итерационный, требующий некоторого числа шагов - к. Однако к на порядок меньше n, поэтому на временной сложности не отразится. Необходимо учесть и трудоемкость процесса решения уравнения Эйлера, что также потребует ощутимого машинного времени.

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

Библиографические ссылки

1. Gourdon A. Simplication ofirregular surface meshes in 3D medical images // Ayache. 1995. P. 413419.

2. Скороспелов В. А. Сплайны в инженерной геометрии. М. : Машиностроение, 1985.

Информационные системы и технологии

A. A. Nikolaev

Siberian State Aerospace University named after academician M. F. Reshetnev, Russia, Krasnoyarsk

SYSTEM OF RECOGNITION OF THREE-DIMENSIONAL MODELS OF CLOUD POINT

Two methods of classification of three-dimensional point cloud by comparing them with standard models are considered.

© Николаев А. А., 2011

УДК 004.932.2

А. В. Носов, Д. В. Бузаев, А. Г. Зотин

Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева, Россия, Красноярск

ОЦЕНКА ЭФФЕКТИВНОСТИ СОСТАВЛЯЮЩИХ ЦВЕТОВЫХ МОДЕЛЕЙ ПРИ СЕГМЕНТАЦИИ ИЗОБРАЖЕНИЙ ПО ЦВЕТОВЫМ ПРИЗНАКАМ

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

В обработке изображений при распознавании образов одной из самых важных задач является задача обнаружения и локализации объектов интереса [1]. Эта задача очень актуальная, так как точность локализации напрямую влияет на точность распознавания или эффективность дальнейшего анализа. В большинстве случаев, когда объекты интереса имеют определенный цвет, для локализации их используют цветовую сегментацию, суть которой заключается в выделении областей, имеющих цвет объекта интереса. В зависимости от цветовой модели цвет объекта может иметь различные представления в различных цветовых пространствах. Наиболее перспективным является использование цветовых моделей с выраженной яркостной и хроматическими компонентами, примерами таких моделей являются модели HSV, TSL, YCrCb [2].

Цветовая модель HSV - модель, в которой координатами цвета являются цветовой тон (Hue); насыщенность (Saturation); значение цвета (Value).

Цветовая модель TSL схожа с моделью HSV и ее координатами являются цветовой тон (Tint); насыщенность (Saturation); яркость (Lightness).

Цветовая модель YCrCb представляет собой цветовое пространство, координатами которого являются Y - яркость, Cr и Cb - хроматические компоненты.

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

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

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

К = 1 min + К--К-,

max min

где X - i-й элемент выборки; Xmin - нижняя, а Xmax -верхняя граница цветового канала. После нормализации все значения цветовых каналов будут принадлежать интервалу [0, 1].

Вторым этапом является анализ и оценка эффективности цветовых каналов. По нормализованной выборке выбранного нами цветового канала оценивается эталонный вектор m математических ожиданий и среднеквадратическое отклонение с. Если значения выборки распределены по нормальному закону, можно применить правило трех сигм: «Не менее чем с 99,7%-й достоверностью значение нормально распределенной случайной величины лежат в интервале [m - 3-с; m + 3-с] и с достоверностью не менее чем с 95%-й -в интервале [m - 2-с; m + 2-с]». Отсюда эффективность цветового канала можно рассчитать по формуле

E = (1 - 4-с) -100 %.

В противном случае, если значения выборки не распределены по нормальному закону или закон распределения не известен, определяется параметр допустимого отклонения 5е(0; 1). А эффективность цветового канала будет вычисляться по формуле

E = — -100%,

N

где k - число элементов выборки, принадлежащее диапазону [m - 0,5-5; m + 0,5-5]; N - общее число элементов. Очевидно, чем больше параметр эффективно-