algorithm - tecnicas - Entendiendo los códigos de cadena de Freeman para OCR

software reconocimiento de caracteres (4)

Como su pregunta no es lo suficientemente específica (ya sea que desee un algoritmo completo basado en el código de la cadena o simplemente una clasificación probabilística), le diré lo que sé sobre el problema.

Usando el código de la cadena, puede contar algunas propiedades del símbolo, por ejemplo, el número de rotaciones de la forma 344445, 244445, 2555556, 344446 (número arbitrario de 4s), es decir, los "picos" en la letra. Digamos que hay 3 secciones en el código de la cadena que se ve así. Por lo tanto, esto es casi seguro que "W"! Pero este es un buen caso. Puede contar números de diferentes tipos de rotaciones y compararlos con los valores guardados previamente para cada letra (lo que hace a mano). Este es un buen clasificador, pero solo no es suficiente, por supuesto. Le será imposible diferenciar "D" y "O", "V" y "U". Y mucho depende de tu imaginación.

Debe comenzar por crear un caso de prueba de imágenes de algunas letras con una referencia y verificar su algoritmo entre los cambios e inventar nuevos criterios.

Espero que esto responda a su pregunta al menos parcialmente.

Actualización : una idea brillante acaba de llegar a mi mente :) Puede contar el número de secuencias monótonas en la cadena, por ejemplo, para la cadena 000111222233334443333222444455544443333 (un ejemplo rápido y simple, no corresponde a ninguna letra) que tenemos
00011122223333444 3333222444455544443333,
00011122223333444 3333222 444455544443333,
000111222233334443333222 4444555 44443333,
0001112222333344433332224444555 44443333 ,

Es decir, cuatro subsecuencias monotónicas.

Esto debería ser una buena generalización, solo cuente el número de cambios de letras reales y compare con el adquirido de la cadena detectada, este es un buen intento.

Algunos problemas e ideas:

La cadena es cíclica de alguna manera, por lo que debes lidiar con la detección de la monotonía en los extremos de la cadena (para evitar errores off-by-one),
Algunos artefactos deben tenerse en cuenta, por ejemplo, si sabe que la letra es lo suficientemente grande (por ejemplo, 20 píxeles de altura), desearía ignorar la interrupción de monotonía más corta que 3 elementos, por ejemplo :)

Tenga en cuenta que realmente estoy buscando una respuesta a mi pregunta. No estoy buscando un enlace a algún código fuente o a algún artículo académico: ya he usado la fuente y ya he leído artículos y aún no he descubierto la última parte de este problema ...

Estoy trabajando en una fuente de pantalla rápida OCRing y estoy progresando muy bien.

Ya estoy encontrando las líneas de base, separando los caracteres, transformando cada personaje en blanco y negro y luego contorneando cada carácter para aplicarle un código de cadena Freeman.

Básicamente es un código de cadena conectado a 8 que se ve así:

3 2 1 / | / 4-- --0 / | / 5 6 7

Entonces, si tengo una ''a'', después de todas mis transformaciones (incluida la transformación a blanco y negro), termino con algo como esto:

11110 00001 01111 10001 10001 01110

Entonces, el contorno externo puede verse así (es posible que me esté equivocando aquí, ese es el contorno ASCII-art y mi ''algoritmo'' puede tener un contorno incorrecto, pero ese no es el punto de mi pregunta):

XXXX X1111X XXXX1X X01111X X10001X X10001X X111X XXX

Siguiendo las X, obtengo el código de la cadena, que sería:

0011222334445656677

Tenga en cuenta que ese es el código de cadena normalizado, pero siempre puede normalizar un código de cadena como este: simplemente mantiene el entero más pequeño.

(Por cierto, hay una implementación súper eficiente para encontrar el código de cadena donde simplemente tomas los 8 píxeles adyacentes de una ''X'' y luego miras en una tabla de búsqueda 256 si tienes 0,1,2,3,4, 5,6 o 7)

Sin embargo, mi pregunta ahora es: a partir del código de cadena 0011222334445656677, ¿cómo puedo encontrar que tengo una ''a''?

Porque, por ejemplo, si mi ''a'' se ve así:

11110 00001 01111 10001 10001 01111 <-- This pixel is now full

Entonces mi código de cadena es ahora: 0002222334445656677

Y sin embargo, esto también es una ''a''.

Sé que el punto central de este código de cadena es ser resistente a cambios tan pequeños, pero no puedo entender cómo se supone que debo encontrar qué personaje corresponde a un código de cadena.

He estado tan lejos y ahora estoy atascado ...

(Por cierto, no necesito 100% de eficiencia y cosas como diferenciar ''0'' de ''O'' o de ''o'' no es realmente un problema)

El mes pasado, estaba lidiando con el mismo problema. Ahora, he resuelto este problema por el código de cadena vetex.

El código de cadena vetex es el código de cadena binario. Luego, lo corté en 5 partes. Obviamente, el número 0-9 tiene su propio caracter en otra parte.

