Содержание к диссертации
Введение 7
Глава 1. Проблема обучения автоматизированной системы
сегментации изображений 12
1.1. Анализ задачи сегментации изображений 12
1.1.1. Изображение как способ представления информации 12
1.1.2. Классы и преобразования изображений 14
1.1.3. Формальная постановка задачи сегментации 17
1.1.4. Обзор простейших методов сегментации 19
1.1.5. Текстура как пример сложного условия семантической однородности областей изображения 24
1.1.6. Выделение сегмента по локальным данным как пример задачи распознавания образов 29
1.2. Возможности обучения сегментации 32
1.2.1. Обучение сегментации по локальным данным как задание функции на изображении 32
1.2.2. Понятия «атрибут», «предикат», «признак» 34
1.2.3. Методы обучения при распознавании образов 35
1.2.4. Проблемы при обучении сегментации 39
1.2.5. Базовые признаки и алгоритмические блоки 42
1.2.6. Модели интерфейсов для задания диапазона признака 45
1.2.7. Производные признаки 50
1.2.8. Проблема формирования понятийного аппарата для заданной области приложений 51
1.3. Неформализованная структурная модель автоматизированной системы сегментации изображений 52
1.3.1. Изображения и их элементы 52
1.3.2. Признаки и алгоритмические блоки
1.3.3. Решающее правило 5 З
1.3.4. Декларативное и процедурное описание требуемого результата 54
1.3.5. Роли пользователя и разработчика в процессе эксплуатации системы 55
1.3.6. Структурная схема комплекса 56
Выводы по главе 58
Глава 2. Модель процесса сегментации 59
2.1. Основные сущности модели 59
2.1.1. Сегменты 5 9
4 2.1.2. Признаки 62
2.1.3. Диапазоны признака 62
2.1.4. Определение диапазона признака по заданному сегменту 66
2.1.5. Учет взаимозависимости признаков 68
2.1.6. Алгоритмические блоки 72
2.2. Модель процесса сегментации 73
2.2.1. Оператор выделения сегмента и его свойства 73
2.2.2. Учет форматов представления сегмента 75
2.2.3. Представление решающего правила в форме графа 78
2.2.4. Проверка корректности построения решающего правила 81
Выводы по главе 83
Глава 3. Разработка модели декларативного описания выделяемого сегмента - 84
3.1. Анализ предметной области описания изображений 84
3.1.1. Категории, используемые для описания сегмента на изображении 85
3.1.2. Таксономии наиболее важных признаков 94
3.1.3. Примеры терминов, используемых для описания 98 3.2. Построение модели декларативного описания 100
3.2.1. Анализ требований к модели 100
3.2.2. Выбор выразительных средств 103
3.2.3. Основные сущности модели 104
3.2.4. Возможные варианты представления декларативного описания 107
3.2.5. Формальное представление модели 108
3.2.6. Элементарные операции над ГСО 111
3.2.7. Условия синтаксической правильности ГСО и алгоритм ее проверки 111
3.2.8. Условия семантической правильности ГСО и алгоритм ее проверки 113
3.2.9. Модельная непротиворечивость 114
3.3. Свойства декларативного описания 115
3.3.1. Изоморфизм между ГСО и решающим правилом 115
3.3.2. Алгоритм построения решающего правила по ГСО 118
3.3.3. Семантически эквивалентные преобразования ГСО 122
3.4. Расширение возможностей модели 126
3.4.1. Анализ выразительных средств модели 126
3.4.2. Понятийная свертка и подстановка 127
3.4.3. Стандартная подстановка «расположены рядом» 127
3.4.4. Стандартная подстановка «является границей» 128
Выводы по главе 129
Глава 4. Разработка методов оптимизации решающего правила
1 4.1. Критерий эффективности решающего правила 130
4.2. Обоснованность применения оптимизации 1 4.2.1. Понятие потоковой обработки 133
4.2.2. Критерий отказа от оптимизации 133
4.3. Оптимизация последовательности вызова алгоритмических блоков 135
4.3.1. Сравнение вычислительной сложности последовательного и квазипараллельного вариантов выделения сегмента
4.3.2. Оптимизация последовательности вызова для нескольких одноуровневых условий 137
4.4. Учет взаимозависимости признаков при оптимизации 141
4.4.1. Взаимное уменьшение диапазонов для зависимых признаков 141
4.4.2. Выделение и поглощение ослабленного условия 143
4.4.3. Выдвижение гипотез о подмножестве значимых признаков 146
4.5. Оптимизация поиска и выделения сцен 147
4.5.1. Операторы расширения и сжатия сегмента 147
4.5.2. Учет условий пространственной близости при оптимизации решающего правила 148
4.6. Оптимизация поиска и выделения областей 150
4.6.1. Стратегия разреженного поиска 150
4.6.2. Оператор наращивания областей 154
4.6.3. Зависимость коэффициента вычислительной сложности от стратегии перебора 158
4.6.4. Поиск неоднородных областей 159
4.7. Модель блока оптимизации 161
4.7.1. Продукционная модель 161
4.7.2. Интегральный алгоритм оптимизации 162
Выводы по главе 164
Глава 5. Экспериментальная проверка разработанной модели 165
5.1. Описание программного комплекса 1
5.1.1. Структура программного комплекса 165
5.1.2. Статистика программного комплекса 166
5.1.3. Главная форма программы 167
5.1.4. Блок отображения и редактирования сегментов 168
5.1.5. Блок отображения и редактирования решающего правила 170
5.1.6. Алгоритмические блоки для задания диапазона признака, оценки значения признака и сопоставления с диапазоном 171
5.1.7. Блок выполнения решающего правила 172
5.1.8. Блок построения декларативного описания 173
5.1.9. Блок формирования решающего правила по декларативному описанию 174
5.2. Испытания программного комплекса 175
5.2.1. Ручная сегментация 175
5.2.2. Нахождение диапазона признака по выделенному сегменту 177
5.2.3. Автоматическое формирование решающего правила по декларативному описанию 178
5.2.4. Построение сложного условия выделения сегмента 179
5.3. Исследование эффективности разработанных методов оптимизации 180
5.3.1. Оптимизация последовательности вызовов алгоритмических блоков 182
5.3.2. Оптимизация поиска и выделения областей 182
5.3.3. Оптимизация выделения неоднородных областей 183
Выводы по главе 185
Заключение 186
Литература 189
Введение к работе
В настоящее время идет активный процесс создания электронных справочников, атласов, энциклопедий и экспертных систем. Важную роль в представлении подобного рода знаний играют изображения. Однако специфика этой информации такова, что для создания «разумной» системы не достаточно просто отсканировать изображение. Как правило, необходимо наделить его семантическими ссылками, когда каждому типу участков изображения ставится в соответствие определенная подсказка или другая автоматическая реакция системы. Для реализации подобных систем, помимо самого изображения, используют одну или несколько «вспомогательных карт» . Каждая такая карта имеет размер, соответствующий размеру изображения и призвана ответить лишь на один вопрос - принадлежит ли выбранная точка к заданному типу объектов.
Если для каждого типа объектов вводится своя карта, то ее элементы могут быть бинарными, а если в одной карте совмещается информация о нескольких непересекающихся областях разных типов, то элементы карты должны быть целыми величинами, где для каждого типа выделен свой номер. Например, аэрофотоснимку земной поверхности могут быть поставлены в соответствие сразу несколько вспомогательных карт: «страны», «рельеф» (горы, низменности, плоскогорья и т.п.), а для микрофотографии клеток крови - несколько вспомогательных карт иного содержания: «типы клеток», «элементы клеток» (ядро, ядрышко, цитоплазма и т.д.) и т.п. Подготовка подобных вспомогательных карт является одним из классических примеров задачи сегментации изображений.
При подготовке к изданию в Новгородском Государственном университете электронной версии цитологического атласа [76], проблема автоматизации такого вида работ проявилась во всей своей полноте. Действительно, выделение вручную областей на нескольких сотнях изображений оказалось очень утомительной работой. Однако автоматизировать ее стандартными методами сегментации не удалось, так как выделяемые области не однотонны, а содержат достаточно сложную текстуру.
Если необходимо регулярно проводить сегментацию большого числа однотипных изображений, для этих целей оказывается рентабельным спроектировать специализированный программно-аппаратный комплекс. Примерами подобного подхода могут служить системы распознавания рентгеновских изображений грудной клетки [69]. В этом случае обучение системы, настройка ее параметров под выбранную задачу проводится в процессе разработки и не вызывает проблем у пользователя.
Однако сейчас все чаще встречаются задачи, для которых характерен «промежуточный» объем обрабатываемого материала. Т.е., с одной стороны данную задачу крайне дорого решать вручную, но ее объем еще недостаточен для того, чтобы было рентабельно разрабатывать специализированную систему. При этом в пределах отдельной задачи, обрабатываемые изображения являются в известном смысле однородными. В качестве примера подобных типовых задач можно упомянуть: Задачи на обработку последовательности кадров фильма или мультфильма, когда какого-то героя или сцену нужно выделить из имеющегося изображения и смонтировать на другом фоне, а Задачи на выделение заданных участков в сериях изображений
биомедицинских препаратов, полученных с микроскопа, а Задачи автоматического выделения областей при обработке
аэрофотоснимков, а Задачи выделения семантически однородных областей на изображениях из атласов и учебников при создании их электронных интерактивных версий. С другой стороны, условия семантической однородности выделяемых областей часто оказываются достаточно сложными, так как выделяемые участки могут содержать сложную текстуру. В этой ситуации стандартные методы автоматической сегментации оказываются недостаточными. Поэтому требуется создание системы, которую пользователь мог бы самостоятельно обучить решению конкретной задачи.
В данной работе предлагается подход, позволяющий пользователю быстро получать эффективные алгоритмы обработки и анализа изображений под задачи такого типа без привлечения элементов программирования.
На сегодняшний день существует множество алгоритмов, предложенных для решения задачи сегментации и анализа изображений. Однако большинство из них хорошо работают лишь при определенных явно или неявно подразумеваемых условиях. Многие алгоритмы требует от пользователя дополнительной настройки параметров. Естественна тенденция к перекладыванию специфических сложностей подбора и настройки алгоритмов на автоматизированную экспертную систему, дружественная оболочка которой позволяет ему вместо процедурного решения, т.е. определения последовательности и параметров вызова алгоритмов, задавать декларативное описание требуемого результата, на основе которого система самостоятельно строит и реализует процедурное решение.
Таким образом, целью данной работы является разработка и экспериментальная проверка принципов построения открытой автоматизированной системы, проводящей сегментацию изображений по заданному пользователем декларативному описанию выделяемого сегмента.
Для достижения данной цели необходимо было решить несколько задач:
о Провести анализ предметной области сегментации изображений и построить модель процесса сегментации.
о Провести анализ предметной области описания изображений, используемого при этом понятийного аппарата, и построить модель декларативного описания выделяемого сегмента.
о Разработать алгоритм построения и оптимизации решающего правила по заданному декларативному описанию.
о Создать экспериментальный программный комплекс сегментации изображений и проверить справедливость предложенных решений.
В первой главе проводится анализ задачи сегментации изображений и анализируются проблемы обучения автоматизированной системы сегментации изображений.
Во второй главе строится и исследуется модель процесса сегментации изображений по локальным данным. Предлагается принцип построения открытой автоматизированной системы. Вводится понятие алгоритмического блока и решающего правила. Строится модель автоматизированной системы сегментации изображений.
Третья глава посвящена наиболее сложной проблеме - построению модели декларативного описания требуемого результата. Такая модель должна одновременно удовлетворять нескольким достаточно противоречивым требованиям.
Проводится анализ предметной области описания изображений. На основании проведенного анализа выбирается наиболее удобная форма для декларативного описания, строится и исследуется его формальная модель. Описывается алгоритм автоматического формирования решающего правила по заданному декларативному описанию.
В четвертой главе исследуются возможности для оптимизации решающего правила. Вводится критерий оптимизации. Предлагается ряд оптимизирующих правил. Строится модель оптимизации решающего правила и предлагается алгоритм такой оптимизации.
В пятой главе описывается практическая реализация программного комплекса и методика проведения экспериментов для проверки теоретических положений, полученных в рамках данной работы. Приводятся и анализируются результаты проведенных экспериментов.
В заключении перечисляются основные научные и практические результаты диссертационной работы, рассматриваются направления дальнейших научных исследований.
