1#![allow(
8 clippy::cast_possible_truncation,
9 clippy::cast_precision_loss,
10 clippy::cast_sign_loss
11)]
12
13extern crate alloc;
14
15use crate::anomaly::{AnomalyEvent, AnomalyReason, Severity};
16use crate::anomaly_backend::AnomalyDetector;
17use crate::input::{AnalysisSeries, PairSample, RouteSample, TimedSubjectEvent};
18use alloc::{vec, vec::Vec};
19use sightloom_core::{AnomalyId, EventId, MediaTime, SourceId, SubjectId, ZoneId};
20
21#[derive(Clone, Copy, Debug, Eq, PartialEq)]
23pub struct GraphEdge {
24 pub from: SourceId,
26 pub to: SourceId,
28 pub min_travel_ns: i64,
30 pub max_travel_ns: Option<i64>,
32}
33
34#[derive(Clone, Debug, Default, PartialEq, Eq)]
36pub struct CameraGraph {
37 edges: Vec<GraphEdge>,
38 pub strict_unknown: bool,
40}
41
42impl CameraGraph {
43 #[must_use]
45 pub const fn new(strict_unknown: bool) -> Self {
46 Self {
47 edges: Vec::new(),
48 strict_unknown,
49 }
50 }
51
52 pub fn set_edge_window(
54 &mut self,
55 from: SourceId,
56 to: SourceId,
57 min_travel_ns: i64,
58 max_travel_ns: Option<i64>,
59 ) {
60 if let Some(edge) = self.edges.iter_mut().find(|e| e.from == from && e.to == to) {
61 edge.min_travel_ns = min_travel_ns;
62 edge.max_travel_ns = max_travel_ns;
63 } else {
64 self.edges.push(GraphEdge {
65 from,
66 to,
67 min_travel_ns,
68 max_travel_ns,
69 });
70 }
71 }
72
73 pub fn set_bidirectional_window(
75 &mut self,
76 a: SourceId,
77 b: SourceId,
78 min_travel_ns: i64,
79 max_travel_ns: Option<i64>,
80 ) {
81 self.set_edge_window(a, b, min_travel_ns, max_travel_ns);
82 self.set_edge_window(b, a, min_travel_ns, max_travel_ns);
83 }
84
85 #[must_use]
87 pub fn allows_hop(&self, from: SourceId, to: SourceId, elapsed_ns: i64) -> bool {
88 if from == to {
89 return true;
90 }
91 match self.edges.iter().find(|e| e.from == from && e.to == to) {
92 Some(edge) if elapsed_ns < edge.min_travel_ns => false,
93 Some(edge) if edge.max_travel_ns.is_some_and(|max| elapsed_ns > max) => false,
94 None if self.strict_unknown => false,
95 Some(_) | None => true,
96 }
97 }
98
99 #[must_use]
101 pub fn edges(&self) -> &[GraphEdge] {
102 &self.edges
103 }
104}
105
106#[derive(Clone, Copy, Debug, PartialEq)]
108#[allow(clippy::struct_excessive_bools)]
109pub struct GraphAnomalyConfig {
110 pub min_hop_samples: usize,
112 pub rare_hop_fraction: f32,
114 pub min_pair_samples: usize,
116 pub rare_pair_fraction: f32,
118 pub min_route_samples: usize,
120 pub rare_route_fraction: f32,
122 pub flag_impossible_hops: bool,
124 pub flag_rare_hops: bool,
126 pub flag_rare_pairs: bool,
128 pub flag_rare_routes: bool,
130}
131
132impl Default for GraphAnomalyConfig {
133 fn default() -> Self {
134 Self {
135 min_hop_samples: 8,
136 rare_hop_fraction: 0.05,
137 min_pair_samples: 6,
138 rare_pair_fraction: 0.05,
139 min_route_samples: 6,
140 rare_route_fraction: 0.05,
141 flag_impossible_hops: true,
142 flag_rare_hops: true,
143 flag_rare_pairs: true,
144 flag_rare_routes: true,
145 }
146 }
147}
148
149#[derive(Clone, Copy, Debug, PartialEq, Eq)]
151pub struct CameraHop {
152 pub subject_id: Option<SubjectId>,
154 pub from: SourceId,
156 pub to: SourceId,
158 pub elapsed_ns: i64,
160 pub at_ns: i64,
162 pub event_id: Option<EventId>,
164}
165
166#[derive(Clone, Debug, Default, PartialEq)]
168pub struct GraphBaseline {
169 pub hop_counts: Vec<(SourceId, SourceId, u32)>,
171 pub hop_n: usize,
173 pub pair_counts: Vec<(SubjectId, SubjectId, u32)>,
175 pub pair_n: usize,
177 pub route_counts: Vec<(Vec<ZoneId>, u32)>,
179 pub route_n: usize,
181}
182
183impl GraphBaseline {
184 #[must_use]
186 pub fn hop_fraction(&self, from: SourceId, to: SourceId) -> f32 {
187 if self.hop_n == 0 {
188 return 0.0;
189 }
190 let c = self
191 .hop_counts
192 .iter()
193 .find(|(a, b, _)| *a == from && *b == to)
194 .map_or(0, |(_, _, n)| *n);
195 c as f32 / self.hop_n as f32
196 }
197
198 #[must_use]
200 pub fn pair_fraction(&self, a: SubjectId, b: SubjectId) -> f32 {
201 if self.pair_n == 0 {
202 return 0.0;
203 }
204 let (lo, hi) = order_subjects(a, b);
205 let c = self
206 .pair_counts
207 .iter()
208 .find(|(x, y, _)| *x == lo && *y == hi)
209 .map_or(0, |(_, _, n)| *n);
210 c as f32 / self.pair_n as f32
211 }
212
213 #[must_use]
215 pub fn route_fraction(&self, zones: &[ZoneId]) -> f32 {
216 if self.route_n == 0 {
217 return 0.0;
218 }
219 let c = self
220 .route_counts
221 .iter()
222 .find(|(z, _)| z.as_slice() == zones)
223 .map_or(0, |(_, n)| *n);
224 c as f32 / self.route_n as f32
225 }
226}
227
228#[must_use]
230pub fn extract_camera_hops(events: &[TimedSubjectEvent]) -> Vec<CameraHop> {
231 let mut by_subject: Vec<(Option<SubjectId>, Vec<TimedSubjectEvent>)> = Vec::new();
232 for event in events {
233 if event.source_id.is_none() {
234 continue;
235 }
236 if let Some((_, list)) = by_subject
237 .iter_mut()
238 .find(|(sid, _)| *sid == event.subject_id)
239 {
240 list.push(*event);
241 } else {
242 by_subject.push((event.subject_id, vec![*event]));
243 }
244 }
245
246 let mut hops = Vec::new();
247 for (subject_id, mut list) in by_subject {
248 list.sort_by_key(|e| e.at_ns);
249 for window in list.windows(2) {
250 let a = window[0];
251 let b = window[1];
252 let (Some(from), Some(to)) = (a.source_id, b.source_id) else {
253 continue;
254 };
255 if from == to {
256 continue;
257 }
258 let elapsed = b.at_ns.saturating_sub(a.at_ns);
259 if elapsed <= 0 {
260 continue;
261 }
262 hops.push(CameraHop {
263 subject_id,
264 from,
265 to,
266 elapsed_ns: elapsed,
267 at_ns: b.at_ns,
268 event_id: b.event_id,
269 });
270 }
271 }
272 hops
273}
274
275#[must_use]
277pub fn build_graph_baseline(series: &AnalysisSeries) -> GraphBaseline {
278 let mut baseline = GraphBaseline::default();
279
280 for hop in extract_camera_hops(&series.timed) {
281 bump_hop(&mut baseline.hop_counts, hop.from, hop.to);
282 baseline.hop_n = baseline.hop_n.saturating_add(1);
283 }
284
285 for pair in &series.pairs {
286 let (lo, hi) = order_subjects(pair.subject_a, pair.subject_b);
287 bump_pair(&mut baseline.pair_counts, lo, hi);
288 baseline.pair_n = baseline.pair_n.saturating_add(1);
289 }
290
291 for route in &series.routes {
292 bump_route(&mut baseline.route_counts, &route.zones);
293 baseline.route_n = baseline.route_n.saturating_add(1);
294 }
295
296 baseline
297}
298
299#[must_use]
301pub fn detect_graph_anomalies(
302 live: &AnalysisSeries,
303 baseline: &GraphBaseline,
304 graph: &CameraGraph,
305 config: GraphAnomalyConfig,
306 next_id: &mut u64,
307) -> Vec<AnomalyEvent> {
308 let mut out = Vec::new();
309 if config.flag_impossible_hops || config.flag_rare_hops {
310 out.extend(detect_hop_anomalies(
311 &extract_camera_hops(&live.timed),
312 baseline,
313 graph,
314 config,
315 next_id,
316 ));
317 }
318 if config.flag_rare_pairs {
319 out.extend(detect_pair_anomalies(
320 &live.pairs,
321 baseline,
322 config,
323 next_id,
324 ));
325 }
326 if config.flag_rare_routes {
327 out.extend(detect_route_anomalies(
328 &live.routes,
329 baseline,
330 config,
331 next_id,
332 ));
333 }
334 out
335}
336
337fn detect_hop_anomalies(
338 hops: &[CameraHop],
339 baseline: &GraphBaseline,
340 graph: &CameraGraph,
341 config: GraphAnomalyConfig,
342 next_id: &mut u64,
343) -> Vec<AnomalyEvent> {
344 let mut out = Vec::new();
345 let rare = config.rare_hop_fraction.clamp(0.0, 0.5);
346 for hop in hops {
347 if config.flag_impossible_hops && !graph.allows_hop(hop.from, hop.to, hop.elapsed_ns) {
348 out.push(make_event(
349 next_id,
350 8.0,
351 AnomalyReason::ImpossibleCrossCameraHop,
352 hop.subject_id,
353 Some(hop.to),
354 hop.event_id,
355 hop.at_ns,
356 ));
357 continue;
358 }
359 if !config.flag_rare_hops || baseline.hop_n < config.min_hop_samples {
360 continue;
361 }
362 let frac = baseline.hop_fraction(hop.from, hop.to);
363 if frac > rare {
364 continue;
365 }
366 let score = (1.0 / (frac + 1e-3)).min(20.0);
368 out.push(make_event(
369 next_id,
370 score,
371 AnomalyReason::UnusualCameraTransition,
372 hop.subject_id,
373 Some(hop.to),
374 hop.event_id,
375 hop.at_ns,
376 ));
377 }
378 out
379}
380
381fn detect_pair_anomalies(
382 pairs: &[PairSample],
383 baseline: &GraphBaseline,
384 config: GraphAnomalyConfig,
385 next_id: &mut u64,
386) -> Vec<AnomalyEvent> {
387 if baseline.pair_n < config.min_pair_samples {
388 return Vec::new();
389 }
390 let rare = config.rare_pair_fraction.clamp(0.0, 0.5);
391 let mut out = Vec::new();
392 for pair in pairs {
393 let frac = baseline.pair_fraction(pair.subject_a, pair.subject_b);
394 if frac > rare {
395 continue;
396 }
397 let score = (1.0 / (frac + 1e-3)).min(20.0);
398 out.push(make_event(
399 next_id,
400 score,
401 AnomalyReason::UnusualCoOccurrence,
402 Some(pair.subject_a),
403 pair.source_id,
404 pair.event_id,
405 pair.at_ns,
406 ));
407 }
408 out
409}
410
411fn detect_route_anomalies(
412 routes: &[RouteSample],
413 baseline: &GraphBaseline,
414 config: GraphAnomalyConfig,
415 next_id: &mut u64,
416) -> Vec<AnomalyEvent> {
417 if baseline.route_n < config.min_route_samples {
418 return Vec::new();
419 }
420 let rare = config.rare_route_fraction.clamp(0.0, 0.5);
421 let mut out = Vec::new();
422 for route in routes {
423 if route.zones.len() < 2 {
424 continue;
425 }
426 let frac = baseline.route_fraction(&route.zones);
427 if frac > rare {
428 continue;
429 }
430 let score = (1.0 / (frac + 1e-3)).min(20.0);
431 out.push(make_event(
432 next_id,
433 score,
434 AnomalyReason::UnusualRoute,
435 Some(route.subject_id),
436 None,
437 route.event_id,
438 route.at_ns,
439 ));
440 }
441 out
442}
443
444fn make_event(
445 next_id: &mut u64,
446 score: f32,
447 reason: AnomalyReason,
448 subject_id: Option<SubjectId>,
449 source_id: Option<SourceId>,
450 event_id: Option<EventId>,
451 at_ns: i64,
452) -> AnomalyEvent {
453 let id = AnomalyId(*next_id);
454 *next_id = next_id.saturating_add(1);
455 let mut evidence = Vec::new();
456 if let Some(event_id) = event_id {
457 evidence.push(event_id);
458 }
459 let severity = if score >= 10.0 {
460 Severity::Critical
461 } else if score >= 6.0 {
462 Severity::High
463 } else if score >= 3.5 {
464 Severity::Medium
465 } else {
466 Severity::Low
467 };
468 AnomalyEvent {
469 anomaly_id: id,
470 score: if score.is_finite() { score } else { 100.0 },
471 severity,
472 reasons: vec![reason],
473 evidence,
474 subject_id,
475 source_id,
476 at: MediaTime::new(at_ns, 1_000_000_000).unwrap_or_default(),
477 }
478}
479
480fn order_subjects(a: SubjectId, b: SubjectId) -> (SubjectId, SubjectId) {
481 if a.0 <= b.0 { (a, b) } else { (b, a) }
482}
483
484fn bump_hop(counts: &mut Vec<(SourceId, SourceId, u32)>, from: SourceId, to: SourceId) {
485 if let Some(slot) = counts.iter_mut().find(|(a, b, _)| *a == from && *b == to) {
486 slot.2 = slot.2.saturating_add(1);
487 } else {
488 counts.push((from, to, 1));
489 }
490}
491
492fn bump_pair(counts: &mut Vec<(SubjectId, SubjectId, u32)>, a: SubjectId, b: SubjectId) {
493 if let Some(slot) = counts.iter_mut().find(|(x, y, _)| *x == a && *y == b) {
494 slot.2 = slot.2.saturating_add(1);
495 } else {
496 counts.push((a, b, 1));
497 }
498}
499
500fn bump_route(counts: &mut Vec<(Vec<ZoneId>, u32)>, zones: &[ZoneId]) {
501 if let Some(slot) = counts.iter_mut().find(|(z, _)| z.as_slice() == zones) {
502 slot.1 = slot.1.saturating_add(1);
503 } else {
504 counts.push((zones.to_vec(), 1));
505 }
506}
507
508#[derive(Clone, Debug, Default)]
510pub struct GraphRelationalDetector {
511 pub config: GraphAnomalyConfig,
513 pub graph: CameraGraph,
515 pub baseline: Option<GraphBaseline>,
517}
518
519impl GraphRelationalDetector {
520 #[must_use]
522 pub fn new(config: GraphAnomalyConfig) -> Self {
523 Self {
524 config,
525 graph: CameraGraph::new(true),
526 baseline: None,
527 }
528 }
529
530 #[must_use]
532 pub fn with_graph(config: GraphAnomalyConfig, graph: CameraGraph) -> Self {
533 Self {
534 config,
535 graph,
536 baseline: None,
537 }
538 }
539
540 pub fn set_graph(&mut self, graph: CameraGraph) {
542 self.graph = graph;
543 }
544}
545
546impl AnomalyDetector for GraphRelationalDetector {
547 type Error = &'static str;
548
549 fn fit(&mut self, history: &AnalysisSeries) -> Result<(), Self::Error> {
550 self.baseline = Some(build_graph_baseline(history));
551 Ok(())
552 }
553
554 fn detect(
555 &mut self,
556 live: &AnalysisSeries,
557 next_id: &mut u64,
558 ) -> Result<Vec<AnomalyEvent>, Self::Error> {
559 let baseline = self
560 .baseline
561 .clone()
562 .unwrap_or_else(|| build_graph_baseline(live));
563 Ok(detect_graph_anomalies(
564 live,
565 &baseline,
566 &self.graph,
567 self.config,
568 next_id,
569 ))
570 }
571}
572
573#[cfg(test)]
574mod tests {
575 use super::*;
576 use crate::input::AnalysisSeries;
577
578 fn cam(id: u32) -> SourceId {
579 SourceId(id)
580 }
581
582 fn sub(id: u64) -> SubjectId {
583 SubjectId(id)
584 }
585
586 fn timed(subject: u64, source: u32, at_ns: i64) -> TimedSubjectEvent {
587 TimedSubjectEvent {
588 subject_id: Some(sub(subject)),
589 source_id: Some(cam(source)),
590 at_ns,
591 event_id: Some(EventId(at_ns as u64)),
592 kind_tag: 0,
593 }
594 }
595
596 #[test]
597 fn extract_hops_skips_same_camera() {
598 let events = [timed(1, 1, 1_000), timed(1, 1, 2_000), timed(1, 2, 5_000)];
599 let hops = extract_camera_hops(&events);
600 assert_eq!(hops.len(), 1);
601 assert_eq!(hops[0].from, cam(1));
602 assert_eq!(hops[0].to, cam(2));
603 assert_eq!(hops[0].elapsed_ns, 3_000);
604 }
605
606 #[test]
607 fn impossible_hop_flagged() {
608 let mut graph = CameraGraph::new(true);
609 graph.set_edge_window(cam(1), cam(2), 10_000_000_000, None);
611
612 let mut history = AnalysisSeries::default();
613 for i in 0..10 {
614 history.timed.push(timed(1, 1, i * 20_000_000_000));
615 history
616 .timed
617 .push(timed(1, 2, i * 20_000_000_000 + 15_000_000_000));
618 }
619 let baseline = build_graph_baseline(&history);
620
621 let mut live = AnalysisSeries::default();
622 live.timed.push(timed(1, 1, 100_000_000_000));
624 live.timed.push(timed(1, 2, 101_000_000_000));
625
626 let mut next_id = 1;
627 let found = detect_graph_anomalies(
628 &live,
629 &baseline,
630 &graph,
631 GraphAnomalyConfig {
632 flag_rare_hops: false,
633 flag_rare_pairs: false,
634 flag_rare_routes: false,
635 ..GraphAnomalyConfig::default()
636 },
637 &mut next_id,
638 );
639 assert!(
640 found
641 .iter()
642 .any(|a| a.reasons.contains(&AnomalyReason::ImpossibleCrossCameraHop)),
643 "{found:?}"
644 );
645 }
646
647 #[test]
648 fn rare_hop_flagged_against_baseline() {
649 let mut history = AnalysisSeries::default();
650 for i in 0_i64..12 {
652 history
653 .timed
654 .push(timed(i as u64 + 1, 1, i * 10_000_000_000));
655 history
656 .timed
657 .push(timed(i as u64 + 1, 2, i * 10_000_000_000 + 5_000_000_000));
658 }
659 let baseline = build_graph_baseline(&history);
660 assert_eq!(baseline.hop_n, 12);
661 assert!((baseline.hop_fraction(cam(1), cam(2)) - 1.0).abs() < 1e-5);
662
663 let mut live = AnalysisSeries::default();
664 live.timed.push(timed(1, 1, 200_000_000_000));
666 live.timed.push(timed(1, 3, 205_000_000_000));
667
668 let mut next_id = 1;
669 let found = detect_graph_anomalies(
670 &live,
671 &baseline,
672 &CameraGraph::new(false),
673 GraphAnomalyConfig {
674 flag_impossible_hops: false,
675 flag_rare_pairs: false,
676 flag_rare_routes: false,
677 ..GraphAnomalyConfig::default()
678 },
679 &mut next_id,
680 );
681 assert!(
682 found
683 .iter()
684 .any(|a| a.reasons.contains(&AnomalyReason::UnusualCameraTransition)),
685 "{found:?}"
686 );
687 }
688
689 #[test]
690 fn rare_pair_and_route() {
691 let mut history = AnalysisSeries::default();
692 for i in 0..10 {
693 history.pairs.push(PairSample {
694 subject_a: sub(1),
695 subject_b: sub(2),
696 source_id: Some(cam(1)),
697 at_ns: i * 1_000,
698 event_id: None,
699 });
700 history.routes.push(RouteSample {
701 subject_id: sub(1),
702 zones: vec![ZoneId(1), ZoneId(2)],
703 at_ns: i * 1_000,
704 event_id: None,
705 });
706 }
707 let baseline = build_graph_baseline(&history);
708
709 let mut live = AnalysisSeries::default();
710 live.pairs.push(PairSample {
711 subject_a: sub(1),
712 subject_b: sub(9),
713 source_id: Some(cam(1)),
714 at_ns: 99_000,
715 event_id: None,
716 });
717 live.routes.push(RouteSample {
718 subject_id: sub(1),
719 zones: vec![ZoneId(9), ZoneId(8)],
720 at_ns: 99_000,
721 event_id: None,
722 });
723
724 let mut next_id = 1;
725 let found = detect_graph_anomalies(
726 &live,
727 &baseline,
728 &CameraGraph::new(false),
729 GraphAnomalyConfig {
730 flag_impossible_hops: false,
731 flag_rare_hops: false,
732 ..GraphAnomalyConfig::default()
733 },
734 &mut next_id,
735 );
736 assert!(
737 found
738 .iter()
739 .any(|a| a.reasons.contains(&AnomalyReason::UnusualCoOccurrence))
740 );
741 assert!(
742 found
743 .iter()
744 .any(|a| a.reasons.contains(&AnomalyReason::UnusualRoute))
745 );
746 }
747
748 #[test]
749 fn detector_trait_fit_detect() {
750 let mut det = GraphRelationalDetector::new(GraphAnomalyConfig {
751 flag_impossible_hops: false,
752 flag_rare_pairs: false,
753 flag_rare_routes: false,
754 ..GraphAnomalyConfig::default()
755 });
756 let mut history = AnalysisSeries::default();
757 for i in 0_i64..12 {
758 history
759 .timed
760 .push(timed(i as u64 + 1, 1, i * 10_000_000_000));
761 history
762 .timed
763 .push(timed(i as u64 + 1, 2, i * 10_000_000_000 + 5_000_000_000));
764 }
765 det.fit(&history).unwrap();
766 let mut live = AnalysisSeries::default();
767 live.timed.push(timed(1, 1, 500_000_000_000));
768 live.timed.push(timed(1, 3, 505_000_000_000));
769 let mut next_id = 1;
770 let found = det.detect(&live, &mut next_id).unwrap();
771 assert!(!found.is_empty());
772 }
773}