Бесплатный автореферат и диссертация по геологии на тему

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

ВАК РФ 04.00.12, Геофизические методы поисков и разведки месторождений полезных ископаемых

Автореферат диссертации по теме "Разработка компьютерной технологии ввода и векторизации растровой картографической информации для задач геологии и экологии"

Й^ИТЕТ ГОССИЙСКОЙ ФЕДЕРАЦИИ ПО ГЕОЛОГИИ И

- У П]\Рч ВЗЙСПОЛЬЗОВАНИЮ НЕДр

Всероссийский научно-исследовательский институт геологических, геофизических и геохимических систем (ВНИИГеосистем)

На правах рукописи

АЛСЫНБАЕВ Камил Салихович

РАЗРАБОТКА КОМПЬЮТЕРНОЙ ТЕХНОЛОГИИ ВВОДА И ВЕКТОРИЗАЦИИ РАСТРОВОЙ КАРТОГРАФИЧЕСКОЙ ИНФОРМАЦИИ ДЛЯ ЗАДАЧ ГЕОЛОГИИ И ЭКОЛОГИИ

Специальность 04.00.12. - Геофизические методы поисков и разведки месторождений полезных испокаемых

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Москва, 1993 г.

Работа выполнена в Новосибирском государственном университете министерства науки, высшей школы и технической политихи Российской федерации

Научный руководитель:

Черемисина Евгения Наумовна, доктор технических наук, (ВНИИГеосистем, пМосква)

Официальные оппоненты:

доктор технических наук, профессор ЕШЛиряев, (Научно-технический центр "ГЕОКАРТ" пМосква), кандидат технических наук В.ВДобрынин (ВИМС,г.Москва)

часов на заседании

Ведущая организация - НПО СибГео (г.Новосибирск)

Защита состоится ¿¿¿¿¿ЯЬж г. в. Ж___________________

Специализированного совета ДО71Л0Х)1 при Всероссийском научно-исследовательском институте геологических, геофизических и геохимических геосистем, г.Москва, 113105, Варшавское шоссе, дД конференц-зал.

С диссертацией можно ознакомиться в библиотеке ВНИИГеосистем. Автореферат разослан 1993г.

Ученый секретарь Специализированного совета

В.СЛебедев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

Основные задачи работы.

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

и обработки пространственной информации и разработка требований к программному комплексу ввода и векторизации геологической и экологической видеоинформации.

2. Разработка алгоритмов и программных компонент комплекса.

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

4. Апробация созданной технологии при решении задачи изучения глубинного строения земной коры акватории Карского моря по гравимагаитным данным и задачи геоэкологического районирования фрагмента территории Калмыкии.

Научная новизна

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

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

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

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

Защищаемые положения

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

2. Разработаные алгоритмы позволяют сконструировать гибкую

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

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

Реализация и апробация работы

Приведенные в диссертации разработки реализованы в Новосибирском госуниверситете. Высшем колледже информатики Новосибирского госуниверситета, НПО СибГео (г.Новосибирск), ВНИИГеосистем, ВИМСе, (пМосква), в Экоцентре (г-Магадан).

Основные результаты работы докладывались на 6-ой Всесоюзной конференции "Использование вычислительных машин в спектроскопии молекул и химических исследованиях* (Новосибирск, 1983), на Всесоюзном научном семинар "Интерактивные и диалоговые системы в вычислительных комплексах и сетях ЭВМ", (Москва, 1986), на межвузовской конференции "ЭВМ в учебном процессе вуза", (Новосибирск, 1988Х на расширенном семинаре лаборатории системного программного обеспечения НГУ (07.12.92)

Публикации и личный вклад в решение проблемы

Диссертация основана на теоретических, методических и экспериментальных исследованиях, выполненных автором.

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

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

Объем н структура работы

Диссертация состоит из введения, четырех глав, заключения, списка литературы, содержит 115 страниц машинописного текста. Список литературы включает 62 наименования.

Автор выражает глубокую признательность научному руководителю Черемисиной Е.Н, искренне благодарит Ерофеева С.Г, Голенкова АЛО, Грузмана И .С., Забелина В А. и других участников совместной разработки, а также к.тл. Галуева В.И. и кл\н. О.В.Митракову за ценные советы при обсуждении работы.

