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

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

Автор: Костюк, Юрий Леонидович

Шифр специальности: 05.13.18

Научная степень: Докторская

Год защиты: 2002

Место защиты: Томск

Количество страниц: 264 с. ил

Артикул: 2327811

Автор: Костюк, Юрий Леонидович

Стоимость: 250 руб.

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

Введение
1 Алгоритмы представления кривых и графиков
1.1 Интерполяция кривых локальными параметрическими сплайнами 3й степени
1.1.1 Нормирование производных по длине хорды.
1.1.2 Нормирование производных по длине цуги
1.1.3 Свойства локальных параметрических сплайнов .
1.2 Цифровая интерполяция полиномов.
1.2.1 Интерполяция с постоянным шагом независимой переменной
1.2.2 Интерполяция при задании максимальной величины
приращения полинома.
1.2.3 Программноаппаратная реализация алгоритмов интерполяции
1.2.4 Интерполяция параметрического полинома линией
единичной толщины.
1.3 Построение красивых функциональных шкал.
1.3.1 Красивые последовательности.
1.3.2 Разметка линейной шкалы . .
1.3.3 Красивые функциональные шкалы.
1.3.4 Изображение шкал.
1.4 Выводы
2 Алгоритмы триангуляции и графического поиска
2.1 Введение .
2.1.1 Структура данных триангуляции.
2.1.2 Алгоритмы построения триангуляции Делоне
2.1.3 Триангуляция с ограничениями и графический поиск .
2.2 Триангуляция Делоне для точек, распределенных равномерно в ограниченной области
2.2.1 Свойства триангуляции в случае равномерного распределения точек
2.2.2 Полосовой алгоритм триангуляции Делопе.
2.2.3 Модифицированный полосовой алгоритм триангуляции Делоне
2.2.4 Вычислительный эксперимент . . .
2.3 Триангуляция Делоне для неравномерно распределенных точек
2.3.1 Фрактальные распределения точек
2.3.2 Многоуровневый полосовой алгоритм триангуляции
Делоне.
2.4 Триангуляция Делоне с ограничениями.
2.4.1 Итеративный алгоритм триангуляции Делоне с ограничениями
2.4.2 Точная триангуляция Делоне с наличием ограничений
2.4.3 Многоуровневый алгоритм триангуляции Делоне с
ограничениями
2.5 Применение триангуляции с ограничениями для решения задач графического поиска
2.5.1 Поиск па триангуляции с помощью иоисковой таблицы
2.5.2 Многоуровневая поисковая таблица.
2.5.3 Построение поисковой таблицы.
2.5.4 Классификация треугольников
2.5.5 Поиск по региональным запросам.
2.6 Выводы.
Приближенное вычисление оптимальной триангуляции
3.1 Введение
3.2 Локальные приближенные алгоритмы построения оптимальной триангуляции
3.2.1 Перестроения пар и четверок треугольников.
3.2.2 Перестроения в окрестностях точек.
3.3 Экспериментальное исследование локальных перестроений
на плоскости
3.3.1 Локальные иересгроення случайных точек
3.3.2 Локальные перестроения для специальных размещений точек
3.4 Экспериментальное исследование локальных перестроений
на однозначной поверхности
3.4.1 Модель случайной однозначной поверхности
3.4.2 Вычислительный эксперимент для точек случайной
поверхности.
3.4.3 Вычислительный эксперимент с минимизацией площади треугольников.
3.4.4 Вычислительный эксперимент лля точек гладкой поверхности
3.5 Выводы
4 Представление однозначной поверхности на основе триангуляции
4.1 Интерполяция однозначной поверхности
4.1.1 Вычисление нормальных векторов в узлах сетки . . .
4.1.2 Визуально гладкая интерполяция поверхности
4.1.3 Визуально гладкая интерполяция поверхности с разрывами наклона
4.2 Построение сечений однозначной поверхности
4.2.1 Построение коридора лля изолиний.
4.2.2 Построение ломаной минимальной длины в коридоре .
4.2.3 Сглаживание ломаной минимальной длины кривыми
4.2.4 Сглаживание ломаной минимальной длины локальными сплайнами
4.2.5 Построение визуально гладкой коридорной кривой . .
4.3 Выводы
5 Алгоритмы приближенного решения метрической задачи коммивояжера и ее обобщения для отрезков
5.1 Модификации приближенных алгоритмов с использованием
триангуляции и локальною поиска.
5.1.1 Модификация алгоритма дерева.
5.1.2 Алгоритм зацикленного дерева.
5.1.3 Поиск наилучшего цикла для склеивания
5.1.4 Результаты численного эксперимента.
5.2 Метрическая задача коммивояжера для отрезков
5.2.1 Постановка задачи
5.2.2 Погрешность алгоритмов решения метрической задачи коммивояжера для отрезков.
5.2.3 Алгоритмы на базе минимального остова компонен т .
5.2.4 Алгоритмы с использованием минимальных по весу
паросочстаний.
5.3 Реализация алгоритмов решения задачи коммивояжера на
дорожной сети.
5.3.1 Модель дорожной сети .
5.3.2 Вычисление матрицы кратчайших расстояний . . . .
5.4 Выводы.
Алгоритмы векторизации и распознавания растровых изображений
.1 Первичная векторизация растровых изображений с использованием триангуляции .
6.1.1 Нормализация цвета на растре
.1.2 Построение граничных линий на растре
6.1.3 Построение скелетных линий в одноцветных областях
6.2 Объектная векторизация растровых изображений с использованием триангуляции .
.2.1 Распознавание точечных, линейчатых и площадных
объектов по скелету одноцветной области.
6.2.2 Построение объектной триангулированной графовой
6.2.3 П1еобразование объектной триангулированной графовой модели и распознавание составных объектов . .
6.3 Выводы.
Реализация разработанных алгоритмов в программных комплексах
7.1 Система графического вывода СМОГ.
7.1.1 Система СМОГ для ЕС ЭВМ
7.1.2 Виртуальный графопостроитель.
7.1.3 Основные символы и фрагменты рисунки.
7.1.4 Изображение графиков функций.
7.1.5 Пакет программ иллюстративной графики в системе
автоматизации научных исследований .
7.2 Комплексы программ построения цифровых моделей рельефа местности
7.2.1 Пакет программ построения изолиний и разрезов однозначной поверхности.
7.2.2 Комплекс программ построения цифровых моделей
рельефа
7.3 Универсальная гсоинформацпонная система ГрафИн
7.3.1 Общие принципы архитектуры системы ГрафИн . . .
7.3.2 Подсистема векторизации ГрафИнВсктор
7.4 Технология создания трехмерных моделей объектов по плоским проекциям.
7.4.1 Восстановление матрицы перспективной проекции . .
7.4.2 Вычисление координат трехмерной точки
7.4.3 Параллельная проекция
7.4.4 Создание модели трехмерного объекта, содержащего
плоские грани
7.5 Алгоритмы зашиты информации и их программная реализация
7.5.1 Метод II шифрования открытым ключом и аутентификации данных
7.5.2 Модифицированный способ шифрования открытым
ключом.
7.5.3 Модификация метода для аутентификации данных
7.5.4 Программная реализация алгоритмов защиты информации
7.5.5 Реализация сверхдлииной арифметики
7.5.6 Реализация алгоритма генерирования ключей.
7.5.7 Реализация алгоритмов шифрования и дешифрования
7.5.8 Реализация алгоритмов аутентификации
7.6 Выводы.
Заключение
Литература


При участии автора на основе этой технологии создан программный комплекс для моделирования трехмерных объектов типа архитектурных сооружений, который можно использовать, как надстройку ГИС. Предлагаются новые способы шифования и аутентификации данных, являющиеся модификациями метода ЛБА и обладающие по сравнению с ним рядом преимуществ. На основе этих способов разработан программный комплекс система АВТОГРАФ. Результаты этой главы опубликованы в работах автора , , , , , , , , , , , , , , , , , , , , 9, 0. В настоящее время разработаны различные способы представления кривых и графиков. Для итерполяшш кривых применяются полиномиальные сплайны, в том числе в параметрическом виде 1, , . Хотя они единственны и лают паилучшее приближение в классе кусочнонепрерывных функций дефекта 2, но расчет их довольно громоздок, кроме того, весь сплайн зависит от любой из заданных точек, что не всегда соответствует практическим потребностям. Поэтому во многих графических системах используют локальные методы кривые Безье, Всплайны. Кроме того, в последнее время иптененвно развиваются методы изогеометричсской аппроксимации рациональными сплайнами , удовлетворяющих некоторым геометрическим свойствам. Локальные параметрические сплайны, являющиеся самыми простыми с вычислительной точки зрения, также обладают рядом изогеомстричсских свойств, однако слабая изученность препятствует их широкому использованию. Кривые, представленные полиномами, в частности сплайнами, отображаются после цифровой растровой интерполяции, осуществляемой либо непосредственно трудоемкими в вычислительном отношении алгоритмами. Поэтому для интерполяции полиномов необходимы более эффективные алгоритмы. При изображении сеток для графиков функций, а также номограмм, обычно используют эвристические алгоритмы, например 9, как в некоторых графических системах 3, 4. Однако для совершенно произвольных функциональных шкал необходимы более универсальные алгоритмы с изученными свойствами. Вторая задача цифровая растровая интерполяция кривых, решается путем разработки эффективных алгоритмов, иснользуюших исключительно быстрые целочисленные операции сложения, вычитания и сдвига по разрядной сетке и не применяющих обычную в таких алгоритмах операцию умножения, а также вещественную арифметику. Третья задача разметка координатных сеток графиков функций и номограмм различных функций решается путем строгого определения красивых последовательностей чисел, шкал на их основе и алгоритмов построения таких шкал. Для восстановления плоских кривых по исходному множеству п узловых точек чаше всего используют сплайны 3й степени в параметрическом представлении. I изменяется от 0 до некоторого положительного значения, например до 1. Так как выражения для полиномов А и У похожи друг на друга, в дальнейшем для краткости будем записывать выражения только для Х1. Дх, X Ху1. Набор производных 1,. ДагД
уравнений. При изображении кривых, когда пс требуется обязательной непрерывности вторых производных, с вычислительной точки зрения удобно использовать локальные сплайны, в которых производные х вычисляются по нескольким соседним точкам, минимально по трем х, я,1. Если по этим трем точкам построить квадратный полином, который при 1 равен 1, при 0 равен X, а при I 1 равен ц го значение его п1юнэводноГ1 при . Вычисленный по этим формулам простейший локальный сплайн неустойчив при неравномерном расположении узловых точек в нем образуются нежелательные петли и изгибы. В 1, разд. Соответствующий локальный параметрический сплайн можно построить по производным х, которые вычисляются следующим образом. Х при I , получив систему двух уравнении. Для локального сплайна, в отличие от полного, в общем случае не выполняются условия непрерывности второй пюпзводной и, следовательпо, кривизны, что. В то же время локальный сплайн удобнее полпого при изменении какойлибо одной узловой точки пересчитывать придется пс весь сплайн, а лишь 4 ближайших к точке отрезка. В разделе 1. Результаты данного раздела опубликованы в работах автора , .

Рекомендуемые диссертации данного раздела

28.06.2016

+ 100 бесплатных диссертаций

Дорогие друзья, в раздел "Бесплатные диссертации" добавлено 100 новых диссертаций. Желаем новых научных ...

15.02.2015

Добавлено 41611 диссертаций РГБ

В каталог сайта http://new-disser.ru добавлено новые диссертации РГБ 2013-2014 года. Желаем новых научных ...


Все новости

Время генерации: 0.290, запросов: 244