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

image-processing graph

Question

Situación actual : estoy tratando de extraer segmentos de una imagen. Gracias al método findContours() de findContours() , ahora tengo una lista de 8 puntos conectados para cada contorno. Sin embargo, estas listas no son utilizables directamente, ya que contienen muchos duplicados.

El problema : dada una lista de 8 puntos conectados, que pueden contener duplicados, extraer segmentos de él.

Soluciones posibles :

• Al principio, usé el método approxPolyDP() de approxPolyDP() . Sin embargo, los resultados son bastante malos ... Aquí están los contornos ampliados:

Aquí está el resultado de approxPolyDP() : (9 segmentos! Alguna superposición)

pero lo que quiero es más como:

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

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 vuelve grande (> 100) entonces los segmentos extraídos por approxPolyDP() son desafortunadamente no duplicados (es decir: se superponen entre sí, pero no son estrictamente iguales, así que no puedo decir "eliminar duplicados", a diferencia de los píxeles, por ejemplo)

• Tal vez, tengo una solución, pero es bastante larga (aunque interesante). En primer lugar, para todas las 8 listas conectadas, creo una matriz dispersa (por eficiencia) y establezco los valores de 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 agrego todos los bordes que faltan entre los píxeles (complejidad pequeña, posible debido a la matriz dispersa). Luego elimino todos los "cuadrados" posibles (4 nodos vecinos), y esto es posible porque ya estoy trabajando en contornos bastante finos. Entonces puedo lanzar un algoritmo de árbol de expansión mínimo . Y finalmente, puedo aproximarme a cada rama del árbol con approxPolyDP de approxPolyDP()

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

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

En resumen: tengo un método tedioso, que aún no he implementado, ya que parece propenso a errores. Sin embargo, les pregunto, 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) Luego, el algoritmo en openPV approxPolyDP() 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 el uno del otro

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

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

es fundamentalmente diferente de

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 conglomerados porque se supone que son contornos, y ya existe un algoritmo de adelgazamiento que se ejecuta de antemano en findContours() .

Responda al comentario de Tomalak:

Si el algoritmo DP devuelve 4 segmentos (el segmento del 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 eso.

Aquí hay un ejemplo real con demasiados segmentos:

Answer 1

Implementé un algoritmo similar anteriormente, y lo hice en una especie de mínimos cuadrados incrementales. Funcionó bastante bien. El pseudocódigo es algo así como:

L = empty set of line segments
for each white pixel p
  line = new line containing only p
  C = empty set of points
  P = set of all neighboring pixels of p
  while P is not empty
    n = first point in P
    add n to C
    remove n from P
    line'' = line with n added to it
    perform a least squares fit of line''
    if MSE(line) < max_mse and d(line, n) < max_distance
      line = line''
      add all neighbors of n that are not in C to P
  if size(line) > min_num_points
    add line to L

donde MSE (línea) es el error cuadrático medio de la línea (suma sobre todos los puntos en la línea de la distancia cuadrada a la línea de mejor ajuste) y d (línea, n) es la distancia desde el punto n a la línea. Los buenos valores para max_distance parecen ser un píxel más o menos y max_mse parece ser mucho menor, y dependerá del tamaño promedio de los segmentos de línea en su imagen. 0.1 o 0.2 píxeles han funcionado en imágenes bastante grandes para mí.

He estado usando esto en imágenes reales preprocesadas con el operador Canny, por lo que los únicos resultados que tengo son de eso. Este es el resultado del algoritmo anterior en una imagen:

Es posible hacer que el algoritmo sea rápido también. La implementación de C ++ que tengo (fuente cerrada impuesta por mi trabajo, lo siento, si no, se la daría) procesó la imagen de arriba en aproximadamente 20 milisegundos. Eso incluye la aplicación del operador Canny para la detección de bordes, por lo que debería ser incluso más rápido en su caso.

Answer 2

Prueba la morfología matemática. Primero necesitas dilate o close tu imagen para llenar los agujeros.

cvDilate(pimg, pimg, NULL, 3);
cvErode(pimg, pimg, NULL);

Tengo esta imagen

El siguiente paso debería ser aplicar algoritmo de thinning . Desafortunadamente no está implementado en OpenCV (MATLAB tiene bwmorph con argumento thin ). Por ejemplo, con MATLAB refine la imagen a esta:

Sin embargo, OpenCV tiene todas las operaciones morfológicas básicas necesarias para implementar el raleo ( cvMorphologyEx , cvCreateStructuringElementEx , etc.).

Otra idea.

Dicen que la transformación a distancia parece ser muy útil en tales tareas. Tal vez sea así. Considere la función cvDistTransform . Crea una imagen como esa:

Luego, usando algo como cvAdaptiveThreshold :

Eso es esqueleto. Supongo que puede iterar sobre todos los píxeles blancos conectados, encontrar curvas y filtrar segmentos pequeños.

Answer 3

Puede comenzar extrayendo líneas rectas de su imagen de contornos utilizando HoughLinesP que se proporciona con openCV:

HoughLinesP(InputArray image, OutputArray lines, double rho, double theta, int threshold, double minLineLength = 0, double maxLineGap = 0)  

Si elige threshold = 1 y minLineLenght small, incluso puede obtener todos los elementos individuales. Tenga cuidado, ya que produce muchos resultados en caso de que tenga muchos píxeles de borde.

Answer 4

Usando Mathematica 8, creé un gráfico morfológico de la lista de píxeles blancos en la imagen. Está funcionando bien en su primera imagen:

Crea el gráfico morfológico:

graph = MorphologicalGraph[binaryimage];

Luego puede consultar las propiedades del gráfico que le interesan.

Esto le da los nombres del vértice en el gráfico:

vertex = VertexList[graph]

La lista de los bordes:

EdgeList[graph]

Y eso le da las posiciones del vértice:

pos = PropertyValue[{graph, #}, VertexCoordinates] & /@ vertex

Así es como se ven los resultados de la primera imagen:

In[21]:= vertex = VertexList[graph]

Out[21]= {1, 3, 2, 4, 5, 6, 7, 9, 8, 10}

In[22]:= EdgeList[graph]

Out[22]= {1 /[UndirectedEdge] 3, 2 /[UndirectedEdge] 4,  3 /[UndirectedEdge] 4, 
          3 /[UndirectedEdge] 5, 4 /[UndirectedEdge] 6,  6 /[UndirectedEdge] 7, 
          6 /[UndirectedEdge] 9, 8 /[UndirectedEdge] 9,  9 /[UndirectedEdge] 10}

In[26]:= pos = PropertyValue[{graph, #}, VertexCoordinates] & /@ vertex

Out[26]= {{54.5, 191.5}, {98.5, 149.5},  {42.5, 185.5}, 
          {91.5, 138.5}, {132.5, 119.5}, {157.5, 72.5},
          {168.5, 65.5}, {125.5, 52.5},  {114.5, 53.5}, 
          {120.5, 29.5}}

Dada la documentación, http://reference.wolfram.com/mathematica/ref/MorphologicalGraph.html , el comando MorphologicalGraph primero calcula el esqueleto por adelgazamiento morfológico:

skeleton = Thinning[binaryimage, Method -> "Morphological"]

Luego se detectan los vértices; son los puntos de ramificación y los puntos finales:

verteximage = ImageAdd[
                  MorphologicalTransform[skeleton, "SkeletonEndPoints"],   
                  MorphologicalTransform[skeleton, "SkeletonBranchPoints"]]

Y luego los vértices se vinculan después del análisis de su conectividad.

Por ejemplo, uno podría comenzar rompiendo la estructura alrededor del vértice y luego buscar los componentes conectados, revelando los bordes del gráfico:

comp = MorphologicalComponents[
           ImageSubtract[
               skeleton, 
               Dilation[vertices, CrossMatrix[1]]]];
Colorize[comp] 

El diablo está en los detalles, pero eso suena como un punto de partida sólido si desea desarrollar su propia implementación.