Post on 23-Jul-2020
Análisis de Imágenes Digitales
Conceptos básicos
Dr. Wilfrido Gómez Flores
Introducción
Análisis de imágenes digitales � Una computadora o dispositivo
electrónico obtiene automáticamente información útil a partir de una
imagen digital para una aplicación especí�ca
Problemas comúnmente abordados:
Reconocimiento de objetos
Segmentación de imágenes
Detección de movimiento
Seguimiento de objetos
Estimación de la pose
1/39 Conceptos básicos AID-01
Introducción
2/39 Conceptos básicos AID-01
Introducción
Etapas básicas para el reconocimiento de objetos.
3/39 Conceptos básicos AID-01
Introducción
Di�cultades
El análisis de imágenes es un problema inverso � recuperar informa-
ción desconocida a partir de datos incompletos o contaminados:
Pérdida de información al pasar de 3D a 2D
Ruido inherente en cada medición del mundo real
Iluminación del ambiente
Gran variabilidad de los objetos
Visión local versus visión global
Cantidad masiva de datos para procesar
4/39 Conceptos básicos AID-01
Formación de imágenes
Ejemplo de adquisición de una imagen digital (Gonzalez and Woods, 2018).
5/39 Conceptos básicos AID-01
Formación de imágenes
Una imagen f(x, y) se puede modelar como el producto de dos com-
ponentes:
f(x, y) = i(x, y) · r(x, y) (1)
donde 0 < i(x, y) < ∞ es la componente de iluminación (cantidad
de luz incidente) y 0 < r(x, y) < 1 es la componente de re�ectancia
(cantidad de luz re�ejada).
6/39 Conceptos básicos AID-01
Formación de imágenes
Fuentes de energía: (a) tomografía por emisión de positrones (Rayos-γ), (b) ra-diografía (Rayos-x), (c) ultrasonido (ondas sonoras), y (d) resonancia magnética(radiofrecuencia).
7/39 Conceptos básicos AID-01
Muestreo y cuanti�cación(a) (b)
Muestreo140
160
180
200
220
240
260(c)
Cuantificacio
n
1
2
3
4
5
6
7
8(d)
(a) Imagen continua. (b) Una línea de escaneo muestra las variaciones de inten-sidad a lo largo de la línea AB en la imagen continua. (c) Muestreo y cuanti�-cación. (d) Línea escaneada digitalizada.
8/39 Conceptos básicos AID-01
Muestreo y cuanti�cación
(a) (b)
La resolución es el grado de detalle discernible en una imagen: (a) imagen con-tinua proyectada sobre un arreglo de sensores y (b) resultado del muestreo ycuanti�cación.
9/39 Conceptos básicos AID-01
Imagen digital
Imagen digital � función de intensidad denotada como f(x, y),
donde x e y son coordenadas espaciales:
f(x, y) =
f(0, 0) f(0, 2) · · · f(0,M − 1)
f(1, 0) f(1, 1) · · · f(1,M − 1)...
.... . .
...
f(N − 1, 0) f(N − 1, 1) · · · f(N − 1,M − 1)
(2)
donde M y N son el ancho y alto de la imagen, respectivamente.
El valor de f(x, y) se denomina nivel de intensidad o nivel de gris:
fmın ≤ f(x, y) ≤ fmax (3)
donde el intervalo [fmın, fmax] se denomina rango dinámico.
10/39 Conceptos básicos AID-01
Imagen digital
0 64 128 191 255
0
64
128
191
255
0 64 128 191 255
Una imagen digital es una matriz de tamaño M ×N donde a cada punto (x, y)le corresponde un valor en el rango [fmın, fmax]. Cada elemento de la imagen sedenomina píxel (picture element).
11/39 Conceptos básicos AID-01
Operaciones entre píxeles
Operaciones aritméticas entre píxeles. Las imágenes f(x, y) y g(x, y), así comolas imágenes resultantes s, d, p y v son del mismo tamaño.
Operación Expresión Aplicación
Adición s(x, y) = f(x, y) + g(x, y) Reducir ruido
Sustracción d(x, y) = f(x, y)− g(x, y) Detectar cambios
Producto p(x, y) = f(x, y)× g(x, y) Enmascaramiento
División v(x, y) = f(x, y)÷ g(x, y) Corregir sombreado
12/39 Conceptos básicos AID-01
Operaciones entre píxeles
(a) (b)
(c) (d)
Adición de imágenes (promediado) para reducción de ruido. (a) Imagen ruidosade la Galaxia Sombrero. (b)�(d) Resultado del promediado de 10, 100 y 1000imágenes ruidosas.
13/39 Conceptos básicos AID-01
Operaciones entre píxeles
(a) (b) (c)
Sustracción de imágenes para detección de cambios. (a) Imagen de angiografíamáscara. (b) Imagen de un frame de video. (c) Diferencia entre (a) y (b) dondedetectan vasos sanguíneos.
14/39 Conceptos básicos AID-01
Operaciones entre píxeles
(a) (b) (c)
Multiplicación de imágenes para enmascaramiento. (a) Imagen de ultrasonido demama. (b) Región de interés para aislar el tumor. (c) Producto de (a) y (b).
15/39 Conceptos básicos AID-01
Operaciones entre píxeles
División de imágenes para corrección de sombreado. (a) Imagen con sombreado.(b) Patrón de sombreado estimado. (c) División de (a) y (b).
16/39 Conceptos básicos AID-01
Operaciones entre píxeles
(a) (b) (c)
(d) (e) (f)
Operaciones lógicas: (a) conjunto A, (b) conjunto B, (c) complemento de A(Ac), (d) intersección de A y B (A ∩ B), (e) unión de A y B (A ∪ B), y(f) or-exclusiva de A y B.
17/39 Conceptos básicos AID-01
Operaciones entre píxeles
Imagen original
0 64 128 191 255
Intensidad de entrada
0
64
128
191
255
Inte
nsid
ad
de
sa
lid
a
Función de transformacion Imagen negativo
Operación de un solo píxel: el valor de salida del píxel p con coordenadas (x, y)dependerá únicamente de su valor de entrada en la misma coordenada.
18/39 Conceptos básicos AID-01
Operaciones entre píxeles
Imagen ruidosa Imagen suavizada Deteccion de bordes
Operación de vecinos: el valor de salida del píxel p con coordenadas (x, y) de-penderá de los valores de entrada de sus n vecinos circundantes.
19/39 Conceptos básicos AID-01
Relaciones entre píxeles
Vecindario de un píxel p con coordenadas (x, y):
Vecinos horizontales y verticales:
N4(p) = {(x− 1, y), (x, y − 1), (x + 1, y), (x, y + 1)}
Vecinos diagonales:
ND(p) = {(x− 1, y − 1), (x + 1, y − 1), (x + 1, y + 1), (x− 1, y + 1)}
Ocho vecinos:
N8(p) = {N4(p), N8(p)}
20/39 Conceptos básicos AID-01
Relaciones entre píxeles
Vecindario del píxel p con coordenadas (x, y).
21/39 Conceptos básicos AID-01
Relaciones entre píxeles
Sea V un conjunto de valores de intensidad usado para de�nir tres
tipos de adyacencia:
4-adyacencia � Dos píxeles p y q tienen valores en V y
q ∈ N4(p)
8-adyacencia � Dos píxeles p y q tienen valores en V y
q ∈ N8(p)
m-adyacencia � Dos píxeles p y q tienen valores en V y
(a) q ∈ N4(p), ó
(b) q ∈ ND(p) y el conjunto N4(p) ∩N4(q) = ∅
22/39 Conceptos básicos AID-01
Relaciones entre píxeles
(a) Un arreglo de píxeles con valores en V = {1}. (b) Píxeles que son 8-adyacentes (líneas punteadas). (c) La m-adyacencia elimina ambigüedades deque surgen en 8-adyacencia.
23/39 Conceptos básicos AID-01
Relaciones entre píxeles
Un camino desde p con coordenadas (x0, y0) hasta q con coorde-
nadas (xn, yn) es una secuencia de píxeles con coordenadas
(x0, y0), (x1, y1), . . . , (xn, yn)
donde (xi, yi) y (xi−1, yi−1) son adyacentes para 1 ≤ i ≤ n.
Dos píxeles p y q de un subconjunto S están conectados si existe
un camino entre ellos que consista totalmente de píxeles de S.
Para cualquier píxel p ∈ S, el conjunto de píxeles de S conectados
a p se denomina componente conexa de S.
Dos regiones Ri y Rj son adyacentes si Ri ∪ Rj es un conjunto
conexo. Regiones no adyacentes son disjuntas.
24/39 Conceptos básicos AID-01
Relaciones entre píxeles
(a) (b)
Supónga una imagen con K regiones disjuntas, Rk, k = 1, 2, . . . ,K. Sea Ru launión de las K regiones y (Ru)
c su complemento. Entonces, los puntos en Ru
representan el (a) primer plano y los puntos de (Ru)c representan el (b) fondo.
25/39 Conceptos básicos AID-01
Contorno de una región
(a) (b)
El contorno de una región conexa es el conjunto de píxeles que tienen al menosun píxel vecino que corresponde al fondo en en 4- ó 8-adyacencia.
26/39 Conceptos básicos AID-01
Contorno de una región
Algoritmo para el seguimiento del contorno en N4:
1. De�nir código de posiciones en N4: ↑= 0,→= 1, ↓= 2,←= 3.
2. Buscar el primer píxel (p0 = pi) de la región conexa a partir de
la esquina superior izquierda de la imagen.
3. Inicializar una variable d = 0.
4. Determinar en N4(pi) el inicio de la búsqueda en la posición del
vecino q = (d + 3) mod 4.
5. A partir del vecino q buscar en sentido horario el primer píxel con
valor 1, el cual es el nuevo elemento pi del contorno y actualizar
el valor de d con el código de su posición.
6. Si el píxel actual pi es igual al punto inicial del borde p0 entonces
terminar el algoritmo; en caso contrario, regresar al Paso 4.
27/39 Conceptos básicos AID-01
Contorno de una región
28/39 Conceptos básicos AID-01
Relaciones de equivalencia
Sea aRb la notación para indicar una relación binaria entre un par
de puntos a y b que pertenecen a un conjunto A.
Una relación de equivalencia sobre un conjunto A debe ser:
1. re�exiva, si para a ∈ A, aRa;2. simétrica, si para (a, b) ∈ A, aRb implica bRa; y3. transitiva, si para (a, b, c) ∈ A, aRb y bRc implica aRc.
Un conjunto A = {p1, p2, p3, p4}, cu-
ya relación binaria en 4-conectividad es
p1Rp2, p2Rp1, p1Rp3, p3Rp1, y p4 no
está relacionado con ningún punto.
29/39 Conceptos básicos AID-01
Relaciones de equivalencia
Sea S = {(a, a), (a, b), (b, d), (c, e), (d, b)} un conjunto de relaciónde símbolos expresado en la matriz binaria
B =
a b c d e
a 1 1 0 0 0
b 0 0 0 1 0
c 0 0 0 0 1
d 0 1 0 0 0
e 0 0 0 0 0
De acuerdo con la propiedad transitiva aRb ∈ S y bRd ∈ S, pero
aRd /∈ S, de modo que al conjunto de relaciones implícitas se
denomina clausura transitiva.
30/39 Conceptos básicos AID-01
Relaciones de equivalencia
Input: matriz B, número de símbolos n
Output: matriz de clausura transitiva B+
1 B+ ← B2 for (k = 1; k ≤ n; k + +) do3 for (i = 1; i ≤ n; i + +) do4 for (j = 1; j ≤ n; j + +) do5 B+[i, j]← B+[i, j] ∪ (B+[i, k] ∩B+[k, j])
Algoritmo de Warshall para encontrar clausura transitiva.a
aA theorem on boolean matrices. Journal of the ACM (1962) 9(1): 11�12.
31/39 Conceptos básicos AID-01
Relaciones de equivalencia
Aplicando el algoritmo de Warshall a la relación de símbolos en S se
obtiene la matriz de clausura transitiva B+
B =
a b c d e
a 1 1 0 0 0
b 0 0 0 1 0
c 0 0 0 0 1
d 0 1 0 0 0
e 0 0 0 0 0
→ B+ =
a b c d e
a 1 1 0 1 0
b 0 1 0 1 0
c 0 0 0 0 1
d 0 1 0 1 0
e 0 0 0 0 0
y el conjunto de clausura transitiva es
S+ = {(a, a), (a, b), (a, d), (b, b), (b, d), (c, e), (d, b), (d, d)}
32/39 Conceptos básicos AID-01
Etiquetado de regiones conexas
El etiquetado asigna una etiqueta única a cada componente conexa
en una imagen basado en relaciones de equivalencia.
El algoritmo de Rosenfeld y Pfaltza realiza tres pasos:
1. Propagación de etiquetas
2. Encontrar clases de equivalencias
3. Asignar etiquetas usando clases de equivalencias
La propagación de etiquetas se de�ne para N4(x):
aSequential operations in digital picture processing. Journal of the ACM (1966) 13(4): 471�494.
33/39 Conceptos básicos AID-01
Etiquetado de regiones conexas
1 for (i = 1; i ≤ N− 1; i + +) do
2 for (j = 1; j ≤ M− 1; j + +) do
3 if I[i, j] == 1 then
4 lp← I[i− 1, j]5 lq← I[i, j− 1]6 if lp == 0 ∧ lq == 0 then
7 Etiqueta + +8 lx← Etiqueta
9 else if (lp != lq) ∧ (lp != 0) ∧ (lq != 0) then
10 Registrar equivalencia (lp, lq)11 lx← lq
12 else if lq != 0 then lx← lq
13 else if lp != 0 then lx← lp
14 I[i, j]← lx
Propagación de etiquetas para una imagen I de tamaño M× N. lp, lq y lx sonetiquetas asignadas a p, q y x, respectivamente. Al inicio, Etiqueta← 0.
34/39 Conceptos básicos AID-01
Etiquetado de regiones conexas
(a) (b)
(a) Imagen binaria y (b) etiquetas propagadas. Cada color representa una etiquetadiferente. Nótese que una región conexa contiene varias etiquetas.
35/39 Conceptos básicos AID-01
Etiquetado de regiones conexas
Generar la matriz binaria B de relaciones de equivalencia, asegu-
rando las propiedades de simetría y re�exividad:
B = B0 ∪BT0 ∪ In (4)
donde B0 es la matriz de equivalencias original, T denota trans-
puesta, e In es una matriz identidad de tamaño n× n.
Obtener la matriz B+ con algoritmo de Warshall.
De�nir clases de equivalencia: si B+(i, j) = 1, entonces el símbolo
asociado en j se le asigna el símbolo asociado en i.
Dar una segunda pasada a la imagen con etiquetas propagadas
reemplazando cada etiqueta por aquella asignada a su clase de
equivalencia.
36/39 Conceptos básicos AID-01
Etiquetado de regiones conexas
(a) (b)
(a) Imagen binaria y (b) etiquetado con algoritmo de Rosenfeld y Pfaltz. Cadacolor representa una etiqueta diferente para cada componente conexa.
37/39 Conceptos básicos AID-01
Medidas de distancia
Sean p, q y s píxeles con coordenadas (x, y), (u, v) y (w, z), res-
pectivamente; D es una función de distancia o métrica si
1. D(p, q) ≥ 0 (D(p, q) = 0 si y solo si p = q)
2. D(p, q) = D(q, p)
3. D(p, s) ≤ D(p, q) + D(q, s)
Medidas de distancias entre píxeles:
1. Distancia Euclidiana: De(p, q) =[(x− u)2 + (y − v)2
]1/2
2. Distancia city-block : D4(p, q) = |x− u|+ |y − v|3. Distancia chessboard : D8(p, q) = max (|x− u| , |y − v|)
38/39 Conceptos básicos AID-01
Medidas de distancia
12
11
10
9
8
7
6
7
8
9
10
11
12
11
10
9
8
7
6
5
6
7
8
9
10
11
10
9
8
7
6
5
4
5
6
7
8
9
10
9
8
7
6
5
4
3
4
5
6
7
8
9
8
7
6
5
4
3
2
3
4
5
6
7
8
7
6
5
4
3
2
1
2
3
4
5
6
7
6
5
4
3
2
1
0
1
2
3
4
5
6
7
6
5
4
3
2
1
2
3
4
5
6
7
8
7
6
5
4
3
2
3
4
5
6
7
8
9
8
7
6
5
4
3
4
5
6
7
8
9
10
9
8
7
6
5
4
5
6
7
8
9
10
11
10
9
8
7
6
5
6
7
8
9
10
11
12
11
10
9
8
7
6
7
8
9
10
11
12
(a)
0 1 2 3 4 5 6 7 8 9 10 11 12
0
1
2
3
4
5
6
7
8
9
10
11
12
8
8
7
7
6
6
6
6
6
7
7
8
8
8
7
6
6
5
5
5
5
5
6
6
7
8
7
6
6
5
4
4
4
4
4
5
6
6
7
7
6
5
4
4
3
3
3
4
4
5
6
7
6
5
4
4
3
2
2
2
3
4
4
5
6
6
5
4
3
2
1
1
1
2
3
4
5
6
6
5
4
3
2
1
0
1
2
3
4
5
6
6
5
4
3
2
1
1
1
2
3
4
5
6
6
5
4
4
3
2
2
2
3
4
4
5
6
7
6
5
4
4
3
3
3
4
4
5
6
7
7
6
6
5
4
4
4
4
4
5
6
6
7
8
7
6
6
5
5
5
5
5
6
6
7
8
8
8
7
7
6
6
6
6
6
7
7
8
8
(b)
0 1 2 3 4 5 6 7 8 9 10 11 12
0
1
2
3
4
5
6
7
8
9
10
11
12
6
6
6
6
6
6
6
6
6
6
6
6
6
6
5
5
5
5
5
5
5
5
5
5
5
6
6
5
4
4
4
4
4
4
4
4
4
5
6
6
5
4
3
3
3
3
3
3
3
4
5
6
6
5
4
3
2
2
2
2
2
3
4
5
6
6
5
4
3
2
1
1
1
2
3
4
5
6
6
5
4
3
2
1
0
1
2
3
4
5
6
6
5
4
3
2
1
1
1
2
3
4
5
6
6
5
4
3
2
2
2
2
2
3
4
5
6
6
5
4
3
3
3
3
3
3
3
4
5
6
6
5
4
4
4
4
4
4
4
4
4
5
6
6
5
5
5
5
5
5
5
5
5
5
5
6
6
6
6
6
6
6
6
6
6
6
6
6
6
(c)
0 1 2 3 4 5 6 7 8 9 10 11 12
0
1
2
3
4
5
6
7
8
9
10
11
12
Patrones de distancia: (a) city-block (rombo), (b) Euclidiana (circular), y(c) chessboard (cuadrado).
39/39 Conceptos básicos AID-01