Existe-t-il un algorithme efficace pour la segmentation de textes manuscrits ?

Question

Je veux diviser automatiquement une image d'un texte manuscrit ancien par lignes (et par mots à l'avenir).

La première partie évidente est le prétraitement de l'image...

J'utilise simplement une numérisation simple (basée sur la luminosité du pixel). Après cela, je stocke les données dans un tableau bidimensionnel.

La prochaine étape évidente est l'analyse du tableau binaire.

1. Mon premier algorithme était assez simple : s'il y a plus de pixels noirs dans une rangée du tableau que la moyenne quadratique des pixels noirs de l'échantillon. Maximum et Minimum alors cette ligne fait partie de la ligne.

   Après avoir formé la liste des lignes, j'ai coupé les lignes avec hauteur qui est inférieur à la moyenne. Finalement, il s'agit d'une sorte de régression linéaire, qui tente de minimiser la différence entre les lignes vides et les lignes de texte. (J'ai supposé que ce fait)

2. Ma deuxième tentative - J'ai essayé d'utiliser GA avec plusieurs fonctions de fitness. Le chromosome contenait 3 valeurs - xo, x1, x2. xo [-1;0] x1 [0;0.5] x2 [0;0.5]

Fonction, qui détermine l'identité la ligne à la ligne est (xo + 1 x1 + 2 x2) > 0 où 1 est la somme mise à l'échelle des pixels noirs de la ligne, 2 est la valeur médiane des intervalles entre les pixels noirs extrêmes de la ligne. (a1,a2 [0,1]) Une autre fonction, que j'ai essayée est (x1 < 1 OU x2 > 2) et (1/xo + [a1 x1] / [a2 x2] ) > 0 La dernière fonction est la plus efficace. La fonction de fitness est (1 / (HeigthRange + SpacesRange)

Où l'étendue est la différence entre le maximum et le minimum. Elle représente l'homogénéité du texte. L'optimum global de cette fonction - la manière la plus douce de diviser l'image en lignes.

J'utilise C# avec mon AG auto-codé (classique, avec croisement à 2 points, chromosomes à code gris, population maximale de 40, taux de mutation de 0,05).

Maintenant, je suis à court d'idées pour diviser cette image en lignes avec une précision de ~100%.

Quel est l'algorithme efficace pour faire cela ?

---

UPDATE : BMP original (1.3 MB)

---

UPDATE2 : Amélioration des résultats sur ce texte à 100%.

Comment je l'ai fait :

• correction d'un bug mineur dans le comptage des plages
• modification de la fonction d'aptitude en 1/(distancesRange+1)*(hauteursRange+1))
• fonction de classification minimisée à (1/xo + x2/gamme) > 0 (les points dans la rangée n'affectent pas la classification) (c.-à-d. optimisation des données d'entrée et optimisation plus explicite de la fonction de fitness)

Problème :

GA n'a étonnamment pas reconnu cette ligne. J'ai regardé les données de débogage de la fonction "find rages" et j'ai constaté qu'il y avait trop de bruit à l'endroit "non reconnu". Le code de la fonction est ci-dessous :

public double[] Ranges()
{
    var ranges = new double[_original.Height];

    for (int y = 0; y < _original.Height; y++ )
    {
        ranges[y] = 0;
        var dx = new List<int>();
        int last = 0;
        int x = 0; 

        while (last == 0 && x<_original.Width)
        {
            if (_bit[x, y])
                last = x;
            x++;
        }

        if (last == 0)
        {
            ranges[y] = 0;
            continue;
        }

        for (x = last; x<_original.Width; x++)
        {
            if (!_bit[x, y]) continue; 

            if (last != x - 1)
            {
                dx.Add((x-last)+1);
            }
            last = x;
        }
        if (dx.Count > 2)
        {
            dx.Sort();
            ranges[y] = dx[dx.Count / 2];
            //ranges[y] = dx.Average();
        }
        else
            ranges[y] = 0;
    }

    var maximum = ranges.Max();
    for (int i = 0; i < ranges.Length; i++)
    {
        if (Math.Abs(ranges[i] - 0) < 0.9)
            ranges[i] = maximum;
    }
    return ranges;
}

J'utilise quelques astuces dans ce code. La raison principale - je veux minimiser l'écart entre les pixels noirs les plus proches, mais s'il n'y a pas de pixels, la valeur devient '0', et il devient impossible de résoudre ce problème en trouvant des optimas. La deuxième raison - ce code change trop fréquemment. Je vais essayer de changer complètement ce code, mais je n'ai aucune idée de comment le faire.

Q :

1. S'il existe une fonction de fitness plus efficace ?
2. Comment trouver une fonction de détermination plus polyvalente ?

Answer 1

Bien que je ne sache pas comment traduire l'algorithme suivant en GA (et que je ne sache pas non plus pourquoi il faut utiliser GA pour ce problème), et que je puisse être à côté de la plaque en le proposant, voici ce que je propose.

La technique simple que je propose consiste à compter le nombre de pixels noirs par ligne. (En fait, il s'agit de la densité de pixels noirs par ligne.) Cela nécessite très peu d'opérations, et avec quelques calculs supplémentaires, il n'est pas difficile de trouver des pics dans l'histogramme de la somme des pixels.

Un histogramme brut ressemblera à ceci, où le profil de gauche indique le nombre de pixels sombres dans une rangée. Pour des raisons de visibilité, le nombre réel est normalisé pour s'étendre à x = 200.

Après un traitement supplémentaire simple (décrit ci-dessous), nous pouvons générer un histogramme comme celui-ci, qui peut être coupé à une certaine valeur seuil. Ce qui reste, ce sont les pics indiquant le centre des lignes de texte.

À partir de là, il est facile de trouver les lignes : il suffit d'écrêter (seuil) l'histogramme à une valeur telle que la moitié ou les deux tiers du maximum, et éventuellement de vérifier que la largeur du pic à votre seuil d'écrêtage est une valeur minimale w.

Une implémentation de l'algorithme complet (mais toujours simple !) pour trouver le plus bel histogramme est la suivante :

1. Binarisez l'image à l'aide d'un seuil de "moyenne mobile" ou d'une technique de seuillage local similaire au cas où un seuil d'Otsu standard opérant sur les pixels proches des bords ne serait pas satisfaisant. Ou, si vous avez une belle image en noir et blanc, utilisez simplement 128 comme seuil de binarisation.
2. Créez un tableau pour stocker votre histogramme. La longueur de ce tableau sera la hauteur de l'image.
3. Pour chaque pixel (x,y) de l'image binarisée, trouvez le nombre de pixels sombres au-dessus et au-dessous de (x,y) à un certain rayon R. Autrement dit, comptez le nombre de pixels sombres de (x, y - R) à x (y + R), inclus.
4. Si le nombre de pixels sombres dans un rayon vertical R est égal ou supérieur à R - c'est-à-dire qu'au moins la moitié des pixels sont sombres - alors le pixel (x,y) a suffisamment de voisins sombres verticaux. Augmentez votre nombre de cases pour la ligne y.
5. Au fur et à mesure que vous avancez le long de chaque ligne, suivez les valeurs x les plus à gauche et les plus à droite pour les pixels ayant suffisamment de voisins. Tant que la largeur (droite - gauche + 1) dépasse une valeur minimale, divisez le nombre total de pixels sombres par cette largeur. Cela permet de normaliser le compte pour s'assurer que les lignes courtes, comme la toute dernière ligne de texte, sont incluses.
6. (Facultatif) Lissez l'histogramme résultant. J'ai juste utilisé la moyenne sur 3 rangées.

Le "comptage vertical" (étape 3) élimine les traits horizontaux qui se trouvent au-dessus ou au-dessous de la ligne centrale du texte. Un algorithme plus sophistiqué se contenterait de vérifier directement au-dessus et au-dessous de (x,y), mais aussi en haut à gauche, en haut à droite, en bas à gauche et en bas à droite.

Avec mon implémentation plutôt grossière en C#, j'ai pu traiter l'image en moins de 75 millisecondes. En C++, et avec une optimisation de base, je ne doute pas que le temps pourrait être considérablement réduit.

Cette méthode d'histogramme suppose que le texte est horizontal. L'algorithme étant raisonnablement rapide, vous aurez peut-être le temps de calculer des histogrammes du nombre de pixels par incréments de 5 degrés par rapport à l'horizontale. L'orientation du balayage présentant les plus grandes différences entre les pics et les vallées indique la rotation.

Je ne suis pas familier avec la terminologie de GA, mais si ce que j'ai suggéré a une quelconque valeur, je suis sûr que vous pouvez le traduire en termes de GA. Dans tous les cas, ce problème m'intéressait de toute façon, alors autant partager.

EDIT : peut-être que pour l'utilisation de GA, il est préférable de penser en termes de "distance depuis le pixel sombre précédent en X" (ou selon l'angle thêta) et "distance depuis le pixel sombre précédent en Y" (ou selon l'angle [thêta - pi/2]). Vous pouvez également vérifier la distance entre le pixel blanc et le pixel foncé dans toutes les directions radiales (pour trouver les boucles).

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;

Answer 2

Après avoir bricolé pendant un certain temps, j'ai découvert que je devais simplement compter le nombre de croisements pour chaque ligne, c'est-à-dire qu'un passage du blanc au noir compterait pour un, et qu'un passage du noir au blanc serait à nouveau incrémenté d'un. En mettant en évidence chaque ligne avec un nombre > 66, j'ai obtenu une précision proche de 100%, sauf pour la ligne la plus basse.

Bien sûr, ce système ne serait pas robuste pour des documents scannés légèrement tournés. Et il y a cet inconvénient de devoir déterminer le seuil correct.

Answer 3

Je pense qu'avec l'image montrée, il serait très difficile de le faire parfaitement à 100%. Ma réponse est de vous donner des idées alternatives.

Idée 1 : Faites votre propre version de ReCaptcha (pour la mettre sur votre propre site pron) - et faites-en un jeu amusant "Comme découper un mot (les bords doivent être des espaces blancs - avec une certaine tolérance pour les caractères qui se chevauchent sur les lignes supérieures et inférieures)."

Idée 2 : C'est un jeu auquel nous jouions quand nous étions enfants, le fil d'un cintre était plié en vagues et connecté à un buzzer et vous deviez faire naviguer une baguette avec un anneau au bout et le fil à travers, d'un côté à l'autre sans faire sonner le buzzer. Vous pourriez peut-être adapter cette idée et créer un jeu mobile où les gens tracent les lignes sans toucher le texte noir (avec une tolérance pour les caractères qui se chevauchent)... lorsqu'ils parviennent à faire une ligne, ils obtiennent des points et accèdent à de nouveaux niveaux où vous leur donnez des images plus difficiles...

Idée 3 : Recherchez comment google/recaptcha l'a contourné

Idée 4 : Obtenez le SDK de Photoshop et maîtrisez ses fonctionnalités. Outil d'extraction des bords.

Idée 5 : Étirez l'image en tas sur l'axe Y, ce qui devrait vous aider, appliquez l'algorithme, puis réduisez les mesures de localisation et appliquez-les sur l'image de taille normale.