Метод математического регрессионного анализа смежных кадров подстилающей поверхности

Введение

Опубликовано немало теоретических статей [1, 3, 4] об автокорреляционных способах определения динамических параметров движения и ориентации мобильного объекта трассированием характерных точек (трассеров) на смежных кадрах видеозаписи «подстилающей» поверхности.

Появлению таких способов и их быстрому современному развитию способствовало создание дешевых микроконтроллеров и малогабаритных телевизионных камер с прямоугольно-координатной пиксельной структурой фоточувствительных ПЗС-матриц, работоспособных в широком диапазоне освещенности [2].

Эти способы стали использовать даже для навигации всем известных оптических компьютерных «мышек». В них устанавливают специальные микросхемы, которые выпускают компании AVAGO, PixArt Imaging и Genius, с устройством лазерной подсветки коврика, играющего роль «подстилающей» поверхности. Каждая такая микросхема представляет собой миниатюрную ТВ‑камеру по цене не дороже 100 руб./шт. со встроенным DSP-микропроцессором и с ПЗС-матрицей размерностью от 8×8 до 20×20 пикселей.

Суть известных автокорреляционных способов определения динамических параметров движения и ориентации трассированием «подстилающей» поверхности заключается в том, что на мобильном объекте жестко закрепляют источник подсветки и специальную ТВ‑камеру, направив оптическую ось ее фотообъектива перпендикулярно к подсвечиваемой «подстилающей» поверхности. При этом источник подсветки и физическая природа его излучения могут быть самыми разными: локальные, дистанционные, ИК или УФ, радио, лазерные и т. д.

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

Для анализа видеокадров методом трассирования с помощью математической автокорреляции [3] требуется:

• Для каждой точки в предшествующем кадре отыскивать (идентифицировать) соответственную ей точку в последующем смежном кадре.
• Непрерывно измерять градацию яркости всех точек трассеров, используя для этого ПЗС-матрицу с высокой чувствительностью и большим количеством пикселей.
• Многократно повторять процесс идентификации всех пар точек изображения или характерных зон во всех кадрах видеозаписи.

На выполнение указанных действий, особенно на процесс идентификации, микроконтроллер ИСН может затрачивать до 80% ресурса времени вычислений.

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

Предложенный регрессионный математический метод анализа контрастных точек растра в смежных кадрах видеозаписи «подстилающей» поверхности позволяет применить в навигационных системах недорогие ТВ‑камеры с ПЗС-матрицами меньшей размерности, а значит, сократить время вычислений динамических параметров движения и ориентации мобильного объекта, причем без потери точности расчетов.

Построение метода математического регрессионного анализа контрастных точек смежных кадров

Объектив ТВ‑камеры на ПЗС-матрице создает изображения быстро мелькающих разноцветных точек-трассеров, или, как говорят, проецирует «бег подстилающей поверхности». Поэтому:

• Во‑первых, выберем и зафиксируем (навсегда!) нужную бинарную величину порога чувствительности.
• Во‑вторых, будем считать, что «подстилающая» поверхность не деформируется, то есть расположение всех контрастных точек на ней не меняется во времени. В расплавленных, газовых и жидких средах это не так.
• В‑третьих, поставим в соответствие каждому пикселю из массива размерностью (N, M) ПЗС-матрицы логическую переменную l_i,j из массива Dim{l_i,j}_N,M с той же размерностью, причем так, чтобы ее величина «0» (false) означала отсутствие, а «1» (true) — наличие контрастной точки в этом месте на «подстилающей» поверхности. Благодаря видеосъемке с достаточно высокой кадровой частотой ПЗС-матрица формирует мгновенные кадры, повернутые или плоскопараллельно сдвинутые конечное количество раз относительно своего начального положения.

Теперь построим регрессионную математическую модель «бега» контрастных точек на «подстилающей» поверхности по их изображениям в виде черно-белых пикселей на ПЗС-матрице. Для этого, мысленно пронумеровав по порядку все кадры видеозаписи числами 1, 2, 3, 4, 5… и т. д., сравним между собой попарно изображения в смежных кадрах с номерами: 1–2, 2–3, 3–4, 4–5 и т. д.

На рисунке условно показаны последовательные этапы эволюции кадров относительно «подстилающей» поверхности: плоскопараллельно сдвинутый (синий) и повернутый (зеленый) относительно исходного кадра (красного). Здесь же показаны контрастные точки на «подстилающей» поверхности, причем некоторые из них попали в границы соответствующих кадров ПЗС-матрицы, а некоторые выпали за их пределы.

Рисунок. Последовательные этапы эволюции кадров
относительно «подстилающей» поверхности

На практике в диапазоне даже малых стандартных кадровых частот видеозаписи от 16 до 200 Гц сюжеты смежных кадров отличаются друг от друга гораздо менее ощутимо, чем показано на рисунке. Это обстоятельство и позволяет применить дифференциальное исчисление.

В основу идеи вычисления навигационных параметров мобильного объекта положим метод математической линейной регрессии булевых переменных в массиве с размерностью (N, M), а не традиционно применяемый метод трассирования с помощью математической автокорреляции.

Но прежде докажем три теоремы «существования» (класс таких теорем существования по традиции принято называть «теоремами Коши»), то есть докажем корректность применения математического метода линейной регрессии для навигационных целей в нашем случае.

Пусть кадр, изображенный красным цветом (рисунок), является начальным в последовательности кадров. Дополним массив точек в начальном кадре еще одной точкой T₀(x₀,y₀), которую назовем центром регрессионного группирования данного кадра.

Вычислим векторы отклонений между центром регрессионного группирования кадра и каждой другой точкой следующим образом:

Теперь синтезируем четную (!) целевую функцию в виде суммы векторов отклонений , умноженных на соответствующие весовые коэффициенты. Границы индексов суммирования зададим в пределах плоскости кадра в соответствии с номерами пикселей в его растре, причем четная степень исключит влияние знаков проекций векторов отклонений на сумму.

Итак:

Физический смысл этой функции означает сумму квадратов отклонений всех точек в кадре от одной общей точки — центра регрессионного группирования. В этой формуле λ_i,j для всех точек в кадре имеют значения «0» или «1» из ранее указанного булевого массива Dim{λ_i,j}_N,M. И хотя аргументами целевой функции в пределах плоскости кадра являются дискретно изменяющиеся аргументы — модули векторов отклонений, будем считать целевую функцию непрерывной. На практике ошибка в вычислениях не превосходит величины удвоенного расстояния между соседними пикселями ПЗС-матрицы, а этим можно пренебречь из-за его малого значения (не более 3,5 мкм).

Теорема 1. О единственности центра регрессионного группирования в кадре.

Для доказательства теоремы единственности центра регрессионного группирования найдем на непрерывной плоскости, ограниченной размерами кадра, точку, в которой достигается минимум указанной выше целевой функции.

Считая, как было сказано выше, координаты векторов отклонений непрерывными аргументами, выполним систему условий для частных производных целевой функции:

Очевидно, что указанные условия равносильны системе из двух уравнений:

Решая совместно уравнения (1), получим выражения для координат искомой точки T₀(x₀,y₀):

Таким образом, согласно (2) можно сделать вывод, что регрессионный центр группирования кадра существует и является единственным. Он обладает уникальными координатами (2) в текущем кадре, зависящими только от распределения точек в массиве Dim{l_i,j}_N,M. Теорема доказана.

Теорема 2. При плоскопараллельном сдвиге предшествующего кадра на произвольную величину, то есть при сдвиге координат всех T_i,j — точек массива в системе X0Y, координаты центра регрессионного группирования в следующем кадре сдвигаются на ту же величину.

Используя доказанную теорему 1, выполним доказательство очевидным переписыванием и преобразованием уравнений (2):

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

Теорема 3. При повороте кадра на произвольный угол α вокруг центра 0 в системе координат X0Y центр регрессионного группирования кадра поворачивается на тот же угол.

Используя доказанную теорему 1 и выполнив соответствующее переписывание и преобразование уравнений (2), получим (4).

или окончательно 

  или окончательно 

Полученные окончательные формулы (4) совпадают с известными формулами преобразования координат точек при повороте системы координат, что доказывает истинность утверждения теоремы о повороте центра регрессионного группирования кадра.

Построение локальной полярной системы координат

Для расчета изменений координат из-за поворотов объекта построим в текущем кадре полярную систему координат с центром, совпадающим с центром регрессионного группирования.

Известно, что уравнение плоской прямой линии общего положения имеет вид:

Y = kx+b.                      (5)

Если на этой же линии лежит точка T₀(x₀,y₀), то:

y₀ = kx₀+b.                 (6)

Вычитая выражение (6) из (5), получим простое уравнение:

y–y₀ = k(x–x₀)           (7)

плоской линии полярной оси, проходящей через центр регрессионного группирования кадра (точку T₀(x₀,y₀)).

Для определения параметра k в выражении (7) снова используем принцип линейной регрессии, «подбирая» его значение так, чтобы вектор полярной оси максимально «плотно» прилегал ко всем  — радиусам-векторам точек массива, попавших в кадр, то есть выполним целевое условие:

Находя выражение для частной производной в явном виде и решая его относительно k с учетом (6), получим:

Итак, в каждом кадре локальная полярная система координат представлена:

полюсом, совпадающим (по построению) с центром регрессионного группирования кадра в точке T₀(x₀,y₀);

полярной осью в виде вектора:

Выводы

Предложенный метод математического регрессионного анализа контрастных точек растра в смежных кадрах видеозаписи «подстилающей» поверхности для навигации мобильного объекта позволяет применить в навигационных системах недорогие черно-белые ТВ‑камеры с ПЗС-матрицами меньшей размерности и, значит, сократить время вычислений динамических параметров движения и ориентации мобильного объекта, причем без потери точности расчетов.

Во всех приведенных уравнениях операции суммирования проводятся по индексам 1 ≤ i ≤ N и 1 ≤ i ≤ M контрастных точек в растре ПЗС-матрицы в предположении, что в процессе эволюций предыдущего кадра все точки окажутся в последующем смежном кадре.

На практике это не так: количество проецируемых объективом ТВ‑камеры и «попавших», «сместившихся» или «выпавших» точек в границах смежных кадров сильно зависит от соотношения скорости съемки и скорости движения мобильного объекта. Однако даже в диапазоне малых стандартных кадровых частот видеозаписи от 16 до 200 Гц сюжеты смежных кадров отличаются друг от друга незначительно. Выбрав необходимую скорость видеосъемки, мы можем пренебречь погрешностями вычислений.