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

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

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

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



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



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

    Подробности для задачи стереозрения
    В задаче стереозрения я использовал Гауссово распределение, конкретно 1000 частиц. Кадр слева — это изображение с левой камеры. Я моделирую фокусировку внимания тем, что мышью кликаю на произвольную точку в левом кадре. На видео вы увидите зеленый прямоугольник на левом кадре. Назовем его «фокус внимания». Одновременно это будет наша первоначальная гипотеза, т.е. мы верим, что фокусу внимания на левом кадре соответствуют области приблизительно с такими же координатами на правом кадре.

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


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

    Подробности для задачи стереозрения
    Правильность (т.е. вес) каждой частицы в нашей задаче — это мера ее подобия фокусу внимания в левом кадре. Напоминаю, что частицы у нас — в правом кадре. Частицы у нас — это матрицы 8х8 черно-белых значений яркости пикселов исследуемой области. Я тупо вычитаю одну матрицу 8х8 из другой (т.е. левую из правой или наоборот) и считаю сумму квадратов разностей. Чем меньше это число, тем более одинаковые левое и правое изображение.

    ВНИМАНИЕ! Это очень примитивный способ сравнения двух областей изображения. Есть способы гораздо лучше, например перед вычитанием делать нормализацию локального контраста. Я бы начал улучшения с того, что учитывал цветность, сейчас я ее игнорирую и все считаю в оттенках серого.


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

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

    Зная координаты предыдущего и нового фокуса, мы получаем вектор перемещения (например, на 19 пикселов влево и 2 пиксела вниз).


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

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

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

    Отобранным частицам мы изменяем координаты на плоскости, прибавляя вектор перемещения фокуса плюс случайное значение (по Гауссу с центром в 0).

    Эти частицы мы изображаем в правом нижнем кадре.


    Все. Цикл.

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

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

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

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

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



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

    UPDATE

    Исходный код pastebin.com/a8hDiyMc

    Требования:
    • Установить Python с сайта python.org
    • Установить numpy с сайта scipy.org
    • Установить pygame с сайта pygame.org
    • Запустить программу с двумя параметрами: путь к JPEG-файлу левого кадра и путь к JPEG-файлу правого кадра


    Не судите за качество кода, писалось для собственного развлечения.

    Similar posts

    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 24

      +1
      Очень круто! Даже не приходило в голову решать эту задачу при помощи Particle Filter.
        +2
        Наверное, меня заминусуют, но мне в голову даже сама задача не приходила...)
          +1
          Particle Filter — отличная вещь, когда надо учитывать предысторию процесса. Я например сейчас его пытаюсь использовать в одной задаче по обработке текста!
          0
          Супер!
          А где-то доступна реализация под Mac OS (что на видео)?
            +1
            Реализация на Python, не зависит от платформы. Да и не реализация это, а просто непромышленный код, попробовать идею.
            0
            Хм. Нам все время твердят, что использовать sampling в компьютерном зрении как-бы моветон.
            Кстати, а что вы используете как меру похожести точек? Просто сравниваете кусочки 8х8 пикселей или все же SIFT/SURF?
              0
              Кусочки. В статье написано под спойлером.

              SIFT конечно отличная технология, но меня интересуют более «гуманные» или биологически обоснованные подходы. Пусть они менее точные пока.
              0
              Очень интересно! Самому «поиграться» можно с результатом или это будущая часть коммерческого продукта?
                0
                Нет, никакой коммерции. Если есть интерес, выложу исходники.
                  0
                  На самом деле сам давно размышлял об этой идее и лет о ужас 10 назад в матлабе пытался реализовать, но до ума не довёл. В общем интерес есть самый настоящий. Готов предложить рефакторинг вашего кода на плюсах.
                    0
                    Вывесил исходники — смотрите Update в статье.
                0
                Правильно я понимаю, что построить карту глубины в автоматическом режиме этим методом нельзя? А какова тогда его практическая ценность?
                Particle Filter это конечно здорово, но задачу «сопоставления «одной и той же точки» на двух изображениях» он не решает в общем случае.
                  +1
                  Кстати, а вы раньше интересные и очень познавательные статьи выкладывали по обработке изображений!:)
                  Но что-то ничего нового давно не появлялось(
                    0
                    Ну так ничего интересного из теории не появляется, потому и писать не о чем…
                    Что касается построения карт глубин, то самые лучшие результаты дают вроде бы алгоритмы на марковских цепях, но что-то они настолько сложные что я так и не смог их толком понять :)
                      0
                      Particle Filter вполне можно рассматривать как алгоритм на марковских цепях. Есть последовательность действий, предыстория. Этот алгоритм даже преподают в блоке с марковскими цепями. Только он очень понятный :)
                    0
                    Ваш вопрос показывает как свободную мысль загоняют в рамки шаблонных решений. Карта глубины что, теперь, единственный полезный продукт любого алгоритма? Я предлагаю способ как сопоставлять две области на изображениях. Хотите построить карту глубины — походите подольше по всему кадру. Меня больше интересовало как смоделировать процесс микроскопических колебаний глаза при рассматривании сцены. Всего в 200 строках кода получилось показать как анализируются несколько гипотез и отбираются наиболее правдоподобные с учетом предыстории.

                    Извините за ошибки набираю с андройда.
                      0
                      >Ваш вопрос показывает как свободную мысль загоняют в рамки шаблонных решений
                      Боже упаси :) Я просто позиционирую данный алгоритм. Это не есть алгоритм сопоставления областей изображения. Области вы сопоставляете простым сравнением локальной области.

                      >Я предлагаю способ как сопоставлять две области на изображениях.
                      Правильно это фраза должна звучать «Я предлагаю способ как вручную сопоставлять две области на изображениях», потому что алгоритм без вас этого сделать не может.

                      >Хотите построить карту глубины — походите подольше по всему кадру.
                      Это не алгоритм…
                        0
                        Мне кажется, вы не поняли идею. Я не просто сопоставляю области, а сопоставляю последовательность областей. Например если у меня забор из одинаковых досок, то в разных местах этого забора локальные области будут практически неразличимы. Но если я моделирую перемещение фокуса внимания вдоль забора, то достаточно точно позиционируюсь.

                        Что касается ручного режима, то тривиально делается автоматическое перемещение фокуса внимания на случайный вектор или даже лучше с учетом градиента в предыдущей локальной области. Зачем упражняться в очевидном?
                          0
                          Так я ж вас и спрашиваю, может ли ваш алгоритм работать в атономном режиме? Вы же сразу начали про «закапывание идей» :)

                          >Но если я моделирую перемещение фокуса внимания вдоль забора, то достаточно точно позиционируюсь.

                          Дык для того что бы программа сама моделировала движение вдоль забора, она должна «понимать» где этот забор. А этого ж как раз и нет.

                          >Что касается ручного режима, то тривиально делается автоматическое перемещение фокуса внимания на случайный вектор или даже лучше с учетом градиента в предыдущей локальной области

                          Если вы будете перемещать «фокус внимания» случайным образом, ваш алгоритм работать не будет, ибо он основан на том, что вы перемещаетесь вдоль какого-либо объекта, а не произвольно.
                          Поправте меня, если я не прав.
                            0
                            Нет, не должна она понимать где забор. Мое единственное предположение: если я в левом кадре смотрю на точку (x, y), то на правом кадре где-то рядом с (x, y) должна быть похожая область. Затем я случайно перемещаюсь в левом кадре в точку (x + dx, y + dy), а в правом кадре перемещаю частицы, наиболее похожие на область (x, y) левого кадра на тот же вектор dx, dy с добавлением шума.

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

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

                            Если не лень попробовать, могу выложить также несколько кадров. Хотя их можно просто снять своим телефоном, не особенно беспокоясь за калибрацию. Я так вначале и делал.
                              0
                              Я понимаю ход ваших мыслей. Однако метод который вы предлагаете даст заведомо худший результат, чем метод динамического программирования.
                              Это легко доказать: метод динмического программирования гарантированно дает решение, при котором невязка между левым и правым изображением — минимальна. У вас же алгоритм ничего не гарантирует, а значит дает худший результат. Более того, результат вашего алгоритма не детерминирован. Ведь если вы будете сканировать строки слева направо и справа налево, то вы получите разные результаты.
                              По сути вы применяете самую простую инутитивную эвристику: если точка сдвинута на dx, то и соседняя точка тоже сдвинута на dx. К сожалению, это простое и неправильное решение. Оно дает посредственные результаты.
                              Кроме того, для этой эвристики можно применить более простую схему с предсказывающим фильтром (типа фильтра габора) и без всяких партиклов и роев.
                    0
                    Задача построении карты глубин по двум изображениям, даже откалиброванными камерами нормально не решается. Слишком большие ошибки вылазят, проблемное детектирование границ. Годится только в узкоспециализированных задачах. Восстановление 3D с одной камеры из видеопотока в общем случае и то лучше работает.
                      0
                      Это следующий этап — восстановление 3d. Как раз и проверим не выгоднее ли использовать particle filter в услоаиях реального времени и реальной биологической задачи. Здесь не карта глубины важна, а отбор наиболее информативных фрагментов кадра. Например движущихся или быстро приближающихся к нашему организму.

                      Уже купил нокию е6 на замену надоевшему андро. В нокии питон удобный с легкими библиотеками доступа ко всем нужным аппаратным функциям…
                      –1
                      компу торное зрение в массы стажёров и руководителей

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