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

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

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

• 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 и попробовать работать без канала яркости, то можно увеличить точность алгоритма. Руки еще не дошли проверить.

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