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

2

Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

«ИЖЕВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Факультет «Информатика и вычислительная техника»

Кафедра «Программное обеспечение»

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к дипломной работе на тему:

«Система автоматизированного анализа пространственной структуры изображений. Подсистема линейной сегментации»

Дипломник студент группы 10-19-2	Ю.Н. Данилов
Руководитель ведущий инженер кафедры «Программное обеспечение»	Л.Н. Левицкая
Консультант по экономической части к.э.н., доцент	И.И. Радыгина
Консультант по безопасности и экологичности к.б.н., доцент	Г.Ф. Якименко
Нормоконтроль	В.П. Соболева
Рецензент ведущий инженер АО «Аксион»	В.Н. Захаров
Заведующий кафедрой «Программное обеспечение» д.т.н., профессор	А.И. Мурынов

Ижевск 2006

РЕФЕРАТ

Пояснительная записка к дипломной работе на тему «Система автоматизированного анализа пространственной структуры изображений. Подсистема линейной сегментации» оформлена на 119 листах, содержит 34 рисунка, 10 таблиц.

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

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

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

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

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

Система реализована для персональных электронно-вычислительных машин, работающих под управлением Microsoft Windows 98/Me/2000/XP/NT и выше, не требует установки дополнительных инструментов и не требовательна к системным ресурсам.

СОДЕРЖАНИЕ

