Эффективные алгоритмы обработки и отображения графических данных и их реализация в программных комплексах тема диссертации и автореферата по ВАК РФ 05.13.18, доктор технических наук Костюк, Юрий Леонидович

• Костюк, Юрий Леонидович
• доктор технических наук
• 2002

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

Введение

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 Вычислительный эксперимент для точек случайной поверхности.'.1.

3.4.3 Вычислительный эксперимент с минимизацией площади треугольников.

3.4.4 Вычислительный эксперимент для точек гладкой поверхности

3.5 Выводы.

Представление однозначной поверхности на основе триангуляции

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.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 Выводы.

Алгоритмы векторизации и распознавания растровых изображений

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

6.1.1 Нормализация цвета на растре.

6.1.2 Построение граничных линий на растре.

6.1.3 Построение скелетных линий в одноцветных областях

6.2 Объектная векторизация растровых изображений с использованием триангуляции.

6.2.1 Распознавание точечных, линейчатых и площадных объектов, по скелету одноцветной области.

6.2.2 Построение объектной триангулированной графовой модели.

6.2.3 Преобразование объектной триангулированной графовой модели и распознавание составных объектов

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 Метод RSA шифрования открытым ключом и аутентификации данных.

7.5.2 Модифицированный способ шифрования открытым ключом.

7.5.3 Модификация метода RSA для аутентификации данных

7.5.4 Программная реализация алгоритмов защиты информации

7.5.5 Реализация сверхдлинной арифметики.

7.5.6 Реализация алгоритма генерирования ключей.

7.5.7 Реализация алгоритмов шифрования и дешифрования

7.5.8 Реализация алгоритмов аутентификации.

7.6 Выводы.

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

Актуальность проблемы. В настоящее время интенсивно развиваются такие самостоятельные направления информатики, как компьютерная графика и вычислительная геометрия, которые, в свою очередь, разрабатывают структуры данных и алгоритмы, применяемые в ряде прикладных областей, в частности, в геоинформационных системах (ГИС) и системах обработки данных (СОД) дистанционного зондирования (ДЗ).

В большинстве случаев объекты исследования современных ГИС и СОД ДЗ считаются планарными, но часто они характеризуются не только привязкой на плоскости, но и значениями пространственно распределенных параметров (например, температуры, уровня загрязнения, высот точек поверхности Земли или дна мирового океана). В ряде случаев объекты являются трехмерными, например модели архитектурных сооружений на поверхности Земли. При отображении таких объектов на современных цифровых устройствах необходимо формировать растровые изображения, а при вводе графической информации — распознавать объекты на растровых изображениях. Поэтому в универсальных ГИС и СОД ДЗ необходима реализация практически всех известных алгоритмов компьютерной графики и вычислительной геометрии, и поэтому актуальной является задача - разработки таких новых алгоритмов, которые бы увеличивали скорость обработки данных и расширяли бы функциональные возможности систем.

В настоящее время разработаны различные способы представления кривых и графиков, в частности, интерполяционные полиномиальные сплайны, предложенные И. Шенбергом [1, 31, 32]. Хотя они единственны и дают наилучшее приближение в классе кусочно-непрерывных функций дефекта 2, но расчет их довольно громоздок, кроме того, любой отрезок сплайна зависит от всех заданных точек, что не всегда соответствует практическим потребностям. Поэтому часто используют локальные методы — кривые

Безье, В-сплайны, а также некоторые простейшие виды локальных параметрических сплайнов [7, 21, 35, 98, 103, 117, 118, 125]. Локальные параметрические сплайны, являющиеся самыми простыми с вычислительной точки зрения, обладают рядом полезных свойств, однако слабая изученность препятствует их широкому использованию.

Кривые, представленные полиномами, в частности сплайнами, отображаются после цифровой (растровой) интерполяции, осуществляемой либо непосредственно трудоемкими в вычислительном отношении алгоритмами, либо через аппроксимацию ломаными линиями [104]. Брезенхем предложил эффективные алгоритмы цифровой интерполяции прямых и окружностей, использующие только быстрые операции над целыми числами [104]. Для интерполяции полиномов также необходима разработка более эффективных алгоритмов.

При изображении сеток для графиков функций с произвольным функциональным масштабом, а также номограмм, используют эвристический алгоритм, предложенный С. Н. Борисовым [9], который не всегда корректен. Поэтому для построения функциональных шкал необходимы более универсальные алгоритмы с изученными свойствами.

Триангуляция является одной из важнейших структур, на основе которой разработаны эффективные алгоритмы решения многочисленных задач вычислительной геометрии. Из всех видов триангуляций важнейшее значение имеет та, которую предложил Б. Н. Делоне [25]. Важное значение имеет также триангуляция с ограничениями, в частности, для решения задачи локализации точки на триангуляции. В настоящее время известны достаточно эффективные алгоритмы Д. Т. Ли и Б. Шехтера [169], А. В. Скворцова [111], А. Л. Фукса [120, 121] построения триангуляции Делоне, алгоритм Ф. Препарата и др. [152] построения триангуляции с ограничениями , а также асимптотически эффективный алгоритм Д. Г. Киркпатрика [164] для локализации точки на триангуляции. Однако до сих пор остаются не исследованными ряд свойств триангуляции Делоне, что препятствует разработке еще более эффективных и удобных на практике алгоритмов для решения как перечисленных, так и ряда смежных задач.

В отличие от триангуляции Делоне, которую можно вычислить за время 0(п log п) в наихудшем и 0(п) в среднем [102,111], оптимальную триангуляцию, построение которой, по всей видимости, относится к NP-полным задачам, можно вычислить практически лишь за экспоненциальное время. Жадную триангуляцию можно считать приближением оптимальной. Ее строит жадный алгоритм, предложенный П. Н. Джильбертом [153], за время 0(n2logn), что слишком много для практического применения, поэтому необходимы эффективные алгоритмы приближенного вычисления оптимальной триангуляции.

