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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

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

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

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

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

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

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

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

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

Дипломник

студент группы 10-19-2.......................................................Е.В. Балобанова

Руководитель

вед. инженер кафедры ПО.................................................. Л.Н. Левицкая

Консультант по экономической части

к.э.н., доцент.........................................................................И.И. Радыгина

Консультант по безопасности

и экологичности....................................................................Г.Ф. Якименко

Нормоконтроль.......................................................................В.П. Соболева

Рецензент

вед. Инженер АО «Аксион».................................................. В.Н. Захаров

Заведующий кафедрой

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

д.т.н., профессор....................................................................А.И. Мурынов

ИЖЕВСК 2006

РЕФЕРАТ

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

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

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

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

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

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

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

СОДЕРЖАНИЕ

• ВВЕДЕНИЕ
• 1. РАЗРАБОТКА СИСТЕМЫ АВТОМАТИЗИРОВАННОГО АНАЛИЗА ПРОСТРАНСТВЕННОЙ СТРУКТУРЫ ИЗОБРАЖЕНИЙ
• 1.1. Обоснование целесообразности разработки системы автоматизированного анализа пространственной структуры изображений
• 1.1.2. Характеристика функциональной структуры системы
• 1.1.3. Обоснование цели создания системы
• 1.1.4. Обоснование состава автоматизируемых задач
• 1.2. Аналитический обзор
• 1.3. Основные требования к системе
• 1.3.1. Основные цели создания системы и критерии эффективности ее функционирования
• 1.3.2. Функциональное назначение системы
• 1.3.3. Особенности системы и условия ее эксплуатации
• 1.3.4. Требования к функциональной структуре
• 1.3.5. Требования к техническому обеспечению
• 1.3.6. Требования к информационному обеспечению
• 1.3.7. Требования к программному обеспечению
• 1.4. Основные технические решения проекта системы
• 1.4.1. Решение по комплексу технических средств
• 1.4.2. Описание системы программного обеспечения
• 2. РАЗРАБОТКА ЗАДАЧИ «ПОДСИСТЕМА ЦЕНТРОИДНОЙ РЕЛАКСАЦИИ»
• 2.1. Описание постановки задачи
• 2.1.1. Характеристика задачи
• 2.1.2. Входная информация
• 2.1.3. Выходная информация
• 2.1.4. Математическая постановка задачи
• 2.2. Описание алгоритма построения кольцевого фильтра
• 2.2.1. Назначение и характеристика алгоритма
• 2.2.2. Используемая информация
• 2.2.3. Результаты решения
• 2.2.4. Алгоритм решения
• 2.2.5. Список условных обозначений
• 2.3. Описание алгоритма вычисления центра масс
• 2.3.1. Назначение и характеристика алгоритма
• 2.3.2. Алгоритм решения
• 2.3.3. Список условных обозначений
• 2.4. Описание алгоритма вычисления кривизны
• 2.4.1. Назначение и характеристика алгоритма
• 2.4.2. Алгоритм решения
• 2.4.3. Список условных обозначений
• 2.5. Описание алгоритма обработки изображения
• 2.5.1. Назначение и характеристика алгоритма
• 2.5.2. Алгоритм решения
• 2.5.3. Список условных обозначений
• 2.6. Описание программы «Центроидная релаксация»
• 2.6.1. Вводная часть
• 2.6.2. Функциональное назначение
• 2.6.3. Описание информации
• 2.6.4. Используемые подпрограммы
• 2.6.5. Описание логики
• 2.7. Описание контрольного примера
• 2.7.1. Назначение
• 2.7.2. Исходные данные
• 2.7.3. Результаты расчета
• 2.7.4. Результаты испытания
• 3. ОРГАНИЗАЦИОННО-ЭКОНОМИЧЕСКАЯ ЧАСТЬ
• 3.1. Обоснование необходимости разработки подсистемы центроидной релаксации
• 3.2. Планирование разработки
• 3.3. Расчет расходов на создание системы
• 4. БЕЗОПАСНОСТЬ И ЭКОЛОГИЧНОСТЬ ПРОЕКТА
• 4.1. Анализ вредных и опасных производственных факторов
• 4.2. Техника безопасности при работе с компьютером
• 4.3. Электробезопасность при работе с компьютером
• 4.4. Требования к освещению рабочего места и его расчет
• 4.4.1. Требования к освещению рабочего места
• 4.4.2. Расчет освещенности рабочего места
• 4.5. Параметры микроклимата, загрязнение воздуха рабочей зоны вредными веществами
• 4.6. Пожаробезопасность при работе с компьютером
• ЗАКЛЮЧЕНИЕ
• СПИСОК ЛИТЕРАТУРЫ
• ПРИЛОЖЕНИЕ 1 ТЕКСТ ПРОГРАММЫ
• ПРИЛОЖЕНИЕ 2 РЕЗУЛЬТАТЫ РАБОТЫ ПРОГАММЫ
• ПРИЛОЖЕНИЕ 3 РУКОВОДСТВО ПРОГРАММИСТА
• ПРИЛОЖЕНИЕ 4 РУКОВОДСТВО ОПЕРАТОРА