• ВВЕДЕНИЕ 7
• 1. РАЗРАБОТКА «ПОДСИСТЕМЫ ЛИНЕЙНОЙ СЕГМЕНТАЦИИ» В СОСТАВЕ «СИСТЕМЫ АВТОМАТИЗИРОВАННОГО АНАЛИЗА ПРОСТРАНСТВЕННОЙ СТРУКТУРЫ ИЗОБРАЖЕНИЙ» 9
• 1.1. Обоснование целесообразности разработки системы 9
• 1.1.1. Назначение системы 9
• 1.1.2. Обоснование цели создания системы 10
• 1.1.3. Назначение «Подсистемы линейной сегментации» 11
• 1.1.4. Характеристика организационной и функциональной структуры 11
• 1.1.5. Обоснование состава автоматизируемых задач 11
• 1.1.6. Обоснование применения типовых и оригинальных решений 12
• 1.1.7. Общая оценка экономической целесообразности создания подсистемы 13
• 1.2. Основные требования к «Подсистеме линейной сегментации» 13
• 1.2.1. Основные цели создания подсистемы 13
• 1.2.2. Функциональное назначение подсистемы 14
• 1.2.3. Требования к функциональной структуре подсистемы 14
• 1.2.4. Требования к техническому обеспечению 15
• 1.2.5. Требования к информационному обеспечению 15
• 1.2.6. Требования к программному обеспечению 16
• 1.3. Основные технические решения проекта подсистемы «Линейная сегментация» 16
• 1.3.1. Решения по комплексу технических средств 16
• 1.3.2. Описание организации информационной базы 17
• 2. РАЗРАБОТКА ЗАДАЧИ «ПОИСК УЗЛОВ» 19
• 2.1. Описание постановки задачи 19
• 2.1.1. Характеристика задачи 19
• 2.1.2. Входная информация 19
• 2.1.3. Выходная информация 19
• 2.1.4. Математическая постановка задачи 20
• 2.1.5. Специальные требования к техническому обеспечению 23
• 2.2. Описание алгоритма «Поиск узлов» 23
• 2.2.1. Назначение и характеристика 23
• 2.2.2. Используемая информация 24
• 2.2.3. Результаты решения 24
• 2.2.4. Алгоритм решения 24
• 2.2.6. Условные обозначения 25
• 2.3. Описание программы «Поиск узлов» 26
• 2.3.1. Вводная часть 26
• 2.3.2. Функциональное назначение 26
• 2.3.3. Описание информации 27
• 2.3.4. Используемые подпрограммы 27
• 2.3.5. Описание логики 27
• 2.3.6. Настройка программных средств 28
• 3. РАЗРАБОТКА ЗАДАЧИ «ПОИСК СЕГМЕНТОВ» 30
• 3.1. Описание постановки задачи 30
• 3.1.1. Характеристика задачи 30
• 3.1.2. Входная информация 31
• 3.1.3. Выходная информация 31
• 3.1.4. Математическая постановка задачи 31
• 3.1.5. Специальные требования к техническому обеспечению 34
• 3.2. Описание алгоритма «Поиск сегментов» 34
• 3.2.1. Назначение и характеристика 34
• 3.2.2. Используемая информация 35
• 3.2.3. Результаты решения 35
• 3.2.4. Алгоритм решения 35
• 3.2.5. Требования к контрольному примеру 36
• 3.2.6. Условные обозначения 36
• 3.3. Описание программы «Поиск сегментов» 37
• 3.3.1. Вводная часть 37
• 3.3.2. Функционально назначение 37
• 3.3.3. Описание информации 37
• 3.3.4. Используемые подпрограммы 38
• 3.3.5. Описание логики 38
• 3.3.6. Настройка программных средств 38
• 4. РАЗРАБОТКА ЗАДАЧИ «ОБРАБОТКА И КОДИРОВАНИЕ СЕГМЕНТОВ» 40
• 4.1. Описание постановки задачи 40
• 4.1.1. Характеристика задачи 40
• 4.1.2. Входная информация 40
• 4.1.3. Выходная информация 40
• 4.1.4. Математическая постановка задачи 41
• 4.1.5. Специальные требования к техническому обеспечению 42
• 4.2. Описание алгоритма «Обработка и кодирование сегментов» 42
• 4.2.1. Назначение и характеристика 42
• 4.2.2. Используемая информация 42
• 4.2.3. Результаты решения 43
• 4.2.4. Алгоритм решения 43
• 4.2.5. Требования к контрольному примеру 44
• 4.2.6. Список условных обозначений 44
• 4.3. Описание программы «Обработка и кодирование сегментов» 45
• 4.3.1. Вводная часть 45
• 4.3.2. Функциональное назначение 45
• 4.3.3. Описание информации 45
• 4.3.4. Используемые подпрограммы 46
• 4.3.5. Описание логики 47
• 4.3.6. Настройка программных средств 48
• 4.4. Описание контрольного примера 48
• 4.4.1. Назначение 48
• 4.4.2. Исходные данные 49
• 4.4.3. Результаты расчета 51
• 4.4.4. Результаты испытания программы 54
• 5. ОРГАНИЗАЦИОННО-ЭКОНОМИЧЕСКАЯ ЧАСТЬ 56
• 5.1. Расчет затрат на разработку «Подсистемы линейной сегментации» 56
• 6. ЭКОЛОГИЧНОСТЬ И БЕЗОПАСНОСТЬ ПРОЕКТА 61
• 6.1. Актуальность безопасности труда 61
• 6.2. Анализ опасных и вредных производственных факторов 62
• 6.3. Техника безопасности при работе с компьютером 64
• 6.4. Организация рабочего места оператора 68
• 6.5. Расчет защитного заземления 69
• 6.6. Требования к параметрам микроклимата 73
• 6.7. Пожаробезопасность 73
• 6.8. Выводы 74
• ЗАКЛЮЧЕНИЕ 75
• СПИСОК ЛИТЕРАТУРЫ 77
• ПРИЛОЖЕНИЕ 1 РУКОВОДСТВО ПРОГРАММИСТА 79
• ПРИЛОЖЕНИЕ 2 РУКОВОДСТВО ОПЕРАТОРА 85
• ПРИЛОЖЕНИЕ 3 ТЕКСТ ПРОГРАММЫ 96

ВВЕДЕНИЕ

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

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

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

1. РАЗРАБОТКА «ПОДСИСТЕМЫ ЛИНЕЙНОЙ СЕГМЕНТАЦИИ» В СОСТАВЕ «СИСТЕМЫ АВТОМАТИЗИРОВАННОГО АНАЛИЗА ПРОСТРАНСТВЕННОЙ СТРУКТУРЫ ИЗОБРАЖЕНИЙ»

1.1. Обоснование целесообразности разработки системы

1.1.1. Назначение системы

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

Структурная схема системы автоматизированного анализа

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

Рис. 1.1

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

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

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

- подсистема цепного кодирования, позволяющая в дифференциальном кодированном виде представить линии;

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

1.1.2. Обоснование цели создания системы

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

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

- значительное уменьшение объемов хранимой информации;

- увеличение скорости и качества синтеза изображений;

- аккумуляция информации с целью последующего использования.

1.1.3. Назначение «Подсистемы линейной сегментации»

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

1.1.4. Характеристика организационной и функциональной структуры

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

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

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

Структурная схема подсистемы линейной сегментации

Рис. 1.2

1.1.6. Обоснование применения типовых и оригинальных решений

В качестве технического обеспечения рабочей станции используется IBM-совместимый персональный компьютер, оснащенный русифицированной клавиатурой, манипулятором типа «мышь», монитором, накопителями на жестком диске. Данный состав технических средств был выбран исходя из их доступности и достаточно высокой надежности при оптимальных ценах. В качестве целевой операционной системы выбрана платформа Windows 2000/XP, являющаяся на данный момент наиболее широко распространенной платформой общего назначения. Средством разработки выбрана система C++ Builder 6 фирмы Borland. Выбор этого языка обусловлен наличием развитой среды программирования и отладки, его высокой эффективностью создания рабочих приложений, и легкостью создания пользовательского интерфейса приложения.

1.1.7. Общая оценка экономической целесообразности создания подсистемы

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

Создание системы позволит изменить такие показатели, как:

- объем хранимой информации;

- скорость передачи информации;

- скорость синтеза изображений;

- объем знаний о графических изображениях;

- актуальность получения графической информации;

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

1.2. Основные требования к «Подсистеме линейной сегментации»

1.2.1. Основные цели создания подсистемы

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

1.2.2. Функциональное назначение подсистемы

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

- получение изображения из различных источников;

- первичная обработка изображения при необходимости;

- поиск узловых элементов изображения;

- поиск линейных сегментов;

- поиск принадлежности точек изображения узлам и сегментам линий;

- вывод координат распознанных сегментов линий;

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

1.2.3. Требования к функциональной структуре подсистемы

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

1.2.4. Требования к техническому обеспечению

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

- персональный компьютер IBM PC с процессором не ниже Pentium I;

- клавиатура;

- монитор;

- жесткий диск с объемом свободного пространства не менее 50 МБ;

- оперативная память объемом не менее 128 МБ.

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

- сохранение работоспособности подсистемы при неправильной работе других подсистем;

- дублирование информации;

- проверка вводимых данных на корректность.

1.2.5. Требования к информационному обеспечению

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

- характеристики обрабатываемого изображения;

- взаимные связи всех характеристик в процессе решения;

- процедуры обработки описаний структурных элементов;

- формы обмена данными для согласования работы подсистем.

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

Следовательно, должны обеспечиваться:

- многократное использование данных;

- формализация процедур для машинной обработки данных;

- установка четкой последовательности обработки данных;

- правильное использование накопленной информации.

1.2.6. Требования к программному обеспечению

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

- программы, реализующие задачи подсистемы, должны функционировать в среде операционной системы Microsoft Windows 98/Me/2000/XP/NT или выше;

- система должна быть автономной с точки зрения использования стороннего программного обеспечения;

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

1.3. Основные технические решения проекта подсистемы «Линейная сегментация»

1.3.1. Решения по комплексу технических средств

Комплекс технических средств подсистемы «Линейной сегментации» должен являться составной частью системы автоматизированного анализа пространственной структуры графических изображений и обеспечивать реализацию всех автоматизированных функций подсистемы (см. п. 1.2.2). Технические средства базируются на средствах обработки данных, на персональных ЭВМ и могут быть дополнены средствами ввода изображений (сканеры, планшеты рукописного ввода, цифровые фотокамеры) и вывода изображений (принтеры, плоттеры, графопостроители).

Планируемый комплекс технических средств для функционирования задач реализующих подсистему «Линейная сегментация» включает следующие технические средства:

- персональный компьютер IBM PC с процессором не ниже Pentium I;

- клавиатура;

- монитор;

- жесткий диск с объемом свободного пространства не менее 50 МБ;

- оперативная память объемом не менее 128 МБ.

1.3.2. Описание организации информационной базы

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

Формат входного массива точек

<M >

<N>

a₁₁,a₁₂,…,a_1m

a₂₁,a₂₂,…,a_2m

a_n1,a_n2,…,a_nm

где <M > - строка, содержащая число точек изображения по горизонтали;

<N > - строка, содержащая число точек изображения по вертикали;

a_ij - элемент массива точек, соответствующий точке изображения с координатами (i,j), может принимать значения «1» и «0».

Пример входных данных:

8

8

00000000

01000000

00100000

00010000

11111111

00000100

00000010

00000000

Соответствующее данному массиву изображение показано на рис. 1.3.

Соответствующее изображение 8х8

Рис. 1.3

Формат описания сегментов линий:

