Gibt es einen effizienten Algorithmus zur Segmentierung von handschriftlichem Text?

Obwohl ich nicht sicher bin, wie ich den folgenden Algorithmus in GA übersetzen soll (und ich bin mir nicht sicher, warum Sie GA für dieses Problem verwenden müssen), und ich könnte mit dem Vorschlag falsch liegen, hier geht es.

Die einfache Technik, die ich vorschlagen würde, besteht darin, die Anzahl der schwarzen Pixel pro Zeile zu zählen. (Eigentlich ist es die Dunkelpixeldichte pro Zeile.) Dies erfordert sehr wenige Operationen, und mit ein paar zusätzlichen Berechnungen ist es nicht schwierig, Spitzen im Pixelsummen-Histogramm zu finden.

Ein rohes Histogramm sieht etwa so aus, wobei das Profil auf der linken Seite die Anzahl dunkler Pixel in einer Reihe zeigt. Für die Sichtbarkeit wird die tatsächliche Anzahl auf x =200 normalisiert.

Nachdem eine zusätzliche, einfache Verarbeitung hinzugefügt wurde (unten beschrieben), können wir ein Histogramm wie dieses erzeugen, das bei einem bestimmten Schwellenwert abgeschnitten werden kann. Was bleibt, sind Spitzen, die die Mitte der Textzeilen anzeigen.

Von dort aus ist es eine einfache Sache, die Linien zu finden:Beschneiden (Schwellenwert) Sie einfach das Histogramm auf einen Wert wie 1/2 oder 2/3 des Maximums und prüfen Sie optional, ob die Breite der Spitze an Ihrem Beschneidungsschwellenwert ein Mindestwert ist w.

Eine Implementierung des vollständigen (aber immer noch einfachen!) Algorithmus, um das schönere Histogramm zu finden, ist wie folgt:

1. Binarisieren Sie das Bild mit einem "gleitenden Durchschnitt"-Schwellenwert oder einer ähnlichen lokalen Schwellenwerttechnik, falls ein Standard-Otsu-Schwellenwert, der auf Pixel in der Nähe von Kanten angewendet wird, nicht zufriedenstellend ist. Oder, wenn Sie ein schönes Schwarz-Weiß-Bild haben, verwenden Sie einfach 128 als Schwellenwert für die Binarisierung.
2. Erstellen Sie ein Array, um Ihr Histogramm zu speichern. Die Länge dieses Arrays entspricht der Höhe des Bildes.
3. Finden Sie für jedes Pixel (x,y) im binarisierten Bild die Anzahl der dunklen Pixel über und unter (x,y) bei einem bestimmten Radius R. Das heißt, zählen Sie die Anzahl der dunklen Pixel von (x, y - R) bis x (y + R), einschließlich.
4. Wenn die Anzahl dunkler Pixel innerhalb eines vertikalen Radius R gleich oder größer als R ist – das heißt, mindestens die Hälfte der Pixel ist dunkel – dann hat Pixel (x, y) genügend vertikale dunkle Nachbarn. Erhöhen Sie Ihre Bin-Zählung für Zeile y.
5. Verfolgen Sie beim Durchlaufen jeder Reihe die X-Werte ganz links und ganz rechts für Pixel mit genügend Nachbarn. Solange die Breite (rechts - links + 1) einen Mindestwert überschreitet, teilen Sie die Gesamtzahl der dunklen Pixel durch diese Breite. Dadurch wird die Zählung normalisiert, um sicherzustellen, dass die kurzen Zeilen wie die allerletzte Textzeile enthalten sind.
6. (Optional) Glätten Sie das resultierende Histogramm. Ich habe nur den Mittelwert über 3 Zeilen verwendet.

Die "vertikale Zählung" (Schritt 3) eliminiert horizontale Striche, die sich zufällig über oder unter der Mittellinie des Textes befinden. Ein ausgefeilterer Algorithmus würde einfach direkt über und unter (x,y) prüfen, aber auch oben links, oben rechts, unten links und unten rechts.

Mit meiner eher groben Implementierung in C# konnte ich das Bild in weniger als 75 Millisekunden verarbeiten. In C++ und mit einigen grundlegenden Optimierungen habe ich kaum Zweifel, dass die Zeit erheblich verkürzt werden könnte.

Diese Histogrammmethode geht davon aus, dass der Text horizontal ist. Da der Algorithmus relativ schnell ist, haben Sie möglicherweise genug Zeit, um Pixelzählhistogramme in Schritten von jeweils 5 Grad von der Horizontalen zu berechnen. Die Scan-Orientierung mit den größten Gipfel-/Tal-Unterschieden würde die Drehung anzeigen.

Ich bin mit der GA-Terminologie nicht vertraut, aber wenn das, was ich vorgeschlagen habe, von gewissem Wert ist, bin ich sicher, dass Sie es in GA-Begriffe übersetzen können. Auf jeden Fall hat mich dieses Problem sowieso interessiert, also kann ich es genauso gut teilen.

BEARBEITEN:Vielleicht ist es für die Verwendung von GA besser, in Bezug auf "Abstand seit dem vorherigen dunklen Pixel in X" (oder entlang des Winkels Theta) und "Abstand seit dem vorherigen dunklen Pixel in Y" (oder entlang des Winkels [theta - pi / 2]) zu denken ). Sie können auch den Abstand von weißen Pixeln zu dunklen Pixeln in allen radialen Richtungen überprüfen (um Schleifen zu finden).

byte[,] arr = get2DArrayFromBitamp();   //source array from originalBitmap
int w = arr.GetLength(0);               //width of 2D array
int h = arr.GetLength(1);               //height of 2D array

//we can use a second 2D array of dark pixels that belong to vertical strokes
byte[,] bytes = new byte[w, h];         //dark pixels in vertical strokes


//initial morph
int r = 4;        //radius to check for dark pixels
int count = 0;    //number of dark pixels within radius

//fill the bytes[,] array only with pixels belonging to vertical strokes
for (int x = 0; x < w; x++)
{
    //for the first r rows, just set pixels to white
    for (int y = 0; y < r; y++)
    {
        bytes[x, y] = 255;
    }

    //assume pixels of value < 128 are dark pixels in text
    for (int y = r; y < h - r - 1; y++)
    {
        count = 0;

        //count the dark pixels above and below (x,y)
        //total range of check is 2r, from -r to +r
        for (int j = -r; j <= r; j++)
        {
            if (arr[x, y + j] < 128) count++;
        }

        //if half the pixels are dark, [x,y] is part of vertical stroke
        bytes[x, y] = count >= r ? (byte)0 : (byte)255;
    }

    //for the last r rows, just set pixels to white
    for (int y = h - r - 1; y < h; y++)
    {
        bytes[x, y] = 255;
    }
}

//count the number of valid dark pixels in each row
float max = 0;

float[] bins = new float[h];    //normalized "dark pixel strength" for all h rows
int left, right, width;         //leftmost and rightmost dark pixels in row
bool dark = false;              //tracking variable

for (int y = 0; y < h; y++)
{
    //initialize values at beginning of loop iteration
    left = 0;
    right = 0;
    width = 100;

    for (int x = 0; x < w; x++)
    {
        //use value of 128 as threshold between light and dark
        dark = bytes[x, y] < 128;  

        //increment bin if pixel is dark
        bins[y] += dark ? 1 : 0;    

        //update leftmost and rightmost dark pixels
        if (dark)
        {
            if (left == 0) left = x;    
            if (x > right) right = x;   
        }
    }

    width = right - left + 1;

    //for bins with few pixels, treat them as empty
    if (bins[y] < 10) bins[y] = 0;      

    //normalize value according to width
    //divide bin count by width (leftmost to rightmost)
    bins[y] /= width;

    //calculate the maximum bin value so that bins can be scaled when drawn
    if (bins[y] > max) max = bins[y];   
}

//calculated the smoothed value of each bin i by averaging bin i-1, i, and i+1
float[] smooth = new float[bins.Length];

smooth[0] = bins[0];
smooth[smooth.Length - 1] = bins[bins.Length - 1];

for (int i = 1; i < bins.Length - 1; i++)
{
    smooth[i] = (bins[i - 1] + bins[i] + bins[i + 1])/3;
}

//create a new bitmap based on the original bitmap, then draw bins on top
Bitmap bmp = new Bitmap(originalBitmap);

using (Graphics gr = Graphics.FromImage(bmp))
{
    for (int y = 0; y < bins.Length; y++)
    {
        //scale each bin so that it is drawn 200 pixels wide from the left edge
        float value = 200 * (float)smooth[y] / max;
        gr.DrawLine(Pens.Red, new PointF(0, y), new PointF(value, y)); 
    }
}

pictureBox1.Image = bmp;

Nachdem ich eine Weile daran herumgefummelt hatte, stellte ich fest, dass ich einfach die Anzahl der Kreuzungen für jede Linie zählen muss, das heißt, ein Wechsel von Weiß nach Schwarz würde als eins zählen und ein Wechsel von Schwarz nach Weiß würde wieder um eins erhöht. Indem ich jede Zeile mit einer Anzahl> 66 hervorhob, erreichte ich eine Genauigkeit von fast 100 %, mit Ausnahme der untersten Zeile.

Natürlich wären leicht gedreht gescannte Dokumente nicht robust. Und es gibt diesen Nachteil, dass man den korrekten Schwellenwert bestimmen muss.

Idee 1: Erstellen Sie Ihre eigene Version von ReCaptcha (um Ihre eigene Pron-Site zu erstellen) - und machen Sie daraus ein unterhaltsames Spiel )."

Idee 2: Das war ein Spiel, das wir als Kinder gespielt haben, der Draht eines Kleiderbügels war ganz in Wellen gebogen und mit einem Summer verbunden, und man musste einen Zauberstab mit einem Ring am Ende mit dem Draht hindurch navigieren, von einer Seite zur anderen ohne dass der Summer losgeht. Vielleicht könnten Sie diese Idee anpassen und ein Handyspiel machen, bei dem die Leute die Linien nachzeichnen, ohne schwarzen Text zu berühren (mit Toleranz für überlappende Zeichen). Bilder..

Idee 3: Untersuchen Sie, wie Google/recaptcha es umgangen hat

Idee 4: Holen Sie sich das SDK für Photoshop und meistern Sie die Funktionalität des Tools „Kanten extrahieren“

Idee 5: Strecken Sie die Bildhaufen auf der Y-Achse, was helfen sollte, wenden Sie den Algorithmus an, reduzieren Sie dann die Standortmessungen und wenden Sie sie auf das normal große Bild an.