ПЕРЕЧЕНЬ УСЛОВНЫХ ОБОЗНАЧЕНИЙ, СОКРАЩЕНИЙ, СИМВОЛОВ И СПЕЦИАЛЬНЫХ ТЕРМИНОВ С ИХ ОПРЕДЕЛЕНИЯМИ

ААПСИ - автоматизированный анализ пространственной структуры изображений

ОС - операционная система

ЭВМ - электронно-вычислительная машина

ПО - программное обеспечение

ВВЕДЕНИЕ

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

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

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

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

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

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

Цифровая графическая информация имеет две формы представления:

- растровая;

- векторная.

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

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

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

– искажение тоновых и цветовых шкал носителя изображения;

– пространственно-частотные искажения;

– шумы и помехи носителя изображения;

– собственные искажения процессов цифровой регистрации изображений.

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

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

ѕ в векторном формате - заданы координаты начала и конца прямой, цвет и толщина;

ѕ в растровом формате - заданы координаты каждой точки прямой, входящей в этот отрезок, и ее цвет.

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

ѕ изменение масштаба без потери качества и практически без увеличения размеров исходного файла;

ѕ огромная точность (до сотой доли микрона);

ѕ небольшой размер файла по сравнению с растровыми изображениями;

ѕ прекрасное качество печати;

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

ѕ возможность редактирования каждого элемента изображения в отдельности.

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

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

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

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

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

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

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

1.1.2. Характеристика функциональной структуры системы

Обработка изображений состоит из следующих этапов:

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

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

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

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

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

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

Функциональная схема системы приведена на рис. 1.1.

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

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

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

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

Рис. 1.1

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

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

Реализация системы ААПСИ позволит интегрировать в едином интерфейсе все этапы обработки изображений:

1) создание, изменение, выбор фильтра для сканирования изображения;

2) фильтрация изображения и выделение осевых линий посредством обработки центроидным фильтром;

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

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

5) эффективное представление сегментов линий и непрерывных кривых посредством цепного кодирования;

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

1.2. Аналитический обзор

Как уже было указано во введении, модели представления изображений в ЭВМ можно разделить на два типа: растровые и векторные. Работа с растровыми и векторными моделями изображений реализована во многих программных продуктах.

Microsoft Paint

Простейший редактор растровых изображений, входящий в состав стандартной поставки ОС Microsoft Windows. Основные возможности:

– проведение прямых и кривых линий различной толщины и цвета;

– использование кистей различной формы, ширины и цвета;

– построение различных фигур: прямоугольников, многоугольников, овалов, эллипсов - закрашенных и не закрашенных;

– помещение текста на рисунок;

– использование преобразований: поворотов, отражений, растяжений и наклона;

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

– Недостатки:

– отсутствуют средства по улучшению качества изображения, подавлению шумов;

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

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

Adobe Photoshop

Профессиональный редактор растровых изображений. Основные возможности:

