Формирование и передача сложных алгебраических поверхностей по телекоммуникационным каналам тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Крылов, Иван Павлович

• Крылов, Иван Павлович
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Крылов, Иван Павлович

ВВЕДЕНИЕ. f 1. ОБРАЗОВАНИЕ ГЕОМЕТРИЧЕСКИХ ПОВЕРХНОСТЕЙ СЛОЖНОЙ ФОРМЫ И

МЕТОДЫ ИХ МАТЕМАТИЧЕСКОГО ОПИСАНИЯ.

1.1 Понятие поверхности.

1.2 Способы задания поверхности.

1.2.1 Точечный.

1.2.2 Алгебраический.

1.2.3 Каркасный.

1.2.4 Кинематический.

1.2.5 Треугольные сети.

1.2.5.1 Полигональная сеть-явное представление.

1.2.5.2 Полигональная сеть - вершинное представление.

1.2.5.3 Полигональная сеть - реберное представление.

1.2.5.4 Корректность представлений полигональных сетей.

1.2.5.5 Типы треугольных сетей.

1.3 Параметрические поверхности.

1.4 Параметрические кривые.

1.4.1 Кривые Эрмита.

1.4.2 Кривые Безье.

1.4.3 Кривые Бернштейна.

1.4.4 Поверхности Безье.

1.4.5 Методы построения семейства кривых.

1.4.6 Однородные нерациональные В-сплайны.

§ 1.4.7 Неравномерные нерациональные В-сплайны.

1.4.8 Неоднородные нерациональные В-сплайны.

1.5 Задачи моделирования.

1.6 Решение алгебраических уравнений от одной переменной.

1.7 Свойства корней алгебраических уравнений.

1.8 Приближенные методы решения алгебраических уравнений.

1.8.1 Метод половинного деления.

1.8.2 Метод хорд.

1.8.3 Метод Ньютона.

1.8.4 Метод итераций.

1.8.5 Метод Барстоу.

1.8.6 Метод Лагранжа.

1.8.7 Метод Лобачевского.

1.8.8 Метод Бродетского — Смила.

1.8.9 Метод Бернулли.

1.8.10 Метод Лина.

1.8.11 Метод Н.В. Палувера.

1.9 Алгебраические поверхности второго порядка.

1.10 Алгебраические поверхности третьего порядка.

1.10.1 Простые точки самопересечения.

1.11 Поверхность Кайлей.

1.12 Поверхности четвертого порядка.

1.12.1 Поверхности Куммера.

1.12.2 Римская поверхность.

1.12.3 Поверхности Горсата.

1.12.4 Поверхности Штейнера.

1.13 Выводы.

2. Методы формирования новых видов и типов алгебраических поверхностей.

2.1 Алгебраические поверхности в машинной графике.

2.2 Нумерация коэффициентов.

2.2.1 Лексикографический порядок.

2.2.2 Степенной порядок.

2.2.3 Степенной-лексикографичекий порядок.

2.3 Классификация алгебраических поверхностей.

2.3.1 Типы поверхностей.

2.3.2 Подтипы поверхностей.

2.3.3 Виды поверхностей.

2.4 Классификация типов и подтипов 1-го и 2-го порядков.

2.4.1 Методы определения типов и подтипов поверхностей высших порядков.

2.5 Метод перебора значений коэффициентов уравнения (-1,0,1).

2.6 Метод объединения поверхностей.

2.7 Метод модификации коэффициентов.

2.8 Метод конструирования симметричных поверхностей.

2.9 Метод получения видов поверхностей.

2.10 Выводы.

3. Передача сложных геометрических форм, заданных алгебраическими поверхностями, по каналам связи.

3.1 Условия эксперимента.

3.2 Форматы данных в экспериментах.

3.3 Влияние ошибок на вид поверхности при передаче данных.

3.4 Измерение скорости передачи изображений по коммутируемой телефонной линии

3.5 Измерение скорости передачи изображений по ADSL каналу.

3.6 Измерение скорости передачи изображений в сети GSM с использованием технологии GPRS.

3.7 Выводы.

Введение диссертации (часть автореферата) на тему «Формирование и передача сложных алгебраических поверхностей по телекоммуникационным каналам»

