Download Document

$
'
VISIÓN
COMPUTACIONAL.
3.3
&
1/1
%
$
'
3. Representación digital.
Látices y mallas.
Topologı́a discreta.
Representaciones geométricas.
Funciones de distancia.
Representación de color.
&
1/2
%
$
'
Paradoja!
4-conexidad: Para todos los puntos, entónces los puntos
negros están totalmente desconectados pero aún
ası́ separan al conjunto de puntos blancos en 2
componentes.
8-conexidad: Para todos los puntos, los puntos negros
forman un análogo al la curva de Jordan pero no separan
al conjunto de puntos blancos.
&
1/3
%
$
'
Paradoja!
Esta paradoja se puede evitar si consideramos las
conexiones diferentes para los objetos y para su
complemento.
8-conectividad para los puntos blancos y 4-conectividad
para los negros, o viceversa. Una convención de notación
para referirse a la conectividad considerada en una imágen
es escribir: (8,4) o (4,8).
&
1/4
%
$
'
Teorema de Jordan contı́nuo.
El teorema de Jordan en el caso contı́nuo establece que:
toda curva simple cerrada separa el espacio en dos
componentes conexos, el interior y el exterior.
Ahora bien: una curva simple es aquella cuya lı́nea que
define sus bordes no se curza.
&
1/5
%
$
'
Teorema de Jordan discreto.
Respecto a la conexidad discreta tenemos:
Sobre una látice discreta, toda cadena simple cerrada
separa el espacio en 2 componentes , el interior y el
exterior.
Dado un conjunto de puntos S, una cadena en S es la
secuencia < pi |0 ≤ i ≤ n > de puntos en S de tal manera
que pi es adyacente a pi+1 para todo 0 ≤ i ≤ n. Se dice que
una cadena que va de p0 a pn es cerrada si p0 = pn . Un
punto aislado es un caso particular de una cadena cerrada.
&
1/6
%
$
'
Teorema de Jordan discreto.
Una curva negra simple cerrada es el conjunto conectado
de puntos negros cada uno de los cuales es adyacente a
sólo dos puntos del conjunto. La conectividad entre puntos
se define según la convención tomada (8,4) o (4,8).
&
1/7
%
$
'
Complejos celulares (Cellular complexes)
Una manera alternativa de definir conectividades entre
células y evitar las paradojas mencionadas anteriormente
son los llamados complejos celulares, que definen a una
imágen discreta no sólo compuesta por los elementos de
una matrı́z sino también por elementos de los bordes.
Es decir, en 3D los complejos celulares contienen ademas
de cubos, también caras, lados y vértices.
&
1/8
%
$
'
Complejos celulares (Cellular complexes)
Definición. Sea L una látice discreta en 3D. Una célula-0
es un punto, una célula-1 es una lı́nea recta que conecta
dos células-0, una célula-2 es una unidad cuadrada (cara)
bordeada por cuatro células-1, y una célula-3 es una
unidad cubo bordeada por seis células-2.
&
1/9
%
$
'
El número de Euler.
El número de Euler es igual el número de componentes
conexas menos el número de hoyos:
E = Ncc − Nh
Objetos en 8-conexidad y hoyos en 4-conexidad:
Ncc = 1 y Nh = 2 ⇒ E = −1
Convención inversa: Ncc = 1 y Nh = 1 ⇒ E = 0
&
1/10
%
$
'
El número de Euler.
Existen diferentes métodos para calcular de manera local
el número de Euler. S.B. Gray en: Local properties of
binary images in two dimentions IEEE. Trans. on
Comput. C-20,551-561, 1971; propuso el siguiente método:
Para imágenes (4,8) contar el número de
configuraciones siguientes:
E=Σ
&
0 0
0 1
+Σ
1
0
0
1
−Σ
0 1
1 1
E =1+1−2=0
1/11
%
$
'
Cuál es el número de Euler de esta
imágen?
&
TAREA 2
1/12
%
$
'
3. Representación digital.
Látices y mallas.
Topologı́a discreta.
Representaciones geométricas.
Funciones de distancia.
Representación de color.
&
1/13
%
$
'
Representaciones geométricas.
La representación discreta de la mayor parte de las
entidades geométricas simples (rectas, cı́rculos, curvas)
conlleva a dos tipos de problemas:
1.
¿Cómo representar sobre una látice discreta una
entidad geométrica contı́nua?, y ¿cuáles son las
propiedades de ésta en comparación con las verificadas
en el caso contı́nuo?
2.
A partir de una entidad geométrica discreta, ¿cuáles
son las representaciones contı́nuas que le
corresponden?
&
1/14
%
$
'
Representaciones geométricas.
Por ejemplo, para una recta contı́nua es posible dar las
reglas que permitan determinar los puntos discretos de la
látice que la representan.
Por otro lado, si nos dan un conjunto de puntos discretos
podremos verificar si esos puntos corresponden o no a una
recta contı́nua siguiendo esas mismas reglas. Sin embargo,
encontraremos en general que no hay una respuesta única
y que ese conjunto de puntos constituirán una familia de
rectas.
&
1/15
%
$
'
Discretización de una recta contı́nua.
Un primer método es el llamado ”célula semi-abierta”. La
célula semi-abierta asociada a un punto P de coordenadas
(i, j) es el ensamble de puntos de R2 donde las coordenadas
(x, y) cumplen con:
i−
1
2
<x≤i+
1
2
y
j−
1
2
<y≤j+
1
2
Este método consiste entónces en cuidar que en la
representación discreta para cada punto P de la látice, la
célula semi-abierta que le está asociada tenga una
intersección no vacı́a con la entidad a discretizar.
&
1/16
%
$
'
Discretización de una recta contı́nua.
El ensamble de discreto ası́ obtenido no constituye una
cadena simple en el sentido de la 4- o 8-conexidad. En este
ejemplo la cadena no es 4-conexa, y ciertos puntos tienen
más de 2 vecinos por lo cual tampoco es 8-conexa.
&
1/17
%
$
'
Otra alternativa.
Si buscamos ahora discretizar la frontera del medio-plano
cerrado limitado por la recta (es decir, el más cercano a la
recta misma) imponiendo una restricción de
unilateralidad, obtenemos esta vez una cadena 8-conexa.
El método consiste en cuidar que los puntos discretos estén
situados de un mismo lado de la recta y que el segmento
vertical de la malla en donde están corte la recta.
&
1/18
%
$
'
Tercera alternativa.
Es posible combinar estos dos métodos, asociando cada
punto de la malla un segmento semi-abierto, centrado en
éste punto y vertical. Un punto discreto se conserva si el
segmento del cual resulta intersecta a la recta.
Obtenemos una cadena 8-conexa, pero ahora los puntos
discretos están repartidos a los dos lados de la recta
contı́nua (minimiza el error de cada uno de los puntos).
&
1/19
%
$
'
Caracterización de un segmento discreto.
Consideremos ahora el problema inverso: dado un
ensamble de puntos discretos, ¿es la discretización de una
recta contı́nua?
Existen dos métodos para esto:
1.
Utilizando las propiedades de la cuerda.
2.
Utilizando una descripción sintáctica de un segmento
de recta discreto.
&
1/20
%
$
'
Propiedades de la cuerda.
Sea S un conjunto de puntos discretos. Decimos que S
verifica la propiedad de la cuerda si:
∀(P, Q) ∈ S, ∀R ∈ [P, Q], ∃T ∈ S, d∞ (T, R) < 1
donde [P, Q] designa el segmento de R2 (contı́nuo) que une
P a Q, y d∞ designa la distancia obtenida a partir de la
norma L∞ en R2 :
d∞ ((x, y), (x0 , y 0 )) = máx(|x − x0 |, |y − y 0 |)
&
1/21
%
$
'
Descripción sintáctica.
Un segmento de recta discreto está constituı́do por una
serie de puntos que podemos recorrer observando los
cambios de dirección. El método es el siguiente:
Llamemos sección a una serie de puntos maximal sin
cambio de dirección (8 posibles en la látice cuadrada).
En un segmento de recta discreto, las secciones no
pueden terner más que dos direcciones, que son
consecutivas.
Para una de éstas direcciones las secciones son todas
de longitud 1.
&
1/22
%
$
'
Descripción sintáctica.
Uno puede, entónces utilizar esta caracterización para
verificar si el conjunto de puntos considerado es un
segmento de recta discreta.
&
1/23
%
$
'
Rectas analı́ticas discretas.
En lugar de discretizar una recta por una serie de puntos
conexos, buscamos, al contrario, saber cuáles son los
puntos de intersección de la látice discreta con una recta
contı́nua cualquiera.
La ecuación de la recta es: y = ax + b, para que esta
intersección no sea vacı́a, hace falta que la pendiente de la
recta sea de la forma:
p
a=
q
donde p y q son enteros y p ≤ q ≤ N , si la imágen es de
tamaño N × N y para una pendiente de recta inferior a 1
(los demas casos se obtienen por simetrı́a).
&
1/24
%
$
'
Rectas analı́ticas discretas.
Las pendientes de rectas posibles forman una serie de
Farey de orden N , notación F (N ). Para una imágen de
tamaño 4 × 4, las rectas posibles tales que a ≤ 1 son
representadas en cada caso:
1 1 2
F (N ) = {0, , , , 1}
3 2 3
&
1/25
%
$
'
Rectas analı́ticas discretas.
El número de rectas aumenta según el tamaño de la
imágen. Por ejemplo para N = 6 tenemos:
1 1 1 2 1 3 2 3 4
F (N ) = {0, , , , , , , , , , 1}
5 4 3 5 2 5 3 4 5
Ası́ podemos calcular el número de rectas posibles según
el tamaño de la imágen y los números de ocurrencias de
estas rectas en función de la pendiente a.
&
1/26
%
$
'
Rectas analı́ticas discretas.
Este fenómeno puede causar grandes sesgos, por lo cual
hay que tener cuidado. Por ejemplo, si queremos detectar
contornos rectilı́neos contando con las parejas de puntos
que contribuyen al contorno para una orientación dada
(tranformada de Hough), detectaremos mucho más
facilmente los conotornos de pendiente 0 o 1 que otros
contornos de otras pendientes fiables.
&
1/27
%
$
'
Rectas analı́ticas discretas (otros
parámetros).
Si ahora buscamos cuáles son las longitudes de segmentos
discretos, llegamos a concluciones del mismo tipo. Sea L el
cuadrado de una longitud de segmento entre dos puntos
discretos de coordenadas enteras. L es entónces solución
de la ecuación:
a2 + b 2 = L
con a y b enteros. Esta función no siempre tiene solución.
&
1/28
%
$
'
Cı́rculos discretos.
De la misma manera que para las rectas, el número
discreto de puntos que están situados sobre un cı́rculo
contı́nuo puede variar mucho, y de manera muy irregular
seguir al radio. Para ciertos valores de radio, no hay
solución. Aquı́ también tenemos la ecuación:
a2 + b 2 = n
donde a y b son enteros, n el cuadrado del radio y a2 + b2
la distancia cuadrática al centro del cı́rculo (suponemos
que el centro coincide con uno de los puntos de la látice.)
&
1/29
%
$
'
Cı́rculos discretos.
Encontramos ası́, 4 puntos sobre un cı́rculo de radio 1, 4
puntos para n = 2, ningun punto para n = 3, etc.
Para n = 5 resultan 8 puntos y para n = 25 obtenemos 12
puntos.
&
1/30
%
$
'
Cı́rculos, otra alternativa.
En la práctica, la definición de un cı́rculo discreto limitado a
puntos de intersección con la malla resulta muy restrictivo.
Otra alternativa es considerar que el cı́rculo tiene una cierta
”espesura”, y entónces buscar intersecciones de una corona
circular con los puntos de la malla.
Si k es el espesor de la corona, buscamos entónces el número de
puntos que satisfagan la ecuación:
n ≤ a2 + b 2 < n + k
siempre con a y b enteros. El número de soluciones está dado
por:
i=n+k−1
X
r(n, k) =
r(i)
&
i=n
1/31
%
$
'
Cı́rculos, otra alternativa.
En este caso por ejemplo, para n = 54 y k = 4 encontramos
que r(n, k) = 0. Aquı́ otra vez la gran variabilidad de la
función r(n, k) genera un sesgo en los métodos de análisis o
sı́ntesis de imágenes, ası́ como de reconocimiento de
formas, que no se debe descuidar.
&
1/32
%
$
'
Referencias
Kovalevsky, V.A. Finite topology as applied to image
analysis. Computer Vision, Graphics and Image
Processing. 46:141-161, 1989.
Cointepas, Y., Bloch, I., Garnero, L. A cellular model for
multi-objects multi-dimensional homotopic deformations.
Pattern Recognition, 34(9):1785-1798, 2001.
Rosenfeld, A. Digital straight line segments. IEEE Trans.
on Comput. 23(12):1264-1269, 1974.
Pham, S. Digital straight segments. Computer Vision,
Graphics, and Image Processing. 36:10-30, 1986.
Maı̂tre, H. Contribution to the prediction of performances
of the Hough transform. IEEE Trans. on Patt. Ana. Mach.
Intel. 8(5):669-674, 1986.
&
1/33
%
$
'
FIN
Solo por hoy...
&
1/34
%