c# - tipos - ¿Existe un algoritmo eficiente para la segmentación del texto escrito a mano?

segmentacion de mercado tipos

Question

Quiero dividir automáticamente una imagen de texto manuscrito antiguo por líneas (y por palabras en el futuro).

La primera parte obvia es preprocesar la imagen ...

Solo estoy usando una digitalización simple (basada en el brillo del píxel). Después de eso, almacé los datos en una matriz bidimensional.

La siguiente parte obvia es analizar la matriz binaria.

1. Mi primer algoritmo fue bastante simple: si hay más píxeles negros en una fila de la matriz que la raíz media cuadrada del valor Máximo y Mínimo , entonces esta fila es parte de la línea.

   Después de formar la lista de líneas, corté las líneas con una altura inferior a la media. Finalmente resultó en algún tipo de regresión lineal, tratando de minimizar la diferencia entre las filas en blanco y las filas de texto. (Yo asumí ese hecho)

2. Mi segundo intento: intenté usar GA con varias funciones de ejercicio. El cromosoma contenía 3 valores - xo, x1, x2. xo [-1; 0] x1 [0; 0.5] x2 [0; 0.5]

Función, que determina la identidad de la fila a la línea es (xo + α1 x1 + α2 x2)> 0 , donde α1 es la suma escalada de píxeles negros en la fila, α2 es el valor mediano de rangos entre los píxeles negros extremos en la fila. (a1, a2 [0,1]) Otra función que probé es (x1 <α1 OR x2> α2) y (1 / xo + [a1 x1] / [a2 x2])> 0 La última función es la más eficiente. La función de aptitud es (1 / (HeigthRange + SpacesRange)

Donde el rango es la diferencia entre el máximo y el mínimo. Representa la homogeneidad del texto. El óptimo global de esta función: la forma más sencilla de dividir la imagen en líneas.

Estoy usando C # con mi GA autocodificado (clásico, con cruce de 2 puntos, cromosomas de código gris, la población máxima es 40, la tasa de mutación es 0.05)

Ahora me quedaron sin ideas de cómo dividir esta imagen en líneas con ~ 100% de precisión.

¿Cuál es el algoritmo eficiente para hacer esto?

ACTUALIZACIÓN: Imagen original BMP original (1.3 MB)

ACTUALIZACIÓN2: mejores resultados en este texto al 100%

Cómo lo hice:

• error menor fijo en el conteo de rango
• función de acondicionamiento físico modificada a 1 / (distanciaRango + 1) * (alturasRango + 1))
• función de clasificación minimizada a (1 / xo + x2 / rango)> 0 (los puntos en la fila ahora no afectan la clasificación) (es decir, los datos de entrada optimizados y las optimizaciones de las funciones de aptitud física son más explícitas)

Problema:

GA sorprendentemente no pudo reconocer esta línea. Miré los datos de depuración de la función ''find rages'' y encontré que hay demasiado ruido en el lugar ''no reconocido''. El código de función está a continuación:

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;
}

Estoy usando algunos hacks en este código. La razón principal es que quiero minimizar el rango entre los píxeles negros más cercanos, pero si no hay píxeles, el valor se convierte en ''0'', y se vuelve imposible resolver este problema al encontrar optimas. La segunda razón: este código está cambiando con demasiada frecuencia. Trataré de cambiar completamente este código, pero no tengo idea de cómo hacerlo.

P:

1. Si hay una función de aptitud más eficiente?
2. ¿Cómo encontrar una función de determinación más versátil?

Answer 1

En mi humilde opinión con la imagen que se muestra que sería tan difícil de hacer 100% perfectamente. Mi respuesta es darte una idea alternativa.

Idea 1: Cree su propia versión de ReCaptcha (para poner en su propio sitio pron) y conviértalo en un juego divertido .. "Como cortar una palabra (los bordes deben ser espacios en blanco) con cierta tolerancia para superponer caracteres en la parte superior y debajo de las líneas). "

Idea 2: Este era un juego que jugamos de niños, el cable de un perchero estaba doblado en ondas y conectado a un timbre y se tenía que navegar una varita con un anillo al final con el cable a través de él, a través de un lado al otro sin hacer sonar el timbre. Tal vez podrías adaptar esta idea y crear un juego para dispositivos móviles donde las personas tracen las líneas sin tocar el texto en negro (con tolerancia para caracteres superpuestos) ... cuando pueden hacer una línea obtienen puntos y llegan a nuevos niveles donde les das más fuerza imágenes ...

Idea 3: Investigue cómo Google / recaptcha lo solucionó

Idea 4: Obtenga el SDK para photoshop y domine la funcionalidad de la herramienta Extraer bordes

Idea 5: Estire los montones de imágenes en el eje Y que deberían ayudar, aplique el algoritmo, luego reduzca las mediciones de ubicación y aplíquelas en la imagen de tamaño normal.

Answer 2

Aunque no estoy seguro de cómo traducir el siguiente algoritmo a GA (y no estoy seguro de por qué necesita usar GA para este problema), y podría estar fuera de lugar al proponerlo, aquí va.

La técnica simple que propondría es contar el número de píxeles negros por fila. (En realidad es la densidad de píxeles oscura por fila). Esto requiere muy pocas operaciones, y con algunos cálculos adicionales no es difícil encontrar picos en el histograma de suma de píxeles.

Un histograma en bruto se verá algo así, donde el perfil a lo largo del lado izquierdo muestra la cantidad de píxeles oscuros en una fila. Para la visibilidad, el recuento real se normaliza para estirar a x = 200.

Después de añadir un procesamiento adicional y simple (que se describe a continuación), podemos generar un histograma como este que se puede recortar en un valor de umbral. Lo que queda son picos que indican el centro de las líneas de texto.

A partir de ahí, es sencillo encontrar las líneas: simplemente recorte (umbral) el histograma con un valor como 1/2 o 2/3 el máximo y, opcionalmente, verifique que el ancho del pico en su límite de recorte sea un valor mínimo w.

Una implementación del algoritmo completo (¡pero aún así sencillo!) Para encontrar el histograma más agradable es la siguiente:

1. Binarice la imagen utilizando un umbral de "promedio variable" o una técnica de umbralización local similar en caso de que un umbral de Otsu estándar que opera en píxeles cerca de los bordes no sea satisfactorio. O bien, si tiene una bonita imagen negra sobre blanco, simplemente use 128 como su umbral de binarización.
2. Crea una matriz para almacenar tu histograma. La longitud de esta matriz será la altura de la imagen.
3. Para cada píxel (x, y) en la imagen binarizada, encuentre el número de píxeles oscuros arriba y abajo (x, y) en algún radio R. Es decir, cuente el número de píxeles oscuros de (x, y - R) a x (y + R), inclusive.
4. Si el número de píxeles oscuros dentro de un radio vertical R es igual o superior a R, es decir, al menos la mitad de los píxeles son oscuros, entonces el píxel (x, y) tiene suficientes vecinos oscuros verticales. Incremente su conteo de contenedores para la fila y.
5. A medida que marchas a lo largo de cada fila, rastrea los valores x más a la izquierda y más a la derecha para los píxeles con suficientes vecinos. Siempre que el ancho (derecha - izquierda + 1) exceda algún valor mínimo, divida el recuento total de píxeles oscuros por este ancho. Esto normaliza el recuento para garantizar que se incluyan las líneas cortas como la última línea de texto.
6. (Opcional) Alise el histograma resultante. Acabo de usar la media en 3 filas.

El "recuento vertical" (paso 3) elimina los trazos horizontales que se ubican por encima o por debajo de la línea central del texto. Un algoritmo más sofisticado simplemente verificaría directamente arriba y abajo (x, y), pero también a la parte superior izquierda, arriba a la derecha, abajo a la izquierda y abajo a la derecha.

Con mi implementación bastante cruda en C #, pude procesar la imagen en menos de 75 milisegundos. En C ++, y con algunas optimizaciones básicas, tengo pocas dudas de que el tiempo podría reducirse considerablemente.

Este método de histograma supone que el texto es horizontal. Dado que el algoritmo es razonablemente rápido, puede tener tiempo suficiente para calcular histogramas de conteo de píxeles a incrementos de cada 5 grados con respecto a la horizontal. La orientación del escaneo con las mayores diferencias de pico / valle indicaría la rotación.

No estoy familiarizado con la terminología de GA, pero si lo que he sugerido tiene algún valor, estoy seguro de que puede traducirlo a términos de GA. En cualquier caso, estaba interesado en este problema de todos modos, así que también podría compartirlo.

EDITAR: quizás para usar GA, es mejor pensar en términos de "distancia desde el pixel oscuro anterior en X" (oa lo largo del ángulo theta) y "distancia desde el pixel oscuro anterior en Y" (oa lo largo del ángulo [theta - pi / 2] ) También puede verificar la distancia desde el píxel blanco al píxel oscuro en todas las direcciones radiales (para encontrar los bucles).

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 3

Después de juguetear con esto por un tiempo, descubrí que simplemente necesito contar el número de cruces para cada línea, es decir, un cambio de blanco a negro contaría como uno, y un cambio de negro a blanco aumentaría en uno nuevamente. Al resaltar cada línea con un recuento> 66 obtuve una precisión cercana al 100%, excepto en la línea inferior.

Por supuesto, no sería robusto para documentos escaneados ligeramente girados. Y existe la desventaja de necesitar determinar el umbral correcto.