Содержание к диссертации
Введение 5
Глава 1. АНАЛИЗ ИЗОБРАЖЕНИЙ ГРАФИЧЕСКИХ ДОКУМЕНТОВ, МОДЕЛЕЙ И
МЕТОДОВ ИХ ОБРАБОТКИ 10
Виды изображений и их информативная емкость 10
Основные технологические этапы, методы и алгоритмы обработки растровых изобразісений ГД 13
Выводы 30
Глава 2. МАТЕМАТИЧЕСКИЕ МОДЕЛИ ОПИСАНИЯ И ПРЕДСТАВЛЕНИЯ
РАСТРОВОЙ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ 31
Структурная модель растровых данных 31
Структурная модель векторных данных 40
Структуры и форматы хранения растровых данных для различных моделей описания 42
23Л. Растровая модель 42
Штриховая модель 43
Модели, реализующие объектное описание растровых данных (совокупность РПО, РСО, контурная, линейно-контурная, линейная, сегментно-узловая) 46
Выводы 53
Глава 3 Алгоритмы построения моделей описания и обработки растровых
изображений графических документов .-...55
Запись алгоритмов 56
Базовые алгоритмы обработки растровых данных, представленных в формате пиксельной матрицы 57
Sw_Pix -определение 4-элементной связности пикселя 57
Pix_Strix - преобразование пиксельной строки в строку штрихов 57
Strix _Pix -- преобразование строки штрихов в пиксельную строку 58
Pix_Blob - построение одиночной области связных одноцветных пикселей ... 59
Pix_BlobAll - построение всех областей связных одноцветных пикселей ...60
RastrJECon - построение одиночного контура области связных не фоновых пикселей 61
Rastr_Kon_All - построение всех контуров не фоновых связных растровых областей пиксельной матрицы Р 62
SITPIL - расслоение растровых данных на «площадные» и «линейные» объекты 63
3.3. Алгоритмы построения иерархии моделей штрихового и векторного уровней
описания растровых данных ГД 65
Формирование штриховой модели растровых данных по бинарной пиксельной матрице 66
Алгоритм формирования связных растровых компонент по штриховым растровым данным 67
КОМ - алгоритм формирования контурной модели по штриховой модели растровых данных 68
VLO - алгоритм построения линейной векторной модели 69
FSSU - алгоритм построения сегментно-узловой модели 71
3.4. Вспомогательные и сервисные алгоритмы построения моделей растровых
данных 73
SwStrixString - Установление связности штриха со штрихами смежной строки 73
SwStr - установление связи штрихов двух смежных строк 75
Add_Strih - алгоритм логического сложения двух строк штрихов 76
Sub_Strih - алгоритм логического вычитания двух строк штрихов 78
Mul_Strih - логическое умножение двух строк штрихов 80
ARITHSTR - алгоритм выполнения логических операций над файлами в штриховой модели данных 81
LineApr - алгоритм линейной аппроксимации множества точек плоскости методом наименьших квадратов 83
KLAST - алгоритм кластеризации множества точек плоскости 85
FIP - алгоритм объектной фильтрации растровых данных 86
FRS - алгоритм автоматической коррекции границ линейных растровых объектов и поиск зон разрыва растровых линий 86
POVOROT - алгоритм поворота растра на заданный угол 88
Privlmp.exe - алгоритм координатной привязки документа 90
КРК - алгоритм сегментации плоской кривой на однородные фрагменты..90
Кусочно-линейная аппроксимация плоских кривых методом наименьших квадратов и их представление набором ортогональных отрезков 92
3.5. Алгоритмы конвертации форматов представления различных моделей описания
растровых изображений ГД 93
KMP_STR - алгоритм перехода от контурной модели изображения к штриховой 93
LMP_BAS - алгоритм передачи объектов из файла в структуре «паспорт-метрика» в формат базы данных 95
3. б. Алгоритмы распознавания и описания объектов жилой застройки на
топографических картах масштаба 1:10000 -1:100000 95
Определения 96
Особенности представления выделяемых объектов 96
Непроизводные элементы и признаки распознавания объектов жилой застройки 97
Эталоны объектов решающих правил 97
Алгоритмы формирования признаков распознавания 99
Алгоритмы распознавания и описания объектов жилой застройки на топографических картах масштаба 1:10000 100
Алгоритм распознавания и описания объектов жилой застройки на топографических картах масштабов 1:25000-1:50000 102
Алгоритмы распознавания и описания объектов жилой застройки на топографических картах масштаба 1:100000 104
Алгоритмы распознавания и описания объектов "КВАРТАЛ" на ТК масштабов 1:10000- 1:50000 106
3.7. Алгоритмы распознавания и описания объектов инвентаризационных планов
зданий и сооружений 109
3.7.1. Особенности цифровых изображений инвентаризационных планов зданий....
109
Непроизводные элементы и признаки распознавания объектов инвентаризационных планов зданий и сооружений 110
Алгоритмы формирования признаков распознавания 111
Результаты экспериментов по обработке планов 119
Выводы 120
Глава 4. Разработка и создание программного и технологического обеспечения
автоматизированных комплексов тематической обработки РИГД 122
4.1. Информационное обеспечение 122
Структуры для работы со штриховыми данными 122
Структуры для работы с векторными данными 125
Структурное описание сегментно-узловой модели 127
4.1.4. Структуры, используемые при построении контурной модели по сегментно-
узловой 128
4.1.5. Форматы служебных файлов 129
4.2. Библиотеки базовых и интерфейсных функций построения иерархии моделей
описания и тематической обработки РИГД 132
4.2.1 Функции 132
Файловые форматы графических данных 132
Среда разработки и условия использования 133
4.2.4 Интерфейсные библиотеки 133
Библиотека базовых функций 137
Программные технологические цепочки 137
4.3. Интеллектуальный редактор растровых изображений 137
Принципы создания интеллектуального редактора графических данных ..138
Назначение и функциональные возможности редактора 140
Входные и выходные данные программы 142
Состав комплекса интеллектуального редактирования 142
Порядок работы 142
4.4. Автоматизированная подсистема создания цифровых инвентаризационных
планов зданий и сооружений 152
АЛЛ. Особенности цифровых изображений инвентаризационных планов зданий...
; ; 152
Основные требования, предъявляемые к подсистеме 153
Назначение подсистемы 154
Входные и выходные данные 155
Состав программного обеспечения подсистемы 155
Условия функционирования подсистемы 156
Функциональная блок-схема технологии создания цифровых баз данных инвентаризационных планов БТИ и последовательность технологических операций....
Методика выбора и формирования параметров обработки 165
Технология обработки инвентаризационных поэтажных планов зданий 168
4.5. Подсистема выделения и описания топографических знаков жилой застройки
173
Назначение 176
Состав программного обеспечения подсистемы 178
Основные технологические этапы 180
Выводы 184
ЗАКЛЮЧЕНИЕ 186
Список используемой литературы
Введение к работе
Актуальность темы. Цифровая обработка графической информации (ГИ) относится к числу наиболее трудоемких задач современной кибернетики, информатики и вычислительной техники. При этом ГИ является наиболее естественным носителем исходной информации практически во всех областях науки и техники. Цифровая обработка графической информации широко используется при решении многих важных отраслевых задач, автоматизации проектирования (САПР), автоматизации научных исследований (АСНИ), в робототехнике, медицинской и технической диагностике, мониторинге природных ресурсов, геоинформационных технологиях (ГИС) и т.д.
Расширение сфер, требующих автоматизации обработки графической
информации, привело к качественному усложнению графических документов
(ГД)- большие размеры, отсутствие строгих ограничений на шрифты и
типоразмеры, наличие фона, большое количество
пространственно-логических и топологических связей и метрических отношений между линейными, площадными и дискретными объектами. Практикой выдвинута проблема обработки сложно-структурированных графических документов. Сложно-структурированный, семантически насыщенный документ - это материальный объект (конструкторские проекты, географические и топографические карты, графические материалы медицинской диагностики и поэтажные планы БТ и др.), содержащий образно-знаковые модели действительности в форме графических изображений и терминов естественного языка. Размеры документов могут достигать порядка 1000x1000 мм и более, объекты могут изменяться от 0.1 мм до нескольких метров, точность обработки составляет порядка 0.1 мм. Это предопределяет огромные размеры исходных данных - порядка 104 - 103 Кбайт.
При этом большое число задач требует производить обработку графической информации в реальном масштабе времени и при ограниченных ресурсах памяти.
Необходимо отметить, что технология автоматического анализа графической информации (ГИ) - сложный многоэтапный процесс, включающий в себя большое количество методов и алгоритмов обработки -фильтрации, сжатия, хранения и поиска, анализа и принятия решений. Для эффективной работы этого «конвейера» необходимо, чтобы все математические модели, методы и алгоритмы, а также структуры представления данных, что очень важно, были взаимоувязаны и взаимоэффективны, так как очевидно, что сколь угодно высокая эффективность на каком-то отдельном участке обработки может быть сведена на нет на других этапах. Таким образом, модели и методы обработки
должны быть технологичными и удовлетворять некоторым общим требованиям, предопределенным эффективностью решения задач анализа ГИ в целом. Однако, в настоящее время большинство методов и математических моделей описания растровых изображений, позволяющих решать частную задачу, малоэффективны для работы в «конвейере» обработки ГИ. Это особенно важно на нижних уровнях иерархии. Проблемы еще более усугубляются в ГИС в связи с необходимостью осуществлять обработку очень большого объема растровой информации в реальном масштабе времени, при ограниченных ресурсах оперативной памяти и необходимости их естественной интеграции в геоинформационные технологии и системы. Таким образом, основные требования, предъявляемые к моделям описания, методам и алгоритмам обработки растровой информации ГД в ГИС следующие:
технологичность;
высокая емкостная и временная эффективность;
естественная интегрируемость в общую схему ГИС.
Все это определяет актуальность проблемы развития новых математических моделей описания и методов обработки растровых изображений сложно-структурированных графических документов.
Существенный вклад в решение проблем обработки графической информации и изображений внесли российские ученые А.С. Лебедев, В.В. Александров, В.А. Виттих, Ю.Г. Васин, В.В. Сергеев, В.А. Сойфер, В.П. Пяткин, СВ. Абломейко, а также зарубежные ученые Т.Павлидис, Ф.Препарат, У.Претт, Х.Самет, У.Гренандер, Р. Дуда, Г.Харт, К.Фу и другие.
В работах Васина Ю.Г., Башкирова О.А., Чудиновича Б.М. и др. (НИИ ПМК ННГУ) был предложен комбинаторно-геометрический подход к обработке растровых изображений графической информации пространственно-распределенных данных (ПРД) в основе которого весь сложный комплекс задач, связанный с анализом видеоданных, рассматривается с единой точки зрения построения иерархии взаимосвязанных математических моделей описания, структур представления и принятия решений, нижний уровень которых обрабатывает растровую информацию со сканирующего устройства, а верхний уровень соответствует описанию ГД в терминах пользователя. Были предложены математические модели нижних уровней иерархии для описания изображений, в которых графические изображения представлялись в виде растра (набора пикселей), совокупности линий, контуров и точек (контурная, линейно-контурная модели). Линейно-контурная модель изображения ГД рассматривалась как базовая для всех последующих уровней моделей. На базе контурной и линейно-контурной моделей строились модели высших уровней. Для моделей высших уровней были развиты эффективные методы вычислительной геометрии (метод от общего к частному на базе иерархических структур представления векторных данных), методы
распознавания графических объектов (корреляционно-экстремальный метод) и пр.
Однако, дальнейшее расширение типов обрабатываемых ГД (схемы, планы, чертежи, поэтажные планы), особенно ГД, взятых из архивов, вызвало новые серьезные проблемы, связанные с переходом от нижнего (пиксельного) представления к векторному, что, в свою очередь, привело к необходимости дальнейшего развития иерархии моделей описания растровых изображений, особенно на нижних уровнях, где наиболее велики объемы обрабатываемых данных и временные затраты.
В настоящей работе, в рамках комбинаторно-геометрического подхода, получили дальнейшее развитие исследования в области конструирования новых моделей описания, методов и алгоритмов обработки растровых изображений ГД, удовлетворяющих отмеченным выше требованиям.
Цели и задачи диссертационной работы. Цель диссертационной работы состояла в разработке, в рамках комбинаторно-геометрического подхода, новых математических моделей описания, эффективных методов и алгоритмов для решения возможно более полного класса задач обработки растровых изображений ГД и создании на их основе соответствующего информационного, программного и технологического обеспечения автоматизированных систем обработки сложноструктурированной ГИ.
Для достижения этой цели в диссертации решены следующие задачи:
Рассмотрены различные классы сложных графических документов с целью выявления основных задач их цифровой обработки, проведен анализ технологий, существующих моделей описания и методов решения задач обработки растровых изображений этих документов. Выработаны основные требования к моделям, методам и алгоритмам решения поставленных задач.
Исследованы и развиты новые эффективные модели описания растровых изображений ГД и структуры их представления, а также алгоритмическое и программное обеспечение их реализации.
Разработаны и развиты методы и алгоритмы решения прикладных задач обработки растровых изображений ГД в ГИС на базе предложенных моделей описания.
Разработано информационное, алгоритмическое, программное и технологическое обеспечение, реализующие предложенные модели описания методов и алгоритмов в автоматизированных системах и комплексах обработки растровых изображений сложных графических документов в ГИС.
Методы исследования.
В диссертационной работе используются методы аналитической геометрии, распознавания образов, теории информации, общей теории алгоритмов, математического моделирования.
Научная новизна диссертационной работы заключается в следующем:
В развитии иерархии моделей нижнего уровня структурированного описания растровых изображений ГД.
В разработке эффективных логических и физических структур представления и хранения предложенных моделей описания.
В разработке алгоритмического и программного обеспечения построения предложенных моделей описания.
В разработке признаков и решающих правил для структурных методов распознавания объектов жилищной застройки на топокартах и площадных, линейных и дискретных объектов на поэтажных инвентаризационных планах зданий и сооружений.
В разработке и развитии эффективных методов и алгоритмов решения тематических прикладных задач анализа цифровой графической информации на основе предложенных моделей описания.
В разработке архитектуры, информационного, алгоритмического, программного и технологического обеспечения, реализующих предложенные модели описания, методы и алгоритмы обработки в автоматизированных системах и комплексах обработки растровых изображений ГД в ГИС.
Практическая ценность. В основу диссертационной работы положены результаты, полученные автором в ходе исследований, проводимых в рамках НИОКР Министерства Науки и образования РФ, Федеральной службы геодезии и картографии России, Главного управления навигации и океанографии МО РФ.
Работа выполнена при финансовой поддержке РФФИ, грант поддержки ведущих научных школ № 00-15-96108 и ФЦП «Интеграция» проект К-03392.
Полученные в диссертационной работе результаты могут быть использованы при проектировании новых обрабатывающих процедур и технологий, а также программно-аппаратных комплексов, связанных с обработкой метрической информации пространственно-распределенных объектов, в системах принятия решений в ГИС. Апробация полученных результатов.
Разработанное алгоритмическое и программное обеспечение внедрено: В геоинформационных центрах Федеральной службы геодезии и картографии России в рамках технологии создания цифровых топографических карт и топографических планов городов всего масштабного ряда;
В Главном управлении навигации и океанографии ВМФ МО РФ
(ЦКП-280 ВМФ МО РФ) в автоматизированных системах создания
мировой коллекции электронных морских навигационных карт;
В НИИ прикладной математики и кибернетики ННГУ в объектно-ориентированной интеллектуальной геоинформационной системе «ГИС-ТЕРРА»;
В региональных кадастровых бюро;
В учебном процессе на факультете Вычислительной математики и кибернетики Нижегородского государственного университета им. Н.И. Лобачевского (кафедра Интеллектуальные информационные системы и геоинформатика);
Результаты диссертационной работы докладывались и обсуждались на III Конференции «Распознавание образов и анализ изображений: новые информационные технологии - РОАИ» (Н.Новгород, 1-7 декабря 1997г.), 6-ой,7-ой,8-ой Всероссийской конференциях «Методы и средства обработки сложной графической информации» (Н.Новгород, 2001, 2003, 2005 гг.).
Основные положения работы освещены в десяти опубликованных печатных работах.
Структура и объем работы
Диссертация состоит из введения, 4 глав, заключения, списка литературы. Объем основного текста работы - 193 машинописных страниц, список литературы включает 105 наименований.
Похожие диссертации на Исследование моделей описания, разработка алгоритмического, программного и технологического обеспечения обработки растровых изображений графических документов