– контроль цвета и тона компонент изображения: возможность подбора палитры, замены цветов, поддержка 32-битного цвета (прозрачности), возможность построения гистограмм распределения цвета;

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

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

– возможность создания многих независимых слоев в одном изображении.

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

Corel Draw

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

– объектность и структурность, свойственные векторной модели, позволяют добиться большого удобства при создании и изменении изображений;

– поддержка импорта и экспорта в большое количество форматов, в том числе и преобразования в растр;

– возможность рисования линий, фигур, текста.

Недостатки:

– невозможность импорта растровых изображений, полученных сканометрически;

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

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

Consistance Software Spotlight

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

– изображение состоит из растра, на который наложены структурные элементы, это позволяет редактировать растровые изображения так же легко, как и векторные;

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

– возможность работы с цветными и монохромными входными растрами, наличие инструментов и фильтров, улучшающих изображение;

– инструменты автокоррекции векторных структур.

Среди недостатков программного продукта можно упомянуть:

– недостаточная эффективность фильтров, производящих редукцию цвета (уменьшение количества цветов);

– недостаточная эффективность инструментов по разделению цветов (уменьшение цветовых компонент до одной тоно-цветовой шкалы)/13/.

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

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

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

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

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

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

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

1.3. Основные требования к системе

1.3.1. Основные цели создания системы и критерии эффективности ее функционирования

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

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

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

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

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

– фильтрация изображения от шумов и различных искажений;

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

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

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

– кодирование структурных элементов изображения цепным и дифференциальным цепным кодом;

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

– визуализация полученных результатов работы с возможностью их сохранения.

1.3.3. Особенности системы и условия ее эксплуатации

Система ААПСИ предназначена для работы с цифровыми монохромными изображениями, полученными посредством сканирования или растровых редакторов. Для получения приемлемого качества при сканировании необходимо разрешение сканера минимум 600 dpi (точек на дюйм). Полученные таким образом изображения имеют размер порядка нескольких мегапикселей и должны сохраняться в формате без сжатия, чтобы избежать искажений. Изображение должно быть в формате GreyScale (цвета от белого до черного, промежуточные - оттенки серого). Таким образом, объем графической информации, обрабатываемый системой, достаточно велик и составляет десятки мегабайт. Эти особенности накладывают ограничения на использование непроизводительных и медленных алгоритмов.

1.3.4. Требования к функциональной структуре

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

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

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

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

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

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

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

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

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

Таблица 1.1

Технические характеристики персонального компьютера

Наименование	Значение
Частота процессора, МГц	от 900
Объем оперативной памяти, Мб	от 128
Разрешение экрана монитора	не менее 1024x768

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

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

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

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

Систему ААПСИ целесообразно разрабатывать для функционирования под операционной системой семейства Windows, так как ОС данного класса наиболее широко распространены в современном мире. Платформами для разработки выбраны среды Borland C++ Builder 6 и Microsoft Visual C++. Эти среды поддерживают алгоритмический язык C++ и обладают при этом возможностями быстрой разработки и проектирования визуальных интерфейсов, что особенно важно при работе с графической информацией.

1.4. Основные технические решения проекта системы

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

Как уже отмечалось в п. 1.3.5 «Требования к техническому обеспечению», для достижения удобного пользователю режима функционирования системы необходимо следующая минимальная конфигурация персонального компьютера: частота процессора 900 МГц, объем оперативной памяти 128 Мб, монитор, поддерживающий разрешение 1024x768 точек. Также желательно наличие следующих периферийных технических средств: планшетный сканер с разрешающей способностью не менее 600x600 dpi (точек на дюйм), цветной струйный принтер для вывода на печать результатов обработки изображений.

1.4.2. Описание системы программного обеспечения

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

