File size: 15,322 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 | """
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 union stage, behind find_tables(union=True): fuse the layout
analyzer's table grids with the line-based finder's candidates. Table,
TableFinder and _iou come from pymupdf.table; find_tables is imported lazily.
"""
import pymupdf
from pymupdf.table import CHARS, EDGES, Table, TableFinder, _iou
# ---------------------------------------------------------------------------
# find_tables(union=True) fuses two table sources on one page: PRIMARY grids
# from the layout analyzer (each "table" group's GridPrediction, read from
# page.get_layout(return_raw=True) by _layout_table_grids in its raw form) and
# CANDIDATE grids from a nested line-based find_tables. A candidate matching a
# primary 1:1 (high IoU) may REPLACE its grid (grid-ref), several candidates
# each contained in one primary may SPLIT it, and candidates owned by no primary
# are APPENDED. The output order -- primaries (kept / grid-ref'd / split) then
# appended candidates -- is contractual: downstream consumers key tables by it.
#
# _layout_table_grids also replaces find_tables' make_table_from_bbox path,
# which silently yields an empty Table because the stext grid block it needs is
# not emitted; make_table_from_bbox is left in place pending a separate cleanup.
# ---------------------------------------------------------------------------
_UNION_STRATEGY = "lines_strict" # candidate detection strategy
_UNION_GRID_REF_IOU = 0.9 # min IoU for a 1:1 grid-ref replacement
_UNION_GRID_REF_SPAN_MULT_GATE = True # reject under-segmented candidate grids
_UNION_GRID_REF_SPAN_MULT_THRESHOLD = 3.0 # max horizontally-separated span groups per cell
_UNION_OWNER_CONTAINMENT = 0.85 # min containment for a split candidate's owner
_UNION_OWNER_AMBIGUOUS_OVERLAP = 0.25 # overlap above which an unowned candidate is suppressed
def _layout_table_grids(page):
"""Primary table grids from the raw layout analyzer result.
Reads page.layout_information in its raw (return_raw=True) form and yields a
``(bbox, grid)`` pair per "table" group -- ``grid`` is the full row-major cell
grid built from the group box plus its interior GridPrediction lines, in
layout (reading) order. Boxes without a usable grid are skipped.
"""
grids = []
for group in (page.layout_information or []):
if not isinstance(group, dict):
# The union path needs the raw (return_raw=True) layout form; the
# normalized [x0, y0, x1, y1, class] tuples carry no table_grid.
continue
if group.get("class_name") != "table":
continue
group_bbox = group.get("group_bbox")
grid_pred = group.get("table_grid")
if not group_bbox or grid_pred is None:
continue
x0, y0, x1, y1 = group_bbox[0], group_bbox[1], group_bbox[2], group_bbox[3]
h_lines = [y0] + [h + y0 for h in grid_pred.h_lines] + [y1]
v_lines = [x0] + [v + x0 for v in grid_pred.v_lines] + [x1]
grid = []
for i in range(len(h_lines) - 1):
row = []
for j in range(len(v_lines) - 1):
row.append((v_lines[j], h_lines[i], v_lines[j + 1], h_lines[i + 1]))
grid.append(row)
grids.append((pymupdf.Rect(group_bbox[:4]), grid))
return grids
def _union_line_candidates(page):
"""Line-based table candidates for the union stage as ``(bbox, grid)`` pairs.
Runs a nested find_tables (strategy=_UNION_STRATEGY, use_layout=False) and
keeps each detected table's bbox and row-major cell grid (Table.rows, None
for a gap), deduped by rounded bbox. Returns ``(candidates, finder)``; the
finder is reused as the returned TableFinder shell.
"""
# Imported here, not at module top, to break the import cycle: this
# module is itself imported lazily by table.find_tables (union path).
from pymupdf.table import find_tables
finder = find_tables(page, strategy=_UNION_STRATEGY, use_layout=False)
candidates = []
seen = set()
for tab in (getattr(finder, "tables", None) or []):
try:
bbox = pymupdf.Rect(tab.bbox)
except (ValueError, TypeError):
continue
if bbox.is_empty:
continue
grid = [[cell for cell in row.cells] for row in (tab.rows or [])]
if not grid:
continue
key = tuple(round(value) for value in bbox)
if key in seen:
continue
seen.add(key)
candidates.append((bbox, grid))
return candidates, finder
def _union_rect_area(rect):
return max(0.0, float(rect.x1 - rect.x0)) * max(0.0, float(rect.y1 - rect.y0))
def _union_intersection_area(left, right):
x0 = max(float(left.x0), float(right.x0))
y0 = max(float(left.y0), float(right.y0))
x1 = min(float(left.x1), float(right.x1))
y1 = min(float(left.y1), float(right.y1))
if x1 <= x0 or y1 <= y0:
return 0.0
return (x1 - x0) * (y1 - y0)
def _union_x_overlap(left, right):
return max(0.0, min(float(left.x1), float(right.x1)) - max(float(left.x0), float(right.x0)))
def _union_find_owner(candidate_bbox, existing_bboxes):
"""The primary a split candidate belongs inside, plus an ambiguity flag.
Returns ``(owner_index, ambiguous)``: owner is the best-contained primary
(candidate>=_UNION_OWNER_CONTAINMENT inside it), else None; ambiguous is True
when the candidate overlaps some primary enough to be unsafe to append."""
candidate_area = _union_rect_area(candidate_bbox)
if candidate_area <= 0:
return None, True
best_owner = None
best_containment = 0.0
ambiguous = False
for index, existing_bbox in enumerate(existing_bboxes):
existing_area = _union_rect_area(existing_bbox)
inter_area = _union_intersection_area(candidate_bbox, existing_bbox)
if inter_area <= 0 or existing_area <= 0:
continue
candidate_containment = inter_area / candidate_area
existing_coverage = inter_area / existing_area
if candidate_containment >= _UNION_OWNER_CONTAINMENT and candidate_containment > best_containment:
best_owner = index
best_containment = candidate_containment
elif candidate_containment >= _UNION_OWNER_AMBIGUOUS_OVERLAP or existing_coverage >= _UNION_OWNER_AMBIGUOUS_OVERLAP:
ambiguous = True
return best_owner, ambiguous
def _union_text_span_rects(page):
"""Non-empty page text-span rects, cached on the page.
Drives the grid-ref span-multiplicity gate: every non-blank span as a bare
rect."""
cached = getattr(page, "_union_text_spans_cache", None)
if cached is not None:
return cached
spans = []
for block in page.get_text("dict").get("blocks", []) or []:
for line in block.get("lines", []) or []:
for span in line.get("spans", []) or []:
if not str(span.get("text") or "").strip():
continue
bbox = span.get("bbox")
if not bbox:
continue
rect = pymupdf.Rect(bbox)
if not rect.is_empty:
spans.append(rect)
try:
setattr(page, "_union_text_spans_cache", spans)
except Exception:
pass
return spans
def _union_cell_span_group_count(cell, text_spans):
"""Max horizontally-separated text-span groups on any single text line in a cell."""
line_bands = []
for span in text_spans:
center_y = (float(span.y0) + float(span.y1)) / 2.0
if center_y < float(cell.y0) - 1.0 or center_y > float(cell.y1) + 1.0:
continue
if _union_x_overlap(span, cell) <= 1.0:
continue
x0 = max(float(cell.x0), float(span.x0))
x1 = min(float(cell.x1), float(span.x1))
if x1 <= x0:
continue
for index, (band_y, intervals) in enumerate(line_bands):
if abs(center_y - band_y) <= 4.0:
intervals.append((x0, x1))
line_bands[index] = ((band_y + center_y) / 2.0, intervals)
break
else:
line_bands.append((center_y, [(x0, x1)]))
best = 0
for _, intervals in line_bands:
groups = 0
last_x1 = None
for x0, x1 in sorted(intervals):
if last_x1 is None or x0 - last_x1 > 4.0:
groups += 1
last_x1 = x1
else:
last_x1 = max(last_x1, x1)
best = max(best, groups)
return best
def _union_span_multiplicity(page, grid):
"""Max cell span-group count over a grid (high => under-segmented grid)."""
if page is None:
return None
text_spans = _union_text_span_rects(page)
best = None
for row in grid:
for cell in row:
if cell is None:
continue
rect = pymupdf.Rect(cell)
if rect.is_empty:
continue
count = _union_cell_span_group_count(rect, text_spans)
if count > 0:
best = count if best is None else max(best, count)
return float(best) if best is not None else None
def _union_one_to_one_grid_refs(existing, candidates, *, iou_threshold, page, span_mult_gate, span_mult_threshold):
"""Primaries a candidate can grid-ref (replace grid with), 1:1 by IoU.
``existing``/``candidates`` are ``(bbox, grid)`` lists. Returns ``(refs,
consumed)``: ``refs`` maps a primary index to the candidate supplying its
grid (mutual 1:1 IoU>=threshold matches passing the span-multiplicity gate),
``consumed`` the candidate indexes used."""
existing_matches = {}
candidate_matches = {}
for existing_index, (existing_bbox, _grid) in enumerate(existing):
for candidate_index, (candidate_bbox, _cgrid) in enumerate(candidates):
iou = _iou(existing_bbox, candidate_bbox)
if iou >= iou_threshold:
existing_matches.setdefault(existing_index, []).append((candidate_index, float(iou)))
candidate_matches.setdefault(candidate_index, []).append((existing_index, float(iou)))
refs = {}
consumed = set()
for existing_index, matches in existing_matches.items():
if len(matches) != 1:
continue
candidate_index, _ = matches[0]
if len(candidate_matches.get(candidate_index, [])) != 1:
continue
if span_mult_gate:
span_mult = _union_span_multiplicity(page, candidates[candidate_index][1])
if span_mult is not None and span_mult >= span_mult_threshold:
continue
refs[existing_index] = candidates[candidate_index]
consumed.add(candidate_index)
return refs, consumed
def _union_replace_append(existing, candidates, *, page, grid_ref, grid_ref_iou, span_mult_gate, span_mult_threshold):
"""Fuse primary and candidate ``(bbox, grid)`` entries.
Applies grid-ref replacement, split replacement (>=2 candidates owned by one
primary replace it, ordered by y0/x0) and append of unowned candidates,
returning the fused entry list in the contractual order."""
existing_bboxes = [entry[0] for entry in existing]
if grid_ref:
grid_refs, consumed = _union_one_to_one_grid_refs(
existing,
candidates,
iou_threshold=grid_ref_iou,
page=page,
span_mult_gate=span_mult_gate,
span_mult_threshold=span_mult_threshold,
)
else:
grid_refs, consumed = {}, set()
replacements = {}
append_candidates = []
for candidate_index, candidate in enumerate(candidates):
if candidate_index in consumed:
continue
owner_index, ambiguous = _union_find_owner(candidate[0], existing_bboxes)
if owner_index is not None:
replacements.setdefault(owner_index, []).append(candidate)
elif ambiguous:
continue # overlaps a primary but is not contained -> suppress
else:
append_candidates.append(candidate)
final_replacements = {
index: sorted(items, key=lambda entry: (float(entry[0].y0), float(entry[0].x0)))
for index, items in replacements.items()
if len(items) >= 2
}
entries = []
for index, entry in enumerate(existing):
if index in final_replacements:
entries.extend(final_replacements[index])
elif index in grid_refs:
# Grid-ref: keep the primary's (layout) bbox, take the candidate grid.
entries.append((entry[0], grid_refs[index][1]))
else:
entries.append(entry)
entries.extend(append_candidates)
return entries
def _find_tables_union(page):
"""Detect a page's tables by fusing layout grids with line-based candidates.
Ensures the raw layout (computed only when page.layout_information is None,
like the official use_layout path), reads primary grids, detects candidates,
applies grid-ref / split / append, and returns a TableFinder whose .tables
carry the fused grids in contractual order (grid-ref tables keep their
explicit layout bbox)."""
if page.layout_information is None:
page.get_layout(return_raw=True)
primaries = _layout_table_grids(page)
candidates, finder = _union_line_candidates(page)
entries = _union_replace_append(
primaries,
candidates,
page=page,
grid_ref=True,
grid_ref_iou=_UNION_GRID_REF_IOU,
span_mult_gate=_UNION_GRID_REF_SPAN_MULT_GATE,
span_mult_threshold=_UNION_GRID_REF_SPAN_MULT_THRESHOLD,
)
if finder is None:
# Candidate detection failed mid-way; the nested find_tables may have
# left partially-filled EDGES/CHARS state behind, and TableFinder's
# constructor runs a full detection from that state -- clear it first
# so the fallback really is an empty shell.
EDGES.clear()
CHARS.clear()
finder = TableFinder(page)
tables = []
for bbox, grid in entries:
flat = [cell for row in grid for cell in row if cell is not None]
if not flat:
continue
tables.append(Table(page, flat, bbox=bbox))
finder.tables = tables
return finder
|