Содержание к диссертации
Введение
1 Современное состояние проблемы распознавания объектов 11
1.1 Проблема распознавания объектов 11
1.2 Основные методы распознавания объектов 16
1.2.1 Классификация методов распознавания объектов 16
1.2.2 Интенсиональные методы распознавания объектов . 18
1.2.3 Экстенсиональные методы распознавания объектов . 28
1.2.4 Методы совместной классификации 32
1.2.5 Сравнительный анализ известных методов распознавания объектов 34
1.3 Выводы. Цели и задачи исследования 41
2 Иерархический итерационный метод распознавания объектов на основе анализа многомерных данных 44
2.1 Разработка иерархического итерационного метода распознавания объектов 44
2.1.1 Общая постановка задачи распознавания объектов и определения их положения и ориентации в пространстве 44
2.1.2 Основные принципы иерархического итерационного метода распознавания объектов 44
2.1.3 Алгоритм иерархического итерационного метода распознавания объектов 47
2.2 Разработка алгоритмического обеспечения иерархического итерационного метода распознавания объектов 56
2.2.1 Алгоритм иерархической оптимизации многомерной функции 57
2.2.2 Алгоритм иерархического сопоставления 68
2.2.3 Алгоритм расчёта критерия качества с использованием матричного представления исходных данных 73
2.2.4 Алгоритм деформации прототипов распознаваемых объектов 78
2.2.5 Алгоритм итерационного сопоставления 82
2.2.6 Алгоритм иерархизации прототипов распознаваемых объектов 85
2.3 Анализ преимуществ разработанных алгоритмов 88
2.4 Выводы по второй главе 90
3 Разработка систем распознавания объектов для решения практических задач 92
3.1 Методика разработки системы распознавания объектов 92
3.2 Разработка системы распознавания положения и ориентации объектов для регистрации медицинских изображений 96
3.2.1 Постановка задачи регистрации медицинских изображений 96
3.2.2 Описание архитектуры системы распознавания объектов для решения задачи регистрации медицинских изображений 98
3.2.3 Экспериментальные результаты 108
3.3 Разработка системы распознавания объектов в задаче распознавания текста 113
3.3.1 Постановка задачи распознавания текста 113
3.3.2 Описание архитектуры системы распознавания объектов для решения задачи распознавания текста 115
3.3.3 Экспериментальные результаты 123
3.4 Разработка системы распознавания объектов в задаче автоматического извлечения деталей из контейнера 128
3.4.1 Постановка задачи распознавания множества объектов для системы автоматического извлечения деталей из контейнера 128
3.4.2 Описание архитектуры системы распознавания объектов для решения задачи автоматического извлечения деталей из контейнера 129
3.4.3 Экспериментальные результаты 137
3.5 Выводы по третьей главе 140
4 Разработка и экспериментальное исследование прикладных программных систем, основанных на иерархическом итерационном методе распознавания объектов 143
4.1 Прикладная программная система для решения задачи регистрации медицинских изображений 146
4.2 Прикладная программная система для решения задачи распознавания текста в промышленных системах 147
4.3 Прикладная программная система для решения задачи распознавания объектов в системе автоматического извлечения деталей из контейнера 148
4.4 Выводы по четвёртой главе 150
Заключение 152
Список использованных источников
- Проблема распознавания объектов
- Разработка иерархического итерационного метода распознавания объектов
- Разработка системы распознавания положения и ориентации объектов для регистрации медицинских изображений
- Прикладная программная система для решения задачи регистрации медицинских изображений
Введение к работе
Актуальность темы
Одной из основных задач, которую человек постоянно решает в процессе своей жизнедеятельности, является задача распознавания объектов. Эта задача эффективно решается человеком как на бытовом уровне (например, при чтении книг, при разговоре с собеседником), так и при выполнении своих профессиональных обязанностей (например, при визуальном контроле
г-
за качеством производства, при поиске и идентификации объектов на изображениях и т.п.). При этом, при решении задачи распознавания, человек является наиболее эффективной и универсальной системой, т.е. человек способен распознавать не только конкретные, но и абстрактные образы (например, обнаружить логическую связь). Именно поэтому создание эффективных автоматических систем распознавания объектов, явлений, ситуаций и процессов, которые по своим возможностям приближались бы к возможностям человека, является одной из приоритетных задач в области разработки искусственного интеллекта, привлекающей внимание многих исследователей.
Задача автоматического распознавания объектов известна довольно давно, а первые попытки её решения предпринимались уже в начале 70-х годов прошлого века. По данной тематике опубликовано и выпущено множество статей и книг, разработан целый ряд методов распознавания и спроектированных на их основе автоматических систем, которые находят широкое применение в различных областях.
Вместе с тем, несмотря на высокий уровень исследований в этой области, создание эффективно работающих систем для распознавания объектов остаётся сложной, до конца не решённой проблемой. Существует ряд практических задач, которые не могут быть эффективно решены с помощью известных методов и алгоритмов распознавания. Фундаментальные исследования по данной проблеме сегодня практически не ведутся, а конкретные научные разработки имеют своей целью лишь решение узкоспециализированных задач. Основная причина этого заключается в отсутствии эффективных методов распознавания объектов, способных решать задачи различных классов, особенно в реальном времени. Отсюда вытекает и основная проблема существующих систем распознавания: каждая такая система жёстко ориентирована на специфику обрабатываемых данных и распознаваемых объектов. При изменении исходных данных либо классов распознаваемых объектов необходимо адаптировать систему к изменившимся условиям, если это возможно, а также проводить длительное переобучение на новых наборах тестовых данных. Само распознавание может занимать, как правило, довольно значительное время.
Другой характерной особенностью существующих систем и методов распознавания объектов является невозможность либо неточность одновременного распознавания объекта и определения его положения и ориентации в пространстве либо по отношению к другим объектам.
Одним из путей решения вышеназванных проблем является разработка нового метода распознавания объектов, основанного на комбинации методов сопоставления с образцом и использовании оптимизационных алгоритмов. В основе этого подхода лежит идея объединения различных методов сопоставления с использованием общей математической модели задачи распознавания объектов на основе анализа многомерных данных, не зависящей от характера обрабатываемых данных, а также от признаков распознаваемого объекта.
Однако, такой подход требует решения ряда задач, связанных с оптимизацией длительности и сложности процедуры обучения, сложности процедуры построения набора признаков распознаваемого объекта, длительности процедуры сопоставления и возможности распознавания объектов на искажённых и зашумлённых данных. Таким образом, тема диссертационной работы, связанная с разработкой универсального метода распознавания объектов на основе анализа многомерных данных, является актуальной.
Цель и задачи исследования
Целью диссертационной работы является повышение скорости, точности и надёжности распознавания объектов и определения их положения на множестве многомерных данных на основе разработки и использования нового иерархического итерационного метода.
Для достижения указанной цели требуется решить следующие задачи:
Разработать метод распознавания объектов на основе анализа многомерных данных, позволяющий одновременно определять класс объектов, их положение и ориентацию в пространстве.
Разработать алгоритмическое обеспечение для реализации предложенного метода распознавания объектов.
Разработать архитектуру системы распознавания объектов, основанную на предложенном методе, а также методику её практического применения при решении конкретных задач.
Разработать программное обеспечение, реализующее предложенный метод распознавания объектов.
Оценить эффективность применения предложенного метода распознавания объектов при решении ряда практических задач.
Научная новизна
В диссертационной работе разработан иерархический итерационный метод распознавания объектов. При этом получены следующие результаты, обладающие научной новизной:
1. Предложен метод распознавания объектов на множестве многомерных данных, новизна которого состоит в комбинации метода сопоставления с алгоритмами оптимизации, а также в интерпретации метода сопоставления, которая заключается в обнаружении и локализации объекта, заданного прототипом, на полном множестве многомерных данных. Разработанный метод обладает высокой устойчивостью к шумам, инвариантен к физической природе исходных данных и распознаваемых объектов, а также не только значительно увеличивает вероятность верного распознавания объектов и повышает точность определения их положения и ориентации в пространстве, но и сокращает время обучения и распознавания, что позволяет разрабатывать системы распознавании объектов, способные решать практические задачи, такие как регистрация медицинских изображений, распознавание текста в промышленных системах и автоматическое извлечение деталей из контейнера.
2. Разработано оригинальное алгоритмическое обеспечение, состоящее из системы взаимосвязанных алгоритмов и процедур, включающих в себя иерархическую оптимизацию, иерархическое сопоставление, расчёт критерия качества с использованием матричного представления исходных данных, деформацию прототипов распознаваемых объектов, итерационное сопоставление и иерархизацию прототипов распознаваемых объектов. Разработанные процедуры позволяют повысить точность и сократить время распознавания объектов.
Практическая значимость результатов
Разработана архитектура универсальной системы распознавания объектов, основанная на предложенном иерархическом итерационном методе распознавания, а также методика её использования при решении различных классов практических задач.
Разработано прикладное программное обеспечение на базе языка С++ с использованием кроссплатформенной библиотеки обработки изображений ОрепСУ, реализующее предложенный иерархический итерационный метод распознавания объектов и эффективно решающее широкий круг задач в рамках реальных промышленных систем, включая задачи регистрации медицинских изображений, распознавания текста и автоматического извлечения деталей из контейнера.
при решении задачи регистрации медицинских изображений обеспечивается уменьшение времени распознавания по сравнению с классическим методом сопоставления и методом Покрандта в 7,2 и 1,15 раз соответственно, а также повышение точности определения положения на 19,5% и 8,5% и увеличение количества верных результатов в 2,3 и 1,3 раза;
при решении задачи распознавания текста обеспечивается увеличение количества верных результатов в 1,8 раза (на 44,1%) по сравнению с современными программными системами распознавания текста, что составило 99,7% от всего количества изображений;
при решении задачи распознавания объектов в системе автоматического извлечения деталей из контейнера обеспечивается уменьшение времени распознавания по сравнению с классическим методом сопоставления в 7,2 раза, повышение точности определения положения на 16,8% (в 1,2 раза) и увеличение количества верных результатов в 2,2 раза.
Иерархический итерационный метод распознавания объектов на основе анализа многомерных данных.
Алгоритмическое обеспечение иерархического итерационного метода распознавания объектов.
Архитектура универсальной системы распознавания объектов, основанная на предложенном иерархическом итерационном методе распознавания.
Прикладное программное обеспечение, реализующее иерархический итерационный метод распознавания объектов.
Результаты сравнительного анализа эффективности иерархического
VII-X международных научных конференциях "Компьютерные науки и информационные технологии" (Карлсруэ, Германия, 2006; Уфа, 2005, 2007; Анталия, Турция, 2008);
международной конференции по робототехнике "Robotik 2008" (Мюнхен, Германия, 2008);
семинарах в Институте управляющих вычислительных систем и робототехники Технического университета Карлсруэ (Германия, 2007, 2008).
задачи распознавания единичного объекта, т.е. отнесение объекта к одному из классов;
задачи поиска и распознавания множества объектов, т.е. определение положения и ориентации объектов, информация о существовании которых отсутствует, а также их классификация. Данную подзадачу также называют задачей анализа сцены.
область исходных данных, выделенная таким классификатором и отнесённая к какому-либо объекту, не связана с координатами распознанного объекта;
в некоторых случаях исходные данные содержат области, не связанные друг с другом, но относящиеся к одному объекту, что приводит к появлению ложных объектов;
иногда области, относящиеся к различных объектам одного класса, могут оказаться связанными, что приводит к потере объекта;
области, относящиеся к объектам разных классов, могут находиться вблизи друг друга, что приводит к потере объекта или его неверной классификации.
Задача регистрации медицинских изображений, которая заключается в анализе томограмм каких-либо органов или частей тела и поиске за приемлемое время аналогичных томограмм в атласе (базе данных томограмм) для последующей постановки диагноза или в совмещении томограмм другого типа для этого же органа (например, компьютерной и магниторезонансной томограмм).
Задача распознавания текстов в промышленных системах, которая осложняется сильными помехами, дефектами и искажениями символов.
Задача автоматического извлечения деталей из контейнера, которая требует распознавания множества объектов и определении их положения и ориентации среди перекрывающих друг друга объектов, относящихся к разным классам.
при решении задачи распознавания объектов нежелателен процесс повторного обучения или модификации, даже в случае изменения набора распознаваемых объектов;
необходимо распознавать не только объекты, но и определять их положение в пространстве, ориентацию и взаимное расположение;
необходимо распознавать объект в режиме реального времени (задачи распознавания текста в промышленных системах и автоматического извлечения деталей из контейнера).
способность эффективно распознавать объекты без повторного обучения и модификации метода в случае изменения набора распознаваемых объектов;
способность распознавать не только объекты, но их положение в пространстве, ориентацию и взаимное расположение;
способность распознавать объект в режиме реального времени.
методы распознавания, основанные на теории принятия решений. Данные методы используют количественные дескрипторы для распознавания объектов, например, такие как длина, площадь, текстура;
структурные методы. Данные методы используют качественные дескрипторы, например, реляционные.
методы сопоставления {template matching). Данные методы распознают объект, сопоставляя его с образцом или шаблоном из базы данных;
статистические методы {statistical pattern recognition). Данные методы используют статистические свойства объектов, например, функцию плотности распределения вероятностей и т.п.;
нейронные сети;
структурные и синтаксические методы (syntactic pattern recognition). Данные методы используют при распознавании логические правила или грамматики.
методы, основанные на принципе разделения;
статистические методы;
методы, построенные на основе потенциальных функций;
методы вычисления оценок (голосования);
методы, основанные на исчислении высказываний, в частности на аппарате алгебры логики.
интенсиональное представление, т.е. в виде схемы связей между атрибутами (признаками);
экстенсиональное представление, т.е. с помощью конкретных фактов (объекты, примеры).
интенсиональные методы распознавания объектов: методы, основанные на операциях с признаками;
экстенсиональные методы распознавания объектов: методы, основанные на операциях с объектами.
3. Результаты проведённого сравнительного анализа эффективности разработанного метода распознавания объектов с использованием разработанного программного обеспечения показали, что:
Основные научные результаты, полученные автором и выносимые на защиту
итерационного метода распознавания объектов.
Связь исследований с научными проектами
Работа выполнена в рамках совместных научных проектов Уфимского государственного авиационного технического университета и Института управляющих вычислительных систем и робототехники Технического университета Карлсруэ (Германия), поддержанных грантом №16SV2296-310 Министерства образования Германии и компаниями Leibinger Stryker GmbH и Elliptec AG.
Апробация работы
Основные научные и практические результаты диссертационной работы докладывались на:
Публикации
Основные материалы диссертационной работы опубликованы в 11 статьях, в том числе в 1 статье в рецензируемом журнале из перечня ВАК.
Структура и объем диссертации
Диссертационная работа состоит из 165 страниц машинописного текста, включая введение, 4 главы, библиографический список из 106 наименований.
1 Современное состояние проблемы распознавания объектов
1.1 Проблема распознавания объектов
В общем случае задача распознавания образов заключается в классификации объекта на множестве признаков, вычисляемых при анализе исходных данных, т.е. отнесение объектов, обладающих высокой степенью близости, к одному классу.
Общую задачу распознавания можно разделить на два класса задач:
Задачи второго класса являются математически более сложными, чем задачи первого класса, а также требуют более ресурсоёмкие алгоритмы для их решения.
Блок-схема алгоритма решения задач первого класса представлена на рисунке 1.1.
описание объекта в виде набора признаков
исходные данные
классификатор
- > класс объекта
формирование признаков
Рисунок 1.1- Алгоритм распознавания единичного объекта
Наиболее распространённым подходом к решению задач второго класса является выделение фрагментов исходных данных (сегментация) и последующая классификация выделенного фрагмента (см. рис. 1.2), т.е. использование задачи первого класса в качестве подзадачи задачи второго класса.
описание объекта в виде набора признаков
исходные данные
Рисунок 1.2 - Алгоритм поиска и распознавания множества объектов на изображении/сцене
параметры объекта
Однако данный подход обладает следующими недостатками [28]:
Наличие этих недостатков приводит к тому, что скорость, точность и надёжность процесса распознавания объектов при решении ряда распространённых задач, возникающих на практике, являются недостаточными. К таким задачам относятся:
Также при решении данных задач необходимо учитывать и их специфику:
Как уже было отмечено, при построении систем распознавания необходимо учитывать специфику обрабатываемых данных и объектов. Поэтому при изменении этих данных либо распознаваемых объектов приходится решать задачу распознавания заново, что приводит к определённым осложнениям. Кроме того, требования к методам и алгоритмам распознавания часто дополняются условиями их конкретного применения, например, в промышленности.
Таким образом, метод распознавания, который бы обладал способностью эффективно решать рассмотренные практические задачи, должен обладать следующими свойствами:
На основе анализа данных свойств, были выработаны требования к методу, которые представлены в таблице 1.1.
Таблица 1.1- Требования к разрабатываемому методу распознавания объектов
Для того, чтобы определить метод, наиболее полно удовлетворяющий сформулированным требованиям, необходимо провести сравнительных анализ известных методов распознавания объектов.
1.2 Основные методы распознавания объектов
1.2.1 Классификация методов распознавания объектов
В существующей литературе можно встретить разнообразные варианты классификации методов распознавания объектов. Так, в [9] классификация методов производится по используемым признакам объектов. Выделяются следующие классы методов:
В [26] методы распознавания выделены в следующие четыре группы по используемым алгоритмам:
В [23] классификации методов распознавания объектов производится также по используемым алгоритмам:
Кроме этого, в [23] также предлагается следующий способ представления знаний:
Выделенные способы представления знаний позволяют провести следующую классификацию методов распознавания объектов (см. рис. 1.3):
Рисунок 1.3 - Классификация методов распознавания объектов
1.2.2 Интенсиональные методы распознавания объектов
Интенсиональные методы распознавания используют различные характеристики признаков объектов и их связей, например, значения признаков, распределение значений признаков и т.д. Данные методы оперируют только с признаками, не воспринимая объект в качестве целостной системы.
Формально любой интенсиональный метод можно представить следующим образом:
Допустим, что существует W классов объектов а)\,а)2Требуется найти W решающих функций d\(x), dn{x),... ,dw(x), таких, что если объект х принадлежит классу со„ то
d,(x)>dj(x) у = 1,2 gfc /. (1.1)
Незнакомый объект х относят к -ому классу, если из всех решающих функций, использующих в качестве аргумента х, наибольшее численное значение даёт функция d,(x). В случае неоднозначности необходимо использовать дополнительные условия.
Проблема распознавания объектов
В общем случае задача распознавания образов заключается в классификации объекта на множестве признаков, вычисляемых при анализе исходных данных, т.е. отнесение объектов, обладающих высокой степенью близости, к одному классу.
Общую задачу распознавания можно разделить на два класса задач: - задачи распознавания единичного объекта, т.е. отнесение объекта к одному из классов; - задачи поиска и распознавания множества объектов, т.е. определение положения и ориентации объектов, информация о существовании которых отсутствует, а также их классификация. Данную подзадачу также называют задачей анализа сцены.
Задачи второго класса являются математически более сложными, чем задачи первого класса, а также требуют более ресурсоёмкие алгоритмы для их решения.
Блок-схема алгоритма решения задач первого класса представлена на рисунке 1.1.
Наиболее распространённым подходом к решению задач второго класса является выделение фрагментов исходных данных (сегментация) и последующая классификация выделенного фрагмента (см. рис. 1.2), т.е. использование задачи первого класса в качестве подзадачи задачи второго класса. - область исходных данных, выделенная таким классификатором и отнесённая к какому-либо объекту, не связана с координатами распознанного объекта; - в некоторых случаях исходные данные содержат области, не связанные друг с другом, но относящиеся к одному объекту, что приводит к появлению ложных объектов; - иногда области, относящиеся к различных объектам одного класса, могут оказаться связанными, что приводит к потере объекта; - области, относящиеся к объектам разных классов, могут находиться вблизи друг друга, что приводит к потере объекта или его неверной классификации.
Наличие этих недостатков приводит к тому, что скорость, точность и надёжность процесса распознавания объектов при решении ряда распространённых задач, возникающих на практике, являются недостаточными. К таким задачам относятся:
1. Задача регистрации медицинских изображений, которая заключается в анализе томограмм каких-либо органов или частей тела и поиске за приемлемое время аналогичных томограмм в атласе (базе данных томограмм) для последующей постановки диагноза или в совмещении томограмм другого типа для этого же органа (например, компьютерной и магниторезонансной томограмм).
2. Задача распознавания текстов в промышленных системах, которая осложняется сильными помехами, дефектами и искажениями символов.
3. Задача автоматического извлечения деталей из контейнера, которая требует распознавания множества объектов и определении их положения и ориентации среди перекрывающих друг друга объектов, относящихся к разным классам.
Также при решении данных задач необходимо учитывать и их специфику: - при решении задачи распознавания объектов нежелателен процесс повторного обучения или модификации, даже в случае изменения набора распознаваемых объектов; - необходимо распознавать не только объекты, но и определять их положение в пространстве, ориентацию и взаимное расположение; - необходимо распознавать объект в режиме реального времени (задачи распознавания текста в промышленных системах и автоматического извлечения деталей из контейнера).
Как уже было отмечено, при построении систем распознавания необходимо учитывать специфику обрабатываемых данных и объектов. Поэтому при изменении этих данных либо распознаваемых объектов приходится решать задачу распознавания заново, что приводит к определённым осложнениям. Кроме того, требования к методам и алгоритмам распознавания часто дополняются условиями их конкретного применения, например, в промышленности.
Таким образом, метод распознавания, который бы обладал способностью эффективно решать рассмотренные практические задачи, должен обладать следующими свойствами: - способность эффективно распознавать объекты без повторного обучения и модификации метода в случае изменения набора распознаваемых объектов; - способность распознавать не только объекты, но их положение в пространстве, ориентацию и взаимное расположение; - способность распознавать объект в режиме реального времени.
В существующей литературе можно встретить разнообразные варианты классификации методов распознавания объектов. Так, в [9] классификация методов производится по используемым признакам объектов. Выделяются следующие классы методов: - методы распознавания, основанные на теории принятия решений. Данные методы используют количественные дескрипторы для распознавания объектов, например, такие как длина, площадь, текстура; - структурные методы. Данные методы используют качественные дескрипторы, например, реляционные.
В [26] методы распознавания выделены в следующие четыре группы по используемым алгоритмам: - методы сопоставления {template matching). Данные методы распознают объект, сопоставляя его с образцом или шаблоном из базы данных; - статистические методы {statistical pattern recognition). Данные методы используют статистические свойства объектов, например, функцию плотности распределения вероятностей и т.п.; - нейронные сети; - структурные и синтаксические методы (syntactic pattern recognition). Данные методы используют при распознавании логические правила или грамматики.
В [23] классификации методов распознавания объектов производится также по используемым алгоритмам: - методы, основанные на принципе разделения; - статистические методы; - методы, построенные на основе потенциальных функций; - методы вычисления оценок (голосования); - методы, основанные на исчислении высказываний, в частности на аппарате алгебры логики. Кроме этого, в [23] также предлагается следующий способ представления знаний: - интенсиональное представление, т.е. в виде схемы связей между атрибутами (признаками); - экстенсиональное представление, т.е. с помощью конкретных фактов (объекты, примеры).
Разработка иерархического итерационного метода распознавания объектов
Данный алгоритм основан на оптимизации функции качества в несколько этапов, т.е. поиск оптимума производится последовательно, начиная с грубого определения точек возможных оптимумов функции, как глобальных, так и локальных, и заканчивая точным определением местоположения глобального оптимума (максимума либо минимума) функции качества.
Этапами (уровнями) иерархической оптимизации функции качества являются следующие процессы: - глобальный поиск; - локальный поиск; - точный поиск. оптимизации качества - величиной интервалов отсчётов. При глобальном поиске точки отсчётов вдоль какой-либо координаты отстоят друг от друга на большем расстоянии, чем при локальном поиске. При точном же поиске оптимизация функции производится только лишь в малой окрестности
точки возможного оптимума, найденной на предыдущем уровне, т.е. при локальном поиске; - используемыми критериями качества. На каком-либо уровне оптимизации возможно использование дополнительных критериев качества, имеющих отличную от основного критерия природу и, соответственно, иное расположение локальных оптимумов; - критериями остановки процесса оптимизации. Под критериями остановки процесса оптимизации понимаются такие переменные, как: максимальное количество итераций одномерной функции оптимизации; максимальное количество итераций основной многомерной функции оптимизации; разность значений критериев качества, достигнутых на текущей и на предыдущих итерациях оптимизации. - методом расчёта критерия качества. Например, для ускорения расчёта критерия качества при глобальном поиске используется матрица расстояний, а при точном поиске матрица указателей; - результатом оптимизации. Результатом глобального поиска является массив, состоящий из определённого числа точек, которые представляют вероятные местоположения оптимумов функции. Результатом точного описка является лишь одна точка, т.е. глобальный оптимум.
На рисунке 2.6 представлен алгоритм иерархической оптимизации на примере смоделированной функции качества.
Процесс иерархической оптимизации выглядит следующим образом: рисунке 2.6 окружностями. Результатом оптимизации является массив нескольких точек, вероятность нахождения оптимумов в которых наиболее высока.
2. Второй уровень - уровень локальных поисков, которые производятся с использованием меньших интервалов отсчётов (отмечены на рисунке 2.6 окружностями с точками в центре) в точках, найденных на предыдущем этапе глобального поиска. Результатом оптимизации является точка . наиболее вероятного нахождения глобального оптимума.
3. Последний уровень - точный поиск. Интервалы отсчётов при данном поиске наиболее короткие (отмечены на рисунке 2.6 закрашенными окружностями). Поиск производится лишь в окрестностях точки, найденной на этапе локального поиска. Результатом является уточнённая точка глобального оптимума.
Иерархическая оптимизация позволяет увеличить вероятность нахождения глобальных оптимумов, а также уменьшить время, затрачиваемое на оптимизацию функций качества.
2.2.1.2 Классический метод Пауэлла предназначен для оптимизации многомерных функций по линейнонезависимым координатам. Например, каждая итерация оптимизации функции качества, имеющей 6 координат (3 перемещения по осям х, у и г и 3 вращения вокруг осей х, у и г), при использовании классического метода Пауэлла включает оптимизацию этой функции последовательно по шести координатам. Проведённые эксперименты показали эффективность использования также комбинаций координат функции качества при её оптимизации. Например, при решении задачи регистрации томограмм используются также следующие комбинации: (х,у), (х, -у), (х,г) и т.п. Применение данного подхода позволяет существенно уменьшить время оптимизации, а также увеличить вероятность нахождения глобального оптимума.
Использование непространственных параметрических координат
При сопоставлении прототипа распознаваемого объекта с исходными данными в решении многих задач используются функции качества, представленные 6 координатами: тремя смещениями по осям (пространственно-линейные координаты) и тремя вращениями вокруг этих осей (пространственно-угловые координаты). Т.е. все эти координаты являются пространственными. При оптимизации подобной функции качества достаточно провести процесс поиска оптимума только по этим пространственным координатам. Однако, для увеличения точности распознавания объекта и его положения предлагается при оптимизации в комбинации с пространственными использовать и непространственные параметрические координаты прототипа объекта
Разработка системы распознавания положения и ориентации объектов для регистрации медицинских изображений
Для оценки эффективности разработанного алгоритма был проведён ряд экспериментов, данные о которых отображены в таблице 2.6. Для сравнения использовался иерархический итерационный метод с алгоритмами иерархической оптимизации, иерархического сопоставления и расчёта критерия качества на основе матричного представления исходных данных и тот же метод, но уже с использованием дополнительного алгоритма деформации прототипов распознаваемых объектов.
Как и в предыдущем разделе, для сравнения результатов использовались 4 критерия: К\, К2, К3 и К4. а также использовались 5 наборов экспериментальных данных, каждый из которых содержал по 20 трёхмерных сцен.
Анализируя таблицу 2.6, можно прийти к следующим заключениям: применение разработанного алгоритма деформации прототипов позволило увеличить точность смещения и вращения на 29,9% и 23,6% соответственно, а также количество верных результатов на 14,1% при небольшом увеличении времени распознавания на 30,4%.
Принцип работы данного алгоритма основан на том предположении, что различные объекты могут быть верно распознаны только в случае предварительной обработки одних и тех же исходных данных фильтрами с различными параметрами. Т.е. необходимо проводить процесс сопоставления итеративно и с изменением параметров обрабатывающих фильтров на каждой итерации.
В общем алгоритме иерархического итерационного метода распознавания объектов, представленном на рисунке 2.2, алгоритм итерационного сопоставления реализуется шагами 3, 4 и 20. Отдельно этот алгоритм можно представить следующим образом (см. рис. 2.14).
Применение алгоритма итерационного сопоставления помогает решить задачу распознавания объектов даже в случае, представленном на рисунке 2.15.
На рисунке 2.15 приведён пример распознавания текста. Буквой а) обозначено оригинальное изображение, содержащее распознаваемый текст. Буквами б), в) и г) обозначены бинарные изображения текста, полученные с использованием различного порога фильтрации (75% белых точек - б, 70% - в, 65% - г). Видно, что при пороге в 75% распознать цифру "0" довольно сложно, а при пороге в 70% цифры становятся более отчётливыми. Однако, при пороге в 70% становится сложным распознать комбинацию цифр "36" , что можно легко сделать при пороге в 75%. Таким образом, использование помогает решить данную проблему.
Для оценки эффективности разработанного алгоритма был проведён ряд экспериментов, данные о которых отображены в таблице 2.7. Для сравнения использовался иерархический итерационный метод с алгоритмами иерархической оптимизации, иерархического сопоставления, расчёта критерия качества на основе матричного представления исходных данных, деформации прототипов и тот же метод, но уже с использованием дополнительного алгоритма итерационного сопоставления.
Как и в предыдущем разделе, для сравнения результатов использовались 4 критерия: К[, К3 и К4, а также использовались 5 наборов экспериментальных данных, каждый из которых содержал по 20 трёхмерных сцен.
Иерархический итерационный метод использует прототипы существующих объектов для распознавания объектов на множестве многомерных исходных данных. Такие прототипы могут быть заданы и построены двумя способами: - вручную. Например, задание прототипа с помощью CAD модели; - автоматически. Например, производится съёмка существующих объектов по отдельности и затем на основе полученных данных строятся модели прототипов этих объектов.
Использование прототипов распознаваемых объектов даёт возможность быстро и качественно идентифицировать объекты на исходных данных, а также одновременно определить их положение. Однако основными проблемами при решении задачи распознавании многих объектов, принадлежащих разным классам, является их возможное перекрытие друг другом. В этом случае алгоритм распознавания может давать сбои, т.е. существенно снижается точность распознавания.
Для решения вышеописанной проблемы был разработан алгоритм иерархизации прототипов распознаваемых объектов, принцип которого заключается в следующем: - модель прототипа распознаваемого объекта после анализа разбирается на составные части (выделяются геометрические примитивы); - строится иерархическая модель прототипа; - определяются пространственно-топологические связи между компонентами модели прототипа; - каждому компоненту на каждом уровне иерархии присваивается вес. Таким образом, при использовании алгоритма иерархизации моделей прототипов при распознавании учитывается значимость компонентов, заданная их весом.
Представим, что прототип распознаваемого объекта задан следующей иерархической моделью (см. рис. 2.16). Каждому компоненту присвоен вес где у - порядковый номер компонента, а г - номер уровня
Уровень 1 иерархии. Алгоритм расчёта критерия качества с использованием алгоритма иерархизации прототипа распознаваемого объекта выглядит следующим образом (см. рис. 2.17).
Прикладная программная система для решения задачи регистрации медицинских изображений
Модуль распознавания объектов, разработанный на основе иерархического итерационного метода, был адаптирован и встроен в систему автоматического планирования медицинских операций в двух вариантах для операционных систем Windows и Linux. Т.к. при разработке модуля использовался платформонезависимые язык С++ и библиотека OpenCV, то программная доработка практически не потребовалась.
Задача модуля распознавания заключается в определении положения и ориентации одной томограммы (обычно магниторезонансной) по отношению к другой (обычно компьютерной).
На рисунке 4.2 представлен графический интерфейс пользователя программы Stryker Leibinger для операционной системы Windows со встроенным модулем распознавания.
На рисунке 4.3 представлен графический интерфейс пользователя программы регистрации медицинских изображений, разработанной в Институте управляющих вычислительных систем и робототехники Технического университета Карлсруэ (Германия) для операционной системы Linux со встроенным модулем распознавания.
Система автоматического контроля качества при производстве пьезо- моторов фирмы ЕШр1ес предназначена для выполнения следующих задач: - определение точного положения пьезо-элемента в моторе; - определение параметров искажения рамки мотора после впрессовки пьезо-элемента и др.
После выполнения вышеназванных задач система должна занести определённые параметры в базу данных на основе серийного номера мотора, который распознаётся с помощью разработанного модуля, реализующего иерархический итерационный метод.
На рисунке 4.4 представлен графический интерфейс пользователя программы ЯеАсгУтоп со встроенным модулем распознавания текста. Система Ьупкет предназначена для решения двух робототехнических задач: 1) автоматическое извлечение деталей из контейнера; 2) безопасное взаимодействие человек-машина.
Особенность системы Ьупкеиз заключается в использовании сенсоров, основанных на новой технологии - РМО. Эти сенсоры представляют собой компактные камеры, способные генерировать как обычные 2-мерные изображения в градациях серого, так и 2,5-мерные изображения, которые также содержат информацию о дальности каждой точки объекта до камеры (см. рис. 3.28). При использовании данной технологии и разработанного в данной диссертации иерархического итерационного метода были достигнуты результаты, позволяющие говорить о повышении эффективности при решении вышеупомянутых задач.
Задача автоматического извлечения деталей из контейнера состоит из следующих подзадач (см. также рис. 4.6): 1) моделирование 3-мерной сцены; 2) анализ сцены; 3) определение точек захвата; 4) разработка стратегии извлечения деталей; ( 5) планирование траектории движения манипулятора без коллизий.
Эффективность и точность решения последних трёх задач сильно зависит от результатов решения задачи анализа сцены, т.е. от задачи распознавания объектов и определения их положений и ориентаций в пространстве. Для решения данной задачи в системе ЬупкеиБ и используется разработанный модуль, основанный на иерархическом итерационном методе.
Графический интерфейс разработанного прикладного ПО системы представлен на рисунке 4.5.
На рисунке 4.6 представлена архитектура разработанной системы Ьупкеиз, в состав которой входит модуль распознавания объектов на основе иерархического итерационного метода.
1. В данной главе разработано прикладное программное обеспечение для решения практических задач регистрации медицинских изображений, распознавания текста в промышленных системах и задачи распознавания объектов для системы автоматического извлечения деталей из контейнера, включающее в себя модуль распознавания объектов, реализованный на основе разработанного иерархического итерационного метода.
2. Разработанное программное обеспечение было успешно внедрено в следующие промышленные системы: - Stryker Leibinger - система автоматического планирования медицинских операций; - ReActVision - система автоматического контроля качества при производстве пьезо-моторов фирмы Elliptec:; - Lynkeus - система фирмы KUKA Robotics автоматического извлечения деталей из контейнера. Промышленная эксплуатация разработанного прикладного программного обеспечения показала эффективность использования разработанного метода распознавания объектов при решении конкретных практических задач.
