3.2. Tamaño
En esta sección consideramos las propiedades de tamaño de un conjunto S - área, perímetro, extensión en una dirección dada, etc. Las propiedades de la forma como la rectitud, convexidad, elongación, etc., se considerarán en las dos próximas secciones.
a. Área
El área de S es simplemente el número de puntos de S. Las áreas de los conjuntos de cualquiera partición S1, . . ., Sm de S pueden ser contadas en un sólo rastreo de S, usando un contador para cada Si. En un ordenador multiprocesador, las marcas que corresponden a cada Si pueden ser cambiadas, e.g., a la izquierda y hacia arriba, y contadas en la esquina superior izquierda de S; el tiempo necesario es del orden del diámetro de S. Las áreas de las componentes conexas de S, o de cualquier partición, pueden ser medidas en el proceso de etiquetado (Sección 3.1a y 3.1b); cada ocurrencia de etiqueta suma 1 al contador apropiado, y si dos etiquetas se encuentra que son equivalentes, el contenido de sus contadores se combina.
El cálculo del área a partir de otras representaciones es también fácil. Dada la representación de longitud de secuencia de S, simplemente añadimos las longitudes de todas las secuencias de 1’s para obtener el área de S; dada la representación de árbol de cuadrados, sumamos las áreas de todos los nodos hoja negros (i.e., añadimos 4k-h por cada nodo hoja negro en el nivel h del árbol). Por otra parte, no es sencillo obtener el área de S a partir de su representación MAT, ya que hay múltiples superposiciones de bloques.
Dada la
representación de borde de S,
conseguimos su área añadiendo las áreas encerradas por todos los bordes externos
y substrayendo las áreas encerradas por todos los bordes internos. El área
encerrada por un borde dado puede obtenerse usando las fórmulas de integración
estándar. Por ejemplo, supongamos que se nos da el código de fisura e1 . . . er, donde cada ei es 0, 1, 2 ó 3. Si tomamos el punto de inicio (x0, y0) = (0, 0) en el origen,
entonces la coordenada-y en el final
del segmento k-ésimo es yk = Ski = 1 Dyi,
donde Dyi = 1
si ei = 1, 0 si ei = 0 ó 2, y - 1 si ei= 3. Sea Dxi = 1
si ei = 2, 0 si ei = 1 o 3, y - 1 si ei= 0. Entonces se puede verificar que el área encerrada es
Sni = 1
yi - 1 Dxi. La
fórmula análoga de un código de cadenas se deja como ejercicio para el lector
[19].
El área de S y las áreas de los conjuntos pueden obtenerse a partir de S (e.g., sus componentes conexas, sus puntos de una distancia dada de Š, sus, su envolvente convexa, etc.) todas son propiedades descriptivas útiles de S. Los criterios basados en área pueden también ser usados para obtener nuevos conjuntos a partir de un S dado; e.g., podemos descartar todas las componentes conexoa de menos de un área dado - o, menos trivialmente, si son adyacentes a tan sólo otro conjunto de la partición dada, podemos fundirlo con ese conjunto. Debería realizarse eso para algunas particiones, la mayoría de las componentes conexas serán muy pequeñas; por ejemplo, ha sido encontrado empíricamente [43] que el número de componentes de niveles grises constantes teniendo área N es proporcional a 1/N4.
Anteriormente, hemos tratado los puntos de S como cuadrados unitarios. Alternativamente, podemos observar S como un conjunto de puntos de enrejado, y definir el área de S como la suma de las áreas de los polígonos obtenidos al unir puntos de enrejado de los bordes externos de cada componente de S, menos la suma de las áreas de los polígonos obtenidos de unir los puntos enrejados de los bordes internos. El teorema de Pick declara que si un S simplemente conexo tiene puntos de borde b y puntos internos i, entonces su área es 1/2b + i -1(en vez de b + i, cuando tratamos los puntos de enrejados como cuadrados unitarios). De forma más general [69], si S tiene agujeros n, su área es 1/2b + i + n - 1.
b. Perímetro y longitud de arco
La longitud de un arco o curva digital obtenida por su representación del código de cadenas contando movimientos horizontales y verticales como 1 y movimientos diagonales como Ö2. Esto da valores razonables para un 8-arco o 8-curva, pero da valores que son un poco altos en el 4-caso, donde un movimiento diagonal está representado por un movimiento horizontal más uno vertical y es tratado como si tuviera longitud 2.
El perímetro de S puede ser definido en un número de diferentes maneras. Algunas posibles definiciones son:
(1) La suma de las longitudes de los códigos de fisura de todos los bordes de S.
(2) La suma de la longitud de los arcos de todos estos bordes, considerados como 8-curvas.
(3) La suma de las áreas de los bordes de S.
Fig. 18 Perímetro
digital. (a) Tres S’s. (b1)-(b3) Sus perímetros de acuerdo a las definiciones
(1)-(3).
Ejemplos simples de los resultados obtenidos usando estas definiciones se muestran en la Fig. 18.
Es sencillo definir algoritmos para calcular perímetros, como medidas en cualquiera de estas maneras, a partir de la representación de matriz de S. Podemos calcular fácilmente la contribución de cada punto del borde y sumar estas contribuciones durante un rastreo; o podemos calcular las contribuciones en paralelo en un ordenador multiprocesador, y sumarlas cambiando y añadiendo. Cada representación del borde de S (código de fisura, código de cadena, cS’) produce una de estas medidas directamente; el problema de obtener cada una de ellas a partir de las otras dos representaciones (e.g., la longitud del código de cadenas o el área del borde a partir de los códigos de fisura) se deja como ejercicio para el lector.
El perímetro se mide fácilmente a partir de una representación de longitud de secuencia de S; e.g., la longitud del código de fisura es la suma del número de finales de secuencias y las longitudes de las subsecuencias que no están solapadas con secuencias de la fila superior o de la fila anterior. Para calcular la longitud del código de fisura de una representación de árbol de cuadrados, visitamos cada nodo hoja, y comprobamos los colores de los nodos cuyos bloques son adyacentes a su bloque en ambos lados, por ejemplo bajo y derecho, para determinar cual de estas adyacencias contribuye al perímetro; el tiempo requerido para esto es proporcional al número de nodos veces la altura del árbol [68]. No es sencillo calcular el perímetro desde la representación MAT; solapamientos múltiples de bloques lo hace complicado para determinar cuanto contribuye cada bloque al perímetro.
Deberíamos señalar que el perímetro de una región digitalizada a menudo crece exponencialmente conforme la digitalización se vuelve más fina [35]; el área, por otra parte, tiende a un límite finito. Sobre la exactitud de estimar las longitudes de las líneas rectas y curvas de representaciones digitales ver [18, 50].
Si consideramos S como un conjunto de puntos enrejados, su perímetro es la suma de los perímetros de los polígonos formados por la unión de sus puntos de borde. Una fórmula para el perímetro calculado de esta manera se obtiene como sigue [69]: Sean P0, . . ., P7 los ocho vecinos de P, numerados en el sentido contrario a las agujas del reloj empezando por el vecino a mano derecha. Sea
donde los subíndices son todos módulos 8. Entonces el perímetro de S es
c. Secciones transversales y de perímetro
La altura de S es la distancia vertical entre sus puntos más alto y más bajo, y similarmente su anchura es la distancia horizontal entre sus puntos más a la izquierda y más a la derecha. [La anchura no debería ser confundida con el grosor, que permanece esencialmente igual cuando S es girada o doblada; ver subsección (d).] Más generalmente, el extent de S en una dirección q dada es la distancia entre sus puntos extremos como medidas en paralelo a q. De forma equivalente: Si dejamos caer una perpendicular desde cada punto de S sobre una línea l de pendiente q, el extent de S en dirección q es la distancia a lo largo de l desde el pie de la primera perpendicular hasta el pie de la última. En otras palabras, el extent de S es la longitud de su proyección sobre una línea de pendiente q. Alternativamente, si juntamos un par de líneas paralelas de pendiente q + p/2 hasta que golpeen a S desde lados opuestos, la distancia entre ellas es el extent de S en dirección q.
Medir la altura o anchura de S es sencillo; medir el extent en una dirección q arbitraria es más complicado, ya que es más difícil identificar los puntos extremos. Una solución de fuerza-bruta es la de rotar S -q y medir la anchura de la S rotada. En el próximo párrafo indicamos cómo medir la anchura de una representación dada de S.
Dada la representación de matriz cS, la rastreamos para encontrar las columnas más a la izquierda y más a la derecha que contienen 1’s; la diferencia entre las coordenadas de estas columnas es la anchura. (Un algoritmo de cuenta puede ser ideado para calcular esta diferencia en un ordenador multiprocesador en tiempo proporcional al diámetro de la imagen). Dada la representación de longitud de secuencia, la rastreamos para encontrar las coordenadas de los finales más a la izquierda y más a la derecha de las secuencias de 1’s; similarmente, dada la representación del árbol de cuadrados, recorremos el árbol para encontrar los bloques de 1’s más a la derecha y más a la izquierda. Dada una representación del borde, podemos rastrear los códigos de los bordes externos para encontrar los puntos de borde más a la izquierda y más a la derecha de S (que evidentemente son además los puntos más a la izquierda y más a la derecha de S). Por ejemplo, dado un código de fisura, calculamos xk = Ski = 1 Dxi para cada k [ver (a) arriba], y mantenga la pista de sus valores positivos y negativos más grandes sobre todos los k; esto indica a qué distancia a la derecha e izquierda del punto de inicio se extiende el borde dado.
El extent de S en una dirección dada es una propiedad de S sensible a la orientación. Las propiedades de este tipo son útiles principalmente cuando se conoce la orientación. Alternativamente, podemos normalizar la orientación de S e.g., encontrando su extent más grande y rotándolo para hacerlo vertical, o encontrando su rectángulo circunscrito de menor área (i.e., encontrando una pareja de direcciones perpendiculares en las cuales el producto de los extents de S es el más pequeño) y rotándolo para hacer vertical su lado largo. Existen métodos de normalización de la orientación de una imagen arbitraria que no vamos a ver aquí; estos métodos pueden ser también usados para imágenes segmentadas.
Obtenemos información direccional más detallada sobre S si examinamos sus secciones cruzadas individuales en una dirección dada (o a lo largo de una familia dada de curvas; pero consideraremos aquí para simplificar las secciones cruzadas definidas por las filas de la imagen). Cada una de tales secciones trasversales (de cS) consta de secuencias de 1’s separadas por secuencias de 0’s. Varias propiedades de estas secuencias, como las funciones de posición de las filas, pueden proporcionar propiedades descriptivas útiles de S; e.g., podemos usar el extent de los conjuntos de secuencias, sus longitudes totales, el número de secuencias, etc. También podemos usar comparaciones entre secuencias en filas sucesivas como base para segmentar S en trozos de forma simple [24]. En particular, podemos romper S en partes consistentes en sucesiones de secuencias simples que no cambian radicalmente en longitud o posición; siempre que las secuencias se partan o se fundan, o crezcan, encojan, o cambien significativamente, se definen nuevos trozos de S. De este modo cada trozo es una tira que tiene aproximadamente una anchura constante o que varía lentamente. Por supuesto, las propiedades o segmentos obtenidos a partir de estas secuencias son bastante sensibles a la orientación; deberían también ser aplicadas sólo cuando se conoce la orientación, o después de normalizarla.
d. Distancias y
grosor
Al mayor extent de S en cualquier dirección se le llama su diámetro. Esto es igual a la distancia mayor entre dos puntos cualesquiera de S. El extent de S en varias direcciones, o las distancias entre puntos de S, son a veces útiles como propiedades descriptivas.
Conocer el conjunto de todas las distancias entre puntos no determina S más allá de su congruencia; por ejemplo [37],
1 1 1 1 1 1
1 y 1 1
1
Fig. 19
Simplificación mediante encogimiento y reexpansión. (a) S; (b)
S(-1); (c) (S(-1))(1)
tienen el mismo conjunto de distancias (cuatro 1’s, dos 2’s, dos Ö2’s, y dos Ö5’s). Por otra parte, si tenemos una correspondencia uno-a-uno entre S y T tal que las parejas correspondientes de puntos tengan la misma distancia, S y T deben ser congruentes; esto generaliza el teorema familiar (correspondiente al caso donde S y T tienen cada uno tres puntos) que un triángulo está determinado hasta la congruencia especificando las longitudes de sus tres lados.
Uno además puede usar la noción de distancia para definir nuevos conjuntos a partir de un S dado, e.g., el conjunto de puntos de S a (o en) una distancia dada de S o de Š. Recordamos (Sección 2.1c) que la expansión paso-k S(k) de S es el conjunto de puntos dentro de la distancia k de S, mientras que la contracción paso-k S(-k) es el conjunto de puntos más allá de k de Š. En los próximos párrafos mostramos cómo pueden usarse combinaciones de expansión y encogimiento para extraer nuevos conjuntos a partir de S, y para “limpiarlo”.
Nótese primero que el encogimiento seguido de expansión borra partes pequeñas de S; puede de este modo ser usado como una operación de limpieza de ruido. Un ejemplo simple se da en la Fig. 19. Observamos que este proceso además borra partes delgadas de S tales como curvas; no debería usarse si tales partes son significativas. De hecho, podemos definir el grosor de S como dos veces el número de pasos de encogimiento requeridos para borrarlo. Los métodos de detectar partes delgadas o alargadas de S encogiéndolas, expandiéndolas, y comparándolas con la S original se discutirán en la Sección 3.4b.
Ahora mostramos como la expansión seguida del encogimiento puede usarse para identificar partes aisladas y partes con clústers de S. Supongamos que expandimos S k veces y entonces encogemos el resultado k veces, i.e., calculamos (S(k))(-k); recordamos que este conjunto siempre contiene a S. Un pequeño trozo aislado de S (donde “aislado” significa “a más de 2k del resto de S”) simplemente se expande y se encoge de vuelta, así que hace surgir un pequeño componente conexo de (S(k))(-k);. Por otra parte, un clúster de trozos de S (menos que a 2k) “se funde” bajo la expansión, y tan sólo se encoge de vuelta es sus bordes, así que produce un componente grande de (S(k))(-k); como se ilustra en la Fig. 20. De este modo para detectar clústers o trozos aislados de S, calculamos (S(k))(-k); (para varios k’s) y examinamos sus componentes conexos; si el área de una componente es grande en comparación a k2, debe haber surgido a partir de un clúster de trozos de S, mientras que si es pequeño, debe haber surgido a partir de un trozo aislado.
Se han usando expansión y encogimiento 8-vecinas. En (b) y (c) Los puntos originales de S son
Fig. 20
Detección de clúster mediante expansión y
encogimiento. (a) S; (b) S(1) ; (c)
(S(1))(-1).