Extracción de segmentos de una lista de 8 píxeles conectados

situación Actual : estoy tratando de extraer segmentos de una imagen. Gracias al método findContours() de OpenCV, ahora tengo una lista de 8 puntos conectados para cada contorno. Sin embargo, estas listas no son directamente utilizables, porque contienen una gran cantidad de duplicados.

El problema : Dada una lista de 8 puntos conectados, que pueden contener duplicados, extraiga segmentos de ella.

Posibles soluciones:

• Al principio, usé el {[4] de OpenCV]} método. Sin embargo, los resultados son bastante malos... Aquí están los contornos ampliados:

Aquí está el resultado de approxPolyDP() : (9 segmentos! Algunas superposiciones)

Pero lo que quiero es más como : {[16]]}

Es malo porque approxPolyDP() puede convertir algo que "parece varios segmentos" en "varios segmentos". Sin embargo, lo que tengo es una lista de puntos que tienden a repetirse varias veces sobre sí mismos.

Por ejemplo, si mis puntos son:

0 1 2 3 4 5 6 7 8 
  9   

Entonces, la lista de puntos será 0 1 2 3 4 5 6 7 8 7 6 5 4 3 2 1 9... Y si el número de puntos se hace grande (>100) entonces los segmentos extraídos por approxPolyDP() desafortunadamente no son duplicados (es decir : se superponen entre sí, pero no son estrictamente iguales, por lo que no puedo decir simplemente "eliminar duplicados", en lugar de píxeles, por ejemplo)

• Tal vez, tengo una solución, pero es bastante largo (aunque interesante). En primer lugar, para toda la lista de 8 conectados, yo crear un matrix (para eficiencia) y establezca los valores de la matriz en 1 si el píxel pertenece a la lista. Luego, creo un gráfico , con nodos correspondientes a píxeles, y bordes entre píxeles vecinos. Esto también significa que yo añado todos los bordes faltantes entre píxeles (complejidad pequeña, posible debido a la matriz dispersa). Entonces yo remove all possible "squares" (4 neighouring nodes), y esto es posible porque ya estoy trabajando en contornos bastante finos. Entonces puedo inicie un algoritmo minimal spanning tree. Y finalmente, puedo aproximar cada rama del árbol con approxPolyDP()

Segmentación http://img197.imageshack.us/img197/4488/segmentation.png

Aquí hay fotos fantásticas (gracias Paint!) de la lista original, y el gráfico asociado. Luego, cuando agrego bordes entre vecinos. Y finalmente, cuando elimino bordes y hago un árbol de expansión mínimo (no es útil aquí)

Para resumir: Tengo un método tedioso, que aún no he implementado, ya que parece propenso a errores. Sin embargo, les pregunto a ustedes , la gente de StackOverflow: ¿hay otros métodos existentes, posiblemente con buenas implementaciones?

Editar: Para aclarar, una vez que tengo un árbol, puedo extraer "ramas" (las ramas comienzan en hojas o nodos vinculados a 3 o más nodos) Entonces, el algoritmo en el approxPolyDP() de OpenCV es el algoritmo Ramer–Douglas–Peucker, y aquí está la imagen de Wikipedia de lo que hace :

Con esta imagen, es fácil entender por qué falla cuando los puntos pueden ser duplicados entre sí{[16]]}

Otra edición : En mi método, hay algo que puede ser interesante notar. Cuando se consideran los puntos ubicados en una cuadrícula (como píxeles), entonces generalmente, el algoritmo de árbol de expansión mínima no es útil porque hay muchos árboles mínimos posibles

X-X-X-X
|
X-X-X-X

Es fundammentally muy diferente de{[16]]}

X-X-X-X
| | | |
X X X X

Pero ambos son árboles de expansión mínima

Sin embargo, en mi caso, mis nodos rara vez forman clústeres porque se supone que son contornos, y ya hay un algoritmo de adelgazamiento que se ejecuta de antemano en el findContours().

Respuesta al comentario de Tomalak:

Si el algoritmo DP devuelve 4 segmentos (el segmento desde el punto 2 al centro está allí dos veces) ¡estaría feliz! Por supuesto, con buenos parámetros, puedo llegar a un estado donde" por casualidad " tengo segmentos idénticos, y puedo eliminar duplicados. Sin embargo, claramente, el algoritmo no está diseñado para ello.

Aquí hay un ejemplo real con demasiados segmentos: