long_screen/kernels/track/
screen_fixed.rs

1//! Which parts of a moving region stay on screen while the region moves: a map's status bar, search bar, chips,
2//! watermark and buttons float over it, and a sticky header or side panel can sit inside a scrolling page. Their
3//! pixels match at zero offset on every frame, so the odometry's zero-offset hypothesis, the keyframe patches and
4//! relocalization all lock onto them and pull the pose back. Registration leaves these cells out; the output region
5//! and its ownership do not change.
6//!
7//! The evidence is the layer learner's stationary-versus-motion test (`kernels::layers::Learner::add`), taken on the
8//! steps the solve pass itself measured: at a sampled analysis pixel standing still explains the frame better than
9//! the measured step by more than [`MARGIN`] levels, or the reverse. A cell stayed in a frame when such pixels
10//! outnumber the ones that followed the step, and followed when the reverse holds.
11
12use crate::kernels::geometry::js_hypot;
13
14/// Side of a cell, in analysis pixels.
15pub const CELL: usize = 8;
16/// Analysis pixels a cell samples per axis (every second one).
17const SAMPLE: usize = 2;
18/// Grey levels by which one explanation must beat the other for the pixel to vote, as in `Learner::add`.
19const MARGIN: i32 = 6;
20/// A step shorter than this many analysis pixels does not separate staying from following on soft texture.
21pub const MIN_STEP: f64 = 2.0;
22/// Pixels of one kind a cell needs in a frame for its verdict that frame.
23const MIN_VOTES: u32 = 2;
24/// Frames in which a cell must have stayed while the region moved before registration leaves it out.
25const STAYED_FRAMES: u16 = 6;
26/// It must also have stayed this many times as often as it followed the region.
27const STAYED_RATIO: u16 = 4;
28/// A region more than this share of whose voting cells stayed is not a page with something floating over it: the
29/// measured steps belong to something inside it (a nested pane), and nothing is left out.
30const MAX_SHARE: f64 = 0.5;
31
32/// Per-cell evidence over one moving region's analysis rectangle.
33pub struct ScreenFixed {
34    x0: i64,
35    y0: i64,
36    cols: usize,
37    rows: usize,
38    stayed: Vec<u16>,
39    followed: Vec<u16>,
40    /// The cells registration leaves out (one cell of margin included); empty while none qualifies.
41    excluded: Vec<bool>,
42    any: bool,
43}
44
45impl ScreenFixed {
46    /// Cells over the analysis rectangle `[x0, x0 + width) × [y0, y0 + height)`.
47    pub fn new(x0: i64, y0: i64, width: usize, height: usize) -> ScreenFixed {
48        let (cols, rows) = (width.div_ceil(CELL).max(1), height.div_ceil(CELL).max(1));
49        ScreenFixed {
50            x0,
51            y0,
52            cols,
53            rows,
54            stayed: vec![0; cols * rows],
55            followed: vec![0; cols * rows],
56            excluded: Vec::new(),
57            any: false,
58        }
59    }
60
61    /// Whether any cell is left out.
62    pub fn any(&self) -> bool {
63        self.any
64    }
65
66    /// Whether registration leaves out analysis pixel (`x`, `y`).
67    pub fn excludes(&self, x: f64, y: f64) -> bool {
68        if !self.any {
69            return false;
70        }
71        let (cx, cy) = (
72            (x.floor() as i64 - self.x0).div_euclid(CELL as i64),
73            (y.floor() as i64 - self.y0).div_euclid(CELL as i64),
74        );
75        cx >= 0
76            && cy >= 0
77            && (cx as usize) < self.cols
78            && (cy as usize) < self.rows
79            && self.excluded[cy as usize * self.cols + cx as usize]
80    }
81
82    /// Adds one measured step. `previous`/`current` are `width`-wide analysis grays, `step` the region's step in
83    /// analysis pixels (content at (x, y) now was at (x + step.0, y + step.1) before), `inside` the region's
84    /// membership of an analysis pixel. Returns whether the set of left-out cells changed.
85    pub fn observe(
86        &mut self,
87        previous: &[u8],
88        current: &[u8],
89        width: usize,
90        height: usize,
91        step: (f64, f64),
92        inside: impl Fn(i64, i64) -> bool,
93    ) -> bool {
94        if js_hypot(step.0, step.1) < MIN_STEP {
95            return false;
96        }
97        let (w, h) = (width as i64, height as i64);
98        // A step that leaves no overlap (or is not a number) shows nothing about what stayed.
99        if !(step.0.abs() < w as f64 && step.1.abs() < h as f64) {
100            return false;
101        }
102        let (dx, dy) = (step.0.round() as i64, step.1.round() as i64);
103        for cy in 0..self.rows {
104            for cx in 0..self.cols {
105                let (mut fixed, mut moving) = (0u32, 0u32);
106                let (bx, by) = (self.x0 + (cx * CELL) as i64, self.y0 + (cy * CELL) as i64);
107                for y in (by..by + CELL as i64).step_by(SAMPLE) {
108                    for x in (bx..bx + CELL as i64).step_by(SAMPLE) {
109                        let (sx, sy) = (x + dx, y + dy);
110                        if x < 0
111                            || y < 0
112                            || x >= w
113                            || y >= h
114                            || sx < 0
115                            || sy < 0
116                            || sx >= w
117                            || sy >= h
118                            || !inside(x, y)
119                        {
120                            continue;
121                        }
122                        let c = current[(y * w + x) as usize] as i32;
123                        let still = (previous[(y * w + x) as usize] as i32 - c).abs();
124                        let followed = (previous[(sy * w + sx) as usize] as i32 - c).abs();
125                        if still + MARGIN < followed {
126                            fixed += 1;
127                        } else if followed + MARGIN < still {
128                            moving += 1;
129                        }
130                    }
131                }
132                let i = cy * self.cols + cx;
133                if fixed >= MIN_VOTES && fixed > moving {
134                    self.stayed[i] = self.stayed[i].saturating_add(1);
135                } else if moving >= MIN_VOTES && moving > fixed {
136                    self.followed[i] = self.followed[i].saturating_add(1);
137                }
138            }
139        }
140        self.settle()
141    }
142
143    fn settle(&mut self) -> bool {
144        let qualifies = |i: usize| {
145            self.stayed[i] >= STAYED_FRAMES
146                && self.stayed[i] >= STAYED_RATIO.saturating_mul(self.followed[i])
147        };
148        let (mut core, mut voting) = (0usize, 0usize);
149        for i in 0..self.stayed.len() {
150            if self.stayed[i] > 0 || self.followed[i] > 0 {
151                voting += 1;
152            }
153            if qualifies(i) {
154                core += 1;
155            }
156        }
157        let mut excluded = Vec::new();
158        if core > 0 && (core as f64) <= MAX_SHARE * voting as f64 {
159            excluded = vec![false; self.stayed.len()];
160            for cy in 0..self.rows {
161                for cx in 0..self.cols {
162                    if !qualifies(cy * self.cols + cx) {
163                        continue;
164                    }
165                    for ny in cy.saturating_sub(1)..(cy + 2).min(self.rows) {
166                        for nx in cx.saturating_sub(1)..(cx + 2).min(self.cols) {
167                            excluded[ny * self.cols + nx] = true;
168                        }
169                    }
170                }
171            }
172        }
173        let any = !excluded.is_empty();
174        let changed = excluded != self.excluded;
175        self.excluded = excluded;
176        self.any = any;
177        changed
178    }
179}
180
181#[cfg(test)]
182mod tests {
183    use super::*;
184
185    const W: usize = 96;
186    const H: usize = 96;
187
188    /// Hashed texture of world pixel (x, y).
189    fn texture(x: i64, y: i64) -> u8 {
190        let v = (x.wrapping_mul(73_856_093) ^ y.wrapping_mul(19_349_663)) as u64;
191        (v.wrapping_mul(0x9E37_79B9_7F4A_7C15) >> 56) as u8
192    }
193
194    /// A page scrolled by `offset` rows, with rows `[0, bar)` a textured bar that stays on screen and rows
195    /// `[bar, flat)` a flat bar that stays.
196    fn frame(offset: i64, bar: usize, flat: usize) -> Vec<u8> {
197        let mut out = vec![0u8; W * H];
198        for y in 0..H {
199            for x in 0..W {
200                out[y * W + x] = if y < bar {
201                    texture(x as i64 + 5000, y as i64)
202                } else if y < flat {
203                    200
204                } else {
205                    texture(x as i64, y as i64 + offset)
206                };
207            }
208        }
209        out
210    }
211
212    fn run(frames: usize, step: i64, bar: usize, flat: usize) -> ScreenFixed {
213        let mut s = ScreenFixed::new(0, 0, W, H);
214        for k in 0..frames as i64 {
215            let (a, b) = (frame(k * step, bar, flat), frame((k + 1) * step, bar, flat));
216            // Content now at y was at y + step before.
217            s.observe(&a, &b, W, H, (0.0, step as f64), |_, _| true);
218        }
219        s
220    }
221
222    // Failure case: a textured bar that stays while the page scrolls under it is registered with the page.
223    #[test]
224    fn a_textured_bar_that_stays_is_left_out_and_the_page_is_not() {
225        let s = run(STAYED_FRAMES as usize, 5, 16, 16);
226        assert!(s.any());
227        assert!(s.excludes(40.0, 4.0));
228        assert!(s.excludes(40.0, 15.0));
229        // One cell of margin below the bar, nothing further down.
230        assert!(s.excludes(40.0, 20.0));
231        assert!(!s.excludes(40.0, 30.0));
232        assert!(!s.excludes(40.0, 90.0));
233    }
234
235    // Failure case: one frame's coincidence leaves a cell out.
236    #[test]
237    fn a_bar_is_left_out_only_after_enough_frames() {
238        let s = run(STAYED_FRAMES as usize - 1, 5, 16, 16);
239        assert!(!s.any());
240        assert!(!s.excludes(40.0, 4.0));
241    }
242
243    // Failure case: a step within analysis jitter casts votes.
244    #[test]
245    fn a_short_step_casts_no_votes() {
246        let s = run(3 * STAYED_FRAMES as usize, 1, 16, 16);
247        assert!(!s.any());
248    }
249
250    // Failure case: flat chrome (or blank page) counts as staying; it holds no texture to pull a match. Only its
251    // edge against the page does, and that edge is left out.
252    #[test]
253    fn a_flat_bar_is_left_out_only_at_its_edge() {
254        let s = run(3 * STAYED_FRAMES as usize, 5, 0, 48);
255        assert!(!s.excludes(40.0, 8.0));
256        assert!(!s.excludes(40.0, 24.0));
257        assert!(s.excludes(40.0, 44.0));
258        assert!(!s.excludes(40.0, 70.0));
259    }
260
261    // Failure case: when most of the region stays, the steps belong to something inside it, which must not be
262    // registered alone.
263    #[test]
264    fn a_region_that_mostly_stays_leaves_nothing_out() {
265        let s = run(3 * STAYED_FRAMES as usize, 5, 64, 64);
266        assert!(!s.any());
267        assert!(!s.excludes(40.0, 4.0));
268    }
269
270    // Failure case: a cell that follows the page about as often as it stays (a header that scrolls away, then
271    // sticks) is left out.
272    #[test]
273    fn a_cell_that_also_follows_the_page_is_kept() {
274        let mut s = ScreenFixed::new(0, 0, W, H);
275        for k in 0..STAYED_FRAMES as i64 {
276            let (a, b) = (frame(k * 5, 16, 16), frame((k + 1) * 5, 16, 16));
277            s.observe(&a, &b, W, H, (0.0, 5.0), |_, _| true);
278        }
279        assert!(s.excludes(40.0, 4.0));
280        // Now the whole frame follows the page for two frames: the bar's cells followed twice.
281        for k in 0..2i64 {
282            let a: Vec<u8> = (0..W * H)
283                .map(|i| texture((i % W) as i64, (i / W) as i64 + k * 5))
284                .collect();
285            let b: Vec<u8> = (0..W * H)
286                .map(|i| texture((i % W) as i64, (i / W) as i64 + (k + 1) * 5))
287                .collect();
288            s.observe(&a, &b, W, H, (0.0, 5.0), |_, _| true);
289        }
290        assert!(!s.excludes(40.0, 4.0));
291    }
292
293    // Failure case: a step past the frame (an out-of-range pose) overflows the shifted index.
294    #[test]
295    fn a_step_without_overlap_casts_no_votes() {
296        let mut s = ScreenFixed::new(0, 0, W, H);
297        let (a, b) = (frame(0, 16, 16), frame(5, 16, 16));
298        for step in [(0.0, 1e300), (f64::NAN, 0.0), (W as f64, 0.0)] {
299            assert!(!s.observe(&a, &b, W, H, step, |_, _| true));
300        }
301        assert!(!s.any());
302    }
303
304    // Failure case: pixels outside the region vote for it.
305    #[test]
306    fn pixels_outside_the_region_cast_no_votes() {
307        let mut s = ScreenFixed::new(0, 0, W, H);
308        for k in 0..3 * STAYED_FRAMES as i64 {
309            let (a, b) = (frame(k * 5, 16, 16), frame((k + 1) * 5, 16, 16));
310            s.observe(&a, &b, W, H, (0.0, 5.0), |_, y| y >= 16);
311        }
312        assert!(!s.any());
313    }
314}
long_screen/kernels/track/screen_fixed.rs

long_screen/kernels/track/
screen_fixed.rs
