File size: 23,067 Bytes
2523bef | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 | """
Copyright (C) 2023 Artifex Software, Inc.
This file is part of PyMuPDF.
PyMuPDF is free software: you can redistribute it and/or modify it under the
terms of the GNU Affero General Public License as published by the Free
Software Foundation, either version 3 of the License, or (at your option)
any later version.
PyMuPDF is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more
details.
You should have received a copy of the GNU Affero General Public License
along with MuPDF. If not, see <https://www.gnu.org/licenses/agpl-3.0.en.html>
Alternative licensing terms are available from the licensor.
For commercial licensing, see <https://www.artifex.com/> or contact
Artifex Software, Inc., 39 Mesa Street, Suite 108A, San Francisco,
CA 94129, USA, for further information.
---------------------------------------------------------------------
PyMuPDF table cell-span resolution (opt-in extension).
Provides SpanCell and resolve_spans (plus the _span_* helpers), which
reconstruct a detected table's merged-cell (colspan / rowspan) structure.
Re-exported by pymupdf.table; never runs on the default find_tables() path.
Reuses the word-selection helpers of pymupdf._table_refine.
"""
import pymupdf
from pymupdf._table_refine import (
_refine_is_vertical_or_rotated,
_refine_page_words,
)
class SpanCell:
"""One reconstructed table cell after span resolution (PyMuPDF extension).
``bbox`` is the placement's ``(x0, y0, x1, y1)`` union rect, ``text`` the
page text it claims (lines joined by ``\\n``), and ``colspan``/``rowspan``
how many grid columns/rows it covers. resolve_spans always sets a real bbox;
a caller padding its own grid may construct SpanCells with ``bbox=None``.
``tag`` is the cell's HTML tag (``"td"``/``"th"``), defaulting to ``"td"``.
resolve_spans leaves it at the default; find_tables(refine=True) overwrites
it from the resolved header region so Table.to_html() can serialize the grid
directly, and a caller building its own grid may set it too."""
def __init__(self, bbox, text, colspan, rowspan, tag="td"):
self.bbox = bbox
self.text = text
self.colspan = colspan
self.rowspan = rowspan
self.tag = tag
# --- slot geometry: cluster cell edges into column/row boundaries ------------
def _span_clustered_boundaries(values, *, tolerance=3.0):
"""Greedy 1-D clustering of edge coordinates into slot boundaries.
Keeps a sorted value only when it is more than ``tolerance`` from the last
kept boundary, so the first value of each run is the retained boundary."""
boundaries = []
for value in sorted(values):
if boundaries and value - boundaries[-1] <= tolerance:
continue
boundaries.append(float(value))
return boundaries
def _span_covered_slot_count(start, end, boundaries, *, tolerance=1.0):
"""How many [boundaries[i], boundaries[i+1]] slots the span start..end covers."""
count = 0
for index in range(len(boundaries) - 1):
midpoint = (boundaries[index] + boundaries[index + 1]) / 2.0
if start - tolerance <= midpoint <= end + tolerance:
count += 1
return max(1, count)
def _span_slot_range(rect, x_boundaries, *, tolerance=1.0):
"""The half-open column-slot range (first, last+1) a rect's x-extent covers."""
hits = []
for index in range(len(x_boundaries) - 1):
midpoint = (x_boundaries[index] + x_boundaries[index + 1]) / 2.0
if rect.x0 - tolerance <= midpoint <= rect.x1 + tolerance:
hits.append(index)
if not hits:
return (0, 1)
return (min(hits), max(hits) + 1)
def _span_ranges_intersect(a, b):
return a[0] < b[1] and b[0] < a[1]
def _span_point_in_rect(x, y, rect):
return float(rect.x0) <= x <= float(rect.x1) and float(rect.y0) <= y <= float(rect.y1)
def _span_rect_union(rects):
return pymupdf.Rect(
min(rect.x0 for rect in rects),
min(rect.y0 for rect in rects),
max(rect.x1 for rect in rects),
max(rect.y1 for rect in rects),
)
def _span_x_overlap(a, b):
return min(a.x1, b.x1) - max(a.x0, b.x0)
def _span_substantial_x_overlap(span_rect, cell_rect):
"""True if a text span overlaps a cell by enough x to signal a merge.
A few points of overlap is noise (a span drifting across a column line with
trailing whitespace or a currency glyph); require >2pt and >=15% of the cell
width before treating it as a merged-cell signal."""
overlap = _span_x_overlap(span_rect, cell_rect)
if overlap <= 2.0:
return False
cell_width = max(1.0, cell_rect.width)
return overlap / cell_width >= 0.15
def _span_contiguous_ranges(indices):
"""Collapse a sorted index list into (start, end) inclusive runs."""
if not indices:
return []
ranges = []
start = end = indices[0]
for index in indices[1:]:
if index == end + 1:
end = index
continue
ranges.append((start, end))
start = end = index
ranges.append((start, end))
return ranges
def _span_merge_intervals(intervals):
"""Merge overlapping (start, end, text) intervals, accumulating their texts."""
merged = []
for start, end, text in sorted(intervals, key=lambda item: (item[0], item[1])):
if start == end:
continue
if not merged or start > merged[-1][1]:
merged.append((start, end, [text]))
continue
prev_start, prev_end, texts = merged[-1]
merged[-1] = (prev_start, max(prev_end, end), texts + [text])
return merged
# --- cell text: page words + vertical-text lines claimed by a placement -------
def _span_line_text(line):
"""Space-joined non-empty span texts of a get_text('dict') line."""
parts = [
str(span.get("text") or "").strip()
for span in line.get("spans", [])
if str(span.get("text") or "").strip()
]
return " ".join(parts)
def _span_line_rect(line):
"""Bounding rect of a dict line (its bbox, else the union of its span bboxes)."""
bbox = line.get("bbox")
if bbox:
rect = pymupdf.Rect(bbox)
if not rect.is_empty:
return rect
rects = [
pymupdf.Rect(span.get("bbox") or [])
for span in line.get("spans", [])
if span.get("bbox")
]
rects = [rect for rect in rects if not rect.is_empty]
if not rects:
return None
return _span_rect_union(rects)
def _span_vertical_text_lines(page):
"""Vertical/rotated text lines as (rect, text), cached on the page.
Selects non-horizontal lines whose reading order get_text('dict') already
preserves."""
cached = getattr(page, "_span_vertical_lines_cache", None)
if cached is not None:
return cached
lines = []
for block in page.get_text("dict").get("blocks", []):
if block.get("type") not in (None, 0):
continue
for line in block.get("lines", []):
if not _refine_is_vertical_or_rotated(line):
continue
text = _span_line_text(line)
if not text:
continue
rect = _span_line_rect(line)
if rect is None:
continue
lines.append((rect, text))
try:
setattr(page, "_span_vertical_lines_cache", lines)
except Exception:
pass
return lines
def _span_vertical_text_for_rect(page, rect, selected_words):
"""Text of vertical lines centered in rect, when they dominate the rect.
Returns the stacked line text only if vertical lines are centered in the rect,
cover >=60% of the rect's selected words, and carry >=2 tokens; else None so
the caller falls back to horizontal line synthesis."""
if not selected_words:
return None
candidates = []
for line_rect, text in _span_vertical_text_lines(page):
cx = (float(line_rect.x0) + float(line_rect.x1)) * 0.5
cy = (float(line_rect.y0) + float(line_rect.y1)) * 0.5
if _span_point_in_rect(cx, cy, rect):
candidates.append((line_rect, text))
if not candidates:
return None
vertical_hits = 0
for _, (wx0, wy0, wx1, wy1, _) in selected_words:
cx = (wx0 + wx1) * 0.5
cy = (wy0 + wy1) * 0.5
if any(_span_point_in_rect(cx, cy, line_rect) for line_rect, _ in candidates):
vertical_hits += 1
if vertical_hits / max(1, len(selected_words)) < 0.6:
return None
if sum(len(text.split()) for _, text in candidates) < 2:
return None
return "\n".join(
text
for _, text in sorted(
candidates,
key=lambda item: (float(item[0].x0), -float((item[0].y0 + item[0].y1) * 0.5)),
)
)
def _span_words_to_line_text(words):
"""Join center-point-selected cell words into text, re-synthesizing lines.
``words`` are (y0, x0, y1, text) tuples; they are grouped into lines by an
adaptive median-height nearest-line rule, each line's words ordered by x, and
the lines joined by newlines."""
if not words:
return ""
heights = [max(0.1, y1 - y0) for y0, _, y1, _ in words]
median_height = sorted(heights)[len(heights) // 2]
line_threshold = max(2.0, median_height * 0.55)
lines = []
for y0, x0, y1, text in sorted(words, key=lambda item: (item[0], item[1])):
cy = (y0 + y1) / 2.0
best_line = None
best_distance = line_threshold
for line in lines:
distance = abs(cy - float(line["center_y"]))
if distance <= best_distance:
best_line = line
best_distance = distance
if best_line is None:
lines.append({"center_y": cy, "words": [(x0, text)]})
continue
best_line["words"].append((x0, text))
count = len(best_line["words"])
best_line["center_y"] = (float(best_line["center_y"]) * (count - 1) + cy) / count
text_lines = []
for line in sorted(lines, key=lambda item: float(item["center_y"])):
text_lines.append(" ".join(text for _, text in sorted(line["words"], key=lambda item: item[0])))
return "\n".join(text_lines)
def _span_word_line_tuple(word):
"""Reorder a (x0, y0, x1, y1, text) word to the (y0, x0, y1, text) line tuple."""
x0, y0, _x1, y1, text = word
return (float(y0), float(x0), float(y1), str(text))
def _span_select_words_in_rect(page_words, rect):
"""(index, word) pairs whose center lies in rect, index into ``page_words``.
The index is what lets resolve_spans claim each page word for exactly one
placement (an earlier cell's word is not re-claimed by a later one)."""
selected = []
for index, word in enumerate(page_words):
wx0, wy0, wx1, wy1, text = word
if not str(text).strip():
continue
cx = (wx0 + wx1) * 0.5
cy = (wy0 + wy1) * 0.5
if _span_point_in_rect(cx, cy, rect):
selected.append((index, word))
return selected
def _span_words_text_for_rect(page, rect, selected_words):
"""Text for a rect: vertical-line text if it dominates, else line synthesis."""
vertical_text = _span_vertical_text_for_rect(page, rect, selected_words)
if vertical_text is not None:
return vertical_text
return _span_words_to_line_text([_span_word_line_tuple(word) for _, word in selected_words])
def _span_claim_text_in_rect(page, rect, page_words, claimed_words):
"""Text of rect's words, skipping words already claimed and claiming the rest."""
selected = [
(index, word)
for index, word in _span_select_words_in_rect(page_words, rect)
if index not in claimed_words
]
for index, _ in selected:
claimed_words.add(index)
return _span_words_text_for_rect(page, rect, selected)
def _span_text_spans(page):
"""Page text spans as (rect, text), length>=2, cached on the page.
These drive merged-cell detection: a single span whose x-extent crosses a
grid column line signals cells the line grid split but text joins."""
cached = getattr(page, "_span_text_spans_cache", None)
if cached is not None:
return cached
spans = []
for block in page.get_text("dict").get("blocks", []):
for line in block.get("lines", []):
for span in line.get("spans", []):
text = str(span.get("text") or "").strip()
if len(text) < 2:
continue
bbox = span.get("bbox")
if not bbox:
continue
rect = pymupdf.Rect(bbox)
if rect.is_empty:
continue
spans.append((rect, text))
try:
setattr(page, "_span_text_spans_cache", spans)
except Exception:
pass
return spans
def _span_crossing_intervals(entries, text_spans):
"""Column ranges within one grid row that a single text span crosses.
``entries`` are the row's cell rects (in column order). A text span centered
in the row band and substantially overlapping >=2 adjacent cells marks those
cells for merging; overlapping intervals are merged. Returns
(start, end, texts) with end>start."""
if len(entries) < 2:
return []
row_y0 = min(entry.y0 for entry in entries)
row_y1 = max(entry.y1 for entry in entries)
intervals = []
for span_rect, span_text in text_spans:
center_y = (span_rect.y0 + span_rect.y1) / 2.0
if center_y < row_y0 - 1.0 or center_y > row_y1 + 1.0:
continue
hit_positions = [
position
for position, entry in enumerate(entries)
if _span_substantial_x_overlap(span_rect, entry)
]
if len(hit_positions) < 2:
continue
for start, end in _span_contiguous_ranges(hit_positions):
if end > start:
intervals.append((start, end, span_text))
return _span_merge_intervals(intervals)
# --- strict-colspan gate: reject a merge that fights the header/body split ----
# When strict_colspan is set, a header cell may only merge across columns if the
# body rows below actually split there (and vice-versa for a body cell against a
# leaf header). This keeps a stray text span from collapsing a real column.
def _span_is_leaf_header_range(row_idx, cols, base, body_start):
if row_idx >= body_start:
return False
for other in base:
if other["role"] not in {"header", "header_leaf", "header_group"}:
continue
if other["row"] <= row_idx or other["row"] >= body_start:
continue
if _span_ranges_intersect(cols, other["cols"]):
return False
return True
def _span_build_base_cells(cells, x_boundaries, body_start):
"""Describe every grid cell by row/slot-range/role for the strict-colspan gate.
Header cells split into ``header_leaf`` (no header cell below within body) vs
``header_group`` (spans over a lower leaf), which the reject rules compare
against the body split."""
base = []
for row_idx, row in enumerate(cells):
for position, cell in enumerate([cell for cell in row if cell is not None]):
rect = pymupdf.Rect(cell)
cols = _span_slot_range(rect, x_boundaries)
base.append(
{
"row": row_idx,
"position": position,
"rect": rect,
"cols": cols,
"colspan": cols[1] - cols[0],
"role": "body" if row_idx >= body_start else "header",
}
)
for item in base:
if item["role"] != "header":
continue
item["role"] = (
"header_leaf"
if _span_is_leaf_header_range(item["row"], item["cols"], base, body_start)
else "header_group"
)
return base
def _span_body_rows_split_under(cols, base, body_start):
"""True if some body row splits the column range ``cols`` into >1 cell."""
body_rows = sorted({item["row"] for item in base if item["role"] == "body" and item["row"] >= body_start})
for row_idx in body_rows:
hits = [
item
for item in base
if item["role"] == "body" and item["row"] == row_idx and _span_ranges_intersect(cols, item["cols"])
]
if not hits:
continue
if len(hits) == 1 and hits[0]["cols"] == cols:
continue
covered_start = min(max(cols[0], item["cols"][0]) for item in hits)
covered_end = max(min(cols[1], item["cols"][1]) for item in hits)
if covered_start <= cols[0] and covered_end >= cols[1]:
return True
return False
def _span_header_leafs_split_over(cols, base):
"""True if leaf-header cells split the column range ``cols`` into >1 cell."""
hits = [item for item in base if item["role"] == "header_leaf" and _span_ranges_intersect(cols, item["cols"])]
if not hits:
return False
if len(hits) == 1 and hits[0]["cols"] == cols:
return False
covered_start = min(max(cols[0], item["cols"][0]) for item in hits)
covered_end = max(min(cols[1], item["cols"][1]) for item in hits)
return covered_start <= cols[0] and covered_end >= cols[1]
def _span_reject_colspan_mismatch_merge(*, row_idx, cols, base, body_start):
"""Whether to reject a candidate merge over ``cols`` as a (reason,) mismatch."""
if cols[1] - cols[0] <= 1:
return False, ""
if row_idx < body_start:
if not _span_is_leaf_header_range(row_idx, cols, base, body_start):
return False, ""
if _span_body_rows_split_under(cols, base, body_start):
return True, "header_leaf_colspan_changed_against_body_split"
return False, ""
if _span_header_leafs_split_over(cols, base):
return True, "body_colspan_changed_against_header_leaf_split"
return False, ""
def _span_cell_texts_for_entries(page, entries, start, end, page_words):
texts = []
for entry in entries[start : end + 1]:
words = _span_select_words_in_rect(page_words, entry)
texts.append(_span_words_text_for_rect(page, entry, words))
return texts
def _span_allow_header_colspan_merge_with_empty_part(*, reason, page, entries, start, end, page_words):
"""Allow an otherwise-rejected header merge when a covered part is empty.
A header leaf that would be rejected against a body split is still merged if
one of the merged parts has no text (an empty header slot the body fills)."""
if reason != "header_leaf_colspan_changed_against_body_split":
return False
part_texts = [text.strip() for text in _span_cell_texts_for_entries(page, entries, start, end, page_words)]
return not all(part_texts)
def resolve_spans(page, cells, *, header_row_count=None, strict_colspan=False):
"""Resolve a detected table's merged-cell (colspan/rowspan) structure.
``cells`` is a row-major grid: a list of rows, each a list of ``[x0, y0, x1,
y1]`` cell rectangles (``None`` for a gap) -- the same grid shape
:func:`refine_grid` accepts. Returns a row-major grid of :class:`SpanCell`
placements, ragged where cells span: each placement carries its union
``bbox``, the page ``text`` it claims, and its ``colspan``/``rowspan`` (how
many clustered column/row slots it covers). Every page word is claimed by at
most one placement.
``header_row_count`` is the number of leading header rows (default a
conservative 1); it only matters together with ``strict_colspan``.
``strict_colspan`` (default False), when set, refuses a merge whose colspan
would contradict the header/body column split. This is a PyMuPDF extension;
it reads page text/graphics but does not mutate the page.
"""
rows = len(cells)
x_edges = []
y_edges = []
for row in cells:
for cell in row:
if cell is None:
continue
rect = pymupdf.Rect(cell)
x_edges.extend([rect.x0, rect.x1])
y_edges.extend([rect.y0, rect.y1])
x_boundaries = _span_clustered_boundaries(x_edges)
y_boundaries = _span_clustered_boundaries(y_edges)
body_start = max(1, min(int(header_row_count or 1), rows)) if rows else 0
base_cells = _span_build_base_cells(cells, x_boundaries, body_start) if strict_colspan else []
text_spans = _span_text_spans(page)
page_words = _refine_page_words(page)
claimed_words = set()
placements = []
for row_idx, row in enumerate(cells):
placement_row = []
entries = [pymupdf.Rect(cell) for cell in row if cell is not None]
intervals = _span_crossing_intervals(entries, text_spans)
intervals_by_start = {start: (end, texts) for start, end, texts in intervals}
position = 0
while position < len(entries):
interval = intervals_by_start.get(position)
if interval is not None:
end_position, _crossing_texts = interval
rect = _span_rect_union(entries[position : end_position + 1])
if strict_colspan:
candidate_cols = _span_slot_range(rect, x_boundaries)
reject, reason = _span_reject_colspan_mismatch_merge(
row_idx=row_idx,
cols=candidate_cols,
base=base_cells,
body_start=body_start,
)
if reject and _span_allow_header_colspan_merge_with_empty_part(
reason=reason,
page=page,
entries=entries,
start=position,
end=end_position,
page_words=page_words,
):
reject = False
if reject:
rect = entries[position]
position += 1
else:
position = end_position + 1
else:
position = end_position + 1
else:
rect = entries[position]
position += 1
if rect.is_empty:
continue
colspan = _span_covered_slot_count(rect.x0, rect.x1, x_boundaries)
rowspan = _span_covered_slot_count(rect.y0, rect.y1, y_boundaries)
placement_row.append(
SpanCell(
bbox=tuple(rect),
text=_span_claim_text_in_rect(page, rect, page_words, claimed_words),
colspan=colspan,
rowspan=rowspan,
)
)
placements.append(placement_row)
return placements
|