Ich schreibe eine einfache OCR-Lösung für eine endliche Menge von Zeichen. Das heißt, ich weiß genau, wie alle 26 Buchstaben im Alphabet aussehen werden. Ich verwende C # und kann leicht feststellen, ob ein bestimmtes Pixel als schwarz oder weiß behandelt werden sollte.
Ich erzeuge eine Matrix aus schwarzen / weißen Pixeln für jedes einzelne Zeichen. So könnte beispielsweise der Buchstabe I (Großbuchstabe i) folgendermaßen aussehen:
%Vor%Hinweis: Alle Punkte, die ich später in diesem Beitrag verwende, gehen davon aus, dass das obere linke Pixel (0, 0), das untere rechte Pixel (4, 4) ist. 1 sind schwarze Pixel und 0 weiße Pixel.
Ich würde eine entsprechende Matrix in C # wie folgt erstellen:
%Vor%Ich weiß, dass ich diesen Teil wahrscheinlich optimieren könnte, indem ich stattdessen ein mehrdimensionales Array verwende, aber lassen Sie uns das jetzt ignorieren, dies dient der Veranschaulichung. Jeder Buchstabe hat genau die gleichen Abmessungen, 10px mal 11px (10px mal 11px ist die tatsächliche Größe eines Charakters in meinem realen Programm. Ich habe das in diesem Beitrag auf 5px um 5px vereinfacht, da es viel einfacher ist, die Buchstaben mit 0 zu zeichnen und 1 ist auf einem kleineren Bild).
Wenn ich nun einen 10 x 11 Pixel großen Teil eines Bildes zur Analyse mit OCR gebe, müsste es auf jeden einzelnen Buchstaben (26) auf jedem einzelnen Pixel (10 x 11 = 110) laufen, was 2.860 (26) bedeuten würde * 110) Iterationen (im schlimmsten Fall) für jedes einzelne Zeichen.
Ich dachte, dass dies optimiert werden könnte, indem man die einzigartigen Eigenschaften jedes Charakters definiert. Nehmen wir zum Beispiel an, dass der Satz von Zeichen nur aus 5 verschiedenen Buchstaben besteht: I, A, O, B und L. Diese könnten wie folgt aussehen:
%Vor%Nachdem ich die einzigartigen Eigenschaften jedes Charakters analysiert habe, kann ich die Anzahl der Tests, die durchgeführt werden müssen, um nach einem Charakter zu suchen, erheblich reduzieren. Zum Beispiel könnte ich für das "I" -Charakteristika seine einzigartigen Eigenschaften so definieren, dass es ein schwarzes Pixel in der Koordinate (3, 0) hat, da keine anderen Zeichen dieses Pixel als schwarz haben. Also statt 110 Pixel für eine Übereinstimmung mit dem "I" -Zeichen zu testen, habe ich es auf einen 1-Pixel-Test reduziert.
So könnte es für alle diese Zeichen aussehen:
%Vor%Dies ist schwierig manuell für 5 Zeichen zu tun und wird umso schwieriger, je größer die Anzahl der hinzugefügten Buchstaben ist. Sie möchten außerdem sicherstellen, dass Sie über die Mindestanzahl eindeutiger Merkmale eines Buchstabens verfügen, da Sie ihn so gut wie möglich optimieren möchten.
Ich möchte einen Algorithmus erstellen, der die eindeutigen Merkmale aller Buchstaben identifiziert und ähnlichen Code wie oben generiert. Ich würde dann diese optimierte Schwarz / Weiß-Matrix verwenden, um Zeichen zu identifizieren.
Wie nehme ich die 26 Buchstaben, die alle ihre schwarzen / weißen Pixel enthalten (zB den CreateLetter Codeblock) und wandle sie in einen optimierten Satz einzigartiger Merkmale um, die einen Buchstaben definieren (zB den neuen OcrLetter () Codeblock) ) Und wie würde ich garantieren, dass es der effizienteste Definitionssatz von einzigartigen Merkmalen ist (zB anstatt 6 Punkte als die einzigartigen Merkmale zu definieren, könnte es einen Weg geben, es mit 1 oder 2 Punkten zu machen, wie der Buchstabe "I" in meinem Beispiel konnte).
Eine alternative Lösung, die ich mir ausgedacht habe, ist die Verwendung einer Hash-Tabelle, die sie von 2.860 Iterationen auf 110 Iterationen reduziert, eine 26-fache Reduzierung. So könnte es funktionieren:
Ich würde es mit Daten füllen, die der folgenden ähneln:
%Vor%Wenn ich nun eine Stelle im zu verarbeitenden Bild erreiche, konvertiere ich sie in eine Zeichenkette wie: "01110 00100 00100 00100 01110" und finde sie einfach in der Hash-Tabelle. Diese Lösung scheint sehr einfach zu sein, erfordert jedoch immer noch 110 Iterationen, um diese Zeichenfolge für jeden Buchstaben zu generieren.
In der großen O-Notation ist der Algorithmus derselbe, da O (110N) = O (2860N) = O (N) für N Buchstaben, die auf der Seite zu verarbeiten sind. Es wird jedoch immer noch um einen konstanten Faktor von 26 verbessert, eine signifikante Verbesserung (z.B. statt 26 Minuten dauert es 1 Minute).
Update: Die meisten der bisher angebotenen Lösungen haben sich nicht mit der Identifizierung der einzigartigen Merkmale eines Charakters befasst und bieten stattdessen alternative Lösungen. Ich suche immer noch nach dieser Lösung, die, soweit ich das beurteilen kann, der einzige Weg ist, die schnellste OCR-Verarbeitung zu erreichen.
Ich habe gerade eine Teillösung gefunden:
Speichern Sie für jedes Pixel im Raster die Buchstaben, die es enthalten, als schwarzes Pixel.
Verwenden Sie diese Buchstaben:
%Vor%Sie hätten so etwas:
%Vor%Nun müssen Sie für jeden Buchstaben, um die einzigartigen Merkmale zu finden, sehen, zu welchen Eimern er gehört, sowie die Anzahl der anderen Buchstaben im Eimer. Nehmen wir das Beispiel von "Ich". Wir gehen zu allen Eimern, zu denen es gehört (1,0; 2,0; 3,0; ...; 3,4), und sehen, dass derjenige mit der geringsten Menge anderer Zeichen (3,0) ist.Tatsächlich hat es nur 1 Charakter, was bedeutet, dass es in diesem Fall ein "Ich" sein muss, und wir haben unsere einzigartige Eigenschaft gefunden.
Sie können dasselbe auch für Pixel tun, die weiß wären. Beachten Sie, dass Bucket (2.0) alle Buchstaben außer "L" enthält. Dies bedeutet, dass es als weißer Pixeltest verwendet werden kann. In ähnlicher Weise enthält (2,4) kein "A".
Buckets, die entweder alle Buchstaben oder keinen der Buchstaben enthalten, können sofort verworfen werden, da diese Pixel nicht helfen können, ein eindeutiges Merkmal zu definieren (z. B. 1,1; 4,0; 0,1; 4,4).
Es wird kniffliger, wenn Sie keinen 1-Pixel-Test für einen Buchstaben haben, zum Beispiel für "O" und "B". Lass uns durch den Test für 'O' gehen ...
Es ist in den folgenden Bereichen enthalten:
%Vor%Zusätzlich haben wir noch ein paar weiße Pixel-Tests, die helfen können: (Ich habe nur diejenigen aufgelistet, die höchstens 2 fehlen). Die fehlende Anzahl wurde berechnet als (5 - Bucket.Count).
%Vor%Nun können wir also den kürzesten schwarzen Pixel-Bucket (3,2) nehmen und sehen, dass wenn wir nach (3,2) testen, wir wissen, dass es entweder ein "A" oder ein "O" ist. Wir brauchen also einen einfachen Weg, um den Unterschied zwischen einem "A" und einem "O" zu erkennen. Wir könnten entweder nach einem schwarzen Pixel-Bucket suchen, der 'O', aber nicht 'A' (z.B. 2,4) enthält, oder nach einem weißen Pixel-Bucket, der ein 'O', aber kein 'A' (z.B. 1,1) enthält. Beide können in Kombination mit dem (3,2) Pixel verwendet werden, um den Buchstaben "O" mit nur zwei Tests eindeutig zu identifizieren.
Dies scheint ein einfacher Algorithmus zu sein, wenn es 5 Zeichen gibt, aber wie würde ich das tun, wenn es 26 Buchstaben und viel mehr Pixel gibt, die sich überlappen? Nehmen wir beispielsweise an, dass nach dem (3,2) -Pixel-Test 10 verschiedene Zeichen gefunden wurden, die das Pixel enthalten (und dies war das kleinste aus allen Buckets). Jetzt muss ich Unterschiede zu 9 anderen Zeichen finden, anstatt nur 1 anderen Zeichen. Wie erreiche ich mein Ziel, so wenig Kontrollen wie möglich zu erreichen und sicherzustellen, dass ich keine überflüssigen Tests durchführe?
Ich habe keine Antwort, aber hier sind einige Grenzen für Ihre eventuelle Lösung:
Wenn Sie eine direkte Verwendung von X Pixeln als Schlüssel wünschen, benötigen Sie mindestens ceiling(log2(number of characters)) pixels. Sie werden nicht in der Lage sein, Buchstaben mit weniger Bits zu disambiguieren. In Ihrem Fall entspricht das Auffinden der 5 Pixel dem Auffinden von 5 Pixeln, die die Buchstaben in unabhängige Partitionen aufteilen. Es ist wahrscheinlich nicht so einfach.
Sie können auch Morons (heheh) Vorschlag verwenden und baue einen Baum, der auf den Buchstabenfrequenzen der Sprache basiert, die du scannest, ähnlich wie Huffman-Codierung . Das würde mehr Platz als 5 Bits pro Buchstabe beanspruchen, wäre aber wahrscheinlich kleiner, wenn man eine Potenzgesetzverteilung des Buchstabens annimmt Verwendung. Ich würde mit diesem Ansatz gehen, da es Ihnen ermöglicht, nach einer bestimmten Partition für jeden Knoten zu suchen, anstatt nach einer Reihe von Partitionen zu suchen.
Sie könnten einen Baum erstellen.
Wählen Sie ein Pixel aus und teilen Sie die Buchstaben in zwei Buckets auf, je nachdem, welches Pixel weiß oder schwarz ist. Wählen Sie dann ein zweites Pixel, teilen Sie die Buckets je nach Pixel in zwei Buckets auf.
Sie könnten versuchen, die Tiefe des Baums zu optimieren, indem Sie Pixel auswählen, die Buckets mit ungefähr gleicher Größe ergeben.
Das Erstellen des Baums ist ein einmaliger Vorverarbeitungsschritt. Sie sollten es nicht mehrmals tun müssen.
Wenn Sie nun ein passendes Alphabet erhalten, folgen Sie dem Baum basierend auf den eingestellten / nicht gesetzten Pixeln und erhalten Sie Ihren Buchstaben.
Ich habe keinen Algorithmus, um Ihnen die Schlüsselfunktionen zu geben, aber hier sind einige Dinge, die Ihnen helfen könnten.
Erstens würde ich mir nicht zu viele Gedanken darüber machen, nach einem charakteristischen Pixel für jedes Zeichen zu suchen, denn im Durchschnitt würde die Überprüfung, ob ein gegebenes Zeichen mit einem gegebenen Streifen (5x5) des Binärbildes übereinstimmt, nicht mehr als 5-7 überprüft, dass es keine Übereinstimmung gibt. Warum? Wahrscheinlichkeit. Für 7 binäre Pixel gibt es 2 ** 7 = 128 verschiedene Möglichkeiten. Das heißt, es gibt 1/128 & lt; 1% Wahrscheinlichkeit eines Zeichens, das sogar bis zu 7 Pixel entspricht. Stellen Sie nur sicher, dass Sie die Vergleiche richtig beenden, wenn Sie eine Nichtübereinstimmung finden.
Zweitens, wenn Sie keine Hashtabelle erstellen möchten, sollten Sie einen trie zum Speichern verwenden all deine Charakterdaten. Es wird weniger Speicher benötigt und Sie prüfen alle Zeichen gleichzeitig. Es wird nicht so schnell wie eine Hash-Tabelle durchsucht werden, aber Sie müssen auch nicht in eine Zeichenfolge konvertieren. An jedem Knoten im Baum können maximal 2 Nachkommen sein. Zum Beispiel, wenn Sie zwei 2x2 Zeichen haben (nennen wir sie A und B):
%Vor%Ihr Trie hätte nur einen Nachkommen am ersten Knoten - nur nach links (der 0-Zweig). Wir fahren mit diesem nächsten Knoten fort. Es hat zwei Nachkommen, der linke (0) Zweig führt zum Rest von B und der rechte (1) Zweig führt zum Rest von A. Sie erhalten das Bild. Lassen Sie mich wissen, wenn dieser Teil nicht klar ist.
Warum betrachten Sie das Bild nicht einfach als 25-Bit-Integer? Ein 32-Bit-Int kann funktionieren. Zum Beispiel kann der Buchstabe 'I' als Integer 14815374 behandelt werden, dessen binärer Ausdruck 0111000100001000010001110 ist. Es ist bequemer, zwei Bilder mit der Operation '==' als zwei Integer zu vergleichen.
Ein Weg wäre, ein Pixel zu identifizieren, das in ungefähr der Hälfte der Buchstaben schwarz und in dem anderen Satz weiß ist. Dies kann dann verwendet werden, um die Buchstaben in zwei Gruppen zu teilen, wobei derselbe Algorithmus auf beiden Hälften rekursiv verwendet wird, bis Sie einzelne Zeichen erreicht haben.
Wenn Sie kein einzelnes Pixel finden, das die Sets in zwei teilt, müssen Sie möglicherweise zu einer Gruppe von zwei oder mehr Pixeln gehen, aber hoffentlich sollte die Verwendung einzelner Pixel gut genug sein.
Um das Pixel zu finden, beginnen Sie mit einem Array von ganzen Zahlen, die die gleiche Größe wie Ihre Buchstaben haben, initialisieren Sie alle Elemente auf 0 und inkrementieren Sie dann die Elemente, wenn das entsprechende Pixel in einem Buchstaben (etwa) schwarz ist. Die, an denen Sie interessiert sind, sind die im Bereich von (grob) 10 ≤ sum≤16 (für die oberste Ebene müssen niedrigere Ebenen andere Grenzen verwenden).
Okay, ich habe die Lösung herausgefunden.
Sie verwenden einfach eine Tiefensuche für jedes einzelne Pixel mit jeder anderen Pixelkombination, bis Sie die Menge der eindeutigen Merkmale des Buchstabens gefunden haben. Stellen Sie bei der Tiefensuche sicher, dass Sie nicht jedes Mal bei x = 0 und y = 0 beginnen, da Sie jede Kombination nur einmal verarbeiten möchten. In diesem Fall erhöhen Sie also die x- und y-Werte Iteration.
Ich habe ein Hilfsobjekt erstellt, das diese Eigenschaften enthält:
%Vor%Wenn ich für jede Iteration keine eindeutige Eigenschaft finden konnte (zB alle anderen Buchstaben haben dieses Pixel als schwarz, aber dieser Buchstabe hat es als weiß ... oder umgekehrt), füge ich alle nachfolgenden Pixel zu einer Schlange hinzu verarbeitet werden, indem eine Instanz dieses obigen Objekts mit den richtig eingestellten Eigenschaften erstellt wird.
Einige Pseudo-Code:
%Vor%Um festzustellen, ob "node.CharsWithSimilarProperites.IsAlwaysWhite ()" oder "IsAlwaysBlack ()" ist, können Sie in jeder Iteration der Warteschlange eine CompositeMap generieren:
%Vor% Bevor ich das alles mache, bearbeite ich auch das ganze Alphabet, um Pixel zu finden, die immer weiß oder immer schwarz sind, da diese niemals benutzt werden können. Ich habe sie zu List<Point> ignoredPixels hinzugefügt, und jedes Mal, wenn ich über Pixel iteriere, verwende ich immer if (ignoredPixels[x, y]) continue; .
Das funktioniert perfekt und ist wirklich schnell. Bedenken Sie jedoch, dass dieser Teil meiner Lösung nicht unbedingt schnell sein muss, da es sich um eine einmalige Optimierung handelt, die mir später hilft. In meinen Testfällen von maximal 8 Zeichen pro "Alphabet" -Satz erzeugt es normalerweise ein oder zwei Merkmale für jedes Zeichen. Ich muss es noch auf einem vollständigen Satz von 26 Zeichen ausführen.
Ich gehe einen ähnlichen Weg, indem ich versuche, einen Algorithmus zu erfinden, der mir eine minimale Anzahl von Tests gibt, die ich verwenden kann, um ein Bild mit einem zu vergleichen, das ich vorher gesehen habe. Meine Anwendung ist OCR, aber in einem begrenzten Bereich der Erkennung eines Bildes aus einem festen Satz von Bildern so schnell wie möglich.
Meine Grundannahme (die ich denke, ist die gleiche wie Ihre, oder war die gleiche) ist, dass, wenn wir ein einzigartiges Pixel identifizieren können (wo ein Pixel als ein Punkt innerhalb eines Bildes plus eine Farbe definiert ist), dann haben wir gefunden der perfekte (schnellste) Test für dieses Bild. In Ihrem Fall möchten Sie Buchstaben finden.
Wenn wir ein solches Pixel nicht finden können, suchen wir (widerwillig) nach zwei Pixeln, die in Kombination einzigartig sind. Oder drei. Und so weiter, bis wir einen minimalen Test für jedes Bild haben.
Ich sollte beachten, dass ich ein starkes Gefühl habe, dass ich in meiner speziellen Domäne solche einzigartigen Pixel finden kann. Es ist vielleicht nicht dasselbe für Ihre Anwendung, wo Sie eine Menge "Überlappung" zu haben scheinen.
Nach Berücksichtigung von Kommentaren in diese andere Frage (wo ich gerade anfange, ein Gefühl für das Problem zu bekommen) und Kommentare hier, ich denke, ich hätte vielleicht einen brauchbaren Algorithmus gefunden.
Hier ist, was ich bisher habe. Die Methode, die ich unten beschreibe, ist in der Zusammenfassung geschrieben, aber in meiner Anwendung ist jeder "Test" ein Pixel, das durch einen Punkt plus eine Farbe identifiziert wird, und ein "Ergebnis" repräsentiert die Identität eines Bildes. Die Identifizierung dieser Bilder ist mein Endziel.
Betrachten Sie die folgenden Tests mit den Nummern T1 bis T4.
Diese Liste von Tests kann wie folgt interpretiert werden;
Für jedes einzelne Ergebnis A, B, C, D möchten wir eine Kombination von Tests finden (idealerweise nur einen Test), die es uns ermöglichen wird, ein eindeutiges Ergebnis zu testen.
Wenn wir Intuition anwenden und ein wenig auf den Bildschirm schielen, können wir uns auf die folgende Anordnung von Tests einlassen.
Für A können wir eine Kombination von T4 (entweder A oder D) und T1 (A, aber nicht D)
testenB ist einfach, da es einen Test T2 gibt, der Ergebnis B ergibt und sonst nichts.
C ist ein bisschen schwieriger, aber schließlich können wir sehen, dass eine Kombination von T3 (A oder C oder D) und NICHT T4 (nicht A und nicht D) das gewünschte Ergebnis liefert.
Und ähnlich kann D mit einer Kombination von T4 und (nicht T1) gefunden werden.
Zusammenfassend
%Vor% (wobei <- gelesen werden sollte, wie 'gefunden werden kann, wenn die folgenden Tests wahr' ergeben)
Intuition und Schielen ist in Ordnung, aber wir werden diese Techniken wahrscheinlich erst ab C # 5.0 in die Sprache einbauen, daher hier ein Versuch, die Methode für die Implementierung in weniger Sprachen zu formalisieren.
Um ein Ergebnis zu finden R ,
Tr , der das gewünschte Ergebnis R und die wenigsten unerwünschten Ergebnisse liefert (im Idealfall keine anderen) R ergibt und nichts anderes, sind wir fertig. Wir können für R übereinstimmen, wobei Tr wahr ist. X im Test Tr ;
Tn , der R , aber nicht X ergibt. Wenn wir einen solchen Test finden, können wir für R wo (T && Tn)
Tx , der X enthält, aber nicht R . (Ein solcher Test würde X als Ergebnis von test Tr eliminieren). Wir können dann auf R testen, wo (T && ¬Tx)
Nun werde ich versuchen, diese Regeln für jedes der gewünschten Ergebnisse zu befolgen, A, B, C, D.
Hier sind die Tests wieder als Referenz;
Gemäß Regel (1) beginnen wir mit T4, da es der einfachste Test ist, der Ergebnis A ergibt. Aber es gibt auch das Ergebnis "D", was ein unerwünschtes Ergebnis ist. Gemäß Regel (3) können wir Test T1 verwenden, da er "A" enthält, aber nicht "D".
Daher können wir mit
auf A testen %Vor%Um 'B' zu finden, finden wir schnell den Test T2, der der kürzeste Test für 'B' ist und da er nur das Ergebnis 'B' ergibt, sind wir fertig.
%Vor%Um nach 'C' zu suchen, beginnen wir mit T1 und T3.Da die Ergebnisse dieser Tests gleich kurz sind, wählen wir willkürlich T1 als Ausgangspunkt.
Nun müssen wir gemäß (3a) einen Test finden, der "C", aber nicht "A" enthält. Da kein Test diese Bedingung erfüllt, können wir T1 nicht als ersten Test verwenden. T3 hat das gleiche Problem.
Da wir keinen Test finden können, der (3a) erfüllt, suchen wir nun nach einem Test, der die Bedingung (3b) erfüllt. Wir suchen nach einem Test, der "A", aber nicht "C" ergibt. Wir können sehen, dass Test T4 diese Bedingung erfüllt, daher können wir mit
auf C testen %Vor%Um D zu finden, beginnen wir mit T4. T4 enthält das unerwünschte Ergebnis A. Es gibt keine anderen Tests, die das Ergebnis D, aber nicht A ergeben, also suchen wir nach einem Test, der A aber nicht D ergibt. Test T1 erfüllt diese Bedingung, daher können wir mit
auf D testen %Vor%Diese Ergebnisse sind gut, aber ich glaube nicht, dass ich diesen Algorithmus genug getestet habe, um 100% Vertrauen zu haben. Ich werde darüber noch ein wenig nachdenken und vielleicht ein paar Tests schreiben, um zu sehen, wie es geht. Leider ist der Algorithmus nur so komplex, dass die Implementierung einige Minuten in Anspruch nimmt. Es könnte Tage dauern, bevor ich etwas weiter schließe.
Aktualisieren
Ich fand, dass es optimal ist, gleichzeitig nach Tests zu suchen, die (a) OR (b) erfüllen, anstatt nach (a) und dann (b) zu suchen. Wenn wir zuerst nach (a) suchen, können wir eine lange Liste von Tests erhalten, wenn wir eine kürzere Liste haben könnten, indem wir einige (b) Tests erlauben.
Tags und Links algorithm optimization ocr