Содержание к диссертации
Введение
1. Быстрый поиск (локализация) фрагмента фотографического изображения в другом изображении 22
1.1. Обзор существующих методов и систем 23
1.2. Описание метода, лежащего в основе программной системы локализации образца в изображении 27
1.2.1. Определения и обозначения 27
1.2.2. Низкочастотная фильтрация 28
1.2.3. Медианная фильтрация 29
1.2.4. Выделение контуров 30
1.2.5. Дополнительные условия преобразований 30
1.2.6. Выбор опорных точек 30
1.2.7. Построение структуры вспомогательных данных 31
1.2.8. Поиск опорных точек 34
1.2.9. Поворот изображения 39
1.2.10. Коррекция по яркости и контрастности 42
1.2.11. Выбор адаптивных порогов 43
1.3. Сравнение с аналогичными системами 45
1.4. Описание реализации программы 48
1.4.1. Общая схема реализации и интерфейс 48
1.4.2. Выделение контуров 49
1.4.3. Формирование вспомогательных данных 52
1.4.4. Поиск опорных точек 53
1.4.5. Основной цикл распознавания 56
1.4.6. Локализация опорных точек с помощью деревообразной поисковой структуры 57
1.5. Результаты тестовых испытаний 59
1.6. Параллельный вариант метода 64
1.7. Выводы 67
2. Распознавание и локализация движущегося объекта в видеопотоке 68
2.1. Постановка задачи 71
2.2. Описание метода 73
2.2.1. Блок схема алгоритма 73
2.2.2. Определение адаптивного фильтра 74
2.2.3. Этап локализации объектов 77
2.2.4. Обработка контуров 80
2.2.5. Привязка контура к структуре цепочек 80
2.3. Описание прораммной реализации 84
2.4. Параллельный вариант метода 85
2.4. Выводы 86
3. Локализация на фотографическом изображении маркера и распознавания содержащегося в нём текста 87
3.1. Постановка задачи 87
3.2. Начальные предположения 89
3.3. МРМ - Модуль Распознавания Маркера 91
3.3.1. Нахождение отрезков на изображении 91
3.3.2. Нахождение отрезков маркера 93
3.4. МИМ — Модуль Интерпретации Маркера 94
3.4.1. Нахождение символов в строке 95
3.4.2. Идентификация символов 95
3.5. Описание программного продукта 98
3.6. Параллельный вариант метода 98
4. Восстановление положения движущегося тела по информации, получаемой с множества одномерных видеокамер 99
4.1. Постановка задачи 99
4.2. Факторы, осложняющие решение задачи 100
4.3. Математическая постановка задачи 100
4.4. Аналогичные работы 100
4.5. Описание метода 102
4.5.1. Случай, когда на одном временном шаге данных (плоскостей) достаточно для однозначного восстановления положения тела 102
4.5.2. Случай, когда на одном временном шаге нам приходит недостаточное количество плоскостей (менее 6), для того чтобы однозначно восстановить положение тела 106
4.5.3. Фильтрация шумов 107
4.6. Описание программно-аппаратного комплекса 107
Заключение 109
Список литературы 112
- Локализация опорных точек с помощью деревообразной поисковой структуры
- Привязка контура к структуре цепочек
- Случай, когда на одном временном шаге данных (плоскостей) достаточно для однозначного восстановления положения тела
- Описание программно-аппаратного комплекса
Введение к работе
Диссертационная работа посвящена исследованиям, возникшим в связи с реализацией ряда программных средств для локализации и идентификации объектов в изображениях и видеопотоке.
Цель работы - создание программных средств, расширяющих интеллектуальные возможности компьютеров и компьютерных систем машинного зрения, и повышение эффективности процессов обработки данных в вычислительных машинах и комплексах. Под данными здесь понимаются фотографические изображения и видеоинформация. Основные задачи состояли в создании программных систем, позволяющих осуществлять следующие функции.
Быстрый поиск (локализация) фрагмента фотографического изображения в другом изображении.
Распознавание и локализация движущегося объекта в видеопотоке.
Локализация на фотографическом изображении маркера и распознавания содержащегося в нём текста.
Восстановление положения движущегося тела по информации, получаемой с множества одномерных видеокамер.
Практически все исследования и программные продукты, описанные в диссертации, делались для зарубежных заказчиков.
Актуальность.
Компьютерный анализ изображений является одним из самых мощных и широко распространенных методов экспериментальных наук. Решение сложных и разнообразных проблем, стоящих перед исследователями, зачастую требует достоверных опытных данных, для получения которых необходимы быстро работающие программно-аппаратные системы для автоматической локализации и идентификации объектов в изображениях.
Одна из важных задач, которая возникает в том или ином виде во многих областях науки - это быстрый поиск фрагментов в изображениях. Яркими примерами являются задачи подсчета количества бактерий на фотоснимке, поиска заданного участка местности на аэрофотоснимке, сравнение выпускаемой продукции с эталоном и т.д.
На данный момент в мире существует всего несколько программных продуктов, осуществляющих быстрый поиск образца на изображении для случая, когда образец внутри данного изображения может быть повернут. Еще меньше программ, позволяющих выполнить поиск образца, искаженного аффинным преобразованием.
Один из лидеров по времени поиска среди таких систем является продукт американской фирмы Datacube - MaxVision Toolkit [], который обладает рядом неоспоримых достоинств: поиск образца, искаженного аффинным преобразованием, нелинейной коррекции освещенности. Но основным недостатком метода нормализованной корреляции оттенков серого, на котором основан продукт, является большая вычислительная сложность. Это заставляет исследователей искать новые подходы к решению данной задачи.
Нельзя не отметить вклад фирмы ABBY Software House в создание систем автоматического распознавания текста. Продукт FineReader является ф одним из лучших в мире для этой задачи. Одним из недостатком этого продукта является чувствительность к большим (больше 15 градусов) углам поворота сканируемого изображения. Таким же недостатком обладают различные системы локализации и распознавания этикеток и штрих кодов. На сегодняшний день требуются быстро работающие решения в контексте данной задачи.
Научная новизна.
В результате проведенных исследований реализован ряд конкурентно-способных программных систем для локализации и идентификации объектов в изображениях.
Предложен высокоэффективный алгоритм для решения задачи о локализации фрагмента в изображении, базирующийся на использовании множества опорных точек.
Программная система созданная на основе этого метода успешно локализует фрагменты, искаженные преобразованием масштаба и поворота. По времени локализации она не уступает лидерам в данной области, а в некоторых случаях и превосходит их.
В задаче о локализации объектов в видео потоке применен метод «адаптивного фильтра» и метод фильтрации одномерных шумов, с помощью которых удалось построить систему устойчивую к небольшим резким изменениям угла зрения видеокамеры. Созданная система работает в режиме реального времени и по времени локализации не уступает своим зарубежным аналогам.
В рамках решения задачи о локализации маркера и распознавания содержащегося в нем текста, реализована система, которая успешно локализует маркеры специального вида, повернутые на произвольный угол, и имеющие произвольный размер. По времени локализации маркеров, искаженных преобразованием поворота, превосходит широко известную систему распознавания текста FineReader.
В задаче о восстановлении положения тела по информации, получаемой с множества одномерных видеокамер, предложен новый подход, основанный на использовании многомерного метода Ньютона.
В первой главе представлены алгоритмы и дано краткое описание программной системы для быстрого поиска фрагмента изображения в другом изображении. При этом фрагмент может быть повернут и/или его масштаб изменен.
Поиск фрагментов в изображениях — важная задача, которая в том или ином виде возникает во многих отраслях. В качестве примера можно привести подсчет количества бактерий на фотоснимке, поиск заданного участка местности на аэрофотоснимке и т. д.
Нередко задача осложняется тем, что искомый фрагмент может ц отличаться от образца расположением, цветовыми характеристиками, такими как яркость, контрастность, насыщенность цвета и др. Его геометрия может быть искажена, например, вытянута по какому-то направлению.
Наконец, при разработке систем машинного зрения в робототехнике, систем безопасности, военных систем наведения и целеуказания возникает еще одно требование, состоящее в том, что поиск должен осуществляться максимально быстро.
_ Речь идет об обработке цветных изображений. Более того, для цветного
изображения поиск происходит быстрее. Это является отличием от типичных алгоритмов, описанных в литературе, которые работают с цветными изображениями так же медленно, как и с черно-белыми.
Особенностью данного алгоритма является также и то, что яркость и контрастность всего изображения и фрагмента могут быть различными.
На данный момент в мире существует всего несколько программных продуктов, осуществляющих быстрый поиск образца на изображении для случая, когда образец внутри данного изображения может быть повернут.
Еще меньше программ, позволяющих выполнить поиск образца, искаженного аффинным преобразованием.
Один из таких продуктов — MaxVision Toolkit фирмы Datacube. Этот пакет представляет собой набор удобных в использовании, быстрых и высокоточных инструментов для машинного зрения, включающий процедуры калибровки съемочной аппаратуры, ввода, подготовки и анализа изображений и поиска объектов. При поиске осуществляется коррекция перспективного искажения.
Для работы пакета требуются специализированные аппаратные средства. Более подробную информацию о фирме и ее продуктах можно получить на веб-сайте фирмы [28].
Существуют и другие программные и программно-аппаратные
комплексы, осуществляющие поиск объектов теми или иными методами [29 4 32].
В реализованной нами программе образцы для поиска и изображение, в котором осуществляется поиск, могут быть загружены из файлов в одном из распространенных растровых форматов. Искомый фрагмент может быть повернут, растянут или иметь яркость, контраст и насыщенность цвета, отличные от аналогичных параметров образца.
Реализованная программа состоит из двух частей — вычислительного ядра и управляющей оболочки, осуществляющей пользовательский интерфейс. Вычислительное ядро можно использовать при разработке других программ с минимальными изменениями, связанными с особенностями конкретной аппаратной платформы,. Программа разработана для операционной системы Microsoft Windows.
Пользовательский интерфейс обеспечивает удобное управление функциями программы, вывод результатов в понятной форме, возможность скрыть ту информацию, которая временно не требуется пользователю. It Поддерживается большинство широко используемых форматов файлов изображений. При обработке изображений в диссертации используется система цветовых координат RGB. Цветное изображение размером ихш задается тремя матрицами sr = Suit j), SG=SG(i ) и SB =5б(/,у ),где Значения элементов матриц SR(i,j), SG(i,j) и SB(i,j) изменяются в пределах от 0 до 255. Предположим, что точки /? = (/, у) и р - (/", у") имеют цвета (r,g,b) и (r ,g ,b ) следовательно, Sr 0\ Л = г, Sc (і, j) = g, 5fl (/, У) = 6, SR(i ,f) = r , SG{i J ) = g\ SB{i\f) = b . Цветовое расстояние cd(piP ) = m \SR(p)-SR(p%\SG(p)-SG(p%\SB(p)-SB(p )\}. Введем константу Q,, такую, что если выполнено условие cd(p,p ) ,Cv, то считаем что точки р,р имеют одинаковый цвет. При выполнении обратного неравенства — разный. Евклидово расстояние р(р, р ) - л/(/ -1")2 + (j - j )2 , Пусть S = (SR,SG,SB) - некоторое фотографическое изображение (Source Bitmap), Sc =(SR,SG,SB) - образец для локализации (Control Bitmap). Задача состоит в том, чтобы найти такой локализованный фрагмент S = (S R,S G,S B)cS,что Eq = \S - F(Sc)\c),n\G F = I М2 о Л/, о R -композиция функций: R:SC — iSjc - поворот на некоторый угол относительно центра Sc, М, :Sf — Sj - изменения масштаба вдоль направления -L ширине 5,с, М2: 2 - 5"з - изменения масштаба вдоль направления -L высоте S%, I:S$ —»S% -коррекция интенсивности (яркости и/или контрастности), Th(Sc)- адаптивный порог для S , Zcd(p,p )/ Eq = \S- S] = pes,p es;P(p,P )=o где Q_ площадь SnS .
Для решения данной задачи в диссертации предложен метод, основанный на использовании опорных точек.
Он состоит из двух этапов - предварительной обработки и собственно поиска.
Предварительная обработка включает в себя несколько подэтапов: низкочастотная фильтрация, медианная фильтрация.
Далее следует выделение контуров.
Пустьр\р" -дветочки исследуемого изображения:
Обозначим Вт{р) - квадратную окрестность точки р со стороной квадрата 2т +1.
Пусть теперь cd[Bm (/?)] = max {cd(p\ р"):р\ р" є Вт(р)} максимальное цветовое расстояние в окрестности Вт (р) исследуемой точки.
Заключение о том, проходит контур через точку или нет, фиксируется соответствующими значениями функции / (0 или 1 соответственно). Др) = \ 0,ifcd[B„(p)]7 Cy, \,ifcd[Bm{p)]v. Следующий этап - выбор опорных точек - выполняем с помощью некоторой вспомогательной функции: g(p,p ) = a p(p,p ) + (\-a) cd(p,p ), 0 а 1. Наиболее сложным этапом алгоритма является построение древообразной поисковой структуры, ассоциированной с данным изображением.
На построение данной структуры затрачивается некоторое время, но после ее создания появляется возможность находить опорные точки за логарифмическое время, т.е. за С \og(n х т) шагов, где С - константа, характеризующая время выполнения одного шага поиска и не зависящая от размеров исходного изображения.
Деревообразная структура порождается в процессе разбиения данного изображения на прямоугольники.
Для нумерации прямоугольников используются пары (і, У), кодирующие уровень разбиения, и порядковый номер прямоугольника.
Обозначим через Rrs(i,j) соответствующий прямоугольник размера rxs. Далее с /?г (/,у) ассоциируется определенная на рассматриваемой палитре характеристическая функция Zkjj Метод построения грубых палитр состоит в том, что последние три бита значений r,g,b для любой точки полагаются равными нулю.
В итоге, вместо 16М цветов получаем 215 = 32К цветов.
Поиск опорных точек в исходном изображении осуществляется с помощью построенной деревообразной структуры рекурсивно в лексикографическом порядке с возвратами на верхние уровни разбиения. Дополнительное использование метрических характеристик, а именно расстояний между опорными точками на образцах, позволяет пропускать большое число узлов при обходе дерева.
После локализации опорных точек мы можем однозначно восстановить фрагмент, соответствующий данному положению опорных точек. Далее проводится контрольное сравнение и локализованного фрагмента с образцом, а также коррекция яркости и контрастности.
Если при сравнении в указанной мере близости образца и локализованного фрагмента мы с помощью адаптивного порога пришли к выводам, что несмотря на близость опорных точек, фрагменты различны, мы вынуждены продолжить поиск другого положения опорных точек, удовлетворяющих цветовым и метрическим соотношениям. Иначе локализация образца будет успешно завершена.
Отметим, что разработанный алгоритм допускает различные модификации, в том числе распространение на аффинный случай. Нами аффинный случай не реализовывался ввиду отсутствия заказчика на подобный программный продукт. Реализация же на инициативной основе затруднена ввиду высокой трудоемкости проекта.
Во второй главе описан программный комплекс для локализации движущихся объектов в видеопотоке в рамках задачи контроля дорожного трафика. Такие системы смогли появиться только в результате значительного увеличения мощности вычислительной техники, так как приходится обрабатывать непрерывный видеопоток.
Такого рода комплексы уже используются на дорогах в некоторых западных странах (например, Германия, производитель: концерн «Мерседес»).
В последнее время в связи с ростом мощности компьютеров появилось возможность создания относительно дешевых программно-аппаратных систем, реализующих обработку большого количества информации, поступающей в реальном времени. Примером может служить система отслеживания движения объектов, на вход которой поступают изображения, полученные с видеокамеры, а на выходе имеются данные об объектах, попавших в поле зрения, а также об их динамических характеристиках, например, скорости и ускорения.
Такая система была успешно реализована. В качестве аппаратной части выступает обычный компьютер Pentium-З, а в качестве программной части используется логический модуль собственной разработки, устройству которого и посвящена вторая глава.
К особенностям системы можно отнести следующее: камера должна обозревать от кадра к кадру одну и ту же область пространства; допускаются цветовые шумы и небольшое дрожание камеры; отслеживаемые объекты могут плавно менять форму и размер; не допускается пересечение движущихся объектов одного цвета на продолжительное время. Метод можно условно разбить на три части: построение адаптивного фильтра; локализация объектов; идентификация локализованных объектов (идентификация одного и того же объекта в различных фреймах (кадрах)). Построение адаптивного фильтра. Фильтр моделируется как медленно изменяемая последовательность изображений, которая позволяет адаптироваться к изменениям освещения и погодным условиям. Локализация объектов. Рассмотрим П)_, сйЧ - объединение всех областей, где точно находятся объекты на предыдущем фрейме /}_,. Если П)_, =0, то просто производим сравнение с фреймом адаптивного фильтра R и выявляем области, отличные по цвету, - эти области и будут кандидаты в объекты. В противном случае: еслир єП_,,то /?єП,,о ci cR, если р . П_, ,то р є CIj, = Cj c,_i.
В третьей главе описана программа быстрого поиска маркеров и распознавания текста, содержащегося в них. Такие программы применяются, например, в обслуживании обычной почты. Трудность задачи в том, что допускается поворот маркера на любой произвольный угол. При использовании знаменитых систем (например, ABBY FineReader) значительно замедляются локализация и распознавание символов при наличии поворота фрагмента. А также возрастает ошибка распознавания.
Далее рассматриваются алгоритмы быстрого поиска маркеров на изображении и распознавания содержащегося в них текста.
На изображении имеется прямоугольная рамка (маркер), разделенная на верхнюю и нижнюю половину. В каждой половине есть набор цифр. Нужно быстро найти маркер на изображении и распознать цифры на нем. Рамка может быть повернута относительно изображения на произвольный угол и может иметь произвольный размер. В параграфе описан подход, который хорошо зарекомендовал себя для решения этой задачи.
Дополнительные требования.
Фон должен быть примерно одного цвета.
Прямоугольник и текст также должны быть одного цвета, отличающегося от фонового.
Заметим, что геометрия маркера представлена как набор связанных векторов. Следовательно, геометрия может быть легко изменена. Алгоритмы универсальны, т.е. работают с любыми символами.
Обработка изображения делится на две стадии: Модуль Распознавания Маркера (МРМ) и Модуль Интерпретации Маркера (МИМ), которые в свою очередь состоят из модулей, детально описанных далее.
В четвертой главе рассмотрена и реализована задача нахождения оптимального положения тела в пространстве по данным, поступающим с одномерных камер для 3d оптической системы анализа движения объектов.
В пространстве имеется твердое тело с известной геометрией, на котором в определенных местах закреплены светоизлучающие диоды, в дальнейшем называемые маркерами, которым присвоены уникальные номера. Также имеется набор одномерных детекторов, расположенных вокруг твердого тела, которые достаточно часто (200 - 300 раз в сек.) фиксируют положение маркеров. Каждый маркер обладает уникальными характеристиками (цвет, частота мерцания, и т.п. ), по которым детектор может отличить его от других маркеров и восстановить его номер. В силу одномерности детектора, о каждом маркере, попадающим в его поле видимости можно получить лишь уравнение плоскости, в которой этот маркер содержится. Все плоскости, получаемые от фиксированного детектора, пересекаются по одной прямой ("фокусная прямая").
Задача состоит в том, чтобы по имеющимся данным в реальном времени восстанавливать положение твердого тела с максимальной точностью.
Осложняющие факторы.
В нескольких последовательных фреймах может быть недостаточно информации для однозначного восстановления положения тела (недоопределенность).
В силу несовершенства детектора возможна ситуация, когда он выдает ошибочный номер маркера.
Математическая постановка.
Положение тела в пространстве можно представить в виде Ах + b, где Z = (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 в секунду - эта цифра уже вполне реальна как для обработки, так и для передачи. Более того, за счет применения одномерных камер можно увеличить скорость обработки, а следовательно и точность.
Выпишем в явном виде представление матрицы А:
Пусть на данном временном шаге известны N плоскостей, заданных в виде (n,,X) = dlt / = 1...//, где и, = (a,, 6,, с,) - вектор нормали к плоскости, ( у ) - скалярное произведение, а также N точек Хх =( /, /,2,), характеризующих координаты маркера в системе координат твердого тела (предполагается, что эта информация считывается из файла с описанием твердого тела). Метод наименьших квадратов приводит к следующей задаче: n ,,/ ,+6)-4]2- min. В итоге остается система трех нелинейных уравнений с тремя неизвестными p,q,r: f\(P,4 r) = 0 fi(P,4,r) = Q /з(Р Ч г) = или в векторном виде F(P) = 0,rAeF = (fiif2,f3),P = (p,q,r). Для ее решения воспользуемся методом последовательных приближений Ньютона. Пусть на п-ом шаге известно приближение P„=(p„,4„,f„), тогда следующее приближение Рп+1 находится по формуле : Рп+Х =Рп -J xF(Pn), где J - матрица Якоби преобразования F. Как известно, метод Ньютона очень быстро сходится в случае хорошего начального приближения.
В алгоритме для начального приближения используются данные, полученные в результате экстраполяции по предыдущим временным шагам (с предыдущих фреймов), - это обеспечивает хорошее начальное приближение и позволит обойтись в методе Ньютона двумя-тремя итерациями для достижения нужной нам точности.
О личном вкладе автора.
Реализация описанных выше алгоритмов является достаточно трудоемкой задачей, и выполнялась коллективно. Наибольший вклад в первой задаче автор диссертации внес в разработку и реализацию следующих алгоритмов: быстрый поворот фрагмента изображения, метод адаптивных порогов, оптимизация древовидной поисковой структуры, контрольное сравнение, метод обратной связи между алгоритмом поиска и контрольного сравнения. Во второй задаче диссертанту полностью принадлежит реализация всех методов. Совместно с Мехонцевым Д.Ю. осуществлялась отработка алгоритмических деталей. При разработке третьей задачи диссертант был ответственным за реализацию алгоритма локализации маркера, программу распознавания текста реализовывали другие соавторы. В четвертой задаче автор диссертации участвовал в разработке алгоритмов, проводил проектирование и вывод наиболее сложных формул в системе символьных преобразований Maple vR4 и частично реализовывал программу на C++ (фильтрация и интерполяция данных).
Основные результаты диссертации состоят в следующем.
Проведены комплексные теоретические исследования и созданы алгоритмы и программные средства для локализации объектов в системах распознавания изображений для следующих задач.
1. Быстрый поиск (локализация) фрагмента фотографического изображения в другом изображении. Программное средство для У локализации объектов по своим характеристикам не уступает лидеру в данной области, продукту MaxVision Toolkit фирмы Datacube и в некоторых случаях и превосходят его.
2. Распознавание и локализация движущегося объекта в видеопотоке. Основным результатом является метод «сверх» адаптивного фильтра и метод фильтрации одномерного шума, которые позволили решить две важные задачи: небольшие быстрые изменения угла зрения («дрожание») видеокамеры и устойчивость всей системы при внесении различных помех, например, MPEG-сжатие видеопотока с потерей качества.
3. Локализация на фотографическом изображении шаблона и распознавание содержащегося в нём текста. Время локализации маркера быстрее, чем у продукта лидера в области распознавания текста Fine Reader ABBY Software House. Речь идет о задаче, осложненной тем, что допускается поворот на произвольный угол и изменение масштаба маркера.
4. Восстановление положения движущегося тела по информации, получаемой с множества одномерных видеокамер. Предложена и обоснована новая идея использования одномерных камер для решения этой задачи. В этой постановке предложен и реализован эффективный алгоритм, основанный на многомерном методе ш Ньютона.
Работы выполнялись, в основном, для зарубежных заказчиков. Результаты также докладывались на международных конференциях.
Диссертационная работа состоит из введения, трех глав и списка литературы. Объем диссертации - 118 стр. Список литературы содержит 60 наименований. Работа включает 45 рисунков и графиков, полученных в результате расчетов на ЭВМ.
Автором опубликовано 20 печатных работ, из них по теме диссертации - 16 работ.
Благодарности.
Автор диссертации хотел бы выразить глубокую благодарность своему научному руководителю Федору Александровичу Мурзину за многолетнюю помощь, сотрудничество в научных исследованиях и моральной поддержке в трудные минуты научной карьеры.
Автору хотелось бы выразить особую признательность остальным всем своим соавторам и бывшим однокурсникам, особенно Мехонцеву Д. и Кравченко А. (они продолжают заниматься наукой в ИМ СО РАН и создали лучший в мире конструктор трехмерных фракталов - IFS), Селезневу К. (технический руководитель проекта связанного с получением и анализом рентгенограмм нефтяных пластов - ЮКОС-Новосибирск). Без их самоотверженной работы и помощи невозможно было бы успешное создание этих программных систем.
Так же хочу выразить благодарность за ценные замечания Касьянову В.Н., Марчуку А.Г., Городней Л.В., Евстигнееву В.А., Вшивкову В.А., а также всех участников семинаров, на которых я был выслушан.
Локализация опорных точек с помощью деревообразной поисковой структуры
В третьей главе описана программа быстрого поиска маркеров и распознавания текста, содержащегося в них. Такие программы применяются, например, в обслуживании обычной почты. Трудность задачи в том, что допускается поворот маркера на любой произвольный угол. При использовании знаменитых систем (например, ABBY FineReader) значительно замедляются локализация и распознавание символов при наличии поворота фрагмента. А также возрастает ошибка распознавания.
Далее рассматриваются алгоритмы быстрого поиска маркеров на изображении и распознавания содержащегося в них текста.
На изображении имеется прямоугольная рамка (маркер), разделенная на верхнюю и нижнюю половину. В каждой половине есть набор цифр. Нужно быстро найти маркер на изображении и распознать цифры на нем. Рамка может быть повернута относительно изображения на произвольный угол и может иметь произвольный размер. В параграфе описан подход, который хорошо зарекомендовал себя для решения этой задачи.
Дополнительные требования. Фон должен быть примерно одного цвета. Прямоугольник и текст также должны быть одного цвета, отличающегося от фонового. Заметим, что геометрия маркера представлена как набор связанных векторов. Следовательно, геометрия может быть легко изменена. Алгоритмы универсальны, т.е. работают с любыми символами. Обработка изображения делится на две стадии: Модуль Распознавания Маркера (МРМ) и Модуль Интерпретации Маркера (МИМ), которые в свою очередь состоят из модулей, детально описанных далее. В четвертой главе рассмотрена и реализована задача нахождения оптимального положения тела в пространстве по данным, поступающим с одномерных камер для 3d оптической системы анализа движения объектов. В пространстве имеется твердое тело с известной геометрией, на котором в определенных местах закреплены светоизлучающие диоды, в дальнейшем называемые маркерами, которым присвоены уникальные номера. Также имеется набор одномерных детекторов, расположенных вокруг твердого тела, которые достаточно часто (200 - 300 раз в сек.) фиксируют положение маркеров. Каждый маркер обладает уникальными характеристиками (цвет, частота мерцания, и т.п. ), по которым детектор может отличить его от других маркеров и восстановить его номер. В силу одномерности детектора, о каждом маркере, попадающим в его поле видимости можно получить лишь уравнение плоскости, в которой этот маркер содержится. Все плоскости, получаемые от фиксированного детектора, пересекаются по одной прямой ("фокусная прямая"). Задача состоит в том, чтобы по имеющимся данным в реальном времени восстанавливать положение твердого тела с максимальной точностью. Осложняющие факторы. В нескольких последовательных фреймах может быть недостаточно информации для однозначного восстановления положения тела (недоопределенность). В силу несовершенства детектора возможна ситуация, когда он выдает ошибочный номер маркера. Математическая постановка. Положение тела в пространстве можно представить в виде Ах + b, где Z = (w,v,w) - вектор сдвига, А - ортогональная матрица поворота тела относительно начального положения. Задача будет решена, если будут найдены величины А,Ь, при которых отклонение положений маркеров от соответствующих плоскостей будут минимальны в некоторой норме. Попробуем выявить одну из главных проблем, которая возникает у исследователей в данной области. Подсчитаем объем информации, который должен обрабатываться в реальном времени. Рассмотрим обычную профессиональную 2d камеру, 1024x1024 True Color - размер изображения, получаемой с камеры. Требование на рабочую частоту камеры 300 fps. Так как частота промышленных мониторов и Цх телеприемников 24-30 fps и для того чтобы изображение на экране было непрерывным, нужна частота в 10 раз большая, т.е. 300 fps. Всего в результате лишь с одной камеры получается видеопоток 900МЬ в секунду. Но так как камер 4 (например, в системе Vicon 8i), получается более 3Gb в секунду. Эта цифра очень огромна даже для сегодняшнего уровня вычислительной техники как для передачи такого объема информации в реальном времени, так и для обработки. Поэтому все направления ее исследований нацелены на уменьшение этого показателя, например, применение методов сжатия, увеличение количества вычислительных узлов и их мощности, привлечение суперкомпьютеров.
Привязка контура к структуре цепочек
В последнее время в связи с ростом мощности компьютеров появилась возможность создания относительно недорогих программно-аппаратных систем, реализующих обработку большого количества информации, поступающей в реальном времени. Примером может служить система отслеживания движения объектов, на вход которой поступают изображения, полученные с видеокамеры, а на выходе имеются данные об объектах, попавших в поле зрения, а также об их динамических характеристиках, например, скорости и ускорения. Отслеживание движения транспортных средств в видеопотоке является активной областью исследований в сфере компьютерного зрения [9-13].
В [15] описана система реального времени для измерения параметров трафика. Она использует метод особенностей с разбором пересечений. В случае пересечения 2d проекций двух транспортных средств, вместо того чтобы отслеживать все пересечения, отслеживаются под-особенности транспортных средств. Этот подход заставляет производить вычисления большого объема, и поэтому он очень медленный. В [14] описан метод распознавания движущихся объектов, который использует адаптивный фильтр для отделения транспортных средств от фона. Фильтр моделируется как медленно изменяемая последовательность изображений, которая позволяет адаптироваться к изменениям освещения и погодным условиям. В похожей работе [16] отслеживается и вычисляется количество пешеходов с использованием неподвижной камеры. Изображения из входящей видеопоследовательности сегментируются с помощью сравнения с фтльтром. Результирующие связанные регионы группируются в пешеходов, которые затем отслеживаются. При разделении и объединении регионов возникает задача оптимизации графа. В [17] описана система для отслеживания смены полосы транспортным средством. В ней использован подход сходный с [16] с дополнением, что вычисляются траектории движения транспортных средств для определения пересечения с полосой движения. Работа очень близка к работе [17]. Но все перечисленные работы -работы западных ученых.
Материальная база зарубежных исследователей, как правило, лучше материальной базы, которой располагают наши исследователи, но все же это не помешало нам ввести ряд инноваций, которые помогли решить несколько важных проблем, возникающих перед всеми исследователями в данной области. А именно, фильтр в работе «сверхадаптивный», т.е. процесс локализации объектов нечувствителен к небольшим колебаниям камеры.
Такие колебания в системах контроля дорожного трафика невозможно избежать, так как камера крепится неподвижно к некоторой конструкции, которая совершает мелкие колебания во время проезда автомобильных средств в поле видимости. Так как камера по экономическим соображениям достаточно мала, то при таких колебаниях угол зрения может плавать существенно, и это является большой проблемой в системах такого рода.
Вторая инновация была применена в подзадаче локализации объектов при отделении их от фона. Проблема заключается в том, что в силу несовершенства детектора (например, применение различных сжатий с потерей качества для увеличения скорости передачи), а также физических помех (пыль, снег, дождь, туман, дымка) объекты локализуются неточно. Часто проекции двух объектов, после применения адаптивного фильтра, соединены некоторыми кривыми, которые полностью состоят из шумов. Для решения этой важной проблемы был придуман и успешно применен метод удаления вытянутых одно- и дву-пиксельных шумов. Это позволило существенно улучшить устойчивость алгоритма к различным помехам и успешно локализовывать объекты даже после обработки видеопотока MPEG-сжатием с потерей качества. (Как известно, после такой обработки объем передаваемой информации от камеры к центру обработки значительно уменьшается, но к сожалению на изображениях возникают характерные помехи в виде прямоугольников).
Таким образом, система была успешно реализована, в ней в качестве аппаратной части выступает обычный компьютер Pentium-З, а в качестве программной части используется логический модуль собственной разработки, устройству которого и посвящена данная глава.
К особенностям системы можно отнести следующие: камера должна обозревать от кадра к кадру одну и ту же область пространства; допускаются цветовые шумы и небольшое дрожание камеры; отслеживаемые объекты могут плавно менять форму и размер (например, приближающийся автомобиль); не допускается пересечение движущихся объектов одного цвета на продолжительное время. Рассмотрим декартову систему координат (x,y,z). Возьмем некоторую точку (0,0, Л0). Под углом а через точку S проведена плоскость (плоскость экрана) параллельно оси у. На этой плоскости зададим экран - прямоугольник (рисунки 22, 23, 24) длиной L (параллельной оси у), высотой Н и пересечением диагоналей в точке S. Глаз наблюдателя Е (рисунок 22), находится на расстоянии d от точки S плоскости экрана. По плоскости (х,у) вдоль вектора V движутся некоторые трехмерные объекты. Задача - определить их мгновенную и среднюю скорость при прохождении в поле видимости. Расчеты должны происходить в реальном времени.
Случай, когда на одном временном шаге данных (плоскостей) достаточно для однозначного восстановления положения тела
Создан ряд программных средств, расширяющих интеллектуальные возможности компьютеров и компьютерных систем, которые позволяют повысить эффективность процессов обработки данных в вычислительных машинах и вычислительных комплексах. Под данными здесь понимаются фотографические данные. Основные задачи состояли в создании программных систем, позволяющих осуществлять следующие функции. Быстрый поиск (локализация) фрагмента фотографического изображения в другом изображении. Распознавание и локализация движущегося объекта в видеопотоке. Локализация на фотографическом изображении шаблона и распознавание содержащегося в нём текста. Восстановление положения движущегося тела по информации, получаемой с множества одномерных видеокамер. Все работы выполнялись для зарубежных заказчиков и применяются в коммерческих приложениях. Работы докладывались на международных конференциях. Опубликованы соответствующие статьи по материалам конференций. Например, результаты работы докладывались на международной конференции «Современные проблемы прикладной математики и механики: теория, эксперимент и практика», посвященной 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 и частично реализовывал программу на C++ (фильтрация и интерполяция данных).
Описание программно-аппаратного комплекса
Оболочка реализована на MS VC++ (MFC) [33]. Алгоритмы [18] реализованы на стандартном C++ и представлены в виде dll библиотеки. Проведены серии тестов для различных изображений (100dpi, 200dpi, 300dpi,...) и шрифтов (Arial, Times New Roman, Courier,...). Среднее время работы 20-40ms на изображениях 800x600 (100dpi quality, Pentium -3/700MHz).
Локализация самого маркера на изображении - быстрая процедура, если область поиска не очень большая (например 1024x768). Если область огромная, то предлагается разрезать исходное изображение на области с перехлестом [19] (перехлест толщины размера маркера) и придать каждую такую область отдельному процессорному элементу. Эта методика должна существенно ускорить локализацию маркера.
Выделение символов - достаточно трудоемкая операция, так как она зависит от мощности алфавита и типа шрифта. После локализации всех строк с символами предлагается ее распараллеливать разделением строк по процессорным элементам.
В пространстве имеется твердое тело с известной геометрией, на котором в определенных местах закреплены светоизлучающие диоды, в дальнейшем называемые маркерами, которым присвоены уникальные номера. Также имеется набор одномерных детекторов (рисунок 41), расположенных вокруг твердого тела, которые достаточно часто (200 -300 раз в секунду) фиксируют положение маркеров. Каждый маркер обладает уникальными характеристиками (цвет, частота мерцания, и т.п.), по которым детектор может отличить его от других маркеров и восстановить его номер. В силу одномерности детектора, о каждом маркере, попадающим в его поле видимости, можно получить лишь уравнение плоскости, в которой этот маркер содержится. Все плоскости, получаемые от фиксированного детектора, пересекаются по одной прямой ("фокусная прямая").
Задача состоит в том, чтобы по имеющимся данным в реальном времени восстанавливать положение твердого тела с максимальной точностью. На рисунке 41, показан блок из четырех одномерных камер. Таких блоков, расположенных в разных частях пространства, может быть несколько. В нескольких последовательных фреймах может быть недостаточно информации для однозначного восстановления положения тела (недоопредел енность). В силу несовершенства детектора возможна ситуация, когда он выдает ошибочный номер маркера. Положение тела в пространстве можно представить в виде Ах + b, где Ъ = (u,v,w) - вектор сдвига, А - ортогональная матрица поворота тела относительно начального положения. Задача будет решена, если будут найдены величины А,Ь, при которых отклонения положений маркеров от соответствующих плоскостей будут минимальны в некоторой норме. Абсолютным лидером в данной области является фирма Vicon, ее продукты использовались для съемок таких знаменитых фильмов, как: "Titanic", "Gladiator", "The Mummy", "The Mummy Returns", "Star Wars Episode 1 - the Phantom Menace", "The Patriot", "Enemy at the Gates", "Pearl Harbor" и др. Также ее продукты используются для постановки физических экспериментов, производства игр, обучения. Попробуем выявить одну из главных проблем, которая возникает у исследователей в данной области. Подсчитаем объем информации, который должен обрабатываться в реальном времени. Рассмотрим обычную профессиональную 2d камеру, 1024x1024 True Color размер изображения, получаемой с камеры. Требование на рабочую частоту камеры - 300 fps. Так как частота промышленных мониторов и телеприемников 24-30 fps, то соответственно, для того, чтобы изображение на экране было непрерывным нужна частота в 10 раз большая, т.е. 300 fps. Итого, лишь с одной камеры получается видеопоток 900МЬ в секунду. Но камер - 4 (например, в системе Vicon 8i), итого более 3Gb в секунду. Эта цифра очень огромна даже для сегодняшнего уровня вычислительной техники как для передачи такого объема информации в реальном времени, так и для обработки. Поэтому все направления исследований нацелены на уменьшение этой цифры, например, применение методов сжатия, увеличение количества вычислительных узлов и их мощности, привлечение суперкомпьютеров. Мы предлагаем принципиально новое решение этого вопроса. Посчитаем то же самое, но для одномерных камер: 1024x1 размер изображения, 300 fps - условие на частоту то же самое. С одной камеры 900КЬ в секунду. Так как камер теперь нужно больше, то пусть будет 40 камер, итого около 40 Mb в секунду, эта цифра уже вполне реальна как для обработки, так и для передачи. Более того, за счет применения одномерных камер можно увеличить скорость обработки, а следовательно, и точность. Основная идея алгоритма заключается в том, чтобы в начале отфильтровать входные данные, а затем по ним восстановить положение тела. При этом недостающая информация о положении тела дополняется данными с предыдущих фреймов на основе интерполяции.
