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

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

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


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

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

Similar posts

AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 31

    +4
    Вы под дельтой пороговое значение подразумеваете, я так понял?
    И да: уберите стрелочки, а то кажется, что алгоритм определяет направление движения, а не наличие или отсутствие.
      0
      да, «дельта» другими словами — пороговое значение. Для каждой маски подбирается свое.
        0
        Можете тогда этот «подбор» пояснить? Почему написано, что отнимается 2, но при этом просто убраны двойки из маски, и почему именно 2?
          0
          Я убираю «на глаз». Смотрю все значения по изображению и определяю, при какой «дельте» (каком пороге) маска будет иметь необходимый вид (чтобы различные шумы на нее почти не влияли). А в шагах 6 и 7 — смотрим, чтобы и блики убирались нормально, и реальный объект не сильно «съедало».
          Может есть и математический метод какой. Но я такой не искал. На глаз настроил и работает.
          На второй вопрос — 2 это и есть порог. То что равно или меньше обнуляем, все что больше — оставляем.
      +1
      Спасибо! Очень познавательно, как для меня.
        +2
        Есть ощущение, что в реальном видео с камеры будет работать лучше, ибо 2 соседних кадра не могут очень сильно отличаться. Итого — порогом будут порезаны незначительные движения деревьев и смена освещённости (далеко они за 1/20 секунды на простой веб-камере не переедут), а если ещё и подключить предыдущий кадр, и вычитать его движения, то всё вообще должно быть чистенько. Кажется мне…
          0
          зачастую такие алгоритмы требуется использовать с камерами наблюдения, которые сильно шумят, дают мало fps и т.д.
            0
            На практике, в режиме слежения не обязательно «колбасить» со скоростью 1/20 сек. У меня работает сейчас слежение с паузой 0.3 сек. При записи — 0.1 сек.
            Так вот за 0.3 секунды освещение может сильно меняться, пришлось улучшать алгоритм.
            А так вы правы. В статье я привел экстремальный пример.
            +5
            Как насчет воспользоваться Гаусс-размытием?
            Сила размытия будет определять границу между подавлением шумов и чувствительностью определения движения. Определить силу размытия можно на этапе калибрации: включить камеру на неподвижную сцену и снять первые десяток-два кадров для проведения сравнения и выделения шумов.

            После того, как с шумами разобрались, остается проблема автоподстройки камеры под изменение светового заполнения сцены. Эту проблему можно как игнорировать (в случае, если камера профессиональная и подобная автоподстройка может быть выключена), так и обработать далее:
            — выбросить «мигающий» кадр
            — определить, не произошло ли полное перестроение источников света (включили/выключили свет в помещении)

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

            Грубый анализ можно реализовать через вычитание двух соседних (а может и не соседних) размытых гауссом кадров — Вы получите перемещение контрастных точек. После этого проведение уточнения следует делать в окрестностях этих точек, не тратя процессорное время на неизменную часть кадра. Определение границ объекта может проходить как с помощью готовых алгоритмов (заливка, повышение контрастности), так и прикидочным образом с помощью попиксельного/поблочного вычитания.
              0
              Я как-то занимался похожей задачей. Поэтому вопрос: почему нельзя просто оценить арифметическую разность двух кадров, и не заморачиваться вообще ни с чем?
                0
                Например, шумы испортят вам всю малину.
                  +1
                  Представляем изображение в HSV, используем только H, шумы фильтруем элементарным гауссом (медианный фильтр, конечно, лучше, но он слишком медлителен для realtime). В итоге разность двух изображений даст нам надежную оценку, чего там новенького появилось.

                    0
                    Медианный фильтр, если его грамотно написать, вполне подходит для обработки реального видео (у меня, например, медианный фильтр 3х3 занимает менее 1 мс для 1 мегапиксельного серого изображения на одном ядре).
                      0
                      Вы сейчас на какой вопрос ответили?
                        0
                        На этот:
                        Например, шумы испортят вам всю малину.
                          0
                          А вы прочитали на что это был ответ? Там был вопрос, почему бы, не заморачиваясь ни с чем, просто не подсчитать арифметическую разность кадров. Я ответил почему нельзя. На что вы отвечаете мне непонятно.
                      0
                      я думаю, количество шума на двух фотографиях, снятых с разностью 5 секунд, будет одинаковым. Этот уровень и сделать пороговым.

                      Зачем избавляться от шума, если он присутствует на обоих изображениях в одинаковом количестве.
                      В любом случае, если в кадре появляется человек, то это будет значительное изменение, точно не шум.
                        0
                        Количество будет примерно равным, расположение шумовых элементов, очевидно, будет разным. Вот это вам и помешает просто вычесть один кадр из другого.
                          0
                          если уровень шума будет одинаковым, то можно просто не обращать на него внимания.
                            0
                            Ложные срабатывания даст.
                              0
                              минимальный порог = кол-во шума*2
                                0
                                т.е. порог срабатывания сделаем в два раза больше, чем количество шума.
                                  0
                                  Что значит «количество шума»? Все равно вам после вычитания кадров придется сделать медианную либо другую сглаживающую фильтрацию, иначе шум вида «соль-перец» будет давать множество ложных срабатываний. Ну, а после сглаживания нужно будет бинаризовать результат и выделить связанные области, которые и будут масками, позволяющими выделить новые объекты на кадре.
                      0
                      Just For Fun и для самообучения — сойдёт и интересно… Спасибо. Хотя я в подобных случаях просто настраиваю Motion :)
                        +2
                        Жуткая картинка. Девушка без ног.
                          0
                          наверно она их под себя подложила :)
                            0
                            а стул у нее на ливитационной платформе )
                          • UFO just landed and posted this here
                          • UFO just landed and posted this here
                              +2
                              Для этих целей принято использовать алгоритм Lucasa-Kanade: Лучший мануал от Jean-Yves Bouguet.
                              Вот тут картинки Лекция про оптический поток.
                              Ваш подход мне показался наивным. Как по вашему алгоритму определить параметры проективных (или афинных в упрощении) искажений?
                                +3
                                Это конечно интересно, но почему для видео наблюдения, не использовать обычные датчики объема, на подобие этих www.gsm-alert.ru/media/catalog/product/cache/1/image/70e4f3cdda829922f4301d3770cbe283/5/5/55.jpg, точность срабатывания будет выше, да и реализовать такую систему гораздо проще, а если скомбинировать эти 2 метода, вообще хорошо будет.

                                Only users with full accounts can post comments. Log in, please.