¿Cómo se utilizan conjuntos disjuntos en el etiquetado de componentes conectados?

Question

Tengo problemas para usar conjuntos disjuntos en el etiquetado de componentes conectados. He buscado en muchos ejemplos y también en this question donde Bo Tian proporcionó una muy buena implementación de Conjuntos Disjuntos como lista enlazada de C++. Ya implementé el etiquetado de componentes conectados (las etiquetas son enteros simples) en mi programa, pero me cuesta mucho resolver las equivalencias entre las etiquetas con conjuntos disjuntos.

¿Alguien puede ayudarme en eso - tal vez usando la implementación de Bo Tian? Creo que eso también ayudará a otros cuando lleguen a este punto.

EDITAR

Mi algoritmo pasa a través de la imagen y cuando encuentra dos etiquetas de dos píxeles conectados con diferentes etiquetas que tiene que hacer una nota en el 'registro de equivalencia' (que sería el disjunto establece bosque) . Después de recorrer toda la imagen, tengo que resolver las equivalencias (pasando el segundo pase sobre la imagen) mirando el registro y luego marcando estos píxeles que tienen etiquetas equivalentes al mínimo fuera del conjunto.

Answer 1

Compruebe esto tutorial on DJS. La única modificación es que durante la unión debe conectarse de mayor a menor, por lo que root es siempre el mínimo del conjunto.

Answer 2

los suministros forestales disjuntos-set dos operaciones:

• Unión, que toma dos objetos y los vincula y
• Encuentra, que toma dos objetos y devuelve el ID del grupo de están en.

Los bosques de conjuntos disjuntos se usan principalmente para mantener una partición de un grupo de objetos en una familia de diferentes grupos, cada uno de los cuales unión del otro (es decir, cada objeto está en un máximo de un grupo). El bosquejo de conjuntos disjuntos luego le permite decir de manera eficiente qué objetos hay en cada grupo, o (en aproximadamente O (n) tiempo) para determinar los ID del clúster para cada objeto.

Para utilizar un bosque de conjuntos disjuntos, comenzaría por colocar cada objeto en su propio clúster. A partir de ese momento, cada vez que desee marcar que dos objetos diferentes están en el mismo clúster, utilizará la operación de unión para vincularlos entre sí. Al final, debe llamar al y encontrar en cada punto para determinar a qué grupo pertenece, y desde allí puede leer a qué grupo pertenece todo.

Espero que esto ayude!

Answer 3

Tiene razón, etiquetar los juegos conectados es solo la mitad del trabajo realizado. Encontrar conjuntos disjuntos utilizando equivalencias también es una parte igualmente difícil. Me enfrenté al escenario exacto.

Una forma de encontrar conjuntos disjuntos (después del etiquetado) es mediante el algoritmo Union-Find. Mira el siguiente artículo. Comprenderá desde cero cómo se implementan el etiquetado y la búsqueda de conjuntos disjuntos. Las ilustraciones también se proporcionan con matrices de entrada y salida de muestra.

http://www.codeding.com/articles/connected-sets-labeling

Answer 4

Hay un blog sobre etiquetado componente conectado con el conjunto disjunto:

http://www.keithlantz.net/2011/04/c-implementation-of-the-connected-component-labeling-method-using-the-disjoint-set-data-structure/