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

ВВЕДЕНИЕ.

Глава 1. Обзор методов векторизации растровых изображений.

1.1. Технологии векторизации. Этапы преобразования изображений из растрового в векторную форму.

1.2. Основные определения.

1.3. Сегментация изображений.

1.3.1. Сегментация текста и графики.

1.3.2. Сегментация закрашенных объектов и линий.

1.3.3. Сегментация линий разной толщины.

1.3.4. Разделение цветного растра на монохромные, соответствующие базовым цветам.

1.4. Первичная векторизация.

1.4.1. Методы выделения осевых линий на растре.

1.4.2. Алгоритмы линейной аппроксимации осевых и граничных линий.

1.4.3. Методы постобработки векторной модели.

1.5. Возможности популярных пакетов программ векторизации и первичного распознавания.

1.6. Выводы.

Глава 2. Скелетизация растровых изображений.

2.1. Применение задачи скелетизации.

2.2. Эффективный алгоритм скелетизации бинарных растров.

2.3. Алгоритм построения обобщенного скелета.

2.4. Алгоритм «векторной скелетизации».

2.5. Выводы.

Глава 3. Построение первичных векторных моделей растров.

3.1. Определения.

3.2. Расширенная графовая модель бинарного растра.

3.2.1. Общее определение расширенной графовой модели.

3.2.2. Триангулированное представление расширенной графовой модели.

3.3. РГМ бинарного растра, полученная в результате векторной скелетизации.

3.4. Полигонально-линейная графовая модель «-цветного растра.

3.4.1. Содержательное описание ПЛГМ.

3.4.2. Алгоритм построения ПЛГМ.

3.4.3. Построение графовой модели обобщенного скелета.

3.4.4. Выделение и атрибутивное описание полигонов.

3.5. Полигональная графовая модель «-цветного растра.

3.5.1. Предобработка растра.

3.5.2. Построение векторной модели цветного растра.

3.5.3. Триангулированное представление ПГМ.

3.6. Выводы.

Глава 4. Объектная векторизация (с применением первичных векторных моделей растров).

4.1. Задача полуавтоматической объектной векторизации.

4.2. Полуавтоматическое построение линейных объектов.

4.2.1. Применение поиска в ширину на графе для интерполяции линейного объекта.

4.2.2. Поиск в глубину в применении к интерполяции линейного объекта.

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

4.3.1. Применение поиска в ширину для экстраполяции площадного объекта.

4.3.2. Использование поиска в глубину для выделения минимальной «почти связной» границы многоугольника.

4.3.3. Построение моделей закрашенных площадных объектах.

4.3.4. Использование выделения связных областей триангуляции для построения площадных объектов.

4.4. Полуавтоматическое выделение линейных и площадных объектов используя ПГМ растра).

4.5. Алгоритмы линейной аппроксимации с геометрическими ограничениями.

4.6. Выводы.

Глава 5. Реализация алгоритмов векторизации в ГИС ГрафИн.

5.1. Возможности векторизации в ГИС ГрафИн.

5.2. Общая структура подсистемы векторизации в структуре объектов

ГИС ГрафИн.

5.3. Порядок действий оператора ввода данных при использовании векторизации.

5.4. Выводы.

Картографическая информация играет важную роль в жизни человека и общества. До недавнего времени средства обработки человеком картографической информации оставались практически неизменными. Для понимания и анализа географической информации использовались бумажные карты, которые первоначально рисовались от руки, затем стали изготавливаться типографскими способами. Это обусловлено чрезвычайно удобным для человека способом представления информации как рисунка на плоской поверхности. Тем не менее, данный способ далек от идеала. Будучи однажды нарисованной или напечатанной, карта со временем теряет свою актуальность, и для того, чтобы карта была действительно полезной для человека, его использующего, требуется заменять ее время от времени на более «свежую», содержащую новые, появившиеся на изображаемой области, объекты, а также отредактированные изображения объектов, изменивших свою форму и положение.

В связи с широким распространением компьютеров в настоящее время активно разрабатываются геоинформационные системы (ТИС), способные хранить базы графических данных, имеющих координатную привязку. Данные системы позволяют хранить информацию об объектах, расположенных на поверхности Земли, и обладают способностью обрабатывать информацию, хранящуюся в виде базы объектов, то есть получать от пользователя запросы на выбор либо модификацию географической информации и выполнять требуемые действия с информацией. В развитие геоинформатики в России внесли значительный вклад Кошкарёв, Тикунов, Цветков, Королев.

Среди разработанных отечественных универсальных ГИС следует отметить системы Нева, ГеоГраф/GeoDraw, Полис, Растр-2. Одно из основных направлений разработки ГИС в России - создание городских кадастровых информационных систем. В качестве успешных примеров можно привести пакеты Альбея, CityComm, ГрафИн.

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

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

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

3. Сканирование карты с последующей обработкой в системе распознавания либо растрово-векторного редактирования. Данный способ является наиболее предпочтительным, так как позволяет во многом автоматизировать работу операторов ввода данных. Кратко, суть его состоит в следующем. Используя любой качественный сканер, в память компьютера заносится модель бумажной карты, представляющая собой растр - прямоугольный массив точек, каждая из которых несет информацию о цвете соответствующей точки плоскости сканирования. Таким образом строится дискретизованная модель традиционной карты, называемая растровым изображением или просто растром. Современные сканеры позволяют получать высококачественные растровые изображения с разрешением до 9600 dpi, при использовании до нескольких млрд. цветов. Полученное растровое изображение подается на вход программы-векторизатора. Функциональность существующих программ-векторизаторов, имеющихся на рынке программного обеспечения (ПО), как правило, включает функции обработки растровых изображений совместно с нанесением векторной информации в ручном режиме, а также возможностями полуавтоматической трассировки контуров и линий объектов. Некоторые программы - векторизаторы дают возможность распознавания ряда классов объектов (например, точечных условных знаков) автоматически, без участия пользователя.

Среди широко известных и хорошо зарекомендовавших себя программных пакетов векторизации следует отметить системы EasyTrace, MapEDIT, Vec-tory, Spotlight Pro, R2V, Сюрфер, Геор, Интелвек, отдельно следует выделить универсальную ГИС Arclnfo, имеющую в своем составе модуль полуавтоматической векторизации. Также следует обратить внимание на универсальную систему автоматизированной обработки данных дистанционного зондирования (ДДЗ) ERDAS/Imagine, манипулирующую растровыми данными.

В развитие теоретической базы задач технического зрения, обработки изображений и структурного распознавания значительный вклад внесли Розен-фельд, Роберте, Марр, Р. Фишер, Прэтт, Гримсон, Хуанг, Сираи, Дунхам, Фельдман, Павлидис, Минский, Пейперт, Дуда, Харт. Также широко известны своими работами в данной области Дорманн, Кастури, Дори, Томбре, О'Горман, Лэм, Абламейко, Семенков, Файн.

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

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

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

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

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

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

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

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

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

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

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

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

Внедрение результатов работы. Разработанная автором в НПО «Сибгео-информатика» система полуавтоматической векторизации используется в процессе подготовки электронных картографических материалов в ПО «Инжгеоде-зия» (г. Новосибирск). Основные результаты теоретического характера также используются в курсе «Вычислительная геометрия и интерактивные графические системы», читаемом для студентов факультета информатики ТГУ. Ряд результатов, полученных в данной работе, был использован автором при разработке коммерческого программного продукта - дополнительного модуля векторизации растров для системы Adobe Illustrator™, разработанного автором в компании Panopticum LLC.

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

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

2. Группа полигональных графовых моделей «-цветного растра и эффективные алгоритмы их построения.

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

4. Новые алгоритмы линейной аппроксимации, учитывающие геометрические ограничения, для типовых графических объектов ГИС.

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

Апробация работы и публикации.

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

1. Международной научно-практической конференции ИНПРИМ (Новосибирск, 2000).

2. Международной научно-практической конференции DAOR-2000 (Новосибирск, 2000).

3. Международной научно-практической конференции Геоинформатика-2000 (Томск, 2000).

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

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

8. Всероссийском научно-техническом семинаре «Энергетика: экология, надёжность, безопасность» (Томск, 1999).

9. Всероссийской научно-практической конференции «Новые технологии и комплексные решения: наука, образование, производство» (Анжеро-Судженск, 2001).

По результатам выполненных исследований опубликовано 16 печатных работ, из них 8 статей и 8 тезисов докладов.

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

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

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

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

В третьей главе рассматривается задача первичной векторизации. Предложена новая трактовка данной задачи как построения модели не только объектов, образованных единичными пикселями, но и всей области растра, включая фоновые области произвольной конфигурации. Эти результаты опубликованы автором в работах [9-11, 17].

В четвертой главе рассматриваются предложенные автором в работах [8, 11, 12] алгоритмы объектной векторизации. Данные алгоритмы используют предложенные в третьей главе модели растров для поиска и выделения наиболее характерных для ГИС объектов. Предложенные алгоритмы отличаются устойчивостью к помехам и неточностям представления объектов на растре и в первичных векторных моделях. Для некоторых классов объектов предложен способ линейной аппроксимации с геометрическими ограничениями, позволяющий из приближенных моделей объектов получить качественные объекты, удовлетворяющие ограничениям, накладываемым на классы объектов ГИС.

Пятая глава посвящена описанию реализации основных алгоритмов, рассматриваемых в работе, в ГИС ГрафИн в виде библиотеки классов автоматизации векторизации. Реализованная в данном проекте технология векторизации рассмотрена в работах [7, 19].

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

5.4. Выводы

1. Автором реализована подсистема векторизации, встроенная в универсальную ГИС ГрафИн. Интеграция подсистемы векторизации в универсальную ГИС позволяет сократить накладные расходы, связанные с преобразованием форматов данных из средства подготовки ЦММ в формат целевой ГИС.

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

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

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

Рис. 84. Примеры результатов векторизации в системе ГрафИн

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

5. Предложена полигонально-линейная графовая модель (ПЛГМ) п-цветного растра, являющаяся представленным в триангулированной форме планарным графом линий, топологически корректно моделирующим «-цветные растры, содержащие как линейные, так и площадные объекты. Предложен эффективный алгоритм построения ПЛГМ, основанный на алгоритме обобщенной скелетизации, и имеющий линейную трудоемкость.

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

7. Предложено семейство алгоритмов полуавтоматической объектной векторизации линейных и площадных объектов, основанных на обобщении алгоритмов поиска на планарных графах линий, образованных элементами первичных векторных моделей (РГМ и ПЛГМ). При выполнении этих алгоритмов

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

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

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

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

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

2. Борисенко В.И. Сегментация изображений (состояние проблемы) // Автоматика и телемеханика, 1987, № 7.

3. Галанский Б.Л., Поляков В.И. Информационные системы. Томск: Изд-во Том. ун-та, 1989. - 154 с.

4. Денисов Д.А. Сегментация изображений на ЭВМ // Зарубежная радиоэлектроника, 1985, № 10.

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

6. Костюк Ю.Л., Новиков Ю.Л. Графовые модели цветных растровых изображений высокого разрешения // Вестник ТГУ, 2002, № 275, с. 153-160.

7. Макаров А.А. Модифицированный алгоритм утоныпения штриховых изображений // Вопросы радиоэлектроники. Сер. ЭВТ, 1984, вып.8.

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

9. Новиков Ю.Л. Полигонально-линейные графовые модели растровых изображений // «Геоинформатика-2000»: Труды Международной научно-практической конференции / Под ред. А.И. Рюмкина, Ю.Л. Костюка, А.В. Скворцова. Томск: Изд-во Том. ун-та, 2000, с. 50-55.

10. Новиков Ю.Л. Эффективная скелетизация бинарных изображений // "Геоинформатика-2000": Труды Международной научно-практической конференции / Под ред. А.И. Рюмкина, Ю.Л. Костюка, А.В. Скворцова. -Томск: Изд-во Том. ун-та, 2000. с. 58-63.

11. Новиков Ю.Л., Слюсаренко С.Г., Скворцов А.В., Сарычев Д.С. Информационные системы предприятий трубопроводных сетей // Вестник ТГУ, 2002, №275, с. 75-81.

12. Обработка изображений и цифровая фильтрация./ Под ред. Т. Хуанга / Пер. с англ.- М.:Мир,1979, 318 с.-17223. Обработка и отображение информации в растровых графических системах. -Минск: ИТК АН БССР.- 1989.- 180 с.

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

14. Прэтт У. Цифровая обработка изображений / Пер. с англ. М.:Мир, 1982.- кн. 1.-312 с.

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

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

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

18. Сираи И. Анализ массивов интенсивности с использованием знаний о сценах // Психология машинного зрения / Пер. с англ. / Под ред. П. Уин-стона:. М.: Мир. - 1978, с. 112-136.

19. Скворцов А.В., Костюк Ю.Л. Эффективные алгоритмы построения триангуляции Делоне // Геоинформатика: Теория и практика. Выпуск 1. -Томск: Изд-во Томск, ун-та, 1998, с. 22-47.

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

21. Скворцов А.В. Триангуляция Делоне и ее применение. Томск: Изд-во Том. ун-та, 2002. - 128 с.

22. Скворцов А.В., Сарычев Д.С., Новиков Ю.Л, Тарбоков А.А. Использование модели местности для анализа состояния окружающей среды // Энергетика: экология, надёжность, безопасность. Томск, 1999, с. 56.

23. Скворцов А.В., Сарычев Д.С., Новиков Ю.Л. Применение геоинформационных технологий для информационного обеспечения деятельности промышленных предприятий // Энергетика: экология, надёжность, безопасность. Томск, 1999, с. 57.

