1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
% Consider matching sources to detections
% s1 d2
% s2 d3
% d1
%a = bipartiteMatchingHungarian([52;0.01])
% sources(:,i) = [x y] coords
sources = [0.1 0.7; 0.6 0.4]';
detections = [0.2 0.2; 0.2 0.8; 0.7 0.1]';
dst = sqdist(sources, detections);
% a = [2 3] which means s1-d2, s2-d3
a = bipartiteMatchingHungarian(dst);
a2 = bipartiteMatchingIntProg(dst);
assert(isequal(a(:),a2(:)))
figure(1); clf
bipartiteMatchingDemoPlot(sources, detections, a)
%%%% Flip roles of sources and detections
%dst = dst';
dst = sqdist(detections, sources);
% a = [0 1 2] which means d1-0, d2-s1, d3-s2
a = bipartiteMatchingHungarian(dst);
a2 = bipartiteMatchingIntProg(dst);
assert(isequal(a(:),a2(:)))
figure(2); clf
bipartiteMatchingDemoPlot(detections, sources, a) % swapped args
%%%%%%%%%% Move s1 nearer to d1
% d2
% s2 d3
% s1 d1
sources = [0.1 0.3; 0.6 0.4]';
detections = [0.2 0.2; 0.2 0.8; 0.7 0.1]';
dst = sqdist(sources, detections);
% a = [2 3] which means s1-d2, s2-d3
a = bipartiteMatchingHungarian(dst);
[a2, ass] = bipartiteMatchingIntProg(dst);
assert(isequal(a(:),a2(:)))
figure(3); clf
bipartiteMatchingDemoPlot(sources, detections, a)
%%%%%%%%%%
% Use random points
% Generate 2D data from a mixture of 2 Gaussians (from netlab demgmm1)
randn('state', 0); rand('state', 0);
gmix = gmm(2, 2, 'spherical');
ndat1 = 10; ndat2 = 10; ndata = ndat1+ndat2;
%gmix.centres = [0.3 0.3; 0.7 0.7];
%gmix.covars = [0.01 0.01];
gmix.centres = [0.5 0.5; 0.5 0.5];
gmix.covars = [0.1 0.01];
[x, label] = gmmsamp(gmix, ndata);
ndx = find(label==1);
sources = x(ndx,:)';
ndx = find(label==2);
detections = x(ndx,:)';
dst = sqdist(sources, detections);
[a, ass] = bipartiteMatchingIntProg(dst);
[a2] = bipartiteMatchingHungarian(dst);
assert(isequal(a(:), a2(:)))
figure(4); clf
bipartiteMatchingDemoPlot(sources, detections, a)
% only match 80% of points
p1 = size(sources, 2);
p2 = size(detections, 2);
nmatch = ceil(0.8*min(p1,p2));
a2 = bipartiteMatchingIntProg(dst, nmatch);
figure(5); clf
bipartiteMatchingDemoPlot(sources, detections, a2)
%%% swap roles
ndx = find(label==2);
sources = x(ndx,:)';
ndx = find(label==1);
detections = x(ndx,:)';
dst = sqdist(sources, detections);
% only match 80% of points
p1 = size(sources, 2);
p2 = size(detections, 2);
nmatch = ceil(0.8*min(p1,p2));
a2 = bipartiteMatchingIntProg(dst, nmatch);
figure(6); clf
bipartiteMatchingDemoPlot(sources, detections, a2)
|