Разработка системы ААПСИ и ее подсистем будет вестись с использованием сред для разработки приложений Borland C++ Builder 6 и Microsoft Visual Studio C++. Среды разработки включают в себя высокопроизводительный 32-битный компилятор, что позволяет оптимизировать создаваемый код. В состав каждой среды включен обширный набор средств, которые повышают производительность труда программистов и сокращают продолжительность цикла разработки. Удобство разработки и эффективность созданных в данных средах разработки программ делают их оптимальным выбором для построения исследовательской системы, какой является система ААПСИ.

2. РАЗРАБОТКА ЗАДАЧИ «ПОДСИСТЕМА ЦЕНТРОИДНОЙ РЕЛАКСАЦИИ»

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

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

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

Задача включает в себя следующие подзадачи:

– построение фильтра для исследования изображения;

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

– вычисление кривизны структурных элементов;

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

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

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

Формат входного файла приведен в приложении 3.

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

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

Формат выходного файла описан в приложении 3.

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

Математическое описание построения кольцевого фильтра

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

Алгоритм вычисления точек кольцевого фильтра основан на соотношении сторон прямоугольного треугольника.

Рис. 2.1

Исходя из рисунка, точка P(x,y) - является точкой фильтра, если выполняется следующее условие:

(2.1)

Математическое описание вычисления центра масс

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

, (2.2)

где N - количество пикселов в фильтре,

p(i, j) - “вес” пиксела.

Рассчитываются вес пикселей по оси Ox:

, (2.3)

и вес по оси Oy:

, (2.4)

Смещение по оси Оx к центру “тяжести” пикселей, относительно текущей точки:

, (2.5)

Смещение по оси Оy к центру “тяжести” пикселей, относительно текущей точки:

, (2.6)

Координаты центра тяжести P(i, j):

, (2.7)

, (2.8)

где u,v - координаты центра фильтра.

Математическое описание алгоритма вычисления кривизны

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

Вычисление кривизны

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

C_f - центр фильтра; P₁,P₂ - точки линии, попавшие в фильтр;

r - радиус фильтра; h - смещение центра масс от центра фильтра;

l - расстояние от центра масс до точки пересечения линии рисунка и фильтра; M - центр масс; О - центр окружности на изображении;

R - радиус окружности на изображении;

Рис.2.2

Рассмотрим треугольник ДС_fMP₂ .Из соотношения гипотенузы и катетов в прямоугольных треугольниках, следует:

(2.9)

Из прямоугольного треугольника ДOMP₂ следует:

(2.10)

Из (2.9) выразим l² , получим:

(2.11)

Подставив в (2.10), получим:

(2.12)

Раскроем скобки:

(2.13)

Для получения h, сделаем несколько преобразований:

, (2.14)

, (2.15)

, (2.16)

Нормируем h по r :

(2.17)

Дифференцируем (2.17) по r /10/ :

(2.18)

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

Окружность. При обработке фильтрами различных радиусов (рис 2.3), кривизна остается постоянной (рис.2.4), т.к. радиус окружности - величина постоянная.

Окружность
a) обработка фильтром большого радиуса;	б) обработка фильтром маленького радиуса;
Рис.2.3

График зависимости кривизны от радиуса фильтра для окружности

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рис.2.4

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

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

Кривая
a) обработка фильтром большого радиуса;	б) обработка фильтром маленького радиуса;
Рис.2.5

График зависимости кривизны от радиуса фильтра для кривой

Рис.2.6

Угол
a) обработка фильтром большого радиуса;	б) обработка фильтром маленького радиуса;
Рис.2.7

График зависимости кривизны от радиуса фильтра для угла

Рис.2.8

2.2. Описание алгоритма построения кольцевого фильтра

2.2.1. Назначение и характеристика алгоритма

Алгоритм описывает метод вычисления координат кольцевого фильтра. Математическое описание алгоритма приведено в подразделе 2.1.4.

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

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

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

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

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

1. i=-MASK_SIZE;

2. j=MASK_SIZE;

3. s=sqrt(i*i+j*j);

4. Если ((s<=outsideR)&&(s>=insideR)), то к.п.5, иначе переход к п.7

5. FltArr[FltArr_index].x=i;

6. FltArr[FltArr_index++].y=j;

7. j--;

