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

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

КРЫЛОВ

Иван Павлович

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

Специальность 05.13.01. -Системный анализ, управление и обработка информации

АВТОРЕФЕРАТ

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

Санкт-Петербург - 2004

Работа выполнена в Санкт-Петербургском государственном университете телекоммуникаций им. проф.М.А.Бонч-Бруевича на кафедре "Инженерная машинная графика"

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

доктор технических наук, профессор Дегтярев В.М. Официальные оппоненты:

доктор технических наук, профессор Торгашев В.А. кандидат технических наук, доцент Абросимов С.Н.

Ведущая организация: ОАО «Авангард»

Защита диссертации состоится 10 июня 2004 года в 14-00 часов на заседании диссертационного совета К 219.004.01 Санкт-Петербургского государственного университета телекоммуникаций им. проф. М.А. Бонч-Бруевича по адресу: 191065, Санкт-Петербург наб.р. Мойки, 61

С диссертацией можно ознакомится в библиотеке Санкт-Петербургского государственного университета телекоммуникаций им. проф. М.А. Бонч-Бруевича.

Автореферат разослан 26 апреля 2004 г.

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

диссертационного совета, "7

К.Т.Н., доцент ' у^/ г В.Х. Харитонов

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

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

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

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

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

Исследованиями алгебраических уравнений, описывающих сложные поверхности, занимались ученые на протяжении многих веков. Решение алгебраических уравнений высших степеней исследовали Н.Х. Абель, Н.И. Лобачевский, ЖЛ. Ла-гранж, Л. Эйлер, Э. Варинг, П. Руффини, А. Крелле, Н.В. Палувер и др. Исследования сложных геометрических форм алгебраических поверхностей проводили

АКайлей, Л.Шлафли, Г.Фишер, Г . С , Н.Слоан,

и

БИБЛИОТЕКА С. Петербург О» тЦщт

Е.Кумер, Е.Горсат, А.Грей и др. Однако использование их исследований для решения геометрических задач с помощью вычислительной техники начинает применяться только в последнее время. Это связано со сложностью классификации поверхностей и установления однозначной связи свойств уравнения с геометрической формой поверхности. Научная школа под руководством доктора технических наук, профессора Дегтярева В.М. занимается исследованиями в этой области. Данная работа базируется на исследованиях известных ученых и результатах работ научной школы В.М. Дегтярева.

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

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

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

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

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

Научные положения, выносимые на защиту:

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

- Определение типа, подтипа и вида поверхности;

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

- Исследование влияния изменений коэффициентов алгебраических уравнений

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

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

Научная новизна. В процессе решения поставленных задач получены следующие новые научные результаты:

- Предложена классификация алгебраических поверхностей высших порядков;

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

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

- Определены дальнейшие пути развития результатов, полученных в данной работе.

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

Реализация результатов работы. Результаты работы использованы в учебном процессе кафедры «Инженерная Машинная Графика» Санкт-Петербургского

5

государственного университета телекоммуникаций им. проф. М.А. Бонч-Бруевича, в учебном процессе кафедры «Информационные Вычислительные Системы и Технологии» Санкт-Петербургского государственного политехнического университета, при проведении проектных работ в Энергомаш (ЮК) Лимитед.

Апробация работы. Результаты работы докладывались на заседании секции .. дома ученых им. М. Горького (РАН) «Начертательная геометрия, графика и автоматизация проектирования» в октябре 2002 и мае 2003 года, на 55-ой Научно-технической конференции профессорско-преподавательского состава Санкт-Петербургского государственного университета телекоммуникаций, январь, 2003; на Седьмой международной конференции New Approaches to High-Tech: Nondestructive Testing and Computer Simulations in Science and Engineering, июнь, 2003; на заседании кафедры «Инженерная Машинная Графика» Санкт-Петербургского государственного университета телекоммуникаций, март, 2004.

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

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

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

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

В главе 1 «Образование геометрических поверхностей сложной формы и методы их математического описания» рассматриваются различные способы задания

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

В работе представлены следующие методы формирования поверхностей: совокупностью точек (точечный); набором каркасных линий (каркасный); движением образующей линии по направляющей линии (кинематический); составлением из треугольников и многоугольников (триангуляционный); параметрами таких известных поверхностей, как плоскости и поверхности 2-го порядка, (параметрический) и описание уравнениями (аналитический). Точечный метод при качественном описании модели требует огромных объемов памяти и теряет информацию при масштабировании и поворотах модели в пространстве. Каркасная модель на поверхностях, имеющих часто меняющуюся кривизну, требует большого числа линий для детализации модели, что тоже сказывается на объеме данных машинного представления модели. В такой модели точки поверхности между линиями отсутствуют и для их получения нужны дополнительные построения, которые могут иметь значительные погрешности (отклонения от реальной поверхности). При кинематическом способе большое значение имеет шаг перемещения. Если он большой - модель грубая, если он уменьшается - объем вычислений растет и весьма значительно. Кинематические модели хорошо реализуются при простых формах образующих и направляющих. Параметрические модели более компактны, чем предыдущие, но для этого метода возникают трудности с подбором параметризированных поверхностей сложной геометрической формы. Аналитические модели самые компактные. Они могут быть представлены различными видами уравнений (алгебраическими, дифференциальными, тригонометрическими, и другими). Описание поверхности алгебраическим уравнением высшего порядка (более 2-ой степени), дает огромное многообразие форм уже для уравнений четвертого порядка Обзор литературы показал, что на текущий момент не существует всеобъемлющей классификации поверхностей выше второго порядка, не найдены инварианты и нет перечисления всех типов и видов поверхностей, по этой причине алгебраические поверхности высших порядков практически не используются в системах моделирования и проектирования. Отдельные геометрические свойства алгебраических поверхностей

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

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

При визуализации алгебраических поверхностей высших порядков возникают задачи решения алгебраических уравнений высших порядков. В 1826 году Абель показал неразрешимость уравнений, начиная с пятого порядка, в радикалах, следовательно, возникает необходимость приближенного решения таких уравнений. Проведен анализ 11 методов приближенного решения уравнений с их краткими характеристиками, что позволило выбрать и использовать наиболее быстрый метод для программы динамической визуализации алгебраических уравнений 3 и 4-ой степени.

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

Рассматриваются разные формы записи многочлена, вводится степенная -лексикографическая форма записи. В степенной - лексикографической форме радикалы сначала группируются по суммам степеней всех входящих переменных, внутри этой группы радикалы выстраиваются в лексикографическом порядке. Уравнение четвертого порядка записывается в общем виде таким образом: aux4 + a33X?y + a^z + а3^у2 + a^yz + a^tV + a2gx$ + a2ixtfz + a2$y£ + a2sx^ + a24y4 + azsfz + aztfi + a21y^ + a20z4 + aiç? + aigêy + a^z + a]( jtf + aisxyz+a14x £ + aJ3/ + г+Оцу Z2 + a^ + + agxy + a?xz + a^y2 + a^yz + «¿z+ajx + ajjy +ац + а/гО.

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

Тип поверхности - определен условиями, при которых численные значения коэффициентов уравнения определяют характерную геометрическую форму. Пример: «Куб 4-го порядка» уравнение х4+у4+з? -1*=0.

Подтип поверхности - измененная поверхность, которая сохранила основные свойства, такие как схожесть или подобие типа поверхности. Пример: «Модифицированный куб 4го порядка», уравнение;»:* +у4-2^—1 — 0.

Вид поверхности — это тип или подтип поверхности, пропорционально измененный в размерах относительно трех осей системы координат (масштабирование), повернутой или перемещенной в пространстве.

Пример: «Модифицированный куб 4го порядка, повернутый вокруг оси У» уравнение х4 +/+г4-2 £ = 0.

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

Рис 1. Классификация поверхностей

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

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

Для решения задачи классификации предложены 5 методов для формирования типов, подтипов и видов поверхностей:

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

Анализ поверхностей 2-го порядка показал, что все 12 действительных типов поверхностей 2-го порядка: сфера, конус, круговой, гиперболический и параболический цилиндр, однополостной и двуполостной гиперболоид, гиперболический и круговой параболоид, пара пересекающихся, параллельных и совпадающих плоскостей могут быть получены в результате перебора коэффициентов значениями (О, 1, -1) в приведенном уравнении 2-го порядка (центр или ось симметрии поверхности находится в начале системы координат).

Метод состоит в экстраполяции этого принципа на поверхности высших порядков. Перебор каждого из Зх значений (1, 0,-1) для 35 коэффициентов уравнения 4-го порядка дает 50 031 545 098 999 707 вариантов, то есть порядка 5*101в. Однако формообразующими коэффициентами являются коэффициенты при высших степенях уравнения, таким образом, необходимо перебирать коэффициенты -1,0,1 только для ац ... Я2о. Перебор этих коэффициентов дает 14261427 типов поверхностей. Далее, необходимо исключить инвертированные поверхности, то есть те, которые

получены переворотом относительно одной из осей. Таких поверхностей - 87480. В итоге получается типов: 4-й порядок - 14173819,3-й порядок: 49329. В числе этих типов будут мнимые поверхности. Их можно исключить, проверив решения каждого уравнения.

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

АХуа)=2*а, у1* г?4 : V к к1+11+щ<2; 8(х,у,2)=1Ь1хк'у,'^п' : V у. к,+1,+т1<2. Тогда объединенная поверхность задается уравнением

