Программные системы для идентификации и локализации объектов в изображениях тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Лобив, Игорь Васильевич

• Лобив, Игорь Васильевич
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Лобив, Игорь Васильевич

ВВЕДЕНИЕ.

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 и частично реализовывап программу на С++ (фильтрация и интерполяция данных).

Список литературы диссертационного исследования кандидат физико-математических наук Лобив, Игорь Васильевич, 2004 год

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.