СОДЕРЖАНИЕ РАБОТЫ

ГЛАВА 1. Автоматизация геологических и экологических исследований и проблемы ввода пространственной информации

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

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

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

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

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

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

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

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

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

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

Основные выводы формулируются следующим образом:

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

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

Проведенный анализ ГИС позволил сформулировать требования к

программному комплексу ввода и векторизации растровой картографической информации:

1) Использование в качестве входной информации растровых изображений карт и данных дистанционного зондирования Земли (ДЗЗ).

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

3) Программы комплекса должны быть ориентированы на распространенную вычислительную технику: ЮМ PC AT, SUPER AT.

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

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

6) Комплекс должен быть легко наращиваем новыми функциями, в том числе пользовательскими.

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

ГЛАВА 2. Проектирование программного комплекса ввода н векторизации растровой геологической и экологической информация.

В первом разделе проводится анализ операций нал растровыми изображениями в процессе обработки, векторизации и модификации для различных по характеру, типу и размеру исходных картографических материалов (КМ).

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

При растровой склейке изображений, обычно необходимо

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

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

-улучшение изображений: подавление высокочастотного или низкочастотного шума, удаление мелких объектов, изменение яркостных или контрастных характеристик;

- расслоение серого изображения на псевдоцвета, соответствующие цветовой палитре исходной карты;

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

•растровое выделение геологических или антропогенных факторов (линеаментов, кольцевых структур, контуров);

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

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

между несколькими фрагментами.

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

Введенное растровое изображение . может использоваться не для векторизации, а для модификации ранее существовавшего векторного изображения.

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

Рассмотренные транформации можно представить в виде условной функционально-информационной схемы (рис. 1).

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

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

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

□що с

КМ2

1 I Ф3 1 I | Ф3.2 } СФЗЦ

а Ф2.1 | 8 Ф2.2 | а Ф2.з а

т

СКАНИРОВАНИЕ

] 8 РФ2.1 | I РФ2.2 | | РФ2.3 I

РАСТРОВАЯ МОДИФИКАЦИЯ

} РМК1 I

ВПЗПМЕИЗН

I

I РМФ2.3 | I РМКЗ 1

|ВК1

ВЕКТОРИЗАЦИЯ

I

■АЦП

1ВФ2.1 I ? ВФ2.2 | | ВФ2.3 | I ВЕКТОРНАЯ СКЛЕЙКА ] 1ВК2 I

Т

ЕЗШ

I

ИНТЕГРАЦИЯ И МОДИФИКАЦИЯ

[вкаГ]

ИМПОРТ

ш

I ВКИ2

IВКИЗ |

ь:

енэ

ЭКСПОРТ

I ВКАЗ I

Рис.1 Функционально-информационная схема преобразования картографических данных:

КШ - ¡-исходный картографический материал; ФЦ - ./-фрагмент ¡-го картографического материала; РЮ - растровое представление ¡-го картографического материала; РФУ - растровое представление .¡-го фрагмента ¡-го картографического материала; РМОД - модифицированное растровое представление .¡-го фрагмента ¡-го картографического материала; ЕЮ - векторная карта с ¡-го картографического материала; ВФу - векторная карта с ¿-го фрагмента ¡-го картографического материала; ВКИш • интегрированная векторная карта; ВКА1 - векторная карта в альтернативной системе.

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

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

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

2). Блок улучшения растровых изображений карт и обработки ДЗЗ. Учитывая, что в данной технологической позиции могут использоваться другие отечественные и зарубежные разработки, блок должен включать наиболее универсальные виды растровых обработок.

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

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

5) Блок топологических и координатных преобразований векторных изображений должен обеспечивать координатные, афинные, проективные и нелинейные преобразования векторных карт по заданным опорным точкам или данным координатной привязки исходных картматериалов.

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

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

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

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

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

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

В четвертом разделе рассматриваются вопросы организации данных.

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

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

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

ГЛАВА 3. Математическое обеспечение программного комплекса ввода и векторизации растровой картографической информации.

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

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

Структура программного комплекса и схема взамодействия его составных частей приведена на рисунке 2.

Рис.2. Структура программного комплекса

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

