sistema eﬁciente de reconocimiento de gestos de la … · introducción este proyecto de ﬁn de...

UNIVERSIDAD POLITÉCNICA DE MADRID

Escuela Técnica Superior de Ingenieros de Telecomunicación

PSfrag replacements

NULO

. . .Recta producida pormínimos cuadrados

Esta recta es mejor

(x, y)

(x,y)

d

deje x

eje y

φuφ+ π

2

Departamento de Señales, Sistemas y Radiocomunicación

Grupo de Procesado de Señal y Simulación

Sistema eficiente de reconocimiento

de gestos de la mano

Proyecto Fin de Carrera

Autor: Jaime Silvela Maestre

Tutor: Javier Ignacio Portillo García

Madrid, Enero de 2000

Agradecimientos

En primer lugar quiero dar las gracias a mi tutor, Javier Portillo, y al Grupo de

Procesado de Señal y Simulación, por darme esta oportunidad y por su apoyo.

Algunos amigos me han prestado ayuda específica con el proyecto: Guillermo

Parodi me escuchó, me hizo sugerencias, me animó a publicar mis resultados, y

es siempre una fuerte influencia. Pablo Rosales y Guillermo Díez me prestaron su

tiempo y me hicieron sugerencias muy acertadas. Anabel González-Tablas encon-

tró los libros furtivos que le pedí. Javier Gamo y Pablo Rosales me echaron una

mano con LATEX.

Quiero también reconocer mi deuda con dos grupos de personas que no conoz-

co. En primer lugar, los programadores responsables de todo el software (gratis)

que he utilizado para hacer este proyecto: Emacs, Linux, Perl, LATEX, etc. En se-

gundo lugar, los autores de los excelentes libros, como Structure and Interpretation

of Computer Programs [1] e Introduction to Algorithms [3], que me han descubier-

to el mundo de la programación.

Por último, lo más importante. Quiero dar las gracias a todos mis amigos y a

mi familia. Me han ayudado más de lo que piensan, y, probablemente, más de lo

que pienso yo.

Índice general

Índice de cuadros VII

Índice de figuras IX

1. Introducción 1

2. Segmentación de la imagen 7

2.1. Relaciones de vecindad 9

2.2. Algoritmos de llenado de regiones 10

2.2.1. Algoritmo intuitivo 10

2.2.2. Algoritmo iterativo 12

2.2.3. Algoritmo híbrido 13

2.2.4. Llenado “breadth-first” o a lo ancho 14

2.2.5. Algoritmo intuitivo revisado 17

2.2.6. Otros algoritmos de llenado 19

2.3. ¿Regiones 4-conexas o 8-conexas? 19

2.4. Separación en regiones 20

3. Operaciones morfológicas 23

3.1. Almacenamiento de pixels de frontera 24

3.2. Erosión 24

3.3. Dilatación 26

3.4. Transformación de distancia 28

3.5. Esqueletización 30

3.6. Otras consideraciones 33

4. Obtención del contorno 35

4.1. Especificación del contorno 35

IV ÍNDICE GENERAL

4.2. Algoritmos funcionales y mutación 36

4.3. Algoritmos de obtención de contorno 37

4.3.1. Algoritmo intuitivo 37

4.3.2. El contorno visto como un grafo 39

4.3.3. Limpieza del contorno 43

4.4. Hallando el contorno, por fin 45

5. Procesado del contorno 47

5.1. Curvatura de arcos continuos 47

5.2. Nuestra definición de curvatura 48

5.3. El grafo de curvatura 50

5.4. Caracterización de elementos del contorno 53

5.5. Detección de elementos del contorno 55

6. Extracción de características 59

6.1. Área de la mano 59

6.2. Número de agujeros 60

6.3. Perímetro 60

6.4. Curvosidad 61

6.5. Número de dedos 61

6.6. Circularidad 61

6.7. Ángulo de inclinación 62

6.8. Momentos principal y secundario 67

6.9. Relación de aspecto 68

6.10. Cuestiones de implementación 68

6.11. El programa clasificador 69

7. Resultados 71

7.1. Área 80

7.2. Perímetro 81

7.3. Circularidad 82

7.4. Curvosidad 83

7.5. Agujeros 84

7.6. Dedos 85

7.7. Ángulo de inclinación 86

7.8. Relación de aspecto 87

7.9. Momento principal 88

ÍNDICE GENERAL V

7.10. Momento secundario 89

7.11. Rendimiento del programa 90

7.12. Utilidad de los parámetros calculados 91

8. Conclusiones y mejoras 97

A. Cómo usar el programa 101

B. Dactilología 103

C. Implementación 105

C.1. Organización del código 105

C.2. Representación de la imagen 106

C.3. Operaciones sobre regiones 109

C.4. Obtención del contorno 114

C.5. Procesado del contorno 118

C.6. Inclinación y momentos de inercia 120

C.7. Operaciones morfológicas 121

C.8. El intérprete 124

C.9. Interacción con el exterior 125

Bibliografía 127

Índice de cuadros

7.1. Tabla de resultados. Primer grupo de características (1). 74



7.4. Tabla de resultados. Segundo grupo de características (1). 77



7.7. Tiempo de ejecución de operaciones. 90

Índice de figuras

1.1. El sistema de clasificador completo. 1

1.2. Etapas de un clasificador. 2

1.3. Un hombre y su perro. 3

1.4. Una de las figuras de entrada al programa. 4

2.1. Aplicación de un umbral. 8

2.2. 4-vecinos y 8-vecinos recorridos en orden. 10

2.3. Una sola pasada deja pixels sin colorear. 12

2.4. Una segunda pasada también deja pixels sin colorear. 13

2.5. 4-distancia y 8-distancia. 14

2.6. Equivalencia entre matriz y grafo. 15

2.7. Llenado a lo ancho. Los pixels almacenados en cola se muestran

más oscuros. 16

2.8. Llenado a lo profundo. Los pixels en pila se muestran más oscuros. 18

2.9. Regiones 8-conexas pero no 4-conexas. 20

2.10. Resultado de segmentar la imagen. 22

3.1. Erosión incorrecta. 25

3.2. Erosión correcta. 25

3.3. Erosión de una región. Los pixels de frontera son grises. 27

3.4. Dilatación de una región. Los pixels de frontera son grises. 29

3.5. Transformación de distancia de la región. 31

3.6. Imagen transformada. 32

3.7. Índices de cruce de 1 y 2, respectivamente. 32

3.8. Resultado de esqueletizar. 34

4.1. Ejemplo de mutación. 36

4.2. Callejón sin salida. 38

X ÍNDICE DE FIGURAS

4.3. Contorno de la mano visto como un grafo. 39

4.4. Contorno con algoritmo “a lo ancho”. 41

4.5. Recorriendo el camino más corto evitamos callejones sin salida. 42

4.6. El pixel inicial es negro. Los pixels blancos sueltos son callejones

sin salida que el algoritmo evita. 42

4.7. Las dos mitades del contorno no casan. 43

4.8. Regiones que producen estrangulamientos de contorno. Los pixels

de frontera están coloreados. 43

4.9. Erosión seguida de dilatación. 44

4.10. Un “opening” no siempre vale. 44

4.11. Acción de LIMPIAR-CONTORNO. 45

5.1. La digitalización arruga el contorno. 49

5.2. Usamos sólo algunos pixels. 49

5.3. Postura correspondiente a la letra ‘q’. 50

5.4. Análisis de la postura correspondiente a la letra ‘q’. 51

5.5. Postura correspondiente a la letra ‘ch’. 53

5.6. Análisis de la postura correspondiente a la letra ‘ch’. 54

5.7. Postura correspondiente a la letra ‘r’. 55

5.8. Análisis de la postura correspondiente a la letra ‘r’. 56

6.1. Recta de regresión. 62

6.2. El método de mínimos cuadrados no es adecuado. 65

6.3. Una distancia distinta. 65

6.4. Distancia entre punto y recta. 66

6.5. Momentos de inercia pequeño y grande. 68

7.1. El alfabeto dactilológico español (1). 72

7.2. El alfabeto dactilológico español (2). 73

7.3. Área de la mano en número de pixels. 80

7.4. Perímetro de la mano en unidades naturales (unidad de longitud =

diámetro de un pixel). 81

7.5. Circularidad de la mano. 82

7.6. Curvosidad de la mano. 83

7.7. Número de agujeros de la mano. 84

7.8. Número de dedos de la mano. 85

7.9. Ángulo de inclinación de la mano en radianes. 86

ÍNDICE DE FIGURAS XI

7.10. Relación de aspecto de la mano. 87

7.11. Momento de inercia principal de la mano. 88

7.12. Momento de inercia secundario de la mano. 89

7.13. Diagrama del clasificador. Los grupos finales se muestran enmar-

cados. 94

Capítulo 1

Introducción

Este Proyecto de fin de carrera se inscribe en una linea de investigación seguida

en el Grupo de Procesado de Señal y Simulación (GPSS) en el campo de la Visión

Artificial, con el objetivo final de desarrollar un sistema clasificador de gestos de

la mano.

Las posturas de la mano que debe distinguir provienen del alfabeto dactilológi-

co para sordos, es decir, cada postura de la mano simboliza una letra. Así, el clasi-

ficador, dada una imagen de una mano, debe producir una letra, idealmente la que

corresponde a la mano. El clasificador podría formar parte de un sistema en que

una cámara tomase una foto de una mano, la digitalizase y la enviase a un orde-

nador, en el que se podría analizar la postura en que se encuentra, y decir a qué

letra corresponde, todo de forma automática (figura 1.1).

A

PSfrag replacements

NULO

. . .Recta producida pormínimos cuadradosEsta recta es mejor

(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 1.1 El sistema de clasificador completo.

Este es el tipo de problema que se trata de resolver en Visión Artificial, una

rama de la Inteligencia Artificial. La Visión Artificial es un campo multidisciplinar

en que se mezclan los Gráficos de Computador, la Estadística, Procesado Digi-

tal de Imagen, . . . Su objetivo es reconocer los objetos que están representados en

una imagen, y obtener información sobre ellos. En este sentido, es una disciplina

complementaria a los Gráficos por Computador, donde el objetivo es producir una

imagen que represente una serie de objetos a partir de una descripción de los mis-

2 Capítulo 1 Introducción

mos.

Las aplicaciones de la Visión Artificial son muchas y muy importantes, desde

el reconocimiento automático de errores de fabricación en componentes al análisis

de imágenes astronómicas o médicas. Pero, como en otras subdisciplinas de la

Inteligencia Artificial, el progreso es más lento de lo que se esperaba, por la simple

razón de que no sabemos cómo vemos.

El sistema que nos concierne es, entonces un clasificador de imágenes. Tales

sistemas consisten, por lo general, en una etapa inicial en que la imagen de partida

es procesada para resaltar alguna de sus características más interesantes, una se-

gunda etapa que realiza medidas sobre la imagen procesada y produce un vector de

características, y una tercera etapa, en que el vector de características de la imagen

se compara con vectores correspondientes a distintas clases, y se asigna a la clase

que se le parezca más según algún criterio acordado (figura 1.2).

IMAGENORIGINAL

−→ IMAGENPROCESADA

−→VECTOR DE

CARACTERÍSTICAS−→ CLASE DEL

OBJETO

Figura 1.2 Etapas de un clasificador.

Este Proyecto se ha centrado en las dos primeras etapas, es decir, en el proce-

sado de la imagen, y en la obtención de sus características. Propone varias car-

acterísticas medibles sobre las imágenes de entrada, y estudia su poder discrimi-

nador sobre el grupo de imágenes que nos interesa. Si las características estudiadas

toman valores claramente distintos para posturas de la mano distintas, servirán co-

mo base para el desarrollo de un sistema clasificador. El objetivo de este Proyecto

es, entonces, encontrar un conjunto de características medibles sobre imágenes de

manos, que sirvan para distinguir unas manos de otras, con vistas a formar parte de

un sistema clasificador.

Los sistemas de reconocimiento de imágenes pueden ser muy complicados y

lentos, y en este Proyecto se intentó desde desde el principio obtener un sistema

sencillo y rápido; lo suficientemente rápido como para poder usarlo en tiempo real,

es decir, interactivamente. Para conseguir una ejecución rápida, se decidió simpli-

ficar al máximo la etapa de procesado de la imagen. Observemos, entonces, con

qué tipo de imágenes nos enfrentamos.

Las imágenes de ordenador se pueden crear y almacenar en memoria de diver-

sas formas, pero la más conocida, y la que nos interesa, es la representación de

raster. La imagen, en este caso, está formada por filas y columnas de puntos, es

decir, es una matriz de pixels (figura 1.3), siendo un pixel un punto en la imagen;

3

el nombre pixel es una abreviatura de “picture element”, o elemento de la imagen.

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 1.3 Un hombre y su perro.

Una matriz de pixels puede reproducir cualquier imagen que deseemos, pero

la calidad de la reproducción aumenta cuantas más filas y columnas tengamos, y

cuantos más colores o tonos de gris pueda tener cada pixel. En este proyecto trata-

mos con imágenes de 576 filas y 768 columnas, en que cada pixel puede tener 256

tonos de gris, es decir, tiene un nivel de gris representado por 8 bits. Las imágenes

de este tipo tienen ya una calidad apreciable. Vemos un ejemplo en la figura 1.4,

que nos muestra, además, la postura de la mano que corresponde a la letra “s”.

Podemos observar en la figura que los pixels que corresponden a la mano son

más claros que los que corresponden al fondo. En la representación que usamos,

un pixel con un nivel de gris de 0 es negro, y un pixel con un nivel de gris de 255

es blanco. Es decir, que un pixel es más claro cuanto mayor es su nivel de gris.

Entonces, los pixels de la mano tienen un nivel de gris superior a los del fondo.

Podemos aprovechar este hecho para realizar un primer procesado de la imagen:

vamos a separar los pixels de la mano de los de el fondo. Para ello basta con es-

coger un determinado umbral, colorear de blanco los pixels con un nivel de gris

mayor que el umbral, y colorear de negro los demás pixels. Deberíamos obten-

er una imagen en que todos los pixels de la mano son blancos, y el resto negros.

Sin embargo, siempre vamos a encontrarnos con pixels de la mano coloreados de

negro, y pixels del fondo coloreados de blanco.

Para evitar esto usaremos una técnica normalmente empleada para otros fines.

Vamos a dividir la imagen, a la que hemos aplicado el umbral, en regiones conexas,


PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 1.4 Una de las figuras de entrada al programa.

es decir, en manchas de un solo color (nivel de gris), y vamos a borrar las re-

giones demasiado pequeñas, que consideraremos debidas a ruido. De esta forma

conseguimos el objetivo de separar la mano del fondo. La separación de los ob-

jetos que forman la mano es lo que se conoce, en la literatura de Procesado de

Imagen, como segmentación. Tratamos este tema en el capítulo 2.

Una vez tenemos nuestra imagen segmentada, podemos calcular el número de

pixels que pertenecen a la mano, que es proporcional a su área. Podemos calcular el

ángulo de inclinación de la mano usando operaciones de estadística, como veremos

en el capítulo 6. También podemos hallar de forma simple su contorno, que nos

podría dar una idea del número de dedos extendidos, del perímetro de la mano, de

su circularidad, y otras medidas. Pero para tomar estas medidas necesitamos que

el contorno sea continuo, es decir, hay que obtener el contorno de forma ordenada,

como si estuviéramos calcándolo. Esto ha resultado ser un problema complicado,

como veremos en el capítulo 4, y la mejor alternativa ha resultado ser eliminar de

la imagen segmentada algunos pixels que resultan problemáticos. Se buscó otras

alternativas para contar el número de dedos en la mano que evitasen las dificultades

de trabajar con el contorno.

La mejor alternativa es usar las llamadas operaciones morfológicas, como erosión

o esqueletización. La esqueletización consiste en extraer de la imagen un esqueleto,

de un pixel de grosor, que idealmente debe contener toda la información relevante

5

de la imagen. A partir de este esqueleto debe ser más sencillo contar el número

de dedos de la mano. Aunque este enfoque es prometedor, no se ha conseguido un

procedimiento de esqueletización satisfactorio (de hecho nadie lo ha conseguido

todavía). Este es el tema del capítulo 3.

Cuando hayamos conseguido todo esto, tendremos ya el número de agujeros

en la imagen, el área de la mano, su perímetro, su número de dedos, su pendiente

media y otras características, y observaremos si estas características son muy dis-

tintas para las distintas posturas de la mano. Si es así, serán adecuadas para formar

parte de un sistema clasificador.

Estructura de la memoria

En esta memoria se describe las etapas de procesado de imagen y extracción

de características. En los primeros capítulos, las descripciones de algoritmos se

hacen en pseudocódigo, es decir, lenguaje normal que usa construcciones típicas

en lenguajes de programación. Cualquier persona que haya programado debería

poder leerlo y entenderlo.

El capítulo 2 describe los algoritmos usados para segmentar la imagen, e intro-

duce la idea de ver la imagen como un grafo, que será de gran utilidad a la hora de

desarrollar algoritmos.

El capítulo 3 describe las operaciones morfológicas que se han usado en el

proyecto, que aunque han resultado menos útiles que la exploración del contorno,

son siempre interesantes. Además, han sido implementadas de forma muy eficiente.

Los capítulos 4 y 5 describen el procesado y clasificación del contorno de la mano,

la parte quizás menos precisa del Proyecto, aunque promete ser muy útil cuando se

desarrolle con más detenimiento.

El capítulo 6 resume las características medidas hasta ese momento, y muestra

cómo hallar otras características, basadas en parámetros estadísticos, de forma sen-

cilla. También presenta los pasos seguidos por el proyecto para generar el vector

de características. Aquí vemos cuáles han sido al fin las operaciones empleadas en

la extracción de características.

El capítulo 7 muestra los resultados, es decir, los vectores de características

obtenidos para cada una de las imágenes que se han examinado en el transcur-

so del Proyecto. En este capítulo vemos también si las características propuestas

tienen interés para la clasificación de imágenes, y mostramos el tiempo que tarda

en ejecutarse cada una de las operaciones necesarias en la obtención del vector de

características. Finalmente, vemos cómo podría ser un sistema clasificador basado


en este proyecto.

El capítulo 8 resume los resultados obtenidos, y propone direcciones de desar-

rollo para el futuro, pensando tanto en extender los resultados del presente Proyec-

to, como en obtenerlos de forma más rápida y sencilla.

En los apéndices hay un resumen de las implementaciones, en C++, de los

algoritmos desarrollados a lo largo del Proyecto. Será de utilidad principalmente

a quien desee modificar el código fuente o añadir extensiones; pero además, pre-

sentar los algoritmos en un lenguaje de programación real da una idea de algunos

detalles de “bajo nivel” que son muy importantes. También se incluye una breve

explicación acerca de cómo usar el programa que se ha desarrollado, y del alfabeto

dactilológico español, que es, al fin y al cabo, la fuente de las posturas de la mano

que han sido estudiadas.

Capítulo 2

Segmentación de la imagen

En esta fase tomamos como entrada una imagen de una mano en 256 tonos de

gris y debemos segmentarla, es decir, delimitar los objetos que la forman. Estamos

interesados en tres tipos de objetos: la mano, el fondo, y posibles huecos o agu-

jeros formados por los dedos. El primer paso que seguimos para esto es aplicar un

umbral, de forma que un pixel con un nivel de gris superior o igual al umbral se

considera perteneciente a la mano y se colorea de blanco, y un pixel con un nivel

de gris inferior al umbral se considera parte del fondo y se colorea de negro.

APLICAR-UMBRAL(umbral)

para cada pixel p de la imagen

si color(p) < umbral

color(p) ← negro

si no

color(p) ← blanco

El problema que nos encontramos es que, para cualquier umbral, obtenemos

manchas blancas que corresponden a objetos claros en el fondo, y manchas negras

que corresponden a sombras en la mano, como vemos en la figura 2.1.

¿Cómo evitamos esto? Una posible solución es filtrar la imagen antes de aplicar

el umbral, pero esto en primer lugar falsea nuestra imagen, y en segundo, para

una implementación eficiente requiere transformadas de Fourier [2]. La solución

escogida en este proyecto evita esto, y de paso resuelve también la detección de

agujeros.

La idea es que la mano debe ser una región conexa de pixels del mismo col-

or. Por conexa se entiende que entre cualquier par de pixels podemos encontrar

8 Capítulo 2 Segmentación de la imagen

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

(a) Imagen original

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

(b) Imagen después de aplicar un umbral de 90

Figura 2.1 Aplicación de un umbral.

2.1 Relaciones de vecindad 9

un camino formado por pixels vecinos pertenecientes a la mano. Un pixel blan-

co que no podamos conectar a la mano no pertenece a ella. Lo mismo ocurre con

las regiones negras. El fondo debe ser una región conexa, y también los agujeros

formados por los dedos deben ser conexos.

Vamos a separar nuestra imagen binaria en regiones conexas disjuntas. Para

distinguir unas regiones de otras vamos a colorear cada región de un nivel de gris

distinto. Para librarnos de los espúreos tan sólo tenemos que borrar las regiones

demasiado pequeñas. Es decir, vamos a pintarlas de negro si su color original era

blanco, y de blanco si su color original era negro.

Como vemos, necesitamos un procedimiento para colorear una región conexa

dado un punto inicial contenido en ella. Este problema se conoce en Visión Ar-

tificial como “object labelling” o “marking” [11], y a menudo se implementa sin

colorear las regiones, asignando una etiqueta a cada pixel como característica adi-

cional [4]. En el campo de los Gráficos por Computador este problema también

es importante. Es común en programas de dibujo querer colorear una región que

hemos “pinchado” con el ratón. En los libros de Gráficas por Computador [7]

este problema se llama “flood-fill”. Nosotros usaremos el término “llenado de re-

giones”.

Antes de resolver el problema necesitamos definir con precisión qué se en-

tiende por “camino de vecinos” entre pixels, y qué es un vecino.

2.1. Relaciones de vecindad

Una imagen de “raster” [7], que es el tipo más habitual en computadores, y el

que nos concierne, está representada mediante una agrupación de puntos en filas

y columnas o matriz. Cada punto tiene un nivel de gris (o color), codificado por

un número entero. En nuestro caso, hay 256 grises posibles, por lo que cada pixel

ocupa 8 bits de memoria.

Los vecinos de un pixel están en filas y columnas adyacentes. En concreto, hay

dos definiciones de vecindad: 4-vecindad y 8-vecindad.

Los 4-vecinos de un pixel dado son los que se encuentran directamente arri-

ba, abajo, a la izquierda y a la derecha. Los 8-vecinos añaden a los anteriores el

pixel de arriba a la derecha, arriba a la izquierda, abajo a la izquierda y abajo a

la derecha. Cuando en las secciones siguientes digamos “para todos los vecinos

del pixel p. . . ” debemos entender que recorreremos los vecinos en el orden que

especifica la figura 2.2.


PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 2.2 4-vecinos y 8-vecinos recorridos en orden.

Un camino de vecinos es un camino que podemos recorrer completamente

saltando de un pixel a su vecino, y al vecino de éste. . . hasta el final. Por tanto

tenemos dos posibles definiciones de región conexa, según el tipo de relación de

vecindad que queramos.

Reformulando la definición: una región 4-conexa es un conjunto de pixels del

mismo color, en que cualquier par de pixels puede ser unido por un camino de

4-vecinos pertenecientes a la región. La definición de región 8-conexa es análoga.

Por el momento basta con esta definición, aunque más adelante veremos que las

regiones 4-conexas nos convienen más.

En las secciones siguientes diremos que los vecinos de un pixel dado están a

una distancia 1 de él, los vecinos de sus vecinos a una distancia 2 y así sucesiva-

mente. También diremos que sus vecinos están a una profundidad de 1. Ya estamos

preparados para ver los algoritmos de llenado de regiones.

2.2. Algoritmos de llenado de regiones

Para formalizar: queremos, dado un pixel inicial, colorear de un nivel de gris

determinado la región conexa a la que pertenece el pixel. Como veremos, este es un

problema complicado con muchas soluciones posibles. En las siguientes secciones,

suponemos que la región de interés es blanca, y que queremos colorearla de negro.

2.2.1. Algoritmo intuitivo

El algoritmo más sencillo (y el que muestran los libros de texto) que resuelve

nuestro problema es el siguiente: dado un pixel inicial, digamos blanco, lo col-

oreamos de negro, y para cada uno de sus vecinos blancos realizamos la misma

operación. Hay que tener en cuenta que algunos pixels están en un borde de la im-

agen, y algunos de sus vecinos quedarían “fuera” de la imagen. Por supuesto, éstos

2.2 Algoritmos de llenado de regiones 11

no nos interesan. Este algoritmo no es más que una adaptación de lo que podría ser

la definición matemática de una región:

La región conexa a que pertenece un punto p está determinada por dos

reglas:

p pertenece a esta región

q pertenece a esta región si tiene el mismo color que p y tiene un

vecino v que pertenece a la región

LLENAR(p , gris_inicial, gris_final)

color(p) ← gris_final

para cada v ∈ Vecinos(p)

si color(v) = gris_inicial

LLENAR(v, gris_inicial, gris_final)

Pero este algoritmo, siendo correcto, no funciona, ni en el ordenador personal

usado para realizar el proyecto, ni en las estaciones de trabajo SPARC del Grupo

de Procesado de Señal y Simulación. La razón es su enorme recursividad. Se suele

decir que un algoritmo es recursivo cuando está definido en términos de sí mismo.

Para implementar un procedimiento o algoritmo recursivo, los compiladores

e intérpretes de la mayoría de lenguajes de programación usan una estructura de

datos en memoria llamada pila o en inglés stack. Veamos cómo funciona: en nue-

stro procedimiento, supongamos que hemos coloreado de negro el punto p, ini-

cialmente blanco, y que tenemos 3 vecinos, v1,v2,v3, sobre los que tenemos que

hacer LLENAR(vi , blanco, negro). Cuando hayamos aplicado este procedimiento a

v1 necesitamos “volver” a la situación anterior y llamar a LLENAR(v2 , gris). Nece-

sitamos salvar el contexto, lo que los compiladores de, entre otros lenguajes, C y

C++, consiguen almacenando toda la información que se encuentra en los registros

del microprocesador en la pila o stack. Esto se conoce como disciplina “framed-

stack” [1]. El resultado es que si en nuestro programa hay muchas llamadas re-

cursivas a procedimientos, la pila crece mucho, y puede producir un fallo de seg-

mentación, esto es, la pila crece tanto que invade memoria en uso, y el sistema

operativo aborta el programa para que no produzca daños. Esto es exactamente lo

que ocurre en nuestro caso.

Si tuviéramos un ordenador con más memoria o imágenes más pequeñas (las

que usamos tienen 768×576 = 442368 pixels) el algoritmo que hemos descrito


funcionaría, pero está claro que necesitamos desarrollar un algoritmo menos recur-

sivo.

2.2.2. Algoritmo iterativo

En el extremo opuesto a los procedimientos recursivos están los iterativos, que

se ejecutan en espacio (memoria) constante, y que no suelen contener llamadas a

sí mismos1.

Podemos formular fácilmente un procedimiento iterativo. Por ejemplo: dado el

pixel inicial, lo coloreamos de gris. Recorremos lo que queda de fila coloreando de

gris los pixels blancos que tengan un vecino gris. Cuando se acaba la fila vamos

a la siguiente, y de nuevo la recorremos coloreando de gris los pixels blancos que

tienen un vecino gris. Así hasta cubrir la imagen. Este procedimiento es iterativo:

sólo necesitamos tener en memoria la fila y la columna en que nos encontramos

dentro de la imagen.

Pero tiene un grave problema: es posible que en una fila dada haya dos pix-

els blancos pertenecientes a la misma región, separados por pixels negros. Este

procedimiento deja uno de los dos sin colorear, como vemos en la figura 2.3.

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 2.3 Una sola pasada deja pixels sin colorear.

Si queremos colorearlo debemos hacer otra “pasada” sobre la imagen, esta vez

de abajo a arriba. Pero una segunda pasada deja todavía pixels sin colorear, y en

general, para tener resultados aceptables debemos hacer muchas “pasadas” sobre

la imagen. De hecho para todo número de pasadas podemos encontrar una región

que no queda bien coloreada (por ejemplo, una espiral).

Podemos pensar en un algoritmo iterativo que coloree los pixels a distancia

1 de nuestro pixel, después los que están a distancia 2, y así sucesivamente, pero

1Es posible que un procedimiento que se llama a sí mismo se ejecute en espacio constante, esdecir, genere un proceso iterativo, como se demuestra en Abelson et al. [1]


PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 2.4 Una segunda pasada también deja pixels sin colorear.

incluso en este caso tendremos necesidad de “volver atrás” con pases sucesivos, lo

que ocurre en general con las soluciones iterativas a este problema.

2.2.3. Algoritmo híbrido

Ya sin esperanza de encontrar un algoritmo iterativo, el objetivo es encontrar

un procedimiento que no se llame a sí mismo tan a menudo como nuestro primer

intento. Podemos conseguir esto si, dado el pixel inicial, somos capaces de colorear

varios pixels antes de hacer una llamada recursiva. Un posible algoritmo es: dado

el pixel inicial, lo coloreamos. Coloreamos los pixels blancos a distancia 1 de él

(sus vecinos); coloreamos los pixels blancos a distancia 2, y hacemos una llamada

recursiva para cada pixel blanco a distancia 3.

LLENAR-2(p, gris_inicial, gris_final)


para cada pixel v a distancia 1 de p


color(v) ← gris_final






LLENAR-2(v, gris_inicial, gris_final)

¿Por qué hacer la llamada recursiva para distancia 3? Haciendo la llamada re-

cursiva con los pixels a distancia 2, se seguía produciendo un consumo excesivo de

memoria, y fallos de segmentación. Por otra parte hemos ocultado cómo podemos

implementar “para cada pixel v a distancia d”, lo que no es trivial. Podemos ver en


la figura 2.5 que si usamos 8-conexión y 8-distancia, los pixels a distancia n de uno

dado son cuadrados cuyos lados son filas y columnas de la imagen, así que no es

complicado recorrerlos secuencialmente. Con 4-distancia, en cambio, los vecinos a

distancia k forman un cuadrado cuyos lados están en diagonal respecto de las filas

y las columnas de la imagen, así que recorrer estos pixels es más complicado.

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 2.5 4-distancia y 8-distancia.

En ambos casos, la solución más eficiente y elegante consiste en almacenar las

posiciones relativas de los pixels a distancia k como variables globales de nuestro

programa. Debemos hacerlo para distancias 1, 2, y 3, para 4-conexión y para 8-

conexión, porque usar 8-distancia produce siempre regiones 8 conexas.

Este enfoque es claramente torpe, porque si decidiéramos hacer la llamada re-

cursiva en los pixels a distancia 4, necesitaríamos almacenar las posiciones relati-

vas de esos pixels. Esto es dado a errores y poco flexible. Además, es un método

algo redundante.

Vemos que hemos reducido el volumen de llamadas recursivas: entorno a un

pixel vamos a colorear 48 pixels y vamos a realizar 24 llamadas recursivas (suponien-

do que todos los pixels deben ser coloreados). Cada uno de los pixels sobre los que

hemos hecho la llamada recursiva va a examinar de nuevo los pixels de su entorno,

incluyendo nuestro pixel de partida. Es decir, nuestro pixel de partida va a ser col-

oreado una vez y examinado 24.

A pesar de todas estas pegas, el método funciona, y fue el usado durante varios

meses en este proyecto, hasta que un problema posterior dio la idea para un nuevo

algoritmo de llenado.

2.2.4. Llenado “breadth-first” o a lo ancho

La idea del siguiente algoritmo es que podemos ver nuestra matriz de puntos

como un grafo, en que los nodos representan pixels, y los nexos representan vecin-

dad.

El problema de llenar una región a partir de un punto inicial se convierte en


PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 2.6 Equivalencia entre matriz y grafo.

recorrer su grafo de vecinos y colorear los adecuados. El problema de recorrer un

grafo es de importancia enorme en informática, y está presente en ramas distintas,

como la inteligencia artificial, la teoría de algoritmos, problemas de búsqueda. . .

Para resolver nuestro problema vamos a adaptar una técnica de recorrido de

grafos que se conoce en la jerga como “breadth-first search” [3] y que algunos

autores españoles traducen como “búsqueda a lo ancho”. La explicación presentada

para este algoritmo imita a Cormen [3].

Pero antes tenemos que definir unos términos: una cola, en inglés queue, es

una serie de elementos puestos en fila. Podemos poner un elemento al final de

la cola (en inglés enqueue), y podemos quitar el primer elemento de la cola (en

inglés dequeue). En una cola, el primer elemento que metemos es el primero que

borramos, y el último que metemos es el último que borramos, por lo que a veces

se llama a las colas FIFOs (First In, First Out).

Durante la ejecución del algoritmo examinaremos pixels que posiblemente for-

men parte de la región. Si en efecto forman parte de la región, los colorearemos del

nivel deseado y los colocaremos en cola. A esto lo llamaremos “descubrir el pixel”.

La cola alberga pixels que tienen vecinos no descubiertos; cuando todos los veci-

nos de un pixel han sido descubiertos, lo retiraremos de la cola. Debido a esto, se

usa la memoria eficientemente, y de hecho no se producen fallos de segmentación.

El algoritmo es el siguiente. Dado un pixel inicial, lo coloreamos del nivel de

gris deseado, y lo ponemos en la cola (que hasta entonces estaba vacía); es decir,

lo descubrimos. A partir de ese momento, mientras la cola no esté vacía hacemos

lo siguiente: tomamos el primer elemento de la cola y examinamos sus vecinos. Si

alguno pertenece a la región (tiene el mismo nivel de gris), lo pintamos del nivel

de gris deseado, y lo ponemos en cola. Después quitamos el primer elemento de la

cola.

LLENAR-A-LO-ANCHO(p, gris_inicial, gris_final)



poner p en la cola

mientras la cola no esté vacía

q ← primer elemento en cola

para v ∈ Vecinos(q)



poner v en cola

quitar q de la cola

La mayor ventaja de este algoritmo es que recicla la memoria: una vez que un

pixel no tiene vecinos sin descubrir lo podemos sacar de la cola. Veamos cómo

funciona en la figura 2.7.

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 2.7 Llenado a lo ancho. Los pixels almacenados en cola se muestran más oscuros.


Los resultados de este algoritmo son excelentes: la ocupación de memoria es

relativamente baja, es 3 veces más rápido que el algoritmo híbrido (tarda 0.3 seg.

en segmentar una imagen), y es idéntico para 4-conexión y para 8-conexión. ¿Es

este procedimiento iterativo o recursivo? Podemos ver que el procedimiento no se

llama a sí mismo, pero tiene una cola que va creciendo (o decreciendo) a lo largo

de la ejecución del programa. Por esta razón diremos que es recursivo, aunque no

sea sintácticamente recursivo. Para verlo más claro, en este procedimiento cada

punto de nuestra imagen produce una búsqueda de sus vecinos, cada punto inicia

un llenado a lo ancho. Esto es reminiscente de nuestro algoritmo intuitivo.

Los conocimientos adquiridos con este algoritmo nos permiten entender mejor

el algoritmo intuitivo.

2.2.5. Algoritmo intuitivo revisado

Después de ver el algoritmo anterior podemos retomar nuestro algoritmo ini-

cial. Es muy parecido a la técnica de recorrido de grafos llamada “depth-first

search” o “búsqueda a lo profundo” según algunos autores españoles. Veíamos

antes que producía un consumo de memoria enorme debido a la disciplina “framed

stack” de los lenguajes como C y C++. Podemos entonces engañar al compilador

e implementar manualmente la recursión usando nuestra propia pila o stack.

Una pila es una serie de elementos puestos en fila. Podemos poner un elemento

al principio de la pila, y podemos borrar el primer elemento de la pila. Es notable

el parecido entre la pila y la cola, excepto que en la pila, tanto las inserciones como

los borrados de elementos se realizan en el mismo extremo de la fila, y en la cola,

las inserciones y los borrados se realizan en los extremos opuestos de la fila. En una

pila, sacamos siempre el último elemento que hemos metido, y el primer elemento

que hemos metido es el último que sacamos. Por eso las pilas se llaman a veces

LIFOs (Last In, First Out).

De nuevo, un pixel que examinamos por primera vez es descubierto y coloreado

del nivel de gris deseado, si es que pertenece a la región. La reformulación del

algoritmo intuitivo es: dado el pixel inicial, lo coloreamos y lo ponemos en la pila.

Mientras la pila no esté vacía, tomamos el primer elemento de la pila, y si tiene un

vecino perteneciente a la región (su nivel de gris es igual que el de la región), lo

coloreamos y lo ponemos en la pila. Si no tiene ningún vecino con el nivel de gris

de la región, lo quitamos de la cola.

LLENAR-A-LO-PROFUNDO(p, gris_inicial, gris_final)



poner p en la pila

mientras la pila no esté vacía

q ← primer elemento de la pila

si q no tiene vecinos con gris_inicial

quitar q de la pila

si q tiene un vecino v con gris_inicial


poner v en la pila

Observemos cómo funciona en la figura 2.8:

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 2.8 Llenado a lo profundo. Los pixels en pila se muestran más oscuros.

En la figura podemos ver que cuando el algoritmo llega a un callejón sin sal-

2.3 ¿Regiones 4-conexas o 8-conexas? 19

ida, vuelve atrás hasta encontrar un pixel que sí tenga vecinos blancos, y con-

tinúa el llenado a partir de ahí. Esta vuelta atrás tiene nombre propio en los libros

de Inteligencia Artificial [12]: backtracking. Este procedimiento tiene un compor-

tamiento idéntico al intuitivo, pero una utilización de memoria menor, debido a

que en la pila que mantenemos por nuestra cuenta sólo almacenamos pixels, y no

información de contexto que, como vemos, no es necesaria. De nuevo, este es un

procedimiento recursivo, aunque no se llame a sí mismo. La utilización de memo-

ria es muy superior a la del algoritmo “breadth-first”; de hecho en una imagen

cualquiera de las usadas en este proyecto la pila llega a albergar más de 300000

pixels. Por contra, en el algoritmo de llenado a lo ancho la cola nunca supera los

6000 elementos; es decir, tiene un consumo de memoria al menos 50 veces inferi-

or. También el llenado a lo ancho es más rápido. Tarda 0.3 seg. en segmentar una

imagen, frente a 0.9 seg. del llenado a lo profundo.

2.2.6. Otros algoritmos de llenado

Aunque los libros de Visión Artificial dan una visión somera del llenado de

regiones (que llaman etiquetado o marcado), y presentan algoritmos ineficientes,

en el campo de los Gráficos por Ordenador este es un problema muy importante.

De hecho, en el artículo de Levoy [8], se comparan cuatro estrategias de llenado

de regiones, una de las cuales es idéntica al llenado a lo ancho. La tendencia actual

es usar algoritmos de llenado por scan-lines, en que se trata de llenar de forma

iterativa una fila de pixels entera, antes de hacer una llamada recursiva o almacenar

pixels en pila o cola. Pueden verse ejemplos en los libros de Gráficos [7].

2.3. ¿Regiones 4-conexas o 8-conexas?

Hemos visto que tenemos varios algoritmos de llenado para elegir, entre los

que el llenado a lo ancho es el mejor. Pero ¿qué tipo de regiones nos interesa tener?

La elección de este proyecto es buscar regiones 4-conexas; la razón es que estas

regiones son más restrictivas y tienen contornos más suaves. Veremos que aún

usando regiones 4-conexas, los contornos no se comportan suficientemente bien, y

será necesario modificarlos.

La figura 2.9 muestra ejemplos de la diferencia entre usar 8-conexión y 4-

conexión:

Hay un beneficio adicional en usar 4-conexión. Usando 4-conexión, cada pixel

va a examinar sus 4 vecinos, y de la misma forma va a ser examinado por ellos.


PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 2.9 Regiones 8-conexas pero no 4-conexas.

Si usamos 8-conexión, cada pixel examina y es examinado 16 veces, es decir, el

doble de veces. Por tanto, aunque la complejidad asintótica de nuestros algoritmos

de llenado sea igual en 4-conexión que en 8-conexión, podemos esperar que el

4-llenado sea más rápido.

Otro detalle: hemos visto que en nuestros algoritmos de llenado se descubre ca-

da pixel una vez y se examina varias. Podemos evitar esto si añadimos a cada pixel

una lista con sus vecinos no descubiertos, lo que se conoce en los libros de Al-

goritmos y Estructuras de Datos como representación con lista de adyacencia [3].

Cuando descubriéramos un pixel lo borraríamos de las listas de adyacencia de sus

vecinos. Así evitaríamos la redundancia anterior. No está claro que esta estrategia

pueda mejorar los algoritmos: evitamos redundancia pero por cada pixel tenemos

que modificar cuatro u ocho listas. Además, es complicada. Quizás un proyecto

posterior investigue este punto.

2.4. Separación en regiones

Ya sabemos que queremos tener regiones 4-conexas, y que las podemos obtener

usando, por ejemplo, LLENAR-A-LO-ANCHO. Debemos colorear cada región de la

imagen con un nivel de gris distinto para poder distinguirlas, y como sabemos que

vamos a borrar alguna de las regiones, es conveniente acordarnos de su color ini-

cial. Para borrar una región cuyo color inicial era negro, la colorearemos de blanco,

y si el color inicial era negro, la colorearemos de blanco. El criterio para borrar una

región es que sea demasiado pequeña, es decir tenga un número de pixels menor

que un umbral convenientemente elegido. Es fácil integrar en nuestros algoritmos

de llenado la cuenta de pixels que posee la región. En el caso de LLENAR-A-LO-

ANCHO o LLENAR-A-LO-PROFUNDO, basta con sumar 1 cada vez que sacamos un

pixel de la cola o de la pila. Por tanto, cada región puede quedar descrita también

de forma sencilla por el número de pixels que posee.

Esta representación de una región es suficiente para nuestros propósitos. Para

2.4 Separación en regiones 21

concretar, representamos una región mediante un pixel que pertenezca a ella, su

color inicial, y el número de pixels que contiene. En la etapa de segmentación,

construimos un mapa de regiones, es decir, una lista de regiones representadas

como hemos visto. La construcción del mapa de regiones es la estrategia general

a usar cuando no sabemos cuántas regiones debe tener la imagen; pero dado que

en este Proyecto nos enfrentamos con un tipo de imagen particular, es más sencillo

usar un método distinto.

En este proyecto suponemos que sólo hay una mano, esto es, hay una sola

región blanca, lo cual simplifica la segmentación. Buscamos regiones blancas hasta

encontrar una con un número de pixels superior a un determinado umbral. Cuando

la encontramos pintamos de negro todos los pixels que no pertenecen a ella, y

después la pintamos de blanco (porque la habíamos pintado de gris). Con esto

hemos eliminado las regiones blancas indeseadas. Ahora buscamos las regiones

negras, y si son menores que un umbral las pintamos de blanco.

Con esto, nuestra imagen contiene una región blanca correspondiente a la ma-

no, y una o más regiones en distintos tonos de gris, correspondientes al fondo. La

presencia de más de una de estas regiones indica que hay un agujero en la imagen.

El número de agujeros se puede contar fácilmente sin más que sumar 1 por cada

región lo suficientemente grande.

Resumiendo:

SEGMENTAR

nivel = 0

repetir

buscar siguiente pixel blanco p

nivel ← nivel + 1

tamaño ← LLENAR-A-LO-ANCHO

hasta que tamaño > umbral-blanco

pintar pixels fuera de la última región de negro

repetir

buscar siguiente pixel negro p

nivel ← nivel + 1

tamaño ← LLENAR-A-LO-ANCHO

si tamaño < umbral-negro

LLENAR-A-LO-ANCHO(p, blanco)

hasta que no queden pixels negros


Podemos ver en la figura 2.10 el resultado de aplicar SEGMENTAR a la imagen

de prueba mostrada al principio del capítulo.

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 2.10 Resultado de segmentar la imagen.

Capítulo 3

Operaciones morfológicas

Una vez segmentada la imagen, el objetivo es contar el número de dedos, para

lo cual procesaremos el contorno de la mano. Como veremos en los capítulos 4

y 5, la obtención y el procesado del contorno de la imagen presentan muchas com-

plicaciones. Otra alternativa para contar el número de dedos de la mano es obtener

el esqueleto de la mano. El esqueleto es una serie de lineas de 1 pixel de grosor

que pasan por el centro de la región estudiada. En el caso de que logremos generar

el esqueleto correctamente, tendremos una linea pasando por el centro de cada de-

do, y quizás una linea pasando por el centro de la muñeca. Entonces, no tenemos

más que contar el número de lineas de esqueleto, lo que podemos hacer fácilmente

contando el número de extremos de linea.

La obtención del esqueleto de una región es un problema difícil y no ha sido re-

suelto satisfactoriamente nunca. Pertenece a un tipo de operaciones llamadas mor-

fológicas. Otras operaciones morfológicas son la erosión, la dilatación, la trans-

formación de distancia, la abertura y el cerrado. Usaremos alguna de estas opera-

ciones en el capítulo 4.

En este capítulo se muestra la forma en que las operaciones morfológicas han

sido implementadas en el proyecto. La idea de usar el esqueleto para contar dedos

todavía no es practicable, pero no hay que descartarla.

A lo largo de todo este capítulo, todos los pixels de la región de interés se

suponen blancos, y todos los pixels de fondo se suponen negros.

24 Capítulo 3 Operaciones morfológicas

3.1. Almacenamiento de pixels de frontera

Las implementaciones de los algoritmos morfológicos que veremos a contin-

uación están basadas en el mismo principio que la búsqueda a lo ancho; es decir,

vemos la matriz de pixels como un grafo, y lo recorremos a lo ancho, usando una

cola para almacenar los pixels a partir de los cuales debe continuar el recorrido.

En estos algoritmos, al contrario que antes, vamos a comenzar el recorrido de

la región por la frontera, y vamos a progresar hacia el interior. Para ello, vamos

a almacenar los pixels de frontera de la región en una cola. Veremos pronto que

resulta útil colorear los pixels de frontera de un color que no se pueda confundir con

el fondo ni con la mano. En nuestro caso, el fondo es negro, y la mano blanca, así

que coloreamos la frontera de gris. Comprenderemos mejor esto en el capítulo 4,

donde examinamos diversas formas de guardar el contorno en una cola. En este

capítulo no necesitamos más que almacenar los pixel de frontera, no importa en

qué orden. El siguiente algoritmo resuelve el problema. Usa el símbolo Q para

denotar la cola. A partir de ahora, usamos encolar(Q, p) para decir que hemos

puesto el pixel p en la cola Q, y descolar(Q) para decir que hemos borrado el

primer elemento de la cola.

GUARDAR-FRONTERA(Q)

para cada pixel p en la imagen

si ( color(p) = blanco Y

existe v vecino de p tal que color(v) = negro)

color(p) ← gris

encolar(Q, p)

3.2. Erosión

Una erosión consiste en borrar la frontera de una región. De forma intuitiva,

podríamos pensar en recorrer la imagen fila por fila y colorear de negro cada pixel

de frontera. Sin embargo, una vez hemos borrado un pixel, hemos convertido a

sus vecinos en pixels de frontera, si no lo eran ya. El resultado es que acabamos

borrando la imagen completa, como vemos en la figura 3.1. Examinamos este tipo

de problema en profundidad en la sección 4.2, página 36.

Hay dos formas sencillas de evitar este problema. Una es hacer una copia de la

imagen original. Recorremos la imagen principal, y cuando encontramos un pixel

3.2 Erosión 25

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 3.1 Erosión incorrecta.

de frontera, borramos el pixel homólogo en la imagen auxiliar. Cuando terminamos

el recorrido, la región erosionada está en la imagen auxiliar.

Otra forma es colorear los pixels de frontera de gris. Como hemos definido un

pixel de frontera como un pixel blanco con un vecino negro, un pixel gris no pro-

duce pixels de frontera falsos. Después recorremos la imagen otra vez y borramos

los pixels grises, como vemos en la figura 3.2.

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 3.2 Erosión correcta.

Estos dos métodos son correctos y funcionan bien si queremos realizar una

erosión sobre la imagen. Pero ¿y si queremos realizar varias erosiones? En ese caso,

para cada nueva erosión debemos repetir el proceso, es decir, recorrer la imagen, y

pintar de gris cada pixel de frontera. Esto es poco eficiente.

Las ideas desarrolladas a lo largo de este proyecto sobre búsqueda a lo ancho

tienen también aplicación aquí. En el siguiente algoritmo, hacemos un recorrido “a

lo ancho” de la región, solo que, al contrario que en el algoritmo de llenado, vamos

a empezar con los pixels de frontera y progresar hacia el interior.

Empezamos por almacenar los pixels de frontera en una cola, Q, y colorearlos

de gris. Después colocamos un símbolo especial, NULO, al final de la cola. La

función de este símbolo es que no puede representar un pixel. Tomamos la cabeza

de la cola. Si es un pixel, exploramos sus vecinos, y si alguno es blanco, lo ponemos

en la cola y lo coloreamos de gris. Después borramos la cabeza de la cola. Si la

cabeza de la cola es el símbolo NULO, hemos realizado una erosión. Para realizar

una nueva iteración, quitamos NULO de la cabeza de la cola y lo colocamos al

final. En el procedimiento mostrado primero(Q) denota al primer elemento en la

cola Q.


EROSIONAR (num-repeticiones)

GUARDAR-FRONTERA(Q)

mientras num-repeticiones > 0

encolar(Q, NULO)

h ← primero(Q)

mientras h 6= NULO

para cada n ∈ vecinos(h)

si color(n) = blanco

color(n) ← gris

encolar(Q, n)

color(h) ← negro

descolar(Q)

h ← primero(Q)

descolar(Q) ;; eliminar NULO

num-repeticiones ← num-repeticiones - 1

Vemos cómo funciona en la figura 3.3.

En cada iteración, comenzamos con los pixels de frontera almacenados en la

cola Q, seguidos de NULO. Entonces vamos añadiendo los “nuevos” pixels de

frontera, después de NULO, y vamos borrando los “viejos” pixels de frontera de

la cabeza de la cola. Es decir, los pixels que añadimos después de NULO son los

vecinos de los pixels almacenados antes de NULO. Este algoritmo tiene varias ven-

tajas. En primer lugar, sólo examina los pixels que elimina y sus vecinos, lo cual

es un ahorro enorme respecto de examinar todos los pixels de la imagen en cada

iteración. En segundo lugar, al igual que en el algoritmo de llenado a lo ancho, la

cola sólo almacena los pixels cuyos vecinos no han sido examinados, lo cual es

eficiente. En cada momento la cola alberga los pixels de frontera de la región actu-

al. Puesto que erosiones sucesivas encogen la región, almacenamos en cola como

máximo tantos pixels como pixels de frontera tiene la imagen original. Este mismo

método se puede aprovechar para implementar eficientemente las otras operaciones

morfológicas.

3.3. Dilatación

La dilatación es casi la operación inversa a la erosión, aunque una dilatación

no es capaz de reponer todos los pixels que la erosión borra. Consiste en añadir

3.3 Dilatación 27

PSfrag replacements

NULO

NULO

. . .

. . .

Recta producida pormínimos cuadradosEsta recta es mejor

(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 3.3 Erosión de una región. Los pixels de frontera son grises.


una nueva capa de pixels a la región. La combinación de una erosión y una di-

latación produce como resultado las operaciones de abertura (erosión seguida de

dilatación), y cerrado (dilatación seguida de erosión).

El algoritmo usado para la dilatación es idéntico al de erosión, excepto que

añadimos pixels negros (de fondo) a la cola, y cuando sacamos un pixel de la cola

lo coloreamos de blanco (ahora pertenece a la región).

DILATAR (num-repeticiones)

GUARDAR-FRONTERA(Q)

mientras num-repeticiones > 0

encolar(Q, NULO)

h ← primero(Q)

mientras h 6= NULO


si color(n) = negro

color(n) ← gris

encolar(Q, n)

color(h) ← blanco

descolar(Q)

h ← primero(Q)

descolar(Q)

num-repeticiones ← num-repeticiones - 1

Las consideraciones de eficiencia de la erosión sirven aquí también, excepto

por que la cola aumenta de tamaño con cada iteración, y por tanto almacenamos

tantos pixels como pixels de frontera hay en la región final.

3.4. Transformación de distancia

La transformación de distancia de una región consiste en asignar a cada pixel

su distancia a la frontera, como en la figura 3.5.

Esto es parecido a la erosión: una erosión borra los pixels de frontera, que están

a distancia 0 de la frontera, y cada nueva erosión borra pixels a una distancia de la

frontera 1 mayor que los de la iteración anterior. Esto quiere decir que los pixels

que una erosión repetida borra en la iteración n son los mismos pixels a los que la

transformación de distancia debe asignar n como nivel de gris. Es fácil, entonces,

adaptar el algoritmo de erosión para que sirva en la transformación de distancia.

3.4 Transformación de distancia 29

PSfrag replacementsNULO

NULO

NULO . . .

. . .


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 3.4 Dilatación de una región. Los pixels de frontera son grises.


TRANSFORMAR

distancia ← 1

GUARDAR-FRONTERA(Q)

para cada b en Q

color(b) ← distancia

mientras Q not vacia

distance ← distancia + 1

encolar(Q, NULO)

h ← primero(Q)

mientras h 6= NULO


si color(n) = blanco

color(n) ← distancia

encolar(Q, n)

descolar(Q)

h ← primero(Q)

descolar(Q) ;; elimina NULO

Este algoritmo requiere un solo pase sobre la imagen (de hecho, ni siquiera un

pase completo), en contraposición al chamfer algorithm, que requiere dos pases

sobre la imagen. Vemos sus resultados en la figura 3.6.

3.5. Esqueletización

La esqueletización o adelgazamiento es una técnica muy usada en reconoci-

miento de patrones. Consiste en eliminar pixels de la imagen hasta que queda un

esqueleto de un pixel de grosor. Idealmente, este esqueleto contiene toda la infor-

mación relevante de la región, y en particular, debe conservar el número de regiones

de la imagen, y debe ser parecido a la región original. Esto es complicado de con-

seguir. De hecho, aunque ha habido muchos intentos de resolver el problema, no

hay todavía una solución completamente satisfactoria.

El algoritmo propuesto usa las ideas de recorrido a lo ancho, y es una versión—

más eficiente—del algoritmo de Zhang y Suen [13].

La idea del algoritmo es que la esqueletización se puede ver como la elim-

inación de capa tras capa de pixels de frontera, como erosiones repetidas, pero

teniendo cuidado de no eliminar algunos pixels que mantienen las relaciones de

3.5 Esqueletización 31

PSfrag replacements

NULO

NULO

NULO

. . .

. . .

. . .

. . .


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 3.5 Transformación de distancia de la región.


PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 3.6 Imagen transformada.

conexión. Los pixels que podemos borrar se caracterizan, según Zhang y Suen,

por:

Su índice de cruce es distinto de 1.

Tienen más de 1 y menos de 7 8-vecinos.

En el algoritmo propuesto, los pixels de frontera son coloreados de gris y al-

macenados en una cola. A medida que recorremos la cola vamos sustituyendo los

pixels de frontera pos sus vecinos, coloreados de gris. Los pixels que no debemos

eliminar son aquellos que producen una nueva conexión entre pixels de la fronte-

ra. El índice de cruce de un pixel es, entonces, el número de regiones grises que

existirían en los 9 pixels que rodean a dicho pixel, suponiendo que este pixel se

elimina. Este número es el mismo que el número de transiciones de gris a blanco o

negro si recorremos los vecinos en orden. En la figura 3.7 podemos ver ejemplos:

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 3.7 Índices de cruce de 1 y 2, respectivamente.

En el algoritmo propuesto, cuando un pixel no cumple las condiciones nece-

sarias para ser eliminado, lo coloreamos de un color distinto, digamos rojo, y no lo

3.6 Otras consideraciones 33

ponemos en cola. El algoritmo completo es:

ESQUELETIZAR

GUARDAR-COLA(Q)

mientras Q no vacia

h ← primero(Q)

para cada n ∈ 8_vecinos(h)

si (color(n) = blanco)

si ( indice_de_cruce(n) = 1 AND

num_8vecinos(n) >= 2 AND

num_8vecinos(n) <= 6)

color(n) ← gris

encolar(Q, n)

sino

color(n) ← rojo

descolar(Q)

Este procedimiento da buenos resultados cuando la frontera de la región bajo

estudio es suave; si no, produce segmentos espúreos de esqueleto. Un saliente en la

frontera produce líneas de esqueleto que a menudo son falsas. Una forma de evitar

esto es erosionar la región varias veces antes de hallar su esqueleto, pero no es una

solución general: fronteras irregulares siguen produciendo esqueletos falsos. Por

otra parte, la forma de la región queda bien reflejada en el esqueleto, es decir, el

proceso es poco distorsionante. Vemos un ejemplo en la figura 3.8.

3.6. Otras consideraciones

En todos los algoritmos de esta sección, el primer paso ha sido almacenar los

pixels de frontera en una cola y colorearlos de gris. Esto es poco eficiente. Es más

sensato almacenar los pixels de frontera en cola sólo una vez, para lo que esta co-

la debe estar siempre disponible, es decir, debe ser una variable global. Esta es la

estrategia seguida en el proyecto. Los algoritmos, entonces, usan y modifican la

cola global, y es fácil encadenar operaciones; por ejemplo, realizar 10 erosiones

seguidas de una transformación de distancia no implica recomputación de la fron-

tera. Además, al usar una cola global, sólo hace falta pedir memoria al sistema

operativo una vez.


PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 3.8 Resultado de esqueletizar.

Capítulo 4

Obtención del contorno

Hemos visto en el capítulo 2 cómo obtener, a partir de la imagen original, una

imagen con los pixels de la mano formando una región 4-conexa blanca, y con los

pixels de fondo formando una o más regiones 4-conexas de diversos tonos de gris.

Esto nos permite medir el número de pixels de cada región, y el número de regiones

grises es 1 más que el número de agujeros en la mano.

Ahora nos interesa contar el número de dedos de la mano, y para ello en este

proyecto se ha seguido dos estrategias distintas. Una es usar operaciones mor-

fológicas, como en el capítulo 3; otra, obtener el contorno de la mano, y medir

su curvatura, usando las definiciones de la geometría diferencial [5]. Los dedos

corresponderán a zonas con una curvatura más o menos marcada y estable.

Puede parecer sencillo obtener el contorno a partir de nuestra imagen segmen-

tada, pero hay que tener en cuenta que si queremos hallar la curvatura, debemos

recorrer los pixels del contorno de forma ordenada. También debemos especificar

qué tipo de pixel pertenece al contorno, y, como en el capítulo 2, tenemos que

decidir entre 4-conexión y 8-conexión.

4.1. Especificación del contorno

Para simplificar las cosas, en este momento vamos a colorear de negro todos los

pixels de la imagen que no sean blancos. Al fin y al cabo, para hallar el contorno

de la mano no hace falta distinguir entre regiones correspondientes al fondo y a

agujeros en la mano. Podemos dar varias definiciones de qué pixel pertenece al

contorno. En concreto, puede ser un pixel blanco que tiene al menos un 4-vecino

negro, un pixel blanco con al menos un 8-vecino negro, un pixel negro con un 4-

36 Capítulo 4 Obtención del contorno

vecino blanco, y un pixel negro con un 8-vecino blanco. Qué definición escojamos

es cuestión en gran parte de gusto. En este proyecto se considera que un pixel es de

contorno si es blanco y tiene un 8-vecino negro. Una consecuencia de esta elección

es que el contorno forma una región 4-conexa. Si hubiéramos dicho que un pixel

de contorno debe tener un 4-vecino negro, el contorno sería una región 8-conexa.

4.2. Algoritmos funcionales y mutación

Hasta ahora hemos evitado el tema de dónde se ejecutan las operaciones sobre

imágenes. Una imagen en el ordenador ocupa una determinada zona de la memo-

ria, en la que están almacenados los pixels que la forman. ¿Sobre qué memoria

ejecutamos nuestros algoritmos? Es, decir, si hay que cambiar algo en nuestra ima-

gen, ¿podemos cambiarlo sobre el espacio de memoria ocupado por la imagen? La

respuesta es que no siempre es posible.

Pensemos en nuestro problema de obtener el contorno de una mano. En princi-

pio, esto parece fácil: sólo hay que recorrer la imagen y pintar de negro cada pixel

blanco que no tenga vecinos negros. Así, al acabar, sólo los pixels de contorno

quedan blancos. En la figura 4.1 vemos que esto puede dar problemas.

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 4.1 Ejemplo de mutación.

Una vez que hemos borrado el primer pixel de la imagen, la hemos mutado, y

la imagen modificada tiene una frontera distinta. En particular, los vecinos de este

pixel modificado forman ahora parte de la frontera.

Este es un ejemplo de los peligros de modificar los objetos que maneja un

procedimiento. ¿Como evitamos esto? Una solución consiste en hacer una copia de

la imagen original en otra zona de memoria, y operar sobre ella. Observamos que

un pixel debe ser borrado en la imagen original, y borramos su homólogo en la otra

zona de memoria. Así, la imagen original no es modificada, y la imagen resultado

queda almacenada en una zona de memoria distinta. Esta idea es la principal de la

programación funcional [1], que pretende evitar la mutación de objetos.

Tenemos otra opción: cuando encontramos un pixel blanco en la imagen que

esté rodeado de pixels blancos, lo pintamos de gris sobre la imagen original. Al no

4.3 Algoritmos de obtención de contorno 37

pintarlo de negro, sus vecinos se van a comportar correctamente. Al final, sólo los

pixels de frontera quedan blancos.

Vamos a usar un enfoque parecido a éste. Vamos a recorrer la imagen y pintar

de gris los pixels de frontera. Las ventajas de usar esta estrategia quedan claras

también en el capítulo 3.

4.3. Algoritmos de obtención de contorno

Hemos visto que vamos a colorear de gris los pixels del contorno y vamos a

dejar el resto igual. Necesitamos una lista con los pixels del contorno recorridos de

forma continua para poder estudiar la curvatura. Sabemos también que el contorno

de la mano formará una región 4-conexa, o más bien, varias curvas cerradas 4-

conexas, ya que puede que haya agujeros en la mano. Como en el caso de el llenado

de regiones, nos vamos a encontrar con más problemas de los previstos.

4.3.1. Algoritmo intuitivo

Como nos interesa obtener los pixels de contorno de forma ordenada, el algo-

ritmo más sencillo que podemos pensar es el siguiente: dado un punto inicial del

contorno, lo pintamos de gris y lo almacenamos. Buscamos sus vecinos, y si alguno

es un pixel de contorno, realizamos el mismo proceso recursivamente.

CONTORNO(p, contorno)

colorear p de gris

añadir p a contorno

para cada vecino v de p

si v es punto de contorno

CONTORNO(v, contorno)

Este procedimiento colorea de gris todos los pixels del contorno, pero cuan-

do examinamos la lista contorno que produce, vemos que no es continua, sino

que consta de segmentos continuos inconexos unos con otros. Es decir, el proced-

imiento obtiene los pixels de contorno desordenadamente. ¿Por qué? Lo podemos

entender mejor si modificamos el procedimiento anterior. Si vamos a rodear la ma-

no de forma ordenada, dado un pixel de contorno, sólo hace falta saltar a un vecino

de contorno. El contorno recorrerá un bucle y llegará al pixel inicial por otra direc-

ción.



colorear p de gris

añadir p a contorno

para el primer vecino v de p que sea punto de contorno

CONTORNO(v, contorno)

Este procedimiento da en la lista contorno un segmento continuo, pero ni

mucho menos completo, y no colorea todos los pixels de frontera de la mano. Lo

que ocurre es que por alguna razón, cuando el procedimiento recorre el contorno de

la mano, llega a un callejón sin salida, un punto que no ofrece continuación posible.

Nuestro segundo algoritmo termina aquí. Nuestro primer algoritmo, ya que busca

un camino para todos los vecinos de un pixel de contorno, realizará un retroceso

o backtracking, hasta encontrar un pixel con una continuación practicable. Por eso

nuestro primer algoritmo produce segmentos inconexos.

El problema está en que hay pixels de contorno que quedan “ahogados”, sin

vecinos de contorno, y esto es lo que detiene nuestro recorrido secuencial. En la

figura 4.2 podemos ver un ejemplo.

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 4.2 Callejón sin salida.

Es precisamente en los “pelos” de un pixel o dos de grosor donde se producen

los estrangulamientos, así que la idea que surgió fue la de alisar el contorno de la

mano antes de aplicar los algoritmos. En este proyecto se experimentó con cuatro

formas de alisar el contorno de la mano:

Filtrado previo de la imagen. Como veíamos en el capítulo 2, un filtrado

eficiente requiere uso de FFT.

Erosión: consiste en el borrado de todos los pixels de frontera, con lo cual

eliminamos los molestos “pelos”.

Dilatación: consiste en colorear de blanco los pixels adyacentes a la mano.

Con esto suavizamos los picos de la imagen.

Diversas combinaciones de varias erosiones y dilataciones.


Todos los métodos anteriores tuvieron éxito parcial: conseguían aumentar la

longitud de los segmentos continuos de contorno, pero nunca se podía recorrer la

mano entera de forma continua. Además, las operaciones que realizan son caras,

así que hacía falta otra estrategia.

4.3.2. El contorno visto como un grafo

Al igual que en el capítulo 2, la idea salvadora fue la de ver el contorno de la

mano no como un conjunto de pixels sino como un grafo, en que un enlace entre

dos nodos quiere decir que son vecinos, figura 4.3.

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 4.3 Contorno de la mano visto como un grafo.

De hecho, la idea surgió al tratar de resolver este problema, y fue aplicada más

tarde a los problemas de llenado de regiones. El problema que estamos tratando de

resolver se beneficia mucho más que los anteriores de verlo como un problema de

grafos.

En efecto, si construyéramos un grafo completo del contorno, los “pelos” que

tanto nos estorban se ven sencillamente como fragmentos cortos del grafo que no

nos llevan a ninguna parte. El camino que nos interesa en el grafo es cerrado, llega

al pixel de partida, y seguramente es el más largo que contiene.

Así que parece lógico dividir el problema en dos partes:

A partir de la imagen obtener un grafo equivalente al contorno de la mano.

Elegir como contorno el camino más largo que haya en el grafo.

Este procedimiento para resolver el problema tiene dos pegas:

Consume bastante memoria si en el grafo hay variedad de caminos.

Requiere el manejo de estructuras de datos complejas, lo que siempre es

pesado en C/C++.


La segunda pega hizo que en primer lugar se probase a implementar un pro-

cedimiento para enumerar los caminos de un grafo en lenguaje Scheme.

(define (list-of-paths tree)

(let ((descendants (node-descendants tree)))

(if (null? descendants)

(list (list (node-entry tree)))

(accumulate

append

()

(map (lambda (descendant)

(map (lambda (path)

(cons (node-entry tree) path))

(list-of-paths descendant)))

descendants)))))

En efecto, la ocupación de memoria resultaba alta, y la traducción a C++

parecía torpe. Por suerte, en Cormen et al. [3] hay un excelente algoritmo para

obtener los caminos en un grafo, que no sólo consume poca memoria sino que

tiene fácil traducción a C++. Es una versión fuerte de LLENAR-A-LO-ANCHO, o

más bien, LLENAR-A-LO-ANCHO es una versión simplificada de este algoritmo.

Este algoritmo es una versión completa de “breadth-first-search”, y se diferencia

de LLENAR-A-LO-ANCHO precisamente en que almacena en memoria el camino

seguido para llegar del pixel inicial a cada pixel. Además, no hace falta construir

un grafo antes de poder aplicarlo, podemos aplicarlo directamente sobre la imagen.

De nuevo vamos a usar una cola para almacenar los pixels que descubrimos, pero

en esta ocasión los elementos que saquemos de ella los almacenaremos en una

lista. Para recordar el camino seguido hasta llegar a un pixel, almacenaremos en

cada pixel la dirección de su predecesor, es decir del pixel desde el cual lo hemos

descubierto. Veamos cómo funciona:

Buscamos un punto inicial del contorno, lo coloreamos de gris y lo metemos en

la cola, hasta entonces vacía. A partir de ahora, mientras la cola no esté vacía, hare-

mos lo siguiente: tomamos el primer elemento de cola, y para todos sus vecinos, si

son parte del contorno, los coloreamos de gris, los metemos en cola, y asignamos

el primer elemento de la cola como su predecesor. Después quitamos el elemento

de la cola y lo almacenamos en una lista.

CONTORNO-BREADTH-FIRST


buscar punto p de contorno

color(p) ← gris

predecesor(p) ← nulo

encolar(Q, p)

mientras Q no vacia

q ← primero(Q)

para cada v ∈ Vecinos(q)

si v pertenece al contorno

color(v) ← gris

predecesor(v) ← p

encolar(Q, v)

descolar(Q)

poner q en la lista de puntos de contorno

La figura 4.4 nos muestra cómo funciona.

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 4.4 Contorno con algoritmo “a lo ancho”.

Como vemos, el resultado del algoritmo es una lista con todos los pixels de

frontera. Cada pixel en la lista tiene un puntero a su predecesor, y podemos, dado

un pixel de la lista, ir a su predecesor, y al predecesor de éste, y así sucesivamente,

hasta llegar al punto de inicio del algoritmo. Es decir, en la lista que obtenemos

como resultado podemos extraer fácilmente el camino recorrido hasta llegar a un


pixel. Pero hay todavía una propiedad más interesante: los caminos que encon-

tramos de esta forma son siempre los más cortos entre el pixel inicial y el dado,

como se demuestra en Cormen et al. [3]. Así que podemos ver el problema así.

Encontrado el punto inicial de frontera, construimos la lista de puntos de frontera,

cuyos dos últimos elementos serán los pixels opuestos al inicial. Recorriendo el

camino desde cada uno de los dos hasta el pixel inicial, tenemos dos curvas que

unidas, forman el contorno. Al ser cada una de ellas la más corta desde el pixel

dado hasta el inicial, evitamos los pelos que antes nos molestaban, como vemos en

la figura 4.5.

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 4.5 Recorriendo el camino más corto evitamos callejones sin salida.

Vemos entonces, cuál es la estrategia: aplicar CONTORNO-BREADTH-FIRST a

la imagen para extraer la lista de pixels de frontera. Recorrer el camino desde el

último pixel de la lista hasta el primero, lo que nos da una mitad del contorno.

Recorrer el camino desde el penúltimo pixel de la lista hasta el primero, lo que nos

da la otra mitad del contorno. Formar una lista con la primera mitad del contorno,

y con la segunda invertida. Es decir tendremos la lista siguiente: (último pixel . . .

pixel inicial . . . penúltimo pixel), que da un contorno continuo y completo, como

queríamos.

Podemos ver en la figura 4.6 el contorno resultante en una imagen de prueba.

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 4.6 El pixel inicial es negro. Los pixels blancos sueltos son callejones sin salidaque el algoritmo evita.

Este procedimiento tiene un comportamiento muy bueno, pero un grave prob-

lema: puede ser que el pixel en que iniciemos el recorrido sea parte de una zona


problemática, conectada con la mano por un canal estrecho. En ese caso, las dos

mitades de contorno que hemos hallado antes no se reunirían en el punto inicial, y

tendremos un contorno discontinuo, como podemos ver en la figura 4.7.

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 4.7 Las dos mitades del contorno no casan.

Se podía pensar en formas de evitar este nuevo obstáculo, pero es complicar

más un algoritmo de por sí complicado. Parece que la mejor alternativa es eliminar

las zonas que nos molestan.

4.3.3. Limpieza del contorno

Dado que todos nuestros problemas se deben a que ciertas zonas producen

callejones sin salida podemos pensar en borrar estas zonas, para lo cual debemos

ser capaces, en primer lugar, de caracterizarlas: las zonas que parecen molestarnos

son canales de un pixel o dos de grosor, como vemos en la figura 4.8.

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 4.8 Regiones que producen estrangulamientos de contorno. Los pixels de fronteraestán coloreados.

Anteriormente habíamos intentado erosionar la imagen para regularizar el con-

torno. Erosionar no es más que eliminar los pixels de frontera, y como vemos en

la figura 4.8, esto borraría tanto los “canales” de un pixel de anchura como los de

dos. El único problema es que convierte canales de tres pixels de ancho en canales

de uno, es decir, nos borra las zonas molestas pero introduce otras. Podemos reme-


diar esto si acompañamos la erosión con una dilatación, que consiste en añadir una

nueva capa de pixels alrededor de una región. Con esto, los canales de tres pixels

recobran su grosor original, y los de dos y un pixel no rebrotan, como vemos en la

figura 4.9.

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 4.9 Erosión seguida de dilatación.

La secuencia de una erosión seguida de una dilatación es tan común que tiene

nombre propio, opening. En nuestro caso, no siempre vale, y en particular, en el

caso de que el canal estrecho conecte con una pequeña región blanca, un “opening”

eliminaría el canal estrecho pero no la región blanca, y el contorno de la mano daría

un salto a esa región, rompiendo la continuidad, como vemos en la figura 4.10.

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 4.10 Un “opening” no siempre vale.

Por fin la solución al problema se presentó. Recordemos que al hallar la fronte-

ra hemos coloreado los pixels de contorno de gris, y los hemos almacenado en una

cola. Al estar coloreados de gris, ahogan la conexión entre las regiones blancas pe-

queñas de la figura 4.10 y la región correspondiente a la mano propiamente dicha.

Esto quiere decir que podemos borrar estas regiones blancas indeseadas usando

los algoritmos de llenado del capítulo 2. Podemos ver, una vez hecho esto, que

los pixels que nos molestan son aquellos pixels de frontera que no tienen vecinos

blancos. Simplemente recorremos la cola de pixels de frontera y borramos estos

pixels. Después, pintamos de blanco los pixels de frontera restantes, y podemos ya

recorrer el contorno ordenadamente. Formalizando:

LIMPIAR-CONTORNO(Q) ;;Q es la cola de frontera

borrar regiones blancas ahogadas

para cada p ∈ Q

4.4 Hallando el contorno, por fin 45

si p no tiene vecinos blancos

color(p) ← negro

para cada p ∈ Q

color(p) ← blanco

El procedimiento tiene un comportamiento excelente. Produce regiones que

podemos recorrer de forma continua, es decir, regiones con un contorno con buenas

propiedades. Como parte del proyecto se escribió también un test para verificar que

el contorno sea continuo y que acabe en su punto de inicio. Después de pasar por

LIMPIAR-CONTORNO, todas las imágenes usadas en el proyecto pasaron este test.

Veamos cómo se comporta LIMPIAR-CONTORNO en el caso de la figura ante-

rior:

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 4.11 Acción de LIMPIAR-CONTORNO.

4.4. Hallando el contorno, por fin

La estrategia de limpiar el contorno da resultados excelentes, y en la región

resultante cada pixel de frontera tiene exactamente dos vecinos de frontera, lo cual

es la condición necesaria para que el contorno tenga un comportamiento intuitivo.

Aplicar el primer algoritmo de este capítulo ya da un contorno ordenado y comple-

to, pero por comodidad vamos a manejar una pila explícitamente, al igual que en

el algoritmo de llenado a lo profundo.


colorear p de gris

poner p en la pila

repetir

q ← primer elemento de la pila

buscar un vecino v de q que sea de contorno

colorear v de gris


poner v en la pila

hasta que lleguemos al punto inicial

en este momento la pila contiene el contorno ordenado

La razón de usar una pila tiene que ver con la torpeza de C++ para manejar

listas y recursión.

Cuando el algoritmo concluye, la pila contiene los pixels de contorno de la

mano recorridos en orden. El problema de encontrar el contorno está por fin com-

pletamente resuelto.

Capítulo 5

Procesado del contorno

Ya hemos resuelto el problema de obtener una lista ordenada de los pixels de

frontera de la mano. Ahora nos interesa, a partir de esta lista, contar el número de

dedos extendidos en nuestra imagen. Para ello, estudiaremos la curvatura del con-

torno de la mano. La definición de curvatura que usaremos aquí será una adaptación

de la que usan los libros de geometría diferencial [5].

5.1. Curvatura de arcos continuos

Supongamos una curva dada por su vector de posición, una función vectorial

diferenciable r : I ⊂ R→ R3.

r(t) = (x(t),y(t),z(t))

Cada coordenada es una función diferenciable en el intervalo de definición, I.

Supongamos además que r(t) es regular, es decir, su derivada no es nunca nula,

r′(t) 6= 0 para todo t ∈ I. Podemos hallar la longitud de arco así:

s(t) =∫ t

t0‖r′(t)‖dt

Como r′(t) no se anula, s(t) es biyectiva, y por tanto, podemos hallar t = f (s),

con lo cual, podemos parametrizar la curva en función de su longitud de arco

s, y definirla mediante una función v(s). Esta función tiene la propiedad de que

48 Capítulo 5 Procesado del contorno

‖v′(s)‖ = 1. En efecto,

∫ s

0‖v′(s)‖ds =

∫ t

t0‖r′(t)‖dt = s

Para una curva parametrizada por su longitud de arco, v′(s) se denomina el

vector normal, ya que es tangente a la curva y de módulo unidad. Si hallamos

la derivada del vector normal obtenemos v′′(s), que es perpendicular a v′(s). En

efecto,

‖v′(s)‖= 1

dds

(v′(s) ·v′(s)) = 0

v′(s) ·dds

v′(s) = 0

Se suele definir como curvatura en un punto al módulo de la derivada del vector

normal en ese punto, ‖v′′(s)‖. Esta definición da los resultados esperados, en que la

curvatura es el inverso del radio de la circunferencia que mejor aproxima la curva

en el punto bajo estudio.

Puesto que es el módulo de la derivada del vector normal, que es unitario, la

curvatura mide la velocidad angular del vector normal. Esto es lo que necesitamos

imitar en nuestro caso.

5.2. Nuestra definición de curvatura

En este proyecto no usamos en ningún caso funciones continuas. Hemos visto

en el capítulo anterior cómo obtener una lista ordenada de los pixels de contorno,

y es a partir de esta lista que tenemos que encontrar la curvatura del contorno

de la mano. Resultaría muy complicado encontrar una descripción del contorno

mediante una función parametrizada por longitud de arco, así que la definición de

curvatura vista en la sección anterior no es de utilidad.

Sin embargo, si definimos la curvatura como la velocidad de giro del vector

tangente al contorno, tenemos más posibilidades. Podemos hallar el vector tan-

gente al contorno en un pixel de forma sencilla. Basta restar a las coordenadas del

pixel bajo estudio las coordenadas del pixel anterior en la lista. Usando funciones

trigonométricas inversas podemos hallar el ángulo del vector tangente. La diferen-

cia de ángulos de los vectores tangentes en pixels sucesivos es la velocidad angular

5.2 Nuestra definición de curvatura 49

que queríamos calcular.

En este proyecto, por eficiencia, un pixel se representa mediante un puntero

a un lugar de la memoria que contiene un nivel de gris (o color). Para tener un

manejo sencillo de los pixels en los procedimientos de detección de curvatura,

cambiaremos a una representación del pixel como un número complejo, cuya parte

real es la columna ocupada por el pixel, y cuya parte imaginaria es la fila, siendo

la fila inferior en la imagen la 0.

Entonces, convertimos la lista de pixels a una lista de números complejos. La

diferencia (restar a cada número el anterior) de esta lista es la lista de tangentes al

contorno. Formamos la lista de argumentos de los vectores (números complejos)

tangentes, y su diferencia nos da la lista de curvaturas en cada punto.

Hay sólo un problema con esta definición, y es que debido al proceso de dig-

italización, el contorno es demasiado rugoso, hay aliasing [7], como vemos en la

figura 5.1.

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 5.1 La digitalización arruga el contorno.

Para evitar esto vamos a desechar algunos de los pixels de contorno. De es-

ta forma, perdemos detalle, pero el contorno es más regular, como vemos en la

figura 5.2.

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 5.2 Usamos sólo algunos pixels.

Debemos encontrar un punto medio entre tener un contorno con mucho detalle

pero con falsas rugosidades, y uno más regular y menos fiel (a la imagen digital-

izada). La estrategia seguida en este proyecto es usar sólo un pixel de cada diez


de contorno. Es decir, dada la lista de pixels de contorno, formamos una lista con

cada décimo pixel representado como número complejo. Después formamos las

listas de tangentes, argumentos y curvaturas sin más complicaciones.

5.3. El grafo de curvatura

Después de lo visto en las secciones anteriores estamos ya en condiciones de

examinar el contorno de una mano. Como ejemplo observemos el procesado de

una imagen correspondiente a la letra ‘q’, en las figuras 5.3 y 5.4.

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 5.3 Postura correspondiente a la letra ‘q’.

El recorrido del contorno comienza en su punto más alto, y continúa hacia la

izquierda, en sentido contrario a las agujas del reloj. En la gráfica de curvatura, las

zonas con curvatura positiva corresponden a convexidades, o “giros hacia dentro”,

del contorno, mientras que las zonas con curvatura negativa corresponden a con-

cavidades. Las zonas con curvatura alta (≈ 1,5) indican una esquina o un giro muy

brusco. Las zonas con curvatura nula o muy pequeña son casi rectas.

Podemos ver en la gráfica que entorno a 90 en la escala horizontal (recordar

que estamos observando un pixel de cada diez), hay una zona de curvatura nula.

Esto corresponde a la frontera izquierda de la mano, que debido a que coincide con

el límite de la imagen, es plana. A los lados de esta zona hay picos pronunciados de

curvatura positiva, que se deben a que el contorno de la mano es casi perpendicular

5.3 El grafo de curvatura 51

100

150

200

250

300

350

400

450

0 100 200 300 400 500 600

(a) Puntos de contorno

-2.5

-2

-1.5

-1

-0.5

0

0.5

1

1.5

2

0 50 100 150 200 250

(b) Gráfica de curvatura

Figura 5.4 Análisis de la postura correspondiente a la letra ‘q’.


al límite izquierdo. En la gráfica, a la izquierda de la zona plana hay una zona en

que la curvatura es apreciable y alterna de signo con frecuencia. Esto corresponde

a la zona plana pero rugosa de la parte superior izquierda del contorno. Las zonas

rugosas se van a ver caracterizadas precisamente por una curvatura apreciable y de

signo alternante.

A la derecha de la zona plana hay también alternancia de signos, pero esta vez

la curvatura es pequeña, debido a que el contorno es suave. Los giros muy suaves

que vienen a continuación se muestran en una ligera preponderancia de valores,

o bien positivos (giro hacia dentro) o bien negativos, pero pequeños. Llegados al

nudillo del dedo pulgar vemos cuatro valores consecutivos de curvatura positiva,

rodeados de nulos, y más adelante, en la yema del pulgar, vemos tres valores pos-

itivos de curvatura, seguidos de un pico negativo, correspondiente al giro brusco

en el contorno, donde comienza un nuevo dedo. Después de este giro brusco hay

una zona de curvatura positiva pequeña, debida a la postura flexionada del índice,

seguida de un pico negativo (comienza un nuevo dedo). Hay otros dos giros brus-

cos más, correspondientes a las yemas del medio y anular. Entre los giros bruscos

hay 6 o 7 valores positivos de curvatura, correspondientes a las yemas.

Como vemos, contar el número de picos de curvatura no nos resulta útil. Los

picos no sólo son producidos por los dedos, sino por el “choque” de la mano con

los límites de la imagen, e incluso por grietas debidas a sombra, que no nos intere-

san. Sin embargo, parece que las yemas de dedos producen zonas de 6 o 7 puntos

consecutivos de curvatura positiva, y eso sí es aprovechable.

En las figuras 5.5 y 5.6, correspondientes a la letra ‘ch’, podemos ver cómo

cambia esto para el caso de que haya dedos extendidos.

Las yemas o nudillos de los dedos, al igual que antes, producen zonas de 5 o

6 puntos de curvatura positiva en la gráfica de curvaturas. Pero en esta ocasión,

los dos dedos extendidos dan pixels consecutivos de curvatura positiva, rodeados

de zonas relativamente planas. El tramo intermedio entre los dos dedos extendidos

es, en esta ocasión, más achatado, aunque sigue produciendo una zona de gran cur-

vatura negativa. De nuevo, entorno a 50 en la escala horizontal, la zona de curvatura

nula corresponde al margen izquierdo de la imagen. Los nudillos del meñique y del

anular son esta vez menos claros, y no llegan a producir más de 4 puntos consecu-

tivos con curvatura positiva.

Los dedos, en esta ocasión, están claramente separados, pero no siempre vamos

a tener esta ventaja. Vemos en las figuras 5.7 y 5.8 el caso correspondiente a la letra

‘r’.

5.4 Caracterización de elementos del contorno 53

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 5.5 Postura correspondiente a la letra ‘ch’.

En esta ocasión, los dos dedos extendidos no están separados. Podemos ver

en la gráfica que entre las yemas del índice y el medio hay un pico de curvatura

negativa, correspondiente a un giro brusco entre dedo y dedo, pero no hay una zona

plana apreciable. Aunque sí hay zonas planas a los lados del par de dedos. Como

se puede ver, un dedo extendido no siempre está rodeado de zonas de curvatura

pequeña.

5.4. Caracterización de elementos del contorno

En la sección anterior hemos visto que las zonas más o menos rectas del con-

torno de la manos se caracterizan por que, en la gráfica de curvaturas, producen

valores de curvatura pequeños, y de signo alternante. Si los valores absolutos de

curvatura son pequeños, tenemos una zona recta suave. Si los valores absolutos

de curvatura son mayores, tenemos una zona recta, pero rugosa (o ruidosa). Para

determinar si una zona es recta, entonces, tenemos que examinar varios puntos

consecutivos en la gráfica de curvaturas. En este proyecto se examinan 7 posi-

ciones consecutivas. Tenemos que definir también qué se entiende por “curvatura

pequeña”. En este proyecto se ha usado un umbral de 0.1. Una curvatura con un

valor menor es “pequeña”.

Las yemas de los dedos se han visto distinguidas por que producen valores


150

200

250

300

350

400

450

0 100 200 300 400 500 600 700


-2.5

-2

-1.5

-1

-0.5

0

0.5

1

1.5

2

0 50 100 150 200 250


Figura 5.6 Análisis de la postura correspondiente a la letra ‘ch’.

5.5 Detección de elementos del contorno 55

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 5.7 Postura correspondiente a la letra ‘r’.

consecutivos de curvatura apreciable (mayor que el umbral de 0.1). Puesto que

hemos recorrido el contorno de la mano en sentido contrario a las agujas del reloj,

las yemas, que son salientes, o convexidades, giran también en sentido contrario

a las agujas del reloj. Esto quiere decir que producen curvatura positiva. Es posi-

ble también que entre dos dedos extendidos haya una zona achatada como la de

la figura 5.6. En este caso tendremos varios puntos consecutivos de curvatura neg-

ativa. Los giros producen también valores consecutivos positivos (para giros que

producen convexidad) o negativos, aunque no tantos como las yemas.

Finalmente, las zonas rugosas del contorno no se pueden identificar con ninguno

de los casos anteriores.

5.5. Detección de elementos del contorno

Ahora que hemos caracterizado los elementos del contorno es necesario en-

contrar un método para detectarlos. Puesto que todos los elementos de contorno

se caracterizan por puntos consecutivos de curvatura similar, vamos a recorrer el

grafo de curvatura examinando varios puntos al mismo tiempo; en nuestro caso, 7.

Para cada conjunto de 7 puntos consecutivos, vamos a contar el número de pun-

tos con curvatura positiva, negativa, y nula. Hay que puntualizar que consideramos

la curvatura positiva cuando es mayor que un umbral (en este caso 0.1), negativa


100

150

200

250

300

350

400

0 100 200 300 400 500 600 700


-3

-2.5

-2

-1.5

-1

-0.5

0

0.5

1

1.5

0 50 100 150 200 250


Figura 5.8 Análisis de la postura correspondiente a la letra ‘r’.

5.5 Detección de elementos del contorno 57

cuando es menor que el umbral cambiado de signo, y nula en el resto de los casos.

Vamos a asignar a cada tipo de elemento una letra.

Si en un conjunto de 7 puntos 6 o 7 de ellos tienen:

curvatura positiva tenemos una yema de dedo. Letra c.

curvatura negativa tenemos una zona achatada entre dedos. Letra C.

curvatura nula tenemos una zona recta. Letra s.

Si 4 o 5 tienen:

curvatura positiva tenemos un giro suave “hacia dentro”. Letra g.

curvatura negativa tenemos un giro suave “hacia fuera”. Letra G.

curvatura nula tenemos una zona recta. Letra s.

En cualquier otro caso, tenemos una zona ruidosa de contorno, que denotamos

con la letra n. Vamos a producir una lista con los elementos de contorno denotados

por sus correspondientes letras. Por ejemplo, en el caso de la postura estudiada en

la figura 5.6 obtenemos:

nnnnnnnnnnnnnnnsssnssnnnnnnnnnnnnssssssnnggnnssssssssssss

sssssssnnnnnnssssssssssnnnnnnGnGnnnnnssssssssssssssssssss

sssssssssssssssssggccccgggssssssnnnnnnnnsssssssGGGGnnssss

ssssssssnnnnnnnsngggcccccggsssssssssssssssssnnnnnnnnnnggg

cccggcggnnnnngggcggnnn

En la última linea podemos ver varias cs separadas por dos gs. Las cs consec-

utivas corresponden claramente a la misma yema, pero la siguiente ¿corresponde a

otra? La respuesta es que no tiene sentido tener dos yemas separadas por tan poco

espacio. Para evitar estas separaciones indeseadas, vamos a convertir los puntos

vecinos a una c en cs, es decir, vamos a dilatar las yemas de dedos. Después de

esto, tenemos para el caso anterior:

nnnnnnnnnnnnnnnsssnssnnnnnnnnnnnnssssssnnggnnssssssssssss

sssssssnnnnnnssssssssssnnnnnnGnGnnnnnssssssssssssssssssss

sssssssssssssssssgccccccggssssssnnnnnnnnsssssssGGGGnnssss

ssssssssnnnnnnnsnggcccccccgsssssssssssssssssnnnnnnnnnnggc

cccccccgnnnnnggcccgnnn


Ahora, todas las yemas producen zonas de cs consecutivas. Para contarlas no

tenemos más que contar el número de transiciones de c a una letra distinta. Con esto

ya podemos contar el número de yemas de dedo. En este caso particular, tenemos

4.

Capítulo 6

Extracción de características

En los capítulos anteriores hemos visto cómo segmentar la imagen, aplicar op-

eraciones morfológicas, obtener el contorno de la mano, y extraer de él distintos

elementos. Aún hay algunas características de la mano que podemos calcular de

forma sencilla, como su ángulo de inclinación. En este capítulo describimos to-

das las características de la mano estudiadas en este proyecto, y formalizamos los

métodos usados para calcularlas.

6.1. Área de la mano

En el capítulo 2 vimos varios algoritmos de llenado de regiones. En todos ellos

es fácil contar el número de pixels de la región llenada. En concreto, el algoritmo

usado en este proyecto es:

LLENAR-A-LO-ANCHO(p, gris_inicial, gris_final)

area = 0


encolar(Q, p)

mientras Q no esté vacía

q ← primero(Q)

para cada vecino v de q


color(v) = gris_final

encolar(Q, v)

descolar(Q)

area = area + 1

60 Capítulo 6 Extracción de características

Estamos aprovechando que cada pixel de la región va a ser puesto en cola (y

extraído de la cola) exactamente una vez durante el proceso de llenado. El proced-

imiento presentado aquí (traducido a C++) es el usado en el programa de ordenador

desarrollado en el proyecto.

Como veíamos en el capítulo 2, vamos a suponer que en nuestras imágenes

hay una sola mano, y por tanto, después de la segmentación, y de la eliminación de

ruido, una sola región habrá sido llenada de blanco. La diferencia entre las regiones

blancas que debemos borrar y la mano es que la mano debe tener un área superior

a un umbral, que en este proyecto es 100000 pixels. El número de pixels en esta

región es el área de la mano.

6.2. Número de agujeros

De forma parecida, durante la etapa de segmentación y eliminación de ruido

vamos a eliminar las regiones negras menores de un umbral, en este caso 2000

pixels. De las regiones que sobrevivan, la más grande corresponderá el fondo, y si

hay más regiones negras que sobrevivan, corresponderán a huecos entre los dedos,

o agujeros.

En otras palabras: después de la etapa de segmentación tendremos una región

blanca correspondiente a la mano, y varias regiones en distintos niveles de gris.

Una de estas regiones es el fondo. El resto son agujeros.

Número de agujeros = Número de regiones grises−1

6.3. Perímetro

En el capítulo 5 vimos que era conveniente formar una lista con uno de cada

diez pixels de contorno, representados como números complejos. Gracias a usar

sólo un pixel de cada diez, evitamos el aliasing, y tenemos un contorno más fiel al

original.

Como los pixels están representados como números complejos, es fácil hallar

el perímetro: dada la lista de frontera, hallamos la diferencia de la lista, hallamos

su valor absoluto, y sumamos.

PERIMETRO (lista)

perimetro ← 0

para i ← 1 hasta fin

6.4 Curvosidad 61

v ← lista[i] − lista[i−1]

perimetro ← perimetro + |v|

;; En este punto, perimetro contiene el resultado

6.4. Curvosidad

Este índice, de nombre inventado, mide la proporción de curvatura en el con-

torno. Una curvosidad alta debería indicar que el contorno es muy ondulado, una

curvosidad baja, que el contorno es relativamente poco curvo, como la frontera de

una figura convexa. Por desgracia, como hemos podido ver en el capítulo 5, el ruido

y las sombras en la imagen pueden hacer que zonas rectas de contorno den zonas

de curvatura elevada y alternante en la gráfica de curvaturas.

La curvosidad no es más que la media de los valores absolutos de curvatura

calculados como en el capítulo anterior.

6.5. Número de dedos

El capítulo 5 ha estado dedicado a la cuenta del número de dedos. De forma

resumida, dada la lista de puntos de contorno, formamos la lista de tangentes al

contorno, la lista de argumentos de éstos, y la lista de diferencias de argumentos, o

de curvaturas. Después recorremos los puntos de la lista de curvaturas, y asignamos

a cada uno un carácter que lo identifica como parte de una recta, un giro, o una

yema de un dedo. El número de dedos es el número de agrupaciones de puntos que

pertenecen a una yema.

6.6. Circularidad

La circularidad es una medida muy usada en la clasificación de imágenes. Su

objetivo es indicar cuánto difiere la figura bajo estudio de un círculo. Un círculo

de radio r un perímetro P (circunferencia) de 2πr y un área A de πr2. Esto quiere

decir que para un círculo,

P2 = 4πA

Definiremos entonces la circularidad por

C =P2

4πA


que es 1 en caso de un círculo, y mayor de 1 en cualquier otro caso (el círculo es

la figura que encierra mayor área para un perímetro dado). Puesto que ya hemos

calculado el perímetro y el área de la mano, calcular la circularidad es trivial.

6.7. Ángulo de inclinación

La inclinación de la mano es posiblemente uno de los parámetros de mayor

interés. Pero dado que la mano es una figura bidimensional, ¿cómo calculamos

esta inclinación? La estrategia inicial del proyecto fue ajustar una recta a la mano

por el método de mínimos cuadrados. Es decir, tomamos la mano como una nube

de puntos, y hallamos la recta de regresión que minimiza la suma de los cuadrados

de las diferencias en altura (coordenada y) entre puntos de la nube y puntos de la

recta que tengan igual abscisa (coordenada x). Observar la figura 6.1.

PSfrag replacements

NULO


(x, y)

(x,y)

d d

eje x

eje y

φuφ+ π

2

Figura 6.1 Recta de regresión.

6.7 Ángulo de inclinación 63

Desarrollando obtenemos:

y = mx+n tal que

∑i

[yi−mxi−n]2 es mínimo

∂∂m ∑

i

[yi−mxi−n]2 = 0

∑i

2(yi−mxi−n)(−xi) = 0

∑i

yixi = m∑i

x2i +n∑

i

xi

∂∂n ∑

i

[yi−mxi−n]2 = 0

∑i

2(yi−mxi−n)(−1) = 0

∑i

yi = m∑i

xi +n∑i

1

Para resolver el sistema de ecuaciones

∑i yixi = m∑i x2i +n∑i xi

∑i yi = m∑i xi +n∑i 1(6.1)

es conveniente usar una serie de números muy conocidos en estadística:

las medias

x =∑i xi

∑i 1

y =∑i yi

∑i 1


y los momentos centrales de orden 2

µ20 =∑i

(xi− x)2 (6.2)

µ11 =∑i

(xi− x)(yi− y) (6.3)

µ02 =∑i(yi− y)2 (6.4)

Con estas definiciones, es fácil llegar a la solución del sistema de ecuaciones

( 6.1), como demuestra Papoulis [10]:

m =µ11

µ20

n = y−mx

Puesto que m es la pendiente de la recta de regresión que se ajusta a la mano,

tomamos su arco-tangente para tener el ángulo de inclinación.

Ángulo de inclinación = arctan(m)

Por cierto, en todas las ecuaciones usadas anteriormente hemos supuesto que

el peso de los pixels de la mano era 1, de los demás, 0. En el caso más general,

deberíamos haber multiplicado por el peso, y obtendríamos, por ejemplo:

x =∑i xiF(xi,yi)

∑i F(xi,yi)

pero todos los resultados obtenidos antes seguirían siendo válidos.

Este método tiene serias pegas. La principal es que debido a que minimiza

las diferencias de ordenadas, tiende a dar preferencia a las líneas con orientación

horizontal, cuando a veces es más conveniente una línea de orientación cercana a

la vertical. Vemos un ejemplo en la figura 6.2.

El problema de la estrategia anterior es que toma como distancia entre un punto

y la recta de regresión la longitud del segmento vertical entre el punto y la recta

(figura 6.1). Para regiones de orientación más o menos horizontal esto es adecuado,

pero si la región bajo estudio tiene una pendiente apreciable, no funciona bien.

Nos interesa, más bien, definir la distancia entre un punto y una recta como la

longitud del segmento que une el punto a la recta y es perpendicular a ella (figu-

ra 6.3). La recta tal que la suma de los cuadrados de las distancias de los puntos a

6.7 Ángulo de inclinación 65

PSfrag replacements

NULO

. . .

Recta producida pormínimos cuadrados

Esta recta es mejor

(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 6.2 El método de mínimos cuadrados no es adecuado.

ella sea mínima es la que llamaremos eje de la región.

PSfrag replacements

NULO


(x, y)

(x,y)dd

eje x

eje y

φuφ+ π

2

Figura 6.3 Una distancia distinta.

Concretando, buscamos una recta r tal que

D2(r) = ∑i

d2((xi,yi),r)

sea mínimo. Esto recuerda a la definición en física del momento de inercia de un

sólido respecto de un eje. De hecho, es la misma, o sea que llamaremos I(r) a

D2(r). Reformulamos el problema: se trata de encontrar una recta respecto de la

cual el momento de inercia de la región sea mínimo. Llamaremos a esta recta el

eje de la región. Es un hecho conocido [6] que dado un haz de rectas paralelas,

un objeto tiene el momento de inercia menor respecto de la recta que pasa por su

centro de gravedad. Sabemos, entonces, que el eje de la región pasa por su centro

de gravedad, cuyas coordenadas son (x, y), y sólo necesitamos saber el ángulo del

eje. Vamos a hallar el momento de inercia como función de este ángulo.

Podemos calcular la distancia de un punto a una recta fácilmente, sin más que

hallar el producto escalar de un vector unitario normal a la recta con la diferencia


entre el punto dado y un punto sobre la recta (figura 6.4).PSfrag replacements

NULO


(x, y)

(x,y)

d

deje xeje y

φ

uφ+ π2

Figura 6.4 Distancia entre punto y recta.

Esto es,

d((xi,yi),r) = uφ+ π2· (x− x,y− y)

donde uφ+ π2

es perpendicular a la recta r. Calculamos, entonces, el momento de

inercia de la región respecto de una recta que pasa por su centro de masas, (x, y),

con ángulo φ,

I(φ) = ∑i

(uφ+ π2· (xi− x,yi− y))2 =

∑i

(cos(φ+ π2 )(xi− x)+ sin(φ+ π

2 )(yi− y))2 =

∑i

(cos(φ)(yi− y)− sin(φ)(xi− x))2 =

∑i

cos2(φ)(yi− y)2 + sin2(φ)(xi− x)2−2sin(φ)cos(φ)(xi− x)(yi− y) =

I(φ) = µ02 cos2 φ+µ20 sin2 φ−µ11 sin2φ

donde µ20, µ11, µ02 son los momentos centrales de segundo orden definidos en

( 6.2)( 6.3)( 6.4), página 64. La función

I(φ) = µ02 cos2 φ+µ20 sin2 φ−µ11 sin2φ (6.5)

es muy interesante. Nos muestra que el momento de inercia de la región respecto

de un eje varía sinusoidalmente con el ángulo del eje. En concreto, es una sinu-

soide de periodo π. Esto quiere decir que tiene, a lo largo del intervalo [−π,π],

6.8 Momentos principal y secundario 67

dos máximos, en ángulos diferenciados en π (es decir, en la misma dirección y

sentido opuesto), y dos mínimos, separados π2 de los máximos. Esto quiere decir

que la región tiene un eje respecto del cual su momento de inercia es mínimo, que

llamaremos eje principal, y un eje respecto del cual su momento de inercia es máx-

imo, que llamaremos eje secundario. Estos dos ejes son siempre perpendiculares,

no importa de qué región se trate. Así mismo, llamaremos momento principal al

momento de inercia respecto del eje principal, y momento secundario al momento

respecto del eje secundario.

Para hallar el ángulo de inclinación de los dos ejes, derivamos la función I(φ)

respecto de φ. Usando la fórmula 6.5 obtenemos:

∂I∂φ

= (µ20−µ02)sin2φ−2µ11 cos 2φ (6.6)

que se anula para

tan2φ =2µ11

µ20−µ02(6.7)

Esta ecuación tiene cuatro soluciones en [−π,π]. Vamos a usar sólo las que se

encuentran en [− π2 ,

π2 ], que son un máximo y un mínimo separados π

2 . Para saber

cuál es cuál, simplemente sustituimos en la fórmula 6.5 que da el momento de

inercia,. El ángulo que da el momento de inercia mínimo es el ángulo de inclinación

de la mano.

6.8. Momentos principal y secundario

Tal y como hemos visto en la sección anterior, el momento de inercia de la

región que corresponde a la mano tiene dos direcciones privilegiadas, una para

la que es máximo y otra para la que es mínimo. El momento de inercia en sí es

una magnitud interesante: nos da una idea de la separación entre los pixels de la

región y el eje. Una región muy estrecha tendrá, respecto de su eje longitudinal, un

momento de inercia muy pequeño. Una región más achatada tendrá un momento

de inercia mayor (figura 6.5).

Puesto que hemos calculado los ángulos de los ejes principal y secundario,

calcular los correspondientes momentos es fácil.


PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 6.5 Momentos de inercia pequeño y grande.

6.9. Relación de aspecto

Una de las magnitudes más usadas en los libros de Visión Artificial para clasi-

ficar objetos es la relación de aspecto, que es el cociente entre la “altura” y la

“anchura” del objeto. Qué entendamos por altura y anchura del objeto está sujeto

a variación, pero la estrategia más comúnmente utilizada es obtener el rectángulo

abarcante mínimo (minimum enclosing rectangle), es decir, el rectángulo más pe-

queño dentro del cual cabe el objeto. Por supuesto, esto requiere alguna estrategia

para calcular el ángulo de inclinación del objeto, como hemos visto antes. Pero

ya que hemos calculado los momentos de inercia principal y secundario, es intere-

sante usarlos. El momento de inercia de un objeto respecto de un eje es tanto mayor

cuanto más ancho es respecto del eje. Por ejemplo, el momento de inercia de una

varilla de longitud l y masa m respecto de un eje perpendicular a ella que pasa por

su centro es 112 ml2 (ver [6]).

Entonces, usaremos como relación de aspecto del objeto el cociente entre sus

momentos de inercia principal y secundario. Puesto que el momento de inercia

parece ser proporcional al cuadrado de la anchura del objeto, esta relación de as-

pecto será aproximadamente el cuadrado de la relación de aspecto tradicional.1

6.10. Cuestiones de implementación

En las secciones anteriores hemos visto que los cálculos eran muy sencillos una

vez disponemos de x, y, µ20, µ11, µ02. Podemos calcular todas estas magnitudes

1Para obtener una relación de aspecto más ortodoxa, podríamos calcular las dimensiones de unrectángulo de iguales momentos principal y secundario que nuestro objeto.

6.11 El programa clasificador 69

con un solo pase sobre la imagen. En concreto:

x =∑i xi

∑i 1

y =∑i yi

∑i 1

µ20 = ∑i

x2i − x2 ∑

i

1

µ11 = ∑i

xiyi− xy∑i

1

µ02 = ∑i

y2i − y2 ∑

i1

lo que quiere decir, que a medida que recorremos la imagen, podemos formar las

sumas ∑i 1 ∑i xi ∑i yi ∑i x2i ∑i xiyi ∑i y2

i , donde xi,yi se obtienen en función de la

fila y columna del pixel que estamos examinando. A partir de estas sumas tenemos

todas las magnitudes que nos interesan.

6.11. El programa clasificador

Ahora vemos la secuencia general de operaciones seguida para extraer las car-

acterísticas.

1. Aplicar un umbral a la imagen. (capítulo 2)

2. Segmentar la imagen. (capítulo 2)

3. Calcular el área de la mano. (capítulo 2)

4. Calcular el número de agujeros. (capítulo 2)

5. Calcular los estadísticos (medias, momentos de segundo orden). (capítulo 6)

6. Hallar la pendiente de la imagen, sus momentos de inercia, y su relación de

aspecto. (capítulo 6)

7. Hallar frontera desordenadamente y colorearla de gris. (capítulo 4)

8. Borrar regiones blancas ahogadas por la frontera. (capítulo 4)

9. Borrar los pixels de frontera que no tienen vecinos blancos. (capítulo 4)

10. Hallar la frontera ordenada. (capítulo 4)


11. Formar la lista de uno de cada diez pixels de frontera representados como

números complejos. (capítulo 5)

12. Calcular perímetro y circularidad. (capítulo 5)

13. Hallar lista de curvaturas. (capítulo 5)

14. Calcular curvosidad y número de dedos. (capítulo 5)

Capítulo 7

Resultados

En este capítulo mostramos los vectores de características obtenidos para las

distintas manos examinadas en el proyecto. En total son 87 imágenes, correspondi-

entes a 23 letras y 4 manos diferentes. Estas imágenes fueron obtenidas por Marcos

Pineda como parte de su Proyecto de fin de carrera [9]. Las fotografió usando dos

cámaras, y produjo ficheros de imagen en formato TIFF, en escala de grises con 8

bits por pixel (256 niveles de gris), y 768× 576 pixels. Los nombres de fichero usa-

dos están compuestos por una primera letra (o letras en el caso de ‘ch’) que indica a

qué letra corresponde la imagen, seguida de un número usado para distinguir entre

distintas manos en igual postura, y finalmente la extensión .tif. Así, por ejemplo

a20000.tif y a30000.tif contienen dos manos en postura correspondiente a la

letra ‘a’.

En las gráficas, tenemos en abscisas la letra a que corresponde cada mano ex-

aminada, y en ordenadas la magnitud relevante para cada medida. No se ha hecho

esfuerzo en distinguir, en las gráficas, entre las manos de distintas personas, por lo

que hay varios puntos en cada abscisa representados de la misma forma.

Hay que decir que 4 muestras de cada postura son pocas para tener parámetros

estadísticos fiables. Para hacer estimaciones y medidas consistentes será necesario

añadir imágenes de las manos de muchas personas al banco de pruebas. Aún así,

podemos discernir ya algunas tendencias que seguramente serían confirmadas con

un estudio de mayores dimensiones.

Por completitud, he aquí una muestra de las posturas del alfabeto dactilológico

español sobre las que se centra el estudio:

72 Capítulo 7 Resultados

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 7.1 El alfabeto dactilológico español (1).

73

PSfrag replacements

NULO


(x, y)(x,y)

dd

eje xeje y

φuφ+ π

2

Figura 7.2 El alfabeto dactilológico español (2).


Fichero Área Perímetro Circularidad Curvosidad Agujeros

a20000.tif 114497 1704.04 2.01816 0.259001 0a30000.tif 83180 1388.31 1.84392 0.241964 0a40000.tif 76466 1327.27 1.83332 0.241053 0aa0000.tif 107402 1707.4 2.15998 0.279535 0b20000.tif 117539 1822.86 2.24966 0.261673 0b30000.tif 117229 1935.23 2.54226 0.221085 0b40000.tif 108202 2231.28 3.66154 0.23939 0bb0000.tif 148088 1979.59 2.10582 0.245506 0c20000.tif 103624 1942.3 2.89709 0.27673 0c20001.tif 103629 1873.96 2.69668 0.245848 0c30000.tif 71159 1887.24 3.98305 0.276442 0c40000.tif 79170 1810.71 3.29556 0.225152 0cc0000.tif 65023 1862.73 4.24641 0.287914 0ch20000.tif 108431 2473.08 4.48861 0.240521 0ch40000.tif 84336 2004.85 3.79264 0.235293 0d20000.tif 87030 1609.22 2.36783 0.328815 1d30000.tif 78648 1733.46 3.04039 0.313787 1d40000.tif 79936 1741.74 3.02006 0.265452 1dd0000.tif 91689 1799.8 2.8114 0.272187 1e20000.tif 94708 1955.55 3.21322 0.368906 0e30000.tif 62430 1664.69 3.53235 0.31945 0e40000.tif 68074 1358.74 2.15816 0.237111 0e410000.tif 62430 1664.69 3.53235 0.31945 0ee0000.tif 71033 1696.54 3.22446 0.282759 0f20000.tif 72089 1740.97 3.34584 0.274707 0f30000.tif 59562 1476.63 2.91315 0.296884 0f40000.tif 64808 1509.37 2.79739 0.302785 0g20000.tif 93485 1649.69 2.31661 0.262854 0g30000.tif 85284 1629.55 2.47776 0.222516 0g40000.tif 68074 1358.74 2.15816 0.237111 0h20000.tif 122315 2417.82 3.80328 0.238671 0h30000.tif 84299 1632.82 2.51676 0.281972 0h40000.tif 82705 1398.91 1.88294 0.220813 0hh0000.tif 105786 2029.7 3.09903 0.261926 0

Cuadro 7.1 Tabla de resultados. Primer grupo de características (1).

75


i20000.tif 101290 1574.82 1.94842 0.234135 0i30000.tif 85519 1471.95 2.01611 0.207479 0i40000.tif 66195 1259.6 1.90735 0.266923 0k20000.tif 80738 1467.13 2.12154 0.305958 1k30000.tif 67677 1465.76 2.52624 0.358405 1k40000.tif 70308 1344.81 2.04695 0.306186 1kk0000.tif 69833 1693.33 3.26747 0.377422 1l20000.tif 89141 1509.19 2.03329 0.282917 0l30000.tif 66122 1423.36 2.43821 0.253126 0l40000.tif 72665 1344.67 1.98015 0.251547 0m20000.tif 113200 1875.21 2.47198 0.234513 0m30000.tif 111161 1692.1 2.04971 0.259409 0m40000.tif 111161 1692.1 2.04971 0.259409 0n20000.tif 102598 1744.74 2.36109 0.302023 0n30000.tif 84387 1442.47 1.96214 0.275277 0n40000.tif 84387 1442.47 1.96214 0.275277 0n410000.tif 84387 1442.47 1.96214 0.275277 0nn0000.tif 65168 1312.91 2.10488 0.370012 0nn0001.tif 65197 1313.09 2.10452 0.374464 0o20000.tif 90436 1674.35 2.46684 0.345848 1o30000.tif 66190 1393.9 2.33594 0.263474 1o40000.tif 71897 1465.61 2.37747 0.32095 1oo0000.tif 85069 1953.78 3.57083 0.396523 1p20000.tif 98656 1637.1 2.16181 0.22518 0p30000.tif 86318 1355.31 1.69341 0.232229 0p40000.tif 83150 1670 2.66908 0.281689 0q20000.tif 108921 1907.44 2.65815 0.359582 0q30000.tif 61809 1605.65 3.31925 0.343131 0q40000.tif 66912 1955.79 4.54916 0.378391 1r20000.tif 106588 2003.02 2.99537 0.248894 1r30000.tif 84085 1981 3.714 0.222245 0r40000.tif 85461 1996.89 3.71305 0.195501 0s20000.tif 82151 1491.75 2.15561 0.275284 1s20001.tif 82157 1541.37 2.30122 0.345831 1s30000.tif 67533 1474.57 2.56216 0.299983 1




s40000.tif 73745 1549.17 2.58973 0.264863 0t20000.tif 78485 1969.7 3.9337 0.402413 0t30000.tif 55894 1395.25 2.77161 0.273717 0t40000.tif 62092 1510.5 2.92414 0.275899 0t410000.tif 55894 1395.25 2.77161 0.273717 0tt0000.tif 57332 1760.34 4.30116 0.373229 0u20000.tif 88955 1907.58 3.25526 0.270443 0u30000.tif 67669 1619.61 3.08477 0.181782 0u40000.tif 77546 1809.57 3.36032 0.198603 0x20000.tif 100931 2120.1 3.54386 0.264832 1x30000.tif 85284 1629.55 2.47776 0.222516 0x310000.tif 85284 1629.55 2.47776 0.222516 0x40000.tif 77462 1624.33 2.7105 0.23784 0x410000.tif 85284 1629.55 2.47776 0.222516 0xx0000.tif 78324 1559.69 2.47155 0.229266 0y20000.tif 85261 1415.05 1.86888 0.397771 0y30000.tif 82542 1438.77 1.99571 0.26483 0y40000.tif 96839 1623.48 2.16589 0.211695 0


77

Fichero Dedos Pendiente (rad.)Relación

de aspectoMomentoPrincipal

a20000.tif 3 0.0503233 6.36053 4.61906e+08a30000.tif 3 -0.00283665 5.1631 2.68595e+08a40000.tif 4 -0.0402411 4.59212 2.3809e+08aa0000.tif 4 -0.412405 6.23208 4.06571e+08b20000.tif 3 -0.289953 6.79435 4.4835e+08b30000.tif 5 -0.0189213 4.93551 5.14004e+08b40000.tif 5 0.00270697 5.30008 4.24111e+08bb0000.tif 4 -0.317411 6.26682 7.20892e+08c20000.tif 2 -0.12671 3.64759 5.9078e+08c20001.tif 0 -0.12653 3.64297 5.91133e+08c30000.tif 2 -0.233827 3.69855 3.68611e+08c40000.tif 0 -0.232355 4.40853 3.48637e+08cc0000.tif 2 0.0280679 2.81777 3.76976e+08ch20000.tif 4 -0.0974764 7.34046 4.05839e+08ch40000.tif 4 -0.0414594 7.6678 2.37078e+08d20000.tif 3 -1.45692 3.65525 3.98748e+08d30000.tif 3 -0.287792 6.20566 2.69359e+08d40000.tif 3 -0.138488 6.2946 2.64154e+08dd0000.tif 1 0.532317 6.10731 3.82978e+08e20000.tif 2 -1.06146 3.19675 6.05618e+08e30000.tif 2 -0.85062 2.7625 3.42478e+08e40000.tif 2 0.0264569 6.33872 1.66629e+08e410000.tif 2 -0.85062 2.7625 3.42478e+08ee0000.tif 1 -0.722803 2.92846 3.7152e+08f20000.tif 2 -1.50678 4.85436 2.56721e+08f30000.tif 3 -1.48846 7.44779 1.24462e+08f40000.tif 1 1.52204 5.41595 1.68747e+08g20000.tif 4 -0.127598 5.78154 3.35254e+08g30000.tif 3 -0.180863 4.51954 3.15477e+08g40000.tif 2 0.0264569 6.33872 1.66629e+08h20000.tif 4 -0.412422 5.58221 5.54353e+08h30000.tif 3 1.55537 4.1064 3.10841e+08h40000.tif 3 -1.30358 4.37874 2.82912e+08hh0000.tif 5 -1.1303 3.97088 5.07335e+08

Cuadro 7.4 Tabla de resultados. Segundo grupo de características (1).




i20000.tif 2 1.43771 1.32198 8.33738e+08i30000.tif 2 -1.50636 4.18494 3.33366e+08i40000.tif 2 -1.3276 3.18041 2.22313e+08k20000.tif 3 -1.40649 2.55576 3.98869e+08k30000.tif 2 -1.357 3.47606 2.61787e+08k40000.tif 1 1.44367 4.26881 2.35824e+08kk0000.tif 3 1.51508 2.99534 3.05113e+08l20000.tif 4 1.32282 2.71336 4.55035e+08l30000.tif 4 1.29179 3.09459 2.47783e+08l40000.tif 1 -1.46544 2.08752 3.33217e+08m20000.tif 5 1.52024 2.91922 6.41687e+08m30000.tif 5 -1.54182 3.66927 5.47567e+08m40000.tif 5 -1.54182 3.66927 5.47567e+08n20000.tif 4 -1.50976 2.60183 5.79058e+08n30000.tif 3 -1.38826 4.97404 2.7522e+08n40000.tif 3 -1.38826 4.97404 2.7522e+08n410000.tif 3 -1.38826 4.97404 2.7522e+08nn0000.tif 2 -1.42878 5.76951 1.58705e+08nn0001.tif 3 -1.4302 5.75872 1.59167e+08o20000.tif 2 -1.44666 2.19182 5.91253e+08o30000.tif 2 -1.41885 4.69121 2.19392e+08o40000.tif 3 1.54928 3.81666 2.89979e+08oo0000.tif 3 1.29399 3.32628 4.55127e+08p20000.tif 3 1.46626 5.02395 3.78148e+08p30000.tif 3 1.52244 5.29302 2.67802e+08p40000.tif 4 1.5274 6.00076 2.36714e+08q20000.tif 3 0.0275684 4.90063 5.09132e+08q30000.tif 3 -1.50592 5.30054 1.9375e+08q40000.tif 2 -1.25503 8.37595 1.62594e+08r20000.tif 2 -0.138703 7.81976 3.73501e+08r30000.tif 4 -0.165632 6.8409 2.63047e+08r40000.tif 3 0.0222373 7.24288 2.53322e+08s20000.tif 2 -1.44073 3.33584 3.4813e+08s20001.tif 2 -1.44212 3.33275 3.47934e+08s30000.tif 2 -1.30656 3.25571 2.64746e+08


79



s40000.tif 3 -1.38948 4.14883 2.37421e+08t20000.tif 1 -1.47429 4.74925 2.71992e+08t30000.tif 2 -1.36959 5.38599 1.35921e+08t40000.tif 3 -1.53347 5.9838 1.54053e+08t410000.tif 2 -1.36959 5.38599 1.35921e+08tt0000.tif 3 -1.38381 3.2218 2.26625e+08u20000.tif 4 1.46706 4.1098 3.77278e+08u30000.tif 3 1.38909 4.42085 2.28863e+08u40000.tif 4 -1.46859 4.85167 2.66775e+08x20000.tif 3 -0.143574 5.85099 3.97794e+08x30000.tif 3 -0.180863 4.51954 3.15477e+08x310000.tif 3 -0.180863 4.51954 3.15477e+08x40000.tif 4 -0.0643013 5.75055 2.32011e+08x410000.tif 3 -0.180863 4.51954 3.15477e+08xx0000.tif 3 -0.186061 6.56948 2.26192e+08y20000.tif 3 1.41793 2.35767 4.21072e+08y30000.tif 3 -1.54767 4.17265 3.12549e+08y40000.tif 4 1.46766 4.53261 3.86448e+08



7.1. Área

50000

60000

70000

80000

90000

100000

110000

120000

130000

140000

150000

a b c d e f g h i k l m n o p q r s t u x y ch

Figura 7.3 Área de la mano en número de pixels.

El área de por sí no es un buen parámetro para la clasificación debido a que dis-

tintas personas tienen manos de distinto tamaño, y de que incluso para las manos

de una sola persona, representando la misma letra, puede haber variaciones sus-

tanciales en el área mostrada en imagen. Aún así, podemos ver en la gráfica que

para algunas letras, el área es consistentemente grande; por ejemplo, las letras b,

m, ch. Para otras el área es consistentemente pequeña, como f, k, s, t. El umbral

entre “pequeño” y “grande” estaría entorno a 90000 pixels. Los resultados obte-

nidos son lógicos: las letras de área pequeña corresponden precisamente a manos

que son vistas de lado o tienen agujeros, mientras que las letras de área grande

corresponden a manos totalmente extendidas. Aunque el área no deba usarse por

sí sola como parámetro de clasificación, es indispensable calcularla, precisamente

para tener una idea de la escala de la mano. Podemos esperar que el área sea propor-

cional al cuadrado de las dimensiones de la mano, así que para conseguir resultados

normalizados, dividiremos por el área o su raíz cuadrada.

7.2 Perímetro 81

7.2. Perímetro

1200

1400

1600

1800

2000

2200

2400

2600


Figura 7.4 Perímetro de la mano en unidades naturales (unidad de longitud = diámetrode un pixel).

La misma observación que para el área es pertinente en este caso: el perímetro

medido puede depender, para una misma letra, de la persona cuya mano anal-

izamos, de cada fotografía que tomamos, de variaciones en distancia entre la mano

y la cámara. Por eso no debemos usar esta medida por sí sola, a menos que realice-

mos medidas sobre imágenes normalizadas en tamaño.

Aún así, podemos ver algunas letras con perímetro consistentemente grande,

como b, c, r, y otras con perímetro consistentemente pequeño, como a, f, i, k, s.

La separación entre unas y otras estaría entorno a 1800.


7.3. Circularidad

1.5

2

2.5

3

3.5

4

4.5

5


Figura 7.5 Circularidad de la mano.

Esta es la primera medida robusta, en teoría independiente de la distancia entre

cámara y mano, y del tamaño de la mano. Recordemos que la circularidad es tanto

más próxima a 1 cuanto más circular es el objeto; para objetos poco regulares, la

circularidad toma valores grandes.

Podemos observar en la gráfica dos grupos: letras de baja circularidad (formas

regulares) como a, g, i, l, m, n, p, s, y, frente a letras de circularidad alta, como f,

q, r, t, u, ch.

El umbral estaría en 2.6, aproximadamente. En algunos casos los resultados no

son intuitivos, pero por lo general, las manos con circularidad alta poseen uno o

dos dedos extendidos, y la palma de la mano encogida.

7.4 Curvosidad 83

7.4. Curvosidad

0.15

0.2

0.25

0.3

0.35

0.4

0.45


Figura 7.6 Curvosidad de la mano.

Esta magnitud es un índice de lo curvo que es el contorno. Valores altos de-

berían indicar un contorno zigzagueante, valores bajos, un contorno regular. Puesto

que se calcula dividiendo la suma de valores absolutos de curvatura entre el perímetro

de la mano, esta medida debe ser también independiente del tamaño de la mano y

de la distancia a la cámara.

Fijemos un umbral de 0.28. Manos con un valor superior de curvosidad suelen

ser: d, e, f, k, n, o, q, s, t. Manos con curvosidad inferior: b, g, h, i, m, p, r, u, x,

ch.

Los resultados son esperados, en que las manos de baja curvosidad son aquellas

en que hay zonas casi rectas, como dedos totalmente extendidos.


7.5. Agujeros

-0.5

0

0.5

1

1.5


Figura 7.7 Número de agujeros de la mano.

Los resultados aquí son los esperados. El programa detecta correctamente las

cuatro posturas de la mano que poseen agujeros: d, k, o, s. Pero por desgracia, de-

tecta también falsos agujeros en las letras r, t, x. En realidad, estos “agujeros” son

zonas de sombra más grandes que el umbral que usamos para reconocer agujeros.

Modificar el umbral no resuelve el problema, porque los falsos agujeros son a veces

mayores que los reales. Hay, sin embargo, dos soluciones claras a este problema:

una es usar una iluminación uniforme al fotografiar la mano, con lo que se podría

evitar casi por completo las sombras. Otra solución, más complicada, sería usar una

técnica de aplicación de umbral a la imagen original más sofisticada. Por ejemp-

lo, usando una técnica adaptativa (adaptative thresholding), se usaría un umbral

distinto para distintas zonas de la imagen, y las sombras se verían disminuídas.

7.6 Dedos 85

7.6. Dedos

-1

0

1

2

3

4

5

6


Figura 7.8 Número de dedos de la mano.

Podemos ver que el número de dedos (yemas de dedo), no es, después de todo,

muy útil. Una misma postura de la mano puede presentar en distintas ocasiones

distinto número de dedos. Podemos, sin embargo, usar una pequeña separación:

manos con 4 o 5 dedos son a, b, g, h, l, m, n, p, r, u, x, y, ch. Con 0 o 1 dedos, c, d,

e, f, k, l, t. Estos resultados no son muy intuitivos si nos fijamos en las posturas rep-

resentadas, y probablemente se vean modificados si usamos un banco de pruebas

mayor. Sin embargo, la técnica de cuenta de dedos usada era muy cruda; una téc-

nica más elaborada seguramente pudiera emplear mejor la abundante información

que se encuentra en la gráfica de curvatura.


7.7. Ángulo de inclinación

-2

-1.5

-1

-0.5

0

0.5

1

1.5

2


Figura 7.9 Ángulo de inclinación de la mano en radianes.

Esta es la magnitud que nos da la separación más clara entre manos, y es,

además independiente de la escala. Podemos ver claramente que para algunas

manos, la inclinación esta cerca de 1.5 o -1.5 ( π2 ) que corresponde a una postu-

ra vertical, mientras que para otras es casi 0, por lo que la postura es horizontal.

Para d, h, la inclinación es intermedia.

Posturas horizontales: a, b, c, ch, g, q, r, x.

Posturas verticales: d, f, i, k, l, m, n, o, p, s, t, u, y.

Posturas inclinadas: e, h

7.8 Relación de aspecto 87

7.8. Relación de aspecto

1

2

3

4

5

6

7

8

9


Figura 7.10 Relación de aspecto de la mano.

Es el cociente entre los momentos de inercia principal y secundario. Independi-

ente de la escala. Esta magnitud nos da una idea tanto de si la postura es “alargada”,

como de si tiene un eje marcado y claro. Manos con relación de aspecto alta (>4) :

a, b, ch, f, g, h, p, q, r, t, u, x. Con relación de aspecto baja: c, e, i, k, l, o, y.

Los resultados son muy intuitivos. Las manos más alargadas tienen mayor

relación de aspecto, las manos en postura más encogida o circular, relaciones de

aspecto menores.


7.9. Momento principal

1e+08

2e+08

3e+08

4e+08

5e+08

6e+08

7e+08

8e+08

9e+08


Figura 7.11 Momento de inercia principal de la mano.

Es pequeño para regiones “pegadas” al eje: c, ch, d, f, g, i, p, r, s, t, u, x.

Esta medida aporta poco sobre los resultados de la relación de aspecto. En efecto,

una relación de aspecto alta indica que la mano es mucho más larga que ancha, y

esto es prácticamente lo mismo que decir que la mano es estrecha, o pegada al eje.

Podemos ver que las manos con momento principal pequeño son casi las mismas

que tienen una relación de aspecto grande.

7.10 Momento secundario 89

7.10. Momento secundario

5e+08

1e+09

1.5e+09

2e+09

2.5e+09

3e+09

3.5e+09

4e+09

4.5e+09

5e+09


Figura 7.12 Momento de inercia secundario de la mano.

Al igual que el momento principal, esta medida aporta poco sobre los resulta-

dos de la relación de aspecto. Un valor bajo del momento secundario indica manos

“chatas”: e, k, l, s. Esto es casi lo mismo que decir que la relación de aspecto es

baja: la mano no es mucho más larga que ancha. En efecto, las letras con momento

secundario bajo son casi las mismas que tienen una relación de aspecto baja.


7.11. Rendimiento del programa

Mostramos aquí el tiempo invertido en cada una de las operaciones que se

han investigado en este proyecto. Las pruebas han sido realizadas sobre el fichero

q20000.tif, en el que el área de la mano es de unos 116400 pixels. El ordenador

usado es un Pentium MMX a 166 MHz, corriendo Linux:

Operación Tiempo (s.)

Aplicar umbral 0.02Segmentar 0.30Obtener orientación 0.05Frontera desordenada 0.20Limpieza de contorno 0.15Extraer contorno 0.16Estudiar curvatura 0.01100 erosiones 0.18100 dilataciones 0.34Esqueletización 0.50Transformación de distancia 0.34

Total obtención de vector característico 0.79

Cuadro 7.7 Tiempo de ejecución de operaciones.

7.12 Utilidad de los parámetros calculados 91

7.12. Utilidad de los parámetros calculados

Ya que hemos visto los resultados empíricos, es el momento de pensar si los

parámetros estudiados en este proyecto son adecuados para desarrollar un clasifi-

cador basado en ellos. Algunos de los parámetros calculados no son útiles por sí

mismos, como el área y el perímetro; otros no se comportan satisfactoriamente, co-

mo el número de dedos. Los momentos de inercia han resultado interesantes, pero

no aportan nada nuevo respecto a la relación de aspecto.

Sin embargo, hemos encontrado una serie de parámetros que dividen las manos

estudiadas en grupos diferenciados. Son el número de agujeros, el ángulo de incli-

nación, la circularidad, la curvosidad y la relación de aspecto. Podemos especular

cómo sería un clasificador basado en estos parámetros.

Proponemos a continuación un clasificador basado en estos parámetros. Hay

que decir que este clasificador es sólo una propuesta, y no ha sido todavía lleva-

do a la práctica. Pero nos permitirá tener una idea de cómo podríamos usar los

parámetros calculados en un clasificador real; además, el sistema propuesto es lo

suficientemente detallado para que no sufra muchas modificaciones a la hora de ser

implementado.

La forma de funcionamiento del clasificador es sencilla: en una etapa dada,

tenemos nuestra imagen de una mano, y sabemos que debe corresponder a una de

un conjunto de letras. Nos fijamos en el valor de uno de los parámetros calculados,

y lo comparamos con el valor del mismo parámetro para cada una de las posibles

letras. Sólo algunas letras tienen un valor similar, de forma que reducimos el con-

junto de letras a que puede corresponder el parámetro estudiado. Repetimos esta

operación hasta quedarnos con una sola letra posible.

Esto supone que tenemos una librería de imágenes preclasificadas, y por ejem-

plo, sabemos que la relación de aspecto de la letra f está cerca de 3.2. La formación

de esta librería de imágenes preclasificadas se conoce como entrenamiento del sis-

tema. Vamos a ver que el entrenamiento es posible con los parámetros que hemos

aprendido a calcular en este proyecto, y para ello veremos que podemos dividir

el conjunto de imágenes que hemos estudiado en subconjuntos, muchos de ellos

con un solo elemento, que están completamente determinados por el valor de los

parámetros.

Al comenzar, tenemos un gran conjunto formado por todas las imágenes de

entrada, que corresponden a las letras a, b, c, ch, d, e, f, g, h, i, k, l, m, n, o, p, q,

r, s, t, u, x, y, z.


Ahora observamos el valor del ángulo de inclinación, que básicamente divide

el conjunto de entrada en manos horizontales y manos verticales, salvo para las

imágenes que corresponden a las letras e, h, que tienen una pendiente intermedia,

entorno a -1 radián. Diremos que la e y la h están inclinadas. Por tanto, tenemos

los siguientes grupos:

Manos horizontales: a, b, c, ch, g, r, x

Manos verticales: d, f, i, k, l, m, n, o, p, q, s, t, u, y

Manos inclinadas: e, h

Para dividir estos grupos en subgrupos menores, estudiamos la relación de as-

pecto. Fijémonos por separado en cada grupo. Para las manos horizontales, hay

tres subgrupos distintos:

Relación de aspecto baja (0–4.5): c

Relación de aspecto media (4.5–6.8): a, b, g, x

Relación de aspecto alta (6.8–9): r, ch

Por tanto, una mano horizontal con relación de aspecto baja debe corresponder a c.

Sólo hemos podido formar dos subgrupos para las manos verticales:

Relación de aspecto baja (0–5): d, i, k, l, m, o, s, u, y

Relación de aspecto alta (5–9): f, n, p, q, t

Finalmente, para las manos inclinadas:

Relación de aspecto alta (0–4): h

Relación de aspecto baja (4–9): e

En esta segunda etapa de clasificación ya tenemos tres grupos aislados, que corre-

sponden a c, h, e.

Podemos partir en dos el grupo de manos verticales con relación de aspecto

baja contando el número de agujeros:

Con un agujero: d, k, o, s

Sin agujeros: i, l, m , u, y


Ningún otro grupo contiene manos con agujeros. Como todavía quedan grupos con

más de un elemento, estudiamos a continuación el valor de la circularidad para los

distintos grupos. Para manos horizontales con relación de aspecto media (a, b, g,

x)

Circularidad baja (1–2.2): a

Circularidad media (2.2–2.6): b, g

Circularidad alta (2.6–9): x

Para manos horizontales con relación de aspecto alta (r, ch)

Circularidad alta (4–9): ch

Circularidad baja (1–4): r

Para manos verticales con relación de aspecto alta (f, n, p, q, t)

Circularidad baja (1–2.6): n, p

Circularidad alta (2.6–9): f, q, t

Para manos verticales con relación de aspecto baja y sin agujeros (i, l, m, u, y),

sólo u tiene una circularidad mayor de 2.7. Por desgracia, la circularidad no nos

ha servido para refinar el grupo (d, k, o, s). Sin embargo, podemos estudiar la

curvosidad ahora. Tomemos el grupo (f, q, t). La q tiene una curvosidad visible-

mente mayor. En el grupo (n, p), la n tiene una curvosidad visiblemente mayor.

Finalmente, estudiando el conjunto (i, l, m, y), vemos que la m es la única con 5

dedos.

Recapitulemos: usando los parámetros calculados, hemos logrado determinar

los siguientes grupos: (a), (b, g), (c), (ch), (d, k, o, s), (e), (f, t), (h), (i, l, y), (m),

(n), (p), (q), (r), (u), (x). Resumimos el proceso en la figura 7.13.

La clasificación es bastante buena, pero ¿podemos mejorarla aún?, ¿podemos

subdividir los grupos (b, g), (d, k, o, s), (f, t), (i, l, y)? Con los parámetros que

hemos calculado no podemos hacer más. Un vistazo a la gráfica del alfabeto dac-

tilológico (páginas 72 y 73) nos sirve para comprender por qué:

La f y la t son casi idénticas. Ambas son verticales, vistas de lado, con todos

los dedos extendidos, y el índice extendido en ángulo recto. La única diferencia

es que en la t, el pulgar pasa por debajo del índice. Ninguno de los parámetros


DDDDDDDDDDDDDDDDDD

\\

\\\

��

��

@@@

TTT

TTT

,,

CCCCCCC

(((((((((

hhhhhhhhh

,,

ZZZ

.................

........

@@

(((((((hhhhhhhb

bb

bb

bbb

��

bbb

��

````````AAA

��

AA

Manos

Horiz.

Inclin.

Vert.

Alta

Baja

r, ch

a, b, g, x

c

h

e

d, k, o, s

i, l, m, u, y

f, q, t

n, p

u

i, l, m, y

ch

r

x

b, g

a

f, t

n

p

m

i, l, y

Orientacion Agujeros Circularidad Curvosidad DedosRel. aspecto

q

Figura 7.13 Diagrama del clasificador. Los grupos finales se muestran enmarcados.


calculados puede detectar esto, y de hecho, es probable que sea necesaria una etapa

de preprocesado de imagen más sofisticada para ello.

Las manos correspondientes a i, l, y son muy parecidas, pero podemos ver

fácilmente que en la l el dedo extendido es el índice, mientras que en las otras

dos es el meñique. Podremos distinguir esto fácilmente con un análisis más fino

del gráfico de curvatura. Si siempre recorremos el contorno de la mano en sentido

contrario a las agujas del reloj, para l tendremos: “dedo, seguido de zona circular,

zona recta, y de nuevo otra zona recta”, mientras que para i, y será: “dedo, seguido

de zona recta, otra zona recta, y una zona curva”. Hemos visto cómo hacer tales

descripciones.

Las manos correspondientes a d, k, o, s son muy parecidas, pero se podrán

distinguir por la forma del agujero. El de k es alargado, por lo que tendrá una

relación de aspecto mayor que los otros, o una circularidad mayor. El de s es más

pequeño. Los de o, d son muy parecidos, y de hecho, la única diferencia entre ellos

es que en uno el agujero lo forman el pulgar y el índice, y en otro el agujero lo

forman el pulgar y el medio. De nuevo, la etapa de preprocesado de este proyecto

no parece suficiente.

En resumen, para distinguir d de o, y f de t, seguramente hará falta un pre-

procesado más sofisticado, probablemente con algún operador diferencial. Para las

demás letras, la etapa de preprocesado es suficiente, y en algunos casos quizás haga

falta refinar el estudio de los agujeros o del gráfico de curvatura. El balance es muy

positivo.

Esta descripción de alto nivel no muestra con justicia la complejidad de una eta-

pa de clasificación. Suele ser necesario emplear criterios estadísticos para decidir

cuál es la clase (o posibles clases) a que pertenece una mano. Por otra parte, un estu-

dio estadístico detallado podría aumentar el poder de resolución de los parámetros

calculados. En el sistema propuesto cada parámetro ha permitido partir un grupo

en dos o tres subgrupos (o ninguno), y quizás un estudio más serio muestre que al-

gunos parámetros pueden tener un poder de resolución mayor. Para tener un clasi-

ficador completo será necesario un estudio mucho más detallado, y este estudio

puede ser lo suficientemente extenso como para justificar un Proyecto de fin de

carrera.

En cualquier caso, los parámetros calculados en este proyecto parecen prom-

etedores.

Capítulo 8

Conclusiones y mejoras

Hemos visto ya la descripción de los algoritmos de este proyecto, y los resul-

tados obtenidos. Como se mencionaba en la introducción, el objetivo es encontrar

parámetros que sean útiles para construir un clasificador de gestos de la mano. En

este proyecto se ha desarrollado un programa que extrae de la imagen multitud de

características, y algunas de ellas parecen tener un buen poder discriminador. Esto

es una buena base a la que añadir una etapa de clasificación.

En concreto, de las características obtenidas, la circularidad, curvosidad, el

número de agujeros, el ángulo de inclinación y la relación de aspecto, producen

una separación de los gestos en grupos (horizontales/verticales, con/sin agujeros,

alargados/chatos . . . ) que seguramente resulten útiles para una clasificación com-

pleta.

De las demás características, el área y el perímetro son muy dependientes del

tamaño de las manos fotografiadas, y de la forma en que han sido fotografiadas. Los

momentos de inercia principal y secundario son interesantes, pero aportan poco que

no dé la relación de aspecto. Y el número de dedos no ha resultado ser satisfactorio.

Por otra parte, el proyecto ha tenido su mayor éxito en la etapa de procesado

de imagen. La etapa de procesado es robusta y efectiva, y se ejecuta en tan solo

0.79 segundos. La idea de deshacerse de los espúreos en la etapa de segmentación

ha resultado muy acertada, y el procesado de regiones se ha logrado implementar

de forma que sea muy rápido y consuma poca memoria. Las implementaciones de

las operaciones morfológicas son también muy rápidas, como hemos visto en el

capítulo anterior, y aunque no hemos usado las operaciones morfológicas aquí, son

frecuentes en la literatura sobre el tema, y muy útiles. Seguramente un proyecto

posterior encuentre buen uso para ellas.

98 Capítulo 8 Conclusiones y mejoras

También ha sido interesante la idea de colorear los pixels de frontera de gris

para llevar a cabo la limpieza del contorno. Los contornos obtenidos son realmente

“dibujables” de forma continua. Esto ha posibilitado el estudio de curvatura de la

silueta. Este estudio ha sido muy somero en este proyecto, y su producto, el número

de yemas de dedo, no ha resultado muy afortunado. Sin embargo, el estudio de

la curvatura del contorno promete ser interesante. Es concebible que pudiéramos

realizar una descripción de la silueta de la mano del tipo:

Zona recta larga, seguida de un giro suave y breve, y otro segmento

corto, en dirección opuesta al anterior. Después viene una zona circu-

lar con radio amplio, seguida de . . .

y que esta descripción resultase suficiente para la clasificación. Un clasificador

basado en una descripción cualitativa como esta se suele denominar sintáctico,

debido a que las descripciones cualitativas se suelen representar usando un lenguaje

especializado al problema en cuestión.

Por contra, la mayoría de los clasificadores son paramétricos, lo que quiere

decir que se basan en el uso de vectores de parámetros, cuyas componentes son

números reales. En general, para realizar estos clasificadores se recurre a la estadís-

tica y a la teoría de la decisión, y es necesario realizar un entrenamiento del clasifi-

cador, es decir, hay que formar una librería de imágenes de prueba pre-clasificadas.

También se recurre a veces a técnicas modernas como redes neuronales.

En este proyecto, en concreto, todos los parámetros de clasificación obtenidos,

excepto el número de dedos y el número de agujeros, son números reales, y parece

que se presta más a un clasificador paramétrico.

En cuanto a posibles mejoras para el futuro, son innumerables. Para empezar,

las implementaciones pueden hacerse más rápidas con poco esfuerzo: en este proyec-

to se usa las estructuras de datos, como colas y pilas, de la STL (Standard Tem-

plate Library) de C++. Esta librería ha sido diseñada para proporcionar estructuras

de datos genéricas, y por ello ha sacrificado algo de velocidad. Reimplementan-

do colas y listas como estructuras de datos de C seguramente conseguiríamos un

aumento considerable de velocidad. En general, reimplementar en C supone un

aumento de velocidad notable.

El peor defecto de este proyecto es su dependencia con las imágenes de entra-

da. Para manos obtenidas en otros lugares seguramente funcione con más dificul-

tades. Esto es debido a que el sistema se ha configurado ad hoc. Por ejemplo, en la

primera etapa, aplicamos un umbral de 100, que ha resultado adecuado para nues-

99

tras necesidades. Pero para tener un sistema versátil, la selección de umbral se debe

hacer en función de cada imagen, usando métodos adaptativos. Lo mismo ocurre

con los tamaños de regiones mínimo y máximo permitido, que se han definido con

arreglo a las posturas estudiadas. En resumen, es urgente, para tener un sistema

versátil, realizar la configuración del sistema de forma automática y adaptativa, no

“a dedo”.

Otra dirección futura es añadir más operaciones de procesado de imagen, co-

mo la obtención de la envolvente convexa, el uso de la transformada de Hough,

transformadas integrales . . . También sería recomendable hacer un estudio más se-

rio de la curvatura del contorno, que puede resultar muy interesante y debería poder

implementarse de forma eficiente.

En cuanto a la clasificación, es necesario ampliar el banco de imágenes de

prueba, y tomar las fotos con una iluminación más uniforme que reduzca las som-

bras. La etapa de clasificación de vectores característicos debe aún realizarse por

completo.

Finalmente, el programa de ordenador desarrollado para este proyecto es de

por sí interesante. Ofrece un intérprete de comandos rudimentario, y en sistemas

que proporcionan la librería GTK+, produce imágenes que resultan útiles a la hora

de visualizar lo que ocurre y corregir errores en los algoritmos. Con un intérprete

más sofisticado, que quizás permitiese definir procedimientos y variables, y aña-

diendo más operaciones, tendríamos el comienzo de un buen programa de proce-

sado de imagen. Por supuesto, sería deseable un interfaz gráfico intuitivo, pero no

debe olvidarse el intérprete de comandos. Gracias a él, en este proyecto no ha sido

necesario recompilar cada vez que se ha cambiado el orden de aplicación de las

operaciones. Para tener la mayor portabilidad posible del programa quizás conven-

dría usar para gráficos la librería Xlib, presente en casi todos los sistemas UNIX.

GTK+ es todavía sólo una promesa.

En resumen, lo mejor de este proyecto es que ha producido un programa que

da acceso, mediante un sencillo intérprete, a operaciones de procesado de imagen

implementadas de forma eficiente. Este programa puede usarse para producir un

vector de características de la imagen, que luego se podría clasificar por métodos

estadísticos. También puede formar la base de un programa general para Visión

Artificial.

Apéndice A

Cómo usar el programa

El programa desarrollado en el proyecto se llama desde la línea de comando

con proyvision, y admite por el momento, dos opciones:

-v modo verboso, produce cronometrado de operaciones y muestra texto produci-

do por los comandos. En el código, estos mensajes se muestran como if

(VERBOSE) std::cout < <, lo que resulta útil en la depuración de progra-

mas.

-d depth-first: esta opción cambia la implementación usada para los algoritmos.

Por lo general, para el llenado, erosión, obtención de contorno . . . , se usa el

método “a lo ancho”, pero esta opción nos permite hacerlo de otra forma.

También se le puede dar, a continuación de las opciones, el nombre de un fichero

de tipo TIFF (el único tipo soportado), que el programa abrirá inmediatamente.

Una vez hemos invocado el programa, introducimos comandos, y pulsamos

ENTER para ejecutarlos. Los comandos admitidos son:

write seguido de un nombre: almacena la imagen en memoria en un fichero de

formato TIFF con el nombre dado.

read seguido de un nombre. Lee el fichero TIFF nombrado.

threshold seguido de un entero. Aplica un umbral a la imagen.

regions segmenta la imagen.

regions_bis calcula el mapa de regiones (no se ha usado en el proyecto).

white_regions elimina regiones blancas pequeñas.

102 Apéndice A Cómo usar el programa

black_regions elimina regiones negras pequeñas.

skeleton esqueletiza la imagen (usar sólo después de tener la cola de frontera).

boundary obtiene cola de frontera desordenada.

contour obtiene contorno ordenado.

contour_outer obtiene silueta (contorno exterior) ordenada.

erode seguido de un número. Erosiona la imagen las veces deseadas.

dilate seguido de un número. Dilata la imagen las veces deseadas.

clean limpia la frontera.

curvature estudia la curvatura de la mano.

statistic realiza cálculos estadísticos y halla inclinación y momentos de inercia.

results muestra el vector de características.

q para salir.

Una ventaja de usar un intérprete que lee del standard input es que podemos

pasarle ficheros con instrucciones redirigiendo el input. Para generar los vectores

de características, en este proyecto se ha usado

proyvision fichero.tif < curvinput

donde curvinput contiene

threshold 100 regions statistic

boundary white_regions clean

contour_outer curvature results q

Apéndice B

Dactilología

El origen de los lenguajes de signos no está claro, puede que sean anteriores a

los lenguajes orales. Ya en el siglo XVI, Fray Pedro de León usaba gestos con el

propósito de comunicarse con sus alumnos, niños sordos de familias ricas. A partir

de entonces, el uso de comunicación gestual se extendió por Europa.

Los lenguajes de signos se han considerado a veces como mímica. Sin em-

bargo, a menudo los gestos de estos lenguajes no son evidentes para quien los

desconoce, y además, hay grandes diferencias entre ellos (los lenguajes).

El significado de un gesto en estos lenguajes depende de:

La postura que la mano adopta para realizar el signo.

La orientación de la palma de la mano.

La posición de la mano relativa al cuerpo.

El movimiento de la mano.

Componentes no manuales como movimiento de los labios o expresión fa-

cial.

Pero además, no hay una correspondencia estricta entre signos y palabras, lo

que a veces dificulta la traducción del lenguaje de signos. Para facilitar la comuni-

cación entre sordos y oyentes se usa a veces la dactilología, que consiste en asignar

un signo a cada letra del alfabeto. Un sordo usa la dactilología para:

Denominar un nuevo concepto que todavía carece de signo propio. Esto

ocurre hasta que se da un signo al concepto, o hasta que el concepto cae

en desuso.

104 Apéndice B Dactilología

Para expresar nombres de lugares o personas a oyentes.

La dactilología, por tanto, es auxiliar del lenguaje de signos convencional.

Existen en el mundo varios alfabetos dactilológicos. El que nos interesa es el

español, que, al igual que el irlandés o el americano, usa una sola mano (la mano

dominante). El alfabeto dactilológico inglés, por otra parte, emplea dos manos.

Este proyecto ha usado imágenes de manos en posturas del alfabeto dactilológi-

co español; en concreto, sólo en aquellas posturas correspondientes a letras que se

pueden representar sin movimiento. Por cierto, en este alfabeto no están recogidos

los signos de puntuación ni la distinción entre mayúsculas y minúsculas. Las letras

estudiadas se muestran en la figura 7.1, página 72, y en la figura 7.2, página 73.

Apéndice C

Implementación

Ha llegado el momento de presentar la implementación de los algoritmos de-

sarrollados en el Proyecto. Hasta ahora, las descripciones de algoritmos se han

hecho en pseudocódigo, y han evitado meterse en detalles “laterales”, pero el códi-

go real está escrito en C++, y debe tener en cuenta sucesos como el acceso a zonas

de memoria no asignadas, representación específica de estructuras de datos, y al-

ternativas de diseño.

C.1. Organización del código

El código del proyecto se ha dividido en los siguientes ficheros:

boundary-ops.cpp contiene las operaciones que usan la frontera de la mano, es

decir, los procedimientos de obtención de contorno y las operaciones mor-

fológicas.

curvature.cpp contiene las funciones que extraen los elementos del contorno es-

tudiando su curvatura y que calculan el número de dedos.

eval.cpp contiene el intérprete de comandos.

greylevel-ops.cpp contiene las operaciones que sólo dependen del nivel de gris de

cada punto, como aplicar un umbral.

gtk-image.cpp contiene la función que dibuja en pantalla la imagen contenida en

memoria.

gtk-main.cpp define el ejecutable con interfaz gráfico.

106 Apéndice C Implementación

image-basic.cpp define las operaciones básicas con imágenes (creación, destruc-

ción, lectura. . . ).

image-main.cpp define el ejecutable sin interfaz gráfico.

image.hpp contiene declaraciones de clases y variables globales.

region-ops.cpp describe las operaciones sobre regiones, esto es, llenado y borrado

de regiones.

statistic.cpp contiene las funciones que calculan los estadísticos y los momentos

de inercia de la imagen.

C.2. Representación de la imagen

Hemos visto varias veces a lo largo del proyecto que usamos imágenes de tipo

raster, en que los pixels están organizados en filas y columnas. Cada pixel tiene un

nivel de gris, con lo cual necesitamos un tipo de datos para almacenar este nivel

de gris. En las imágenes que nos interesan, los pixels pueden tener 256 niveles de

gris, con lo cual debemos usar 8 bits por pixel. La forma más sencilla de conseguir

posiciones de memoria con 8 bits es:

typedef unsigned char grey;

Además, por comodidad y portabilidad, vamos a definir las siguientes constantes:

const int grey_depth = 256;

const grey white = 255;

const grey black= 0;

La razón de estas definiciones es que en algunos casos, un nivel de gris de 0 repre-

senta el color blanco. No es el caso aquí, pero conviene prevenir.

Puesto que queremos una matriz de pixels, es lógico pensar en un array bidi-

mensional en C/C++, como

grey matrix[num_filas][num_columnas];

pero esto tiene la desventaja de que necesitamos saber de antemano el tamaño de

la imagen. Nuestras imágenes tienen 768 columnas y 576 filas, pero vale la pena

hacer que el programa no dependa de ello. Para esto, el espacio reservado para la

imagen debe asignarse dinámicamente, y no podemos usar la definición anterior.

C.2 Representación de la imagen 107

Cuando pedimos al sistema operativo memoria dinámica (mediante new), éste nos

devuelve un puntero a una región de memoria tan grande como necesitamos, pero

sin estructura. Para conseguir acceder a pixels con un número de fila y un número

de columna debemos poner la estructura nosotros mismos. En cualquier libro de

nivel medio sobre C/C++ se discute varias alternativas para hacer esto. La escogida

aquí pretende copiar la estructura en memoria de las matrices estáticas declaradas

como veíamos arriba. En estas matrices, los pixels de una fila ocupan posiciones

contiguas, y unas filas están directamente al lado de otras.

fila 1 fila 2 fila 3 · · · fila n

Una consecuencia interesante de esto, es que, debido a que C/C++ no realizan

control sobre los índices de un array, podemos acceder a cualquier elemento de la

matriz usando un solo índice. Por ejemplo,

matrix[0][num_columnas+5]

es lo mismo que

matrix[1][5]

Si vamos a acceder a una fila tras otra, modificar un solo índice es más rápido y

más corto de expresar. Las siguientes expresiones serían equivalentes:

for (i=0; i<num_filas; ++i)

for (j=0; j<num_columnas; ++j)

matrix[i][j] . . .

for (i=0; i<num_pixels; ++i)

matrix[0][i] . . .

Nos interesa, por tanto, tener todos los pixels ocupando posiciones consecuti-

vas de memoria. Conseguimos esto con

start = new grey[size];

donde size es el número de pixels de la imagen. El nombre start es debido a que

new nos va a devolver la dirección del comienzo de la región libre en memoria en

la que almacenaremos la imagen. Por completitud, definimos también la variable

end, que nos da la posición del último pixel de la imagen.

Necesitamos también saber el número de filas y columnas de la imagen para

algunos de los algoritmos del programa, así como para evitar accesos ilegales a


memoria. Los almacenaremos en las variables height y width. Con esto tenemos

suficiente información para acceder a cualquier pixel, pero por comodidad vamos

a proporcionar la posibilidad de acceder a la matriz por fila y columna. Para el-

lo necesitamos tener un puntero a la dirección de comienzo de cada fila, lo que

conseguimos con

matrix = new grey* [height];

for (int i=0; i<height; ++i)

matrix[i]=start+i*width;

Es decir, definimos un nuevo array que contiene punteros al array que contiene la

imagen. Con dos niveles de indirección, podemos usar matrix como base de la

matriz de pixels.

Esto es todo lo necesario para empezar a trabajar. Nos conviene tener todas las

variables que hemos definido juntas, para lo cual podemos utilizar struct o clases.

Se ha escogido usar clases porque de esta forma el alcance (scope) de las variables

es local a cada imagen, y global dentro de ella.

La definición básica de la estructura de datos que almacena la imagen es:

class Image {

public:...

private:

int height;

int width;

int size;

grey **matrix;

grey *start;

grey *end;

int offset_8neighbor[8];

int offset_4neighbor[4];

};

Ahora examinaremos las variables offset_Xneighbor. Aunque hemos pro-

visto acceso a la matriz por fila y columna, esto no es por lo general necesario, así

que no representaremos los pixels como un par de números, sino como punteros al

array start.

C.3 Operaciones sobre regiones 109

typedef grey * point;

Varios de los algoritmos vistos en el proyecto requerían poder recorrer los vecinos

de un pixel secuencialmente. offset_Xneighbor contiene las posiciones relativas

de estos vecinos respecto al pixel de origen. Recordemos que los 4-vecinos se

encuentran a la derecha, a la izquierda, encima, y debajo del pixel de origen.

offset_4neighbor[0] = 1;

offset_4neighbor[1] = -width;

offset_4neighbor[2] = -1;

offset_4neighbor[3] = width;

Para recorrer los vecinos secuencialmente, basta con

point pixel_original, pixel_vecino;

for (int i=0; i<4; ++i)

pixel_vecino = pixel_original + offset_4neighbor[i];...

C.3. Operaciones sobre regiones

Casi todas las operaciones que hemos visto necesitan conocer el valor de las

variables de clase definidas en la sección anterior, así que las implementaremos

como funciones miembro de la clase. Como ejemplo, veamos cómo aplicamos un

umbral a la imagen.

void Image::threshold(grey level)

{

point pt;

for(pt=start; pt<=end; ++pt)

if (*pt < level)

*pt=black;

else

*pt=white;

}

En la función anterior no hemos usado índices para acceder a los pixels, sino

que aprovechamos la capacidad de C/C++ para incrementar punteros. En muchos


casos (depende de la calidad del compilador), el código máquina producido es más

rápido. También conviene fijarse en el uso del operador de indirección. Ya que un

pixel pt es un puntero a un pedazo de memoria que almacena un nivel de gris,

*pt nos da ese nivel de gris. Veremos a menudo esta utilización de * a lo largo del

capítulo.

Una posibilidad que ocurre realmente en el proyecto y que no hemos discutido

hasta ahora es que podemos intentar acceder a un pixel que no pertenece a la ima-

gen. Esto ocurre, por ejemplo, cuando tratamos de recorrer los 8-vecinos de pixels

en las esquinas de la imagen. Vamos a usar un pequeño test para determinar si el

pixel pertenece a la imagen.

bool Image::in_range(point pt)

{

return (pt >= start && pt <= end);

}

Esta pequeña función demuestra la conveniencia de la representación escogida.

En caso de que hubiéramos elegido acceder a los pixels usando dos índices, la

función hubiera sido:

bool Image::in_range(int x, int y)

{

return (x >= 0 && x < width && y >= 0 && y < height);

}

No es tampoco muy complicado, pero una función que va a ser ejecutada tan a

menudo merece ser escrita de forma eficiente.

Llegamos ahora a los algoritmos de llenado discutidos en el capítulo 2. El al-

goritmo intuitivo es prácticamente una traducción del pseudocódigo.

int Image::fill4_recursive(point first, grey g_in, grey g_out)

{

point aux;

int re=1;

*first=g_out;

for (int i=0; i<4; ++i) {

aux = first + offset_4neighbor[i];


if (in_range(aux) && *aux==g_in)

re += mark4_recursive(aux,g_in,g_out);

}

return re;

}

Sólo tiene un par de elementos reseñables. Uno es que devuelve el número

de pixels que forman la región, y otro es que usa la función in_range antes de

comprobar si un pixel debe ser borrado. En el bucle for podemos comprobar cómo

salta de vecino en vecino.

La función que implementa el algoritmo de llenado a lo ancho es más intere-

sante:

int Image::fill4_breadth_first(point first,

grey g_in, grey g_out)

{

queue<point> Q;

int re=0;

int i;

point aux;

*first=g_out;

++re;

Q.push(first);

while (!Q.empty()) {

first = Q.front();

for (i=0; i<4; ++i) {


if (in_range(aux) && *aux==g_in) {

*aux=g_out;

++re;

Q.push(aux);

}

}

Q.pop();

}

return re;


}

Este es el primer ejemplo de la utilización de la Standard Template Library

(STL) de C++ en este proyecto. La STL proporciona estructuras de datos genéricas,

es decir, independientes del tipo de datos. Para ello, toman el tipo de datos como

parámetro. Así, una cola de números de coma flotante con precisión simple se

define mediante

queue<float> Q;

Las funciones de acceso a estructuras de la STL son funciones miembro, y

tienen nombres genéricos para facilitar el cambio de una estructura de datos a otra.

En la función anterior hemos usado:

Q.pop() para eliminar el primer elemento de cola.

Q.push() para poner un elemento al final de la cola.

Q.front() para acceder al primer elemento en cola.

Q.empty() para determinar si la cola está vacía.

La función que implementa el algoritmo a lo profundo es, gracias a esto, casi

idéntico

int Image::fill4_depth_first(point first,

grey g_in, grey g_out)

{

stack<point> S;

int i, re=0;

bool is_on_top;

point aux;

*first=g_out;

S.push(first);

++re;

while (!S.empty()) {

first = S.top();

is_on_top = true;

for (i=0; i<4; ++i) {



if (in_range(aux) && *aux==g_in) {

is_on_top = false;

*aux=g_out;

++re;

S.push(aux);

break;

}

}

if (is_on_top) S.pop();

}

return re;

}

Sólo se diferencia en que usamos stack<point> en vez de queue<point>, y

en que sólo realizamos pop() en caso de que no se haya añadido nuevos pixels a

la pila.

Finalmente, he aquí la función que borra las regiones negras demasiado pe-

queñas para ser agujeros entre los dedos.

void Image::get_black_regions()

{

int holes = 0;

point pt, last;

grey g_out = 1;

last=start-1;

while ((pt=get_next_point_with_level(black, last))) {

assert(g_out < white);

if (fill(pt, black, g_out) <

SMALLEST_BLACK_REGION)

fill(pt, g_out, white);

else

++holes;

++g_out;

last=pt;

}

feature_vector[num_holes] = holes-1;


}

Esta función debería resultar clara: busca el siguiente pixel negro usando la fun-

ción get_next_point_with_level, colorea la región a que pertenece, y la borra

si es demasiado pequeña. En caso de que tenga el tamaño suficiente, incrementa

el contador de agujeros. Vemos aquí por primera vez el vector de características,

feature_vector, que es una variable global del programa. Por comodidad, ac-

cedemos a sus elementos usando una variable de tipo enum.

La función que busca regiones blancas es similar, excepto que cuando encuen-

tra una región lo suficientemente grande, pinta todas las demás de negro y con-

cluye.

C.4. Obtención del contorno

El primer paso en la obtención del contorno es decidir qué pixels forman parte

de él. La definición que usamos es que un pixel pertenece al contorno si es blanco

y tiene un vecino negro. Naturalmente, esto quiere decir que todos los pixels del

fondo deben ser negros. Recordando que en la etapa de segmentación obtenemos

una región blanca y varias con distintos niveles de gris, debemos pintar de negro

todo pixel que no sea blanco. Hecho esto, averiguamos que un pixel es de contorno

con:

bool Image::is_8boundary_point(point pt)

{

point aux;

if (*pt == white) {

for (int i=0; i<8; ++i) {

aux= pt + offset_8neighbor[i];

if (!in_range(aux))

return true;

else if (*aux == black)

return true;

}

}

return false;

}

C.4 Obtención del contorno 115

La función anterior tiene la peculiaridad de que trata a los pixel “fuera de la

imagen” como pixels negros. Es decir, que los pixels blancos en un lateral de la

imagen son siempre de frontera. Es como si la imagen estuviera enmarcada por

bandas de pixels negros.

Para almacenar los pixels de contorno en una lista empleamos la siguiente fun-

ción:

void Image::get_boundary_breadth_first(queue<point> & Points)

{

int i;

queue<point> Q;

point pt, aux, last = start-1;

filter_by_level(white);

while ( (pt=get_next_boundary_point(last)) ) {

last = pt;

*pt = bound;

Q.push(pt);

while ( !Q.empty()) {

pt=Q.front();

for (i=0; i<4; ++i) {


if (in_range(aux) &&

is_8boundary_point(aux)) {

*aux=bound;

Q.push(aux);

}

}

Points.push(pt);

Q.pop();

}

}

}

Es idéntica a la función de llenado a lo ancho, excepto por que añadimos a la

cola los vecinos del pixel en cabeza de cola que pertenecen al contorno. Otra partic-

ularidad es que los pixels borrados de la cola son almacenados en una lista. La fun-


ción get_next_boundary_point, al igual que get_next_point_with_level,

usada antes, recorre la imagen a partir del pixel especificado por su argumento de

entrada, y devuelve el primer pixel que satisface un test, en este caso, is_8boundary_point.

Como veíamos en el capítulo 4, para tener un contorno continuo modificaremos la

imagen ligeramente. Este procedimiento colorea el contorno de gris, y al hacerlo,

produce “ahogos”, regiones que pierden conexión con el resto de la mano. Nos in-

teresa borrarlas, para lo cual usamos la función Image::erase_small_whites(),

que es casi idéntica a Image::get_black_regions() descrita anteriormente, ex-

cepto por que no trata de contar el número de regiones. Después de borrar las re-

giones ahogadas, es necesario borrar los pixels de frontera que ya no tienen vecinos

blancos. Usamos para ello:

void Image::clean_boundary(queue<point> & Q)

{

vector<point> Keep;

point aux;

int i, size;

while (!Q.empty()) {

aux = Q.front();

if (has_white_8neighbor(aux))

Keep.push_back(aux);

else

*aux = black;

Q.pop();

}

size = Keep.size();

for (i=0; i<size; ++i)

*( Keep[i] ) = white;

}

Esta función simplemente pinta los pixels sin vecinos blancos de negro, y el

resto de blanco, para hallar la frontera de nuevo, esta vez ordenada. No debemos

colorear de blanco ningún pixel de frontera hasta haber borrado los pixels necesar-

ios. De otra forma, falseamos el contorno. Ahora podemos ya obtener el contorno

ordenado de forma sencilla, usando

C.4 Obtención del contorno 117

void Image::get__contour_depth_first(bool once,

queue<point> & Q)

{

int i;

point pt, aux, first, last = start-1;

bool is_on_top;

pt = first = get_next_boundary_point(last);

while ( pt != 0) {

last = first = pt;

stack<point> S;

*pt = bound;

S.push(pt);

while ( !S.empty()) {

pt=S.top();

is_on_top = true;

for (i=0; i<4; ++i) {



is_8boundary_point(aux)) {

is_on_top = false;

*aux=bound;

S.push(aux);

break;

}

}

if (is_on_top) {

assert(

are_4neighbors(pt, first));

stack_to_queue(S, Q);

}

}

if (once) break;

pt = get_next_boundary_point(last);

}


}

Esta función de apariencia complicada es en realidad bastante simple. Busca

un punto de contorno, y si lo encuentra, realiza una búsqueda a lo profundo de pix-

els de frontera vecinos. Es casi idéntico a fill4_depth_first que hemos visto,

incluyendo la variable booleana is_on_top para saber cuándo llegamos a un calle-

jón sin salida. En este caso, sólo llegamos a un callejón sin salida cuando hemos

concluido el recorrido del contorno. Para certificarlo, la sentencia assert com-

prueba si el último pixel añadido a la pila es vecino del pixel inicial. Si no es así, la

limpieza del contorno, después de todo, no ha sido efectiva. La sentencia assert

se ha cumplido para todas las imágenes del proyecto, por lo que podemos decir que

la limpieza de contorno es muy robusta. La función toma un parámetro booleano,

once, que nos indica si debemos buscar un solo contorno o más. La razón de es-

to es que en posiciones de la mano con agujeros, tendremos al menos dos curvas

cerradas de contorno. Si deseamos usar sólo el contorno exterior, daremos a once

(“una vez” en inglés), el valor true.

La función are_4neighbors toma dos pixels como argumentos y recorre todos

los vecinos de uno de ellos, devolviendo true en caso de que el otro se encuentre

entre los vecinos. La función stack_to_queue forma una cola con los elementos

de la pila. Con esto queda concluida la extracción del contorno.

C.5. Procesado del contorno

La primera operación a hacer para procesar el contorno es cambiar los pix-

els de representación. Dado un pixel representado como un puntero a un byte en

la imagen, debemos ser capaces de producir un número complejo cuya parte real

sea el número de columna del pixel, y cuya parte imaginaria sea el número de fi-

la. Aprovechando la posibilidad de hacer aritmética con punteros que nos ofrece

C, podemos hallar el número de pixel en que nos encontramos respecto del pixel

inicial de imagen, es decir, el índice de pixel. Puesto que las filas completas se al-

macenan una después de otra, dividiendo el índice de pixel por el número de pixels

en cada fila tenemos como cociente el número de fila, y como resto, el número de

columna.

typedef complex<float> cmplx;

cmplx Image::make_complex(point pt)

C.5 Procesado del contorno 119

{

int dif, row, col;

dif = pt-start;

row = dif / width;

col = dif % width;

cmplx re(col, height-1-row);

return re;

}

Nótese que debido a que en nuestra matriz de pixels la fila 0 es la superior,

damos la parte imaginaria referida a la fila inferior para tener un sistema de coor-

denadas más habitual.

Convertir la lista de pixels de frontera en una lista de números complejos es

una cuestión trivial, así como lo es hallar la lista de diferencias, de argumentos y de

curvaturas. Como muestra, presentamos la función que decima (rechaza elementos

de lista periódicamente) la lista de pixels de frontera.

void decimate(int n, vector<cmplx> & V)

{

vector<cmplx> re;

int i, size = V.size();


if (i%n == 0)

re.push_back(V[i]);

V = re;

}

Las demás funciones de este tipo son análogas. Vale la pena examinar las fun-

ciones que se ocupan de la detección de dedos. Algunas de ellas van a producir la

lista de elementos de contorno (representada por una ristra de letras). Estas fun-

ciones no presentan ninguna peculiaridad, y ocupan mucho espacio, por lo que no

las presentamos. Una vez tenemos la lista de elementos de contorno, la siguiente

función obtiene el número de dedos.

int numfingers(vector<char> letters)

{

int i, size = letters.size(), crossings =0;

bool is_curved;


dilate_tips(letters);

is_curved = (letters[size-1] == ’c’);


if (letters[i] != ’c’ && is_curved) {

is_curved = false;

++crossings;

}

else if (letters[i] == ’c’ && !is_curved) {

is_curved = true;

}

return crossings;

}

La función realiza una llamada a dilate_tips, que dilata las yemas, es decir,

convierte en c las letras adyacentes a una c, como se describe en el capítulo 5. De-

spués, cuenta el número de dedos, que es el número de regiones de cs consecutivas.

Para obtener este número cuenta los cambios de c a otra letra.

C.6. Inclinación y momentos de inercia

Vimos en el capítulo 6 que para definir el eje de una región es conveniente hallar

una serie de estadísticos comúnmente usados, como las medias y los momentos

centrales de orden 2.

La función get_statistics los calcula:

void Image::get_statistics()

{

int x, y;

double sum = 0, sum_x=0, sum_y =0;

double sum_xx =0, sum_xy = 0, sum_yy = 0;

double cx, cy, mu_11, mu_20, mu_02;

double mean_square_angle, axis_angle;

double mom_1, mom_2;

for (y=0; y<height; ++y) {

for (x=0; x<width; ++x) {

C.7 Operaciones morfológicas 121

if (matrix[height-1-y][x] == white) {

++sum;

sum_x += x;

sum_y += y;

sum_xx += x*x;

sum_xy += x*y;

sum_yy += y*y;

}

}

}

cx = sum_x / static_cast<double>(sum);

cy = sum_y / static_cast<double>(sum);

mu_11 = sum_xy - cx*cy*sum;

mu_20 = sum_xx - cx*cx*sum;

mu_02 = sum_yy - cy*cy*sum;

.

.

Para las sumas, que dan números enteros, se ha tenido que usar tipo de datos

double, debido a que los números producidos son tan grandes que no caben tan

siquiera en un long int. Esta es una de las pocas ocasiones en que vale la pena

acceder a los pixels por fila y columna. cx y cy representan las medias, y mu_nm

los momentos centrales. El procedimiento es muy grande, y no lo hemos mostrado

entero. El resto contiene sentencias para hallar los ejes y los momentos, dados los

estadísticos. Hacer una función grande suele ser mala política, pero en este caso,

para poder usar los estadísticos hubiéramos debido definirlos como variables glob-

ales, siempre desaconsejable, o haber formado con ellos una estructura de datos.

Formar una estructura de datos es lo más recomendable, y si no se ha hecho aquí

es porque el procesado es tan sencillo que casi no vale la pena molestarse.

C.7. Operaciones morfológicas

Presentamos ahora la implementación de las operaciones morfológicas. La más

sencilla de ellas es la erosión:

void Image::erode(int n, queue<point> & Q)


{

point pt, aux;

int i;

if (Q.empty()) {

std::cerr << "erode: given an"

<< " empty boundary queue!!"

<< endl;

return;

}

for ( ; n>0; --n) {

aux = 0;

Q.push(aux);

pt = Q.front();

while (pt !=0) {

for (i=0; i<8; ++i) {



*aux==white) {

*aux=bound;

Q.push(aux);

}

}

*pt=black;

Q.pop();

pt = Q.front();

}

Q.pop();

}

}

Incluye un par de sentencias para reaccionar en caso de que intentemos aplicar

esta operación a una región cuya frontera no hemos hallado todavía. Este mane-

jador de error está presente en las otras operaciones morfológicas. Como vemos,

usamos la STL y su implementación de las colas. Las operaciones de dilatación

y transformación de distancia tienen una implementación muy parecida, que no

mostramos.

La función que obtiene el esqueleto es más interesante:

C.7 Operaciones morfológicas 123

void Image::get_skeleton(queue<point> & Q)

{

int i, num_neighbors;

point pt, aux;

if (Q.empty()) {

std::cerr << "get_skeleton: given an"

<< " empty boundary queue!!"

<< endl;

return;

}

while ( !Q.empty()) {

pt=Q.front();

for (i=0; i<8; ++i) {


if (in_range(aux) && *aux==white) {

num_neighbors =

get_num_8neighbors(aux,

white);

if (!makes_8connection(aux,

bound)

&& num_neighbors >= 2

&& num_neighbors <= 6

) {

*aux=bound;

Q.push(aux);

} else {

*aux=skel;

}

}

}

Q.pop();

}

}

Colorea los pixels de esqueleto de un nivel de gris especial, llamado skel. Uti-

liza dos funciones auxiliares; makes_8connection comprueba si un pixel, de ser

coloreado del nivel de gris de los pixels de frontera, produciría una conexión en


la frontera, o, lo que es igual, ahogaría una región blanca. get_num_8neighbors

simplemente recorre los 8-vecinos de un pixel y cuenta cuántos de ellos son blan-

cos.

C.8. El intérprete

Para tener una mayor flexibilidad en la aplicación de operaciones sobre imá-

genes, se ha escrito un intérprete de comandos rudimentario. Gracias a él nos

ahorramos recompilar cada vez que queremos combinar operaciones de una nue-

va forma. No es más que una sentencia if ... else ... gigante, y proporciona

cronometrado de operaciones:

void eval(string expr, Image & im, queue<point> & Q)

{

clock_t start_, finish_;

start_ = clock();

if (expr == "write") {

char bf[40];

std::cin >> bf;

im.write_TIFF(bf);

} else if (expr == "read") {

char bf[40];

std::cin >> bf;

im.read_TIFF(bf);

} else if (expr == "threshold") {

int level;

.

.

.

El comportamiento del programa está determinado por ciertas variables glob-

ales, como VERBOSE o DEPTH_FIRST, que controlan cuánta información im-

prime en pantalla, y qué alternativas de implementación escoge. Podemos dar val-

ores a estas variables a través de la línea de comandos, para lo cual usamos un

lector específico a tal fin, parse_command_line

C.9 Interacción con el exterior 125

C.9. Interacción con el exterior

Las imágenes que usa el proyecto están almacenadas en disco duro, en ficheros

de tipo TIFF. Por suerte, hay una librería, TIFFIO, que es gratis y proporciona

funciones para leer y escribir ficheros TIFF. La documentación de esta librería,

por desgracia, no es muy buena, así que mostramos la función que escribe los

contenidos de la imagen en memoria en un fichero:

void Image::write_TIFF(char *filename)

{

TIFF* tif = TIFFOpen(filename, "w");

if (!tif) {

std::cerr << "Cannot write file: " << filename << endl;

return;

}

TIFFSetField(tif, TIFFTAG_PLANARCONFIG, PLANARCONFIG_CONTIG);

TIFFSetField(tif, TIFFTAG_IMAGELENGTH, height);

TIFFSetField(tif, TIFFTAG_IMAGEWIDTH, width);

TIFFSetField(tif, TIFFTAG_BITSPERSAMPLE, 8);

TIFFSetField(tif, TIFFTAG_COMPRESSION, COMPRESSION_NONE);

TIFFSetField(tif, TIFFTAG_PHOTOMETRIC, PHOTOMETRIC_MINISBLACK);

TIFFSetField(tif, TIFFTAG_MINSAMPLEVALUE, 0);

TIFFSetField(tif, TIFFTAG_MAXSAMPLEVALUE, 255);

TIFFSetField(tif, TIFFTAG_ORIENTATION, ORIENTATION_BOTLEFT);

for (int r = 0; r < height; r++)

TIFFWriteScanline(tif, matrix[r], r);

TIFFClose(tif);

}

También se ha implementado un pequeño interfaz gráfico para poder visualizar

la imagen contenida en memoria en una ventana. Para ello se usa la librería de

widgets GTK+. Esta librería está basada en el sistema de ventanas X de MIT, y

está escrita en C. Todas las distribuciones de Linux la incluyen, pero no suele estar

disponible en sistemas UNIX más antiguos.

Bibliografía

[1] Harold Abelson and Gerald Jay Sussman with Julie Sussman. Structure and

Interpretation of Computer Programs. MIT Press, Cambridge, MA, second

edition, 1996.

[2] Kenneth R. Castleman. Digital Image Processing. Prentice Hall, Upper Sad-

dle River, NJ, 1996.

[3] Thomas Cormen, Charles Leiserson, and Ronald Rivest. Introduction to Al-

gorithms. MIT Press, Cambridge, MA, 1990.

[4] E. R. Davies. Machine Vision: Theory, Algorithms, Practicalities. Academic

Press, London, second edition, 1997.

[5] Manfredo P. do Carmo. Geometría diferencial de curvas y superficies. Alian-

za Editorial, Madrid, 1995.

[6] Richard Feynman. Fisica. Volumen I. Addison-Wesley Iberoamericana,

Wilmington, DE, 1987.

[7] James D. Foley, van Dam, Feiner, and Hughes. Computer Graphics: Princi-

ples and Practice. Addison-Wesley, Reading, MA, second edition, 1996.

[8] Marc Levoy. Area flooding algorithms. Technical report, Hanna-Barbera

Productions, June 1981.

[9] Marcos Pineda Ortega. Desarrollo de un sistema de clasificación de gestos de

la mano, 1998. Proyecto de Fin de Carrera, ETSI Telecomunicaciones. UPM.

[10] Athanasios Papoulis. Probability, Random Variables, and Stochastic Process-

es. McGraw-Hill, New York, third edition, 1991.

[11] J. R. Parker. Practical Computer Vision using C. John Wiley & Sons, New

York, 1993.

128 BIBLIOGRAFÍA

[12] Patrick Henry Winston. Artificial Intelligence. Addisson Wesley, Reading,

MA, second edition, 1992.

[13] T. Y. Zhang and C. Y. Suen. A fast parallel algorithm for thinning digital

patterns. In Communications of the ACM, volume 27, pages 236–239, 1984.

sistema eﬁciente de reconocimiento de gestos de la … · introducción este proyecto de ﬁn de...

Documents