= * в(х,у^)= ¿ах^У1'^ : V п к,+1,+т,<4.

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

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

1. Симметричная поверхность, дающая замкнутую кривую 2-го порядка в любом

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

аз4Х4++ а9к?+а$х+щу2+а4£+а<гО 2. Цилиндрические поверхности, вытянутые параллельно оси Ъ задаются уравнением: а^+а^у + в^рсУ++ а^4+а^+а^у+а16ху' +д2Д/++ ару + а^у3 + азк + агу +

Рис 2. Примеры поверхностей, полученные методом конструирования симметричных поверхностей

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

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

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

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

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

Для примера была рассмотрена поверхность четвертого порядка «периформа» (Рис. 3). Периформа задается уравнением:^'

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

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

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

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

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

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

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

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

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

Имя файла Размф в байтах

periformM_l_0001.bmp 589878

PeriformM_l_0001.hmpjar 4975

periformMJ_0001.wri 129708

PeriformM_l _0001.wrLrar 24737

perifonnM_l_000I.bin 140

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

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

- Метод объединения поверхностей (перемножения уравнений);

- Метод перебора значений коэффициентов уравнения;

- Метод модификации коэффициентов;

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

- Метод формирования видов поверхностей.

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

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

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

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

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

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

- Решение задач поиска, конструирования и сглаживания поверхности по заданным параметрам

Основные положения диссертации опубликованы в следующих работах:

1. I. Shturtz, I.Krylov, St. Petersburg State Technical University (Russia) "Internet-based 3D editor for carbon molecular models","International Workshop on Nondestructive Testing and Computer Simulatios in Science and Enginering", Alexander

1.Melker, Editor,Proceedings of SPIE Vol.3687, page numbers (1999) pp 142-148

2. V.Degtyarev, I. Krylov, "On classification of cubic and quartic surfaces", in the International Workshop on New Approaches to High-Tech Nondestructive Testing and Computer Simulatios in Science and Enginering, preprints and program, Alexander I.Melker, Editor, Proceedings of SPAS Vol. 7, pp F12-F13 (2003)

3. Крылов И.П. Виды и типы геометрических поверхностей, описываемых алгебраическими уравнениями 4-го порядка, Материалы 55 НТК СП6ТУТ 27-31 января 2003

4. Крылов И.П., Дегтярев В.М. Библиотека алгебраических поверхностей, используемая для передачи геометрических образов по каналам связи // Труды учебных заведений связи / СПбГУТ. СПб, 2003. № 169. С. 70-81

5. V.Degtyarev, I. Krylov, Department of engineering computer graphics, St. Petersburg state telecommunications university (Russia) "On classification of cubic and quartic surfaces", "Seventh International Workshop on Nondestructive Testing and Computer Simulatios in Science and Enginering", edited by Alexander LMelker, Proceedings of SPIE Vol. 5400 (2004) pp 287-291

11739

ВВЕДЕНИЕ. 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-го порядка и более Зх переменных;

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

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