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/// Share of the smaller box's area two boxes from *different* crops must
483/// overlap by to be one line read twice ([`merge_crop_boxes`]). Boxes the
484/// detector returns from one crop never overlap like that — DB's components
485/// are disjoint — so the only source of such a pair is the same pixels seen
486/// through two padded crops.
487const CROP_DUP_OVERLAP: f32 = 0.5;
488
489/// Within this many pixels of a crop side that is not the image's own edge,
490/// a box counts as cut by the crop (its glyphs run on past the crop).
491const CROP_EDGE_PX: f32 = 1.5;
492
493/// One detector crop's `(l, t, r, b)` rectangle in image pixels and the
494/// boxes found in it, already offset to image pixels.
495pub type CropBoxes = ((u32, u32, u32, u32), Vec<DetBox>);
496
497/// The boxes of [`DetModel::detect_regions`]'s per-region crops as one set,
498/// in reading order, with every line two crops both detected kept once
499/// (#1133). The crops are padded by half a line (#945), so a heading that
500/// touches its paragraph lies mostly inside the paragraph's crop too, and
501/// the detector found it there again — with the glyph tops cut off by the
502/// crop edge. Both boxes have their centre inside the heading's region,
503/// both were recognised, and the item read `Opening Hours opemig Hours`.
504/// docling never sees the pair: `_find_pdf_aware_layout_ocr_rects` merges
505/// touching cluster rects into connected components before OCR. We keep
506/// the per-region crops (their sizes are #945's cost budget) and drop the
507/// duplicate instead: of two boxes from different crops overlapping by
508/// [`CROP_DUP_OVERLAP`] of the smaller one, the one its crop cut is
509/// dropped; when neither or both were cut, the smaller (a fragment of the
510/// other) — ties keep the earlier crop's. `crops` pairs each crop's
511/// `(l, t, r, b)` in image pixels with its boxes (already in image pixels);
512/// `(iw, ih)` is the image size, whose own edges cut nothing.
513pub fn merge_crop_boxes(crops: Vec<CropBoxes>, (iw, ih): (u32, u32)) -> Vec<DetBox> {
514    let cut = |rect: (u32, u32, u32, u32), b: &DetBox| {
515        let (l, t, r, bt) = (rect.0 as f32, rect.1 as f32, rect.2 as f32, rect.3 as f32);
516        (rect.0 > 0 && b.l - l <= CROP_EDGE_PX)
517            || (rect.1 > 0 && b.t - t <= CROP_EDGE_PX)
518            || (rect.2 < iw && r - b.r <= CROP_EDGE_PX)
519            || (rect.3 < ih && bt - b.b <= CROP_EDGE_PX)
520    };
521    let area = |b: &DetBox| (b.r - b.l).max(0.0) * (b.b - b.t).max(0.0);
522    // (crop index, cut by its crop, box)
523    let mut all: Vec<(usize, bool, DetBox)> = crops
524        .into_iter()
525        .enumerate()
526        .flat_map(|(i, (rect, boxes))| {
527            boxes
528                .into_iter()
529                .map(move |b| (i, cut(rect, &b), b))
530                .collect::<Vec<_>>()
531        })
532        .collect();
533    let mut keep = vec![true; all.len()];
534    for i in 0..all.len() {
535        for j in i + 1..all.len() {
536            if !keep[i] || !keep[j] || all[i].0 == all[j].0 {
537                continue;
538            }
539            let (a, b) = (&all[i].2, &all[j].2);
540            let ow = (a.r.min(b.r) - a.l.max(b.l)).max(0.0);
541            let oh = (a.b.min(b.b) - a.t.max(b.t)).max(0.0);
542            let smaller = area(a).min(area(b));
543            if smaller <= 0.0 || ow * oh < CROP_DUP_OVERLAP * smaller {
544                continue;
545            }
546            let drop_j = match (all[i].1, all[j].1) {
547                (false, true) => true,
548                (true, false) => false,
549                _ => area(b) <= area(a),
550            };
551            keep[if drop_j { j } else { i }] = false;
552        }
553    }
554    let mut out: Vec<DetBox> = all
555        .drain(..)
556        .zip(keep)
557        .filter_map(|((_, _, b), k)| k.then_some(b))
558        .collect();
559    sort_boxes(&mut out);
560    out
561}
562
563/// A candidate enclosing rectangle: its area, corners and shorter side.
564type RectCandidate = (f32, [(f32, f32); 4], f32);
565
566/// `cv2.minAreaRect` over a point set (rotating calipers on the convex hull):
567/// the four corners of the smallest enclosing rectangle and its shorter side,
568/// in the order `get_mini_boxes` returns (top-left, top-right, bottom-right,
569/// bottom-left, for an upright box). `None` for fewer than one point.
570pub fn min_area_rect(points: &[(f32, f32)]) -> Option<([(f32, f32); 4], f32)> {
571    let hull = convex_hull(points);
572    if hull.is_empty() {
573        return None;
574    }
575    if hull.len() <= 2 {
576        // A single pixel or a straight run: a degenerate rectangle along it.
577        let (a, b) = (hull[0], *hull.last().unwrap());
578        return Some((order_corners([a, b, b, a]), 0.0));
579    }
580    let mut best: Option<RectCandidate> = None;
581    for i in 0..hull.len() {
582        let (p, q) = (hull[i], hull[(i + 1) % hull.len()]);
583        let (ex, ey) = (q.0 - p.0, q.1 - p.1);
584        let len = (ex * ex + ey * ey).sqrt();
585        if len < 1e-6 {
586            continue;
587        }
588        let (ux, uy) = (ex / len, ey / len);
589        let (vx, vy) = (-uy, ux);
590        let (mut umin, mut umax, mut vmin, mut vmax) = (f32::MAX, f32::MIN, f32::MAX, f32::MIN);
591        for &(x, y) in &hull {
592            let u = x * ux + y * uy;
593            let v = x * vx + y * vy;
594            umin = umin.min(u);
595            umax = umax.max(u);
596            vmin = vmin.min(v);
597            vmax = vmax.max(v);
598        }
599        let area = (umax - umin) * (vmax - vmin);
600        if best.as_ref().is_none_or(|(a, _, _)| area < *a) {
601            let corner = |u: f32, v: f32| (u * ux + v * vx, u * uy + v * vy);
602            let corners = [
603                corner(umin, vmin),
604                corner(umax, vmin),
605                corner(umax, vmax),
606                corner(umin, vmax),
607            ];
608            best = Some((area, corners, (umax - umin).min(vmax - vmin)));
609        }
610    }
611    best.map(|(_, corners, sside)| (order_corners(corners), sside))
612}
613
614/// `get_mini_boxes`' corner order: sort by x, then the left pair top-first and
615/// the right pair top-first → `[tl, tr, br, bl]`.
616pub(crate) fn order_corners(mut c: [(f32, f32); 4]) -> [(f32, f32); 4] {
617    c.sort_by(|a, b| a.0.total_cmp(&b.0));
618    let (i1, i4) = if c[1].1 > c[0].1 { (0, 1) } else { (1, 0) };
619    let (i2, i3) = if c[3].1 > c[2].1 { (2, 3) } else { (3, 2) };
620    [c[i1], c[i2], c[i3], c[i4]]
621}
622
623/// Andrew's monotone chain; counter-clockwise, no collinear duplicates.
624fn convex_hull(points: &[(f32, f32)]) -> Vec<(f32, f32)> {
625    let mut pts: Vec<(f32, f32)> = points.to_vec();
626    pts.sort_by(|a, b| a.0.total_cmp(&b.0).then(a.1.total_cmp(&b.1)));
627    pts.dedup();
628    if pts.len() < 3 {
629        return pts;
630    }
631    let cross = |o: (f32, f32), a: (f32, f32), b: (f32, f32)| {
632        (a.0 - o.0) * (b.1 - o.1) - (a.1 - o.1) * (b.0 - o.0)
633    };
634    let mut lower: Vec<(f32, f32)> = Vec::new();
635    for &p in &pts {
636        while lower.len() >= 2 && cross(lower[lower.len() - 2], lower[lower.len() - 1], p) <= 0.0 {
637            lower.pop();
638        }
639        lower.push(p);
640    }
641    let mut upper: Vec<(f32, f32)> = Vec::new();
642    for &p in pts.iter().rev() {
643        while upper.len() >= 2 && cross(upper[upper.len() - 2], upper[upper.len() - 1], p) <= 0.0 {
644            upper.pop();
645        }
646        upper.push(p);
647    }
648    lower.pop();
649    upper.pop();
650    lower.extend(upper);
651    lower
652}
653
654/// `box_score_fast`: mean probability over the pixels inside the rectangle
655/// (a convex quad — the pixel-center test replaces `cv2.fillPoly`).
656fn box_score_fast(prob: &[f32], w: usize, h: usize, quad: &[(f32, f32); 4]) -> f32 {
657    let xmin = quad
658        .iter()
659        .map(|p| p.0)
660        .fold(f32::MAX, f32::min)
661        .floor()
662        .clamp(0.0, (w - 1) as f32) as usize;
663    let xmax = quad
664        .iter()
665        .map(|p| p.0)
666        .fold(f32::MIN, f32::max)
667        .ceil()
668        .clamp(0.0, (w - 1) as f32) as usize;
669    let ymin = quad
670        .iter()
671        .map(|p| p.1)
672        .fold(f32::MAX, f32::min)
673        .floor()
674        .clamp(0.0, (h - 1) as f32) as usize;
675    let ymax = quad
676        .iter()
677        .map(|p| p.1)
678        .fold(f32::MIN, f32::max)
679        .ceil()
680        .clamp(0.0, (h - 1) as f32) as usize;
681    let (mut sum, mut n) = (0f64, 0usize);
682    for y in ymin..=ymax {
683        for x in xmin..=xmax {
684            if inside_convex(quad, (x as f32, y as f32)) {
685                sum += prob[y * w + x] as f64;
686                n += 1;
687            }
688        }
689    }
690    if n == 0 {
691        0.0
692    } else {
693        (sum / n as f64) as f32
694    }
695}
696
697/// Point-in-convex-polygon (boundary counts as inside), any winding.
698fn inside_convex(quad: &[(f32, f32); 4], p: (f32, f32)) -> bool {
699    let mut pos = false;
700    let mut neg = false;
701    for i in 0..4 {
702        let (a, b) = (quad[i], quad[(i + 1) % 4]);
703        let cross = (b.0 - a.0) * (p.1 - a.1) - (b.1 - a.1) * (p.0 - a.0);
704        pos |= cross > 1e-6;
705        neg |= cross < -1e-6;
706    }
707    !(pos && neg)
708}
709
710/// `unclip` + `get_mini_boxes`: grow the rectangle outward by
711/// `area · unclip_ratio / perimeter` (the polygon offset of a rectangle is a
712/// rounded rectangle whose minimum-area rectangle is the original grown by
713/// the offset on every side). Returns the corners and the shorter side.
714fn unclip(quad: &[(f32, f32); 4]) -> Option<([(f32, f32); 4], f32)> {
715    let side = |a: (f32, f32), b: (f32, f32)| ((a.0 - b.0).powi(2) + (a.1 - b.1).powi(2)).sqrt();
716    let (wlen, hlen) = (side(quad[0], quad[1]), side(quad[1], quad[2]));
717    let perimeter = 2.0 * (wlen + hlen);
718    if perimeter < 1e-6 {
719        return None;
720    }
721    let d = wlen * hlen * UNCLIP_RATIO / perimeter;
722    let (cx, cy) = (
723        quad.iter().map(|p| p.0).sum::<f32>() / 4.0,
724        quad.iter().map(|p| p.1).sum::<f32>() / 4.0,
725    );
726    // Unit axes of the rectangle.
727    let (ux, uy) = if wlen > 1e-6 {
728        (
729            (quad[1].0 - quad[0].0) / wlen,
730            (quad[1].1 - quad[0].1) / wlen,
731        )
732    } else {
733        (1.0, 0.0)
734    };
735    let (vx, vy) = if hlen > 1e-6 {
736        (
737            (quad[2].0 - quad[1].0) / hlen,
738            (quad[2].1 - quad[1].1) / hlen,
739        )
740    } else {
741        (-uy, ux)
742    };
743    let (hw, hh) = (wlen / 2.0 + d, hlen / 2.0 + d);
744    let corner = |su: f32, sv: f32| {
745        (
746            cx + su * hw * ux + sv * hh * vx,
747            cy + su * hw * uy + sv * hh * vy,
748        )
749    };
750    let corners = order_corners([
751        corner(-1.0, -1.0),
752        corner(1.0, -1.0),
753        corner(1.0, 1.0),
754        corner(-1.0, 1.0),
755    ]);
756    Some((corners, (wlen + 2.0 * d).min(hlen + 2.0 * d)))
757}
758
759/// The detected lines the recognizer still has to read (#429): those not
760/// already covered by the region-scoped pass. `detected` is in image pixels
761/// at `scale` px/pt; `regions` and `cells` are the page's layout regions and
762/// the cells recognized so far, in page points. A line counts as covered when
763/// it lies mostly (> 50 %) inside a text-like or table region — whose lines
764/// the region pass segmented and recognized, whatever it made of them — when
765/// the recognized cells inside it sum to > 30 % of its area, or when a line
766/// accepted earlier in reading order overlaps it by > 30 %. Cumulative on
767/// purpose: DB happily spans two adjacent columns in one box, and judged cell
768/// by cell such a box overlaps every cell a little while re-reading all of
769/// them (the `old_newspaper` scan doubled a paragraph that way); and DB can
770/// emit a word and its whole line. Returns `text` regions in page points for
771/// the recognizer's line prep. Shared by the native worker and the browser
772/// pipeline.
773pub fn uncovered_lines(
774    detected: &[DetBox],
775    scale: f32,
776    regions: &[crate::layout::Region],
777    cells: &[crate::pdfium_backend::TextCell],
778) -> Vec<crate::layout::Region> {
779    let mut accepted: Vec<crate::layout::Region> = Vec::new();
780    for d in detected.iter().map(|d| crate::layout::Region {
781        label: "text",
782        score: d.score,
783        l: d.l / scale,
784        t: d.t / scale,
785        r: d.r / scale,
786        b: d.b / scale,
787    }) {
788        let da = ((d.r - d.l) * (d.b - d.t)).max(1.0);
789        let inter = |l: f32, t: f32, r: f32, b: f32| {
790            (d.r.min(r) - d.l.max(l)).max(0.0) * (d.b.min(b) - d.t.max(t)).max(0.0)
791        };
792        let in_region = regions.iter().any(|r| {
793            (crate::ocr_prep::is_text_label(r.label) || crate::assemble::is_table_like(r.label))
794                && inter(r.l, r.t, r.r, r.b) / da > 0.5
795        });
796        let by_cells: f32 = cells.iter().map(|c| inter(c.l, c.t, c.r, c.b)).sum::<f32>() / da;
797        let by_accepted = accepted
798            .iter()
799            .any(|u| inter(u.l, u.t, u.r, u.b) / da > 0.3);
800        if !in_region && by_cells <= 0.3 && !by_accepted {
801            accepted.push(d);
802        }
803    }
804    accepted
805}
806
807#[cfg(feature = "ml")]
808pub use session::DetModel;
809
810#[cfg(feature = "ml")]
811mod session {
812    use super::{
813        budget_enabled, db_boxes, det_crop_size, det_input_size, det_input_size_capped,
814        line_height_p25, max_side_cap, merge_crop_boxes, offset_boxes, prep_det_input_to,
815        scan_budget, DetBox,
816    };
817    use image::RgbImage;
818    use ort::session::Session;
819    use ort::value::Tensor;
820
821    /// The detector session. Loaded lazily by the page worker alongside the
822    /// recognizer; absent model → the pipeline runs recognition-only.
823    pub struct DetModel {
824        session: Session,
825    }
826
827    /// `DOCLING_OCR_DET_ONNX`, else `.models/ocr_det.onnx` through the asset
828    /// resolver (CWD, `DOCLING_RS_MODELS_DIR`, exe dir).
829    pub(crate) fn resolve_det_path() -> String {
830        docling_core::env::nonempty("DOCLING_OCR_DET_ONNX")
831            .unwrap_or_else(|| crate::resolve_asset(".models/ocr_det.onnx"))
832    }
833
834    impl DetModel {
835        /// Load the detector with `intra` intra-op threads (the worker's layout
836        /// thread budget; DB is a plain conv net, so the output is stable
837        /// across thread counts to the precision a 0.3 threshold sees).
838        pub fn load(intra: usize) -> Result<Self, String> {
839            let path = resolve_det_path();
840            if !std::path::Path::new(&path).exists() {
841                return Err(format!("text detection model not found at {path}"));
842            }
843            let builder = docling_onnx::session_builder()
844                .map_err(|e| format!("ocr-det: builder: {e}"))?
845                .with_intra_threads(intra.max(1))
846                .map_err(|e| format!("ocr-det: intra_threads: {e}"))?;
847            let builder = docling_onnx::apply(builder).map_err(|e| format!("ocr-det: {e}"))?;
848            let session = docling_onnx::commit(builder, &path, "det")
849                .map_err(|e| format!("ocr-det: load {path}: {e}"))?;
850            Ok(Self { session })
851        }
852
853        /// Detect text lines on `img`; boxes in `img` pixels, reading order.
854        pub fn detect(&mut self, img: &RgbImage) -> Result<Vec<DetBox>, String> {
855            match det_input_size(img.width(), img.height()) {
856                Some(size) => self.detect_at(img, size),
857                None => Ok(Vec::new()),
858            }
859        }
860
861        /// [`detect`](Self::detect) for a scanned page: with `budget` (a PDF
862        /// page render at its own 2 px/pt — not a standalone image, which
863        /// has `scale` 1.0 and reads at docling's 3 px/pt effective
864        /// resolution or, over 2000 px, as decoded; not an `--ocr-scale`
865        /// resample), the input budgeted to the page's own
866        /// text size ([`scan_budget`], #945) — the full cap for small print,
867        /// down to the 960 px floor for large type — unless
868        /// `DOCLING_RS_OCR_DET_BUDGET=full`.
869        pub fn detect_scan(&mut self, img: &RgbImage, budget: bool) -> Result<Vec<DetBox>, String> {
870            if !budget || !budget_enabled() {
871                return self.detect(img);
872            }
873            let cap = max_side_cap();
874            let line = crate::timing::timed("ocr.det.budget", || line_height_p25(img));
875            let budget = scan_budget(img.width(), img.height(), line, cap);
876            if budget != cap {
877                docling_core::debug_log!(
878                    "docling-pdf: text detector budget {budget} px for {}×{} (p25 line {:.0} px)",
879                    img.width(),
880                    img.height(),
881                    line.unwrap_or(0.0)
882                );
883            }
884            self.detect_capped(img, budget)
885        }
886
887        /// [`detect`](Self::detect) under an explicit longer-side cap
888        /// (`0` = none) instead of `DOCLING_RS_OCR_DET_MAX_SIDE`'s — the
889        /// orientation probe of a page that has a text layer (#936) reads a
890        /// few wide lines and does not keep the boxes, so it pays the
891        /// pre-#570 960 px budget, not the full one (#945).
892        pub fn detect_capped(
893            &mut self,
894            img: &RgbImage,
895            max_side: u32,
896        ) -> Result<Vec<DetBox>, String> {
897            match det_input_size_capped(img.width(), img.height(), max_side) {
898                Some(size) => self.detect_at(img, size),
899                None => Ok(Vec::new()),
900            }
901        }
902
903        /// Detect text lines inside the given `(l, t, r, b)` pixel rectangles
904        /// of `img` — each cropped and run on its own at [`det_crop_size`] —
905        /// and return their boxes in `img` pixels, reading order (#945). For
906        /// the layout regions a page's text layer leaves empty (#931): a
907        /// caption-sized crop costs a small fraction of the whole page at
908        /// the 2000 px budget and reads it at full render resolution.
909        /// Rectangles are clamped to the image; empty ones are skipped.
910        pub fn detect_regions(
911            &mut self,
912            img: &RgbImage,
913            rects: &[(u32, u32, u32, u32)],
914        ) -> Result<Vec<DetBox>, String> {
915            let (iw, ih) = img.dimensions();
916            let cap = max_side_cap();
917            let mut crops = Vec::with_capacity(rects.len());
918            for &(l, t, r, b) in rects {
919                let (r, b) = (r.min(iw), b.min(ih));
920                if r <= l || b <= t {
921                    continue;
922                }
923                let Some(size) = det_crop_size(r - l, b - t, cap) else {
924                    continue;
925                };
926                let crop = image::imageops::crop_imm(img, l, t, r - l, b - t).to_image();
927                let boxes = offset_boxes(self.detect_at(&crop, size)?, l as f32, t as f32);
928                crops.push(((l, t, r, b), boxes));
929            }
930            // Padded crops overlap; a line two of them saw is kept once
931            // (#1133).
932            Ok(merge_crop_boxes(crops, (iw, ih)))
933        }
934
935        /// One detector run over `img` resized to `size`; boxes in `img`
936        /// pixels.
937        fn detect_at(&mut self, img: &RgbImage, size: (u32, u32)) -> Result<Vec<DetBox>, String> {
938            let (data, w, h) =
939                crate::timing::timed("ocr.det.prep", || prep_det_input_to(img, size));
940            let input = Tensor::from_array(([1usize, 3, h as usize, w as usize], data))
941                .map_err(|e| format!("ocr-det: input: {e}"))?;
942            let name = self.session.inputs()[0].name().to_string();
943            let outputs = crate::timing::timed("ocr.det.net", || {
944                docling_onnx::run(&mut self.session, ort::inputs![name.as_str() => input])
945                    .map_err(|e| format!("ocr-det: run: {e}"))
946            })?;
947            let (shape, prob) = outputs[0]
948                .try_extract_tensor::<f32>()
949                .map_err(|e| format!("ocr-det: output: {e}"))?;
950            let dims: Vec<usize> = shape.iter().map(|&d| d as usize).collect();
951            let (ph, pw) = match dims.as_slice() {
952                [_, _, ph, pw] => (*ph, *pw),
953                _ => return Err(format!("ocr-det: unexpected output shape {dims:?}")),
954            };
955            Ok(crate::timing::timed("ocr.det.post", || {
956                db_boxes(prob, pw, ph, img.width(), img.height())
957            }))
958        }
959    }
960}
961
962#[cfg(test)]
963mod tests {
964    use super::*;
965
966    #[test]
967    fn input_size_scales_the_short_side_to_736_in_multiples_of_32() {
968        // RapidOCR's uncapped rule. 445 × 884: short side 445 → ×1.654;
969        // 736 × 1462 → 736 × 1472.
970        assert_eq!(det_input_size_capped(445, 884, 0), Some((736, 1472)));
971        // Already ≥ 736 on the short side: unchanged bar the /32 rounding.
972        assert_eq!(det_input_size_capped(1335, 2652, 0), Some((1344, 2656)));
973        assert_eq!(det_input_size(0, 10), None);
974        // The default cap (2000, RapidOCR's) applies when the env knob is
975        // unset — a Letter render stays at its shorter-side-rule size.
976        assert_eq!(det_input_size(1224, 1584), Some((1216, 1600)));
977        // A longer-side cap scales a big page down (1224 × 1584 → 736 × 960
978        // for 960) and leaves a small image's shorter-side upscale alone
979        // (445 × 884 still goes to 736 × 1472 under a 1500 cap, 480 × 960
980        // under 960).
981        assert_eq!(det_input_size_capped(1224, 1584, 960), Some((736, 960)));
982        assert_eq!(det_input_size_capped(445, 884, 1500), Some((736, 1472)));
983        assert_eq!(det_input_size_capped(445, 884, 960), Some((480, 960)));
984        assert_eq!(det_input_size_capped(1224, 1584, 0), Some((1216, 1600)));
985    }
986
987    /// #945: a region crop is detected at its own pixels — no shorter-side
988    /// upscale — rounded up to the net's 32-px grid, and only scaled down
989    /// when it exceeds the cap; boxes come back in page pixels.
990    #[test]
991    fn crops_keep_their_pixels_and_boxes_return_to_the_page() {
992        assert_eq!(det_crop_size(300, 60, 2000), Some((320, 64)));
993        assert_eq!(det_crop_size(1, 1, 2000), Some((32, 32)));
994        assert_eq!(det_crop_size(4000, 1000, 2000), Some((2016, 512)));
995        assert_eq!(det_crop_size(4000, 1000, 0), Some((4000, 1024)));
996        assert_eq!(det_crop_size(0, 10, 2000), None);
997        let moved = offset_boxes(vec![DetBox::rect(1.0, 2.0, 11.0, 7.0, 0.9)], 100.0, 50.0);
998        assert_eq!(moved[0].l, 101.0);
999        assert_eq!(moved[0].b, 57.0);
1000        assert_eq!(moved[0].quad[2], (111.0, 57.0));
1001    }
1002
1003    /// #945: the budget follows the small print — full cap at or under the
1004    /// 12 px target (FUNSD), the 960 floor for 2 px/pt body text, clamped to
1005    /// the cap and, uncapped, to the page's own size; no lines = full.
1006    #[test]
1007    fn scan_budget_follows_the_small_print() {
1008        assert_eq!(scan_budget(1224, 1584, Some(30.0), 2000), 1056);
1009        assert_eq!(scan_budget(1224, 1584, Some(40.0), 2000), 960);
1010        assert_eq!(scan_budget(1190, 1684, Some(23.0), 2000), 1464);
1011        assert_eq!(scan_budget(1224, 1584, Some(20.0), 2000), 2000);
1012        assert_eq!(scan_budget(1224, 1584, Some(14.0), 2000), 2000);
1013        assert_eq!(scan_budget(1224, 1584, None, 2000), 2000);
1014        assert_eq!(scan_budget(762, 1000, Some(9.0), 2000), 2000);
1015        // A strip or wide figure (shorter side under 736) is never budgeted.
1016        assert_eq!(scan_budget(2552, 402, Some(96.0), 2000), 2000);
1017        // A cap under the floor wins; uncapped never upscales.
1018        assert_eq!(scan_budget(1224, 1584, Some(40.0), 800), 800);
1019        assert_eq!(scan_budget(3000, 4000, Some(50.0), 0), 1600);
1020        assert_eq!(scan_budget(3000, 4000, Some(9.0), 0), 4000);
1021        // Synthetic page: 20 px black bars every 40 px → p25 = 20.
1022        let mut img = RgbImage::from_pixel(800, 600, image::Rgb([255, 255, 255]));
1023        for y in (40..560).step_by(40) {
1024            for yy in y..y + 20 {
1025                for x in 50..750 {
1026                    img.put_pixel(x, yy, image::Rgb([0, 0, 0]));
1027                }
1028            }
1029        }
1030        assert_eq!(line_height_p25(&img), Some(20.0));
1031        assert_eq!(
1032            line_height_p25(&RgbImage::from_pixel(800, 600, image::Rgb([255; 3]))),
1033            None
1034        );
1035        assert!(budget_enabled());
1036    }
1037
1038    #[test]
1039    fn det_input_is_bgr_normalized() {
1040        let mut img = RgbImage::new(736, 736);
1041        img.put_pixel(0, 0, image::Rgb([255, 0, 128]));
1042        let (data, w, h) = prep_det_input(&img).unwrap();
1043        assert_eq!((w, h), (736, 736));
1044        let n = (w * h) as usize;
1045        // Blue plane first: pixel (0,0) has B=128 → ~0.0039; G=0 → -1; R=255 → 1.
1046        assert!((data[0] - (128.0 / 127.5 - 1.0)).abs() < 1e-6);
1047        assert_eq!(data[n], -1.0);
1048        assert_eq!(data[2 * n], 1.0);
1049    }
1050
1051    #[test]
1052    fn min_area_rect_of_an_upright_and_a_tilted_blob() {
1053        let pts: Vec<(f32, f32)> = (0..20)
1054            .flat_map(|x| (0..5).map(move |y| (x as f32, y as f32)))
1055            .collect();
1056        let (c, sside) = min_area_rect(&pts).unwrap();
1057        assert!((sside - 4.0).abs() < 1e-3);
1058        assert!(
1059            (c[0].0 - 0.0).abs() < 1e-3 && (c[0].1 - 0.0).abs() < 1e-3,
1060            "{c:?}"
1061        );
1062        assert!(
1063            (c[2].0 - 19.0).abs() < 1e-3 && (c[2].1 - 4.0).abs() < 1e-3,
1064            "{c:?}"
1065        );
1066        // The same strip rotated 45°: the tight rectangle is ~19 × 4, not the
1067        // axis-aligned 16 × 16 box.
1068        let s = std::f32::consts::FRAC_1_SQRT_2;
1069        let rot: Vec<(f32, f32)> = pts
1070            .iter()
1071            .map(|&(x, y)| (x * s - y * s + 50.0, x * s + y * s + 50.0))
1072            .collect();
1073        let (_, sside) = min_area_rect(&rot).unwrap();
1074        assert!((sside - 4.0).abs() < 1e-2, "{sside}");
1075    }
1076
1077    /// Two text-like blobs on a probability map → two boxes, grown by the
1078    /// unclip distance (area·1.6/perimeter) on every side, in reading order,
1079    /// scaled to the destination image; a faint blob below `box_thresh` and a
1080    /// speck below `min_size` are dropped.
1081    #[test]
1082    fn db_boxes_from_a_synthetic_probability_map() {
1083        let (w, h) = (128usize, 64usize);
1084        let mut prob = vec![0f32; w * h];
1085        let blob = |prob: &mut Vec<f32>, l: usize, t: usize, r: usize, b: usize, p: f32| {
1086            for y in t..b {
1087                for x in l..r {
1088                    prob[y * w + x] = p;
1089                }
1090            }
1091        };
1092        blob(&mut prob, 70, 10, 110, 20, 0.9); // right, upper row
1093        blob(&mut prob, 10, 12, 50, 22, 0.9); // left, same row (top within 10)
1094        blob(&mut prob, 10, 40, 60, 48, 0.35); // above thresh but mean < box_thresh
1095        blob(&mut prob, 100, 50, 102, 52, 0.9); // speck
1096        let boxes = db_boxes(&prob, w, h, 256, 128);
1097        assert_eq!(boxes.len(), 2, "{boxes:?}");
1098        // Left blob first (same row, smaller x). Its rectangle spans pixel
1099        // centers 10..49 × 12..21 (39 × 9 after dilation shifts by one:
1100        // 10..50 × 12..22 → 40 × 10), unclip d = 400·1.6/100 = 6.4.
1101        let a = &boxes[0];
1102        assert!(a.l < boxes[1].l);
1103        // The dilated rectangle takes in one zero-probability rim row and
1104        // column, so the mean sits a little under the blob's 0.9 — RapidOCR
1105        // scores the dilated contour on the raw map the same way.
1106        assert!(a.score > 0.75 && a.score < 0.9, "{}", a.score);
1107        // Doubled for the 2× destination scale: l ≈ (10 − 6.4)·2, r ≈ (50 + 6.4)·2.
1108        assert!(
1109            (a.l - 7.0).abs() <= 2.0 && (a.r - 113.0).abs() <= 2.0,
1110            "{a:?}"
1111        );
1112        assert!(
1113            (a.t - 11.0).abs() <= 2.0 && (a.b - 57.0).abs() <= 2.0,
1114            "{a:?}"
1115        );
1116    }
1117
1118    /// The coverage rule: a line inside a text region, one whose area
1119    /// recognized cells mostly fill (cumulatively — two half-covering cells
1120    /// count), and a duplicate of an accepted line are all skipped; a line in
1121    /// the open is kept, converted to page points.
1122    #[test]
1123    fn uncovered_lines_skip_what_the_region_pass_read() {
1124        use crate::layout::Region;
1125        use crate::pdfium_backend::TextCell;
1126        let bx = |l: f32, t: f32, r: f32, b: f32| DetBox::rect(l, t, r, b, 0.9);
1127        let regions = vec![Region {
1128            label: "text",
1129            score: 0.9,
1130            l: 0.0,
1131            t: 0.0,
1132            r: 100.0,
1133            b: 20.0,
1134        }];
1135        let cell = |l: f32, r: f32| TextCell {
1136            text: "x".into(),
1137            l,
1138            t: 50.0,
1139            r,
1140            b: 60.0,
1141        };
1142        let cells = vec![cell(0.0, 50.0), cell(50.0, 100.0)];
1143        let detected = vec![
1144            bx(0.0, 0.0, 200.0, 40.0), // inside the text region (page pts 0..100 × 0..20)
1145            bx(0.0, 100.0, 200.0, 120.0), // two cells cover it half each → covered
1146            bx(0.0, 300.0, 200.0, 320.0), // in the open → kept
1147            bx(20.0, 302.0, 100.0, 318.0), // a word of the accepted line → duplicate
1148        ];
1149        let out = uncovered_lines(&detected, 2.0, &regions, &cells);
1150        assert_eq!(out.len(), 1, "{out:?}");
1151        assert_eq!(
1152            (out[0].l, out[0].t, out[0].r, out[0].b),
1153            (0.0, 150.0, 100.0, 160.0)
1154        );
1155        assert_eq!(out[0].label, "text");
1156    }
1157
1158    #[test]
1159    fn boxes_sort_by_row_then_column() {
1160        let bx = |l: f32, t: f32| DetBox::rect(l, t, l + 10.0, t + 10.0, 1.0);
1161        let mut boxes = vec![
1162            bx(50.0, 100.0),
1163            bx(10.0, 105.0),
1164            bx(30.0, 20.0),
1165            bx(5.0, 200.0),
1166        ];
1167        sort_boxes(&mut boxes);
1168        let order: Vec<(f32, f32)> = boxes.iter().map(|b| (b.l, b.t)).collect();
1169        assert_eq!(
1170            order,
1171            vec![(30.0, 20.0), (10.0, 105.0), (50.0, 100.0), (5.0, 200.0)]
1172        );
1173        // Two columns whose line tops interleave within the threshold (a
1174        // newspaper): each column's lines must stay top-to-bottom, and a
1175        // right-column line sorts after the left-column line it shares a
1176        // baseline with — RapidOCR's result, not one page-wide "row".
1177        let mut cols = vec![
1178            bx(97.0, 154.0),
1179            bx(96.0, 173.0),
1180            bx(600.0, 160.0),
1181            bx(97.0, 191.0),
1182            bx(601.0, 178.0),
1183            bx(600.0, 197.0),
1184        ];
1185        sort_boxes(&mut cols);
1186        let order: Vec<(f32, f32)> = cols.iter().map(|b| (b.l, b.t)).collect();
1187        assert_eq!(
1188            order,
1189            vec![
1190                (97.0, 154.0),
1191                (600.0, 160.0),
1192                (96.0, 173.0),
1193                (601.0, 178.0),
1194                (97.0, 191.0),
1195                (600.0, 197.0)
1196            ]
1197        );
1198    }
1199
1200    #[test]
1201    fn a_line_two_padded_crops_saw_is_kept_once_unclipped() {
1202        // #1133's page at 2 px/pt: the heading region's crop holds the
1203        // heading whole; the paragraph's crop is padded up into it and cut
1204        // the glyph tops off — the second, shorter box of the same line.
1205        let heading_crop = (130, 160, 400, 230);
1206        let para_crop = (130, 190, 880, 290);
1207        let heading = DetBox::rect(141.0, 180.0, 365.0, 213.0, 0.83);
1208        let clipped = DetBox::rect(141.0, 190.0, 365.0, 213.0, 0.71);
1209        let lines = [
1210            DetBox::rect(141.0, 217.0, 846.0, 245.0, 0.83),
1211            DetBox::rect(141.0, 245.0, 815.0, 270.0, 0.77),
1212        ];
1213        let mut para = vec![clipped];
1214        para.extend(lines);
1215        let out = merge_crop_boxes(
1216            vec![(heading_crop, vec![heading]), (para_crop, para.clone())],
1217            (1224, 1584),
1218        );
1219        let tops: Vec<f32> = out.iter().map(|b| b.t).collect();
1220        assert_eq!(tops, vec![180.0, 217.0, 245.0], "{out:?}");
1221        // The crop order does not decide which copy survives.
1222        let out = merge_crop_boxes(
1223            vec![(para_crop, para), (heading_crop, vec![heading])],
1224            (1224, 1584),
1225        );
1226        assert_eq!(out.iter().map(|b| b.t).collect::<Vec<_>>(), tops);
1227    }
1228
1229    #[test]
1230    fn distinct_lines_and_one_crops_boxes_are_all_kept() {
1231        // Boxes of one crop are never merged, however close; neighbouring
1232        // crops' boxes that only graze each other are different lines.
1233        let a = (0, 0, 500, 100);
1234        let b = (0, 90, 500, 200);
1235        let out = merge_crop_boxes(
1236            vec![
1237                (
1238                    a,
1239                    vec![
1240                        DetBox::rect(10.0, 10.0, 400.0, 40.0, 0.9),
1241                        DetBox::rect(10.0, 30.0, 400.0, 60.0, 0.9),
1242                    ],
1243                ),
1244                (b, vec![DetBox::rect(10.0, 85.0, 400.0, 120.0, 0.9)]),
1245            ],
1246            (500, 200),
1247        );
1248        assert_eq!(out.len(), 3, "{out:?}");
1249        // A duplicate neither crop cut: the fragment (smaller) goes.
1250        let out = merge_crop_boxes(
1251            vec![
1252                (a, vec![DetBox::rect(10.0, 20.0, 400.0, 50.0, 0.9)]),
1253                (
1254                    (0, 0, 500, 200),
1255                    vec![DetBox::rect(10.0, 22.0, 300.0, 50.0, 0.9)],
1256                ),
1257            ],
1258            (500, 200),
1259        );
1260        assert_eq!(out.len(), 1);
1261        assert_eq!(out[0].r, 400.0);
1262    }
1263}