7 files changed, 703 insertions, 0 deletions

diff --git a/SD-VBS/common/toolbox/toolbox_basic/matching/pub/contrib/v5/optim/assignprob/Contents.m b/SD-VBS/common/toolbox/toolbox_basic/matching/pub/contrib/v5/optim/assignprob/Contents.m
new file mode 100755
index 0000000..3ddb232
--- /dev/null
+++ b/SD-VBS/common/toolbox/toolbox_basic/matching/pub/contrib/v5/optim/assignprob/Contents.m
@@ -0,0 +1,26 @@
+%Functions related to the assignment problem.
+%Version 1.0, 25-May-1999.
+%
+%Copyright (c) 1995-1999 Niclas Borlin, Dept. of Computing Science, 
+%                        Umea University, SE-901 87 UMEA, Sweden.
+%                        Niclas.Borlin@cs.umu.se. 
+%                        www.cs.umu.se/~niclas.
+%
+%All standard disclaimers apply.
+%
+%You are free to use this code as you wish.  If you use it for a
+%publication or in a commercial package, please include an
+%acknowledgement and/or at least send me an email. (Looks good in my CV :-).
+%
+%Main functions:
+%   hungarian - calculate a solution of the square assignment
+%               problem. See HELP for a reference.
+%   condass   - calculate a condition number of the solution to the
+%               assignment problem. See HELP for a reference.
+%   allcosts  - calculate the costs of all possible assignments.
+%   allperms  - calculate all possible permutations/assignments of a
+%               given problem size.
+%
+%Test/demo functions.
+%   demo      - short demonstration of the main functions.
+%   test      - test/verification of the main functions.
diff --git a/SD-VBS/common/toolbox/toolbox_basic/matching/pub/contrib/v5/optim/assignprob/allcosts.m b/SD-VBS/common/toolbox/toolbox_basic/matching/pub/contrib/v5/optim/assignprob/allcosts.m
new file mode 100755
index 0000000..ffdb8b9
--- /dev/null
+++ b/SD-VBS/common/toolbox/toolbox_basic/matching/pub/contrib/v5/optim/assignprob/allcosts.m
@@ -0,0 +1,17 @@
+function [c,p]=allcosts(C)
+%ALLCOSTS Calculate all costs for an assignment problem.
+%
+%[c,p]=allcosts(C)
+%c returns the costs, p the corresponding permutations.
+
+% v1.0  95-07-18. Niclas Borlin, niclas@cs.umu.se.
+
+p=allperm(size(C,1));
+
+c=zeros(size(p,1),1);
+
+I=eye(size(C,1));
+
+for i=1:size(p,1)
+        c(i)=sum(C(logical(sparse(p(i,:),1:size(C,1),1))));
+end
diff --git a/SD-VBS/common/toolbox/toolbox_basic/matching/pub/contrib/v5/optim/assignprob/allperm.m b/SD-VBS/common/toolbox/toolbox_basic/matching/pub/contrib/v5/optim/assignprob/allperm.m
new file mode 100755
index 0000000..b8d419e
--- /dev/null
+++ b/SD-VBS/common/toolbox/toolbox_basic/matching/pub/contrib/v5/optim/assignprob/allperm.m
@@ -0,0 +1,17 @@
+function p=allperm(n)
+%ALLPERM All permutation matrix.
+%
+%p=allperm(n)
+%Returns a matrix with all permutations of 1:n stored row-wise.
+
+% v1.0  95-07-18. Niclas Borlin, niclas@cs.umu.se.
+
+if (n<=1)
+        p=1;
+else
+        q=allperm(n-1);
+        p=[];
+        for i=1:n
+                p=[p;i*ones(size(q,1),1) q+(q>=i)];
+        end
+end
diff --git a/SD-VBS/common/toolbox/toolbox_basic/matching/pub/contrib/v5/optim/assignprob/condass.m b/SD-VBS/common/toolbox/toolbox_basic/matching/pub/contrib/v5/optim/assignprob/condass.m
new file mode 100755
index 0000000..82552e7
--- /dev/null
+++ b/SD-VBS/common/toolbox/toolbox_basic/matching/pub/contrib/v5/optim/assignprob/condass.m
@@ -0,0 +1,54 @@
+function [k,C1,T1,C2,T2]=condass(A)
+%CONDASS Calculate condition number of the assigment problem.
+%
+%[k,C1,T1,C2,T2]=condass(A)
+%A  - A square cost matrix.
+%k  - The condition number of the assigment problem.
+%C1 - The best assigment.
+%T1 - The lowest cost.
+%C2 - The second best assignment.
+%T2 - The second lowest cost.
+%
+%The condition number is calculated as the relative difference between
+%the best and second best solutions, as described in Nystrom, Soderkvist,
+%and Wedin, "A Note on some Identification Problems Arising in Roentgen
+%Stereo Photogrammetric Analysis", J of Biomechanics, 27(10):1291-1294,
+%1994.
+
+% v1.0  96-09-14. Niclas Borlin, niclas@cs.umu.se.
+
+% A substantial effort was put into this code. If you use it for a
+% publication or otherwise, please include an acknowledgement and notify
+% me by email. /Niclas
+
+% Create a large number used to block selected assignments.
+big=sum(sum(A))+1;
+
+% Get best assigment.
+[C1,T1]=hungarian(A);
+
+% Initialize second best solution.
+T2=inf;
+C2=zeros(size(C1));
+
+% Create a work matrix.
+B=A;
+for i=1:length(C1)
+    % Block assigment in column i.
+    B(C1(i),i)=big;
+    % Get best assigment with this one blocked.
+    [C,T]=hungarian(B);
+    if (T<T2)
+                % Remember it if it's the best so far.
+                T2=T;
+                C2=C;
+    end
+    % Remove blocking in column i.
+    B(C1(i),i)=A(C1(i),i);
+end
+
+% Calculate difference...
+mu=T2-T1;
+
+% ...and condition number.
+k=T1/mu;
diff --git a/SD-VBS/common/toolbox/toolbox_basic/matching/pub/contrib/v5/optim/assignprob/demo.m b/SD-VBS/common/toolbox/toolbox_basic/matching/pub/contrib/v5/optim/assignprob/demo.m
new file mode 100755
index 0000000..2d34e37
--- /dev/null
+++ b/SD-VBS/common/toolbox/toolbox_basic/matching/pub/contrib/v5/optim/assignprob/demo.m
@@ -0,0 +1,38 @@
+A=magic(10);
+B=A(4:7,4:7);
+disp('Cost matrix:')
+disp(B)
+disp('Calculating best assignment...');
+[c,t]=hungarian(B);
+disp('Best assignment (as row indices):')
+disp(c)
+disp('Best assignment (as logical matrix):')
+disp(logical(full(sparse(c,1:4,1))))
+disp('Lowest cost:')
+disp(t)
+
+disp(sprintf('\nCalculating condition number for solution...'));
+[k,c1,t1,c2,t2]=condass(B);
+disp('Lowest cost (should be same as above): ')
+disp(t1)
+disp('corresponding assignment (should be same as above):')
+disp(c1)
+disp('Second lowest cost: ')
+disp(t2)
+disp('corresponding assignment:')
+disp(c2)
+disp('Condition number for solution:')
+disp(k)
+
+disp(sprintf('\nCalculating all possible costs...'));
+[c,p]=allcosts(B);
+% Sort by cost.
+[y,i]=sort(c);
+disp('The three lowest costs:')
+disp(c(i(1:3)))
+disp('Corresponding assignments:')
+disp(p(i(1:3),:))
+disp('The three highest costs:')
+disp(c(i(end+[-2:0])))
+disp('Corresponding assignments:')
+disp(p(i(end+[-2:0]),:))
diff --git a/SD-VBS/comm