24. Чэн Ш.-К. Принципы проектирования систем визуальной информации / Пер. с англ. М.: Мир, 1994. - 408 с.

25. Хомяков Ю.Н. Методы классификации текстур // Зарубежная радиоэлектроника, 1986, № 2.

26. Ah-Soon С., Tombre К. Variations on the Analysis of Architectural Drawings // Proceedings 4th International Conference on Document Analysis and Recognition, Ulm (Germany), August 1997, pp. 347-351.

27. Amin T.J., Kasturi R. Recognition of Lines and Symbols in Maps // SPIE Vol. 638, Hybrid Image Processing. 1986, pp. 117-122.

28. Antoine D., Collin S., Tombre K. Analysis of Technical Documents: The REDRAW System // H. S. Baird, H. Bunke, and K. Yamamoto, editors, Structured Document Image Analysis, Springer-Verlag, Berlin/Heidelberg, 1992, pp. 385-402.

29. Arcelli C., Cordelia L.P., Levialdi S. From Local Maxima to Connected Skeletons // IEEE Transactions on Pattern Analysis and Machine Intelligence, Mar. 1981, Vol. PAMI-3, No. 2, pp. 134-143.

30. Arias J.F., Kasturi R. Efficient Extraction of Primitives from Line Drawings Composed of Horizontal and Vertical Lines // Machine Vision and Applications, 1997, Vol. 10, pp. 214-221.

31. Arias J.F., Lai C.P., Surya S., Kasturi R., Chhabra A. Interpretation of Telephone System Manhole Drawings // Pattern Recognition Letters, 1995, Vol. 16, pp. 355-369.

32. Asada H., Brady M. The Curvature Primal Sketch // IEEE Transactions on Pattern Analysis and Machine Intelligence, 1986, Vol. 8, No. 1, pp. 2-14.

33. Atiquzzaman M. Mutiresolution Hough Transform An Efficient Method on Detecting Patterns in Images // IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, Vol. 14, No. 11.

34. Blum H. A Transformation for Extracting New Descriptors of Shape // Symp. on Models for Perception of Speech and Visual Form, MIT Press, Cambridge, Massachusets, 1967, pp. 362-380.

35. Boatto L. An Interpretation System for Land Register Maps. IEEE Computer, 1992, Vol. 25, No. 7, pp. 25-32.

36. Bresenham J.E. Algorithm for Computer Control of a Digital Plotter // IBM Systems Journal, 1965, Vol. 4, No. 1, pp. 25-30.

37. Brice C.R., Fennema C.L. Scene Analysis Using Regions // Artificial Intelligence, 1970, Vol. 1, No. 3, pp. 205-226.

38. Camera Models and Machine Perception: Technical Report / Standard Artificial Intelligence Project; Sobel I.; AIM-121; California; 1970.

39. Canny J. A Computational Approach to Edge Detection // IEEE Transactions on Pattern Analysis and Machine Intelligence, 1986. Vol.8, No. 6, pp.679-698.

40. Cao R., Tan C. L. Separation of Overlapping Text from Graphics // Proceedings of the 6th International Conference on Document Analysis and Recognition, ICDAR'2001, Seattle, Washington, Sept. 10-13, 2001.

41. 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. pp. 221-230.

42. Chai I, Dori D. Orthogonal Zig-Zag: An Efficient Method for Extracting Lines from Engineering Drawings // Arcelli C, Cordelia LP, Sanniti di Baja G (eds). Visual Form. Plenum Press, New York London, 1992, pp. 127-136.

43. Chandran S., Balasubramanian S., Gandhi Т., Prasad A., Kasturi R. Structure Recognition and Information Extraction from Tabular Documents // International Journal of Imaging Systems and Technology, 1996, Vol. 7, pp. 289-303.

44. Chang F., Lu Y.-C., Pavlidis T. Feature Analysis Using Line Weep Thinning Algorithm // IEEE Transactions on Pattern Analysis and Machine Intelligence, Feb. 1999, Vol. 21, No. 2, pp. 145-158.

45. Chen Y.-S., Hsu W.-H. A 1-subcycle Parallel Thinning Algorithm for Producing Perfect 8-Curves and Obtaining Isotropic Skeleton of an L-Shape Pattern // Proc. Computer Vision and Pattern Recognition, June 1989, San Diego, pp. 208-215.

46. Chen Y., Langrana N. A., Das A. K. Perfecting Vectorized Mechanical Drawings // Computer Vision and Image Understanding, March 1996, Vol. 63, No. 2, pp. 273-286.

