Метод идентификации объектов на основе логических описаний деформируемых моделей Авраменко Юрий Владимирович

Содержание к диссертации

Введение

Глава 1. Обзор моделей, методов и алгоритмов, применяемых для идентификации объектов на растровых изображениях 13

1.1. Содержательная постановка задачи идентификации объектов 13

1.2. Логические методы идентификации объектов 15

1.3. Применение деформируемых моделей в задаче идентификации объектов 23

1.4. Выделение и оценка признаков на растровых изображениях

1.4.1. Теория нечетких множеств 26

1.4.2. Метод описания текстуры на основе локальных бинарных шаблонов 27

1.4.3. Метод опорных векторов 30

1.5. Методы и алгоритмы, применяемые в работе для уменьшения

вычислительной сложности алгоритма идентификации объектов 31

1.5.1. Метод ветвей и границ 31

1.5.2 Алгоритм поиска А 31

1.5.3. Метод обнаружения точечных особенностей 32

Выводы по главе 1 34

Глава 2. Метод идентификации объектов на основе логических описаний деформируемых моделей 35

2.1. Логические описания деформируемых моделей 36

2.2. Алгоритм идентификации объектов 39

2.3. Язык пространственных запросов SOQL 42

2.4. Алгоритмы уменьшения вычислительной сложности 47

2.4.1. Отсечение слабовыраженных признаков 47

2.4.2. Отсечение неперспективных ветвей логического вывода 48

2.4.3. Анализ пространственных ограничений 49

2.4.4. Выделение областей идентификации объектов 54

2.4.5. Сужение множества точек старта алгоритма идентификации 58

Выводы по главе 2 59

Глава 3. Реализация метода идентификации на основе логических описаний деформируемых моделей 61

3.1. Структура программной системы нечеткого поиска объектов на растровых изображениях 61

3.1.1. Модуль интерпретации 62

3.1.2. Модуль встроенных предикатов 68

3.1.3. Модуль трансляции текста программы во внутренний формат 80

3.1.4. Модуль ввода-вывода 82

3.1.5. Подключаемые библиотеки 85

3.2. Реализация методов уменьшения вычислительной сложности 86

3.2.1. Метод отсечения неперспективных ветвей логического вывода 86

3.2.2. Формирование множества точек старта идентификации объекта 88

3.2.3. Выделение областей идентификации по текстуре 89

3.2.4. Реализация оператора LBP

3.3. База знаний для идентификации объектов 92

3.4. Интерфейс пользователя 95

3.5. Инструмент создания логического описания деформируемой модели 98

3.6. Методика применения метода идентификации объектов на основе логических описаний деформируемых моделей 101

3.7 Реализация метода в виде WPS сервиса обработки данных дистанционного зондирования Земли 101

Выводы по главе 3 103

Глава 4. Апробация метода идентификации на основе логических описаний деформируемых моделей 105

4.1 Применение метода на тестовых примерах 105

4.2. Идентификация точечных источников антропогенного загрязнения воздуха в г. Улан-Баторе 111

4.3. Актуализация цифрового топографического плана города Иркутска 113

Заключение 117

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

Список литературы 122

• Применение деформируемых моделей в задаче идентификации объектов
• Язык пространственных запросов SOQL
• Модуль трансляции текста программы во внутренний формат
• Методика применения метода идентификации объектов на основе логических описаний деформируемых моделей

Введение к работе

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

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

антропогенных изменений на поверхности Земли по мультиспектральным данным ДЗЗ. Среди зарубежных исследователей можно отметить: U. Grenander, который предложил теорию шаблонов; M. Kass, D. Terzopoulos, предложивших использовать деформируемые модели для учета пространственных расположений фрагментов границы объектов. Идея применения деформируемых моделей получила развитие в работах: D.J. Williams, и M. Shah, разработавших упрощенную и дискретную версию применения деформируемых моделей, в которой применяются методы локальной

оптимизации, чтобы достичь оптимального решения; A.A. Amini, T.E. Weymouth, R.C. Jain, использовавших методы динамического программирования, что позволило применить более общий класс ограничений формы объектов.

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

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

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

1. на основе анализа мирового и российского опыта разработки методов, программно-алгоритмического обеспечения и информационных систем (ИС) идентификации объектов на растровых изображениях определить требования к создаваемому методу идентификации объектов;

2. разработать язык пространственных запросов Spatial Object Query Language (SOQL) для идентификации объектов на космических снимках высокого и сверхвысокого пространственного разрешения;

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

4. создать ПС, позволяющую проводить идентификацию объектов на растровых изображениях в соответствии с запросами на языке SOQL;

5. провести реализацию и апробацию разработанного метода.

Объект исследования – объекты, их признаки и отношения на растровых изображениях.

Предмет исследования – методы, алгоритмы и ПС идентификации объектов на растровых изображениях.

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

Научная новизна диссертационной работы.

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

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

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

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

Практическая значимость полученных результатов. Результаты

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

1. грантов РФФИ (№ 13-07-12080 офи_м, 14-47-04125 р_сибирь_а, 14-07-00166 а, 16-07-00411 а, 16-07-00554 а, 16-37-00110 мол_а);

2. программы Президиума РАН «Фундаментальные проблемы математического моделирования»;

3. программы № 43 Президиума РАН;

4. междисциплинарного интеграционного проекта № 74 СО РАН;

5. проекта № 1.4 программы ИНЦ СО РАН;

6. проекта «Моделирование загрязнения атмосферы г. Улан-Батора в зависимости от выбросов промышленных предприятий и автотранспорта, создание программного комплекса на основе ГИС-технологий».

При выполнении диссертационной работы, получены свидетельства (ФИПС) о государственной регистрации программы для ЭВМ: «Интерпретатор языка пространственных запросов SOQL» № 2016663524 от 12.12.2016 [4], «Программная система нечеткого поиска объектов на растровых изображениях» № 2014616587 от 27.06.2014 [5].

«Программная система нечеткого поиска объектов на растровых

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

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

источников загрязнения по спутниковому снимку г. Улан-Батор в рамках совместного проекта с учреждениями академии наук Монголии «Моделирование загрязнения атмосферы г. Улан-Батора в зависимости от выбросов промышленных предприятий и автотранспорта, создание программного комплекса на основе ГИС-технологий» и междисциплинарного интеграционного проекта № 74 СО РАН. Полученные результаты использовались для выработки рекомендаций администрации г. Улан-Батор по уменьшению антропогенного загрязнения воздуха. Программная система

применялась в задаче актуализации цифрового топографического плана (ЦТП) города Иркутска на основе космоснимка. Применение разработанного метода позволило сократить время работы пользователей и поставить на учет градостроительные объекты города. Результаты диссертационной работы также используются в учебном процессе на кафедре «Информационных технологий» Института математики, экономики и информатики Иркутского государственного университета (ИМЭИ ИГУ) в преподавании специальных курсов студентам 3-4 курсов дневного отделения.

Положения, выносимые на защиту.

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

2. Язык пространственных запросов SOQL для формирования логических описаний деформируемых моделей.

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

4. Программная система нечеткого поиска объектов на растровых изображениях.

Соответствие специальности. Диссертационная работа соответствует пунктам 3-5, 7 паспорта специальности 05.13.17 «Теоретические основы информатики»:

п. 3. Исследование методов и разработка средств кодирования информации в виде данных. Принципы создания языков описания данных, языков манипулирования данными, языков запросов. Разработка и исследование моделей данных и новых принципов их проектирования;

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

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

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

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

Апробация результатов работы. Основные результаты диссертации докладывались и обсуждались на четырех международных, трех всероссийских и пяти региональных конференциях: III, IV Всероссийская конференция «Математическое моделирование и вычислительно-информационные технологии в междисциплинарных научных исследованиях» (г. Иркутск, 2013-2015 гг.); Ляпуновские чтения (г. Иркутск, 2013-2016 гг.); XXXVIII Дальневосточная Математическая Школа-Семинар имени академика Е.В. Золотова (г. Владивосток, 2014 г.); Шестая международная конференция «Системный анализ и информационные технологии» (г. Калининград, 2015 г.); III Российско-монгольская конференция молодых ученых по математическому моделированию, вычислительным технологиям и управлению (п. Ханх, Монголия, 2015 г.), конференция Современные информационные технологии для научных исследований в области наук о Земле (г. Южно-Сахалинск, 2016); 26-я международная конференция GraphiCon2016 (г. Нижний Новгород, 2016), XVII Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям (г. Новосибирск, 2016).

Личный вклад соискателя. Все выносимые на защиту результаты получены соискателем лично. В наиболее значимых работах [2-5], опубликованных в соавторстве, лично соискателем разработаны:

1. язык пространственных запросов SOQL;

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

3. программная система нечеткого поиска объектов на растровых изображениях.

Публикации. Научные результаты, в полном объеме отражающие содержание диссертации, опубликованы в 9 работах, включающих: 1 коллективную монографию;

2 статьи в изданиях из перечня ВАК; 2 свидетельства (ФИПС) о государственной регистрации программ для ЭВМ; 4 статьи, опубликованных в других изданиях.

Благодарности. Автор выражает глубокую благодарность научному руководителю академику И.В. Бычкову за руководство диссертационной работой и помощь в подготовке рукописи, к.т.н. Р.К. Фдорову, д.т.н. Г.М. Ружникову за обсуждение, консультации и полезные замечания при выполнении и оформлении диссертационной работы.

Структура и объем диссертации. Диссертация состоит из: введения, 4 глав, приложения, заключения, списка сокращений и терминов, списка литературы из 76 наименований. Иллюстративный материал состоит из 53 рисунков и 2 таблиц. Общий объем составляет 133 страницы.

Применение деформируемых моделей в задаче идентификации объектов

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

Основными проблемами, возникающими при решении задач идентификации объектов на растровых изображениях, являются: 1) формирование признаков, качество идентификации сильно зависит от того, насколько хорошо подобраны признаки для описания изображения [12]; 2) необходимость в выполнении перебора большого количества вариантов, что требует больших вычислительных расчетов. Перебор позволяет обеспечить устойчивость к инвариантности изображения искомого объекта, шуму, сдвигу, повороту и масштабированию. Рассмотрим существующие методы с точки зрения их применения для идентификации объектов по спецификации пользователя. Разработано большое количество методов идентификации объектов, основанных на обучении [2, 55, 75]. С одной стороны подобные системы довольно легко использовать для идентификации некоторых классов объектов. Для этого необходимо сформировать набор прецедентов и выполнить обучение. С другой стороны при идентификации объектов с определенной формой сложно сформировать полный набор прецедентов, представляющих все возможные изменения формы и положения объектов, с учетом изменения освещенности шума и т.п. Поэтому для идентификации объектов с определенной формой лучше предоставить пользователю возможность описать модель объект.

Для идентификации объектов широко используются методы, основанные на применении деформируемых моделей [31–33]. В этих методах пользователь может указать модель объекта с помощью множество точек, сплайнов, и т.д. Применение деформируемых моделей позволяет выбирать положение границ объектов не только на основе локальных характеристик, но и с учетом относительного пространственного расположения фрагментов. Соответствие положения объекта и деформируемой модели оценивается функцией энергии [34]. Общим недостатком существующих методов в рамках деформируемых моделей является сложность задания модели идентифицируемого объекта.

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

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

Постановка задачи идентификации объектов на изображении при помощи логических методов по [36]. Пусть Q - множество w = w1, ...,w,J идентифицируемых объектов, где w1,...,wt - признаки. Подмножество т a w -подмножество признаков объекта. Набор предикатов р1,...,рп - характеристики признаков объекта w и отношений между ними. Множество Q разбивается на М классов (возможно пересекающихся): Q = \}k=1Q1c.

