Алгоритм Particle Filter в компьютерном зрении: стереовидение

Алгоритм Particle Filter замечателен своей простотой и интуитивной понятностью. Предлагаю собственный вариант его использования в задаче стереоскопического зрения для сопоставления «одной и той же точки» на двух изображениях — с левой и правой камеры. Для реализации (исключительно в целях развлечения) использован Python с библиотеками numpy (матричные вычисления) и pygame (графика и обработка событий мышки). Сам алгоритм Particle Filter без изменений взят из курса Programming a Robotic Car ^[1] на Udacity. Меня извиняет лишь то, что я честно прослушал весь курс и сделал все домашние работы, включая и реализацию этого алгоритма.

В задаче стереоскопического зрения нужно сопоставлять малые области (например, 8х8 пикселей) на левом и правом кадре. При идеальном расположении камер строго горизонтально, зная разность координаты по оси Х одинаковой области между левым и правым кадром, можно вычислить расстояние до объекта, который изображен в этой области. Понимаю, что звучит запутанно, но на самом деле это легко выводится простейшими геометрическими построениями по правилу подобных треугольников. Например, на видео с недостроенной колокольней, мы видим уходящий вдаль забор с одинаковыми ромбами. Ближний к нам ромб наиболее сильно смещен на правом кадре относительно левого, следующий — чуть меньше и т.д.

Стандартная схема решения такой задачи довольно тяжелая в вычислительном плане. Нужно откалибровать погрешности взаимного расположения камер так, чтобы гарантировать, что горизонтальная линия с координатой Y на левом кадре точно соответствует горизонтали с той же координатой на правом кадре. Затем сопоставить каждой точке (или области ) вдоль горизонтальной линии на левом кадре наилучшую точку на правом кадре (это решается, например, методом динамического программирования, имеющем квадратическую сложность). Тогда у нас будут вычислены смещения по Ох для каждой точки вдоль рассматриваемой горизонтали. И повторить процедуру для каждой горизонтальной линии. Немного сложновато, и уж совсем не похоже на то, как это работает в мозге ^[2] (мы ведь знаем это, правда?)

Посмотрите, как алгорим Particle Filter решает эту же задачу. На мой взгляд, это очень похоже на биологическую модель, по крайней мере имитируются микро-движения глаза для фокусировки внимания на отдельных фрагментах изображения, и учитывается «предыстория» таких микро-движений.

Сам алгоритм Particle Filter очень прост. Генерируем N точек, называем из частицами (particles). Частицы располагаем на плоскости случайным образом вокруг первоначальной гипотезы.

Затем для каждой частицы проверяем, насколько она «правильная». Чем более она правильная, тем больше у нее вес (все поняли, что мы составляем матрицу весов, то есть вектор, ну короче вы поняли).

Теперь мы перемещаем гипотезу. В алгоритме Particle Filter мы должны хотя-бы приблизительно знать, куда мы перемещаем гипотезу.

Теперь самая соль алгоритма. Мы порождаем новое облако частиц из старых частиц. При этом делаем два действия: выбираем «старые» частицы пропорционально их весу и перемещаем их на тот же вектор, на который переместилась гипотеза.

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

Все. Цикл.

Теперь мы отбираем из всего облака 10 частиц с наибольшим весом (их мы показываем на правом верхнем кадре). Среднее значение их центра считаем координатами фокуса нашего внимания на правом кадре. То есть мы получили соответствующую область на правом и левом кадре! Можем вычислить разность координат, подставить в формулу (в которой участвует также расстояние между камерами и фокусное расстояние объектива) и получить координату Z — расстояние от камер до точки фокуса нашего внимания.

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

Итог нашей работы — черное поле с белыми точками в левом нижнем углу окна. Там отображаются точки в проекции сверху. Смотрите: с 0 по 9 секунду мы мысленно движемся вдоль забора, и белые точки появляются параллельно нижнему краю экрана, то есть соответствуют виду на забор сверху.

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

Наконец, когда мы переносим взгляд на колокольню, мы видим, что облако частиц внезапно «растерялось», то есть перемещение фокуса оказалось слишком большим, и не удалось выявить явного соответствия между изображениями. Но буквально за 3-4 итерации облако опять сжимается, и мы уверенно отслеживаем контуры и окна колокольни. При этом разрешающей способности камеры уже не хватает, чтобы отобразить разницу в координатах между левым и правим кадром, поэтому расстояние Z до колокольни становится равным бесконечности. Заметим, что разрешение кадров действительно плохое, всего 230х344.

На этом видео алгоритм протестировали с другим изображением. Смотрите, как уверенно мы справляемся с могильными плитами на 0-20 секундах. Далее мы успешно отрисовываем контуры тени от куста и сам куст — обратите внимание, что на проекции он правильно попадает в среднюю часть отбрасываемой им тени. И затем опять переносимся взглядом на задний план, теряемся в облаке частиц, но быстро восстанавливаемся и уверенно находим одинаковые фрагменты стены. Но они уже так бесконечно далеко от нас…

Автор: sergeypid