Цифровая стабилизация изображения со стационарных камер — корреляционный подход

    Введение


    Данную статью я решил написать после прочтения статьи «Массивно-параллельная стабилизация изображения», в которой описывается алгоритм для стабилизации изображения с поворотных камер. Дело в том, что в свое время мной был реализован алгоритм для стабилизации изображения со стационарных камер, который используется в IP-видеосервере MagicBox и некоторых других продуктах компании Синезис, в которой я работаю по настоящее время. Алгоритм получился достаточно удачным по своим скоростным характеристикам. В частности, в нем очень эффективно реализован алгоритм поиска смещения текущего изображения относительно фона. Эта эффективность позволила задействовать основные его элементы (конечно с некоторыми модификациями) для сопровождения объектов, а также для проверки их на неподвижность.

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

    Рис. 1 Стабилизация изображения иногда очень полезна.


    Обнаружение смещения текущего кадра


    Базовый подход, на котором основывается корреляционный подход по определению смещения, можно кратко описать так:
    1) Берется центральная часть фонового изображения. Величина отступа определяется максимальным возможным смещением, которое мы хотим определить. Центральная часть не должна быть слишком маленькой, иначе у корреляционной функции (смотри ниже) не будет хватать данных для стабильной работы.
    2) На текущем кадре выбирается часть такого же размера, но смещенная относительно центра картинки.
    3) Для каждого смещения рассчитывается некоторая метрика, описывающая корреляцию центральной части фона и текущего изображения. Для этого может быть использована, например, сумма квадратов разности для каждой точки этих двух изображений или, например, сумма абсолютной разности для каждой точки.
    4) Смещение, для которого корреляция максимальна (меньше сумма квадратичных разностей или сумма абсолютных разностей), и будет искомым смещением.

    Рис. 2 Смещение текущего кадра относительно фона.

    Естественно, что если такой подход применить в лоб, то скорость работы алгоритма будет катастрофически низкой, даже не смотря на то, что скорость работы корреляционной функций может быть очень высока. Это не удивительно, так как нам нужно будет перебирать все варианты возможного смещения изображений относительно друг друга (сложность алгоритма можно оценить как O(n^2), где n – число точек изображения).

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

    Рис.3 Поиск максимума корреляционной функции. Градиентный спуск.

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

    Рис.4 Многомасштабное изображение.

    Субпиксельная точность


    Если компенсировать дрожание изображения с камеры с точностью до пиксела, то стабилизированное изображение будет все равно весьма заметно дергаться. К счастью это можно исправить. Если внимательно проанализировать окрестность корреляционной функции вблизи максимума (см. рис 3), то можно заметить, что значения функции не симметричны относительно максимума, что говорит о том, что максимум располагается не в точке (3, 2), где-то между ней, и точкой (1, 4). Если аппроксимировать поведение корреляционной функции вблизи максимума параболоидом A*x^2 + B*x*y + C*y^2 + D*x + E*y + F = 0, то задача уточнения координат максимума сведется к подбору таких параметров параболоида, при которых его отклонение от фактических значений в известных точках минимально. Опыт подсказывает, что точность получаемого таким образом уточнения будет порядка 0.1-0.2. При компенсации дрожания с такой точностью, стабилизированное изображение уже практически не дергается.

    Компенсация смещения


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

    Обновление фона


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

    Работа в паре с детектором движения


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

    Плюсы предложенного подхода:


    1) Высокая скорость работы алгоритма. В частности, для стабилизации изображения разрешением 1280x720 в формате BGRA32 на процессоре Core i7-4470 (задействовано 1 ядро) алгоритму требуется 1.5 миллисекунды.
    2) Компенсация дрожания камеры с субпиксельной точностью.

    Недостатки предложенного подхода


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

    Замечания по практической реализации


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

    При реализации стабилизатора желательно использовать оптимизированные функции для работы с изображениями. Я для этих целей использовал библиотеку Simd. В ней в частности можно найти:
    1) SimdAbsDifferenceSum и SimdAbsDifferenceSumMasked — для расчета корреляционной функции.
    2) SimdReduceGray2x2, SimdReduceGray3x3, SimdReduceGray4x4 и SimdReduceGray5x5 — для построения многомасштабных изображений.
    3) SimdBgrToGray — для получения серого изображения.
    4) SimdShiftBilinear — для компенсации сдвига.

    Посмотреть результат работы алгоритма


    Пример 1:


    Пример 2:
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 23

      +3
      Идея хороша, но пример совсем плох. Может там вообще в видео редактор поставили фиксированный кадр и изредка изредка «тягали»? Покажите работу в динамике: с людьми, поездом, птицами. А то вдруг их тоже «стабилизирует»?
        +1
        Работает честно — во время тряски движущиеся объекты сопровождаются детектором движения. В данном примере тоже все честно — я сам лично штатив с камерой тряс :).
          +2
          во время тряски движущиеся объекты сопровождаются детектором движения

          Ну так покажите!
            +1
            Добавил пример с сопровождением объектов. Не понимаю, почему вы мне не верите — алгоритм реализован уже пять лет назад. И 4 года как минимум присутствует в готовых продуктах.
              0
              Очень даже верю, но полноценно картинка сложилась только после последнего видео.
              Спасибо!
        +1
        а что за продукт?
        0
        Почему бы не использовать уже существующие алгоритмы матчинга? берем motion estimation или тот же SURF, получаем сматченные точки, потом аппроксимируем аффинное или перспективное преобразование (с RANSAC для стабильности), применяем к картинке, вуаля. Я использовал ME + перспективное + RANSAC для более сложной задачи, все ок. Если нужно побыстрее — меняем SURF на FAST и получаем матчинг за единицы миллисекунд!
        рекомендую к просмотру
        www.youtube.com/watch?v=fYUDfD2nc0A
        www.youtube.com/watch?v=QdXugkXBTbc
          +2
          Ну так, а у меня и 1.5 миллисекунды, из которых поиск корреляционного максимума — 0.3 миллисекунды, а остальное компенсация ARGB изображения методом билинейной интерполяции.
            0
            Зато по точкам можно будет компенсировать поворот + не только стационарную съемку. При этом укладываясь в realtime (25 FPS)
              0
              Предполагаю, что судя по описанному применению решения (системы видеонаблюдения) проблема тут не только в том что нужно укладываться в реалтайм, а в том что нужно укладываться в реалтайм на 32 одновременно обрабатываемых сервером каналах. Т.е. нужно выдавать 25 х 32 = 800 FPS на имеющихся мощностях.
              Решения требующие 1 ядро на обработку одной камеры в системах видеонаблюдения будут неконкурентоспособны.
          0
          Какая именно «метрика» корреляционной функции у вас применялась и каков размер «центральной части»? Максимальное смещение в роликах, похоже, не очень-то большое по отношению к размеру кадра?
            0
            В качестве корреляционной функции использовалась сумма абсолютных разностей точек изображений. Максимальное смещение — где-то четверть от высоты изображения.
              0
              Следовательно, центральная часть, которая сравнивается, примерно вполовину кадра?
                0
                Зависит от максимально возможного смещения, которое компенсируется (выступает в качестве параметра алгоритма). Для максимально возможного значения сравнивается действительно где-то половина изображения, но по умолчанию процентов 75.
            0
            Мне кажется, ваши последовательные масштабные преобразования то же самое, что производить градиентный спуск с переменным шагом. Интересное решение.

            Если вычислять корреляцию не в 9 точках на каждом шаге, а в 5 (крестиком), то количество вычислений в вашем квадратике уменьшится с 36 до 25, что существенно быстрее
              0
              Градиентный спуск с переменным шагом надо делать над исходным изображением, а не над уменьшенным (правда это частично компенсируется необходимостью строить многомасштабные изображения). У многомасштабного изображения есть другой плюс — в процессе их построения происходит усреднение и сглаживание, что уменьшает вероятность попасть в ложный локальный максимум.
                0
                Да, это понятно
              0
              Удивился, когда не увидел в статье слова «БПФ»/«FFT».
                0
                Второе видео где вода течет, та часть которая с водой ровненько так встала в половину кадра с «оригиналом», ну а на половинке где стабилизированное изображение, воды с рябью нет. Крайне удобно выбран ракурс. Можете прогнать тот же алгоритм на том же видео, но теперь уже стабилизировать ту часть где вода. Хочется посмотреть что он сделает с рябью.
                  0
                  Чуда не будет, о чем я честно указал в статье (см. раздел Недостатки предложенного подхода).
                  0
                  1) Стабилизация изображения в текущей реализации возможна только для стационарных камер.
                  — если опорный кадр постоянно сдвигать на усредненное смещение, то высокочастотные дрожания компенсируются, а сканирование (или дрейф опорного кадра) будет отслеживаться, примерно так, правда, с некоторым запаздыванием, зависящим от степени усреднения
                    0
                    Прошелся по своим старым комментариям, заметил что Вы и в самом деле написали эту статью. =)

                    Спасибо Вам огромное.

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