Medición de la rectitud de un segmento de curva (representado como una polilínea)

11

Estoy trabajando en un algoritmo de etiquetado automático de contornos de elevación y uno de los factores que quiero tener en cuenta al decidir las posiciones de las etiquetas es cuán "recto" es un segmento particular de un contorno. Cuanto más recta sea, más probable es que se use para colocar la etiqueta en ese segmento.

Cada contorno está representado por una polilínea (pero con puntos muy juntos para parecer una curva a simple vista). Entonces tengo una longitud fija (ancho de una etiqueta), digamos, 100 píxeles. Si elijo aleatoriamente (o de otro modo) un segmento de contorno con un ancho de 100 píxeles, quiero poder obtener un valor cuantitativo numérico de su rectitud (digamos cero para un segmento de contorno totalmente recto, algún valor mayor que cero para un no segmento recto, y este valor aumenta a medida que aumenta la torcedura).

Busqué respuestas pero no pude encontrar nada realmente útil. Agradecería cualquier sugerencia.

Igor Brejc
fuente

Respuestas:

9

La respuesta depende del contexto : si investigará solo un número pequeño (limitado) de segmentos, podría permitirse una solución computacionalmente costosa. Sin embargo, parece probable que desee incorporar este cálculo en algún tipo de búsqueda de buenos puntos de etiqueta. Si es así, es una gran ventaja tener una solución que sea computacionalmente rápida o que permita una rápida actualización de una solución cuando el segmento de línea candidato varía ligeramente.

Por ejemplo, suponga que tiene la intención de realizar una búsqueda sistemáticaa través de todo un componente conectado de un contorno, representado como una secuencia de puntos P (0), P (1), ..., P (n). Esto se haría inicializando un puntero (índice en la secuencia) s = 0 ("s" para "inicio") y otro puntero f (para "finalización") como el índice más pequeño para cuya distancia (P (f), P (s))> = 100, y luego avanza s por la distancia (P (f), P (s + 1))> = 100. Esto produce una polilínea candidata (P (s), P (s + 1) ..., P (f-1), P (f)) para evaluación. Después de evaluar su "aptitud" para admitir una etiqueta, entonces incrementaría s en 1 (s = s + 1) y procedería a aumentar f a (digamos) f 'ys a s' hasta que una vez más una polilínea candidata exceda el mínimo se produce un intervalo de 100, representado como (P (s '), ... P (f), P (f + 1), ..., P (f')). Al hacerlo, los vértices P (s) ... P (s ' Es altamente deseable que la aptitud pueda actualizarse rápidamente a partir del conocimiento de solo los vértices caídos y agregados. (Este procedimiento de escaneo continuaría hasta s = n; como de costumbre, se debe permitir que f "envuelva" de n de nuevo a 0 en el proceso).

Esta consideración descarta muchas posibles medidas de aptitud ( sinuosidad , tortuosidad , etc.) que de otra manera podrían ser atractivas. Nos lleva a favorecer las medidas basadas en L2 , porque generalmente pueden actualizarse rápidamente cuando los datos subyacentes cambian ligeramente. Tomar una analogía con el Análisis de componentes principales sugiere que consideremos la siguiente medida (donde pequeño es mejor, según lo solicitado): use el menor de los dos autovalores de la matriz de covarianzade las coordenadas del punto. Geométricamente, esta es una medida de la desviación "típica" de lado a lado de los vértices dentro de la sección candidata de la polilínea. (Una interpretación es que su raíz cuadrada es el semieje más pequeño de la elipse que representa los segundos momentos de inercia de los vértices de la polilínea.) Será igual a cero solo para conjuntos de vértices colineales; de lo contrario, excede cero. Mide una desviación promedio de lado a lado en relación con la línea base de 100 píxeles creada por el inicio y el final de una polilínea, y por lo tanto tiene una interpretación simple.

Debido a que la matriz de covarianza es solo 2 por 2, los valores propios se encuentran rápidamente resolviendo una sola ecuación cuadrática. Además, la matriz de covarianza es una suma de contribuciones de cada uno de los vértices en una polilínea. Por lo tanto, se actualiza rápidamente cuando se eliminan o agregan puntos, lo que lleva a un algoritmo O (n) para un contorno de n puntos: esto escalará bien a los contornos altamente detallados previstos en la aplicación.

Aquí hay un ejemplo del resultado de este algoritmo. Los puntos negros son vértices de un contorno. La línea roja continua es el mejor segmento de polilínea candidato de longitud de extremo a extremo mayor que 100 dentro de ese contorno. (El candidato visualmente obvio en la esquina superior derecha no es lo suficientemente largo).

Figura

whuber
fuente
Wow, me tienes perdido allí :). Tiene razón sobre la búsqueda sistemática, ya tengo que hacer eso para obtener la tangente de cada vértice de polilínea / polígono (se prefieren las etiquetas horizontales a las verticales), por lo que en teoría podría extender esta búsqueda para cubrir otras mediciones. Por cierto: ¿produjo el gráfico de muestra utilizando un algoritmo real o manualmente?
Igor Brejc
1
La ilustración es real, pero la implementación que utilicé no utiliza el procedimiento de actualización de covarianza y, por lo tanto, no es computacionalmente óptima.
whuber
2
El gráfico al final hace que esta respuesta sea aún más impresionante
Ragi Yaser Burhum,
2
Igor, debo mencionar que la dirección de la etiqueta es gratuita: viene dada por la dirección del eje mayor de la elipse (el vector propio asociado con el valor propio más grande). Por lo tanto, puede buscar simultáneamente de manera eficiente la mejor combinación de orientación de etiqueta y linealidad de sección de contorno.
whuber
3