Lo que necesita es una función d que mida la distancia entre los códigos de cadena. Después de eso, encontrar la letra de un código de cadena dado es sencillo:

Entrada:

códigos de cadena normalizados S para el conjunto de letras posibles (generalmente los códigos de Caín para AZ, az, 0-9, ...)
el código de cadena x de una letra que necesita ser detectado y que podría estar ligeramente deformado (el código de cadena no coincidiría con ningún código de cadena en el conjunto S )

El algoritmo recorrería el conjunto de posibles códigos de cadena y calcularía la distancia d(x,si) para cada elemento. La letra con la distancia más pequeña sería la salida del algoritmo (la letra identificada).

Sugeriría la siguiente función de distancia : para dos códigos de cadena, sume las diferencias de longitud de cada dirección: d(x,si) = |x0-si0| + |x1-si1| + .. + |x7-si7| d(x,si) = |x0-si0| + |x1-si1| + .. + |x7-si7| . x0 es el número de 0s en el código de cadena x , si0 es el número de 0s en el código de cadena si , etc.

Un ejemplo explicará mejor lo que estoy pensando. En la siguiente imagen están las letras 8, B y D, la cuarta letra es un 8 ligeramente deformado, que debe identificarse. Las letras se escriben con Arial con tamaño de fuente 8. La segunda línea de la imagen se amplía 10 veces para ver mejor los píxeles.

Calculé manualmente (con suerte, corrijo) los códigos de cadena normalizados que son:

8: 0011223123344556756677 B: 0000011222223344444666666666 D: 00001112223334444666666666 8'': 000011222223344556756666 (deformed 8)

Las diferencias de longitud (absolutas) son:

direction | length | difference to 8'' | 8 | B | D | 8''| 8 | B | D | ----------+---+---+---+----+-----+----+----- 0 | 2 | 5 | 4 | 4 | 2 | 1 | 0 | 1 | 3 | 2 | 3 | 2 | 1 | 0 | 1 | 2 | 3 | 5 | 3 | 5 | 2 | 0 | 2 | 3 | 3 | 2 | 3 | 2 | 1 | 0 | 1 | 4 | 2 | 5 | 4 | 2 | 0 | 3 | 2 | 5 | 3 | 0 | 0 | 3 | 0 | 3 | 3 | 6 | 3 | 9 | 9 | 5 | 2 | 4 | 4 | 7 | 3 | 0 | 0 | 1 | 2 | 1 | 1 | ----------+---+---+---+----+-----+----+----- sum 10 | 12 | 14 |

8'' tiene la menor distancia al código de cadena de 8 , por lo que el algoritmo identificaría la letra 8 . La distancia a la letra B no es mucho mayor, pero esto se debe a que el 8 deformado se parece casi al B

Este método no es escalado invariante. Creo que hay dos opciones para superar esto:

Para diferentes tamaños de fuente, con diferentes conjuntos de códigos de cadena normalizados
Un conjunto de códigos de cadena normalizados en un tamaño grande (por ejemplo, 35x46 píxeles) y escalando la letra de entrada (que debe identificarse) para este tamaño más grande.

No estoy seguro de si la función de distancia es lo suficientemente buena para el conjunto de todas las letras alfanuméricas, pero espero que sí. Para minimizar el error en la identificación de una letra, puede incluir otras funciones (no solo códigos de cadena) en el paso de clasificación. Y nuevamente, necesitaría una medida de distancia, esta vez para los vectores de características.

Podría convertir el código de cadena en un modelo aún más simple que transmita la topología y luego ejecutar el código de aprendizaje automático (que probablemente se escribiría en Prolog).

Pero no lo endosaría. La gente ha hecho / intentado esto durante años y todavía no tenemos buenos resultados.

En lugar de perder su tiempo con este enfoque no lineal / basado en umbrales, ¿por qué no usa una técnica robusta basada en la correlación? Lo más fácil sería convolucionar con plantillas.

Pero desarrollaría wavelets de Gabor en las letras y clasificaría los coeficientes en un espacio vectorial. Entrene una máquina de vectores de soporte con algunos ejemplos y luego úsela como un clasificador.

Así es como nuestro cerebro lo hace y estoy seguro de que es posible en la computadora.

Algunos chats al azar chatear (ignorar):

No usaría redes neuronales porque no las entiendo y, por lo tanto, no me gustan. Sin embargo, siempre me impresiona el trabajo del grupo Geoff Hintons http://www.youtube.com/watch?v=VdIURAu1-aU .

De alguna manera, trabaja en redes que pueden propagar información hacia atrás (aprendizaje profundo). Se habla de él donde permite que una red de reconocimiento de dígitos entrenada sueñe. Eso significa que establece una de las neuronas de salida en "2" y la red generará imágenes de cosas que cree que son dos en las neuronas de entrada.

Esto me pareció muy genial.