автореферат диссертации по радиотехнике и связи, 05.12.13, диссертация на тему:Представление и эффективное кодирование трехмерных пространственных объектов для передачи по цифровым каналам связи

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

ЕЛКИН Сергей Леонидович

УДК 681.3.01 +539.22+528.854+519.218

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

Специальность: 05.12.13- Системы, сети и устройства телекоммуникаций

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

Ижевск 2004

Работа выполнена в ГОУ ВПО «Ижевский государственный технический университет» (ИжГТУ) и в Самарском филиале ОАО «Волга Телеком».

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

Заслуженный изобретатель Российской Федерации, доктор технических наук, профессор Лялин В.Е.

Официальные оппоненты:

доктор технических наук, профессор Лихтциндер Б.Я. (Поволжская государственная академия телекоммуникаций и информатики);

заслуженный деятель науки Удмуртской Республики, доктор технических наук, профессор Климов И.З. (ИжГТУ).

Ведущая организация: Центральный научно-исследовательский институт связи (г. Москва).

Защита состоится 21 января 2005 г. в 16 часов

на заседании диссертационного совета Д 212.065.04

в ИжГТУ по адресу: 426069, г. Ижевск, ул. Студенческая, 7, корп. 1

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

С диссертацией можно ознакомиться в библиотеке ИжГТУ. Автореферат разослан 20 декабря 2004 г.

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

Б.Я. Бендерский

ышоо

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

Актуальность темы. Реализация коммуникативных функций в глобальном аспекте требует решения двух задач - установления связи, т.е. обеспечения возможности двусторонней передачи информации, и обмена информацией (собственно коммуникативная функция).

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

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

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

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

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

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

Таким образом, актуальной яв я оперативной пе-

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

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

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

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

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

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

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

- формирование анимационных преобразований трехмерных пространственных объектов на основе комбинирования пространственных операций трансляций и ротаций тетрагональных регулярных сетей;

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

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

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

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

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

Методы исследования. В работе применялись теоретические и экспериментальные методы исследования.

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

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

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

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

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

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

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

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

- результаты исследования возможностей оперирования трехмерными пространственными объектами на основе использования непространственных

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

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

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

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

- программное обеспечение терминальной обработки информации о трехмерных пространственных объектах, обеспечивающее реализацию процессов их формообразования, анимации и проецирования;

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

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

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

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

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

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

ротаций, масштабирований и компрессий тетрагональных регулярных сетей;

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

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

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

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

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

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

Реализация и внедрение работы. Полученные результаты использованы и апробированы для опытно-проиэводственной эксплуатации системы терминальной обработки данных о пространственных объектах, их представления и кодирования для повышения коммуникативных возможностей в телекоммуникационных системах в Филиале в Удмуртской Республике ОАО «Волга Телеком».

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

Апробация работы. Результаты работы докладывались на российских и международных научно-технических конференциях и конгрессах: Международном Самарском симпозиуме телекоммуникаций для руководящих работников отрасли связи (Самара, 1996 - 2004); Международной конференции: International Conference «Intelligent Networks Services and Standards» & IFIP WG.6.7 (Москва, 1999); Российской научно-технической конференции «Приборостроение в XXI веке. Интеграция науки, образования и производства» (Ижевск, 2001); 32-й Научно-технической конференции ИжГТУ (Ижевск, 2002); Российской научно-технической конференции «Высокопроизводительные вычисления и технологии» (Ижевск, 2003); Международном симпозиуме «Надежность и качество» (Пенза, 2004); VI Международном конгрессе по математическому моделированию (Нижний Новгород, 2004); XXXI Международной конференции «Информационные технологии в науке, социологии, экономике и бизнесе» (Украина,

Крым, Ялта - Гурзуф, 2004); V Международной научно-технической конференции «Проблемы техники и технологии телекоммуникаций» (Самара, 2004).

Публикации. Основные научные результаты по теме диссертации опубликованы в 23 научных работах, в том числе: 1 депонированная рукопись (объемом 47 страниц), 4 статьи в научно-технических журналах и сборниках и 18 тезисов докладов на научно-технических конференциях.

Объем и структура диссертационной работы. Диссертация содержит введение, 4 главы и заключение, изложенные на 131 с. машинописного текста. В работу включены 28 рис., 12 табл., список литературы из 118 наименований и приложение, в котором представлен акт об использовании результатов работы.

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

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

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

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

Объемы памяти различных типов данных

Тип данных Формат данных -объем памяти F(MB)

Исходный Сжатый

1. Текст (1970 символов) txt - 0.002 rar - 0.001

2. Документ (A4, 1970 символов) doc - 0.02 rar - 0.003

3. Аудиоданные (чтение документа, 2 мин) wav - 2.4 шрЗ - 0.4

4. Изображение (A4,150 dpi) bmp - 6.7 tif-2.1

5. Видеоданные (2 мин) mpg-21

6. Интерактивная трехмерная модель (ИТМ) (32x104 точек, 65 х 104 TIN-элементов) wrl - 44

ний. Наконец, интерактивные трехмерные модели (ИТМ в форме треугольной нерегулярной сети - TIN; см. рис. 1) обладают наиболее эффективной воспринимаемостью, т.к. воспроизводят наиболее привычную для человека реальную или виртуальную среду. Такое понимание вполне отвечает максимуму коммуникационных возможностей в концепции информационной магистрали Б. Гейтса и обеспечивает качественно новую реализацию этих возможностей в телекоммуникационных системах.

Рис 1. Трехмерная ТШ-модель и фрагмент ее сети

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

Данные табл 1, отраженные в логарифмическом масштабе на рис 2, позволяют в первом приближении определить оценку перцептивной значимости-

Р,=

л VT

4н——

Гто

Ig^ro

где Т — индекс типа

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

Из полученных оценок следует актуальность решения задачи сокращения объемов памяти данных, обладающих наибо-Рис 2 Объемы памяти лее высокой перцептивной значимостью,

различных типов данных Решение этой задачи определяется возможностью создания более эффективных моделей данных.

Анализ различных моделей класса ИТМ показал, что в большинстве своем

они являются чрезвычайно ресурсозатратами и, что обусловлено низким уровнем представления элементов данных. Например, в TIN-модели элементом является треугольная грань (тригон), определяющая небольшой участок поверхности трехмерного объекта. Из рис. 1 видно, сколь разнообразны по размерам и форме элементы сети, и насколько нерегулярно они могут быть состыкованы друг с другом. Это создает большие вычислительные сложности при расчете сети и ее визуализации (рендеринге). Так, для трехмерного объекта на рис. 1 (участок горной местности), расчет сети на современном высокопроизводительном компьютере занимает несколько часов, а загрузка сети в браузер VRML — около получаса. Анализ ресурсных затрат на обработку таких моделей показывает, что высокая потребность ресурсов определяется в первую очередь слабой упорядоченностью массивов элементов пространственных объектов, что приводит к необходимости постоянного и многократного использования индексно-поисковых алгоритмов. Отсюда - большие временные затраты и большой объем потребляемой памяти на обработку информации.