В настоящее время известно много методов кусочно-непрерывной и кусочно-гладкой интерполяции однозначной поверхности на прямоугольной сетке, в частности, методы С. А. Кунса, П. Безье, Дж. Алберга [1, 32, 35, 103, 126]. Однако для многих приложений, в частности ГИС, прямоугольную сетку использовать нежелательно, так как исходные данные обычно являются нерегулярными, и тогда переход к прямоугольной сетке приведет к их недопустимому огрублению. Кроме того, в построенной поверхности практически невозможно учесть линии разлома. Поэтому для построения однозначной поверхности целесообразно использовать треугольную сетку, построенную на триангуляции Делоне по проекциям исходных точек. Дж. Фарин [148] разработал способ построения кусочно-гладкой поверхности Безье на совокупности треугольников, но для этого необходимо предварительное вычисление нормальных векторов к касательным плоскостям в узлах сетки. Для построения гладкой поверхности с учетом линий разлома необходима разработка специальных методов.

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

Задача коммивояжера (ЗК) и ее различные обобщения [96] имеют многочисленные приложения в геоинформационных системах, системах управления территориями, системах автоматизированного проектирования. ЗК является NP-трудной, и для нее разработано множество эвристических и приближенных алгоритмов решения как для общего случая, так и для метрического пространства [161]. Для ряда эвристических алгоритмов, например одного из наилучших из них — алгоритма С. Лина и Б. У. Кер-нигана — время работы и качество окончательного решения зависит от начального варианта маршрута. Вследствие этого актуальным является разработка быстрых алгоритмов решения ЗК с высокой степенью приближения. ЗК для отрезков отличается тем, что маршрут должен содержать заранее заданные отрезки [170]. Если эта задача метрическая, то ее сведение к обычной ЗК переводит в разряд неметрических, а это приводит к получению решения худшего качества, поэтому актуальным является разработка специальных алгоритмов ее решения.

Графическая информация вводится в компьютер в виде растрового изображения, поэтому одной из важнейших задач является задача векторизации — распознавание на растре изображений графических объектов, прежде всего, прямолинейных отрезков. Известные способы векторизации опираются на введенное А. Розенфельдом [105] понятие скелета линии. На втором этапе векторизации распознаются более сложные типовые объекты на основе распознанных отрезков линий [106, 107, 181]. При этом известные алгоритмы обладают большой трудоемкостью и требуют активного вмешательства пользователя в процесс распознавания, поэтому актуальна проблема создания новых подходов к решению задачи векторизации.

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

При практическом применении ГИС часто приходится иметь дело с конфиденциальными данными. Как при хранении, так и при пересылке по компьютерным сетям таких данных, их необходимо шифровать, причем для более высокой надежности метод шифрования должен иметь открытый ключ. Кроме того, часто также необходимо аутентифицировать важные данные. В настоящее время наиболее совершенным методом шифрования открытым ключом и аутентификации данных при относительно невысокой трудоемкости считается метод RSA Ривеста, Шамира и Адле-мана [101, 176]. Препятствием повсеместного использования метода RSA является то, что он запатентован, поэтому актуальной задачей является разработка новых эффективных криптографических методов.

Решению рассмотренных проблем и посвящена настоящая работа.

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

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

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

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

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

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

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

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

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

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

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

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

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

11. Проведено исследование метрической задачи коммивояжера для ориентированных, неориентированных и смешанных отрезков. Предложены новые специальные способы приближенного решения всех вариантов этой задачи за время от O(nlogn) до 0(п3), дающие решения различного качества.

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

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

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

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