8. Если j>=-MASK_SIZE, то переход к п.3

9. i++;

10. Если i<=MASK_SIZE, то переход к п.2

11. Конец

2.2.5. Список условных обозначений

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

Таблица 2.1

Список условных обозначений

Обозначение	Расшифровка
MASK_SIZE	Радиус максимального фильтра в пикселях
i, j	Координаты текущего пиксела
FltArr	Массив координат
FltArr_index	Индекс текущего элемента в массиве FltArr
s	Расстояние от центра фильтра до текущего пиксела

2.3. Описание алгоритма вычисления центра масс

2.3.1. Назначение и характеристика алгоритма

Алгоритм описывает процесс вычисления центра масс относительно центра фильтра. Математическое описание алгоритма приведено в подразделе 2.1.4. В результате решения алгоритма вычисляются координаты центра масс.

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

1. M=0,Wx=0,Wy=0;

2. Cx=0,Cy=0; k=0;

3. Если (k>=FltArr_index), то переход к п.8

4. M=M+ImArr[CF.x+FltArr[k].x][CF.y+FltArr[k].y:

5. Wx=Wx+

+(CF.x+FltArr[k].x)*ImArr[CF.x+FltArr[k].x][CF.y+FltArr[k].y];

6. Wy=Wy+

+(CF.y+FltArr[k].y)*ImArr[CF.x+FltArr[k].x][CF.y+FltArr[k].y];

7. k++; переход к п.3

8. M=M/255;

9. Wx=Wx/255;

10. Wy=Wy/255;

11. Если (M==0), то переход к п.14

12. Cx=Wx/M;

13. Cy=Wy/M;

14. Конец

2.3.3. Список условных обозначений

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

Таблица 2.2

Список условных обозначений

Обозначение	Расшифровка
M	Общая масса пикселей попавших в фильтр
Wx, Wy	Вес пикселей по осям Ox и Oy соответственно.
FltArr_index	Количество точек фильтра
k	Порядковый номер точки фильтра
FltArr	Массив координат точек фильтра
ImArr	Массив исходного изображения
CF	Точка, относительно которой вычисляется центр масс
Cx, Cy	Координаты центра масс

2.4. Описание алгоритма вычисления кривизны

2.4.1. Назначение и характеристика алгоритма

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

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

1. Если (CF.mass==0), то к п.2, иначе переход к п.3

2. С= 140; переход к п.6

3. P=CentrMass(CF);

4. h=sqrt( (P.x-CF.x)^2 + (P.y-CF.y)^2 );

5. C=(h / insideR^2+0.005)*100;

6. Конец;

2.4.3. Список условных обозначений

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

Таблица 2.3

Список условных обозначений

Обозначение	Расшифровка
CF	Центр фильтра ( поле mass - масса пиксела, x,y - соответственно, координаты)
С	Кривизна
CentrMass	Функция, вычисляющая центр масс
P	Центр масс
h	Смещение центра масс от центра фильтра
insideR	Внутренний радиус кольца
sqrt	Функция, вычисляющая корень квадратный
^	Операция возведения в степень

2.5. Описание алгоритма обработки изображения

2.5.1. Назначение и характеристика алгоритма

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

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

1. Name = FormNewFileName(OpenDialog1->FileName);

2. outIm=fopen(Name,"wb");

3. fwrite(&Width,sizeof(Width),1, outIm);

4. fwrite(&Height,sizeof(Height),1, outIm);

5. RingFiltrPoint(insideR,outsideR);

6. i=outsideR;

7. j=outsideR;

8. CrArr[i][j]=CentroidRelax(i,j,insideR,outsideR);

9. j++;

10. Если j<Height-outsideR, то переход к п. 8

11. i++;

12. Если i< Width-outsideR, то переход к п. 7

13. i=0;

14. j=0;

15. fwrite(&CrArr[i][j],sizeof(CrArr[i][j]),1, outIm);

16. j++;

17. Если j<Height, то переход к п. 15

18. i++;

19. Если i<Width, то переход к п. 14

20. fclose(outIm);

21. Конец;

2.5.3. Список условных обозначений

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

Таблица 2.4

Список условных обозначений

Обозначение	Расшифровка
outIm	Выходной файловый поток
Name	Имя выходного файла
FormNewFileName	Функция, формирующая новое имя выходного файла
OpenDialog1-> FileName	Имя файла, открытого с помощью диалога “Открыть”
fopen	Функция открытия файла
outsideR	Внешний радиус кольца
insideR	Внутренний радиус кольца
RingFiltrPoint	Функция вычисления точек фильтра
Обозначение	Расшифровка
CrArr	Массив кривизны линий
CentroidRelax	Функция вычисления кривизны
fwrite	Функция записи в файл
sizeof	Функция вычисления размера переменной
fclose	Функция закрытия файла

2.6. Описание программы «Центроидная релаксация»

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

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

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

Программа имеет обозначение Relax, разработана в среде программирования Borland C++ Builder 6.0.

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

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

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

– процессор Intel Pentium 900 MHz;

– подсистема «Центроидная релаксация» занимает около 15 Мб оперативной памяти. Оболочка системы ААПСИ занимает около 5 Мб оперативной памяти. Дополнительно к этому и оболочка и программа выделяют память под рабочее изображение. Таким образом, оболочка использует дополнительную память, соответствующую размерам изображения, а программа использует память, соответствующую двум размерам изображения;

– для размещения ОС Windows XP и прикладных задач на жестком диске необходимо минимально 1,5 Гб свободного пространства. Система ААПСИ занимает около 10 Мб на жестком диске. Программа занимает около 1 Мб на жестком диске. Дополнительное место на диске занимают файлы изображений используемых программой, а также файлы создаваемые программой. С учетом этого на диске необходимо выделить достаточное пространство для всех файлов (от 100 Мб и выше);

– видеоподсистема с объемом памяти 32 Мб;

– цветной SVGA монитор с диагональю не менее 15'' и разрешением не ниже 800x600 (рекомендуется 1024x768);

– русифицированная клавиатура;

– манипулятор «мышь».

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

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

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

– Width - ширина исходного изображения;

– Height - ширина исходного изображения;

– ImArr - исходное изображение подготовленное для дальнейшей обработки;

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

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

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

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

– RingFiltrPoint - вычисление точек кольцевого фильтра;

– CenrMass - определение центра масс;

– CentroidRelax - расчет кривизны структурного элемента;

– Imaging - обработка входного изображения;

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

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

Описание логики программы «Центроидная релаксация» приведено на рис. 2.9.

Логика программы «Центроидная релаксация»

Рис. 2.9

2.7. Описание контрольного примера

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

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

2.7.2. Исходные данные

В качестве исходных данных использовался файл изображения, приведенный на рис. П.2.7.

2.7.3. Результаты расчета

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

2.7.4. Результаты испытания

В результате обработки данных контрольного примера получены изображения, представленные на рис. П.2.8 - П.2.26. Результаты полностью соответствуют ожиданиям. Программа справляется с решением задачи «Центроидной релаксации».

3. ОРГАНИЗАЦИОННО-ЭКОНОМИЧЕСКАЯ ЧАСТЬ

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

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

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

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

- уменьшение занимаемого объема памяти машины.

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

3.2. Планирование разработки

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

Расчет трудоемкости разработки задачи приведен в табл.3.1.

Таблица 3.1

Расчет трудоемкости разработки задачи

Наименование этапа разработки	Исполнители	Трудоемкость работ, чел-ч
	Должность	Кол-во
1. Изучение постановки задачи и методов решения	инженер-программист	1	84
2. Разработка алгоритмов	инженер-программист	1	168
3. Реализация и отладка алгоритмов	инженер-программист	1	168
4. Документирование системы	инженер-программист	1	84
ИТОГО		1	504

3.3. Расчет расходов на создание системы

Для определения величины расходов на создание системы, используем метод прямого счета. Расчет расходов осуществляется по следующим статьям: