Skip to main content

sightloom_tracking/
matching.rs

1//! Deterministic intersection-over-union assignment for track/detection pairs.
2
3use sightloom_core::{ClassId, Rect, iou};
4
5/// A candidate pair for assignment with an intersection-over-union score.
6#[derive(Clone, Copy, Debug, PartialEq)]
7pub struct MatchCandidate {
8    /// Track row index.
9    pub track_index: usize,
10    /// Detection column index.
11    pub detection_index: usize,
12    /// Intersection-over-union between predicted track box and detection box.
13    pub iou: f32,
14}
15
16/// Sizes of the assignment outputs.
17#[derive(Clone, Copy, Debug, Eq, PartialEq)]
18pub struct AssignResult {
19    /// Number of matched pairs written.
20    pub match_count: usize,
21    /// Number of unmatched track indices written.
22    pub unmatched_track_count: usize,
23    /// Number of unmatched detection indices written.
24    pub unmatched_detection_count: usize,
25}
26
27/// Scratch buffers required by [`greedy_iou_assign`].
28pub struct AssignScratch<'a> {
29    /// Candidate pair storage (`tracks * detections` worst case).
30    pub candidates: &'a mut [MatchCandidate],
31    /// Per-track used flags (`track_boxes.len()`).
32    pub track_used: &'a mut [bool],
33    /// Per-detection used flags (`detection_boxes.len()`).
34    pub detection_used: &'a mut [bool],
35}
36
37/// Greedy deterministic assignment sorted by descending score, then track index,
38/// then detection index. Each track and detection is used at most once.
39///
40/// Pairs with intersection-over-union at or below `iou_threshold` are ignored.
41#[allow(clippy::too_many_arguments)]
42pub fn greedy_iou_assign(
43    track_boxes: &[Rect],
44    detection_boxes: &[Rect],
45    track_classes: &[Option<ClassId>],
46    detection_classes: &[Option<ClassId>],
47    class_aware: bool,
48    iou_threshold: f32,
49    scratch: &mut AssignScratch<'_>,
50    matches: &mut [(usize, usize)],
51    unmatched_tracks: &mut [usize],
52    unmatched_detections: &mut [usize],
53) -> AssignResult {
54    let mut candidate_count = 0_usize;
55    for (ti, track_box) in track_boxes.iter().enumerate() {
56        for (di, det_box) in detection_boxes.iter().enumerate() {
57            if class_aware {
58                let tc = track_classes.get(ti).copied().flatten();
59                let dc = detection_classes.get(di).copied().flatten();
60                if tc != dc {
61                    continue;
62                }
63            }
64            let score = iou(*track_box, *det_box);
65            if score <= iou_threshold {
66                continue;
67            }
68            if candidate_count < scratch.candidates.len() {
69                scratch.candidates[candidate_count] = MatchCandidate {
70                    track_index: ti,
71                    detection_index: di,
72                    iou: score,
73                };
74                candidate_count += 1;
75            }
76        }
77    }
78
79    let candidates = &mut scratch.candidates[..candidate_count];
80    candidates.sort_unstable_by(|left, right| {
81        right
82            .iou
83            .partial_cmp(&left.iou)
84            .unwrap_or(core::cmp::Ordering::Equal)
85            .then_with(|| left.track_index.cmp(&right.track_index))
86            .then_with(|| left.detection_index.cmp(&right.detection_index))
87    });
88
89    let track_used_len = track_boxes.len().min(scratch.track_used.len());
90    let det_used_len = detection_boxes.len().min(scratch.detection_used.len());
91    let track_used = &mut scratch.track_used[..track_used_len];
92    let det_used = &mut scratch.detection_used[..det_used_len];
93    for value in track_used.iter_mut() {
94        *value = false;
95    }
96    for value in det_used.iter_mut() {
97        *value = false;
98    }
99
100    let mut match_count = 0_usize;
101    for candidate in candidates.iter() {
102        if candidate.track_index >= track_used.len() || candidate.detection_index >= det_used.len()
103        {
104            continue;
105        }
106        if track_used[candidate.track_index] || det_used[candidate.detection_index] {
107            continue;
108        }
109        if match_count >= matches.len() {
110            break;
111        }
112        matches[match_count] = (candidate.track_index, candidate.detection_index);
113        match_count += 1;
114        track_used[candidate.track_index] = true;
115        det_used[candidate.detection_index] = true;
116    }
117
118    let mut ut = 0_usize;
119    for index in 0..track_boxes.len() {
120        let used = index < track_used.len() && track_used[index];
121        if !used && ut < unmatched_tracks.len() {
122            unmatched_tracks[ut] = index;
123            ut += 1;
124        }
125    }
126    let mut ud = 0_usize;
127    for index in 0..detection_boxes.len() {
128        let used = index < det_used.len() && det_used[index];
129        if !used && ud < unmatched_detections.len() {
130            unmatched_detections[ud] = index;
131            ud += 1;
132        }
133    }
134
135    AssignResult {
136        match_count,
137        unmatched_track_count: ut,
138        unmatched_detection_count: ud,
139    }
140}