Однако потребность решения задач указанного выше класса привела к тому, что были разработаны различные сетевые решения для передачи информационно емких данных. К их числу можно отнести, например, язык разметки гипертекста HTML, геоинформационный сервер SDE и язык разметки виртуальной реальности VRML. Упрощения при работе с графикой в HTML, основанные на использовании тегов и сжатых форматов графических данных, общеизвестны, и, хотя они приводят к существенному сжатию информации, однако качество предоставления этой информации зачастую уступает, например, обычным офисным графическим документам. Специализированный сервер для обработки цифровой картографической информации в геоинформационных системах (ГИС) построен на совершенно иных принципах представления и обработки информации, нежели базовая геоинформационная система Arclnfo. Здесь, также, имеют место упрощения - отказ от топологического векторного представления данных и переход к сегментированным растрам для их последующей передачи пользователям.

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

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

Во второй главе рассматривается тетрагональная регулярная сетевая мо-

Таблица 2

Количество элементов TIN-модели в примитивах VRML

Примитив Количество элементов

Бокс 12

Цилиндр 48

Конус 26

Сфера | 224

дель трехмерных пространственных объектов (ТТШ-модель). Модель предполагает, что в плоскости х()у укладывается прямоугольная сеть, состоящая из узлов и связей, образующих квадратные ячейки размером 1><1. Количество узлов сети - тхр, соответственно, количество ячеек - (ш-1)х(п-1). Сеть первоначально укладывается в первом квадранте таким образом, чтобы ее границы совпадали с осями координат, а узел, находящийся на пересечении этих границ, совпадал с началом координат (см. рис. 3).

Таким образом, состояние сети определяется тремя матрицами координат узлов сети размером т х п ■ X = [дгу У = [уч ], г = ],

где / = 1,2 ,...,т, у = 1,2,...,л, а элементы этих

матриц в начальном состоянии сети прини-

Рис. 3 Начальная укладка сети

мают значения: х„ = / -1, у - у -

1,4=0.

о , о

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

Образование поверхности моделируемого тела производится путем деформации сети - перемещения ее узлов на поверхность тела. При этом используется представление о полях деформаций пространства (ПДГТ), основанное на двух допущениях. А именно, для преобразований пространства х* =/х (*> У-21 У* = /у (*» У> 2* = /г (х, у, г) допускается обращение якобиана преобразования в ноль.

уо >1

уз У4

хО х1 лг2 хЗ х4

3* г

Л

лЛ хЗ х4 а) сеть

ш ш ш @ Ш

ш Е1 @

ш ш Ш ш

т 5з| й

0 0

в) индексация ячеек

г) индексация связей

Рис. 4 Сеть и индексации ее элементов

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

(х,у,г) в точку (*,у,¿) и позволяет говорить о деформации всего пространства: **=л: + <рх{х,у,г)

У* = У + <Ру{х,У,=) г* = г + (р,(х,у,г) Для описания формы тела сеть деформируется путем задания ГЩП в узлах сети. Таким образом, сеть покрывает

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

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

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

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

Поскольку якобиан преобразования может вырождаться в ноль, то в результате деформации возможна склейка узлов - совпадение конечных значений их координат. Склейки могут быть локальными, определяющими сингулярные элементы структуры поверхности тела (вершины и ребра), и нелокальными, описывающими замыкания сети на поверхности тела. Учет склеек узлов производится с помощью матриц инциденций размера 2т х п (для случая двухполюсного сфероидального замыкания, подобного разграфке поверхности сферы линиями параллелей и меридианов). С = [су где / = 1,2,...,2/и, ] = 1,2,...,/?, где

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

хО х1 х2 хЗ х4 х5 г ♦ . •.„ ». •

х1 хЪ х% х5

Рис 5. Индексация графа инциденций сети

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

Непространственные операции над сетями - склейки и замыкания (рис. 6, 7) сетей, сводятся к модификации их графов с помощью характеристических матриц

а) склейка одной связи (порядок узла

Т

I

типы я( 1), с(1) 2)

б) склейка двух связей - гипы п{2,1), с(2.0) (порядок узла - 3, порядок сипи - 2)

ЕСЕ

в) склейка двух связей - тип п(2,2) (порядок узла - 3)

г) склейка трех связей - тип «(3) (порядок узла - 4, порядок свяэей~2)

—4 »—■ уг 1 _ ас

г/

д) склейка четырех связей - т ип п{4) (порядок узла - 5, порядок связей - 2)

е) склейка двух связей - тип с(2,1) (порвдеж узлов-2, порядок снязи-2)

ж) склейка трех (четырех) связей - тип сО) (порядок узла - 4)

з) песегевая скнейка двух связей -тип а 1.2) (порчшж узла - 2, поряд ок связей - 2)

Рис. б. Локальные склейки узлов сети

- т £-_

''Ь

¡1—1—к—*—Ц| I

а) двухполюсное сферовдальное замыкание

24

6) однополюсное сфероидальное замыкание 8 ^

8 I

в) шшиндрическое (призматическое) замыкание

г) коническое (пирамидальное) замыкание

3 5

д) кубическое замыкание

е) тороидальное замыкание Рис. 7 Замыкания сети

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

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

Поскольку в конечном состоянии сети х^, у^ , узлы находятся на поверхности объекта, то координаты узлов сети определяются соответствующими значениями ПДП в узлах начального состояния сети: = х° + х*, Уу = у® + у*,

г^ = 2® + г*. Иначе говоря, деформация сети может быть описана оператором О, компоненты которого определяются матрицами Д. = [о^Д Оу = \с!уу\, Л, = а результат деформации имеет вид: ОХ = X + ВУ = К + Оу,

ог=г+вг.

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

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

Таким образом, можно говорить о «мягкой» и «жесткой» деформациях сети. «Мягкая» или регулярная деформация сети образуется в результате гладкого непрерывного (эластичного) преобразования пространства, при котором склейки узлов не производятся. В этом случае возможно получение деформированных ячеек сети в плоской трапецеидальной форме, что, по существу, означает возможность огранки гладких поверхностей четырехугольными плитками «Жесткая» или сингулярная деформация сети приводит к нарушению ис-

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

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

абсциссная(х)

ординатная (у)

-05 -15 -15 1 -25 -35 | -03 -05 -05 -05 -05

-05 -15 -15 | -25 -4 5 -15 -15 -15 -15 -15

-05 -15 -15 1 -25 45 1 -15 -15 -15 -15 -15

•03 -15 -15 1 -25 -25 -25 -25 -25 -25

аппликатная (г)

-15 ; -15 1 -15 -15 -15

-15 -05 -05 -15 -15

-13 •05 -05 -15 -15

-15 -15 -15 | -15 -15

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

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

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

Различные стадии процесса формообразования объектов показаны на рис. 9.

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

Полный набор таких ПДП включает в себя:

- трансляции Т(а,Ь);

- ротации Я,(а). Ях(а), Ях(а) (нижний индекс определяет ось вращения),

- масштабирование 5(к);

- компрессии - Сх(я) (нижний индекс определяет ось компрессии)

(^рл

а) формообразование сферы в проекции произвольного наблюдателя

б) формообразование сферы в проекции ^-наблюдателя

б) формообразование тора в проекции произвольного наблюдателя

г) формообразование тора в проекции г-наблюдателя Рис. 9. Процессы формообразования объектов в различных проекциях

Воздействие ПДП на тетрагональную регулярную сеть сводится к соответствующему перемещению ее узлов (см. рис 11). При этом также могут

иметь место новые склейки узлов. Формально перемещение узлов сводится к аддитивному преобразованию сети.

дяу = У+/>,+£>,,,

УУУ/ У 'УУУ

У/// 'УУУ

ууу/ 'УУУ

УУУ/ 'УУУ

ш

✓

а) трансляция

б) масштабирование

0]£>2 = 2 + £>г+£>]г.

в) ротация (о=30°)

Рис 10 ПДП различных видов движений

Промежуточные состояния сечи в этом случае определятся номерами кадров к в последовательности из заданного количества А^-Ч кадров.

4 -А 4 = & -4 ^

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

деляется направлением на него с углом поворота <р в горизонтальной плоскости хОу и углом возвышения ;// в вертикальной плоскости, проходящей через ось 0~. Вид координатных осей с позиции наблюдателя - на рис. 12.

При формировании проекций трехмерных пространственных объектов следует учитывать, что изменение положения наблюдателя эквивалентно противоположному изменению положения объектов, т.е вполне определенному их перемещению. Поэтому формирование новой проекции также можно представить в виде оператора деформации Д, соответствующего перемещению объекта в пространстве. Это допускает возможность использования единственной базовой проекции, в качестве которой можно выбрать проекцию на плоскость, параллельную плоскости ХУ с направлением наблюдения, противоположным направлению оси 2 (положение г-наблюдателя). В этом случае базовая проекция полностью определяется компонентами Г\ОХ = Х + Ох + Ои и 0,07 = 7+^+0,3,.

Решение задачи экранирования ячеек тетрагональной регулярной сети при проецировании выпуклых тел заключается в вычислении индикационной матрицы, которая определяет для каждой ячейки направление порядка обхода узлов ее проекции. Индикационная матрица размера (/и-1)х(и-1) имеет вид: Я = [гу ], где элемент матрицы г^ принимает значение 1 при направлении обхода

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

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

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

Рис. П. Композиция деформаций сети

О

л

а) направление на наблюдателя

б) вид координатных осей с позиции наблюдателя

Рис. 12. Позиция стандартного наблюдателя

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

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

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

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

Замена операции центрального проектирования операцией параллельною проектирования, путем локальной аппроксимации центральной проекции параллельной проекцией.

Замена операции параллельного проектирования операцией аффинного преобразования ранее полученной проекции.

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

Форсированное решение задачи экранирования (заслонений) элементов тетрагональной регулярной сети, а также самих трехмерных пространственных

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

Ускоренная анимация трехмерных сцен за счет применения полей деформаций пространства и комбинирования анимационных преобразований трансляций, ротаций и масштабирования.

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

НАУЧНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Фомичев СМ, Елкин С.Л Опыт эксплуатации элемента интеллектуальной сети в Удмуртии // В кн. Интеллектуальные сети: разработка стандартов и внедрение услуг: Труды международной конференции: Internation Conference "Intelligent Networks Services and Standards" & IFIP WG.6.7. Workshop "Smartnet" (Москва-1999).- M.: Диалог-МГУ, 1999,- С. 243-246.

2. Анализ причин появления ошибок в кодовых векторах, видов корректирующих тестовых сигналов и методов статистического анализа помех в цифровых информационных системах / Елкин С.Л, Лялин В.Е.; ИжГТУ, 2000- 47с. - Деп. в ВИНИТИ 2000, № 1038-В00.

3. Фомичев С.М, Елкин С.Л., Лялин В.Е Разработка оценок потерь достоверности многомерных сигналов в непрерывном и дискретном каналах связи. Часть 1. Математические модели // Приборостроение в XXI веке. Интеграция науки, образования и производства: Труды российской научно-технической конференции (Ижевск, 2001). ~ Ижевск: Изд-во ИжГТУ, 2001.- С.8-15.

4 Елкин С Л Устройства хранения данных в инфокоммуникационных системах // 32-я науч -техн. конф. ИжГТУ: Тез докл. - Ижевск: Изд-во ИжГТУ, 2002. - С 47-49.

5 Григорьев ЕВ, Елкин С Л, Пивоваров И В Повышение производительности вычислений при обработке моделей данных трехмерных пространственных объектов // Высокопроизводительные вычисления и технологии (ВВТ-2003): Тр Российской науч.-техн. конф. - Ижевск: Изд. дом УдГУ, 2003. - С. 46-54.

6. Елкин С Л Метод компаративного преобразования при обработке сигналов в системах контроля качества // Надежность и качество: Труды международного симпозиума. Ч. II / Под. ред. Н.К. Юркова - Пенза: Изд-во Пенз. гос. унта, 2004.-С. 452.

7. Лялин В Е., Елкин С.Л Программное обеспечение спектрального анализа сигналов в рамках модели авторегрессии скользящего усреднения // Надежность и качество: Труды международного симпозиума. Ч. II / Под. ред. Н.К. Юркова - Пенза: Изд-во Пенз. гос. ун-та, 2004. - С. 477 - 480.

8. Lyalin V.E, ЕШп S.L. Coding of signals on the basis of comparative transformation // Тез. докл. - Нижний Новгород: Изд-во Нижегородского госуниверситета, 2004. - С. 255.

9 Murynov А I, Elkin S L. The transformation of the comparative signals to digital communication channels // Тез. докл. - Нижний Новгород: Изд-во Нижегородского госуниверситета, 2004. - С. 257.

10. Галичанин А А , Елкин С Л Влияние шума на качество распознавания структурных элементов графического изображения на основе центроидного преобразования // Информационные технологии в науке, социологии, экономике и бизнесе: Материалы 31 Междунар. конф. - Украина, Крым, Ялта - Гурзуф : Прилож. к журн. «Открытое образование», 2004,- С. 53 -55.

11. Елкин C.JJ., Лялин В.Е. Перцептивная значимость и когнитивные модели данных при передаче информации // Информационные технологии в науке, социологии, экономике и бизнесе: Материалы 31 Междунар. конф. - Украина, Крым, Ялта - Гурзуф.: Прилож. к журн. «Открытое образование», 2004,- С. 80-81.

