|
wolffd@0
|
1 function [a,ass] = bipartiteMatchingIntProg(dst, nmatches)
|
|
wolffd@0
|
2 % BIPARTITEMATCHINGINTPROG Use binary integer programming (linear objective) to solve for optimal linear assignment
|
|
wolffd@0
|
3 % function a = bipartiteMatchingIntProg(dst)
|
|
wolffd@0
|
4 % a(i) = best matching column for row i
|
|
wolffd@0
|
5 %
|
|
wolffd@0
|
6 % This gives the same result as bipartiteMatchingHungarian.
|
|
wolffd@0
|
7 %
|
|
wolffd@0
|
8 % function a = bibpartiteMatchingIntProg(dst, nmatches)
|
|
wolffd@0
|
9 % only matches the specified number (must be <= min(size(dst))).
|
|
wolffd@0
|
10 % This can be used to allow outliers in both source and target.
|
|
wolffd@0
|
11 %
|
|
wolffd@0
|
12 % For details, see Marciel & Costeira, "A global solution to sparse correspondence
|
|
wolffd@0
|
13 % problems", PAMI 25(2), 2003
|
|
wolffd@0
|
14
|
|
wolffd@0
|
15 if nargin < 2, nmatches = []; end
|
|
wolffd@0
|
16
|
|
wolffd@0
|
17 [p1 p2] = size(dst);
|
|
wolffd@0
|
18 p1orig = p1; p2orig = p2;
|
|
wolffd@0
|
19 dstorig = dst;
|
|
wolffd@0
|
20
|
|
wolffd@0
|
21 if isempty(nmatches) % no outliers allowed (modulo size difference)
|
|
wolffd@0
|
22 % ensure matrix is square
|
|
wolffd@0
|
23 m = max(dst(:));
|
|
wolffd@0
|
24 if p1<p2
|
|
wolffd@0
|
25 dst = [dst; m*ones(p2-p1, p2)];
|
|
wolffd@0
|
26 elseif p1>p2
|
|
wolffd@0
|
27 dst = [dst m*ones(p1, p1-p2)];
|
|
wolffd@0
|
28 end
|
|
wolffd@0
|
29 end
|
|
wolffd@0
|
30 [p1 p2] = size(dst);
|
|
wolffd@0
|
31
|
|
wolffd@0
|
32
|
|
wolffd@0
|
33 c = dst(:); % vectorize cost matrix
|
|
wolffd@0
|
34
|
|
wolffd@0
|
35 % row-sum: ensure each column sums to 1
|
|
wolffd@0
|
36 A2 = kron(eye(p2), ones(1,p1));
|
|
wolffd@0
|
37 b2 = ones(p2,1);
|
|
wolffd@0
|
38
|
|
wolffd@0
|
39 % col-sum: ensure each row sums to 1
|
|
wolffd@0
|
40 A3 = kron(ones(1,p2), eye(p1));
|
|
wolffd@0
|
41 b3 = ones(p1,1);
|
|
wolffd@0
|
42
|
|
wolffd@0
|
43 if isempty(nmatches)
|
|
wolffd@0
|
44 % enforce doubly stochastic
|
|
wolffd@0
|
45 A = [A2; A3];
|
|
wolffd@0
|
46 b = [b2; b3];
|
|
wolffd@0
|
47 Aineq = zeros(1, p1*p2);
|
|
wolffd@0
|
48 bineq = 0;
|
|
wolffd@0
|
49 else
|
|
wolffd@0
|
50 nmatches = min([nmatches, p1, p2]);
|
|
wolffd@0
|
51 Aineq = [A2; A3];
|
|
wolffd@0
|
52 bineq = [b2; b3]; % row and col sums <= 1
|
|
wolffd@0
|
53 A = ones(1,p1*p2);
|
|
wolffd@0
|
54 b = nmatches; % total num matches = b (otherwise get degenerate soln)
|
|
wolffd@0
|
55 end
|
|
wolffd@0
|
56
|
|
wolffd@0
|
57
|
|
wolffd@0
|
58 ass = bintprog(c, Aineq, bineq, A, b);
|
|
wolffd@0
|
59 ass = reshape(ass, p1, p2);
|
|
wolffd@0
|
60
|
|
wolffd@0
|
61 a = zeros(1, p1orig);
|
|
wolffd@0
|
62 for i=1:p1orig
|
|
wolffd@0
|
63 ndx = find(ass(i,:)==1);
|
|
wolffd@0
|
64 if ~isempty(ndx) & (ndx <= p2orig)
|
|
wolffd@0
|
65 a(i) = ndx;
|
|
wolffd@0
|
66 end
|
|
wolffd@0
|
67 end
|
|
wolffd@0
|
68
|
|
wolffd@0
|
69
|