En la comunidad de gráficos por computadora, a menudo es necesario encontrar un cuadro delimitador alrededor de un objeto. En consecuencia, ese es un problema bien estudiado, con algoritmos rápidos. Por ejemplo, consulte el artículo de algoritmos de cuadro de límite mínimo de Wikipedia . Puede encontrar el rectángulo de área mínima que rodea su polilínea y luego usar la relación de aspecto, altura / longitud del rectángulo. Para obtener una medida más precisa, puede observar la desviación de la polilínea de la línea central de este rectángulo delimitador.

Joseph O'Rourke
fuente
1
He pensado en usar min. cuadros delimitadores, pero veo dos problemas: a) la complejidad computacional de calcular un cuadro que realmente sería un mínimo (y, por lo tanto, girado), b) dos segmentos de curva con la misma relación de aspecto pueden tener una curvatura muy diferente (piense en una sinusoidal curva con la misma amplitud pero diferentes períodos de onda).
Igor Brejc
1
¡Qué bueno verte aquí en las páginas de SIG, Joseph!
whuber
1
Sí, tengo tu libro "Geometría computacional en C" en mis manos ahora mismo :)
Igor Brejc
1
Gracias por la bienvenida a todos! :-) Me doy cuenta de que mi sugerencia no es la medida ideal, pero la codificación está lista para usar (si tiene el estante correcto). Este tipo de problema se ha estudiado bastante en contextos de fabricación, donde necesitan medir la calidad de una pieza mecanizada.
Joseph O'Rourke
3

No sé si esto ayuda, o incluso si cuenta como una respuesta, pero mientras estaba sentado aquí pensando en la pregunta que acabo de publicar, pensé:

¿Qué sucede si coloca un círculo de un radio particular en su línea de contorno? Ese círculo intersectará la línea de contorno en al menos dos lugares. Cuanto más recta es la línea, más corta es la distancia a lo largo de la línea de contorno entre los dos puntos de intersección. Cuanto mayor sea la distancia a lo largo de la línea de contorno entre los puntos de intersección, más curva será la línea. Si hay más de dos puntos de intersección, la línea de contorno es demasiado curva.

Podrías averiguar qué longitud daría el mejor indicador de rectitud y establecer una rutina para avanzar a lo largo de cada línea de contorno y donde era lo suficientemente recta, coloca la etiqueta.

