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

На правах рукописи

Рябииин Константин Борисович

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

Специальность 05 13 18 —Математическое моделирование, численные методы и комплексы программ

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Ульяновск — 2008

003447085

Работа выполнена на кафедре «Радиотехнических и медико-биологических систем» Марийского государственного технического университета

Научный руководитель

доктор технических наук, профессор Фурман Яков Абрамович

Официальные оппоненты доктор физико-математических наук,

профессор

Валеев Султан Галимзянович

кандидат технических наук, доцент Кревецкий Александр Владимирович

Ведущая организация

ОАО «Марийский машиностроительный завод», г Йошкар-Ола

Защита состоится « 8 » октября 2008 г в 15°° на заседании диссертационного совета Д212 277 02 при Ульяновском государственном техническом университете по адресу 432027, г. Ульяновск, ул Северный Венец, 32 (ауд 21П

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

Автореферат разослан «_»_2008 г

Ученый секретарь

диссертационного совета, доктор технических наук, профессор

ВР Крашенинников

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

1) использование третьей координаты повышает информативность изображения;

2) усиливается степень ортогональности зашумленных пространственных групповых точечных объектов разных классов, что обеспечивает значительный рост эффективности распознавания по сравнению с двумерным случаем,

3) появляется возможность анализа результатов трехмерного моделирования в любой проекции и сечении объекта

Техническое зрение является трехмерной проблемой Поэтому в основе разработки многофункциональных систем технического зрения, пригодных для работы в различных средах, лежит процесс обработки информации о трехмерных сценах Интенсивные исследования в этой области имеют многолетнюю историю и связаны с работами М Минского, ПУинстона, К Фу, РГонсалеса, ВКиричука. Я Фурмана и др Вместе с тем, единый подход к обработке трехмерных изображений в настоящее время отсутствует В этом плане целесообразно прив чечение аппарата кватернионного ан&чиза, который в полной мере отражает свойства трехмерного пространства

В диссертационной работе исследуются точечные трехмерные сцены двух видов Сцены первого вида - это скопления небольшого количества точек — пространственные групповые точечные объекты (количество точек невелико и составляет 10-20 отметок), сцены второго вида - это обширные точечные поля, расположенные на поверхности трехмерных объектов (количество точек порядка 103 и более) Обработка сцен первого вида актуальна для радиолокационных, астронавигационных и медико-биологических задач Здесь важной нерешенной проблемой является задача упорядочения отметок пространственного группового точечного объекта (ПГТО), без решения которой нельзя корректно перейти к решению вопросов распознавания и оценки параметров объектов Для пространственных точечных полей (ПТП) актуальны задачи детектирования (обнаружения) заданной формы трехмерной подстилающей поверхности и визуализации результатов обработки Решению этих задач посвящено данное диссертационное исследование

В диссертации процесс обработки ПТП сводится к обработке векторных полей Поскольку отметки на поверхности трехмерных объектов получены случайным образом, то исследуемые модели трехмерной поверхности и ПГТО являются разновидностями трехмерных случайных полей Обработке многомерных случайных полей посвящены работы Васильева К К, Крашенинникова В Р

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

Целью диссертационной работы является разработка оптимального по критерию минимума расстояния алгоритма формирования «проволочной» математической модели для решения задач распознавания изображений, расположенных в пространстве в виде групповых точечных объектов при наличии координатного шума, а также разработка алгоритмов для визуализации и анализа пространственных объектов, заданных в виде ПТП Под проволочной моделью будем понимать пространственную полигональную линию, проходяи(ую единственным образом без разветвлений через все точки объекта

Для достижения заявленных в диссертационной работе целей решаются следующие задачи

• Разработка алгоритма представления ПГТО в виде упорядоченной последовательности точек

• Исследование эффективности и устойчивости алгоритма распознавания упорядоченного ПГТО в условиях воздействия координатных шумов

• Разработка алгоритма определения параметров вращения кватернионных моделей сигналов, таких как угол поворота и ось вращения, для решения задачи распознавания

• Синтез алгоритма сегментации и визуализации ПТП на основе процедур кластеризации

Методы исследования. Для решения поставленных в диссертационной работе задач использованы методы математического моделирования, методы обработки сигналов и изображений, спектрального и корреляционного анализа, теории вероятностей, математической статистики, линейной алгебры, методы объектно-ориентированного программирования

Научная новизна. В диссертационной работе получены следующие, выносимые на защиту, новые научные результаты

• Проволочная модель ПГТО и результат исследования ее на помехоустойчивость при воздействии координатных шумов

• Алгоритм упорядочения ПГТО на базе проволочной модели, оптимальный по критерию минимума расстояния

• Алгоритм распознавания кватернионных сигналов с неизвестным углом поворота и осью вращения относительно эталонного сигнала, оптимальный по критерию минимума расстояния

• Алгоритм визуализации трехмерной модели анализируемого объекта или сцены на основе процедуры кластеризации точек множества

Практическая ценность работы заключается в следующем

1 Решение задачи упорядочения ПГТО, представленного в виде его проволочной модели, позволяет использовать методы теории сигналов для распознавания трехмерных изображений групповых точечных объектов

2 Реализованы в виде программных модулей алгоритмы упорядочивания и распознавания отметок ПГТО в виде проволочной модели, алгоритмы определения параметров вращения кватернионных сигналов - угла поворота и оси вращения

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

4 Результаты, полученные в ходе диссертационного исследования, вошли в учебный процесс кафедры «Радиотехнических и медико-биологических систем» по специальности «Радиотехника» в курсы «Радиотехнические системы», «Цифровая обработка радиотехнических сигналов» и для специальности «Инженерное дело в медико-биотогической практике» - «Обработка медико-биологических объектов»

На защиту выносятся:

1 Адекватная провоючная кватернионная модель изображения ПГТО, ассоциированная с выпуклыми вложенными многогранниками, вершинами которых служат точки объекта и оценка ее помехоустойчивости

2 Оптимальный по критерию минимума расстояния алгоритм распознавания ПГТО, представленных в виде их проволочных моделей

3 Алгоритм опредечения параметров вращения ПГТО по результатам его согласованной фильтрации

4 Оптимальный алгоритм сегментации ПТП по критерию максимума модуля гиперкомплексной части скалярного произведения кватернионных сигналов

Личный творческий вклад автора. Непосредственно автором разработан алгоритм нумерации граней ассоциированного с ПГТО выпуклого многогранника на основе интегральных характеристик и на основе расстояния между контурами граней [1] Автором были проведены эксперименты по проверке помехоустойчивости сформированной проволочной модели при воздействии координатных шумов [7,8] Лично была разработана программа определения параметров вращения кватернионного сигнала [2,3,9] и программа визуализации точечных полей на основе процедуры кластеризации [4,5,6,10,11]

Апробация работы. Результаты работы обсуждались на 8-ой Международной конференции «Распознавание образов и анализ изображений новые информационные технологии» (РОАИ-8-2007) (Йошкар-Ола, 2007 г), на 13-ой Всероссийской конференции «Математические методы распознавания образов» (ММРО-13) (Санкт-Петербург, 2007 г), на всероссийском семинаре «Современное состояние и перспективы применения ГИС-технологий и аэрокосмочиских методов в лесном хозяйстве и садово-парковом строительстве» (Йошкар-Ола, 2008), на ежегодных научных конференциях профессорско-преподавательского состава МарГТУ Результаты работы использованы в проектах, поддержанных грантами РФФИ проект №07-01-00058-а «К решению проблемы визуализации и анализа ЗБ сцен, распознавания пространственных образов методами кватернионного исчисления», проект №08-01-12000-офи «Разработка методов и создание информационной технологии визуализации и сравнительного анализа сопряженных пространственных статических и динамических сцен»

Публикации По теме диссертации опубликовано 11 печатных работ Из них две - в журналах РАН, в том числе одна работа, опубликована в журнале, рекомендованном ВАК Также получено одно свидетельство об официальной регистрации программы

Структура и объем диссертации. Диссертационная работа включает в себя

введение, 6 глав, заключение, список литературы из 70 наименований и одного приложения Основная часть работы изложена на 196 страницах машинописного текста, содержит 90 рисунков, 7 таблиц

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе отражено состояние вопросов обработки, распознавания и упорядочения отметок объемных изображений, представленных в виде ПГТО Приведена классификация известных методов решения задач визуализации трехмерных изображений Изложено преимущество аппарата кватернионого анализа для представления ПГТО в трехмерном пространстве По результатам аналитического обзора сформированы конкретные цели и задачи исследований

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

Большинство задач распознавания решаются при условии предварительного упорядочения отметок ПГТО, т е известна начальная точка прослеживания объекта, а также порядок следования отметок ПГТО В условиях отсутствия такой информации, решить задачи определения класса объекта известными методами не представляется возможным. Таким образом, одной из важнейших задач в области обработки ПГТО является именно задача упорядочения его отметок

Среди применяемых алгоритмов упорядочения множества точек следует отметить следующие 1) нумерация точек по принципу максимальной простоты, 2) нумерация на основе графа «минимальное дерево»' 3) естественный подход к нумерации точек ГТО, 4) алгоритм объективной группировки точек

