%This software implements the point matching algorithm described in the paper:
%"Rotation Invariant Nonrigid Point Set Matching in Cluttered Scenes", IEEE transaction on Image Processing, 2012

%Author: Wei Lian (Changzhi University, Changzhi, 046011, Shanxi Province, P.R. China, Email: lianwei3 at gmail.com)

%If you use this software for research purposes, you should cite the aforementioned paper in any resulting publications.


function ind=minSpanTree(X)
%X: Nx x 2, point set
%ind: Ne x 2, edges of minimum spanning tree
% [X,Y]=generate_point_set('fu2',2);

N=size(X,1);
dif=repmat(permute(X,[1,3,2]),[1,N,1])-repmat(permute(X,[3,1,2]),[N,1,1]);%%jj versus kk
%%length of difference vector for Y
len=sqrt(sum(dif.^2,3)); %N x N

indx=[];
indy=[];
weigh=[];
for ii=1:N-1
    for jj=ii+1:N
        indx=[indx,jj];
        indy=[indy,ii];
        weigh=[weigh,len(ii,jj)];
    end
end
graph=sparse(indx,indy,weigh);
graph(N,N)=0;
[ST,pred] = graphminspantree(graph);
[indx,indy]=find(ST);%edges of minimum spanning tree
ind=[indx,indy];
% figure;hold on;
% plot(X(:,1),X(:,2),'o');
% plot([X(indx,1)';X(indy,1)'],[X(indx,2)';X(indy,2)'],'-');
%%%%%%%%%%%%%%%%%%%%


% list=[1,tree2list(1,[indx,indy])];%sort tree into a list
% figure;
% plot(X(list,1),X(list,2),'-');
