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

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

Васин Дмитрий Юрьевич

ИССЛЕДОВАНИЕ МОДЕЛЕЙ ОПИСАНИЯ, РАЗРАБОТКА АЛГОРИТМИЧЕСКОГО, ПРОГРАММНОГО И ТЕХНОЛОГИЧЕСКОГО ОБЕСПЕЧЕНИЯ ОБРАБОТКИ РАСТРОВЫХ ИЗОБРАЖЕНИЙ ГРАФИЧЕСКИХ

ДОКУМЕНТОВ

05.01.01 — Инженерная геометрия и компьютерная графика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Нижний Новгород-2006

РАБОТА ВЫПОЛНЕНА В НИИ ПРИКЛАДНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ НИЖЕГОРОДСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА ИМ. Н. И. ЛОБАЧЕВСКОГО

Научный руководитель: доктор физико-математических наук, профессор Шалфеев Владимир

Дмитриевич

Официальные оппоненты: доктор технических наук, профессор Немирко Анатолий Павлович, доктор физико-математических наук, профессор Супрун Анатолий

Николаевич

Ведущая организация: Вычислительный центр РАН (г. Москва)

октября 2006 п в

Защита диссертации состоится октября 2006 г. в часов на

заседании диссертационного совета Д 212.162.04 при Нижегородском государственном архитектурно-строительном университете по адресу: 603950, г. Нижний Новгород, ул. Ильинская, 65, корпус 5, аудитория 202.

С диссертацией можно ознакомиться в библиотеке Нижегородского государственного архитектурно-строительного университета.

Автореферат разослан *

/2006 г.

Ученый секретарь диссертационного совета кандидат технических наук, профессор. ' В.И. Дергунов

Общая характеристика работы

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

