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

На правах рукописи

□□3456687

САФРОНОВ Кирилл Валерьевич

ИЕРАРХИЧЕСКИЙ ИТЕРАЦИОННЫЙ МЕТОД РАСПОЗНАВАНИЯ ОБЪЕКТОВ НА ОСНОВЕ АНАЛИЗА МНОГОМЕРНЫХ ДАННЫХ

Специальность 05.13.01 - Системный анализ, управление и обработка информации (в промышленности)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

О 5 ДЕК 2008

Уфа 2008

Работа выполнена в ГОУ ВПО «Уфимский государственный авиационный технический университет» на кафедре вычислительной техники и защиты информации

Научный руководитель д-р техн.наук, проф.

Васильев Владимир Иванович

Официальные оппоненты д-р техн.наук, проф.

Юсупова Нафиса Исламовпа

канд.техн.наук, доц. Гиниятуллин Вахит Мансурович

Ведущая организация ГОУ ВПО МО «Челябинский

государственный университет»

Защита диссертации состоится « № » ^ 2008 г. в ^0 часов

на заседании диссертационного совета Д212.288.03 при Уфимском государственном авиационном техническом университете по адресу: 450000, Уфа-центр, ул.К.Маркса, 12. УГАТУ

С диссертацией можно ознакомиться в научной библиотеке университета. Автореферат размещён на сайте университета http://www.ugatu.ac.ru/science

Автореферат разослан « » 41 2008 г.

Ученый секретарь диссертационного совета д-р техн.наук, проф.

В.В. Миронов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

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

Задача автоматического распознавания объектов известна довольно давно, а первые попытки её решения предпринимались уже в начале 70-х годов прошлого века. По данной тематике опубликовано и выпущено множество статей И книг, разработан целый ряд методов распознавания и спроектированных на их основе автоматических систем, которые находят широкое применение в различных областях.

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

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

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

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

Цель и задачи исследования

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

Для достижения указанной цели требуется решить следующие задачи:

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

2. Разработать алгоритмическое обеспечение для реализации предложенного метода распознавания объектов.

3. Разработать архитектуру системы распознавания объектов, основапную на предложенном методе, а также методику её практического применения при решении конкретных задач.

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

5. Оценить эффективность применения предложенного метода распознавания объектов при решении ряда практических задач.

Методы исследования

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

Научная новизна

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

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

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

2. Разработано оригинальное алгоритмическое обеспечение, состоящее из системы взаимосвязанных алгоритмов и процедур, включающих в себя иерархическую оптимизацию, иерархическое сопоставление, расчёт критерия качества с использованием матричного представления исходных данных, деформацию прототипов распознаваемых объектов, итерационное сопоставление и иерархизащпо прототипов распознаваемых объектов. Разработанные процедуры позволяют повысить точность и сократить время распознавания объектов.

Практическая значимость результатов

1. Разработана архитектура универсальной системы распознавания объектов, основанная на предложенном иерархическом итерационном методе распознавания, а также методика её использования при решении различных классов практических задач.

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

3. Результаты проведённого сравнительного анализа эффективности разработанного метода распознавания объектов с использованием разработанного программного обеспечения показали, что:

- при решении задачи регистрации медицинских изображений обеспечивается уменьшение времени распознавания по сравнению с классическим методом сопоставления и методом Покрандга в 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 раза.

Основные научные результаты, полученные автором и выносимые на защиту

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

2. Алгоритмическое обеспечите иерархического итерационного метода распознавания объектов.

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

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

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

Связь исследований с научными проектами

Работа выполнена в рамках совместных научных проектов Уфимского государственного авиационного технического университета и Института управляющих вычислительных систем и робототехники Технического университета Карлсруэ (Германия), поддержанных грантом №16SV2296-310 Министерства образования Германии и компаниями Leibinger Stryker GmbH и Elliptec AG.

Апробация работы

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

- VII-X международных научных конференциях "Компьютерные пауки и информационные технологии" (Карлсруэ, Германия, 2006; Уфа, 2005, 2007; Анталия, Турция, 2008);

- международной конференции по робототехнике "Robotik 2008" (Мюнхен, Германия, 2008);

- семинарах в Институте управляющих вычислительных систем и робототехники Технического университета Карлсруэ (Германия, 2007, 2008).

Публикации

Основные материалы диссертационной работы опубликованы в 11 статьях, в том числе в 1 статье в рецензируемом журнале из перечня ВАК.

Структура и объем диссертации

Диссертационная работа состоит из 165 страниц машинописного текста, включая введение, 4 главы, библиографический список из 106 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе проводится анализ современного состояния проблемы распознавания объектов.

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

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

Общими недостатками существующих методов распознавания объектов являются:

- отсутствие эффективного универсального метода распознавания объектов, способного с высокой эффективностью решать задачи, относящиеся к различным классам;

- невозможность либо неточность одновременного распознавания объекта и определения его положения в пространстве, а также расположения по отношению к другим объектам.

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

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

В качестве особенностей постановки и решения этих задач отмечаются:

- необходимость распознавания объектов и определения их положения в пространстве, ориентации и взаимного расположения;

- нежелательность процесса повторного обучения или модификации метода и алгоритмов;

- необходимость распознавания объектов в режиме реального времени.

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

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

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

- простота обучения алгоритма распознавания (обучение заключается в выборе функций качества и их взаимосвязи);

- простота процедуры построения набора признаков (в качестве набора признаков используется прототип распознаваемого объекта).

Даётся общая постановка задачи распознавания объекта и определения его положения и ориентации в пространстве.

Пусть заданы следующие множества: -

- множество прототипов N классов объектов (ХьХг,..., Хдг};

- множество М объектов (Уь У2.....Ум), принадлежащих пространству исходных данных Ик.

Для каждого объекта У; требуется найти пару (X,-, Р^, где / = 1... ] = 1 ...М, а Р'! - это положение и ориентация объекта на исходных данных, которое задаётся следующим образом:

где с^,..., с1]к - положение объекта, а ,..., ¿^ - ориентация объекта.

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

точечную модель А, полигональную модель В и др.):

*K = ¡(Af, <,...},..., (<.<,...}}, '

где {А[, В[,...} - к-й уровень пирамидального представления, NP - количество уровней пирамиды.

Для определения степени соответствия прототипа распознаваемого объекта X, исходным данным RK будем использовать критерий качества F,,„„ который рассчитывается с помощью функции качества f(X,,RK, Рт). Функцию качества / представим следующим образом:

ДХ„ RK, Рт) = М(Х„ й*. ¿U fi(Xt, РЛ ■■■), (3)

гДе f\,hi ■ ■ ~ функции качества более низких порядков, использующие только определённые группы признаков (например, только точечные модели или только полигональные модели).

Таким образом, входные параметры алгоритма представлены в таблице 1.

Таблица 1 - Входные параметры алгоритма иерархического итерационного метода распознавания объектов

Параметр Описание

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

N0 количество наборов фильтров предварительной обработки исходных данных

NP количество уровней пирамиды

¡X¡,X2,.. - ,XNx) прототипы распознаваемых объектов

Nx количество прототипов распознаваемых объектов

F ■ 1 mm минимальное значение критерия качества соответствия прототипа распознаваемому объекту, ниже которого объект считается нераспознанным.

Полная блок-схема алгоритма иерархического итерационного метода распознавания объектов представлена на рисунке 1.

В целях увеличения точности, а также скорости распознавания образов разработаны следующие алгоритмы, входящие в состав предлагаемого иерархического итерационного метода:

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

( Начало )

1. Задание входных параметров

2. Построение пирамидального представления прототипов распознаваемых объектов

3. Выбор (-го набора параметров фильтров предварительной обработки исходных данных б,

| 4. Предварительная обработка исходных данных |

5. Построение пирамидального представления исходных данных

1=1

Н 6. Выбор 1-го прототипа объекта X,

7. Выбор начального набора параметров Рв

_прототипаХ)_

—

8. Загрузка )с-го уровня пирамидального _представления прототипа-У,_

9. Загрузка *-го уровня пирамидального представления исходных данных

10. Расчет значения критерия качества Рщ^ отражающего степень соответствия прототипа X, исходным данным

18. Удалить распознанный объект, соответствующий прототипу X,, со всех уровней пирамидального представления исходных данных

( Конец )

Рисунок 1 - Блок-схема алгоритма иерархического итерационного метода распознавания объектов

(глобальный, локальный и точный поиски) при использовании комбинаций пространственно-линейных, пространственно-угловых и параметрических аргументов функции;

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

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

- Алгоритм деформации прототипов распознаваемых объектов. Данный алгоритм реализует деформацию прототипов распознаваемых объектов при их сопоставлении с исходными данными, которые могут быть зашумлены и искажены;

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

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

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

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

Первой задачей, решаемой с помощью иерархического итерационного метода распознавания объектов, является задача регистрации медицинских изображений (рис. 2 ).

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

Исходными данными являются медицинские изображения, а именно томограммы: компьютерная, магнитно-резонансная и другие. Прототипом распознаваемого объекта является томограмма. Для определения соответствия прототипа исходным данным предлагается использовать следующие два критерия

магниторезонанская томограмма

(4)

(5)

Рисунок 2 - Задача регистрации медицинских изображений

качества:

1, Коэффициент схожести гистограмм:

М М .. .S

tij^ РМРуО)

где

P(1,J) = -ff-.pAi) = —;p,0) = —;

j=0 i-0

N - количество всех точек изображения; px(i) - частота появления определённой комбинации значений серого в г'-м столбце гистограммы; py(j) - частота появления определённой комбинации значений серого в j-м столбце гистограммы.

2. Суммарная квадратическая ошибка:

Fssd ~

Z Z Z№+1>у+г+к)2 ■ ;'г(г' j>к))' (6) / ; к

где f" - матрица расстояний, полученная на основе данных одной томограммы; (х,у, z) - положение томограммы т по отношению к матрице расстояний; а т вычисляется по следующей формуле:

т(х, у, z) = Т(т(Тх(х), Ту(у), Tz(z))), (7)

где m - вторая томограмма, которая сопоставляется с первой; Т, Тх, 7"v, Т, функции трансформации томограммы.

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

Следующей задачей, решаемой в работе с помощью иерархического итерационного метода распознавания объектов, является задача распознавания текстов в промышленных системах (рие. 3). Основные требования в этом классе задач - это надёжность и устойчивость, поскольку даже единичные

_ _ ошибки при распознавании

Рисунок 3 - Задача распознавания текста в про-

^ г р относительно коротких над-

мьшшенных системах

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

1. Суммарная квадратическая ошибка:

Ъзо = £ £(/Дх + иу + Л ■ т, ])?, (8)

где - матрица расстояний изображения, содержащего текст; (х, у) - положение шаблона символа по отношению к матрице расстояний; а т вычисляется по следующей формуле:

т(х,у) = Г(т(Тх(Х),Ту(уШ (9)

где т - шаблон распознаваемого символа; Т, Тх, Ту - функции трансформации шаблона.

2. Степень перекрытия или коэффициент корреляции:

_ л^ N. _ (Ь^уь + иу + л-т.л)? сс к'к

где Ne - количество точек шаблона, совпадающих с точками распознаваемого символа; ¿V, - общее количество точек шаблона; - количество точек области изображения, ограниченного наложенным шаблоном; / - изображение, содержащее текст.

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

весь спектр методов распознавания текста, разработанных на данный момент: SimpleOCR, GOCR, TopOCR, Readiris Pro, ScreenOCR, OpenOCR, Finereader, TOCR.

ИИМРО 1

205,1 мс; 99,7%

TOCR

Finereader ♦ 125 ис; 55,6% i

61,1 мс; 35% screcnOCR SimpleOCR

❖ мс; 34,2% 204,7 мс; 25,3%

QpcnQCR ♦ TopOCR & ♦ ♦_

66,7 мс; 24,8% 99,6 мс; 30,1% Readiris Pro GOCR

274,6 мс; 23,1%

Среднее время распознавания (мс) ¡VsimpleOCR • GOCR TopOCR oReeUiris Pro ♦ ScreenOCR *Opt;nOCR о Finereader ♦ ТОГ-R ^ИИМРО;

Рисунок 4 - Экспериментальные результаты

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

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

5).

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

Прототипом распознаваемого объекта также является трёхмерная точечная модель, которая может быть получена двумя способами: автоматически (производится конструирование трёхмерной модели идеального объекта с помощью используемой сенсорной системы) и с помощью САП-модели.

РМО-кз мера

2.5-мерное изображения

Рисунок 5 - Задача автоматического извлечения деталей из контейнера

Для определения соответствия прототипа исходным данным предлагается использовать следующие критерии качества:

1. Суммарная квадратическая ошибка:

Zihj LkWd(x + У + b z +к)- m(i, j, к))2

rwsso =-v v v -/■• ■ in-, (.11)

Л. LjLk m{i,jtk)

ще fj - матрица расстояний трёхмерной сцены; (х,у, z) - положение прототипа распознаваемого объекта по отношению к матрице расстояний: in - модель распознаваемого объекта.

При использовании матрицы указателей величина d рассчитывается по следующей формуле:

d(i, j, к) =((/;(* + i,у + j, z + k)x~ if + 0JT(X + i,y + j,z + k)y - jf+ +(/?(* +У+ J,z + к)г - к)2) ■ m{i, j. k).

2. Среднеквадратическая ошибка:

_ Ш^тЩЩ ....

''тот =-^-. (13)

где <1 - расстояние от точки модели распознаваемого объекта с координатами ((, ]', к) до ближайшей поверхности сцены; N - общее количество точек модели распознаваемого объекта.

3. Степень перекрытия или коэффициент корреляции:

^ N. _ + У +1 г + *) ■ йС.*) <

сс ^ '

где Л'е - количество точек модели, расстояние от которых до ближайшей поверхности сцены меньше заданной величины о; ЭД - общее количество точек модели.

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

В четвёртой главе разрабатывается прикладное программное обеспечение (1ШО), реализующее предложенный иерархический итерационный метод распознавания объектов для решения вышеописанных практических задач. Приводятся результаты вычислительных экспериментов с использованием разработанного ППО.

С использованием разработанного ППО проведены эксперименты по отладке и тестированию алгоритмов распознавания объектов, разработанных в рамках диссертации.

Разработанное ППО успешно внедрено в следующие промышленные системы:

1. Система автоматического планирования медицинских операций фирмы Strylcer Leibinger.

2. Система автоматического контроля качества при производстве пьезо-моторов фирмы Elhptec - ReActVision.

3. Система автоматического извлечения деталей из контейнера фирмы KUKA Robotics - Lynkeus.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

2. Разработано оригинальное алгоритмическое обеспечение, состоящее из системы взаимосвязанных алгоритмов и процедур, включающих в себя иерархическую оптимизацию, иерархическое сопоставление, расчёт критериев качества с использованием матричного представления исходных данных, деформацию прототипов распознаваемых объектов, итерационное сопоставление и иерархизацию прототипов распознаваемых объектов. Разработанные процедуры позволяют повысить точность и сократить время распознавания объектов.

3. Разработана архитектура универсальной системы распознавания объектов, основанная на предложенном иерархическом итерационном методе распознавания, а также методика её использования при решении различных классов практических задач.

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

изображений, распознавания текста и автоматического извлечения деталей из контейнера.

5. Результаты проведённого сравнительного анализа эффективности разработанного метода распознавания объектов с использованием разработанного программного обеспечения показали, что:

- при решении задачи регистрации медицинских изображений обеспечивается уменьшение времени распознавания по сравнению с классическим методом сопоставления и методом Покрандта в 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 раза.

СПИСОК ПУБЛИКАЦИЙ В рецензируемых мсурналах из списка ВАК

1. Иерархический итерационный метод распознавания образов на основе анализа многомерных данных / X. Вёрн, В.И. Васильев, К.В. Сафронов, И.М. Чушенков // Вестник УГАТУ : науч. журн. Уфимск. гос. авиац. техн. ун-та. Серия«Управление, вычислительная техника и информатика?.2007. Т.9, №5(23). С.3-8.

В других изданиях

2. Автоматическая регистрация медицинских томограмм головного мозга с использованием градиентного метода / Ю. Граф, К.В. Сафронов, И.М. Чушен-ков, X. Вёрн // Матер. 7-й межд. науч. конф. С51Т'2005. Уфа : УГАТУ, 2005. Т.1. С. 174-179. (Статья на ант. яз.).

3. Комбинированный метод регистрации медицинских изображений с использование градиентной и взаимной информации / К.В. Сафронов, И.М. Чу-шенков, X. Вёрн // Матер. 8-й межд. науч. конф. С51Т'200б. Карлсруэ, Германия, 2006. ТЛ. С 7-10. (Статья на англ. яз.).

4. Распознавание текста с использование алгоритмов оптимизации / К.В. Сафронов, И.М. Чушенков, X. Вёрн // Матер. 9-й межд. науч. конф. СЗГГ'2007. Уфа : УГАТУ, 2007. Т.1. С.85-89. (Статья на англ. яз.).

5. Применение алгоритмов оптимизации для решения задачи распознавания символов / К,В. Сафронов, И.М. Чушенков, X. Вёрн // Вычислительная техника и новые информационные технологии: межвуз. научн. сб.- Уфа : УГАТУ, 2007. С.92-97.

6. Применение алгоритмов оптимизации для решения задачи распознавания образов / К.В. Сафронов, И.М Чушенков, X. Вёрн // Матер. Всерос. молодёжи. науч.-техн. конф. Уфа : УГАТУ, 2007. Т.З. С.46 47.

7. Решение задачи извлечения деталей из контейнера с использованием иерархического итерационного метода распознавания образов / К.В. Сафронов, И.М. Чушенков, X. Вёрн // Матер, межд. конф. Robotik 2008. Мюнхен, Германия, 2008. С.3-6. (Статья на англ. яз.).

8. Использование иерархического итерационного метода распознавания объектов в системе извлечения деталей из контейнера, построенной с использованием PMD-камер / К.В. Сафронов, И.М. Чушенков, X. Вёрн // Матер. 8-й межд. науч. конф. АРССМ 2008. Харбин, Китай, 2008. С.80-84 (Статья на англ. яз.).

9. Система извлечения деталей из контейнера, построенная с использованием PMD-технологии / К.В. Сафронов, И.М. Чушенков, X. Вёрн // Информатика, управление и компьютерные науки : сб. ст. 3-й per. зимн. шк.-сем. аспирантов и молодых учёных. Уфа : УГАТУ, 2008". С.523-529.

10. PMD технология: Особенности калибровки PMD камеры / И.Р. Мамаев, К.В. Сафронов, X. Вёрн // Информатика, управление и компьютерные науки : сб. ст. 3-й реп зимн. шк.-сем. аспирантов и молодых учёных. Уфа : УГАТУ, 2008. С. 154-160.

11. Система реального времени для решения задачи автоматического извлечения деталей из контейнера при использовании преимуществ PMD технологии / И.Р. Мамаев, К.В. Сафронов, И.М. Чушенков, X. Вёрн // Матер. 9-й межд. науч. конф. CSIT'2008, Анталия, Турция, 2008. Т.1. С.21-26. (Статья на англ. яз.).

Диссертант

К.В. Сафронов

САФРОНОВ Кирилл Валерьевич

ИЕРАРХИЧЕСКИЙ ИТЕРАЦИОННЫЙ МЕТОД РАСПОЗНАВАНИЯ ОБЪЕКТОВ НА ОСНОВЕ АНАЛИЗА МНОГОМЕРНЫХ ДАННЫХ

Специальность 05.13.01 - Системный анализ, управление и обработка информации (в промышленности)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Подписано к печати 27.10.2008. Формат 60x84 1/16. Бумага офсетная. Печать плоская. Гарнитура Тайме. Усл. печ. л. 1,0. Усл. кр. - отт. 1,0. Уч.-изд. л. 0,9. Тираж 100 экз. Заказ № 477.

ГОУ ВПО Уфимский государственный авиационный технический университет Центр оперативной полиграфии 450000, Уфа-центр, ул. К.Маркса, 12.

Введение.

1 Современное состояние проблемы распознавания объектов

1.1 Проблема распознавания объектов

1.2 Основные методы распознавания объектов

1.2.1 Классификация методов распознавания объектов

1.2.2 Интенсиональные методы распознавания объектов

1.2.3 Экстенсиональные методы распознавания объектов

1.2.4 Методы совместной классификации

1.2.5 Сравнительный анализ известных методов распознавания объектов

1.3 Выводы. Цели и задачи исследования

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

2.1 Разработка иерархического итерационного метода распознавания объектов.

2.1.1 Общая постановка задачи распознавания объектов и определения их положения и ориентации в пространстве

2.1.2 Основные принципы иерархического итерационного метода распознавания объектов.

2.1.3 Алгоритм иерархического итерационного метода распознавания объектов.

2.2 Разработка алгоритмического обеспечения иерархического итерационного метода распознавания объектов

2.2.1 Алгоритм иерархической оптимизации многомерной функции.

2.2.2 Алгоритм иерархического сопоставления

2.2.3 Алгоритм расчёта критерия качества с использованием матричного представления исходных данных.

2.2.4 Алгоритм деформации прототипов распознаваемых объектов.

2.2.5 Алгоритм итерационного сопоставления

2.2.6 Алгоритм иерархизации прототипов распознаваемых объектов.

2.3 Анализ преимуществ разработанных алгоритмов.

2.4 Выводы по второй главе

3 Разработка систем распознавания объектов для решения практических задач.

3.1 Методика разработки системы распознавания объектов

3.2 Разработка системы распознавания положения и ориентации объектов для регистрации медицинских изображений

3.2.1 Постановка задачи регистрации медицинских изображений

3.2.2 Описание архитектуры системы распознавания объектов для решения задачи регистрации медицинских изображений

3.2.3 Экспериментальные результаты.

3.3 Разработка системы распознавания объектов в задаче распознавания текста

3.3.1 Постановка задачи распознавания текста

3.3.2 Описание архитектуры системы распознавания объектов для решения задачи распознавания текста

3.3.3 Экспериментальные результаты.

3.4 Разработка системы распознавания объектов в задаче автоматического извлечения деталей из контейнера.

3.4.1 Постановка задачи распознавания множества объектов для системы автоматического извлечения деталей из контейнера

3.4.2 Описание архитектуры системы распознавания объектов для решения задачи автоматического извлечения деталей из контейнера.

3.4.3 Экспериментальные результаты.

3.5 Выводы по третьей главе.

4 Разработка и экспериментальное исследование прикладных программных систем, основанных на иерархическом итерационном методе распознавания объектов.

4.1 Прикладная программная система для решения задачи регистрации медицинских изображений

4.2 Прикладная программная система для решения задачи распознавания текста в промышленных системах

4.3 Прикладная программная система для решения задачи распознавания объектов в системе автоматического извлечения деталей из контейнера

4.4 Выводы по четвёртой главе

Актуальность темы

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

Задача автоматического распознавания объектов известна довольно давно, а первые попытки её решения предпринимались уже в начале 70-х годов прошлого века. По данной тематике опубликовано и выпущено множество статей и книг, разработан целый ряд методов распознавания и спроектированных на их основе автоматических систем, которые находят широкое применение в различных областях.

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

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

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

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

Цель и задачи исследования

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

Для достижения указанной цели требуется решить следующие задачи:

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

2. Разработать алгоритмическое обеспечение для реализации предложенного метода распознавания объектов.

3. Разработать архитектуру системы распознавания объектов, основанную на предложенном методе, а также методику её практического применения при решении конкретных задач.

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

5. Оценить эффективность применения предложенного метода распознавания объектов при решении ряда практических задач.

Научная новизна

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

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

2. Разработано оригинальное алгоритмическое обеспечение, состоящее из системы взаимосвязанных алгоритмов и процедур, включающих в себя иерархическую оптимизацию, иерархическое сопоставление, расчёт критерия качества с использованием матричного представления исходных данных, деформацию прототипов распознаваемых объектов, итерационное сопоставление и иерархизацию прототипов распознаваемых объектов. Разработанные процедуры позволяют повысить точность и сократить время распознавания объектов.

Практическая значимость результатов

1. Разработана архитектура универсальной системы распознавания объектов, основанная на предложенном иерархическом итерационном методе распознавания, а также методика её использования при решении различных классов практических задач.

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

3. Результаты проведённого сравнительного анализа эффективности разработанного метода распознавания объектов с использованием разработанного программного обеспечения показали, что:

- при решении задачи регистрации медицинских изображений обеспечивается уменьшение времени распознавания по сравнению с классическим методом сопоставления и методом Покрандта в 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 раза.

Основные научные результаты, полученные автором и выносимые на защиту

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

2. Алгоритмическое обеспечение иерархического итерационного метода распознавания объектов.

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

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

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

Связь исследований с научными проектами

Работа выполнена в рамках совместных научных проектов Уфимского государственного авиационного технического университета и Института управляющих вычислительных систем и робототехники Технического университета Карлсруэ (Германия), поддержанных грантом №16SV2296-310 Министерства образования Германии и компаниями Leibinger Stryker GmbH и Elliptec AG.

Апробация работы

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

- VII-X международных научных конференциях "Компьютерные науки и информационные технологии" (Карлсруэ, Германия, 2006; Уфа, 2005, 2007; Анталия, Турция, 2008);

- международной конференции по робототехнике "Robotik 2008" (Мюнхен, Германия, 2008);

- семинарах в Институте управляющих вычислительных систем и робототехники Технического университета Карлсруэ (Германия, 2007, 2008).

Публикации

Основные материалы диссертационной работы опубликованы в 11 статьях, в том числе в 1 статье в рецензируемом журнале из перечня ВАК.

Структура и объем диссертации

Диссертационная работа состоит из 165 страниц машинописного текста, включая введение, 4 главы, библиографический список из 106 наименований.

3.5 Выводы по третьей главе

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

- задача регистрация медицинских изображений;

- задача распознавания текста в промышленных системах;

- задача автоматического извлечения деталей из контейнера.

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

- при решении задачи регистрации медицинских изображений сравнивались классический метод сопоставления, метод Покрандта и иерархический итерационный метод. Эксперименты показали, что применение иерархического итерационного метода распознавания образов позволило уменьшить время распознавания по сравнению с обычным методом сопоставления и методом Покрандта в 7,2 и 1,15 раз соответственно, а также повысить точность определения положения на 19,5% и 8,5% и увеличить количество верных результатов в 2,3 и 1,3 раза;

- при решении задачи распознавания текста в промышленных системах сравнивались существующие программные системы, такие как, например, TOCR, SimpleOCR и т.д., и иерархический итерационный метод. Наилучший результат из существующих программных систем показала система TOCR. Эксперименты показали, что применение иерархического итерационного метода распознавания образов позволило существенно увеличить количество верных результатов в 1,8 раза (на 44,1%) по сравнению с системой TOCR, что составило 99,7% от всех изображений;

- при решении задачи автоматического извлечения деталей из контейнера сравнивались классический метод сопоставления и иерархический итерационный метод. Эксперименты показали, что применение иерархического итерационного метода распознавания образов позволило существенно уменьшить время распознавания по сравнению с обычным методом сопоставления в 7,2 раза, повысить точность определения положения на 16,8% (в 1,2 раза) и увеличить количество верных результатов в 2,2 раза.

4 Разработка и экспериментальное исследование прикладных программных систем, основанных на иерархическом итерационном методе распознавания объектов

В качестве программной реализации иерархического итерационного метода распознавания объектов разработан специальный программный компонент в виде ^///-модуля, предоставляющий интерфейс для взаимодействия с внешними системами и модулями и обладающий возможностью встраивания в любую систему обработки изображений. Данный модуль разработан на языке С++ с использованием библиотеки MFC и библиотек обработки изображений OpenCV и VTK.

Архитектура модуля распознавания, реализующего иерархический итерационный метод, представлена на рисунке 4.1.

В состав модуля входят следующие компоненты:

- модуль управления: реализует основной алгоритм процесса распознавания объектов, а также осуществляет межмодульное взаимодействие;

- модуль предварительной обработки исходных данных, состоящий из следующих компонентов:

• модуль расчёта матричного представления исходных данных. Рассчитывает матрицу расстояний или указателей (см. раздел 2.2.3);

• модуль расчёта пирамидального представления исходных данных. Рассчитывает каждый уровень пирамиды с помощью специальных фильтров (см. разделы 2.2.2);

• модуль нормализации исходных данных. Содержит разнообразные фильтры для шумовой, яркостной и других нормализаций i доходных данных;

- модуль алгоритма сопоставления. Реализует основной —-г=шгоритм сопоставления (см. разделы 2.2.2 и 2.2.5), используя модули, представленные ниже;

- модуль иерархизации прототипов. Реализует алгоритм иера^-у^>хизапии прототипов распознаваемых объектов (см. раздел 2.2.6);

- модуль оптимизации функции качества. Реализует -^алгоритм иерархической оптимизации многомерной функции качес - j-ва (см. раздел 2.2.1);

- модуль деформации прототипов. Реализует алгоритм дег Д ормации прототипов распознаваемых объектов (см. раздел 2.2.4);

- модуль расчёта критерия качества. Реализует алгоритм расчёта. меритерия качества на основе матричного представления исходных дага^гтых (см.

раздел 2.2.3);

- модуль дополнительной обработки результатов сопоо-пгавления.

Производит после основного процесса распознавания дополн*^зтгельную обработку результатов, улучшая их;

- база данных прототипов распознаваемых объектов.

Модуль распознавания, реализующий иерархический итерационЕгг^Еэ-тй метод, внедрён в следующие промышленные программные системы: Stryker Leibinger - система автоматического планирования меи т^г цинских операций. Разработанный модуль распознавания, встроенный zb данную систему, предназначен для поиска наилучшего расположен^ггЕгя одной

Рисунок 4.1 - Архитектура модуля распознавания томограммы относительно другой. Обычно в роли таких томограмм выступают компьютерная и магниторезонансные томограммы головы; ,

2. ReActVision - система автоматического контроля качества при производстве пьезо-моторов фирмы Elliptec. Разработанный модуль распознавания, встроенный в данную систему, предназначен для распознавания серийных номеров пьезо-моторов;

3. Система автоматического извлечения деталей из контейнера фирмы KUKA Robotics. Разработанный модуль распознавания, встроенный в данную систему, предназначен для распознавания разнообразных деталей и определения их положений и ориентаций на основе данных, предоставляемых PMD-камерой.

4.1 Прикладная программная система для решения задачи регистрации медицинских изображений

Модуль распознавания объектов, разработанный на основе иерархического итерационного метода, был адаптирован и встроен в систему автоматического планирования медицинских операций в двух вариантах для операционных систем Windows и Linux. Т.к. при разработке модуля использовался платформонезависимые язык С++ и библиотека OpenCV, то программная доработка практически не потребовалась.

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

На рисунке 4.2 представлен графический интерфейс пользователя программы Stryker Leibinger для операционной системы Windows со встроенным модулем распознавания.

P-tUtt vin. VIII9 mi* jfft*

SWU CT/fll Jf uullruur™ Ж Л Ш ■

-» I " * Ъ "U*

И" JI.-I |Д.»|м. j гяа£. э-*1' 1ас—« tew".и-as иг

Рисунок 4.2 - Графический интерфейс ППО Stryker Leibinger под Windows

На рисунке 4.3 представлен графический интерфейс пользователя программы регистрации медицинских изображений, разработанной в Институте управляющих вычислительных систем и робототехники Технического университета Карлсруэ (Германия) для операционной системы Linux со встроенным модулем распознавания.

Рисунок 4.3 - Графический интерфейс ППО регистрации медицинских изображений под Linux

Программная система Leibinger Stryker успешно используется для решения практических задач.

4.2 Прикладная программная система для решения задачи распознавания текста в промышленных системах

Система автоматического контроля качества при производстве пьезо-моторов фирмы Elliptec предназначена для выполнения следующих задач:

- определение точного положения пьезо-элемента в моторе;

- определение параметров искажения рамки мотора после впрессовки пьезо-элемента и др.

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

На рисунке 4.4 представлен графический интерфейс пользователя программы ReActVision со встроенным модулем распознавания текста.

Рисунок 4.4 - Графический интерфейс ППО ReActVision

4.3 Прикладная программная система для решения задачи распознавания объектов в системе автоматического извлечения деталей из контейнера

Система Lynkeus предназначена для решения двух робототехнических задач:

1) автоматическое извлечение деталей из контейнера;

