Содержание к диссертации
Введение
ГЛАВА 1. Аналитический обзор 10
1.1. Исходные положения 10
1.1.1. Понятие изображения 10
1.1.2. Активное восприятие 17
1.1.3. Пирамидальная обработка визуальной информации 18
1.2. Анализ состояния проблемы узнавания 22
1.2.1. Зрительное восприятие человека и машинное зрение 23
1.2.2. Проблема отыскания соответствия анализируемого и эталонных изображений 26
1.3. Основные положения теории активного восприятия 39
ГЛАВА 2. Информационная модель пирамидальной координатной системы в представлении на плоскость 52
2.1. Постановка задачи 52
2.2. Определение взаимного расположения объектов на разных уровнях разложения 53
2.3. Определение взаимного расположения объектов на одном уровне разложения 58
2.4. Выводы 60
ГЛАВА 3. Координатное совмещение эталонного и анализируемого изображений 61
3.1. Постановка задачи 61
3.1.1. Формальная модель преобразований на плоскости 61
3.2. Информационная модель компенсации параллельного переноса 64
3.3. Информационная модель компенсации поворота 67
3.3.1. Определение поворота на углы кратные 90 68
3.3.2. Грубое определение поворота на углы некратные 90 74
3.4. Информационная модель компенсации изменения масштаба 75
3.4.1. Зеркальное отражение 75
3.4.2. Деформации типа расширения и сжатия 82
3.5. Выводы 83
ГЛАВА 4. Информационная модель многоуровневой обработки на примере текста 85
4.1. Постановка задачи 85
4.2. Информационная модель уровня страницы текста при многоуровневой обработке изображений 85
4.3. Информационная модель выделения на странице текста строк и букв 94
4.4. Выводы 100
ГЛАВА 5. Практические применения разработанных моделей 102
5.1. Узнавание изображений на произвольных шумах 102
5.2. Формирование гипотез в процессе узнавания (неполный перебор эталонных образов) 119
5.3. Определение ориентации объекта изображения с заданной точностью на примере определения ориентации изображения микросхемы 123
5.4. Определение номеров на железнодорожных вагонах 131
5.5. Выводы 134
Заключение 135
Литература 137
Приложение
- Зрительное восприятие человека и машинное зрение
- Определение взаимного расположения объектов на разных уровнях разложения
- Информационная модель компенсации параллельного переноса
- Информационная модель уровня страницы текста при многоуровневой обработке изображений
Введение к работе
Актуальность темы
Одной из фундаментальных проблем современности является проблема зрительного восприятия. Возникнув очень давно, она является актуальной и в настоящее время, ибо изображение является естественным средством взаимодействия человека и окружающего его мира; изображение является естественным средством общения человека и машины в любых системах обработки, анализа и контроля.
Вопросы обработки, анализа и распознавания изображений получили фундаментальное развитие в работах научных коллективах Вычислительного центра РАН, Института проблем передачи информации РАН, Института систем обработки изображений РАН, Института прикладной математики и кибернетики при Нижегородском госуниверситете и др. Значительный вклад в решение проблемы распознавания изображений внесли М.А. Айзерман, Э.М. Браверман, В.Н. Вапник, Ю.Г. Васин, А.И. Галушкин, А.Л. Горелик, И.Б. Гуревич, Р. Дуда, Ю.И. Журавлев, Н.Г. Загоруйко, Д. Марр, М. Минский, Ю.И. Неймарк, С. Пейперт, К.В. Рудаков, Ф. Розенблатт, А. Розенфельд, В.А. Сойфер, Р. Фишер, К. Фу, П. Харт, М.И. Шлезингер и другие российские и зарубежные ученые.
Развитие современных средств компьютерной техники и информационных технологий способствует широкому внедрению в практику систем автоматической обработки изображений.
Одной из актуальных проблем, стоящей перед разработчиками таких систем является узнавание в анализируемом изображении или его части известных системе эталонных образов, особенно при высоком уровне шума в анализируемом изображении и в реальном масштабе времени. Именно неспособность успешно функционировать при наличии высокого уровня шума в анализируемых изображениях наиболее ограничивает возможность
использования существующих в настоящее время систем автоматической обработки изображений.
Другой актуальной проблемой является координатное описание анализируемой информации, под которым понимается соответствие систем координат различных уровней представления данных. В широком смысле координатное соответствие есть взаимно-однозначная связь объекта изображения на множестве уровней разложения на пирамиде описания и принятия решений. В узком смысле — соответствие объекта и его эталона на г-ом уровне разложения. Возникновение этой проблемы связано с необходимостью обработки изображений в условиях априорной неопределенности их системы координат. Несоответствие системы координат исходного изображения с системами координат эталонных образов, хранящихся в памяти, приводит к невозможности обработки таких изображений. Поэтому, в настоящее время актуально стоит задача совмещения систем координат исходного изображения и эталонных образов. Особенно остро эта задача стоит в случае необходимости работы системы в реальном масштабе времени, так как большинство существующих методов совмещения координатных систем при обработке изображений требуют значительных вычислительных затрат.
Цель работы
Целью данной работы является разработка информационной модели многоуровневой обработки изображений.
Задачи
Для достижения поставленной цели необходимо решить следующие задачи:
1. Решить задачу построения пирамидальной координатной системы в представлении на плоскость.
Разработать информационную модель определения взаимного расположения объектов на разных уровнях разложения с использованием пирамидальной координатной системы.
Разработать информационную модель определения взаимного расположения объектов на одном уровне разложения с использованием пирамидальной координатной системы.
Решить задачу установления координатного соответствия между различными изображениями через рассмотрение всех случаев изоморфных преобразований исходного изображения и выработать меры по их устранению с целью совмещения систем координат исходного и эталонного изображений.
Разработать информационную модель уровня страницы текста при многоуровневой обработке изображений: на примере уровня страницы текста рассмотреть модели определения расположения и ориентации страницы текста.
Разработать информационную модель уровня строк и букв при многоуровневой обработке изображений.
Методы исследования
Для решения поставленных задач в работе использованы методы распознавания образов, теории активного восприятия, системного анализа, математического моделирования, анализа и синтеза изображений, теории групп и теории вычислительных систем.
Научная новизна
Научная новизна работы состоит в следующем:
1. Решена задача построения пирамидальной координатной системы в представлении на плоскость.
Разработана информационная модель определения взаимного расположения объектов на разных уровнях разложения с использованием пирамидальной координатной системы.
Разработана информационная модель определения взаимного расположения объектов на одном уровне разложения с использованием пирамидальной координатной системы.
Решена задача установления координатного соответствия между различными изображениями на множестве изоморфных преобразований исходного изображения и выработаны меры по их устранению с целью совмещения систем координат исходного и эталонного изображений.
Разработана информационная модель уровня страницы текста и уровня строк и букв при многоуровневой обработке изображений.
Разработана информационная модель обработки изображений объектов при их частичном стирании.
Практическая ценность
Реализованы в виде программных модулей алгоритмы узнавания на произвольных шумах, формирования гипотез о результатах узнавания на ранних стадиях процесса узнавания, подавления искажений, возникающих ввиду воздействия на анализируемое изображение всех видов изоморфных преобразований, формирования гипотез в процессе узнавания частично стертых изображений объектов, анализа изображений, содержащих текстовую информацию. Проведена проверка разработанного программного комплекса на множестве изображений как реальных, в том числе искаженных, так и созданных специально для проведения исследования.
Результаты работы использованы проектах РФФИ №01-01-00452, №01-01-00459 и внедрены в учебный процессе Нижегородского государственного технического университета.
Полученные результаты подтверждают эффективность методов анализа и разработанных алгоритмов.
Апробация работы
Основные положения диссертационной работы были апробированы на 6 научных конференциях:
Научно-техническая конференция факультета информационных систем и технологий (Нижний Новгород, 1999);
Всероссийская научно-техническая конференция ИСТ-2001 (Нижний Новгород, 2001);
. Региональный молодежный научно-технический форум «Будущее технической науки Нижегородского региона» (Нижний Новгород, 2002);
Всероссийская научно-техническая конференция ИСТ-2002 (Нижний Новгород, 2002);
Всероссийская научно-техническая конференция ИСТ-2003 (Нижний Новгород, 2003);
II Региональная молодежная научно-техническая конференция «Будущее технической науки Нижегородского региона» (Нижний Новгород, 2003);
Публикации
По материалам диссертации опубликовано 11 научных работ [1-11], в том числе 5 статей.
Структура и объем диссертации
Основной текст диссертации состоит из введения, 5 глав, заключения, библиографического списка и приложения, содержит 147 страниц машинописного текста, 82 рисунка и 16 таблиц.
Список литературы включает в себя 130 наименований.
Зрительное восприятие человека и машинное зрение
Через зрительный канал в мозг человека поступает от 70 до 90% информации. Поэтому при создании систем, воспринимающих информацию извне, необходимо учитывать особенности зрительного восприятия человека. Основными функциями зрения человека являются: общая ориентировка в окружающей среде (оценивание размера и формы объектов в пространстве дальности до объектов, пространственных взаимоотношений объектов, обнаружение движущихся объектов и т. д.); узнавание объектов (идентификация знакомых объектов сопоставлением их с названиями метками); запоминание наблюдаемых сцен (кратковременная и долговременная зрительная или образная память); обучение и получение новой информации (выработка новых понятий на основе наблюдаемых образов, «называние» или оречевление новых образов).
Из-за невозможности построить прямые аналоги между представлением в вычислительных машинах и представлением в коре головного мозга приходится переходить от имитационного уровня моделирования зрительного аппарата к функциональному, т. е. к моделированию реакций системы, а не ее структуры. В то же время физиологические и психологические исследования свидетельствуют о неразрывной связи зрительных и мыслительных процессов. Отсюда возникает вторая проблема машинного зрения: построение системы представления знаний, обобщающей опыт восприятия человека, для обеспечения полноценного восприятия изображений.
Реализация трех основных функций зрений - ориентации, узнавания, понимания (в особенности последних двух) связана с установлением соответствия между элементами структуры, представляющей изображения в памяти, и элементами (фактами) базы знаний. Фактически эта большая проблема распадается на три подзадачи: выбор адекватного представления изображений и формы представления знаний, описывающих опыт восприятия в некоторой предметной области, а также разработка механизмов установления соответствия между образами (изображениями) и понятиями.
Идея о том, что глаз есть часть мозга, принадлежит Клавдию Галену, жившему в I в. до н. Первые модели глаза, в которых сетчатка рассматривалась как светочувствительный элемент, реагирующий на лучи, преломленные хрусталиком, были построены Ф.Платтером и И.Кеплером в начале XVII в. Большую роль в исследованиях зрительного восприятия сыграли.
работы, в которых рассматривались процедуры, выполняемые нейронными структурами. При исследовании глаза лягушки было обнаружено четыре типа нейронных структур, реагирующие на определенные изображения на сетчатке: детекторы перепада яркости (края образа), детекторы движущегося края, детекторы затемнения и детекторы движущихся малых объектов. Работа этих детекторов тесно связана с поведением лягушки. Например, перемещение маленького темного предмета в поле зрения вызывает реакцию нападения, а затемнение поля зрения - реакцию бегства.
В ряде работ отмечалось, что зрительное поле сетчатки у млекопитающих отображается на зрительные отделы коры, т. е. в коре как бы существует слепок изображения с сетчатки. Были найдены специфические нейронные комбинации: «простые» клетки, реагирующие на прямые линии определенного направления, «сложные» обнаруживающие углы, движущиеся линии, «сверхсложные», обнаруживающие отрезки прямых определенной длины. Дальнейшее развитие эти идеи нашли в [51], где были описаны нейроны, реагирующие на решетки определенной частоты, и выдвинута гипотеза о голографическом принципе запоминания изображений в памяти.
В последнее время все больше исследователей считают, что системы восприятия визуальной информации должны использовать в своей работе не только поступающие извне изображения, но и знания об окружающей среде -своеобразные модели мира. Первые такие системы разделяли во времени процессы анализа изображений и их интерпретации на основе имеющихся знаний. В дальнейшем было предложено, чтобы эти подсистемы работали параллельно, непрерывно обмениваясь информацией.
Одной из особенностей зрительного восприятия, согласно является проблемная ориентация зрения. Во многих случаях глаз ошибается в достаточно простых ситуациях. Возникают различные зрительные иллюзии. Часть из предопределена генетически, другие могут вырабатываться. Имеются основания считать, что иллюзии - следствие работы восприятия не как.
универсальной, а как проблемно-ориентированной в каждый момент системы. Это означает, что система «глаз-мозг» постоянно подстраивается под ситуацию и в текущий момент обладает существенно меньшим разнообразием реакций, чем потенциально она допускает. Перестройка системы управляется контекстом наблюдения и состоянием самой системы. Организм постоянно ищет информацию, необходимую ему для действий, и выделяет наиболее важную в данный момент. Отсюда следует, что система восприятия должна обладать избирательностью и проблемной ориентацией.
Поскольку в каждый момент важны различные признаки и особенности образов, необходима автоматическая перестройка системы на текущий контекст. Информация о нем может поступать в систему как изнутри (определяться решаемой задачей), так и извне (определяться анализируемыми изображениями). В последнем случае должны быть выделены признаки контекста, многие из которых можно получить на основе анализа зрительных иллюзий (например, сходящиеся в одну точку линии на изображении есть признак контекста «перспективное видение», приводящему к вполне определенному восприятию объектов на изображении). При столкновении с новой ситуацией перестройка восприятия должна происходить «сверху вниз» от глобального контекста (модели мира) до набора локальных признаков объектов - по аналогии с живыми организмами.
Определение взаимного расположения объектов на разных уровнях разложения
В любых алгоритмах, разработанных на базе теории активного восприятия, будь то алгоритмы узнавания, сегментации и др., геометрическим элементом является та или иная подобласть изображения, которая лишь на последнем уровне разложения представляет собой пиксель исходного изображения. Обычные координатные системы на плоскости (прямоугольная, радиальная и т.д.) наделяют любую точку координатами, и таким образом не могут отразить специфики работы с изображениями в рамках теории активного восприятия. Поэтому вычисления, необходимые для определения взаимного расположения подобластей получаются достаточно громоздкими, особенно с учетом различных комбинаций. Таким образом, координатная система, которая была бы удобна с точки зрения использования в алгоритмах, основывающихся на базе теории активного восприятия, должна оперировать не с понятием математической точки, а с понятием подобласти изображения, представленной точкой, имеющей визуальную массу подобласти. Как уже отмечалось, на каждом уровне разложения изображения в соответствии с теорией активного восприятия изображение разделяется на 16 равных по площади частей (рис. 2.1). Поэтому на каждом из уровней разложения размер рассматриваемых подобластей является неизменной величиной относительно размеров всего изображения. Таким образом, зная размеры всего изображения и номер рассматриваемого уровня, мы точно знаем размеры рассматриваемой на этом уровне подобласти изображения.
Разложение изображения в соответствии с теорией активного восприятия происходит в виде пирамиды: сначала система фильтров F, (рис. 2.2) накладывается на все изображение, затем, как уже было сказано, изображение делится на 16 частей, и на каждую из них опять накладывается система фильтров (рис. 2.3). Таким образом, в пространстве изображения на каждом уровне образуется множество подобластей изображения, на которые накладываются фильтры. Следуя работе [126], назовем это множество картой изображения на данном уровне. Тогда множество карт на множестве уровней есть атлас изображения.
Так как на первом уровне карта изображения состоит только из одной области, то любая подобласть изображения на любом уровне будет относиться к этой области (лежать внутри), поэтому для обозначения координаты области карты первого уровня будем использовать пустую последовательность координат (0) (цепочку координат нулевой длины). 2. Карта второго уровня содержит 16 подобластей, таким образом, для обозначения координат подобластей этого уровня будем использовать в качестве координаты номер подобласти (п) (пока порядок нумерации подобластей не важен). 3. Карта третьего уровня содержит 16 х 16 = 256 подобластей, и в качестве координат этих подобластей будем использовать координату с карты предыдущего уровня и номер подобласти внутри подобласти предыдущего уровня. Таким образом, на этом уровне у нас будет по 16 подобластей имеющие одинаковые номера, но сочетание координаты на карте предыдущего уровня с номером подобласти этой карты будет уникальными. Получившиеся координаты будем записывать следующим образом: (n, т). 4. Карты последующих уровней будут содержать все большее число подобластей, но в сочетании с координатами на карте предыдущего уровня, будем иметь разбиение каждой подобласти карты предыдущего уровня на 16 подобластей, которые необходимо пронумеровать и этот номер добавить в качестве еще одной координаты к координатам карты предыдущего уровня. Таким образом, число координат в цепочке координат будет на одно меньше чем номер уровня карты, к которой относится данная подобласть. В результате в целом получили координатное дерево, на котором можно задать координатные цепочки (пути). Это координатное дерево, соответственно, будет обладать следующими особенностями: во-первых, длина цепочки напрямую зависит от количества рассматриваемых уровней разложения; во-вторых, точность указания подобласти соответствует точности сегментации, узнавания и т.д. на данном уровне разложения. Но наиболее важной особенностью такой координатной системы является то, что для случая, когда один объект является частью другого, координатная цепочка меньшего объекта (рассматриваемого на карте более поздних уровня) будет состоять из координатной цепочки большего объекта (рассматриваемого на карте более раннего уровня) и «окончания» цепочки, которое в свою очередь будет указывать где внутри большего объекта находится меньший. Полученное координатное дерево отражает структуру пирамидальное координатной системы, моделирующей атлас карт в представлении на плоскость.
Рассмотрим, например, изображение дома (рис. 2.1). Дом состоит из более мелких объектов: в частности окна. В рассматриваемой пирамидальной координатной системе, координатная цепочка окна будет состоять из координатной цепочки дома и некоторого «окончания» цепочки, которое фактически указывает на расположение окна внутри дома. Кроме того, по длине цепочки мы можем определить и точность, с которой указывается расположение окна как относительно всего изображения, так и относительно дома.
Для точного указания месторасположения некоторого объекта с учетом всех особенностей его геометрической формы может потребоваться указания нескольких подобластей на картах одного или разных уровней. Таким образом, для определения нахождения одного объекта внутри другого, необходимо выполнить сравнение цепочек их координат и определить содержит ли более длинная из них более короткую.
Другими словами, использование рассматриваемой координатной системы в алгоритмах, построенных на базе теории активного восприятия, позволяет решить задачу стратегии восприятия с точки зрения определения подобластей интереса и взаимного расположения объектов на изображении, относящихся к разным уровням разложения изображения.
Необходимым и достаточным условием 45-связности с учетом гладкой склейки является различие в номерах подобластей планигона только в одном двоичном разряде. Для случая же определения 4у-связности без учета гладкой склейки, необходимо выполнить соответствующую дополнительную проверку.
Две подобласти изображения являются 8 -связными, если они имеют хотя бы одну общую вершину. Как и в случае 4?-связности, если речь идет о 85-связности с учетом гладкой склейки, то это означает, что самый левый и самый правый столбцы планигона, а также самая верхняя и самая нижняя строка планигона являются соседними, т.е. имеют общую сторону, а, следовательно, и вершину.
Необходимым и достаточным условием 85-связности с учетом гладкой склейки является различие в номерах подобластей планигона только в одном или только в двух подряд идущих двоичных разрядах, считая первый и последний разряды соседними. Для случая же определения 85-связности без учета гладкой склейки, необходимо выполнить соответствующую дополнительную проверку.
Каждый двоичный разряд получающейся цепочки определяет принадлежность подобласти к той или иной половине всей рассматриваемой области, постепенно сужая размеры этой подобласти, при необходимости, вплоть до пикселя исходного изображения. Первый из четырех двоичных разрядов (рис. 2.4) определяет принадлежность подобласти левой или правой частям планигона, а второй разряд - верхней или нижней части планигона. А затем, для следующих двух разрядов наблюдается рефлексность направлений, своя для каждого из 4 углов планигона.
Информационная модель компенсации параллельного переноса
В любых алгоритмах, разработанных на базе теории активного восприятия, будь то алгоритмы узнавания, сегментации и др., геометрическим элементом является та или иная подобласть изображения, которая лишь на последнем уровне разложения представляет собой пиксель исходного изображения. Обычные координатные системы на плоскости (прямоугольная, радиальная и т.д.) наделяют любую точку координатами, и таким образом не могут отразить специфики работы с изображениями в рамках теории активного восприятия. Поэтому вычисления, необходимые для определения взаимного расположения подобластей получаются достаточно громоздкими, особенно с учетом различных комбинаций. Таким образом, координатная система, которая была бы удобна с точки зрения использования в алгоритмах, основывающихся на базе теории активного восприятия, должна оперировать не с понятием математической точки, а с понятием подобласти изображения, представленной точкой, имеющей визуальную массу подобласти. Как уже отмечалось, на каждом уровне разложения изображения в соответствии с теорией активного восприятия изображение разделяется на 16 равных по площади частей (рис. 2.1). Поэтому на каждом из уровней разложения размер рассматриваемых подобластей является неизменной величиной относительно размеров всего изображения. Таким образом, зная размеры всего изображения и номер рассматриваемого уровня, мы точно знаем размеры рассматриваемой на этом уровне подобласти изображения.
Разложение изображения в соответствии с теорией активного восприятия происходит в виде пирамиды: сначала система фильтров F, (рис. 2.2) накладывается на все изображение, затем, как уже было сказано, изображение делится на 16 частей, и на каждую из них опять накладывается система фильтров (рис. 2.3). Таким образом, в пространстве изображения на каждом уровне образуется множество подобластей изображения, на которые накладываются фильтры. Следуя работе, назовем это множество картой изображения на данном уровне. Тогда множество карт на множестве уровней есть атлас изображения.
Так как на первом уровне карта изображения состоит только из одной области, то любая подобласть изображения на любом уровне будет относиться к этой области (лежать внутри), поэтому для обозначения координаты области карты первого уровня будем использовать пустую последовательность координат (0) (цепочку координат нулевой длины). 2. Карта второго уровня содержит 16 подобластей, таким образом, для обозначения координат подобластей этого уровня будем использовать в качестве координаты номер подобласти (п) (пока порядок нумерации подобластей не важен). 3. Карта третьего уровня содержит 16 х 16 = 256 подобластей, и в качестве координат этих подобластей будем использовать координату с карты предыдущего уровня и номер подобласти внутри подобласти предыдущего уровня. Таким образом, на этом уровне у нас будет по 16 подобластей имеющие одинаковые номера, но сочетание координаты на карте предыдущего уровня с номером подобласти этой карты будет уникальными. Получившиеся координаты будем записывать следующим образом: (n, т). 4. Карты последующих уровней будут содержать все большее число подобластей, но в сочетании с координатами на карте предыдущего уровня, будем иметь разбиение каждой подобласти карты предыдущего уровня на 16 подобластей, которые необходимо пронумеровать и этот номер добавить в качестве еще одной координаты к координатам карты предыдущего уровня. Таким образом, число координат в цепочке координат будет на одно меньше чем номер уровня карты, к которой относится данная подобласть. В результате в целом получили координатное дерево, на котором можно задать координатные цепочки (пути). Это координатное дерево, соответственно, будет обладать следующими особенностями: во-первых, длина цепочки напрямую зависит от количества рассматриваемых уровней разложения; во-вторых, точность указания подобласти соответствует точности сегментации, узнавания и т.д. на данном уровне разложения. Но наиболее важной особенностью такой координатной системы является то, что для случая, когда один объект является частью другого, координатная цепочка меньшего объекта (рассматриваемого на карте более поздних уровня) будет состоять из координатной цепочки большего объекта (рассматриваемого на карте более раннего уровня) и «окончания» цепочки, которое в свою очередь будет указывать где внутри большего объекта находится меньший. Полученное координатное дерево отражает структуру пирамидальное координатной системы, моделирующей атлас карт в представлении на плоскость.
Рассмотрим, например, изображение дома (рис. 2.1). Дом состоит из более мелких объектов: в частности окна. В рассматриваемой пирамидальной координатной системе, координатная цепочка окна будет состоять из координатной цепочки дома и некоторого «окончания» цепочки, которое фактически указывает на расположение окна внутри дома. Кроме того, по длине цепочки мы можем определить и точность, с которой указывается расположение окна как относительно всего изображения, так и относительно дома.
Для точного указания месторасположения некоторого объекта с учетом всех особенностей его геометрической формы может потребоваться указания нескольких подобластей на картах одного или разных уровней. Таким образом, для определения нахождения одного объекта внутри другого, необходимо выполнить сравнение цепочек их координат и определить содержит ли более длинная из них более короткую.
Другими словами, использование рассматриваемой координатной системы в алгоритмах, построенных на базе теории активного восприятия, позволяет решить задачу стратегии восприятия с точки зрения определения подобластей интереса и взаимного расположения объектов на изображении, относящихся к разным уровням разложения изображения.
Необходимым и достаточным условием 45-связности с учетом гладкой склейки является различие в номерах подобластей планигона только в одном двоичном разряде. Для случая же определения 4у-связности без учета гладкой склейки, необходимо выполнить соответствующую дополнительную проверку.
Две подобласти изображения являются 8 -связными, если они имеют хотя бы одну общую вершину. Как и в случае 4?-связности, если речь идет о 85-связности с учетом гладкой склейки, то это означает, что самый левый и самый правый столбцы планигона, а также самая верхняя и самая нижняя строка планигона являются соседними, т.е. имеют общую сторону, а, следовательно, и вершину.
Необходимым и достаточным условием 85-связности с учетом гладкой склейки является различие в номерах подобластей планигона только в одном или только в двух подряд идущих двоичных разрядах, считая первый и последний разряды соседними. Для случая же определения 85-связности без учета гладкой склейки, необходимо выполнить соответствующую дополнительную проверку.
Каждый двоичный разряд получающейся цепочки определяет принадлежность подобласти к той или иной половине всей рассматриваемой области, постепенно сужая размеры этой подобласти, при необходимости, вплоть до пикселя исходного изображения. Первый из четырех двоичных разрядов (рис. 2.4) определяет принадлежность подобласти левой или правой частям планигона, а второй разряд - верхней или нижней части планигона. А затем, для следующих двух разрядов наблюдается рефлексность направлений, своя для каждого из 4 углов планигона. В процессе узнавания изображения необходимо установление соответствия между системой координат анализируемого изображения и системой координат эталонного изображения, так как при их несоответствии неизбежны ошибки при сравнении анализируемого и эталонного изображений.
Таким образом, мы можем разбить задачу координатного совмещения эталонного и анализируемого изображения на три подзадачи: 1. Координатное совмещение при параллельном переносе. 2. Координатное совмещение при повороте. 3. Координатное совмещение при изменении масштаба. 3.2. Информационная модель компенсации параллельного переноса
В качестве способа компенсации параллельного переноса распознаваемого изображения относительно эталонного изображения, используется система координат, начало которой приходится на центр тяжести изображения. При этом принято предположение о том, что расположение центра тяжести изображения, состоящего из совокупности знака и помех, будет незначительно отличатся от расположения центра тяжести идеального знака. Так как, в нашем случае, начало системы координат соответствует центру рецепторного поля - центру анализируемой области изображения, то совмещением начала координат с центром тяжести изображения является центрирование изображения. Центрирование изображения достигается путем анализа значений компонентов вектора разложения Ці, JJ,2, щ, Из на фильтрах в соответствии с теорией активного восприятия .
Отследить поворот анализируемого изображения относительно эталонного представляется возможным путем вращения рецепторного поля. Однако, на практике возможность получения одного и того же изображения под разными углами встречается редко. Для решения этой проблемы возможно применение стандартных цифровых методов поворота изображения, однако их применение связано со значительным вычислительными затратами.
Более эффективный способ заключается во вращении самой системы фильтров.
Информационная модель уровня страницы текста при многоуровневой обработке изображений
Под определением ориентации объекта понимается определение месторасположения объекта и выявление взаимосвязи между направлениями осей условной координатной системы объекта и абсолютной координатной системой, привязанной к плоскости объекта. Задача определения месторасположения объекта сводится к разделению объекта и фона на изображении. В восприятии человека поверхность, заключенная в пределах определенных границ и обладающая меньшей площадью, стремится приобрести статус фигуры (объекта) [37]. Тогда окружающая ее поверхность будет восприниматься как фон.
Рассмотрим решение данной задачи с позиций теории активного восприятия. В этом случае на каждом уровне g-пирамиды, необходимо определить месторасположение объекта с точностью до «клетки» планигона, т.е. с точностью до 1Л от высоты и ширины участка изображения, на который накладываются фильтры [102]. При этом по мере увеличения уровня разложения на «g-пирамиде точность будет увеличиваться вплоть до пикселя изображения (на последнем уровне).
Рис. 4.1. В качестве критерия границ объекта выберем максимальный перепад сумм яркостей по «столбцам» (для левой и правой границ) планигона и «строкам» планигона (для верхней и нижней границ). Например, для определения левой границы изображения страницы текста (рис. 4.1) находим максимальный перепад в сторону увеличения суммарной яркости «столбцов» планигона (рис. 4.2). Аналогично для определения правой границы находим максимальный перепад в сторону уменьшения суммарной яркости. Для данного случая, значения перепадов на соответствующих переходах занесены в табл. 4.1. Номера переходов изображены на рис. 4.3. Как видно из табл. 4.1, в данном случае на первом уровне разложения левая граница соответствует переходу «1», правая - переходу «4», верхняя - переходу «О», нижняя - переходу «4».
Таким образом, алгоритм нахождения границ объекта можно сформулировать следующим образом: 1. Раскладываем изображение на Q-пирамиде, вычисляем значения компонентов вектора разложения ц(. 2. Вычисляем значения Hst и Vst (z = 0 -ь 4) по формулам (4.1) - (4.10). 3. Определяем номера переходов (г), соответствующие максимальным и минимальным значениям Hs{ и VSJ (і - 0 - - 4). 4. Определяем уточненные границы изображения в соответствии с полученными номерами переходов. 5. Раскладываем части изображения, лежащие «вокруг» уточненных границ изображения (левой, правой, верхней и нижней границ), на Q-пирамиде, вычисляем значения компонентов вектора разложения ц,- для этих частей изображения. Например, если мы определили на предыдущем шаге, что левая граница соответствует переходу «1», то, на этом шаге, разложению на Q-пирамиде подлежит участок изображения, находящийся между переходом «О» и переходом «2». В результате получаем 4 различных вектора {]ij}, соответствующие соответственно левой, правой, верхней и нижней границам объекта (на этом уровне разложения). 6. Для каждой из уточняемых границ (левой, правой, верхней и нижней), на основе полученных векторов {ц/}, по формулам (4.2) — (4.4) и (4.7) - (4.9) вычисляем значенияHst и Vst (і=1+ 3). 7. Определяем номера переходов (/), соответствующие максимальным и минимальным значениям Hst и Vst (/=1- 3). 8. Переходим снова к шагу 4.
Процесс прекращается при достижении заданной точности определения границ, при этом на каждой итерации (шаги 4-8), мы повышаем точность нахождения границ в 2 раза. Таким образом, возможно нахождение границ объекта с необходимой точностью (вплоть до пикселя исходного изображения).
Задача выявления взаимосвязи между направлениями осей координатной системы объекта и абсолютной координатной системой сводится к определению угла поворота между двумя прямоугольными системами координат на плоскости: условной системой координат самого объекта и абсолютной системой координат плоскости объекта (рис. 4.4); а также к определению возможного зеркального отражения осей координат (рис. 4.5), возникающего, например, в случае получения изображения с прозрачной пленки, если ее положили «другой» стороной.
При наличии таких «повернутых» эталонных образов определение угла поворота выполняется путем узнавания в анализируемом изображении «повернутого» эталонного образа. При этом вместе с самим эталонным образом (в виде результатов разложения на -пирамиде) должна храниться и информация относительно величины угла поворота.
Для случая уровня страницы текста это означает необходимость хранения образов прямоугольника, повернутого на различные углы.
Для случаев, когда угол поворота - прямой или когда мы имеем дело с зеркальным отражением, в целях уменьшения необходимых ресурсов, компоненты векторов разложения «повернутых» эталонных изображений можно не хранить в памяти, т. к. их легко вычислить на основе компонентов векторов разложения «правильно ориентированного» эталонного изображения. В этих случаях достаточно пересчитать соответствующие компоненты вектора разложения, учитывая данные табл. 4.2. Такой подход возможен благодаря особенности фильтров, используемых в теории активного восприятия.
Для определения поворота на острые углы, соответствующие эталонные образы приходится хранить в памяти. При этом обычно достаточно хранить только один уровень разложения (16 значений щ), поэтому это не оказывает значительного влияния на необходимый объем ресурсов.
Количество «повернутых» образов зависит от требуемой точности определения угла наклона. Если определение ориентации объекта изображения необходимо для его последующего узнавания с помощью алгоритмов, базирующихся на теории активного восприятия, то, как правило, достаточно определять угол с точностью не более 15 [102]. Поворот на углы большие 90 рассматривается как поворот на уже рассмотренный прямой угол и последующий поворот на так же рассмотренный острый угол.
