24 de septiembre de 2008

Algoritmo de Esqueletizacion de Pavlidis


En ocasiones, debido a la gran cantidad de información que presenta una imagen, resulta conveniente trabajar solo con las características más importantes de la imagen a procesar. Para el caso particular de reconocimiento óptico de caracteres las características más importantes se encuentran representadas en el esqueleto del caracter.

Entendemos por Esqueletización a una transformación que busca reducir la cantidad de datos o simplificar la forma del objeto, con el fin de encontrar características útiles en algoritmos de reconocimiento y clasificación.


El algoritmo de esqueletizacion de Pavlidis se basa en la idea de que los pixeles esqueletales son solo aquellos pixels que presentan alguna similaridad con alguna de las plantillas que se muestran a continuación:


En las plantillas del inciso A, al menos un píxel de los grupos etiquetados como A o B debe ser diferente de cero. Los píxeles marcados con el valor de 2 son píxeles esqueletales.

En la plantilla del inciso B, al menos un píxel marcado con debe ser diferente de cero. Si ambos píxeles etiquetados con C son diferentes de cero, entonces los píxeles etiquetados con CA o pueden tener cualquier valor. De otra manera, al menos un miembro de cada par marcados con BA y deben ser diferentes de cero


En base a esta teoría y atendiendo a dificultades en los resultados con el algoritmo antes mencionado, planteo una solución alternativa, la cual se basa en las rotaciones de las plantillas que muestro a continuacion:

Según lo cual, las cuatro rotaciones en 90º de cada una de las plantillas deben ser comparadas con cada uno de los 4-vecinos de cada pixel de la imagen. Los 4-vecinos de un pixel en una vecindad de 3x3 se denota bajo el siguiente esquema:
Y los que son necesarios a considerarse en el algoritmo de pavlidis y en ste algoritmo son los pixels 0,2,4,6.


Algoritmo
% Entrada: Imagen binarizada imBin normalizada (0 = negro, 1 = blanco)
% Salida: Imagen Esqueletizada normalizada (0=negro, 1=blanco)

REMAIN = 1; % se usa para denotar la existencia de pixeles esqueletales
SKEL = 0; % se fija a cierta cuando alguna vecindad de un pixel es similar a
% alguna de las plantillas existentes en P
CONVERTIR IMBIN A CEROS Y UNOS Y ALMACENARLA EN IMG
nf = NUMERO DE FILAS DE MATRIZ img
nc = NUMERO DE COLUMNAS DE MATRIZ img
d = 1 % columnas que no se evalúan por ser la plantilla de 3 x 3
MIENTRAS REMAIN = 1
REMAIN = 0;
PARA k=1 hasta 4 % los indices de los vecinos de un determinado punto
% se recorre toda la imagen
PARA i=1+d hasta nf-d
PARA j=1+d hasta nc-d
SI P TIENE EL VALOR DE 1 Y SI J-VECINO TIENE EL VALOR DE CERO
SKEL = 0
SI VECINDAD DE P CONCUERDA CON ALGUNA PLANTILLA, SKEL SE ACTUALIZA A 1
SI SKEL == 1 ENTONCES % si la plantilla concuerda con la matriz
img(i,j) = 2;
EN CASO CONTRARIO
img(i,j) = 3;
REMAIN = 1;
FIN SI
FIN SI
FIN PARA
FIN PARA
REEMPLAZAR TODOS LOS PIXELS CON VALOR “3” POR “0”
FIN PARA
FIN MIENTRAS % fin del algoritmo



Aca les dejo la implementación del algoritmo de pavlidis, con una ligera modificación hecha por mi parte para Adelgazamiento de Imágenes. El trabajo fue desarrollado en el curso de Procesamiento de Imágenes, un curso de Pre-grado de la carrera de Informática en la Universidad Nacional de Trujillo. El codigo esta hecho en matlab y se encuentra documentado.

4 comentarios:

oscar andrey dijo...

Buenos días Jhon Alvares, mi nombre es Oscar Andrey de la ciudad de Bucaramanga, Colombia, soy estudiante de Ing. control, y curso 6 semestre, me gusta todo lo relacionado con redes neuronales y métodos de aprendizaje, me gustaría saber mas a fondo, no se como si fuera un manual de la aplicación que creaste, o no se.. no se si me hago entender.. Espero que si.. mi correo es djandrey5@hotmail.com, espero me contestes y me colabores.. Muchas gracias de antemano..

ardal dijo...

Buenas tardes JHON, mucho gusto muy bueno tu trabajo
mi nombre es arnold perez estudian te ING CONTROL, 10 semestre de bucaramanga colombia. tengo algunas dudas en la implementacion de la esqueletizacion, tienes algun correo con el cual me pueda comunicar mi correo es arnoldp22@hotmail.com agradezco alguna comunicacion

Luis Flores dijo...

Hola, Excelente artículo, me agrada la manera en que explicas. De hecho, ésa es también mi filosofía.

Les dejo una liga a un artículo en mi sitio donde explico con igual detalle el algoritmo de Esqueletización de Zhang-Suen
y pondré definitivamente una liga a tu sitio para las personas que les interese conocer este algoritmo.

Saludos!

Luis

Carlos Masseratti dijo...

buen articulo este,buen algoritmo el de pavlidis, el problema es que no le entiendo del todo, soy algo cabeza dura, podrias ayurme a implementarlo en c?
Es para un proyecto de la uni