Содержание к диссертации
Введение
1 Обзор и анализ методов распознавания и понимания изображений 9
1.1 Анализ методов распознавания изображений 10
1.1.1 Классификация методов распознавания 10
1.1.2 Анализ систем оптического распознавания символов 18
1.1.3 Анализ информационно-поисковых систем 23
1.2 Анализ систем представления знаний 25
1.3 Анализ методов понимания изображений 30
1.3.1 Парадигмы процесса восприятия визуальной информации 30
1.3.2 Анализ подходов к моделированию памяти человека 32
1.3.3 Анализ возможностей моделирования мнемонических процессов 38 Выводы 41
2 Разработка и исследование метода семантического анализа изображений 43
2.1 Разработка метода семантического анализа изображений 43
2.1.1 Выбор непроизводных структурных элементов 43
2.1.2 Методика построения геометрического описания 44
2.1.3 Методика построения семантического описания 47
2.1.4 Метод семантического анализа изображений 48
2.2 Разработка неоднородной нечеткой семантической сети 53
2.2.1 Неоднородная нечеткая семантическая сеть 53
2.2.2 Вывод на неоднородной нечеткой семантической сети путем сопоставления ее фрагментов 56
2.2.3 Пополнение неоднородной нечеткой семантической сети 60
2.3 Разработка геометрической модели объекта и структуры базы знаний 63
2.3.1 Геометрическая модель объекта 63
2.3.2 Модель библиотеки специальных понятий 68
2.3.3 Модель библиотеки примитивов 68
2.3.4 Модель лингвистических шкал 69
2.3.5 Модель структуры аннотаций 71
Выводы 73
3 Разработка и исследование алгоритмов семантического анализа изображений 74
3.1. Разработка алгоритма построения геометрической модели объекта 74
3.1.1. Поиск особых точек 74
3.1.2 Описание взаимного положения особых точек 78
3.1.3. Поиск геометрических элементов 81
3.1.4. Описание размеров геометрических элементов 85
3.1.5. Поиск обособленных частей контура 86
3.1.6 Описание взаимного положения обособленных частей контура 87
3.1.7. Алгоритм построения геометрической модели объекта 88
3.2 Разработка алгоритма восстановления визуального образа по геометрической модели объекта 96
3.3 Разработка алгоритма сопоставления геометрических моделей 106
Выводы 117
4 Анализ эффективности и экспериментальная оценка алгоритмов семантического анализа изображений 118
4.1. Исследование алгоритма построения геометрической модели объекта 118
4.2 Исследование алгоритма восстановления визуального образа по геометрической модели объекта 125
4.3 Исследование алгоритма сопоставления геометрических моделей . 130
4.4 Программная система для семантического анализа контурных изображений 138
Выводы 146
Заключение 148
- Классификация методов распознавания
- Вывод на неоднородной нечеткой семантической сети путем сопоставления ее фрагментов
- Описание взаимного положения особых точек
- Исследование алгоритма построения геометрической модели объекта
Введение к работе
Актуальность темы. Благодаря всеобщей компьютеризации и распространению электронного документооборота в различных областях человеческой деятельности накоплены огромные архивы текстовой и визуальной информации. Непрерывно расширяющимся электронным архивом является глобальная сеть Internet. Проведенное в диссертационной работе исследование современных информационных систем позволило сделать вывод об ограниченных возможностях семантического анализа и поиска изображений. Под семантическим анализом изображений понимается автоматическое получение их семантических описаний (аннотаций) и поиск в пространстве этих описаний (поиск по содержанию). Из реализованных информационными системами видов поиска поиск изображений по ключевым словам наиболее близок к содержательному поиску, но обладает одним существенным недостатком - ключевые слова к изображениям формирует эксперт. Развитие информационных систем при отсутствии механизмов содержательного поиска изображений обуславливает актуальность темы исследования.
Задача анализа и распознавания изображений сложных объектов (например, фотопортретов людей, рукописных символов) на сегодня не имеет достаточно эффективных решений: точность распознавания варьируется от 60 до 70 %. Чем более сложный визуальный образ подвергается анализу, тем большую важность приобретает понимание того, что анализируется. Только располагая знаниями об изображаемой предметной области, система сможет сформировать семантические описания изображений. В диссертационной работе решается задача разработки метода и алгоритмов анализа изображений сложных объектов на основе базы знаний.
Цель работы и задачи исследования. Целью диссертационной работы является разработка метода и алгоритмов семантического анализа контурных изображений сложных объектов на основе структурного подхода и формализованных знаний предметной области. Объектом семантического анализа является полутоновое изображение объекта, контур которого может быть вербально (словесно) описан.
Для достижения цели диссертационной работы поставлены и решены следующие задачи:
- исследование методов распознавания изображений;
сравнительный анализ систем представления знаний в ЭВМ, обоснование выбора семантической сети;
анализ результатов исследований человеческой памяти, особенностей использования знаний в процессе восприятия визуальной информации;
разработка метода семантического анализа изображений;
разработка структуры базы знаний, используемой в процессе семантического анализа;
разработка и исследование алгоритмов, реализующих метод семантического анализа изображений.
Задача разработки метода и алгоритмов семантического анализа ограничивается двумя условиями: анализу подлежат изображения одиночных объектов, на изображении присутствуют только смысловые контуры.
Ограничение на тип изображаемых объектов и предметных областей не накладывается. Возможность анализа изображений объектов из разных предметных областей обеспечивается соответствующим наполнением базы знаний.
Методы исследования. В исследованиях использовался аппарат теории множеств, математической и нечеткой логики, теории распознавания образов, искусственного интеллекта, теории вероятности, математической статистики, теории алгоритмов, аналитической геометрии и системного анализа.
Научная новизна. Предложен метод и алгоритмы анализа контурных изображений одиночных объектов, отличающиеся от известных тем, что позволяют автоматически формировать семантические описания изображений. Семантическое описание изображения осуществляется через интерпретацию его геометрического описания понятиями предметной области на основе базы знаний.
Для представления знаний предложена неоднородная нечеткая семантическая сеть, позволяющая моделировать лингвистическую неопределенность и интенсивность информационных единиц естественной памяти.
Предложена геометрическая модель объекта — геометрическое описание изображения, формализованное на неоднородной нечеткой семантической сети.
Предложена структура базы знаний для семантического анализа изображений, представленная на неоднородной нечеткой семантической сети в виде модели библиотеки примитивов, модели библиотеки специальных понятий, модели лингвистических шкал и модели структуры аннотаций.
Практическая ценность диссертационной работы заключается в возможности решения следующих практических задач:
автоматическая аннотация базы изображений (заменяющая описательную работу эксперта) и поиск по содержанию в визуальных информационных системах разных предметных областей;
сопоставление изображений сложных объектов, при описании которых существенное значение имеет форма их контуров, например, контроль соответствия подписей на документах по имеющимся образцам;
автоматическое выделение семантически значимых точек на контурных изображениях объектов, например, антропометрических точек на изображениях частей тела человека;
автоматическое выделение геометрических кривых, фигур и их конфигураций на контурных изображениях, например, для распознавания таблиц, чертежей, схем.
Реализация результатов работы. Основные результаты диссертационной работы внедрены на этане эскизного проекта программного комплекса «Следотека» для аннотации базы изображений следов обуви и поиска информации по визуальному запросу, рекомендованы к использованию при анализе и поиске информации по фотопортретным признакам в УВД г, Рыбинска; использованы при разработке подсистемы контроля подписей в автоматизированной системе «Бюджет» для финансовых органов субъектов Российской Федерации и муниципальных образований в ООО «Автоматизированные информационные процессы» (г. Москва); внедрены в учебном процессе Рыбинской государственной авиационной технологической академии им. П. А- Соловьева при обучении студентов.
Основные положения, выносимые на защиту:
неоднородная нечеткая семантическая сеть, позволяющая моделировать лингвистическую неопределенность и интенсивность информационных единиц естественной памяти;
метод анализа контурных изображений одиночных объектов, обеспечивающий семантическое описание объекта через интерпретацию его геометрической модели за счет выделения понятийных уровней;
структура базы знаний, используемой в процессе семантического анализа изображений, и геометрическая модель объекта на неоднородной нечеткой семантической сети;
алгоритм восстановления визуального образа по геометрической модели на основе лингвистических шкал, обеспечивающий минимизацию рассогласованности восстановленной информации;
алгоритм целенаправленного сопоставления геометрических моделей через генерацию гипотез о соответствии их частей на основе варианта сопоставления особых точек экстремума, позволяющий сократить время поиска.
Апробация работы. Все основные результаты теоретического и практического характера, полученные автором или при его непосредственном участии, докладывались на IВНТК «Компьютерные технологии в науке, проектировании и производстве», 1999 г. — Нижний Новгород; П ВНТК «Компьютерные технологии в науке, проектировании и производстве», 2000 г. -Нижний Новгород; XXVI конференции молодых ученых и студентов РГАТА, 2000 г. - Рыбинск; Международной научно-технической конференции «Контроль, измерения, информатизация», 2000 г, - Барнаул; IV ВНТК «Информационные технологии в науке, проектировании и производстве», 2002 г. - Нижний Новгород; в Институте программных систем РАН (Переславль-Залесский, 2003 г.); на кафедре Вычислительные системы Рыбинской государственной авиационной технологической академии им. П. А, Соловьева,
Публикации. По теме диссертации опубликовано 8 печатных работах, из них 1 статья, 1 депонированная рукопись и 6 тезисов докладов.
Краткое содержание работы* Диссертационная работа состоит из введения, 4-х глав и заключения, а также списка использованных источников и приложений.
Во введении обоснована актуальность темы исследования, сформулированы цели работы, основные задачи и методы исследования, охарактеризована научная новизна и практическая ценность полученных результатов, приведены основные положения, выносимые на защиту, кратко изложено содержание работы.
В первой главе исследованы методы распознавания изображений, выявлены проблемы их применения для анализа сложных классов изображений, выполнен сравнительный анализ систем представления знаний, обоснован выбор семантической сети для представления знаний, используемых в процессе семантического анализа изображений, определены требования, которым должна отвечать искусственная система понимания изображений.
Вторая глава посвящена разработке метода семантического анализа структуры контурного изображения одиночного объекта на основе формализованных знаний предметной области, в качестве системы представления знаний предложена
неоднородная нечеткая семантическая сеть, геометрическое описание изображения формализовано в виде геометрической модели объекта на неоднородной нечеткой семантической сети, разработана структура базы знаний, используемой в процессе семантического анализа, на неоднородной нечеткой семантической сети.
Третья глава посвящена разработке алгоритмов семантического анализа изображений: алгоритма построения геометрической модели объекта, алгоритма восстановления визуального образа по геометрической модели объекта, алгоритма сопоставления геометрических моделей, выполнена теоретическая оценка эффективности предложенных алгоритмов.
В четвертой главе проведено экспериментальное исследование эффективности предложенных алгоритмов, описаны методики оценки, выявлены пути повышения качества результатов, рассмотрены структура, функциональные возможности и форматы хранения внешних данных программной системы для семантического анализа контурных изображений.
В заключении приведены основные выводы и результаты работы.
Классификация методов распознавания
Методы распознавания по способу предварительной обработки следует разделить на интегральные и дифференциальные [19-20]. Интегральные методы - это методы, основанные на определении некоторых суммарных свойств дискретных изображений, их глобальных особенностей. Большинство из них базируется на интегральных преобразованиях, таких как дискретные преобразования Фурье, Уолша, Адамара. Интегральные методы используются для фильтрации различного рода помех как на многоградационных, так и на бинарных изображениях, причем в последнем случае они существенно упрощаются.
Дифференциальные методы требуют предварительного выделения контурного остова изображения. Считается, что такие характеристики, как границы плоских объектов и отверстий в них, ребра трехмерных объектов и т.п. соответствуют максимуму нормы градиента функции яркости изображения f(xty). Градиент яркости сохраняет свои величину и ориентацию по отношению к визуальному образу, когда тот поворачивается или сдвигается. Поиск градиента связан с определением производных функции /(х,у), поэтому соответствующие алгоритмы называют дифференциальными. Дифференциальные методы обработки изображений позволяют получить контурный остов как на многоградационном, так и на бинарном изображении. Поиск перепадов яркости выполняется с помощью операторов Лапласа, Робертса, Собеля, Превитта и др. [29-37].
Существуют четыре источника возникновения контуров на изображении: - нарушение непрерывности расстояния, с которого ведется наблюдение; - нарушение непрерывности ориентации поверхности; - изменение отражательной способности поверхности; - эффекты, связанные с освещением, такие как тени, собственно источники света, блики. Контуры изображения, воспринимаемые человеком, двухмерны, но дают достаточную информацию о форме, количестве и местоположении изображенных объектов- На предмет исследования налагаются два ограничения: - анализу подлежат изображения одиночных объектов (объект является одиночным, если он характеризуется одним семантически значимым понятием, например, стол - это одиночный объект, а стол, на котором стоит лампа, - сцена); - на изображении присутствуют только смысловые контуры (например, должны быть исключены контуры, порождаемые текстурным рисунком).
Данные ограничения обоснованы существованием специальных методов и средств выделения на изображении одиночных объектов, в том числе ими решается задача выделения только смысловых контуров этих объектов [2].
Контурный препарат (контурный остов) изображения может быть получен двумя способами: отслеживанием или утончением [21,23]. Отслеживание границ предполагает получение ограничивающего область контура, т.е. участков изображения, на которых происходит резкое изменение градаций яркости. Утончение контура основано на нахождении крайних точек области изображения и их удалении, при условии, что это не нарушит основные размеры и топологию области. Алгоритмы отслеживания границ в качестве результата дают линии контура неодинаковой ширины, поэтому после отслеживания контура его утончают. Выбор способа получения контурного остова зависит от класса анализируемых изображений. Для символов, например, целесообразно использовать утончение, для фотопортретных изображений - отслеживание.
Из-за различного рода помех при печати и считывании на изображении появляются случайные отклонения, которые вносят искажения в контурный препарат. К таким отклонениям относятся: шум в виде одиночных элементов, «бахрома» контуров, пустоты внутри линий, разрывы линий. Для устранения случайных отклонений выделение контура сопровождается применением алгоритмов удаления шума и заполнения пустот [21].
Для векторизации контурного изображения - выделения на контуре известных примитивных элементов контура (кривых, характерных точек) - используются алгоритмы векторизации: алгоритм соединения локальных разрывов, глобальный эвристический поиск, преобразование Хоу (Hough), алгоритм Монтанари [10,38], По мнению автора, алгоритм Монтанари является наиболее полезным для решения задачи описания структуры контура известными геометрическими примитивами (таблица 1-2),
По характеру зависимости между описаниями и классами методы распознавания делятся на детерминированные, вероятностные и нечеткие [14,15,18]. В де термин ирован ных методах близость объектов и явлений к известным классам определяется точными мерами, соответственно процедуры вычисления и сравнения этих мер принадлежат классической алгебре и геометрии: евклидово расстояние, расстояние по Хэммингу, взвешенные расстояния и т.д.
Вывод на неоднородной нечеткой семантической сети путем сопоставления ее фрагментов
По результатам анализа известных систем представления знаний, в том числе видов семантической сети» в главе 1 был сделан вывод о необходимости разработки семантической сети, которая позволила бы описать интенсивность информационных единиц естественной памяти, Интенсивность информационной единицы естественной памяти человека характеризует скорость ее вспоминания [100]. Чем более интенсивный след понятия имеется в памяти, тем более легко это понятие вспоминается.
Неоднородная семантическая сеть имеет два типа элементов, а, следовательно, два типа информационных единиц: вершины и дуги. Вершины представляют понятия, явления, объекты; дуги — разного рода отношения между понятиями, явлениями и объектами. Интенсивность необходимо задавать для обоих типов элементов, т.е. каждой вершине и дуге семантической сети сопоставить меру интенсивности— /гиз интервала Л/=[0..Л].
Рассмотрим, как может быть представлено некоторое структурное описание изображения с наложением мер интенсивности на его элементы. Вот пример описания образа некого Петрова: «Круглое лицо, широкий нос средней длины, средней ширины припухлые губы, зеленые глаза, короткие волосы» на лбу вихор, который не дает короткой челке лежать ровно, через лоб идут продольные морщины, А какие у него брови и уши? Не помню, обычные», В любом образе объекта, который мы держим в памяти, на первый взгляд, есть пробелы. Однако постепенно мы можем вспомнить новые детали, которые не являются отличительными и не бросаются в глаза при знакомстве с этим объектом. Эти несущественные детали имеют в нашей памяти меньшую интенсивность.
По всей видимости, такое «разноинтенсивное» описание формируется на основе прошлого опыта человека, важные детали запоминаются, обычные опускаются. Интенсивность информационных единиц памяти уменьшается также в результате забывания или увеличивается в результате припоминания. Автор предлагает формировать «разноинтенсивное» описание в процессе обучения искусственной системы анализа изображений. Для обучения системы некоторому объекту на ее вход предъявляется набор изображений объекта - обучающая выборка. Общие детали изображений обучающей выборки должны оставить в памяти более интенсивный след. Поэтому при предъявлении на вход каждого нового изображения интенсивность повторяющихся деталей следует увеличивать, а отсутствующих - уменьшать, новые детали должны иметь интенсивность, обратно пропорциональную количеству ранее предъявленных изображений.
Моделируя интенсивность информационной единицы памяти, мы приходим к нечеткому описанию. Пусть, например, морщины на лбу Петрова видны не всегда, а в зависимости от выражения его лица, освещения и т.д., и на 7 изображениях из 10 морщины видны. Это означает, что морщины на лбу характерны лицу Петрова, но только некоторым неопределенным образом, а описание лица Петрова имеет нечеткие границы. Для распознавания некоторого множества объектов мы должны разбить это множество на подмножества, описать их, а затем классифицировать изображения, относя их к тому или иному подмножеству. Многие, или даже большинство человеческих знаний и связей включают такие построения, которые нельзя назвать множествами в классическом смысле. Их следует считать нечеткими множествами (или подмножествами), т.е. классами с нечеткими границами, когда переход от принадлежности классу к непринадлежности происходит постепенно, не резко [115,116]. Теория нечетких множеств позволяет структурировать то, что разделено не очень точными границами, например, подмножество изображений Петрова среди изображений других людей. В обработке информации человеком или с помощью машины числовые и нечисловые данные во многих случаях не могут быть ни четкими, ни даже вероятностными, их можно поместить только в интервалы достоверности- Вот тогда вступает в действие теория нечетких множеств. Теория нечетких множеств не конкурирует с теорией вероятности и статистическими методами, она заполняет пробел в области струюуризованной неопределенности [118]. Нечеткость означает, что некий элемент принадлежит подмножеству, но только несколько неопределенным образом Поскольку меры интенсивности позволяют создать нечеткое описание объекта, неоднородную семантическую сеть G = {S9R), вершинам seS и дугам reR которой сопоставлены меры интенсивности [I из интервала М=[0,.Л] будем называть неоднородной нечеткой сем антической сетью [110,111]:
Представление интенсивности, по мнению автора, очень важно для моделирования мнемонических процессов, так как интенсивность - это механизм управления поиском информации в памяти. Информация, имеющая большую интенсивность, более доступна, лежит на поверхности, как бы составляя верхний слой памяти. Чем меньше интенсивность информации, тем более глубоко она спрятана в памяти, и тем более сложно человеку к ней обратиться. Обращение к более глубоким слоям памяти происходит в случае неудачного поиска в верхних слоях. Автор вводит операцию фильтрации информационных единиц семантической сети по интенсивности, с помощью которой предлагает ограничивать пространство информационного поиска в сети. Фильтрацией по интенсивности с порогом L будем называть операцию преобразования неоднородной нечеткой семантической сети Gx = (Sl9Rx) в G2 = (52,A2)» такую, что: Фильтрация по интенсивности позволяет рассматривать структурные описания изображений на разных уровнях детализации. Высокий порог фильтра дает совокупность наиболее существенных и обязательных элементов описания, низкий порог — более детальное описание и позволяет проводить более точный анализ. Анализ знаний» представленных на неоднородной нечеткой семантической сети, с постепенным уменьшением порога фильтрации моделирует вспоминание информации человеком.
Описание взаимного положения особых точек
Алгоритм разбиения множества геометрических элементов на группы достаточно прост. Для некоторого геометрического элемента с помощью метода прямой волны находятся две его особые точки, для каждой найденной особой точки с помощью метода обратной волны находятся опирающиеся на нее геометрические элементы. Найденные таким образом геометрические элементы являются непосредственно связанными и образуют группу- Процедура поиска непосредственно связанных элементов повторяется для каждого вновь найденного элемента до тех пор, пока не будут найдены все элементы группы. Аналогичным образом находятся все обособленные части контура.
Каждая выделенная часть контура описывается в геометрической модели объекта W0: - вершиной Я} є 5Э, которая будет представлять эту часть контуры; - дугой г7 є R7, соединяющей s2 с корневой вершиной модели sroot; -дугами rs єfig, соединяющими s3 с вершинами s2 eS2 (геометрическими элементами группы); - дугами r9f eR9, соединяющими s3 с вершинами s]f eS (особыми точкам в основании геометрических элементов группы); -четырьмя дугами г10 еЛ,0? соединяющими s3 с вершинами s, є5р являющимися крайней левой, крайней правой, крайней верхней и крайней нижней среди особых точек данной части контура - особыми точками экстремум а. ЗЛ.6 Описание взаимного положения обособленных частей контура В геометрической модели объекта W0 взаимное положение обособленных частей описывают пространственные отношения (слой L{) и дополнительные размеры между точками экстремума этих частей (слой Z4). Описание взаимного положения каждой пары обособленной частей избыточно, поэтому автор предлагает описывать взаимное положение соседних пар обособленных частей, упорядоченных некоторым образом в плоском пространстве. Упорядочивание обособленных частей в пространстве осуществляется в соответствии с порядком точек экстремума, возможны следующие варианты порядка: - порядок крайних левых точек по возрастанию абсцисс; - порядок крайних левых точек по возрастанию ординат; - порядок крайних правых точек по возрастанию абсцисс; - порядок крайних правых точек по возрастанию ординат; - порядок крайних верхних точек по возрастанию абсцисс; - порядок крайних верхних точек по возрастанию ординат; - порядок крайних нижних точек по возрастанию абсцисс; - порядок крайних нижних точек по возрастанию ординат. Для каждого варианта порядка и для каждой пары соседних точек экстремума геометрическая модель объекта дополняется: -дугой г2 єЛ2, соединяющей две вершины 1 1 єSx (пространственным отношением, соединяющим две особые точки экстремума); - вершиной sAS4 которая будет представлять дополнительный размер; - дугой Гц є Дп, соединяющей 54 с корневой вершиной модели sroot; - парой дуг / i4pr14i+1 Й14, соединяющих sA с вершинами i/ssli+l GSX (особыми точками экстремума). После того, как необходимые дополнительные размеры определены, описываются их нечеткие соотношения аналогично тому, как описываются соотношения размеров геометрических элементов некоторой обособленной части контура (см. пункт 3Л.3). 3.1.7 Алгоритм построения геометрической модели объекта Блок-схема алгоритма построения геометрической модели объекта представлена на рисунке 3.4. Здесь и далее действия алгоритма, обозначенные на блок-схеме прямоугольником с двойной рамкой, описаны вспомогательными блок-схемами. Вспомогательные блок-схемы для алгоритма построения геометрической модели представлены на рисунках 3.5-3,9, Обобщая все вышесказанное, можно сформулировать отличительные особенности предлагаемого алгоритма [111]: - первоначальная декомпозиция контура выполняется особыми точками окончания и ветвления контура, если попытка идентификации выделенных таким образом элементов контура заканчивается неудачей, элементы считаются составными, декомпозиция составных элементов на примитивные осуществляется особыми точками перегиба; - идентификация геометрического элемента контура считается неудачной, если он слишком отличается ото всех геометрических примитивов библиотеки, необходимый и достаточный набор геометрических примитивов библиотеки, а также оптимальное значение для максимально-допустимой меры отличия необходимо выбрать экспериментально; - для выделения на кривой точек перегиба используется критерий поиска оптимально гладкой кривой Монтанари, адаптированный для решаемой задачи. Разбиение составного контура продолжается до успешной идентификации всех его частей, на каждом шаге алгоритма контур делится на две части одной точкой перегиба; - при описании отношений взаимного положения и размера между элементами модели последние упорядочиваются, и описанию подвергаются отношения только между соседними в последовательности элементами, благодаря этому из геометрической модели объекта исключаются отношения, которые могут быть получены выводом по транзитивному замыканию, т.е. способствует упрощению модели; - описание каждой обособленной части контура самодостаточно, так как сначала описываются отношения внутри частей, а затем части соотносятся друг с другом, благодаря этому при выводе знаний на модели появляется возможность сведения решаемой задачи к подзадачам, т.е. появляется возможность разработки более эффективных алгоритмов вывода; - качество геометрической модели объекта зависит от качества исходного контура, предлагаемый алгоритм обеспечивает улучшение качества контура на основе приобретенных знаний о его структуре; - нечеткие отношения между элементами геометрической модели строятся с помощью лингвистических шкал, для упрощения последующего вывода знаний на модели из лингвистических шкал, а, следовательно, из модели, исключаются понятия-антонимы, лучшую размерность и содержание лингвистических шкал необходимо определить экспериментально.
Исследование алгоритма построения геометрической модели объекта
Разработан алгоритм построения геометрической модели объекта по его контурному изображению, позволяющий улучшить качество контурного изображения на основе приобретенных знаний о его структуре, оптимизировать структурное описание и, как следствие, повысить эффективность алгоритмов вывода на неоднородной нечеткой семантической сети. Теоретически время работы алгоритма и количество элементов получаемой геометрической модели линейно зависят от параметров, характеризующих сложность контура: количества обособленных частей и особых точек изображения. 2 Некоторые параметры алгоритма построения геометрической модели объекта должны быть выбраны экспериментально для адаптации к конкретной задаче: необходимый и достаточный набор геометрических примитивов библиотеки примитивов; оптимальное значение для максимально-допустимой меры отличия кривой от примитива; лучшая размерность и содержание лингвистических шкал, 3 Разработан алгоритм восстановления визуального образа по геометрической модели объекта на основе лингвистических шкал, обеспечивающий минимизацию рассогласованности восстановленной информации. Алгоритм восстановления позволяет экспериментально оценить полноту и качество геометрической модели объекта, выбрать необходимый и достаточный набор геометрических примитивов библиотеки примитивов, определить лучшую размерность и содержание лингвистических шкал. 4 Разработан алгоритм целенаправленного сопоставления геометрических моделей через генерацию гипотез о соответствии их частей на основе варианта сопоставления особых точек экстремума, позволяющий сократить время поиска. В алгоритме решена основная проблема применения семантической сети — трудоемкость вывода из-за громоздкости получаемых на ней описаний. Теоретически время работы алгоритма сопоставления Т пропорционально полиному четвертой степени: Т т4+—г-» гДе я — количество обособленных частей, am- количество особых точек сопоставляемых изображений. 5 Параметры алгоритма сопоставления (порог приемлемости результата Nmin и коэффициент оптимистичности прогноза L) должны быть определены экспериментально, исходя из оптимального сочетания качества результата и времени его получения. 117 Анализ эффективности и экспериментальная оценка алгоритмов семантического анализа изображений Исследованию подлежат три разработанные автором алгоритма; - алгоритм построения геометрической модели объекта; - алгоритм восстановления визуального образа по геометрической модели; - алгоритм сопоставления геометрических моделей объектов. Эффективность алгоритмов оценивается по качеству получаемого результата и времени его получения. Поскольку предложенный автором метод семантического анализа не накладывает ограничений на характер изображенных объектов и предметных областей кроме возможности вербального (словесного) описания контура и одиночности объекта, исследование эффективности алгоритмов проводится относительно изображений разных предметных областей. Выбраны два класса изображений, для которых актуальна задача создания и систематизации архивов: - изображения лица человека в целом, а также изображения частей лица: глаз, губ, носа; - изображения подписей человека. Примеры экспериментальных изображений приведены в Приложении В. В соответствии с введенными в первом разделе ограничениями все экспериментальные изображения являются изображениями одиночных объектов. Предложенные алгоритмы реализованы в программной системе для семантического анализа контурных изображений. Рассматриваются структура, функциональные возможности и схема интеграции программной системы с визуальной информационной системой. 4.1 Исследование алгоритма построения геометрической модели объекта Эффективность алгоритма построения геометрической модели объекта автор предлагает оценивать по трем критериям: - качество декомпозиции контура на составляющие элементы (отклонение векторизованного контура от исходного); - количество элементов геометрической модели объекта (простота модели); - время работы алгоритма. Между критериями качества декомпозиции и простоты модели существует противоречие: для повышения соответствия векторизованного контура исходному приходится увеличивать число структурных элементов, что приводит к увеличению количества элементов модели. Оба критерия зависят от ряда параметров алгоритма построения геометрической модели, оптимальные значения которых необходимо выбрать экспериментально таким образом, чтобы приемлемое отклонение контуров сочеталось с достаточной простотой модели (см. подраздел 3.1): - используемого набора геометрических примитивов библиотеки примитивов; - максимально-допустимого отклонения кривой исходного контура от примитива Qm x (формула (ЗЛЗ)). Значения параметров необходимо выбрать таким образом, чтобы приемлемое отклонение контуров сочеталось с достаточной простотой модели. Поскольку векторизованный контур представлен совокупность структурных элементов, отклонение векторизованного контура от исходного Qe будем рассчитывать через усреднение отклонений его структурных элементов: где N - количество структурных элементов в векторизованном контуре Qi - оценка отличия исходного и векторизованного контуров і-го структурного элемента, рассчитанная в соответствии с (3.12), которая используется в алгоритме построения геометрической модели при идентификации геометрических элементов. Данная оценка показывает среднее отклонение точки исходного контура от точки векторизованного в пикселях и должна стремиться к нулю. Отклонение векторизованного контура от исходного автор предлагает считать приемлемым, если векторизованный визуальный образ объекта узнаваем и отличим среди множества объектов анализируемого класса- Суть уменьшения отклонения контуров - их разбиение точками перегиба. Для векторизации контура малыми отрезками кривых и дуг точки перегиба выделяются при очень незначительных изменениях кривизны контура. Чем меньше кривизна кривой в точке перегиба, тем меньше эта точка несет информации о структуре контура. Чрезмерная детализация векторизованного контура незначительно увеличивает информативность модели, делая ее сложной для анализа. Приемлемость отклонения (узнаваемость контура) оценивается экспертом.