n₁:x₁₁,y₁₁ [,x₁₂,y₁₂ [,x₁₃,y₁₃]]

n₂:x₂₁,y₂₁ [,x₂₂,y₂₂ [,x₂₃,y₂₃]]

n_k:x_k1,y_k1 [,x_k2,y_k2 [,x_k3,y_k3]]

где n_i - номер i-го сегмента линии (идентификатор);

x_i1,y_i1 - координаты первой точки i-го сегмента линии;

x_i2,y_i2 - координаты второй точки i-го сегмента линии, указываются в том случае, если точка (x_i2,y_i2) является узлом;

x_i3,y_i3 - координаты направления кодирования от точки (x_i1,y_i1), указываются в том случае, если точки (x_i1,y_i1) и (x_i2,y_i2) являются узлами.

2. РАЗРАБОТКА ЗАДАЧИ «ПОИСК УЗЛОВ»

2.1. Описание постановки задачи

2.1.1. Характеристика задачи

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

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

2.1.2. Входная информация

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

2.1.3. Выходная информация

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

2.1.4. Математическая постановка задачи

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

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

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

- если значение равно нулю, то это означает, что данному элементу не соответствует ни один из узлов и, следовательно, соответствующая точка в массиве точек не является узлом;

- если значение больше нуля, то оно представляет собой номер узла, которому соответствует данная точка.

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

Линия единичной толщины

Рис. 2.1

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

(2.1)

где N - количество точек в линии;

x-_t, y-_t - координаты рассматриваемой точки a-_t;

K(x-_t, y-_t) - количество точек, соседних с a-_t.

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

(2.2)

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

x-_t, y-_t - координаты рассматриваемой точки a-_t;

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

Рис. 2.2

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

Это можно представить в виде формул:

(2.3)

где (x,y) - координаты рассматриваемой точки;

M и N - ширина и высота изображения;

B - массив узлов, размерность MxN;

n - номер обрабатываемого узла.

На рис. 2.3 приведен пример пересечения линий, где выделенные точки являются узловыми.

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

Пример пересечения линий

Рис. 2.3

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

Точки вокруг узла

Рис. 2.4

2.1.5. Специальные требования к техническому обеспечению

Требования к техническому обеспечению для решения задачи «Поиск узлов» полностью совпадают с требованиями к комплексу технических средств, предъявленными при разработке подсистемы «Линейная сегментация» (см. п. 1.3.1).

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

- персональный компьютер IBM PC с процессором не ниже Pentium I;

- клавиатура;

- монитор;

- жесткий диск с объемом свободного пространства не менее 50 МБ;

- оперативная память объемом не менее 128 МБ.

Работа программы возможна только на ЭВМ, которые поддерживают 32-разрядные операционные системы семейства Windows, такие как Windows 95, Windows NT или выше. Как указано выше, работа может вестись на ЭВМ с процессором не ниже Intel Pentium. Но желательно использовать ЭВМ с процессором не ниже класса Intel Pentium II, который работает более эффективно.

2.2. Описание алгоритма «Поиск узлов»

2.2.1. Назначение и характеристика

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

2.2.2. Используемая информация

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

2.2.3. Результаты решения

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

2.2.4. Алгоритм решения

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

1. Начало;

2. Инициализация массива узлов;

3. i=0; j=0; z=0;

4. Если j>=N, то переход к п.11;

5. Если i>=M, то переход к п.10;

6. Если (apix[i][j]=1)и(apix2[i][j]<0)и(NeigCount(i,j)>2), то переход к п.7, иначе к п.9;

7. z=z+1;

8. NodeSelect(i,j,z);

9. i=i+1; переход к п.5;

10. i=0; j=j+1; переход к п.4;

11. Конец.

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

2.2.6. Условные обозначения

В таблице 2.1 представлены условные обозначения, введенные в тексте подраздела

Таблица 2.1

Условные обозначения

Условные обозначения	Расшифровка
M	ширина входного изображения
N	высота входного изображения
apix[M][N]	исходный массив точек
apix2[M][N]	массив узлов
NeigCount	функция вычисления количества соседних точек
NodeSelect(x,y,n)	рекурсивная функция выделения узловых точек, x,y - координаты начала выделения, n - номер узла
Z	номер текущего узла

2.3. Описание программы «Поиск узлов»

2.3.1. Вводная часть

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

2.3.2. Функциональное назначение