12. Елкин С.Л. Процессы формообразования и анимации 3D-сцен на основе использования полей деформаций пространства // Информационные технологии в науке, социологии, экономике и бизнесе: Материалы 31 Междунар. конф. - Украина, Крым, Ялта - Гурзуф.: Прилож. к журн. «Открытое образование», 2004,-С. 82-84.

13. Елкин СЛ., Мурынов А.И. Тетрагональная регулярная пространственная сеть как модель описания геометрико-топологических пространственных объектов размерности 3 // Информационные технологии в науке, социологии, экономике и бизнесе: Материалы 31 Междунар. конф - Украина, Крым, Ялта -Гурзуф.: Прилож. к журн. «Открытое образование», 2004.- С. 84 - 86.

14. Елкин С.Л Решение проблемы согласования перцептивной значимости передаваемой информации // Математическое моделирование и интеллектуальные системы: Сб. науч. тр. ИжГТУ,- 2004.- №1(3).- Ижевск: Изд-во ИЭ УрО РАН, 2004-С. 9-10.

15. Елкин С.Л Построение тетрагональной регулярной пространственно деформируемой сетевой модели трехмерных объектов // Математическое моделирование и интеллектуальные системы: Сб. науч. тр. ИжГТУ.- 2004,- №1(3).-Ижевск: Изд-во ИЭ УрО РАН, 2004.- С. 27-29.

16. Галичанин A.A., Елкин С.Л. Точность восстановления линейных элементов структуры графических изображений при наличии фонового шума // Математическое моделирование и интеллектуальные системы: Сб. науч. тр. ИжГТУ.- 2004,- №1(3).- Ижевск: Изд-во ИЭ УрО РАН, 2004,- С. 59 - 62.

17. Елкин С.Л., Мурынов А.И. Формирование в телекоммуникационных сетях интегрированного перцептивно - реалистического информационного пространства // Инфокоммуникационные технологии Глобального информационного общества: Сб. трудов II Ежегодной Международной научно-практич. конф. - М.: МАС, 2004. - С.73 - 80.

18. Елкин С.Л., Лялин В.Е. Моделирование трехмерных объектов на основе тетрагональной регулярной пространственно деформируемой сети // Проблемы техники и технологии телекоммуникаций: Материалы Пятой Междунар. научи -техн. конф,- Самара: Изд-во ПГАТИ, 2004.- С. 39-41.

19. Елкин С Л. Геометрические и топологические особенности формирования поверхностей тел в интерактивных трехмерных моделях // Проблемы техники и технологии телекоммуникаций: Материалы Пятой Междунар. на-учн.-техн. конф,- Самара: Изд-во ПГАТИ, 2004,- С. 72 - 74.

• 20. Елкин С.Л, Мурынов А.И Процессы формообразования, проецирования и анимации объектов в интерактивных динамических трехмерных моделях // Про-

Щ-1009

блемы техники и технологии телекоммуникаций: Материалы Пятой Междунар. научн.-техн. конф.- Самара: Изд-во ПГАТИ, 2004.- С. 75 - 77.

21. Елкин СЛ., Мурынов А И. Представление процессов формообразования, проецирования и анимации тел посредством Т1Ш-модели // Известия Тульского гос. университета. Серия «Математика. Механика. Информатика» -Тула: Изд-во ТТУ, 2004. - Выпуск 10. - №3. - С. 41 - 43.

22. Елкин С.Л., Лялин В.Е. Особенности формирования поверхностей объектов на основе ПШ-модели // Известия Тульского -ос. университета. Серия «Математика. Механика. Информатика» - Тула: Изд-во ТГУ, 2004. - Выпуск 10. -№3.-С.48-50.

23. Елкин С.Л. Анимирование объектов ЗБ-сцен в интерактивных динамических трехмерных моделях // Известия Тульского гос. университета. Серия «Математика. Механика. Информатика» - Тула: Изд-во ТГУ, 2004. - Выпуск 10.

-№3.-С. 54-56.

СЛ. Елкин

РНБ Русский фонд

Лицензия ЛР №020764 от 29.04.98 г

Подписано в печать 20.12.2004 Формат 60x84 1/16. Отпечатано на ризографе. Уч.-изд.л. 1,62 Усл. печ.л. 1,39. Тираж 100 экз Заказ № 307/2.

Издательство Института экономики УрО РАН 620014, г. Екатеринбург, ул. Московская - 29

Список сокращений.

Введение.

Глава 1. Задачи представления и эффективного кодирования трехмерных пространственных объектов.

1.1. Информационная емкость и перцептивная значимость данных.

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

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

1.4. Сетевые решения в интерактивном трехмерном моделировании

1.5. Выводы и постановка цели и задач исследований.

Глава 2. Тетрагональная регулярная сетевая модель трехмерных пространственных объектов.

2.1. Поля деформаций пространства.

2.2. Тетрагональная регулярная сеть.

2.3. Характеристики сетей.

2.4. Непространственные операции над сетями.

2.4.1. Локальные склейки узлов.

2.4.2. Замыкания сети.

2.4.3. Операции форматирования сетей.

2.5. Пространственные операции над сетями.

2.6. Полученные результаты и выводы.

Глава 3. Процессы формообразования, анимации и проецирования трехмерных пространственных объектов.

3.1. Формообразование и деформации объектов.

3.2. Пространственные трансформации трехмерных сцен.

3.3. Проецирование, визуализация и рендеринг трехмерных пространственных объектов.

3.4. Полученные результаты и выводы.

Глава 4. Представление и кодирование трехмерных пространственных объектов в телекоммуникационных системах

4.1. Информационная емкость данных и производительность вычислительных процессов.

4.2. Алгоритмические решения и программное обеспечение.

4.3. Экспериментальные данные и результаты.

4.4. Полученные результаты и выводы.

Актуальность темы. Реализация коммуникативных функций в глобальном аспекте требует решения двух задач - установления связи, т.е. обеспечения возможности двусторонней передачи информации, и обмена информацией (собственно коммуникативная функция).

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

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

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

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

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

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

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

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

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

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

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

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

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

- формирование анимационных преобразований трехмерных пространственных объектов на основе комбинирования пространственных операций трансляций и ротаций тетрагональных регулярных сетей;

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

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

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

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

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

Методы исследования. В работе применялись теоретические и экспериментальные методы исследования.

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

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

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

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

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

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

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

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

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

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

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

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

- программное обеспечение терминальной обработки информации о трехмерных пространственных объектах, обеспечивающее реализацию процессов их формообразования, анимации и проецирования;

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

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

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

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

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

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

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

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

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

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

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

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

Реализация и внедрение работы. Полученные результаты использованы и апробированы для опытно-проиэводственной эксплуатации системы терминальной обработки данных о пространственных объектах, их представления и кодирования для повышения коммуникативных возможностей в телекоммуникационных системах в Филиале в Удмуртской Республике ОАО «Волга Телеком».

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