47. Chiang J., Tue S.C., Leu Y.C. A New Algorithm for Line Image Vectorization // Pattern Recognition, 1998, Vol. 31, No. 10, pp. 1541-1549.

48. Chin R.T., Wan H.-K. A One-Pass Thinning Algorithm and its Parallel Implementation // Computer Vision, Graphics, and Image Processing, 1987, Vol. 40, pp. 30^0.

49. Davies E.R., Plummer A.P.N. Thinning Algorithms: a Critique and a New Methodology // Pattern Recognition, 1981, Vol. 14, pp. 53-53.

50. Deutsch E.S. Thinning Algorithms on Rectangular, Hexagonal, and Triangular Arrays // Comm. ACM, 1972, Vol. 15, No. 9, pp. 827-837.

51. Di Zenzo S., Cinque L., Levialdi S. Run-Based Algorithms for Binary Image Analysis and Processing // IEEE Transactions on Pattern Analysis and Machine Intelligence, January 1996, Vol. 18, No. 1, pp. 83-89.

52. Di Zenzo S., Morelli A. A Useful Image Representation // Proceedings of the 5th International Conference on Image Analysis mid Processing, Word Scientific Publishing, Singapore, 1989, pp. 170-178.

53. Dori D., Liang Y., Dowell J., Chai I. Spare Pixel Recognition of Rrimitives in Engineering Drawings // Machine Vision and Applications, 1993, Vol. 6, pp. 79-82.

54. Dori D., Liu W. Automated CAD Conversion with the Machine Drawing Understanding System: Concepts, Algorithms, and Performance // IEEE Transactions on Systems, Man, and Cybernetics, 1999, Vol. 29, No. 4, pp.411-416.

55. Dori D., Liu W. Sparse Pixel Vectorization: An Algorithm and Its Performance Evaluation // IEEE Transactions on Pattern Analysis and Machine Intelligence, 1999, Vol. 21, No. 3, pp. 202-215.

56. Dori D. Liu W. Stepwise Recovery of Arc Segmentation in Complex Line Environments // International Journal on Document Analysis and Recognition, Feb. 1998, Vol. 1, No. 1, pp. 62-71.

57. Dori D. Orthogonal Zig-Zag: an Algorithm for Vectorizing Engineering Drawings Compared with Hough Transform // Advances in Engineering Software, 1997, Vol. 28, No. l,pp. 11-24.

58. Dosch Ph., Masini G., Tombre K. Improving Arc Detection in Graphics Recognition // Proceedings of 15th International Conference on Pattern Recognition, Barcelona (Spain), September 2000. Vol. 2, pp. 243-246.

59. Dosch Ph., Tombre K., Ah-Soon C., Masini G. A Complete System for Analysis of Architectural Drawings // International Journal on Document Analysis and Recognition, December 2000, Vol. 3, No. 2, pp. 102-116.

60. Dunham J.G. Optimum Uniform Piecewise Linear Approximation of Planar Curves // IEEE Transactions on Pattern Analysis and Machine Intelligence, 1986, Vol. 8, No. l,pp. 67-75.

61. Fan K.-C., Chen D.-F., Wen M.-G. Skeletonization of Binary Images with Nonuniform Width via Block Decomposition and Contour Vector Matching // Pattern Recognition, July 1998, Vol. 31, No. 7, pp. 823-838.

62. Feldman J.A. The Stanford Hand-Eye Project // Proceedings of International Joint Conference on Artificial Intelligence, Washington, 1969.

63. Fletcher L. A., Kasturi R. A Robust Algorithm for Text String Separation from Mixed Text/Graphics Images // IEEE Transactions on Pattern Analysis and Machine Intelligence, 1988, Vol. 10, No. 6, pp. 910-918.

64. Franti P., Ageenko E.I., Kolesnikov A. Vectorizing and Feature-Based Filtering for Line-Drawing Image Compression // Pattern Analysis and Applications, 1999, Vol.2, No.3, pp. 285-291.

65. Govindan V.K., Shivaprasad A.P. A Pattern Adaptive Thinning Algorithm // Pattern Recognition, Vol. 20, 1987, pp. 623-637.

66. Guo Z., Hall R.W. Parallel Thinning With Two-Subiteration Algorithms // Communications of the ACM, 1989, Vol. 32, pp. 359-373.

67. Guzman A. Decomposition of Scenes into Bodies // Proc. AFIPS Conf., 33, Parti, 1968. pp. 291-304.

68. Han C.-C., Fahn K.-C. Skeleton Generation of Engineering Drawings via Contour Matching // Pattern Recognition, 1994, Vol. 27, No. 2, pp. 261-275.

