Algoritmos: coincidencia de Elipse

Tengo muchas imágenes como las siguientes (solo blanco y negro):

enter image description here

Mi problema final es encontrar elipses que combinen bien. Lamentablemente, las imágenes reales utilizadas no siempre son tan agradables como esta. Podrían deformarse un poco, lo que hace que la coincidencia de elipse sea más difícil.

Mi idea es encontrar “puntos de quiebre”. Los marco en la siguiente imagen:

enter image description here

Tal vez estos puntos podrían ayudar a hacer una coincidencia para las elipses. El resultado final debería ser algo como esto:

enter image description here

¿Alguien tiene una idea de qué algoritmo se puede utilizar para encontrar estos puntos de quiebre? ¿O mejor aún para hacer una buena coincidencia de elipse?

Muchas gracias

  1. Muestra los puntos de circunferencia

    Simplemente escanee su imagen y seleccione Todos los píxeles negros con cualquier Blanco vecino. Puede hacer esto cambiando el color de los píxeles negros restantes a cualquier color no utilizado (Azul).

    Una vez completada la imagen completa, puede volver a colorear el revés interior desde el color no utilizado (azul) hasta el blanco.

  2. formar una lista de puntos de circunferencia ordenados por grupo / elipse

    Simplemente escanee su imagen y encuentre el primer píxel negro. Luego use A * para ordenar los puntos de circunferencia y almacene la ruta en alguna matriz o lista pnt[] y manipúlela como una matriz circular.

  3. Encuentra los “puntos de quiebre”

    Se pueden detectar por pico en el ángulo entre los vecinos de los puntos encontrados. algo como

     float a0=atan2(pnt[i].y-pnt[i-1].y,pnt[i].x-pnt[i-1].x); float a1=atan2(pnt[i+1].y-pnt[i].y,pnt[i+1].x-pnt[i].x); float da=fabs(a0-a1); if (da>M_PI) da=2.0*M_PI-da; if (da>treshold) pnt[i] is break point; 

    o utilice el hecho de que en el punto de ruptura el signo del cambio delta del ángulo de la pendiente:

     float a1=atan2(pnt[i-1].y-pnt[i-2].y,pnt[i-1].x-pnt[i-2].x); float a1=atan2(pnt[i ].y-pnt[i-1].y,pnt[i ].x-pnt[i-1].x); float a2=atan2(pnt[i+1].y-pnt[i ].y,pnt[i+1].x-pnt[i ].x); float da0=a1-a0; if (da0>M_PI) da0=2.0*M_PI-da0; if (da0<-M_PI) da0=2.0*M_PI+da0; float da1=a2-a1; if (da1>M_PI) da1=2.0*M_PI-da1; if (da1<-M_PI) da1=2.0*M_PI+da1; if (da0*da1<0.0) pnt[i] is break point; 
  4. elipses en forma

    así que si no se encuentran puntos de ruptura, puede ajustar todo el pnt [] como elipse simple. Por ejemplo Buscar cuadro delimitador. Su centro es el centro de elipse y su tamaño te da semiejes.

    Si se encuentran puntos de quiebre, primero encuentre el cuadro delimitador de pnt[] entero pnt[] para obtener límites para semiejes y búsqueda de área de posición central. Luego divida el pnt[] en partes entre los puntos de ruptura. Maneje cada parte como parte separada de elipse y ajuste.

    Después de que todas las partes pnt[] estén ajustadas, compruebe si algunas elipses no son las mismas; por ejemplo, si están superpuestas por otra elipse, se dividirían ... Por lo tanto, combine las idénticas (o la media para mejorar la precisión). A continuación, vuelva a colorear todos los puntos pnt[i] en blanco, borre la lista pnt[] y el bucle n . ° 2 hasta que no se encuentre más píxeles negros.

  5. cómo ajustar la elipse de la selección de puntos?

    1. algebraicamente

      use la ecuación de elipse con puntos conocidos dispersos "uniformemente" para formar un sistema de ecuaciones para calcular los parámetros de la elipse ( x0,y0,rx,ry,angle ).

    2. geométricamente

      por ejemplo, si detecta la pendiente 0,90,180 o 270 grados, entonces se encuentra en la intersección del eje semi con la circunferencia. Entonces, si tiene dos puntos (uno para cada semieje), eso es todo lo que necesita para ajustar (si es elipse alineado con el eje).

      para las elipses no alineadas al eje, necesita tener una porción lo suficientemente grande de la circunferencia disponible. Puede explotar el hecho de que el centro del cuadro delimitador es también el centro de la elipse. Entonces, si tienes toda la elipse, también conoces el centro. Las intersecciones de semiejes con circunferencia se pueden detectar con el cambio de tangente mayor y menor. Si tienes centro y dos puntos es todo lo que necesitas. En caso de que solo obtenga un centro parcial (solo coordenada x, o), puede combinar con más puntos de eje (buscar 3 o 4) ... o aproximar la información faltante.

      También el eje de las medias H, V líneas se está cruzando el centro de la elipse por lo que se puede utilizar para detectar si no toda la elipse en la lista pnt[] .

      ajuste de elipse no alineado con el eje

    3. búsqueda de aproximación

      Puede recorrer "todas" las combinaciones posibles de parámetros de elipse dentro de los límites que se encuentran en el n . ° 4 y seleccionar el más cercano a sus puntos. Eso sería increíblemente lento de modo que utilice la búsqueda binaria como acercarse a algo como la clase de la mía. Ver también

      • Ajuste de curva con puntos y en posiciones x repetidas (arms Galaxy Spiral)

      sobre cómo se usa para un ajuste similar al tuyo.

    4. híbrido

      Puede combinar el enfoque geométrico y de aproximación. Primero calcule lo que pueda por enfoque geométrico. Y luego calcule el rest con la búsqueda de aproximación. también puede boost la precisión de los valores encontrados.

    En casos excepcionales, cuando dos elipses se fusionan sin punto de ruptura, la elipse ajustada no coincidirá con sus puntos. Entonces, si tal caso se detecta, debe subdividir los puntos usados ​​en grupos hasta que coincidan sus coincidencias ...

Esto es lo que tengo en mente con esto:

visión de conjunto

Probablemente necesites algo como esto:

https://en.wikipedia.org/wiki/Circle_Hough_Transform

Sus puntos de ventaja son simplemente píxeles negros con al menos un vecino blanco de 4.

Desafortunadamente, sin embargo, dices que tus elipsis pueden estar “inclinadas”. Elipses genéricas se describen mediante ecuaciones cuadráticas como

 x² + Ay² + Bxy + Cx + Dy + E = 0 

con B² <4A (⇒ A> 0). Esto significa que, en comparación con el problema del círculo, no tiene 3 dimensiones sino 5. Esto hace que la transformación de Hough sea considerablemente más difícil. Afortunadamente, su ejemplo sugiere que no necesita una alta resolución.


Ver también: algoritmo para detectar un círculo en una imagen


EDITAR

La idea anterior para un algoritmo era demasiado optimista , al menos si se aplicaba de manera directa. La buena noticia es que parece que dos tipos inteligentes (Yonghong Xie y Qiang Ji) ya nos han hecho los deberes:

https://www.ecse.rpi.edu/~cvrl/Publication/pdf/Xie2002.pdf

No estoy seguro de crear mi propio algoritmo. ¿Por qué no aprovechar el trabajo que otros equipos han hecho para descubrir toda esa curva de ajuste de mapas de bits?

INKSCAPE (Enlace de la aplicación)

Inkscape es una herramienta de código abierto que se especializa en la edición de gráficos vectoriales con alguna capacidad para trabajar también con partes de bitmap (bitmap).

Aquí hay un enlace a un punto de partida para la API de Inkscape:

http://wiki.inkscape.org/wiki/index.php/Script_extensions

Parece que puede crear scripts en Inkscape o acceder a Inkscape a través de scripts externos.

También puede hacer algo con cero scripts desde la interfaz de línea de comandos de Inkscape:

http://wiki.inkscape.org/wiki/index.php/Frequently_asked_questions#Can_Inkscape_be_used_from_the_command_line.3F

COREL DRAW (Enlace a la aplicación)

Corel Draw es reconocida como la principal solución de la industria para gráficos vectoriales, y tiene algunas excelentes herramientas para convertir imágenes rasterizadas en imágenes vectoriales.

Aquí hay un enlace a su API:

https://community.coreldraw.com/sdk/api

Aquí hay un enlace al procesamiento de imágenes por lotes de Corel Draw (solución sin script):

http://howto.corel.com/en/c/Automating_tasks_and_batch-processing_images_in_Corel_PHOTO-PAINT