Содержание к диссертации
ВВЕДЕНИЕ 4
ГЛАВА 1. ИЗВЕСТНЫЕ МЕТОДИКИ ВЫЧИСЛЕНИЯ ДВИЖЕНИЯ. 7
1.1. ЗРЕНИЕ и ДВИЖЕНИЕ 7
1.2. ДВИЖЕНИЕ ЧЕРЕЗ ВЫЧИСЛЕНИЕ ОПТИЧЕСКОГО ПОТОКА 8
1.2.1. Основные понятия и ограничения 8
Области с ограниченной информацией 10
Изменения яркости не связанные с движением 11
Временная неоднозначность 11
Движение, несвязанное с непосредственным перемещением объекта 12
7.2.2. Локальные механизмы оценки движения 12
1.2.2.1. Градиентная методика 14
Комбинация локальных ограничений 16
Производные высших порядков 18
1.2.2.2. Методики пространственно- временной фильтрации 19
Пространственно-временные энергетические модели 20
Производные как пространственно-временные фильтры 21
Градиентный метод и пространственно- временные энергетические модели 23
Решение, использующее различные порядки в качестве ПВЭМ 25
1.2.2.3. Методика Описания через Пространство Частот 27
Регрессия в пространстве частот 28
1.3. МЕТОДЫ СЕГМЕНТАЦИИ ИЗОБРАЖЕНИЙ 30
1.4. КЛАССИФИКАЦИЯ МЕТОДОВ ВЫДЕЛЕНИЯ ДВИЖЕНИЯ 34
1.5. Выводы по ОБЗОРНОЙ ГЛАВЕ 1 : 37
ГЛАВА 2. ОБОСНОВАНИЕ НОВЫХ МЕТОДОВ И РАЗРАБОТКА АЛГОРИТМОВ 38
2.1. ВЫЧИСЛЕНИЕ ДВИЖЕНИЯ ЧЕРЕЗ СЕГМЕНТАЦИЮ 38
2.1.1. Сегментация по цвето - яркостным признакам 39
2.1.2. Вычисление движения 45
2.2. ДВИЖЕНИЕ ЧЕРЕЗ ВЫЧИСЛЕНИЕ ОПТИЧЕСКОГО ПОТОКА 49
2.2.7. Обнаружение движущихся объектов на неподвижном фоне 49
Вычисление с «Нулевым кадром» 49
Вычисление без использования «Нулевого Кадра» 5.0
2.2.2. Вычисление оптического потока при подвижном фоне 53
Методика сопоставления 53
Методы вычисления поля скоростей с использованием 3D фильтров 60
2.3. РАСТРИРОВАНИЕ ПОЛУТОНОВЫХ ИЗОБРАЖЕНИЙ ПРИ ПЕЧАТИ 62
2.4. Выводы по ГЛАВЕ 2 67
ГЛАВА 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МЕТОДОВ ВЫДЕЛЕНИЯ ДВИЖЕНИЯ 68
3.1. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ 68
3.1.1. Реализация алгоритма вычисления движения через сегментацию 68
3.1.2. Реализация методики вычисления движения при неподвижном фоне 70
3.1.3. Реализация алгоритма сопоставления 72
3.1.4. Реализация алгоритмов на основе фильтрации 74
3.1.5. Сравнение методов и сопоставление вычислительных затрат и особенностей алгоритмов в плане аппаратной реализации 77
Оценка вычислительных затрат 77
Сравнение алгоритмов и прогноз аппаратной реализации 79
3.2. ПРИКЛАДНЫЕ ПРОГРАММЫ, СОЗДАННЫЕ В РАМКАХ РАБОТЫ И ИХ ВНЕДРЕНИЕ .81
3.2.1. ППП «Зек - Морфология v.4.0» и «библиотека программ для обработки изображений» 57
3.2.2. Программный комплекс "Pictures Demolisher" 82
3.3. Выводы по
ГЛАВЕ 3 84
ГЛАВА 4. ВАРИАНТЫ СОЗДАНИЯ АППАРАТНОЙ БАЗЫ ВЫДЕЛЕНИЯ ДВИЖЕНИЯ 85
4.1. АППАРАТНОЕ ВЫЧИСЛЕНИЕ ОПТИЧЕСКОГО ПОТОКА ПРИ ПОДВИЖНОМ ФОНЕ ПО АЛГОРИТМУ НЕПОСРЕДСТВЕННОГО СРАВНЕНИЯ 85
4.1.1. Принцип работы и основные логические блоки вычислителя 86
4.1.2. Оценка потоков данных и объемов памяти. Критичные блоки 88
Статическая память (SRAM) 90
Динамическая память (DRAM) 92
4.1.3. Построение вычислителя. Технические решения при построении блоков. 94
4.1.4. Оценка производительности 101
4.2. АППАРАТНОЕ ВЫЧИСЛЕНИЕ ОПТИЧЕСКОГО ПОТОКА ПРИ ПОМОЩИ ТРЕХМЕРНОЙ ФИЛЬТРАЦИИ 102
4.2.1. Общий принцип работы и основные логические блоки вычислителя 103
4.2.2. Оценка потоков данных и объемов памяти 105
5.2.1. Технические решения при построении вычислителя в целом и его блоков. 108
4.2.1. Оценка скорости работы аппаратного модуля 113
4.3. Выводы по
ГЛАВЕ 4 115
ЗАКЛЮЧЕНИЕ 116
ЛИТЕРАТУРА 118
ПРИЛОЖЕНИЯ 126
ПРИЛОЖЕНИЕ А. ШИРОКО РАСПРОСТРАНЕННЫЕ МОДЕЛИ ПРЕДСТАВЛЕНИЯ ЦВЕТА 126
ПРИЛОЖЕНИЕ Б. Акты о ВНЕДРЕНИИ 127
Введение к работе
Попытки использовать компьютеры для решения задач машинного восприятия окружающего мира появились одновременно с появлением вычислительных машин. Однако до сих пор способность машины воспринимать реальный мир остается крайне ограниченной. Для преобразования света, звука, температуры и т.д. в электрические сигналы созданы разнообразные датчики и устройства. Если обрабатываемые машиной сигналы просты и четко ограничены, то задача восприятия информации кажется несложной. Но, как только от машины требуется чтение рукописного текста или ориентация в пространстве, вместо задач ввода информации приходится иметь дело с гораздо более сложными задачами ее интерпретации.
Та видимая легкость, с которой животные и даже насекомые справляются с задачами восприятия, одновременно и ободряет, и обескураживает. Психологические и физиологические исследования дали ряд интересных результатов, касающихся процессов восприятия животными. Тем не менее, этого пока недостаточно для воспроизведения процессов восприятия с помощью машин. Бесполезными оказываются и попытки исследования сущности восприятия посредством самоанализа из-за того, что, по-видимому, большинство обычных процессов восприятия протекает подсознательно. Задача ориентации в пространстве становится день ото дня все более актуальной. Причиной тому служит выход компьютеров из лабораторий и машинных залов для применения на каждом шагу. Уже появляются первые приборы, способные самостоятельно общаться друг с другом, улучшая качество обслуживания человека. Пройдет совсем немного времени, и новые покорения автоматизированных систем заполнят нашу жизнь. И уж конечно, этим машинам понадобится гораздо больше «зрительной» информации об окружающем мире для уверенной ориентации в нем.
Актуальность темы определяет то, что анализ сцен реального мира без сомнения будет важнейшей составляющей задачи ориентации. При этом, несмотря на многолетние усилия в плане разрешения этих проблем, приходится признать, что до сих пор эти вопросы остаются нетривиальными. Для задачи анализа сцен реального мира важнейшим этапом является анализ движения. Исследования показывают, что именно анализ движения является важнейшей частью биологических систем. При этом для машинных решений наиболее актуален анализ движения на последовательности кадров. Уверенная ориентация машин может быть достигнута только при условии обработки информации в режиме реального времени. Отсюда следуют и особые требования, накладываемые на скорость работы подсистемы оценки движения. Проблеме оценки и анализа движения на последовательности кадров уделено значительное внимание со стороны исследователей всего мира. К настоящему моменту существует как значительное количество методик оценки движения, так и их успешных реализаций. Но, в тоже время, известные методики либо не могут быть реализованы в режиме реального времени, либо представляют собой узкоспециальные решения, предназначенные для ограниченного круга задач.
Целями работы являются:
- анализ известных подходов к вычислению движения;
- описание вновь разработанных методик, используемых для оценки движения;
- разработка практических алгоритмов, их программная реализация и исследование их параметров;
- разработка вариантов создания аппаратных ускорителей для решения проблем оценки движения в реальном времени.
В работе будут рассмотрены различные подходы к вычислению движения.
В главе 1 будут проанализированы различные ранее известные алгоритмы, проведено обобщение их свойств, произведено сравнение их характеристик.
В главах 2 и 3 диссертации будет рассмотрен ряд оригинальных подходов к вычислению движения, а так же обратимся к вопросу построения алгоритмов и практической программной реализации для новых и известных методов.
Глава 4 посвящена вопросам аппаратной реализации подсистем выделения движения. Хотелось бы отметить, что предлагаемые аппаратные решения в достаточной степени гибки и позволяют совершенствовать алгоритмы выделения движения.
Для достижения поставленных целей в работе использовались следующие методы исследования: Теория обработки изображений, теория дифференциальных уравнений, теория структурного программирования, алгоритмы вычислительной математики. Основные теоретические результаты проверялись экспериментально, результаты экспериментальной программной реализации алгоритмов послужили основой для создания вариантов аппаратных ускорителей вычислений.
Научная новизна. Основными научными результатами, полученными в работе, являются следующие:
- Разработана новая методика сегментации изображений по цвето- яркостным характеристикам.
- Предложен и разработан подход оценки движения объектов на последовательном наборе кадров, основанный на сегментации изображений и отслеживании перемещений сегментов.
- Показана возможность реализации большинства известных алгоритмов вычисления оптического потока через линейную фильтрацию.
Практическая ценность работы заключается в следующем:
- Разработаны алгоритмы и программное обеспечение, реализующие методику сегментации изображений и оценки движения на основе сегментации. Разработаны алгоритмы и программы вычисления оптического потока методом непосредственного сравнения.
Созданы алгоритмы и программы, реализующие различные методики вьиисления оптического потока на основе трехмерной фильтрации, работа которых подтвердила правильность теоретических обоснований.
Предложены варианты построения аппаратных ускорителей, позволяющие производить вычисление движения в реальном времени.
Созданы программные комплексы, использующие предложенные алгоритмы вычисления движения, в составе которых также предложены методики, алгоритмы и программы, реализующие качественный вьшод изображений на печать.
Приведенные в работе алгоритмы тестировались на искусственных и натуральных последовательностях изображений. Результаты работы алгоритмов показаны в главе 2.
Реализация результатов.
Созданные на основе разработанных алгоритмов программы применены на практике, о чем свидетельствуют акты, приведенные в приложении Б.
В частности, разработанные алгоритмы выделения движения и оптимизированного растрирования изображений при печати были представлены в «оптимизированной библиотеке программ для обработки изображений», созданной для 000 "Электронные компоненты", а также в ППП "JEK-Морфология v.4.0", разработанного 000 «МИФИ - Система» для Лаборатории (Центра) акустической микроскопии Института биохимической физики РАН. Кроме того, предложенные варианты аппаратных модулей и программный комплекс «Pictures Demolisher», реализующий алгоритмы оценки оптического потока, были переданы в опытную эксплуатацию фирме Trilogies L.L.C (США).
