kwarray.algo_assignment
¶
A convinient interface to solving assignment problems with the Hungarian algorithm (also known as Munkres or maximum linear-sum-assignment).
The core implementation of munkres in in scipy. Recent versions are written in C, so their speed should be reflected here.
Todo
[ ] Implement linear-time maximum weight matching approximation algorithm from this paper: https://web.eecs.umich.edu/~pettie/papers/ApproxMWM-JACM.pdf
Module Contents¶
Functions¶
|
Finds minimum cost assignment between two sets of D dimensional vectors. |
|
Finds the minimum cost assignment based on a NxM cost matrix, subject to |
|
Finds the maximum value assignment based on a NxM value matrix. Any pair |
- kwarray.algo_assignment.mindist_assignment(vecs1, vecs2, p=2)¶
Finds minimum cost assignment between two sets of D dimensional vectors.
- Parameters
vecs1 (np.ndarray) – NxD array of vectors representing items in vecs1
vecs2 (np.ndarray) – MxD array of vectors representing items in vecs2
p (float) – L-p norm to use. Default is 2 (aka Eucliedean)
- Returns
- tuple containing assignments of rows in vecs1 to
rows in vecs2, and the total distance between assigned pairs.
- Return type
Notes
Thin wrapper around mincost_assignment
- CommandLine:
xdoctest -m ~/code/kwarray/kwarray/algo_assignment.py mindist_assignment
- CommandLine:
xdoctest -m ~/code/kwarray/kwarray/algo_assignment.py mindist_assignment
Example
>>> # xdoctest: +REQUIRES(module:scipy) >>> # Rows are detections in img1, cols are detections in img2 >>> rng = np.random.RandomState(43) >>> vecs1 = rng.randint(0, 10, (5, 2)) >>> vecs2 = rng.randint(0, 10, (7, 2)) >>> ret = mindist_assignment(vecs1, vecs2) >>> print('Total error: {:.4f}'.format(ret[1])) Total error: 8.2361 >>> print('Assignment: {}'.format(ret[0])) # xdoc: +IGNORE_WANT Assignment: [(0, 0), (1, 3), (2, 5), (3, 2), (4, 6)]
- kwarray.algo_assignment.mincost_assignment(cost)¶
Finds the minimum cost assignment based on a NxM cost matrix, subject to the constraint that each row can match at most one column and each column can match at most one row. Any pair with a cost of infinity will not be assigned.
- Parameters
cost (ndarray) – NxM matrix, cost[i, j] is the cost to match i and j
- Returns
- tuple containing a list of assignment of rows
and columns, and the total cost of the assignment.
- Return type
- CommandLine:
xdoctest -m ~/code/kwarray/kwarray/algo_assignment.py mincost_assignment
Example
>>> # xdoctest: +REQUIRES(module:scipy) >>> # Costs to match item i in set1 with item j in set2. >>> cost = np.array([ >>> [9, 2, 1, 9], >>> [4, 1, 5, 5], >>> [9, 9, 2, 4], >>> ]) >>> ret = mincost_assignment(cost) >>> print('Assignment: {}'.format(ret[0])) >>> print('Total cost: {}'.format(ret[1])) Assignment: [(0, 2), (1, 1), (2, 3)] Total cost: 6
Example
>>> # xdoctest: +REQUIRES(module:scipy) >>> cost = np.array([ >>> [0, 0, 0, 0], >>> [4, 1, 5, -np.inf], >>> [9, 9, np.inf, 4], >>> [9, -2, np.inf, 4], >>> ]) >>> ret = mincost_assignment(cost) >>> print('Assignment: {}'.format(ret[0])) >>> print('Total cost: {}'.format(ret[1])) Assignment: [(0, 2), (1, 3), (2, 0), (3, 1)] Total cost: -inf
Example
>>> # xdoctest: +REQUIRES(module:scipy) >>> cost = np.array([ >>> [0, 0, 0, 0], >>> [4, 1, 5, -3], >>> [1, 9, np.inf, 0.1], >>> [np.inf, np.inf, np.inf, 100], >>> ]) >>> ret = mincost_assignment(cost) >>> print('Assignment: {}'.format(ret[0])) >>> print('Total cost: {}'.format(ret[1])) Assignment: [(0, 2), (1, 1), (2, 0), (3, 3)] Total cost: 102.0
- kwarray.algo_assignment.maxvalue_assignment(value)¶
Finds the maximum value assignment based on a NxM value matrix. Any pair with a non-positive value will not be assigned.
- Parameters
value (ndarray) – NxM matrix, value[i, j] is the value of matching i and j
- Returns
- tuple containing a list of assignment of rows
and columns, and the total value of the assignment.
- Return type
- CommandLine:
xdoctest -m ~/code/kwarray/kwarray/algo_assignment.py maxvalue_assignment
Example
>>> # xdoctest: +REQUIRES(module:scipy) >>> # Costs to match item i in set1 with item j in set2. >>> value = np.array([ >>> [9, 2, 1, 3], >>> [4, 1, 5, 5], >>> [9, 9, 2, 4], >>> [-1, -1, -1, -1], >>> ]) >>> ret = maxvalue_assignment(value) >>> # Note, depending on the scipy version the assignment might change >>> # but the value should always be the same. >>> print('Total value: {}'.format(ret[1])) Total value: 23.0 >>> print('Assignment: {}'.format(ret[0])) # xdoc: +IGNORE_WANT Assignment: [(0, 0), (1, 3), (2, 1)]
>>> ret = maxvalue_assignment(np.array([[np.inf]])) >>> print('Assignment: {}'.format(ret[0])) >>> print('Total value: {}'.format(ret[1])) Assignment: [(0, 0)] Total value: inf
>>> ret = maxvalue_assignment(np.array([[0]])) >>> print('Assignment: {}'.format(ret[0])) >>> print('Total value: {}'.format(ret[1])) Assignment: [] Total value: 0