69. Haralick R.M, Shapiro L. Computer and Robot Vision. Reading, MA, Addison Wesley, 1992.

70. Heijmans H.J.A.M. Morphological Image Operators. Boston, Academic Press, 1994.

71. Hilaire X., Tombre K. Improving the Accuracy of Skeleton-Based Vectoriza-tion // Proceedings of 4th IAPR International Workshop on Graphics Recognition (Kingston, Ontario, Canada), September 2001, pp. 281-394.

72. Hilditch C.J. Linear Skeletons from Square Cupboards // Machine Intelligence 1969, Vol. 4, pp. 403-420.

73. Hori O., Tanigawa S. Raster-to-Vector Conversion by Line Fitting Based on Contours and Skeletons // Proceedings of 2nd International Conference on Document Analysis and Recognition, Tsukuba (Japan), 1993, pp. 353-358.

74. Hough P.V.C., Arbor A. A Method and Means for Recognizing Complex Patterns. USA Patent 3,096,654, 1962.

75. Hueckel M.H. An Operator which Locates Edges in Digitized Pictures // JACM, 1971, Vol. 18, No. l,pp. 113-125.

76. Hung S.H.Y., Kasvand T. Critical Points on a Perfectly 8- or Perfectly 6-Connected Thin Binary Line // Pattern Recognition, 1983, Vol. 16, pp. 297284.

77. Ikonomakis N., Plataniotis K.N., Venetsanopoulos A.N. A Region Based Color Image Segmentation Scheme // Proceedings of Visual Communications and Image Processing, January 1999, San Jose, California, SPIE Vol. 3653, pp. 1202-1209.

78. Jaisimha M.Y., Haralick R.M., Dori D. A Methodology for the Characterization of the Performance of Thinning Algorithms // Proceedings of the 2nd International Conference on Document Analysis and Recognition, Tsukuba, Japan, 1993, pp. 282-286.

79. Janssen R. D. Т., Vossepoel A. M. Adaptive Vectorization of Line Drawing Images // Computer Vision and Image Understanding, January 1997, Vol. 65, No. 1, pp. 38-56.

80. Jimenez J. Navalon J.L. Some Experiments in Image Vectorization // IBM J. Res. Develop., 1982, Vol. 26, pp. 724-734.

81. Kasturi R., Alemany J. Information Extraction from Images of Paper-Based Maps // IEEE Transactions on Software Engineering, 1988, Vol. 14, No. 5, pp. 671-675.

82. Kasturi R., Bow S. Т., El-Masri W., Shah J., Gattiker J. R., Mokate U. В. A System for Interpretation of Line Drawings // IEEE Transactions on Pattern Analysis and Machine Intelligence, 1990, Vol. 12, No. 10, pp. 978-992.

83. Kasturi R, Bow S. Т., Gattiker J., Shah J., El-Masri W., Mokate U., Honnena-halli S. A system for recognition and description of graphics // Proceedings of the 9th International Conference on Pattern Recognition, Rome, Italy, Nov. 1417, 1988.

84. Kolesnikov A.N., Belekhov V.V., Chalenko I.O. Vectorization of Raster Images // Pattern Recognition and Image Analysis, 1996, Vol. 6, No. 4, pp. 786794.

85. Kwok P.C.K. A Thinning Algorithm by Contour Generation // Communications of the ACM, 1988, Vol. 31, pp. 1314-1324.

86. Lam L., Lee S.W., Suen C.Y. Thinning Methodologies A Comprehensive Survey // IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, Vol. 14, No. 9, pp. 869-887.

87. Lam L., Suen C.Y. An Evaluation of Parallel Thinning Algorithms for Character Recognition // IEEE Transactions on Pattern Analysis and Machine Intelligence, September 1995, Vol. 17, No. 9, pp. 914-919.

88. Lam L., Suen C.Y. Evaluation of Thinning Algorithms from an OCR Viewpoint // Proceedings of the 2nd International Conference on Document Analysis and Recognition, Tsukuba, Japan, 1993, pp. 287-290.

89. Lee S., Lam L., Suen C.Y. Performance Evaluation of Skeletonization Algorithms for Document Image Processing // Proceedings of the 1st International Conference on Document Analysis and Recognition, France, Saint-Malo, 1991, pp. 260-271.

90. Lin X., Shimotsuji S., Minoh M., Sakai T. Efficient Diagram Understanding with Characteristic Pattern Detection // Computer Vision, Graphics and Image Processing, 1985, Vol. 30, pp. 84-106.