- система графического вывода СМОГ (первый вариант — для ЭВМ типа М-20, второй — для ЕС ЭВМ и двух типов операционных систем (ДОС и ОС ЕС ЭВМ); на ее основе разработан ряд проблемно-ориентированных надстроек;

- комплекс программ построения цифровых моделей рельефа (для Windows 95/98/2000);

- универсальная инструментальная ГИС ГрафИн (для Windows 95/98/2000) и ее надстройка— подситема векторизации ГрафИн-Вектор;

- программный комплекс (для Windows 95/98/2000) моделирования трехмерных объектов типа архитектурных сооружений;

- система шифрования открытым ключом и аутентификации АВТОГРАФ (для MS DOS и Windows 95/98/2000).

Внедрение результатов работы. Система графического вывода СМОГ для ЕС ЭВМ вместе с разработанными на ее основе проблемно-ориентированными надстройками была внедрена на ряде предприятий, где она использовалась в научных исследованиях. Комплекс программ построения цифровых моделей рельефа использовался при выполнении работ по созданию цифровых карт местности для республик Алтай и Хакасия, одного из районов Красноярского края, а также города Томска. Универсальная инструментальная ГИС ГрафИн использована в НПО Сибгеоинформатика при выполнении ряда прикладных разработок по заказам различных предприятий. Система ГрафИн вместе с подсистемой векторизации ГрафИн-Вектор внедрена на госпредприятии Инжгеодезия.

Кроме того, материалы исследований использовались при чтении курсов лекций "Компьютерная графика" и "Вычислительная геометрия и интерактивные графические системы" на факультете информатики Томского госуниверситета.

На защиту автором выносятся следующие положения.

1. Новые варианты локальных параметрических сплайнов 3-й степени и исследование их свойств.

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

3. Новый способ построения красивых функциональных шкал для произвольных функциональных масштабов, исследование свойств шкал.

4. Исследование свойств триангуляции Делоне для равномерного и фрактального распределений точек и полученные на его основе новые эффективные способы построения триангуляции Делоне, новые способы графического поиска.

5. Новые способы приближенного построения оптимальной триангуляции на основе локальных перестроений триангуляции Делоне.

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

7. Новый метод построения сглаженных семейств сечений однозначных поверхностей с помощью вспомогательных коридоров.

8. Новые эффективные алгоритмы приближенного решения метрической задачи коммивояжера для точек и отрезков на основе использования в качестве вспомогательной структуры триангуляции Делоне.

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

10. Новые способы шифрования и аутентификации данных на основе модификации метода RSA.

11. Программные комплексы, разработанные с использованием предложенных в работе методов, способов и алгоритмов.

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

1. На международной конференции "Автоматизация научных исследований на основе применения ЭВМ", Новосибирск, СО АН СССР, 1972.

2. На всесоюзном семинаре "Использование ЭВМ при составлении океанографических атласов и пособий, Обнинск, ВНИИГМИ-МЦД, 1976.

3. На всесоюзной конференции "Проблемы совершенствования управления народным хозяйством на основе средств вычислительной техники (Управление-86)", Москва, ВНИИПОУ, 1986.

4. На всесоюзной конференции "Методы и средства обработки сложной графической информации, Горький, Горьковский университет, 1988.

5. На научно-практической конференции "Наука, образование, производство: интеграция и новые технологии", Анжеро-Судженск, Томский государственный педагогический университет, 1997.

6. На Третьем сибирском конгрессе по прикладной и индустриальной математике (ИНПРИМ-98), Новосибирск, СО РАН, 1998.

7. На Международной сибирской конференции по исследованию операций (SCOR-98), Новосибирск, Институт математики СО РАН, 1998.

8. На Шестом международном семинаре "Распределенная обработка информации", Новосибирск, СО РАН, 1998.

9. На международной конференции " Интеркарто-4" Барнаул, 1998.

10. На международной конференции "Дискретный анализ и исследование операций" (DAOR'2000)", Новосибирск, Институт математики СО РАН, 2000.

11. На Четвертом сибирском конгрессе по прикладной и индустриальной математике (ИНПРИМ-2000), Новосибирск, СО РАН, 2000.

12. На научной конференции "Фундаментальные проблемы охраны окружающей среды и экологии природно-территориальных комплексов Западной Сибири", Горно-Алтайск, Алтайский государственный университет, 2000.

13. На международной научно-практической конференции "Геоинфор-матика-2000", Томск, Томский государственный университет, 2000.

14. На сибирской конференции "Методы сплайн-функций", Новосибирск, Институт математики СО РАН, 2001.

15. На всероссийской научно-практической конференции "Новые технологии и комплексные решения: наука, образование, производство", Анжеро-Судженск, Кемеровский государственный университет, 2001.

16. На всероссийской конференции, посвященной 90-летию со дня рождения А. А. Ляпунова, Новосибирск, 2001.

По результатам выполненных исследований опубликовано 57 печатных работ, из них 8 статей в реферируемых научных журналах, 4 изобретения, 24 статьи в сборниках научных трудов и сборниках докладов на международных, всесоюзных и всероссийских конференциях, 2 брошюры, 19 тезисов докладов на конференциях и информационных листков в изданиях ЦНТИ.

Структура диссертации.

Работа состоит из введения, семи глав, заключения, списка литературы и приложения, включающего документы о внедрении.

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

Результаты этой главы опубликованы в работах автора [17, 33, 42, 45, 48, 50].

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

Результаты этой главы опубликованы в работах автора [51, 84,111,108, 112].

Третья глава посвящена задаче приближенного вычисления оптимальной триангуляции, имеющей минимальную сумму длин ребер (минимальный вес). Предлагается способ последовательных локальных перестроений исходной триангуляции, в котором перестроение ведется в окрестностях треугольника или точки. Способ можно реализовать за среднее время О(п), что гораздо лучше жадного алгоритма, имеющего временную сложность 0(n2 log п), причем вес полученной триангуляции будет даже меньше, чем вес жадной триангуляции. Способ обобщается для точек, заданных на однозначной поверхности z F(x,y), при этом возможно применение ряда других критериев оптимальности.

Результаты этой главы опубликованы в работах автора [64, 69].

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

Полученные в этой главе результаты опубликованы в работах автора [53, 65, 76, 77, 78, 80].

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

Рассмотренные в этой главе вопросы нашли отражение в работах автора [29, 30, 55, 58, 61, 67, 68, 75].

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

Результаты этой главы опубликованы в работах автора [54, 70, 71, 72, 79, 81, 82, 83].

Седьмая глава посвящена вопросам практической реализации разработанных алгоритмов в программных комплексах.

Рассматривается два разработанных варианта системы графического вывода СМОГ, один из которых реализован для ЭВМ типа М-20, второй — для ЕС ЭВМ и двух типов операционных систем (ДОС и ОС ЕС ЭВМ) и на основе которой разработан ряд проблемно-ориентированных надстроек.

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

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

Предлагается технология создания трехмерных моделей объектов по плоским проекциям (фотографиям, планам, чертежам), ориентированная на макетирование зданий на плане местности. Технология использует особенности представления объектов, состоящих из плоских граней, и минимизирует действия пользователя при построении модели. При участии автора на основе этой технологии создан программный комплекс для моделирования трехмерных объектов типа архитектурных сооружений, который можно использовать, как надстройку ГИС.

Предлагаются новые способы шифрования и аутентификации данных, являющиеся модификациями метода RSA и обладающие по сравнению с ним рядом преимуществ. На основе этих способов разработан программный комплекс — система АВТОГРА.Ф.

Результаты этой главы опубликованы в работах автора [15, 16, 18, 19, 20, 43, 44, 46, 47, 49, 52, 56, 57, 59, 60, 62, 63, 66, 73, 74, 109, 110].

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Костюк, Юрий Леонидович

7.6 Выводы

1. Разработаны два варианта системы графического вывода СМОГ. Первый — для ЭВМ типа М-20, второй — для ЕС ЭВМ и двух типов операционных систем (ДОС и ОС ЕС ЭВМ). На нижнем уровне системы СМОГ для ЕС ЭВМ реализован виртуальный графопостроитель, благодаря чему система легко расширяется для вывода на различные типы цифровых графопостроителей. По базовым функциональным возможностям система превосходила большинство имевшихся в тот период времени систем графического вывода. На ее основе разработан ряд проблемно-ориентированных надстроек.

2. Разработанный при участии автора комплекс программ построения цифровых моделей рельефа (для Windows 95/98/2000) позволяет строить триангуляцию однозначной поверхности с ограничениями разных типов, вычислять сглаженные коридорные изолинии и разрезы, строить визуально гладкую поверхность с учетом линий разломов. Комплекс по своим функциональным возможностям превосходит известные аналоги.

3. В*разработанной при участии автора инструментальной ГИС ГрафИн (для Windows 95/98/2000) реализован ряд алгоритмов, изложенных в данной работе. На ее основе при участии автора создана подсистема векторизации ГрафИн-Вектор, в которой реализованы алгоритмы, описанные в главе 6. Благодаря высокой степени автоматизации подсистема обеспечивает большую скорость обработки данных по сравнению с известными системами векторизации.

4. Разработана технология создания трехмерных моделей объектов по плоским проекциям (фотографиям, планам, чертежам), ориентированная на макетирование зданий на плане местности. Технология использует особенности представления объектов, состоящих из плоских граней, и минимизирует действия пользователя при построении модели. При участии автора на основе этой технологии создан программный комплекс (для Windows 95/98/2000) моделирования трехмерных объектов типа архитектурных сооружений, который можно использовать, как надстройку ГИС.

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

12. Рассмотрена задача коммивояжера на дорожной сети города, для нее разработан эффективный алгоритм вычисления матрицы кратчайших расстояний, исследованы свойства матрицы.

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

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

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

16. Предложены новые способы шифрования и аутентификации данных, являющиеся модификациями метода RSA и обладающие по сравнению с ним рядом преимуществ.

17. Автором или при участии автора созданы следующие программные комплексы, в которых реализованы разработанные в работе алгоритмы:

- система графического вывода СМОГ (первый вариант — для ЭВМ типа М-20, второй — для ЕС ЭВМ и двух типов операционных систем (ДОС и ОС ЕС ЭВМ); на ее основе разработан ряд проблемно-ориентированных надстроек;

- комплекс программ построения цифровых моделей рельефа (для Windows 95/98/2000);

- универсальная инструментальная ГИС ГрафИн (для и Windows 95/98/2000) и ее надстройка — подсистема векторизации ГрафИн-Вектор;

- программный комплекс (для и Windows 95/98/2000) моделирования трехмерных объектов типа архитектурных сооружений;

- система шифрования открытым ключом и аутентификации АВТОГРАФ (для MS DOS и Windows 95/98/2000).

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

1. Алберг Дж., Нилъсон Э., Уолш Дж. Теория сплайнов и ее приложения. - М.: Мир, 1972.

2. Алферов А. П., Зубов А. Ю., Кузьмин А. С., Черемушкин А. В. Основы криптографии: Учебное пособие. М.: Гелиос АРВ, 2001.

3. Андрюшин О. Ф., Ершов В. П., Неронов Н. Н. Автоматизация документирования данных прикладных океанографических исследований: Препринт. — Севастополь: Изд-во МГИ АН УССР, 1985.

4. Андрюшин О. Ф., Ляпичев Г. И., Поддубный В. В. Моделирование навигационных измерений в имитационной системе сбора океанографической информации // Судостроительная промышленность. Сер. 8, N 10, 1987. С 64-71.

5. Аронов Б.С. Методы математической обработки геологических данных на ЭВМ. М.: Недра, 1977.

6. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

7. Баяковский Ю.М., Галактионов В.А., Михайлова Т.Н. Графор: Графическое расширение фортрана. М.: Наука, 1985.

8. Бобир Н. Я., Лобанов А. Н., Федорук Г. Д. Фотограмметрия. М: Недра, 1974.

9. Борисов С. Н. Автоматизация расчета шкал номограмм // Номографический сборник N 2, М.: ВЦ АН СССР, 1964. С. 85-90.

10. Вирт Н. Алгоритмы и структуры данных. Пер. с англ. М.: Мир, 1989.

11. Выгодский М. Я. Справочник по высшей математике. 8-е изд. М.: Наука, 1966.

12. Гаек Я., Шидак 3. Теория ранговых критериев. М.: Наука, 1971.

13. Гилой В. Интерактивная машинная графика. М.: Мир, 1982.

14. Гимади Э. X., Глебов Н. И., Сердюков А. И. Алгоритм для приближенного решеия задачи коммивояжера и его вероятностный анализ // Сиб. журн. исслед. операций, 1994, т. 1, N 2. С. 8-17.

15. Гладких Б. А., Бородин А.Н., Ивашинцов И. А., Костюк Ю. JI. СМОГ система математического обеспечения графопостроителя // Автоматизация научных исследований на основе применения ЭВМ (Труды конференции), т.2. - Новосибирск: СО АН СССР, 1972. С. 93-98.

16. Гладких Б. А., Костюк К). Л., Позолотин В. А. СМОГ система математического обеспечения графопостроителя. - Томск: Изд-во Томск, ун-та, 1974. - 76 с.

17. Гладких Б. А., Золотенков В. В., Костюк Ю. Л. Цифровой интерполятор: А.с. N 557370 // Бюлл. изобретений N 17, 1977.

18. Гладких Б. А., Золотенков В. В., Костюк Ю. Л. Устройство для управления графопостроителем: А.с. N 610108 // Бюлл. изобретений N 21, 1978.

19. Гладких Б. А., Костюк Ю. Л. Система графического вывода СМОГ и ее реализация на ЕС ЭВМ // Автоматизация эксперимента и машинная графика. Томск: Изд-во Томск, ун-та, 1977. С. 103-115.

20. Гладких Б. А., Костюк К). Л. Общие принципы системы математического обеспечения графического вывода СМОГ для ЕС ЭВМ // Использование ЭВМ при составлении океанографических атласов и пособий. Труды ВНИИГМИ-МЦД, вып. 54, 1978. С. 33-38.

21. ГРАФИК система математического обеспечения ЭВМ и графопостроителей / Под ред. Е. Л. Ющенко. - Кишинев: Штиинца, 1975.

22. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. М.: Мир, 1975.

23. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

24. Деза М. М., Лфан М. Геометрия разрезов и метрик. М.: МЦНМО, 2001.

25. Делоне Б. Н. О пустом шаре // Известия АН СССР, VII серия, т. б, 1934. С. 793-800.

26. Джермейн К. Программирование на IBM/360. М.: Мир, 1971.

27. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976.

28. Ершов А. П., Кожу хин Г. И., Поттосин И. В. Руководство к пользованию системой АЛЬФА. Новосибирск: Наука, 1968.

29. Жихарев С. А., Костюк Ю. Л. Локальный поиск в метрической задаче коммивояжера // Геоинформатика. Теория и практика. Вып. 1. Томск: Изд-во Томск, ун-та, 1998. С. 84-95.

30. Жихарев С. А., Костюк Ю. Л: Использование локального поиска в метрической задаче коммивояжера // Известия вузов. Физика, т.42, N 3, 1999. С. 129-134.

31. Завьялов Ю. С. Интерполяция кубическими многозвенниками // Вычислительные системы. N 38, Новосибирск, 1970.

32. Завьялов Ю. С., Квасов Б. И., Мирошниченко В. Л. Методы сплайн-функций. М.: Наука, 1980.

33. Золотенков В. В., Костюк Ю. Л. Цифровая интерполяция полиномов, не требующая умножения // Управляющие системы и машины, N 3, 1984. С. 31-34.

34. Иваненко С.А. Адаптивные сетки и сетки на поверхности // Ж. выч. мат. и мат. физики., т. 33, N 9, 1993, с. 1333-1351.

35. Иванов В.П., Батраков А.С. Трехмерная компьютерная графика. -М.: Радио и связь, 1995.

36. Интеллектуальное программное обеспечение. Easy Trace Group, 1999. http://www.easytrace.com

37. Квасов Б. И. Изогеометрическая аппроксимация сплайнами: Учеб. пособие. Новосибирск: Новосибирский ун-т, 1998.

38. Кнут Д. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. М.: Мир, 1976.

39. Кнут Д. Искусство программирования для ЭВМ. Т.2. Получисленные алгоритмы. М.: Мир, 1977.

40. Кнут Д. Искусство программирования для ЭВМ. Т.З. Сортировка и поиск. М.: Мир, 1978.

41. Ковин Р.В., Марков Н.Г. Цифровые модели рельефов в среде ГИС Map Info Professional / / .Геоинформатика-2000. Труды межд. научно-практ. конф. Томск: Изд-во Томск, ун-та, 2000, с. 96-101.

42. Костюк Ю. JI. Красивые разбиения функциональных шкал // Прикладная математика и кибернетика. Томск: Изд-во Томск, ун-та,1976. С. 98-106.

43. Костюк Ю. JI. СМОГ система математического обеспечения графического вывода для ЕС ЭВМ. - Томск: Изд-во Томск, ун-та, 1977. - 104 с.

44. Костюк К). J1. Обзор систем графического вывода // Автоматизация эксперимента и машинная графика. Томск: Изд-во Томск, ун-та,1977. С. 90-102.

45. Костюк Ю. JI. Применение сплайнов для изображения линий в машинной графике // Автоматизация эксперимента и машинная графика. Томск: Изд-во Томск, ун-та, 1977. С. 116-130.

46. Костюк Ю. Д., Фукс A. JI. Язык представления рисунков в системе СМОГ // Автоматизация эксперимента и машинная графика. -Томск: Изд-во Томск, ун-та, 1977. С. 131-139.

47. Костюк Ю. JI. Универсальная процедура рисования графиков // Автоматизация эксперимента и машинная графика. Томск: Изд-во Томск, ун-та, 1977. С. 140-147.

48. Костюк Ю. JI. Изображение плоских кривых локальными сплайнами // Использование ЭВМ при составлении океанографических атласов и пособий. Труды ВНИИГМИ-МЦД, вып. 54, 1978. С. 39-45.

49. Костюк Ю. JI., Фукс A. JI. СМОГ система математического обеспечения графического вывода для ЕС ЭВМ. - Томск: ЦНТИ, информационный лист N 4-84, 1984. - 3 с.

50. Костюк Ю. JI. Алгоритмы разбиения функциональных шкал красивыми последовательностями // Известия АН СССР. Техническая кибернетика, N 1, 1985. С. 160-161.

51. Костюк Ю. JL, Грибсль В. А. Обработка и изображение сплошных площадей в машинной графике // Известия АН СССР. Техническая кибернетика^ 5, 1987. С. 213.

52. Костюк Ю. JL, Фукс A. JI. Генерализация кривых в иллюстративной машинной графике // Методы и средства обработки сложной графической информации. Тезисы докл. всес. конф., ч. 1, сентябрь, 1988 г.- Горький: Горьк. ун-т. С. 84.

53. Костюк Ю. J1. Быстрый алгоритм классификации точек // Методы и средства обработки сложной графической информации. Тезисы докл. всес. конф., ч. 1, сентябрь, 1988 г. Горький: Горьк. ун-т. С. 85.

54. Костюк Ю. Д., Грибель В. А. Размещение и отображение на карте точечных объектов // Методы и средства обработки сложной графической информации. Тезисы докл. всес. конф., ч. 2, сентябрь, 1988 г.- Горький: Горьк. ун-т. С. 60-61.

55. Костюк Ю. JI. Способ шифрования сообщений открытым ключом и система для его осуществления: патент РФ N 2071180 // Бюлл. изобретений N 36, 1996.

56. Костюк Ю. JT. Способ электронного подписывания сообщений (его варианты): патент РФ N 2110157 // Бюлл. изобретений N 12, 1998.

57. Костюк Ю. JL Система шифрования открытым ключом и электронного подписывания " Автограф" // Научно-технические разработки ТГУ. Каталог. Томск: Изд-во Томск. ЦНТИ, 1998. - С. 90.

58. Костюк Ю. Л. Модификация метода RSA для шифрования открытым ключом и электронного подписывания // Международная Сибирская конференция по исследованию операций (SCOR-98). Материалы конф. Новосибирск: Изд-во Института математики, 1998. С. 128.

59. Костюк Ю. Л. Усовершенствование метода RSA для криптосистемы с открытым ключом // Распределенная обработка информации. Труды Шестого международного семинара, 23-25 июня 1998 г. Новосибирск: Изд-во СО РАН, 1998. С. 415-417.

60. Костюк Ю. Л., Фукс А. Л. Приближенное вычисление оптимальной триангуляции // Геоинформатика. Теория и практика. Вып. 1. -Томск: Изд-во Томск, ун-та, 1998. С. 61-66.

61. Костюк Ю. Л., Фукс А. Л. Построение и аппроксимация изолиний однозначной поверхности, заданной набором исходных точек // Геоинформатика. Теория и практика. Вып. 1. Томск: Изд-во Томск, ун-та, 1998. С. 119-126.

62. Костюк Ю. Л., Гриценко В. Г., Парамонов А. С. Технология создания трехмерных моделей объектов по плоским проекциям и ее применение в геоинформатике // Геоинформатика. Теория и практика. Вып. 1. -Томск: Изд-во Томск, ун-та, 1998. С. 96-106.

63. Костюк Ю. Л., Жихарев С. А. Эффективный алгоритм приближенного решения метрической задачи коммивояжера // Дискретный анализ и исследование операций, 2000, сер. 2, т. 7, N 1. С. 65-74.

64. Костюк Ю. Л., Жихарев С. А. Алгоритмы приближенного решения метрической задачи коммивояжера // Международная конференция

65. Дискретный анализ и исследование операций" (DAOR'2000): Материалы конф. (Новосибирск, 26 июня 1 июля). - Новосибирск: Изд-во Института математики, 2000. С. 151.

66. Костюк Ю. J1. Метрическая задача коммивояжера для отрезков // Автоматика и телемеханика, 2000, N 3. С. 142-148.

67. Костюк Ю. J1. Представление рельефа земной поверхности в геоинформационных системах // Геоинформатика-2000: Труды межд. научно-практ. конф. Томск: Изд-во Томск, ун-та, 2000. С. 12-17.

68. Костюк Ю. Л., Фукс А. Л. Гладкая аппроксимация изолиний однозначной поверхности, заданной нерегулярным набором точек // Геоинформатика-2000: Труды межд. научно-практ. конф. Томск: Изд-во Томск, ун-та, 2000. С. 37-41.

69. Костюк Ю. Л., Фукс А. Л. Визуально гладкая аппроксимация однозначной поверхности, заданной нерегулярным набором точек // Геоинформатика-2000: Труды межд. научно-практ. конф. Томск: Изд-во Томск, ун-та, 2000. С. 41-45.

70. Костюк Ю. Л., Новиков Ю. Л. Векторизация растровых изображений с использованием триангуляции // Геоинформатика-2000: Труды межд. научно-практ. конф. Томск: Изд-во Томск, ун-та, 2000. С. 55-58.

71. Костюк Ю. Л., Новиков Ю. Л. Графовые модели на основе триангуляции в задаче векторизации цветных растровых изображений // Конф., посвященная 90-летию со дня рожд. А. А. Ляпунова, 8-11 октября 2001 г. Сб. докладов. Новосибирск, 2001. С. 301-315.

72. Костюк Ю. Л., Новиков Ю. Л. Графовые модели цветных растровых изображений высокого разрешения // Вестник Томского гос. ун-та, N 273. С. 153-161.

73. Костюк Ю. Л. Графический поиск с использованием триангуляции и клеточного разбиения // Вестник Томского гос. ун-та, N 273. С. 147152.

74. Кошель С.М., Мусин О.Р. Методы цифрового моделирования: кри-гинг и радиальная интерполяция // Информационный бюллетень ГИС-ассоциации, N 4(26)-5(27), 2000, с. 32-33.

75. Кошкарев А. В., Тикунов В. С. Геоинформатика. М.: Картгео-центр - Геоиздат, 1993.

76. Кравцова В.И. Космические методы картографирования. М.: Изд-во МГУ, 1995.

77. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.

78. Ларионов А. М. ЕС ЭВМ. М.: Статистика, 1973.

79. Лившиц К. И. Сглаживание экспериментальных данных сплайнами. Томск: Изд-во Томск, ун-та, 1991.

80. Лисейкин В.Д. Обзор методов построения структурных адаптивных сеток // Ж. выч. мат. и мат. физики., Т. 36, N 1, 1996, с. 3-41.

81. Лисицкий Д.В. Основные принципы цифрового картографирования местности. М.: Недра, 1988.

82. Мартынов М. Г. Пространственные методы доступа // Программирование, 1998, N 3. С. 59-69.

83. Математика и САПР: в 2-х кн. Кн. 1 / Шенен П., Коснар М., Гардан И. и др. М.: Мир, 1988.

84. Математика и САПР: в 2-х кн. Кн. 2 / Жермен-Лакур П., Жорж П., Пистр Ф., Безье П. М.: Мир, 1989.

85. Меламед И. И., Сергеев С. И., Сигал И. X. Задача коммивояжера. Вопросы теории // Автоматика и телемеханика, 1989, N 9. С. 3-33.

86. Обработка и отображение информации в растровых графических системах. Минск: ИТК АН БССР, 1989.

87. Павлидис У. Алгоритмы машинной графики и обработка изображений. В 2-х книгах. М.: Мир, 1985.

88. Пакет программ оцифровки картографических материалов MapEdit, версия 2.1. Руководство пользователя. М.: АО Резидент, 1996.

89. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность. — М.: Мир, 1985.

90. Патент США N 4405829, кл. Н 04К 1/00, 1983.

91. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. -М.: Мир. 1989.

92. Роджерс Д., Адаме Дж. Математические основы машинной графики. М.: Машиностроение, 1980. - 240 с.

93. Роджерс Д. Алгоритмические основы машинной графики. -- М.: Мир, 1989.

94. Розенфельд А. Распознавание и обработка изображений с помощью вычислительных машин. — М.: Мир, 1972.

95. Садыков С.С., Кан В.Н., Самандаров И.Р. Методы выделения структурных признаков изображений. — Ташкент: Фан, 1990.

96. Семенков О. И. и др. Методы обработки и формирования растровых изображений. — Минск: НТК АН БССР, 1986.

97. Скворцов А. В., Костюк Ю. J1. Сравнительный анализ алгоритмов построения триангуляции Делоне // Международная Сибирская конференция по исследованию операций (SCOR- 98). Материалы конф. -Новосибирск: Изд-во Института математики, 1998. С. 138.

98. Скворцов А. В., Костюк Ю. JI. Универсальная графическая информационная система ГрафИн // Третий сибирский конгресс по прикладной и индустриальной математике (ИНПРИМ 98), Тезисы докладов, ч. V. Новосибирск: Изд-во Института математики, 1998. С. 65.

99. Скворцов А. В., Костюк Ю. Л. Система ГрафИн, как пример современной интегрированной ГИС // Интеркарто-4 (Материалы межд. конф.), Барнаул, 1998. С. 152-157.

100. Фукс A. JI. Быстрый алгоритм триагуляции Делоне, основанный на предварительной обработке набора точек // Геоинформатика-2000: Труды межд. научно-практ. конф. Томск: Изд-во Томск, ун-та, 2000. С. 45-50.

101. Хованский Г. С. Основы номографии. М.: Наука, 1976. - 352 с.

102. Чибисов В. В. Вычерчивание и оформление номограмм на графопостроителе, подключенном к машине БЭСМ-6 // Номографический сборник N 9, М.: ВЦ АН СССР, 1973. С. 169-176.

103. Чибисов В. В. Автоматизация построения номограмм и графиков устройством АЦПУ и графопостроителем // Проблемы повышения эффективности БЭСМ-6, Вильнюс, 1974.

104. ARC/INFO User's Guide: Surface Modeling with TIN. Environmental Systems Research Institute Inc., NY, 1992.

105. Belussi A., Faloutos C. Estimating the Selectivity of Spatial Queries Using the "Correlation" Fractal Dimension // VLDB. 1995. P. 299-310.

106. Rob. and Autorn., Philadelphia, Pa, Apr. 24-29, 1988. Philadelphia, Pa, 1988. P. 1798-1803.

107. Brown J.L. Vertex Based Data Dependent Triangulations // Comput. Aided Geom. Des., Vol. 8, N 3, 1991. P. 239-251.

108. Centeno J. S. Segmentation of Thematic Maps Using Colour and Spatial Attributes // Tombre K. and Chhabra A. K., ed. Graphics Recognition-Algorithms and Systems, vol. 1389 of Lecture Notes in Computer Science, Springer-Verlag, April 1998. P. 221-230.

109. Chazelle В. M., Edelsbrunner H. Optimal Solutions for a Class of Point Retrival Problems // Tech. Rep. CS-84-16, Dept. of Computer Science, Brown University, July, 1984.

110. Chrisman N. Exploring Geographic Information Systems. N.Y.: Wiley, 1997.

111. Christofides N. Worst-Case Analysis of a New Heuristic for the Traveling Salesman Problem // Symp. on Algorithms and Coinplexit. Dep. of Computer Sci., Carnegie-Mellon Univ., Apr. 1976.

112. Diffie W., Hellman M. E. New Directions in Cryptography // IEEE Trans. Inform. Theory, IT, N 6, 1976. P. 644-654.

113. Dori Dov, Wenyin Liu. Automated CAD Conversion with the Machine Drawing Understanding System: Concepts, Algorithms, and Performance // IEEE Transactions on Systems, Man, and Cybernetics, 29, 4, 1999. P. 411-416.

114. ElGamal T. Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms // IEEE Trans. Inform. Theory, v. 31, N 4, July, 1985. P. 469-479.

115. ERDAS Field Guide. ERDAS Inc. 1997.

116. ESRI Shapefile: A Technical Description. Environmental System Research Institute Inc., USA, 1997.

117. Farin G. A Modified Clough-Tocher Interpolant // Comput. Aided Geom. Des., Vol. 2, No 1-3, 1985. P. 19-27.ч

118. Fletcher L. A., Kasturi R. A Robust Algorithm for Text String Separation from Mixed Text/Graphics Images // IEEE Transactions on PAMI, 10(6), 1988, P. 910-918.

