Technik zur Korrektur von Seitenverzerrungen

 (mzucker.github.io)
2 Punkte von GN⁺ 2024-05-14 | 1 Kommentare | Auf WhatsApp teilen
  • Modelliert 3D-Pose und Krümmung, um ein Foto eines gebogenen Dokuments in ein flaches Bild umzuwandeln, und formuliert das Ganze als Optimierungsproblem zur Ausrichtung von Text-Referenzpunkten
  • Folgt einem Ablauf wie Leptonica und CTM: Text wird zeilenweise segmentiert, danach wird eine Koordinatentransformation gesucht, durch die die Zeilen parallel und nahezu horizontal erscheinen
  • Das Modell umfasst den Rotationsvektor r, den Translationsvektor t, die Krümmungssteigungen α, β sowie x- und y-Offsets der Text-Spans und minimiert den Reprojektionsfehler
  • Die Pipeline besteht aus Zuschneiden der Seitengrenzen, Erkennen von Textkonturen, Zusammensetzen von Spans, Sampling von Referenzpunkten, Erzeugen von Initialwerten, Powell-Optimierung und Remapping mit cv2.remap
  • In den Beispielausführungen lagen die Parameterzahlen bei 104 bis 600, die Gesamtlaufzeit bei 5,3 bis 24,8 Sekunden; der Großteil entfiel auf die Optimierung, sodass mit anderen Solvern oder kompilierten Sprachen noch Spielraum für Beschleunigung bleibt

Eine gebogene Seite als Optimierungsproblem lösen

  • Ein bestehendes Skript zum Erzeugen von PDFs aus Fotos handschriftlicher Notizen beschränkte sich auf adaptiveThreshold und das Bündeln mehrerer Bilder zu einem PDF; bei Fotos archivierter Dokumente verbog sich der Text jedoch stark durch Seitenwölbung
  • Ziel ist ein Programm, das ein Foto einer gebogenen Seite automatisch in ein flaches Dokumentbild umwandelt
  • Der Code ist auf GitHub unter page_dewarp veröffentlicht

Grundablauf aus Leptonica und CTM

  • Die Entzerrung von Dokumentbildern ist ein bekanntes Problem und ist auch in Dan Bloombergs Open-Source-Bildverarbeitungsbibliothek Leptonica implementiert
  • Zu den Referenzen gehören eine Zusammenfassung der Ergebnisse eines Dewarping-Wettbewerbs und ein Paper zum Siegerverfahren, dem Coordinate Transform Model, kurz CTM
  • Leptonica und CTM teilen das Problem grundsätzlich in zwei Schritte auf
    • Text wird zeilenweise getrennt
    • Es wird eine Verzerrungs- oder Koordinatentransformation gesucht, sodass die Zeilen parallel und horizontal werden
  • Diese Implementierung beschreibt die äußere Form der Seite mit mehreren Parametern
    • r, t: Rotations- und Translationsvektor für 3D-Ausrichtung und Position der Seite
    • α, β: zwei Steigungen, die die Krümmung der Seitenoberfläche bestimmen
    • y₁ ... yₙ: vertikale Offsets von n horizontalen Spans auf der Seite
    • xᵢ: horizontale Offsets für mehrere Referenzpunkte innerhalb jedes Spans

3D-Krümmungsfläche und Reprojektionsfehler

  • Die 3D-Form der Seite wird als Oberfläche beschrieben, die entsteht, indem eine Kurve entlang der lokalen y-Achse gezogen wird
  • Die horizontale Seitenkoordinate x wird auf eine Verschiebung in z-Richtung der Oberfläche abgebildet; horizontale Querschnitte werden als kubischer Spline modelliert
    • Die beiden Endpunkte des Splines sind auf 0 fixiert
    • Die Form des Splines wird allein durch die Endpunktsteigungen α, β bestimmt
  • Sind Pose- und Krümmungsparameter festgelegt, wird jede (x, y)-Koordinate der Seite auf eine bestimmte Position in der Bildebene projiziert
  • Aus dem Originalfoto werden Keypoints horizontaler Text-Spans ermittelt; ausgehend von einer Anfangsschätzung werden Parameter gesucht, die den Reprojektionsfehler der Keypoints minimieren
  • Vor der Optimierung wird angenommen, dass keine Krümmung vorliegt, sodass die reprojizierten Punkte auf einer geraden Linie liegen; nach der Optimierung decken sich die Modell-Projektionspunkte fast mit den tatsächlich erkannten Keypoints

Bildverarbeitungs-Pipeline

  • Seitengrenzen zuschneiden

    • Statt das gesamte Bild zu verwenden, wird nur der mittlere Bereich mit einem festen Rand zugeschnitten, um unnötige Randbereiche zu vermeiden
    • Eine intelligente Erkennung der Seitengrenzen wird nicht verwendet

  • Textkonturen erkennen

    • Zunächst wird ein adaptiver Threshold angewendet
    • Mit einer horizontalen Box wird morphological dilation) ausgeführt, um horizontal benachbarte Maskenpixel zu verbinden
    • Mit einer vertikalen Box wird erosion) ausgeführt, um Rauschen mit einer Pixelhöhe zu entfernen
    • Nach einer connected component analysis werden zu hohe oder zu dicke Blobs herausgefiltert
    • Die verbleibenden Textkonturen werden per PCA durch das am besten passende Liniensegment approximiert

  • Ergänzende Erkennung horizontaler Linien

    • Da einige Eingaben tabellenartig waren und viel vertikalen Text enthielten, wird bei unzureichender Erkennung horizontalen Texts auch versucht, horizontale Linien oder Rules zu erkennen

Aufbau von Text-Spans und Sampling von Referenzpunkten

  • Um erkannte Konturen demselben horizontalen Span zuzuordnen, werden für alle Konturpaare Kandidaten-Edges gebildet und deren Kosten berechnet
  • Wenn sich zwei Konturen in Längsrichtung stark überlappen, zu weit voneinander entfernt sind oder ihre Winkel stark auseinanderliegen, werden die Kosten auf unendlich gesetzt
  • Die Kosten gültiger Edges werden als lineare Kombination aus Distanz und Winkeländerung berechnet
  • Die Edges werden nach Kosten sortiert; anschließend wird ein gieriges Verfahren mit quadratischer Laufzeit verwendet, das nur dann verbindet, wenn beide Konturen noch nicht verbunden sind
    • Da der Großteil der Laufzeit in die Optimierung fließt, war die quadratische Zeitkomplexität dieses Schritts kein großes Problem
  • Nachdem Spans gebildet wurden, werden zu kleine Spans entfernt, die nicht zur Bestimmung des Modells beitragen
  • Da das Parametermodell diskrete Referenzpunkte benötigt, wird etwa alle 20 Pixel entlang der Textkontur ein Keypoint ausgewählt

Initialwerte und Powell-Optimierung

  • Die durchschnittliche Richtung aller Spans wird per PCA geschätzt
  • Mithilfe der Hauptkomponenten aus dem PCA-Ergebnis werden die initialen x-, y-Koordinaten sowie die Pose einer flachen Seite ohne Krümmung analytisch festgelegt
  • Für die Reprojektion wird ein kubischer Spline gesampelt, um den z-Offset der Objektpunkte zu erhalten; anschließend werden diese mit OpenCV-Funktionen in die Bildebene projiziert
    • cv2.solvePnP
    • cv2.projectPoints
  • Zur Minimierung des Reprojektionsfehlers werden scipy.optimize.minimize und der 'Powell'-Solver verwendet
    • Er wird als Black-Box-Optimierer ohne Ableitungen genutzt
    • Das Problem selbst entspricht nichtlinearer kleinster Quadrate
    • Andere Solver oder spezialisierte Solver für nichtlineare kleinste Quadrate wurden nicht umfassend getestet
  • Nahezu 100 % der Programmlaufzeit entfallen auf diesen Optimierungsschritt

Remapping und Erzeugung des Ausgabebilds

  • Nach Abschluss der Optimierung werden nur r, t, α, β extrahiert, um eine Koordinatentransformation zu erzeugen
  • Das eigentliche Dewarping entsteht, indem ein dichtes Mesh aus 3D-Seitenpunkten mit cv2.projectPoints projiziert und diese Bildkoordinaten an cv2.remap übergeben werden
  • Das Endergebnis wird mit cv2.adaptiveThreshold und Pillow als bi-level PNG gespeichert

Beispielergebnisse und Laufzeiten

  • Das GitHub-Repository enthält mehrere example images
  • Die Statistiken für eine Ausführung auf einem einzelnen 2012 MacBook Pro lauten wie folgt
Eingabe Spans Keypoints Parameter Optimierungszeit Gesamtzeit
boston_cooking_a.jpg 38 554 600 23,3 s 24,8 s
boston_cooking_b.jpg 38 475 521 18,0 s 18,8 s
linguistics_thesis_a.jpg 20 161 189 5,1 s 6,1 s
linguistics_thesis_b.jpg 7 89 104 4,2 s 5,3 s
  • Selbst das kleinste Modell hat 104 Parameter, das größte 600; es handelt sich also nicht um ein kleines Optimierungsproblem
  • Die Optimierungsgeschwindigkeit ließe sich möglicherweise verbessern, indem andere Methoden ausprobiert oder kompilierte Sprachen verwendet werden

Verbleibende Grenzen

  • Der gesamte Ansatz besteht darin, etwas Hintergrundwissen zu lesen und das gesamte Problem als Ausgabe eines Optimierungsprozesses zu formulieren
  • Diese Methode erinnert an deformable part models und active appearance models, ist aber nicht so ausgefeilt wie diese
  • Leptonica und CTM versuchen, nicht nur vertikale Verzerrungen, sondern auch horizontale Verzerrungen zu modellieren und zu korrigieren
  • Diese Implementierung behandelt die Korrektur horizontaler Verzerrungen nicht
    • Da der kubische Spline nicht nach arc length parametrisiert ist, wird Text in Bereichen mit großer Spline-Steigung leicht komprimiert
    • Da das Projekt hauptsächlich ein Proof of Concept war, wurde dieses Problem nicht weiterverfolgt
  • Der finale Code ist im GitHub-Repository veröffentlicht; ausführliche ergänzende Kommentare sind noch nicht ausreichend vorhanden

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-05-14
Hacker-News-Kommentare

  • Man sollte vorsichtig damit sein, wie der Autor eine starke Schwellwertverarbeitung auf die Ausgabe anzuwenden.
    Bei normalen Textseiten funktioniert das ziemlich gut, aber ich habe bei mehreren Seiten in Google Books gesehen, dass Illustrationen oder kleine Fußnoten bis zur Unlesbarkeit zerstört werden.
    Wenn der Google-Books-Scan die einzige Quelle ist, steckt man komplett fest.

    • Ist die Schwellwertverarbeitung nicht dazu da, Referenzpunkte zu finden, um die Parameter für die Verzerrungskorrektur auszuwählen?
      Sobald man die Referenzpunkte gefunden hat, sollte man diese Parameter doch auf das Originalbild anwenden können.

  • Es ist frustrierend, dass wir 2024 haben und Dokumentenscanner-Apps so eine Funktion immer noch nicht standardmäßig eingebaut haben.

    • An meiner Schule verwenden wir GeniusScan, und das hat diese Funktion: https://blog.thegrizzlylabs.com/2024/03/genius-scan-7.16.htm...
    • Sehr gut.
      Der Schlüssel dafür, dass dieser Ansatz gut funktioniert, scheint ein niedrigdimensionales Seitenverformungsmodell zu sein, das optimiert wird.
      Das ist genau ein Problem in YC-Größenordnung. Ein paar Wochen bis zum Marktstart, die Launch-Kosten dürften im Bereich einiger Hunderttausend Dollar liegen.
      Apples Phone-App erfordert viel zu viele manuelle Anpassungen, und zu Microsofts Office Lens / Microsoft Lens gibt es Bewertungen wie „die Ränder drehen am Ende völlig durch und sehen schrecklich aus“.
      Es gibt also einen Markt für ein Produkt, das einfach gut funktioniert, und ein Exit durch Verkauf an die üblichen Übernahmekandidaten scheint ebenfalls möglich.
    • Ich meine, Google Drive hat das früher ordentlich gemacht, aber in den letzten Jahren fühlt es sich deutlich schlechter an.
    • Das Produktmanagement dürfte entschieden haben, dass das technische Risiko es nicht wert ist.
      Vermutlich hielten sie es für zu komplex und mathematisch und kamen stattdessen zu dem Schluss, dass ein Modell, das die Social-Media-Aktivitäten der Nutzer auswertet, um Benachrichtigungen noch genauer zu timen, bessere Nutzerkennzahlen liefern würde.
      Beim Versuch, die Abwanderungsrate zu senken, haben die Entscheidungsträger also streng datengetrieben entschieden.
    • vflat ist für diesen Zweck gut.

  • Nachdem John Warnock als CEO von Adobe zurückgetreten war, engagierte er sich stärker bei Octavo, einem Unternehmen zur Bewahrung seltener historischer Bücher.
    Eine der Herausforderungen, vor denen sie standen, war das Glätten der Krümmung gescannter Seiten, die man nicht flach drücken konnte.
    https://en.m.wikipedia.org/wiki/Rare_Book_Room

  • Der Artikel war hervorragend.
    Man könnte ihn im Unternehmen als Beispiel dafür heranziehen, wie man technische Projekte und die zugehörigen Entscheidungen effektiv dokumentiert.

  • An der Uni wollte ich einmal eine App zum Scannen farblich codierter Notizen bauen und stieß dabei auf ein anderes Problem.
    Von oben nach unten auf der Seite verschoben sich die Farben, sodass es schwierig war, blauen Stift und grünen Stift zuverlässig zu unterscheiden.
    Irgendwann sollte ich mir das noch einmal ansehen.

    • Wenn man annimmt, dass sich der weiße Hintergrund auf dieselbe Weise verschiebt, ist ein guter Trick, das Bild zu kopieren, sehr stark weichzuzeichnen und dann das Originalbild durch diese weichgezeichnete Version zu teilen.
      Dadurch werden niederfrequente Farb-/Helligkeitsänderungen praktisch entfernt.
      Das wird häufig verwendet, um Schatten zu entfernen, wenn man Papier fotografiert; bei Farbverläufen dürfte es genauso funktionieren.

  • Sieht ausreichend gut aus.
    Allerdings wirkt das Verformungsmodell etwas zu global.
    Einige der komplexeren Verformungen des Papiers werden vom Modell nicht erfasst und erscheinen im Endergebnis als Restverzerrungen.

  • Bei der Installation tritt ein Fehler auf:
    ERROR: Could not find a version that satisfies the requirement cv2>=3.0 (from versions: none)
    ERROR: No matching distribution found for cv2>=3.0
    Ich habe ein GitHub-Issue erstellt.

  • Sehr cool.
    Es wäre schön, eine brauchbare Dokumentenscan-App für Mobilgeräte zu haben – eine, die Verzerrungskorrektur, Schwellwertverarbeitung und PDF-Erzeugung gut beherrscht.
    Im Moment hänge ich an Adobe Scan, weil die Ergebnisse dort noch am besten sind, aber die Verzerrungskorrektur ist trotzdem ziemlich mies.

    • Ich habe gehört, Microsoft Lens sei gut, aber wenn ich es auf meinem Telefon öffne, hängt es sich einfach auf.

  • Wirklich interessant zu lesen.
    Scheint ein Artikel zu sein, den ich 2016 verpasst habe; mir gefällt, dass der gesamte Ablauf gut sichtbar wird: „Es gab dieses Problem, und durch den Einsatz kluger Techniken entstand eine gut funktionierende Lösung.“
    Persönlich werde ich so etwas wohl nie brauchen, aber es ist ein hervorragendes Beispiel dafür, ein Problem auf gute Weise anzugehen und innerhalb dessen, was die Ausgaben und Erwartungen zulassen, angemessene Kompromisse zu schließen.
    Der Artikel ist außerdem gut geschrieben und gut erklärt.

  • Wenn man das Buch nicht visuell darstellen muss und nur OCR braucht, kann man diesen Schritt vermutlich überspringen.
    Google hat dieses Problem schon vor mehr als zehn Jahren gelöst: https://hardware.slashdot.org/story/09/05/15/1834246/how-goo...
    Wenn das Manuskript wirklich wertvoll ist, ist auch eine berührungslose Verzerrungskorrektur per Röntgentomografie möglich: https://scrollprize.org/tutorial1

    • Dann müsste man brauchbare Software finden und empfehlen.
      Google hat dafür Hardware eingesetzt, und die Sache mit der Röntgentomografie klingt stark nach ChatGPT.
      Trotzdem ist die Methode aus diesem Artikel für den Stand von 2016 schön und einfach.