Введение
Данную статью я решил написать после прочтения статьи «Массивно-параллельная стабилизация изображения», в которой описывается алгоритм для стабилизации изображения с поворотных камер. Дело в том, что в свое время мной был реализован алгоритм для стабилизации изображения со стационарных камер, который используется в 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 — для компенсации сдвига.
Посмотреть результат работы алгоритма
Автор: ErmIg
