3.3 Ángulo
En esta sección discutiremos propiedades que implican pendiente y curvatura, como medidas para curvas y bordes. La mayor parte de este material asume que la curva o borde dado está especificado por un código de cadenas. También discutiremos brevemente las relaciones de posiciones relativas (e.g., “a la izquierda de”) entre objetos.
a. Pendiente y
curvatura
La pendiente de un código de cadenas en cualquier punto es un múltiplo de 45º, y la pendiente de un código de fisura es siempre un múltiplo de 90º. Para medir un rango más continuo de pendientes, debemos usar algún tipo de allanamiento. Por ejemplo, podemos definir las k-pendientes izquierda y derecha en el punto P como las pendientes de las líneas que unen P a los puntos k pasos más allá a lo largo de la curva a cada lado. Alternativamente, podríamos definir la k-pendiente de P como la media de las pendientes unitarias (i.e., códigos) en una secuencia de k puntos centrados en P.
La curvatura se define normalmente como el porcentaje de cambio de la pendiente. Aquí de nuevo, si usamos las diferencias de las pendientes unitarias, siempre tenemos un múltiplo de 45º para el código de cadenas, y un múltiplo de 90º para el código de fisuras. Para obtener un rango de valores más continuo, debemos de nuevo usar allanamiento. Por ejemplo, podemos definir la k-curvatura de P como la diferencia entre sus k-pendientes izquierda y derecha. (No querríamos usar la media de las curvaturas unitarias (i.e., las diferencias de códigos consecutivos) en una secuencia de puntos k centrados en P, ya que las curvaturas deberían ser acumuladas mejor que promediadas).
Las k-pendientes (y análogamente para la k-curvatura) pueden tener valores angulares cuyas tangentes son números racionales con denominador £ k. Por supuesto, la k-pendiente no está definida si P está a menos de k de un final del arco. No hemos especificado aquí cómo elegir k; su elección depende de la aplicación particular. Ordinariamente, k no debería ser una fracción demasiado grande de la longitud o perímetro total del arco. (¡Consideremos qué pasaría en el caso de una curva cerrada cuando k es la mitad del perímetro o más!).
Como ejemplo simple, considereramos el arco en la Fig. 21a y asumiremos que es continua indefinidamente en ambas direcciones. Aquí la 1-pendiente derecha es 0º en algunos puntos y 45º en otros, pero la 3-pendiente derecha es tan-1(1/3) en cada punto (esto es porque el arco es periódico con período 3). Para k > 3, las k-pendientes derechas no son todas iguales, pero conforme k aumenta, todas aproximan tan-1(1/3). Similarmente, las k-curvaturas fluctúan para k pequeñas (excepto si todas son cero para k = 3), y aproximan cero conforme k se agranda.
Para un borde, por ejemplo de una región de 1’s, también podemos medir la curvatura en un punto P a partir de la representación de matriz contando el número de 1’s en una vecindad de P. Si es más o menos la mitad del tamaño de la vecindad, el borde es relativamente recto a P; si es mucho más alto o mucho más bajo, el borde tiene una curvatura afilada convexa o cóncava en P. El tamaño de la vecindad usado determina la cantidad de allanamiento en esta definición.
b. Rectitud
Es de interés caracterizar esos arcos digitales que puedan surgir a partir de la digitalización de un límite recto o segmento de línea. Damos una caracterización aquí en términos del código de cadena; el caso del código de fisura se le deja al lector. Como ejemplos, las Figs. 21a y 21b son segmentos de líneas digitales rectos, pero las Figuras 21c-21e no.
Son necesarias las condiciones siguientes en el código de cadenas para la condición de rectitud [53]:
(1) Como máximo dos pendientes aparecen en la cadena, y si hay dos, difieren en 45º. Esto no se cumple en la Fig. 21c.
(2) Al menos una de las dos pendientes aparece en las secuencias de longitud 1. Esto no se cumple en la Fig. 21d.
(3) La otra pendiente aparece en secuencias de al menos dos longitudes (excepto posiblemente en los finales del arco, donde las secuencias pueden estar truncadas), y si hay dos longitudes, difieren en 1. Esto no se cumple en la Fig. 21e.
Estas condiciones no son suficientes. De hecho, resulta que al menos una de las dos longitudes aparece en secuencias de longitud 1; la otra aparece en secuencias de cómo máximo de dos longitudes (excepto en los finales) que difieren en 1; y así sucesivamente. Estas condiciones aseguran que las secuencias de longitud 1 están espaciadas con tanta regularidad como sea posible en la cadena. En cualquier caso, para muchos propósitos uno no debería molestarse en comprobar estas condiciones exactamente; sería suficiente comprobar que la pendiente allanada es aproximadamente constante, o que el ajuste del arco a una línea recta real es bueno.
Fig. 21 Rectitud
digital. (a) y (b) son segmentos de líneas rectas, pero (c)-(e)
no.
Nótese que podría haber más de un segmento de línea recta entre dos puntos, si la dirección de uno al otro no es un múltiplo de 45º. Como un ejemplo muy simple, consideremos
1 1 1
1 1 y 1
c. Segmentación de una
curva
Hay muchas maneras de segmentar una curva en partes. Algunas de estas son análogas a las técnicas para la segmentación de un imagen (Capítulo 10), con la pendiente (o la pendiente allanada) jugando el rol de nivel de gris. Otras no dependen de la pendiente; por ejemplo, podemos segmentar una curva en puntos extremos locales o globales, e.g., el de más a la izquierda, el de más a la derecha, el de más arriba o el de más abajo. Aquí se asume que la segmentación en las uniones, si existen, ya ha sido realizada, así que estamos tratando con un arco simple, curva o borde.
El histograma de pendiente de una curva nos dice con qué frecuencia cada pendiente ocurre en una curva. Por supuesto, no nos dice cómo estas pendientes están organizadas a lo largo de la curva: un squiggle que consta de números iguales de segmentos horizontales y verticales puede que tenga el mismo histograma de pendiente que un cuadrado. Sin embargo, para curvas no complejas es razonable asumir que una cumbre en el histograma ofrece información sobre la orientación del conjunto. Debería también señalarse que si la curva es el borde de un objeto convexo, su histograma de pendiente lo determina, ya que en este caso la secuencia de pendientes alrededor de la curva debe ser monótona. Las Figuras 22a-22c muestran una curva cerrada, su código de cadenas, y su histograma de 1-pendientes; las dos crestas, 180º aparte, corresponden a la orientación predominante de la curva. El histograma de pendiente se llama a veces “espectro direccional”.
La información sobre el “wiggliness”(ondulación) de una curva puede obtenerse por su histograma de curvatura. Para una curva lisa, las curvaturas estarán concentradas cerca del 0, mientras que para una curva wiggly(ondulada) deben estar más esparcidas. Esto es análogo al uso de histogramas de magnitudes diferenciales de nivel de gris para describir la aspereza u ocupación(busyness) de una textura. El histograma de 1-curvatura para la Fig. 22a se muestra en la Fig. 22d; ya que la curva es lisa, los valores absolutos son casi todos £ 1. Uno puede usar el histograma de curvatura para determinar un umbral para la segmentación de una curva en partes curvas y rectas; y similarmente, uno puede usar el histograma de pendiente como una guía para la segmentación de una curva en partes relativamente rectas (“strokes”) en varias direcciones.
Fig. 22
Segmentación de una curva digital. (a) Curva; punto de inicio subrayado,
la curvatura máxima con asterisco, inflexiones con apóstrofe. (b) Código de
cadena. (c) Histograma de 1-pendientes. (d) Histograma de
1-curvaturas.
El análogo de los límites para las curvas son las esquinas; éstas son los puntos donde la pendiente cambia bruscamente, i.e., donde la curvatura absoluta es alta. De este modo las esquinas del tipo más simple son máximos de la curvatura (allanada) [57]. El máximo de la 1-curvatura en la Fig. 22a está con asterisco; hablando de una forma general, representan un conjunto razonable de esquinas. Esta simple definición, sin embargo, no distingue muy bien entre giros lisos y puntiagudos, e.g., entre
mientras que la cantidad total de giro
sea la misma. Una manera de hacer la distinción es comparar las k-curvaturas para varios valores de k; si k’s pequeñas dan el mismo valor que las
grandes en el máximo, la esquina debe ser puntiaguda [20, 60].
Inflexiones(puntos de inflexión) son puntos donde el signo de la curvatura cambia; separan la curva en partes convexas y cóncavas. Las 1-inflexiones en la Fig. 22a tienen apóstrofes.
Varios tipos de características locales en una curva pueden ser detectados dibujando cuerdas. La distancia (máxima) entre una cuerda y su arco es alta (en comparación con la longitud de la cuerda) cuando el arco está una curvado en punta y baja cuando es relativamente recta; pero puede además ser ondulada o S-curvada. Otra medida es el radio de la longitud del arco a la longitud de la cuerda; es alta para una curva puntiaguda o un arco ondulado, y baja para una relativamente recta. Ambas medidas son especialmente altas para “espuelas” o “púas” en la curva Por supuesto, los tamaños de las características que son detectadas de esta manera dependen de las longitudes de los arcos que se utilizan (i.e., de k). (Nótese que esto es una técnica de segmentación de una curva basada en la longitud, más que en la pendiente o la curvatura).
Más generalmente, secuencias arbitrarias de curvatura pueden ser detectadas en una curva por un proceso de correspondencia. Por ejemplo, podemos calcular una suma de diferencias de pendientes absolutas entre los puntos correspondientes, justo como en correspondencia en una imagen, para obtener medidas de desemparejamiento de una “plantilla” con una curva en varias posiciones. La mayor parte de la discusión en el capítulo 9 sobre la correspondencia de imagen se aplica también al emparejamiento de curvas, con las apropiadas modificaciones.
Los métodos de segmentación de una curva mencionados hasta ahora son todos “paralelos”, i.e., se aplican independientemente en todas las posiciones a lo largo de la curva. Uno puede también usar métodos secuenciales análogos al tracking o crecimiento de región, e.g., seguir extendiendo un arco hasta que permanezca encajado relativamente bien en una línea recta. Las técnicas de partición también pueden ser usadas - por ejemplo, si una cuerda no encaja bien en su arco, se subdivide el arco (e.g., en los puntos más lejanos de la cuerda), se dibujan las cuerdas de los dos arcos y se repite el proceso para cada uno. Por supuesto, partición y fusión pueden ser combinados; para una discusión detallada de este acercamiento a la aproximación de curvas ver [46], capítulos 2 y 7, también [9]. Cuando estamos construyendo aproximaciones poligonales de una curva de esta manera, un buen lugar para poner los vértices iniciales del polígono (i.e., los puntos iniciales de segmentación) es en aquellos donde la curvatura es máxima, ya que la gira rápidamente en estos puntos y no puede encajar bien allí mediante un solo segmento de línea.
Los métodos de “relajación” iterativos también pueden usarse para la segmentación de una curva. Por ejemplo, supongamos que en cada punto estimamos probabilidades iniciales de esquinas y no esquinas (= rectas), basadas en la k-curvatura para alguna k. Con cada probabilidad de esquina asociamos la cantidad de giros (e.g., la k-curvatura sí misma, que es la diferencia entre las k-pendientes izquierda y derecha), y con cada probabilidad de recta asociamos la media de estas dos k-pendientes. Las rectas entonces refuerzan las rectas cercanas al extent que sus pendientes coincidan; una esquina refuerza las rectas cercanas a cada lado, al extent que su pendiente en ese lado coincida con la pendiente de la recta, y compite con las esquinas cercanas. Cuando este proceso de refuerzo se itera, las probabilidades de esquina llegan a ser altas en un máximo de una curvatura puntiaguda, y las probabilidades de rectitud se vuelven altas en el resto [12].
d. Ecuaciones de curva y
transformaciones
En el plano real, varios tipos de ecuaciones pueden ser usadas para definir curvas. Las ecuaciones paramétricas especifican las coordenadas de los puntos en la curva como funciones de un parámetro, i.e., x = f (t), y = g (t). La ecuación intrínseca de pendiente especifica la pendiente como una función de la longitud del arco a lo largo de la curva; esto determina la curva una vez que un punto de inicio es dado. Similarmente, la ecuación intrínseca de curvatura especifica la curvatura como una función de la longitud del arco; esto determina la curva, dados un punto de inicio y una pendiente inicial. (El parámetro t en las ecuaciones paramétricas puede ser también la longitud del arco). Una curva puede ser definida a veces especificando una coordenada como función de la otra, e.g., y = f (x) o r = f (q); pero esto sólo posible cuando la función es monovaluada..
Todas estos tipos de ecuaciones pueden usarse para curvas digitales. Aquí la longitud del arco y las coordenadas tienen todas valores discretos. Las funciones pueden ser especificadas listando sus valores, o podemos especificarlos analíticamente y obtener los valores discretos mediante cuantización. Evidentemente, el código de cadenas es una versión digital de la ecuación intrínseca de la pendiente, ya que especifica la pendiente como una función de la posición a lo largo de la curva; nótese, sin embargo, que las posiciones usadas no siempre están equilibradamente espaciadas, ya que los pasos diagonales son Ö2 veces tan largos como los pasos horizontales o verticales. Similarmente, la código de cadenas diferencial (Sección 1.3) es una versión digital de la ecuación intrínseca de curvatura.
Dada una cadena de números especificando una curva, podemos calcular transformación discreta uni-dimensional de la cadena, e.g., su transformada discreta de Fourier. (Nótese que para curvas cerradas, la cadena puede considerarse como periódica, lo que simplifica su análisis de Fourier). En el caso de ecuaciones paramétricas, podemos usar aún una transformación dimensional si combinamos las dos coordenadas reales en una coordenada compleja única, i.e., x + iy = f (t) + ig (t).
La transformación puede proporcionar información descriptiva útil sobre la curva. Por ejemplo, una curva ondulada debería tener contenido de alta frecuencia más fuerte que una curva lisa; se pueden usar rasgos basados en Fourier para medir texturas de aspereza busyness. Las simetrías en la curva deberían ser detectables como crestas en esta transformación, y los valores de la transformación de baja-frecuencia deberían ser buenas descripciones de la forma gruesa de la curva. Si obtenemos estos rasgos de las magnitudes de los coeficientes de Fourier (i.e., a partir del espectro de poder), deberían ser esencialmente invariantes a la rotación, ya que excepto para efectos de cuantización, la rotación de la curva corresponde a un cambio cíclico de las cadenas de los valores que especifican la curva. Podemos conseguir invarianza de escala usando radios de los valores de transformación.
Uno puede incluso “filtrar” una curva operando sobre la transformación y entonces transformar a la inversa, e.g., alisar la curva suprimiendo las altas frecuencias de la transformación. Nótese, sin embargo, que la transformación inversa puede que no sea una simple curva cerrada a menos que los cambios realizados a la transformación sean pequeños.
e. Posición
relativa
En la descripción de una imagen, a menudo queremos hacer declaraciones sobre las posiciones relativas de los objetos en la imagen, e.g., “A está a la derecha de B”, “A está sobre B”, “A está cercana a B”, o “C está entre A y B”. Nótese que excepto “cerca” (y “lejos”), éstas son relaciones de tratamiento relativo, i.e., envuelven la dirección de A como vista desde B, olas direcciones relativas de A y B como vistas desde C.
Para objetos de puntos, no es difícil dar definiciones borrosas para estas relaciones, e.g., “A está a la izquierda de B” tiene valor 1 para la dirección de 180º (donde B está en el origen), y se dirige hacia cero de alguna manera conforme vamos de 180º a ± 90º. Para objetos ampliados, sin embargo, definir estas relaciones se vuelve algo complicado, como se muestra en la Fig. 23. Si requerimos que cada punto de A esté a la izquierda de cada punto de B, los excluimos todos excepto los casos (a) y (b); pero excluir el caso (e) parece irrazonable. Si tan sólo requerimos que cada punto de A esté a la izquierda de algunos puntos de B, incluimos todos excepto el caso (f); pero incluir (d) parece irrazonable. Si requerimos que los A’s centroide estén a la izquierda de los B’s centroide, incluimos todos excepto el caso (d); pero incluir (f) parece irrazonable. Una definición propuesta [76] requiere que dos condiciones tienen que ser satisfechas: los A’s centroide deben estar a la izquierda del punto más a la izquierda de los B’s, y el punto más a la derecha de los A’s deben estar a la izquierda del punto más a la derecha de B’s. Esta definición excluye (c), (d), y (f), lo que es defendible. Sin embargo, una regla puramente basada en coordenadas de este tipo no se habituará a todos los casos; nuestros juicios acerca de “a la izquierda de” dependen de nuestra interpretación tridimensional de la imagen dado, y también pueden depender incluso de los significados de los objetos que aparecen en la imagen.
Fig. 23 La
dificultad de definir “a la izquierda de”. En cuál de estos casos está el objeto
formado por los A’s a la izquierda del objeto compuesto por los
B’s.