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