Как работает сравнение / сопоставление изображений с kd-деревьями и поиск ближайшего соседа? - PullRequest
Новая
       49

Как работает сравнение / сопоставление изображений с kd-деревьями и поиск ближайшего соседа?

3 голосов
/ 18 апреля 2011

Я запрашивал у Google некоторые материалы о kd-деревьях и сравнении изображений, но я не смог сделать «связь» между техниками для сравнения изображений с использованием kd-деревьев. Сначала я нашел несколько статей, в которых говорилось об улучшении скорости с помощью рандомизированных kd-деревьев, затем я познакомился с SIFT. Поняв, в основном, как работает SIFT, я прочитал о поиске ближайшего соседа.

Мой реальный вопрос: если у меня есть сетка точек из SIFT, то я создаю kd-дерево для каждого изображения. Как поиск ближайшего соседа может помочь мне сравнить изображения? Сначала я подумал, что сравнение изображений с деревом будет работать с некоторым алгоритмом, проверяющим древовидную структуру и то, насколько близко каждая точка находится на изображении A от точки в том же узле и на изображении B.

Если вопрос слишком тупой, предложите материал или тему для поиска.

Спасибо!

Ответы [ 3 ]

8 голосов
/ 19 апреля 2011

Я бы предложил сначала понять медленное сопоставление объектов, без kdtrees.

  • ввод: 1000 опорных объектов, например, лиц или цветов; Назовите это F1 .. F1000
  • функция запроса Q: какая особенность лица или цветка больше всего похожа, ближайшая, Q?

Как вы знаете, SIFT уменьшает функцию изображения до 128 8-битных чисел, масштабируемых так, чтобы
сходство (функция F, функция Q) = Евклидово расстояние (SIFT (F), SIFT (Q)).

Самый простой способ узнать, какая из F1 .. F1000 больше всего похожа на Q это просто посмотреть на F1, F2 ... один за другим: 

# find the feature of F1 .. F1000 nearest Q
nearestdistance = infinity
nearestindex = 0
for j in 1 .. 1000:
    distance = Euclideandistance( SIFT(Fj), SIFT(Q) )  # 128 numbers vs. 128 numbers
    if distance < nearestdistance:
        nearestdistance = distance
        nearestindex = j

(Конечно, каждый вычисляет числа SIFT вне цикла.)

A Kdtree это просто способ быстро найти соседние векторы; это не имеет ничего общего с , с чем сопоставляется (векторы чисел, представляющих ...), или как (евклидово расстояние). Теперь kdtrees очень быстрые для 2d, 3d ... вплоть до 20d, но может быть не быстрее, чем линейное сканирование всех данных выше 20d. Так как же работает kdtree для функций в 128d? Основная хитрость - рано закончить поиск. Бумага Муджи и Лоу, Быстрые приблизительные ближайшие соседи с автоматической настройкой алгоритма , 2009, 10p, описывает несколько рандомизированных kdtrees для сопоставления 128d SIFT-функций. (Лоу является изобретателем SIFT.)

Чтобы сравнить два изображения I и Q, нужно найти набор векторов признаков - от нескольких сотен до нескольких тысяч SIFT-векторов - для каждого, и ищет близкие совпадения этих наборов. (Можно представить изображения как молекулы, особенности как атомы; почти совпадающие молекулы на намного тверже, чем почти совпадающие атомы но это помогает быстро сопоставлять атомы.)

Надеюсь, это поможет.

0 голосов
/ 13 февраля 2013

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

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

im = imread('image.jpg');

len = size(im,3);
if(len == 1)
    im = ind2rgb(im, colourMap);
    im = uint8(im.*255);
end

im(logical(  0 <= im & im <=  63)) = 0;
im(logical( 64 <= im & im <= 127)) = 1;
im(logical(128 <= im & im <= 191)) = 2;
im(logical(192 <= im & im <= 255)) = 3;
im = im(:,:,1) * 16 + im(:,:,2) * 4 + im(:,:,3);

imHist = histc(im(:),0:63);
0 голосов
/ 13 июля 2011

Если вы планируете использовать kd-деревья для приблизительного поиска NN в более высоких измерениях, вы можете просмотреть эксперименты здесь: http://zach.in.tu -clausthal.de / software / приблизительно_nn /

...