Document image preprocessing

Deep dive

How it works

In: one page image from a scanner or phone (any size, dpi, rotation, lighting) · Out: upright, flat-lit, binarised or normalised grey page near 300 dpi · State: none between pages (per-page angle and threshold only) · Cost: O(pixels) per stage; Sauvola about 42 ms on a 2480x3508 page, measured below

1. Perspective (phone photos). Find the page quad (largest convex four-corner contour of an edge map), solve the homography to a rectangle of known paper ratio, warp.
2. Grey and orientation. Luma from RGB. Fix 0/90/180/270 now: skew scoring cannot tell a page from its 180-degree flip. Use an orientation detector or the best OCR confidence.
3. Flatten. Background = large-kernel blur or grey morphological closing (kernel wider than a letter); output = 255 * image / background. Divide, because light multiplies reflectance.
4. Denoise. 3x3 median (convolution-style filter): kills speckle, keeps stroke edges.
5. Deskew. Rotate a downscaled copy over about +-5 degrees; the angle maximising the variance of row ink sums puts lines on rows. Or fit lines through character centroids (Hough transform).
6. Binarise. Flat light: Otsu maximises between-class variance of the histogram. Uneven: Niblack, T = m - ks, or Sauvola, T = m(1 + k*(s/R - 1)), with m, s the window mean and deviation; the s/R term stops speckle on blank paper. Window a character height or more.
7. Clean borders. Delete dark scanner edges and punch holes (large components touching the border, round blobs); pad 10 px white.
8. Normalise scale. Resample once to about 300 dpi (filters). Compose steps 1, 5 and 8 into one warp so the page is interpolated once.

Code

Otsu, Sauvola on summed-area tables and projection-profile deskew, std only, on a synthetic page whose light ramps 0.3 to 1.0.

/// Global threshold maximising between-class variance. Ink = pixel <= t.
fn otsu(img: &[u8]) -> u8 {
    let mut h = [0f64; 256];
    for &p in img { h[p as usize] += 1.0; }
    let (n, total) = (img.len() as f64, h.iter().enumerate().map(|(i, c)| i as f64 * c).sum::<f64>());
    let (mut w0, mut s0, mut best, mut bt) = (0.0, 0.0, -1.0, 0u8);
    for t in 0..255 {
        w0 += h[t]; s0 += t as f64 * h[t];
        let w1 = n - w0;
        if w0 == 0.0 || w1 == 0.0 { continue; }
        let d = s0 / w0 - (total - s0) / w1;
        if w0 * w1 * d * d > best { best = w0 * w1 * d * d; bt = t as u8; }
    }
    bt
}

/// Sauvola: T = m * (1 + k * (s / R - 1)) over a win x win window; R = 128 for 8-bit.
/// Window sums come from summed-area tables: constant cost per pixel.
fn sauvola(img: &[u8], w: usize, h: usize, win: usize, k: f64) -> Vec<bool> {
    let s = w + 1;
    let (mut a, mut q) = (vec![0u64; s * (h + 1)], vec![0u64; s * (h + 1)]);
    for y in 0..h {
        let (mut r, mut rq) = (0, 0);
        for x in 0..w {
            let v = img[y * w + x] as u64;
            r += v; rq += v * v;
            a[(y + 1) * s + x + 1] = a[y * s + x + 1] + r;
            q[(y + 1) * s + x + 1] = q[y * s + x + 1] + rq;
        }
    }
    let r = win / 2;
    let mut out = vec![false; w * h];
    for y in 0..h {
        let (y0, y1) = (y.saturating_sub(r), (y + r + 1).min(h));
        for x in 0..w {
            let (x0, x1) = (x.saturating_sub(r), (x + r + 1).min(w));
            let n = ((y1 - y0) * (x1 - x0)) as f64;
            let rect = |t: &[u64]| ((t[y1 * s + x1] + t[y0 * s + x0]) - (t[y0 * s + x1] + t[y1 * s + x0])) as f64;
            let m = rect(&a) / n;
            let sd = (rect(&q) / n - m * m).max(0.0).sqrt();
            out[y * w + x] = img[y * w + x] as f64 <= m * (1.0 + k * (sd / 128.0 - 1.0));
        }
    }
    out
}

