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

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

ргг од

АНДРЮШКИН/Александр Анатольевич Т _ ... оппп

' АоГ ¿000

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

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

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

автор /Уд/,

Москва - 2000

Работа выполнена в Московском Государственном Инженерно - Физическом Институте (Техническом Университете)

Научный руководитель: . Кандидат технических наук, с.н.с.,

доцент Е.В. Чепин

Официальные оппоненты:

Доктор технических наук, профессор Афанасьев В.Н.

Кандидат технических наук, доцент Кудрявцев К.Я.'

Ведущая организация: Концерн "Системпром"

2000 г. в часов ш

Защита диссертации состоится " РЬ" игня заседании специализированного совета Д.053.03.04 в Московском инженерно физическом институте. .

Адрес: 115409 Москва, Каширское шоссе,31,т. 323-91-67,324-84-98

С диссертацией можно ознакомиться в библиотеке МИФИ.

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

Автореферат разослан " -( " ¿¿К, 2000 г.

Ученый' секретарь специализированного совета

/ Вольфепгаг'ен В.Э. /

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Диссертационная работа посвящена актуальной проблеме обработки изображений, а именно теоретическим и практическим вопросам - анализа движения на последовательности кадров. Актуальность темы,

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

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

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

Цель работы

- анализ известных подходов к вычислению движения;

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

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

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

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

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

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

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

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

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

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

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

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

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

Внедрение полученных результатов.

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

Разработанные алгоритмы выделения движения были представлены в «оптимизированной библиотеке программ для обработки изображений», созданной для ООО "Электронные компоненты", а также в ППП "JEK-Морфологпя v.4.0", разработанного ООО «МИФИ - Система» для Лаборатории (Центра) акустической микроскопии Института биохимической физики РАН. Нолынннство методов, алгоритмов и их программных реализаций были также включены в программный комплекс «Pictures Dcmolislier», предназначенный для исследования различных методик анализа движения. Основу этого программного комплекса составляют функции выделения движения для подвижного фона. Программный комплекс передан в эксплуатацию фирме Trilogies LLC (США).

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

ученых, "Молодежь н наука - третье тысячелетие" (1997) , семинаре Computer Science and Information Technologies (1999), Научной сесоил МИФИ (2000). Публикации. Основные положения диссертационной работы изложены в 7 печатных работах, напнеанных лично п в соавторстве, из них 3 на английском языке.

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

16 таблиц, а также список литературы - 122 наименования и приложение.

•

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

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

Вычисление поля движения изображения, в общем случае предполагается как главная цель задач обработки движения в система* машинного зрения. Как приближение к этому, методики, применяемые г машинном зрении, обычно вычисляют оценку поля движения, известную ка» «оптический поток», при этом измеряется, как перемещаются локальны« участки'изображения (матрицы яркостей) от одного кадра к другому. Чаете это делается исходя из предположения, что локальные участки матриць интенсивности не изменяются в силу.других причин; При известной скоросп ввода кадров, понятие оптического потока логично заменяется понятнее, «поле скоростей». Как правило, оба эти понятия используются как синонимы т.к. скорость кадрирования известна в абсолютном большинстве случаев. Пол*

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

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

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

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

Разностная методика. Она также известна как «градиентная» методика. В этом случае для вычисления векторов оптического потока используются производные изображения (интенсивности) по времени п пространству. Запишем шпенсивность точек изображения как непрерывную функцию координаты и времени /(-V, V,О- Методика основывается, на предположении, что интенсивность неизменна по времени, откуда следует:

с1Дх,у,П

ск

= 0

д[ д/ дг п

— +— V +— = 0

их * ду

7, ■? + /,=<>

где

г.' Уу .. /х , /у и Л - пространственные и временная

с1х с1у

Ж' У Ж

частные-производные функции изображения /, 5- вектор оптического потока (в позиции и времени, где вычисляется производные).

Налагая дополнительное условие локальной гладкости поля скоростей, решение может бы1ъ найдено как: •

где •

Г1л2 . ь =

1 Елл Е/.2 J >

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

/ту > ./л/ »/у1 > . . '

': Х(/;2 +/*) 1(л/,+/„/„+л, л

Л./,,+/,/,) ]

Е (/",/,+лх +л,Л/ +/,,/„)л

л/ =

ь =

Хк/'

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

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

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

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

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

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

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

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

- Методика сопоставления.

- Градиентная методика.

- Методики, базирующиеся ¡1а фильтрации в пространстве X, У, I (т.е. на пространственно- временной фильтрации).

- Методики, основанные на описании изображения в пространстве частот.

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

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

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

- улучшение известных методик оценки движения;

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

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

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

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

Сравнение кадров базируется на линейной фильтрации, подобной методикам подавления шумов.

1. Элсм'епт / результирующего массива ¿', полагается щмеппынпмез! (устанавливается в значение 2) путем сравнения разносш яркостей соответствующих пикселей для двух кадров/' с порогом д.

£1 =

2. Производится линейна* фильтрация (на подмножестве п близких точек с коэффициентами и-,), н для окончательного иида результирующею массива g¡' отбираются точки, значение которых равно или превосходит 1.

> д

'о, fi-.fi < д *

м

1

п-

Массив g¡' определяет маску, пли «область различия».

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

В работе предложена новая методика оценки движения через сегментацию. Алгоритм этой методики последовательно проходит несколько стадий "

• Сегментация каждого кадра.

• Описание сегментов.

• Вычисление движения сегментов.

• Сборка объекта и выделение объекта в движении.

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

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

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

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

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

2) Взаиморасположение Центра масс, Геометрического центра и Центра максимального удаления от краев (определяет середину наиболее «толстого» участка фрагмента).

3) Спектр масс по направлениям, а также

4) Спектр максимального удаления по направлениям косвенно описывают форму фрагмента, в то же время являясь достаточно простыми характеристиками для вычисления схожести фрагментов

5) Простое грамматическое описание - выражает еще один * способ упрощенного описания формы объекта. В данном случае объект описывается цепочкой символов, соответствующих достаточно крутому повороту направо (+) или налево (-). ■

(>) Цвет (пли яркость для черно- белых изображений)

На основании перечисленных характеристик можно записать критерий схожести двух фрагментов. Близость сегментов Допрсделяется с учетом весовых коэффициентов к„ где Д, - разность пары 1-х признаков как:

При этом разность каждой пары /-х признаков определяется специфичным образом. Так, например, для цветовых характеристик эта разность может быть выражена: ' v

Д < К-("г -"У+• fo -s?+к • (к -W .

" 1 *А для. цветовой системы HSV, где kh. ks, kv - коэффициенты значимости компонентов представления цвета.

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

Каждая такая пара дает нам вектор движения сегмента. Этот вектор движения может приниматься во внимание при сравнении следующих двух кадров, т.е. может использоваться свойство инерции.

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

Таким образом, на выходе системы мы имеем описание объектов и характеристики их движения.

Для новых методик, описанных выше, а также для методики сопоставления и методик, основанных па фильтрации, были предложены алгоритмы и схемы построения программ. Каждая из методик была реализована программно на языке С++.

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

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

глобальному изменению яркости. Исходя из этого,' для реализации была выбрана новая методика <<без нулевого кадра», как наиболее устойчивая.

Была программно реализована методика сопоставления. В соответствии с методикой последовательно производится сравнение кадров Р, и' /•',, /, смещенных на различное расстояние {Ах,&у) друг относительно друга. При тгом осуществляется поиск значении (Лл-,Дг), минимизирующий функцию ошибки, определенную как „

Е{Ах, Лг) = Е 1'', (-V, у) - ^ и (Л- + .Ах, у + Ду)]2

I

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

Были реализованы ряд методик, основанных на фильтрации в пространстве - времени. ■

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

= I \1 (*/ > > о • V + 7, (х,, ,/)]2;

где пространственные, а /,- временная производные. И "решение может быть найдено как,: .

Г ЕЛ2 X«] А - 'I и;

X/.2) и — У JL^fyf' >

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

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

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

Так, разработанные алгоритмы выделения движения были представлены в «оптимизированной библиотеке программ для обработки изображений», созданной для ООО "Электронные компоненты", а также в ППП "JEK-Морфология v.4.0", разработанном для Лаборатории (Центра) акустической микроскопии Института биохимической физики РАН.

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

Акты внедрения, касающиеся этих программных продуктов, представлены в приложении Б.

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

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

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

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

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

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

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

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

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

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

2. На основе приведенного анализа была предложена классификация методов выделения движения.

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

4. Была предложена улучшенная методика вычисления движения при неподвижном фоне.

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

ф. Разработаны алгоритмы и принципы построения программ, реализующие следующие методики:

-оптимизированные методики сопоставления, в т.ч. методика для случая неподвижного фона; •

- методика вычисления движения через сегментацию;

- методики, основанные на фильтрации.

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

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

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

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

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

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

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

Публикации по теме диссертации. .