В последние несколько десятилетий вычислительная техника продела огромный путь в своей эволюции. Прошедшее десятилетие можно смело охарактеризовать десятилетием развития мобильных технологий от технологий передачи лишь речевой информации до сегодняшнего уровня мобильных решений по передачи данных. Развитие вычислительной базы позволяет решать все новые задачи, но с их решением появляются новые потребности, новые задачи, решение которых невозможно развитием лишь вычислительных мощностей, необходимы новые математические подходы. Ярким примером может служить развитие технологий по передаче аудио-, теле- и видеосигналов в последние 2 десятилетия, которое стимулировало, и продолжают стимулировать разработку алгоритмов для сжатия информации с потерями или без таковых, однако если бы не существовало к данному времени дешевых и доступных вычислительных устройств, то и задача по разработке таких • алгоритмов не стояла бы. Развитие техники не стоит на месте, новые задачи требуют улучшение и разработка новых математических конструкций для моделирования реальных процессов. Исследованиями алгебраических уравнений, описывающих сложные поверхности, занимались ученые на протяжении многих веков. Решение алгебраических уравнений высших степеней исследовали Н.Х. Абель, Н.И. Лобачевский, Ж.Л. Ла-гранж, Л. Эйлер, Э. Ва-ринг, П. Руффини, А. Крелле, Н.В. Палувер и др. Исследова-ния сложных геометрических форм алгебраических поверхностей проводили А.Кайлей, Л.Шлафли, Г.Фишер, Г.Салмон, С.В.Чмутов, С.Эндраас, Н.Слоан, Е.Кумер, Е.Горсат, А.Грей и др. Одним из направлений исследований в данной области является создание аналитических моделей. В последние годы целая группа исследователей под руководством В.М. Дегтярева разрабатывают новые подходы к использованию аналитических моделей. Очевидными преимущества-# ми аналитических моделей является их компактность, что особенно важно для их использование в области телекоммуникаций и передачи данных, а также их близость к реальным объектам. Аналитические модели могут использоваться в синтетической графике, которая в свою очередь может применяться в цифровом телевидении, мобильном и Интернет- телевидении, дистанционная медицина и т.п. Компактность аналитических моделей делает их использование оптимальным везде, где есть ограничения по пропускной скорости каналов, а также в областях, где налагаются существенные требования на скорость доставки информации. Но если разобраться, то такие ограничения существуют почти во всех системах мобильной связи, активно используемых в наше время. В системах доступа к данным по сотовой связи ограничения связаны с нехваткой частот, организация доступа по проводным сетям может оказаться дорогой, если клиентское устройство находиться в труднодоступном регионе. Объем передаваемых данных также очевидным образом влияет на возможность их моментальной передачи на расстояние, передача большого объема данных с существенной задержкой во времени считается нормальным условием для большинства приложений. На сегодняшний день бытовые мобильные устройства (второго поколения) работают на скоростях до 50 кбод, причем обычно эта связь обладает свойством асимметричности: ширина канала данных в одну сторону может быть больше, чем в обратную сторону. С развитием систем мобильной связи третьего поколения планируется переход на скорости передачи данных от 150 кбод, однако внедрение таких систем достаточно дорого и может растянуться на десять и более лет. Но даже с внедрением этих систем в урбанизированных регионах, проблема наличия скоростных каналов еще долго исчезнет в труднодоступных, малонаселенных регионах.

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

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

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

ОПИСАНИЯ

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

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Крылов, Иван Павлович

3.7 Выводы

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

Среди рассмотренных типов каналов связи самым быстрым оказался ADSL канал. Также быстрым оказалось и GPRS соединение, затем идет коммутируемое соединение и самым медленным - простое GSM соединение. Малая скорость модемного соединения обусловлено низким качеством местной АТС. Декадо-шаговые АТС не предназначены для передачи цифровых данных, однако такая телефонная линия была выбрана в силу распространенности ДШС в регионах России.

ЗАКЛЮЧЕНИЕ

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

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

2. Проведен обзор исследованных типов поверхностей по четвертый порядок, рассмотрены их свойства. Рассмотрены известные классы поверхностей третьего и четвертого порядков: поверхности Куммера, поверхности Горсата, поверхности Штейнера и другие.

3. Разработаны аналитические методы образования алгебраических поверхностей:

-Метод перебора значений коэффициентов уравнения; -Метод объединения поверхностей (перемножения уравнений); -Метод модификации коэффициентов; -Метод конструирования симметричных поверхностей; -Метод формирования видов поверхностей.

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

Проведено 30 экспериментов по передаче файлов в коммутируемой телефонной сети, в сети с использованием технологии передачи ADSL, в сети GSM с использованием стандартной технологии передачи данных и с использованием технологии GPRS.

Эксперименты по передаче данных в телекоммуникационных сетях показали, что геометрические формы, задаваемые в виде алгебраических уравнений высших порядков, передаются за наименьшее время из рассмотренных видов представления объектов. В сети GPRS файлы с алгебраическими коэффициентами предавались быстрее, чем: растровые несжатые файлы - в 299 раз, растровые файлы сжатые WinRar - в 4 раза, файлы содержащие триангуляцию - в 77 раз, файлы содержащие триангуляцию сжатую WinRar - в 17 раз.

Предложены пути дальнейшего развития полученных результатов:

-Исследование алгебраических поверхностей выше 4-го порядка и более Зх переменных;

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

Список литературы диссертационного исследования кандидат технических наук Крылов, Иван Павлович, 2004 год

1. Колесников В.Г., Димент Л.И. Моделирование и пересечение по-верх-ностей : учебное пособие — СПбГТУ, 1997Токмаджян Л. В. «Образование поверхностей, индуцируемых множествами линейных преобразований» / Автореферат дис. на соиск. К.т.н. — Киев: Киев, 1991

2. Малкина В.М. «Геометрическое моделированние повехностей на основе специальных систем ортонормированных полиномов» / Ав-тореф. на соискание к.т.н. Киев, 1999

3. Woo Т. «А Combinatorial Analysis of Boundary Data Structure Schemata» / CG & A, 5(3), March 1985, 19-27

4. Baumgart B.G. A polyhedron representation for computer vision. // NCC 75, 589-596

5. Томпсон H. «Секреты програмирования трехмерной графики для windows 95» / издательство Питер, Санкт-Петербург, 1997

6. Debunne G., Desbrun М., Barr A., Cani М. « Interactive multiresolution animation of deformable models » / California technology institute, 1998

7. Lee A., Swelden W., Shroeder P., Cowsar L., Dobkin D. « MAPS: Multiresolution Adaptive Parametrization of Surfaces » / California technology institute, 1997

8. Lee A., Dobkin D., Swelden W., Shroeder P. «Multiresolution Mesh Morphing» / California technology institute, 1999

9. Guskov I., Sweldens W., Shroeder P. «Multiresolution Signal Processing for Meshes» / California technology institute, 1996

10. Khodakovsky A., Shroeder P., Sweldens W. «Progressive Geometry Compression» / California technology institute, 1997

11. Khodakovsky A., Guskov I. «Normal mesh compression» / California technology institute, 1998

12. Kobbelt L., Bareuther Т., Seidel H. «Multiresolution Shape Derforma-tions for Meshes with Dynamic Vertex Connectivity» / Eurograph materials, 2000

13. Жермен-Лакур П., Жорж П., Пистр Ф., Безье П. «Математика и САПР» / Москва, Мир, 1989

14. Денискин Ю.И. «Локальная модификация кривых Безье с сохранением заданного порядка гладкости» / Геометрическое моделирование и компьютерная графика. Сборник научных трудов, Санкт-Петербург, 1992.

15. Foley J.D., Dam A. «Computer graphics: principles and practice» / Adi-son-Wesley Systems Programming Series, 1992-1995.

16. Murugaiyan E., Clapworthy G. «Using CISSes for Detailed Modeling of Cylinders» / Третья международная конференция по компьютрной графике и визуализации. Конкурсные доклады. Санкт-Петербург, 13-17 сентября 1993.

17. Дорот В.Л., Троицкий В.А., Шелест В.Д. «Элементы вычислительной математики. Численное решение алгебраических и трансцендентных уравнений» / учебное пособие, издательство ЛПИ им.Калинина, 1977

18. Демидович Б.П., Марон И.А. «Основы вычислительной математики» / Москва, Наука, 1970

19. Шапиро Г.М. «Высшая алгебра» / изд. 4, ГУПИ, Москва, 1938, глава 3 и4

20. Никифоровский В.А. В мире уравнений. // Москва, Наука, 1987

21. Анго А. «Математика для электро- и радиоинженеров» / Москва, Наука, 1964

22. Канторович Л.В. О методе Ньютона. // Труды матем. института им. В.А.Стеклова, XXVIII (1949)

23. Беланов А.А. Решение алгебраических уравнений методом Лобачевского. // Мо-сква, Наука, 198924