Captulo 2.
Tcnicas de procesamiento digital de imgenes y
reconocimiento de patrones.
2.1 Revisin sistema reconocimiento caracteres
Un sistema de reconocimiento tpicamente esta conformado por los siguientes partes [8]
[9]:
Adquisicin: Se refiere al proceso de convertir un documento a una representacin apta
para ser procesada por la computadora. Tal adquisicin y conversin puede ser realzada por un
escner, cmara fotogrfica o de video, etc. y el resultado puede variar dependiendo del proceso
de digitalizacin usado y el mtodo de codificacin.
Binarizacin: Convierte la imagen recibida en una imagen binaria separando as el fondo
de los objetos a analizar.
Anlisis de docume nto: Trata de analizar la estructura de un documento y entender la
informacin contenida en sus componentes.
Segmentacin: Se refiera a delimitar las regiones que nos interesan. En el caso del
reconocimiento de caracteres se refiere a las lneas y caracteres individuales.
Normalizacin: Trata de ajustar la forma, tamao y posicin del caracter esto con el
objetivo de minimizar la variacin entre imgenes de la misma clase.
Extraccin de caracte rsticas : Permite conocer las caractersticas como lo son el tamao,
permetro, rea, etc. As como caractersticas topogrficas como lo es la orientacin de
segmentos.
Reconocimiento: Convierte la imagen binaria en una representacin electrnica. Misma
que permite realizar operaciones de validacin y anlisis.
11
Prosproceso: Re refiere a mejorar el proceso de reconocimiento mediante el uso de
informacin contextual como lo es anlisis a nivel lingstico.
Figura 2.1: Sistema ptico de reconoci miento de caracteres
2.2 Binarizacin
Los mtodos de binarizacin se pueden dividir en dos tipos: Globales y locales [8].
Los mtodos globales tratan de encontrar un umbral el cual aplicar a toda la imagen entre
estos se encuentran los mtodos por umbral y Otsu. Los mtodos locales obtiene el umbral para
cada pixel en la imagen usando para ello los valores de sus vecinos, entre los mtodos de esta
categora entran el mtodo de Niblack y Saovola.
Los mtodos locales generalmente producen un mejor resultado al binarizar la imagen
incluso en situaciones donde la iluminacin en el documento es variable. Sin embargo las
limitaciones de procesamiento y memoria lo hacen difcil de implementar en dispositivos
mviles. Si bien se pueden utilizar alternativas como los son las imgenes integrales [10] para
obtener los resultados de la binarizacin local y una rpida ejecucin esto requiere memoria,
adems de que los grandes valores que se puede necesitar la imagen pueden provocar un
desbordamiento de bfer.
12
Por las razones mencionadas arriba se opto por un mtodo global que esta que se define
como [11]:
1 si f ( x , y ) T
g ( x, y )
0 si f ( x , y ) T
Para definir el tamao del umbral se recurre al algoritmo iterativo:
1. Se obtiene un estimado inicial del umbral T
2. Se calcula la media de los valores debajo (m1 ) y sobre (m2 ) del umbral T.
1
3. Se calcula el nuevo umbral: T = m 1 + m 2
2
4. Se repite el paso dos hasta que el nuevo umbral sea igual al umbral anterior.
2.3 Segmentacin
En el caso de la segmentacin se evaluaron dos mtodos Descomposicin de rbol X-Y y
Etiquetado de componentes conexos. Una breve explicacin de su funcionamiento, sus
caractersticas y por qu se eligi uno se muestra a continuacin.
2.3.1 Descomposicin de rbol X-Y
La descomposicin de rbol X- Y [8] es un algoritmo de bajo nivel que realiza la
proyeccin horizontal y vertical de una pgina para separar los caracteres de un documento.
Primero se obtiene la proyeccin horizontal de la pgina para obtener los renglones del
documento (Figura 2.2.). Una vez obtenidos los renglones se realiza la proyeccin vertical, se
13
analiza la proyeccin para obtener los caracteres del rengln. Estas proyecciones pueden variar
dependiendo de la complejidad del documento.
La descomposicin es un mtodo comnmente usado, sin embargo tiene las siguientes
desventajas:
1. Susceptible a fallar en la presencia si existen lneas que cubran o rodeen a los caracteres.
2. Puede fallar en la presencia de ruido en la imagen.
3. Requiere que la imagen se encuentre alineada, pro lo cual precisa de aplicar correccin de
inclinacin sobre la imagen.
La efectividad de este algoritmo puede no ser la adecuada para ser aplicado a dispositivos
mviles debido a que la posibilidad de que las imgenes obtenidas con la cmara de un telfono
celular contengan ruido es alta, la inclinacin de la fotografa tomada raramente estar
correctamente alineada y que estimar tamao del caracter es difcil dado que el histograma no sea
lo suficientemente claro debido a las variaciones de luz.
Figura 2.2: Proyecci ones vertical y horizontal
14
2.3.2 Etiquetado de componentes conexas
Es una tcnica que asigna una etiqueta a cada componente conexo para obtener al final
una regin [12]. Bsicamente el algoritmo recorre una imagen binaria de izquierda a derecha y
de arriba hacia abajo en busca de pxeles con valor 1 que se encuentren conectados entre si en
un rango que puede ser N8, N4 o ND y les asigna una etiqueta construyendo de esta manera
regiones.
Esta tcnica, a diferencia de la descomposicin de rbol X-Y, no es tan susceptible a tener
errores si los caracteres estn rodeados o de lneas que cubran o rodeen los caracteres. Adems
no requiere que la imagen se encuentre alineada con respecto al eje para ser efectiva lo cual es de
gran utilidad debido a que no siempre se pueden tener correctamente alienado el dispositivo
mvil con la imagen como seria con un escner de sobremesa o plano.
Figura 1.3: Imagen Binaria Figura 1.4: Eti quetado termi nado
Figur a 1.5: Eti quetado des pus de unificar
15
2.4 Normalizacin
Una vez binarizada la imagen se realzala normalizacin del caracter. Para esto se centra
la imagen en un plano cuyas dimensiones son iguales a m x m donde m es igual al tamao del
lado ms largo del caracter a normalizar. Despus esta imagen se escalara a un tamao de 128 x
128 pixeles y se le aplicara un filtro para eliminar el ruido que pueda quedar en la imagen para
terminar con un suavizado.
2.5 Extraccin de caractersticas
Para la fase de extraccin de caractersticas se propone utilizar Local Strokedirection
features (LSD) [8]. En esta tcnica se procesa por cada pixel 1 los pixeles repetidos en cada
una de las cuatro direcciones y despus es normalizado. Despus se divide la imagen en
secciones de tamao n x n y se procesan las direcciones de cada rea como el promedio de los
pixeles en el rea que en este caso serian ocho.
2.6 Clasificacin
2.6.1 K-vecino ms cercano
K-vecino ms cercano es un algoritmo de clasificacin supervisada, esto es que se parte
de un conjunto de muestras que son etiquetadas dentro de una clase a la que pertenecen; siendo
estas clases asociadas despus con un conjunto de muestras de entrenamiento. En este algoritmo
clasifica los objetos de acuerdo a sus atributos y a las muestras de entrenamiento [13].
Dado un conjunto de entrenamiento T = {(x1 , y1 ), (x2 , y2 ),..., (xn , yn )}, que contiene clases
conocidas, para decidir si una muestra desconocida x pertenece a una clase se decide mediante a
la probabilidad condicional p (y|x).
16
En su versin ms bsica (K =1) se busca determinar el vecino ms cercano al cual afecta x:
1_NN = argmin ||x - xi ||
Para determinar la cercana a de alguna instancia se utiliza por lo general distancias
euclidianas, aunque se pueden utilizar otras.
En el caso de k-vecinos ms cercano dado un dato xq a clasificar y sean x1 ...xk lo vecinos
ms cercanos a xq usando, en el caso de clasificaciones discretas:
f(xq) = argmax v
V (V, f(x i ))
t= 1
Y en el caso de continuas:
f (x ) i
i1
f (xq )
k
17