Estoy seguro de que esto no ayuda demasiado, y lo que digo en inglés es mucho más difícil en cualquier lenguaje de programación que esté utilizando, pero ¿podría ser un comienzo?

Rex-H
fuente
Idea interesante. Para hacerlo más simple, puede calcular la relación entre la longitud del segmento en un lado y la distancia entre los puntos inicial y final. No es tan preciso, pero es rápido de calcular. Y su idea de usar un círculo permitiría un cálculo más preciso de la rectitud.
Igor Brejc
3

El enfoque más fácil que se me ocurre es la relación entre la longitud real de la ruta entre el inicio y el final y la distancia más corta (línea recta) desde el inicio hasta el punto final. Las líneas rectas tendrán relaciones cercanas a uno, mientras que las líneas muy curvas tendrán una relación muy alta.

Esta debería ser una solución realmente fácil de implementar.


Actualización: como Mike notó correctamente, esto sería igual a Sinuosity .

ingrese la descripción de la imagen aquí

bajo oscuro
fuente
Justo lo que se me ocurrió después de leer la respuesta de Rex :)
Igor Brejc
44
básicamente el recíproco de la sinuosidad
Mike T
exactamente :) ....
oscuro
2
Tiene razón en que esto sería fácil de implementar, porque actualizar la longitud a medida que uno busca segmentos apropiados para etiquetar es tan simple como sumar y restar longitudes entre vértices sucesivos. Sin embargo, la sinuosidad no captura efectivamente el sentido en que una curva puede apartarse de la linealidad. Por ejemplo, compare un semicírculo de diámetro 100 con una secuencia lineal de semicírculos de diámetro 1 : ambas curvas tienen la misma sinuosidad, pero la desviación de lado a lado de la primera es 100 veces mayor que la de la segunda (lo que sería una buena base para una etiqueta).
whuber
Tenga en cuenta que si su polilínea dibuja un círculo, este método le dará una sinuosidad infinita que quizás no sea el resultado deseado.
obchardon
1

Al buscar "curvatura" y "polilínea", obtuve esta información ¿Cómo puedo encontrar la curvatura de una polilínea? . Allí sugirió usar volver a la definición de curvatura - K= DF/Ds. Aquí por lo Fque quiere decir phi, o Ten la notación de Wikipedia aquí ( http://en.wikipedia.org/wiki/Curvature ).

Digamos que tiene una secuencia de tres puntos, p0, p1 y p2. calcule la distancia sentre p0 y p1, que es delta de s ( Ds), suponiendo que los puntos estén lo suficientemente cerca uno del otro. Entonces necesita delta de T ( DT), que es el cambio en el vector tangencial unitario entre p0 y p1. Puede haber una manera sofisticada, pero el método en bruto que se me ocurre es tomar dos bectors p0-> p1, p1-> p2, normalizar cada uno para que tenga una longitud de uno, luego tomar la resta vectorial de esos dos y luego determinar la magnitud. Es decir DT. La división produce una curvatura K0_1. agarra p1, p2 y p3 para calcular K1_2y así sucesivamente.

Sin embargo, me pregunto si puedes obtener el contorno como una polilínea, no como píxeles renderizados. Dijiste 100 px, así que eso me preocupa un poco.

yosukesabai
fuente
Gracias por el enlace, tendré que estudiar las matemáticas detrás de él. Mencioné 100px simplemente porque el texto de la etiqueta representada tiene un cierto ancho (en píxeles), 100px fue solo un ejemplo.
Igor Brejc
Pensar en la curvatura es una buena idea. La curvatura a través de secciones de contorno muy suavizadas de longitud suficiente podría ser apropiada, pero la curvatura en sí misma no lo es: un pequeño zig-zag tendría una curvatura extremadamente alta, por ejemplo, pero en general sería intrascendente. Por lo tanto, en efecto, estaría utilizando algún resumen estadístico de la desviación de la linealidad en las secciones de la polilínea. Entre los posibles candidatos, la curvatura sería uno de los cálculos más complejos para realizar.
whuber