Логическим описанием объекта w является формула 4(w), построенная на основе атомарных формул вида р{{т), где w1, ...,wt являются не связанными переменными. Задача идентификации формулируется следующим образом: найти такой объект w, который приводит формулу Аумп к истине. В работе [36] исследуется возможность применения языка Пролог для решения задачи идентификации объекта. Авторы используют интерпретатор языка Пролог без каких-либо модификаций и работают с изображениями без предварительной обработки. Для того чтобы интерпретатор Пролога смог работать с изображением необходимо сформировать базу фактов. База фактов формируется из значений яркости пикселей изображения. Каждый факт задается предикатом вида р (х.,у.) , где р еі-4еі-зеі-2еі-іеіеі+іеі+2еі+зеі+4 \ г -W г ei_Aei_?Iei_2ei_leieMei+2eMei+A описание цвета пикселя е., (хг.,_уг.) - координаты пикселя е.. Такие имена используются для уменьшения количества фактов с одинаковыми именами, это позволяет ускорить процедуру унификации предикатов. Идентифицируемый объект описывается функцией вида f е.,(Х,Г)1,\е.АХ.,Y) ,... , где е. является массивом значений яркости центрального и соседних пикселей в восьмисвязной окрестности с центром заданного координатами (Хг., ). Алгоритм идентификации объекта на изображении состоит в том, чтобы для каждого элемента ег,(Хг,1 ) функции f выполнить унификацию предиката р (х.,у.). Решением будет список result, содержащий пары ґеі-4еі-Зеі-2еі-Іеіеі+Іеі+2еі+Зеі+4 V г -W х,Х , у,У , которые определяют положение идентифицируемого объекта на изображении. Пары добавляются в список во время унификации предикатов, если выполняются условия проверки на возможность включения пары в список. Суть проверки заключается в том, чтобы список пар не содержал повторений. На рисунке 1 представлен результат идентификации объекта методом [36].

Язык пространственных запросов SOQL

На вход алгоритма идентификации подаются следующие входные данные: изображение, пользовательское описание объекта (логическое описание деформируемой модели). В процессе работы алгоритма идентификации происходит извлечение признаков объектов из изображения, проводится перебор их возможных сочетаний, удовлетворяющих описанию модели идентифицируемого объекта. На выходе получаем множество решений со значением функции энергии меньше порога, соответствующих запросу пользователя. Перебор возможных сочетаний признаков осуществляется поиском в глубину. На каждом шаге происходит извлечение признаков при помощи встроенных предикатов, для каждого встроенного предиката вычисляется значение функции принадлежности. Релевантность каждого найденного решения оценивается значением функции энергии. Рассмотрим псевдокод алгоритма идентификации объекта. Для упрощения восприятия алгоритма и определения вычислительной сложности рекурсивный алгоритм представлен с помощью вложенных циклов. Обозначим через J - множество переменных, используемых в правиле, Уг с У - подмножество переменных, унифицируемых предикатом Р.. Вход: описание объекта P:—Pl,...,PCl,...,C,L, /л, J = \JJi. 2=1 Выход: список найденных объектов list. алгоритм идентификации начало вычисление порога д; формирование базы ограничений С1,...,Ст; цикл для всех унификаций Jl Pl выполнить если ограничения С1,...,Ст не выполняются тогда продолжить; конец условия вычисление порога jun ; цикл для всех унификаций Jn Pn выполнить если ограничения С1,...,Ст не выполняются тогда продолжить; конец условия вычислить значение функции энергииL; если значение функции энергии объекта L L тогда добавить объект в список list; конец условия конец цикла конец цикла конец алгоритма идентификации На рисунке 6 приведена иллюстрация работы алгоритма идентификации. Вершина P . - голова правила. Вершины Pi - возможные варианты унификации предиката с номером i в теле правила P, Lє[0;і]. Вершины с оценками соответствуют извлеченным признакам объекта и их значениям функции принадлежности. Ребра определяют последовательность унификации предикатов. Все пути от корневой вершины до конечной являются решениями, каждому решению соответствует значение функции энергии L. Под каждой веткой расположены значения функции энергии для соответствующего пути решения. Решения со значением функции энергии L L добавляются в список.