119. Fowler R.J. Automatic Extraction of Irregular Network Digital Terrain Model // Comput. Graph., Vol. 13, No 2, 1979. R 199-207.

120. Gabow H. N. An Efficient Implementation of Edmonds' Algorithm for Maximum Matching of Graphs // J. ACM, v. 23, 1976. R 221-234.

121. Garey M., Johnson D. S., Preparata F. P., Tarjan R. E. Triangulating a Simple Polygon // Info. Proc. Lett. 7(4), 1978. P. 175-180.

122. Gilbert P. N. New Results on Planar Triangulations. Tech. Rep. AST-15, Coord. Sci. Lab., University of Illinois at Urbana. July 1979.

123. Graham R. L. An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set // Info. Proc. Lett. V. 1, 1972. P. 132-133.

124. Gueziec A. Locally Toleranced Surface Simplification // IEEE Trans. Visual, and Comput. Graph., Vol. 5, N 2, 1999. P. 168-189.

125. Hagen H., Nielson G., Nakajima Y. Surface Design Using Triangular Patches // Comput. Aided Geom. Des., Vol. 13, No 9, 1996. P. 895-904.

126. Handbook of Grid Generation / Ed. J.F. Thompson, B.K. Soni, N.P. Weatherill. Boca Raton, Fl.: CRC Press, 1999.

127. Heckbert, P.S., Garland M. Optimal Triangulation and Quadric-Based Surface Simplification // Comput. Geom., Vol. 14, No 1-3, 1999. P. 49 -65.

128. Held M., Karp R. M. The Traveling Salesman Problem and Minimum . Spanning trees // Operations Res. v. 18, 1970. P. 1138-1162.

129. Held M., Karp R. M. The Traveling Salesman Problem and Minimum Spanning trees: Part II // Math. Programming v. 1, 1971. P. 6-25.

130. Johnson D. S., McGeoch L. A. The Traveling Salesman Problem: A Case Study in Local Optimization // Local Search in Combinatorial Optimization / Aarts E. H. L., Lenstra J. K. (eds.). N. Y.: John Willey & Sons, 1995.

131. Johnson D. S., McGeoch L. A., Rothberg E. E. Asmptotic Experimental Analsis for the Held-Karp Traveling Salesman Bound // Proceedings of the 7th ACM-SIAM Smposium on Discrete Algorithm, 1996. P. 341-350.

132. Kirkpatrick D. G. A Note on Delauney and Optimal Triangulations // Inform. Process. Lett. 1980. Vol. 10. No 3. P. 127-128.

133. Kirkpatrick D. G. Optimal Search in Planar Subdivisions // SI AM J. Comput. 12(1), 1983. P. 28-35.

134. Lawson C.L. Transforming Triangulations // Discrete Mathematics, Vol. 3, No 4, 1972. P. 365-372.

135. Laurini R., Thompson D. Fundamentals of Spatial Information Systems. London: Academic Press, 1996.

136. Lee D.T., Lin A.K. Generalized Delaunay Triangulation for Planar Graph // Discrete Comput. Geom., Vol. 1, 1986. P. 201-217.

137. Lee D. Т., Preparata F. P. The all Nearest Neighbor Problem for Convex Poligons // Inform. Process/Lett. 1978. Vol. 7. P. 189-192.

138. Lee D. Т., Shachter B. Two Algorithms for Constructing a Delaunay Triangulation // Inter. Jour, of Сотр. and Inf. Sciences. 1980. Vol. 9, No 6. P. 219-242.

139. Liesegang D. G. The "Tube-Passing Problem" and the S. T. P. // Proc. 9th Int. Math. Program. Symp. Budapest, 1976, v. 2. — Budapest, 1979. P. 537-543.

140. Lingas A. The Greedy and Delauney Triangulations are not Bad in the Average Case and Minimum Weight Geometric Triangulation of Multi-Connected Poligons is NP-Complete // Lect. Notes in Comput. Sci. 1983. Vol. 158. P. 270-284.

141. Manacher G. K., Zobrist A., L. Neither the Greedy nor the Delauney Triangulation of a Planar Point Set Approximates the Optimal Triangulation // Inform. Process. Lett. 1979. Vol. 9. No 1. P. 31-34.

142. Manning J. R. Continuity Conditions for Spline Curves // Computer Journal, v. 17, No 2, 1974. P. 181-186.

143. Pretty Good Privacy, http://www.pgp.com

144. Philip G.M., Watson D.F. Automatic Interpolation Methods for Mapping Piezometric Surfaces // Automatica, Vol. 22, No 6, 1986. P. 753-756.

145. Rivest R. L., Shamir A., Adleman L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems // Communications of the ACM, v. 21, No. 2, 1978. P. 120-126.

146. Rosenkrantz D. J., Stearns R. E., Lewis P. M. Appoximate Algorithms for the Traveling Salesperson Problem // Fifteens Annual IEEE Symp. on Switching and Automata Theory, May, 1974. P. 33-42.

147. Service J. SAS User's Guide. Institute of Statistics North Carolina State University. Raleigh, N. Carolina 27607, 1972.

148. SurferR. A Powerful Contouring, Gridding and Surface Mapping Package for Scientist and Engineers.http://www.goldensoftware.com/frames/surferframe.htm.

149. TNTrnipsR. The Map and Image Processing System. http://www.microimages.com/product/tntmips.htm.

150. Tombre K. Ten Years of Research in the Analysis of Graphics Documents: Achievements and Open Problems // Proceedings of 10th Portuguese Conference on Pattern Recognition, Lisbon, Portugal, march 1998. P. 11-17.

151. Vaidya P. M. Geometry helps in Matching // SIAM J. Comput. 1989. Vol. 18, No 6. P. 1201-1225.

152. Vertical Mapper, http://www.esti-map.ru/vertmap.htm.f