Skip to main content

docling_pdf/
ocr_det.rs

1//! PP-OCR text *detection* for bitmap pages (#429): the DB (Differentiable
2//! Binarization) detector RapidOCR runs in front of its recognizer, ported so
3//! text the layout model gives no region — a diagram's labels, a chart's
4//! ticks, a stamp, a page number in the margin — is still read.
5//!
6//! The pipeline's OCR has always been *recognition-only*: PP-OCRv3 rec runs
7//! on the lines inside layout regions, and nothing else on a page is looked
8//! at. docling's engines (RapidOCR, EasyOCR, Tesseract) instead detect text
9//! lines over the whole bitmap and every detected line becomes a cell — the
10//! ones no layout cluster claims turn into orphan text clusters (confidence
11//! 1.0) and read out in the flow. `ModalNet-19.png` shows the gap: the layout
12//! model scores only `SoftMax` above its 0.5 threshold (docling's own layout
13//! run yields *zero* clusters there), yet docling reads `MatMul`, `SoftMax`,
14//! `Mask (opt.)`, `Scale`, `Q`, `K` — all from its detector.
15//!
16//! Model: RapidOCR's `PP-OCRv6_det_small.onnx` (the one docling 2.127's
17//! RapidOCR default resolves to; `.models/ocr_det.onnx`, `DOCLING_OCR_DET_ONNX`
18//! overrides). Pre/post-processing follow `rapidocr/ch_ppocr_det`
19//! (`DetPreProcess` / `DBPostProcess`) with RapidOCR's config: shorter side
20//! scaled up to 736 (`limit_type: min`), sides rounded to multiples of 32,
21//! BGR channel order (cv2 input), `(x/255 − 0.5)/0.5`; probability threshold
22//! 0.3, 2×2 dilation, per-blob minimum-area rectangle, `box_score_fast` ≥ 0.5,
23//! unclip ratio 1.6, RapidOCR's row-then-column box order. Two deliberate
24//! simplifications: only outer blob boundaries are considered (OpenCV's
25//! `RETR_LIST` also walks hole contours, whose boxes fail the score gate
26//! anyway), and a detected quad is handed on as its axis-aligned bounding
27//! box — the recognizer's line prep crops rectangles, and rotated lines are
28//! not what documents lose today. The quad rides along on [`DetBox::quad`]:
29//! with `ocr_textline_orientation` on (#666) the line prep warps it upright
30//! the way RapidOCR's `get_rotate_crop_image` does.
31//!
32//! Since #570 the detector is also the recognizer's *line source* inside the
33//! layout regions (`ocr_prep::prep_region_lines_det`), as it is for RapidOCR:
34//! the projection split that preceded it cut a region into full-width strips,
35//! which on forms — several fields per baseline — glued and dropped words
36//! (FUNSD word recall 0.57 → 0.68 on this change alone; `DOCLING_RS_OCR_LINES=
37//! projection` restores the strips). Detected boxes outside every region are
38//! still recognized and placed as orphan text (`uncovered_lines`). Missing
39//! model → no detection, quietly (`DOCLING_RS_DEBUG` reports it): regions
40//! fall back to the projection split, the margins go unread.
41
42use image::RgbImage;
43
44/// RapidOCR `Det.limit_side_len` with `limit_type: min`.
45pub const LIMIT_SIDE_LEN: u32 = 736;
46/// `DBPostProcess(thresh=…)`: probability → binary mask.
47pub const THRESH: f32 = 0.3;
48/// `DBPostProcess(box_thresh=…)`: minimum mean probability inside a box.
49pub const BOX_THRESH: f32 = 0.5;
50/// `DBPostProcess(unclip_ratio=…)`.
51pub const UNCLIP_RATIO: f32 = 1.6;
52/// `DBPostProcess.min_size`: the shortest side a blob's rectangle may have.
53const MIN_SIZE: f32 = 3.0;
54/// `TextDetector._BOX_SORT_Y_THRESHOLD`: boxes whose top-left `y` differ by
55/// less than this share a row when ordering.
56const BOX_SORT_Y_THRESHOLD: f32 = 10.0;
57
58/// One detected text line: its axis-aligned box in *input image pixels* and
59/// the DB score (mean probability inside the pre-unclip rectangle).
60#[derive(Debug, Clone, Copy, PartialEq)]
61pub struct DetBox {
62    pub l: f32,
63    pub t: f32,
64    pub r: f32,
65    pub b: f32,
66    pub score: f32,
67    /// The detector's (unclipped) minimum-area rectangle the box bounds,
68    /// `[tl, tr, br, bl]` in the same pixels (#666) — what RapidOCR crops.
69    pub quad: [(f32, f32); 4],
70}
71
72impl DetBox {
73    /// An axis-aligned box, its quad the rectangle itself.
74    pub fn rect(l: f32, t: f32, r: f32, b: f32, score: f32) -> Self {
75        Self {
76            l,
77            t,
78            r,
79            b,
80            score,
81            quad: [(l, t), (r, t), (r, b), (l, b)],
82        }
83    }
84}
85
86/// `DetPreProcess.resize`: the network input size for a `w × h` image —
87/// shorter side scaled up to [`LIMIT_SIDE_LEN`] (never down), both sides
88/// rounded to a multiple of 32. `None` when a side rounds to zero.
89pub fn det_input_size(w: u32, h: u32) -> Option<(u32, u32)> {
90    det_input_size_capped(w, h, max_side_cap())
91}
92
93/// Default cap on the detector input's longer side: RapidOCR's
94/// `Global.max_side_len` (2000) — the longest side its whole OCR input is
95/// shrunk to before detection, and so what docling's detector sees. Until
96/// #570 this was PaddleOCR's 960 (`det_limit_side_len`, `limit_type: max`):
97/// while the detector only supplemented the region pass that cost about a
98/// third of the detection time and moved outputs by noise-level amounts;
99/// now that its boxes are the recognizer's crops the resolution is recall —
100/// 960 reads 0.834 of FUNSD's words where 2000 reads 0.856 (30 forms, same
101/// recognizer). A Letter page at the 2.0 px/pt render goes in at 1216 ×
102/// 1600; `DOCLING_RS_OCR_DET_MAX_SIDE=0` lifts the cap entirely, 960 restores
103/// the old budget.
104pub const DEFAULT_MAX_SIDE: u32 = 2000;
105
106/// `DOCLING_RS_OCR_DET_MAX_SIDE`: the cap on the detector input's longer
107/// side — [`DEFAULT_MAX_SIDE`] unless set, `0` = uncapped (RapidOCR's rule).
108/// The DB net is the costliest OCR stage on a scanned page and its cost is
109/// linear in input pixels; a tighter cap trades small-print recall for time.
110pub(crate) fn max_side_cap() -> u32 {
111    static CAP: std::sync::OnceLock<u32> = std::sync::OnceLock::new();
112    *CAP.get_or_init(|| {
113        docling_core::env::parse::<u32>("DOCLING_RS_OCR_DET_MAX_SIDE").unwrap_or(DEFAULT_MAX_SIDE)
114    })
115}
116
117/// The text-size-aware detector budget for a scanned page (#945): the
118/// longer-side cap under which the page's small print still lands at
119/// [`BUDGET_LINE_PX`] in the detector input. `line_px` is the page's 25th
120/// percentile text-line height in its own pixels ([`line_height_p25`]) —
121/// the small print, not the headings, sets the budget; `None` (no lines
122/// found: a blank or noise page) and lines already at or under the target
123/// keep the full `cap` (FUNSD's 72-dpi forms, whose 8–10 px lines are why
124/// #570 raised the cap, stay at it). The result never drops under
125/// [`BUDGET_FLOOR`] — the pre-#570 budget, the known worst case (−0.02 FUNSD
126/// recall) — nor over `cap` (`0` = RapidOCR's uncapped rule: no upscale past
127/// the page's own longer side).
128///
129/// Why: the DB net's cost and arena are linear in input pixels, and a 2 px/pt
130/// render of 12–15 pt text (a typewritten letter, a form's print) shows
131/// 24–30 px lines where [`BUDGET_LINE_PX`] reads identically (the scanned
132/// PDF fixtures' Markdown is byte-identical) — paying the 2000 px budget
133/// there bought nothing and cost ~2× the time and +250 MB per worker.
134/// Standalone images (read at docling's 3 px/pt effective resolution, #570)
135/// are not budgeted by the caller: their OCR output moved under any input
136/// change, and their baselines are pinned to the cap.
137pub fn scan_budget(w: u32, h: u32, line_px: Option<f32>, cap: u32) -> u32 {
138    let longer = w.max(h);
139    let upper = if cap == 0 { longer } else { cap };
140    // A page whose shorter side RapidOCR's rule would *upscale* (a wide
141    // figure PDF, a strip) is not budgeted: its output moved under any
142    // input change, the upscale and the cap interact, and it is small.
143    if w.min(h) < LIMIT_SIDE_LEN {
144        return upper;
145    }
146    let Some(line) = line_px.filter(|l| *l > BUDGET_LINE_PX) else {
147        return upper;
148    };
149    let floor = BUDGET_FLOOR.min(upper);
150    ((longer as f32 * BUDGET_LINE_PX / line).round() as u32).clamp(floor, upper)
151}
152
153/// [`scan_budget`]'s target: the text-line height (px) the detector input
154/// keeps for the page's small print. Conservative on purpose: the scanned
155/// PDF fixtures read byte-identically with their 23–30 px lines brought to
156/// 20 (and, for the 30 px ones, down to the 960 floor), while at 12 — which
157/// the three plainest scans also tolerated — the paper scanned as a TIFF
158/// and the figure images drifted at character level (mixed, not better or
159/// worse); below ~10 px the DB net starts missing words (the FUNSD finding
160/// of #570).
161pub const BUDGET_LINE_PX: f32 = 20.0;
162
163/// [`scan_budget`]'s floor: the pre-#570 960 px longer side.
164pub const BUDGET_FLOOR: u32 = 960;
165
166/// The 25th-percentile height of the text lines a horizontal ink-projection
167/// split ([`crate::ocr_prep::segment_lines`]) finds on `img`, in its pixels;
168/// `None` under four lines. The small-print quantile, so a page with
169/// headings or a few tall rows still budgets for its body text.
170pub fn line_height_p25(img: &RgbImage) -> Option<f32> {
171    let mut heights: Vec<u32> = crate::ocr_prep::segment_lines(img)
172        .into_iter()
173        .map(|(_, t, _, b)| b - t)
174        .collect();
175    if heights.len() < 4 {
176        return None;
177    }
178    heights.sort_unstable();
179    Some(heights[heights.len() / 4] as f32)
180}
181
182/// `DOCLING_RS_OCR_DET_BUDGET` (#945): `auto` (default) — a scanned page's
183/// detector input follows [`scan_budget`]; `full` — always the cap, the
184/// pre-#945 behavior.
185pub fn budget_enabled() -> bool {
186    static ON: std::sync::OnceLock<bool> = std::sync::OnceLock::new();
187    *ON.get_or_init(|| {
188        !matches!(
189            docling_core::env::nonempty("DOCLING_RS_OCR_DET_BUDGET").as_deref(),
190            Some("full")
191        )
192    })
193}
194
195/// [`det_input_size`] with an explicit longer-side cap (`0` = none): the cap
196/// scales the image down first, then RapidOCR's shorter-side rule applies to
197/// what is left (so a capped input never exceeds the cap).
198pub fn det_input_size_capped(w: u32, h: u32, max_side: u32) -> Option<(u32, u32)> {
199    if w == 0 || h == 0 {
200        return None;
201    }
202    let (w, h) = (w as f32, h as f32);
203    // RapidOCR's rule first (shorter side up to 736, never down), then the
204    // cap pulls the longer side back if that overshoots it.
205    let mut ratio = if w.min(h) < LIMIT_SIDE_LEN as f32 {
206        LIMIT_SIDE_LEN as f32 / w.min(h)
207    } else {
208        1.0
209    };
210    if max_side > 0 && w.max(h) * ratio > max_side as f32 {
211        ratio = max_side as f32 / w.max(h);
212    }
213    let round32 = |v: f32| ((v as i64 as f32 / 32.0).round() * 32.0) as i64;
214    let (rw, rh) = (round32(w * ratio), round32(h * ratio));
215    (rw > 0 && rh > 0).then_some((rw as u32, rh as u32))
216}
217
218/// The NCHW float input for the detector: the image resized to
219/// [`det_input_size`] (bilinear, cv2's default), channels in **BGR** order
220/// (RapidOCR feeds a cv2 image), normalized `(x/255 − 0.5)/0.5`. Returns the
221/// tensor and its `(width, height)`.
222pub fn prep_det_input(img: &RgbImage) -> Option<(Vec<f32>, u32, u32)> {
223    let size = det_input_size(img.width(), img.height())?;
224    Some(prep_det_input_to(img, size))
225}
226
227/// The network input size for a *crop* of a page — a layout region the text
228/// layer leaves empty (#931), detected on its own instead of on the whole
229/// page (#945): the crop at its own pixels (a 2 px/pt render already shows
230/// body text 16–20 px tall, the DB net's range — RapidOCR's shorter-side
231/// upscale to 736 is for whole pages and would blow a one-line crop up to
232/// the 2000 px cap), each side rounded up to a multiple of 32 (min 32), the
233/// longer side scaled down to `max_side` (0 = no cap) when it exceeds it.
234pub fn det_crop_size(w: u32, h: u32, max_side: u32) -> Option<(u32, u32)> {
235    if w == 0 || h == 0 {
236        return None;
237    }
238    let (mut fw, mut fh) = (w as f32, h as f32);
239    if max_side > 0 && fw.max(fh) > max_side as f32 {
240        let f = max_side as f32 / fw.max(fh);
241        fw *= f;
242        fh *= f;
243    }
244    let up32 = |v: f32| ((v / 32.0).ceil() as u32).max(1) * 32;
245    Some((up32(fw), up32(fh)))
246}
247
248/// [`prep_det_input`] at an explicit `(width, height)`.
249pub fn prep_det_input_to(img: &RgbImage, (w, h): (u32, u32)) -> (Vec<f32>, u32, u32) {
250    let resized = if (w, h) == img.dimensions() {
251        img.clone()
252    } else {
253        resize_bilinear(img, w, h)
254    };
255    let n = (w * h) as usize;
256    let mut data = vec![0f32; 3 * n];
257    for (i, px) in resized.pixels().enumerate() {
258        // B, G, R planes.
259        data[i] = px[2] as f32 / 127.5 - 1.0;
260        data[n + i] = px[1] as f32 / 127.5 - 1.0;
261        data[2 * n + i] = px[0] as f32 / 127.5 - 1.0;
262    }
263    (data, w, h)
264}
265
266/// Translate boxes detected on a crop at `(dx, dy)` back onto the page.
267pub fn offset_boxes(mut boxes: Vec<DetBox>, dx: f32, dy: f32) -> Vec<DetBox> {
268    for b in &mut boxes {
269        b.l += dx;
270        b.r += dx;
271        b.t += dy;
272        b.b += dy;
273        for (x, y) in &mut b.quad {
274            *x += dx;
275            *y += dy;
276        }
277    }
278    boxes
279}
280
281/// Bilinear resize (cv2's default `INTER_LINEAR`) — `fast_image_resize`'s SIMD
282/// convolution with the triangle kernel, the scalar `image` crate resize with
283/// `DOCLING_RS_SLOW_RESIZE=1` (same kernel, several times slower; the
284/// scalar path is also the fallback should the SIMD one refuse the buffer).
285pub(crate) fn resize_bilinear(img: &RgbImage, w: u32, h: u32) -> RgbImage {
286    #[cfg(feature = "ml")]
287    {
288        use fast_image_resize as fir;
289        static SLOW: std::sync::OnceLock<bool> = std::sync::OnceLock::new();
290        let slow = *SLOW.get_or_init(|| docling_core::env::flag("DOCLING_RS_SLOW_RESIZE"));
291        if !slow {
292            let fast = || {
293                let src = fir::images::ImageRef::new(
294                    img.width(),
295                    img.height(),
296                    img.as_raw(),
297                    fir::PixelType::U8x3,
298                )
299                .ok()?;
300                let mut dst = fir::images::Image::new(w, h, fir::PixelType::U8x3);
301                fir::Resizer::new()
302                    .resize(
303                        &src,
304                        &mut dst,
305                        &fir::ResizeOptions::new()
306                            .resize_alg(fir::ResizeAlg::Convolution(fir::FilterType::Bilinear)),
307                    )
308                    .ok()?;
309                RgbImage::from_raw(w, h, dst.into_vec())
310            };
311            if let Some(out) = fast() {
312                return out;
313            }
314        }
315    }
316    image::imageops::resize(img, w, h, image::imageops::FilterType::Triangle)
317}
318
319/// `DBPostProcess.__call__`: text boxes from the detector's `w × h`
320/// probability map, mapped onto a `dest_w × dest_h` image (the one the map was
321/// computed from). Boxes come back in RapidOCR's reading order.
322pub fn db_boxes(prob: &[f32], w: usize, h: usize, dest_w: u32, dest_h: u32) -> Vec<DetBox> {
323    if prob.len() < w * h || w == 0 || h == 0 {
324        return Vec::new();
325    }
326    // Binarize, then dilate with a 2×2 kernel (cv2.dilate, anchor at the
327    // kernel center = its bottom-right cell, so a pixel lights up when it or
328    // its left / upper / upper-left neighbour is set).
329    let seg = |x: usize, y: usize| prob[y * w + x] > THRESH;
330    let mut mask = vec![false; w * h];
331    for y in 0..h {
332        for x in 0..w {
333            mask[y * w + x] = seg(x, y)
334                || (x > 0 && seg(x - 1, y))
335                || (y > 0 && seg(x, y - 1))
336                || (x > 0 && y > 0 && seg(x - 1, y - 1));
337        }
338    }
339    let mut quads: Vec<([(f32, f32); 4], f32)> = Vec::new();
340    let mut seen = vec![false; w * h];
341    let mut stack = Vec::new();
342    let mut component = Vec::new();
343    for start in 0..w * h {
344        if !mask[start] || seen[start] {
345            continue;
346        }
347        // 8-connected blob (cv2.findContours' outer boundary connectivity).
348        component.clear();
349        seen[start] = true;
350        stack.push(start);
351        while let Some(i) = stack.pop() {
352            component.push(i);
353            let (x, y) = (i % w, i / w);
354            for dy in -1i64..=1 {
355                for dx in -1i64..=1 {
356                    let (nx, ny) = (x as i64 + dx, y as i64 + dy);
357                    if nx < 0 || ny < 0 || nx >= w as i64 || ny >= h as i64 {
358                        continue;
359                    }
360                    let j = ny as usize * w + nx as usize;
361                    if mask[j] && !seen[j] {
362                        seen[j] = true;
363                        stack.push(j);
364                    }
365                }
366            }
367        }
368        if quads.len() >= 1000 {
369            // `max_candidates`.
370            break;
371        }
372        // The contour points are pixel centers on the blob's boundary; the
373        // minimum-area rectangle of the boundary is that of the whole blob.
374        let boundary: Vec<(f32, f32)> = component
375            .iter()
376            .copied()
377            .filter(|&i| {
378                let (x, y) = (i % w, i / w);
379                x == 0
380                    || y == 0
381                    || x + 1 == w
382                    || y + 1 == h
383                    || !mask[i - 1]
384                    || !mask[i + 1]
385                    || !mask[i - w]
386                    || !mask[i + w]
387            })
388            .map(|i| ((i % w) as f32, (i / w) as f32))
389            .collect();
390        let Some((corners, sside)) = min_area_rect(&boundary) else {
391            continue;
392        };
393        if sside < MIN_SIZE {
394            continue;
395        }
396        let score = box_score_fast(prob, w, h, &corners);
397        if score < BOX_THRESH {
398            continue;
399        }
400        let Some((expanded, sside)) = unclip(&corners) else {
401            continue;
402        };
403        if sside < MIN_SIZE + 2.0 {
404            continue;
405        }
406        // Into the source image's pixel grid.
407        let mapped: [(f32, f32); 4] = std::array::from_fn(|k| {
408            let (x, y) = expanded[k];
409            (
410                (x / w as f32 * dest_w as f32)
411                    .round()
412                    .clamp(0.0, dest_w as f32),
413                (y / h as f32 * dest_h as f32)
414                    .round()
415                    .clamp(0.0, dest_h as f32),
416            )
417        });
418        quads.push((mapped, score));
419    }
420    // `filter_det_res`: drop boxes whose rectangle is ≤ 3 px on a side.
421    let mut boxes: Vec<DetBox> = quads
422        .into_iter()
423        .filter_map(|(q, score)| {
424            let side =
425                |a: (f32, f32), b: (f32, f32)| ((a.0 - b.0).powi(2) + (a.1 - b.1).powi(2)).sqrt();
426            let (rw, rh) = (side(q[0], q[1]).floor(), side(q[0], q[3]).floor());
427            if rw <= 3.0 || rh <= 3.0 {
428                return None;
429            }
430            let xs = q.iter().map(|p| p.0);
431            let ys = q.iter().map(|p| p.1);
432            Some(DetBox {
433                l: xs.clone().fold(f32::MAX, f32::min),
434                t: ys.clone().fold(f32::MAX, f32::min),
435                r: xs.fold(f32::MIN, f32::max),
436                b: ys.fold(f32::MIN, f32::max),
437                score,
438                quad: q,
439            })
440        })
441        .collect();
442    sort_boxes(&mut boxes);
443    boxes
444}
445
446/// `TextDetector.sorted_boxes`: by top edge, then a bubble pass that swaps
447/// *adjacent* boxes whose tops lie within [`BOX_SORT_Y_THRESHOLD`] when the
448/// lower one starts further left — RapidOCR's exact algorithm. The first
449/// port (#429) grouped boxes into rows transitively (consecutive tops within
450/// the threshold = one row) and sorted each row by `x`; on a two-column
451/// newspaper every line top is within 10 px of the next line's in the other
452/// column, the whole page chained into one "row", and the lines of a column
453/// came out ordered by their left edge — scrambled — once they became the
454/// recognizer's crops (#570). RapidOCR's local swaps only reorder boxes that
455/// genuinely share a baseline.
456pub fn sort_boxes(boxes: &mut [DetBox]) {
457    boxes.sort_by(|a, b| a.t.total_cmp(&b.t).then(a.l.total_cmp(&b.l)));
458    for i in 0..boxes.len().saturating_sub(1) {
459        let mut j = i;
460        loop {
461            let (upper, lower) = (j, j + 1);
462            if (boxes[lower].t - boxes[upper].t).abs() < BOX_SORT_Y_THRESHOLD
463                && boxes[lower].l < boxes[upper].l
464            {
465                boxes.swap(upper, lower);
466            } else {
467                break;
468            }
469            if j == 0 {
470                break;
471            }
472            j -= 1;
473        }
474    }
475}
476
477/// A candidate enclosing rectangle: its area, corners and shorter side.
478type RectCandidate = (f32, [(f32, f32); 4], f32);
479
480/// `cv2.minAreaRect` over a point set (rotating calipers on the convex hull):
481/// the four corners of the smallest enclosing rectangle and its shorter side,
482/// in the order `get_mini_boxes` returns (top-left, top-right, bottom-right,
483/// bottom-left, for an upright box). `None` for fewer than one point.
484pub fn min_area_rect(points: &[(f32, f32)]) -> Option<([(f32, f32); 4], f32)> {
485    let hull = convex_hull(points);
486    if hull.is_empty() {
487        return None;
488    }
489    if hull.len() <= 2 {
490        // A single pixel or a straight run: a degenerate rectangle along it.
491        let (a, b) = (hull[0], *hull.last().unwrap());
492        return Some((order_corners([a, b, b, a]), 0.0));
493    }
494    let mut best: Option<RectCandidate> = None;
495    for i in 0..hull.len() {
496        let (p, q) = (hull[i], hull[(i + 1) % hull.len()]);
497        let (ex, ey) = (q.0 - p.0, q.1 - p.1);
498        let len = (ex * ex + ey * ey).sqrt();
499        if len < 1e-6 {
500            continue;
501        }
502        let (ux, uy) = (ex / len, ey / len);
503        let (vx, vy) = (-uy, ux);
504        let (mut umin, mut umax, mut vmin, mut vmax) = (f32::MAX, f32::MIN, f32::MAX, f32::MIN);
505        for &(x, y) in &hull {
506            let u = x * ux + y * uy;
507            let v = x * vx + y * vy;
508            umin = umin.min(u);
509            umax = umax.max(u);
510            vmin = vmin.min(v);
511            vmax = vmax.max(v);
512        }
513        let area = (umax - umin) * (vmax - vmin);
514        if best.as_ref().is_none_or(|(a, _, _)| area < *a) {
515            let corner = |u: f32, v: f32| (u * ux + v * vx, u * uy + v * vy);
516            let corners = [
517                corner(umin, vmin),
518                corner(umax, vmin),
519                corner(umax, vmax),
520                corner(umin, vmax),
521            ];
522            best = Some((area, corners, (umax - umin).min(vmax - vmin)));
523        }
524    }
525    best.map(|(_, corners, sside)| (order_corners(corners), sside))
526}
527
528/// `get_mini_boxes`' corner order: sort by x, then the left pair top-first and
529/// the right pair top-first → `[tl, tr, br, bl]`.
530pub(crate) fn order_corners(mut c: [(f32, f32); 4]) -> [(f32, f32); 4] {
531    c.sort_by(|a, b| a.0.total_cmp(&b.0));
532    let (i1, i4) = if c[1].1 > c[0].1 { (0, 1) } else { (1, 0) };
533    let (i2, i3) = if c[3].1 > c[2].1 { (2, 3) } else { (3, 2) };
534    [c[i1], c[i2], c[i3], c[i4]]
535}
536
537/// Andrew's monotone chain; counter-clockwise, no collinear duplicates.
538fn convex_hull(points: &[(f32, f32)]) -> Vec<(f32, f32)> {
539    let mut pts: Vec<(f32, f32)> = points.to_vec();
540    pts.sort_by(|a, b| a.0.total_cmp(&b.0).then(a.1.total_cmp(&b.1)));
541    pts.dedup();
542    if pts.len() < 3 {
543        return pts;
544    }
545    let cross = |o: (f32, f32), a: (f32, f32), b: (f32, f32)| {
546        (a.0 - o.0) * (b.1 - o.1) - (a.1 - o.1) * (b.0 - o.0)
547    };
548    let mut lower: Vec<(f32, f32)> = Vec::new();
549    for &p in &pts {
550        while lower.len() >= 2 && cross(lower[lower.len() - 2], lower[lower.len() - 1], p) <= 0.0 {
551            lower.pop();
552        }
553        lower.push(p);
554    }
555    let mut upper: Vec<(f32, f32)> = Vec::new();
556    for &p in pts.iter().rev() {
557        while upper.len() >= 2 && cross(upper[upper.len() - 2], upper[upper.len() - 1], p) <= 0.0 {
558            upper.pop();
559        }
560        upper.push(p);
561    }
562    lower.pop();
563    upper.pop();
564    lower.extend(upper);
565    lower
566}
567
568/// `box_score_fast`: mean probability over the pixels inside the rectangle
569/// (a convex quad — the pixel-center test replaces `cv2.fillPoly`).
570fn box_score_fast(prob: &[f32], w: usize, h: usize, quad: &[(f32, f32); 4]) -> f32 {
571    let xmin = quad
572        .iter()
573        .map(|p| p.0)
574        .fold(f32::MAX, f32::min)
575        .floor()
576        .clamp(0.0, (w - 1) as f32) as usize;
577    let xmax = quad
578        .iter()
579        .map(|p| p.0)
580        .fold(f32::MIN, f32::max)
581        .ceil()
582        .clamp(0.0, (w - 1) as f32) as usize;
583    let ymin = quad
584        .iter()
585        .map(|p| p.1)
586        .fold(f32::MAX, f32::min)
587        .floor()
588        .clamp(0.0, (h - 1) as f32) as usize;
589    let ymax = quad
590        .iter()
591        .map(|p| p.1)
592        .fold(f32::MIN, f32::max)
593        .ceil()
594        .clamp(0.0, (h - 1) as f32) as usize;
595    let (mut sum, mut n) = (0f64, 0usize);
596    for y in ymin..=ymax {
597        for x in xmin..=xmax {
598            if inside_convex(quad, (x as f32, y as f32)) {
599                sum += prob[y * w + x] as f64;
600                n += 1;
601            }
602        }
603    }
604    if n == 0 {
605        0.0
606    } else {
607        (sum / n as f64) as f32
608    }
609}
610
611/// Point-in-convex-polygon (boundary counts as inside), any winding.
612fn inside_convex(quad: &[(f32, f32); 4], p: (f32, f32)) -> bool {
613    let mut pos = false;
614    let mut neg = false;
615    for i in 0..4 {
616        let (a, b) = (quad[i], quad[(i + 1) % 4]);
617        let cross = (b.0 - a.0) * (p.1 - a.1) - (b.1 - a.1) * (p.0 - a.0);
618        pos |= cross > 1e-6;
619        neg |= cross < -1e-6;
620    }
621    !(pos && neg)
622}
623
624/// `unclip` + `get_mini_boxes`: grow the rectangle outward by
625/// `area · unclip_ratio / perimeter` (the polygon offset of a rectangle is a
626/// rounded rectangle whose minimum-area rectangle is the original grown by
627/// the offset on every side). Returns the corners and the shorter side.
628fn unclip(quad: &[(f32, f32); 4]) -> Option<([(f32, f32); 4], f32)> {
629    let side = |a: (f32, f32), b: (f32, f32)| ((a.0 - b.0).powi(2) + (a.1 - b.1).powi(2)).sqrt();
630    let (wlen, hlen) = (side(quad[0], quad[1]), side(quad[1], quad[2]));
631    let perimeter = 2.0 * (wlen + hlen);
632    if perimeter < 1e-6 {
633        return None;
634    }
635    let d = wlen * hlen * UNCLIP_RATIO / perimeter;
636    let (cx, cy) = (
637        quad.iter().map(|p| p.0).sum::<f32>() / 4.0,
638        quad.iter().map(|p| p.1).sum::<f32>() / 4.0,
639    );
640    // Unit axes of the rectangle.
641    let (ux, uy) = if wlen > 1e-6 {
642        (
643            (quad[1].0 - quad[0].0) / wlen,
644            (quad[1].1 - quad[0].1) / wlen,
645        )
646    } else {
647        (1.0, 0.0)
648    };
649    let (vx, vy) = if hlen > 1e-6 {
650        (
651            (quad[2].0 - quad[1].0) / hlen,
652            (quad[2].1 - quad[1].1) / hlen,
653        )
654    } else {
655        (-uy, ux)
656    };
657    let (hw, hh) = (wlen / 2.0 + d, hlen / 2.0 + d);
658    let corner = |su: f32, sv: f32| {
659        (
660            cx + su * hw * ux + sv * hh * vx,
661            cy + su * hw * uy + sv * hh * vy,
662        )
663    };
664    let corners = order_corners([
665        corner(-1.0, -1.0),
666        corner(1.0, -1.0),
667        corner(1.0, 1.0),
668        corner(-1.0, 1.0),
669    ]);
670    Some((corners, (wlen + 2.0 * d).min(hlen + 2.0 * d)))
671}
672
673/// The detected lines the recognizer still has to read (#429): those not
674/// already covered by the region-scoped pass. `detected` is in image pixels
675/// at `scale` px/pt; `regions` and `cells` are the page's layout regions and
676/// the cells recognized so far, in page points. A line counts as covered when
677/// it lies mostly (> 50 %) inside a text-like or table region — whose lines
678/// the region pass segmented and recognized, whatever it made of them — when
679/// the recognized cells inside it sum to > 30 % of its area, or when a line
680/// accepted earlier in reading order overlaps it by > 30 %. Cumulative on
681/// purpose: DB happily spans two adjacent columns in one box, and judged cell
682/// by cell such a box overlaps every cell a little while re-reading all of
683/// them (the `old_newspaper` scan doubled a paragraph that way); and DB can
684/// emit a word and its whole line. Returns `text` regions in page points for
685/// the recognizer's line prep. Shared by the native worker and the browser
686/// pipeline.
687pub fn uncovered_lines(
688    detected: &[DetBox],
689    scale: f32,
690    regions: &[crate::layout::Region],
691    cells: &[crate::pdfium_backend::TextCell],
692) -> Vec<crate::layout::Region> {
693    let mut accepted: Vec<crate::layout::Region> = Vec::new();
694    for d in detected.iter().map(|d| crate::layout::Region {
695        label: "text",
696        score: d.score,
697        l: d.l / scale,
698        t: d.t / scale,
699        r: d.r / scale,
700        b: d.b / scale,
701    }) {
702        let da = ((d.r - d.l) * (d.b - d.t)).max(1.0);
703        let inter = |l: f32, t: f32, r: f32, b: f32| {
704            (d.r.min(r) - d.l.max(l)).max(0.0) * (d.b.min(b) - d.t.max(t)).max(0.0)
705        };
706        let in_region = regions.iter().any(|r| {
707            (crate::ocr_prep::is_text_label(r.label) || crate::assemble::is_table_like(r.label))
708                && inter(r.l, r.t, r.r, r.b) / da > 0.5
709        });
710        let by_cells: f32 = cells.iter().map(|c| inter(c.l, c.t, c.r, c.b)).sum::<f32>() / da;
711        let by_accepted = accepted
712            .iter()
713            .any(|u| inter(u.l, u.t, u.r, u.b) / da > 0.3);
714        if !in_region && by_cells <= 0.3 && !by_accepted {
715            accepted.push(d);
716        }
717    }
718    accepted
719}
720
721#[cfg(feature = "ml")]
722pub use session::DetModel;
723
724#[cfg(feature = "ml")]
725mod session {
726    use super::{
727        budget_enabled, db_boxes, det_crop_size, det_input_size, det_input_size_capped,
728        line_height_p25, max_side_cap, offset_boxes, prep_det_input_to, scan_budget, sort_boxes,
729        DetBox,
730    };
731    use image::RgbImage;
732    use ort::session::Session;
733    use ort::value::Tensor;
734
735    /// The detector session. Loaded lazily by the page worker alongside the
736    /// recognizer; absent model → the pipeline runs recognition-only.
737    pub struct DetModel {
738        session: Session,
739    }
740
741    /// `DOCLING_OCR_DET_ONNX`, else `.models/ocr_det.onnx` through the asset
742    /// resolver (CWD, `DOCLING_RS_MODELS_DIR`, exe dir).
743    pub(crate) fn resolve_det_path() -> String {
744        docling_core::env::nonempty("DOCLING_OCR_DET_ONNX")
745            .unwrap_or_else(|| crate::resolve_asset(".models/ocr_det.onnx"))
746    }
747
748    impl DetModel {
749        /// Load the detector with `intra` intra-op threads (the worker's layout
750        /// thread budget; DB is a plain conv net, so the output is stable
751        /// across thread counts to the precision a 0.3 threshold sees).
752        pub fn load(intra: usize) -> Result<Self, String> {
753            let path = resolve_det_path();
754            if !std::path::Path::new(&path).exists() {
755                return Err(format!("text detection model not found at {path}"));
756            }
757            let builder = docling_onnx::session_builder()
758                .map_err(|e| format!("ocr-det: builder: {e}"))?
759                .with_intra_threads(intra.max(1))
760                .map_err(|e| format!("ocr-det: intra_threads: {e}"))?;
761            let builder = docling_onnx::apply(builder).map_err(|e| format!("ocr-det: {e}"))?;
762            let session = docling_onnx::commit(builder, &path, "det")
763                .map_err(|e| format!("ocr-det: load {path}: {e}"))?;
764            Ok(Self { session })
765        }
766
767        /// Detect text lines on `img`; boxes in `img` pixels, reading order.
768        pub fn detect(&mut self, img: &RgbImage) -> Result<Vec<DetBox>, String> {
769            match det_input_size(img.width(), img.height()) {
770                Some(size) => self.detect_at(img, size),
771                None => Ok(Vec::new()),
772            }
773        }
774
775        /// [`detect`](Self::detect) for a scanned page: with `budget` (a PDF
776        /// page render at its own 2 px/pt — not a standalone image, which
777        /// has `scale` 1.0 and reads at docling's 3 px/pt effective
778        /// resolution or, over 2000 px, as decoded; not an `--ocr-scale`
779        /// resample), the input budgeted to the page's own
780        /// text size ([`scan_budget`], #945) — the full cap for small print,
781        /// down to the 960 px floor for large type — unless
782        /// `DOCLING_RS_OCR_DET_BUDGET=full`.
783        pub fn detect_scan(&mut self, img: &RgbImage, budget: bool) -> Result<Vec<DetBox>, String> {
784            if !budget || !budget_enabled() {
785                return self.detect(img);
786            }
787            let cap = max_side_cap();
788            let line = crate::timing::timed("ocr.det.budget", || line_height_p25(img));
789            let budget = scan_budget(img.width(), img.height(), line, cap);
790            if budget != cap {
791                docling_core::debug_log!(
792                    "docling-pdf: text detector budget {budget} px for {}×{} (p25 line {:.0} px)",
793                    img.width(),
794                    img.height(),
795                    line.unwrap_or(0.0)
796                );
797            }
798            self.detect_capped(img, budget)
799        }
800
801        /// [`detect`](Self::detect) under an explicit longer-side cap
802        /// (`0` = none) instead of `DOCLING_RS_OCR_DET_MAX_SIDE`'s — the
803        /// orientation probe of a page that has a text layer (#936) reads a
804        /// few wide lines and does not keep the boxes, so it pays the
805        /// pre-#570 960 px budget, not the full one (#945).
806        pub fn detect_capped(
807            &mut self,
808            img: &RgbImage,
809            max_side: u32,
810        ) -> Result<Vec<DetBox>, String> {
811            match det_input_size_capped(img.width(), img.height(), max_side) {
812                Some(size) => self.detect_at(img, size),
813                None => Ok(Vec::new()),
814            }
815        }
816
817        /// Detect text lines inside the given `(l, t, r, b)` pixel rectangles
818        /// of `img` — each cropped and run on its own at [`det_crop_size`] —
819        /// and return their boxes in `img` pixels, reading order (#945). For
820        /// the layout regions a page's text layer leaves empty (#931): a
821        /// caption-sized crop costs a small fraction of the whole page at
822        /// the 2000 px budget and reads it at full render resolution.
823        /// Rectangles are clamped to the image; empty ones are skipped.
824        pub fn detect_regions(
825            &mut self,
826            img: &RgbImage,
827            rects: &[(u32, u32, u32, u32)],
828        ) -> Result<Vec<DetBox>, String> {
829            let (iw, ih) = img.dimensions();
830            let cap = max_side_cap();
831            let mut all = Vec::new();
832            for &(l, t, r, b) in rects {
833                let (r, b) = (r.min(iw), b.min(ih));
834                if r <= l || b <= t {
835                    continue;
836                }
837                let Some(size) = det_crop_size(r - l, b - t, cap) else {
838                    continue;
839                };
840                let crop = image::imageops::crop_imm(img, l, t, r - l, b - t).to_image();
841                all.extend(offset_boxes(
842                    self.detect_at(&crop, size)?,
843                    l as f32,
844                    t as f32,
845                ));
846            }
847            sort_boxes(&mut all);
848            Ok(all)
849        }
850
851        /// One detector run over `img` resized to `size`; boxes in `img`
852        /// pixels.
853        fn detect_at(&mut self, img: &RgbImage, size: (u32, u32)) -> Result<Vec<DetBox>, String> {
854            let (data, w, h) =
855                crate::timing::timed("ocr.det.prep", || prep_det_input_to(img, size));
856            let input = Tensor::from_array(([1usize, 3, h as usize, w as usize], data))
857                .map_err(|e| format!("ocr-det: input: {e}"))?;
858            let name = self.session.inputs()[0].name().to_string();
859            let outputs = crate::timing::timed("ocr.det.net", || {
860                docling_onnx::run(&mut self.session, ort::inputs![name.as_str() => input])
861                    .map_err(|e| format!("ocr-det: run: {e}"))
862            })?;
863            let (shape, prob) = outputs[0]
864                .try_extract_tensor::<f32>()
865                .map_err(|e| format!("ocr-det: output: {e}"))?;
866            let dims: Vec<usize> = shape.iter().map(|&d| d as usize).collect();
867            let (ph, pw) = match dims.as_slice() {
868                [_, _, ph, pw] => (*ph, *pw),
869                _ => return Err(format!("ocr-det: unexpected output shape {dims:?}")),
870            };
871            Ok(crate::timing::timed("ocr.det.post", || {
872                db_boxes(prob, pw, ph, img.width(), img.height())
873            }))
874        }
875    }
876}
877
878#[cfg(test)]
879mod tests {
880    use super::*;
881
882    #[test]
883    fn input_size_scales_the_short_side_to_736_in_multiples_of_32() {
884        // RapidOCR's uncapped rule. 445 × 884: short side 445 → ×1.654;
885        // 736 × 1462 → 736 × 1472.
886        assert_eq!(det_input_size_capped(445, 884, 0), Some((736, 1472)));
887        // Already ≥ 736 on the short side: unchanged bar the /32 rounding.
888        assert_eq!(det_input_size_capped(1335, 2652, 0), Some((1344, 2656)));
889        assert_eq!(det_input_size(0, 10), None);
890        // The default cap (2000, RapidOCR's) applies when the env knob is
891        // unset — a Letter render stays at its shorter-side-rule size.
892        assert_eq!(det_input_size(1224, 1584), Some((1216, 1600)));
893        // A longer-side cap scales a big page down (1224 × 1584 → 736 × 960
894        // for 960) and leaves a small image's shorter-side upscale alone
895        // (445 × 884 still goes to 736 × 1472 under a 1500 cap, 480 × 960
896        // under 960).
897        assert_eq!(det_input_size_capped(1224, 1584, 960), Some((736, 960)));
898        assert_eq!(det_input_size_capped(445, 884, 1500), Some((736, 1472)));
899        assert_eq!(det_input_size_capped(445, 884, 960), Some((480, 960)));
900        assert_eq!(det_input_size_capped(1224, 1584, 0), Some((1216, 1600)));
901    }
902
903    /// #945: a region crop is detected at its own pixels — no shorter-side
904    /// upscale — rounded up to the net's 32-px grid, and only scaled down
905    /// when it exceeds the cap; boxes come back in page pixels.
906    #[test]
907    fn crops_keep_their_pixels_and_boxes_return_to_the_page() {
908        assert_eq!(det_crop_size(300, 60, 2000), Some((320, 64)));
909        assert_eq!(det_crop_size(1, 1, 2000), Some((32, 32)));
910        assert_eq!(det_crop_size(4000, 1000, 2000), Some((2016, 512)));
911        assert_eq!(det_crop_size(4000, 1000, 0), Some((4000, 1024)));
912        assert_eq!(det_crop_size(0, 10, 2000), None);
913        let moved = offset_boxes(vec![DetBox::rect(1.0, 2.0, 11.0, 7.0, 0.9)], 100.0, 50.0);
914        assert_eq!(moved[0].l, 101.0);
915        assert_eq!(moved[0].b, 57.0);
916        assert_eq!(moved[0].quad[2], (111.0, 57.0));
917    }
918
919    /// #945: the budget follows the small print — full cap at or under the
920    /// 12 px target (FUNSD), the 960 floor for 2 px/pt body text, clamped to
921    /// the cap and, uncapped, to the page's own size; no lines = full.
922    #[test]
923    fn scan_budget_follows_the_small_print() {
924        assert_eq!(scan_budget(1224, 1584, Some(30.0), 2000), 1056);
925        assert_eq!(scan_budget(1224, 1584, Some(40.0), 2000), 960);
926        assert_eq!(scan_budget(1190, 1684, Some(23.0), 2000), 1464);
927        assert_eq!(scan_budget(1224, 1584, Some(20.0), 2000), 2000);
928        assert_eq!(scan_budget(1224, 1584, Some(14.0), 2000), 2000);
929        assert_eq!(scan_budget(1224, 1584, None, 2000), 2000);
930        assert_eq!(scan_budget(762, 1000, Some(9.0), 2000), 2000);
931        // A strip or wide figure (shorter side under 736) is never budgeted.
932        assert_eq!(scan_budget(2552, 402, Some(96.0), 2000), 2000);
933        // A cap under the floor wins; uncapped never upscales.
934        assert_eq!(scan_budget(1224, 1584, Some(40.0), 800), 800);
935        assert_eq!(scan_budget(3000, 4000, Some(50.0), 0), 1600);
936        assert_eq!(scan_budget(3000, 4000, Some(9.0), 0), 4000);
937        // Synthetic page: 20 px black bars every 40 px → p25 = 20.
938        let mut img = RgbImage::from_pixel(800, 600, image::Rgb([255, 255, 255]));
939        for y in (40..560).step_by(40) {
940            for yy in y..y + 20 {
941                for x in 50..750 {
942                    img.put_pixel(x, yy, image::Rgb([0, 0, 0]));
943                }
944            }
945        }
946        assert_eq!(line_height_p25(&img), Some(20.0));
947        assert_eq!(
948            line_height_p25(&RgbImage::from_pixel(800, 600, image::Rgb([255; 3]))),
949            None
950        );
951        assert!(budget_enabled());
952    }
953
954    #[test]
955    fn det_input_is_bgr_normalized() {
956        let mut img = RgbImage::new(736, 736);
957        img.put_pixel(0, 0, image::Rgb([255, 0, 128]));
958        let (data, w, h) = prep_det_input(&img).unwrap();
959        assert_eq!((w, h), (736, 736));
960        let n = (w * h) as usize;
961        // Blue plane first: pixel (0,0) has B=128 → ~0.0039; G=0 → -1; R=255 → 1.
962        assert!((data[0] - (128.0 / 127.5 - 1.0)).abs() < 1e-6);
963        assert_eq!(data[n], -1.0);
964        assert_eq!(data[2 * n], 1.0);
965    }
966
967    #[test]
968    fn min_area_rect_of_an_upright_and_a_tilted_blob() {
969        let pts: Vec<(f32, f32)> = (0..20)
970            .flat_map(|x| (0..5).map(move |y| (x as f32, y as f32)))
971            .collect();
972        let (c, sside) = min_area_rect(&pts).unwrap();
973        assert!((sside - 4.0).abs() < 1e-3);
974        assert!(
975            (c[0].0 - 0.0).abs() < 1e-3 && (c[0].1 - 0.0).abs() < 1e-3,
976            "{c:?}"
977        );
978        assert!(
979            (c[2].0 - 19.0).abs() < 1e-3 && (c[2].1 - 4.0).abs() < 1e-3,
980            "{c:?}"
981        );
982        // The same strip rotated 45°: the tight rectangle is ~19 × 4, not the
983        // axis-aligned 16 × 16 box.
984        let s = std::f32::consts::FRAC_1_SQRT_2;
985        let rot: Vec<(f32, f32)> = pts
986            .iter()
987            .map(|&(x, y)| (x * s - y * s + 50.0, x * s + y * s + 50.0))
988            .collect();
989        let (_, sside) = min_area_rect(&rot).unwrap();
990        assert!((sside - 4.0).abs() < 1e-2, "{sside}");
991    }
992
993    /// Two text-like blobs on a probability map → two boxes, grown by the
994    /// unclip distance (area·1.6/perimeter) on every side, in reading order,
995    /// scaled to the destination image; a faint blob below `box_thresh` and a
996    /// speck below `min_size` are dropped.
997    #[test]
998    fn db_boxes_from_a_synthetic_probability_map() {
999        let (w, h) = (128usize, 64usize);
1000        let mut prob = vec![0f32; w * h];
1001        let blob = |prob: &mut Vec<f32>, l: usize, t: usize, r: usize, b: usize, p: f32| {
1002            for y in t..b {
1003                for x in l..r {
1004                    prob[y * w + x] = p;
1005                }
1006            }
1007        };
1008        blob(&mut prob, 70, 10, 110, 20, 0.9); // right, upper row
1009        blob(&mut prob, 10, 12, 50, 22, 0.9); // left, same row (top within 10)
1010        blob(&mut prob, 10, 40, 60, 48, 0.35); // above thresh but mean < box_thresh
1011        blob(&mut prob, 100, 50, 102, 52, 0.9); // speck
1012        let boxes = db_boxes(&prob, w, h, 256, 128);
1013        assert_eq!(boxes.len(), 2, "{boxes:?}");
1014        // Left blob first (same row, smaller x). Its rectangle spans pixel
1015        // centers 10..49 × 12..21 (39 × 9 after dilation shifts by one:
1016        // 10..50 × 12..22 → 40 × 10), unclip d = 400·1.6/100 = 6.4.
1017        let a = &boxes[0];
1018        assert!(a.l < boxes[1].l);
1019        // The dilated rectangle takes in one zero-probability rim row and
1020        // column, so the mean sits a little under the blob's 0.9 — RapidOCR
1021        // scores the dilated contour on the raw map the same way.
1022        assert!(a.score > 0.75 && a.score < 0.9, "{}", a.score);
1023        // Doubled for the 2× destination scale: l ≈ (10 − 6.4)·2, r ≈ (50 + 6.4)·2.
1024        assert!(
1025            (a.l - 7.0).abs() <= 2.0 && (a.r - 113.0).abs() <= 2.0,
1026            "{a:?}"
1027        );
1028        assert!(
1029            (a.t - 11.0).abs() <= 2.0 && (a.b - 57.0).abs() <= 2.0,
1030            "{a:?}"
1031        );
1032    }
1033
1034    /// The coverage rule: a line inside a text region, one whose area
1035    /// recognized cells mostly fill (cumulatively — two half-covering cells
1036    /// count), and a duplicate of an accepted line are all skipped; a line in
1037    /// the open is kept, converted to page points.
1038    #[test]
1039    fn uncovered_lines_skip_what_the_region_pass_read() {
1040        use crate::layout::Region;
1041        use crate::pdfium_backend::TextCell;
1042        let bx = |l: f32, t: f32, r: f32, b: f32| DetBox::rect(l, t, r, b, 0.9);
1043        let regions = vec![Region {
1044            label: "text",
1045            score: 0.9,
1046            l: 0.0,
1047            t: 0.0,
1048            r: 100.0,
1049            b: 20.0,
1050        }];
1051        let cell = |l: f32, r: f32| TextCell {
1052            text: "x".into(),
1053            l,
1054            t: 50.0,
1055            r,
1056            b: 60.0,
1057        };
1058        let cells = vec![cell(0.0, 50.0), cell(50.0, 100.0)];
1059        let detected = vec![
1060            bx(0.0, 0.0, 200.0, 40.0), // inside the text region (page pts 0..100 × 0..20)
1061            bx(0.0, 100.0, 200.0, 120.0), // two cells cover it half each → covered
1062            bx(0.0, 300.0, 200.0, 320.0), // in the open → kept
1063            bx(20.0, 302.0, 100.0, 318.0), // a word of the accepted line → duplicate
1064        ];
1065        let out = uncovered_lines(&detected, 2.0, &regions, &cells);
1066        assert_eq!(out.len(), 1, "{out:?}");
1067        assert_eq!(
1068            (out[0].l, out[0].t, out[0].r, out[0].b),
1069            (0.0, 150.0, 100.0, 160.0)
1070        );
1071        assert_eq!(out[0].label, "text");
1072    }
1073
1074    #[test]
1075    fn boxes_sort_by_row_then_column() {
1076        let bx = |l: f32, t: f32| DetBox::rect(l, t, l + 10.0, t + 10.0, 1.0);
1077        let mut boxes = vec![
1078            bx(50.0, 100.0),
1079            bx(10.0, 105.0),
1080            bx(30.0, 20.0),
1081            bx(5.0, 200.0),
1082        ];
1083        sort_boxes(&mut boxes);
1084        let order: Vec<(f32, f32)> = boxes.iter().map(|b| (b.l, b.t)).collect();
1085        assert_eq!(
1086            order,
1087            vec![(30.0, 20.0), (10.0, 105.0), (50.0, 100.0), (5.0, 200.0)]
1088        );
1089        // Two columns whose line tops interleave within the threshold (a
1090        // newspaper): each column's lines must stay top-to-bottom, and a
1091        // right-column line sorts after the left-column line it shares a
1092        // baseline with — RapidOCR's result, not one page-wide "row".
1093        let mut cols = vec![
1094            bx(97.0, 154.0),
1095            bx(96.0, 173.0),
1096            bx(600.0, 160.0),
1097            bx(97.0, 191.0),
1098            bx(601.0, 178.0),
1099            bx(600.0, 197.0),
1100        ];
1101        sort_boxes(&mut cols);
1102        let order: Vec<(f32, f32)> = cols.iter().map(|b| (b.l, b.t)).collect();
1103        assert_eq!(
1104            order,
1105            vec![
1106                (97.0, 154.0),
1107                (600.0, 160.0),
1108                (96.0, 173.0),
1109                (601.0, 178.0),
1110                (97.0, 191.0),
1111                (600.0, 197.0)
1112            ]
1113        );
1114    }
1115}