Thread Subject:

find nearest,closest value

Hi,
I have two vectors a & b and I want to look for closest value of vector b in vector a one by one. How to find it?

megha bhatt wrote:
> Hi,
> I have two vectors a & b and I want to look for closest value of
> vector b in vector a one by one. How to find it?

doc interp1

--

"megha bhatt" <mubhatt19@yahoo.co.in> wrote in message <gmf901$45e$1@fred.mathworks.com>...
> Hi,
> I have two vectors a & b and I want to look for closest value of vector b in vector a one by one. How to find it?

  I put your problem aside ten days ago to look at and temporarily forgot about it. Sorry for the delay. I interpret your question to mean that for each element of vector 'a' you seek the nearest element of 'b' in terms of absolute difference. The following assumes that 'a' and 'b' are row vectors and that all the elements of 'a' are finite. It obtains the two row vectors 'd' and 'ib' of the same length as 'a'. Each element of 'd' is the absolute difference between the corresponding element of 'a' and the nearest element of 'b'. Each element of 'ib' is the index with respect to the 'b' vector of that corresponding nearest 'b' element.

 m = size(a,1); n = size(b,1);
 [c,p] = sort([a,b]);
 q = 1:m+n; q(p) = q;
 t = cumsum(p>m);
 r = 1:n; r(t(q(m+1:m+n))) = r;
 s = t(q(1:m));
 id = r(max(s,1));
 iu = r(min(s+1,n));
 [d,it] = min([abs(a-b(id));abs(b(iu)-a)]);
 ib = id+(it-1).*(iu-id);

  It is possible to write a somewhat shorter for-loop code for this in which a search is made for each element of 'a' for the nearest element of 'b' using the 'min' function, but that would be an order m*n algorithm as opposed to the above order (m+n)*log(m+n) algorithm (due principally to the 'sort' operation on [a,b].) For large m and n, the sort method is therefore considerably faster.

Roger Stafford

m = size(a,2); n = size(b,2); ??

"Shaun" <s@s.com> wrote in message <gnanne$b6m$1@fred.mathworks.com>...
> m = size(a,2); n = size(b,2); ??

  You're quite right Shaun. It should be the way you have it written. I copied that line in haste at the last moment and made a mistake in doing so. I had tested this code snippet starting with defined m and n used in generating random 'a' and 'b' and almost left the creation of 'm' and 'n' out of the final version to be put in this thread. Thanks for pointing that out.

Roger Stafford

That's some amazing code, Roger. Thank you for contributing it. Is it a well-known algorithm, or did you figure it out?

What's the purpose of the following line:
   > r = 1:n; r(t(q(m+1:m+n))) = r;
I can't think of a case where it won't end up the same as just r=1:n;

Thank you.

This is brilliant code. Is there a simple way to extend it for comparison of vectors?

That is, given two matrices, A and B (where size(A,1) == size(B,1)), find the columns of B that have least (sum of) element-by-element absolute differences with each of the columns of A.

I'll have a think about it and post whatever I come up with (but it won't be anything like as elegant as the solution for scalars posted above).

"Harry Commin" <hmc05_remove_this_@ic.ac.uk> wrote in message <i8o734$a2d$1@fred.mathworks.com>...
> ......
> That is, given two matrices, A and B (where size(A,1) == size(B,1)), find the columns of B that have least (sum of) element-by-element absolute differences with each of the columns of A.
>
> I'll have a think about it and post whatever I come up with (but it won't be anything like as elegant as the solution for scalars posted above).
- - - - - - - -
  The following should solve your problem:

C = zeros(2,size(A,2));
for p = 1:size(A,2)
 [m,q] = min(sum(abs(bsxfun(@minus,B,A(:,p))),1));
 C(:,p) = [m;q];
end

In each column of C corresponding to a column of A the top element is equal to the least sum of absolute differences of that A column with the various columns of B and the bottom element is the corresponding B column index.

  Unfortunately this algorithm is order(size(A,2)*size(B,1)*size(B,2)). It has to do that many subtractions, absolute values, and additions. Therefore for large matrices it will be slow. I could not think of any analog to the sorting trick for single dimensional vectors which would reduce this.

Roger Stafford

Delaunay triangulation is usually the best method to find nearest vector

Look ate TRISEARCH(), DELAUNAY() on older Matlab version and TriScatteredInterp class on newer version.

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <i8p8t2$p4c$1@fred.mathworks.com>...
> Delaunay triangulation is usually the best method to find nearest vector
>
> Look ate TRISEARCH(), DELAUNAY() on older Matlab version and TriScatteredInterp class on newer version.
>
> Bruno
- - - - - - - - - - - -
  Hi, Bruno. That sounds like an excellent idea. However, the poster, Harry, stated a criterion that apparently amounts to an L1 metric, not L2. Are delaunay and TriScatteredInterp amenable to such a metric? The idea of having a circumscribed circle containing no data points sounds very L2 to me. Very likely he could be persuaded to switch to L2 if it results in better algorithm performance.

Roger Stafford

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <i8q3g8$o52$1@fred.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <i8p8t2$p4c$1@fred.mathworks.com>...
> > Delaunay triangulation is usually the best method to find nearest vector
> >
> > Look ate TRISEARCH(), DELAUNAY() on older Matlab version and TriScatteredInterp class on newer version.
> >
> > Bruno
> - - - - - - - - - - - -
> Hi, Bruno. That sounds like an excellent idea. However, the poster, Harry, stated a criterion that apparently amounts to an L1 metric, not L2. Are delaunay and TriScatteredInterp amenable to such a metric? The idea of having a circumscribed circle containing no data points sounds very L2 to me. Very likely he could be persuaded to switch to L2 if it results in better algorithm performance.
>
> Roger Stafford

Hi Roger, you are right, I did not read carefully. Matlab Delaunay supposes L2 metric (I don't think user is allowed to change). L1 Delaunay seems to be very nasty problem.

Bruno

Thinking about a little more, even if Delaunay can't be used directly to find L1-closest point,it is clearly the candidate points are the those who are connected with the L2-closest point by a (L2) Delaunay simplex. This property can be used to reduce the search by computing the L1 distance to few candidates points for a given input points.

Bruno

I still need to check whereas the criteria for candidate points works when the points outside the convex hull. But here is what I have in mind:

%% Data
ndim = 2;
nA = 1e2;
nB = 1e4;
A = randn(nA,ndim);
B = 1.2*(randn(nB,ndim));

% Engine: Find the nearest point in A to every point of B
fprintf('L1 nearest started...\n');
T = delaunayn(A);
L2nearest = dsearch(A(:,1),A(:,2),T,B(:,1),B(:,2));

% Delaunay's connectivity matrix
C = sparse([],[],[],nA,nA); % == 0
for j = 1:ndim+1
    C = C + sparse(repmat(T(:,j),1,ndim+1),T,1,nA,nA);
end
C = logical(C);

% Candidate matrix (nA x nB)
C = C(:,L2nearest);

% Compute L1 distances
[iA iB] = find(C);
l1 = sum(abs(A(iA,:)-B(iB,:)),2);
% We put the inverse of distance to discard zero-elements of sparse matrix
invL1 = sparse(iA,iB,1./l1,nA,nB);
% max 1/L1 reaches at where min L1 reaches!
[m L1nearest] = max(invL1, [], 1);
L1min = 1./m;
fprintf('L1 nearest done\n');

%%
fprintf('Graphic output...\n');
Color = lines(64);
ncl = size(Color,1);
figure(1);
clf;
hold on
for iB=1:nB
    k = L1nearest(iB);
    cl = Color(mod(k-1,ncl)+1,:);
    plot(B(iB,1),B(iB,2),'.','Color',cl);
end
for iA=1:nA
    k = iA;
    cl = Color(mod(k-1,ncl)+1,:);
    plot(A(iA,1),A(iA,2),'o','Color',cl);
end
axis equal
title('L1 nearest')

% Bruno

Sorry: The criteria I stated earlier is flawed, that means the closest L1 point can be even not connected to closest L2 point by any Delaunay simplex.

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <i8s483$i4a$1@fred.mathworks.com>...
> Sorry: The criteria I stated earlier is flawed, that means the closest L1 point can be even not connected to closest L2 point by any Delaunay simplex.
>
> Bruno

This is an interesting problem, similar to my present problem:
 Back to the original problem, yet, I do not only attempt to find the closest value from a to b, but also attempt to replace the closest value in a to that in b, and return the index of being replaced elements in a. Notice that if two elements in b corresponds to the same element in a as the common nearest value, then I may want to replace that value in a with the closest or most lefthandside nearest points in b.

For example,
a=[1, 2, 3, 4, 5, 6];
b=[2.1, 1.9, 3.2];
 Obviously, both 1.9 and 2.2 in b close to 2 in a, but I want to replace 2 with 1.9 as ,1.9 is the nearest point in the leftside of 2. Such that, I attempt to obtain the following new vector and index of elements being replaced:
new_a=[1, 1.9, 3.2, 4, 5, 6];
index_replaced_in_a=[2, 2, 3];

Could you guys figure out a way to do so in a general way? a,b can be vectors or arrays of coordinates set (not so important)...

Thank you very much!

Cheers,
Xiaodong

On Apr 30, 9:51 pm, "Xiaodong " <e20...@gmail.com> wrote:
> "Bruno Luong" <b.lu...@fogale.findmycountry> wrote in message <i8s483$i4...@fred.mathworks.com>...
> > Sorry: The criteria I stated earlier is flawed, that means the closest L1 point can be even not connected to closest L2 point by any Delaunay simplex.
>
> > Bruno
>
> This is an interesting problem, similar to my present problem:
>  Back to the original problem, yet, I do not only attempt to find the closest value from a to b, but also attempt to replace the closest value in a to that in b, and return the index of being replaced elements in a. Notice that if two elements in b corresponds to the same element in a as the common nearest value, then I may want to replace that value in a with the closest or most lefthandside nearest points in b.
>
> For example,
> a=[1, 2, 3, 4, 5, 6];
> b=[2.1, 1.9, 3.2];
>  Obviously, both 1.9 and 2.2 in b close to 2 in a, but I want to replace 2 with 1.9 as ,1.9 is the nearest point in the leftside of 2. Such that, I attempt to obtain the following new vector and index of elements being replaced:
> new_a=[1, 1.9, 3.2, 4, 5, 6];
> index_replaced_in_a=[2, 2, 3];
>
> Could you guys figure out a way to do so in a general way? a,b can be vectors or arrays of coordinates set (not so important)...
>
> Thank you very much!
>
> Cheers,
> Xiaodong

-----------------------------------
Why did the 3 also get replaced? Since the 3 got replaced by 3.2, why
didn't 4, 5, and 6 also get replaced by 3.2? Why didn't the 1 get
replaced by 1.9 also? 1.9 was the closest value in b to the 1 in a.
Is there some greatest difference, where you don't replace if the
difference is too great?

"Xiaodong" wrote in message <ipiea9$3vr$1@fred.mathworks.com>...
> This is an interesting problem, similar to my present problem:
> Back to the original problem, yet, I do not only attempt to find the closest value from a to b, but also attempt to replace the closest value in a to that in b, and return the index of being replaced elements in a. Notice that if two elements in b corresponds to the same element in a as the common nearest value, then I may want to replace that value in a with the closest or most lefthandside nearest points in b.
>
> For example,
> a=[1, 2, 3, 4, 5, 6];
> b=[2.1, 1.9, 3.2];
> Obviously, both 1.9 and 2.2 in b close to 2 in a, but I want to replace 2 with 1.9 as ,1.9 is the nearest point in the leftside of 2. Such that, I attempt to obtain the following new vector and index of elements being replaced:
> new_a=[1, 1.9, 3.2, 4, 5, 6];
> index_replaced_in_a=[2, 2, 3];
>
> Could you guys figure out a way to do so in a general way? a,b can be vectors or arrays of coordinates set (not so important)...
>
> Thank you very much!
>
> Cheers,
> Xiaodong
- - - - - - - - -
  To replace elements of vector 'a' by those closest in 'b' in the problem of the original posting (5 Feb 2009) in this thread, just do:

 a = b(ib);

using the 'ib' index derived in the code of 16 Feb 2009 (as corrected by Shaun) and I believe the index in 'ib' would be the index vector you speak of.

  However, this is not in agreement with your example where the above code would produce ib = [2,2,3,3,3,3] and new_a = [1.9,1.9,3.2,3.2,3.2,3.2]. Can you tell me by what logic you don't have all the elements of 'a' replaced by their closest elements of 'b'? You may be thinking of an altogether different problem but I don't quite know what that would be unless you are thinking only of values of 'a' that are bracketed on both sides by values in 'b'.

  At the moment I cannot say for sure how this two-year-old code chooses between two equally distant values in 'b'. I would have to study that code carefully. I have reason to believe it selects the first encountered, moving left-to-right, in 'b' among equal candidates, though in choosing between equally distant upper and lower values in 'b' it may give preference to the lower values.

Roger Stafford

  If I were writing that code today instead of two years ago I would probably prefer the simpler:

 [c,p] = sort(b);
 [~,ic] = histc(a,[-inf,(c(1:end-1)+c(2:end))/2,inf]);
 ib = p(ic);
 ab = b(ib);

where 'a' and 'b' are the original row vectors with 'ib' the indices of 'b' elements nearest to the 'a' elements and 'ab' the replacement for 'a' by these nearest 'b' elements.

Roger Stafford

ImageAnalyst <imageanalyst@mailinator.com> wrote in message <870e8259-6b66-46b9-a101-b1fdc568f271@j26g2000yqa.googlegroups.com>...
> On Apr 30, 9:51 pm, "Xiaodong " <e20...@gmail.com> wrote:
> > "Bruno Luong" <b.lu...@fogale.findmycountry> wrote in message <i8s483$i4...@fred.mathworks.com>...
> > > Sorry: The criteria I stated earlier is flawed, that means the closest L1 point can be even not connected to closest L2 point by any Delaunay simplex.
> >
> > > Bruno
> >
> > This is an interesting problem, similar to my present problem:
> >  Back to the original problem, yet, I do not only attempt to find the closest value from a to b, but also attempt to replace the closest value in a to that in b, and return the index of being replaced elements in a. Notice that if two elements in b corresponds to the same element in a as the common nearest value, then I may want to replace that value in a with the closest or most lefthandside nearest points in b.
> >
> > For example,
> > a=[1, 2, 3, 4, 5, 6];
> > b=[2.1, 1.9, 3.2];
> >  Obviously, both 1.9 and 2.2 in b close to 2 in a, but I want to replace 2 with 1.9 as ,1.9 is the nearest point in the leftside of 2. Such that, I attempt to obtain the following new vector and index of elements being replaced:
> > new_a=[1, 1.9, 3.2, 4, 5, 6];
> > index_replaced_in_a=[2, 2, 3];
> >
> > Could you guys figure out a way to do so in a general way? a,b can be vectors or arrays of coordinates set (not so important)...
> >
> > Thank you very much!
> >
> > Cheers,
> > Xiaodong
>
> -----------------------------------
> Why did the 3 also get replaced? Since the 3 got replaced by 3.2, why
> didn't 4, 5, and 6 also get replaced by 3.2? Why didn't the 1 get
> replaced by 1.9 also? 1.9 was the closest value in b to the 1 in a.
> Is there some greatest difference, where you don't replace if the
> difference is too great?

My problem may be a little different from the original one: I just want to replace one nearest element in a with one element in b. In a, 4, ,5, 6 are all close to 3.2, but 3 is the nearest element, so I only want to replace 3 with 3.2. This is my logic rule in this problem. In this way, your previous codes above is to be adjusted...

Thanks for your concern!
Cheers,
Xiaodong

"Roger Stafford" wrote in message <ipiqv9$cja$1@fred.mathworks.com>...
> "Xiaodong" wrote in message <ipiea9$3vr$1@fred.mathworks.com>...
> > This is an interesting problem, similar to my present problem:
> > Back to the original problem, yet, I do not only attempt to find the closest value from a to b, but also attempt to replace the closest value in a to that in b, and return the index of being replaced elements in a. Notice that if two elements in b corresponds to the same element in a as the common nearest value, then I may want to replace that value in a with the closest or most lefthandside nearest points in b.
> >
> > For example,
> > a=[1, 2, 3, 4, 5, 6];
> > b=[2.1, 1.9, 3.2];
> > Obviously, both 1.9 and 2.2 in b close to 2 in a, but I want to replace 2 with 1.9 as ,1.9 is the nearest point in the leftside of 2. Such that, I attempt to obtain the following new vector and index of elements being replaced:
> > new_a=[1, 1.9, 3.2, 4, 5, 6];
> > index_replaced_in_a=[2, 2, 3];
> >
> > Could you guys figure out a way to do so in a general way? a,b can be vectors or arrays of coordinates set (not so important)...
> >
> > Thank you very much!
> >
> > Cheers,
> > Xiaodong
> - - - - - - - - -
> To replace elements of vector 'a' by those closest in 'b' in the problem of the original posting (5 Feb 2009) in this thread, just do:
>
> a = b(ib);
>
> using the 'ib' index derived in the code of 16 Feb 2009 (as corrected by Shaun) and I believe the index in 'ib' would be the index vector you speak of.
>
> However, this is not in agreement with your example where the above code would produce ib = [2,2,3,3,3,3] and new_a = [1.9,1.9,3.2,3.2,3.2,3.2]. Can you tell me by what logic you don't have all the elements of 'a' replaced by their closest elements of 'b'? You may be thinking of an altogether different problem but I don't quite know what that would be unless you are thinking only of values of 'a' that are bracketed on both sides by values in 'b'.
>
> At the moment I cannot say for sure how this two-year-old code chooses between two equally distant values in 'b'. I would have to study that code carefully. I have reason to believe it selects the first encountered, moving left-to-right, in 'b' among equal candidates, though in choosing between equally distant upper and lower values in 'b' it may give preference to the lower values.
>
> Roger Stafford

Sorry for my uncompleted explanation.

My problem may be similar to a practical issue: taking time-domain sampling for instance, my sampling machine can sample wave magnitude data in a default time series a=[1,2,3,4,5,...] s. But this time series would miss some important peak values and broken lines in the sampled wavelet, which is found locating at b=[1.9, 2,1, 3.2, ...] s. So, I prefer to replace some sampling time series points in 'a' with the peak value time points in 'b', without changing the size of 'a' or repeating any elements in the series. Once I know the indices and values to be changed in 'a', I can update the time series of sampling operations easily. In this way, the sampled wave will have a much more analogical shape to what it should be.

I think your previous discussion on the original problem will be helpful, except for some small changes...

Should I start a new thread?

Xiaodong