ПРОГРАММА УЛУЧШЕНИЯ РАСТРОВЫХ ИЗОБРАЖЕНИЙ

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

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

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

1. Страничный алгоритм скелетирования линий методом стягивания границ для задачи векторизации линий.

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

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

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

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

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

их одновременным стягиванием. Критерием стирания точки контура является наличие пути от соседа слева к соседу справа внутри области.

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

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

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

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

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

3. Алгоритмы трансформации узлово-дугового разбиения областей к представлению п^ошадных факторов полигонами.

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

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

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

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

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

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

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

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

ГЛАВА 4. Разработка типовых технологий применения программного комплекса и его практическая апробация.

В первом разделе предлагаются технологии использования программ комплекса на макро- и микроуровне.

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

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

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

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

4. Коррекция ранее созданной векторной карты при поступлении КМ или данных ДЗЗ с временными изменениями. В технологию этого вида работ входят операции фиксации координатной системы исходной векторной карты, выявления и маркировки опорных точек на поступившем материале,

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

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

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

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

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

ВИМСа (руководитель группы В. В. Грушина).

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

ТКЙСК-растровым жторид1Гор

Файл

Зона Сиенить Около

Пред щщц Функция

СоедПрмп Разъед

Чаг_

Средняя Правая Репер Автомат Линза Объект Элемент

раотр* Номер О/МЯ

МКТОРО»

Цромнь ов —т* i Эмгмнт

Ы|>ОМНЬ мволииим I . . Тип ев *«кта I И*гнитом*о««инмя

РисЗ Визуализация процесса векторизации карты магнитного поля

Сформированные векторные карты были экспортированы в систему ИНТЕГРО (ВНИИГеосистем). Далее, по разработанной в ВИМСе методике были составлены объемные геоплотностная и геомагнитная модели изучаемых территорий. В результате анализа полученных данных были выявлены основные черты глубинного строения региона, выяснен характер сочленения крупных геологических структур.

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

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

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

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

Полученные векторные карты были подвергнуты компьютерной обработке по методике, разработанной во ВНИИГеосистем (Чуткерашвили С.Е. и др.), в результате которой была получена карта динамического потенциала опустынивания, отражающая динамику процесса опустынивания.

ЗАКЛЮЧЕНИЕ

Основные результаты исследований, изложенных в диссертации формулируются следующим образом:

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

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

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

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

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

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

Основные положения диссертационной работы изложены в печатных работах:

1. Система кодирования графической и алфавитно-цифровой информации о химических соединениях. • В кн. 6-ая Всесоюзная конференция "Использование вычислительных машин в спектроскопии молекул и химических исследованиях", ин-т орг. химии СОАН СССР, Новосибирск, 1983,

с.36-37, тезисы докладов (совместно с Вырвич АЛ. и др.).

2. Средства организации "окна" в системе ТЕВУС для цветного графического дисплея. - В сб. "Математические и технические проблемы обработки изображений", ВЦ СОАН СССР, Новосибирск, 1986, с. 113-116.

3. Общесистемное программное обеспечение ТЕВУС - В кн. "Автоматизированная обработка изображений природных комплексов Сибири", Наука, Новосибирск, 1988, с. 128-136. (совместно с Осиповым НА. и ДР-)

4. Пакеты программных средств для интерактивной машинной графики. - В кн.: "Обработка изображений и дистанционные исследования", ВЦ СОАН СССР, Новосибирск, 1987, с28-29.

5. Программное обеспечение цветного полутонового дисплея в системе ТЕВУС - В кн.: "Использование ЭВМ в учебной и научно-исследовательской работе студентов", Новосибирск, НГУ, 1988, с. 185-186. (совместно с Забелиным В А, Осиповым НА)

6. Интерактивные средства изменения и отображения переменных при моделировании процессов и явлений в ТЕВУС - В сб. "Интерактивные диалоговые системы в вычислительных комплексах и. сетях ЭВМ", изд. МИФИ, Москва, 1986, с. 39-41. (совместно с Осиповым НА.)

7. Ввод и векторизация растровых изображений для решения геологических и экологических задач. В журнале "Развитие и охрана недр", 1993 г - в печати (совместно с Черемисиной ЕН, Забелиным ВА.)