Erstellen eines mobilen Dokumentenscanners ohne Abhängigkeiten:Teile und herrsche

Der erste Schritt beim Einstieg in ein neues Projekt ist das Erstellen einer mentalen Liste der Schritte, die ausgeführt werden müssen, um nach und nach die erste Version zu erstellen. Nachdem der erste Prototyp fertig ist, ist das Polieren und Fertigstellen ziemlich einfach (solange Sie keine grundlegenden Komponenten überarbeiten). Ich hatte vor der Erstellung meines Dokumentenscanners so gut wie keine Ahnung von Computer-Vision-Algorithmen, also begann ich mit einem groben Plan und zerlegte jeden Schritt in mehrere kleinere Aufgaben, die ich einzeln angehen konnte. Ich dachte, der Prozess würde ungefähr so ​​ablaufen:

  1. Ein Bild erhalten, das ein Dokument vom Benutzer enthält
  2. Suchen Sie das Dokument im Bild
  3. Perspektive so umwandeln, dass das Dokument den gesamten rechteckigen Bereich eines neuen Bildes ausfüllt

Wenn Sie den ersten Teil dieser Serie gesehen haben, werden Sie sich daran erinnern, wie wir diese Schritte visualisiert haben.



Mit diesem Plan im Hinterkopf begann ich mit meiner Recherche. Wie ich bald feststellen würde, unterscheiden sich diese Schritte dramatisch in ihrer Schwierigkeit. Schritt 1 ist trivial, und ich hatte am Ende meines ersten Arbeitstages an dem Projekt eine funktionierende Benutzeroberfläche zur Bildauswahl. Schritt 3 ist komplex, aber relativ einfach:Diese ausgezeichnete Stack Exchange-Antwort lieferte sogar eine rudimentäre Implementierung der Perspektivtransformation in JavaScript, die ich leicht modifizieren würde, um sie in meinem Prototyp zu verwenden. Schritt 2 ist jedoch unglaublich schwierig und muss in mehrere kleinere Komponenten aufgeteilt werden.

Anfangs dachte ich, der einfachste Weg, ein Dokument in einem Bild zu finden, wäre, die vier eckigsten Punkte im Bild zu finden und diese als Ecken des eigentlichen Dokuments zu nehmen (von dem ich annahm, dass es ein Rechteck ist). Dies führte mich zu einer wilden Verfolgungsjagd mit Harris-Eckenerkennung und Konturerkennung, aber nachdem ich bei meinen zusammengehackten Implementierungen keinen Erfolg hatte, versuchte ich, auf einer höheren Ebene zu recherchieren.

Ich habe schließlich diesen Beitrag von Dropbox gefunden, der mir einen Überblick über die aktuellen State-of-the-Art-Techniken zur Dokumentenerkennung gab. Anstatt nach vier Ecken zu suchen, würde mein Programm alle Kanten im Bild finden und dann nach den vier suchen, die am wahrscheinlichsten die Kanten des Dokuments sind. Genauer gesagt müsste ich eine Bewertungsfunktion entwickeln, um alle Kombinationen von vier Kanten zu bewerten und die Kombination mit der höchsten Punktzahl in meinem perspektivischen Transformationscode zu verwenden.

Ich habe einige Verbesserungen gegenüber den Techniken von Dropbox entwickelt. Sie verwendeten den Canny-Kantenerkennungsalgorithmus, um eine visuelle Darstellung der kantenähnlichen Bereiche im Bild zu erstellen, und wandten dann eine Hough-Transformation auf diese Ausgabe an, um die mathematischen Darstellungen der wahrscheinlichsten Kanten im Bild zu finden.

Stattdessen habe ich mich dafür entschieden, nur den ersten Schritt von Canny, den Sobel-Operator, und die von ihm erzeugte Gradientenrichtung (die normalerweise als Nebeneffekt behandelt wird) zu verwenden, um die Anzahl der Stimmen im Hough-Raum zu reduzieren. Diese Änderung verbessert die Leistung erheblich (ich schätze um das 5-fache oder mehr) und reduziert das Rauschen, das in den Linien erscheint, die über die Hough-Transformation erkannt werden.

Dropbox überprüfte auch alle Kombinationen von vier Kanten, einschließlich derer, die geometrisch unmöglich waren, um ein Dokument zu sein (z. B. wenn sich zwei „Seiten“ des Papiers kreuzen und eine Sanduhrform anstelle eines Vierecks bilden) und filterte diese unmöglichen Formen heraus danach. Ich habe nur jede Kombination von vier Linien betrachtet, die ein gültiges Viereck ergeben, was auch die Leistung ein wenig verbessert, aber was noch wichtiger ist, es einfacher macht, eine geeignete Bewertungsfunktion zu entwerfen, indem der Umfang der Eingabe reduziert wird, mit der sie umgehen muss.

Schließlich habe ich mich dafür entschieden, die Bilder herunterzuskalieren, bevor ich all diese Algorithmen anwende, da dies die Wahrscheinlichkeit verringert, dass Text im Dokument Probleme bei der Kantenerkennung verursacht, und weil es die Leistung quadratisch in Bezug auf den Skalierungsfaktor verbessert, während es eine theoretische maximale Auswirkung von hat der Skalierungsfaktor an der Stelle jeder Kante. Einfacher ausgedrückt würde eine Reduzierung der Breite und Höhe des Bildes um das 5-fache die Leistung um das 25-fache verbessern, aber im schlimmsten Fall dazu führen, dass die erkannten Kanten um 5 Pixel im Vergleich zu ihrer tatsächlichen Position versetzt werden, und wenn die Eingabebilder normalerweise mindestens 1080p haben, Dieser kleine Fehler ist im endgültigen Bild nach der projektiven Transformation nicht erkennbar.

Nachdem ich meine Recherchen abgeschlossen hatte, sah mein überarbeiteter Plan wie folgt aus:

  1. Ein Bild erhalten, das ein Dokument vom Benutzer enthält
  2. Finden Sie das Dokument im Bild
    • Konvertieren Sie das Bild in eine verkleinerte Graustufenversion
    • Wenden Sie Gaußsche Unschärfe an, um Rauschen zu reduzieren
    • Verwenden Sie den Sobel-Operator, um die Gradientengröße und -richtung an jedem Pixel zu ermitteln
    • Verwenden Sie die Hough-Transformation, um die Bewertung für jede mögliche Linie zu finden, die durch das Bild verläuft. Unterteilen Sie den Winkel jeder Linie in etwa 1-Grad-Schritte von 0 bis 180 Grad und die Position in 2-Pixel-Schritte vom negativen zum positiven Wert der Hypotenuse der Bildabmessungen
    • Verwenden Sie die Verlaufsrichtung des Sobel-Operators, um in der Hough-Transformation mehr Gewicht auf Kanten zu legen, die nahezu orthogonal zum Verlauf bei jedem Pixel sind
    • Finden Sie die oberen paar tausend Zeilen in der Hough-Transformation und wenden Sie eine nicht maximale Unterdrückung an, um ein paar Dutzend Zeilen zu finden, die die höchste Endbewertung aufweisen
    • Durchsuchen Sie jede Kombination von vier Linien, die gültige Vierecke bilden, und wenden Sie eine heuristische Bewertungsfunktion an, um den Kandidaten zu finden, der am wahrscheinlichsten das Dokument ist
    • Finden Sie die Schnittpunkte der Linien im besten Kandidaten, um die vier Ecken des Dokuments zu finden
  3. Verwenden Sie eine projektive Transformation, um die Perspektive des Originalfotos in das endgültige Bild zu verzerren
    • Berechnen Sie eine projektive Transformation:Verwenden Sie Matrixalgebra, um lineare Gleichungen zu lösen, die die Koordinaten der Ecken des Dokuments in Basisvektoren abbilden, die homogene Koordinaten darstellen
    • Gehen Sie umgekehrt genauso vor, um die homogenen Koordinaten in 2D-Koordinaten auf einer flachen, rechteckigen Ebene abzubilden, die das Dokument aus der Frontalansicht darstellt (und somit das endgültige Bild)
    • Iterieren Sie über jede Zielkoordinate im projizierten Bild und finden Sie die Quellkoordinate aus dem ursprünglichen RGB-Bild (das wahrscheinlich aus Dezimalzahlen und nicht aus ganzen Zahlen besteht)
    • Verwenden Sie die bilineare Interpolation, um die Pixelwerte an den dezimalen Quellkoordinaten zu simulieren, und verwenden Sie diese Werte an den Zielkoordinaten, um das projizierte Bild zu erstellen

Wenn etwas davon über Ihren Kopf geflogen ist, machen Sie sich keine Sorgen; Ich schreibe diese Beschreibung erst, nachdem ich das Projekt abgeschlossen und mich durch die Mathematik hinter jedem dieser Algorithmen gekämpft habe. Wir werden im nächsten Artikel ausführlicher darauf eingehen, wie jeder Schritt funktioniert, beginnend mit dem Sobel-Operator.