Cómo encontrar 4 puntos al lado de la intersección de dos líneas

Question

Digamos que tengo algunos datos de mapa de bits (en negro) sobre los cuales algunas líneas han sido dibujadas a mano en formato vectorial (en verde). Las líneas siguen aproximadamente la forma de los datos de mapa de bits. En algunos lugares, las líneas se cruzan.

Entonces, ¿qué estoy tratando de hacer es, conociendo la posición de la intersección de las líneas verdes, cómo puedo encontrar la posición de A, B, C y D?

Véase más abajo para algunos ejemplos:

No estoy seguro de cómo abordar este problema teniendo en cuenta el posicionamiento aleatorio de las líneas y en algún momento no son ni siquiera dentro de la forma negro. Sin embargo, supongo que debe haber alguna manera. ¿Cualquier sugerencia?

Answer 1

más simple que puedo pensar es la siguiente:

1. filtro de la imagen para eliminar la línea verde. Un enfoque simple sería usar algún tipo de adelgazamiento que se llene con el color de fondo del píxel (s) vecino.

2. Ahora debe tener una imagen que consista únicamente en líneas negras (anchas) y fondo blanco.

3. Filtre la imagen de nuevo con un algoritmo de detección de esquina, como Harris detector. Esto te dará las cuatro esquinas.

Notas:

1. En función de los datos de entrada, es posible obtener más de cuatro esquinas. En cualquier caso, es una buena idea verificar que las cuatro esquinas que extrajo sean las posibles esquinas de la intersección.

2. De nuevo, este es un enfoque bastante rudo, pero si los datos de entrada son tan limpios como en sus imágenes de ejemplo, y la distancia entre las líneas verdes y negras no es demasiado grande, creo que podría funcionar.

Answer 2

Primero, déjenme decir que no sé nada sobre el tema ni he tenido ninguna experiencia con él. Entonces esto es solo mi suposición. Pero comenzaría ignorando las líneas verdes, que, por cierto, tampoco parecen líneas.

Btw, ¿esto tiene que ver con las carreteras?

Por lo tanto, desactive las líneas verdes. Después de eso, toma un cuadrado pequeño como cualquiera de los 4 que obtuviste arriba, hasta que los examinen todos, y busca aquellos que tengan una relación máxima de píxeles en blanco y negro. Esos deberían ser los que tienen la "encrucijada". Al mapear esos píxeles negros que bordean con píxeles blancos, debe tener los bordes del camino/campo. Después de eso, determinar esos puntos debería ser fácil.

Como dije, supongo. Problema interesante: pregunte qué se le ocurrirá a los expertos.

Answer 3

Primero debe extraer los bordes de la imagen original para obtener polígonos que describan el borde blanco y negro.

Luego itera sobre los puntos de estos bordes y calcula una distancia en puntos al punto de intersección de las dos líneas verdes. Las cuatro distancias más pequeñas provienen de los puntos que está buscando.

¿Responde a esta pregunta? ¿O malinterpreté algo?

Si solo quiere las 4 esquinas, no necesita la línea verde: simplemente tome los bordes de la extracción del borde, alise luego con un filtro Savitzky-Golay y calcule la curvatura puntual. El acaba de extraer los puntos con la curvatura máxima.

enfoque

Answer 4

Necesita vectorización de la imagen binaria. Nuestro proyecto universitario fue justo sobre el tema - Corners Toolbox Allowing Processing Binary Images in a Compressed Form (no se confunda con el título - "comprimido" aquí significa que la imagen binaria se convierte primero en listas vinculadas de las llamadas esquinas).

1) convierta la imagen en esquinas (consulte el capítulo 4 del enlace anterior). A continuación, puede usar la interpolación de líneas de los puntos de las esquinas (capítulo 5.5). Modificaría nuestro algoritmo para ver los cambios de grandes pendientes (~ 90 grados) en líneas de trazos más grandes.

2) no necesita la línea verde. Puede usar el algoritmo de esqueletización para encontrar el esqueleto de la parte negra (consulte el capítulo 5.4) e interpolar este esqueleto con líneas (consulte el capítulo 5.5 del enlace anterior).

Si está interesado en el proyecto, puedo preguntarles a los colegas si podemos proporcionar el código fuente.

Answer 5

La forma más fácil sería una esqueletización. Primero separe la imagen verde y la imagen negro/blanco. Ejecutar un algoritmo de esqueleto (una operación morfológica bastante simple, también en OpenCV) en ambas imágenes y determinar los puntos de intersección (se puede hacer con un recuento de píxeles simple de 8 barrios en imágenes de esqueleto: es decir, para cada píxel negro cuántos los píxeles están conectados horizontalmente, verticalmente o diagonalmente, y si este valor es> = 4, es una intersección). Ahora haz una coincidencia con el vecino más cercano para estos puntos esqueletizados, y listo.

Answer 6

Supongo que usted sabe cómo obtener las coordenadas (x,y) de la intersección de línea de vector (verde), por lo que voy a omitir esa parte.

Comenzando en el píxel más cercano a (x,y), marche gradualmente hacia afuera en una espiral cuadrada (o algún otro patrón de búsqueda de su agrado) de píxel a píxel. En cada paso, verifica si estás en un píxel negro con una y solo una blanca Moore neighbour. Si es así, entonces el lugar donde se tocan el píxel negro y su vecino blanco (probablemente una esquina común) es uno de tus puntos (llámalo A). Continúa marchando hasta que hayas encontrado tres más (B, C, D). Estos serán los cuatro puntos más cercanos a la intersección verde, lo que funcionará bien en los cuatro ejemplos que muestra en su pregunta.

Sin embargo, este algoritmo fallará si la intersección verde está a medio camino entre dos intersecciones negras; en este caso, mezclará puntos de ambas intersecciones negras. Si le preocupa esto, tan pronto como encuentre el punto A, reinicie su espiral de marcha, centrada en A esta vez, y marche hasta que encuentre B, C, D. Esto tendrá efecto ". chasquear "a la intersección negra más cercana.

Puede agregar más inteligencia para evitar buscar en la misma área dos veces; reinicia o vuelve a enfocar tu patrón de búsqueda una vez que hayas encontrado B y una vez más cuando hayas encontrado C, etc. Depende de lo elegante que quieras/necesites obtener.

Answer 7

Debería poder encontrar el punto donde se cruzan las líneas verdes, así como el punto medio donde las líneas negras se cruzan por un proceso de erosión (se reduce a puntos). A continuación, use un par de puntos más cercanos para determinar qué intersección de líneas negras es más cercana a la intersección de la línea verde.

Luego, puede hacer una búsqueda desde el punto donde se cruzan las líneas negras. Necesitará una cola de prioridad que procesará los puntos de acuerdo con su distancia desde el punto de intersección de las líneas negras, el más cercano primero. Coloque los cuatro puntos adyacentes en la intersección de líneas negras en la cola. Para cada punto de la cola, querrá comprobar si se trata de un píxel blanco (queremos eso), comprobar que no se haya visitado antes (omitir en ese caso), y luego agregar sus cuatro píxeles adyacentes a la cola. Los primeros cuatro píxeles blancos deberían ser los que quieras (suponiendo que tienes un buen método de esqueletización/contracción para encontrar la intersección), pero en realidad deberías tomar píxeles blancos hasta que encuentres los primeros cuatro que no estén adyacentes entre sí. .