Фильтрация ложных соответствий между изображениями при помощи динамического графа соответствий


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

    Постановка задачи


    Пусть имеем два набора особых точек полученных с двух изображений P и Q с np и nq точками соответственно.Каждая особая точка представляет собой пару p={pd, pc}. pd — представляет собой местную особенность точки(например SURF-дескриптор), а pc={x,y} — координаты особой точки.
    Имеем множество соответствий M={ci = (i, i') | ci ∈ C, i ∈ P, i' ∈ Q}, построенное при помощи некоторой метрики(например как точки с ближайшими по Евклидовой метрике дескрипторами). Для каждого соответствия построим неотрицательную функцию оценки Sci=f1(id, i'd).

    Для двух соответствий ci=(i, i') и cj=(j, j') предположим, что расстояние между точками i и j на первом изображении и точками i' и j' на втором изображении lij и li'j' соответственно. Очевидно, что если эти два соответствия верные, то мы можем выровнять изображение Q по отношению к P с масштабным коэффициентом lij frasl; li'j', и мы говорим что эта пара соответствий голосует за масштаб lij frasl; li'j'. Теперь предположим, что имеется визуальный образ с n соответствующих ему правильных соответствий, тогда для каждой пары этих соответствий масштабный коэффициент должен быть примерно одинаковый. Такой масштаб будем называть масштабным коэффициентом геометрической согласованности и обозначать через s. Масштабный коэффициент геометрической согласованности пары соответствий ci=(i, i') и cj=(j, j') выражается как:
    Scicj(s)=f2(|lij — s*li'j'|), где f2(x) — неотрицательная монотонно убывающая функция.

    Пускай множество M содержит m соответствий M={c1, ..., cm}. Построим граф G с m вершинами, каждая вершина из которого представляет соответствие из M. Вес ребра между вершинами i и j определяется следующим образом:
    wij(s)=Sci*Scj*Scicj(s).
    Построенный таким образом граф будем называть Динамическим Графом Соответствий(далее ДГС).

    Взвешенную матрицу смежности для ДГС обозначим A(s) и построим следующим образом:

    A(s) ∈ Rm*m — симметрична и неотрицательна.

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

    Если мы представим T в виде индикатор-вектора y такого, что , то средняя внутри-кластерная оценка может быть переписана в квадратичной форме:
    , где , .

    Как известно, теорема Моцкина-Штрауса устанавливает связь между максимальной кликой и локальным максимумом такой квадратичной формы:
    , где — стандартный симплекс в Rm. Проще говоря, в теореме говорится, что подмножество T вершин графа G является максимальной кликой тогда и только тогда, когда его характеристический вектор xT является локальным максимумом квадратичной функции f(x) в стандартном симплексе, где xiT = 1⁄|T| если i ∈ T, xiT=0 иначе.

    Хотя оригинальная теорема Моцкина-Штрауса относится только к не взвешенным графам, Паван и Пелилло обобщили её на взвешенные графы и установили связь между плотными подграфами и локальными максимумами уравнений.

    Принятая норма l1 имеет ряд преимуществ. Во-первых, имеет простой вероятностный смысл: xi представляет вероятность того, что полный подграф содержать вершину i. Во-вторых, решение x разреженно, и только некоторые компоненты в том-же подграфе имеют большое значение, остальные компоненты имеют достаточно малые значения, что позволяет выделить кластер отбросив те вершины которые являются шумом являющиеся шумом.

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

    Описание алгоритма


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

    При инициализации x(1), соответствующее локальное решение x может быть эффективно получено при помощи уравнения самосборки первого порядка, имеющего вид:


    Можно заметить, что симплекс Δ инвариантен относительно такой динамики, а это значит, что любая траектория начинающаяся в Δ, останется в Δ. Кроме того, было доказано, что когда A(s0) симметрична и с неотрицательными элементами, целевая функция строго возрастает вдоль любой неконстантной траектории уравнения самосборки, и эти асимптотически устойчивые точки находятся в строгом взаимно-однозначном соответствии с локальными решениями квадратичной функции.

    Грубо говоря, для того чтобы найти все крупные локальные максимумы x, берут много начальных инициализаций и таким образом гарантируют, что все крупные локальные максимумы на заданном симплексе будут учтены. Как было сказано выше, для нашей задачи каждый локальный максимум соответствует визуальному образу, то он должен обладать двумя свойствами:
    1. Свойство локальности. Особые точки одного визуального образа лежат в некоторой небольшой окрестности, поэтому нам необходимо инициализировать x(1) только в окрестности каждой вершины ДГС.
    2. Свойство непересечения. Различные визуальные образы, как правило, не содержат общих вершин в G, а это значит, что если два локальных максимума x и y соответствуют двум различным визуальным образам, то (x,y)~0.


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

    В конце необходимо восстановить визуальный образ для каждого локального максимума x. Т.к. xi представляет собой вероятность вхождения вершины i в визуальный образ x, мы можем выбирать только те вершины, чье вхождение в визуальный образ наиболее вероятно.

    Параметры алгоритма


    Как видно из приведенного выше описания, алгоритм имеет большое количество настраиваемых параметров таких, как:
    • Sci=f1(id, i'd) -функция оценки соответствия
    • Scicj(s)=f2(|lij — s*li'j'|) — функция оценки геометрической согласованности соответствий
    • Ε — пороговое значение для оценки веса ребра, на предмет принадлежности к окрестности инициализации
    • Φ — радиус окрестности для которой берется инициализация x(1)
    • Ψ — пороговое значение для оценки малости локального максимума
    • Ω — пороговое значение для слияния окрестностей
    • Θ — пороговое значение вероятности вхождения вершины в визуальный образ


    Эксперименты


    Типичные результаты работы алгоритма представлены ниже.



    Заключение


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

    Литература


    • Common Visual Pattern Discovery via Spatially Coherent Correspondences Hairong Liu, Shuicheng Yan, Departament of Electrical and Computer Enginering, National University of Singapore, Singapore
    • T. Motzkin and E. Straus. Maxima for graphs and a new proof of a theorem of Turan. Canad. J. Math, 1965.
    • 10. M. Pelillo, K. Siddiqi, and S. Zucker. Matching hierarchical structures using association graphs. TPAMI, 1999.


    UPD Ссылка на исходники метода: dl.dropbox.com/u/15642384/src.7z
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 23

      +2
      Зачем же такое на ночь выкладывать, когда мозг бездействует (
        +7
        Больше бы таких статей
          +5
          Хотелось бы видеть в таких статьях еще и коды реализации алгоритма, поскольку мне, например, немногое понятно из всех этих формул.
            0
            Добавил в конец статьи ссылку на исходник метода. Правда код написан грязновато, т.к. писался исключительно чтобы поиграться и попробовать какие-то идеи и не предполагалось его дальнейшего использования.
          +1
          Интересно, спасибо! А не могли бы вы добавить статью в топик «Обработка изображений» — прям по теме.
            0
            Спасибо за совет, добавил в «Обработку изображений».
            +4
            я пошел нажрусь
              +1
              Это для проверки алгоритма на себе?
              Гм… достаточно сложные условия ты ему ставишь, думаешь сможешь продержаться и одновременно подобрать параметры чтобы он правильно срабатывал?
                0
                уважаемый, зачем все усложняешь. жизнь прекрасна!
              –1
              Не планируете исходники на GitHub или еще на какой-нибудь хостинг исходного кода выложить?
                +1
                А смысл захламлять GitHub? исходник ничем вообщем-то не примечателен…
                0
                Очень интересно! А есть ли идеи, как выбирать «много начальных инициализаций»?
                  0
                  И могут ли в множестве M быть соответствия (i,i'), (j,j'), в которых i=j или i'=j'? Не помешает ли это алгоритму?
                    0
                    Много начальных инициализаций на практике обеспечиваются за счет того, что берется инициализация для окрестности каждого соответствия, этого вполне хвататет.
                    Ситуация когда i'=j' вполне допустима, это будет означать что одно из соответствий (i,;i'),(j,j') является выбросом, либо оба сразу. По построению матрицы смежности предполагается, что высокий вес выбросов в кластере минимизирует квадратичную форму, поэтому при движении по траекториям уравнения самосборки, вес таких соответствий уменьшается, а значит уменьшается вероятность их вхождения в визуальный образ. Потом их вероятность либо зануляется, либо отбрасываем лишнее по пороговому значению.
                    Случай когда i=j мы можем контролировать т.к. сами выбираем способ построения множества M, я такой случай не рассматривал, но теоретически он особо не отличается от того что я описал выше.
                      0
                      «Случай, когда i=j, мы можем контролировать» — что имеется в виду? Что мы для каждой точки одной картинки зададим не более одного соответствия? Но тогда, если у нас много близких сигнатур, мы проиграем, потому что шансов угадать точку правильно почти нет.
                      У меня похожая задача, только у точек дескрипторов нет вообще, зато масштабный коэффициент всегда равен 1. Для меры соответствия я сравниваю множества расстояний от каждой из точки a_i, b_i' до других точек этого множества, потом выбираю какую-нибудь точку a_i, для которой наилучшее соответствие дает ровно одна точка b_i' (т.е. для остальных b_j' соответствие будет намного хуже), закрепляю это соответствие и в дальнейшем поиске учитываю расстояния от рассматриваемых точек до a_i и b_i' соответственно. Срабатывает почти всегда, но если хоть раз программа угадает неправильно, то задача не будет решена. Сейчас думаю воспользоваться методом, похожим на ваш, но возникает вопрос, сколько соответствий добавлять в множество M. Если все, то время работы будет порядка N^4, что неприемлемо (у меня число точек в множествах примерно 200). Если взять sqrt(N) наилучших соответствий для каждой точки, то можно ограничиться временем N^3, но не уверен, сойдется ли поиск…
                        0
                        Да, конкретно в этом случае я использую только одно соответствие для каждой ОТ с эталонного изображения. Его строго говоря мы не угадываем, а берем лучшее среди всех соответствий для каждой точки. Очевидно, что такой подход не гарантирует нахождения всех возможных правильных соответствий между изображениями, но при достаточном количестве особых точек это не так критично.
                        Насчет того сколько брать точек, этот алгоритм у меня за приемлемое время(не real-time) обрабатывал где-то порядка 1500-2000 соответствий, на 10000+ соответствий не хватало памяти ноутбука. Вообще все зависит от конкретной задачи, а точнее от того какую оценку сверху можно дать количеству ложных соответствий.
                        0
                        Еще вопрос: «Инициализация для окрестности каждого соответствия» — это как? Этому соответствию ставим большую вероятность, а остальным маленькие? Маленькие — одинаковые или случайные? Насколько маленькие? Хватит ли отношения маленькой вероятности к большой 1:2, или лучше брать 1:N, или 1:sqrt(N)?
                        Кстати, локальный максимум достигается не в точке x, у которой некоторые координаты равны 0, а остальные одинаковы. Таким свойством обладает вектор Ax. Впрочем, на общий алгоритм это не влияет.
                          0
                          Окрестность для каждого соответствия (i, i') я инициализировал так:
                          1)для точки i на эталоне я находил все точки лежащие в радиусе Φ от неё.
                          2)затем для каждой точки j попавшей в этот радиус рассматривал её соответствие (j,j') и строил индикатор вектор размерности m: если вес ребра в ДГС между вершинами (i,i') и (j,j') был больше некоторого порогового значения Ε то добавлял это соответствие в кластер.

                          После чего строил индикатор вектор x(1) этого кластера, т.е x(1)d=1 если d-я вершина содержится в кластере, иначе x(1)d=0. И нормировал этот вектор. Вот этот нормированный вектор и брал за начальную инициализацию, соответственно вхождение всех вершин кластера в правильный визуальный образ полагается равновероятным с вероятностью x(1)i=1/k, где k-размерность кластера.

                          «Кстати, локальный максимум достигается не в точке x, у которой некоторые координаты равны 0, а остальные одинаковы. Таким свойством обладает вектор Ax.» //Не понял этой фразы. На вектор x в данном случае налагаются только два условия: он не выходит из окрестности инициализации и сумма компонент равна еденице, т.к. симплекс по норме l1.
                            0
                            Но тогда точки, не попавшие в Ф-окрестность, будут иметь начальную координату 0, и никогда ее не изменят, и в итоге в множество итоговых соответствий войдут только соответствия для этого кластера? Или результат собирается из результатов для разных кластеров?

                            Я говорил про эту фразу:

                            Проще говоря, в теореме говорится, что подмножество T вершин графа G является максимальной кликой тогда и только тогда, когда его характеристический вектор x_T является локальным максимумом квадратичной функции f(x) в стандартном симплексе, где x_iT = 1⁄|T| если i ∈ T, x_iT=0 иначе.

                            Для функции f(x)=x^t*A*x локальный максимум x обладает свойством, что A*x пропорционален характеристическому вектору какого-нибудь T.
                              0
                              Я создаю такой вектор для окрестности каждого соответствия, поэтому учитываются все и не по разу. Потом я объединяю кластеры относящиеся к одному визуальному образу.

                              Да, там пожалуй стоит уточнить, что x имеет такой вид в момент времени 1.
                    +1
                    Поправьте заголовок пожалуйста: «Фильтрация ложных соответствий между изображениями при помощи динамического графа соответствий»
                      0
                      Поправил. Спасибо за исправление!
                      +1
                      Как известно, теорема Моцкина-Штрауса устанавливает связь между максимальной кликой и локальным максимумом такой квадратичной формы.

                      image

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