comparison toolboxes/FullBNT-1.0.7/KPMtools/bipartiteMatchingIntProg.m @ 0:e9a9cd732c1e tip

first hg version after svn

+function [a,ass] = bipartiteMatchingIntProg(dst, nmatches)
+% BIPARTITEMATCHINGINTPROG Use binary integer programming (linear objective) to solve for optimal linear assignment
+% function a = bipartiteMatchingIntProg(dst)
+% a(i) = best matching column for row i
+% 
+% This gives the same result as bipartiteMatchingHungarian.
+%
+% function a = bibpartiteMatchingIntProg(dst, nmatches)
+% only matches the specified number (must be <= min(size(dst))).
+% This can be used to allow outliers in both source and target.
+%
+% For details, see Marciel & Costeira, "A global solution to sparse correspondence
+% problems", PAMI 25(2), 2003
+
+if nargin < 2, nmatches = []; end
+
+[p1 p2] = size(dst);
+p1orig = p1; p2orig = p2;
+dstorig = dst;
+
+if isempty(nmatches) % no outliers allowed  (modulo size difference)
+  % ensure matrix is square
+  m = max(dst(:));
+  if p1<p2
+    dst = [dst; m*ones(p2-p1, p2)];
+  elseif p1>p2
+    dst = [dst  m*ones(p1, p1-p2)];
+  end
+end
+[p1 p2] = size(dst);
+
+
+c = dst(:); % vectorize cost matrix
+
+% row-sum: ensure each column sums to 1
+A2 = kron(eye(p2), ones(1,p1));
+b2 = ones(p2,1);
+
+% col-sum: ensure each row sums to 1
+A3 = kron(ones(1,p2), eye(p1));
+b3 = ones(p1,1);
+
+if isempty(nmatches)
+  % enforce doubly  stochastic
+  A = [A2; A3];
+  b = [b2; b3];
+  Aineq = zeros(1, p1*p2);
+  bineq = 0;
+else
+  nmatches = min([nmatches, p1, p2]);
+  Aineq = [A2; A3];
+  bineq = [b2; b3]; % row and col sums <= 1
+  A = ones(1,p1*p2);
+  b = nmatches; % total num matches = b (otherwise get degenerate soln)
+end
+
+
+ass = bintprog(c, Aineq, bineq, A, b);
+ass = reshape(ass, p1, p2);
+
+a = zeros(1, p1orig);
+for i=1:p1orig
+  ndx = find(ass(i,:)==1);
+  if ~isempty(ndx) & (ndx <= p2orig)
+    a(i) = ndx;
+  end
+end
+
+