Содержание к диссертации
ВВЕДЕНИЕ 4
ГЛАВА 1. ИЗВЕСТНЫЕ МЕТОДЫ ПОСТРОЕНИЯ КРИВЫХ И
ПОВЕРХНОСТЕЙ 12
Постановка задачи интерполяци 12
Задача построения кривых в машинной графике 14
Представление пространственных форм в машинной графике 15
Классическое решение. Полиномиальная интерполяция 16
Многочлен Лагранжа 18
Интерполяционная формула Ньютона 19
Интерполяция кусочно-полиномиальными сплайнами 22
Интерполяция В-сплайнами 27
Полигональные сетки 32
Поверхности вращения 35
Заметающие поверхности 36
Параметрические поверхности 38
Поверхности Кунса 38
Кусочные поверхности 40
1.13. Выводы 41
ГЛАВА 2. РАЗРАБОТКА АЛГОРИТМА ИНТЕРПОЛЯЦИИ НА
ОСНОВЕ ДЕЛЬТА-ПРЕОБРАЗОВАНИЙ ВТОРОГО ПОРЯДКА 44
2.1. Дельта-преобразования второго порядка и постановка задачи
построения сплайна 44
2.2.0 существовании и единственности решения задачи построения
сплайна на основе дельта-преобразования второго порядка 49
2.3. Алгоритм интерполяции на основе дельта-преобразований второго
ПОРЯДКА 56
2.4. Выводы 61
ГЛАВА 3. ИССЛЕДОВАНИЕ ВОЗМОЖНОСТЕЙ И
СРАВНИТЕЛЬНЫЙ АНАЛИЗ АЛГОРИТМА НА ОСНОВЕ ДЕЛЬТА-
ПРЕОБРАЗОВАНИЙ ДЛЯ ПОСТРОЕНИЯ КРИВЫХ В МАШИННОЙ
ГРАФИКЕ 62
Алгоритмизация интерполяции кривых кубическими сплайнами для экспериментов 62
Алгоритмизация интерполяции кривых кубическими В-сплайнами
для экспериментов 65
Алгоритмизация интерполяции кривых кубическими многочленами Эрмита для экспериментов 66
Алгоритмизация интерполяции кривых на основе дельта-преобразований второго порядка для экспериментов 71
Алгоритмизация интерполяции кривых параболическими сплайнами для экспериментов 73
Сравнение методов интерполяции гладких кривых 75
Выводы 95
ГЛАВА 4. ИССЛЕДОВАНИЕ ВОЗМОЖНОСТЕЙ И
СРАВНИТЕЛЬНЫЙ АНАЛИЗ ДЕЛЬТА-ПРЕОБРАЗОВАНИЙ ДЛЯ
ПОСТРОЕНИЯ ТРЕХМЕРНЫХ ОБЪЕКТОВ И ПОВЕРХНОСТЕЙ 97
Алгоритмизация интерполяции поверхностей интерполяционными бикубическими сплайнами для экспериментов 97
Алгоритмизация интерполяции поверхностей интерполяционными бикубическими поверхностями эрмита для экспериментов 103
Алгоритмизация интерполяции поверхностей интерполяционными бикубическими в-сплайнами для экспериментов 108
Алгоритмизация интерполяции поверхностей на основе дельта-преобразований второго порядка для экспериментов 112
Сравнение рассматриваемых методов интерполяции гладких поверхностей 115
Выводы 125
ГЛАВА 5. ИССЛЕДОВАНИЕ ВОЗМОЖНОСТЕЙ ПРИМЕНЕНИЯ
ДЕЛЬТА-ПРЕОБРАЗОВАНИЙ В ТЕХНИЧЕСКИХ РЕШЕНИЯХ И
ПРОГРАММНЫХ КОМПЛЕКСАХ 126
Система компьютерного ультразвукового эхоэнцефалоскопа ... 126
Устройство для измерения электрического сопротивления изоляции 131
Система полиграфического мониторинга человека-оператора... 136
Выводы 140
ЗАКЛЮЧЕНИЕ 142
ЛИТЕРАТУРА 144
ПРИЛОЖЕНИЕ 1 АКТЫ ОБ ИСПОЛЬЗОВАНИИ РЕЗУЛЬТАТОВ
ДИССЕРТАЦИОННОЙ РАБОТЫ 150
ПРИЛОЖЕНИЕ 2 ФРАГМЕНТЫ ИСХОДНЫХ ТЕКСТОВ ПРОГРАММЫ ПОСТРОЕНИЯ ИНТЕРПОЛИРУЮЩИХ КРИВЫХ РАЗРАБОТАННЫМ И СРАВНИВАЕМЫМИ С НИМ МЕТОДАМИ ...155
ПРИЛОЖЕНИЕ 3 ФРАГМЕНТЫ ИСХОДНЫХ ТЕКСТОВ
ПРОГРАММЫ ПОСТРОЕНИЯ ИНТЕРПОЛИРУЮЩИХ
ПОВЕРХНОСТЕЙ РАЗРАБОТАННЫМ И СРАВНИВАЕМЫМИ С НИМ
МЕТОДАМИ 180
Введение к работе
Актуальность темы. При выполнении физико-технических и других математических расчетов, в которых необходимо строить функциональные зависимости на протяженных интервалах, выгодно заменять вычисляемую функцию приближенной формулой, т.е. подобрать некоторую функцию, которая достаточно близка к искомой и просто вычисляется.
В общем случае, если задана функция, то это означает, что любому допустимому значению аргумента соответствует вполне определенное ее значение. Замена приближенной функцией искомой удобна тем, что нахождение значений функции для любого допустимого или всех требуемых значений независимой переменной может быть очень трудоемким. Например, функция может быть определена как решение сложной задачи, или функция измеряется в дорогостоящем эксперименте, который невозможно повторить. Для более эффективного решения данной задачи можно вычислить небольшую таблицу ее значений, а нахождение всех других значений функции при большом числе значений аргумента осуществлять с использованием интерполяции [24].
Класс практических задач и областей, в которых решаются проблемы интерполяции, постоянно расширяется [59]. Математическое решение задач интерполяции смыкается с компьютерной графикой, так как современные технические системы реализуются с использованием компьютеров и информационных технологий, и остро стоит вопрос оперативного отображения интерполируемой графической информации на экранах мониторов, компактного хранения интерполируемой информации в памяти компьютера.
Необходимость интерполяции возникает при обработке метеорологических данных, которые, как правило, измеряются каждый час или чаще (каждые 10-15 минут). В чрезвычайных ситуациях, при обработке большого объема данных о каких-либо аномальных метеорологических
процессах (ураганах, атмосферных фронтах, смерчах) необходимо заполнение интервалов между отдельными выборками. При выполнении наиболее опасных маневров посадки и взлетов воздушных судов также большое значение имеет метеорологическая обстановка. Поэтому, любой современный аэропорт имеет хорошо оснащенную и дорогостоящую метеорологическую станцию. При этом, все изменения в метеорологической обстановке, собранные с метеорологических датчиков, расположенных в зоне аэропорта, должны, быть немедленно обработаны и переданы диспетчеру аэропорта. Это типичные задачи интерполяции.
Обработка данных о сейсмической активности отдельных участков земной поверхности, получаемых с разных сейсмических станций с целью предупреждения землетрясений, также требует решения задачи интерполяции, так как все измерения производятся через строго определенные промежутки времени.
В астрономии, при измерении распределения температуры поверхности Солнца, анализируют так называемые солнечные пятна. Как известно, изменения магнитных полей солнечных пятен приводят к магнитным бурям на Земле и сильно влияет на распространение радиоволн и жизнедеятельность человека.
Решение задачи интерполяции требуется и в медицине, при ультразвуковой томографии головного мозга, при обработке данных о распределении температуры, электрических потенциалов и других параметров на теле человека. Задача актуальна при осуществлении длительного мониторинга биологических параметров человека, например, для точной и достоверной оценки влияния различных лекарственных средств [22,33,61,62,65].
В работе птицефабрик важную роль играет показатель выводимости цыплят. Для этого в инкубаторах должны соблюдаться специальные режимы температуры и влажности. Поэтому, важно знать, как распределяется тепло и влага внутри инкубатора, и своевременно реагировать на изменения. Важен
контроль над распределением тепла ив печах для хлебобулочных изделий. Вообще, представление распределения температур (одномерное или многомерное) важно в любых печах, особенно в доменных.
Необходимость интерполяции существует в системах реального времени при контроле большого числа параметров, например, на ядерных электростанциях, в электрических сетях при переходных режимах. Такая же проблема возникает в системах распознавания перемещающихся с большой скоростью целей, когда на принятие решения требуется очень маленькое время (миллисекунды).
Все выше перечисленные области применения интерполяции связанны с обработкой всё больших объемов информации. В то же время, при реализации интерполируемых функций при построении изображений в компьютерной графике с учетом современных требований к уменьшению задержки обрабатываемой информации при выводе на экран и к повышению частоты смены кадров, размеров и сложности изображения возникают проблемы, связанные с необходимостью существенного уменьшения вычислительной трудоемкости используемых алгоритмов интерполяции [1,4,53,55]. Поэтому, постоянно ищутся новые, более компактные в реализации, требующие меньших вычислительных ресурсов и просто более легкие для освоения методы и способы восстановления и интерполяции.
На сегодняшний день наибольшее распространение получили методы, основанные на кусочно-полиномиальной интерполяции (В-сплайны и их производные). Однако, с повышением гладкости интерполирующей кривой значительно возрастает трудоемкость программирования и время для вычислений промежуточных точек.
В связи с изложенным выше, данная работа посвящена разработке алгоритмов интерполяции, основанных на дельта-преобразованиях второго порядка, которые обладают несомненными достоинствами - простотой и малой вычислительной трудоемкостью при реализации.
Объект исследования. В настоящей работе выполняется разработка высокопроизводительных алгоритмов построения интерполяционных сплайнов на основе дельта-преобразований второго порядка; исследуется возможность и целесообразность применения этих алгоритмов для интерполяции кривых и поверхностей в компьютерной графике.
Цель исследования. Разработка и исследование алгоритмов интерполяции кривых и поверхностей на основе дельта-преобразований второго порядка.
В соответствии с поставленной целью решаются следующие задачи:
разработка алгоритма интерполяции кривых, основанного на дельта-преобразованиях второго порядка;
разработка алгоритма интерполяции поверхностей, основанного на дельта-преобразованиях;
обоснование принципов построения интерполирующей функции на основе дельта-преобразований;
разработка программных моделей алгоритмов интерполяции кривых и интерполяции поверхностей, основанных на дельта-преобразованиях второго порядка;
экспериментальные исследования результатов работы программных моделей алгоритмов интерполяции кривых и интерполяции поверхностей и их сравнительный анализ с существующими методами.
Методы проведения исследований .
При выполнении настоящей работы использовался математический аппарат теории оптимизированных дельта-преобразований второго порядка, теории численных методов, теории дифференциального и интегрального исчислений, аналитической геометрии и теории рядов.
Научный результат:
разработан высокопроизводительный алгоритм интерполяции
кривых, основанный на дельта-преобразованиях второго порядка и
характеризующийся возможностями комплексного обеспечения низкой вычислительной трудоемкости, расчетной независимости производных в узлах интерполяции, качественной отработки скачкообразных изменений первой производной, высокой локальности;
разработан высокопроизводительный алгоритм интерполяции поверхностей, основанный на дельта-преобразованиях;
обоснованны принципы построения интерполирующей функции на основе дельта-преобразований;
обоснована возможность обеспечения существенно большей скорости построения сплайнов на основе разработанных алгоритмов по сравнению с известными алгоритмами интерполяции (в зависимости от сравниваемого метода для кривой в максимальном пределе (при количестве интерполируемых точек, существенно большем количества узлов) от 2 до 10 раз, для поверхности от 10 до 19 раз).
Основные положения, выносимые на защиту:
алгоритм интерполяции кривых, основанный на дельта-преобразованиях второго порядка;
алгоритм интерполяции поверхностей, основанный на дельта-преобразованиях второго порядка.
обоснование принципов построения интерполирующей функции на основе дельта-преобразований;
Практическая ценность.
Разработанные в диссертационной работе высокопроизводительные алгоритмы интерполяции могут быть использованы для увеличения размера изображения и повышения частоты смены кадров в компьютерной графике, в мультимедийных приложениях, при отображении окружающего пространства в различного рода симуляторах и тренажерах; в системах реального времени, связанных с обработкой и отображением большого
объема интерполируемых данных, при дефиците вычислительных ресурсов, в частности, в медицине, метеорологии, системах контроля электрических сетей, ядерных электростанций и т.д.
Достоверность полученных в диссертации результатов подтверждается теоретическим обоснованием, программными реализациями предлагаемых алгоритмов, вычислительными экспериментами, а также, применением разработанных алгоритмов интерполяции для решения практических задач, что подтверждается актами использования и внедрения результатов работы.
Реализация. Результаты работы использованы в рамках работ, выполненных в НКБ «Миус» при разработке ультразвукового компьютерного эхоэнцефалографа, устройства для измерения электрического сопротивления изоляции (уменьшение временных затрат для формирования изображения приблизительно в 1,5-2,5 раза по сравнению с самыми быстрыми из рассматриваемых алгоритмов), а также системы полиграфического мониторинга человека-оператора (уменьшение временных затрат для формирования изображения приблизительно в 10 раза по сравнению с самыми быстрыми из рассматриваемых алгоритмов). На систему полиграфического мониторинга человека-оператора получен патент [54].
Апробация.
Результаты работы докладывались и обсуждались на научно-технических конференциях:
Всероссийская научно-техническая конференция с международным участием «Компьютерные технологии в инженерной и управленческой деятельности», Таганрог, 1999;
4-я всероссийская научно-техническая конференция студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании», Рязань, 1999;
4-я всероссийская научная конференция с международным участием молодых ученых и аспирантов «Новые информационные технологии. Разработка и аспекты применения», Таганрог, 2001;
5-я всероссийская научная конференция с международным участием молодых ученых и аспирантов «Новые информационные технологии. Разработка и аспекты применения», Таганрог, 2002;
Международная научная конференция "Моделирование как инструмент решения технических и гуманитарных проблем", Таганрог, 2002;
XL международная научная студенческая конференция "Студент и научно-технический прогресс ", Новосибирск, 2002;
Всероссийская научно-техническая конференция с международным участием «Компьютерные технологии в инженерной и управленческой деятельности», Таганрог, 2002;
По итогам работы выпущены 15 публикаций, среди них 5 статей и 1
патент.
Структура диссертации.
Диссертационная работа состоит из введения, пяти разделов, заключения, списка литературы, включающего 73 наименований и 3-х приложений на 62 страницах.
В первом разделе выполнен аналитический обзор существующих подходов к интерполяции. Информация первого раздела является базовой для обоснования выбранного в диссертационной работе направления, а также используется при описании разработанных алгоритмов.
Во втором разделе проводится постановка задачи интерполяции кривых на основе теории дельта-преобразований второго порядка, доказывается существование и единственность такой интерполирующей кривой, описывается разработанный алгоритм интерполяции, основанный на оптимизированных дельта-преобразованиях второго порядка.
В третьем разделе проводится исследование возможностей и сравнительный анализ алгоритма интерполяции на дельта-преобразованиях и некоторых других методов для построения кривых.
В четвертом разделе приводится исследование возможностей и сравнительный анализ алгоритма интерполяции на дельта-преобразованиях и некоторых других методов для построения поверхностей.
В пятом разделе приводится обзор практических приложений и устройств, в которых были использованы разработанные алгоритмы интерполяции, основанные на дельта-преобразованиях.
В заключении излагаются основные результаты диссертационной работы.
