在大矩阵中搜索矩阵的一部分最快的方法是什么？

Question

假设你有这个矩阵

X = randn(100, 100);

你把这部分剪掉了

% Windows 95
m = randi(95, 1)
n = randi(95, 1)
x = X(m:m+5, n:n+5);

问题：

在现实世界中，认为可以有一个用于扫描的滑动窗口，其中

x

可以放入

X

并检查最小误差，这是非常天真的。

smallest = inf;
for i = 1:95
  for j = 1:95
    % Extract candidate 
    candidate = X(i:i+5, j:j+5);
    
    % Compare 
    difference = abs(candidate - x);
    
    % Find error 
    error = sum(difference(:));
    if(error < smallest)
      smallest = error;
      index_i = i;
      index_j = j;
    end 
  end
end

fprintf('The smallest error was %f and it was located at %i, %i', smallest, index_i, index_j);

这段代码的一小部分是：

>> m = randi(95, 1)
  m = 21
>> n = randi(95, 1)
  n = 71
>> x = X(m:m+5, n:n+5);
>> The smallest error was 0.000000 and it was located at 21, 71

我想找到可能适合

x

的

X

候选者，但我不知道应该使用哪种算法。

这个问题的目的是我将对图像进行非常基本的地标检测。就像下面这张图一样。

通常，神经网络用于地标检测，但我没有那么多数据来训练神经网络。所以我需要依靠其他方法。我应该使用哪种方法？

Answer 1

这将通过卷积来完成，我认为您已经知道，因为您使用了卷积标签。在 Matlab 中，最好使用

normxcorr2

来完成。这是一些代码的示例：

% Set dimensions
Nx = 1000;
Ny = 1000;
SmallNx = 20;

% Generate matrix
X = rand([Nx Ny]);

% Region of interest
xi = randi(Nx - SmallNx);
yi = randi(Ny - SmallNx);
SmallX = X(xi:xi+SmallNx, yi:yi+SmallNx);

% Convolution
ConvX = normxcorr2(SmallX, X);

% Find convolution peak, correct for padding
[xi_est, yi_est] = find(ConvX == max(max(ConvX)));
xi_est = xi_est - SmallNx;
yi_est = yi_est - SmallNx;

为了更直观的示例，您可以使用图像：

% Load image
load Mandrill;
Nx = size(X, 1);
Ny = size(X, 2);
SmallNx = 100;

% Region of interest
xi = randi(Nx - SmallNx);
yi = randi(Ny - SmallNx);
SmallX = X(xi:xi+SmallNx, yi:yi+SmallNx);

% Convolution
ConvX = normxcorr2(SmallX, X);

% Find convolution peak, correct for padding
[xi_est, yi_est] = find(ConvX == max(max(ConvX)));
xi_est = xi_est - SmallNx;
yi_est = yi_est - SmallNx;

figure; 
subplot(1,2,1);
imagesc(X);
colormap gray;
hold on
rectangle('Position', [yi_est xi_est SmallNx SmallNx], 'EdgeColor','r')
subplot(1,2,2);
imagesc(SmallX);
colormap gray;