Alineamiento de cadenas cí­clicas en el reconocimiento de formas bidimensionales

Abstract

Cuando queremos comparar dos formas bidimensionales utilizando sus contornos, suele presentarse un problema importante: la invarianza al punto inicial en su codificación como secuencia. Aunque existen métodos heurísticos para conseguir un buen punto de inicio que funcionan en ciertos contextos, si queremos una solución genérica, la única manera de conseguir esta invarianza es midiendo distancias con todos los posibles puntos iniciales, es decir, utilizando el alineamiento por fuerza bruta con todo posible inicio de la secuencia del contorno. De aquí surge el concepto de cadena cíclica. Así, medir una distancia entre dos cadenas cíclicas sería lo mismo que medir una distancia entre todos los posibles puntos iniciales de las dos cadenas. Esta comparación es muy costosa computacionalmente y el trabajo de la literatura se ha orientado sobre todo a reducir este coste.<br/><br/>Existe mucho trabajo, a este respecto, en el dominio de las distancias de edición. Sin embargo, con otras técnicas, como son el alineamiento temporal no lineal (en inglés, Dynamic Time Warping) o los modelos ocultos de Markov (más tolerantes al ruido y otras deformaciones), no se ha profundizado demasiado con las cadenas cíclicas. Las aportaciones de esta tesis, van orientadas en esta dirección.<br/><br/>Con el alineamiento temporal no lineal (ATNL), hemos desarrollado un algoritmo eficiente para el cálculo del ATNL cíclico. Hemos planteado también diversas alternativas para acelerar el cálculo del ATNL cíclico en tareas de reconocimiento. En primer lugar, un heurístico para evitar el cálculo cíclico, en el caso de que tengamos categorías etiquetadas. En segundo lugar, un método óptimo para acelerar el cálculo cíclico, utilizando una cota inferior basada en un pseudo-alineamiento que aproxima la distancia cíclica. Finalmente, aportamos soluciones basadas en AESA (Approximating and Eliminating Search Algorithm) y una mejora al algoritmo LAESA (Linear AESA).<br/><br/>Con los modelos ocultos de Markov, estudiamos la topología lineal en el reconocimiento de contornos y desarrollamos extensiones cíclicas para los algoritmos de Viterbi (reconocimiento y entrenamiento) y Baum-Welch (entrenamiento).