Программа «Поиск узлов» предназначена выделения в составе обрабатываемого изображения элементов, представляющих собой области пересечения линий, называемые узлами. Программа работает с массивом точек, представляющих исходное изображение. В процессе ее выполнения происходит обход данного массива точек, с одновременным заполнением массива элементов узлов, расчетом координат узлов и подсчетом их количества. При этом в массиве узлов производится нумерация элементов, тем самым позволяя определять, какому из узлов принадлежит та или иная точка. Значения, полученные при поиске узлов, используются в дальнейшем при выполнении поиска сегментов линий, а также при кодировании линий и получении координат сегментов при генерации описания графического изображения. Программа рассчитана на работу в операционных системах семейства Windows, таких как Windows 9x, Windows NT или выше. Поэтому требования программы к памяти зависят от операционной системы. В этих операционных системах при выделении памяти используется файл подкачки Windows, в котором можно адресовать до 2 Гбайт виртуальной памяти. Но при обращении к диску скорость работы падает. Для Windows 95 оптимальный объем оперативной памяти 32 Мбайт, для Windows NT - 64 Мбайт. На винчестере программе достаточно иметь 100 Мбайт дискового пространства.

2.3.3. Описание информации

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

2.3.4. Используемые подпрограммы

В процессе работы программа обращается к следующим подпрограммам:

- wlog - подпрограмма вывода сообщений в журнал вычислений;

- NeigCount - подпрограмма получения количества соседних точек;

- NeigNode - подпрограмма рекурсивной обработки узловых точек;

- NodeCentre - подпрограмма вычисления центра узла;

- DrawGrid - подпрограмма вывода сетки изображения.

2.3.5. Описание логики

Схема программы AnalyzeNode представлена на рис. 2.5. Здесь представлено текстовое описание схемы проргаммы:

1. Начало;

2. Инициализация массива узлов;

3. i=0; j=0; z=0;

4. Если j>=N, то переход к п.11;

5. Если i>=M, то переход к п.10;

6. Если (apix[i][j]=1)и(apix2[i][j]<0)и(NeigCount(i,j)>2), то переход к п.7, иначе к п.9;

7. z=z+1;

8. NodeSelect(i,j,z);

9. i=i+1; переход к п.5;

10. i=0; j=j+1; переход к п.4;

11. Конец.

2.3.6. Настройка программных средств

Для работы программы необходимо наличие операционной системы Windows 95/Windows NT или более поздней версии. Для работы программы с данными, размещенными в сети, необходима настройка сетевых подключений операционной системы к рабочей группе.

Схема программы AnalyzeNode Рис. 2.5

3. РАЗРАБОТКА ЗАДАЧИ «ПОИСК СЕГМЕНТОВ»

3.1. Описание постановки задачи

3.1.1. Характеристика задачи

Задача «Поиск сегментов» предназначена для определения в составе обрабатываемого графического изображения сегментов линий, получаемых в результате пересечения последних. В процессе выполнения данной задачи осуществляется нахождение сегментов линий, позволяющее, основываясь на узлах, полученных в результате работы задачи «Поиск узлов» (ее характеристика приведена в пункте 2.1.1), выделить структурные элементы изображения. В результате выполнения задачи «Поиск сегментов» можно получать описание исходного графического изображения, подвергая его кодированию и/или последующей обработке, в том числе и в подсистемах синтеза графических изображений. Данная задача является основным звеном в цепи линейной сегментации обработки изображений, ее результаты позволяют наблюдать работу всей подсистемы в целом. В задаче можно выделить следующие основные части:

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

- поиск сегментов линий, одна из начальных точек которой является узлом, таким образом, сегмент является начальной (конечной) частью линии;

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

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

3.1.2. Входная информация

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

- массив точек исходного изображения;

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

3.1.3. Выходная информация

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

3.1.4. Математическая постановка задачи

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

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

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

- если значение равно нулю, то это означает, что данному элементу не соответствует ни одна из сегментов линий и, следовательно, соответствующая точка в массиве точек не является каким-либо сегментом линией;

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

Данные утверждения можно представить в виде формул:

(3.1)

где (x,y) - координаты рассматриваемой точки;

M и N - ширина и высота изображения;

C - массив сегментов, размерность MxN;

n - номер обрабатываемого сегмента.

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

Отдельные сегменты линий

Рис. 3.1

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

На рис. 3.2. выделенные точки отображают сегмент, одна из начальных точек которого является узлом.

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

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

Сегмент линии, содержащий начальную и узловую точки

