Общий метод поиска подматрицы в матрице 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, а затем просто проверяет, соответствует ли подблок соответствующего размера totalsub.

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{:}] 

Благодаря Эйтан 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