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

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

УДК 519.68; 681.513.7; 612.8.001.57; 007.51/.52

ЛОБИВ

Игорь Васильевич

ПРОГРАММНЫЕ СИСТЕМЫ ДЛЯ

ИДЕНТИФИКАЦИИ И ЛОКАЛИЗАЦИИ ОБЪЕКТОВ В ИЗОБРАЖЕНИЯХ

05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико - математических наук

Красноярск 2004

Работа выполнена в Институте систем информатики СО РАН

Научный руководитель: Мурзин Федор Александрович,

кандидат физико - математических наук

Официальные оппоненты: Кашкин Валентин Борисович

доктор технических наук, профессор

Пестунов Игорь Алексеевич кандидат физико - математических наук

Ведущая организация: Институт вычислительной математики

и математической геофизики СО РАН

Защита состоится 18 марта 2004 г. в 14 ч. 00 мин. на заседании диссертационного совета Д 212.098.03 в Красноярском государственном техническом университете по адресу:

666074, г.Красноярск, ул. Киренского, 26, ауд 4-17,

тел. (8-3912) - 49-73-81, факс (8-3912) - 49-79-90

С диссертацией можно ознакомиться в научной библиотеке Красноярского государственного технического университета

Автореферат разослан 16 февраля 2004 г.

Ученый секретарь Диссертационного совета,

кандидат технических наук, профессор —— Вейсов Е.А.

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

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

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

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

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

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

Один из лидеров по времени поиска среди таких систем является продукт американской фирмы Datacube - MaxVision Toolkit [http://www.datacube.com], который обладает рядом неоспоримых достоинств: возможность поиска образца, искаженного аффинным преобразованием, нелинейная коррекция освещенности. Но основным недостатком метода нормализованной корреляции оттенков серого, на котором основан продукт, является большая вычислительная сложность. Это стимулирует поиск новых идей и алгоритмов для решения данной задачи.

Нельзя не отметить вклад фирмы ABBY Software House в создание систем автоматического распознавания текстов. Продукт FineReader является одним из лучших в мире для этой задачи. Одним из недостатком данного продукта является чувствительность к большим (больше 15 градусов) углам поворота сканируемого изображения. Таким же недостатком обладают

з

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

Цель работы

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

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

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

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

3) локализация на фотографическом изображении шаблона и распознавание содержащегося в нём текста;

4) восстановление положения движущегося тела по информации, получаемой с множества одномерных видеокамер.

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

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

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

Программная система созданная на основе этого метода успешно локализует фрагменты, искаженные преобразованием масштаба и поворота.

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

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

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

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

Практическая ценность

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

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

Результаты работы докладывались на международной конференции «Современные проблемы прикладной математики и механики: теория, эксперимент и практика», посвященной 80-летию академика Н.Н. Яненко в 2001 г., на Пятой международной конференции памяти академика А.П. Ершова «Перспективы систем информатики» в 2003 г., на Международной конференции "Вычислительные технологии — 98", а также в Институте систем информатики СО РАН на семинаре «Конструирование и оптимизация программ» (председатель семинара д.ф.-м.н. Касьянов В.Н.) и на семинаре в Институте вычислительной математики и математической геофизики СО РАН (председатель семинара д.т.н. Пяткин В.П.).

Публикации. Автором опубликовано 20 печатных работ, из них по теме диссертации - 14 работ.

Структура и объем работы

Диссертационная работа состоит из введения, четырех глав и списка литературы. Объем диссертации - 116 стр. Список литературы содержит 60 наименований. Работа включает 45 рисунков и графиков, полученных в результате расчетов на ЭВМ.

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

Во введении обосновывается актуальность темы исследований и приводится краткое содержание работы.

В первой главе представлены алгоритмы и дано краткое описание программной системы для быстрого поиска фрагмента изображения в другом изображении. При этом фрагмент может быть повернут и/или изменен его масштаб.

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

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

Один из таких продуктов — MaxVision Toolkit фирмы Datacube [http ://www.datacube.com].

Существуют и другие программные и программно-аппаратные комплексы, осуществляющие поиск объектов теми или иными методами

[http://www.optimas.com, http://www.way2c.com, http://www.impuls-

imaging.com, http: //www.binary-technologies. de].

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

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

Пользовательский интерфейс обеспечивает удобное управление функциями системы и вывод результатов в понятной форме. При обработке изображений в диссертации используется система цветовых координат RGB.

Цветное изображение размером пхт задается тремя матрицами Sr =SR(i,j), SG=SG(i,j) = SB (/, j), где 0 < i S и — 1, OïjZm-l.

Значения элеменгов матриц SR (i, j), SG (/, j) и SB (/, j) изменяются в пределах от 0 до 255.

Пусть точкиимеют цвета (r,g,b) и (r',g',b*) p = (i,j) И p' = (i',/) имеют цвета (r,g,b) и (r\g',b')

соответственно, S„(i,j) = r, SG(i,j) = g, SB(i,j) = b, SR(i',j')-r',

S0V'j') = g', SB(ÏJ')=b'.

Тогда цветовое расстояние определяется, как cd(p, р') = max{ I SR(p)-SR (p') |, | Sc (p) - SG (p') |, | SB (p) - SB (p') |}

Вводится такая константа что если выполнено условие

cd(p, p') < Cv , TO считается, ЧТО p, p' ШР™ ппннягпньш TTRPT_

Евклидово расстояние, оппепеляется, как р(р, p') = -\l(i- О2 + (j ~ j*)2 ■

Пусть - некоторое фотографическое изображение,

Sc =(SR,SG,SB) - образец для локализации.

Qrj ТТП ТТЛ Л А ЛФЛТТФ П ТА Л i TFTA ^Т Т ТТГ1ТГГТ1 ФПТЛЛТТ ТТЛТ/"Л ГТТГПЛП01Т1ТТ ТТТ /Клоп i^T тт

S' = (S'R, SG, S'„) с S, что где F = foM2<>M}°R

- композиция функций:

— поворот на некоторый угол относительно центра ,

М1:5[С —> - изменения масштаба вдоль направления -1_ ширине М2 г^г —- изменения масштаба вдоль направления Л высоте / —» - коррекция интенсивности (яркости и/или контрастности). 771 (5е) -адаптивный порог для 5е,

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

Он состоит из двух этапов — предварительной обработки и собственно поиска.

Предварительная обработка включает в себя несколько подэтапов: низкочастотную фильтрацию, медианную фильтрацию.

Далее следует подэтап выделения контуров.

Пусть р\ р' — две точки исследуемого изображения:

S{p) = (г',g',b'), S(p-) = (г",g',b').

Используется обозначение Ba(p) = Bn(i,j) — ювацраг размером их и с центром в точке р = (/,_/'), где п — нечетное.

П cd[Bm(p)] = max{cd(p', р"): р\ р"е Вт(р)} максимальное цветовое расстояние в окрестности исследуемой точки.

Заключение о том, проходит контур через точку или нет, фиксируется соответствующими значениями функции f (0 или 1 соответственно).

ГО, ifcd[Bm(p)]>Cv,

Яр)-

l,if cd[Bm(p)]<Cv

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

ё{р,р') = а-р{р,р') + {1-а)-са(р,р), 0<а< 1.

Наиболее сложным этапом алгоритма является построение древообразной поисковой структуры, ассоциированной с данным изображением.

На построение данной структуры затрачивается некоторое время, но после ее создания появляется возможность находить опорные точки за логарифмическое время, т.е. за C-log(nXm) шагов, где С - константа, характеризующая время выполнения одного шага поиска и не зависящая от размеров исходного изображения.

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

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

Пусть Rrs(i,j) - соответствующий прямоугольник размера rxs. Далее с каждым Rr^(i,j) ассоциируется определенная на рассматриваемой палитре характеристическая функция Zkjj- Функция Xkjj показывает, существует ли точка, имеющая цвет в грубой палитре, в

прямоугольнике Rr г (j, j) на уровне k.

Метод построения грубых палитр состоит в том, что последние три бита значений r, g, b для любой точки полагаются равными нулю.

В итоге, вместо 16М цветов получается 215 - Ъ2К цветов.

Множество связанных с каждым узлом дерева характеристических функций Х = {Хкц'является той самой специальной структурой данных, упоминавшейся выше.

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

р2 3

"=1

р5

Г» р,

Рис. 3. Рекурсивный поиск опорных точек

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

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

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

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

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

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

Такая система успешно реализована, в ней в качестве аппаратной части выступает обычный компьютер Pentium-З, а в качестве программной части» используется логический модуль собственной разработки, устройству которого и посвящена данная глава.

К особенностям системы можно отнести следующие моменты:

1) камера должна обозревать от кадра к кадру одну и ту же область пространства;

2) допускаются цветовые шумы и небольшое дрожание видеокамеры;

3) отслеживаемые объекты могут плавно менять форму и размер;

4) не допускается пересечение движущихся объектов одного цвета на продолжительное время.

Метод можно условно разбить на три части:

1) выделение адаптивного фильтра;

2) локализация объектов;

3) идентификация локализованных объектов (идентификация одного и того же объекта в различных кадрах);

Выделение адаптивного фильтра - фильтр Я моделируется как медленно изменяемая последовательность изображений, которая позволяет адаптироваться к изменениям освещения и погодным условиям.

Локализация объектов.

Пусть /■) — текущий фрейм (кадр), a Я - фильтр. Вводится цвета точки р с координатами (х, у) на этих фреймах, т.е. с(,с8 соответственно.

Пусть — объединение всех областей на фрейме ^, в которых могут находиться объекты.

Вводится Й^.] £ЙМ — объединение всех областей, в которых находятся идентифицированные объекты на предыдущем фрейме .

Если С1'м =0., то производится сравнение только с фильтром Я, то есть ре с, *сй

В противном случае, решение о том, что точка р принадлежит Й, принимает™ (^тт^тппттттдл* ммгг.г'м\т •

если^е£2М'Т0 с, *ск>

если р е ,то р е £2,, фф с1 * .

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

л

Яц» %{-* _;_" ^

Рис.4. Внешний вид программной системы

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

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

Дополнительные требования:

1) фон должен быть примерно одного цвета;

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

Геометрия маркера представлена как набор связанных векторов. Следовательно, геометрия может быть легко изменена. Алгоритмы универсальны, т.е. работают с любыми символами.

Обработка изображения делится на две стадии: МРМ (Модуль Распознавания Маркера) и (МИМ) Модуль Интерпретации Маркера.

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

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

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

Задача состоит в том, чтобы по имеющимся данным в реальном времени восстанавливать положение твердого тела с максимальной точностью. Осложняющие факторы:

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

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

Математическая постановка.

Положение тела в пространстве можно представить в виде Ах + b, где b = (u,v,w) — вектор сдвига, A - ортогональная матрица поворота тела относительно начального положения.

Задача будет решена, если будут найдены величины A,b, при которых отклонение положения маркеров от соответствующих плоскостей будет минимально в некоторой норме.

Для эффективного решения этого класса задач необходимо выявить проблемы, которые возникают у исследователей в данной области (Vicon, Acty, Advanced Mechanical Technology, DKH, Gsport, Motion Analysis, Peak Performance, PhaseSpace, Phoenix Technologies, Polhemus и Qualisys). Для этого дается оценка объема информации, который должен обрабатываться в реальном времени для обычных видеокамер и для одномерных.

Рассматривается профессиональная 2d камера среднего класса, с характеристиками: 1024x1024 True Color размер изображения,* 300 fps -рабочая частота. (Так как частота промышленных мониторов и телеприемников 24-30 fps, соответственно, для того, чтобы изображение на экране было непрерывным, нужна частота в 10 раз большая, т.е. 300 fps.)

Получается поток 900МЬ в секунду лишь с одной видеокамеры. Но одной камеры недостаточно для того, чтобы восстановить положение тела в пространстве. В решениях фирмы «Vicon» применяются наборы из 4, 6, 12, 24 видеокамер. Если взять самую простую конфигурацию из 4х камер, получается информационный поток объемом более 3GB в секунду.

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

Предлагается новое решение этого вопроса - использование одномерных видеокамер. Далее оценивается объем информационного потока для одномерных камер. 1024x1 - размер изображения, 300 fps - условие на частоту то же самое. С одной камеры 900КЬ в секунду. Так как камер теперь нужно больше, то пусть будет 40 камер, итого около 40МЬ в секунду, эта цифра вполне реальна как для обработки, так и для передачи. Более того, за счет применения одномерных камер можно увеличить скорость обработки и точность.

Матрица А в явном виде представляется, как:

Пусть на данном временном шаге известны N плоскостей, заданных в виде (п/, X) = (¿¡, ¿ = 1...//, где л, = (а(,Ь(,с() - вектор нормали к плоскости, (о,о) - скалярное произведение, а также N точек Х,-=(дТ/.у^г/),, характеризующих координаты маркера в системе координат твердого тела (предполагается, что эта информация считывается из файла с описанием твердого тела).

Метод наименьших квадратов приводит к следующей задаче:

м

В итоге остается система трех нелинейных уравнений с тремя неизвестными р,д,г:

■ /г(р>Ч>г) = 0, или в векторном виде

/Ч/>) = О.где /г = (/1,/2,/3), Р = (р,д,г).

Для ее решения воспользуемся методом последовательных приближений Ньютона. Пусть на п-ом шаге известно приближение Р. =(Ря'Чп>гп)> тог£щ следующее приближение Рп+1 находится по формуле: =РЛ -где / — матрица Якоби преобразования Г.

эл

дд дг

Кг.

дд дг %

дд дг,

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

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

О ЛИЧНОМ ВКЛАДЕ АВТОРА

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

дР Уг 3Р

[др

третьей задачи диссертант был ответственным за реализацию алгоритма локализации маркера, программу распознавания текста реализовывали другие соавторы. В четвертой задаче автор диссертации участвовал в разработке алгоритмов, проводил проектирование и вывод наиболее сложных формул в системе символьных преобразований Maple vR4 и частично реализовывал программу на C++ (фильтрация и интерполяция данных).

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

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

1. Быстрый поиск (локализация) фрагмента фотографического изображения в другом изображении. Программное средство для локализации объектов по своим характеристикам не уступает лидеру в данной области, продукту Max Vision Toolkit фирмы Datacube и в некоторых случаях и превосходят его.

2. Распознавание и локализация движущегося объекта в видеопотоке. Основным результатом является метод «сверх» адаптивного фильтра и метод фильтрации одномерного шума, которые позволили решить две важные задачи: небольшие быстрые изменения угла зрения («дрожание») видеокамеры и устойчивость всей системы при внесении различных помех, например, MPEG-сжатие видеопотока с потерей качества.

3. Локализация на фотографическом изображении шаблона и распознавание содержащегося в нём текста. Время локализации маркера быстрее, чем у продукта лидера в области распознавания текста Fine Reader ABBY Software House. Речь идет о задаче, осложненной тем, что допускается поворот на произвольный угол и изменение масштаба маркера.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Дунаев А.А., Лобив И.В., Мехонцев Д.Ю., Мурзин ФА., Половинке О.Н., Семич Д.Ф., Чепель А.В., Яркое К.А. Алгоритмы быстрого поиска фрагментов фотографических изображений // Современные проблемы конструирования программ. - Новосибирск, 2002. - С. 88-109.

2. Мехонтцев Д.Ю., Лобив И.В., Селезнев К.С. Слежение и определение скорости движущихся на плоскости объектов в реальном времени // Современные проблемы конструирования программ. - Новосибирск, 2002.-С.243-246.

3. Лобив И.В., Мехонцев Д.Ю., Селезнев К.С. Слежение и определение скорости движущихся на плоскости объектов в реальном времени // Материалы междунар. конф. Современные проблемы прикладной математики и механики: теория, эксперимент и практика. - Новосибирск. -2001.-С. 112-114.

4. Мехонцев Д.Ю., Лобив И.В. Решение задачи нахождения оптимального положения тела в пространстве по данным, поступающим с одномерных камер для трехмерной оптической системы анализа движения объектов // Материалы междунар. конф. молодых ученых по математическому моделированию и информатике. - Новосибирск. — 2002. — С. 19-20.

5. Дунаев А.А., Кель А.Э., Лобив И.В., Мурзин Ф.А, Половинко О.Н., Черемушкин Е.С. Алгоритмы визуализации генетической информации // Материалы междунар. конф. памяти академика А.П. Ершова «Перспективы систем информатики». - Новосибирск, 2003. - С. 43-47.

6. Винокуров А.А., Ильин И.В., Лобив И.В., Мурзин Ф.А, Половинко О.Н., Семич Д.Ф. Программное обеспечение для поддержки процесса ядерного каротажа нефтяных скважин. // Материалы междунар. конф. памяти академика А.П. Ершова, «Перспективы систем информатики». -Новосибирск, 2003. - С. 40-43.

7. Лобив И.В., Мурзин Ф.А. "О распараллеливании PIC - метода" // Проблемы систем информатики и программирования. — Новосибирск 1999. - С. 146-155.

8. Вшивков В.А., Лобив И.В., Мурзин Ф.А. Параллельный алгоритм

решения задачи о взаимодействии потоков разряженной плазмы. // Проблемы систем информатики. - Новосибирск, 2001. - С. 6-82.

9. Лобив И.В., Мурзин Ф.А. О распараллеливании метода частиц в ячейках и метода дискретных вихрей // Материалы междунар. конф. Distributed Data Processing. - Новосибирск, 1998, С. 43-44.

10.Мурзин Ф.А., Лобив И.В. О распараллеливании метода дискретных вихрей // Тр. XVI Междунар. школы - семинара по численным методам механики вязкой жидкости. — Новосибирск, 1998. - С. 37-38.

11.Вшивков В А, Лобив И.В., Мурзин Ф.А Параллельный алгоритм на основе PIC-метода для расчета задач о взаимодействии потоков плазмы // Тр XVI Междунар. школы - семинара по численным методам механики вязкой жидкости. - Новосибирск, 1998. - С. 38-39.

12.Мурзин Ф.А., Лобив И.В. Исследование, вопросов, связанных с. распараллеливанием PIC-метода // Тр. XVI Междунар. школы - семинара по численным методам механики вязкой жидкости. - Новосибирск, 1998. - С. 44-46.

13.Cheremushkin E.S., Kel A.E., Lobiv I.V., Murzin F.A., Polovinko O.N. Genetic code and Visualization // Bioinformatics of Genom Regulation and Structure.- Novosibirsk, - 2002, - Vol. 1, - P. 94-97.

14.Дунаев А.А., Кель А.Э., Лобив И.В., Мурзин Ф.А., Половинко О.Н., Черемушкин Е.С. Визуализация генетической информации // Новосибирск, // Новые информационные технологии в науке и образовании. - Новосибирск, 2003. - С. 147-156.

15.Винокуров А.А., Ильин И.В., Лобив И.В., Мурзин Ф.А., Половинко О.Н., Семич Д.Ф. О некоторых задачах, связанных с автоматизацией процесса ядерного каротажа нефтяных скважин // Новые информационные технологии в науке и образовании. - Новосибирск, 2003.-С. 112-123.

16.Дунаев А.А., Лобив И.В., Мехонцев Д.Ю., Мурзин Ф.А., Половинко О.Н., Семич Д.Ф., Ярков К.А Алгоритмы быстрого поиска повернутых и масштабированных образов внутри данного изображения. // Материалы междунар. конф. «Перспективы систем информатики». - Новосибирск, 2003. - С. 50-53.

17.Лобив И.В., Мехонцев Д.Ю., Селезнев К.С. Слежение и определение скорости движущихся на плоскости объектов в реальном времени. // Доклады междунар. конф. молодых ученых по математическому моделированию и информатике, Новосибирск 2001. - С. 12-13.

18.Лобив И.В., Мехонцев Д.Ю., Мурзин Ф.А Восстановление положения тела в пространстве для системы реального времени анализа движения

объектов. // Тр. школы - конкурса молодых ученых ИСИ СО РАН «Теоретические и прикладные задачи информатики: новые подходы и решения». - Новосибирск, 2003. - С. 54-62.

19.Винокуров А.А., Ильин И.В., Лобив И.В., Мурзин Ф.А., Половинко О.Н., Семич Д.Ф. Программный комплекс, предназначенный для обработки результатов, полученных методом ядерного каротажа нефтяных скважин // Тр. школы - конкурса молодых ученых ИСИ СО РАН «Теоретические и прикладные задачи информатики: новые подходы и решения». — Новосибирск, 2003. — С. 23-31.

20.Мурзин Ф.А., Половинко О.Н., Лобив И.В. Распознавание текстур по пространственным закономерностям // Материалы междунар. конф. Новые информационные технологии в науке и образовании. -Новосибирск, 2003. - С. 256-268.

Лобив И.В.

ПРОГРАММНЫЕ СИСТЕМЫ ДЛЯ

ИДЕНТИФИКАЦИИ И ЛОКАЛИЗАЦИИ ОБЪЕКТОВ В ИЗОБРАЖЕНИЯХ

Автореферат

Подписано в печать Формат бумаги 60 X 90 1/16

Объем 1,1 уч.-изд. л. _Тираж 100 экз.

Отпечатано в ЗАО РИЦ «Прайс-курьер»,

630090, г. Новосибирск, пр. Ак. Лаврентьева, 6, тел. 34-22-02

Заказ №135

ВВЕДЕНИЕ.

1. БЫСТРЫЙ ПОИСК (ЛОКАЛИЗАЦИЯ) ФРАГМЕНТА ФОТОГРАФИЧЕСКОГО ИЗОБРАЖЕНИЯ В ДРУГОМ ИЗОБРАЖЕНИИ.

1.1. Обзор существующих методов и систем.

1.2. Описание метода, лежащего в основе программной системы локализации образца в изображении.

1.2.1. Определения и обозначения.

1.2.2. Низкочастотная фильтрация.

1.2.3. Медианная фильтрация.

1.2.4. Выделение контуров.

1.2.5. Дополнительные условия преобразований.

1.2.6. Выбор опорных точек.

1.2.7. Построение структуры вспомогательных данных.

1.2.8. Поиск опорных точек.

1.2.9. Поворот изображения.

1.2.10. Коррекция по яркости и контрастности.

1.2.11. Выбор адаптивных порогов.

1.3. Сравнение с аналогичными системами.

1.4. Описание реализации программы.

1.4.1. Общая схема реализации и интерфейс.

1.4.2. Выделение контуров.

1.4.3. Формирование вспомогательных данных.

1.4.4. Поиск опорных точек.

1.4.5. Основной цикл распознавания.

1.4.6. Локализация опорных точек с помощью деревообразной поисковой структуры.

1.5. Результаты тестовых испытаний.

1.6. Параллельный вариант метода.

1.7. Выводы.

2. РАСПОЗНАВАНИЕ И ЛОКАЛИЗАЦИЯ ДВИЖУЩЕГОСЯ ОБЪЕКТА В ВИДЕОПОТОКЕ.

2.1. Постановка задачи.

2.2. Описание метода.

2.2.1. Блок схема алгоритма.

2.2.2. Определение адаптивного фильтра.

2.2.3. Этап локализации объектов.

2.2.4. Обработка контуров.

2.2.5. Привязка контура к структуре цепочек.

2.3. Описание прораммной реализации.:.

2.4. Параллельный вариант метода.

2.4. Выводы.

3. ЛОКАЛИЗАЦИЯ НА ФОТОГРАФИЧЕСКОМ ИЗОБРАЖЕНИИ МАРКЕРА И РАСПОЗНАВАНИЯ СОДЕРЖАЩЕГОСЯ В НЁМ ТЕКСТА.

3.1. Постановка задачи.

3.2. Начальные предположения.

3.3. МРМ - Модуль Распознавания Маркера.

3.3.1. Нахождение отрезков на изображении.

3.3.2. Нахождение отрезков маркера.

3.4. МИМ — Модуль Интерпретации Маркера.

3.4.1. Нахождение символов в строке.

3.4.2. Идентификация символов.

3.5. Описание программного продукта.

3.6. Параллельный вариант метода.

4. ВОССТАНОВЛЕНИЕ ПОЛОЖЕНИЯ ДВИЖУЩЕГОСЯ ТЕЛА ПО ИНФОРМАЦИИ, ПОЛУЧАЕМОЙ С МНОЖЕСТВА ОДНОМЕРНЫХ ВИДЕОКАМЕР.

4.1. Постановка задачи.

4.2. Факторы, осложняющие решение задачи.

4.3. Математическая постановка задачи.

4.4. Аналогичные работы.

4.5. Описание метода.

4.5.1. Случай, когда на одном временном шаге данных (плоскостей) достаточно для однозначного восстановления положения тела.

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

4.5.3. Фильтрация шумов.

4.6. Описание программно-аппаратного комплекса.

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

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

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

• Быстрый поиск (локализация) фрагмента фотографического изображения в другом изображении.

• Распознавание и локализация движущегося объекта в видеопотоке.

• Локализация на фотографическом изображении маркера и распознавания содержащегося в нём текста.

• Восстановление положения движущегося тела по информации, получаемой с множества одномерных видеокамер.

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

Актуальность.

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

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

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

Один из лидеров по времени поиска среди таких систем является продукт американской фирмы Datacube - MaxVision Toolkit [http://www.datacube.com], который обладает рядом неоспоримых достоинств: поиск образца, искаженного аффинным преобразованием, нелинейной коррекции освещенности. Но основным недостатком метода нормализованной корреляции оттенков серого, на котором основан продукт, является большая вычислительная сложность. Это заставляет исследователей искать новые подходы к решению данной задачи.

Нельзя не отметить вклад фирмы ABBY Software House в создание систем автоматического распознавания текста. Продукт FineReader является одним из лучших в мире для этой задачи. Одним из недостатком этого продукта является чувствительность к большим (больше 15 градусов) углам поворота сканируемого изображения. Таким же недостатком обладают различные системы локализации и распознавания этикеток и штрих кодов. На сегодняшний день требуются быстро работающие решения в контексте данной задачи.

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

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

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

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

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

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

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

В первой главе представлены алгоритмы и дано краткое описание программной системы для быстрого поиска фрагмента изображения в другом изображении. При этом фрагмент может быть повернут и/или его масштаб изменен.

Поиск фрагментов в изображениях — важная задача, которая в том или ином виде возникает во многих отраслях. В качестве примера можно привести подсчет количества бактерий на фотоснимке, поиск заданного участка местности на аэрофотоснимке и т. д.

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

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

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

Особенностью данного алгоритма является также и то, что яркость и контрастность всего изображения и фрагмента могут быть различными.

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

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

Для работы пакета требуются специализированные аппаратные средства. Более подробную информацию о фирме и ее продуктах можно получить на веб-сайте фирмы [28].

Существуют и другие программные и программно-аппаратные комплексы, осуществляющие поиск объектов теми или иными методами [2932].

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

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

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

При обработке изображений в диссертации используется система цветовых координат RGB.

Цветное изображение размером п х т задается тремя матрицами sr =SR{iJ)t SG =SG(i,j) и SB =SB(i,j), где 0</<л-1, 0<у</и-1.

Значения элементов матриц SR(i,j), SG(i,j) и SB(i,j) изменяются в пределах от 0 до 255.

Предположим, что точки р = (i,j) и р' -(i\j') имеют цвета (r>g,b) и (r\g',b') , следовательно, Sr 0\ j) = г, SG (/, j) = g, (/, j) = b, $*('"./) = Л SG(i\f) = gSB{i'J') = b'. Цветовое расстояние o/(/7, p') = max{ | (p) - (//) |, 1(p) - SG (//) |,| (p) - SB (p') |}.

Введем константу Cy, такую, что если выполнено условие сс1(р,р')йСуу то считаем что точки р,р' имеют одинаковый цвет. При выполнении обратного неравенства — разный.

Евклидово расстояние p(p,p') = J(i-i')2 + (j~ j')2 >

Пусть S = (SR, SG, SB) - некоторое фотографическое изображение

Source Bitmap), Sc =(SR,SG,SB) - образец для локализации (Control Bitmap).

Задача состоит в том, чтобы найти такой локализованный фрагмент S' = (S'RyS'G,SB)czSt что £? = |s'-F(Sc)|<77j(Sc),r;ie F = I °М2 ° Мхо R -композиция функций:

R: Sc —> Sf - поворот на некоторый угол относительно центра Sc, М, :S,C —- изменения масштаба вдоль направления -L ширине М2 :Sl - изменения масштаба вдоль направления -L высоте S /: ^з —> 5*4 - коррекция интенсивности (яркости и/или контрастности),

Th(Sc)-адаптивный порог для

Zcd(PiP') /

Eq = \S- = pes.p'es".plp.p>о / , где Q- площадь SnS'.

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

Он состоит из двух этапов - предварительной обработки и собственно поиска.

Предварительная обработка включает в себя несколько подэтапов: низкочастотная фильтрация, медианная фильтрация.

Далее следует выделение контуров.

Пустьр\р" - две точки исследуемого изображения:

Обозначим Вт{р) - квадратную окрестность точки р со стороной квадрата 2т +1.

Пусть теперь cd[Bm(/?)] = шах{cd(p',рп): р',рп е Вт(р)} максимальное цветовое расстояние в окрестности Вт(р) исследуемой точки.

Заключение о том, проходит контур через точку или нет, фиксируется соответствующими значениями функции / (0 или 1 соответственно).

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

Наиболее сложным этапом алгоритма является построение древообразной поисковой структуры, ассоциированной с данным изображением.

S(p')= (r'>g'>b'), S(p") = (r",gn,bn).

О, ifcd[Bm{p)]>C, 1 ,ifcd[Bm(p)]<Cv g(p,p') = a • p') + (\-a)- cd(p, p'), 0 < a < 1.

На построение данной структуры затрачивается некоторое время, но после ее создания появляется возможность находить опорные точки за логарифмическое время, т.е. за С • log(w х т) шагов, где С - константа, характеризующая время выполнения одного шага поиска и не зависящая от размеров исходного изображения.

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

Для нумерации прямоугольников используются пары (i,j), кодирующие уровень разбиения, и порядковый номер прямоугольника.

Обозначим через Rrs(i,j) соответствующий прямоугольник размера rxs. Далее с Rr^(i,j) ассоциируется определенная на рассматриваемой палитре характеристическая функция Zkjj

Метод построения грубых палитр состоит в том, что последние три бита значений r,g,b для любой точки полагаются равными нулю.

В итоге, вместо 16М цветов получаем 215 = 32К цветов.

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

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

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

Отметим, что разработанный алгоритм допускает различные модификации, в том числе распространение на аффинный случай. Нами аффинный случай не реализовывался ввиду отсутствия заказчика на подобный программный продукт. Реализация же на инициативной основе затруднена ввиду высокой трудоемкости проекта.

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

Такого рода комплексы уже используются на дорогах в некоторых западных странах (например, Германия, производитель: концерн «Мерседес»).

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

Такая система была успешно реализована. В качестве аппаратной части выступает обычный компьютер Pentium-З, а в качестве программной части используется логический модуль собственной разработки, устройству которого и посвящена вторая глава.

К особенностям системы можно отнести следующее:

1) камера должна обозревать от кадра к кадру одну и ту же область пространства;

2) допускаются цветовые шумы и небольшое дрожание камеры;

3) отслеживаемые объекты могут плавно менять форму и размер;

4) не допускается пересечение движущихся объектов одного цвета на продолжительное время.

Метод можно условно разбить на три части:

1) построение адаптивного фильтра;

2) локализация объектов;

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

Построение адаптивного фильтра.

Фильтр моделируется как медленно изменяемая последовательность изображений, которая позволяет адаптироваться к изменениям освещения'и погодным условиям.

Локализация объектов.

Рассмотрим сгГ2м - объединение всех областей, где точно находятся объекты на предыдущем фрейме /•},.

Если =0, то просто производим сравнение с фреймом адаптивного фильтра R и выявляем области, отличные по цвету, - эти области и будут кандидаты в объекты.

В противном случае: еслир е , то р е Q{, о с, * сR, если р g ,то р е П,, о с,- ^ см.

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

Далее рассматриваются алгоритмы быстрого поиска маркеров на изображении и распознавания содержащегося в них текста.

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

Дополнительные требования.

• Фон должен быть примерно одного цвета.

• Прямоугольник и текст также должны быть одного цвета, отличающегося от фонового.

Заметим, что геометрия маркера представлена как набор связанных векторов. Следовательно, геометрия может быть легко изменена. Алгоритмы универсальны, т.е. работают с любыми символами.

Обработка изображения делится на две стадии: Модуль Распознавания Маркера (МРМ) и Модуль Интерпретации Маркера (МИМ), которые в свою очередь состоят из модулей, детально описанных далее.

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

В пространстве имеется твердое тело с известной геометрией, на котором в определенных местах закреплены светоизлучающие диоды, в дальнейшем называемые маркерами, которым присвоены уникальные номера. Также имеется набор одномерных детекторов, расположенных вокруг твердого тела, которые достаточно часто (200 - 300 раз в сек.) фиксируют положение маркеров. Каждый маркер обладает уникальными характеристиками (цвет, частота мерцания, и т.п. ), по которым детектор может отличить его от других маркеров и восстановить его номер. В силу одномерности детектора, о каждом маркере, попадающим в его поле видимости можно получить лишь уравнение плоскости, в которой этот маркер содержится. Все плоскости, получаемые от фиксированного детектора, пересекаются по одной прямой ("фокусная прямая").

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

Осложняющие факторы.

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

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

Математическая постановка.

Положение тела в пространстве можно представить в виде Ах + b, где 6 = (w,v,w) - вектор сдвига, А - ортогональная матрица поворота тела относительно начального положения.

Задача будет решена, если будут найдены величины А ,Ь, при которых отклонение положений маркеров от соответствующих плоскостей будут минимальны в некоторой норме.

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

Подсчитаем объем информации, который должен обрабатываться в реальном времени.

Рассмотрим обычную профессиональную 2d камеру, 1024x1024 True Color - размер изображения, получаемой с камеры. Требование на рабочую частоту камеры 300 fps. Так как частота промышленных мониторов и телеприемников 24-30 fps и для того чтобы изображение на экране было непрерывным, нужна частота в 10 раз большая, т.е. 300 fps.

Всего в результате лишь с одной камеры получается видеопоток 900МЬ в секунду. Но так как камер 4 (например, в системе Vicon 8i), получается более 3Gb в секунду.

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

Мы предлагаем принципиально новое решение этого вопроса. Посчитаем то же самое, но для одномерных камер:

1024x1 размер изображения,

300 fps — условие на частоту то же самое,

- с одной камеры 900КЬ в секунду.

Так как камер теперь нужно больше, то пусть будет 40 камер, итого около 40 Mb в секунду - эта цифра уже вполне реальна как для обработки, так и для передачи. Более того, за счет применения одномерных камер можно увеличить скорость обработки, а следовательно и точность.

Выпишем в явном виде представление матрицы А:

A = A(p,q,r) = с -г г с -q р

2 \ Р РЧ рг

1 + с

ЯР Ч rp rq г qr 2 У где с2 = \-(р2 +q2 +r2) = cos2 ф.

Пусть на данном временном шаге известны N плоскостей, заданных в виде {ni,X) = di, i = \.N, где nt = (a,,b{,c{) - вектор нормали к плоскости, (о,о) - скалярное произведение, а также N точек Xt = (xi,yj,zi), характеризующих координаты маркера в системе координат твердого тела (предполагается, что эта информация считывается из файла с описанием твердого тела).

Метод наименьших квадратов приводит к следующей задаче: n nitAXl+b)-diY-+m\n. 1

В итоге остается система трех нелинейных уравнений с тремя неизвестными p,q,r: f\(p,4>r) = 0 з (А ?>>*) = О или в векторном виде

Г(Р) = 0,гдс F = (fl9f2,f3), P = (p,q,r).

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

Пусть на n-ом шаге известно приближение Р„ =(p„,qп,г„), тогда следующее приближение Рл+1 находится по формуле :

Рл+1 =Рп -J~xF(Pn), где J - матрица Якоби преобразования F.

Wx. dp 8q dr j df2 df2 df2 dp 8q dr ф dq dr j

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

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

О личном вкладе автора.

Реализация описанных выше алгоритмов является достаточно трудоемкой задачей, и выполнялась коллективно. Наибольший вклад в первой задаче автор диссертации внес в разработку и реализацию следующих алгоритмов: быстрый поворот фрагмента изображения, метод адаптивных порогов, оптимизация древовидной поисковой структуры, контрольное сравнение, метод обратной связи между алгоритмом поиска и контрольного сравнения. Во второй задаче диссертанту полностью принадлежит реализация всех методов. Совместно с Мехонцевым Д.Ю. осуществлялась отработка алгоритмических деталей. При разработке третьей задачи диссертант был ответственным за реализацию алгоритма локализации маркера, программу распознавания текста реализовывали другие соавторы. В четвертой задаче автор диссертации участвовал в разработке алгоритмов, проводил проектирование и вывод наиболее сложных формул в системе символьных преобразований Maple vR4 и частично реализовывал программу на С++ (фильтрация и интерполяция данных).

Основные результаты диссертации состоят в следующем.

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

ЗАКЛЮЧЕНИЕ

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

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

• Быстрый поиск (локализация) фрагмента фотографического изображения в другом изображении.

• Распознавание и локализация движущегося объекта в видеопотоке.

• Локализация на фотографическом изображении шаблона и распознавание содержащегося в нём текста.

• Восстановление положения движущегося тела по информации, получаемой с множества одномерных видеокамер.

Все работы выполнялись для зарубежных заказчиков и применяются в коммерческих приложениях. Работы докладывались на международных конференциях. Опубликованы соответствующие статьи по материалам конференций. Например, результаты работы докладывались на международной конференции «Современные проблемы прикладной математики и механики: теория, эксперимент и практика», посвященной 80-летию академика Н.Н.Яненко в 2001 г., на Пятой международной конференции памяти академика А.П. Ершова «Перспективы систем информатики» в 2003 г., на Международной конференции "Вычислительные технологии - 98", а также в Вычислительном центре СО РАН, Институте физики полупроводников СО РАН и на конференции Distributed Data Processing - 98.

Автором опубликовано 20 печатных работ, из них по теме диссертации - 16 работ.

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

А именно, в первой главе рассмотрены в сравнении два продукта MaxVision Toolkit корпорации Datacube и ImageDemo. Из сравнения видно, что последний работает быстрее, а также ImageDemo работает с цветными изображениями, что недоступно MaxVision. Но у Datacube есть и преимущества, такие как возможность локализации перспективных (аффинных) преобразований изображений (в ImageDemo только поворот и масштаб), а также нелинейная коррекция освещенности изображения (в ImageDemo только линейная).

Во второй главе описано средство для локализации объектов .в видеопотоке. Основным результатом является метод определения «сверх адаптивного фильтра» и метод фильтрации одномерного шума, которые позволили решить две важные задачи: учесть небольшие быстрые изменения угла зрения (дрожание) камеры и обеспечить устойчивость всей системы при возникновении различных помех, например MPEG-сжатие видеопотока с потерей качества.

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

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

О личном вкладе автора.

Реализация описанных выше алгоритмов является достаточно трудоемкой задачей, и выполнялась коллективно. Наибольший вклад в первой задаче автор диссертации внес в разработку и реализацию следующих алгоритмов: быстрый поворот фрагмента изображения, метод адаптивных порогов, оптимизация древовидной поисковой структуры, контрольное сравнение, метод обратной связи между алгоритмом поиска и контрольного сравнения. Во второй задаче диссертанту полностью принадлежит реализация всех методов. Совместно с Мехонцевым Д.Ю. осуществлялась отработка алгоритмических деталей. При разработке третьей задачи диссертант был ответственным за реализацию алгоритма локализации маркера, программу распознавания текста реализовывали другие соавторы. В четвертой задаче автор диссертации участвовал в разработке алгоритмов, проводил проектирование и вывод наиболее сложных формул в системе символьных преобразований Maple vR4 и частично реализовывап программу на С++ (фильтрация и интерполяция данных).

1. Intelligent and Optimal Normalized Correlation for High- Speed Pattern Matching. Datacube Inc., 2000. - 13 p.

2. Russ, J.C. The image processing handbook / J.C. Russ. CRC Press Inc. 1992

3. Rosenfeld, А., Как A. C. Digital picture processing / A. Rosenfeld, А. С. Как. Academic Press, New York, 1976.

4. Krattenthaler, W. Point correlation: a reduced-cost template matching technique / W. Krattenthaler, K. J. Mayer, M. Zeiller // First IEEE International Conference on Image Processing. 1994.

5. Egmont-Petersen, M. Image processing with neural networks a review / M. Egmont-Petersen, D. de Ridder, H. Handels // Pattern Recognition. - 2002, Vol. 35, No. 10,-P. 2279-2301.

6. Rowley, H. Rotation Invariant Neural Network-Based Face Detection / H. Rowley, S. Baluja, T. Kanade // Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. 1998.

7. Haley, G.M. Rotation-invariant texture classification using a complete space-frequency model / G.M. Haley, B.S. Manjunath // IEEE Transactions on Image Processing. 1999. - P. 8:255-269.

8. Sun, H. Z. Robust extraction of moving objects from video sequences / H. Z. Sun, T. Feng, T. N. Tan // Proc. of the Fourth Asian Conference on Computer Vision. 2002, Vol.2. - P. 961-963.

9. Huwer, S. Adaptive Change Detection for Real-time Surveillance Applications / S. Huwer, H. Niemann // Workshop on Visual Surveillance in ECCV2000. -2000.

10. Ivanov, Y. Fast Lighting Independent Background Subtraction / Y. Ivanov, A. Bobick, J. Liu // Proc. of the IEEE Workshop on Visual Surveillance. -Bombay, 1998.-P. 49-55.

11. H.Karmannand, K.P. Moving object recognition using an adaptive background memory / K.P. Karmannand, A. vonBrandt // Proc. Time-Varying Image Processing and Moving Object Recognition. V. Capellini, Ed. 1990, vol.2.

12. Beymer, D. A real-time computer vision system for measuring traffic parameters / D.Beymer, P.McLauchlan, B.Coifman, J.Malik // Proc. IEEE Conf. Computer Vision and Pattern Recognition. Puerto Rico, 1997. - P.496-501.

13. Mosoud, O. Robust pedestrians tracking using model-based approach / O. Mosoud, P. Papanikolopoulos // Proc. IEEE Conf. Intelligent Transportation Systems. 1997. - P. 338 - 343.

14. Papanikolopoulos, P. Vision-based monitoring of weaving sections / P. Papanikolopoulos, E. Kwon // Proc. IEEE Conf. Intelligent Transportation Systems. 1999. - P. 770 - 775.

15. Коновалов, A.H. Введение в вычислительные методы линейной алгебры -Новосибирск: ВО "Наука", 1993. С. 59.

16. Мурзин, Ф.А. О распараллеливании алгоритма WZ- разложения / Ф.А. Мурзин, Т.С. Мурзина // Оптимизирующая трансляция и конструирование программ. Новосибирск: ИСИ СО РАН, 1997. - С.113 - 122.

17. Братцев, С. Г. Конфликт сложных систем. Модели и управление. / С. Г. Братцев, Ф. А. Мурзин, Б. К. Нартов, А. А. Пунтус М.: Изд. МАИ, 1995.

18. Братцев, С. Г. Исследования по обработке динамических изображений / С. Г. Братцев, Ф. А. Мурзин, Б. К. Нартов // Тез. междунар. конф. по обработке изображений и дистанционным исследованиям. -Новосибирск, 1990. — С. 41-43.

19. Bratsev, S. G. The optimum search of targets and the processing of dynamical images / S. G. Bratsev, F. A. Murzin, В. K. Nartov // Proc. of the Intern. Symp. on Visual Analysis and Interface. Novosibirsk, 1991. - P. 17.

20. Грицык, В. В. Распараллеливание алгоритмов обработки информации в системах реального времени / В. В. Грицык. Киев: Наумова думка, 1981.

21. Писаревский, А.Н. Системы технического зрения / А.Н. Писаревский. — М.: Машиностроение, 1988.

22. Прэтт, У. Цифровая обработка изображений / У. Прэтт. М: Мир, 1982. -Т. 1 - 2.26.0бработка изображений // Под ред. Хуанга. М.: Мир, 1979.

23. Голд, Б. Цифровая обработка сигналов / Б. Голд, Ч. Рэйдер. М.: Советское радио, 1973.

24. Datacube, Inc. http://www.datacube.com

25. Media Cybernetics, L. P. http://www.optimas.com

26. Ronald A. Massa Associates http://www.wav2c.com31 .Impuls GmbH http://www.impuls-imaging.com

27. Binary Technologies http://www.binarv-technologies.de

28. Codeguru http://www.codeguru.com

29. Громов, Ю.Ю. Введение в методы численного анализа: Курс лекций / Ю.Ю. Громов, С.И. Татаренко.- Тамбов, госуд. техн. ун-т. 2001.- 123с. http://www.otd.tstu.ni/is/lang/Numerikalmethods/T03/T03.htm#z3

30. Самарский, А.А. Введение в численные методы / А.А. Самарский. М.: Наука, 1982.-С. 272.

31. The 4th All-Russian with invited foreign participants Conference "Pattern Recognition and Image Analysis: New Information Technologies" ROAI-98. -Novosibirsk: IA&ESibRAS,; 1998.-Vol. 1,2.

32. Gamma, E. Design Patterns / E. Gamma, R. Helm, R. Johnson, J. Vlissides -Addison Wesley Longman Inc, 1995 P. 60, 132.

33. Booch, G. Object oriented analysis and design. 2nd ed. / G. Booch. - Addison Wesley Longman Inc, 1994 - P. 187.

34. Bernd, H. Motion-Based Object Detection and Tracking in Color Image Sequences / H. Bernd. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2000. - P. 14(8):806 - 825.

35. Рябенький, B.C. Введение в вычислительную математику. Учебное пособие для вузов. / B.C. Рябенький М.: Физматлит, 1994. - С. 336.

36. Лобив, И. В. Слежение и определение скорости движущихся на плоскости объектов в реальном времени / Д. Ю. Мехонтцев, И. В. Лобив, К. С. Селезнев // Современные проблемы конструирования программ. -Новосибирск, 2002. С. 243-246.

37. Лобив, И. В. Решение задачи нахождения оптимального положения тела в пространстве по данным, поступающим с одномерных камер для трехмерной оптической системы анализа движения объектов / Д. Ю.

38. Мехонцев, И. В. Лобив // Материалы междунар. конф. молодых ученых поматематическому моделированию и информатике. Новосибирск, 2002. -С. 19-20.

39. Семич, Д. Ф. Программное обеспечение для поддержки процесса ядерного каротажа нефтяных скважин / А. А. Винокуров, И. В. Ильин, И. В. Лобив,

40. Ф. А. Мурзин, О. Н. Половинко, Д. Ф. Семич. // Материалы междунар.конф. памяти академика А. П. Ершова, "Перспективы систем информатики". Новосибирск, 2003. - С. 40-43.

41. Мурзин, Ф. А. О распараллеливании PIC метода / И. В. Лобив, Ф. А. Мурзин // Проблемы систем информатики и программирования. -Новосибирск, 1999.- С. 146-155.

42. Вшивков, В. ■ А. Параллельный алгоритм решения задачи о взаимодействии потоков разряженной плазмы / В. А. Вшивков, И. В. Лобив, Ф. А. Мурзин // Проблемы систем информатики. Новосибирск, 2001.-С. 76-82.

43. Лобив, И. В. Исследование вопросов, связанных с распараллеливанием PIC-метода / Ф. А. Мурзин, И. В. Лобив // Тр. XVI Междунар. школы -семинара по численным методам механики вязкой жидкости. -Новосибирск, 1998.-С. 44-46.

44. Cheremushkin, Е. S. Genetic code and Visualization // Bioinformatics of Genom Regulation and Structure / E. S. Cheremushkin, A. E. Kel, I. V. Lobiv, F. A. Murzin, O. N. Polovinko. Novosibirsk, 2002, - Vol. 1, - P. 94-97.

45. Мурзин, Ф. А. О некоторых задачах, связанных с автоматизацией процесса ядерного каротажа нефтяных скважин / А. А. Винокуров, И. В. Ильин, И. В. Лобив, Ф. А. Мурзин, О. Н. Половинко, Д. Ф. Сем'ич //117

46. Материалы мел<дунар. конф. Новые информационные технологии в науке и образовании. Новосибирск, 2003. - С. 112-123.

47. Половинко, О.Н. Распознавание текстур по пространственным закономерностям / Ф. А. Мурзин, О. Н. Половинко, И. В. Лобив // Материалы междунар. конф. Новые информационные технологии в науке и образовании. Новосибирск, 2003. - С. 256-268.