Сложность алгоритма идентификации объектов зависит от наличия рекурсии в правилах, количества и сложности используемых предикатов. Если в наборе правил, описывающих модель объекта, имеется рекурсия, то сложность алгоритма идентификации может быть экспоненциальной. Рассмотрим случай, когда набор правил не содержит рекурсивного определения. Допустим, что все дочерние предикаты являются встроенным предикатом line (у него сложность O(n ) среди всех встроенных предикатов), то сложность алгоритма идентификации будет O{n m) = O(n \х.O(n )2х...хO(n )m. Соответственно если дочерние предикаты не встроенные, то сложность ограничена полиномом O(n 1+ 2+ + m) = O(n \ х O(n 2 )2 х... х O(n m )m от количества пикселей на изображении.

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

Язык CLP Пролога изначально не ориентирован на работу с изображениями и соответственно, синтаксис языка не адаптирован для описания объектов с использованием пространственных ограничений. Интерпретатор CLP Пролога не позволяет эффективно осуществлять перебор возможных решений на основе анализа пространственных ограничений и функции энергии. Поэтому произведена адаптация языка Пролог и на его основе разработан язык пространственных запросов SOQL. Для реализации языка SOQL язык Пролог дополнен встроенными предикатами, функциями, пространственными ограничениями. Синтаксис языка SOQL состоит из предложений трех типов: факты, правила, запросы. Синтаксической единицей языка является терм. Термы бывают простые и составные (структуры), простые делятся на константы и переменные, константы в свою очередь делятся на атомы и числа. На рисунке 7 представлена иерархия типов данных.

Константы - поименованные конкретные объекты или отношения. Атомы - неделимая осмысленная единица. Атомы задаются: 1) последовательностью букв, цифр и символа подчеркивания «_», начинаются со строчной буквы; 2) специальными символами: «.», «,», «», «(», «)», «:-», «?», «[», «]». 3) арифметическими операторами: « + », «-», « », «/». 4) операторами сравнения: « = », « », « », « », « », « ». Числа: 1) целые в диапазоне от - 2147483648 до + 2147483647; 2) действительные в диапазоне от 1Е - 307 до 1Е + 308. Переменные служат для обозначения объектов, значения которых меняются в ходе выполнения программы. Имена переменных могут начинаться с: прописной буквы; символа подчеркивания.

Модуль трансляции текста программы во внутренний формат

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

Рассмотрим работу модуля на примере правила angle(A,B,C):– line(A,B), line(B,C). angle(A,B,C) будем называть головой правила. Предикаты line(A,B), line(B,C) будем называть дочерними angle(A,B,C) или телом правила. Для каждой унификации предикатов создается фрейм, как изображено на рисунке 19. edges(A,B,C) є sum record p— line(A,B) line (В, С)

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

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

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

Реализация встроенных предикатов осуществлена в соответствии со специальным программным интерфейсом. Такой подход позволит в дальнейшем реализовать другие предикаты без изменения основного кода интерпретатора. Встроенные предикаты реализованы в виде функции, которая принимает на вход контекст. Контекст содержит текущее состояние унификации предиката, список переменных и их значений V = {V1,...,Vn}, список ограничений C = {C1,...,Cm} и пороговое значение функции принадлежности ju. Для каждого вызова функция, реализующая встроенный предикат, возвращает: измененный контекст, унифицированные значения переменных, значение функции принадлежности и флаг, обозначающий, что унификация прошла успешно. Унифицированные значения переменных должны удовлетворять пространственным ограничениям, и значение функции принадлежности должно быть выше порогового ju ju. Унификация предиката (вызов соответствующей функции) происходит до тех пор, пока флаг не станет отрицательным, т.е. перебор всех возможных сочетаний значений переменных закончен. После чего управление передается в модуль интерпретации.

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

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

Из множества альтернатив расположения объектов для уменьшения времени работы алгоритма идентификации объектов необходимо исключать варианты, заведомо не содержащие решения. В процессе идентификации найденные решения (объекты) сохраняются в список. При логическом выводе очередного решения на каждом шаге унификации встроенных предикатов происходит проверка на пересечение с уже найденными объектами. Проверку на пересечение двух объектов можно совершать различными способами. В данной работе предлагается проводить проверку пересекающихся объектов по бинарной маске (0 означает, что в текущей позиции нет границы объекта, 1 – проходит граница) представленной в виде матрицы. Размер матрицы равен размеру изображения. Элементом матрицы является структура, содержащая два поля: Est – значение функции энергии, Obj – указатель на объект, к которому относиться элемент. Расположение объектов на изображении определяется расположением элементов матрицы с непустым указателем Obj. Для того чтобы задать положение объектов в матрице используется алгоритм рисования прямой Брезенхема. На рисунке 29а показан результат рисования линий алгоритмом Брезенхема. В этом случае два пересекающихся отрезка не имеют общих точек, поэтому чтобы вычислить их пересечение, придется проводить дополнительные вычисления. На рисунке 29б показан модифицированный алгоритм рисования прямой, в данном случае пересечение двух отрезков определяется без дополнительных вычислений.

Алгоритм рисования прямой Брезенхема: а – оригинальный вариант, б – модифицированный. Серый – пустые элементы матрицы; черный – координаты точек начала и конца отрезков; синий и красный – элементы, определяющие положение отрезков; белый – общие элементы На рисунке 30а изображен случай пересечения двух объектов. Пусть объект, изображенный синим, был идентифицирован ранее, а идентификация красного объекта происходит с положения элемента, обозначенного черным и расположенного возле начала стрелки, указывающий направление поиска признаков. Когда идентификация красного объекта дойдет до общих элементов, произойдет сравнение значения функции энергии синего объекта с потенциально возможным значением красного. Если значение функции энергии синего элемента окажется лучше, то идентификация красного объекта прекратиться. Фиолетовым цветом изображены элементы, которые будут исключены из дерева решений, что показано на рисунке 30б.

Представление расположения объектов. Серый – пустые элементы матрицы; черный – координаты точек фрагментов контура; синий и красный – элементы, определяющие положение объектов; белый – общие элементы Добавление представлений объектов в матрицу осуществляется посредством вызова метода SetRecord. Последовательно определяются элементы матрицы, в которые заносится значение функции энергии объекта и указатель на объект. Удаление представлений объектов из матрицы осуществляется посредством вызова метода ClearRecord. Последовательно определяются элементы матрицы, в которых значение функции энергии объекта приравнивается к нулю и указатель на объект принимает пустое значение. Проверка на пересечение объектов осуществляется при помощи метода GetRecord. Последовательно определяются элементы матрицы, которые будут соответствовать расположению объекта, если среди них встретится элемент, указывающий на другой объект, то произойдет сравнение значений функций энергии объектов. формирования множества точек старта реализован детектор углов Харриса. Детектору на вход подается изображение и порог значения функции отклика R. Функция отклика вычисляется по формуле (13). В результате на выходе получается множество угловых точек, обозначим его AH ={P1(R),...,Pi(R),...,Pm(R)}. Размер данного множества Для может измеряться десятками тысяч и более. Для его уменьшения можно применять различные способы. Рассмотрим два из них. Первый - угловая изоляция, применяется для выбора лучшей точки из числа обнаруженных в некоторой окрестности пикселя. Угловая изоляция может привести к потере решений. Второй использование порога на значение функции отклика R R. Возникает вопрос выбора порогового значения. Использовать константу для значения R не целесообразно, так как данный прием может привести к образованию пустого множества. Поэтому необходимо предусмотреть другой механизм для сокращения числа обнаруженных точек при помощи выбора порогового значения.