CODEWITHSUNDEEP
matlabdistancevectorizationtemplate-matching
Yuval
Yuval

Reputation: 3433

Find closest matching distances for a set of points in a distance matrix in Matlab

I have a matrix of measured angles between M planes

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

I have a list of known angles between planes, which is an N-by-N matrix which I name rho. Here's is a subset of it (it's too large to display):

 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

My mission is to find the set of M planes whose angles in rho are nearest to the measured angles. For example, the measured angles for the planes shown above are relatively close to the known angles between planes 1, 2, 4 and 6.

Put differently, I need to find a set of points in a distance matrix (which uses cosine-related distances) which matches a set of distances I measured. This can also be thought of as matching a pattern to a mold.

In my problem, I have M=5 and N=415.

I really tried to get my head around it but have run out of time. So currently I'm using the simplest method: iterating over every possible combination of 3 planes but this is slow and currently written only for M=3. I then return a list of matching planes sorted by a matching score:

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

I have a feeling pdist2 might help but not sure how. I would appreciate any help in figuring this out.

Upvotes: 3

Views: 1330

Answers (1)

Gunther Struyf
Gunther Struyf

Reputation: 11168

There is http://www.mathworks.nl/help/matlab/ref/dsearchn.html for closest point search, but that requires same dimensionality. I think you have to bruteforce find it anyway because it's just a special problem.

Here's a way to bruteforce iterate over all unique combinations of the second matrix and calculate the score, after that you can find the one with the minimum 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,:);

The solution of your example actually is [1 2 3 4], so the upperleft part of B and not [1 2 4 6].

This would theoretically solve your problem, and I don't know how to make this algorithm any faster. But it will still be slow for large numbers. For example for your case of M=5 and N=415, there are 100 128 170 583 combinations of B which are a possible solution; just generating the selector indices is impossible in 32-bit because you can't address them all.

I think the real optimization here lies in cutting away some of the planes in the NxN matrix in a preceding filtering part.

Upvotes: 1

Related Questions