91. Liu W., Dori D. A Protocol for Performance Evaluation of Line Detection Algorithms // Machine Vision Applications, 1997, Vol. 9, pp. 240-250.

92. Liu W., Dori D. Automated CAD Conversion with the Machine Drawing Understanding System // Proceedings of the 2nd IAPR Workshop on Document Analysis Systems, Malvern, PA, 1996, pp. 241-259.

93. Liu W., Dori D. From Raster to Vectors: Extracting Visual Information from Line Drawings // Pattern Analysis and Applications, 1999, Vol. 2, No. 1, pp. 10-21.

94. Liu W., Dori D. Sparse Pixel Tracking: A Fast Vectorization Algorithm Applied to Engineering Drawings // Proceedings of the 13th International Conference on Pattern Recognition Volume III (Robotics and Applications), Vienna, Austria, 1996, pp 808-811.

95. Minsky M.A., Papert S. Project MAC Progress, Rep. IV, MIT Press, Cambridge, Massachusets, 1967.

96. Monagan G., Roosli M. Appropriate Base Representation Using a Run Graph // Proceedings of the 2nd International Conference on Document Analysis and Recognition, Tsukuba, Japan, 1993, pp. 623-626.

97. Montanari U. A Note on the Minimal Length Polygonal Approximation to a Digitized Contour // Communications of the ACM, 1970, Vol. 13, No. 1, pp. 41-47.

98. Montanari U. Continuous Skeletons from Digitized Images. Journal of the ACM 1969, No. 16, pp. 534-549.

99. О'Gorman L. kxk Thinning // Computer Vision, Graphics and Image Processing, 1990, Vol. 51, pp. 195-215.

100. Ochta Y., Kanade Т., Sakai T. Color Information for Region Segmentation // Computer Vision, Graphics and Image Processing, 1980, Vol. 13, pp. 222-241.

101. Pao D., Li F. Shapes Recognition Using the Straight Line Transform: Theory and Generalization // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1992, Vol. 14, No. 11.

102. Pavlidis Т., Algorithms for Graphic and Image Processing, Computer Sciences Press. 1982. // рус. пер. Павлидис Т. Алгоритмы машинной графики и обработки изображений. М.: Радио и связь, 1986. - 400 с.

103. Pavlidis Т. An Asynchronous Thinning Algorithm // Computer Graphics and Image Processing, 1982, Vol. 20, pp. 133-157.

104. Pfaltz J.L., Rosenfeld A. Computer Representation of Planar Regions by their Skeletons // Communications of the ACM, 1967, No. 10, pp. 119-125.

105. Ramachandran K. A Coding Method for Vector Representation of Engineering Drawings // IEEE Proceedings, 1980, Vol. 68. pp. 813-817.

106. Roberts L.G. Machine Perception of Three-Dimensional Solids // Optical and Electro-Optical Information Processing, Cambridge, Massachusets: MIT Press, 1965, pp. 159-197.

107. Rosenfeld A. Connectivity in Digital Pictures // Journal of the ACM, 1970, No. 17, pp. 146-160.

108. Rosenfeld A., de la Torre P. Histogram Concavity Analysis as an Aid in Threshold Selection // IEEE Transactions On System, Man and Cybernetics, SMC-13,1979, pp. 62-66.

109. Rosenfeld A., Pfaltz J.L. Distance Functions in Digital Pictures // Pattern Recognition, 1968, Vol. 1, pp. 33-61.

110. Rosin P. L. Techniques for Assessing Polygonal Approximation of Curves // IEEE Transactions on Pattern Analysis and Machine Intelligence, June 1997, Vol. 19, No. 6, pp. 659-666.

111. Rosin P. L. West G. A. Segmentation of Edges into Lines and Arcs // Image and Vision Computing, May 1989, Vol. 7, No. 2, pp. 109-114.

112. Rutovitz D. Pattern recognition // J. Royal Statistical Soc., 1966, Vol. 129, pp. 504-530.

113. Sahoo P.K., Soltani S. Wong A.K.C. A Survey of Thresholding Techniques // Computer Vision, Graphics, and Image Processing, 1988, vol. 41, pp. 233-260.

114. Sanniti di Baja G. Well-Shaped, Stable, and Reversible Skeletons from the (3,4)-Distance Transform // Journal of Visual Communication and Image Representation, 1994. Vol. 5, No. l,pp. 107-115.

115. Serra J. Image Analysis and Mathematical Morphology London; Academic Press, 1982.

116. Shih C.-C., Kasturi R. Extraction of Graphic Primitives from Images of Paper Based Line Drawings // Machine Vision and Applications, 1989, Vol. 2, pp. 103-113.

