Deskew, enderezando una imagen

Download:DeskewDemo

Introduccion

Cuando trabajamos con imagenes, sobre todo con documentos digitalizados, una de las distorciones habituales es la rotacion.

En el caso de los las imagenes que contienen texto impreso o figuras rectas (subrayado, cuadros, renglones, etc.) que permitan detectar el grado de inclinacion, es posible rectificar la misma utilizando algunos algoritmos de procesamiento de imagenes y deteccion de patrones.

Lo primero que deberiamos hacer es encontrar patrones de puntos colineales. Para esto podemos utilizar un algoritmo llamado Hough Transformation.

Hough transformation

A grandes rasgos este algoritmo detecta patrones de puntos colineales, co-circulares, o co-elipticos. En este caso en particular vamos a utilizarlo para detectar lineas.

Como pueden ver este algoritmo convierte un bitmap en un houghmap, un houghmap tiene al igual que el bitmap dos dimensiones. Una de las dimensiones es el angulo de la recta y la otra la distancia al origen.

Mi intencion no es explicar el algoritmo, para ampliar sobre este tema visiten wikipedia http://en.wikipedia.org/wiki/Hough_transform o lean cualquier libro sobre Computer Vision como por ejemplo “Hanbook of Computer Algorithms in Image Algebra”, 2nd Edition by Gerhard, Ritter.

Para tener una idea de que hace una transformacion de Hough, veamos la siguiente imagen:

image

Luego de aplicar una transformacion de Hough y el houghmap queda de la siguiente manera:

image

Cada punto en el houghmap representa el angulo de una recta  y su distancia al centro. Se pueden ver que hay dos maximo en la parte superior de la imagen y otros tantos cerca de la mitad. Cada maximo corresponde a una posible recta de la imagen original, en la siguiente figura se puede ver como se representa cada una:

image

Si quisieramos regresar esta imagen a la horizontalidad deberiamos tomar como referencia las lineas que provienen del texto y las dos rectas paralelas a este que se encuentran a la misma altura, es decir en el mismo angulo por ser paralelas.

Para entender mejor como se calcula el algulo de cada recta veamos el siguiente grafico de referencia:

image

La recta inferior se traslada con una linea perpendicular a la misma que pasa por origen y luego se mide el angulo que esta forma con el eje X. La distancia al centro se calcula sobre la recta punteada.  Es decir que si podemos calcular Tita podemos rotar la imagen 90 – tita grados (horario) para que la misma quede horizontal.

El problema con esta transformada es que tiene mucho costo computacional debido a que por cada punto calcula las N rectas posibles que pasan, cuando en realidad solo nos interesa una fraccion de las mismas y solo una parte de los puntos.

Optimizacion de Hough para Deskew

Es posible reducir mucho el tiempo de ejecucion restringiendo el angulo y los puntos admitidos bajo los siguientes criterios.

Criterio de seleccion de puntos

No todos lo puntos a la hora de hacer un Deskew son importantes, debemos utilizar solo aquellos que conforman la frontera inferior de las letras y no los que estan dentro o arriba de las mas mismas. En la siguiente imagen vemos que utilizando los pixeles inferiores podemos reducir enormemente el ruido en el mapa de hough dado que transformamos solo los puntos importantes:

image

De esta manera se optienen lineas mas nitidas y maximas mas claras en el mapa de hough. Para hacer esto antes de hacer la transformacion de un punto preguntamos si es opaco y si ademas el punto justo por debajo de este es nitidamente mas claro, si esto se cumple se procede a hacer la transformacion.

Seleccion de angulo

Como por lo general una imagen distorcionada por rotacion no suele estarlo por angulos superiores a 20 grados, podemos descartar del mapa hough angulos superiores a 20 e inferiores a -20 grados y el mapa se reduce de la siguiente manera:

image

El houghmap se reduce a casi 1/5 de su dimension en Y (angulo tita). Se ve claramente en esta imagen como esos dos puntos maximos (correspondientes a las dos lineas verticales) en la parte superior desaparecen.

imageEn esta imagen podemos ver como queda un houghmap luego de realizar estas mejoras.

El mapa tiene menos ruido y los maximos son mas claros, se ha reducido notablemente  la cantidad de lineas incluidas en esta transformacion. Permitiendo una estimacion mas exacta del angulo de skew.

Una vez efectuada la transformacion promediamos los titas de estas rectas y rotamos la imagen segun este promedio.

Solucion propuesta

Para implementar estas mejoras he utilizado la libreria AForge de Adrew Kirillov. Que ya trae una clase para Hough Line Transformation la cual utilice como base para introducir estas mejoras. La nueva clase se llamada FastDeskew y realiza un Auto Deskew.

About these ads

Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s