Comments 23
Зачем же такое на ночь выкладывать, когда мозг бездействует (
UFO just landed and posted this here
Интересно, спасибо! А не могли бы вы добавить статью в топик «Обработка изображений» — прям по теме.
я пошел нажрусь
Не планируете исходники на GitHub или еще на какой-нибудь хостинг исходного кода выложить?
Очень интересно! А есть ли идеи, как выбирать «много начальных инициализаций»?
И могут ли в множестве M быть соответствия (i,i'), (j,j'), в которых i=j или i'=j'? Не помешает ли это алгоритму?
Много начальных инициализаций на практике обеспечиваются за счет того, что берется инициализация для окрестности каждого соответствия, этого вполне хвататет.
Ситуация когда i'=j' вполне допустима, это будет означать что одно из соответствий (i,;i'),(j,j') является выбросом, либо оба сразу. По построению матрицы смежности предполагается, что высокий вес выбросов в кластере минимизирует квадратичную форму, поэтому при движении по траекториям уравнения самосборки, вес таких соответствий уменьшается, а значит уменьшается вероятность их вхождения в визуальный образ. Потом их вероятность либо зануляется, либо отбрасываем лишнее по пороговому значению.
Случай когда i=j мы можем контролировать т.к. сами выбираем способ построения множества M, я такой случай не рассматривал, но теоретически он особо не отличается от того что я описал выше.
Ситуация когда i'=j' вполне допустима, это будет означать что одно из соответствий (i,;i'),(j,j') является выбросом, либо оба сразу. По построению матрицы смежности предполагается, что высокий вес выбросов в кластере минимизирует квадратичную форму, поэтому при движении по траекториям уравнения самосборки, вес таких соответствий уменьшается, а значит уменьшается вероятность их вхождения в визуальный образ. Потом их вероятность либо зануляется, либо отбрасываем лишнее по пороговому значению.
Случай когда i=j мы можем контролировать т.к. сами выбираем способ построения множества M, я такой случай не рассматривал, но теоретически он особо не отличается от того что я описал выше.
«Случай, когда 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, но не уверен, сойдется ли поиск…
У меня похожая задача, только у точек дескрипторов нет вообще, зато масштабный коэффициент всегда равен 1. Для меры соответствия я сравниваю множества расстояний от каждой из точки a_i, b_i' до других точек этого множества, потом выбираю какую-нибудь точку a_i, для которой наилучшее соответствие дает ровно одна точка b_i' (т.е. для остальных b_j' соответствие будет намного хуже), закрепляю это соответствие и в дальнейшем поиске учитываю расстояния от рассматриваемых точек до a_i и b_i' соответственно. Срабатывает почти всегда, но если хоть раз программа угадает неправильно, то задача не будет решена. Сейчас думаю воспользоваться методом, похожим на ваш, но возникает вопрос, сколько соответствий добавлять в множество M. Если все, то время работы будет порядка N^4, что неприемлемо (у меня число точек в множествах примерно 200). Если взять sqrt(N) наилучших соответствий для каждой точки, то можно ограничиться временем N^3, но не уверен, сойдется ли поиск…
Да, конкретно в этом случае я использую только одно соответствие для каждой ОТ с эталонного изображения. Его строго говоря мы не угадываем, а берем лучшее среди всех соответствий для каждой точки. Очевидно, что такой подход не гарантирует нахождения всех возможных правильных соответствий между изображениями, но при достаточном количестве особых точек это не так критично.
Насчет того сколько брать точек, этот алгоритм у меня за приемлемое время(не real-time) обрабатывал где-то порядка 1500-2000 соответствий, на 10000+ соответствий не хватало памяти ноутбука. Вообще все зависит от конкретной задачи, а точнее от того какую оценку сверху можно дать количеству ложных соответствий.
Насчет того сколько брать точек, этот алгоритм у меня за приемлемое время(не real-time) обрабатывал где-то порядка 1500-2000 соответствий, на 10000+ соответствий не хватало памяти ноутбука. Вообще все зависит от конкретной задачи, а точнее от того какую оценку сверху можно дать количеству ложных соответствий.
Еще вопрос: «Инициализация для окрестности каждого соответствия» — это как? Этому соответствию ставим большую вероятность, а остальным маленькие? Маленькие — одинаковые или случайные? Насколько маленькие? Хватит ли отношения маленькой вероятности к большой 1:2, или лучше брать 1:N, или 1:sqrt(N)?
Кстати, локальный максимум достигается не в точке x, у которой некоторые координаты равны 0, а остальные одинаковы. Таким свойством обладает вектор Ax. Впрочем, на общий алгоритм это не влияет.
Кстати, локальный максимум достигается не в точке x, у которой некоторые координаты равны 0, а остальные одинаковы. Таким свойством обладает вектор Ax. Впрочем, на общий алгоритм это не влияет.
Окрестность для каждого соответствия (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.
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, и никогда ее не изменят, и в итоге в множество итоговых соответствий войдут только соответствия для этого кластера? Или результат собирается из результатов для разных кластеров?
Я говорил про эту фразу:
Проще говоря, в теореме говорится, что подмножество 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.
Я говорил про эту фразу:
Проще говоря, в теореме говорится, что подмножество 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.
Поправьте заголовок пожалуйста: «Фильтрация ложных соответствий между изображениями при помощи динамического графа соответствий»
Как известно, теорема Моцкина-Штрауса устанавливает связь между максимальной кликой и локальным максимумом такой квадратичной формы.
Sign up to leave a comment.
Фильтрация ложных соответствий между изображениями при помощи динамического графа соответствий