Представление и эффективное кодирование трехмерных пространственных объектов для передачи по цифровым каналам связи тема диссертации и автореферата по ВАК РФ 05.12.13, кандидат технических наук Елкин, Сергей Леонидович

• Елкин, Сергей Леонидович
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Елкин, Сергей Леонидович

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

Введение.

Глава 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. Проведены экспериментальные исследования по оценке эффективности разработанных средств и методов в целях повышения коммуникативных возможностей при их использовании в телекоммуникационных системах. Полученные оценки подтверждают целесообразность использования разработанных средств и методов для существенного повышения коммуникативных возможностей телекоммуникационных систем на основе применения эффективных интерактивных трехмерных моделей данных.

Список литературы диссертационного исследования кандидат технических наук Елкин, Сергей Леонидович, 2004 год

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.