fn rotate(img: &[u8], w: usize, h: usize, deg: f64) -> Vec<u8> {
    let (s, c) = deg.to_radians().sin_cos();
    let (cx, cy) = (w as f64 / 2.0, h as f64 / 2.0);
    let mut out = vec![255u8; w * h];
    for y in 0..h {
        for x in 0..w {
            let (dx, dy) = (x as f64 - cx, y as f64 - cy);
            let (sx, sy) = ((c * dx + s * dy + cx).round(), (-s * dx + c * dy + cy).round());
            if sx >= 0.0 && sy >= 0.0 && (sx as usize) < w && (sy as usize) < h { out[y * w + x] = img[sy as usize * w + sx as usize]; }
        }
    }
    out
}

/// Angle for `rotate` that levels text lines: maximise variance of row ink sums.
fn deskew_angle(img: &[u8], w: usize, h: usize, max_deg: f64, step: f64) -> f64 {
    let (mut best, mut ba, mut a) = (-1.0, 0.0, -max_deg);
    while a <= max_deg + 1e-9 {
        let r = rotate(img, w, h, a);
        let rows: Vec<f64> = r.chunks(w).map(|row| row.iter().map(|&v| (255 - v) as f64).sum()).collect();
        let mean = rows.iter().sum::<f64>() / h as f64;
        let var = rows.iter().map(|v| (v - mean).powi(2)).sum::<f64>() / h as f64;
        if var > best { best = var; ba = a; }
        a += step;
    }
    ba
}

/// Synthetic page: bars of "text", light ramps lit_lo -> 1 left to right, +-3 noise. (image, ink truth)
fn page(w: usize, h: usize, lit_lo: f64) -> (Vec<u8>, Vec<bool>) {
    let (mut seed, mut img, mut truth) = (12345u32, vec![0u8; w * h], vec![false; w * h]);
    for i in 0..w * h {
        let (x, y) = (i % w, i / w);
        let ink = y % 24 < 8 && x % 50 < 38;
        seed ^= seed << 13; seed ^= seed >> 17; seed ^= seed << 5;
        let lit = lit_lo + (1.0 - lit_lo) * x as f64 / w as f64;
        img[i] = (255.0 * lit * if ink { 0.3 } else { 1.0 } + (seed % 7) as f64 - 3.0) as u8;
        truth[i] = ink;
    }
    (img, truth)
}

fn main() {
    let (w, h) = (600, 800);
    let wrong = |m: &[bool], t: &[bool]| m.iter().zip(t).filter(|(a, b)| a != b).count();
    let global = |img: &[u8]| -> Vec<bool> { let t = otsu(img); img.iter().map(|&p| p <= t).collect() };
    let (flat, truth) = page(w, h, 1.0); // bimodal
    assert!((79..250).contains(&otsu(&flat)) && wrong(&global(&flat), &truth) == 0);
    let (lit, truth) = page(w, h, 0.3); // uneven light
    let (e_otsu, e_sauv) = (wrong(&global(&lit), &truth), wrong(&sauvola(&lit, w, h, 31, 0.2), &truth));
    assert!(e_sauv * 10 < e_otsu, "otsu {e_otsu} sauvola {e_sauv}");
    let a = deskew_angle(&rotate(&flat, w, h, 3.0), w, h, 5.0, 0.25); // plant 3 degrees
    assert!((a + 3.0).abs() <= 0.5, "got {a}");
    let (big, _) = page(2480, 3508, 0.3); // A4 at 300 dpi
    let t0 = std::time::Instant::now();
    let m = sauvola(&big, 2480, 3508, 31, 0.2);
    println!("sauvola A4@300 {:?} ({} ink px)", t0.elapsed(), m.iter().filter(|&&b| b).count());
}

Run result (rustc 1.99, release): on the 600x800 ramp-lit page Otsu mislabels 120,332 pixels, Sauvola 0 (synthetic, easy); the planted 3-degree skew comes back as -3.0 (0.25-degree step).

Complexity and constants

• Otsu: one histogram pass. Sauvola: table pass plus a sqrt per pixel, O(N) for any window; direct windows cost O(N * win^2).
• Tables: two u64 per pixel, 16 B/px, 139 MB for A4 at 300 dpi (arithmetic). Sums of squares overflow u32.
• Deskew: O(angles * N), one gather-rotation per angle.

Efficiency

• Cost: measured on Apple M4 Pro, one core, release build, synthetic A4 at 300 dpi (8.7 M pixels): Sauvola window 31 took 36-62 ms over 7 runs (typically about 42 ms, 5 ns/pixel); Otsu 5 ms; one nearest-neighbour rotation 10 ms; a 41-angle deskew on the full image 0.61 s. Bound: memory bandwidth and sqrt. Real scans add decode and colour conversion.
• Levers:
  • Estimate skew on a 4x downscaled copy — 16x fewer pixels per angle (arithmetic) — always; rotate full size once.
  • Skip Sauvola when the flattened histogram is clearly bimodal — Otsu 5 ms vs about 42 ms (measured) — clean scans.
  • Band processing with a rolling window — tables shrink from 139 MB to megabytes (arithmetic) — big pages.
  • Rows are independent — threads, until memory bandwidth bites — batches.
  • Do not upsample past need: 300 dpi has 4x the pixels of 150 (arithmetic); Tesseract advises at least 300 dpi (Tesseract docs).
• Naive → standard → state of the art:
  • Window loops, one global Otsu · 961 reads per pixel at 31x31, fails on shadows
  • Flatten, median, projection deskew, integral-image Sauvola · tens of ms per A4 page per core (measured)
  • Learned binarisation or dewarping models, or grey straight into the OCR network · cost set by the model, not measured here

Implementation notes

• Keep u8 grey; compute variance in f64 (E[v^2] - m^2 cancels badly in f32). Clip windows at borders or reflect-pad.
• Tesseract 4.x expects dark text on light; invert otherwise. tessedit_write_images shows what it binarised (Tesseract docs).
• Sauvola R = 128 for 8-bit; scikit-image defaults k = 0.2 and a 15 px window (docs). The window must exceed the stroke width, or thick strokes go hollow.

Pitfalls

• Over-binarising: large k or small windows break thin serifs and hairlines; global Otsu on a shadowed half turns paper to ink.
• Skew on tables and pictures: ruling and photos peak at 0 and 90 degrees; score a text mask only, limit the range.
• Curled pages: one angle cannot straighten a warped line; dewarp (page_dewarp).
• Wrong page quad: a light desk or cut-off corner gives a bad homography; reject odd aspect or area.
• Repeated resampling blurs; nearest neighbour is fine for angle search only.
• Binarising first bakes in defects you cannot undo.

Variants and alternatives

In production

Tesseract runs Leptonica Otsu internally (5.0 adds Adaptive Otsu and Sauvola); unpaper and ScanTailor batch-clean book scans; scikit-image and OpenCV are common toolkits.

Implementations

Sources

• Otsu, A Threshold Selection Method from Gray-Level Histograms, IEEE Trans. Systems, Man, and Cybernetics 9(1), 1979. paper
• Sauvola and Pietikainen, Adaptive document image binarization, Pattern Recognition 33(2), 2000. paper
• Niblack, An Introduction to Digital Image Processing, Prentice Hall, 1986 (no link).
• Tesseract documentation, Improving the quality of the output. docs
• scikit-image, skimage.filters thresholding reference. docs