2) безопасное взаимодействие человек-машина.

Особенность системы Lynkeus заключается в использовании сенсоров, основанных на новой технологии - PMD. Эти сенсоры представляют собой компактные камеры, способные генерировать как обычные 2-мерные изображения в градациях серого, так и 2,5-мерные изображения, которые также содержат информацию о дальности каждой точки объекта до камеры (см. рис. 3.28). При использовании данной технологии и разработанного в данной диссертации иерархического итерационного метода были достигнуты результаты, позволяющие говорить о повышении эффективности при решении вышеупомянутых задач.

Задача автоматического извлечения деталей из контейнера состоит из следующих подзадач (см. также рис. 4.6):

1) моделирование 3-мерной сцены;

2) анализ сцены;

3) определение точек захвата;

4) разработка стратегии извлечения деталей; (

5) планирование траектории движения манипулятора без коллизий.

Эффективность и точность решения последних трёх задач сильно зависит от результатов решения задачи анализа сцены, т.е. от задачи распознавания объектов и определения их положений и ориентаций в пространстве. Для решения данной задачи в системе Lynkeus и используется разработанный модуль, основанный на иерархическом итерационном методе.

Графический интерфейс разработанного прикладного ПО системы представлен на рисунке 4.5.

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

Рисунок 4.5 - Графический интерфейс ППО системы Lynkeus

Рисунок 4.6 - Архитектура системы Lynkeus 4 Выводы по четвёртой главе

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

2. Разработанное программное обеспечение было успешно внедрено в следующие промышленные системы:

- Stryker Leibinger - система автоматического планирования медицинских операций;

- ReActVision - система автоматического контроля качества при производстве пьезо-моторов фирмы Elliptec.;

- Lynkeus - система фирмы KUKA Robotics автоматического извлечения деталей из контейнера.

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

Заключение

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

2. Разработано оригинальное алгоритмическое обеспечение, состоящее из системы взаимосвязанных алгоритмов и процедур, включающих в себя иерархическую оптимизацию, иерархическое сопоставление, расчёт критерия качества с использованием матричного представления исходных данных, деформацию прототипов распознаваемых объектов, итерационное сопоставление и иерархизацию прототипов распознаваемых объектов. Разработанные процедуры позволяют повысить точность и сократить время распознавания объектов.

3. Разработана архитектура универсальной системы распознавания объектов, основанная на предложенном иерархическом итерационном методе распознавания, а также методика её использования при решении различных классов практических задач.

4. Разработано прикладное программное обеспечение на базе языка С++ с использованием кроссплатформенной библиотеки обработки изображений

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

5. Результаты проведённого сравнительного анализа эффективности разработанного метода распознавания объектов с использованием разработанного программного обеспечения показали, что:

- при решении задачи регистрации медицинских изображений обеспечивается уменьшение времени распознавания по сравнению с классическим методом сопоставления и методом Покрандта в 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 раза.

1. Автоматическая регистрация медицинских томограмм головного мозга с использованием градиентного метода / Ю. Граф, К. В. Сафронов, И. М. Чушенков, X. Вёрн // Матер. 7-й межд. науч. конф. CSIT'2005. Т. 1. 2005. С. 174-179.

2. Анисимов, Б. В. Распознавание и цифровая обработка изображений: Учеб. пособие для студентов вузов / Б. В. Анисимов, В. Д. Курганов, В. К. Злобин. М.: Высшая школа, 1983. 295 с.

3. Бахвалов, Л. М. Численные методы / JI. М. Бахвалов. М.: Наука, 1973. 630 с.

4. Башмаков, А. И. Интеллектуальные информационные технологии / А. И. Башмаков, И. А. Башмаков. М.: Изд-во МГТУ им. Н.Э.Баумана, 2005. 304 с.

5. Вапник, В. Н. Теория распознавания образов. Статистические проблемы обучения / В. Н. Вапник, А. Я. Червоненкис. Москва: Наука, 1974. 416 с.

6. Введение в контурный анализ и его приложение к обработке изображений и сигналов / Под ред. Я. А. Фурмана. М.: ФИЗМАТЛИТ, 2002. 592 с.

7. Гайдышев, И. Анализ и обработка данных: специальный справочник / И. Гайдышев. СПб: Питер, 2001. 752 с.

8. Гашников, М. В. Методы компьютерной обработки изображений: Учеб. пособие / М. В. Гашников, Н. И. Глумов, Н. Ю. Ильясова. М.: Физм-атлит, 2001. 780 с.

9. Гонсалес, Р. Мир цифровой обработки: Пер. с англ. / Р. Гонсалес, Р. Вудс. М.: Техносфера, 2005. 1072 с.

10. Горбат, А. Н. Обучение нейронных сетей / А. Н. Горбань. М.: СП Параграф, 1990. 160 с.

11. Горелик, А. Л. Современное состояние проблемы распознавания. Некоторые аспекты / А. Л. Горелик, И. Б. Гуревич, В. А. Скрипкин. М.: Радио и связь, 1985. 160 с.

12. Горелик, А. Л. Методы распознавания: Учеб. пособие / А. Л. Горелик, В. А. Скрипкин. 2-е, перераб. и доп. изд. М.: Высшая школа, 1984. 208 с.

13. Гренандер, У. Лекции по теории образов: В 3 т.: Пер. с англ. / У. Грена-ндер. М.: Издательство "Мир", 1979. Т. 1: Синтез образов. 384 с.

14. Гренандер, У. Лекции по теории образов: В 3 т.: Пер. с англ. / У. Гренандер. М.: Издательство "Мир", 1981. Т. 2: Анализ образов. 447 с.

15. Гренандер, У. Лекции по теории образов: В 3 т.: Пер. с англ. / У. Гренандер. М.: Издательство "Мир", 1983. Т. 3: Регулярные структуры. 432 с.

16. Гринберг, А. Д. Цифровые изображения: Практ. руководство / А. Д. Гринберг. Минск: Попурри, 1997. 399 с.

17. Грузман, И. С. Цифровая обработка изображений в информационных системах: Учеб. пособие / И. С. Грузман, В. С. Киричук, В. П. Косых. Новосибирск: НГТУ, 2000. 155 с.

18. Грузман, И. С. Цифровая обработка изображений в информационных системах: Учебник / И. С. Грузман, B.C. Киричук, В. П. Косых. Новосибирск: Изд-во НГТУ, 2002. 351 с.

19. Дуда, Р. Распознавание образов и анализ сцен: Пер. с англ. / Р. Дуда, П. Харт. М.: Мир, 1976. 511 с.

20. Емельянов, В. В. Теория и практика эволюционного моделирования / В. В. Емельянов, В. В. Курейчик, В. М. Курейчик. М.: ФИЗМАТЛИТ, 2003. 432 с.

21. Журавлёв, В. Избранные научные труды / В. Журавлёв. М.: Магистр, 1998. 420 с.

22. Искусственный интеллект: В 3 т. / Под ред. Д. А. Поспелова. М.: Радио и связь, 1990. Т. 2: Модели и методы. Справочник. 304 с.

23. Комарцова, Л. Г. Нейрокомпьютеры: Учеб. пособие для вузов / Л. Г. Ком-арцова, А. В. Максимов. 2-е, перераб. и доп. изд. М.: Изд-во МГТУ им. Н.Э.Баумана, 2004. 400 с.

24. Лакин, Г. Ф. Биометрия / Г. Ф. Лакин. М.: Высш.шк., 1990. 352 с.

25. Лившиц, Ю. Статистические методы распознавания образов / Ю. Лившиц. Режим доступа: http://yury.name/modern/07modernnote.pdf, свободный.

26. Мамаев, И. P. Pmd технология: Особенности калибровки pmd камеры / И. Р. Мамаев, К. В. Сафронов, X. Вёрн // Информатика, управление и компьютерные науки : сб. ст. 3-й per. зимн. шк.-сем. аспирантов и молодых учёных. 2008. С. 154-160.

27. Методы компьютерной обработки изображений / М. В. Гашников, Н. И.

28. Глумов, Н. Ю. Ильясова и др.; Под ред. В. А. Сойфера. 2-е, испр. изд. М.: ФИЗМАТЛИТ, 2003. 784 с.

29. Поцепаев, Р. В. Эффективный алгоритм предобработки изображений для структурных методов распознавания рукописных символов / Р. В. Поцепаев, И. Б. Петров // Исследовано в России. Т. 19. 2003. С. 181190.

30. Приоров, А. Л. Цифровая обработка изображений: Учеб. пособие / A. JI. Приоров, А. Н. Ганин, В. В. Хрящев. Ярославль: ЯрГУ, 2001. 216 с.

31. Путятин, Е. Обработка изображений в робототехнике / Е. Путятин, С. Аверин. М.: Машиностроение, 1990. 320 с.

32. Распознавание образов. Исследование живых и автоматических распознающих систем: Пер. с англ. М.: Изд-во "Мир", 1970. 288 с.

33. Сафронов, К. В. Комбинированный метод регистрации медицинских изображений с использование градиентной и взаимной информации / К. В. Сафронов, И. М. Чушенков, X. Вёрн // Матер. 8-й межд. науч. конф. CSIT'2006. Т. 1. 2006. С. 7-10.

34. Сафронов, К. В. Применение алгоритмов оптимизации для решения задачи распознавания образов / К. В. Сафронов, И. М. Чушенков, X. Вёрн // Матер. Всерос. молодёжи, науч.-техн. конф. Т. 3. 2007. С. 46-47.

35. Сафронов, К. В. Применение алгоритмов оптимизации для решения задачи распознавания символов / К. В. Сафронов, И. М. Чушенков, X. Вёрн // Вычислительная техника и новые информационные технологии: межвуз. научн. сб. 2007. С. 92-97.

36. Сафронов, К. В. Распознавание текста с использование алгоритмовоптимизации / К. В. Сафронов, И. М. Чушенков, X. Вёрн // Матер. 9-й межд. науч. конф. CSIT'2007. Т. 1. 2007. С. 85-89.

37. Сафронов, К. В. Решение задачи извлечения деталей из контейнера с использованием иерархического итерационного метода распознавания образов / К. В. Сафронов, И. М. Чушенков, X. Вёрн // Матер, межд. конф. Robotik 2008. 2008. С. 3-6.

38. Смолин, Д. В. Введение в искусственный интеллект: конспект лекций / Д. В. Смолин. М.: ФИЗМАТЛИТ, 2004. 208 с.

39. Соснин, П. И. Методический комплекс по дисциплине: Распознавание образов и анализ сцен / П. И. Соснин. Режим доступа: old.ulstu.ru/people/sosnin/umk/ImageRecognitionandSceneAnalysis,

40. Старовойтов, В. В. Локальные геометрические методы цифровой обработки и анализа изображений / В. В. Старовойтов. Минск: Ин-т техн. кибернетики, 1997. 282 с.

41. Таха, X. А. Введение в исследование операций: Пер. с англ. / X. А. Таха. 7-е изд. М.: Издательский дом "Вильяме", 2005. 912 с.

42. Томашевич, Н. С. Метод реализации инвариантности к аффинным преобразованиям при распознавания двумерных изображений / Н. С. Томашевич, Д. С. Томашевич, А. И. Галушкин // Информационные технологии. 2001.

43. Ту, Д. Принципы распознавания образов: Пер. с англ. / Д. Ту, Р. Гонсалес. М.: Мир, 1978. 413 с.

44. Федотов, Н. Методы стохастической геометрии в распознавании образов / Н. Федотов. М.: Радио и связь, 1990. 142 с.

45. Форсайт, Д. А. Комьютерное зрение. Современный подход: Пер. с англ. / Д. А. Форсайт, Ж. Понс. М.: Издательский дом "Вильяме", 2004. 928 с.

46. Фурман, Я. А. Цифровые методы обработки и распознавания бинарных изображений / Я. А. Фурман, А. Н. Юрьев, В. В. Яншин. Красноярск: Изд-во Красноярск, 1992. 245 с.

47. Bachem, A. Robust visual servoing: Examination of cameras under different illumination conditions / A. Bachem, T. Mtiller, H. H. Nagel. 2001.

48. Basri, R. Recognition by prototypes / R. Basri. 1993.

49. Bebis, G. Using genetic algorithms for 3d object recognition / G. Bebis, S. Louis, S. Fadali. 1998.

50. Belongie, S. Matching shapes / S. Belongie, J. Malik, J. Puzicha. 2001.

51. Ben-Ezra, M. Model based pose estimator using linear-programming / M. Ben-Ezra, S. Peleg, M. Werman. 2000.

52. Berger, M. 3d model based pose determination in real-time: Strategies, convergence, accuracy / M. Berger, T. Auer, G. Bachler. 2000.

53. Besl, P. J. Three-dimensional object recognition / P. J. Besl, R. C. Jain. 1985.

54. Chin, R. T. Model-based recognition in robot vision / R. T. Chin, C. R. Dyer. 1986.

55. Cipolla, R. Visually guided grasping in unstructed environments / R. Cipolla, N. Hollinghurst. 1996.

56. Deformation models for image recognition / D. Keysers, T. Deselaers, C. Gol-lan, N. Hermann. 2007.

57. Faugeras, O. The Geometry of Multiple Images / O. Faugeras, Q. T. Luong. Cambridge: The MIT Press, 2001. 644 pp.

58. Hartley, R. Multiple View Geometry in Computer Vision / R. Hartley, A. Zis-serman. Second edition. Cambridge: University Press, 2000. 655 pp.

59. Ikeuchi, K. Picking up an object from a pile of objects / K. Ikeuchi, В. K. P. Horn, S. Nagata. 1983.

60. Improving visually servoed disassembly operations by automatic camera placement / F. Kececi, M. Топко, H. H. Nagel, V. Gengenbach. 1998.

61. Jaehne, B. Digital image processing / B. Jaehne. Fifth edition. Berlin: Springer, 2002. 585 pp.

62. Jain, A. K. Statistical pattern recognition: A review / A. K. Jain. 2000.

63. Johnson, A. E. Surface matching for object recognition in complex 3-d scenes / A. E. Johnson, M. Hebert. 1998.

64. Как, A. Experimental state of the art in 3d object recognition and localization using range data / А. Как, J. Edwards. 1996.

65. Как, A. Multisensor fusion for sensory intelligence in robotics / А. Как, A. Kosaka. 1996.

66. Keller, M. G. Matching Algorithms and Feature Match Quality Measures for Model-Based Object Recognition with Applications to Automatic Target Recognition: Ph.D. thesis / New York University. 1999.

67. Kim, S. Automatic model-based 3d object recognition by combining feature matching with tracking / S. Kim, I. S. Kweon. 2005.

68. Kragic, D. Robust visual servoing / D. Kragic, H. I. Christensen// The International Journal of Robotics Research. 2002. Vol. 22, no. 10-11. Pp. 923-939.

69. Kragic, D. Vision techniques for robotic manipulation and grasping / D. Kragic, H. I. Christensen // Proc. International Symposium on Robotics (ISR 2002). 2002. October 7-11.

70. Kragic, D. Visual servoing meets the real world / D. Kragic, H. I. Christensen // Visual Servoing. Lausanne: IEEE, 2002. October.

71. Leibe, B. Segmentierungsfreie Objekterkennung unter Verwendung von Tiefenbildern: Ph.D. thesis / Universitat Stuttgart. 2001.

72. Lepetit, V. Monocular model-based 3d tracking of rigid objects: A survey / V. Lepetit, P. Fua. 2005.

73. Li, H. Feature matching and pose estimation using newton iteration / H. Li, R. Hartley. 2005.

74. Magnor, M. A. Geometry-based automatic object localization and 3-d pose detection / M. A. Magnor. 2002.

75. Maier, D. Fast and accurate closest point search on triangulated surfaces and its application to head motion estimation / D. Maier, J. Hesser, R. Manner. 2000.

76. Marchand, E. Features tracking for visual servoing purpose / E. Marchand, F. Chaumette // Advances in Robot Vision From Domestic Environments to Medical Applications. Sendai, Japan: 2004. September. Pp. 10-20.

77. Model-based vision for robotic manipulation of twisted tubular parts: Using affine transforms and heuristic search / S. Wang, R. Cromwell, А. Как et al. 1994.

78. Muller, M. Entnahmestrategien zur Objektereinzelung mittels Industrier-obotern: Picking Strategies for Object Singularization using Industrial Robots: Ph.D. thesis / Universitat Karlsruhe (TH). 2001.

79. Mtiller, M. Grasping and reliable picking of overlapping objects in unstructered scenes / M. Muller, T. Langle, H. Worn. 1999.

80. Muller, M. Secure picking of disarranged objects using probabilistic reasoning / M. Muller, T. Langle, H. Worn. 2000.

81. Ohba, K. Recognition of the multi specularity objects for bin-picking task / K. Ohba, K. Ikeuchi. 1996.

82. Ohba, K. Recognition of the multi-specularity objects using the eigen-window / K. Ohba, K. Ikeuchi. 1996.

83. Ohba, K. Visual learning and object verification with illumination invariance / K. Ohba, Y. Sato, K. Ikeuchi. 1995.

84. Pokrandt, P. Automatische Uberlagerung medizinischer Bilddatensatze: Ph.D. thesis / Universitat Karlsruhe (TH). 1997.

85. Pope, A. Model-based object recognition, a survey of recent research: Tech. rep. / A. Pope: University of British Columbia, 1994.

86. Rahardja, K. Vision-based bin-picking: Recognition and localization of multiple complex objects using simple visual cues / K. Rahardja, A. Kosaka. 1996.

87. Robust detection of object displacements in unstructured scenes / M. Mtiller, S. Stepanov, T. Langle, H. Worn. 1999.

88. Robuste positionierung eines roboters mittels visual servoing unter verwen-dung einer trust-region-methode / N. T. Siebel, O. Lang, F. Wirth, A. Graser. 1999.

89. Sanz, P. J. Real-time grasping of unknown objects based on computer vision / P. J. Sanz, A. P. del Pobil, J. M. Inesta. 1997.

90. Shape from shading: A survey / R. Zhang, P. Tsai, J. E. Cryer, M. Shah. 2000.

91. Sorg, M Visual Tracking and Grasping of a Dynamic Object: From the Human Example to an Autonomous Robotic System: Ph.D. thesis /, Universitat Mtinchen. 2003.

92. Takenouchi, A. Hough-space-based object recognition tightly coupled with path planning for robust and fast bin-picking / A. Takenouchi, N. Kanamaru, M. Mizukawa. 1998.

93. Theoridis, S. Pattern recognition / S. Theoridis, K. Koutroumbas. Second edition. San Diego: Elsevier, 2003. 689 pp.

94. Toward true 3d object recognition / J. Ponce, S. Lazebnik, F. Rothganger, C. Schmid // CVPR Workshop on Generic Object Recognition and Categorization. 2004.

95. Towards the integration of object recognition and visual servoing for disassembly of used cars / M. Топко, V. Gengenbach, K. Schafer et al. 1997.

96. Towards visually servoed manipulation of car engine parts / M. Топко, К. Schafer, F. Heimes, H. H. Nagel. 1997.

97. Umeda, K. Industrial vision system by fusing range image and intensity image / K. Umeda, T. Arai. 1994.

98. Visual determination of 3d grasping points on unknown objects with a binocular camera system / A. Hauck, J. Riittinger, M. Sorg, G. Farber. 1999.

99. Visual tracking of an end-effector by adaptive kinematic prediction / A. Ruf, M. Топко, R. Horaud, H. H. Nagel. 1997.

100. Wendt, A. 3d-matching von anlichen punktwolken in der huftendoprothetik / A. Wendt. 2000.

101. Winkelbach, S. Gradientenbasierte Rekonstruktion von 3d-Oberflachen: Ph.D. thesis / Universitat Braunschweig. 2001.

102. Wunsch, P. Registration of cad-models to images by iterative inverse perspective matching / P. Wunsch, G. Hirzinger. 1996.

103. Yamany, S. M. Free-form object recognition and registration using surface signatures / S. M. Yamany, A. A. Farag, A. El-Bialy. 1999.