Апробация работы. Результаты работы докладывались на российских и международных научно-технических конференциях и конгрессах: Международном Самарском симпозиуме телекоммуникаций для руководящих работников отрасли связи (Самара, 1996 - 2004); Международной конференции: International Conference «Intelligent Networks Services and Standards» & IFIP WG.6.7 (Москва, 1999); Российской научно-технической конференции «Приборостроение в XXI веке. Интеграция науки, образования и производства» (Ижевск, 2001); 32-й Научно-технической конференции ИжГТУ (Ижевск, 2002); Российской научно-технической конференции «Высокопроизводительные вычисления и технологии» (Ижевск, 2003); Международном симпозиуме «Надежность и качество» (Пенза, 2004); VI Международном конгрессе по математическому моделированию (Нижний Новгород, 2004); XXXI Международной конференции «Информационные технологии в науке, социологии, экономике и бизнесе» (Украина, Крым, Ялта - Гурзуф, 2004); V Международной научно-технической конференции «Проблемы техники и технологии телекоммуникаций» (Самара, 2004).

Публикации. Основные научные результаты по теме диссертации опубликованы в 23 научных работах, в том числе: 1 депонированная рукопись (объемом 47 страниц), 4 статьи в научно-технических журналах и сборниках и 18 тезисов докладов на научно-технических конференциях.

Объем и структура диссертационной работы. Диссертация содержит введение, 4 главы и заключение, изложенные на 131 с. машинописного текста. В работу включены 28 рис., 12 табл., список литературы из 118 наименований и приложение, в котором представлен акт об использовании результатов работы.

1.5. Выводы и постановка цели и задач исследований

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

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

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

- разработать новые эффективные модели трехмерных пространственных объектов;

- исследовать возможности оперирования трехмерными пространственными объектами на основе использования разработанных моделей;

- построить способы описания процессов формообразования, анимации и проецирования трехмерных пространственных объектов на базе операций над ними;

- разработать алгоритм проецирования и визуализация трехмерных пространственных объектов;

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

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

Глава 2. ТЕТРАГОНАЛЬНАЯ РЕГУЛЯРНАЯ СЕТЕВАЯ МОДЕЛЬ ТРЕХМЕРНЫХ ПРОСТРАНСТВЕННЫХ ОБЪЕКТОВ

Ниже рассматривается тетрагональная регулярная сетевая модель трехмерных пространственных объектов (модель TRN) [18,25,30,54]. При построении модели используется представление о полях деформаций пространства [60,61]. Описаны свойства и характеристики модели, а также непространственные и пространственные операции над моделями. Полученные теоретические результаты являются основой для разработки методов оперирования моделями данных трехмерных пространственных объектов, их представления и кодирования, описанных в главе 3.

Следует отметить, что сама по себе прямоугольная сеть как модель данных трехмерных объектов не является новой. Более того, использование таких моделей исторически предшествовало разработке более развитых моделей данных, в большей степени связанных с визуально реалистичным рендерингом, с появлением которых модель прямоугольной сети отошла на второй план [15,35,42-45,94].

Однако, как видно из описанных ниже результатов, потенциал регулярных сетевых моделей далеко не исчерпан. Более детальное рассмотрение этих моделей позволяет вскрыть такие их свойства и особенности, которые придают им новые качества и позволяют эффективно использовать их при передаче перцептивно значимой информации в телекоммуникационных системах [19,27,31]. Причем основной эффект здесь достигается именно за счет регулярности таких моделей.

2.1. Поля деформаций пространства

Построение модели TRN основано на использовании преобразований пространства. Преобразование, переводящее точку пространства t = (х, y,z) в другую точку t* = (x*,y*,z*), имеет вид [2,39,41]: fy{x,y,z). (2.1)

У=fz{x>y>z)

Для того, чтобы соблюдалось условие взаимной однозначности преобразования, необходимо, чтобы якобиан преобразования не обращался в ноль ни в одной точке пространства [39,41]: х dfy Of, дх дх дх х dfy ду ду ду х dfy dz dz dz

В этом случае существует обратное преобразование, переводящее точку t* = {x*,y*,z*} в точку t = {x,y,z). Таким образом, информация о первоначальных координатах любой точки t = (x,y,z) потенциально не утрачена и восстанавливается с помощью обратного преобразования.

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

При построении модели TRN используются два нетипичных представления [18,25,30,54]. Первое представление состоит в том, допускается обращение якобиана преобразования в ноль (несоблюдение условия (2.2)) в некоторых областях пространства (характер этих областей определен в разд. 2.4). Тем самым, допускается «склейка» точек пространства и, соответственно, необратимая потеря информации о первоначальных координатах точек этих областей [39,41].

Второе представление заключается в изменении формы преобразования, которое представляется в виде смещений точек пространства [60,61]. Эта форма описывает преобразование как результат перемещения точки t = (jc,y,z) в точку

Гп гчЯл С К А Я

БИВЛЯОТШ t* = (x*,y*,z*) и позволяет говорить о деформации всего пространства: х* = x + <px(x,y,z)

Ув = У+ <Ру{х,У,z)- (2.3) z* = z + ^z(x,y,z)

Следует отметить, что такая форма представления преобразований является нетипичной: «При рассмотрении отображений вместо того, чтобы говорить «точка М отображается в точку N», сплошь и рядом говорят «точка М переходит в N». Хотя она никуда не переходит. Нельзя двигать точки пространства; тем не менее, наглядно отображения нередко представляют как перемещение и деформацию фигуры, как результат перемещения ее точек» [2, с.220]. Однако, как будет видно из дальнейшего, именно такая форма может быть эффективно использована в модели TRN.

Выражение (2.3) фактически описывает векторное поле перемещений точек пространства - поле деформаций пространства (ПДП) [60,61]. А именно, в каждой точке пространства t = (x,y,z) определен вектор его деформации: d = d{x,y,z)=\(px{xiy,z),(py{x,y,z),(pz(xiy,z)). (2.4)

Тогда результат преобразования имеет вид: t* = t + d. (2.5)

Наглядный вид некоторых типичных ПДП (см.разд. 2.5) приведен на рис. 2.1.

V//S?///. ////////

У///*///. V//SW/.

X -> м ж. Л а а) трансляция б) масштабирование в) ротация (о=30°)

Рис. 2.1. Поля деформаций пространства

На рисунке первый вид ПДП (рис.2Да) представляет собой трансляцию -постоянное для всех точек пространства смещение на величину заданного вектора, ортогонального оси z, второй вид (рис.2.1б) - масштабирование - равномерное по всем направлениям, ортогональным оси z, растяжение пространства в заданное число раз, третий вид (рис.2.1в) - ротация — поворот пространства вокруг оси z на величину заданного угла.

2.2. Тетрагональная регулярная сеть

Модель тетрагональной регулярной сети (TRN-модель) предполагает, что в плоскости хОу укладывается прямоугольная сеть, состоящая из узлов и связей, образующих квадратные ячейки размером 1x1. Количество узлов сети - mxn, соответственно, количество ячеек - (m-l)x(n-l). Сеть первоначально укладывается в первом квадранте таким образом, чтобы ее границы совпадали с осями координат, а узел, находящийся на пересечении этих границ, совпадал с началом координат (см. рис. 2.26). дсО х1 х2 хЗ х4 х5 а) сеть

Рис. 2.2. Тетрагональная регулярная сеть б) начальное пространственное в) индексация узлов сети состояние сети

Таким образом, состояние сети определяется тремя матрицами координат узлов сети размером тхп: у, (ад где i = 1,2,.,т, j = 1,2,.,и, а элементы этих матриц в начальном состоянии сети принимают значения: 0-1 о -1 о Л

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

Образование поверхности моделируемого тела производится путем деформации сети - перемещения ее узлов на поверхность тела. При этом используется представление о полях деформаций пространства (ПДП), основанное на описанных в разд. 2.1 двух допущениях. А именно, для преобразований пространства: fx (*> у» 4 у* = fy (*> у 4z*=fz (*> у» z) (2-7) допускается обращение якобиана преобразования в ноль.

Второе допущение - изменение формы преобразования, представляемого в виде смещений точек пространства, что описывает преобразование как результат перемещения точки {x,y,z) в точку (*W) и позволяет говорить о де

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

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

4-xl+xh у* = У$+УЬ =zl+zb (2-8)

Иначе говоря, деформация сети может быть описана оператором D, компоненты которого определяются матрицами:

Dx = [dxij\, Dy = [dyij\, Dz = [dzij j, (2.9) а результат деформации имеет вид:

DX = X + Dx, DY = Y + Dy, DZ = Z + Dz. (2.10)

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

2.3. Характеристики сетей

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

Наиболее просто выглядит производная от индексации узлов индексация ячеек сети, показанная на рис. 2.4а. Как видно из рисунка, индекс ячейки совпадает с индексом левого верхнего ее узла (см. рис. 2.2в).

Кроме того, важной характеристикой сети является граф инциденций [33,66], который может быть получен путем индексации связей сети (см. рис. 2.46) и последующего построения производного графа, узлы которого соответствуют связям исходного графа сети, а связи между узлами прокладываются при наличии смежности соответствующих связей исходного графа, т.е. в том случае, когда они опираются на одну и ту же вершину. Из рисунка видно, что производный граф инциденций также образует регулярную сеть. Однако эта сеть не является тетрагональной. Каждый элемент этой сети имеет связи с шестью другими элементами, поэтому сеть является гексагональной. Это однако не является помехой для установки такой индексации элементов сети инциденций, которая имела бы тетрагональный вид. Индексация такого вида формируется при последовательной индексации сначала горизонтальных связей в строке матрицы, а затем - вертикальных связей в той же строке матрицы (см. рис. 2.4в. Затем таким же образом производится индексация элементов следующей строки матрицы и т.д. ш ш ш ш о ш 11 ш т из ш ш 13 ш ш ш ш ш

ИЗ ш ш ш хО jcI л2 JC3 jc4 jc5 z s

I ч '. ч 1 X.'l

I > I > I > 1 > ' 1 i ' 1 i * X

6) индексация связей z JtO jcl x2 дсЗ дс4 jc5 в) индексация узлов графа инциденций

Рис. 2.4. Индексация элементов сети

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

2.4. Непространственные операции над сетями

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

2.4.1. Локальные склейки узлов

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

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

С = |сД (2.11) где i = 1,2,.,2m, j = 1,2,.,,п, а элементы матрицы с{- принимают значение 1, если соответствующая связь подвергается склейке, или 0 - при отсутствии склейки.

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

1- -1 —

4 1 > < t ' 1 \д

1 к' р Г а) склейка одной связи - типы «(1), с(Х) б) склейка двух связей - типы п{2,1), с(2,0) (порядок узла - 2; 2 вида) (порядок узла - 3; порядок связи - 2; 4 вида)

Л \з \ \4

Ч t 2/

7\ в) склейка двух связей - тип /7(2,2) (порядок узла - 3; 2 вида) г) склейка трех связей - тип л(3) (порядок узла - 4; порядок связей - 2; 4 вида) л р ъ N г i t i У2 Р^Ч К

1 5/ Ч 1 Л t ч 1 i t ч г д) склейка четырех связей - тип «(4) е) склейка двух связей - тип с(2,1) порядок узла - 5; порядок связей - 2; f вид) (порядок узлов - 2; порядок связи - 2; 2 вида) i i k V 9

-5 . r\ 1 ж) склейка ipex (четырех) связей - тип с(3) з) несетевая склейка двух связей - тип 1,2) (порядок узла - 4; 1 вид) (порядок узла - 2; порядок связей - 2; 2 вида)

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

1. Авраамова О.Д. Язык VRML. - М.: ДИАЛОГ-МИФИ, 2000. - 288с.

2. Александров А.Д., Нецветаев Н.Ю. Геометрия. М.: Наука, 1990. - 672с.

3. Анализ причин появления ошибок в кодовых векторах, видов корректирующих тестовых сигналов и методов статистического анализа помех в цифровых информационных системах / Елкин С.Л., Лялин В.Е.; ИжГТУ, 2000- 47с. Деп. в ВИНИТИ 2000, № 1038-В00.

4. Артюшенко В.М., Шелухин О.И., Афонин М.Ю. Цифровое сжатие видеоинформации и звука. М.: Дашков и К0, 2003.-426с.

5. Башков Е.А., Казак А.Б. Генераторы изображения для авиатренажеров // Зарубежная радиоэлектроника, 1989, № 8. С. 60-68.

6. Берлянт A.M. Геоиконика. М.: Астрея, 1996. - 208с.

7. Берлянт A.M. Геосемиотика и визуализация геоизображений // Инф. бюлл. ГИС-Ассоциации, 2002, № 1(33)-2(34). С. 27-30.

8. Берлянт A.M. Образ пространства: Карта и информация. М.: Мысль, 1986.-240с.

9. Бобков В.А., Кислюк О.С., ХамидуллинА.В. Формирование растровых графических изображений пространственных объектов, построенных методом конструктивной геометрии // Программирование, 1989, № 3. С. 88-92.

10. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. М.: ДИАЛОГ-МИФИ, 2003.-384с.

11. Галичанин А.А., Елкин С.Л. Точность восстановления линейных элементов структуры графических изображений при наличии фонового шума //

12. Математическое моделирование и интеллектуальные системы: Сб. науч. тр. ИжГТУ.- 2004.- №1(3).- Ижевск: Изд-во ИЭ УрО РАН, 2004.- С. 59 62.

13. Гасилов В.А., Карагичев А.Б., Карташева E.JI. идр. Интерактивная система генерации тетраэдральных сеток ITERA // Труды IV Междунар. конф. по математическому моделированию. М.: Станкин, 2001. - С. 84-91.

14. Гейтс Б. Дорога в будущее. М.: ZmeiKa Co., 1999. - 318с.

