Algoritmos topológicos de adelgazamiento de imágenes digitales

Cámara Caunedo, Adrián (2016). Algoritmos topológicos de adelgazamiento de imágenes digitales. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S. de Ingenieros Informáticos (UPM), Madrid, España.

Description

Title: Algoritmos topológicos de adelgazamiento de imágenes digitales
Author/s:
  • Cámara Caunedo, Adrián
Contributor/s:
  • Giraldo Carbajo, Antonio
Item Type: Final Project
Degree: Grado en Matemáticas e Informática
Date: June 2016
Subjects:
Freetext Keywords: Topología digital; Plano digital; Imagen digital; Algoritmo de adelgazamiento; Continuidad digital; Función multivaluada; Retracciones digitales; Digital topology; Digital plane; Digital image; Thinning algorithm; Digital continuity; Multivalued function; Digital retractions
Faculty: E.T.S. de Ingenieros Informáticos (UPM)
Department: Matemática Aplicada
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (389kB) | Preview

Abstract

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.

More information

Item ID: 42884
DC Identifier: http://oa.upm.es/42884/
OAI Identifier: oai:oa.upm.es:42884
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 19 Jul 2016 10:58
Last Modified: 27 Oct 2016 07:48
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM