Найти близкие расстояния, соответствующие набор точек на расстоянии матрицы в Matlab

Question

У меня есть матрица измеренных углов между плоскостями M

0 52 77 79 
52  0 10 14 
77 10  0  3 
79 14  3  0 

У меня есть список известных углов между плоскостями, который представляет собой N- by-N, которую я называю rho. Вот это подмножество (он слишком велик для отображения):

0 51 68 75 78 81 82 
51  0 17 24 28 30 32 
68 17  0  7 11 13 15 
75 24  7  0  4  6  8 
78 28 11  4  0  2  4 
81 30 13  6  2  0  2 
82 32 15  8  4  2  0 

Моя миссия состоит в том, чтобы найти множество М плоскостей, чьи углы в rho ближе всего к измеренным углам. Например, измеренные углы для плоскостей, показанных выше, относительно близки к известным углам между плоскостями 1, 2, 4 и 6.

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

В моей проблеме у меня есть M = 5 и N = 415.

Я действительно пытался обвести голову, но у меня закончилось время. Поэтому в настоящее время я использую простейший метод: итерацию по любой возможной комбинации из трех плоскостей, но это медленно и в настоящее время написано только для M = 3. Затем я возвращаюсь список соответствия самолетов, отсортированных по согласующему баллу:

function [scores] = which_zones(rho, angles) 
    N = size(rho,1); 
    scores = zeros(N^3, 4); 
    index = 1; 
    for i=1:N-2 
     for j=(i+1):N-1 
      for k=(j+1):N 
       found_angles = [rho(i,j) rho(i,k) rho(j,k)]; 
       score = sqrt(sum((found_angles-angles).^2)); 
       scores(index,:)=[score i j k]; 
       index = index + 1; 
      end 
     end; 
    end 
    scores=scores(1:(index-1),:); % was too lazy to pre-calculate # 
    scores=sortrows(scores, 1); 
end 

У меня есть ощущение pdist2 может помочь, но не знает, как. Я был бы признателен за любую помощь в этом.

Answer 1

Для поиска ближайшей точки существует http://www.mathworks.nl/help/matlab/ref/dsearchn.html, но для этого требуется такая же размерность. Я думаю, что вам все равно придется искать его, потому что это просто особая проблема.

Это способ перебора всех уникальных комбинаций второй матрицы и вычисления score, после чего вы можете найти тот, у которого минимальный балл.

A=[ 0 52 77 79; 
    52  0 10 14; 
    77 10  0  3; 
    79 14  3  0]; 
B=[ 0 51 68 75 78 81 82; 
    51  0 17 24 28 30 32; 
    68 17  0  7 11 13 15; 
    75 24  7  0  4  6  8; 
    78 28 11  4  0  2  4; 
    81 30 13  6  2  0  2; 
    82 32 15  8  4  2  0]; 

M = size(A,1); 
N = size(B,1); 

% find all unique permutations of `1:M` 
idx = nchoosek(1:N,M); 
K = size(idx,1); % number of combinations = valid candidates for matching A 

score = NaN(K,1); 
idx_triu = triu(true(M,M),1); 
Atriu = A(idx_triu); 

for ii=1:K 
    partB = B(idx(ii,:),idx(ii,:)); 
    partB_triu = partB(idx_triu); 
    score = norm(Atriu-partB_triu,2); 
end 

[~, best_match_idx] = min(score); 
best_match = idx(best_match_idx,:); 

Решение вашего примера на самом деле [1 2 3 4], поэтому часть левого верхнего B и не [1 2 4 6].

Это теоретически решит вашу проблему, и я не знаю, как сделать этот алгоритм быстрее. Но он будет медленным для больших чисел. Например, для вашего случая M=5 и N=415 есть 100 128 170 583 комбинации B, которые являются возможным решением; просто генерировать индексы селектора невозможно в 32-битном, потому что вы не можете адресовать их все.

Я думаю, что настоящая оптимизация заключается в том, чтобы отрезать некоторые плоскости в матрице NxN в предыдущей фильтрующей части.