使用 FFT 的 Matlab 模板匹配
Matlab Template Matching Using FFT
我正在为 Matlab 中傅立叶域中的模板匹配而苦苦挣扎。这是我的图片（艺术家是 DeviantArt 上的 RamalamaCreatures）：
我的目标是在负鼠的耳朵周围放置一个边界框，就像这个例子（我使用 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);
代码未按预期运行 - 它未识别正确的区域。这是失败的结果——错误的区域被框起来了：
这是失败匹配的相关性表面图：
希望对您有所帮助！谢谢。
您在代码中所做的实际上根本不是相关性。您正在使用模板并对输入图像执行卷积。回想一下傅立叶变换，两个信号的频谱相乘相当于两个信号在time/spatial域的卷积。
基本上，您正在做的是将模板用作内核并使用它来过滤图像。然后您会找到此输出的最大响应，这就是模板所在的位置。响应被装箱的地方是有意义的，因为该区域是完全白色的，并且使用模板作为具有完全白色区域的内核会给你一个非常大的响应，这就是为什么它很可能将该区域确定为最大回复。具体来说，该区域将有很多高值（~255 左右），并且自然地与模板补丁执行卷积，并且由于操作是加权和，该区域将为您提供非常大的输出。因此，如果您在图像的暗区使用模板，输出会很小 - 这是错误的，因为模板也由暗像素组成。
不过，您当然可以使用傅里叶变换来定位模板所在的位置，但我建议您改用Phase Correlation。基本上，您不是计算两个光谱的乘积，而是计算交叉功率谱。频域中两个信号之间的互功率谱R定义为：
来源：Wikipedia
Ga和Gb是原图和频域模板，*是共轭。 o 就是所谓的 Hadamard 积或元素级积。我还想指出，这个分数的分子和分母的除法也是按元素划分的。使用交叉功率谱，如果您在此处找到产生绝对最大响应的 (x,y) 位置，则模板应位于背景图像中的位置。
因此，您只需更改计算 "correlation" 的代码行，使其计算交叉功率谱。但是，我想指出一些非常重要的事情。当您执行 normxcorr2 时，相关性从图像的左上角开始。模板匹配从这个位置开始，并与 window 进行比较，window 是以左上角为原点的模板大小。查找模板匹配的位置时，位置是相对于匹配的左上角window。计算 normxcorr2 后，您通常会添加最大响应的一半行和一半列以找到 中心位置 .
因为我们或多或少都在做模板匹配（滑动windows、相关等）与FFT/频域相同的操作，当你在这个相关数组中找到峰值后，你也必须考虑到这一点。但是，无论如何，您调用 imrect 以在模板匹配的位置周围绘制一个矩形位于边界框的左上角，因此无需在此处进行偏移。因此，我们将略微修改该代码，但在稍后使用此代码时如果想要找到匹配的中心位置，请牢记偏移逻辑。
我也修改了您的代码以直接从 Whosebug 读取图像，以便它可以重现：
clear all; close all;
template = rgb2gray(imread('http://i.stack.imgur.com/6bTzT.jpg'));
background = rgb2gray(imread('http://i.stack.imgur.com/FXEy7.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);
这样，我得到了下图：
在显示交叉功率谱的表面图时，我还得到以下信息：
有一个清晰定义的峰值，其余输出的响应非常小。这实际上是一个 属性 的 Phase Correlation ，所以很明显，最大值的位置被明确定义，这就是模板所在的位置。
希望对您有所帮助！
刚刚用 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('http://i.stack.imgur.com/FXEy7.jpg')) # target
im_tm = 255*rgb2gray(imread('http://i.stack.imgur.com/6bTzT.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()
此外，下面的动画显示了在一组（目标）帧中定位一只鸟的模板图像时获得的结果，这些帧是从有一群鸟的视频中提取的。
需要注意一点：输出很大程度上取决于要与模板匹配的对象的大小和形状的相似性，如果与模板图像相差较大，则模板可能完全不匹配。
我正在为 Matlab 中傅立叶域中的模板匹配而苦苦挣扎。这是我的图片（艺术家是 DeviantArt 上的 RamalamaCreatures）：
我的目标是在负鼠的耳朵周围放置一个边界框，就像这个例子（我使用 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);
代码未按预期运行 - 它未识别正确的区域。这是失败的结果——错误的区域被框起来了：
这是失败匹配的相关性表面图：
希望对您有所帮助！谢谢。
您在代码中所做的实际上根本不是相关性。您正在使用模板并对输入图像执行卷积。回想一下傅立叶变换，两个信号的频谱相乘相当于两个信号在time/spatial域的卷积。
基本上，您正在做的是将模板用作内核并使用它来过滤图像。然后您会找到此输出的最大响应，这就是模板所在的位置。响应被装箱的地方是有意义的，因为该区域是完全白色的，并且使用模板作为具有完全白色区域的内核会给你一个非常大的响应，这就是为什么它很可能将该区域确定为最大回复。具体来说，该区域将有很多高值（~255 左右），并且自然地与模板补丁执行卷积，并且由于操作是加权和，该区域将为您提供非常大的输出。因此，如果您在图像的暗区使用模板，输出会很小 - 这是错误的，因为模板也由暗像素组成。
不过，您当然可以使用傅里叶变换来定位模板所在的位置，但我建议您改用Phase Correlation。基本上，您不是计算两个光谱的乘积，而是计算交叉功率谱。频域中两个信号之间的互功率谱R定义为：
来源：Wikipedia
Ga和Gb是原图和频域模板，*是共轭。 o 就是所谓的 Hadamard 积或元素级积。我还想指出，这个分数的分子和分母的除法也是按元素划分的。使用交叉功率谱，如果您在此处找到产生绝对最大响应的 (x,y) 位置，则模板应位于背景图像中的位置。
因此，您只需更改计算 "correlation" 的代码行，使其计算交叉功率谱。但是，我想指出一些非常重要的事情。当您执行 normxcorr2 时，相关性从图像的左上角开始。模板匹配从这个位置开始，并与 window 进行比较，window 是以左上角为原点的模板大小。查找模板匹配的位置时，位置是相对于匹配的左上角window。计算 normxcorr2 后，您通常会添加最大响应的一半行和一半列以找到 中心位置 .
因为我们或多或少都在做模板匹配（滑动windows、相关等）与FFT/频域相同的操作，当你在这个相关数组中找到峰值后，你也必须考虑到这一点。但是，无论如何，您调用 imrect 以在模板匹配的位置周围绘制一个矩形位于边界框的左上角，因此无需在此处进行偏移。因此，我们将略微修改该代码，但在稍后使用此代码时如果想要找到匹配的中心位置，请牢记偏移逻辑。
我也修改了您的代码以直接从 Whosebug 读取图像，以便它可以重现：
clear all; close all;
template = rgb2gray(imread('http://i.stack.imgur.com/6bTzT.jpg'));
background = rgb2gray(imread('http://i.stack.imgur.com/FXEy7.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);
这样，我得到了下图：
在显示交叉功率谱的表面图时，我还得到以下信息：
有一个清晰定义的峰值，其余输出的响应非常小。这实际上是一个 属性 的 Phase Correlation ，所以很明显，最大值的位置被明确定义，这就是模板所在的位置。
希望对您有所帮助！
刚刚用 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('http://i.stack.imgur.com/FXEy7.jpg')) # target
im_tm = 255*rgb2gray(imread('http://i.stack.imgur.com/6bTzT.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()
此外，下面的动画显示了在一组（目标）帧中定位一只鸟的模板图像时获得的结果，这些帧是从有一群鸟的视频中提取的。
需要注意一点：输出很大程度上取决于要与模板匹配的对象的大小和形状的相似性，如果与模板图像相差较大，则模板可能完全不匹配。