image - Algoritmos: coincidencia de elipse
algorithm ellipse (3)
-
Muestra los puntos de circunferencia
Simplemente escanee su imagen y seleccione Todos los píxeles negros con cualquier vecino blanco. Puede hacer esto volviendo a colorear los píxeles negros restantes a cualquier color no utilizado (azul).
Una vez completada la imagen, puede volver a colorear el interior del color no utilizado (azul) a blanco.
-
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 almacenar la ruta en alguna matriz o lista
pnt[]y manejarla como una matriz circular. -
Encuentra los "puntos de quiebre"
Se pueden detectar por pico en el ángulo entre vecinos de 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 use el hecho de que en el punto de ruptura el ángulo de pendiente delta cambia el signo:
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; -
elipses en forma
así que si no se encuentran puntos de ruptura, puede ajustar todo el pnt [] como una sola elipse. Por ejemplo, Buscar cuadro delimitador. Su centro es el centro de la elipse y su tamaño te da semiejes.
Si se encuentran puntos de ruptura, primero encuentre el cuadro delimitador de
pnt[]completopnt[]para obtener límites para semiejes y búsqueda de área de posición central. Luego divida elpnt[]en partes entre los puntos de ruptura. Maneje cada parte como parte separada de la elipse y ajuste.Después de que todas las partes
pnt[]estén ajustadas, compruebe si algunas elipses no son iguales, por ejemplo, si se superponen con otra elipse, se dividirían ... Así que combine las idénticas (o promedio para mejorar la precisión). Luego, vuelva a colorear todos los puntospnt[i]en blanco, borre la listapnt[]y realice el bucle n . ° 2 hasta que no se encuentren más píxeles negros. -
¿Cómo ajustar la elipse de la selección de puntos?
-
algebraicamente
utilice la ecuación de elipse con puntos conocidos dispersos "uniformemente" para formar un sistema de ecuaciones para calcular los parámetros de elipse (
x0,y0,rx,ry,angle). -
geométricamente
por ejemplo, si detecta una pendiente de 0,90,180 o 270 grados, entonces está en una intersección de semieje con circunferencia. Entonces, si tiene dos de esos puntos (uno para cada semieje), eso es todo lo que necesita para el ajuste (si es una elipse alineada con el eje).
para elipses no alineadas con ejes, debe tener disponible una porción lo suficientemente grande de la circunferencia. Puede explotar el hecho de que el centro del cuadro delimitador también es el centro de la elipse. Entonces, si tienes toda la elipse, también conoces el centro. Las intersecciones semiejes con circunferencia se pueden detectar con el cambio tangente más grande y más pequeño. Si tienes el centro y dos puntos es todo lo que necesitas. En caso de que tenga solo un centro parcial (solo coordenadas X o Y), puede combinarlo con más puntos de eje (encontrar 3 o 4) ... o aproximar la información que falta.
Además, el eje de las líneas media H, V se cruza con el centro de la elipse, por lo que puede usarse para detectarlo, si no la elipse completa en la lista
pnt[]. -
búsqueda de aproximación
Puede recorrer "todos" la combinación posible de parámetros de elipse dentro de los límites que se encuentran en el n . ° 4 y seleccionar el que esté más cerca de sus puntos. Eso sería increíblemente lento o grosero, así que use la búsqueda binaria como un enfoque similar al mío aproximadamente en mi clase . Ver también
- Ajuste de curva con puntos y en posiciones repetidas x (brazos Galaxy Spiral)
sobre cómo se usa para un ajuste similar al tuyo.
-
híbrido
Puede combinar el enfoque geométrico y de aproximación. Primero calcule lo que pueda por aproximación geométrica. Y luego calcule el resto con búsqueda de aproximación. También puede aumentar la precisión de los valores encontrados.
En casos excepcionales, cuando se fusionan dos elipses sin punto de ruptura, la elipse ajustada no coincidirá con sus puntos. Entonces, si se detecta ese caso, debe subdividir los puntos utilizados en grupos hasta que coincidan ...
-
Esto es lo que tengo en mente con esto:
Tengo muchas imágenes como las siguientes (solo en blanco y negro):
Mi último problema es encontrar elipses que coincidan bien. Lamentablemente, las imágenes reales utilizadas no siempre son tan bonitas como esta. Se podrían deformar un poco, lo que hace que la coincidencia de elipse sea probablemente más difícil.
Mi idea es encontrar "puntos de quiebre". Los marco en la siguiente imagen:
Quizás estos puntos podrían ayudar a hacer una correspondencia para las elipses. El resultado final debería ser algo como esto:
¿Alguien tiene idea de qué algoritmo se puede usar para encontrar estos puntos de quiebre? ¿O incluso mejor para hacer una buena combinación de elipse?
Muchas gracias
No estoy seguro de crear mi propio algoritmo. ¿Por qué no aprovechar el trabajo que otros equipos han hecho para descubrir todo ese ajuste de curvas 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 cierta capacidad para trabajar también con partes ráster (mapa de bits).
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 escribir en Inkscape o acceder a Inkscape a través de scripts externos.
También puede hacer algo con cero secuencias de comandos, desde la interfaz de línea de comandos de inkscape:
COREL DRAW (Enlace de la aplicación)
Corel Draw es reconocido como la principal solución de la industria para gráficos vectoriales, y tiene algunas herramientas excelentes 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
Probablemente necesites algo como esto:
https://en.wikipedia.org/wiki/Circle_Hough_Transform
Sus puntos de borde son simplemente píxeles negros con al menos un 4 vecino blanco.
Sin embargo, desafortunadamente, usted dice que sus elipses pueden estar "inclinadas". Las 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 han hecho la tarea por nosotros: