Matlab шаблон соответствия с использованием FFT

Question

Я борюсь с сопоставлением с шаблоном в области Фурье в Matlab. Вот мои изображения (автор RamalamaCreatures на DeviantArt):

Моя цель - поместить ограничивающий прямоугольник вокруг уха опоссума, как в этом примере (где я выполнил сопоставление с шаблоном с помощью normxcorr2):

Вот код Matlab, который я использую:

clear all; close all;

template = rgb2gray(imread('possum_ear.jpg'));
background = rgb2gray(imread('possum.jpg'));

%% calculate padding
bx = size(background, 2); 
by = size(background, 1);
tx = size(template, 2); % used for bbox placement
ty = size(template, 1);

%% fft
c = real(ifft2(fft2(background) .* fft2(template, by, bx)));

%% find peak correlation
[max_c, imax]   = max(abs(c(:)));
[ypeak, xpeak] = find(c == max(c(:)));
figure; surf(c), shading flat; % plot correlation 

%% display best match
hFig = figure;
hAx  = axes;
position = [xpeak(1)-tx, ypeak(1)-ty, tx, ty];
imshow(background, 'Parent', hAx);
imrect(hAx, position);

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

Это поверхностный график корреляций для неудачного совпадения:

Надеюсь, вы можете помочь! Благодарю.

Answer 1

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

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

---

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

^{Источник: Википедия}

Ga а также Gb исходное изображение и шаблон в частотной области, а * является сопряженным. o это то, что известно как продукт Адамара или поэлементный продукт. Я также хотел бы отметить, что деление числителя и знаменателя этой дроби также поэлементно. Используя перекрестный спектр мощности, если вы найдете (x,y) Здесь местоположение, которое дает абсолютный максимальный отклик, это место, где шаблон должен находиться на фоновом изображении.

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

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

---

Я также изменил ваш код, чтобы читать изображения непосредственно из Stackru, чтобы он воспроизводился:

clear all; close all;

template = rgb2gray(imread('https://stackru.com/images/b66c51f099925cc618ca4b63a4e5ca445bf82201.jpg'));
background = rgb2gray(imread('https://stackru.com/images/c5accc99e93b8e9c47119cac0c23d763d17792f0.jpg'));

%% calculate padding
bx = size(background, 2); 
by = size(background, 1);
tx = size(template, 2); % used for bbox placement
ty = size(template, 1);

%% fft
%c = real(ifft2(fft2(background) .* fft2(template, by, bx)));

%// Change - Compute the cross power spectrum
Ga = fft2(background);
Gb = fft2(template, by, bx);
c = real(ifft2((Ga.*conj(Gb))./abs(Ga.*conj(Gb))));

%% find peak correlation
[max_c, imax]   = max(abs(c(:)));
[ypeak, xpeak] = find(c == max(c(:)));
figure; surf(c), shading flat; % plot correlation    

%% display best match
hFig = figure;
hAx  = axes;

%// New - no need to offset the coordinates anymore
%// xpeak and ypeak are already the top left corner of the matched window
position = [xpeak(1), ypeak(1), tx, ty];
imshow(background, 'Parent', hAx);
imrect(hAx, position);

С этим я получаю следующее изображение:

Я также получаю следующее при отображении поверхностного графика перекрестного спектра мощности:

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

---

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

Answer 2

Просто закончил тем, что реализовал то же самое с python с аналогичными идеями, что и @rayryeng, используя scipy.fftpack.fftn() / ifftn() функции со следующим результатом для тех же изображений цели и шаблона:

import numpy as np
import scipy.fftpack as fp
from skimage.io import imread
from skimage.color import rgb2gray, gray2rgb
import matplotlib.pylab as plt
from skimage.draw import rectangle_perimeter

im = 255*rgb2gray(imread('https://stackru.com/images/c5accc99e93b8e9c47119cac0c23d763d17792f0.jpg'))    # target
im_tm = 255*rgb2gray(imread('https://stackru.com/images/b66c51f099925cc618ca4b63a4e5ca445bf82201.jpg')) # template

# FFT 
F = fp.fftn(im)                   
F_tm = fp.fftn(im_tm, shape=im.shape)

# compute the best match location
F_cc = F * np.conj(F_tm)
c = (fp.ifftn(F_cc/np.abs(F_cc))).real
i, j = np.unravel_index(c.argmax(), c.shape)
print(i, j)
# 214 317

# draw rectangle around the best match location
im2 = (gray2rgb(im)).astype(np.uint8)
rr, cc = rectangle_perimeter((i,j), end=(i + im_tm.shape[0], j + im_tm.shape[1]), shape=im.shape)
for x in range(-2,2):
    for y in range(-2,2):
        im2[rr + x, cc + y] = (255,0,0)

# show the output image
plt.figure(figsize=(10,10))
plt.imshow(im2)
plt.axis('off')
plt.show()

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

Одно замечание: результат очень сильно зависит от схожести размера и формы объекта, который должен быть сопоставлен с шаблоном, если он сильно отличается от изображения шаблона, шаблон может вообще не совпадать.