15 декабря 2011

Алгоритм определения движения через сравнение двух кадров

Алгоритмы
Из песочницы
Здравствуйте, хабражители.
Хочу с вами поделиться своими наработками по обработке изображений. В последнее время занимаюсь написанием домашнего сервера под «умный дом» и начал с видеонаблюдения.
Задача оказалась не такой тривиальной. По поводу всего видеонаблюдения я напишу отдельно (если кому-то это интересно), а сейчас хотел бы затронуть тему «Алгоритм определения движения через сравнение двух кадров».
Этот алгоритм необходим для включения (выключения) записи видео с видеокамер.
Информации по этой теме в сети не так много. Изначальный алгоритм придумывал сам (он очень простой), а улучшить его мне помогла статья «Алгоритм детектирования теней на видеоизображении».
В этой статье затрону только алгоритм (без примеров на языке программирования). Весь алгоритм базируется на циклах, все элементарно и просто для воссоздания на вашем любимом языке программирования.
Примеры в описаниях алгоритма буду давать как «живые» так и придуманные таблицы (для понимания).

Базовый алгоритм


  • 1. Берем два последних кадра с видеокамеры.

    Frame 1 и Frame 2. Картинки взяты для примера. На втором кадре «вышло солнце» (увеличил яркость), появились блики на стенах и полу. За стол села девушка и от нее стала падать тень.
  • 2. Дробим изображение на блоки и получаем их среднее значение по цвету.
    Зачем разделять на блоки. К примеру, 640х480 разделяем на блоки размером 10х10 и берем из каждого блока цвета 25 пикселей). Получаем вместо ~300 000 пикселей и итераций для анализа всего ~3000 итераций и ~75 000 пикселей для анализа. Для определения движения можно допустить такое упрощение.

  • 3. Сравниваем полученные две таблицы цветов (матрицы) и получаем разницу цветов по каждому блоку в третей таблице.
    Назовем ее MoveMask

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

    (1) – применение «дельты» (в данном примере отнимаем 2)
    (2) – переход в готовую маску



    Пример наложения маски (изменений в изображении) на реальный кадр.
  • 5. Считаем «силу» изменений на изображении с помощью MoveMask.
    Я это делаю, суммируя рядомстоящие блоки по горизонтали (отнимая отдельностоящие, выжившие после чистки от шумов) и по такому же алгоритму суммирую уже суммы рядов по вертикали. По полученной сумме измененных блоков (рядомстоящих) и подобранному порогу срабатывания флага «есть движение» настраивается триггер.
    К примеру, посчитаем такую MoveMask

    В данном примере, «сила» изменений равна 12. «Сила» на одинаковое изменение будет разной, в зависимости от размера блоков. Поэтому размер блоков и порог срабатывания (при какой «силе» срабатывает триггер движения) настраиваются относительно друг друга.

Преимущества данного алгоритма: простота программирования, малая ресурсоемкость, хорошая чувствительность (малейшие движения не пропускает).
Недостаток вижу только один – срабатывание на изменение освещенности. Так как весь алгоритм построен на анализе цвета, то в облачную погоду вы легко сможете следить за тем, когда солнце выходит из-за туч и в комнате становится намного светлее. В этот момент страбатывают блоки по всему изображению. В п.4 алгоритма, я показал маску с завышенной «дельтой». Реально же на этом примере (см. п.1) с рабочей дельтой маска закрывает почти весь кадр.

Если завышать дельту (как в п.4 нашего алгоритма), то это сильно сказывается на чувствительности, и наш датчик движения может перестать срабатывать на слабо освещенных объектах.

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

Улучшенный алгоритм


  • 1. Берем два последних кадра с видеокамеры.

    Frame 1 и Frame 2
  • 2. Дробим изображение на блоки и получаем их среднее значение по цвету.
  • 3. Сравниваем полученные две таблицы цветов (матрицы) и получаем разницу цветов по каждому блоку в третей таблице.
  • 4. Фильтруем третью таблицу от шумов.
    Назовем итоговую таблицу MoveMask.
  • 5. На этом шаге получаем таблицу усредненных значений возле каждого блока (см. изображение).
    Получаем что-то типа усредненного фона вокруг точки.

    Суммируются блок с цифрой и соседние блоки (отмечены точками). Можно брать и больше соседних блоков. Среднее значение помещается в блок с цифрой. Таблицы назовем AvFrame (1 и 2).
  • 6. Делаем таблицу разницы между значениями, полученными на шаге 5 и фильтруем ее по своей «дельте».
    Аналогично, как и с кадрами в пункте 3 первого алгоритма. См. там же иллюстрацию.

    Эта маска показана на реальном кадре.
  • 7. Теперь делаем перемножение, которое называется «относительная корреляция» (см. статью, указанную в начале).
    Создаем таблицу, где в ячейки пишем результат следующего вычисления |frame1[x][y] x AvFrame2[x][y] – frame2[x][y] x AvFrame1[x][y]|. Опять фильтруем своей «дельтой».
    Т.е. мы умножает цвет блока из первого кадра на среднее значение в таком же блоке, но второго кадра, аналогично цвет блока второго кадра, на среднее первого и находим разницу.

    Эта маска на реальном кадре.
  • 8. Теперь скрещиваем таблицы из п. 6 и п. 7.
    Я в результирующую таблицу (назовем ее MaskFilter) положил среднее арифметическое только в те ячейки, которые положительные в обеих таблицах.

    Получаем такую картину
  • 9. Фильтруем MoveMask фильтром MaskFilter.
    Оставляем в MoveMask только те блоки, которые присутствуют в MaskFilter на тех же позициях (или рядом).

    Отфильтрованный MoveMask на изображении. Сравните с п.4 первого алгоритма.
  • 10. Дополнительно (не обязательно) можно еще отфильтровать MoveMask, удаляя блоки, у которых мало соседей (к примеру, меньше 4).

    Окончательный вид маски.
  • 11. И в конце, считаем «силу» изменений с помощью готовой таблицы MoveMask.
    См. п.5 первого алгоритма.



В данном алгоритме, фильтруя MoveMask фильтром MaskFilter, мы удаляем из MoveMask большинство блоков, которые срабатывают на тень или блик. Можно уменьшить более чем в два раза ошибочные срабатывания датчика.
Из недостатков, огромное количество “дельт” и сложность как программирования, так и настройки алгоритма.


Алгоритм базовый и алгоритм улучшенный.
На данном примере тень, блики на стенах и окнах удалось убрать полностью. Блики на полу оказались «пережаренными» и не исчезли. Но, возможно, для этого помещения, подкорректировав одну из «дельт», можно настроить фильтр на игнорирование и бликов с пола. Разные помещения – разные подстройки алгоритма.

Как можно еще улучшить алгоритм


Может, если конвертировать RGB в HSV и попробовать работать без канала яркости, то можно увеличить точность алгоритма. Руки еще не дошли проверить.

Надеюсь, мой опыт и это описание алгоритма кому-то пригодится. А если у вас есть что дополнить, исправить, подсказать – буду рад услышать.
Теги:алгоритмывидеонаблюдениеобработка изображений
Хабы: Алгоритмы
+79
18,1k 217
Комментарии 31
Лучшие публикации за сутки

Минуточку внимания

Разместить