Рис. 3.2

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

Рис. 3.3

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

3.1.5. Специальные требования к техническому обеспечению

Требования к техническому обеспечению для решения задачи «Поиск узлов» полностью совпадают с требованиями к комплексу технических средств, предъявленными при разработке подсистемы «Линейная сегментация» (см. п. 1.3.1).

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

- персональный компьютер IBM PC с процессором не ниже Pentium I;

- клавиатура;

- монитор;

- жесткий диск с объемом свободного пространства не менее 50 МБ;

- оперативная память объемом не менее 128 МБ.

Работа программы возможна только на ЭВМ, которые поддерживают 32-разрядные операционные системы семейства Windows, такие как Windows 95, Windows NT или выше. Как указано выше, работа может вестись на ЭВМ с процессором не ниже Intel Pentium. Но желательно использовать ЭВМ с процессором не ниже класса Intel Pentium II, который работает более эффективно.

3.2. Описание алгоритма «Поиск сегментов»

3.2.1. Назначение и характеристика

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

3.2.2. Используемая информация

При работе данного алгоритма используются следующие массивы:

- массив точек исходного изображения;

- массив узлов.

3.2.3. Результаты решения

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

3.2.4. Алгоритм решения

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

1. Начало;

2. Инициализация массива сегментов;

3. i=0; j=0; nsegs =0;

4. Если j>=N, то переход к п.11;

5. Если i>=M, то переход к п.10;

6. Если (apix[i][j]=1)и(apix1[i][j]<0)и((NeigCount(i,j)=1)или(NeigCount(i,j)=2)), то переход к п.7, иначе к п.9;

7. nsegs = nsegs +1;

8. NeigLine(i,j, nsegs);

9. i=i+1; переход к п.5;

10. i=0; j=j+1; переход к п.4;

11. Конец.

3.2.5. Требования к контрольному примеру

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

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

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

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

3.2.6. Условные обозначения

В таблице 3.1 представлены условные обозначения, введенные в тексте подраздела

Таблица 3.1

Условные обозначения

Условные обозначения	Расшифровка
M	ширина входного изображения
N	высота входного изображения
apix[M][N]	исходный массив точек
apix1[M][N]	массив сегментов
NeigCount	функция вычисления количества соседних точек
NeigLine(x,y,n)	рекурсивная функция выделения узловых точек, x,y - координаты начала выделения, n - номер узла
nsegs	номер текущего сегмента

3.3. Описание программы «Поиск сегментов»

3.3.1. Вводная часть

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

3.3.2. Функционально назначение

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

3.3.3. Описание информации

Программа AnalyzeSeg на входе использует следующие данные:

- массив точек;

- массив узлов;

На выходе программа формирует следующие данные:

- массив сегментов;

3.3.4. Используемые подпрограммы

В процессе работы программа обращается к следующим подпрограммам:

- wlog - подпрограмма вывода сообщений в журнал вычислений;

- NeigCount - подпрограмма получения количества соседних точек;

- NeigLine - подпрограмма рекурсивной обработки точек одного сегмента линии;

- DrawGrid - подпрограмма вывода сетки изображения.

3.3.5. Описание логики

Схема программы AnalyzeSeg представлена на рис. 3.4. Здесь представлено текстовое описание схема программы:

1. Начало;

2. Инициализация массива сегментов;

3. i=0; j=0; nsegs =0;

4. Если j>=N, то переход к п.11;

5. Если i>=M, то переход к п.10;

6. Если (apix[i][j]=1)и(apix1[i][j]<0)и((NeigCount(i,j)=1)или(NeigCount(i,j)=2)), то переход к п.7, иначе к п.9;

7. nsegs = nsegs +1;

8. NeigLine(i,j, nsegs);

9. i=i+1; переход к п.5;

10. i=0; j=j+1; переход к п.4;

11. Конец.

3.3.6. Настройка программных средств

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

Схема программы AnalyzeSeg

Рис. 3.4

4. РАЗРАБОТКА ЗАДАЧИ «ОБРАБОТКА И КОДИРОВАНИЕ СЕГМЕНТОВ»

4.1. Описание постановки задачи

4.1.1. Характеристика задачи

Задача «Обработка и кодирование сегментов» предназначена для формирования кода трех типов сегментов линий на основании найденных сегментов линий и узлов. В задаче обрабатываются следующие типы сегментов линий:

- сегменты линий, не содержащие узлов;

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

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

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