3.4. Forma
Los rasgos de los bordes como las esquinas proporcionan información sobre la forma a un nivel local. En esta sección discutiremos las propiedades de la forma global como la complejidad, alargamiento y convexidad. Otras medidas que nos ofrecen información global sobre la forma, como momentos y los coeficientes de Fourier, se discutirán en el Capítulo 12, ya que son aplicables a imágenes no segmentadas. En esta sección, S es normalmente un grupo conectado.
a.
Complejidad
Los juicios humanos de la complejidad de la forma dependen de muchos factores. Por supuesto, los factores topológicos juegan un importante papel; los números de componentes y agujeros de S afectan su juicio de complejidad. Asumiremos en los próximos párrafos que S es simplemente conexa, i.e., es conexa y no tiene agujeros, así que tan sólo tiene un borde único.
La ondulación o indentación del borde de los S’s es un factor importante de complejidad. Esto puede ser medido mediante la curvatura total absoluta sumada al borde [77]. Alternativamente, simplemente podemos contar la curvatura máxima (“esquinas”), quizás con pesos asignados según su grado de afilado.
Otra medida de complejidad frecuentemente propuesta es p2/A, (perímetro)2/área. (p está al cuadrado en esta expresión para hacer el radio independiente del tamaño; cuando aumentamos S mediante el factor m, p se multiplica por m y A se multiplica por m2), En el plano real, la “desigualdad isoperimétrica” declara que p2 / A ³ 4p para cualquier forma, manteniendo la igualdad sii la forma es un círculo; el radio aumenta cuando la forma alarga o se vuelve irregular; o si sus bordes se ondulan. En una imagen digital, resulta [52] que, dependiendo de cómo se mide el perímetro (ver Sección 3.2b), p2 / A es más pequeño para ciertos octógonos que para círculos digitalizados. Sin embargo, aún podemos usarla como medida (aproximada) de complejidad. §
La complejidad de S también depende de cuánta información se requiere para especificar S. De este modo la presencia de partes iguales, periodicidades, o simetrías en S reduce su complejidad. Hay una tendencia a percibir ciertas imágenes ambiguas de tal manera que sus descripciones están simplificadas. Por ejemplo, la Fig. 3.18a es fácil verla como un cubo tridimensional, ya que esta interpretación hace las líneas y ángulos todos iguales, mientras que la Fig. 3.18b es más fácil verla como bi-dimensional. La interpretación tridimensional de la Fig. 3.18b es también improbable, ya que requiere que dos esquinas del cubo estén exactamente en línea con el ojo.
Las medidas de curvatura, perímetro, y área ya han sido discutidas. La periodicidad o la simetría de (las partes de) una imagen puede ser detectada usando técnicas (aproximadas) de emparejamiento (Capítulo 9); en el caso de simetría, debemos rotar 180º (para la simetría relativa a un punto) o reflejar (para la simetría relativa a una línea) antes del emparejamiento. Es más fácil percibir la simetría de una imagen sobre un eje vertical u horizontal; en estos casos, la simetría de una forma es relativamente fácil de detectar usando cualquiera de las representaciones estándar - matriz, longitud de secuencia, MAT, árbol de cuadrados [2], o borde - o a partir de aproximaciones [10]. Los detalles no se darán aquí.
b.
Elongación
Como en la Sección 2.1c, Denotemos con S(k) el resultado de expandir S k veces, y con S(-k) el resultado de encogerla k veces. De este modo cada punto de S está a una distancia dentro de k de Š, así que podemos decir que el grosor de S es hasta 2k, como en la Sección 3.2d.
Supongamos que el área A de S es grande en comparación con k2, por ejemplo A ³ 10k2. Entonces podemos decir que S está elongada, ya que su “longitud” intrínseca (=A/t) ³ 10k2/2k = 5k es al menos 2½ veces su grosor. En general, podemos definir la elongación de una S simplemente conexa como A/t2, donde A es el área de S y t es dos veces el número de pasos de encogimiento requeridos para hacer desaparecer a S.
Nótese que esta medida de elongación es poco fiable para valores pequeños de t; por ejemplo,
1 1
1 1 y 1 1 1 1
ambas tienen A = 4 y t = 2, pero sólo llamaríamos elongada a la segunda. Podemos usar esta medida incluso cuando S tiene agujeros, pero su razonabilidad es menos obvia; podemos llamarlo un anillo alargado, pero ¿qué hay de una criba? Si S tiene ruido debería limpiarse (e.g., mediante expansión y volviendo a encoger; ver Sección 3.2d) antes de aplicar los métodos de esta subsección.
Puede obtenerse algo más de información sobre la elongación de S estudiando cómo el área de los S’s cambia conforme la encogemos, mejor que simplemente usando A y t. En particular, para una S elongada por todas partes la proporción de la disminución del área debería ser relativamente constante, ya que los áreas de los bordes de S, S(-1), S(-2), . . . son casi los mismos; mientras que para un S compacto, la proporción de decremento debería declinar firmemente, ya que los áreas de los bordes decrecen.
Todas las
medidas de elongación de S son sólo
de utilidad limitada, ya que S puede
estar parcialmente elongada o parcialmente no, y las partes elongadas pueden
tener diferente grosor (e.g., S consta en arroyos, ríos y
lagos). Ahora mostraremos como encoger y reexpandir puede usarse para detectar
partes elongadas de S.
Fig. 24 Detección
de una parte elongada. (a) S; (b) S(-1);
(c) (S(-1))(1); (d) S – (S(-1))(1).
La componente 10-punto es
grande, por lo tanto esta elongada.
Consideremos (S(-k))(k), el cual es el resultado de encogimiento de S k veces y entonces la re-expansión k veces. Como mencionamos en Sección 2.1c, esto siempre está contenido en S. Dejemos que C sea cualquier componente conexo del grupo de diferencia s -(S(-k))(k). Ya que C desaparece bajo los k pasos de encogimiento, su grosor es hasta 2k; de este modo si su área es grande relativa a k2, está aislada. Haciendo este análisis para varios valores de k, podemos detectar partes aisladas de S que tengan varios grosores. Un simple ejemplo, usando sólo k = 1, se muestra en Fig. 24.
Los métodos descritos en esta subsección están diseñados para usarlos con la representación de colecciones de S. Son especialmente eficientes en un ordenador de colecciones celulares, pero también puede implementarse en un ordenador convencional, como se discutió en la Sección 2.1c. El aislamiento es relativamente fácil de detectar usando representaciones de maximal-bloque, e.g., S debe estar aislada si el número de bloques MAT es alto y sus radios son pequeños, o el número de hojas negras del árbol de cuadrados es grande y sus tamaños son pequeños. Es más difícil detectar desde una representación de borde.
c.
Convexidad
En esta y las próximas subsecciones discutiremos las propiedades de S que están definidas en términos de las intersecciones de líneas rectas con S.
En el plano real, se dice que S es convexa si cualquier línea recta se encuentra con S al menos una vez, i.e., en sólo una secuencia de puntos. Evidentemente, un conjunto convexo debe ser conexo y no puede tener agujeros; y un arco puede ser convexo sólo si es un segmento de línea recta.
Es fácil ver que cada una de las siguientes propiedades es equivalente a la convexidad:
(1) Para cualesquier puntos P, Q de S, el segmento de línea recta de P a Q se encuentra en S.
(2) Para cualesquier puntos P = (x, y), Q = (u, v) de S, el punto medio ((x + u)/2, (y + v)/2) de P y Q está en S.
De hecho, es suficiente, en estas definiciones, asumir que P y Q son puntos de borde de S.
Podemos usar definiciones análogas para las imágenes digitales, pero debemos tener cuidado para permitir los efectos de cuantización. El segmento de línea recta digital de P a Q no está siempre unívocamente definido (ver Sección 3.3b); puede que requiramos, e.g., que al menos uno de los posibles segmentos está enteramente en S. El punto medio de P y Q puede no tener coordenadas enteras; aquí podemos requerir que para un redondeo al menos de cada coordenada medio-entera, hacia arriba o hacia abajo, el resultado está en S.
Debería señalarse que incluso si S es convexa digitalmente [e.g., tiene la versión digital de la propiedad (2), t puede que no sea la digitalización de ningún objeto convexo. (Recíprocamente, sin embargo, si S es tal digitalización se puede mostrar [26] que S tiene la propiedad digital (2)). Nótese que cualquier S puede ser la digitalización de un objeto cóncavo, e.g., uno que tenga pequeñas concavidades que se pierden en el proceso de muestreo.
Hay varias maneras de subdividir una S dada en trozos convexos; para una tratamiento detallado de este tema ver [46], Capítulo 9. Una heurística útil es hacer cortes en S que unen los puntos más profundos de las concavidades (e.g., las esquinas cóncavas sobre el borde de S).
La convexidad es principalmente detectada a partir de la representación del borde de S; de hecho, podemos definir S como convexa si la curvatura de su borde nunca cambia de signo. (Comparemos los comentarios en la Sección 3.3c). Es más difícil detectar la convexidad en las representaciones de bloques maximales. Algunos métodos de determinar la convexidad en la representación de matriz se describen en la próxima subsección.
d. La envolvente
convexa
En el plano real, hay un conjunto convexo SH que es el más pequeño de los que contienen cualquier conjunto dado de S. (Prueba: Fácilmente cualquier intersección de conjuntos convexos es convexa; en particular, la intersección de todos los conjuntos convexos que contienen S es convexa). A SH se le llama la envolvente convexa de S; está ilustrado esquemáticamente en la Fig. 25. Puede mostrarse que SH es la intersección de todos los medios-planos que contienen S; y si S es conexa, SH es la unión de todos los segmentos de líneas cuyos puntos finales están en S.
Claramente S es convexa sii SH = S. De este modo una manera de decidir si S es convexa es construir su envolvente convexa y ver si realmente contiene S. En cualquier caso, podemos definir las concavidades de S como las componentes conexas del conjunto diferencial SH - S.
Fig. 25 Un conjunto
(sombreado vertical) y su envolvente convexa (incluye las partes sombreadas
horizontalmente).
La definición del medio-plano conduce a la siguiente construcción de SH [62], que puede ser usada también para construir (y definir) una envolvente convexa en el caso digital. Sea P1 el punto que está más a izquierda de los puntos más arriba de S, y sea L1 la línea horizontal a través de P1. Rotamos L1 en el sentido contrario de las agujas del reloj sobre P1 hasta que alcance S; llamemos a la línea rotada resultante línea L2, y sea P2 el punto de S más lejano de P1 a lo largo de L2. Rotemos L2 en sentido contrario de las agujas del reloj sobre P2 hasta que alcance S; sea L3 esta línea rotada, y sea P3 el punto más lejano de P2 a lo largo de L3. No es difícil demostrar que cuando se repite este proceso, eventualmente tenemos Pn = P1 y Ln = L1. El polígono cuyos vértices son P1, . . ., Pn - 1 es entonces SH. Nótese que las L’s limitan a los medio-planos que tan sólo contienen S. Otra caracterización de las P’s es la siguiente: Para cualquier punto de borde P, Q de S, sea ŠPQ la parte de Š que está rodeada por S y por el segmento de línea PQ. Entonces ŠPQ es maximal (i.e., no está contenido en ninguna otra ŠP’Q’) sii P y Q son dos Pi’s consecutivos (módulo n - 1).
La unión de la definición de segmentos de línea conduce [4] a la construcción (y definición) de una envolvente convexa digital que es más apropiada para un ordenador multiprocesador. Denotemos con S0 el resultado de “untar” S en dirección q, i.e., es la unión de todos los posibles cambios de S en cantidades de 0, 1, 2,... en dirección q; no necesitamos usar cambios mayores que el diámetro de S. Entonces Sq Ç Sq + p es el conjunto de puntos que tienen puntos de S a ambos lados de ellos en dirección q, i.e., éstos son justo los puntos que están sobre segmentos de línea de pendiente q entre dos puntos de S. De este modo È q (Sq Ç Sq + p ) = SH, si S es conexa. No podemos usar sólo unas pocas direcciones q en esta construcción; por ejemplo,
1
1 1
1 1 1 1 1 1
contiene cada segmento de línea entre una pareja de sus puntos cuya pendiente es un múltiplo de 45º, pero no es convexa.
Ciertas propiedades simples de SH pueden estimarse sin construirla de verdad. Por ejemplo, se puede mostrar [45], usando métodos de geometría integral, que el número esperado de veces que una línea aleatoria se encuentra con S es proporcional al perímetro de SH; de este modo podemos estimar este perímetro dibujando un gran número de líneas al azar y contando sus intersecciones. A propósito, la longitud esperada de la intersección de una línea aleatoria con S (i.e., la suma de las longitudes de las secuencias en las que las líneas se encuentran con S) es proporcional al área de S.
e. Generalizaciones de
convexidad
Si S está en una orientación conocida, o si su orientación ha sido normalizada, las intersecciones con S de líneas en direcciones específicas pueden proporcionar propiedades descriptivas útiles de S. Por ejemplo, llamamos a S fila convexa si cada fila de la imagen se encuentra con ella una sola vez; columna convexa se define análogamente. La S mostrada en la subsección precedente es a la vez fila y columna convexa, a la vez que diagonalmente convexa para ambas direcciones diagonales.
Estos conceptos pueden también usarse para definir nuevos subconjuntos en términos de S. Por ejemplo, la “fila envolvente convexa” de una S conexa puede definirse como la unión de todos los segmentos de línea horizontales cuyos puntos finales están en S, i.e., como S0 Ç Sp ; y similarmente para otras direcciones. Análogamente, la sombra de S desde la dirección q es el conjunto de puntos desde los que una media-línea en dirección q se encuentra a S; estos son los puntos que estarían en sombra si S estuviese iluminada por un haz de luz paralelo en dirección q + p [22]. Más generalmente, uno puede definir conjuntos de puntos desde los cuales la media-línea en dirección q encuentre a S un cierto número de veces, o en secuencias de ciertos longitudes totales, etc.
Se pueden definir conceptos similares si usamos familias de líneas emanando desde un punto dado, en vez de en una dirección dada. En el plano real, para cualquier punto P de S, llamamos a S de forma estrellada desde P si cada línea a través de P encuentra a S exactamente una vez. [Equivalentemente: (1) para todos los puntos Q de S, el segmento de línea-recta desde P a Q está en S; (2) para tales Q, el punto medio de P y Q está en S]. Fácilmente, una S de forma estrellada debe ser conexa y puede no contener agujeros, pero necesita ser convexa (una estrella tienen forma estrellada desde su centro). Evidentemente S es convexa sii tiene forma estrellada desde cualquiera de sus puntos. En general, el conjunto de puntos de S desde los cuales la S es visible se llama núcleo de S; nótese que podría estar vacía.
Si S es de forma estrellada desde P, cada punto de S, y en particular cada punto del borde de S, es visible desde P; de este modo este borde tiene una ecuación polar de valor único r = f (q) cuando tomamos el origen en P. Si S es convexa, esto es real para cada P Î S. Para conjuntos arbitrarios, la parte visible de S puede variar de punto a punto. Si [11] asociamos el área (o alguna otra propiedad) de esta parte visible con cada punto de S, podemos segmentar S en partes clasificando los puntos sobre las bases de estos valores; esto es análogo a la segmentación de S sobre las bases de las distancias de sus puntos desde S.