117. Skarbek W., Koschan A. Color Image Segmentation A Survey. 1994.

118. Sklansky J., Gonzalez V. Fast Polygonal Approximation of Digitized Curves // Pattern Recognition, 1980, Vol. 12, pp. 327-331.

119. Smith R.W. Computer Processing of Line Images: A Survey // Pattern Recognition, 1987, Vol. 20, No. 1, pp. 7-15.

120. Song J., Su F., Chen J., Tai C. L., Cai S. Line-Net Global Vectorization: an Algorithm and its Performance Analysis // Proceedings of IEEE Conference on

121. Computer Vision and Pattern Recognition, 13-15 June, 2000, South Carolina, pp. 383-388.

122. Svalbe I.D., Natural Representation for Straight Lines and Hough Transform on Discrete Arrays // IEEE Transactions on Pattern Analysis and Machine Intelligence. Vol. 11, No. 9, 1989.

123. Stapor K. A Vectorized Thinning Algorithm for Handwritten Symbols Recognition // Machine Graphics and Vision, 1999, Vol. 8, No. 3, pp. 341-352.

124. Stefanelli R., Rosenfeld A. Some Parallel Thinning Algorithms for Digital Pictures // Journal of the ACM, April 1971, Vol. 18, No. 2, pp. 255-264.

125. Suzuki S., Abe K. Binary Picture Thinning by an Iterative Parallel Two-Subcycle Operation // Pattern Recognition, 1987, Vol. 20, pp. 297-307.

126. Suzuki S., Yamada T. MARIS: Map Recognition Input System // Proceedings of IAPR Workshop on Conputer Vision, Tokyo (Japan), 1988, pp. 421-426.

127. Tamura H. A Comparison of Line Thinning Algorithms from Digital Geometry Viewpoint // International Joint Conference on Pattern Recognition, Kyoto, Japan, Nov. 1978, pp. 715-719.

128. TIFF 6.0 Specification. Adobe Systems Inc. 1992. - 121 p.

129. Tombre K., Ah-Soon C., Dosch Ph., Habed A., Masini G. Stable, Robust and Off-the-Shelf Methods for Graphics Recognition // Proceedings of 14th International Conference on Pattern Recognition, Brisbane, Australia, Aug. 1998, pp. 406-408.

130. Tombre K., Ah-Soon C., Dosch Ph., Masini G., Tabbone S. Stable and Robust Vectorization: How to Make the Right Choices // A. K. Chhabra and D. Dori, editors, Graphics Recognition Recent Advances, Springer Verlag, September 2000, pp. 3-18.

131. Tombre K. Analysis of Engineering Drawings: State of the Art and Challenges // K. Tombre and A. K. Chhabra, editors, Graphics Recognition Algorithms and Systems, Lecture Notes in Computer Science, Vol. 1389, Springer Verlag, April 1998, pp. 257-264.

132. Tombre K., Tabbone S. Vectorization in Graphics Recognition: To Thin or not to Thin // Proceedings of 15th International Conference on Pattern Recognition, Barcelona (Spain), September 2000. Vol. 2, pp. 91-96.

133. 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, pp. 11-17.

134. Vaxiviere P., Tombre K. Cellestin: CAD conversion of mechanical drawings // IEEE Computer, 1992, Vol. 25, No. 5, pp. 46-54.

135. Vaxiviere P., Tombre K. Subsampling: A Structural Approach to Technical Document Vectorization // Shape, Structure and Pattern Recognition / D. Dori and A. Bruckstein, editors, World Scientific, August 1995. pp. 323-332.181 —

136. Wall К., Danielsson P. A Fast Sequential Method for Polygonal Approximation of Digitized Curves // Computer Vision, Graphics and Image Processing, 1984, Vol. 28, pp. 220-227.

137. Yachida M., Saburo T. Application of Color Information to Visual Perception // Pattern Recognition, 1971, Vol. 3, No. 3, pp. 307-323.

138. УТВЕРЖДАЮ Президент Panopticum LLCа7 «211. О. И. Охримец Ъ 2002 г.1. АКТоб использовании результатов диссертационной работы Ю.Л. Новикова «Эффективные алгоритмы векторизации растровых изображений и их реализация в геоинформационной системе»

139. Ведущий специалист, к.т.н.1. Утверждаю»

140. Проректор Томского госуниверситета1. А.С. Ревушкин2002 г.1. АКТоб использовании в учебном процессе результатов диссертационной работы Ю.Л. Новикова «Эффективные алгоритмы векторизации растровых изобра

141. Декан факультета информатики1. Б.А. Гладких

142. Заместитель декана по научно-производственной работе1. С.П. Сущенко