Следующей задачей является визуализация полученных точечных объектов В настоящее время известно довольно большое число различных методов представления трехмерных объектов и связанных с ними методов визуализации Эти представления можно разделить на несколько классов, обладающих характерными свойствами

1 Поверхностные, либо объемные

2 Связанные, либо дискретные

3 Явные, либо параметрические

Поверхностные модели описывают только поверхность объекта в трехмерном пространстве При этом область пространства Е3 при воксельном представлении делится на набор элементарных кубов (вокселей) Связанные модели явно или неявно содержат информацию о непрерывных участках поверхностей моделей, тогда как дискретные представления описывают только приближение поверхности объекта Явное задание моделей предполагает, что описание модели объекта в данном представлении доступно в явной форме, а параметрическое - что для его получения необходимо дополнительно вычислять некоторую функцию, зависящую от ряда параметров

Во второй главе приведен обзор методов аналитического представления ПГТО Проведен структурный анализ точек ПГТО, в результате чего получен алгоритм для представления ПГТО в виде сложной многогранной структуры, в которой отметки

ПГТО представляются вершинами этой структуры. По результатам структурного анализа на базе кватернионных сигналов получено описание ПГТО в виде проволочной модели.

ПГТО задается в виде кватернионного сигнала, который получается следующим образом. Пусть Л = {а„}05_| - множество расположенных в трехмерном

пространстве .у точек (рис. 1).

Каждую его точку а„ соединим с началом отсчета одноименным вектором аг =я„1< + <2„2 ] + « = 0,1,...,5—1, заданным в кватернионном виде. В

результате получим векторный кватернионный сигнал ■.._-•

Л = =| а„Х1 + а„2] + апгк V . (1)

I ] См-1

Для аналитического описания ПГТО известны следующие методы представления;

1) в виде пучка кватернионов;

2) в виде полигонального контура;

3) в виде амплитудно-фазовой модели.

Для решения задачи упорядочения ПГТО во второй главе находится представление в виде выпуклого многогранника по заданному множеству точек его вершин. В данном разделе будет показано, что для решения этой задачи достаточно задать неупорядоченный ПГТО Е= {£(

' ' " = 0,1.....х — одна из х его

вершин.

Основная проблема задания выпуклого многогранника множеством его вершин состоит в установлении по результатам анализа ПГТО связей между этими вершинами в виде графа или матрицы. Например, для гексаэдра (рис.2.а) такой граф имеет вид представленный на рис. 2,6.

Каждое полупространство, пересечение конечного числа которых образует выпуклый многогранник, содержит ограничивающую плоскость 4. Такую плоскость назовем критической. Она обладает следующими свойствами: 1) содержит не менее трех точек ПГТО Е. являющихся вершинами выпуклого многогранника, и 2) все остальные вершины многогранника расположены по одну сторону критической плоскости, а по другую сторону плоскости нет ни одной точки ПГТО.

а0

а)

Рис 2 Объемная фигура гексаэдра (а) и его граф (б) Синтез выпуклого многогранника по заданному множеству точек Е = {¡;(«)}о л—1

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

Результатом начального этапа должно быть построение по этим данным нулевой (начальной) критической плоскости Д0 и определение находящихся в ней вершин А/, те точек Ад = {ап0}

Для построения текущей плоскости из множества А = {ап}(1произвольно

выбирается одна точка в качестве полюса и еще две точки для построения двух разностных векторов Далее вычисляется нормаль г к полученной плоскости Если полученная плоскость не обладает свойством критичности, то оставшиеся 5-5 точки множества А будут располагаться по обе ее стороны Поэтому для проверки плоскости на критичность достаточно вычислить знаки косинусов углов, образованных векторами, соединяющих каждую из этих ($-2) точек с полюсом, и вектором нормали г к полученной плоскости (рис 3,а)

Построенная плоскость будет критической, если вычисленные значения косинусов углов (р будут иметь один и тот же знак После получения первой критической плоскости Д0 определяем распочоженные в ней точки аг„ подмножества .*)0 Эти точки будут вершинами многоугольника, ограничивающего грань

Следующей, после получения многогранника, является процедура упорядочения точек данного подмножества, являющихся вершинами выпуклого многоугольника Стороны этого многоугольника будут ребрами многогранника, относящимися к грани Са Упорядочение проводится методом построения критических линий для расположенного в плоскости множества точек На рис 3,6 показаны линии, проходящие через точки, принадлежащие одной плоскости Точки этого множества расположены по обе стороны линии 1Г и поэтому данная линия не будет, в отличии от линии 22', критической.

I

9

Результат начального этапа анализа многоугольника можно представить в виде фрагмента полного графа, описывающего структуру многогранника (рис. 4,6).

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

Контур От ={^/т(л)}, т = 0,1, ...,/„, —1, представляет собой последовательность кватернионов, задающих упорядоченные ребра многогранника в пределах грани Ст. Упорядоченные точки множества А = {ап }оы , относящиеся к грани не

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

грани Ст. Также известны нормали г'п, площади и точки центров тяжести граней вт, т = 0.1...../„,-1.

Следующий этап упорядочивания состоит в получении проволочной модели ПГТО. Проволочная модель дает правила нумерации его отметок, при которых номер точки с достаточно высокой вероятностью сохраняется в условиях действия

а) б)

Рис. 3: Решение задачи представления ПГТО в виде выпуклого многогранника: а) к методу критических плоскостей; б) к методу критических линий

После получения первой критической линии аналогично строится вторая подобная линия, причем полюс выбирается во второй точке первой критической линии и т.д. Процесс построения критических линий является сходящимся, т.е. в конечном счете, мы получаем замкнутую ломаную линию в виде выпуклого многоугольника, являющегося границей грани (70 (рис. 4,а).

Рис. 4: Формирование грани многоугольника в результате пересечения всех критических линий множества точек, а) контур грани; б) фрагмент графа многогранника

