294 lines
12 KiB
C++
294 lines
12 KiB
C++
// SPDX-License-Identifier: GPL-3.0-or-later
|
||
// SPDX-FileCopyrightText: 2025 ai-ad4 and the FreePDFEditor contributors
|
||
//
|
||
// Reconstruct.cpp — the text reconstruction pipeline (plan §4.1).
|
||
//
|
||
// Implements steps 2–5 of the pipeline on a synthetic in-memory model:
|
||
// Step 2 — run assembly: merge adjacent glyphs sharing typography.
|
||
// Step 3 — line detection: cluster by baseline.
|
||
// Step 4 — reading order: top-to-bottom, left-to-right (the synthetic corpus
|
||
// is single-column LTR; the recursive XY-cut from §4.1 reduces to
|
||
// this for the single-column case, and is where the real
|
||
// implementation would plug in).
|
||
// Step 5 — paragraph grouping: merge consecutive lines with consistent
|
||
// leading and overlapping horizontal extents unless the previous
|
||
// line ended short of the right margin (a paragraph break).
|
||
//
|
||
// The synthetic generator produces runs already in reading order along a
|
||
// horizontal baseline, so the line-detection step is a baseline cluster and the
|
||
// reading-order step is a sort. This is the 80% that the §11 risk table calls
|
||
// out ("easy to get 80% right and very visibly wrong at the last 20%"); the
|
||
// spike measures the 80% on a controlled corpus and records where it breaks.
|
||
|
||
#include "Reconstruct.h"
|
||
|
||
#include <algorithm>
|
||
#include <cmath>
|
||
#include <cstdint>
|
||
#include <set>
|
||
#include <vector>
|
||
|
||
namespace freepdfeditor::spike::b {
|
||
|
||
namespace {
|
||
|
||
// A glyph placed in absolute device-space coordinates, carrying a back-pointer
|
||
// to its source run. The pipeline works in this flattened form.
|
||
struct PlacedGlyph {
|
||
std::uint32_t unicode = 0;
|
||
float confidence = 0.0f;
|
||
float x = 0.0f; // origin x
|
||
float y = 0.0f; // origin y (baseline)
|
||
float advance = 0.0f;
|
||
float size = 0.0f;
|
||
float rise = 0.0f;
|
||
std::size_t run_index = 0;
|
||
};
|
||
|
||
// Flatten runs into placed glyphs. Each run's glyphs are laid out along its
|
||
// baseline direction starting from the first glyph's origin. For the spike the
|
||
// generator places glyphs with absolute origins, so we use those directly.
|
||
std::vector<PlacedGlyph> flatten(const std::vector<GlyphRun>& runs)
|
||
{
|
||
std::vector<PlacedGlyph> out;
|
||
for (std::size_t ri = 0; ri < runs.size(); ++ri) {
|
||
const auto& run = runs[ri];
|
||
for (const auto& g : run.glyphs) {
|
||
PlacedGlyph p;
|
||
p.unicode = g.unicode;
|
||
p.confidence = g.confidence;
|
||
p.x = g.origin.x;
|
||
p.y = g.origin.y;
|
||
p.advance = g.advance;
|
||
p.size = run.size;
|
||
p.rise = run.rise;
|
||
p.run_index = ri;
|
||
out.push_back(p);
|
||
}
|
||
}
|
||
return out;
|
||
}
|
||
|
||
// Step 3 — line detection: cluster glyphs by baseline. Two glyphs are on the
|
||
// same line if their baseline y values agree within `tol` (default 0.25 × font
|
||
// size per §4.1 step 3). We use a simple sort-then-merge cluster: sort by y,
|
||
// then walk and start a new cluster when the gap exceeds the running tolerance.
|
||
std::vector<Line> detect_lines(const std::vector<PlacedGlyph>& glyphs,
|
||
float font_size_tolerance)
|
||
{
|
||
if (glyphs.empty()) return {};
|
||
|
||
// Sort into reading order. The synthetic corpus uses PDF coordinates
|
||
// (origin bottom-left, y increases upward), so reading order is *descending*
|
||
// y — the top of the page has the largest y. Within a line, ascending x.
|
||
std::vector<PlacedGlyph> sorted = glyphs;
|
||
std::stable_sort(sorted.begin(), sorted.end(),
|
||
[](const PlacedGlyph& a, const PlacedGlyph& b) {
|
||
if (a.y != b.y) return a.y > b.y; // top of page (large y) first
|
||
return a.x < b.x;
|
||
});
|
||
|
||
std::vector<Line> lines;
|
||
Line cur;
|
||
cur.baseline_y = sorted[0].y;
|
||
cur.size = sorted[0].size;
|
||
cur.run_indices.push_back(sorted[0].run_index);
|
||
cur.x_start = sorted[0].x;
|
||
cur.x_end = sorted[0].x + sorted[0].advance;
|
||
if (sorted[0].unicode) cur.text.push_back(char32_t(sorted[0].unicode));
|
||
|
||
auto flush = [&]() {
|
||
if (!cur.run_indices.empty()) {
|
||
std::sort(cur.run_indices.begin(), cur.run_indices.end());
|
||
cur.run_indices.erase(std::unique(cur.run_indices.begin(),
|
||
cur.run_indices.end()), cur.run_indices.end());
|
||
lines.push_back(std::move(cur));
|
||
cur = Line{};
|
||
}
|
||
};
|
||
|
||
for (std::size_t i = 1; i < sorted.size(); ++i) {
|
||
const auto& g = sorted[i];
|
||
float tol = font_size_tolerance * g.size;
|
||
if (std::fabs(g.y - cur.baseline_y) <= tol) {
|
||
// same line
|
||
cur.run_indices.push_back(g.run_index);
|
||
cur.x_end = std::max(cur.x_end, g.x + g.advance);
|
||
cur.x_start = std::min(cur.x_start, g.x);
|
||
if (g.unicode) cur.text.push_back(char32_t(g.unicode));
|
||
} else {
|
||
flush();
|
||
cur.baseline_y = g.y;
|
||
cur.size = g.size;
|
||
cur.run_indices.push_back(g.run_index);
|
||
cur.x_start = g.x;
|
||
cur.x_end = g.x + g.advance;
|
||
if (g.unicode) cur.text.push_back(char32_t(g.unicode));
|
||
}
|
||
}
|
||
flush();
|
||
return lines;
|
||
}
|
||
|
||
// Step 5 — paragraph grouping. Merge consecutive lines when:
|
||
// - leading is consistent (gap between baselines ≈ font size, ±10% per §4.1)
|
||
// - horizontal extents overlap (not a column break)
|
||
// - the previous line ended near the right margin (wrapped, not a paragraph
|
||
// break). A line that ends short of the right margin starts a new paragraph.
|
||
//
|
||
// The right-margin heuristic needs the page's text column width; we infer it as
|
||
// the max x_end across all lines (the widest line). A line "ends near the right
|
||
// margin" if its x_end is within `wrap_tolerance` of the column width.
|
||
std::vector<Paragraph> group_paragraphs(const std::vector<Line>& lines)
|
||
{
|
||
if (lines.empty()) return {};
|
||
|
||
// Infer the column right edge as the maximum line end. This is a crude
|
||
// proxy; §4.1 step 4's XY-cut would give us the real column geometry.
|
||
// Use a high percentile of x_end rather than the max, so a single outlier
|
||
// line (one that overshoots the column) doesn't push the inferred right
|
||
// edge out and make every other line look "not wrapped".
|
||
std::vector<float> ends;
|
||
ends.reserve(lines.size());
|
||
for (const auto& l : lines) ends.push_back(l.x_end);
|
||
std::sort(ends.begin(), ends.end());
|
||
float column_right = ends.empty() ? 0.0f
|
||
: ends[std::min(ends.size() - 1,
|
||
std::size_t(ends.size() * 0.9))]; // 90th percentile
|
||
// A line is considered "full width" if it reaches within 10% of the column
|
||
// width (or within 18pt, whichever is larger) — i.e. it wrapped.
|
||
const float wrap_tol = std::max(column_right * 0.10f, 18.0f);
|
||
|
||
std::vector<Paragraph> paras;
|
||
Paragraph cur;
|
||
cur.line_indices.push_back(0);
|
||
// In PDF coordinates y increases upward, so the top of a block is the
|
||
// largest y and the bottom is the smallest y.
|
||
cur.top = lines[0].baseline_y;
|
||
cur.bottom = lines[0].baseline_y;
|
||
cur.left = lines[0].x_start;
|
||
cur.right = lines[0].x_end;
|
||
cur.text = lines[0].text;
|
||
|
||
auto flush = [&]() {
|
||
if (!cur.line_indices.empty()) paras.push_back(std::move(cur));
|
||
cur = Paragraph{};
|
||
};
|
||
|
||
for (std::size_t i = 1; i < lines.size(); ++i) {
|
||
const Line& prev = lines[i - 1];
|
||
const Line& line = lines[i];
|
||
// Lines are in descending-y (reading) order: prev is above, line below,
|
||
// so prev.baseline_y > line.baseline_y and leading is positive.
|
||
float leading = prev.baseline_y - line.baseline_y;
|
||
float expected_leading = line.size > 0 ? line.size : 12.0f;
|
||
expected_leading *= 1.2f; // leading is typically 1.2 × font size
|
||
// The PRIMARY paragraph-break signal is increased leading: a gap
|
||
// noticeably larger than the intra-paragraph leading. §4.1 step 5 lists
|
||
// "leading is consistent (±10%)" as a merge condition; we treat a gap
|
||
// up to ~1.45× the expected leading as intra-paragraph (allows for
|
||
// space-before/after and slightly variable leading) and a larger gap as
|
||
// a paragraph break.
|
||
bool consistent_leading = leading > 0 &&
|
||
leading <= expected_leading * 1.45f;
|
||
// Horizontal extent overlap: the lines share x range (not a column
|
||
// break, which §4.1 step 4's XY-cut would have split already).
|
||
bool overlaps = line.x_start < prev.x_end + 1.0f &&
|
||
line.x_end > prev.x_start - 1.0f;
|
||
// The SHORT-LAST-LINE signal is confirming, not primary: a paragraph
|
||
// break is more likely when the previous line ended well short of the
|
||
// column AND the leading is at the upper end of intra-paragraph range.
|
||
// Using it alone over-segments (a short first line is common). We only
|
||
// treat a short line as a break when the leading is also above 1.1×
|
||
// expected — i.e. there's *some* extra space, not just a short line.
|
||
bool prev_short = prev.x_end < column_right - wrap_tol;
|
||
bool short_line_break = prev_short && leading > expected_leading * 1.1f;
|
||
// List items always start a new paragraph.
|
||
bool starts_list = !line.marker.empty();
|
||
|
||
bool same_para = consistent_leading && overlaps &&
|
||
!short_line_break && !starts_list;
|
||
if (same_para) {
|
||
cur.line_indices.push_back(i);
|
||
cur.top = std::max(cur.top, line.baseline_y);
|
||
cur.bottom = std::min(cur.bottom, line.baseline_y);
|
||
cur.left = std::min(cur.left, line.x_start);
|
||
cur.right = std::max(cur.right, line.x_end);
|
||
if (!cur.text.empty()) cur.text.push_back(U'\n');
|
||
cur.text += line.text;
|
||
cur.is_list_item = cur.is_list_item || !line.marker.empty();
|
||
} else {
|
||
flush();
|
||
cur.line_indices.push_back(i);
|
||
cur.top = line.baseline_y;
|
||
cur.bottom = line.baseline_y;
|
||
cur.left = line.x_start;
|
||
cur.right = line.x_end;
|
||
cur.text = line.text;
|
||
cur.is_list_item = !line.marker.empty();
|
||
}
|
||
}
|
||
flush();
|
||
return paras;
|
||
}
|
||
|
||
} // namespace
|
||
|
||
ReconstructionResult reconstruct(const std::vector<GlyphRun>& runs,
|
||
float font_size_tolerance)
|
||
{
|
||
ReconstructionResult result;
|
||
auto placed = flatten(runs);
|
||
result.lines = detect_lines(placed, font_size_tolerance);
|
||
result.paragraphs = group_paragraphs(result.lines);
|
||
return result;
|
||
}
|
||
|
||
BoundaryScore score_boundaries(const std::vector<Paragraph>& predicted,
|
||
const std::vector<GroundTruthParagraph>& truth,
|
||
float tolerance)
|
||
{
|
||
BoundaryScore s;
|
||
// A boundary is the vertical gap between two consecutive paragraphs. We
|
||
// represent each boundary by the y of the gap (the bottom of the upper
|
||
// paragraph). A predicted boundary matches a true boundary if within tol.
|
||
auto boundaries_of = [&](const auto& paras, std::vector<float>& out) {
|
||
// Sort by top so boundaries are in order.
|
||
std::vector<typename std::decay<decltype(paras)>::type::value_type> sorted = paras;
|
||
std::sort(sorted.begin(), sorted.end(),
|
||
[](const auto& a, const auto& b) { return a.bottom < b.bottom; });
|
||
// The boundary *between* paragraph i and i+1 is at sorted[i].bottom
|
||
// (the bottom of the upper one). With N paragraphs there are N-1 gaps.
|
||
for (std::size_t i = 0; i + 1 < sorted.size(); ++i) {
|
||
out.push_back(sorted[i].bottom);
|
||
}
|
||
};
|
||
|
||
std::vector<float> pred_b, true_b;
|
||
boundaries_of(predicted, pred_b);
|
||
boundaries_of(truth, true_b);
|
||
s.predicted_boundaries = pred_b.size();
|
||
s.true_boundaries = true_b.size();
|
||
|
||
// Greedy match: each true boundary matches at most one predicted boundary
|
||
// within tolerance, nearest first.
|
||
std::vector<char> used(pred_b.size(), 0);
|
||
for (float tb : true_b) {
|
||
float best_dist = tolerance;
|
||
int best_idx = -1;
|
||
for (std::size_t j = 0; j < pred_b.size(); ++j) {
|
||
if (used[j]) continue;
|
||
float d = std::fabs(pred_b[j] - tb);
|
||
if (d <= best_dist) { best_dist = d; best_idx = int(j); }
|
||
}
|
||
if (best_idx >= 0) { used[std::size_t(best_idx)] = 1; ++s.matched; }
|
||
}
|
||
|
||
s.precision = s.predicted_boundaries ? double(s.matched) / double(s.predicted_boundaries) : 0.0;
|
||
s.recall = s.true_boundaries ? double(s.matched) / double(s.true_boundaries) : 0.0;
|
||
s.f1 = (s.precision + s.recall) > 0
|
||
? 2.0 * s.precision * s.recall / (s.precision + s.recall) : 0.0;
|
||
return s;
|
||
}
|
||
|
||
} // namespace freepdfeditor::spike::b
|