Resumen

En las estructuras de datos, muchas de las implementaciones o mapeos de problemas, sus soluciones o procesos, se basan en matrices binarias. Existen varios métodos y algoritmos que trabajan sobre ellas dependiendo de la complejidad del problema y los resultados esperados. El desarrollo de la tecnología, así como el incremento de la velocidad de procesado, ha sido considerable. Aún así es necesario incrementar la velocidad de los métodos de procesamiento ó mejorar los resultados de los métodos aplicados con un bajo costo de implementación. Esto con mayor énfasis en sistemas que requieren respuestas casi en tiempo real ó que utilicen procesos en lotes, donde el método de solución del problema sea recurrente.

El tratado de matrices, en ciertos problemas (descritos más adelante), es directamente el uso que tiene el filtro binario que se desarrolla en ésta tesis. El algoritmo propuesto, se basa en un caso base de solución de laberintos. Éste se modifica de acuerdo a los problemas específicos en los cuales se implemente. Orientados al trabajo de visión artificial y planeación de rutas, serán las pruebas del comportamiento del algoritmo.

En el área de visión artificial, el problema de reconocimiento de patrones con información difusa, es uno de los problemas a tratar. [1] En el reconocimiento de caracteres, existen varios métodos para la segmentación de los renglones. En imágenes con problemas de ruido, se utilizan filtros y procesados de imagen previos al reconocimiento. Generalmente, se utilizan algoritmos de filtros de reconocimiento de bordes para la localización de objetos como es el filtro Prewitt. [2] La distorsión en las imágenes puede distorsionar el área a reconocer y por tanto decrementar la eficiencia del reconocedor mediante filtros para sal y pimienta. [2] Se busca una manera de mejorar la selección de los renglones en las imágenes de texto a ser reconocidas (segmentación), mediante el uso del filtro binario diseñado en esta tesis.

El algoritmo realizado es un filtro binario capaz de conectar las orillas de una matriz binaria, junto con las orillas de los obstáculos dentro de ella. Dependiendo de la sensibilidad, la cuál se refiere a la verificación de sus vecinos, se hablará en el capítulo tres con más detalle. Sus resultados pueden variar según esta sensibilidad. Puede convertir objetos cóncavos en convexos rellenando espacios. Tiene un tiempo de corrida polinomial On³.

Los métodos de planeación de rutas en robótica, aplica a muchos campos como son, sistemas de realidad virtual, diseño asistido por computadora (CAD), manufactura (movimiento de brazos mecánicos ó robots), animación por computadora (videojuegos o movimiento de agentes en videojuegos), diseño de fármacos.[3] Un robot tiene no sólo un conjunto discreto de rutas, sino que, puede moverse en un espacio continuo. Puede tener un conjunto infinito de acciones y estados posibles. Para un robot circular que se mueve en una superficie plana, el espacio es esencialmente de dos dimensiones. [4] El problema principal es la distribución, donde se colocan millones de componentes y de conexiones. Después, generalmente se divide en dos partes: distribución de celdas y dirección del canal. [3] Se busca mejorar los resultados así como la velocidad de respuesta al problema. Actualmente existen soluciones a la planeación de rutas que son tardadas [2]. Algunas de las soluciones son en base a métodos inexactos y que pudieran no encontrar las soluciones existentes.

Los libros antiguos de la biblioteca franciscana de la Universidad de las Americas Puebla, actualmente se encuentran en proceso de digitalización. Se están escaneando para su difusión digital con otras universidades. Parte de la difusión de las imágenes, es convertirlas en texto. Se está desarrollando software de reconocimiento de caracteres para llevar a cabo esta tarea. Empero las imágenes, debido a lo deteriorado de los libros, poseen mucho ruido (manchas) y texto borroso, que deteriora el proceso de reconocimiento. Por lo cuál no es preciso el resultado que se obtiene mediante los métodos convencionales utilizados en un reconocedor de texto común. Se requiere de filtrar y preprocesar la imagen en editores, para lograr una mejora de calidad de imagen y por tanto de reconocimiento. A falta de un proceso previo de limpieza los sistemas de reconocimiento de caracteres comerciales no funcionan adecuadamente. Principalmente por que no logran definir correctamente las zonas de texto. Se planteará un modo de segmentar texto en imágenes de libros de acervos antiguos. Mediante el procesado de la matriz binaria que forma la imagen en blanco y negro. El resultado del procesado será el relleno de las letras de la imagen, dando como resultado más peso en los renglones. Para encontrarse la zona de texto, se suma la cantidad de unos en los renglones de la matriz que representa a la imagen. Al tener las letras de la imagen una secuencia de números 1´s que las representa, el algoritmo irá rellenando cada carácter. Logrando que cada letra, incluso estando borrosa, sea rellenada y el peso del renglón aumente. De éste modo, al cuantificar la cantidad de 1´s (unos) por renglón, la determinación de la zona de texto mejora automáticamente.

En la planeación de rutas, se propondrá un modo de encontrar caminos y un modo de segmentar la zona de tráfico. Esto como un preproceso para encontrar una mejor solución a una ruta. La ruta, es el camino que sigue el robot para llegar de la posición en que se encuentra a la posición deseada en un espacio de trabajo. [9] El espacio de trabajo, es la zona donde transitará el robot. Dentro del espacio de trabajo habrá obstáculos, que se interponen en el camino del robot. En caso de haber un camino, evadiendo los obstáculos, se necesitan varios pasos para encontrarlo y existen diferentes implementaciones, descritos en el siguiente capitulo. Para procesar el espacio de trabajo, se tomará de una imagen, y se representará mediante una matriz de MxN, Siendo M el alto y N el ancho de la imagen de la zona de tránsito. La matriz será binaria, es decir, sólo tendrá valores cero y uno en las posiciones Xij. Cada espacio en blanco se tomará como uno y cada espacio en colisión con obstáculo se representará con ceros. El propósito es encontrar una forma de procesar la información de ambos casos, de manera que el resultado final de los métodos se mejore. No se implementaran por completo los métodos, pero se indicarán el comportamiento y la tendencia de los procesos. Debido a lo extenso de cada uno de los problemas. Es decir en la visión artificial para el reconocedor de caracteres, el producto final serán las pruebas de mejoría en la segmentación de la imagen. No llegar hasta el reconocimiento final de cada uno de los caracteres. En la parte de la planeación de movimiento se experimentará con las zonas y los resultados de la segmentación utilizando el filtro binario. No se terminará el método de movimiento puesto que la planeación de movimiento y los cálculos del objeto en movimiento. Tendrían que definirse completamente el objeto para algún caso de uso específico.

Índice de contenido

Agradecimientos (archivo pdf, 35 kb)

Capítulo 1. Introducción (archivo pdf, 117 kb)

Capítulo 2. Casos de Uso y Marco Teórico (archivo pdf, 138 kb)

Capítulo 3. Descripción y Análisis del Algoritmo (archivo pdf, 168 kb)

Capítulo 4. Resultados (archivo pdf, 861 kb)

Capítulo 5. Trabajo a Futuro (archivo pdf, 69 kb)

Capítulo 6. Conclusiones (archivo pdf, 64 kb)

Referencias (archivo pdf, 59 kb)

Apéndice A. Algoritmo (archivo pdf, 58 kb)

López Rincón, O. 2005. Filtro binario para segmentación de matrices. Tesis Licenciatura. Ingeniería en Sistemas Computacionales. Departamento de Ingeniería en Sistemas Computacionales, Escuela de Ingeniería, Universidad de las Américas Puebla. Mayo. Derechos Reservados © 2005.