координатных шумов и при произвольных параметрах масштаба и вращения Первой процедурой для получения проволочной модели ПГТО является упорядочение граней ассоциированного с ним выпуклого многогранника

Упорядочение граней на основе их интегральных характеристик Анализ контура грани Сп позволяет найти нормаль гп к плоскости грани и количество ее вершин .1п, а также такие интегральные характеристики, как площадь 5„, положение центра тяжести 1„ грани относительно центра тяжести 1Х многогранника X, периметр Ьп, коэффициент формы кф, и др

=0.5 %Т,<1„(тШу))

1 т-О

, 2 (2) ■У 1/=| т=О

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

Упорядочение на основе величины расстояний между гранями Ранее рассмотренный подход к упорядочению граней на основе различия их интегральных характеристик имеет эвристический характер Представляя контуры граней элементами метрического пространства, можно найти расстояние между ними и тем самым с позиции критерия максимума расстояние оптимизировать процедуру нумерации граней многогранника X

Пусть {-0,1 }д /_[ - множество контуров многоугольников граней {Си}0/_[

многогранника X, где £>„ = {¿п(тДdJm) = c^ll](m)¡+dnl(m)J + c^„г(m)k, т = 0,1, ,5я-1, контур грани С„ Квадрат расстояния между пространственными контурами Ц, и Ц, равен

С=ИЧ|ДГ-2 (3)

где

(А(4)

т=О

Пусть текущая грань имеет номер и, те С„ = 0[и>, а следующий номер следует присвоить одной из граней Сг+1,Сг+2, Для принятия решения в

соответствии с выражением (3) вычисляется А значений расстояний 2 2 2

Кп,у+1>Кп,у+2> Ал'+а межцу контуром Вп и контурами Д+ьД.+г, ,Д+л Следующий, (г<+1)-й номер присваивается грани, для которой значение вычисленного расстояния максимально, т е

при Лп2;У+х^тахД = 1,2, Л (5)

После процедуры упорядочения граней выпуклого многогранника следует процедура упорядочения отметок всего ПГТО Процедура упорядочения начинается

выбором путевой точки Для этого выбирается одна из точек ап = affl вершин грани исходя из следующих условий 1) она не дотжна совпадать с точками ребра этой грани, общей с гранью Gn> и 2) обход по часовой стрелке всех точек контура грани G(0) должен закончится на точке этого ребра Последующие точки берутся з порядке обхода контура грани

При построении

проволочной модели условимся последовательность точек контура каждой грани устанавливать в направлении часовой стрелки при взгляде на многогранник со

стороны внешних точек, Затем обходятся точки граней и тд При этом

исключаются ранее пронумерованные точки Обход заканчивается после нумерации всех точек многогранника X при возврате в нулевую точку Далее вычисляется кватернионныи код

.] упорядоченного ПГТО D={j(v)}0)J_1=| a(>W°V2W>, (6)

Код задает замкнутый пространственный контур Элементарные векторы d(v) = af'+,J-a(v), v = 0,l, ,л-1, последовательно, без разветвлений, проходят через ряд ребер многогранника X и через все его вершины В таком виде контур ПГТО можно представить отрезком проволоки, начало, и конец которой закреплены в точке

а™

В третьей главе осуществлен синтез алгоритма и структуры распознавания ПГТО по его проволочной модели, при неизвестном угле поворота и оси вращения кватернионного сигнала, задающего этот объект Синтезирована структура для анализа неупорядоченного ПГТО (рис 5)

Рис 5 Стру ктура устройства распознавания кватернионных сигналов с неизвестными углом поворота и оси вращения

На рис 5 представлены КУП - корректор угла поворота, ФСП - формирователь скалярного произведения между входным кватернионным сигналом (3 и эталонным Р, Ие — устройство вычисления реальной части скалярного произведения кватернионных сигналов, экстремальное устройство — устройство определения класса сигнала на входе по оптимальному критерию минимума расстояния (максимума реальной части скалярного произведения)

В результате операции (7) пространственно распотоженная точка Лп, задаваемая

Рис. 6: Решение задачи определения параметров вращения 111 ТО: а) поворот вектора р(п) на угол 2ц/вокруг оси 00' с направляющим вектором грп; б) Соотношения между

эталонным q, исходным р и преобразованным рх векторами Необходимо определить параметры 2)// и кватернионного сигнала Р (рис.7).

вращения исходного

Кватернионный фильтр

ЬР" =Ъ 0 + 6 ,1+Ь 2 ]+Ъ з * = сову/ +гРезйпу/

концом вектора р(п), п = 0,1,...,.у -1, поворачивается на угол 2у/ вокруг оси 00' с направляющим вектором гра и совмещается с точкой А„ х (рис. 6,а).

Рис. 7: К постановке задачи определения параметров вращения кватернионного

сигнала

Сформируем на базе эталонного вектора собственную систему отсчета Х'У'Х', в которой вектор ц расположен вдоль оси 02'. Плоскости П и Г2Д. являются здесь "угломестными", а плоскость в, в которой расположено основание конуса - "азимутальной". Как видно из рис. 6,6, вектор рх может быть получен путем поворота исходного вектора р в угломестной плоскости П на угол Др, а затем получившегося вектора на угол Да в азимутальной плоскости в. Таким образом, углы др и Да являются параметрами преобразования вектора р в вектор рх в собственной сферической системе отсчета, связанной с эталонным вектором #. Если определить значения Ар и Да, то, решив задачу сложения двух поворотов, можно получить кватернион Ь = со5^ + гятц/ поворота вектора р. Компонентами этого кватерниона являются искомые параметры ц/ и г.

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

перпендикулярный кватернионам р и <7 Поэтому в соответствии выражением (8) нормированная гиперкомплексная часть СП векторов р ид задает нормаль к плоскости О, в которой расположены эти векторы га = Ьур (р,д) Аналогично гп, =йур [р„<])

\ /

р{п\д{п) = р(п)д (и) = р(п\д(п) I -

ДиЫ")

(8)

Также в этой главе приведены структуры реализующие алгоритм упорядочения (рис 8) и распознавания ПГТО (рис 9), заданного в виде его проволочной модели

* =Ыо,-1 ■

■ I УШОЛНОЙ |р»|!И

и тклы

Определенна Про» рКЛ П ЮС КОС Г*

К' К* пряш 1ВОСТЯ

Гкрлод к прлп«л\"р»ч ) порто кни4 грани ¡3*2 и пз ИК11 шктроеии«

проулочной иод^ли

Рис В Алгоритм структурного анализа неупорядоченного ПГТО

■н

Распознаваемый ПГТО ——

Упорядочение! точек

Формирование проволочной модели_

Кеттердаонный Кватермюнный Кветерниожый

со глас сеянный согласованный со глас ованный

фильтр фильтр фильтр

"ТИу)

| Решающее устройство_|

^ номер класса

Рис 9 Алгоритм распознавания ПГТО, представленного в виде его проволочной модели

В четвертой главе представлен алгоритм визуализации трехмерной сцены, представленной в виде ПТП К ним относятся точечные сцены с обширным количеством точек (103 и более) В данном разделе ставится задача визуализации ПТП и анализ характеристик трехмерного объекта

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

А„={ а„,»

п = ОД,...,/„ —1, элементарной грани й„ выбран вектор нормали к

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

М

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

В результате сегментации генеральное множество А = { аг }0 4,_1 представляется

совокупностью подмножеств {Ап }0 , относя!дихся к / элементарным граням

{Сп }0 м изображений объектов в сцене 1.

Перейдем к рассмотрению процедуры кластеризации точек генерального множества трехмерной сцены I.

Начальный этап кластеризации. На этом этапе из генерального множества А = {ау }0 выделяется первое подмножество точек, лежащих в одной из граней

визуализируемого многогранного тела. Это подмножество обозначим как

А-

, а соответствующую ему грань - как <30.

Для построения подмножества А0 выбирается произвольная точка генерального множества и назначается полюсом я. Пусть это будут, как показано на рис. 11, точки ¿г, и . На выходе такого устройства формируется гистограмма по значениям нормалей гп.

Да. о

Вычитающее устройство

ПОЛЮС

ау Вычитающее I

устройство <Ко

Формирователь гистограммы значений нормалей

Рис. 11: Структура первого цикла преобразования кластеризации точек множества

Одно из значений отсчета гистограммы, сформированной в результате действия структуры рис. 11, может соответствовать количеству Л^ элементарных граней в составе грани С0. Это произойдет, если опорный разностный вектор Аа10 лежит в плоскости одной из граней анализируемого многогранника. Тогда значение будет самым высоким отсчетом в гистограмме, значительно превосходящим остальные её отсчеты.

Промежуточные этапы На этих этапах кластеризации последовательно из генерального множества выделяются подмножества А,, А2, соответствующие

граням С,, С2, 0,_1 Некоторые точки генерального подмножества находятся на границах этих граней, т е одновременно принадлежат двум и ботее граням Если пренебречь этим фактором, то при выделении с помощью преобразования кластеризации точек множества грани (?т, точки подмножеств А0,А[, можно

исключить из рассмотрения и проверить на соответствие грани только

оставшиеся точки генерального множества

Таким образом, после сегментации сцена I аналитически представляется в виде

ЫС„}0М,С„ = {ал0 г. }, (9)

где 1 - число плоских участков (граней)

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

Ап=<а„,„> к остальным точкам подмножества Эта операция эффективно

I

выполняется путем выделения критических линий к точкам множества А„

Формирование пространственного контура грани Процесс последовательного формирования критических линий к точкам множества Ап является сходящимся, т е через конечное число шагов в качестве поноса для получения следующей критической линии будет выбрана точка, с которой этот процесс был начат К этому моменту в результате пересечения всех построенных критических линий получим выпуклый многоугольник Г,, обладающий следующими свойствами 1) каждое его ребро включает, как минимум, две точки подмножества Ап, 2) все расположенные на этих ребрах точки подмножества Ап являются внешними точками этого подмножества и 3) остальные точки расположены внутри многоугольника Тн и являются внутренними точками подмножества Ап

В кватернионном представлении этот контур имеет вид

= I , Д'»„='„„+!-'„»,. 0°)

п ^ п т )() ± —\ п т п т + 1 пт '

где - число ребер многоугольника Контур в виде (10) аналитически описывает форму грани в которой расположены точки подмножества Ап Этот контур можно интерпретировать в качестве кватернионного сигнала и для его обработки применить методы кватернионного анализа

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

подмножества А„ и (рис 12) На основании этих свойств смежная с Сп грань обнаруживается по критерию "к из п"

Формирование каркаса изображений объектов в трехмерной сцене /, заданной генеральным множеством точек А = {аа}й! , выполняется устранением из нее всех

точек этого множества, являющихся внутренними точками сегментированных граней <7„, п = ОД,..., I -1. Сформированные по краевым точкам контуры ребер в

о,-,

О - краевая точка • - инутргняя точка грани Рис. 12: Соотношения между краевыми точками смежных граней 0„ и С„-1. Пунктирные линии соответствуют истинным границам граней

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

В пятой главе исследована эффективность предложенных алгоритмов распознавания упорядоченного в виде проволочной модели Г1ГТО. Проанализировано влияние координатного шума на характеристики распознавания. Рассмотрено влияние неровностей поверхности, образованной при кластеризации точек ПТП, на эффективность предложенного алгоритма.

При воздействии координатного шума возникает ряд негативных факторов, таких как распад грани многогранника (рис. 13,а), ассоциированного с ПГТО, на одну и более (рис. 14,а), вследствие чего вся проволочная модель (рис. 13,6) теряет начальный вид (рис. 14,6). При этом возникают такие факторы как смещение начальной точки обхода выпуклого многогранника, вследствие чего происходит

модель ПГТО

а\

"I б) "I4 "Í

Рис 14 а) вид многогранника ассоциированного с зашумленным ПГТО б) проволочная модель

перепутыванле отметок ПГТО Соответственно искажается граф связей между вершинами многогранника, ассоциированного с ПГТО

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

1 Для полученных граней многогранника, ассоциированного с зашум пенным ПГТО, вычисляются нормали г:

2 Между полученными нормалями вычисляется расстояние по следующей формуле

3 В том счучае если расстояние Яг г меньше заданного порогового уровня X., то

принимается решение об объединении граней

В результате проведенного эксперимента для различных порогов объединения были получены характеристики правильного распознавания

uuj шума

О 0 04 0 08 0 12 0 16

Рис 15 Характеристики вероятности правильного распознавания от СКО шума при различных порогах объединения плоскостей (число экспериментов 1000 опытов на 1 точку

графика)

Из характеристик видно, что вероятность правильного распознавания при увеличении порога объединения граней сначала увеличивается (при одних и тех же значениях СКО координатного шума), а затем снова уменьшается Такой характер графиков обусловлен особенностями формы получаемого многогранника и зависит от расположения нормалей к граням исходного объекта

В шестой главе приведены практические результаты действия алгоритмов визуализации точечного поля В качестве исходных данных для анализа рассматривалось зашумленное точечное поле (рис 16)

=M2+¡;rj2-2Re(r.r,)

(И)

а) б)

Рис.16: Исходное точечное поле: а) поле отметок; б) поверхность сцены

На базе приведенного алгоритма (рис. 17) проводится низкочастотная фильтрация точечного поля (рис. 18,а) и, на основе полученных результатов, формируется векторное поле нормалей (рис. 18,6).

Рис. 17: Структура алгоритма визуализации точечного поля

щ

а)

б)

Рис.18: Результат работы алгоритма: а) сцена после НЧ фильтрации, б) векторное поле нормалей

Для реализации алгоритмов НЧ фильтрации и формирования векторного поля разработаны следующие структуры:

Рис 19 Структура реализации алгоритма НЧ фильтрации

Рис 20 Структура реализации алгоритма формирования векторного почя

Результатом действия алгоритма кластеризации является выделение плоских участков поверхности (рис 21)

Показана работоспособность алгоритма для визуализации трехмерных геометрических объектов, например для пирамиды (рис 22) и куба (рис 23)

ООО

5 « «

О О <Ъ ООО ООО ООО ООО ООО ООО ООО о о

о

о

Рис 22 Результат работы алгоритма а) исходное точечное поле (пирамида), б) результат

визуализации

•■/Ч4 •;.:•:

* •. ."п •"

• I

а) 6)

Рис.23: Результат работы алгоритма: а) исходное точечное поле (куб), б) результат

визуализации

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

1. Разработан новый устойчивый алгоритм упорядочения отметок ГТГТО по его проволочной модели. Проволочная модель однозначно нумерует отметки ПГТО и представляет собой его аналитическое описание в виде последовательности кватернионов.

2. Синтезирован алгоритм распознавания ПГТО по результатам согласованной фильтрации кватернионного сигнала, задающего проволочную модель объекта. Исследована помехоустойчивость алгоритма распознавания 3D изображений при воздействии координатных шумов для алфавита из четырех близких по форме классов. Достаточно хорошие результаты правильного распознавания с вероятностью не ниже 0,95 достигаются при оптимальном пороге объединения граней и отношении сигнал/шум не менее 700. Исследована также зависимость вероятностей правильного распознавания ПГТО от величины порога объединения элементарных граней в одну грань. Выявлено наличие максимума вероятности правильного распознавания при изменении величины данного порога. Для рассмотренного случая соотношение вероятности правильного распознавания при оптимальном пороге и неоптимальном изменяется от 0,95 до 0,3.

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

4. Выполнена программная реализация алгоритма низкочастотной фильтрации трехмерного точечного поля, а также алгоритмов формирования векторного поля и визуализации точечного поля. Время работы программы при обработке трехмерного изображения объекта (количество точек от 300 до 600), заданного в виде ПТП, на PC с процессором Intel Celeron 2,8 ГГц и ОЗУ 504 МБ при использовании неоптимизированной версии программы составляет 7-10 сек.

СПИСОК ОСНОВНЫХ ПУБЛИКАЦИЙ

В изданиях из списка ВАК:

1 Рябинин К Б , Фурман Я А, Красильников M И Проволочная модель пространственного группового точечного объекта//Автометрия, 2008, №3. - с 3-16

В других изданиях:

2 Рябинин К Б, Фурман Я А Нахождение параметров вращения пространственного группового точечного объекта по результатам его фильтрации// Радиотехника и электроника, 2008, т 53, №1. - с 86-97

3 К В Ryabmin, Ya A. Furman Determimng the rotational variables of a spatial group point object from the object's filtering results// Journal of Communications Technology and Electronics, 2000, vol 53, No 1. - pp 78-89

4 Рябинин К Б, Фурман Я А Новые подходы к обработке трехмерных изображений/ Наука в условиях современности Сборник статей студентов, аспирантов, докторантов и ППС по итогам научно-технической конференции МарГТУ в 2007 году, Йошкар-Ола, 2007. - с 102-106

5 Рябинин К Б, Фурман Я А, Хафизов Д Г К решению проблемы визуализации и анализа 3D сцен, распознавания пространственных образов методами кватернионного исчислении/ Сборник докладов 13-ой Всероссийской конференции «Математические методы распознавания образов — 13», г Санкт-Петербург, 2007 -с 412-414

6 Рябинин К Б , Фурман Я А , Д M Ворожцов Визуализация изображений объектов в трехмерной точечной сцене/ Вестник вятского научного центра №1(7), Киров, 2006 -с 124-129

7 Рябинин К Б , Хафизов Д Г Распознавание 3D изображений групповых точечных объектов по их проволочным моделям на основе кватернионного исчисления/ Сборник докладов 13-ой Всероссийской конференции «Математические методы распознавания образов - 13», г Санкт-Петербург, 2007. -с 417-419.

8 Рябинин К Б , Хафизов Д Г. Идентификация и построение характеристик распознавания пространственных групповых точечных объектов по их проволочных моделям/ Труды 8-ой Международной конференции «Распознавание образов и анализ изображений новые информационные технологии» (РОАИ-8-2007), т.1, Йошкар-Ола, 2007 - с 29 - 31

9 Свидетельство об официальной регистрации программы для ЭВМ № №2007614092 (РФ) Программный комплекс для определения параметров вращения кватернионного сигнала / К Б Рябинин, Я А Фурман//РОСПАТЕНТ, 2007

10 Рябинин КБ, Фурман ЯА, Красильников МИ Оценка степени шероховатости подстилающей поверхности по результатам дистанционного зондирования/ Сборник статей Всероссийского семинара по ГИС технологиям Йошкар-Ола 2007. - с.61 - 66

11 Рябинин К Б. Решение задачи выбора посадочной площадки беспилотного летательного аппарата на базе кватернионного анализа/Вестник МарГТУ, Йошкар-Ола, 2008, №1 -с 33-43

Бумага офсетная Печать офсетная Уел п л 1,0 Тираж 100 экз Заказ №3898

Редакционно-издательский центр Марийского государственного технического университета 424006 Йошкар-Ола, ул Панфилова, 17

ВВЕДЕНИЕ

СОДЕРЖАНИЕ

1. ОБЗОР СУЩЕСТВУЮЩИХ МАТЕМАТИЧЕСКИХ МЕТОДОВ 17 ОБРАБОТКИ И РАСПОЗНАВАНИЯ ПРОСТРАНСТВЕННЫХ ИЗОБРАЖЕНИЙ

1.1. Введение

1.2. Методы формирования цифровых данных при сканировании 18 пространственных объектов

1.3. Способы визуализации трехмерных объектов

1.4. Проблема упорядочивания групповых точечных объектов

1.5. Проблема распознавания и оценки параметров объемных 37 поверхностей

1.6. Выводы

2. УПОРЯДОЧЕНИЕ ПРОСТРАНСТВЕННОГО ГРУППОВОГО 42 ТОЧЕЧНОГО ОБЪЕКТА

2.1. Постановка задачи и подходы к её решению

2.2. Математическая модель представления ГТО в трехмерном 44 пространстве

2.2.1. Задание математической модели ГТО в виде пучка 44 кватернионов

2.2.2. Задание математической модели ГТО в виде полигонального 45 контура

2.2.3. Задание математического описания ГТО в виде амплитудно- 46 фазовой модели

2.3. Математическая модель пространственного ГТО в виде 48 выпуклого многогранника

2.3.1. Общие замечания

2.3.2. Начальный этап построения многогранника

2.3.3. Промежуточные этапы построения многогранника

2.4. Упорядочение пространственного ГТО на базе его «проволочной» 57 модели

2.5. Пример упорядочения точек пространственного ГТО

2.5.1. Построение многогранника по заданному множеству точек 60 его вершин

2.5.2. Представление точек пространственного ГТО в виде 72 проволочной математической модели

2.6. Выводы

3. СИНТЕЗ АЛГОРИТМОВ РАСПОЗНАВАНИЯ

ПРОСТРАНСТВЕННЫХ ГРУППОВЫХ ТОЧЕЧНЫХ ОБЪЕКТОВ

3.1. Введение

3.2. Общий (геометрический) подход к решению задачи 80 распознавания полностью известных кватернионных сигналов

3.3. Распознавание ГТО с неизвестным номером первой точки

3.4. Распознавание кватернионных сигналов с неизвестным значением 86 угла поворота

3.5. Нахождение параметров вращения ПГТО по результатам его 88 фильтрации

3.5.1. Постановка задачи

3.5.2. Преимущество решения задачи при использовании теории 90 кватернионного анализа

3.5.3. Аналитические соотношения между выходным и входным 94 сигналами кватернионного фильтра

3.5.4. Вычисление параметров преобразования исходного вектора в 97 собственной сферической системе отсчета

3.5.5. Определение вида единого преобразования исходного КТС

3.5.6. Пример решения задачи определения параметров вращения

3.6. Алгоритм структурного анализа неупорядоченного 104 пространственного ГТО

3.7. Структура алгоритма распознавание пространственного 106 группового точечного объекта

3.8. Выводы 108 4. ВИЗУАЛИЗАЦИЯ ИЗОБРАЖЕНИЙ ОБЪЕКТОВ В ТРЕХМЕРНОЙ 109 ТОЧЕЧНОЙ СЦЕНЕ НА БАЗЕ КВАТЕРНИОННЫХ МОДЕЛЕЙ

4.1. Введение и постановка задачи

4.2. Преобразование кластеризации точечной трехмерной сцены

4.3. Автозахват плоскости истинной грани многогранника

4.4. Построение гистограммы сферических координат точек нормалей

4.5. Локализация пиков гистограммы сферических координат точек 122 нормалей

4.6. Обнаружение точек нормалей к анализируемой плоскости

4.7. Принципы реконструкции трехмерной сцены, заданной в виде 125 точечного поля

4.8. Визуализация изображения трехмерной сцены на примере 129 объемной пирамиды

4.8.1. Представление объекта генеральным множеством точек

4.8.2. Кластеризация генерального множества

4.8.3. Обнаружение точек нулевой грани объекта

4.8.4. Обнаружение точек последующих граней объекта

4.8.4.1. Первая грань объекта

4.8.4.2. Вторая грань объекта

4.8.4.3. Третья грань объекта

4.8.5. Анализ кластеров

4.8.6. Коррекция подмножеств граней путем добавлений особых 139 точек

4.8.7. Аналитическое описание формы граней

4.8.8. Структурный анализ формы граней объекта

4.8.9. Анализ результатов фильтрации контуров граней объекта 144 4.9. Выводы

5. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ

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

5.1. Введение

5.2. Проволочная модель пространственного группового точечного 150 объекта в условиях воздействия координатного шума

5.2.1. Модель координатного шума для случая трехмерного 150 изображения

5.2.2. Воздействие координатного шума на проволочную модель 152 ПГТО

5.2.3. Алгоритм распознавания зашумленного ПГТО

5.2.4. Экспериментальные исследования при распознавании 155 зашумленного ПГТО

5.3. Исследование пространственных точечных полей в условии 156 воздействия шумов

5.3.1. Появление ложных граней объекта

5.3.2. Методы борьбы с выделением ложных граней

5.4. Выводы 160 6. РЕШЕНИЕ ПРИКЛАДНОЙ ЗАДАЧИ ВЫБОРА УЧАСТКА

ПОВЕРХНОСТИ ДЛЯ ПОСАДКИ ЛЕТАТЕЛЬНОГО АППАРАТА

6.1. Постановка задачи обработки трехмерных изображений

6.2. Программная реализация алгоритма формирования множества 163 ближайших точек

6.3. Программная реализация формирования векторного поля для 166 анализируемого изображения

6.4. Программная реализация метода определения плоских участков 169 поверхности

6.5. Примеры обработки объемных объектов с помощью ,'" 173 разработанного программного продукта

6.6. Выводы 178 ЗАКЛЮЧЕНИЕ

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

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

1) использование третьей координаты повышает информативность изображения;

2) усиливается степень ортогональности зашумленных пространственных групповых точечных объектов разных классов, что обеспечивает значительный рост эффективности распознавания по сравнению с двумерным случаем;

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

Техническое зрение является трехмерной проблемой. Поэтому в основе разработки многофункциональных систем технического зрения, пригодных для работы в различных средах, лежит процесс обработки информации о трехмерных сценах. Интенсивные исследования в этой области имеют многолетнюю "историю и связаны с работами М.Минского, П.Уинстона, К.Фу, Р.Гонсалеса, В.Киричука, Я.Фурмана и др. Вместе с тем, единый подход к обработке трехмерных изображений в настоящее время отсутствует. В этом плане целесообразно привлечение аппарата кватернионного анализа, который в полной мере отражает свойства трехмерного пространства.

В диссертационной работе исследуются точечные трехмерные сцены двух видов. Сцены первого вида — это скопления небольшого количества точек — пространственные групповые точечные объекты (количество точек невелико и составляет 10-20 отметок), сцены второго вида - это обширные точечные поля, расположенные на поверхности трехмерных объектов (количество точек порядка 10 и более). Обработка сцен первого вида актуальна для радиолокационных, астронавигационных и медико-биологических задач. Здесь важной нерешенной проблемой является задача упорядочения отметок пространственного группового точечного объекта (ПГТО), без решения которой нельзя корректно перейти к решению вопросов распознавания и оценки параметров объектов. Для пространственных точечных полей (ПТП) актуальны задачи детектирования (обнаружения) заданной формы трехмерной подстилающей поверхности и визуализации результатов обработки. Решению этих задач посвящено данное диссертационное исследование.

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

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

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

Для достижения заявленных в диссертационной работе целей решаются следующие задачи:

• Разработка алгоритма представления ГЕТТО в виде упорядоченной последовательности точек.

• Исследование эффективности и устойчивости алгоритма распознавания упорядоченного ПГТО в условиях воздействия координатных шумов.

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

• Синтез алгоритма сегментации и визуализации ПТП на основе процедур кластеризации.

Методы исследования

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

Достоверность и обоснованность

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

На защиту выносятся:

1. Адекватная проволочная кватернионная модель изображения ПГТО, ассоциированная с выпуклыми вложенными многогранниками, вершинами которых служат точки объекта и оценка ее помехоустойчивости.

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

3. Алгоритм определения параметров вращения ПГТО по результатам его согласованной фильтрации.

4. Оптимальный алгоритм сегментации ПТП по критерию максимума модуля гиперкомплексной части скалярного произведения кватернионных сигналов.

Научная новизна работы

В диссертационной работе получены следующие, выносимые на защиту, новые научные результаты:

• Проволочная модель ПГТО и результат исследования её на помехоустойчивость при воздействии координатных шумов.

• Алгоритм упорядочения ПГТО на базе проволочной модели, оптимальный по критерию минимума расстояния.

• Алгоритм распознавания кватернионных сигналов с неизвестным углом поворота и осью вращения относительно эталонного сигнала, оптимальный по критерию минимума расстояния.

• Алгоритм визуализации трехмерной модели анализируемого объекта или сцены на основе процедуры кластеризации точек множества.

Практическая значимость работы заключается в следующем:

1. Решение задачи упорядочения ПГТО, представленного в виде его проволочной модели, позволяет использовать методы теории сигналов для распознавания трехмерных изображений групповых точечных объектов.

2. Реализованы в виде программных модулей алгоритмы упорядочивания и распознавания отметок ПГТО в виде проволочной модели; алгоритмы определения параметров вращения кватернионных сигналов — угла поворота и оси вращения.

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

4. Результаты, полученные в ходе диссертационного исследования, вошли в учебный процесс кафедры «Радиотехнических и медико-биологических систем» по специальности «Радиотехника» в курсы «Радиотехнические системы», «Цифровая обработка радиотехнических сигналов» и для специальности «Инженерное дело в медико-биологической практике» - «Обработка медико-биологических объектов».

Апробация работы

Результаты работы обсуждались на 8-ой Международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» (РОАИ-8-2007) (Йошкар-Ола, 2007 г.); на 13-ой Всероссийской конференции «Математические методы распознавания образов» (ММРО-13) (Санкт-Петербург, 2007 г.); на всероссийском семинаре «Современное состояние и перспективы применения ГИС-технологий и аэрокосмических методов в лесном хозяйстве и садово-парковом строительстве» (Йошкар-Ола, 2008), на ежегодных научных конференциях профессорско-преподавательского состава МарГТУ. Результаты работы использованы в проектах, поддержанных грантами РФФИ: проект №07-01-0005 8-а «К решению проблемы визуализации и анализа 3D сцен, распознавания пространственных образов методами кватернионного исчисления», проект №08-01-12000-офи «Разработка методов и создание информационной технологии визуализации и сравнительного анализа сопряженных пространственных статических и динамических сцен».

Публикации

По теме диссертации опубликовано 11 печатных работ. Из них две — в журналах РАН, в том числе одна работа, опубликована в журнале, рекомендованном ВАК. Также получено одно свидетельство об официальной регистрации программы.

Структура и объем диссертации

Диссертационная работа включает в себя введение, 6 глав, заключение, список литературы из 70 наименований и одного приложения. Основная часть работы изложена на 196 страницах машинописного текста, содержит 90 рисунков, 7 таблиц.

6.6 Выводы 1

1. Разработан программный продукт для обработки трехмерных сцен и объектов, включающий в себя: а) пространственную низкочастотную фильтрацию точечного поля; б) построение на базе точечного поля векторного поля нормалей; в) аппроксимация участков поверхности анализируемых сцен с помощью плоскостей.

2. Разработанный алгоритм апробирован на моделях сцен близких по своим параметрам к реальным трехмерным объектам и поверхностям.

3. Решена прикладная задача выбора посадочной площадки для беспилотных летательных аппаратов.

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

ЗАКЛЮЧЕНИЕ

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

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

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

Основные теоретические и практические задачи, решенные в ходе диссертационного исследования:

1. Разработан новый устойчивый алгоритм упорядочения отметок ПГТО по его проволочной модели. Проволочная модель однозначно нумерует отметки ПГТО и представляет собой его аналитическое описание в виде последовательности кватернионов.

2. Синтезирован алгоритм распознавания ПГТО по результатам согласованной фильтрации кватернионного сигнала, задающего проволочную модель объекта. Исследована помехоустойчивость алгоритма распознавания 3D изображений при воздействии координатных шумов для алфавита из четырех близких по форме классов. Достаточно хорошие результаты правильного распознавания с вероятностью не ниже 0,95 достигаются при оптимальном пороге объединения граней и отношении сигнал/шум не менее 700. Исследована также зависимость вероятностей правильного распознавания ПГТО от величины порога объединения элементарных граней в одну грань. Выявлено наличие максимума вероятности правильного распознавания при изменении величины данного порога. Для рассмотренного случая соотношение вероятности правильного распознавания при оптимальном пороге и неоптимальном изменяется от 0,95 до 0,3.

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

4. Выполнена программная реализация алгоритма низкочастотной фильтрации трехмерного точечного поля, а также алгоритмов формирования векторного поля и визуализации точечного поля. Время работы программы при обработке трехмерного изображения объекта (количество точек от 300 до 600), заданного в виде пространственного точечного поля, на PC с процессором Intel Celeron 2,8 ГГц и ОЗУ 504 МБ при использовании неоптимизированной версии программы составляет 7-10 сек.

1. Введение в контурный анализ и его приложения к обработке изображений и сигналов / Я.А. Фурман, А.В. Кревецкий, А.К. Передреев и др.; Под. ред. Фурмана Я.А. М.:ФИЗМАТЛИТ, 2002. - 592 с.

2. Комплекснозначные и гиперкомплексные системы в задачах обработки многомерных сигналов / Я.А. Фурман, А.В. Кревецкий, А.А. Роженцов и др.; Под. ред. Фурмана Я.А. М.:ФИЗМАТЛИТ, 2004. - 456 с.

3. Ишлинский, А.Ю. Ориентация, гироскопы и инерциальная навигация / А.Ю. Ишлинский. -М.: Наука, 1976. 670 с.

4. Зиман, Я.Л. Алгоритмы опознавания звезд на снимках / Я.Л. Зиман, В.А. Красиков, Г.А. Алексешина // Аэрокосмические исследования Земли: Обработка видеоинформации на ЭВМ. М.: Наука, 1978. - С.79-86.

5. Фурман, Я.А. Метод идентификации светил в системах ориентации космических аппаратов на базе вторичных созвездий с уникальной монохроматичностью спектра формы/ Я.А. Фурман // Космонавтика и ракетостроение. 2001. №24. - С.47-65.

6. Шикин, Е.В. Компьютерная графика. Полигональные модели / Е.В. Шикин , А.В. Боресков. М.: ДИАЛОГ-МИФИ, 2001.-461 с.

7. Игнатенко, А. Геометрическое моделирование сплошных тел / А. Игнатенко // On-line журнал «Графика и мультимедиа». 2003— . — Режим доступа к журн.: http://graphics.cs.msu.ru/ru/library/3d/solidmodelling/index.html.

8. Игнатенко, А. Методы представления дискретных трехмерных данных// А. Игнатенко // On-line журнал «Графика и мультимедиа». 2003— . — Режим доступа к журн.: http://graphics.cs.msu.ru/ru/library/multiresrep/index.html.

9. Westover, L. Footprint Evaluation for Volume Rendering / L.Westover // Proc. SIGGRAPH. 1990. - P. 367 - 376.

10. Фор, А. Восприятие и распознавание образов / А. Фор М.: Машиностроение, 1989. - 272 с.

11. Макарова, О. Сканирование в третьем измерении / О. Макарова // Computerworld. 1997. - №40- . — Режим доступа к журн.: http://www.osp.rU/cw/l 997/40/24563.

12. Жигалов, К. Сканирование крупных объектов / К. Жигалов // Журн. Render Magazine. — 2006— . — Режим доступа к журн.: http://www.render.ru/books/showbook.php?bookid=:278.

13. Martti, M. An introduction to solid modeling / Martti Mantyla. Principles of Computer Science Series. Computer Science Press, College Park, Maryland, 1988. -401 p.

14. Chun-Fa, Ch. LDI Tree: A Hierarchical Representation for Image-Based Rendering / Chun-Fa Chang, Gary Bishop, Anselmo Lastra // Proc. SIGGRAPH. -1999. -P.291-298.

15. Levoy, M. The Use of Points as a Display Primitive / M. Levoy,T. Whitted // Technical Report TR 85-022, University of North Carolina at Chapel Hill. 1985. - 131. P

16. Levoy, M. The Digital Michelangelo Project: 3D Scanning of Large Statues / M. Levoy, K. Pulli, B. Curless // Proc. SIGGRAPH. 2000. - P. 131-144.

17. Laur, D. Hierarchical Splatting: A Progressive Refinement Algorithm for Volume Rendering / D. Laur, P. Hanrahan // Proc. SIGGRAPH. 1991. - P.285-288.

18. Curless, B. Volumetric Method for Building Complex Models from Range Images/В. Curless, M. Levoy//Proc. SIGGRAPH. 1996.-P.303-312.

19. Turk, G. Zippered Polygon Meshes from Range Images / G. Turk, M. Levoy // Proc. SIGGRAPH. 1994.- P.311-318.

20. Luebke, David P. A Developer's Survey of Polygonal Simplification Algorithms / David P. Luebke // IEEE Computer Graphics and Applications. 2001. -P. 24-35.

21. Xia, J.C. Adaptive Real-Time Level-of-Detail- Based Rendering for Polygonal Models / J.C. Xia, J. El-Sana, A. Varshney // IEEE Trans, on Visualization and Computer Graphics. 1997. -№2.-P. 171-183.

22. Luebke, D. Perceptually-Driven Simplification for Interactive Rendering / D. Luebke, B. Hallen // Proceedings of the 12th Eurographics Workshop on Rendering Techniques. 2001. - P.223-224.

23. Debevec, P. Introduction to Image-Based Modeling, Rendering, and Lighting / P. Debevec // SIGGRAPH. Course #39. 1999- . - Режим доступа к журн.: http://www.debevec.org/IBMR99.

24. McMillan, L. An Image-Based Approach to Three-Dimensional Computer Graphics: Ph.D. Dissertation. UNC Computer Science Technical Report TR97-013, University of North Carolina. 1997.

25. Grossman, J. Point Sample Rendering / J. Grossman, W. Dally // Proc. Eurographics Rendering Workshop. 1998. - P. 1-58.

26. Levoy, M. QSplat: A Multiresolution Point Rendering system for Large Meshes / M. Levoy, S. Rusinkiewicz // Proc. SIGGRAPH. 2000. - P.343-352.

27. Фурман, Я.А. Распознавание групповых точечных объектов в трехмерном пространстве / Я.А. Фурман, Д.Г. Хафизов // Автометрия. 2003. -№1. - С. 3-18.

28. Кревецкий, А.В. Кодирование и распознавание изображений множеств точечных объектов на основе моделей физических полей / А.В. Кревецкий, С.Е. Чесноков // Автометрия. 2002. - №3. - С. 80-89.

29. Фурман, Я.А. Визуализация изображений в трехмерных сценах: учеб. пособие / Я.А. Фурман. Марийск. гос. техн. ун-т. Йошкар-Ола, 2007. — 227 с.

30. Фурман, Я.А. Задание групповых точечных объектов и алгоритмов нумерации составляющих их точек/ Я.А. Фурман, Н.М. Кравцова // Цифровая обработка многомерных сигналов: Межвуз. сб. науч. тр./ МарПИ, ЛЭТИ, МАИ, МИРЭА. Йошкар-Ола, 1992. - С.25-31.

31. Кревецкий, А.В. Распознавание образов, заданных множеством характерных точек на плоскости / А.В. Кревецкий // Автометрия. 1999. - №2. -С.28-36.

32. Аркадьев, А.Г. Обучение машины классификации объектов / А.Г. Аркадьев, В.Н. Браверман. М.: Наука, 1971. - 192 с.

33. Анисимов, Б.В. Распознавание и цифровая обработка изображений / Б.В. Анисимов, В.Ф. Курганов, В.К. Злобин. М.: Высшая школа, 1983. - 295 с.

34. Хафизов, Д.Г. Упорядочение точек пространственного изображения группового точечного объекта на базе амплитудно-фазового представления / Д.Г. Хафизов // Автометрия. 2007. - №1. - С. 10-23.

35. Прэтт, У. Цифровая обработка изображений / У. Прэтт. М.: Мир, 1982.478 с.

36. Фу, К. Робототехника: пер. с англ./ К. Фу, Р. Гонсалес, К. Ли; под ред. В.Г. Градецкого. М.: Мир, 1989. - 624 с.

37. Рябинин, К.Б. Проволочная модель пространственного группового точечного объекта/ К.Б. Рябинин, Я.А. Фурман, М.И. Красильников // Автометрия. 2008. -№3. - С. 3-16.

38. Furman, Y.A. Processing of Quaternion Signals Specifying Spatially Located Group Point Objects / Y.A. Furman // Pattern Recognition and Image Analysis. 2002. — Vol.12. №2. - P.175-193.

39. Хафизов, Д.Г. Упорядочение точек пространственного изображения группового точечного объекта на базе амплитудно-фазового представления / Д.Г. Хафизов // Автометрия. 2007. - №1. - С. 10-23.

40. Фурман, Я.А. Комплекснозначные и кватернионные сигналы и подходы к их обработке / Я.А. Фурман, А.В. Кревецкий // Известия вузов. Приборостроение. 2006. - Т.49. - № 4. - С. 7-18.

41. Люстерник, Л.А. Выпуклые фигуры и многогранники / Л.А. Люстерник.- М.: ГИТТЛ, 1956. 212 с.

42. Шашкин, Ю.А. Эйлерова характеристика / Ю.А. Шашкин- М.: Наука, 1984.-93 с.

43. Фурман, Я.А. Нахождение параметров вращения пространственного группового точечного объекта по результатам его фильтрации / Я.А. Фурман, К.Б. Рябинин // Радиотехника и электроника. 2008. - Т.53. - №1. - С. 86-97.

44. Фурман, Я.А. Фильтрация кватернионных сигналов / Я.А. Фурман, Р.Г. Хафизов, А.А. Роженцов / Радиотехника и электроника. 2007. - Т52. - №1. - С. 42-50.

45. Furman, Y.A. Processing of Quaternion Signals Specifying Spatially Located Group Point Objects / Y.A. Furman // Pattern Recognition and Image Analysis. 2002. vol.12.-№2.-P.175.

46. Ефимов, H.B. Линейная алгебра и многомерная геометрия / Н.В.Ефимов, Э.Р. Розендорн. М.: Наука, 1974. - 528 с.

47. Казанова, Г. Векторная алгебра / Г. Казанова. М.: Мир, 1979. - 120 с.

48. Кантор, И.А. Гиперкомплексные числа / И.А. Кантор, А.С. Солодовников. М.: Наука, 1973. - 144 с.

49. Zucker, S.W. Three Dimensional Enge Operator / S.W. Zucker, R.A. Hummel // Intell, PAMI-3. 1981. - №.3. - P.324-331.

50. Фурман, Я.А. Визуализация изображений объектов в трехмерной точечной сцене / Я.А. Фурман, К.Б. Рябинин, Д.М. Ворожцов // Вестник вятского научного центра. 2006. - №1(7). - С.124-129.

51. Furman, Y. Image visualization of three dimensional scene objects after considering the results of surface sensing / Y. Furman // 8th International Conference on PATTERN RECOGNITION and IMAGE ANALYSIS: NEW INFORMATION

52. TECHNOLOGIES PRIA-8-2007, Conference Proceeding. Vol. 1. - Yoshkar-Ola, 2007.-P. 301-303.

53. Финкельштейн, М.И. Основы радиолокации: Учеб. для вузов гражд. авиации. / М. И. Финкельштейн. М.: Радио и связь, 1983. - 536 с.

54. Гуревич, И.Б. Дескриптивные алгебры изображений: определения и примеры / И.Б. Гуревич, Ю.И. Журавлев, Ю.Г. Сметанин // Автометрия. 1999. №6. - С.4-22.

55. Журавлев, Ю.И. Распознавание. Математические методы. Программная система. Практические применения / Ю.И. Журавлев, В.В. Рязанов, О.В. Сенько. М.: ФАЗИС, 2005. - 159 с.

56. Рябинин, К.Б. Оценка степени шероховатости подстилающей поверхности по результатам дистанционного зондирования / К.Б. Рябинин, Я.А. Фурман, М.И. Красильников // Сборник статей Всероссийского семинара по ГИС технологиям. Йошкар-Ола. - 2008. - С.61-66.

57. Рябинин, К.Б. Решение задачи выбора посадочной площадки беспилотного летательного аппарата на базе кватернионного анализа / К.Б. Рябинин // Вестник МарГТУ. 2008. - №1. - С.33-43.