Solve linear assignment problem. Parameters ---------- distance_metric : Callable[List[Track], List[Detection], List[int], List[int]) -> ndarray The distance metric is given a list of tracks and detections as well as a list of N track indices and M detection indices. The
(
distance_metric, max_distance, tracks, detections, track_indices=None,
detection_indices=None)
| 9 | |
| 10 | |
| 11 | def min_cost_matching( |
| 12 | distance_metric, max_distance, tracks, detections, track_indices=None, |
| 13 | detection_indices=None): |
| 14 | """Solve linear assignment problem. |
| 15 | Parameters |
| 16 | ---------- |
| 17 | distance_metric : Callable[List[Track], List[Detection], List[int], List[int]) -> ndarray |
| 18 | The distance metric is given a list of tracks and detections as well as |
| 19 | a list of N track indices and M detection indices. The metric should |
| 20 | return the NxM dimensional cost matrix, where element (i, j) is the |
| 21 | association cost between the i-th track in the given track indices and |
| 22 | the j-th detection in the given detection_indices. |
| 23 | max_distance : float |
| 24 | Gating threshold. Associations with cost larger than this value are |
| 25 | disregarded. |
| 26 | tracks : List[track.Track] |
| 27 | A list of predicted tracks at the current time step. |
| 28 | detections : List[detection.Detection] |
| 29 | A list of detections at the current time step. |
| 30 | track_indices : List[int] |
| 31 | List of track indices that maps rows in `cost_matrix` to tracks in |
| 32 | `tracks` (see description above). |
| 33 | detection_indices : List[int] |
| 34 | List of detection indices that maps columns in `cost_matrix` to |
| 35 | detections in `detections` (see description above). |
| 36 | Returns |
| 37 | ------- |
| 38 | (List[(int, int)], List[int], List[int]) |
| 39 | Returns a tuple with the following three entries: |
| 40 | * A list of matched track and detection indices. |
| 41 | * A list of unmatched track indices. |
| 42 | * A list of unmatched detection indices. |
| 43 | """ |
| 44 | if track_indices is None: |
| 45 | track_indices = np.arange(len(tracks)) |
| 46 | if detection_indices is None: |
| 47 | detection_indices = np.arange(len(detections)) |
| 48 | |
| 49 | if len(detection_indices) == 0 or len(track_indices) == 0: |
| 50 | return [], track_indices, detection_indices # Nothing to match. |
| 51 | |
| 52 | cost_matrix = distance_metric( |
| 53 | tracks, detections, track_indices, detection_indices) |
| 54 | cost_matrix[cost_matrix > max_distance] = max_distance + 1e-5 |
| 55 | |
| 56 | row_indices, col_indices = linear_assignment(cost_matrix) |
| 57 | |
| 58 | matches, unmatched_tracks, unmatched_detections = [], [], [] |
| 59 | for col, detection_idx in enumerate(detection_indices): |
| 60 | if col not in col_indices: |
| 61 | unmatched_detections.append(detection_idx) |
| 62 | for row, track_idx in enumerate(track_indices): |
| 63 | if row not in row_indices: |
| 64 | unmatched_tracks.append(track_idx) |
| 65 | for row, col in zip(row_indices, col_indices): |
| 66 | track_idx = track_indices[row] |
| 67 | detection_idx = detection_indices[col] |
| 68 | if cost_matrix[row, col] > max_distance: |
no test coverage detected