use std::collections::BTreeMap;
use docling_core::debug_log;
#[derive(Debug, Clone)]
pub struct TfCell {
pub bbox: [f64; 4],
pub cell_id: usize,
pub row_id: usize,
pub column_id: usize,
pub cell_class: i64,
pub colspan_val: usize,
pub rowspan_val: usize,
}
#[derive(Debug, Clone)]
pub struct PdfWord {
pub id: usize,
pub bbox: [f64; 4],
pub text: String,
}
#[derive(Debug, Clone, PartialEq)]
pub struct MatchEntry {
pub table_cell_id: usize,
pub score: f64,
}
pub type Matches = BTreeMap<usize, Vec<MatchEntry>>;
fn find_intersection(b1: &[f64; 4], b2: &[f64; 4]) -> Option<[f64; 4]> {
if b1[2] < b2[0] || b2[2] < b1[0] || b1[1] > b2[3] {
return None;
}
Some([
b1[0].max(b2[0]),
b1[1].max(b2[1]),
b1[2].min(b2[2]),
b1[3].min(b2[3]),
])
}
fn intersection_over_pdf_match(table_cells: &[TfCell], pdf_cells: &[PdfWord]) -> Matches {
let mut matches: Matches = BTreeMap::new();
for cell in table_cells {
for word in pdf_cells {
let Some(ib) = find_intersection(&cell.bbox, &word.bbox) else {
continue;
};
let warea = (word.bbox[2] - word.bbox[0]) * (word.bbox[3] - word.bbox[1]);
let iarea = (ib[2] - ib[0]) * (ib[3] - ib[1]);
let iopdf = if warea > 0.0 { iarea / warea } else { 0.0 };
if iopdf > 0.0 {
let entry = MatchEntry {
table_cell_id: cell.cell_id,
score: iopdf,
};
let list = matches.entry(word.id).or_default();
if !list.contains(&entry) {
list.push(entry);
}
}
}
}
matches
}
fn get_table_dimension(table_cells: &[TfCell]) -> (usize, usize, usize) {
let mut columns = 1;
let mut rows = 1;
let mut max_cell_id = 0;
for cell in table_cells {
columns = columns.max(cell.column_id);
rows = rows.max(cell.row_id);
max_cell_id = max_cell_id.max(cell.cell_id);
}
(columns + 1, rows + 1, max_cell_id)
}
fn good_bad_cells_in_column(
table_cells: &[TfCell],
column: usize,
matches: &Matches,
) -> (Vec<TfCell>, Vec<TfCell>) {
let mut good = Vec::new();
let mut bad = Vec::new();
for cell in table_cells {
if cell.column_id != column {
continue;
}
let mut bad_match = true;
if cell.cell_class > 1 {
for list in matches.values() {
for m in list {
if m.table_cell_id == cell.cell_id {
good.push(cell.clone());
bad_match = false;
}
}
}
}
if bad_match {
bad.push(cell.clone());
}
}
(good, bad)
}
#[derive(Clone, Copy, PartialEq)]
enum Alignment {
Left,
Middle,
Right,
}
fn find_alignment_in_column(cells: &[TfCell]) -> Alignment {
if cells.is_empty() {
return Alignment::Left;
}
let (mut lmin, mut lmax) = (f64::INFINITY, f64::NEG_INFINITY);
let (mut mmin, mut mmax) = (f64::INFINITY, f64::NEG_INFINITY);
let (mut rmin, mut rmax) = (f64::INFINITY, f64::NEG_INFINITY);
for cell in cells {
let l = cell.bbox[0];
let r = cell.bbox[2];
let m = (l + r) / 2.0;
lmin = lmin.min(l);
lmax = lmax.max(l);
mmin = mmin.min(m);
mmax = mmax.max(m);
rmin = rmin.min(r);
rmax = rmax.max(r);
}
let deltas = [lmax - lmin, mmax - mmin, rmax - rmin];
let mut best = 0;
for (i, d) in deltas.iter().enumerate() {
if *d < deltas[best] {
best = i;
}
}
match best {
0 => Alignment::Left,
1 => Alignment::Middle,
_ => Alignment::Right,
}
}
#[cfg(test)]
pub(crate) fn median_for_test(values: &mut [f64]) -> f64 {
median(values)
}
fn median(values: &mut [f64]) -> f64 {
values.sort_by(|a, b| a.total_cmp(b));
let n = values.len();
if n == 0 {
0.0
} else if n % 2 == 1 {
values[n / 2]
} else {
(values[n / 2 - 1] + values[n / 2]) / 2.0
}
}
fn get_median_pos_size(cells: &[TfCell], alignment: Alignment) -> (f64, f64, f64) {
let mut xs = Vec::new();
let mut ws = Vec::new();
let mut hs = Vec::new();
for cell in cells {
if cell.rowspan_val > 0 || cell.colspan_val > 0 || cell.cell_class <= 1 {
continue;
}
let x = match alignment {
Alignment::Left => cell.bbox[0],
Alignment::Middle => (cell.bbox[2] + cell.bbox[0]) / 2.0,
Alignment::Right => cell.bbox[2],
};
xs.push(x);
ws.push(cell.bbox[2] - cell.bbox[0]);
hs.push(cell.bbox[3] - cell.bbox[1]);
}
let median_x = if xs.is_empty() { 0.0 } else { median(&mut xs) };
let median_w = if ws.is_empty() { 1.0 } else { median(&mut ws) };
let median_h = if hs.is_empty() { 1.0 } else { median(&mut hs) };
(median_x, median_w, median_h)
}
fn move_cells_to_left_pos(cells: &[TfCell], median_x: f64, alignment: Alignment) -> Vec<TfCell> {
cells
.iter()
.map(|cell| {
let width = cell.bbox[2] - cell.bbox[0];
let (new_x1, new_x2) = match alignment {
Alignment::Left => (median_x, median_x + width),
Alignment::Middle => {
let x1 = median_x - width / 2.0;
(x1, x1 + width)
}
Alignment::Right => (median_x - width, median_x),
};
TfCell {
bbox: [new_x1, cell.bbox[1], new_x2, cell.bbox[3]],
..cell.clone()
}
})
.collect()
}
fn deduplicate_cells(
tab_columns: usize,
table_cells: &[TfCell],
iou_matches: &Matches,
ioc_matches: &Matches,
) -> (Vec<TfCell>, Matches) {
use std::collections::BTreeSet;
let mut pdf_cells_in_columns: Vec<BTreeSet<usize>> = Vec::with_capacity(tab_columns);
let mut total_score_in_columns: Vec<f64> = Vec::with_capacity(tab_columns);
for col in 0..tab_columns {
let column_cell_ids: BTreeSet<usize> = table_cells
.iter()
.filter(|c| c.column_id == col)
.map(|c| c.cell_id)
.collect();
let mut ids = BTreeSet::new();
let mut score = 0.0;
for matches in [iou_matches, ioc_matches] {
for (&pdf_id, list) in matches {
for m in list {
if column_cell_ids.contains(&m.table_cell_id) {
score += m.score;
ids.insert(pdf_id);
}
}
}
}
pdf_cells_in_columns.push(ids);
total_score_in_columns.push(score);
}
let mut cols_to_eliminate: Vec<usize> = Vec::new();
for cl in 0..tab_columns.saturating_sub(1) {
let col_a = &pdf_cells_in_columns[cl];
let col_b = &pdf_cells_in_columns[cl + 1];
let int_prc = if col_a.is_empty() {
0.0
} else {
col_a.intersection(col_b).count() as f64 / col_a.len() as f64
};
if int_prc > 0.6 {
if total_score_in_columns[cl] >= total_score_in_columns[cl + 1] {
cols_to_eliminate.push(cl + 1);
} else {
cols_to_eliminate.push(cl);
}
}
}
let mut removed_ids: BTreeSet<usize> = BTreeSet::new();
let mut new_table_cells = Vec::new();
for cell in table_cells {
if cols_to_eliminate.contains(&cell.column_id) {
removed_ids.insert(cell.cell_id);
} else {
new_table_cells.push(cell.clone());
}
}
let mut new_matches: Matches = BTreeMap::new();
for (&pdf_id, list) in ioc_matches {
let kept: Vec<MatchEntry> = list
.iter()
.filter(|m| !removed_ids.contains(&m.table_cell_id))
.cloned()
.collect();
if !kept.is_empty() {
new_matches.insert(pdf_id, kept);
}
}
(new_table_cells, new_matches)
}
fn do_final_assignment(ioc_matches: &Matches) -> Matches {
let mut new_matches: Matches = BTreeMap::new();
for (&pdf_id, list) in ioc_matches {
let mut best = &list[0];
for m in &list[1..] {
if m.score > best.score {
best = m;
}
}
new_matches.insert(pdf_id, vec![best.clone()]);
}
new_matches
}
fn align_table_cells_to_pdf(
table_cells: &[TfCell],
pdf_cells: &[PdfWord],
matches: &Matches,
) -> Vec<TfCell> {
use std::collections::HashMap;
let word_boxes: HashMap<usize, [f64; 4]> = pdf_cells.iter().map(|w| (w.id, w.bbox)).collect();
let mut boxes_per_cell: BTreeMap<usize, [f64; 4]> = BTreeMap::new();
let mut order: Vec<usize> = Vec::new();
for (pdf_id, list) in matches {
let Some(&wb) = word_boxes.get(pdf_id) else {
continue;
};
let mut seen = std::collections::BTreeSet::new();
for m in list {
if !seen.insert(m.table_cell_id) {
continue;
}
match boxes_per_cell.entry(m.table_cell_id) {
std::collections::btree_map::Entry::Vacant(e) => {
e.insert(wb);
order.push(m.table_cell_id);
}
std::collections::btree_map::Entry::Occupied(mut e) => {
let b = e.get_mut();
b[0] = b[0].min(wb[0]);
b[1] = b[1].min(wb[1]);
b[2] = b[2].max(wb[2]);
b[3] = b[3].max(wb[3]);
}
}
}
}
let by_id: HashMap<usize, &TfCell> = table_cells.iter().map(|c| (c.cell_id, c)).collect();
let mut out = Vec::new();
for cell_id in order {
if let Some(&cell) = by_id.get(&cell_id) {
let mut cell = cell.clone();
cell.bbox = boxes_per_cell[&cell_id];
out.push(cell);
}
}
out
}
fn merge_two_bboxes(a: &[f64; 4], b: &[f64; 4]) -> [f64; 4] {
[
a[0].min(b[0]),
a[1].min(b[1]),
a[2].max(b[2]),
a[3].max(b[3]),
]
}
fn py_round(v: f64) -> i64 {
v.round_ties_even() as i64
}
type OrphanRecord = (usize, i64, [f64; 4]);
fn band_orphans(
n_bands: usize,
cells_in_band: impl Fn(usize) -> Vec<[f64; 4]>,
pdf_cells: &[PdfWord],
matches: &Matches,
lo_ix: usize,
hi_ix: usize,
) -> Vec<Vec<OrphanRecord>> {
let mut bands: Vec<Vec<OrphanRecord>> = Vec::with_capacity(n_bands);
let mut used: BTreeMap<usize, usize> = BTreeMap::new();
for band_ix in 0..n_bands {
let boxes = cells_in_band(band_ix);
let mut lo = -1.0f64;
let mut hi = -1.0f64;
if !boxes.is_empty() {
lo = boxes.iter().map(|b| b[lo_ix]).fold(f64::INFINITY, f64::min);
hi = boxes
.iter()
.map(|b| b[hi_ix])
.fold(f64::NEG_INFINITY, f64::max);
}
let mut in_band: Vec<OrphanRecord> = Vec::new();
for word in pdf_cells {
if matches.contains_key(&word.id) {
continue;
}
let centroid_band = (hi + lo) / 2.0;
let centroid_cell = (word.bbox[hi_ix] + word.bbox[lo_ix]) / 2.0;
let within = (word.bbox[lo_ix] >= lo && word.bbox[lo_ix] <= hi)
|| (word.bbox[hi_ix] >= lo && word.bbox[hi_ix] <= hi)
|| (word.bbox[lo_ix] <= lo && word.bbox[hi_ix] >= hi);
if !within {
continue;
}
let depth = py_round((centroid_band - centroid_cell).abs());
match used.get(&word.id) {
None => {
used.insert(word.id, band_ix);
in_band.push((word.id, depth, word.bbox));
}
Some(&old_band) => {
let Some(old_pos) = bands[old_band].iter().position(|r| r.0 == word.id) else {
continue;
};
if depth < bands[old_band][old_pos].1 {
bands[old_band].remove(old_pos);
used.insert(word.id, band_ix);
in_band.push((word.id, depth, word.bbox));
}
}
}
}
bands.push(in_band);
}
bands
}
fn band_centroids(
n_bands: usize,
cells_in_band: impl Fn(usize) -> Vec<[f64; 4]>,
lo_ix: usize,
hi_ix: usize,
) -> Vec<Option<f64>> {
(0..n_bands)
.map(|band_ix| {
let boxes = cells_in_band(band_ix);
if boxes.is_empty() {
return None;
}
let lo = boxes.iter().map(|b| b[lo_ix]).fold(f64::INFINITY, f64::min);
let hi = boxes
.iter()
.map(|b| b[hi_ix])
.fold(f64::NEG_INFINITY, f64::max);
(lo >= 0.0 && hi >= 0.0).then_some((lo + hi) / 2.0)
})
.collect()
}
fn nearest_band(centroids: &[Option<f64>], at: f64) -> Option<(usize, f64)> {
let mut best: Option<(usize, f64)> = None;
for (band_ix, c) in centroids.iter().enumerate() {
let Some(c) = c else { continue };
let dist = (at - c).abs();
if best.is_none_or(|(_, d)| dist < d) {
best = Some((band_ix, dist));
}
}
best
}
#[allow(clippy::too_many_arguments)]
fn attach_orphan(
table_cells: &mut Vec<TfCell>,
matches: &mut Matches,
mut max_cell_id: usize,
pdf_id: usize,
row_id: usize,
column_id: usize,
confidence: i64,
pdf_bbox: [f64; 4],
) -> usize {
let existing = table_cells
.iter()
.position(|c| c.row_id == row_id && c.column_id == column_id);
let table_cell_id = match existing {
Some(ix) => {
let merged = merge_two_bboxes(&table_cells[ix].bbox, &pdf_bbox);
table_cells[ix].bbox = merged;
table_cells[ix].cell_id
}
None => {
max_cell_id += 1;
table_cells.push(TfCell {
bbox: pdf_bbox,
cell_id: max_cell_id,
column_id,
row_id,
cell_class: 2,
colspan_val: 0,
rowspan_val: 0,
});
max_cell_id
}
};
matches.insert(
pdf_id,
vec![MatchEntry {
table_cell_id,
score: confidence as f64,
}],
);
max_cell_id
}
fn pick_orphan_cells(
tab_rows: usize,
tab_cols: usize,
mut max_cell_id: usize,
mut table_cells: Vec<TfCell>,
pdf_cells: &[PdfWord],
mut matches: Matches,
) -> (Matches, Vec<TfCell>, usize) {
let orphans: Vec<usize> = pdf_cells
.iter()
.filter(|w| !matches.contains_key(&w.id))
.map(|w| w.id)
.collect();
let row_cells = |row: usize| -> Vec<[f64; 4]> {
table_cells
.iter()
.filter(|c| c.row_id == row && c.rowspan_val == 0 && c.cell_class > 1)
.map(|c| c.bbox)
.collect()
};
let col_cells = |col: usize| -> Vec<[f64; 4]> {
table_cells
.iter()
.filter(|c| c.column_id == col && c.colspan_val == 0 && c.cell_class > 1)
.map(|c| c.bbox)
.collect()
};
let orphan_rows = band_orphans(tab_rows, row_cells, pdf_cells, &matches, 1, 3);
let orphan_columns = band_orphans(tab_cols, col_cells, pdf_cells, &matches, 0, 2);
let row_centroids = band_centroids(tab_rows, row_cells, 1, 3);
let col_centroids = band_centroids(tab_cols, col_cells, 0, 2);
let mut row_of: BTreeMap<usize, (usize, [f64; 4])> = BTreeMap::new();
for (row_id, records) in orphan_rows.iter().enumerate() {
for r in records {
row_of.insert(r.0, (row_id, r.2));
}
}
let mut col_of: BTreeMap<usize, (usize, i64, [f64; 4])> = BTreeMap::new();
for (col_id, records) in orphan_columns.iter().enumerate() {
for r in records {
col_of.insert(r.0, (col_id, r.1, r.2));
}
}
for (&pdf_id, &(new_row_id, pdf_bbox)) in row_of.iter() {
let (new_column_id, confidence, pdf_bbox) = match col_of.get(&pdf_id) {
Some(&record) => record,
None => {
let at = (pdf_bbox[0] + pdf_bbox[2]) / 2.0;
let Some((col, dist)) = nearest_band(&col_centroids, at) else {
continue;
};
(col, -py_round(dist) - 1, pdf_bbox)
}
};
max_cell_id = attach_orphan(
&mut table_cells,
&mut matches,
max_cell_id,
pdf_id,
new_row_id,
new_column_id,
confidence,
pdf_bbox,
);
}
for (&pdf_id, &(new_column_id, _, pdf_bbox)) in col_of.iter() {
if row_of.contains_key(&pdf_id) || matches.contains_key(&pdf_id) {
continue;
}
let at = (pdf_bbox[1] + pdf_bbox[3]) / 2.0;
let Some((new_row_id, dist)) = nearest_band(&row_centroids, at) else {
continue;
};
max_cell_id = attach_orphan(
&mut table_cells,
&mut matches,
max_cell_id,
pdf_id,
new_row_id,
new_column_id,
-py_round(dist) - 1,
pdf_bbox,
);
}
let dropped = orphans
.iter()
.filter(|id| !matches.contains_key(id))
.count();
if dropped > 0 {
debug_log!(
"docling-pdf: tableformer: {dropped} of {} pdf cells matched neither a row nor a \
column band of the {tab_rows}x{tab_cols} grid and were dropped from the table",
pdf_cells.len()
);
}
(matches, table_cells, max_cell_id)
}
pub fn match_and_post_process(
table_cells: Vec<TfCell>,
pdf_cells: &[PdfWord],
) -> (Vec<TfCell>, Matches) {
let matches = intersection_over_pdf_match(&table_cells, pdf_cells);
let (tab_columns, tab_rows, max_cell_id) = get_table_dimension(&table_cells);
let mut fixed: Vec<TfCell> = Vec::new();
for col in 0..tab_columns {
let (good, bad) = good_bad_cells_in_column(&table_cells, col, &matches);
let alignment = find_alignment_in_column(&good);
let (median_x, median_w, median_h) = get_median_pos_size(&good, alignment);
let _ = (median_w, median_h); let moved = move_cells_to_left_pos(&bad, median_x, alignment);
fixed.extend(good);
fixed.extend(moved);
}
fixed.sort_by_key(|c| c.cell_id);
let ioc = intersection_over_pdf_match(&fixed, pdf_cells);
let (dedupl_cells, dedupl_matches) = deduplicate_cells(tab_columns, &fixed, &matches, &ioc);
let final_matches = do_final_assignment(&dedupl_matches);
let mut dedupl_sorted = dedupl_cells;
dedupl_sorted.sort_by_key(|c| c.cell_id);
let aligned = if pdf_cells.len() > 300 {
dedupl_sorted
} else {
align_table_cells_to_pdf(&dedupl_sorted, pdf_cells, &final_matches)
};
let (final_matches, cells_wo, _) = pick_orphan_cells(
tab_rows,
tab_columns,
max_cell_id,
aligned,
pdf_cells,
final_matches,
);
(cells_wo, final_matches)
}
#[cfg(test)]
mod tests {
use super::*;
fn cell(cell_id: usize, row_id: usize, column_id: usize, bbox: [f64; 4]) -> TfCell {
TfCell {
bbox,
cell_id,
row_id,
column_id,
cell_class: 2,
colspan_val: 0,
rowspan_val: 0,
}
}
fn word(id: usize, bbox: [f64; 4]) -> PdfWord {
PdfWord {
id,
bbox,
text: "w".into(),
}
}
fn matched(pairs: &[(usize, usize)]) -> Matches {
pairs
.iter()
.map(|&(pdf_id, table_cell_id)| {
(
pdf_id,
vec![MatchEntry {
table_cell_id,
score: 0.9,
}],
)
})
.collect()
}
fn placed<'a>(cells: &'a [TfCell], matches: &Matches, pdf_id: usize) -> (&'a TfCell, f64) {
let entry = &matches[&pdf_id][0];
let cell = cells
.iter()
.find(|c| c.cell_id == entry.table_cell_id)
.expect("the matched cell exists");
(cell, entry.score)
}
fn two_by_two() -> Vec<TfCell> {
vec![
cell(0, 0, 0, [10.0, 10.0, 90.0, 25.0]),
cell(1, 0, 1, [110.0, 10.0, 200.0, 25.0]),
cell(2, 1, 0, [10.0, 30.0, 90.0, 45.0]),
cell(3, 1, 1, [110.0, 30.0, 200.0, 45.0]),
]
}
#[test]
fn an_orphan_in_a_row_band_only_goes_to_the_nearest_column() {
let words = [word(99, [550.0, 32.0, 590.0, 43.0])];
let (m, cells, _) = pick_orphan_cells(2, 2, 3, two_by_two(), &words, Matches::new());
let (c, confidence) = placed(&cells, &m, 99);
assert_eq!((c.row_id, c.column_id), (1, 1));
assert_eq!(confidence, -416.0);
let words = [word(7, [20.0, 32.0, 80.0, 43.0])];
let (m, cells, _) = pick_orphan_cells(2, 2, 3, two_by_two(), &words, Matches::new());
let (c, confidence) = placed(&cells, &m, 7);
assert_eq!((c.row_id, c.column_id), (1, 0));
assert!(confidence >= 0.0);
}
#[test]
fn an_orphan_in_a_column_band_only_goes_to_the_nearest_row() {
let grid = vec![
cell(0, 0, 0, [0.0, 0.0, 50.0, 20.0]),
cell(1, 1, 0, [0.0, 30.0, 50.0, 50.0]),
];
let words = [
word(0, [0.0, 30.0, 50.0, 50.0]),
word(9, [0.0, 200.0, 50.0, 220.0]),
];
let (m, cells, _) = pick_orphan_cells(2, 1, 1, grid, &words, matched(&[(0, 1)]));
let (c, confidence) = placed(&cells, &m, 9);
assert_eq!((c.row_id, c.column_id), (1, 0));
assert_eq!(confidence, -171.0);
}
#[test]
fn an_orphan_outside_every_band_is_dropped() {
let grid = || vec![cell(0, 0, 0, [0.0, 0.0, 50.0, 20.0])];
let words = [
word(0, [0.0, 0.0, 50.0, 20.0]),
word(1, [200.0, 200.0, 250.0, 220.0]),
word(2, [200.0, 300.0, 250.0, 320.0]),
];
let (m, _, _) = pick_orphan_cells(1, 1, 0, grid(), &words, matched(&[(0, 0)]));
assert_eq!(m.keys().copied().collect::<Vec<_>>(), [0]);
let words = [
word(0, [0.0, 0.0, 50.0, 20.0]),
word(1, [0.0, 5.0, 50.0, 18.0]),
];
let (m, _, _) = pick_orphan_cells(1, 1, 0, grid(), &words, matched(&[(0, 0)]));
assert_eq!(m.keys().copied().collect::<Vec<_>>(), [0, 1]);
}
}