1.3 Bordes
Todas las representaciones consideradas hasta ahora están basadas en secuencias o bloques maximales de valor constante, posiblemente restringidas tanto en tamaño como en posición. Estas aproximaciones representan cada Si como la unión de las secuencias o bloques maximales que están contenidos en él.
Fig. 4
Métodos para definir las secuencias de bordes. (a) Conjunto S; cada punto se etiqueta con una letra
diferente. En este ejemplo simple no hay puntos interiores. (b) Secuencia en
sentido contrario al de las agujas del reloj de los puntos alrededor del borde,
comenzando con la fisura A. Nótese
que el punto E se visita dos veces.
(c) Secuencia en el sentido contrario al de las agujas del reloj de las fisuras
alrededor del borde, comenzando con la fisura A, encima de A. Los subíndices t, r, b, l denotan
superior, derecha, inferior e izquierda, respectivamente. Nótese que si borramos
los subíndices, y eliminamos las repeticiones consecutivas del mismo punto,
obtenemos la secuencia de puntos de (b).
Otra clase de aproximaciones a la representación hace uso del hecho de que los conjuntos Si están determinados mediante la especificación de sus bordes. (Compare con la discusión de la codificación de contorno de la sección 5.8.) El borde S’ de un conjunto S es el conjunto de puntos de S que están adyacentes a los puntos del complemento Š. Podemos considerar que S’ consiste en un conjunto de curvas cerradas; cada una de estas curvas contiene los puntos que pertenecen a una componente conexa concreta de S y son adyacentes a una componente conexo concreta de Š§. Estos conceptos serán definidos de forma más precisa en las secciones 1.7 y 2.2, y los algoritmos dados para encontrar las curvas de bordes de un S dado y para reconstruir S a partir de sus bordes. En esta sección sólo discutiremos cómo especificar las curvas de bordes.
Una curva de borde se determina especificando un punto de comienzo y una secuencia de movimientos alrededor del borde. La Figura 4 muestra dos formas en las que se puede hacer esto; una aproximación se mueve a lo largo de una secuencia de puntos del borde de un conjunto S, mientras que la otra se mueve a lo largo de una secuencia de “fisuras” entre los puntos de S y los puntos adyacentes de Š.
Moviéndose de un punto a otro alrededor de un borde, siempre vamos de un punto hacia uno de sus ocho vecinos. Numeremos a los vecinos como sigue:
|
3 |
2 |
1 |
|
4 |
|
0 |
|
5 |
6 |
7 |
(mnemotécnico: el vecino i está en dirección 45iº, medido en dirección en el sentido contrario al de las agujas del reloj desde el eje positivo x). Así cada movimiento se define mediante uno de los dígitos 0, 1,..., 7, i.e., por un dígito octal. Por ejemplo, la secuencia de movimientos utilizada en la Figura 4b corresponde a 0766233. Una secuencia de movimientos representada por dígitos octales de esta forma se denomina código de cadenas (chain code). Un borde se define así dando las coordenadas de un punto de inicio junto con un código de cadenas representando una secuencia de movimientos.
Si seguimos las fisuras alrededor de un borde, en cada movimiento vamos tanto a la izquierda como a la derecha, arriba o abajo; si denotamos la dirección 90iº por i, estos movimientos pueden ser representados por una secuencia de números de dos bits (0,1,2,3). Por ejemplo, la secuencia en la Figura 4c está representada por 00303332112121. Llamaremos a esta representación un código de fisuras(crack code). Un borde se especifica dando las coordenadas de una fisura de inicio junto con un código de fisuras.
Cada movimiento en un código de fisuras es representado por un número de 2 bits, mientras que los movimientos en el código de cadenas requieren números de 3 bits; pero el número de movimientos en un crack following es algo mayor que en el código de cadenas, puesto que pueden ser necesarios varios movimientos para atravesar las fisuras alrededor de un único punto. Si asumimos que como mucho la mitad de los puntos de borde de S tienen dos vecinos en Š (i.e., son esquinas o “cinturas” de S), y que los puntos de borde que tienen tres vecinos en Š son raros, entonces el número medio de cracks por punto límite es como mucho 1 ½ . Así el número de bits necesario para representar un límite por un código de fisuras no debería ser mayor que el número necesario para representarlo por un código de cadena.
Los requerimientos de espacio para el almacenamiento de estos esquemas de códigos de borde dependen de la longitud total del borde de los conjuntos Si. En una imagen n ´ n, hay 2n(n+1) fisuras, incluyendo aquellas alrededor de los límites de la imagen. Si la fracción b de estas fisuras son fisuras de borde, necesitamos alrededor de 8bn(n+1) bits para representar todos los códigos de fisura (dos bits por movimiento), puesto que cada fisura de borde –ignorando los límites de la imagen- pertenece a dos curvas de borde §. Como se ha indicado en el párrafo anterior, los códigos de cadenas necesitarían un número de bits similares. Además, para cada curva de borde necesitamos especificar las coordenadas del punto de inicio(2log2 n bits), así como el conjunto Si que se encuentra a la derecha al atravesar el borde [log2 m o log2 (m-1) bits]. Así si hay B bordes, el número total de bits necesarios para este tipo de representación es 8bn(n+1) + B(log2 m +2 log2 n). Nótese que B en sí mismo puede de orden n2, si hay muchos pequeños componentes conexos; en este caso, las representaciones de borde no serían económicas.
Para cualquier código de cadena dado, podemos construir un código de cadena diferencial cuyos valores representan sucesivos cambios en la dirección, e.g., el 0 representa la no existencia de giro, ±1 representa 45º de giro a la derecha o a la izquierda, ± 2 y ± 3 representan, de forma similar, giros de 90º y 135º, y 4 representa un giro de 180º. Así el código de cadena diferencial, como el código de cadena, tiene ocho posibles valores y necesita tres bits por movimiento. Sin embargo, los valores no son asimismo semejantes, e.g., 0 y 1 serían muy comunes, mientras que 4 es raro. (¿Qué implicaciones tiene esto en la posibilidad de compresión del código diferencial?) Evidentemente, un borde es determinado mediante la especificación de las coordenadas del punto de inicio, la dirección inicial y el código de cadena diferencial. El caso del código de fisura diferencial es análogo; aquí hay sólo tres posibles valores diferenciales, 0º y ± 90º.
Los códigos de cadena pueden también utilizarse para la representación digital de curvas planas. El código de cadena de una curva C dada puede ser construido como sigue: Imagine una rejilla cartesiana superpuesta en C. A medida que nos movemos a lo largo de C, siempre que C entre en un cuadrado de la rejilla, tomamos la esquina más cercana a ese cuadrado como un punto en la digitalización de C. (Si C entra en el punto medio de una lado del cuadrado, utilice cualquier convención estándar de redondeo para escoger la esquina “más cercana”.) Cuando C entra y entonces abandona un cuadrado, los dos puntos sucesivos de la rejilla (= esquinas del cuadrado de la rejilla) en la digitalización son o bien los mismos o son vecinos en la rejilla, puesto que son esquinas del mismo cuadrado. Así la secuencia de puntos de rejilla que constituyen la digitalización pueden ser representados por un punto inicial y un código de cadena definiendo la secuencia de movimientos desde un vecino a otro. Los códigos de cadena de las curvas digitales serán discutidos más adelante en las secciones 1.5c y 2.3.