15. Гилой В.А. Интерактивная машинная графика. М.: Мир, 1981. - 380с.

16. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976.-512с.

17. Елкин C.JI Построение тетрагональной регулярной пространственно деформируемой сетевой модели трехмерных объектов // Математическое моделирование и интеллектуальные системы: Сб. науч. тр. ИжГТУ.- 2004.- №1(3).-Ижевск: Изд-во ИЭ УрО РАН, 2004.- С. 27 29.

18. Елкин C.JI Решение проблемы согласования перцептивной значимости передаваемой информации // Математическое моделирование и интеллектуальные системы: Сб. науч. тр. ИжГТУ.- 2004.- №1(3).- Ижевск: Изд-во ИЭ УрО РАН, 2004.- С. 9-10.

19. Елкин C.JI. Анимирование объектов ЗЭ-сцен в интерактивных динамических трехмерных моделях // Известия Тульского гос. университета. Серия «Математика. Механика. Информатика» Тула: Изд-во ТГУ, 2004. - Выпуск 10. - №3. - С. 54-56.

20. Елкин С.JI. Метод компаративного преобразования при обработке сигналов в системах контроля качества // Надежность и качество: Труды международного симпозиума. Ч. II / Под. ред. Н.К. Юркова Пенза: Изд-во Пенз. гос. ун-та, 2004. - С. 452.

21. Елкин C.JI. Устройства хранения данных в инфокоммуникационных системах // 32-я науч.-техн. конф. ИжГТУ: Тез. докл. Ижевск: Изд-во ИжГТУ, 2002. - С. 47-49.

22. Елкин С.Л., Лялин В.Е. Особенности формирования поверхностей объектов на основе TRN-модели // Известия Тульского гос. университета. Серия «Математика. Механика. Информатика» Тула: Изд-во ТГУ, 2004. - Выпуск 10. -№3.-С. 48-50.

23. Желтов С.Ю., Инвалев А.С., Кирьяков К.Р., Степанов А.А. Особенности реализации 3D ГИС // Инф. бюлл. ГИС-Ассоциации, 1997, № 5(12). С. 52-67.

24. Заков А.А. Основы теории графов. М.: Наука, 1987.

25. Зенкин А.А. Когнитивная компьютерная графика. М.: Наука, 1991. - 192с.

26. Иванов В.П., Батраков А.С. Трехмерная компьютерная графика. М.: Радио и связь, 1995. - 224с.

27. Казанцев Н.Н., Флейс М.Э, Яровых В.Б. Проекционные преобразования в геоинформационных системах // ГИС-обозрение, 1995, № 2 (5) (лето-95). -С. 23-25.

28. Клименко С.В., Кочин В.Н. Об одном способе изображения поверхностей в машиной графике // Программирование, 1981, № 2. С. 68-71.

29. Ковалев A.M., Талныкин Э.А. Машинный синтез визуальной обстановки // Автометрия, 1984, № 4. С. 78-83.

30. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. М.: Наука, 1981. — 544с.

31. Коновалова Н.В., Капралов Е.Г. Введение в ГИС. М.: Библион, 1997. - 160с.

32. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. М.: Наука, 1979. 720с.

33. Королев Ю. Тенденции развития моделей данных в ГИС и их значения для ГИС-приложений // ARCREVIEW: современные информационные технологии. 1997, № 3. - С. 15. - 1997, № 2. - С. 2.

34. Королев Ю.К. Модели данных геоинформационных систем // Инф. бюлл. ГИС-Ассоциации, 1998, № 3(15). С. 68-70.

35. Королев Ю.К. Общая геоинформатика. Ч. 1. Теоретическая геоинформатика. Вып. 1. М.: Дата+, 1998. - 119с.

36. Корриган Дж. Компьютерная графика. М.: Энтроп, 1995. - 352с.

37. Кошель С.М., Мусин О.Р. Методы цифрового моделирования: кри-нинг и радиальная интерполяция // Инф. бюлл. ГИС-Ассоциации, 2000, № 4(26). С. 30-33. - № 5(27). - С. 28-30. - 2001, № 1(28). - С. 40-43. - № 2(29)-3(30).-С. 23-26.

38. Кошкарев А.В., Сорокин А.Д. Форматы и стандарты цифровой пространственной информации // ГИС-обозрение, 1995, № 4 (весна-95). С. 40-45.

39. Кошкарев А.В., Тикунов B.C. Геоинформатика М.: Картгеоцентр -Геодезиздат, 1993. - 213с.

40. Кринов П.С., Поляков С.В., Якобовский М.В. Визуализация в распределенных вычислительных системах трехмерных расчетов // Труды IV Междунар. конф. по математическому моделированию. М.: Станкин, 2001. — С. 126-133.

41. Лихтциндер Б.Я. Автоматизация расчета характеристик трафика в сетях ATM // Инфокоммуникационные технологии, Т. 1, № 1, 2003. с.47-53.

42. Лихтциндер Б.Я., Кузякин М.А., Росляков А.В., Фомичев С.М. Интеллектуальные сети связи. М.: Эко-Тренц, 2000. - 206с.

43. Марр Д. Зрение: Информационный подход к изучению представления и обработки зрительных образов. М.: Радио и связь, 1987. - 400с.

44. Математическая энциклопедия. Т. 4. — М.: Советская Энциклопедия, 1984.- 1216с.

45. Машинная графика и вычислительная геометрия в задачах машиностроения. М.: НС по КП «Кибернетика» при АН СССР, 1989. - 178с.

46. Минский М. Структура для представления знания // Психология машинного зрения / Под ред. П. Уинстона. М.: Мир, 1978. - С. 249-338.

47. Мураховский В.И. Компьютерная графика. -М.: АСТ-Пресс СКД, 202с.

48. Мурынов А.И. Конфигурационные модели изображений и оценка параметров структурных элементов их деталей // Химическая физика и мезоско-пия. Т.4, 2002, №1. С. 128-144.

49. Мусин О.Р. Диаграмма Вороного и триангуляция Делоне // Инф. бюлл. ГИС-Ассоциации, 1999, № 2(19). С. 51-54.

50. Мусин О.Р. Цифровые модели для ГИС // Инф. бюлл. ГИС-Ассоциации, 1998, № 4(16). С. 30-33. - № 5(17). - С. 28-30.

51. Ньюмен У., Спрулл Р. Основы интерактивной машинной графики. -М.: Мир, 1976.-562с.

52. Огарков В.М. От триангуляции Делоне к управляемой триангуляции (о настоящих моделях рельефа в ГИС) // Инф. бюлл. ГИС-Ассоциации, 1999, № 2(19). С. 55-58. - № 5(17). - С. 28-30.

53. Оре О. Теория графов: М.: Наука, 1968. - 352с.

54. Павлидис Т. Алгоритмы машинной графики и обработки изображений. М.: Радио и связь, 1986. - 400с.

55. Петров М.Н., Молочков В.П. Компьютерная графика. СПб.: Питер, 2002. - 736с.

56. Полшков Е.А. Особенности ГИС-технологий при математическом моделировании геоэкологических объектов // Инф. бюлл. ГИС-Ассоциации, 1998, №4(16).-С. 28-30.

57. Полшков Е.А. Отображение трехмерных математических моделей геоэкологических объектов в геоинформационной системе // Инф. бюлл. ГИС-Ассоциации, 1997, № 2(9). С. 65-67. - № 3(10). - С. 42-44.

58. Пономаренко С.И. Пиксел и вектор. Принципы цифровой графики. -СПб.: БХВ-Петербург, 2002. 496с.

59. Прэтт У. Цифровая обработка изображений. Кн. 1. - М.: Мир, 1982. -312с. - Кн. 2. - М.: Мир, 1982. - 480с.

60. Психология машинного зрения. М.: Мир, 1978. - 448с.

61. Роджерс Д. Алгоритмические основы машинной графики. — М.: Мир, 1989.-512с.

62. Роджерс Д., Адаме Дж. Математические основы машинной графики. — М.: Машиностроение, 1980. 240с.

63. Слободецкий И.М. 3D Studio МАХ 6.0. М.: Познавательная книга-пресс, 2004. - 384с.

64. Талныкин Э.А. Внутренний язык для описания визуальных моделей // Автометрия, 1985, № 4. С. 44-49.

65. Титтел Э., Сандерс К., Скотт Ч., Вольф П. Создание VRML-миров. -Киев: BHV, 1997.-320с.

66. Тихомиров Ю.В. Программирование трехмерной графики. — СПб.: БХВ-Петербург, 2002. 304с.

67. Файн B.C. Алгоритмическое моделирование формообразования. М.: Наука, 1975. - 178с.

68. Фокс А., Пратт М. Вычислительная геометрия. Применение в проектировании и на производстве. М.: Мир, 1982. - 304с.

69. Фоли Дж., ван Дэм А. Основы интерактивной машинной графики. Ч. 1.-М.: Мир, 1985. - 436с. - Ч. 2.-М.:Мир, 1985.-564с.

70. Хермен Г. Восстановление изображений по проекциям. М.: Мир, 1983.-349с.

71. Хорн Б.К. Зрение роботов. М.: Мир, 1989. - 488с.

72. Цветков В.Я. Геоинформационные системы и технологии. М.: Финансы и статистика, 1998. - 288с.

73. Цветков В Л. Третье измерение в ГИС // ГИС-обозрение, 1997, № 2. С. 22-26.

74. Цикритзис Д., Лоховски Ф. Модели данных. М.: Финансы и статистика, 1985. -344с.

75. Чукин Ю.В. Структуры данных для представления изображений // Зарубежная радиоэлектроника, 1983, № 8. С. 85-107.

76. Чэн Ш.-К. Принципы проектирования систем визуальной информации. М.: Мир, 1994. - 408с.

77. Шикин Е.В., Боресков А.В. Компьютерная графика. Динамика, реалистические изображения. М.: ДИАЛОГ-МИФИ, 1995. - 288с.

78. Шрейдер Ю.А., Шаров А.А. Системы и модели. М.: Радио и связь, 1982.-152с.

79. Эйнджел Э. Интерактивная компьютерная графика. М.: Вильяме, 2001.-592с.

80. Bouville С., Brusq R. Generating high quality pictures by ray-tracing // Computer Graphics Forum, 1985, vol. 4, № 2. P. 567-579.

81. Burtnik N., Wein M. Computer generated key-frame animation // Journal of SMPTE, 1980.-P. 149-153.

82. Computer graphics society. Techniques for computer graphics. NY: Springer, 1987, VIII. - 512p.

83. Cooc R.L., Torrance K.E. A Reflection Model for Computer Graphics // ACM Transactions on Graphics, 1(1),1982. P. 7-24.

84. Daniel L., Ruan M. Computer-aided graphics and design. NY, 1985. -400p.

85. Fleck M.M. Local Rotational Symmetries. Tech. Rep. 852. MIT Press., 1985.- 155p.

86. Gardner G.Y. Visual simulation of clouds // Computer Graphics, 1985, vol. 19, №3.-P. 297-313.

87. Hall R. Illumination andColor in Computer Generated Imagery. NY: Springer-Verlag. 1989.-328p.

88. Jankel A., Morton R. Creative Computer Graphics. Cambridge: Univer-city Press, 1984.- 143p.

89. Julius T. Tov. Pictorial Feature Extraction and Recognition via Image

90. Modeling // Computer Graphics and Image Processing, v. 12, 1980, n.4. P. 376-406.

91. Kilgour A.C. Techniques for modelling and displaying 3D scenes // Advances in Computer Graphics. NY: Springer-Verlag, 1989. - 1123p.

92. Levin J. A Parametric algorithm for drawing pictures of solid objects composed of quadric surfaces // Communication of the ACM, 1976, vol. 19, № 10. P. 555-573.

93. Lord E.A., Wilson C.B. The mathematical description of shape and form. Chichecter: Harwood, 1984. - 260p.

94. Lyalin V.E., Elkin S.L. Coding of signals on the basis of comparative transformation // Тез. докл. Нижний Новгород: Изд-во Нижегородского госуниверситета, 2004. - С. 255.

95. Marshall R.G. Computer graphics and application. New Jersey: Prentice Hall, 1987.-454p.

96. Murynov A.I., Elkin S.L. The transformation of the comparative signals to digital communication channels // Тез. докл. Нижний Новгород: Изд-во Нижегородского госуниверситета, 2004. - С. 257.

97. Nelson L. Max light diffision through clouds and haze // Computer Vision, Graphics and Image Processing, 1986, vol. 33, № 3. P. 19-29.

98. Phong B.T. Illumination for Computer Generated Scenes //Communication of the ACM, 18(6), 1975. Р/ 311-317.

99. Pratt M.J. Interactive geometric modeling for integrated CAD/CAM // Advances in Computer Graphics. Berlin: Springer-Verlag, 1986. P. 363-380.

100. Preparata F.P., Shamos M.I. Computational geometry. An introduction. -NY: Springer, 1985.-390p.

101. Rangasami L. and Ramalingam Chellippa. Estimation and Choice of Neighbors in Spatial-Interaction Models of Images // IEEE Transactions on information theory, 1983, v.it-29, no.l, January. P. 61-70.

102. Shannon C.E. A Mathematical Theory of Communication // The Bell Sys. Jornal, 1948.-P. 370-423.

103. Tanimoto S., Pavlidis T. A hierarchical data structure for picture processing // Сотр. Graph, and Image Proc. 1975, v. 4, № 4. P. 320-328.

104. Torrance K.E., Sparrow E.M. Theoiy for Off-Specular Reflection from Roughened Surfaces. // J. Optical Society of America, 57(9), 1967. P. 1105-1114.