Расширение сфер, требующих автоматизации обработки графической информации, привело к качественному усложнению графических документов (ГДН большие размеры, отсутствие строгих ограничений на шрифты и типоразмеры, наличие фона, большое количество пространственно-логических и топологических связей и метрических отношений между линейными, площадными и дискретными объектами. Практикой выдвинута проблема обработки сложно-структурированных графических документов. Сложно-структурированный, семантически насыщенный документ - это материальный объект (конструкторские проекты, географические и топографические карты, графические материалы медицинской диагностики и поэтажные планы БТ и др.), содержащий образно-знаковые модели действительности в форме графических изображений и терминов естественного языка. Размеры документов могут достигать порядка 1000x1000 мм2 и более, объекты могут изменяться от 0.1 мм до нескольких метров, точность обработки составляет порядка 0.1 мм. Это предопределяет огромные размеры исходных данных - порядка 104 - 105 Кбайт.

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

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

1

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

• технологичность;

• высокая емкостная и временная эффективность;

• естественная интегрируемость в общую схему ГИС.

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

Существенный вклад в решение проблем обработки графической информации и изображений внесли российские ученые A.C. Лебедев, В.В. Александров, В.А. Виттих, Ю.Г. Васин, В.В. Сергеев, В.А. Сойфер, В.П. Пяткин, C.B. Абло-мейко, а также зарубежные ученые Т.Павлидис, Ф.Препарат, У.Претт, Х.Самет, У.Гренандер, Р. Дуда, Г.Харт, К.Фу и другие.

В работах НИИ ПМК ННГУ (Васин Ю.Г,, Башкиров O.A. и др.) был предложен комбинаторно-геометрический подход к обработке растровых изображе-

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

г

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

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

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

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

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

Для достижения этой цели в диссертации решены следующие задачи:

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

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

• Разработаны и развиты методы и алгоритмы решения прикладных задач обработки растровых изображений ГД в ГИС на базе предложенных моделей описания.

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

Методы исследования.

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

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

• В развитии иерархии моделей нижнего уровня структурированного описания растровых изображений ГД.

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

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

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

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

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

гис.

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

Работа выполнена при финансовой поддержке РФФИ, грант поддержки ведущих научных школ № 00-15-96108 и ФЦП «Интеграция» проект К-03392.

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

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

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

• В Главном управлении навигации и океанографии ВМФ МО РФ (ЦКП-280 ВМФ МО РФ) в автоматизированных системах создания мировой коллекции электронных морских навигационных карт;

• В НИИ прикладной математики и кибернетики ННГУ в объектно-ориентированной интеллектуальной геоинформационной системе «ГИС-ТЕРРА»;

• В Поволжском региональном кадастровом бюро Рособразования;

• В учебном процессе на факультете Вычислительной математики и кибернетики Нижегородского государственного университета им. Н.И. Лобачевского (кафедра Интеллектуальные информационные системы и геоинформатика);

Результаты диссертационной работы докладывались и обсуждались ка III Конференции «Распознавание образов и анализ изображений: новые информационные технологии - РОАИ» (Н.Новгород, 1-7 декабря 1997г.), 6-ой,7-ой,8-ой Всероссийской конференциях «Методы и средства обработки сложной графической информации» (Н.Новгород, 2001,2003, 2005 гг.).

Основные положения работы освещены в десяти опубликованных печатных работах.

Структура и объем работы

Диссертация состоит из введения, 4 глав, заключения, списка литературы. Объем основного текста работы — 193 машинописных страниц, список литературы включает 105 наименований

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

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

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

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

В рамках комбинаторно-геометрического подхода к обработке растровых изображений графической информации пространственно-распределенных данных (ПРД) под математической моделью изображения Mv' ранга v понимается тройка вида:

Mv= { Ev, Rv, С}, где Еу = { е/, е2\ е3\ ...esv } - множество непроизводных элементов (НЭ),

Rv = { г/, Tz * гэ\ ••* rtv } — множество допустимых отношений между непроизводными элементами,

Cv = { Civ, Cjv , c3v, ... с/ } - множество характеристик непроизводных элементов.

v= 1,2,3,...N —ранг (уровень) модели.

Исходное растровое изображение на нижнем уровне представляется пиксельной матрицей P={pg|, / = j ~ Pij — код цвета пикселя

(точки) изображения с координатами х; = г*' hx; yj ~j*' hy, где hx, hy - шаг квантования изображения по осям X и Y. Для черно- белых изображений пиксель является бинарной величиной, то есть р = {0,1}.

Пиксель - непроизводный элемент р ={ х, у, с, sw ), где: х, у — растровые координаты пикселя; с — код цвета; sw - коэффициент связи, измеренный в четырех или восьми элементной окрестности пикселя.

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

Связный штрих это набор Н = {1, N. К, С, эшр, } где: I - номер строки или столбца пиксельной матрицы; Н К - координаты начала и конца подряд следующих пикселей одного цвета вдоль линии растра; С — код цвета связанных пикселей, образующих штрих; виу з\у1 — количество связных штрихов со штрихами смежных строк (предыдущей и последующей соответственно).

Два штриха Нр и Нр.[ смежных строк р и р-1связаны, если: (N^1 & л (Ыр.! £ Кр) V (Ки й л (Кр., £ Кр).

Тогда swp = 0, если в предыдущей строке р = * — 1 нет ни одного штриха, для которого справедливо:

(Кр й Н) л(Ир^ К,) V (Кр *Ы.) л (Кр £ К,), (1)

где К, Кл, Ыр, Кр - координаты начала и конца текущего штриха и штриха предыдущей смежной строки. В противном случае з\ур = цр , где цр - кратность выполнения условия (1), то есть цр — количество связанных штрихов предыдущей строки.

Аналогично, зш, = 0, если в последующей строке 8 = 1+1 нет ни одного штриха, для которого справедливо:

(Ы5 ^ Ы,) л (Ы, ^ К,) V (К, ;> N0 л (К. £ КО,

(2)

где N1, К(, К, — координаты начала и конца текущего штриха и штриха последующей смежной строки. В противном случае = где ц, - кратность выполнения условия (2), то есть ц, — количество связанных штрихов последующей строки.

Анализ суперпозиции значений БУ/р и ви^ позволил ввести следующую классификацию графических ситуаций: Штрих изолированный (Ши) Штрих начала растрового объекта (Шн) Штрих конца растрового объекта (Шк) Штрих слияния растровых объектов (Шс) Штрих расщепления растровых объектов (Шр)

3\Ур=0 Л 5\У,=0 &\Ир=0 Л5\У,= 1 8\Ур=1 Л 3\Уа=0

SWp> 1

> 1

Штрих слияния и расщепления растровых объектов (Шср)5\ур > 1 л > 1

Штрихи типа 111с, Шр, Шср - в дальнейшем будем называть узловыми штрихами.

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

Растровый простой объект (РПО) - кластер связных штрихов, не содержащий ситуаций типа слияния или расщепления < 2 л з\у, < 2 (Рис.1). РПО можно выделить только на основе штрихового описания.

¡¡iilllii

III!"*

■Лнншн

Рис. 1

Рис.2

Рис. 3

Растровый составной объект (PCO)- кластер связанных штрихов, для каждого штриха которого выполняется условие swp > 0 л sw, > 0, и для любых двух штрихов найдется хотя бы одна соединяющая их пиксельная траектория, состоящая из связанных смежных элементов (Рис.2). PCO можно построить как на основе пиксельного, так и штрихового описания.

Линейно - площадная модель растра - логическая сумма двух растров, состоящих соответственно из пиксельных линейных, либо площадных растровых объектов (Рис.3). Lsw — характеристика протяженной связности пикселя: Ziw = min(i,,), где и = - направление линии сканирования; Ьц - длина

Л

штриха и в направлении и, содержащего данный пиксель. П - величина порога для Ц, штриха, содержащего данный пиксель. Тогда, если Lsw <; П - пиксель принадлежит линейному растровому объекту, а если Lsw > П - пиксель принадлежит площадному растровому объекту.

Таким образом, иерархию моделей нижних уровней описания растровых изображений можно представить следующей структурной схемой (Рис.4).

Рис. 4 Иерархия растровых моделей описания изображений ГД

Р1х_1 ...Р1х_5 — пиксельное описание растра; - штриховое опи-

сание растра; РП01...РП0П - совокупность простых растровых объектов; РПОЛ РПОЛ к - совокупность линейных, а РПОП1,.,РПОП„ - совокупность площадных растровых объектов; РСС>1,.,РСОт — совокупность растровых составных объектов.

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

Простые растровые объекты делятся на линейные РПОЛ и площадные РПОП. Множество непроизводных элементов (НЭ) состоит из РПОЛ, РПОП, и штрихов (Шн, Шк, Шс, Шр, Шср). Растровые простые объекты примыкают к штрихам.

На рис.5 две связные растровые компоненты: а) растровый простой линейный объект — РПОЛ1 и б) растровый составной объект РСОь состоящий из четырех простых линейных объектов РПОЛ2, РПОЛ5, РПОЛ*, РПОЛ5, одного растро-10

во го простого площадного объекта РПОПь двух штрихов начала - Шн2, Шн3, двух штрихов конца - Шк2, Шкз, одного штриха слияния Шсь одного штриха расщепления Шр(. Шс( — имеет три связи с РПОЛ2, РПОЛз, РПОПь Шр1 - имеет три связи с РПОПь РПОЛ4, РПОЛз

11111 .И И IL-

РПО! -■ • 1 Ü --

- II IIiuHj - III н л II - - ■ 1ШН.

р 1ПП оплп -

i. -t-J- '2 -

:: -И- II г

1 -

* р -п 0 л РПОП*-

1 ■W-l

.ШР, .

ш

- РПОЛд - F М4-Н

-ШК,. IUI -н

tt II . ШК. .

44— 5

1 |

4f

Рис. 5 Структурированное описание растровых изображений ГД

Для PCO и РПО, а также штрихов начала и конца объектов и узловых штрихов, вычисляются характерные признаки следующих типов:

- номер PCO и РПО; количество РПО и штрихов (Шн, Шк, Шс, Шр, Шср) в PCO; координаты описывающего прямоугольника; площадь и периметр этого прямоугольника; площадь РПО н PCO; отношение площади описывающего прямоугольника к площади РПО и PCO; номер штриха; длина штриха; количество связей и др.

Построенная иерархия растровых моделей структурированного описания изображений ГД на растровом уровне, позволяет осуществлять:

• структурирование растровых изображений;

• распараллеливание обработки растровых объектов;

• расширение класса используемых методов обработки растровых изображений на нижних уровнях описания;

• использование не только локальных, но и интегральных критериев обработки;

• распознавание линейных, площадных и дискретных растровых объектов;

• сокращение емкостной и вычислительной сложности алгоритмов обработки растровых изображений ГД.

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

М_к - контурную модель изображения;

М_1к - линейно-контурную модель изображения;

М_зи - сегментно - узловую модель изображения.

Контурная модель изображения. Контурная модель изображения М|' -(Е1,Я,, С^, где Е,={е1,}={Хн', уЛ хД у«"} 1-ый вектор контура, г, -отношение примыкания векторов контура: вектор всегда примыкает к единственному последующему вектору и к единственному предыдущему, так что «черное» всегда остается справа; с~с1 - вектор может быть внутренним и внешним.

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

Линейно-контурная модель изображения. Линейно-контурная модель изображения Мг1 = (Е,, Я,, С^, где Е,-{е,!, е(2, е,3, е(4}, е/ - вектор контура, в]2 -вектор линии, е ,3 - черная точка на белом фоне, е,4 - белая точка на черном фоне. Набор отношений К,; Г] - вектор контура всегда примыкает к предыдущему и последующему векторам контура и может примыкать к вектору линии, г2 • вектор линии может примыкать к последующему и предыдущему векторам линии и

вектору контура или иметь один или два свободных конца, г3 - точки не примы-12

кают ни к каким объектам — изолированы. Набор характеристик С,: с, - вектор линии имеет толщину, с2 - вектор контура может быть внешним или внутренним, с3 - точка имеет диаметр. Объекты изображения: линия - последовательность векторов линии; контур — последовательность векторов контура, черная и белая точки. Линии и контуры не пересекаются, контуры замкнуты.

Сегментно-узловая модель изображения. Сегментно-узловая модель изображения является векторной моделью, целиком описывающей все изображение в виде набора связных множеств. Эту модель можно представить в виде: Msu4 = {Uk4,Sj4}, k = lf 2, 3,p, j=l,2, ...ш, где непроизводные элементы Uk4,Sj4 представляют собой узлы и сегменты. Под сегментом понимается отрезок {хн,ун,хк,ук}, а под узлом, точка с координатами {x,y,SwL}, где SwL указатель на L-сегмент, связанный с этим узлом.

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

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

Штриховая модель. Представляется в ЭВМ в виде файла, содержащего заголовок и совокупность строк штрихов, разделенных специальными символами-разделителями.

Совокупность РПО, ГСО, контурная и линейно-контурная модели

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

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

для штриховых данных: формирование штрих — файла; определение связности двух штрихов; определение связности штрихов двух смежных строк растра; формирование растровых простых объектов (РПО); формирование растровых составных объектов (PCO); разделение РПО на линейные и площадные; вы-

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

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

Множество разработанных алгоритмов можно разделить на следующие классы:

• алгоритмы логической фильтрации растровых изображений ГД;

• алгоритмы построения иерархии растровых и векторных моделей описания изображений ГД;

• алгоритмы структурного распознавания тематических объектов на растровых ГД;

• алгоритмы тематической обработки и редактирования растровых изображений ГД,

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

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

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

*

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

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

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

При построении контурной и линейно-контурной моделей за счет использования информации о РПО и PCO удалось сократить емкостную сложность алгоритмов в 4-5 раз (отпадает необходимость хранить всю таблицу связей координат точек контура или линии), а также временную сложность в 2-3 раза.

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

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

гд.

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

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

Для обработки поэтажных инвентаризационных планов зданий и сооружений были разработаны алгоритмы распознавания объектов типа:

- капитальные стены, перегородки, комнаты, оконные проемы, окна, дверные проемы, двери, лестничные проемы, лестницы, шкафы.

При этом были выделены НЭ - контура, прямоугольники, отрезки, а в качестве признаков выбраны:

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

Распознаваемые объекты жилищной застройки топографических карт масштаба 1:10000— 1:100000 включали: строения дискретные огнестойкие и неогнестойкие, строения площадные огнестойкие и неогнестойкие, кварталы.

При этом были выделены в качестве НЭ - контура объектов, а в качестве признаков выбраны:

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

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

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

1. Информационное обеспечение:

• Обоснован выбор структуры представления моделей описания растровых и тематических объектов ГД.

♦ Разработаны структуры рабочих массивов для различных алгоритмов обработки растровых изображений ГД.

• Разработан формат представления файла протокола, совместимый с информационным обеспечением системы ГИС-ТЕРРА.

• Разработан формат файла кодов, совместимый с информационно -терминологической системой классификатора и форматом интегрального файла в рамках общей технологии ГИС.

• Разработан формат файлов согласования структур моделей описания нижних уровней с моделями верхних уровней.

2. Архитектура программных комплексов:

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

• Обоснован и реализован эффективный выбор стратегии запросов к

базе данных.

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

Были реализованы:

• Библиотека базовых функций, поддерживающая построение иерархии моделей описания и тематической обработки растровых изображений ГД,

• Система «Интеллектуальный редактор растровых изображений

сложных ГД».

• Информационная технология и подсистема для решения задач автоматического ввода объектов жилищной застройки на топографических картах и планах.

• Информационная технология и подсистема создания цифровых инвентаризационных поэтажных планов зданий.

Все программы реализованы на языке программирования С++, В качестве инструментальных средств для создания и отладки ПО использовалась интегрированная среда разработки Borland С++ Builder. Разработанное ПО обладает следующими важными достоинствами: высокая вычислительная производитель-

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

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

Интеллектуальный редактор растровых изображений

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

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

В состав автоматически выполняемых функций редактора входят:

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

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

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

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

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

Автоматизированная подсистема создания цифровых инвентаризационных поэтажных планов зданий.

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

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

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

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

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

Функциональная блок-схема технологии создания цифровых инвентаризационных планов зданий и сооружений представлена па рис.6 (ЦПИПЗС).

Рис. 6. Функциональная блок-схема технологии создания ЦПИПЗС

Автоматизированная подсистема ввода топографических объектов жилищной застройки на топографических картах масштабного ряда 1:10000-1:100000

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

При разработке подсистемы учитывались следующие особенности представления выделяемых объектов: большое число распознаваемых объектов (N>10000); большая вариабельность типоразмеров объектов; особенности нормативного отображения (слияние с другими типами объектов); пространственная распределенность описания дискретных объектов; необходимость использования описания объектов с разных документов для определения их атрибутов.

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

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

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

Реализованы этапы интерактивного редактирования и доввода нераспознанных объектов.

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

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

Полудни*

■ТрикоIих аомл*3

(истросогв

Н»6р£С*ИИ4

«т^нйт нн ых пллотшо»

лри«яжл «опуч^ииых

• ИЛЬТрлф» и с одного р«трЛ>ДЛЛ»м» ! <«Й*Г1>, нмлир»4нных

л ус тот »мугри

*ориир»»»*1* момл*

Ркслейнн* ПФ0ГрФ«ии«

«штурм

МННЫХ м М6А9ЛИ

ПЛ6Ц1АНЫ*

ЯЛ»1*ЖМ* р«01р«1к£к

J цмних

Рлзй*пынл пплциных РО г» гттибупт

Форвнралния мд*т

06ь«ггу О ЛруГМЯ ПЛ4СТЫ4»

Инт*рмтнмм

■ «оно» оВъмт**

■ р*м« гряфмчмиД БД

Устмо«л»ш*

Т»МЛ«П»*«1МХ

С1П(1

Сиаши юкгрол« ич*ст»»

Злгруж» гр>фти1уч БД

*ораир«мин« хгрлггарютм рмпоммннх обьито»

9«1М1>нф*

■ *ТрЯ1И

•и1*л*нник 3*3

ДН«Р,«НЖ*| ПДФЦЛАНШ

«ОрНнрОММ*

Матриц* фАНИЦ

Л поемных ОЙЧГТФКДО

Слити* амрмш

(ОНТУрОР ««ТОДСИ ■ИНН ИКОНОЙ

«ппроясм нации

#0р*Мр4»1НН4

дцеди V ннаншыч

ПрНЭИЛН» РНЛФНШММ

П4рмматф, чнспо

гонту рл

КпЛОФнфмаЦИЯ

■он-гуре» »

»форИИрФМИИШ

Пря»>и>0»*а лр«стр1нег<*

Гйфнирнн«!» »ПЛрФМИЩЦМ »Щ«Л*»1кл( м

ттап*

рЙСЛйОМЯМНН* ({Итуро*

лвпцяДЖЗ_

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

знаками

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

Основные результаты и выводы.

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

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

Разработаны и программно реализованы базовые алгоритмы построения моделей описания РИГД и структур их представления.

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

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

Созданы:

■ Библиотека базовых функций.

■ Интеллектуальный редактор растровых данных.

■ Информационная технология и подсистема для решения задач автоматического ввода объектов жилищной застройки на топографических картах масштабного ряда 1:10000-1:100000.

■ Информационная технология и подсистема создания цифровых инвентаризационных поэтажных планов зданий и сооружений.

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

■ высокую вычислительную и емкостную эффективность;

■ полную технологическую совместимость.

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Васин Д.Ю. Классификация сигналов стохастического автогенератора методами распознавания образов. / Васин Д.Ю., Громов В.П.// Известия высших учебных заведений. Прикладная нелинейная динамика, т,2, № 2, 1994г, Саратов.

2. Васин, Д.Ю. Технология выделения и описания топографических знаков жилой застройки. / Д.Ю. Васин, В.П. Громов // Распознавание образов и анализ изображений.: новые информационные технологии (РОАИ): 3 конференция, 1-7 декабря 1997г., г, II. Но в город, в 2 частях. Часть 2, стр. 12-14.

3. Васин, Д.Ю, Распознавание топографических знаков жилой застройки. / Д.Ю. Васин, В.П. Громов // Распознавание образов и анализ изображений.: новые информационные технологии (РОАИ): 3 конференция, 1-7 декабря 1997г., г. Н.Новгород, в 2 частях. Часть 2, стр. 14-17,

4. Васин, Д.Ю. Подсистема редактирования и обработки растровых графических изображений. / Ю.Г. Васин, Д.Ю. Васин, В.П. Громов, Р.Р.Иксанов, А.Е. Соколов // Распознавание образов и анализ изо-

бражений.: новые информационные технологии (РОАИ): 3 конференция, 1-7 декабря 1997г., г. Н.Новгород, в 2 частях. Часть 2, стр. 23-25.

5. Васин, ДЛО. Разработка и создание базовых интеллектуальных функций редактора растровых графических данных. /Д.Ю. Васин, В.П. Громов //Методы и средства обработки сложной графической информации: 6 Всероссийская конференция с участием стран СНГ, 25-27 сентября 2001г., Н.Новгород, стр. 19-21.

6. Васин, Д.Ю. Интеллектуальный редактор растровых данных. /Д.Ю. Васин, В.П. Громов // Методы и средства обработки сложной графической информации: 6 Всероссийская конференция с участием стран СНГ, 25-27 сентября 2001г., Н.Новгород, стр. 21-23.

7. Васин, Д.Ю. Структурное описание растровых данных. / Ю.Г. Васин, Д.Ю. Васин, В.П. Громов // Методы и средства обработки сложной графической информации: 6 Всероссийская конференция с участием стран СНГ, 25-27 сентября 2001г., Н.Новгород, стр. 23-29.

8. Васин, ДЛО. Геометрическое моделирование зашумленных растровых изображений / Д.Ю. Васин, А.А Горбунов, В.П. Громов // Методы и средства обработки сложной графической информации: 7 Всероссийская конференция с участием стран СНГ, 15-18 сентября 2003г., Н.Новгород, стр. 21-23.

9. Васин ДЛО. Интеллектуальное редактирование линейной модели растрового изображения / Д.Ю. Васин // Методы и средства обработки сложной графической информации: 7 Всероссийская конференция с участием стран СНГ, 15-18 сентября 2003г., Н.Новгород, стр. 1920.

Ю.Васин, ДЛО. Развитие возможностей интеллектуального редактора в задаче оперативного обновления растровых изображений. / Ю.Г. Васин, ДЛО. Васин // Методы и средства обработки сложной графической информации: 8 Всероссийская конференция с участием стран СНГ, 12-16 сентября 2005г., Н.Новгород, стр. 8-10.

Подписано в печать 31.08.2006 г. Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Гарнитура «Тайме». Усл. п. л. 1. Заказ № 1289. Тираж 100 экз.

Отпечатано с готового оригинал-макета в типографии Нижегородского госуниверситета им. Н.И. Лобачевского. Лиц. ПД№ 18-0099 от 4.05.01. 603000, г. Н. Новгород, ул. Б. Покровская, 37

Введение.

Глава 1. АНАЛИЗ ИЗОБРАЖЕНИЙ ГРАФИЧЕСКИХ ДОКУМЕНТОВ, МОДЕЛЕЙ И МЕТОДОВ ИХ ОБРАБОТКИ.

1.1. Виды изображений и их информативная емкость.

1.2. Основные технологические этапы, методы и алгоритмы обработки растровых изобраэ/сений ГД.

Выводы.

Глава 2. МАТЕМАТИЧЕСКИЕ МОДЕЛИ ОПИСАНИЯ И ПРЕДСТАВЛЕНИЯ РАСТРОВОЙ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ.

2.1. Структурная модель растровых данных.

2.2. Структурная модель векторных данных.

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

2.3.1. Растровая модель.

2.3.2. Штриховая модель.

2.3.3. Модели, реализующие объектное описание растровых данных (совокупность РПО, РСО, контурная, линейно-контурная, линейная, сегментно-узловая).

Выводы.

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

3.1. Запись алгоритмов.

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

3.2.1. SwPix - определение 4-элементной связности пикселя.

3.2.2. PixStrix - преобразование пиксельной строки в строку штрихов.

3.2.3. Strix Pix -- преобразование строки штрихов в пиксельную строку.

3.2.4. PixBIob - построение одиночной области связных одноцветных пикселей

3.2.5. PixBIobAII - построение всех областей связных одноцветных пикселей

3.2.6. RastrKon - построение одиночного контура области связных не фоновых пикселей.

3.2.7. RastrKonAll - построение всех контуров не фоновых связных растровых областей пиксельной матрицы Р.

3.2.8. SHPIL - расслоение растровых данных на «площадные» и «линейные» объекты

3.3. Алгоритмы построения иерархии моделей штрихового и векторного уровней описания растровых данных ГД.

3.3.1. Формирование штриховой модели растровых данных по бинарной пиксельной матрице.

3.3.2. Алгоритм формирования связных растровых компонент по штриховым растровым данным.

3.3.3. КОМ - алгоритм формирования контурной модели по штриховой модели растровых данных.

3.3.4. VLO - алгоритм построения линейной векторной модели.

3.3.5. FSSU - алгоритм построения сегментно-узловой модели.

3.4. Вспомогательные и сервисные алгоритмы построения моделей растровых данных.

3.4.1. SwStrixString - Установление связности штриха со штрихами смежной строки

3.4.2. SwStr - установление связи штрихов двух смежных строк.

3.4.3. AddStrih - алгоритм логического сложения двух строк штрихов.

3.4.4. SubStrih - алгоритм логического вычитания двух строк штрихов.

3.4.5. MulStrih - логическое умножение двух строк штрихов.

3.4.6. ARITHSTR - алгоритм выполнения логических операций над файлами в штриховой модели данных.

3.4.7. LineApr - алгоритм линейной аппроксимации множества точек плоскости методом наименьших квадратов.

3.4.8. KLAST - алгоритм кластеризации множества точек плоскости.

3.4.9. FIP - алгоритм объектной фильтрации растровых данных.

3.4.10. FRS - алгоритм автоматической коррекции границ линейных растровых объектов и поиск зон разрыва растровых линий.

3.4.11. POVOROT - алгоритм поворота растра на заданный угол.

3.4.12. Privlmp.exe - алгоритм координатной привязки документа.

3.4.13. КРК - алгоритм сегментации плоской кривой на однородные фрагменты.

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

3.5. Алгоритмы конвертации форматов представления различных моделей описания растровых изображений ГД.

3.5.1. KMPSTR - алгоритм перехода от контурной модели изображения к штриховой.

3.5.2. LMPBAS - алгоритм передачи объектов из файла в структуре «паспорт-метрика» в формат базы данных.

3.6. Алгоритмы распознавания и описания объектов жилой застройки на топографических картах масштаба 1:10000 -1:100000.

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

3.6.2. Особенности представления выделяемых объектов.

3.6.3. Непроизводные элементы и признаки распознавания объектов жилой застройки.

3.6.4. Эталоны объектов решающих правил.

3.6.5. Алгоритмы формирования признаков распознавания.

3.6.6. Алгоритмы распознавания и описания объектов жилой застройки на топографических картах масштаба 1:10000.

3.6.7. Алгоритм распознавания и описания объектов жилой застройки на топографических картах масштабов 1:25000-1:50000.

3.6.8. Алгоритмы распознавания и описания объектов жилой застройки на топографических картах масштаба 1:100000.

3.6.9. Алгоритмы распознавания и описания объектов "КВАРТАЛ" на ТК масштабов 1:10000 - 1:50000.

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

3.7.1. Особенности цифровых изображений инвентаризационных планов зданий.

3.7.2. Непроизводные элементы и признаки распознавания объектов инвентаризационных планов зданий и сооружений.

3.7.3. Алгоритмы формирования признаков распознавания.

3.7.4. Результаты экспериментов по обработке планов.

Выводы.

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

4.1. Информационное обеспечение.

4.1.1. Структуры для работы со штриховыми данными.

4.1.2. Структуры для работы с векторными данными.

4.1.3. Структурное описание сегментно-узловой модели.

4.1.4. Структуры, используемые при построении контурной модели по сегментно-узловой

4.1.5. Форматы служебных файлов.

4.2. Библиотеки базовых и интерфейсных функций построения иерархии моделей описания и тематической обработки РИГД.

4.2.1 Функции.

4.2.2. Файловые форматы графических данных.

4.2.3. Среда разработки и условия использования.

4.2.4 Интерфейсные библиотеки.

4.2.5. Библиотека базовых функций.

4.2.6. Программные технологические цепочки.

4.3. Интеллектуальный редактор растровых изображений.

4.3.1. Принципы создания интеллектуального редактора графических данных

4.3.2. Назначение и функциональные возможности редактора.

4.3.3. Входные и выходные данные программы.

4.3.4. Состав комплекса интеллектуального редактирования.

4.3.5. Порядок работы.

4.4. Автоматизированная подсистема создания цифровых инвентаризационных планов зданий и сооружений.

4.4.1. Особенности цифровых изображений инвентаризационных планов зданий. .;.;.

4.4.2. Основные требования, предъявляемые к подсистеме.

4.4.3. Назначение подсистемы.

4.4.4. Входные и выходные данные.

4.4.5. Состав программного обеспечения подсистемы.

4.4.6. Условия функционирования подсистемы.

4.4.7. Функциональная блок-схема технологии создания цифровых баз данных инвентаризационных планов БТИ и последовательность технологических операций.

4.4.8. Методика выбора и формирования параметров обработки.

4.4.9. Технология обработки инвентаризационных поэтажных планов зданий.

4.5. Подсистема выделения и описания топографических знаков жилой застройки

4.5.1. Назначение.

4.5.2. Состав программного обеспечения подсистемы.

4.5.3. Основные технологические этапы.

Выводы.

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

Расширение сфер, требующих автоматизации обработки графической информации, привело к качественному усложнению графических документов (ГД)- большие размеры, отсутствие строгих ограничений на шрифты и типоразмеры, наличие фона, большое количество пространственно-логических и топологических связей и метрических отношений между линейными, площадными и дискретными объектами. Практикой выдвинута проблема обработки сложно-структурированных графических документов. Сложно-структурированный, семантически насыщенный документ - это материальный объект (конструкторские проекты, географические и топографические карты, графические материалы медицинской диагностики и поэтажные планы БТ и др.), содержащий образно-знаковые модели действительности в форме графических изображений и терминов естественного языка. Размеры документов могут достигать порядка 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 наименований.

Выводы

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

При этом были:

• Разработаны; структуры рабочих массивов для различных алгоритмов обработки растровых изображений ГД.

• Разработан формат представления файла протокола, совместимый с информационным обеспечением системы ГИС-ТЕРРА.

• Разработан формат файла кодов, совместимый с информационно -терминологической системой классификатора и форматом интегрального файла в рамках общей технологии ГИС.

• Разработан формат файлов согласования структур моделей описания нижних уровней с моделями верхних уровней.

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

• Обоснован и реализован эффективный выбор стратегии запросов к базе данных.

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

Разработаны и созданы:

• Библиотека базовых функций, поддерживающая построение иерархии моделей описания и тематической обработки растровых изображений ГД. . ■

• Система «Интеллектуальный редактор растровых изображений сложных ГД».

• Информационная технология и подсистема для решения задач автоматического ввода объектов жилищной застройки на топографических картах и планах. •

• Информационная технология и подсистема создания цифровых инвентаризационных поэтажных планов зданий.

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

• Разработана модель структурированного описания РИГД.

• Разработаны структуры представления и хранения моделей описания РИГД. .

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

• Разработаны базовые алгоритмы построения векторных моделей описания ГД. При построении контурной и линейно-контурной моделей за счет использования информации о РПО и РСО удалось сократить емкостную сложность алгоритмов в 4-5 раз (отпадает необходимость хранить всю таблицу связей координат точек контура или линии), а также временную сложность в 2-3 раза.

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

• Разработаны и программно реализованы алгоритмы решения прикладных тематических задач обработки РИГД на базе предложенных моделей описания.

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

• Созданы:

Библиотека базовых функций.

Интеллектуальный редактор растровых данных.

Информационная технология и подсистема для решения задач автоматического ввода объектов жилищной застройки на топографических картах масштабного ряда 1:10000-1:100000.

Информационная технология и подсистема создания цифровых инвентаризационных поэтажных планов зданий и сооружений.

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

• высокую вычислительную и емкостную эффективность;

• полную технологическую совместимость.

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

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

1. Абламейко С.В. Метод утоныпения объектов бинарных изображений // Автоматизация процессов проектирования. Мн., 1982. Вып. 4.

2. Абламейко С.В., Апарин Г.П. и др. Географические информационные системы. Минск, 2000. АНБ. 265 с.

3. Абламейко С.В., Берейшик В.И., Старовойтов В.В. и др. Распознавание объектов графических изображений: обзор методов. Мн., 1988. (Препринт / Ин-т техн. кибернетики АН БССР: 41).

4. Абламейко С.В., Лагуновский Д.М. Обработка изображений: технология, методы, применение: Учебное пособие Минск: Амалфея, 2000.

5. Александров В.В., Горский Н.Д. Представление и обработка изображений. Рекурсивный подход Л.: Наука, 1985.

6. Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман Структуры данных и алгоритмы Москва: Издательский дом "Вильяме", 2001.

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

8. Анисимов Б.В., Курганов В.Д., Злобин В.К. Распознавание и цифровая обработка изображений. М., 1983.

9. Браверман Э.М., Мучник ' И.Б. Структурные методы обработки эмпирических данных. М., 1983,

10. Бутаков Е.А. Обработка изображений на ЭВМ М.: Радио и связь, 1987.

11. П.Бутаков Е.А., Островский В.И., Фадеев П.Л. Обработка изображений на1. ЭВМ. М., 1987.

12. Васин Д.Ю., Громов В.П. Классификация сигналов стохастического автогенератора методами распознавания образов // Известия высших учебных заведений. Прикладная нелинейная динамика, т.2, № 2, 1994г, Саратов.

13. Васин Д.Ю., Громов В.П. Распознавание топографических знаков жилой застройки // Распознавание образов и анализ изображений: новые информационные технологии (РОАИ): 3 конференция, 1-7 декабря 1997г., г. Н.Новгород, в 2 частях. Часть 2, стр. 14-17.

14. Васин Д.Ю., Громов В.П. Интеллектуальный редактор растровых данных // Методы и средства обработки сложной графической информации: 6 Всероссийская конференция с участием стран СНГ, 25-27 сентября 2001г., Н.Новгород, стр. 21-23.

15. Васин Ю.Г., Васин Д.Ю., Громов В.П. Структурное описание растровых данных // Методы и средства обработки сложной графической информации: 6 Всероссийская конференция с участием стран СНГ, 25-27 сентября 2001г., Н.Новгород, стр. 23-29.

16. Васин Д.Ю. Интеллектуальное редактирование линейной модели растрового изображения // Методы и средства обработки сложной графической информации: 7 Всероссийская конференция с участием стран СНГ, 15-18 сентября 2003г., Н.Новгород, стр. 19-20.

17. Васин Ю.Г. "Хорошо приспособленные" базисы и задачи обработки экспериментальной информации: Учебное пособие / Горьк. гос. ун-т -Горький, 1979.- 129с.

18. Васин Ю.Г. "Хорошо приспособленные" локальные однородные методы обработки графической информации // Автоматическая обработка сложной графической информации: Межвуз. тематич. сб. науч. тр. / Горьк. гос. ун-т. -Горький, 1984.-С. 131-158.

19. Васин Ю.Г., Лебедев Л.И. Контурные корреляционно-экстремальные методы обнаружения и совмещения объектов видеоинформациий // Методы и средства обработки графической информации: Межвуз. сб. науч. тр. / Горьк. гос. ун-т Горький, 1987. - С. 97 - 112.

20. Васин Ю.Г., Башкиров О.А., Рудометова С.Б. Математические модели структурированного описания графических изображений // Автоматизация обработки сложной графической информации. Горький, 1984. С. 92-116.

21. Васин Ю.Г., Жерздев С.В. Эффективное кодирование усеченных двоичных деревьев в задаче сжатия изображений // Труды 6-й конференции "Методы и средства обработки сложной графической информации". Н.Новгород, 2001. С.36-38.

22. Васин Ю.Г., Крахнов А.Д., Утешева Т.Ш. Метод от общего к частному при решении пространственных задач дискретной геометрии // Автоматическая обработка сложной графической информации: Межвуз. сборник / Горьк. гос. ун-т Горький, 1988. - С. 73-83.

23. Виттих В.А., Сергеев В.В., Сойфер В.А. Обработка изображений в автоматизированных системах исследований. М.: Наука, 1982.

24. Гардан И., Люка М. Машинная графика и автоматизация конструирования. -М.: Мир, 1982 .

25. Гашников М.В., Глумов Н.И., Сергеев В.В. Информационная технология компрессии изображений в системах оперативного дистанционного зондирования. // Известия Самарского научного центра РАН, 1999, №1, с.99-107.

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

27. Горелик А.Г. Автоматизация инженерно-графических работ с помощью ЭВМ: Учеб. Пособие для вузов. Мн., 1979.

28. Горелик А.Л., Гуревич И.Б., Скрипкин В.А. Современное состояние проблем распознавания. М., 1985.

29. Гренадер У. Лекции по теории образов: В 3 т. М., 1979. Т.1. Синтез образов.

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

31. Евстигнеев В.А., Касьянов В.Н. Алгоритмы на деревьях Новосибирск: ВЦ, 1989.

32. Журавлев Ю.И., Гуревич И.Б. Распознавание образов и распознавание изображений // Распознавание, классификация, прогноз. Ежегодник. Москва. Наука, 1989. Вып. 2. С. 5-72.

33. Кийко В.М., Шлезингер М.И. Выделение и кодирование линий в системе ввода в ЭВМ графических изображений // УСиМ. 1984. № 1. С. 56-59.

34. Климов А.С. Форматы графических файлов // К.: НИПФ "ДиаСофт Лтд.", 1995.

35. Кричевский, Р.Е. Сжатие и поиск информации М: Радио и связь, 1989.

36. Кудин А.В., Жерздев С.В. Алгоритм RRE-кодирования технических изображений // Вестник Нижегородского университета. Математическое моделирование и оптимальное управление. Н.Новгород: Изд-во ННГУ, 1998. Вып.2~(19).

37. Куконин А.Г., Ларкин Е.В., Ярмош Н.А. // Автоматизация проектирования в машиностроении. Мн., 1983. С. 130-133.

38. Кунт М., Икономопулос А., Кошер М. Методы моделирования изображений второго поколения // ТИИЭР, 1985, т.73, №4.

39. Купчинаус С.Ю. Алгоритмы утоньшения графических изображений // Дискретные системы обработки информации. Ижевск: ИМИ, 1979. С. 23-27.

40. Кучуганов В.Н. // Автоматизация обработки сложной графической информации. Горький, 1984. С. 78-91.

41. Ланге М.М. Древовидная сегментация образов для ускорения анализа сцен // Прикладные проблемы искусственного интеллекта: Сб. науч. тр. М.: ИФТП, 1991.

42. Майника Э. Алгоритмы оптимизации на сетях и графах. М., 1981.

43. Методы компьютерной обработки изображений / Под ред Сойфера В.А. Москва, Физматгиз, 2000. 780 с.

44. Методы компьютерной обработки изображений / Под ред. В.А. Сойфера -М.: Физматлит, 2001.

45. Митчелл О.Р., Делп Э. Усеченное блочное кодирование многоуровневой информации // ТИИЭР, 1980, т.68, №7.

46. Мусман Х.Г., Пирш П., Граллерт Х.Й. Достижения в области кодирования изображений // ТИИЭР, 1985, т.73, №4.

47. Нетравали А.Н., Лимб Дж.О. Кодирование изображений: обзор // ТИИЭР, 1980, т.68, №3.

48. Ноултон К. Простые эффективные методы кодирования без потерь для передачи многоуровневых и двухуровневых изображений с постепенным воспроизведением // ТИИЭР, 1980, т.68, №7.

49. Ньюмен Ню, Спрулл Р. Основы интерактивной машинной графики. М., 1976.

50. Павлидис Т. Алгоритмы машинной графики и обработки изображений -Москва: Радио и связь, 1986 .

51. Петренко А.И., Семенков О.И. Основы построения систем автоматизированного проектирования. Киев, 1985.

52. Петров О.М. О некоторых задачах обработки сложной графической информации // Автоматизация обработки сложной графической информации. Горький, 1984. С. 3-12.

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

54. Претт У. Цифровая обработка изображений, в 2 т., Т. 1, 2. Москва: Мир, 1982.

55. Рамачандран Е. //ТИИЭР. 1980.Т. 68, № 7. С.68-73.

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

57. Романов В.Ю. Популярные форматы файлов для хранения графических изображений на IBM PC. М: Унитех, 1992.

58. Русын Б.П. Структурно-лингвистические. методы распознавания изображений в реальном времени. Киев, 1986.

59. Рябко Б.Я. Сжатие информации с помощью стопки книг // Проблемы передачи информации, 1980. Т.16, №4.

60. Семенков О.И., Абламейко С.В. и др. Обработка и отображение информации в растровых графических системах. Минск. Наука и техника, 1989. 174 с.

61. Стронгин Р.Г. Численные методы в многоэкстремальных задачах // М.: Наука, 1978.

62. Тимохин В.И. Применение ЭВМ для решения задач распознавания образов. Л., 1983.

63. Ту Дж., Гонсалес Р. Принципы распознавания образов. М., 1978.

64. Чеголин П.Г., Леонович Э.Н. Автоматизация преобразования сложных форм графической информации в цифровой код. Мн., 1973.

65. Шлезингер М.И. Математические средства обработки изображений. Киев. Наукова думка, 1989. 200 с.

66. Чукин Ю.В. Стуктуры данных для представления изображений. // Зарубежная радиоэлектроника, 1983, №8.

67. Фу К. Структурные методы в распознавании образов. М., 1977.

68. Фурман М.А., Кревецкий А.В. и др. // Введение в контурный анализ и его приложение к обработке изображений и сигналов. Москва. Физматгиз, 2000. 612 с.

69. Abele L. Statistische und strukturelle Texturanalyse mit Anwendungen in der Bildsegmentierung: Dokt. dissertation. Munchen. 1982

70. Arccellin C., Sanniti di Baja G. An approach to figure decomposition using with information // Computer vision, graphics and image processing. 1984. Vol. 26. P. 61-72.

71. D.H. Ballard Strip trees: A hierarchical representation for curves / Comm. of the ACM-1981.-May.

72. Blum H, Nagel R. Shape description using weighted symmetric axis features // Pattern Recognition. 1978. Vol. 10. P. 167-180.

73. Burt P.J. Tree and Pyramid Structures for Coding Hexagonally Sampled Binary Images. CGIP(14), No. 3, 1980, pp. 271-280.

74. W. Burton Representation of many-sided polygons and polygonal lines for rapid processing / Comm. of the ACM 1977. - March.

75. Christopher J., Van Wyk C.J. // Comput. Vision, Graphigs and Image Process 1984. №25. P. 383-392.

76. Cleary J.G., Witten I.H. A comparison of enumerative and adaptive codes. IEEE Trans. Inf. Theory, IT-30, 2(Mar.l984), pp.306-315.

77. Cleary J.G., Witten I.H. Data compression using adaptive coding and partial string matching. IEEE Trans. Commun. COM-32, 4(Apr.l984), pp.396-402.

78. Cormack G.V., Horspool R.N. Algorithms for adaptive Huffman codes. Inf.Proce'ss.Lett. 18, 3(Mar.l984), pp. 159-166.

79. Fisher Y. editor. Fractal Image Compression. Theory and Application. Springer-Verlag, 1995.

80. Fu K.S. // IEEE Trans, on Pattern Anal, and Mach Intell. 1986. Vol. 7, № 3. P. 394-404.

81. Gunter Efficient structures for geometric data management// LNCS 1988. -V.337.

82. Huffman D.A. A method for the construction of minimum redundancy codes. In Proceedings of the Institute of Electrical and Radio Engineers 40, 9(Sept.l952), pp.1098-1101.

83. Matsuyama Т., Saburi К., Nagao M. // Comput. Graphigs and Image Process. 1982. Vol. 18, №3. P. 259-278.

84. Montanari U. // J. Assoc. Comput. 1969. Vol. 16, № 4. P. 534-549.

85. Pavlidis T.A. // Comput. Graph, and Image Process. 1980. Vol. 13, № 2. P. 142157.

86. Rosenfeld A. //J. Assoc. Comput. 1970. Vol. 17, № 1. P. 146-160.

87. Rosenfeld A. A characterisation of parallel thinning algorithms // Information and Control. 1975. Vol. 29, № 3. P. 286-291.

88. Samet H. Computing Perimeters of Regions In Images Represented By Quadtrees / Trans. Of Pattern Anal, and Math. Intell. 1982. - V.4. - P. 524 - 528.

89. Sklansky J., Gonsalez V. // Pattern Recognition. 1980. Vol. 12. P. 327-331.

90. Stefanelli R., Rosenfeld A. Spme parallel thinning algorithms for digital pictures // J. Assoc. Comput. 1971. Vol. 18, № 2. P. 255-264.

91. Tafoya B.R. //Proc.Soc, Photo-Opt. Instrum. Eng. 1978. Vol. 155. P. 2-7.

92. Toriwaki G.I., Kato U., Fukumura T. // IEEE Trans, on Systems, Man Cybernetics. 1979. Vol. SMC-9, № 10. P. 628-643.

93. Tomita F., Shirai Y., Tsuji S., // IEEE Trans, on Pattern Anal, and Mach Intell. 1982. Vol. 4, №2. P. 183-191.

94. Triendl E.E. Skeletonization of noisy handdrawn symbols using parallel operations // Pattern Recognition. 1970. Vol. 2, № 3. p. 215-226.

95. Tsuji S., Tomita F. // Comput. Graphigs and Image Process. 1973. Vol. 2. P. 216231.

96. Wu F., Xu J, He Y. // Proc. 8-th Int. Conf. On Pattern Recognition. P, 1986. Vol. 2. P. 1210-1212.

97. Ziv J., Lempel A. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, Vol.23, 3(May 1977), pp.337-343.1. УТВЕРЖДАЮ»

98. Зам. руководителя Федерального *езии и картографииаген1. Н. Александров2006 г.1. АКТо внедрении результатов диссертационной работы Васина Д.Ю. на соискание ученой степени кандидата технических наук

99. Краткое описание и основные технические характеристики внедряемой продукции, отличительные черты, положительные качества и технико экономические преимущества.

100. Зам. Начальника Главного управленияокеавдидафди и /Навигации МО РФ1. Г?:1. Ч- -с,