[1] Лндрюшкин A.A. Бинарное растрирование и печать полутоновых изображений:- Материалы Всероссийского молодежного научного Форума, Санкт-Петербург, 1995

[2] Андрюшкин A.A. Чепин Е.В. Растрирование полутоновых изображений:- Материалы Международного Научного Конгресса студентов, аспирантов и молодых ученых, "Молодежь и наука - третье тысячелетие" М., 1997.

[3] Андрюшюш А.А. • Чешш Е.В. Выделение объектов в последовательном ряде изображений и их распознавание на основе самообучения:- 7 Международный Научно- Технический Семинар "Современные технологии в задачах управления, автоматики и обработки информации" г. Алушта 1998 „ "

[4] Андрюшкин А.А. Чешш Е.В. Программно- аппаратное вычисление оптического потока. Научная сессия МИФИ-2000. Сб. научн. трудов в 13 томах. Т.2, М.: МИФИ, с. 140-141

[5] Alexander Andryushkin, Eugueni Tchepine. Dynamic Segmentation of Images Using Color and Brightness Characteristics:- Workshop on Computer Science and Information Technologies CSIT'99, Moscow, Russia, 1999

[6] A. Andryushkin. Motion from dynamic segmentation. Machine Vision Paper Collection, 1998-1999 papers call.

[7] A. Andryushkin, E. Chepin. Dynamic Segmentation of Images and Segments description.-- "COMPUTER GRAPHICS & GEOMETRY" Internet -Journal, 1999, Reg. Number 018689

Подписано к печати С У Я.СС1 'Заказ { Тираж 100 Типография МИФИ 115409, Москва, Каширское шоссе, 31

ВВЕДЕНИЕ.

ГЛАВА 1. ИЗВЕСТНЫЕ МЕТОДИКИ ВЫЧИСЛЕНИЯ ДВИЖЕНИЯ.

1.1. Зрение и движение.

1.2. Движение через вычисление оптического потока.

1.2.1. Основные понятия и ограничения.

Области с ограниченной информацией.

Изменения яркости не связанные с движением.

Временная неоднозначность.

Движение, не связанное с непосредственным перемещением объекта.

1.2.2. Локальные механизмы оценки движения.

1.2.2.1. Градиентная методика.

Комбинация локальных ограничений.

Производные высших порядков.

1.2.2.2. Методики пространственно- временной фильтрации.

Пространственно- временные энергетические модели.

Производные как пространственно-временные фильтры.

Градиентный метод и пространственно- временные энергетические модели.

Решение, использующее различные порядки в качестве ПВЭМ.

1.2.2.3. Методика Описания через Пространство Частот.

Регрессия в пространстве частот.

1.3. Методы сегментации изображений.

1.4. Классификация методов выделения движения.

1.5. Выводы по обзорной главе 1.!.

ГЛАВА 2. ОБОСНОВАНИЕ НОВЫХ МЕТОДОВ И РАЗРАБОТКА АЛГОРИТМОВ.

2.1. Вычисление движения через сегментацию.

2.1.1. Сегментация по цвето - яркостным признакам.

2.1.2. Вычисление движения.

2.2. Движение через вычисление оптического потока.

2.2.1. Обнаружение движущихся объектов на неподвижном фоне.

Вычисление с «Нулевым кадром».

Вычисление без использования «Нулевого Кадра».5.

2.2.2. Вычисление оптического потока при подвижном фоне.

Методика сопоставления.

Методы вычисления поля скоростей с использованием 3D фильтров.

2.3. Растрирование полутоновых изображений при печати.

2.4. Выводы по главе 2.

ГЛАВА 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МЕТОДОВ ВЫДЕЛЕНИЯ ДВИЖЕНИЯ.

3.1. Практическая реализация алгоритмов.

3.1.1. Реализация алгоритма вычисления движения через сегментаг{ию.

3.1.2. Реализация методики вычисления движения при неподвижном фоне.

3.1.3. Реализация алгоритма сопоставления.

3.1.4. Реализация алгоритмов на основе фильтрации.

3.1.5. Сравнение методов и сопоставление вычислительных затрат и особенностей алгоритмов в плане аппаратной реализации.

Оценка вычислительных затрат.

Сравнение алгоритмов и прогноз аппаратной реализации.

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

3.2.1. ППП «Jek - Морфология v. 4.0» и «библиотека программ для обработки изображений».

3.2.2. Программный комплекс "Pictures Demolisher".!.

3.3. Выводы по главе з.

ГЛАВА 4. ВАРИАНТЫ СОЗДАНИЯ АППАРАТНОЙ БАЗЫ ВЫДЕЛЕНИЯ ДВИЖЕНИЯ.

4.1. Аппаратное вычисление оптического потока при подвижном фоне по алгоритму непосредственного сравнения.

4.1.1. Принцип работы и основные логические блоки вычислителя.

4.1.2. Оценка потоков данных и объемов памяти. Критичные блоки.

Статическая память (SRAM).

Динамическая память (DRAM).

4.1.3. Построение вычислителя. Технические решения при построении блоков.

4.1.4. Оценка производительности.

4.2. Аппаратное вычисление оптического потока при помощи трехмерной фильтрации.

4.2.1. Общий принцип работы и основные логические блоки вычислителя.

4.2.2. Оценка потоков данных и объемов памяти.

5.2.3. Технические решения при построении вычислителя в г^елом и его блоков.

4.2.4. Оценка скорости работы аппаратного модуля.

4.3. выводы по главе 4.

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

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

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

Целями работы являются:

- анализ известных подходов к вычислению движения;

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

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

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

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

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

Научная новизна. Основными научными результатами, полученными в работе, являются следующие:

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

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

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

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

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

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

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

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

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

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

Реализация результатов.

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

В частности, разработанные алгоритмы выделения движения и оптимизированного растрирования изображений при печати были представлены в «оптимизированной библиотеке программ для обработки изображений», созданной для ООО "Электронные компоненты", а также в ППП "JEK-Морфология v.4.0", разработанного ООО «МИФИ - Система» для Лаборатории (Центра) акустической микроскопии Института биохимической физики РАН. Кроме того, предложенные варианты аппаратных модулей и программный комплекс «Pictures Demolisher», реализующий алгоритмы оценки оптического потока, были переданы в опытную эксплуатацию фирме Trilogies L.L.C (США).

4.3. Выводы по главе 4

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

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

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

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

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

Заключение

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

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

2. На основе приведенного анализа была предложена классификация методов выделения движения.

3. Был разработан новый метод вычисления движения через сегментацию. При этом была предложена новая методика сегментации изображений, адаптированная для оценки движения через сегментацию.

4. Была предложена улучшенная методика вычисления движения при неподвижном фоне.

5. В результате анализа методов было показано, что градиентная методика, и методики, использующие 3-х мерную фильтрацию, могут быть сведены к фильтрации в пространстве (x,y,t).

6. Разработаны алгоритмы и принципы построения программ, реализующие следующие методики:

- оптимизированные методики сопоставления, (в т.ч.) методика для случая неподвижного фона

- методика вычисления движения через сегментацию,

- методики, основанные на фильтрации.

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

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

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

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

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

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

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

Таким образом, можно говорить о достижении всех целей, поставленных перед kj /•— и этой работой.

1. Андрюшкин А. А. Бинарное растрирование и печать полутоновых изображений:- Санкт-Петербург: Материалы Всероссийского молодежного научного Форума, 1995

2. Андрюшкин А.А. Чепин Е.В. Растрирование полутоновых изображений:- М.: Материалы Международного Научного Конгресса студентов, аспирантов и молодых ученых, 1996.

3. Андрюшкин А.А. Чепин Е.В. Программно- аппаратное вычисление оптического потока. Научная сессия МИФИ- 2000.

4. Хасин Б.Б., Чепин Е.В. СИСТЕМА ОБРАБОТКИ И РАСПОЗНАВАНИЯЯ ИЗОБРАЖЕНИЙ JEK. Россия, МИФИ.

5. ПрэттУ. Цифровая обработка изображений, т.2 М.МИР, 1982.

6. Бутаков Е.А. Обработка изображений на ЭВМ. М. РиС, 1987.

7. Дуда А. Харт П. Распознавание образов и анализ сцен. М. Мир, 1987.

8. Фу К. Структурные методы в распознавании образов. М. Мир, 1977.

9. Шлихт Г.Ю. Цифровая обработка цветных изображений. М. Эком, 1997.

10. Яншин В. Калинин Г. Обработка изображений на языке Си для IBM PC. М. Мир, 1994.

11. Е. Н. Adelson and J. R. Bergen. Spatiotemporal energy models for the perception of motion. J. Opt. Soc. Am. A, 2(2):284-299, February 1985.

12. E. H. Adelson and J. R. Bergen. Perceptual dimensions of spatio-temporal vision. Investigative Opthalmology and Visual Science Supplement (ARVO), 27:141, 1986.

13. E. H. Adelson and J. A. Movshon. Phenomenal coherence of moving visual patterns.Nature, 300(5892):523-525, 1982.

14. G. Adiv. Determining three-dimensional motion and structure from optical flow generated by several moving objects. IEEE Pat. Anal. Mach. Intell., 4:384-401, 1985.

15. J. K. Aggarwal and N. Nandhakumar. On the computation of motion from sequences of images | a review. Proc. IEEE, 76:917-935, 1988.

16. D. G. Albrecht and W. S. Geisler. Motion sensitivity and the contrast-response function of simple cells in the visual cortex. Visual Neuroscience, 7:531-546, 1991.

17. T. D. Albright. Direction and orientation selectivity of neurons in visual area of the macaque. J Neurophysiol, 52(6): 1106-1130, December 1984.

18. P. Anandan. A computational framework and an algorithm for the measurement of visual motion. International Journal of Computer Vision, 2:283-310, 1989.

19. Alexander Andryushkin, Eugueni Tchepine. Dynamic Segmentation of Images Using Color and Brightness Characteristics:- Workshop on Computer Science and Information Technologies CSIT'99, Moscow, Russia, 1999

20. A. Andryushkin. Motion from dynamic segmentation. Machine Vision Paper Collection, 1998-1999 papers call.

21. A. Andryushkin, E. Chepin. Dynamic Segmentation of Images and Segments description:- "COMPUTER GRAPHICS & GEOMETRY" Internet Journal, 1999

22. H. B. Barlow. Single units and sensation: a neural doctrine for perceptual psychology? Perception I, pages 371-394, 1972.

23. J. L. Barron, D. J. Fleet, and S. S. Beauchemin. Performance of optical flow techniques. Technical Report RPL-TR-9107, Queen's University, Kingston, Ontario, Robotics and Perception Laboratory Technical Report, July 1992.

24. M. Basseville, A. Benveniste, К. C. Chou, S. A. Golden, R. Nikoukhah, and A. S. Willsky. Modeling and estimation of multiresolution stochastic processes. Technical Report CICS- P-283, MIT Center for Intelligent Control Systems, February 1991.

25. R. Battiti, E. Amaldi, and C. Koch. Computing optical flow across multiple scales: an adaptive coarse-to-fine strategy. Intl. J. Сотр. Vis., 6(2): 133-145, 1991. 125

26. M. Black and P. Anandan. Robust dynamic motion estimation over time. In IEEE Conference on Computer Vision and Pattern Recognition, pages 296-302, Maui, June1991.

27. M. J. Black. A robust gradient method for determining optical flow. In IEEE Conference on Computer Vision and Pattern Recognition, Champagne-Urbana, June1992.

28. R. W. Brockett. Gramians, generalized inverses, and the least-squares approximation of optical flow. J. Vis. Comm. and Image Rep., 1(1):3-11, Septemeber 1990.

29. P. J. Burt. Fast filter transforms for image processing. Computer Graphics and Image Processing, 16:20-51, 1981.

30. C. Caflorio and F. Rocca. Methods for measuring small displacements of television images. IEEE Trans. Info. Theory, IT-22:573-579, September 1976.

31. F. W. Campbell, G. F. Cooper, and C. Enroth-Cugell. The angular selectivity of visual cortical cells to moving gratings. J. Physiology (London), 198:237-250, 1968.

32. К. C. Chou, A. S. Willsky, A. Benveniste, and M. Basseville. Recursive and iterative estimation algorithms for multi-resolution stochastic processes. Technical

33. Report LIDS- P-1857, MIT Laboratory for Information and Decision Sciences, March 1989.

34. T. Darrell and A. P. Pentland. Robust estimation of a multi-layer motion representation. In Proceedings IEEE Workshop on Visual Motion, Princeton, October 1991.

35. J. G. Daugman. Uncertainty relation for resolution in space, spatial frequency, and orientation optimized by two-dimensional visual cortical filters. J. Opt. Soc. Am. A, 2(7): 1160-1169, July 1985.

36. W. Enkelmann and H. Nagel. Investigation of multigrid algorithms for estimation of optical flow fields in image sequences. Сотр. Vis. Graphics Image Proc., 43:150177, 1988.

37. M. Fahle and T. Poggio. Visual hyperacuity: spatiotemporal interpolation in human vision. Proceedings of the Royal Society of London, B, 213:451-477, 1981.

38. M. Feder and E. Weinstein. Parameter estimation of superimposed signals using the EM algorithm. IEEE Trans. Acoust. Speech Signal Proc., 36(4):477-489, April 1988.

39. C. L. Fennema and W. Thompson. Velocity determination in scenes containing several moving objects. In CGIP-9, pages 301-315, 1979.

40. V. P. Ferrara and H. R. Wilson. Perceived direction of moving two-dimensional patterns. Vis. Res., 30(2):273-287, 1990. 126

41. V. P. Ferrara and H. R. Wilson. Perceived speed of moving two-dimensional patterns. Vis. Res., 31(5):273-287, 1990.

42. D. Fleet and A. Jepson. Computation of component image velocity from local phase information. Intl. J. Сотр. Vis., 5(1):77-104, 1990.

43. D. J. Fleet and A. D. Jepson. A cascaded filter approach to the construction of velocity selective mechanisms. Technical Report RBCV-TR-84-6, Department of Computer Science, University ofToronto, 1984.

44. W. T. Freeman and E. H. Adelson. The design and use of steerable filters. IEEE Pat. Anal. Mach. Intell., 13(9):891-906, 1991.

45. D. Gabor. Theoiy of communication. J. IEE, 93:492-457, 1946.

46. A. Gelb, editor. Applied Optimal Estimation. MIT Press, 1989.

47. S. Geman and D. Geman. Stochastic relaxation, gibbs distibutions, and bayesian restoration of images. IEEE Pattern Analysis and Machine Intelligence, 6:721-741, November 1984.

48. J. J. Gibson. The Perception of the Visual World. Houghton Miflin, Boston, MA, 1950.

49. B. Girod and D. Kuo. Direct estimation of displacement histograms. In OSA meeting on Image Understanding and Machine Vision, Cape Code, Mass, 1989.

50. N. M. Grzywacz and A. L. Yuille. A model for the estimate of local image velocity by cells in the visual cortex. Proc. R. Soc. Lond. A, 239:129-161, 1990.120

51. R. M. Haralick and J. S. Lee. The facet approach to optic flow. In L. Baumann, editor, Proceedings, Image Understanding Workshop, pages 84-93. Science Applications, Arlington, VA, 1983.

52. D. J. Heeger. Model for the extraction of image flow. J. Opt. Soc. Am. A, 4(8): 1455-1471, August 1987.

53. D. J. Heeger. Optical flow using spatiotemporal filters. Intl. J. Сотр. Vis., pages 279- 302, 1988.

54. D. J. Heeger. Half-squaring in responses of cat simple cells. Visual Neuroscience, 9, 1992. In press.

55. D. J. Heeger. Normalization of cell responses in cat striate cortex. Visual Neuroscience, 9, 1992. In press.

56. D. J. Heeger, A. D. Jepson, and E. P. Simoncelli. Model of cell responses in visual area MT. In Proceedings IEEE Workshop on Visual Motion, Princeton, October 1991.

57. D. J. Heeger and E. P. Simoncelli. Model of visual motion sensing. In L. Harris and M. Jenkin, editors, Spatial Vision in Humans and Robots. Cambridge University Press, 1992. 127

58. E. C. Hildreth. Computations underlying the measurement of visual motion. Artificial Intelligence, 23(3):309-355, 1984.

59. В. K. P. Horn. Robot Vision. MIT Press, Cambridge, MA, 1986.

60. В. K. P. Horn and B. G. Schunck. Determining optical flow. Artificial Intelligence, 17:185-203, 1981.

61. D. Hubel and T. Wiesel. Receptive fields, binocular interaction, and functional architec- ture in the cat's visual cortex. J. Physiology (London), 160:106-154, 1962.

62. D. H. Johnson. The application of spectral estimation methods to bearing estimation problems. Proc. IEEE, 70:1018-1028, September 1982.

63. J. K. Kearney, W. B. Thompson, and D. L. Boley. Optical flow estimation: An error analysis of gradient-based methods with local optimization. IEEE Pat. Anal. Mach. Intell., 9(2):229-244, 1987.

64. H. Knutsson and G. H. Granlund. Texture analysis using two-dimensional quadrature filters. In IEEE Computer Society Workshop on Computer Architecture for Pattern Analysis and Image Database Management, pages 206-213, 1983.

65. F. L. Kooi, R. L. DeValois, and Т. K. Wyman. Perceived direction of moving plaids. In Invest. Opthalmol. and Vis. Sci. Suppl. (ARVO), volume 29, 1989.

66. J. O. Limb and J. A. Murphy. Estimating the velocity of moving images in television signals. Computer Graphics and Image Processing, 4:311-327, December 1975.

67. B. D. Lucas and T. Kanade. An iterative image registration technique with an application to stereo vision. In Proceedings of the 7th International Joint Conference on Artificial Intelligence, pages 674-679, Vancouver, 1981.

68. D. Marr. Vision: A Computational Investigation into the Human Representation and Processing of Visual Information. W.H.Freeman and Company, San Fransisco, 1982.

69. D. Marr and S. Ullman. Directional selectivity and its use in early visual processing. Proc. Royal Society of London B, 211:151-180, 1981.

70. J. H. R. Maunsell and D. С. V. Essen. Functional properties of neurons in middle temporal visual area of the macaque monkey i. selectivity for stimulus direction, speed, and orientation. Journal of Neurophysiology, 49(5): 1127-1147, 1983.

71. A. Mitche, Y. F. Yang, and J. K. Aggarwal. Experiments in computing optical flow with the gradient-based, multiconstraint method. Pattern Recognition, 20(2): 173179, 1987. 128

72. J. A. Movshon. Processing of motion information by neurons in the striate and ex-trastriate visual cortex of the macaque. Investigative Opthalmology and Visual Science Supplement (ARVO), 26:133, 1985.

73. D. W. Murray and B. F. Buxton. Scene segmentation from visual motion using global optimization. IEEE Pat. Anal. Mach. Intell., 9:220-228, March 1987.

74. H. Nagel and W. Enkelmann. An investigation of smoothness constraints for the estima- tion of displacement vector fields from image sequences. IEEE Pat. Anal. Mach. Intell., 8:565-593, Septemeber 1986.

75. H. H. Nagel. Displacement vectors derived from second order intensity variations in image sequences. Computer Vision, Pattern Recognition, and Image Processing, 21:85- 117, 1983.

76. K. Nakayama. Biological image motion processing: A review. Vis. Res., 25:625660, 1985.

77. S. Negahdaripour, A. Shokrollahi, and M. A. Gennert. Relaxing the brightness constancy assumption in computing optical flow. In Proc. IEEE Intern. Conf. Image Processing, pages 806-810, September 1989.

78. W. T. Newsome, M. S. Gizzi, and J. A. Movshon. Spatial and temporal properties of neurons in macaque mt. Investigative Opthalmology and Visual Science Supplement (ARVO), 24:106, 1983.

79. P. Perona. Deformable kernels for early vision. In IEEE Сотр. Soc. Conf. Computer Vision and Pattern Recognition, pages 222-227, Maui, 1991.

80. T. Poggio and W. Reichardt. Considerations on models of movement detection. Kybernet, 13:223-227, 1973.

81. T. Poggio, W. Yang, and V. Torre. Optical ow: Computational properties and networks, biological and analog. In R. Durbin, C. Miall, and G. Mitcheson, editors,

82. The Computing Neuron, chapter 19, pages 355-370. Addis on-Wesley, Wokingham, England, 1988.

83. D. Pollen and S. Ronner. Visual cortical neurons as localized spatial-frequency filters. IEEE Trans. Sys. Man Cyber., 13:907-916, 1983.

84. L. Quam. Hierarchical warp stereo. In Proceedings of the DARPA Image Understanding Workshop, September 1984.

85. E. H. A. R С Emerson, J R Bergen. Directionally selective complex cells and the com- putation of motion energy in cat visual cortex. Vision Research, 32(2):203-218, 1992.

86. W. Reichardt. Autocorrelation, a principle for the evaluation of sensory information by the central nervous system. In W. A. Rosenblith, editor, Sensory Communication. Wiley, New York, 1961. 129

87. A. Rougee, В. C. Levy, and A. S. Willsky. An estimation-based approach to the recon- struction of optical flow. Technical Report LIDS-P-1663, MIT Laboratory for Information and Decision Systems, April 1987.

88. M. Shizawa and K. Mase. Simultaneous multiple optical flow estimation. In IEEE Conference on Computer Vision and Pattern Recognition, Atlantic City, June 1990.

89. M. Shizawa and K. Mase. A unified computational theory for motion transparency and motion boundaries based on eigenenergy analysis. In IEEE Conference on Computer Vision and Pattern Recognition, Maui, June 1991.

90. E. P. Simoncelli. Computing optical flow from first and second order directional cosines. Vision and modeling technical report, MIT Media Laboratory, November 1992.

91. E. P. Simoncelli. Distributed representations of image velocity. Vision and Modeling Technical Report 202, MIT Media Laboratory, October 1992.

92. E. P. Simoncelli and E. H. Adelson. Computation of optical flow: Relationship between several standard techniques. Vision and Modeling Technical Report 165, MIT Media Laboratory, November 1990. Revised, March 1991.

93. E. P. Simoncelli and E. H. Adelson. Optical flow distributions: gradient, energy and re- gression methods. In Optical Society of America, Annual Meeting, Boston, MA, November 1990.

94. E. P. Simoncelli and E. H. Adelson. Relationship between gradient, spatio-temporal energy, and regression models for motion perception. In Investigative Opthalmology and Visual Science Supplement (ARVO), volume 32, 1991.

95. E. P. Simoncelli, E. H. Adelson, and D. J. Heeger. Probability distributions of optical flow. In IEEE Conference on Computer Vision and Pattern Recognition, Mauii, Hawaii, June 1991.

96. E. P. Simoncelli and D. J. Heeger. A computational model for representation of image velocities. In Investigative Opthalmology and Visual Science Supplement (ARVO), volume 34, 1993.

97. Е. P. Simoncelli, D. J. Heeger, and E. H. Adelson. Perception of 3D motion in the presence of uncertainly. Inlnvestigative Opthalmology and Visual Science Supplement (ARVO), volume 31, 1990.

98. E. P. Simoncelli, D. J. Heeger, and E. H. Adelson. A computational model for perception of two-dimensional pattern velocities. In Investigative Opthalmology and Visual Science Supplement (ARVO), volume 33, 1992.

99. A. Singh. Incremental estimation of image- flow using a kalman filter. In Proceedings IEEE Workshop on Visual Motion, Princeton, October 1991.

100. P. Sobey and M. V. Srinivasan. Measurement of optical flow by a generalized gradient scheme. J. Opt. Soc. Am. A, 8(9): 1488-1498, September 1991. 130

101. M. V. Srinivasan. Generalized gradient schemes for the measurement of two-dimensional image motion. Biol. Cybern., 63:421-431, 1990.

102. L. S. Stone and P. Thompson. Human speed perception is contrast dependent. Vis. Res., 32(8): 1535-1549, 1992.

103. L. S. Stone, A. B. Watson, and J. B. Mulligan. Effect of contrast on the perceived direction of a moving plaid. Vis. Res., 30(7): 1049-1067, 1990.

104. R. Szeliski. Bayesian modeling of uncertainly inflow-level vision. International Journal of Computer Vision, 5(3):271-301, December 1990.

105. D. Terzopoulos. Image analysis using multigrid relaxation methods. IEEE Pat. Anal. Mach. Intell., 8:129-139, 1986.

106. P. Thompson. Perceived rate of movement depends on contrast. Vis. Res., 22:377-380, 1982.

107. O. Tretiak and L. Pastor. Velocity estimation from image sequences with second order differential operators. In IEEE, pages 16-19, 1984.

108. S. Uras, F. Girosi, A. Verri, and V. Torre. A computational approach to motion percep- tion. Biol. Cybern., 60:79-87, 1988.

109. J. P. H. van Santen and G. Sperling. Temporal covariance model of human motion perception. J. Opt. Soc. Am. A, 1:451-473, 1984.

110. A. Verri and T. Poggio. Motion field and optical flow: Qualitative properties. IEEE Pat. Anal. Mach. Intell., pages 490-498, 1989.

111. A. B. Watson and A. J. Ahumada. A look at motion in the frequency domain. In J. K. Tsotsos, editor, Motion: Perception and representation, pages 1-10. 1983.

112. A. B. Watson and A. J. Ahumada. Model of human visual-motion sensing. J. Opt. Soc. Am. A, 2:322-342, 1985.

113. A. M. Waxman and K. Wohn. Contour evolution, neighbourhood deformation, and global image flow: Planar surfaces in motion. Inter. J. Robotics Res., 4:95-108, 1985.

114. L. Welch. The perception of moving plaids reveals two motion-processing stages. Nature, 337:734-736, 1989.

115. H. R. Wilson, V. P. Ferrera, and C. Yo. A psychophysical^ motivated model for two- dimensional motion perception. Visual Neuroscience, 9:79-97, 1992. 131

116. Sarah Douglas and Ted Kirkpatrick. Do Color Models Really Make a Difference? Department of Computer Science, University of Oregon, 1995

117. Alvy Ray Smith. The HSV-RGB Transform Pair. Published in the Internet, 1996

118. Understanding DRAM Performance Specifications. IBM Applications Note, 12/96

119. Understanding DRAM Operation. IBM Applications Note, 12/96

120. Understanding Static RAM Operation. IBM Applications Note, 03/97

121. Michael J. Zulich. DRAM: The Next Generation. Computer Shopper, June 1997.