///|
priv struct LineState {
mut has_stable : Bool
mut stable_side : Int32
mut candidate_side : Int32
mut candidate_count : Int32
}
///|
priv struct RegionState {
mut stable_inside : Bool?
mut candidate_inside : Bool?
mut candidate_count : Int32
mut candidate_start : Int32
mut entry_frame : Int32?
}
///|
priv struct TrackState {
track_id : Int32
class_id : Int32
lines : Array[LineState]
regions : Array[RegionState]
mut last_exit_region : Int32?
}
///|
priv struct LineTotals {
mut left_to_right : Int32
mut right_to_left : Int32
unique_left_ids : Array[Int32]
unique_right_ids : Array[Int32]
}
///|
priv struct LineClassTotals {
class_id : Int32
mut left_to_right : Int32
mut right_to_left : Int32
unique_left_ids : Array[Int32]
unique_right_ids : Array[Int32]
}
///|
priv struct RegionTotals {
mut entries : Int32
mut exits : Int32
unique_ids : Array[Int32]
mut peak_occupancy : Int32
mut completed_dwell_frames : Int32
}
///|
priv struct RegionClassTotals {
class_id : Int32
mut entries : Int32
mut exits : Int32
unique_ids : Array[Int32]
mut peak_occupancy : Int32
mut completed_dwell_frames : Int32
}
///|
priv struct TransitionTotals {
from_region_id : Int32
to_region_id : Int32
class_id : Int32
mut count : Int32
}
///|
/// Stateful conversion from visible track samples to spatial events and counts.
struct SpatialAnalyzer {
config : AnalyticsConfig
lines : Array[DirectedLine]
regions : Array[PolygonRegion]
mut tracks : Array[TrackState]
mut removed_ids : Array[Int32]
mut line_totals : Array[LineTotals]
mut line_class_totals : Array[Array[LineClassTotals]]
mut region_totals : Array[RegionTotals]
mut region_class_totals : Array[Array[RegionClassTotals]]
mut transition_totals : Array[TransitionTotals]
mut last_frame : Int32?
}
///|
fn ensure_unique_rule_ids(
kind : String,
ids : Array[Int32],
) -> Unit raise AnalyticsError {
let sorted = ids.copy()
sorted.sort()
for index = 1; index < sorted.length(); index = index + 1 {
if sorted[index] == sorted[index - 1] {
raise DuplicateRuleId(kind~, id=sorted[index])
}
}
}
///|
/// Creates an analyzer and fixes a deterministic rule order by rule identifier.
pub fn SpatialAnalyzer::new(
config : AnalyticsConfig,
lines : Array[DirectedLine],
regions : Array[PolygonRegion],
) -> SpatialAnalyzer raise AnalyticsError {
ensure_unique_rule_ids("line", lines.map(line => line.id))
ensure_unique_rule_ids("region", regions.map(region => region.id))
let sorted_lines = lines.copy()
sorted_lines.sort_by((left, right) => left.id.compare(right.id))
let sorted_regions = regions.copy()
sorted_regions.sort_by((left, right) => left.id.compare(right.id))
{
config,
lines: sorted_lines,
regions: sorted_regions,
tracks: [],
removed_ids: [],
line_totals: sorted_lines.map(_ => {
left_to_right: 0,
right_to_left: 0,
unique_left_ids: [],
unique_right_ids: [],
}),
line_class_totals: sorted_lines.map(_ => []),
region_totals: sorted_regions.map(_ => {
entries: 0,
exits: 0,
unique_ids: [],
peak_occupancy: 0,
completed_dwell_frames: 0,
}),
region_class_totals: sorted_regions.map(_ => []),
transition_totals: [],
last_frame: None,
}
}
///|
fn LineState::copy_state(self : LineState) -> LineState {
{
has_stable: self.has_stable,
stable_side: self.stable_side,
candidate_side: self.candidate_side,
candidate_count: self.candidate_count,
}
}
///|
fn RegionState::copy_state(self : RegionState) -> RegionState {
{
stable_inside: self.stable_inside,
candidate_inside: self.candidate_inside,
candidate_count: self.candidate_count,
candidate_start: self.candidate_start,
entry_frame: self.entry_frame,
}
}
///|
fn TrackState::copy_state(self : TrackState) -> TrackState {
{
track_id: self.track_id,
class_id: self.class_id,
lines: self.lines.map(state => state.copy_state()),
regions: self.regions.map(state => state.copy_state()),
last_exit_region: self.last_exit_region,
}
}
///|
fn new_track_state(
sample : TrackSample,
line_count : Int32,
region_count : Int32,
) -> TrackState {
{
track_id: sample.track_id,
class_id: sample.class_id,
lines: Array::makei(line_count, _ => {
has_stable: false,
stable_side: 0,
candidate_side: 0,
candidate_count: 0,
}),
regions: Array::makei(region_count, _ => {
stable_inside: None,
candidate_inside: None,
candidate_count: 0,
candidate_start: 0,
entry_frame: None,
}),
last_exit_region: None,
}
}
///|
fn find_track(states : Array[TrackState], track_id : Int32) -> Int32? {
for index, state in states {
if state.track_id == track_id {
return Some(index)
}
}
None
}
///|
fn contains_id(ids : Array[Int32], id : Int32) -> Bool {
ids.any(value => value == id)
}
///|
fn validate_id_list(ids : Array[Int32]) -> Unit raise AnalyticsError {
let seen : Array[Int32] = []
for id in ids {
if id <= 0 {
raise InvalidTrackId(id)
}
if contains_id(seen, id) {
raise ConflictingTrackId(id)
}
seen.push(id)
}
}
///|
fn validate_frame_inputs(
states : Array[TrackState],
removed_ids : Array[Int32],
samples : Array[TrackSample],
lost : Array[Int32],
removed : Array[Int32],
) -> Unit raise AnalyticsError {
validate_id_list(lost)
validate_id_list(removed)
let visible_ids : Array[Int32] = []
for sample in samples {
if sample.track_id <= 0 {
raise InvalidTrackId(sample.track_id)
}
if sample.class_id < 0 {
raise InvalidClassId(sample.class_id)
}
if contains_id(visible_ids, sample.track_id) {
raise DuplicateTrackId(sample.track_id)
}
if contains_id(removed_ids, sample.track_id) {
raise ReusedRemovedId(sample.track_id)
}
match find_track(states, sample.track_id) {
Some(index) if states[index].class_id != sample.class_id =>
raise ChangedClassId(
track_id=sample.track_id,
previous=states[index].class_id,
received=sample.class_id,
)
_ => ()
}
visible_ids.push(sample.track_id)
}
for id in lost {
if contains_id(visible_ids, id) || contains_id(removed, id) {
raise ConflictingTrackId(id)
}
if contains_id(removed_ids, id) {
raise ReusedRemovedId(id)
}
if find_track(states, id) is None {
raise UnknownLifecycleId(id)
}
}
for id in removed {
if contains_id(visible_ids, id) || contains_id(lost, id) {
raise ConflictingTrackId(id)
}
if contains_id(removed_ids, id) {
raise ReusedRemovedId(id)
}
if find_track(states, id) is None {
raise UnknownLifecycleId(id)
}
}
}
///|
fn LineState::interrupt(self : LineState) -> Unit {
self.has_stable = false
self.stable_side = 0
self.candidate_side = 0
self.candidate_count = 0
}
///|
fn RegionState::interrupt(self : RegionState) -> Unit {
self.candidate_inside = None
self.candidate_count = 0
self.candidate_start = 0
}
///|
fn advance_line(
state : LineState,
side : Int32,
stable_frames : Int32,
line_id : Int32,
track_id : Int32,
totals : LineTotals,
class_totals : LineClassTotals,
events : Array[AnalyticsEvent],
) -> Unit {
if side == 0 {
return
}
if !state.has_stable {
if state.candidate_side == side {
state.candidate_count += 1
} else {
state.candidate_side = side
state.candidate_count = 1
}
if state.candidate_count >= stable_frames {
state.has_stable = true
state.stable_side = side
state.candidate_side = 0
state.candidate_count = 0
}
return
}
if state.stable_side == side {
state.candidate_side = 0
state.candidate_count = 0
return
}
if state.candidate_side == side {
state.candidate_count += 1
} else {
state.candidate_side = side
state.candidate_count = 1
}
if state.candidate_count < stable_frames {
return
}
let direction = if state.stable_side > 0 { LeftToRight } else { RightToLeft }
match direction {
LeftToRight => {
totals.left_to_right += 1
class_totals.left_to_right += 1
if !contains_id(totals.unique_left_ids, track_id) {
totals.unique_left_ids.push(track_id)
}
if !contains_id(class_totals.unique_left_ids, track_id) {
class_totals.unique_left_ids.push(track_id)
}
}
RightToLeft => {
totals.right_to_left += 1
class_totals.right_to_left += 1
if !contains_id(totals.unique_right_ids, track_id) {
totals.unique_right_ids.push(track_id)
}
if !contains_id(class_totals.unique_right_ids, track_id) {
class_totals.unique_right_ids.push(track_id)
}
}
}
events.push(LineCrossed(line_id~, track_id~, direction~))
state.stable_side = side
state.candidate_side = 0
state.candidate_count = 0
}
///|
fn remember_unique(totals : RegionTotals, track_id : Int32) -> Unit {
if !contains_id(totals.unique_ids, track_id) {
totals.unique_ids.push(track_id)
}
}
///|
fn remember_class_unique(totals : RegionClassTotals, track_id : Int32) -> Unit {
if !contains_id(totals.unique_ids, track_id) {
totals.unique_ids.push(track_id)
}
}
///|
fn ensure_line_class_totals(
totals : Array[LineClassTotals],
class_id : Int32,
) -> LineClassTotals {
for total in totals {
if total.class_id == class_id {
return total
}
}
let total = {
class_id,
left_to_right: 0,
right_to_left: 0,
unique_left_ids: [],
unique_right_ids: [],
}
totals.push(total)
total
}
///|
fn ensure_region_class_totals(
totals : Array[RegionClassTotals],
class_id : Int32,
) -> RegionClassTotals {
for total in totals {
if total.class_id == class_id {
return total
}
}
let total = {
class_id,
entries: 0,
exits: 0,
unique_ids: [],
peak_occupancy: 0,
completed_dwell_frames: 0,
}
totals.push(total)
total
}
///|
fn record_transition(
totals : Array[TransitionTotals],
from_region_id : Int32,
to_region_id : Int32,
class_id : Int32,
) -> Unit {
for total in totals {
if total.from_region_id == from_region_id &&
total.to_region_id == to_region_id &&
total.class_id == class_id {
total.count += 1
return
}
}
totals.push({ from_region_id, to_region_id, class_id, count: 1, })
}
///|
fn advance_transitions(
state : TrackState,
events : Array[AnalyticsEvent],
start : Int32,
totals : Array[TransitionTotals],
) -> Unit {
// Every event in this range belongs to one visible track. Record exits first,
// independently of the numeric order of overlapping region rules.
let mut first_exit : Int32? = None
for index in start..
if first_exit is None {
first_exit = Some(region_id)
}
_ => ()
}
}
if first_exit is Some(_) {
state.last_exit_region = first_exit
}
for index in start.. {
if !initial {
match state.last_exit_region {
Some(previous) if previous != region_id =>
record_transition(totals, previous, region_id, state.class_id)
_ => ()
}
}
state.last_exit_region = None
}
_ => ()
}
}
}
///|
fn confirm_initial_region(
state : RegionState,
inside : Bool,
region_id : Int32,
track_id : Int32,
totals : RegionTotals,
class_totals : RegionClassTotals,
events : Array[AnalyticsEvent],
) -> Unit {
state.stable_inside = Some(inside)
if inside {
state.entry_frame = Some(state.candidate_start)
totals.entries += 1
remember_unique(totals, track_id)
class_totals.entries += 1
remember_class_unique(class_totals, track_id)
events.push(RegionEntered(region_id~, track_id~, initial=true))
}
state.candidate_inside = None
state.candidate_count = 0
}
///|
fn advance_region(
state : RegionState,
classification : Int32,
frame_id : Int32,
stable_frames : Int32,
region_id : Int32,
track_id : Int32,
totals : RegionTotals,
class_totals : RegionClassTotals,
events : Array[AnalyticsEvent],
) -> Unit {
if classification == 0 {
return
}
let inside = classification > 0
match state.stable_inside {
None => {
if state.candidate_inside == Some(inside) {
state.candidate_count += 1
} else {
state.candidate_inside = Some(inside)
state.candidate_count = 1
state.candidate_start = frame_id
}
if state.candidate_count >= stable_frames {
confirm_initial_region(
state, inside, region_id, track_id, totals, class_totals, events,
)
}
}
Some(stable) => {
if stable == inside {
state.candidate_inside = None
state.candidate_count = 0
return
}
if state.candidate_inside == Some(inside) {
state.candidate_count += 1
} else {
state.candidate_inside = Some(inside)
state.candidate_count = 1
state.candidate_start = frame_id
}
if state.candidate_count < stable_frames {
return
}
state.stable_inside = Some(inside)
if inside {
state.entry_frame = Some(state.candidate_start)
totals.entries += 1
remember_unique(totals, track_id)
class_totals.entries += 1
remember_class_unique(class_totals, track_id)
events.push(RegionEntered(region_id~, track_id~, initial=false))
} else {
let dwell_frames = match state.entry_frame {
Some(entered) => state.candidate_start - entered
None => 0
}
state.entry_frame = None
totals.exits += 1
totals.completed_dwell_frames += dwell_frames
class_totals.exits += 1
class_totals.completed_dwell_frames += dwell_frames
events.push(RegionExited(region_id~, track_id~, dwell_frames~))
}
state.candidate_inside = None
state.candidate_count = 0
}
}
}
///|
fn event_key(event : AnalyticsEvent) -> (Int32, Int32, Int32) {
match event {
LineCrossed(line_id~, track_id~, ..) => (0, line_id, track_id)
RegionEntered(region_id~, track_id~, ..) => (1, region_id, track_id)
RegionExited(region_id~, track_id~, ..) => (2, region_id, track_id)
}
}
///|
fn compare_event(left : AnalyticsEvent, right : AnalyticsEvent) -> Int32 {
let (left_kind, left_rule, left_track) = event_key(left)
let (right_kind, right_rule, right_track) = event_key(right)
if left_kind != right_kind {
left_kind.compare(right_kind)
} else if left_rule != right_rule {
left_rule.compare(right_rule)
} else {
left_track.compare(right_track)
}
}
///|
fn make_frame(
frame_id : Int32,
lines : Array[DirectedLine],
regions : Array[PolygonRegion],
states : Array[TrackState],
visible_ids : Array[Int32],
line_totals : Array[LineTotals],
line_class_totals : Array[Array[LineClassTotals]],
region_totals : Array[RegionTotals],
region_class_totals : Array[Array[RegionClassTotals]],
transition_totals : Array[TransitionTotals],
events : Array[AnalyticsEvent],
) -> AnalyticsFrame {
events.sort_by(compare_event)
let line_counts = Array::makei(lines.length(), index => {
line_id: lines[index].id,
left_to_right: line_totals[index].left_to_right,
right_to_left: line_totals[index].right_to_left,
unique_left_to_right: line_totals[index].unique_left_ids.length(),
unique_right_to_left: line_totals[index].unique_right_ids.length(),
})
let line_class_counts : Array[LineClassCount] = []
for line_index, line in lines {
let sorted = line_class_totals[line_index].copy()
sorted.sort_by((left, right) => left.class_id.compare(right.class_id))
for total in sorted {
line_class_counts.push({
line_id: line.id,
class_id: total.class_id,
left_to_right: total.left_to_right,
right_to_left: total.right_to_left,
unique_left_to_right: total.unique_left_ids.length(),
unique_right_to_left: total.unique_right_ids.length(),
})
}
}
let occupants : Array[RegionOccupant] = []
let region_counts : Array[RegionCount] = []
let region_class_counts : Array[RegionClassCount] = []
for region_index, region in regions {
let mut occupancy = 0
for state in states {
if !contains_id(visible_ids, state.track_id) {
continue
}
let region_state = state.regions[region_index]
if region_state.stable_inside == Some(true) {
let dwell_frames = match region_state.entry_frame {
Some(entered) => frame_id - entered + 1
None => 0
}
occupants.push({
region_id: region.id,
track_id: state.track_id,
class_id: state.class_id,
dwell_frames,
})
occupancy += 1
}
}
if occupancy > region_totals[region_index].peak_occupancy {
region_totals[region_index].peak_occupancy = occupancy
}
region_counts.push({
region_id: region.id,
entries: region_totals[region_index].entries,
exits: region_totals[region_index].exits,
unique_tracks: region_totals[region_index].unique_ids.length(),
current_occupancy: occupancy,
peak_occupancy: region_totals[region_index].peak_occupancy,
completed_dwell_frames: region_totals[region_index].completed_dwell_frames,
})
let sorted = region_class_totals[region_index].copy()
sorted.sort_by((left, right) => left.class_id.compare(right.class_id))
for total in sorted {
let class_occupancy = occupants.fold(init=0, (count, occupant) => {
if occupant.region_id == region.id &&
occupant.class_id == total.class_id {
count + 1
} else {
count
}
})
if class_occupancy > total.peak_occupancy {
total.peak_occupancy = class_occupancy
}
region_class_counts.push({
region_id: region.id,
class_id: total.class_id,
entries: total.entries,
exits: total.exits,
unique_tracks: total.unique_ids.length(),
current_occupancy: class_occupancy,
peak_occupancy: total.peak_occupancy,
completed_dwell_frames: total.completed_dwell_frames,
})
}
}
occupants.sort_by((left, right) => {
if left.region_id != right.region_id {
left.region_id.compare(right.region_id)
} else {
left.track_id.compare(right.track_id)
}
})
let sorted_transitions = transition_totals.copy()
sorted_transitions.sort_by((left, right) => {
if left.from_region_id != right.from_region_id {
left.from_region_id.compare(right.from_region_id)
} else if left.to_region_id != right.to_region_id {
left.to_region_id.compare(right.to_region_id)
} else {
left.class_id.compare(right.class_id)
}
})
let transition_counts : Array[RegionTransitionCount] = sorted_transitions.map(total => {
from_region_id: total.from_region_id,
to_region_id: total.to_region_id,
class_id: total.class_id,
count: total.count,
},
)
{
frame_id,
events,
line_counts,
line_class_counts,
region_counts,
region_class_counts,
transition_counts,
occupants,
}
}
///|
/// Advances one frame atomically. Coordinates and rules must share one scale.
pub fn SpatialAnalyzer::update(
self : SpatialAnalyzer,
frame_id : Int32,
samples : Array[TrackSample],
lost : Array[Int32],
removed : Array[Int32],
) -> AnalyticsFrame raise AnalyticsError {
match self.last_frame {
Some(previous) if frame_id <= previous =>
raise NonIncreasingFrame(previous~, received=frame_id)
_ => ()
}
validate_frame_inputs(self.tracks, self.removed_ids, samples, lost, removed)
let working_tracks = self.tracks.map(state => state.copy_state())
let working_removed = self.removed_ids.copy()
let working_lines = self.line_totals.map(total => {
left_to_right: total.left_to_right,
right_to_left: total.right_to_left,
unique_left_ids: total.unique_left_ids.copy(),
unique_right_ids: total.unique_right_ids.copy(),
})
let working_line_classes = self.line_class_totals.map(totals => {
totals.map(total => {
class_id: total.class_id,
left_to_right: total.left_to_right,
right_to_left: total.right_to_left,
unique_left_ids: total.unique_left_ids.copy(),
unique_right_ids: total.unique_right_ids.copy(),
})
})
let working_regions = self.region_totals.map(total => {
entries: total.entries,
exits: total.exits,
unique_ids: total.unique_ids.copy(),
peak_occupancy: total.peak_occupancy,
completed_dwell_frames: total.completed_dwell_frames,
})
let working_region_classes = self.region_class_totals.map(totals => {
totals.map(total => {
class_id: total.class_id,
entries: total.entries,
exits: total.exits,
unique_ids: total.unique_ids.copy(),
peak_occupancy: total.peak_occupancy,
completed_dwell_frames: total.completed_dwell_frames,
})
})
let working_transitions : Array[TransitionTotals] = self.transition_totals.map(total => {
from_region_id: total.from_region_id,
to_region_id: total.to_region_id,
class_id: total.class_id,
count: total.count,
},
)
for id in lost {
guard find_track(working_tracks, id) is Some(index) else { continue }
for line_state in working_tracks[index].lines {
line_state.interrupt()
}
for region_state in working_tracks[index].regions {
region_state.interrupt()
}
working_tracks[index].last_exit_region = None
}
for id in removed {
working_removed.push(id)
}
let retained = working_tracks.filter(state => {
!contains_id(removed, state.track_id)
})
let ordered_samples = samples.copy()
ordered_samples.sort_by((left, right) => left.track_id.compare(right.track_id))
let events : Array[AnalyticsEvent] = []
for sample in ordered_samples {
let state_index = match find_track(retained, sample.track_id) {
Some(index) => index
None => {
retained.push(
new_track_state(sample, self.lines.length(), self.regions.length()),
)
retained.length() - 1
}
}
let state = retained[state_index]
let point = sample.anchor_point(self.config.anchor)
let event_start = events.length()
for line_index, line in self.lines {
if !line.accepts_class(state.class_id) {
continue
}
let class_totals = ensure_line_class_totals(
working_line_classes[line_index],
state.class_id,
)
advance_line(
state.lines[line_index],
line.classify(point),
self.config.stable_frames,
line.id,
state.track_id,
working_lines[line_index],
class_totals,
events,
)
}
for region_index, region in self.regions {
if !region.accepts_class(state.class_id) {
continue
}
let class_totals = ensure_region_class_totals(
working_region_classes[region_index],
state.class_id,
)
advance_region(
state.regions[region_index],
region.classify(point),
frame_id,
self.config.stable_frames,
region.id,
state.track_id,
working_regions[region_index],
class_totals,
events,
)
}
advance_transitions(state, events, event_start, working_transitions)
}
retained.sort_by((left, right) => left.track_id.compare(right.track_id))
working_removed.sort()
let visible_ids = ordered_samples.map(sample => sample.track_id)
let frame = make_frame(
frame_id,
self.lines,
self.regions,
retained,
visible_ids,
working_lines,
working_line_classes,
working_regions,
working_region_classes,
working_transitions,
events,
)
self.tracks = retained
self.removed_ids = working_removed
self.line_totals = working_lines
self.line_class_totals = working_line_classes
self.region_totals = working_regions
self.region_class_totals = working_region_classes
self.transition_totals = working_transitions
self.last_frame = Some(frame_id)
frame
}
///|
/// Accepts the visible and lifecycle output of an MBMOT tracker directly.
pub fn SpatialAnalyzer::update_mbmot(
self : SpatialAnalyzer,
frame_id : Int32,
frame_tracks : @mbmot.FrameTracks,
) -> AnalyticsFrame raise AnalyticsError {
self.update(
frame_id,
frame_tracks.tracks().map(TrackSample::from_track),
frame_tracks.lost(),
frame_tracks.removed(),
)
}
///|
/// Clears identities, counters, dwell state and the frame clock.
pub fn SpatialAnalyzer::reset(self : SpatialAnalyzer) -> Unit {
self.tracks = []
self.removed_ids = []
self.line_totals = self.lines.map(_ => {
left_to_right: 0,
right_to_left: 0,
unique_left_ids: [],
unique_right_ids: [],
})
self.line_class_totals = self.lines.map(_ => [])
self.region_totals = self.regions.map(_ => {
entries: 0,
exits: 0,
unique_ids: [],
peak_occupancy: 0,
completed_dwell_frames: 0,
})
self.region_class_totals = self.regions.map(_ => [])
self.transition_totals = []
self.last_frame = None
}