Алгоритм Particle Filter замечателен своей простотой и интуитивной понятностью. Предлагаю собственный вариант его использования в задаче стереоскопического зрения для сопоставления «одной и той же точки» на двух изображениях — с левой и правой камеры. Для реализации (исключительно в целях развлечения) использован Python с библиотеками numpy (матричные вычисления) и pygame (графика и обработка событий мышки). Сам алгоритм Particle Filter без изменений взят из курса Programming a Robotic Car на Udacity. Меня извиняет лишь то, что я честно прослушал весь курс и сделал все домашние работы, включая и реализацию этого алгоритма.
В задаче стереоскопического зрения нужно сопоставлять малые области (например, 8х8 пикселей) на левом и правом кадре. При идеальном расположении камер строго горизонтально, зная разность координаты по оси Х одинаковой области между левым и правым кадром, можно вычислить расстояние до объекта, который изображен в этой области. Понимаю, что звучит запутанно, но на самом деле это легко выводится простейшими геометрическими построениями по правилу подобных треугольников. Например, на видео с недостроенной колокольней, мы видим уходящий вдаль забор с одинаковыми ромбами. Ближний к нам ромб наиболее сильно смещен на правом кадре относительно левого, следующий — чуть меньше и т.д.
Стандартная схема решения такой задачи довольно тяжелая в вычислительном плане. Нужно откалибровать погрешности взаимного расположения камер так, чтобы гарантировать, что горизонтальная линия с координатой Y на левом кадре точно соответствует горизонтали с той же координатой на правом кадре. Затем сопоставить каждой точке (или области ) вдоль горизонтальной линии на левом кадре наилучшую точку на правом кадре (это решается, например, методом динамического программирования, имеющем квадратическую сложность). Тогда у нас будут вычислены смещения по Ох для каждой точки вдоль рассматриваемой горизонтали. И повторить процедуру для каждой горизонтальной линии. Немного сложновато, и уж совсем не похоже на то, как это работает в (мы ведь знаем это, правда?)
Посмотрите, как алгорим Particle Filter решает эту же задачу. На мой взгляд, это очень похоже на биологическую модель, по крайней мере имитируются микро-движения глаза для фокусировки внимания на отдельных фрагментах изображения, и учитывается «предыстория» таких микро-движений.
Сам алгоритм Particle Filter очень прост. Генерируем N точек, называем из частицами (particles). Частицы располагаем на плоскости случайным образом вокруг первоначальной гипотезы.
Координаты этой точки будут центром распределения частиц. Облако частиц генерируем в правом кадре. На видео два правых кадра. На нижнем (черно-белом) показано все облако частиц. На верхнем (цветном кадре) показаны только наиболее «правильные» 10 частиц. О том, что такое правильные частицы, смотрите ниже.
Затем для каждой частицы проверяем, насколько она «правильная». Чем более она правильная, тем больше у нее вес (все поняли, что мы составляем матрицу весов, то есть вектор, ну короче вы поняли).
ВНИМАНИЕ! Это очень примитивный способ сравнения двух областей изображения. Есть способы гораздо лучше, например перед вычитанием делать нормализацию локального контраста. Я бы начал улучшения с того, что учитывал цветность, сейчас я ее игнорирую и все считаю в оттенках серого.
Теперь мы перемещаем гипотезу. В алгоритме Particle Filter мы должны хотя-бы приблизительно знать, куда мы перемещаем гипотезу.
Зная координаты предыдущего и нового фокуса, мы получаем вектор перемещения (например, на 19 пикселов влево и 2 пиксела вниз).
Теперь самая соль алгоритма. Мы порождаем новое облако частиц из старых частиц. При этом делаем два действия: выбираем «старые» частицы пропорционально их весу и перемещаем их на тот же вектор, на который переместилась гипотеза.
То есть чем больше вес «старой» частицы, тем с большей вероятностью она перейдет в новое облако. Есть еще один нюанс, при перемещении новых частиц мы обязательно добавляем хаотическую пограшность к вектору перемещения.
Отобранным частицам мы изменяем координаты на плоскости, прибавляя вектор перемещения фокуса плюс случайное значение (по Гауссу с центром в 0).
Эти частицы мы изображаем в правом нижнем кадре.
Все. Цикл.
Теперь мы отбираем из всего облака 10 частиц с наибольшим весом (их мы показываем на правом верхнем кадре). Среднее значение их центра считаем координатами фокуса нашего внимания на правом кадре. То есть мы получили соответствующую область на правом и левом кадре! Можем вычислить разность координат, подставить в формулу (в которой участвует также расстояние между камерами и фокусное расстояние объектива) и получить координату Z — расстояние от камер до точки фокуса нашего внимания.
Посмотрите на видео, как уменьшается облако частиц после нескольких перемещений фокуса. Вначале алгоритм не знает, «где мы находимся», но после 2-3 итераций облако сжимается, и как бы отслеживает перемещения фокуса внимания с учетом предыстории. Это большое преимущество нашего алгоритма. Например, для стандартного алгоритма стереозрения череда повторяющихся элементов по горизонтали — почти непреодолимое препятствие. На нашем видео это забор с повторяющимися ромбами. За счет того, что алгоритм помнит предысторию, он уверенно отличает ромбы один от другого.
Итог нашей работы — черное поле с белыми точками в левом нижнем углу окна. Там отображаются точки в проекции сверху. Смотрите: с 0 по 9 секунду мы мысленно движемся вдоль забора, и белые точки появляются параллельно нижнему краю экрана, то есть соответствуют виду на забор сверху.
Далее с 13 по 32 секунду мы смотрим на удаляющийся от нас забор. Точки на проекции сверху правильно отображают эту ситуацию. Затем мы еще пробегаемся по тропинке вдоль забора, и белые точки рисуют нам план тропинки (там есть следы от какой-то коляски на песке, но на видео в низком разрешении их почти не видно).
Наконец, когда мы переносим взгляд на колокольню, мы видим, что облако частиц внезапно «растерялось», то есть перемещение фокуса оказалось слишком большим, и не удалось выявить явного соответствия между изображениями. Но буквально за 3-4 итерации облако опять сжимается, и мы уверенно отслеживаем контуры и окна колокольни. При этом разрешающей способности камеры уже не хватает, чтобы отобразить разницу в координатах между левым и правим кадром, поэтому расстояние Z до колокольни становится равным бесконечности. Заметим, что разрешение кадров действительно плохое, всего 230х344.
На этом видео алгоритм протестировали с другим изображением. Смотрите, как уверенно мы справляемся с могильными плитами на 0-20 секундах. Далее мы успешно отрисовываем контуры тени от куста и сам куст — обратите внимание, что на проекции он правильно попадает в среднюю часть отбрасываемой им тени. И затем опять переносимся взглядом на задний план, теряемся в облаке частиц, но быстро восстанавливаемся и уверенно находим одинаковые фрагменты стены. Но они уже так бесконечно далеко от нас…
Автор: sergeypid
