在matlab矩陣中查找子矩陣的一般方法

Question

我正在尋找一種'較好'的方法來在較大的矩陣（任意數量的維度）中查找矩陣（模式）。

例子：

total = rand(3,4,5); 
sub = total(2:3,1:3,3:4); 

現在我想這樣的事情發生：

loc = matrixFind(total, sub) 

在這種情況下loc應該成爲[2 1 3]。

現在我只想找到一個單一點（如果存在）並且不擔心舍入問題。可以假定sub'適合'total。

---

這是我如何能做到這一點的3個維度，但它只是感覺像有一個更好的辦法：

total = rand(3,4,5); 
sub = total(2:3,1:3,3:4); 
loc = []; 
for x = 1:size(total,1)-size(sub,1)+1 
    for y = 1:size(total,2)-size(sub,2)+1 
     for z = 1:size(total,3)-size(sub,3)+1 
      block = total(x:x+size(sub,1)-1,y:y+size(sub,2)-1,z:z+size(sub,3)-1); 
      if isequal(sub,block) 
       loc = [x y z] 
      end 
     end 
    end 
end 

---

我希望能找到一個任意數量的可行的解決方案尺寸。

Answer 1

這是低性能，但（據稱）任意維函數。它使用find在total中創建潛在匹配位置的（線性）索引列表，然後檢查total的大小合適的子塊是否匹配sub。

function loc = matrixFind(total, sub) 
%matrixFind find position of array in another array 

    % initialize result 
    loc = []; 

    % pre-check: do all elements of sub exist in total? 
    elements_in_both = intersect(sub(:), total(:)); 
    if numel(elements_in_both) < numel(sub) 
     % if not, return nothing 
     return 
    end 

    % select a pivot element 
    % Improvement: use least common element in total for less iterations 
    pivot_element = sub(1); 

    % determine linear index of all occurences of pivot_elemnent in total 
    starting_positions = find(total == pivot_element); 

    % prepare cell arrays for variable length subscript vectors 
    [subscripts, subscript_ranges] = deal(cell([1, ndims(total)])); 


    for k = 1:length(starting_positions) 
     % fill subscript vector for starting position 
     [subscripts{:}] = ind2sub(size(total), starting_positions(k)); 

     % add offsets according to size of sub per dimension 
     for m = 1:length(subscripts) 
      subscript_ranges{m} = subscripts{m}:subscripts{m} + size(sub, m) - 1; 
     end 

     % is subblock of total equal to sub 
     if isequal(total(subscript_ranges{:}), sub) 
      loc = [loc; cell2mat(subscripts)]; %#ok<AGROW> 
     end 
    end 
end 

Answer 2

對於尺寸任意數量的，你可以嘗試convn。

C = convn(total,reshape(sub(end:-1:1),size(sub)),'valid'); % flip dimensions of sub to be correlation 
[~,indmax] = max(C(:)); 
% thanks to Eitan T for the next line 
cc = cell(1,ndims(total)); [cc{:}] = ind2sub(size(C),indmax); subs = [cc{:}] 

感謝Eitan T建議使用逗號分隔列表作爲廣義ind2sub。

最後，您應該使用isequal來測試結果，因爲這不是一個標準化的互相關，這意味着本地子區域中的較大數字會使可能給出誤報的相關值膨脹。如果您的total矩陣非常不均勻，且值大的區域，則可能需要在C中搜索其他最大值。

Answer 3

這是基於這樣的原矩陣total的所有可能的變化和移位total的左上角-等子矩陣與所尋求的圖案subs比較。班次使用字符串生成，並使用circshift應用。

大部分工作都是矢量化的。只使用一級循環。

該函數找到所有匹配，而不僅僅是第一個匹配。例如：

>> total = ones(3,4,5,6); 
>> sub = ones(3,3,5,6); 
>> matrixFind(total, sub) 
ans = 

    1  1  1  1 
    1  2  1  1 

下面是函數：

function sol = matrixFind(total, sub) 

nd = ndims(total); 
sizt = size(total).'; 
max_sizt = max(sizt); 
sizs = [ size(sub) ones(1,nd-ndims(sub)) ].'; % in case there are 
% trailing singletons 

if any(sizs>sizt) 
    error('Incorrect dimensions') 
end 

allowed_shift = (sizt-sizs); 
max_allowed_shift = max(allowed_shift); 
if max_allowed_shift>0 
    shifts = dec2base(0:(max_allowed_shift+1)^nd-1,max_allowed_shift+1).'-'0'; 
    filter = all(bsxfun(@le,shifts,allowed_shift)); 
    shifts = shifts(:,filter); % possible shifts of matrix "total", along 
    % all dimensions 
else 
    shifts = zeros(nd,1); 
end 

for dim = 1:nd 
    d{dim} = 1:sizt(dim); % vectors with subindices per dimension 
end 
g = cell(1,nd); 
[g{:}] = ndgrid(d{:}); % grid of subindices per dimension 
gc = cat(nd+1,g{:}); % concatenated grid 
accept = repmat(permute(sizs,[2:nd+1 1]), [sizt; 1]); % acceptable values 
% of subindices in order to compare with matrix "sub" 
ind_filter = find(all(gc<=accept,nd+1)); 

sol = []; 
for shift = shifts 
    total_shifted = circshift(total,-shift); 
    if all(total_shifted(ind_filter)==sub(:)) 
     sol = [ sol; shift.'+1 ]; 
    end 
end