0

I have 2 matrices A and B both of size Rows X 2 where Rows = m , n for A and B respectively. These m and n denote the points in the euclidean space.

The task I wish to perform is to match the maximum number of points from A and B ( assuming A has less number of points than B ) given the condition that the distance is less than a threshold d and each pair is unique.

I have seen this nearest point pairs but this won't work on my problem because for every point in A it select the minimum left in B. However it may happen that the first pair I picked from A and B was wrong leading to less number of matching pairs.

I am looking for a fast solution since both A and B consists of about 1000 points each. Again, some points will be left and I am aware that this would somehow lead to an exhaustive search.

I am looking for a solution where there is some sort of inbuilt functions in matlab or using data structures that can help whose matlab code is available such as kd-trees. As mentioned I have to find unique nearest matching points from B to A.

Community
  • 1
  • 1
user2230369
  • 19
  • 4

1 Answers1

0

You can use pdist2 to compute a pairwise distance between two pairs of observations (of different sizes). The final distance matrix will be an N x M matrix which you can probe for all values above the desired threshold. 

A = randn(1000, 2);
B = randn(500, 2);

D = pdist2(A, B, 'euclidean');  % euclidean distance

d = 0.5; % threshold
indexD = D > d;
pointsA = any(indexD, 2);
pointsB = any(indexD, 1);

The two vectors provide logical indexes to the points in A and B that have at least one match, defined by the minimum distance d, on the other. The resulting sets will be composed of the entire set of elements from matrix A (or B) with distance above d from any element of the other matrix B (or A).

You can also generalize to more than 2 dimensions or different distance metrics.

gevang
  • 4,994
  • 25
  • 33
  • I have a doubt regarding the code you wrote.... Will the pairings of A and B be unique ie once a point gets selected from B it does'nt repeat for further points in A ? – user2230369 Apr 01 '13 at 00:13
  • @user2230369 no, it will not give unique matchings. This will give you the entire set of matches between the two, with repetition of points. You did not specify uniqueness of match in the OP, although your references on kd-trees imply something along that direction. Consider revising the post to include that. – gevang Apr 01 '13 at 00:18
  • Sorry about that... Have revised the question – user2230369 Apr 01 '13 at 00:43