Visión Por Computador
Visión Por Computador
Visión Por Computador
$1$%(/e1025(12'Ì$=
É1*(/6É1&+(=&$//(
-26e/(67(%$16É1&+(=0$5Ì1
9,6,Ð1
325
&20387$'25
Servicio
de
Publicaciones
Reservados todos los derechos. Ni la totalidad ni parte de este libro, incluido el diseño de la cubierta,
puede reproducirse o transmitirse por ningún procedimiento electrónico o mecánico, incluyendo fotocopia,
grabación magnética o cualquier almacenamiento de información y sistemas de recuperación, sin permiso
escrito del AUTOR y de la Editorial DYKINSON, S.L.
© Copyright by
Universidad Rey Juan Carlos
Servicio de Publicaciones
Madrid, 2003
ISBN: 84-9772-069-5
Los autores
-i-
Índice
- ii -
Índice
- iv -
Capítulo 1 Introducción a la
Visión Artificial
por los objetos vistos. Pero fue en el siglo XVII cuando se realizaron los mayores
progresos de la mano de Newton, que hizo notables avances en la teoría del color y
la dispersión. Newton era defensor de una teoría corpuscular, según la cual la luz
estaba formada por un flujo de partículas proyectadas por el cuerpo luminoso. Al
mismo tiempo, otros científicos, como Hooke y Huygens, defendían una teoría
ondulatoria que explicaba mejor ciertos hechos como que dos haces luminosos se
cruzasen sin perturbarse. El principal problema de aquella teoría ondulatoria
estribaba en que no existía ninguna evidencia empírica del medio en el que se
propagaba esa onda. Este medio, que se denominó éter, debería llenar el espacio, y
debería tener una dureza altísima para permitir la alta velocidad de propagación
que caracteriza a la luz. Por ello, y también quizás debido al peso de la autoridad
de Newton, la teoría corpuscular se impuso durante doscientos años.
1.1.2 Definiciones
Aunque las ondas luminosas constituyen una parte muy pequeña del conjunto de
ondas electromagnéticas, son especialmente interesantes porque tienen la
particularidad de que son captadas por los ojos y procesadas en el cerebro. El ojo
-2-
Capítulo 1 - Introducción a la Visión Artificial
Figura 1.- La parte de la radiación electromagnética que constituyen las ondas luminosas
abarca desde el fin del ultravioleta 400 nm hasta el comienzo del infrarrojo 700 nm.
Potencia (w)
680 nm
520 nm
(a) (b)
Figura 3.- Diagramas espectral de una luz verde (a) y de una luz blanca (b).
Flujo radiante
El flujo radiante es la cantidad de energía emitida por una fuente de ondas
electromagnéticas por unidad de tiempo y se mide en vatios (ver Figura 4).
radiación
Potencia eléctrica Flujo radiante Flujo Luminoso
visible
Figura 4.- De la energía usada para producir luz, el humano sólo percibe una pequeña parte
que se denomina flujo luminoso.
-4-
Capítulo 1 - Introducción a la Visión Artificial
Flujo luminoso
El flujo luminoso es la parte del flujo radiante detectada por el ojo (ver Figura 4).
La unidad de flujo luminoso es el lumen (L). Un lumen es el flujo luminoso
procedente de una abertura de 1/60 cm2 en un cilindro de material refractario que
contiene un material patrón que radia a través de un cono de radiación de un
estereorradián. El flujo luminoso se puede medir con un fotómetro y se representa
con el símbolo F.
800
Eficiencia Luminosa (Lumenes/vatio)
700
600
500
400
300
200
100
0
360 440 520 600 680
-5-
Capítulo 1 - Introducción a la Visión Artificial
Esta curva, que llamaremos V(l), permite definir la relación (1.1). Ésta
permite calcular el flujo luminoso de una radiación cuando se conoce su
distribución espectral P(l).
¥
F = ò P(l ) × V (l ) × dl (L) (1.1)
0
Ejemplo 1.-
¥
F = ò P(l) × V (l ) × dl = 27 ´ 420 = 11340 (L)
0
Intensidad luminosa
La intensidad luminosa (1.2) es el flujo luminoso emitido por unidad de ángulo
sólido (Figura 6). Se representa como I, y su unidad es la bujía (b), que se
corresponde a un lumen/estereorradián.
dF
I= (b) (1.2)
dω
Luminancia o brillo
La luminancia o brillo de un manantial es la intensidad luminosa por unidad de
superficie.
-6-
Capítulo 1 - Introducción a la Visión Artificial
Flujo Luminoso
Emisor de luz
-7-
Capítulo 1 - Introducción a la Visión Artificial
· La sensibilidad a la intensidad.
· La inhibición lateral.
Figura 7.- A la izquierda el ojo con detalle de sus partes más importantes. A la derecha un
esquema de un bastón y de un cono.
-8-
Capítulo 1 - Introducción a la Visión Artificial
a1
a2
Intensidad
percibida
b
B
a2’
Intensidad real
Figura 8.- La línea A representa la relación entre el brillo distinguido por el ojo humano y
el nivel de brillo real.
-9-
Capítulo 1 - Introducción a la Visión Artificial
Figura 9.- El color gris del cuadrado interior de la figura de la derecha parece más oscuro
que el cuadrado interior de la figura de la izquierda, a pesar de que ambos están tintados
con el mismo gris.
Inhibición lateral
El otro fenómeno que se indicaba, la inhibición lateral, se origina en el hecho de
que las células de la retina, al detectar un nivel de intensidad, inhiben las células
vecinas, produciendo perturbaciones en las fronteras de cambio de intensidad. Este
fenómeno, que puede apreciarse en la Figura 10, también influye en que el brillo
percibido no esté en proporción directa con el brillo físico.
Figura 10.- La tonalidad de cada una de las franjas verticales de la figura de la izquierda es
uniforme. Sin embargo, al observarlas, parece que son más oscuras por la derecha y más
claras por la izquierda. El brillo percibido para cada banda se refleja en el diagrama de la
derecha.
Los conos tienen una sensibilidad menor que los bastones. Se dice
popularmente que “de noche todos los gatos son pardos”, reflejando el hecho de
que con poca luz sólo los bastones captan suficiente energía para activarse.
Matiz
El matiz o tono se deriva de la relación que se produce entre las activaciones de los
distintos tipos de conos cuando sobre ellos incide la luz. El matiz depende de la
longitud de onda dominante, es decir, aquélla para la que se encuentra más energía
en el diagrama espectral (ver Figura 11). El ser humano es capaz de distinguir
entre 125 y 150 matices distintos cuando están próximos, perdiendo esa capacidad
si están distanciados espacialmente.
680 nm
(a) (b)
Figura 11.- La figura de la izquierda no tiene una longitud de onda dominante, su matiz es
blanco. La figura de la derecha corresponde a un objeto rojo, siendo la longitud de onda
dominante la correspondiente a 680 nm.
Saturación
Mide la proporción entre la longitud de onda dominante y el resto de longitudes de
onda. En la Figura 12 se presenta un ejemplo de dos diagramas espectrales con el
mismo matiz, pero con diferente saturación.
- 11 -
Capítulo 1 - Introducción a la Visión Artificial
680 nm 680 nm
(a) (b)
Figura 12.- Dos espectros con el mismo matiz. El de la izquierda corresponde a un rojo
muy saturado. El de la derecha a una luz roja poco saturada.
Tipos de conos
Estudios fisiológicos han revelado que existen tres tipos de conos, denominados
tipos S, L, y M. Los conos de tipo S (short) son más sensibles a las radiaciones con
longitud de onda corta (azules), los M (medium) a las radiaciones de longitud
media (verdes), y los L (large) a las de longitud larga (rojos). El hecho de la
existencia de sólo tres tipos de receptores, para percibir todos los colores, es la
base de la teoría triestímulo.
- 12 -
Capítulo 1 - Introducción a la Visión Artificial
A B C
x= , y= , z=
A+ B+C A+ B+C A+ B+C
1
Aunque no es posible obtener todos los colores mediante mezcla aditiva de tres linternas,
sí es posible expresar matemáticamente todos los colores como combinación lineal de tres
linternas. La mezcla aditiva puede realizarse en la realidad sin más que mezclar la luz de las
linternas. La combinación lineal debe permitir la resta de luces, cosa que no es posible
físicamente.
- 13 -
Capítulo 1 - Introducción a la Visión Artificial
2,5
c
2
Lumenes
1,5
a
b
1
0,5
0
360 440 520 600 680 760
Longitud de onda (nm)
Figura 13.- Curvas fijadas por la C.I.I., mediante experimentos estadísticos con personas,
que fijan el número de lúmenes de cada una de tres linternas monocromáticas necesarias
para igualar un vatio de flujo radiante para cada matiz del espectro.
(a) (b)
Figura 14.- Diagrama Cromático del C.I.I.
- 14 -
Capítulo 1 - Introducción a la Visión Artificial
Los colores comprendidos dentro del triángulo definido por los puntos R,
G y B2 de la Figura 14 (b) son aquéllos que se pueden obtener por mezcla aditiva
de tres linternas con los colores correspondientes a los vértices del triángulo. Por
eso los televisores y los monitores de ordenador, eligen cuidadosamente la base de
tres colores (rojo, verde y azul) que usarán para construir las imágenes que
presentan, de manera que el área del triangulo dentro del diagrama C.I.I. sea
máxima, y así poder representar el máximo posible de colores en sus pantallas.
Figura 15.- A la izquierda mezcla aditiva de la luz tres linternas sobre una superficie blanca
no iluminada. A la derecha mezcla substractiva de tres tintes sobre un lienzo blanco.
Tintas
Usando tintas no se puede realizar la mezcla aditiva de haces de luz, ya que los
colores percibidos al mezclar tintas son el resultado de una mezcla substractiva.
Así, al tintar un papel blanco se le van restando componentes que ya no podrá
2
RGB por red, green, blue.
3
Hue-Saturation-Value en inglés.
- 15 -
Capítulo 1 - Introducción a la Visión Artificial
Por ejemplo, si se toma la base: rojo, verde, y azul (RGB). Mezclando las
tintas roja (que lo absorbe todo menos el rojo) y verde (que lo absorbe todo menos
el verde), se obtiene un color que absorbe toda la radiación y no refleja ninguna,
por lo que aparece el color negro. Mezclando rojo y azul o verde y azul ocurre lo
mismo. Por ello el rojo, el verde y el azul forman una base que, fuera de los tres
colores que posee, no permite obtener muchos más de manera substractiva.
4
Cyan, magenta, yellow.
- 16 -
Capítulo 1 - Introducción a la Visión Artificial
Imágenes
Una imagen bidimensional es una función que a cada par de coordenadas (x, y)
asocia un valor relativo a alguna propiedad del punto que representa (por ejemplo
su brillo o su matiz). Una imagen acromática, sin información de color, en la que a
cada punto se le asocia información relativa al brillo, se puede representar como
una superficie (ver Figura 16), en la cual la altura de cada punto indica su nivel de
brillo. Una imagen en color RGB se puede representar asociando a cada punto una
terna de valores que indica la intensidad de tres linternas (una roja, otra verde y
otra azul). Una imagen de color de espectro completo se puede representar
asociando a cada punto un diagrama espectral de emisión de color.
Figura 16.- La imagen plana (2D) de la derecha puede representarse como una superficie,
en la que la coordenada z para el punto (x, y) depende del brillo que tenga en la imagen
plana.
Escenas 3D
Otra forma de representar la realidad consiste en asignar a cada punto del espacio
que pertenece a un objeto (x, y, z) una propiedad del punto (su existencia, su
intensidad, su matiz, etcétera.). Al trabajar con imágenes 3D, como se tiene la
forma de los objetos, la información de brillo y color puede no ser tan relevante.
- 17 -
Capítulo 1 - Introducción a la Visión Artificial
Secuencias animadas
Las secuencias de imágenes estáticas dan lugar a secuencias animadas. Por
ejemplo, una cámara cinematográfica toma sucesiones de imágenes estáticas que
se capturan a una frecuencia determinada. Si estas sucesiones de imágenes se
presentan luego a una frecuencia superior a 25 imágenes por segundo
aproximadamente, el sistema visual humano no es capaz de distinguir el cambio e
interpreta movimiento. Éste es el efecto usado en cine y televisión.
- 18 -
Capítulo 1 - Introducción a la Visión Artificial
Figura 17.- Diagrama de bloques de las etapas típicas en un sistema de visión artificial.
[Bax94] caps. 1 y 2.
- 19 -
Capítulo 2 Adquisición y
representación de
imágenes digitales
En este capítulo se tratan los aspectos más relevantes del proceso de captura y
digitalización de una imagen, esto es, la adquisición de la imagen del mundo físico
y su paso al dominio discreto y virtual informático.
5
Del inglés pixel que abrevia a “picture element”.
- 21 -
Capítulo 2 - Adquisición y representación de imágenes digitales
· Es una lente biconvexa de grosor despreciable cuya sección posee dos ejes
de simetría. Al mayor se le denomina eje axial, al menor eje óptico. El
centro óptico es el punto interior a la lente donde se cortan ambos ejes.
· Todo haz de luz que pasa por el centro óptico de una lente continúa en
línea recta (Figura 18 a).
· Todos los haces paralelos que inciden perpendiculares al eje axial de una
lente, tras atravesarla, se cortan en un punto llamado foco (Figura 18 a)
situado sobre el eje óptico. Se define distancia focal como la distancia del
foco al centro óptico de la imagen.
Fo co
C
Eje ó ptico
Punto de formación
de la imagen
E je axia l de la lente
C = Centro óp tico de la lente
(a) (b)
Figura 18.- Trayectoria seguida por la luz al atravesar una lente biconvexa de grosor
despreciable. (a) los haces paralelos que inciden perpendiculares al eje de la lente se cortan
en el foco. (b) los haces provenientes de un mismo punto objeto se cortan en el punto de
formación de la imagen.
- 23 -
Capítulo 2 - Adquisición y representación de imágenes digitales
1 1 1
- =
Si S0 f
6
La aberración cromática se debe a que el índice de refracción es diferente según la
longitud de onda de la luz que atraviesa la lente. Así, diferentes colores dan lugar a
diferentes planos de formación de la imagen, y esto da lugar a la aparición de bandas de
colores en los bordes de los objetos dentro de una imagen.
- 24 -
Capítulo 2 - Adquisición y representación de imágenes digitales
Es por todo esto que las propiedades descritas sólo se cumplen de manera
aproximada en la realidad, aunque en general, cuanto mejor sea la calidad de una
lente más se aproximará su comportamiento al ideal.
La cámara oscura
El principio de cámara oscura, descrito en el punto anterior, se puede usar para
capturar imágenes de escenas tridimensionales (del mundo real) y proyectarlas en
un plano bidimensional. Dispositivos de este tipo son las cámaras fotográficas y
las cámaras de vídeo. Este modelo además se puede usar para capturar imágenes
de elementos bidimensionales, como fotografías y documentos, como por ejemplo
hacen los escáneres de cámara. También se pueden usar dos o más cámaras para
capturar diferentes perspectivas de una misma escena y construir una
representación 3D de la misma.
El escaneo
Este esquema es fundamentalmente distinto del basado en cámara, ya que existe un
elemento activo (generalmente un haz de luz láser) que recorre la escena que se
desea capturar. Por tanto son imprescindibles dos dispositivos, uno emisor del haz
de luz y otro el receptor. El escáner emite el haz de luz y éste, tras chocar con la
imagen que se escanea, es recogido en el detector de luz. Repitiendo este proceso
de manera continua se puede construir una señal que corresponde a una
representación de la escena.
7
La distorsión esférica se origina al existir diferente plano de formación de la imagen para
los rayos que atraviesan la zona más gruesa de la lente que para los que atraviesan la zona
más delgada de la misma.
- 25 -
Capítulo 2 - Adquisición y representación de imágenes digitales
2.1.2 La digitalización
Es el proceso de paso del mundo continuo (o analógico) al mundo discreto (o
digital). En la digitalización normalmente se distinguen dos procesos: el muestreo
(“sampling”) y la cuantización (“quantization”).
Muestreo
El muestreo de una señal continua consiste en la medición a intervalos
(discretización) respecto de alguna variable (generalmente el tiempo o el espacio),
siendo su parámetro fundamental la frecuencia de muestreo, que representa el
número de veces que se mide un valor analógico por unidad de cambio. Mediante
el muestreo se convierte una imagen IC, que es algo continuo, en una matriz
discreta ID de N×M píxeles. El número de muestras por unidad de espacio sobre el
objeto original conduce al concepto de resolución espacial de la imagen. Ésta se
define como la distancia, sobre el objeto original, entre dos píxeles adyacentes. Sin
embargo la unidad de medida de resolución espacial mas habitual suele ser los
píxeles por pulgada (comúnmente DPIs8) siempre medidos sobre el objeto original.
De esta forma, el proceso de muestreo, para una imagen, que asocia a cada
punto un valor real, cambia una imagen del formato:
IC(x, y) Î Â en donde x, y Î Â
al formato:
8
Dots per inch en inglés.
- 26 -
Capítulo 2 - Adquisición y representación de imágenes digitales
Cuantización
La segunda operación es la cuantización de la señal, que consiste en la
discretización de los posibles valores de cada píxel. Los niveles de cuantización
suelen ser potencias de 2 para facilitar su almacenamiento en el computador. Así,
suelen usarse 2, 4, 16 ó 256 niveles posibles. De esta forma, ID que pertenece a Â
se convierte en IDC (discreta cuantizada) que pertenece a N. El número de niveles
posibles define la resolución radiométrica.
IDC (x, y) Î N
Donde,
x, y Î N y 0 £ x £ N-1 , 0 £ y £ M-1
- 27 -
Capítulo 2 - Adquisición y representación de imágenes digitales
Sobre una imagen a impresa a 200 DPIs la frecuencia máxima con la que
pueden cambiar los pixeles es de 100 cambios por pulgada. Para obtener toda la
información posible al digitalizar tal imagen es preciso muestrear, al menos, a la
misma resolución. Sin embargo suele aplicarse un margen doble de seguridad en el
muestreo, según el cual la frecuencia de muestreo debe tomarse igual al doble de la
resolución original, y por ello en este caso se digitalizaría a 400 DPIs.
También hay que tener en cuenta que dependiendo del uso que se vaya a
hacer de una imagen, la elección de los parámetros de digitalización puede variar
de una forma menos objetiva. Así, para la publicación de un periódico en blanco y
negro, 16 niveles de intensidad podrían ser suficientes, pero elegir menos de 80
por 80 píxeles por pulgada de resolución espacial sería inadmisible; mientras que
para una imagen, con vistas a su reconocimiento, aunque podría ser preciso utilizar
más niveles de intensidad, se podría permitir una resolución espacial menor.
9
La imagen de Lena es una imagen clásica dentro del mundo del procesado digital de
imágenes. Es una imagen de una chica, aparecida en la publicación Play Boy en 1972,
escaneada por un investigador desconocido. La ventaja de operar sobre imágenes estándar
radica en que permiten comparar los resultados que se obtienen con los que han obtenido
otros investigadores.
- 28 -
Capítulo 2 - Adquisición y representación de imágenes digitales
Figura 19.- En la fila superior se presenta la misma imagen, siempre a 256 niveles de
intensidad, usando diferentes resoluciones espaciales. En la fila inferior se mantiene la
resolución espacial y se reduce el nivel de cuantización.
- 29 -
Capítulo 2 - Adquisición y representación de imágenes digitales
(b)
)
(c)
(a)
Figura 20.- Efecto de la reducción de resolución sobre una imagen. La imagen (a)
corresponde a un texto y se ha tomado con un escáner bitonal; (b) la misma imagen tras
reducir su resolución en un 50% respecto de la original cuando simplemente se deja uno de
cada cuatro píxeles; (c) la misma imagen tras reducir su resolución en un 50% utilizando un
promediado de cada grupo de cuatro píxeles.
- 30 -
Capítulo 2 - Adquisición y representación de imágenes digitales
Ejemplo 2.-
Para saber cuántos bytes ocupa una imagen de 640x480 píxeles con 256 niveles de
intensidad cuando se representa en una pantalla de ordenador, se opera:
Ejemplo 3.-
Para saber cuantos bytes ocupa una imagen de 1024 por 768 píxeles con
codificación para 16 millones de colores (color Real) se opera:
En este caso cada píxel necesita 3 bytes (uno para codificar 256 niveles de
rojo, otro para 256 niveles de azul, y otro para 256 de verde), por tanto:
- 31 -
Capítulo 2 - Adquisición y representación de imágenes digitales
Las cámaras suelen permitir también variar la cantidad de luz que entra en
la misma mediante un dispositivo conocido como diafragma. Cuando se abre
mucho el diafragma, entran muchos rayos de luz por cada punto P de la escena, y
de acuerdo con los principios que se enunciaron para el modelo de lente fina, esto
hace que sólo los elementos que estén a cierta distancia de la cámara aparezcan
enfocados. Por el contrario, cuanta menor es la apertura del diafragma menos rayos
de luz entran por cada punto P de la escena. En el límite, cuando por cada punto P
de la escena sólo incidiese un rayo en el plano de formación de la imagen, toda la
imagen debería aparecer enfocada simultáneamente. Así, en el caso de poca
apertura se dice que se tiene gran profundidad de campo, y en el caso de mucha
apertura se dice que se tiene poca amplitud de campo.
Por último se debe señalar que existen objetivos con diferente distancias
focales. Para cada distancia focal se obtiene diferente tamaño en la representación
de un objeto (ampliación). Hay también objetivos de focal variable que permiten
cambiar la distancia focal dentro de un rango de valores (zoom). La problemática
que introducen estos objetivos es más compleja. En ellos, por ejemplo, las
aberraciones son más difíciles de corregir. Por ello sólo son útiles para aquellos
problemas en los que la calidad de la imagen no sea un factor muy importante.
10
Se llama grano a cada partícula de haluro de plata, sustancia reactiva a la luz que incide
sobre ella utilizada en las películas fotográficas. Cuanto mayor es el grano mayor
sensibilidad a la intensidad se consigue, pero menor definición y detalle tiene la imagen.
- 33 -
Capítulo 2 - Adquisición y representación de imágenes digitales
Voltios
Segundos
- 34 -
Capítulo 2 - Adquisición y representación de imágenes digitales
Figura 24.- Primer CCD comercial. Constaba de 120.000 elementos y tenía un tamaño de
0’5x0’25 pulgadas.
11
Dispositivo de Carga Acoplada (“Coupled Charge Device”).
- 35 -
Capítulo 2 - Adquisición y representación de imágenes digitales
Para evitar estos problemas podrían utilizarse 3 CCDs (uno por cada plano
de color), aunque esta solución es más cara y voluminosa. En el año 2002 ha
aparecido un nuevo tipo de dispositivos (denominados Foveon) que incorpora los
tres receptores RGB en la misma posición física mediante un sistema multicapa.
Escáner de cámara
Este dispositivo, que sigue el modelo de cámara, recorre una imagen plana (un
documento, una fotografía, un plano...) con un CCD compuesto por una única línea
de elementos fotosensibles, llamado CCD lineal. En su recorrido, el CCD lineal
construye una representación digital de la imagen.
- 36 -
Capítulo 2 - Adquisición y representación de imágenes digitales
Escáner de tambor
Este tipo de escáner se utiliza para digitalizar elementos planos (documentos,
fotografías, etc.). El elemento que se desea escanear se sitúa sobre un cilindro
denominado tambor. Allí, se escanea usando un dispositivo que emite un haz
puntual sobre el mismo. Este haz, tras reflejarse en el elemento que se escanea se
recoge en un detector sensible. Tras analizar el haz recibido se construye una
representación del elemento escaneado.
12
Del inglés voxel que juega con la abreviatura de “volume element” y con el parecido a la
palabra píxel.
- 38 -
Capítulo 2 - Adquisición y representación de imágenes digitales
Ejemplo 4.-
- 39 -
Capítulo 2 - Adquisición y representación de imágenes digitales
El primer punto que se debe tener en cuenta es que no son lo mismo “los
datos usados para presentar una imagen” que “la información que contienen”. Por
ejemplo: la idea del número “dos” se puede representar como: 2, dos, II, 6-3-1...
Cada representación necesita diferente espacio para su codificación (1, 3, 2 y 5
caracteres respectivamente) pero codifican la misma información.
n1
CR =
n2
1
RD = 1-
CR
Así, se dice que un código es más redundante que otro cuando precisa más
datos que aquél para describir la misma información. Clásicamente se distinguen
tres tipos de redundancia:
· Redundancia en la codificación
· Redundancia visual
- 40 -
Capítulo 2 - Adquisición y representación de imágenes digitales
Redundancia en la codificación
Hasta ahora se ha usado un tamaño fijo para representar la información de cada
punto de las imágenes. Por ejemplo, se ha usado un byte13 para representar la
intensidad de cada punto de una imagen con un nivel de cuantización de 256
niveles de gris.
Sin embargo en una imagen suelen existir niveles de intensidad que son
más probables que otros porque aparecen más veces. La codificación de tamaño
variable es una técnica de compresión que aprovecha esta circunstancia. Consiste
en asignarle un código más corto a los niveles de intensidad más probables (que
aparecen más veces) y más largo a los menos probables (que aparecen menos
veces), consiguiendo una reducción del tamaño de los datos de la imagen. Un
ejemplo de este tipo de compresión lo define el método de compresión Huffman.
Ejemplo 5.-
Una imagen de 8 niveles de gris se codifica según la Tabla 1. Para calcular el nivel
de redundancia de la codificación de tamaño fijo (que usa tres bits por píxel y tiene
50x50 píxeles de tamaño) respecto de la que usa compresión mediante
codificación de tamaño variable se debe calcular la cantidad de memoria necesaria
para cada representación. Con el código original, para representar la imagen hacen
falta:
Con el código de tamaño variable se tiene que para cada píxel, en media,
se usan:
13
Un byte está compuesto de 8 bits. Un bit es la unidad mínima de información en un
computador.
- 41 -
Capítulo 2 - Adquisición y representación de imágenes digitales
7500 )
CR = = 1. 1
6750
1 )
RD = 1 - ) = 1 - 0 .0 9 = 0 .1
1. 1
Sin Probabilidad de
Código de tamaño variable
compresión aparición
000 0.19 11
001 0.25 01
010 0.21 10
Ejemplo 6.-
Sin compresión, usando un dígito por cada píxel, los datos de la imagen
son:
14
Consultative Committee on International Telephone and Telegraphy. Comité que ha
estandarizado varios algoritmos de compresión (CCITT-Grupo 3, CCITT-Grupo 4...) con
vistas a su transmisión en formato digital. Ahora se conoce como UIT.
15
Realmente en este ejemplo no se consigue compresión si se observa que sólo es necesario
un bit por píxel en la codificación original, frente al entero que se necesita luego. Pero en un
ejemplo de mayor tamaño si se apreciaría el efecto de la compresión.
- 43 -
Capítulo 2 - Adquisición y representación de imágenes digitales
(20 + 20) 40
CR = = = 3.6363...
(5 + 6) 11
1
RD = 1 - = 0.725
40
11
Así, según esta forma de codificación, el 72’5% del tamaño de los datos
representados por el código original son redundantes.
Redundancia visual
Como se ha explicado en el capítulo 1, la imagen percibida por el ojo no se
corresponde exactamente con la imagen física. Por ejemplo, se ha estudiado que el
humano no es capaz de distinguir entre dos niveles de gris parecidos cuando hay
involucrados niveles de contraste elevados. Así, desde el punto de vista de nuestra
percepción, cierta información puede considerarse menos importante y por tanto
redundante.
- 44 -
Capítulo 2 - Adquisición y representación de imágenes digitales
(a) (b)
(c) (d)
Figura 28.- Efecto de la compresión JPEG, donde se aprecian los artefactos que introduce
la compresión con pérdida. (a) imagen de Lena sin comprimir ocupa 30Kb; (b)
comprimiendo con el algoritmo JPEG el tamaño se reduce a 3Kb. (c) detalle del sombrero
sin comprimir; (d) detalle del sombrero tras comprimir.
N -1 M -1
é p × k1 ù ép × k 2 ù
B(k1 , k 2 ) = C k1 C k 2 å å 4 × I (i, j ) × cos ê (2i + 1)ú × cos ê (2 j + 1)ú
i=0 j =0 ë 2× N û ë2×M û
(2.1)
1 N -1 M -1 é p × k1 ù ép × k 2 ù
I (i, j ) = å å
4 k 2 = 0 k0 = 0
C k1 C k 2 B(k1 , k 2 ) × cos ê
ë 2× N
(2i + 1)ú × cos ê
û ë2×M
(2 j + 1)ú
û
(2.2)
1
Siendo C k = para k = 0, y Ck = 1 para el resto.
2
Ejemplo 7.-
(8 ´ 8) 64
CR = = =4
(16) 16
1
RD = 1 - = 0.75
4
Deduciéndose por tanto que el 75% del tamaño de los datos representados
por el código original son redundantes. En el próximo tema, se profundizará en las
propiedades de la transformada de cosenos cuando se estudie la transformada de
Fourier.
- 46 -
Capítulo 2 - Adquisición y representación de imágenes digitales
- 47 -
Capítulo 2 - Adquisición y representación de imágenes digitales
- Listado 1 –
color real y para grises; 1 bit para bitonales; 1, 2, 4, 8 ó 16 para paletas). Por
último, la tabla de colores RGBQUAD define una paleta de colores en donde cada
color se define por la intensidad para cada una de las componentes RGB.
Vecindad
Para todo punto p de coordenadas (x, y) se dice que un píxel q pertenece a sus 4-
vecinos y se escribe qÎN4(p) si y sólo si q tiene coordenadas:
B A B
A p A
B A B
Figura 29.- Los 4-vecinos de p son los puntos A. Los 8-vecinos de p son los puntos A y B.
- 49 -
Capítulo 2 - Adquisición y representación de imágenes digitales
Conectividad
Se ha visto que una imagen se asimila a una matriz cada uno de cuyos elementos es
un píxel. Entre los píxeles de esta matriz se puede definir una relación que define
dos píxeles como conectados cuando son vecinos y sus valores son similares desde
algún punto de vista. Formalmente, se define un conjunto V que representa los
valores compatibles para que dos píxeles que sean vecinos se diga que están
conectados:
Ejemplo 8.-
- 50 -
Capítulo 2 - Adquisición y representación de imágenes digitales
Figura 30.- Ejemplo de tipos de conectividad: (a) corresponde a una imagen en niveles de
gris. (b), (c) y (d) representan en negro los píxeles de (a) que están dentro de un V
determinado y muestran la relación de conexión entre ellos: (b) 4-conexión, (c) 8-conexión,
(d) m-conexión.
Camino
Un camino desde el píxel p, de coordenadas (x, y), al píxel q, de coordenadas (s, t),
es una secuencia de píxeles distintos de coordenadas:
Donde (x0, y0)=(x, y) y (xn, yn)=(s, t) y (xi, yi) está conectado a (xi-1, yi-1) y
siendo la n la longitud del camino. Se puede hablar de 4, 8 y m-caminos
dependiendo del tipo de conexión involucrada.
Componente conexa
Para todo píxel p de una imagen, el conjunto de los píxeles hasta los que hay una
camino desde p se dice que forman su componente conexa. Además se cumple que
dos componentes conexas distintas tienen conjuntos de píxeles disjuntos.
- 51 -
Capítulo 2 - Adquisición y representación de imágenes digitales
d ( p, q ) = ( x - s ) 2 + ( y - t ) 2
Nótese que siempre que sólo sea importante desde un punto de vista
comparativo, esto es para comprar distancias entre puntos, se puede prescindir del
cálculo de la raíz cuadrada, lo que redundará en una mayor velocidad de cálculo.
d ( p, q ) = x - s + y - t
d ( p, q) = max( x - s , y - t )
- 52 -
Capítulo 2 - Adquisición y representación de imágenes digitales
[Esc01] cap. 3,
[Bax94] cap. 6,
[Mic96]
- 53 -
Capítulo 3 Filtrado y Realzado de
Imagen
E S
H
- 55 -
Capítulo 3 – Filtrado y realzado de imagen
- 56 -
Capítulo 3 – Filtrado y realzado de imagen
· División.- División de los valores de los píxeles de una imagen entre los de
otra.
A B -A A or B
æ x' ö æ 1 0 d x ö æ x ö
ç ÷ ç ÷ ç ÷
ç y'÷ = ç 0 1 d y ÷ × ç y ÷
ç 1 ÷ ç0 0 1 ÷ ç 1÷
è ø è ø è ø
æ x' ö æ s x 0 0ö æ x ö
ç ÷ ç ÷ ç ÷
ç y'÷ = ç 0 sy 0÷ × ç y ÷
ç1÷ ç 0 0 1 ÷ø çè 1 ÷ø
è ø è
- 58 -
Capítulo 3 – Filtrado y realzado de imagen
P
q
(-x,-y) (x,y)
Figura 34.- Ejemplo de rotación. (a) Imagen original que se desea rotar en torno al punto P
de coordenadas (x,y); (b) resultado de la primera traslación; (c) resultado del giro; (d)
resultado final.
Ejemplo 9.-
æ 1 0 x ö æ cos(q ) - sen(q ) 0 ö æ 1 0 - x ö
ç ÷ ç ÷ ç ÷
= ç 0 1 y ÷ × ç sen(q ) cos(q ) 0 ÷ × ç 0 1 - y ÷ =
ç0 0 1÷ ç 0 0 1 ÷ø çè 0 0 1 ÷ø
è ø è
æ cos(q ) - sen(q ) x(1 - cos(q )) + ysen(q ) ö
ç ÷
= ç sen(q ) cos(q ) y (1 - cos(q )) - xsen(q ) ÷
ç 0 0 1 ÷
è ø
- 59 -
Capítulo 3 – Filtrado y realzado de imagen
200
puntos
(a) (b)
Figura 36.- (a) histograma de una imagen con poco contraste. (b) histograma de una
imagen saturada.
- 61 -
Capítulo 3 – Filtrado y realzado de imagen
0 0 0
0 0.5 1 0 0.5 1 0 0.5 1
Una función de transferencia que aclare los niveles claros y oscurezca los
más oscuros, conseguirá sobre el conjunto de la imagen un efecto visual de
aumento de contraste. Una función tal se puede obtener componiendo una función
de transferencia del histograma que hasta el valor de 0’5 se comporte como la
función cuadrado y que en adelante se comporte como la función raíz. En la Figura
38 se ha representado esta función de transferencia. La función (b) de la misma
figura produce el efecto contrario, esto es una disminución del contraste.
- 62 -
Capítulo 3 – Filtrado y realzado de imagen
1 1
0.5 0.5
0 0
0 0.5 1 0 0.5 1
(a) (b)
- 63 -
Capítulo 3 – Filtrado y realzado de imagen
(a)
(b)
(c)
Figura 39.- Transformaciones del histograma sobre la imagen de Lena: (a) imagen original
con su correspondiente histograma; (b) resultado de una operación de disminución de
contraste; (c) aumento de contraste.
PR
PS
a
a
r s
Figura 40.- Si s es el valor transformado de r, el proceso de ecualizado exige que el área a
la izquierda de r debe ser la misma que la que hay a la izquierda de s.
r s s
ò
0
PR (l )dl = ò PS (l )dl = ò dl = s
0 0
(3.1)
nr
PR (r ) = (3.2)
n
r nj
s(r ) = å (3.3)
j =0 n
0 1 0 0 0.2 0
Figura 41.- (a) imagen original; (b) imagen con valores normalizados entre 0 y 1; (c)
histograma de (b).
- 66 -
Capítulo 3 – Filtrado y realzado de imagen
0 0.16 » 0.2
Tabla 3
Figura 42.- (a) Resultado de la ecualización de la Figura 41; (b) histograma ecualizado.
- 67 -
Capítulo 3 – Filtrado y realzado de imagen
Figura 43.- Ecualizado del histograma sobre la imagen de Lena: (a) imagen original con su
correspondiente histograma; (b) ecualizado del histograma.
- 68 -
Capítulo 3 – Filtrado y realzado de imagen
se pueden apreciar y alterar directamente elementos como el ruido, los bordes, las
texturas, etc.
a0 ¥ ¥
+ å a n cos(nx) + å bm sen (mx)
2 n=1 m =1
1 p
an =
p ò
-p
f ( x) cos(nx)dx "n = 0,1,2,...
1 p
bm =
p ò
-p
f ( x)sen (mx)dx "m = 1,2,3...
En adelante se entenderá por coeficiente cada uno de los pares (a1, b1), (a2,
b2)... Así el coeficiente enésimo define la amplitud de las series de cosenos y senos
de frecuencia enésima.
- 69 -
Capítulo 3 – Filtrado y realzado de imagen
Figura 44.- En esta figura se presenta el resultado del cálculo de varios coeficientes de la
transformada de Fourier de una función (a). Las gráficas (b), (c) y (d) presentan las señales
sinusoidales correspondientes a los 3 primeros coeficientes de Fourier. La figura (e)
corresponde a la suma de esas tres primeras señales sinusoidales. Por último, (f)
corresponde a la suma de las 10 primeras componentes.
- 70 -
Capítulo 3 – Filtrado y realzado de imagen
- 71 -
Capítulo 3 – Filtrado y realzado de imagen
puede utilizar la fórmula de Euler a fin de encontrar una notación más compacta,
transformado el coeficiente (an, bn) en un número complejo.
N -1 2p
1 -j kn
ab(n) =
N
å f (k ) × e
k =0
N
"n = 0,1,..., N - 1 (3.4)
N -1 2p
j kn
f (k ) = å ab(n) × e N
"k = 0,1,..., N - 1
n =0
0 0 0
0 0.5 1 0 0.5 1 0 0.5 1
Figura 45.- De izquierda a derecha un filtro paso alto, un filtro paso bajo y un filtro paso
banda.
N -1
E = å f (k )
16 2
La energía de una señal se define como
k =0
- 73 -
Capítulo 3 – Filtrado y realzado de imagen
(a)
(b)
(c)
(d)
(e)
(f)
Figura 46.- (a) Señal que contiene ciertos datos, (b) ruido aleatorio, (c) la señal de datos
más el ruido, (d) representación de los módulos de los coeficientes de Fourier, (e)
representación de los módulos tras eliminar los que tenían poca energía, (f) el resultado de
la transformada inversa de Fourier sobre los coeficientes modificados corresponde a la señal
inicial sin ruido.
- 74 -
Capítulo 3 – Filtrado y realzado de imagen
N -1
1
ab(n) =
N
å f (k ) × PRE (nk mod N)
k =0
"n = 0,1,..., N - 1
N
-1
1 2
ab(2n) =
N
å SUM (k ) × PRE (nk mod N)
k =0
"n = 0,1,..., N / 2 - 1 (3.5)
donde:
N
SUM (k ) = f (k ) + f (k + )
2
17
Fast Fourier Transform en inglés.
- 75 -
Capítulo 3 – Filtrado y realzado de imagen
N
-1
1 2
ab(2n + 1) =
N
å DIF (k ) × PRE (nk mod N)
k =0
"n = 0,1,..., N / 2 - 1 (3.6)
donde:
2p
N j k
DIF (k ) = f (k ) - f (k + )e N
2
2pxn 2pmy
1 N -1 N -1 -j -j
I C (n, m) = F ( I ( x, y )) = åå I ( x, y ) × e N
×e N
N x =0 y =0
"n, m = 0,1,...N - 1
Debe apreciarse que esta definición sólo resulta aplicable sobre imágenes
cuadradas.
- 76 -
Capítulo 3 – Filtrado y realzado de imagen
Figura 47.- En esta figura se muestra una imagen de Lena (a) sobre la que se realiza una
transformada de Fourier, obteniéndose (b) y (c), que corresponden respectivamente a la
representación matricial de los módulos y de las fases de los coeficientes de Fourier
normalizados entre 0 y 1 y en falso color.
2pxn 2pmy
1 N -1 N -1 -j -j
I ( x, y ) = F -1 ( I C (n, m)) = å å
N n =0 m =0
I C (n, m) × e N
×e N
"n, m = 0,1,...N - 1
- 77 -
Capítulo 3 – Filtrado y realzado de imagen
Bajas Frecuencias
Altas frecuencias
Figura 48.- Situación de los valores correspondientes a las altas y a las bajas frecuencias
sobre la matriz de coeficientes de la transformada discreta de Fourier bidimensional.
en azul los valores que han sido puestos a cero. Se observa que sólo han pasado los
módulos de las frecuencias inferiores a 30 píxeles.
Figura 49.- Modificación sobre las matrices de coeficientes poniendo a cero el módulo
correspondiente a las altas frecuencias (a), y manteniendo las fases (b). El resultado de la
transformada inversa sobre las matrices de coeficientes modificadas corresponde a la
imagen (c) donde se aprecia que los bordes han sido suavizados.
- 79 -
Capítulo 3 – Filtrado y realzado de imagen
Figura 50.- Modificación realizada sobre las matrices de coeficientes poniendo a cero el
módulo correspondiente a las bajas frecuencias (a), y manteniendo las fases (b). El
resultado de la transformada inversa sobre las matrices de coeficientes modificadas
corresponde a la imagen (c) donde se aprecia sólo la información de los bordes y el ruido de
alta frecuencia.
- 80 -
Capítulo 3 – Filtrado y realzado de imagen
Figura 51.- Arriba la imagen de Lena a la que se le añade un ruido con estructura que
consiste en la desaparición de 1 de cada 3 líneas de la imagen. Abajo el resultado de un
filtrado paso banda ajustado a la zona del histograma de Fourier en el que aparecen las
frecuencias que corresponden al ruido.
- 81 -
Capítulo 3 – Filtrado y realzado de imagen
N N
2 2
I ' ( x, y ) = I ( x, y ) * h ( x, y ) = å å I (i, j) × h( x - i, y - j )
N N
i =- j =-
2 2
"x, y = 0,1,..., N - 1
Ejemplo 10.-
Supóngase una función impulsional h de tamaño 3x3 igual a la matriz que sigue:
æ h1 h2 h3 ö
ç ÷
h = ç h4 h5 h6 ÷
çh h8 h9 ÷ø
è 7
- 82 -
Capítulo 3 – Filtrado y realzado de imagen
Se aprecia que, para una máscara de convolución de 3x3, el valor del píxel
I’(x,y) tras el filtrado depende únicamente del valor del píxel I(x,y) y de sus ocho
vecinos antes del filtrado.
æ1 1 1ö æ 1 2 1ö
1ç ÷ 1ç ÷
h = ç1 2 1÷ h = ç 2 4 2÷
10 ç ÷ 16 ç ÷
è1 1 1ø è 1 2 1ø
El filtro del bicho raro es otro ejemplo de filtro paso bajo. Consiste en
comparar la intensidad de un píxel con la de sus 8 vecinos. Si la diferencia es
superior a cierto umbral U (que debe elegirse previamente), se sustituye tal píxel
- 83 -
Capítulo 3 – Filtrado y realzado de imagen
por el valor promedio de los píxeles vecinos, en otro caso se mantiene su valor de
intensidad.
Tanto el filtro de la mediana, como el filtro del “bicho raro” son filtros no
18
lineales , es decir, no se pueden deducir de una convolución, y por tanto no tienen
equivalente en el dominio de la frecuencia.
æ1 1 1ö
1ç ÷
ç1 1 1÷
9ç ÷
è1 1 1ø
¶I r ¶I r
Ñ( I ( x, y )) = ux + u y
¶x ¶y
18
Un operador O sobre imágenes bidimensionales se dice que es lineal si se cumple que:
O[k1×I1(x, y)+k2×I2(x, y)] = k1×O[I1(x, y)] + k2×O[I2(x, y)]
siendo k1 y k2 dos constantes e I1 e I2 dos imágenes bidimensionales.
- 84 -
Capítulo 3 – Filtrado y realzado de imagen
¶I
Gx = = I ( x, y ) * h1 ( x, y )
¶x
¶I
Gy = = I ( x, y ) * h2 ( x, y )
¶y
z1 z2 z3
z4 z5 z6
z7 z8 z9
¶f ¶f
= z5 - z6 y = z5 - z8
¶x ¶y
æ0 0 0 ö æ 0 0 0ö
ç ÷ ç ÷
h1 = ç 0 1 - 1÷ h2 = ç 0 1 0 ÷
ç0 0 0 ÷ ç 0 - 1 0÷
è ø è ø
I G ( x, y ) = G x2 ( x, y ) + G y2 ( x, y )
- 85 -
Capítulo 3 – Filtrado y realzado de imagen
1
I G ( x, y ) = G x ( x, y ) + G y ( x , y )
2
¶f
= ( z 3 + 2 z 6 - z 9 ) - ( z1 + 2 z 4 - z 7 )
¶x
¶f
= ( z1 + 2 z 2 - z 3 ) - ( z 7 + 2 z 8 - z 9 )
¶y
æ1 0 -1ö æ1 2 1ö
1ç ÷ 1ç ÷
h1 = ç 2 0 - 2 ÷ h2 = ç 0 0 0÷
4ç ÷ 4ç ÷
è1 0 -1ø è - 1 - 2 - 1ø
Estas matrices se conocen como ventanas de Sobel, que fue quien las
propuso. Mediante ellas se calcula el gradiente en las direcciones horizontal y
vertical. En la Figura 53 se ve cómo el resultado de aplicar h1 sobre la imagen de
Lena produce una imagen en la que aparecen los contornos horizontales de la
figura de la imagen original.
æ - 1 - 1 - 1ö æ - 1 0 1ö
æ 1 0 ö æ 0 1ö ç ÷ ç ÷
Robert : çç ÷÷ y çç ÷÷ Prewitt : ç 0 0 0 ÷ y ç - 1 0 1÷
è 0 - 1ø è - 1 0 ø ç 1 1 1 ÷ ç - 1 0 1÷
è ø è ø
- 86 -
Capítulo 3 – Filtrado y realzado de imagen
æ 1 0 -1ö
1ç ÷
ç 2 0 - 2÷
4ç ÷
è 1 0 -1ø
Figura 53.- Filtrado paso alto de Sobel en la dirección x en valor absoluto. El resultado se
presenta con el valor de los píxeles invertidos.
¶2I r ¶2I r
D( I ( x, y )) = Ñ(Ñ( I ( x, y ))) = ux + 2 u y
¶x 2 ¶y
siendo:
z4' = z4 – z5 y z5' = z5 – z6
y por tanto:
æ 0 1 0ö
1ç ÷
ç 1 - 4 1÷
8ç ÷
è 0 1 0ø
Original Laplaciana
- 88 -
Capítulo 3 – Filtrado y realzado de imagen
(A)x = { c / c = a + x, " a Î A}
Reflexión de A como:
 = { x / x = - a, " a ΠA}
Complementario de A como:
Ac = { x / x Ï A}
A - B = { x / x Î A y x Ï B}
A - B = A Ç Bc
Dilatación
Siendo A y B dos conjuntos en Z2, la dilatación de A con B, denotada como A Å B,
se define:
A Å B = {x / x = a + b "a Î A y "b Î B}
AÅB=BÅA
A Å B = {x /( Bˆ ) x Ç A ¹ f }
- 89 -
Capítulo 3 – Filtrado y realzado de imagen
A Å B = {x /[( Bˆ ) x Ç A] Í A}
A B
B
Figura 55.- Ejemplo de dilatación en el que se ha señalado con un punto negro el origen del
elemento B.
Erosión
Siendo A y B dos conjuntos en Z2, la erosión de A con B, denotada como AQB, se
define:
AQB = {x / x + b Î A "b Î B}
AQB = {x /( B) x Í A}
A B
A B
(AQB ) c = A c Å Bˆ
(AQB) c = {x /( B) x Í A}c = {x /( B) x Ç A c = f }c =
= {x /( B) Ç A c ¹ f } = A c Å Bˆ
x
Apertura
La apertura de A con B se define como:
A ° B = (A Q B) Å B
· A ° B es un subconjunto de A.
· (A ° B) ° B = A ° B.
· Si C es subconjunto de D Þ C ° B es subconjunto de D ° B.
- 91 -
Capítulo 3 – Filtrado y realzado de imagen
B
A
A B
A B
Figura 57.- Arriba se presenta la figura A y el elemento estructurante B. En medio se
presenta la ejecución de la operación de apertura y su resultado. Abajo se presenta la
operación de cierre.
Cierre
El cierre de A con B se define como:
A · B = (A Å B) Q B
· A es un subconjunto de A · B.
· (A · B) · B = A · B.
· Si C es subconjunto de D Þ C · B es subconjunto de D · B.
- 92 -
Capítulo 3 – Filtrado y realzado de imagen
Coincidencia estructural
Si el elemento B se define teniendo en cuenta los puntos a blanco que lo rodean, se
tiene la descripción de un objeto B1 y su entorno B2. La operación de coincidencia
estructural, o Hit or Miss, busca la parte de la imagen A que cumpla que los
puntos activos de B estén en A y los puntos del entorno de B estén en Ac.
A A*B
Figura 58.- Ejemplo de operación de coincidencia estructural.
Eliminación de ruido
Este filtro elimina los objetos de una imagen que tienen un tamaño menor que un
elemento estructurante B determinado.
Limpiar(A) = (A ° B) · B
- 93 -
Capítulo 3 – Filtrado y realzado de imagen
Extracción de bordes
Este filtro obtiene los bordes de una figura A restándole su interior.
Bordes (A) = A – (A Q B)
A B
A-(A B)
Relleno de agujeros
Este filtro precisa de un proceso iterativo que concluye cuando no se producen más
cambios sobre la imagen. Se parte de X0 igual a un punto del agujero que se desea
rellenar. Luego se aplica de manera iterativa:
Xk = (Xk-1 Å B ) Ç Ac
Adelgazamiento
Esta operación adelgaza los elementos de una imagen hasta que se reducen a un
esqueleto interior a la misma. Para poder realizar esta operación es preciso definir
la siguiente operación:
- 94 -
Capítulo 3 – Filtrado y realzado de imagen
A Ä B = A – (A * B)
- 95 -
Capítulo 3 – Filtrado y realzado de imagen
(a) (b)
Figura 61.- Ejemplo de reconstrucción de un código de barras degradado (a). Se utiliza una
operación dilatación con elemento estructurante vertical de 9x1 y se obtiene (b).
- 96 -
Capítulo 3 – Filtrado y realzado de imagen
(a)
(b)
Figura 62.- Ejemplo de eliminación de ruido de la figura (a) mediante una erosión y una
dilatación posterior con un elemento estructural de 3x3, resultando la figura (b).
- 97 -
Capítulo 3 – Filtrado y realzado de imagen
[JKS95] caps. 4 y 5,
[Esc01] caps. 4 y 5,
[Par97] caps. 1 y 2
- 98 -
Capítulo 4 Segmentación
- 99 -
Capítulo 4 –Segmentación
19
Optical Character Recognition, reconocimiento óptico de caracteres.
- 100 -
Capítulo 4 –Segmentación
4.1.1 La textura
Intuitivamente la textura de un objeto dentro de una imagen es el conjunto de
formas que se aprecia sobre su superficie y que le dotan de cierto grado de
regularidad. Una definición típica de textura es la siguiente: “uno o más patrones
locales que se repiten de manera periódica”.
Figura 63.- Diversas imágenes del álbum de Brodatz, utilizadas en el análisis de texturas.
Existen dos enfoques para definir una textura: uno descendente (“top-
down”) y otro ascendente (“bottom-up”). El enfoque descendente se basa en la
existencia de un elemento básico de textura, llamado téxel, y en una regla de
formación. Esta regla define cómo y dónde se sitúan estos elementos básicos. Este
enfoque funciona bien cuando la textura es bastante regular, por ejemplo en la
imagen de una pared de ladrillos. El enfoque ascendente se basa en que la textura
es una propiedad que se puede derivar de estadísticos (como la media y la
varianza) de pequeños grupos de píxeles. Este enfoque funciona bien para texturas
donde resulta difícil ver los componentes individuales, por ejemplo la textura de la
- 101 -
Capítulo 4 –Segmentación
4.1.2 El borde
Los bordes de un objeto en una imagen digital corresponden a la línea de píxeles
que separa ese objeto del fondo de la imagen. Normalmente estos bordes se
corresponden con los puntos donde se producen discontinuidades en los valores de
los píxeles adyacentes (cambios en el matiz o el brillo) o en conjuntos de píxeles
(cambios de textura).
ì1, si I (i, j ) ³ U
B(i, j ) = í
î0, si I (i, j) < U
- 102 -
Capítulo 4 –Segmentación
(a) (b)
(c) (d)
Figura 64.- La elección adecuada del umbral de binarización permite separar la tierra del
mar en esta imagen de satélite. Se aprecia que la sombra de las nubes sobre la tierra y las
nubes sobre el mar producen errores. Por ello es preciso algún posproceso.
Paso 1.- Filtrado paso bajo de la imagen I(x, y) usando una ventana de tamaño V.
1
Repetir "k Î {V/2 £ k £ 255 – V/2}: hF(pk) = å h(p(k-V/2))
V
Paso 2.- Cálculo de la primera y de la segunda derivada de hF. Para ello se puede usar la
aproximación de la derivada como resta de valores de posiciones consecutivas:
Paso 3.- Si hF’(k) £ U, siendo U un umbral positivo, y hF’’(k) > 0, entonces hay que marcar
k como candidato a mínimo local.
Umbralización de banda
La umbralización de banda permite segmentar una imagen en la que los objetos
(regiones de píxeles) contienen niveles de gris dentro de un rango de valores y el
fondo tiene píxeles con valores en otro rango disjunto. Así,
- 104 -
Capítulo 4 –Segmentación
ì1 si I (i, j ) Î R
B(i, j ) = í
î0 en otro caso
Multiumbralización
La multiumbralización, como su nombre indica, consiste en la elección de
múltiples valores de umbral dentro del proceso, permitiendo separar a diferentes
objetos dentro de una escena cuyos niveles de gris difieran. El resultado no será
ahora una imagen binaria sino que los diferentes objetos (regiones) tendrán
etiquetas diferentes:
IS(i,j) = 1, si I(i,j) Î R1
= 2, si I(i,j) Î R2
= 3, si I(i,j) Î R3
……………………
= n, si I(i,j) Î Rn
= 0, en otro caso
Semiumbralización
La semiumbralización persigue obtener una imagen resultado en niveles de gris, y
para ello pone a cero el fondo de la imagen conservando los niveles de gris de los
objetos a segmentar que aparecen en la imagen inicial. Así:
ì I (i, j ) si I (i, j ) ³ U
I S (i, j ) = í
î 0 en otro caso
Umbralización adaptativa
En las técnicas anteriores, el o los rangos de umbralización se consideran fijos con
independencia de las características locales de la imagen considerada. En muchas
imágenes donde la iluminación no es uniforme puede ocurrir que píxeles del
- 105 -
Capítulo 4 –Segmentación
Paso 1.- Dividir la imagen original I(i,j) en subimágenes Ik(i,j) donde se supone que los
cambios de iluminación no son tan fuertes
- 106 -
Capítulo 4 –Segmentación
r
t p
Figura 66.- Los píxeles r y t son los vecinos a tener en cuenta al evaluar el píxel p en el
algoritmo de etiquetado de componentes conexas.
- 109 -
Capítulo 4 –Segmentación
cont++
M(r,t) = M(t,r) = 1
Paso 3.- Hacer p igual al siguiente píxel, siguiendo el orden de izquierda a derecha y de
arriba a abajo. Si quedan más píxeles ir al paso 2.
Paso 4.- Calcular el cierre transitivo de la matriz M y sustituir la etiqueta de cada píxel
por su equivalente de orden menor.
Ejemplo 11.-
Para etiquetar cada píxel de la Figura 67a según la componente conexa a la que
pertenezcan se aplica el algoritmo 1. Al llegar al paso 4 da como resultado la
imagen (b) de la Figura 67, y la siguiente matriz M.
æ1 1 1 0ö
ç ÷
ç1 1 0 0÷
M =ç
1 0 1 0÷
ç ÷
ç0 0 0 1 ÷ø
è
M0 = M
- 110 -
Capítulo 4 –Segmentación
æ1 1 1 0ö æ 1 1 1 0ö æ 1 1 1 0ö
ç ÷ ç ÷ ç ÷
ç1 1 0 0÷ ç 1 1 0 0÷ ç 1 1 1 0÷
M1 = M 0 × M 0 = ç × =
1 0 1 0÷ ç 1 0 1 0÷ ç 1 1 1 0÷
ç ÷ ç ÷ ç ÷
ç0 0 0 1 ÷ø çè 0 0 0 1 ÷ø çè 0 0 0 1 ÷ø
è
æ1 1 1 0ö æ 1 1 1 0ö æ1 1 1 0ö
ç ÷ ç ÷ ç ÷
ç1 1 1 0÷ ç 1 1 1 0÷ ç1 1 1 0÷
M 2 = M1 × M1 = ç × = = MT
1 1 1 0÷ ç 1 1 1 0÷ ç1 1 1 0÷
ç ÷ ç ÷ ç ÷
ç0 0 0 1 ÷ø çè 0 0 0 1 ÷ø çè 0 0 0 1 ÷ø
è
De la matriz MT se deduce:
2 ® 1, 3®1
1 2 1 1
1 3 2 1 1 1
1 1 1 1 1 1 1 1 1 1
4 4 4 4
(a) (b) (c)
Figura 67.- La figura (a) representa un mapa de bits donde los cuadros oscuros representan
píxeles negros y los cuadros blancos píxeles blancos. La figura (b) presenta los píxeles
etiquetados antes del cálculo de la matriz del cierre transitivo. Finalmente (c) presenta el
resultado del algoritmo de etiquetado.
- 111 -
Capítulo 4 –Segmentación
- 112 -
Capítulo 4 –Segmentación
Análogamente, el píxel (x’, y’), vecino de (x, y), tiene un ángulo similar a
éste si y sólo si:
|a(x,y) - a(x’,y’)| £ A
Bordes Sobel
Bordes Laplace
SI
NO
Bordes sin ruido
¿Cambios?
y conexos
Figura 68.- Método para la obtención de bordes continuos en una imagen digital.
- 113 -
Capítulo 4 –Segmentación
- 114 -
Capítulo 4 –Segmentación
(a) (b)
Figura 69.- La cuadrícula representa un mapa de píxeles sobre el que se superpone el grafo
de los bordes: (a) direcciones de los bordes, y (b) grafo correspondiente.
Paso 1.- Expandir el nodo origen nO y poner todos sus sucesores {ni} en una lista L. En ella
todos los nodos tiene un puntero “hacia detrás” a nO. Evaluar la función de coste r(ni) a todo
nodo expandido ni desde nO, que inicialmente valdrá c(nO, ni) según la expresión (4.1).
Paso 2.- Si la lista L es vacía, acabar con fallo; en otro caso, determinar el nodo nj de la lista
L cuya función de coste asociada r(nj) sea la menor y quitar nj de la lista L. Si nj = nD (nodo
final del camino), recorrer el camino de punteros “hacia detrás”, encontrar el valor mínimo
y acabar con éxito.
Paso 3.- Si la opción de parar no fue tomada en el paso 2, expandir el nodo especificado nj
y poner sus sucesores en la lista L con punteros “hacia detrás” a nj. Calcular los costes
según la función r (si nk es un sucesor de nj en L, su coste viene dado por el coste r(nj) para
ir de ni a nj más el coste del arco c(nj, nk) ). Volver al paso 2.
Transformada de Hough
Al igual que las técnicas basadas en grafos, la transformada de Hough es un
método de análisis global que se diseñó para detectar líneas rectas y curvas a
partir de las posiciones de n puntos. Una ventaja de esta técnica es la robustez de
los resultados de segmentación conseguidos al aplicarla; sin embargo, su coste
computacional es elevado.
- 116 -
Capítulo 4 –Segmentación
y i = a xi + b (4.2)
siendo a y b, los parámetros que determinan las infinitas rectas que pasan por el
punto (xi,yi). Para otro punto (xj,yj), las rectas que pasan por él siguen la ecuación:
y j = a xj + b (4.3)
donde a y b son parámetros variables de nuevo. La recta que pasa a la vez por
(xi,yi) y por (xj,yj) tiene como valores de los parámetros (a,b) el resultado de
resolver el sistema planteado por (4.2) y (4.3), que llamaremos a’ y b’.
y b
b' (x2,y2)
=a'x+
y b'
(x1,y1)
x a' a
(a) (b)
Figura 71.- Representación de la recta y = a’x + b’ en el espacio (x,y) y en el espacio de
parámetros (a,b).
- 117 -
Capítulo 4 –Segmentación
xi×cosq + yi×senq = r
siendo q y r los nuevos parámetros que determinan los infinitos puntos que pasan
por xi e yi. Nótese que en esta ecuación el parámetro q está acotado en el intervalo
[0,p].
Ejemplo 12.-
Determinar las dos rectas que con mayor probabilidad aparecen en la imagen de la
Figura 72, obtenida mediante un filtrado de Sobel.
x
0 1 2 3 4 5 6 7
y
0
1
2
3
4
5
6
- 118 -
Capítulo 4 –Segmentación
Tabla 4.- Representación del valor de r a partir de las coordenadas de un punto (x,y) y del
ángulo q.
Tabla 5.- Representación del conteo de los valores de parámetros considerados, que
describen las rectas más probables que aparecen tras la aplicación de la transformada
Hough.
- 119 -
Capítulo 4 –Segmentación
120º 90º
0 1 2 3 4 5 6 7
0
1
2
3
4
5
6
imagen se les agregan otros adyacentes si tienen valores que cumplen cierto
criterio definible de homogeneidad con los de los puntos semilla. Si ocurre esto,
pertenecen a la misma región y pasan a tener los mismos valores que los puntos
semilla. El criterio de agregación más usual suele consistir en que un píxel,
adyacente a una región, se agregue a ésta si su intensidad es similar a la media de
las intensidades de los píxeles de la región. El principal inconveniente del método
se deriva de que el resultado depende de la elección inicial de los puntos semilla.
Figura 74.- Segmentación de objetos por unión de regiones. Las regiones correspondientes
a los colores amarillo, rojo azul y verde crecen por agregación de píxeles con matiz similar.
utilizados para dividir regiones son similares a los usados para agruparlas, y sólo
se diferencian en la dirección en que se aplican.
- 122 -
Capítulo 4 –Segmentación
A B
A
C D
A
A B C D C D
A B C D
C D
A B C D
(a) (b)
- 123 -
Capítulo 4 –Segmentación
- 124 -
Capítulo 4 –Segmentación
Figura 77.- Una imagen que ilustra el símil del watershed en una superficie de un terreno.
- 125 -
Capítulo 4 –Segmentación
· Filtrar las imágenes para dejar sólo las zonas importantes de ella.
- 126 -
Capítulo 4 –Segmentación
Paso 1.- Se calculan las características de color usando los valores de las componentes de
los planos rojo, verde y azul de una imagen RGB.
Paso 2.- La imagen se divide en regiones cuadradas de igual tamaño, usando la estructura
de datos de árbol cuaternario o “quadtree”.
Paso 3.- Cuatro cuadrantes situados a un mismo nivel de subdivisión son mezclados si se
satisface un cierto criterio de homogeneidad. Un cuadrante se subdivide en otros cuatro si
no se satisface una condición de homogeneidad.
- 127 -
Capítulo 4 –Segmentación
20
Random fields en inglés
- 128 -
Capítulo 4 –Segmentación
- 129 -
Capítulo 4 –Segmentación
ì1 si I t ( x, y ) - I t ( x, y ) > 0
d t ,t +1 ( x, y ) = í
î0 en otro caso
1 3 2 1
2 0 4 0
3 5 6 7
- 130 -
Capítulo 4 –Segmentación
Ejemplo 13.-
(a) (b)
Figura 81.- Recorrido del objeto usando código de cadena de conectividad 4. El punto
grueso indica el nodo de inicio.
- 131 -
Capítulo 4 –Segmentación
¥ ¥
m pq = ò ò x p y q f ( x, y )dxdy p, q = 0,1,....¥
- ¥ -¥
Se puede ver que, para una función acotada en el plano, existen infinitos
momentos generales obtenidos haciendo variar p y q de cero a infinito.
Se puede demostrar que dado una función f(x,y) existe un único conjunto
de momentos generales que la definen y viceversa.
f ( x, y ) « {m pq } p, q = 0,1,....¥
N -1 N -1
m pq = åå x p y q I D ( x, y ) p, q = 0,1,....¥
x = 0 y =0
siendo ID(x,y) una función discreta que toma valor 1 cuando el píxel pertenece al
objeto y 0 cuando pertenece al fondo.
N -1 N -1
m00 = åå I D ( x, y )
x = 0 y =0
Los momentos de orden uno (p=0, q=1 y p=1, q=0), junto con el de orden
cero, determinan el centro de gravedad de los objetos.
- 132 -
Capítulo 4 –Segmentación
N -1 N -1 N -1 N -1
m10 = åå xI D ( x, y ) m01 = åå yI D ( x, y )
x =0 y = 0 x = 0 y =0
Invarianza a traslaciones
Los momentos generales se pueden hacer invariantes a las traslaciones. Para ello
basta con referirlos al centro de gravedad del objeto, es decir a los momentos de
orden cero y uno. Estos momentos, que se conocen como momentos centrales,
tienen la siguiente forma:
N -1 N -1
mc pq = åå ( x - x ) p ( y - y ) q I D ( x, y ) p, q = 0,1,....¥
x = 0 y =0
p q
æ p öæ q ö
mc pq = åå çç ÷÷çç ÷÷(- x ) r (- y ) s m p -r ,q - s p, q = 0,1,....¥
r = 0 s = 0 è r øè s ø
Invarianza a giros
La invarianza a giros se consigue tomando una dirección de referencia para cada
objeto. La dirección que se suele tomar es la que marca el eje de mínima inercia
del objeto. Este eje se calcula teniendo en cuenta la definición de inercia:
I = åå [( x - a ) senq - ( y - b) cosq ] I D ( x, y )
2
x y
El eje de mínima inercia será aquél que haga cero las derivadas parciales
respecto a cada variable:
dI dI dI
=0 =0 =0
dx dy dq
1 æ 2mc11 ö
a=x b=y q= arctg çç ÷÷
2 è mc 20 - mc02 ø
p q
æ p öæ q ö
mcg pq = åå (-1) q - s çç ÷÷çç ÷÷(cosq ) p - r + s ( senq ) q - s + r mc p - r + q - s ,r + s
r =0 s = 0 è r øè s ø
p, q = 0,1,....¥
mcg pq p+q
mcgh pq = g
donde g = y p, q = 0,1,....¥
m 00 2
Invarianza a traslaciones
Las componentes de Fourier de dos objetos iguales, que se hallen desplazados uno
respecto a otro, sólo se diferencian en la componente de frecuencia cero (F(0)).
Por tanto, la eliminación de esta componente proporciona una descripción
invariante a traslaciones.
- 134 -
Capítulo 4 –Segmentación
Invarianza a giros
La transformada de Fourier de un objeto girado q radianes respecto a otro igual
pero que no está girado se diferencia en un factor multiplicativo ejq. Por ello, suele
usarse sólo los módulos que no cambian si el objeto está girado.
[SHB99] cap. 5
- 135 -
Capítulo 4 –Segmentación
- 136 -
Capítulo 5 Introducción a los
clasificadores
21
En el resto del capítulo se usarán las mayúsculas para los vectores.
- 137 -
Capítulo 5 –Introducción a los clasificadores
Conocimiento
respecto a las
clases
- 138 -
Capítulo 5 –Introducción a los clasificadores
Ejemplo 14.-
Figura 83.- Muestra de las diferentes piezas entre las que se desea distinguir, obtenidas con
una cámara e iluminación a contraluz.
1
Número de agujeros
Tornillos
Tuercas
Arandelas
Cuando la muestra es abundante suele crearse otro conjunto con ella. Este
segundo conjunto se utiliza para probar los resultados de las funciones
discriminantes calculadas, y se conoce como conjunto de test. Es importante que
estos dos conjuntos sean independientes, como norma general, en el caso de un
universo de trabajo grande, es suficiente con asegurar que el conjunto de
aprendizaje y el test no tengan elementos en común. De esta forma puede probarse
que el clasificador desarrollado ha adquirido la propiedad de generalización. Esta
propiedad garantiza que un sistema clasifica correctamente patrones que no ha
visto durante el proceso de cálculo de funciones discriminantes.
- 140 -
Capítulo 5 –Introducción a los clasificadores
Hay autores que recomiendan tomar alrededor del 60% de la muestra para
construir el conjunto de aprendizaje, un 30% para el conjunto de test y el 10%
restante para el conjunto de validación.
Validación cruzada
Cuando la muestra es escasa, puede no ser factible utilizar el 40% de la misma
para realizar las pruebas, ya que en tal caso, no se dispondría del suficiente número
de ejemplos para poder calcular las funciones discriminantes de manera correcta.
Como utilizar el mismo conjunto para el aprendizaje y para el test ya se ha dicho
que no es aconsejable, se suele usar un procedimiento que, si bien es mucho más
lento, permite obtener una prueba estadísticamente significativa y además permite
usar toda la muestra para calcular las funciones discriminantes.
Con este procedimiento se consigue realizar una prueba que cumple los
principios necesarios para probar la propiedad de generalización. Luego, una vez
demostrada esta propiedad, se construye el sistema utilizando toda la muestra. Este
método presenta el problema de la lentitud, y de que no se prueba el sistema final,
sino que se prueban una serie de sistemas similares al final. Sin embargo, es una
solución válida cuando la muestra es necesariamente reducida.
22
cross-validation en inglés
- 141 -
Capítulo 5 –Introducción a los clasificadores
Economía
El mecanismo preciso para el cálculo o la obtención de las características
discriminantes (sensores, etc..) debe tener un coste razonable.
Velocidad
El tiempo de cálculo no debe superar el umbral que lo haga inviable.
Independencia
Las características no deben estar correladas entre ellas. Una característica que
depende fuertemente del resto no añade información discriminante y por tanto
puede eliminarse sin que esto suponga ninguna pérdida de capacidad
discriminante.
P
c X ,Y = å ( X p - m X )(Y p - mY )
p =0
- 142 -
Capítulo 5 –Introducción a los clasificadores
æ ( X p1 - mk 1 )( X p1 - mk 1 ) ... ( X p1 - mk 1 )( X pN - mkN ) ö
ç ÷
1 Pk
ç ( X p 2 - mk 2 )( X p1 - mk 1 ) ... ( X p 2 - mk 2 )( X pN - mkN ) ÷
Ck = å
Pk p =1 çç ... ... ... ÷
÷
ç ( X - m )( X - m ) ... ( X pN - mkN )( X pN - mkN ) ÷ø
è pN kN p1 k1
1
mk =
Pk
åX " X que peretenece a la clase a k
independientes, entonces el valor de rij debe estar próximo a cero23. Por otro lado,
valores cercanos a –1 ó 1 para rij indican relaciones lineales entre las
características i y j.
cij
rij = " i,j = 1,2 ... N
cii × c jj
Fiabilidad
La fiabilidad implica que objetos de la misma clase deben tener vectores de
características con valores numéricos similares. Esto se cumple si los vectores de
características de una clase tienen poca dispersión. La dispersión se puede medir
sobre la diagonal de la matriz de covarianzas. Cuanto mayores son los valores de la
diagonal, mayor es la dispersión.
Capacidad discriminante
La capacidad discriminante se puede describir como la exigencia de que los
vectores de características de clases distintas tienen que tener valores numéricos
distintos.
( mi - m j ) 2 1 Pi
Fij =
s i2 + s 2j
, donde si =
N
å(X
p =1
p - mi ) 2
23
La independencia lineal entre dos características i y j no implica la independencia
estadística, ya que pueden existir dependencias no lineales. Por el contrario, la dependencia
lineal sí implica dependencia estadística.
- 144 -
Capítulo 5 –Introducción a los clasificadores
K
1
K
å (m
j =1
j - m)2
F= KPk
1
åå
K × P k =1 i =1
( X ki - mk ) 2
siendo
P K
1
m=
N
åmj
j =1
y P = å Pk
k =1
Fuerza bruta
Se construyen todos los conjuntos posibles de características y se selecciona al
que mejor cumpla los criterios de selección. Este procedimiento garantiza
- 145 -
Capítulo 5 –Introducción a los clasificadores
Eliminación
En principio se calcula el rendimiento de N-1 clasificadores resultantes de quitar
una característica distinta cada vez al conjunto de N características. Se elige el
vector de características de aquel clasificador en el que la reducción del
rendimiento sobre el inicial es menor.
Incorporación
Se van añadiendo características siguiendo el criterio de añadir aquélla que
provoca un mayor incremento del rendimiento. Éste es el modo más rápido de
obtener un buen conjunto, aunque generalmente no se obtiene el óptimo.
- 146 -
Capítulo 5 –Introducción a los clasificadores
- 147 -
Capítulo 5 –Introducción a los clasificadores
dE (X , Zk ) = X T × X - 2 × X T × Z k + Z kT × Z k (5.1)
- 148 -
Capítulo 5 –Introducción a los clasificadores
a1
Así, para el caso de K clases: a1, a2, ... aK, se necesitan K prototipos: Z1,
Z2 ... ZK. Al clasificar un patrón se sigue el esquema de la Figura 86. Según este
esquema, para clasificar el patrón X se calcula la distancia del vector de
características X a los vectores de características de cada uno de los K prototipos
(Z1, Z1 ... ZK), clasificando X como perteneciente a la clase cuyo prototipo esté más
próximo.
fd1(x)
dE(x,z1)
fd2(x)
dE(x,z2)
X? Xi
Mínimo
.
.
.
fdN(x)
dE(x,zN)
- 149 -
Capítulo 5 –Introducción a los clasificadores
1 T
fd k ( X ) = X T × Z k - Zk × Zk " k = 1…K (5.2)
2
Pk
1
Zk =
Pk
åX
p =1
p " X p patrón de la clase a k
Ejemplo 15.-
æ 1ö æ7ö
ç ÷ ç ÷
ç 3÷ ç8÷
z1 = ç ÷ z2 = ç ÷
5 1
ç ÷ ç ÷
ç 1÷ ç7÷
è ø è ø
T T
æ1ö æ 1ö æ 1ö æ 7ö æ 7ö æ7ö
ç ÷ ç ÷ ç ÷ ç ÷ ç ÷ ç ÷
r T ç 3÷ 1 ç 3÷ ç 3÷ r T ç 8÷ 1 ç 8÷ ç8÷
fd 1 = X ç ÷ - ç ÷ ç 5÷ y fd 2 = X ç ÷ - ç ÷ ç1÷
5 2 5 1 2 1
ç ÷ ç ÷ ç ÷ ç ÷ ç ÷ ç ÷
ç1÷ ç 1÷ ç 1÷ ç 7÷ ç 7÷ ç7÷
è ø è ø è ø è ø è ø è ø
- 150 -
Capítulo 5 –Introducción a los clasificadores
T T
æ 3ö æ1ö æ 1ö æ1ö
ç ÷ ç ÷ ç ÷ ç ÷
ç 1÷ ç 3÷ 1 ç 3÷ ç 3÷ 1
fd 1 = ç ÷ ç 5÷ - 2 ç 5÷ ç 5 ÷ = 3 + 3 + 15 + 1 - 2 (1 + 9 + 25 + 1) = 4
3
ç ÷ ç ÷ ç ÷ ç ÷
ç 1÷ ç1÷ ç 1÷ ç1÷
è ø è ø è ø è ø
T T
æ 3ö æ7ö æ 7ö æ7ö
ç ÷ ç ÷ ç ÷ ç ÷
ç 1÷ ç 8÷ 1 ç 8÷ ç8÷ 1
fd 2 = ç ÷ ç 1÷ - 2 ç 1÷ ç 1 ÷ = 21 + 8 + 3 + 7 - 2 (49 + 64 + 1 + 49) = -42.5
3
ç ÷ ç ÷ ç ÷ ç ÷
ç 1÷ ç7÷ ç 7÷ ç7÷
è ø è ø è ø è ø
d M ( X , a k ) = ( X - mk ) T × C k-1 × ( X - mk ) (5.3)
- 151 -
Capítulo 5 –Introducción a los clasificadores
a1
a2
Figura 87.- En un clasificador estadístico la región de separación no es determinista.
Además crea separaciones no lineales de dos clases (curvas cónicas como las parábolas,
elipses, hipérbolas y, por su puesto, rectas).
a2
a1
m1 fd m2
Clasificación probabilista
Cuando existe diferente dispersión de los valores de una característica en dos o
más clases una medida de la distancia que tenga en cuenta la desviación típica
ofrecerá mejores resultados. La Figura 88 ejemplifica la disposición de los
patrones de dos clases respecto de una característica particular. En la figura se
- 152 -
Capítulo 5 –Introducción a los clasificadores
P ( X / a i ) × P(a i )
P(a i / X ) =
P( X )
donde,
K
P( X ) = å P ( X / a k ) P(a k )
k =1
XÎai Û P(ai /X) > P(aj /X) " i¹j, j = 1,2 ... N
Como P(X) es un término constante para todos los cálculos de P(ai /X), el
cálculo puede simplificarse eliminando ese factor. Con esto la función
discriminante para la clase ai es:
- 153 -
Capítulo 5 –Introducción a los clasificadores
Y se dice que:
1 ( X - mi ) 2
-
1 2 s i2
P( X / a i ) = e " i = 1,2 ... N
2p × s i
( X - m1 ) 2 ( X - m2 ) 2 s
< + 2 ln( 2 )
s12
s22
s1
- 154 -
Capítulo 5 –Introducción a los clasificadores
1 r T -1 r r T -1 r 1 r T -1 r 1
fd i ( X ) = - X C i X + X C i mi - mi C i mi - ln C i " i = 1,2 ... N
2 2 2
r r 1 r r
fd i ( X ) = X T C i-1 mi - miT C i-1 mi " i = 1,2 ... N
2
r r 1 r
fd i ( X ) = X T mi - miT mi " i = 1,2 ... N
2
Hay que señalar que en la práctica los valores que se obtienen para las
desviaciones nunca son exactamente iguales, ni las covarianzas son exactamente
cero, pero estas reglas se aplican igualmente si se aproximan suficientemente a
tales valores.
Ejemplo 16.-
ìæ 1 ö æ 2 ö æ 3ö æ 2 ö æ 3 öü ìæ 8 ö æ 9 ö æ 9 ö æ 8 ö æ 7 öü
a 1 : íçç ÷÷, çç ÷÷, çç ÷÷, çç ÷÷, çç ÷÷ý a 2 : íçç ÷÷, çç ÷÷, çç ÷÷, çç ÷÷, çç ÷÷ý
îè 2 ø è 2 ø è 1 ø è 3 ø è 2 øþ îè10 ø è 8 ø è 9 ø è 9 ø è 9 øþ
- 155 -
Capítulo 5 –Introducción a los clasificadores
1 T -1
fd i ( X ) = X T C -1 mi - mi C mi
2
obteniendo:
æ 50 25 ö
ç ÷
C -1 = ç 23 23 ÷
ç 25 70 ÷
ç ÷
è 23 23 ø
y por tanto:
Maestro
X?
X Error
Reconocedor
Minimiza el
error
- 157 -
Capítulo 5 –Introducción a los clasificadores
Algoritmo de aprendizaje
Los algoritmos de aprendizaje parten de unas funciones discriminantes al azar y
las van mejorando sucesivamente hasta que obtienen funciones discriminantes que
clasifican correctamente la mayor parte de los patrones del universo de trabajo.
Error
w2
w1
Figura 90.- El error debe verse como una superficie función de los parámetros W del
clasificador. Para unos W dados se obtiene un error determinado. La derivada marca la
dirección con la que disminuye el error.
- 158 -
Capítulo 5 –Introducción a los clasificadores
¶Error
W (t + 1) = W (t ) - m (5.4)
¶W
Para el caso que nos ocupa se toma la siguiente función para el error:
1
Error = ( fdm - WiT X ) 2
4
siendo:
- 159 -
Capítulo 5 –Introducción a los clasificadores
ì+ 1 si X Îai
fdm = í
î- 1 si X Ïai
e = ( fdm - WiT X )
se obtiene que:
¶Error 1 1
ÑError = = 2( fdm - WiT X )(- X ) Þ ÑError = - eX
¶W 4 2
y por tanto:
1
W (t + 1) = W (t ) + m eX
2
Esta expresión muestra como deben cambiarse los pesos de todas las
funciones discriminantes en cada iteración para que el error disminuya
progresivamente. El algoritmo se repite hasta que el error cae por debajo de un
mínimo admisible, o hasta que los vectores W converjan.
Se inician al azar los valores de Wi. Se inicia t = 0 y p = 0. Se fija un nivel de error máximo
aceptable E.
Paso 2.- Se presenta la muestra de entrenamiento Xp (que el maestro sabe que pertenece a
ak) y se calculan las K funciones discriminantes.
- 160 -
Capítulo 5 –Introducción a los clasificadores
Paso 3.- Para cada fd calcular el error que se comete. Si el error es menor al E fijado
PARAR, en otro caso actualizar W según:
Ejemplo 17.-
Determinar los vectores W1, W2 y W3 de las funciones discriminantes fd1, fd2 y fd3
para el problema de clasificación de las tres clases dadas por los siguientes tres
patrones.
æ1ö æ 0ö æ0ö
ç ÷ ç ÷ ç ÷
x1 = ç 0 ÷ Î a 1 , x 2 = ç 1 ÷ Î a 2 , x3 = ç 0 ÷ Î a 3
ç 0÷ ç 1÷ ç - 1÷
è ø è ø è ø
Se obtiene en t = 1: T
fd3(X(2)) = W3(2) × X(2) = 0
X(1) = x1 Î a1
error1(2) = -1
T
fd1(X(1)) = W1 (1 ) × X(1) = 0 error2(2) = 1
T error3(2) = -1
fd2(X(1)) = W2(1) × X(1) = 0
T W1(3) = W1(2) - e×m×X (2) = (1, -1, -1)
fd3(X(1)) = W3(1) × X(1) = 0
W2(3) = W2(2) + e×m×X (2) = (-1, 1, 1)
error0(1) = 1
W3(3) = W3(2) - e×m×X (2) = (-1, -1, -1)
error1(1) = -1
Se obtiene en t = 3:
error2(1) = -1 X(3) = x3 Î a3
W1(2) = W1(1) + e×m×X (1) = (1, 0, 0) T
W2(2) = W2(1) - e×m×X(1) = (-1, 0, 0) fd1(X(3)) = W1(3) × X(3) = 1
T
W3(2) = W3(1) - e×m×X(1) = (-1, 0, 0) fd2(X(3)) = W2(3) × X(3) = -1
Se obtiene en t = 2: T
fd3(X(3)) = W3(3) × X(3) = 1
X(2) = x2 Î a2
error1(3) = -2
T
fd1(X(2)) = W1(2) × X(2) = 0 error2(3) = 0
T error3(3) = 0
fd2(X(2)) = W2(2) × X(2) = 0
- 161 -
Capítulo 5 –Introducción a los clasificadores
- 162 -
Como se ha completado una pasada del clasificador con todos los patrones de
la muestra y no han cambiado los coeficientes W se termina el proceso de
entrenamiento. Las funciones discriminantes obtenidas son:
æ x1 ö
ç ÷
fd 1 ( X ) = (1 - 2 1) × ç x 2 ÷ = x1 - 2 x 2 + 1
ç1÷
è ø
æ x1 ö
ç ÷
fd 2 ( X ) = (- 1 0 1) × ç x 2 ÷ = - x1 + 1
ç1÷
è ø
æ x1 ö
ç ÷
fd 3 ( X ) = (- 1 0 - 1) × ç x 2 ÷ = - x1 - 1
ç1÷
è ø
- 163 -
Capítulo 5 –Introducción a los clasificadores
donde esta sucesión es tal que el siguiente vector de la cadena es el más próximo al
anterior según la distancia euclídea. Es decir Xi(1) es el más próximo a Xi(0), Xi(2)
es el más próximo a Xi(1), etc. Siendo Xi(0) = Xi.
- 164 -
Capítulo 5 –Introducción a los clasificadores
- 165 -
Capítulo 5 –Introducción a los clasificadores
Paso 1.- Se fija una valor umbral h. Se toma al azar un elemento de los P disponibles y se
toma como representante de la clase a1.
Paso 2.- Se calculan las distancias euclídeas del representante de a1 a los P-1 vectores no
agrupados y se toma la máxima distancia, formando una nueva clase con aquél vector que la
maximiza como representante.
Paso 3.- Se distribuyen los restantes vectores en alguna de las clases existentes, anotando el
vector V que esté a mayor distancia de su respectivo representante.
Este algoritmo goza de una amplia difusión debido a que es simple, a que
suele ofrecer unos resultados fiables, y a que no depende de ningún umbral
heurístico. Tiene la desventaja de que es preciso conocer de antemano el número
de clases en que se divide la muestra. Aunque esto, en las ocasiones en que se
dispone de tal dato, es más una ventaja que un inconveniente. También debe
- 166 -
Capítulo 5 –Introducción a los clasificadores
t=0 t=1
t=2 t = 3,4...
- Algoritmo k Medias -
Paso 1.- Se hace t = 1. Se toma al azar k vectores de los P existentes y se convierten en
centroides de cada una de las k clases respectivamente.
Z1(1) de a1
...
Zk(1) de ak
Paso 2.- Se distribuyen las P-k muestras restantes entre las k clases. Se asigna cada vector a
la clase que esté más próxima.
Paso 3.- Se calcula los centroides de las clases como la media ponderada de los vectores de
cada clase.
Paso 4.- Si alguno de los k centroides Zk(t) es distinto de los nuevos centroides Zk(t+1)
hacer t = t+1 e ir al paso 2, en otro caso finalizar el algoritmo.
- 167 -
Capítulo 5 –Introducción a los clasificadores
24
Entre estas técnicas se pueden citar el algoritmo del elemento más votado, el algoritmo
de la votación promediada y el algoritmo BKS. El primero devuelve el resultado del
clasificador que más se repita. El segundo devuelve el resultado del clasificador que
promediado con los demás con cierto coeficiente obtenga un resultado más alto. El último
utiliza los resultados de N clasificadores sobre una muestra de ensayo para construir una
matriz de dimensión N que ofrece resultados para cada combinación de resultados de los N
clasificadores.
- 168 -
Capítulo 5 –Introducción a los clasificadores
[Mar93] caps. 2, 4 y 6,
[Loo97] cap. 5
- 169 -
Capítulo 6 Introducción a la
Visión Tridimensional
Cuando un búho acecha una presa realiza rápidos y precisos movimientos con la
cabeza. Estos movimientos le permiten obtener distintas perspectivas de la escena
que observa. El cerebro del búho usa estas diferentes perspectivas para calcular
con precisión la distancia y la posición exacta en la que se encuentra su próximo
bocado.
- 171 -
Capítulo 6 – Introducción a la Visión Tridimensional
- 172 -
Capítulo 6 – Introducción a la Visión Tridimensional
I
P(x, y, z)
v f
u d
C
a
P’(u, v)
Figura 92.- Modelo Pin-Hole o perspectiva cónica. Obsérvese que todos los puntos de la
recta CP se proyectan en el mismo punto P’ de la imagen.
- 173 -
Capítulo 6 – Introducción a la Visión Tridimensional
P(x, y, z)
I
f d
C
-v a
P’(u, v)
r r r r r r
v d ×v d × v × cos( d ,v)
- = r r= r r r r
f d × a d × a × cos(d , a )
Por último, sólo resta transformar las coordenadas (u, v) del plano de
formación de la imagen en coordenadas (i ,j) del plano digital de la imagen. Para
hacer esta transformación se debe tener en cuenta la relación de tamaño de los
píxeles dentro del plano de formación de la imagen, por lo que se llamará al ancho
de un píxel m, y al alto n. También se deben conocer las coordenadas (i0, j0) del
punto del plano digital de la imagen que se corresponden con las del centro del
plano de formación de la imagen.
- 174 -
Capítulo 6 – Introducción a la Visión Tridimensional
Cuando u vale 0, i vale i0, y cuando i vale i0+1 u toma valor igual al ancho
de un píxel, es decir m. Aplicando un razonamiento similar para calcular la
relación entre j y v se obtienen las igualdades:
u = m (i - i0)
v = - n (j - j0)
6.1.2 Calibración
Las ecuaciones (6.1) y (6.2) permiten conocer la relación entre los píxeles de una
imagen digital, y los puntos de los que son proyección en la escena tridimensional.
No debe pasarse por alto, sin embargo, que es preciso obtener los valores de todos
los parámetros que aparecen en estas ecuaciones. La calibración es el proceso que
se encarga de determinar los valores de los parámetros que intervienen en el
proceso de formación de la imagen. En este modelo la calibración consiste
precisamente en obtener el valor de los parámetros de estas ecuaciones (ver Tabla
6).
- 176 -
Capítulo 6 – Introducción a la Visión Tridimensional
Cálculo matricial
En el siguiente apartado se realiza un desarrollo que llevará a una formulación que
permitirá realizar el proceso de calibración de una manera sencilla.
Llamando
r r r r r r r
l = (P - C) × a Þ l = a t P - a t C
se obtiene el sistema
ì f rt r f rt r
ï i l = - u P + u C + i0 l
m m
ïï f rt r f rt r
í jl = v P - v C + j 0 l
ï n r rn r r
ï l = at P - atC
îï
que se puede escribir en forma matricial, poniendo atención a la matriz central que
sólo contiene parámetros intrínsecos.
- 177 -
Capítulo 6 – Introducción a la Visión Tridimensional
æ- f ö
ç 0 i0 ÷ r t r r t r
æ l ×i ö ç m ÷ æç u Pr - u Cr ö÷
ç ÷ ç f r r
çl × j÷ = ç 0 j0 ÷ × ç v t P - v t C ÷
n ÷ ç rt r rt r ÷
ç l ÷ ç
è ø 0 0 1 ÷ çè a P - a C ÷ø
ç ÷
è ø
æ- f ö
ç 0 i0 ÷ r r æ xö
æ l ×i ö ç m ÷ æç u x uy uz - u tC ö ç ÷
ç ÷ ç f r r ÷ ç y÷
çl × j÷ = ç 0 j0 ÷ × ç v x vy vz - v tC ÷ × ç ÷ Þ
n ÷ ç r r÷ z
ç l ÷ ç
è ø 0 0 1 ÷ çè a x ay az - a t C ÷ø çç ÷÷
ç ÷ è 1ø
è ø
æ- f ö
ç 0 i0 ÷ r rt r æ xö
æ l ×i ö ç m ÷ æç u - u Cr ö÷ ç ÷
ç ÷ ç f r r ç y÷
çl × j÷ = ç 0 j0 ÷ × ç v - v t C ÷ × ç ÷
n ÷ çr rt r ÷ z
ç l ÷ ç
è ø 0 0 1 ÷ çè a - a C ÷ø çç ÷÷
ç ÷ è1ø
è ø
- 178 -
Capítulo 6 – Introducción a la Visión Tridimensional
æ xö
æ l ×i ö ç ÷
ç ÷ r ç y÷
ç l × j ÷ = K × [R t ] × ç ÷
ç l ÷ z
è ø ç ÷
ç 1÷
è ø
æ xö
æ l × i ö æ w1,1 w1, 2 w1,3 w1, 4 ö ç ÷
ç ÷ ç ÷ ç y÷
ç l × j ÷ = ç w2,1 w2 , 2 w2 , 3 w2 , 4 ÷ × ç ÷
ç l ÷ çw z
è ø è 3,1 w3, 2 w3,3 w3, 4 ÷ø çç ÷÷
è1ø
25
Esto no es posible cuando el ángulo que forma el plano de la imagen con el eje axial de la
cámara es distinto de cero. En estos casos es posible tal cambio si se introduce un parámetro
d en la posición (1,2) de la matriz de intrínsecos.
- 179 -
Capítulo 6 – Introducción a la Visión Tridimensional
æ w1,1 ö
ç ÷
ç w1, 2 ÷
çw ÷
ç 1,3 ÷
ç w1, 4 ÷
çw ÷
ç 2,1 ÷
æ x y z 1 0 0 0 0 - xi - yi - zi - i ö ç w2, 2 ÷
çç ÷÷ × ç ÷=0
è 0 0 0 0 x y z 1 - xj - yj - zj - j ø ç w2,3 ÷
ç w2, 4 ÷
ç ÷
ç w3,1 ÷
çw ÷
ç 3, 2 ÷
ç w3,3 ÷
çw ÷
è 3, 4 ø
O más concisamente:
æ x y z 1 0 0 0 0 - xi - yi - zi - i ö
çç ÷÷ × W = 0
è 0 0 0 0 x y z 1 - xj - yj - zj - j ø
26
Puesto que se trabaja con coordenadas homogéneas la escala es irrelevante. En este caso
es posible establecer por ejemplo el valor de w3,4 a 1 y el resultado no cambiará. Así, el
sistema tendrá 12 ecuaciones y 11 incógnitas y estará sobredeterminado. En este caso puede
utilizarse algoritmos de minimización del error, como el método de mínimos cuadrados,
para estimar W en vez de proceder a su cálculo directo.
- 180 -
Capítulo 6 – Introducción a la Visión Tridimensional
El problema de correspondencia
Sin embargo, el uso de más de una imagen plantea un problema que se conoce
como el problema de correspondencia. Este problema se plantea al intentar hacer
corresponder los puntos de 2 imágenes digitales distintas. Es decir, conociendo las
coordenadas (i1, j1) de un píxel dentro de la imagen digital I1 que corresponde a un
punto P de una escena tridimensional, cuáles son las coordenadas (i2, j2)
correspondientes a la representación del mismo punto P en la imagen digital I2.
Este problema se resuelve encontrando la homografía entre los puntos P1 y P2.
Siendo una homografía una transformación que relaciona las diferentes
proyecciones de un punto.
Restricción epipolar
Existe una propiedad geométrica, que posee todo sistema de visión estéreo, que
ayudará a resolver el problema de correspondencia. Esta propiedad se conoce
como la restricción epipolar.
- 181 -
Capítulo 6 – Introducción a la Visión Tridimensional
r r
l 2 × P2 = K 2 × [R2 t 2 ]× P
C1 E1
C2
P1
I2
P2
I1
-1 r
l 2 × P2 = K 2 × R2 × K 1 × l 1× P1 + K 2 × t 2 Þ
- 182 -
Capítulo 6 – Introducción a la Visión Tridimensional
-1 r
l 2 × P2 = l 1× K 2 × R2 × K 1 × P1 + K 2 × t 2 (6.4)
14 4244 3 123
H¥ e
l 2 × P2 = l 1× H ¥ × P1 + e
-1 -1 r
l 2 × K 2 × P2 = l 1× R2 × K 1 × P1 + t 2
[ -1
]
l 2 × t ´ K 2 × P2 = l 1× t ´ R2 × K 1 × P1
-1
Multiplicando por K 2 [ -1
] [
× P2 que es perpendicular a t ´ K 2 × P2 se
-1
]
obtiene:
[ -1
]
0 = l 1× K 2 × P2 × t ´ R2 × K 1 × P1 Þ
-1
-1 -1
0 = P2 × K 2 × t ´ R2 × K 1 × P1 Þ
144 42444 3
F
0 = P2 × F × P1 (6.5)
- 183 -
Capítulo 6 – Introducción a la Visión Tridimensional
- 184 -
Capítulo 6 – Introducción a la Visión Tridimensional
- 185 -
Capítulo 6 – Introducción a la Visión Tridimensional
Así por ejemplo son métodos activos: aquéllos en los que se proyectan
haces controlados de energía (luz o sonido sobre la escena) desde una posición y
orientación conocida, o los que utilizan un observador activo (aquél que se
encuentra implicado en algún tipo de actividad encaminada a controlar la
geometría utilizada para la discretización). Como método pasivo se puede citar el
que se ha descrito en este capítulo basado en visión estereoscópica.
Tiempo de vuelo
Método activo en el que se mide el tiempo invertido por una señal de velocidad
conocida en recorrer la distancia que separa una región de la escena del dispositivo
emisor-receptor. La señal suele ser de naturaleza acústica o electromagnética.
- 186 -
Capítulo 6 – Introducción a la Visión Tridimensional
Inferometría de Moiré
El motivo de interferencia obtenido al iluminar y observar una escena a través de
sendos dispositivos idénticos de tipo rejilla permite la recuperación de la
información tridimensional. Se basa en que la superposición de dos motivos de la
misma frecuencia espacial produce una interferencia de baja frecuencia que
únicamente varía con la diferencia de fase. Los inconvenientes son que los
gradientes de la superficie del objeto han de ser acotados, y ha de existir
continuidad. La Figura 96 muestra la disposición de un sistema de este tipo.
rejilla rejilla
proyector de luz
cámara
P(x,y,z)
Z
b
X
f
p(U,V)
Proyecto Cámara
r
Figura 97.- Disposición de un sistema de visión 3D mediante proyección de luz
estructurada. La obtención de puntos 3D se basa en el método de triangulación activa:
conocidos b, f, U y V, es posible obtener las coordenadas 3D de P.
(a) (b)
Figura 98.- .- (a) Patrón de luz estructurada utilizado para la proyección de luz
estructrurada, y (b) objeto reflejando ese patrón de luz. Los puntos iluminados se pueden
obtener mediante triangulación activa.
- 188 -
Capítulo 6 – Introducción a la Visión Tridimensional
Las imágenes de rango pueden venir dadas, bien mediante una lista de
coordenadas 3D de puntos sin especificaciones de orden ni conectividad entre
ellos, como se muestra en la Figura 99 (a esta forma de representación se la
denomina nube de puntos), o bien mediante una matriz de valores de profundidad
de puntos a lo largo de las direcciones x e y de la imagen. Las imágenes que vienen
dadas de esta forma se denominan imágenes de profundidad, mapas de
profundidad, perfiles de superficie, o imágenes 21/2D.
- 189 -
Capítulo 6 – Introducción a la Visión Tridimensional
Figura 100.- Imagen de rango adquirida mediante un sensor de rango 3D láser que emplea
triangulación activa para el cálculo de las coordenadas 3D. La imagen de la derecha
presenta la vista frontal del objeto y permite apreciar la resolución del escáner. La de la
izquierda esta rotada para que pueda apreciarse su forma.
En cualquier caso este tema, como otros que han sido descritos en este libro,
constituye un problema abierto que seguro encontrará nuevas soluciones en los
próximos años.
[Gon00] caps. 9 y 10
- 191 -
Anexo A Clasificación con el
perceptrón multicapa
El sistema nervioso se encarga de recoger los impulsos del mundo que nos rodea y
de coordinar y dirigir todas las actividades de los órganos de acuerdo a lo que ha
percibido de ese exterior. Este complejo sistema tiene como unidad funcional un
único tipo de células: las neuronas. Las neuronas disponen de un elemento que se
llaman axón que permite trasmitir a otras neuronas a través de las dendritas
impulsos eléctricos de diferente intensidad. Estas células se disponen en forma de
complejas redes y mediante unos procesos, conocidos como procesos sinápticos,
según los cuales se excitación o se inhiben unas a otras, son las responsables de las
capacidades de aprendizaje y comprensión que caracterizan a los seres vivos que
las poseen.
axón
sinapsis
soma
núcleo
dendritas
Figura 101.- Modelo biológico que representa la conexión entre dos neuronas.
- 193 -
Anexo A – Clasificación de patrones con el perceptrón multicapa
27
En su definición más general se definen tres funciones asociadas a cada neurona. La
función de entrada, la función de activación y la función de salida, aunque como la función
de salida suele ser la función identidad en general no se tiene en cuenta. Hay autores que
denominan función de transferencia al conjunto formado por la función de activación y la
función de salida.
- 194 -
Anexo A – Clasificación de patrones con el perceptrón multicapa
depende: de la entrada, de las conexiones que existan entre las células y de los
pesos que éstas tengan asociados.
Figura 102.- Ejemplo de una red de neuronas genérica. Se presentan en negro y más
pequeñas las neuronas de entrada y, sombreadas las de salida. El resto son neuronas
intermedias u ocultas.
28
El proceso de aprendizaje de un conjunto de neuronas reales constituye un tema por
descubrir para la biología actual.
- 195 -
Anexo A – Clasificación de patrones con el perceptrón multicapa
- 196 -
Anexo A – Clasificación de patrones con el perceptrón multicapa
ErrorCPE
Error 1
Error 2
ErrorCE
Error 3
- 197 -
Anexo A – Clasificación de patrones con el perceptrón multicapa
Para simplificar los cálculos suele cambiarse el umbral por una entrada de
peso igual a umbralj, Conectando este axón a una neurona especial que siempre
tendrá estado de activación 1. De esta forma la entrada total a la neurona j será:
1
salida j = - Entrada _ Total j
(A.4)
1+ e
- 198 -
Anexo A – Clasificación de patrones con el perceptrón multicapa
1
Función Escalón
0
1
Función Sigmoide
0 0
Figura 104.- Aspecto de las funciones de activación escalón (arriba) y sigmoide (abajo).
Así, el modelo mas sencillo consistirá en una red compuesta por una única
neurona, en la que la salida viene determinada por la sigmoide (A.4) de la entrada
total. Es sencillo demostrar que este esquema es idéntico al del clasificador
euclídeo. Así, una red con una sola capa puede separar conjuntos de patrones
mediante un hiperplano (ver Figura 105).
Figura 105.- Patrones 2D separados por un hiperplano (en este caso una recta).
- 199 -
Anexo A – Clasificación de patrones con el perceptrón multicapa
Salidas
...
Entradas ... Nivel 1 (Oculto)
i unidades (i>0)
...
Entradas
- 200 -
Anexo A – Clasificación de patrones con el perceptrón multicapa
Para poder discriminar dos conjuntos sea cual sea la disposición de sus
patrones se puede utilizar una red con una sola capa oculta. En los siguientes
párrafos se ofrece una demostración informal de este hecho.
Figura 107.- Los patrones de una muestra siempre se pueden agrupar en regiones convexas.
- 201 -
Anexo A – Clasificación de patrones con el perceptrón multicapa
Por tanto, concatenando las dos redes descritas, es decir, construyendo una
red con una capa oculta y tantas neuronas de salida como clases, se pueden separar
regiones con forma cualquiera.
¶Error
Dpesoi ® j = - m × (A.5)
¶pesoi ® j
Elementos de la red
De (A.5) se deduce que se debe disponer de una medida para el error. La medida
más común de éste consiste en la suma de las diferencias cuadráticas entre los
valores obtenidos y los deseados, en las numN neuronas de salida, después de
presentar cada patrón de entrenamiento. Esta fórmula (A.6) se conoce como error
cuadrático medio.
numN
1
Error =
numN
å (salida
N =1
N - deseada N ) 2 (A.6)
- 203 -
Anexo A – Clasificación de patrones con el perceptrón multicapa
¶entrada j
= salida i (A.9)
¶pesoi® j
Definimos ahora:
¶Error
cambio j = - (A.10)
¶entrada j
¶salida j
= F '(entrada j ) (A.13)
¶entrada j
¶Error
- = (deseada j - salida j ) Þ (A.14)
¶salida j
Funciones de activación
Como se desprende de (A.15) la aplicación de la regla delta depende de la derivada
de la función de activación. La función de activación más común es la sigmoide,
pero también suelen usarse la función tangente hiperbólica y la función identidad.
Derivando:
F’(entradaj) =1 (A.17)
1 - entrada j 1
salidaj = F(entradaj) = - entrada j Þ e = - 1 (A.18)
1+ e salida j
Derivando:
- 205 -
Anexo A – Clasificación de patrones con el perceptrón multicapa
¢ - entrada j
æ 1 ö e
F’(entradaj) = ç ÷ = = salidaj × (1- salidaj) (A.19)
è 1+ e -entrada j ø
( )
- entrada j 2
1+ e
ì
ï 0 Si la salida es correcta
ïï 1
Error = í (m - entrada j ) 2 Si la salida es 0 y debería ser 1 (A.20)
ï 2
ï- 1 (m + entrada j ) 2 Si la salida es 1 y debería ser 0
ïî 2
ì 0 Si la salida es correcta
¶Error ï
cambio j = - = íentrada j - m Si la salida es 0 y debería ser 1
¶entrada j ï
îentrada j + m Si la salida es 1 y debería ser 0
(A.21)
- 206 -
Anexo A – Clasificación de patrones con el perceptrón multicapa
. .
. .
. Neuronas . . . . . . Neuronas .
. de . ... . . ... . de .
. Entrada . . . . . Salida .
i j .
peso i®j .
Figura 108.- Esquema general de una conexión entre dos neuronas en un perceptrón
multicapa. Se presenta el caso de una conexión cualquiera, que une la neurona i de la capa
intermedia I y la neurona j de la capa intermedia J.
¶Error numK
¶Error ¶entrada K
- =-å × = (A.23)
¶salida j K =1 ¶entrada K ¶salida j
- 207 -
Anexo A – Clasificación de patrones con el perceptrón multicapa
numJ
¶ ( å peso J ® K × salida J )
numK
¶Error
=-å × J =1
= (A.24)
K =1 ¶entrada K ¶salida j
numK
¶Error numK
=-å × peso j ® K = å cambio K × peso j ® K (A.25)
K =1 ¶entradaK K =1
numK
cambio j = F ' (entrada j ) × å cambio
K =1
K × peso j ® K (A.26)
Esta fórmula nos permite conocer el factor cambio para una capa siempre
que se conozca el factor cambio para la capa siguiente. Este proceso tiene fin en la
última capa de la que se conoce el valor cambio gracias a (A.15). Constituye por
tanto un método constructivo para ir calculando el incremento de los pesos que
minimiza el error según (A.6), y que exige que la función de activación de cada
neurona sea derivable respecto de la entrada total a la misma.
Paso 1.- Iniciar los pesos de las conexiones de la red con valores aleatorios pequeños.
Paso 2.- Presentar uno de los conjuntos de entrada de la muestra a la red y calcular la salida
que se obtiene.
Paso 3.- Si no coincide la salida obtenida con la deseada ajustar los pesos como sigue:
j = N (N es el número de neuronas)
- 208 -
Anexo A – Clasificación de patrones con el perceptrón multicapa
i=j
Mientras que j ¹ 0
{
Mientras que i¹ 0
{
D pesoi®j(t+1)=m ×cambioj(t) × salidai(t)
pesoi®j(t+1)=pesoi®j(t)+ D pesoi®j(t+1)
i = i –1
}
j = j-1
}
En esta forma los pesos se modifican tras cada iteración constituyendo la variante on-line.
También podrían sumarse cuando han pasado todos los conjuntos de entrada en lo que sería
la variante Batch.
cambioj es una medida del error cometido en la neurona j. En este algoritmo este error
depende del tipo de neurona. Si la neurona j es de salida, cambioj, tendrá en cuenta la
diferencia entre el valor deseado y el obtenido:
mientras que si es una neurona intermedia medirá el error de las neuronas a las que
alimenta:
Paso 4.- Si han coincidido todas las salidas obtenidas con las esperadas después de
presentar todos las entradas de nuestro conjunto de entrenamiento terminar. En otro caso
hacer t = t + 1 e ir al paso 2. Como es posible que el proceso no logre obtener siempre la
salida deseada frente al patrón de entrada, siempre se puede detener el proceso cuando
alcance un valor de error que se considere aceptable.
- 209 -
Anexo A – Clasificación de patrones con el perceptrón multicapa
- 210 -
Anexo A – Clasificación de patrones con el perceptrón multicapa
Figura 109.- Ejemplo de algunos de los caracteres usados para construir los conjuntos de
entrenamiento, validación y test final del clasificador.
- 211 -
Anexo A – Clasificación de patrones con el perceptrón multicapa
Figura 110.- Imagen de una red de neuronas con 68 unidades de entrada (verde), 20
unidades ocultas (amarillo) y 10 de salida (rojo).
20 y 40 unidades ocultas
y dos capas ocultas
10 unidades ocultas
Error cuadrático medio
Iteraciones de entrenamiento
- 212 -
Anexo A – Clasificación de patrones con el perceptrón multicapa
Punto ótimo
de generalización
Iteraciones de entrenamiento
Figura 112.- Curva que presenta el error obtenido con los patrones de entrenamiento y con
los de validación del entrenamiento. El punto óptimo de generalización indica el punto en el
que se debe interrumpir el entrenamiento.
3 17 1
4 18
5 17 1
6 1 17
7 1 17
8 18
9 18
Tabla 7
[Loo97] cap. 5
[Z+95]
- 214 -
Anexo B Referencias
Bibliográficas
[F+97] J.D. Foley, A. van Dam, S.K. Feiner y J.F. Hughes, Computer
Graphics: Principles and Practice, 2nd edition in C, Addison-Wesley,
1997.
- 215 -
Anexo A – Clasificación de patrones con el perceptrón multicapa
[Loo97] C.G. Looney, Pattern Recognition using Neural Networks: Theory and
Algorithms for Engineers and Scientists, Oxford University Press,
1997.
[Par97] J.R. Parker, Algorithms for Image Processing and Computer Vision, J.
Wiley and Sons, 1997.
[Z+95] A. Zell et al, Stuttgart Neural Network Simulator: User Manual v. 4.0,
1995.
[Mat99] Matrox Electronic Systems Ltd, Matrox Imaging Library: User Guide
v. 6.0, 1999.
- 218 -
Anexo A – Clasificación de patrones con el perceptrón multicapa
B.3.1 Revistas
El lector interesado en el tratamiento digital de imágenes y visión artificial puede
consultar multitud de revistas dedicadas a la materia explicada. Tienen especial
relevancia:
- 220 -
Anexo A – Clasificación de patrones con el perceptrón multicapa
· IEEE Press.
· Springer Verlag.
· Academic Press.
· Prentice Hall.
· Kluwer Academic Publishers.
· Elsevier Science.
· Addison Wesley.
· World Scientific Publishing Company.
· John Wiley & Sons.
· MIT Press.
· CRC Press.
B.3.2 Software
Existen numerosas heramientas software que pueden adaptarse, total o
parcialmente para la enseñanza de la visión por computador. Las mejores
herramientas son de pago, aunque también hay software libre que se puede utilizar
para estos propósitos. En la página web: The Computer Vision Homepage de la
Universidad de Carnegie Mellon (cuyo enlace aparece en esta sección) existe un
apartado de software donde puede encontrarse una lista extensa de programas,
librerías, entornos de programación software para imágenes. Remitimos al lector a
la consulta de dicha página, donde también aparecen los enlaces web de las
herramientas referenciadas. Se referencian, a continuación algunas más conocidas:
conocidas las imágenes de: Lena, el hombre de la cámara, etc. También para
determinadas aplicaciones se han creado bases de datos conteniendo una muestra
de imágenes lo suficientemente grande, que libra al usuario en muchos casos de
crearla. Para una información más detallada sobre imágenes de prueba en
aplicaciones de visión, se remite (nuevamente al lector) a la página: : The
Computer Vision Homepag, y dentro de ella al enlace:
http://www-2.cs.cmu.edu/afs/cs/project/cil/ftp/html/v-images.html, donde se
pueden encontrar información de muchas bases de datos, imágenes asiladas y
secuencias de imágenes estándar de prueba.
- 222 -
Anexo A – Clasificación de patrones con el perceptrón multicapa
1. Aplicaciones.
2. Bases de datos e índices.
3. Sistemas de visión famosos.
4. Técnicas de visión genéricas.
5. Métodos de extracción de características geométricas.
6. Física de la imagen.
7. Transformaciones y filtrados sobre imágenes.
8. Movimiento, seguimiento y análisis de secuencias de imágenes.
9. Hardware para tratamiento de imágenes.
10. Modelos de representación de objetos, del mundo y de escenas.
11. Métodos de reconocimiento y de registro.
12. Interpretación de imágenes.
- 223 -
Anexo A – Clasificación de patrones con el perceptrón multicapa
Se trata de una sociedad americana dedicada a la visión por computador desde una
perspectiva más industrial y profesional. Ofrece en sus enlaces una guía de
compradores, consejos para aplicar con éxito la visión por computador, recursos
educativos, eventos, enlaces, etc.
- 224 -
Anexo A – Clasificación de patrones con el perceptrón multicapa
· Información bibliográfica.
- 225 -
Anexo A – Clasificación de patrones con el perceptrón multicapa
En relación con las conferencias promovidas por IEEE Computer Society sobre
visión artificial conviene destacar: la Conference on Computer Vision and Pattern
Recognition (CVPR) y la International Conference on Computer Vision (ICCV).
- 226 -
Anexo C Índice alfabético
bujía, 6
A byte, 41
agrupamiento, 164
C
álbum de Brodatz, 101
algoritmo de etiquetado de cámara oscura, 22
componentes conexas, 107 cámaras, 31
algoritmo de las distancias camino, 114
encadenadas, 164 campos aleatorios, 128
algoritmo de retropropagación del capacidad discriminante, 142
gradiente, 202 captura, 18, 22
algoritmo de Warshall, 109 características discriminantes, 137
algoritmo k-medias, 164, 166 CCDs, 35
algoritmo MaxMin, 164, 165 CCITT Grupo 3, 43
apertura, 91 CCITT Grupo 4, 43
aprendizaje, 146, 157, 195 células nerviosas, 194
axón, 193 centro óptico de una lente, 23
centroide, 148
B cierre, 92
background, 102 clases, 137
Bitmap, 47 clasificación, 18
BMP, 47 clasificador de los k-vecinos, 163
borde, 114 clasificador estadístico, 151
brillo, 6 clasificador euclídeo, 148
- 227 -
Anexo C – Índice alfabético
F I
falsas correspondencias, 185 imágenes 21/2D, 189
FFT, 75 imágenes binarias, 27
fiabilidad, 142 imágenes bitonales, 27
filtrado paso alto, 73 imágenes de profundidad, 189
filtrado paso bajo, 73 imágenes de rango, 188
filtrado paso banda, 72 imágenes en color real, 27
filtro, 55 imágenes en niveles de gris, 27
filtro de la mediana, 83 independencia, 142
filtro del bicho raro, 83 índice de refracción, 24
Flujo Luminoso, 5 inferometría holográfica, 186
flujo radiante, 4 inhibición lateral, 8
foco, 23 Intensidad Luminosa, 6
Fourier, 69 intrínsecos, 175
Foveon, 36
frontera, 114 J
función de activación, 194 JFIF, 47
función de salida, 194 JPEG, 44
función de transferencia, 55, 194 JPEG2000, 45, 82
función escalón, 198
función impulsional, 82 K
función sigmoide, 198
funciones de decisión, 138 k-medias, 127
funciones de filtrado espacial, 82 k-vecinos, 163
funciones discriminantes, 138
L
G LMS, 202
generalización, 140 luminancia, 6
generalizar, 196
GIF, 47 M
grano, 33 maestro, 147
mapas de profundidad, 189
H marcadores básicos, 125
histograma, 60 matiz, 11
hit or miss, 93 matriz de confusión, 213
homografía, 181 matriz de covarianzas, 142
- 229 -
Anexo C – Índice alfabético
R T
saturación, 11 U
segmentación, 18
umbral, 198
- 231 -
Anexo C – Índice alfabético
- 232 -