Факультет: Вычислительной техники и информатики
Специальность: Программное обеспечение автоматизированных систем.
Тема выпускной работы:
Исследование алгоритмов классификации трехмерных облаков точек и их эффективная реализация на графических процессорах
Научный руководитель: Зори Сергей Анатольевич
Реферат по теме выпускной работы
Актуальность темы исследования
В последнее время наблюдается возрастающий интерес к проблемам классификации трехмерных облаков точек. Алгоритмы классификации используются в системах распознавания образов. Подобные системы успешно применяются в различных областях науки и быта. Лидирующие позиции в такого рода исследованиях занимают США, Япония и страны в Евросоюза. В Украине и странах ближнего зарубежья такие технологии еще не получили широкого распространения.
Вкратце охарактеризуем области применения систем распознавания трехмерных моделей и прикладных алгоритмов классификации трехмерных облаков точек, описывающих эти модели. Подобные технологии используются для решения широкого спектра геодезических задач (например, создание и распознавание трехмерных моделей поверхности земли и объектов сложной геометрической формы). Успешные разработки в данной области могут найти применение в таких отраслях медицины, как онкология, рентгенография, компьютерная томография, ультразвуковое исследование. Также актуальны системы распознавания трехмерных сцен и принятия решений, достаточно точных, чтобы обеспечить безопасное автоматическое управление автомобилем на определенных участках дороги (автострада, известный участок дороги, пр.). Алгоритмы классификации необходимы в биометрических технологиях идентификации личности, которые используются в современных системах безопасности. Детальное документирование актуального состояния объектов или ситуации, в которой они были обнаружены (например, при археологических раскопках), является основным и естественным приемом в любом исследовательском проекте в области истории или культуры. Особенный интерес к трехмерному цифровому сохранению объектов в области культуры заметен именно в областях реставрации (составление точных и пригодных для применения виртуальных репрезентаций и моделей объектов для планирования реконструкции уникальных или подлежащих охране памятников культуры) и археологии, палеантологии, частично в связи с проектами виртуальных музеев. Эксперты в области искусствоведения могут применять алгоритмы классификации для распознавания отличительных особенностей культурного объекта (возраст, страна, стиль и т.д.). В том числе, возможно опознание краденых произведений искусства, описанного в специальной базе данных как облако точек.
Цель работы
Исследование алгоритмов классификации трехмерных облаков точек. Связанные с целью задачи сводятся, во-первых, к непосредственному анализу алгоритмов классификации, во-вторых, к поиску возможной оптимизации этих алгоритмов, в-третьих, к формализации теоретической базы и, в-четвертых, к программной реализации алгоритма на языке CUDA.
Предполагаемая научная новизна
Достаточно широкое распространение получила задача визуализации трехмерных облаков точек, разработано множество алгоритмов и методов для эффективного решения данной проблемы. Что касается распознавания, то исследования, проводимые в этой сфере гораздо малочисленней. В данной магистерской работе планируется поиск существующих алгоритмов классификации, в том числе рассматривается возможность применения в этой области алгоритмов, используемых для визуализации, их анализ и разработка своего, более эффективного, нежели существующие, метода. Улучшения скорости и работоспособности алгоритма планируется достичь за счет применения распараллеливания посредством использования ресурсов графических процессоров.
Подходы к решению
Существует два принципиально разных подхода к решению задачи классификации трехмерных облаков точек – методы, в основу которых лег принцип деформации исходного облака до эталонного и интерполяция облака трехмерными сплайнами.
Математические основы деформируемых моделей представляют собой совокупность геометрии, физики и теории приближения. Геометрия служит для отображения формы объекта, физика ограничивает рамки, в которых форма может изменяться во времени и пространстве, а теория оптимальной аппроксимации формально обосновывает требования к устройствам, которые служат для приведения моделей в соответствие с данными измерений.
В основе деформационных моделей лежит задача соотношение контуров. Она известна в англоязычной литературе как “matching”. Эта задача распадается на два направления: разметка (labeling) – соотношение контуру, полученного из среза, с контуром, взятым из модели; регистрация (registration) – соотношение контуров, полученных из двух разных срезов. Решение вышеприведенных задач обычно выполняется путем построения структурированного описания контуров и последующего "эластичного" соотношения описаний. Под структуризацией описания понимается поиск в контуре характерных точек, элементарных кривых и других элементов, которые будут сравниваться между двумя контурами. "Эластичное" соотношение строится на основе метода “деформационных моделей” (deformable models), известного также под названием “геометрические деформированные контуры”. Двумерный вариант этого метода получил название "змейка" (snake). Сущность данного метода заключается в том, что контур или его элемент испытывает итерационную деформацию до тех пор, пока не достигнет максимально возможного соответствия с другим соответствующим контуром или элементом. Изменение поверхности (деформация) происходит исходя из того, что искомый контур испытывает изменения под воздействием двух энергий: внутренней и внешней. На каждом шаге алгоритма отыскивается контур, для которого присутствующий баланс энергий, то есть минимальная деформация. Уточнение происходит до тех пор, пока не будет достигнут критерий соответствия искомого и эталонный контуру.
Еще одной из методик сопоставления двух облаков является метод построения поверхностных сплайнов и дальнейший статистический анализ коэффициентов полученных полиномиальных трехмерных функций.
Интерполированием называют определение значения функции для промежуточных значений аргумента. Можно предположить, что график изменения функции на одном шаге достаточно хорошо аппроксимирует хорда, соединяющая две соседние точки. На практике это условие выполняется далеко не всегда. Результат будет более точным, если через заданные точки провести кривую, как можно более плавную (рис. 2.3) без изломов. Тогда значение функции y(x) для значения x=? можно будет просто считать с графика. Конечно, такой способ интерполирования опирается скорее на интуицию, чем на строгую математику, но, тем не менее, это лучше, чем линейное интерполирование. Особенно хороший результат будет получен в случае применения функциональных шкал, когда кривая зависимости y от x спрямлена.
В случае, если вид функции y(x) известен, но неизвестны лишь ее параметры, то интерполирование может быть строгой математической операцией.
Алгоритм сравнения путем построения деформационных моделей выполняется достаточно долго: для каждой точки распознаваемого облака рассчитывается энергия, с которой в нее будет деформирована каждая точка эталонного облака. Исходное облако составляют n точек, а эталонное – m. Если предположить что n приблизительно равно m, то сложность алгоритма можно оценить, как O(n2). Кроме того, построение деформационной модели – процесс итерационный, требующий некоторого числа шагов – k. Однако, k на порядок меньше n, посему на временной сложности не отразится. Необходимо так же учесть трудоемкость процесса решения уравнения Эйлера, который так же потребует ощутимое машинное время.
При интерполировании происходит построение поверхности по облаку точек путем разбиения облака на определенные участки, и нахождения поверхностной функции, как можно проходящей через точки, составляющие участок. Построение сплайна менее трудоемко, нежели решение уравнения Эйлера. Временная сложность интерполяционного алгоритма составит O(n).
Теперь касательно объема дополнительной памяти, необходимой для работы алгоритма. Для построения деформационной модели, как уже было сказано ранее, необходимо решить уравнение Эйлера. Однако существует способ замены уравнения Эйлера на систему линейных уравнений. Количество уравнений и неизвестных прямо пропорционально количеству точек в облаке, и как следствие нужно будет хранить матрицу с коэффициентами уравнений размером n*n.
Для метода интерполяции по некоторым правилам необходимо будет определить m коэффициентов для каждого полиномиального сплайна, которых насчитывается порядка n единиц. Но так как m< При классификации методой сплайновой интерполяции явного критерия схожести двух облаков нет. Полученные коэффициенты поверхностных сплайнов будут различны для двух облаков со схожей структурой. Напрашивается следующее решение: для каждого облака строится равное число сплайнов, а затем проводится статистический анализ двух равновеликих векторов – например, нахождение коэффициента корреляции. Такой алгоритм имеет право на жизнь, но уступает по надежности проверенному методу построения деформационных моделей.
Камнем преткновения в выборе оптимального алгоритма является потребность в дополнительных исходных данных. Пусть даны два облака, которые должны быть причислены к одному классу. После нахождения интерполяционным методом коэффициентов поверхностных сплайнов возникает проблема сопоставления соответствующих друг другу сплайнов. Одно и то же облако может быть повернуто на любые углы и смещено на неопределенное расстояние. И если проблему смещение можно решить за счет нахождения центра тяжести облаков и перемещения его в начало координат, то очевидного метода нахождение углов поворота и, следовательно, соответствующих друг другу поверхностных сплайнов нет. Перебор приведет к увеличению временной сложности в n2 раз, и станет непригодной дл использования.
Казалось бы, та же самая проблема возникнет и при сравнении облаков методом деформационных модели. Но среди всех вариаций деформационных моделей присутствует алгоритм деформации внутренней или внешней сферой. Алгоритм заключается в поэтапной деформации вписанной в облако, или описанной вокруг него сферы до достижения сходства с облаком с определенной погрешностью. Данная методика обычно используется для визуализации облака, но подойдет и для классификации. При сопоставлении двух облаков считается энергия, необходимая для деформации сферы до исходного и эталонного облаков с учетом коэффициента масштабирования. Мерой сравнения схожести будет разница энергий деформации сферы до исходного облака и до эталона.
На текущий момент выполнен теоретический анализ двух принципиально разных концепций классификации трехмерных облаков точек – метода деформационных моделей и его разновидностей и метода объемной интерполяцией с помощью трехмерных сплайнов. Выявлены их сильные и слабые стороны, рассмотрен возможный путь оптимизации при дальнейшей реализации, а также выявлены возможные проблемы, которые могут возникнуть при разработке программного обеспечения на основе данных алгоритмов. Найден наиболее подходящий для решения поставленной задачи алгоритм - метод построения деформационной модели с использованием внутренней сферы. Оптимизация будет достигнута за счет распараллеливания алгоритмов на графических процессорах с помощью языка CUDA. Следует отметить, что CUDA относится к подмножеству – SIMD языков, то есть на множестве процессоров GPU может одновременно выполняться только один алгоритм. Уменьшение времени работы будет достигнуто за счет разбиения сферы на несколько секторов, для каждого из которых будет рассчитана энергия деформации до соответствующего участка облака.
Данный автореферат носит обзорный характер, так как магистерская диссертация, по которой он написан, находится в стадии разработки и будет совершенствоваться на протяжении осеннего семестра 2009 года.
Достигнутые результаты и дальнейшие перспективы
Список использованной литературы