Algoritmos topológicos de adelgazamiento de imágenes digitales

Resumen

Este trabajo de fin de grado ha consistido en la descripción, implementación y análisis de un
conjunto de algoritmos para el tratamiento de imágenes digitales, varios de ellos ya conocidos
en la literatura y otros de nueva creación en paralelo al desarrollo de este trabajo.
Esta memoria, que describe el trabajo realizado, se organiza como sigue.
En primer lugar se introducirán los conceptos de plano digital y de topología digital y, a
continuación, se tratarán conceptos básicos dentro de la topología digital que serán utilizados a
lo largo del trabajo, empezando por definiciones básicas, como la de puntos adyacentes, seguido
de notaciones sobre ellos y conceptos que surgen a partir de las relaciones de adyacencia.
Más tarde, se definirá el concepto de imagen digital en el contexto de la topología digital,
así como definiciones de diferentes tipos de puntos dentro de las imágenes.
A continuación, se introducirá el concepto de reducción (topológica) de imágenes. Dicho
concepto será clave en el desarrollo de este trabajo, ya que los algoritmos desarrollados están
basados en estas reducciones. Seguidamente, se describirá el concepto de punto simple, fundamental
para realizar la eliminación de puntos dentro de una imagen de forma que se conserve
la topología (reducción de imágenes), y el concepto de punto extremo, necesario para que esta
reducción de imagen permita obtener un esqueleto de la misma (algoritmos de adelgazamiento).
Para terminar esta primera parte de la memoria, se hablará sobre los conceptos de función digital
continua univaluada y multivaluada, que serán necesarias para los algoritmos desarrollados
en este trabajo basados en retracciones digitales.
En una segunda parte de la memoria se describirán todos los algoritmos implementados
para el adelgazamiento de imágenes digitales, comenzando por algoritmos ya existentes y conocidos,
pasando por un algoritmo basado en retracciones univaluadas y una modificación de
los algoritmos clásicos utilizando estas condiciones adicionales de retracciones, para concluir con
la descripción de un algoritmo de basado íntegramente en funciones multivaluadas, creado en
paralelo a la realizacion de este proyecto. Este proyecto ha servido tanto para verificar el buen
funcionamiento de este nuevo algoritmo como para, analizando los resultado obtenidos, extraer
nuevas propiedades de este algoritmo.
Junto con la explicación de todos estos algoritmos, se incluirá también los resultados obtenidos
a partir de ellos sobre diversas imágenes, y comentarios sobre estos resultados.---ABSTRACT---This degree project has involved the description, implementation and analysis of a set of
algorithms for digital image processing, several of them already known in the literature and
other newly created in parallel to the development of this work.
This report, which describes the work done, is organized as follows.
First the concepts of digital plane and digital topology will be introduced and then basic
concepts within digital topology, that will be used throughout the work, will be discussed,
starting with basic definitions, such as adjacent points, followed by notations on them and
concepts arising from the adjacency relations.
Later, the concept of digital image will be defined in the context of digital topology, as well
as definitions of different types of points within the images.
Next, the concept of (topological) reduction of an image is introduced. This concept will be
fundamental in the development of this work, since developed algorithms are based on these
reductions. The concept of simple point, essential for the removal of points within an image so
that the topology (of the reduced image) is preserved, will be described, as well as the concept
of endpoint, required for this reduced image to represent its skeleton (thinning algorithms).
To conclude this first part of the memory, the concepts of digital continuous singlevalued and
multivalued functions, which are needed for the algorithms developed in this work based on
digital retractions, will be discussed.
In a second part of the memory all the algorithms implemented for thinning digital images
will be described, starting with existing and known algorithms, continuing with an algorithm
based on singlevalued retractions and modifications of the classical algorithms using these additional
retractions conditions, to conclude with a description of an algorithm based entirely
on multivalued functions, created in parallel to the realization of this project. This project has
served both to check the proper functioning of this new algorithm and, through the analysis of
the results obtained, obtain new properties of this algorithm.
Along with the explanation of all these algorithms, the results obtained from them on different
images and comments on these results, will also be included.