Estoy resolviendo un problema de "mezclar" conjuntos de imágenes superpuestas. Estos conjuntos se pueden representar mediante un gráfico ponderado no dirigido como este:
Cada nodo representa una imagen. Las imágenes superpuestas están conectadas por un borde. El peso del borde representa el tamaño del área de superposición (la combinación de una superposición más grande conduce a una mejor calidad general )
El algoritmo generalmente elimina bordes. Puede hacerlo secuencialmente o en paralelo. Sin embargo, cuando se produce la fusión, los nodos se fusionan y la estructura del gráfico cambia. ¡Entonces la paralelización es posible solo en componentes conectados que no se superponen!
Tales componentes no superpuestos son DB y FEG. Podemos ejecutar el algoritmo de mezcla en estos componentes de forma segura en paralelo. El resultado es el siguiente gráfico (los nodos combinados se muestran en verde):
Ahora no hay más paralelización posible porque dos componentes conectados se superponen (tienen un borde directamente entre ellos).
La versión paralela del algoritmo se vería así:
1. Find connected components (no two are connected directly) and create task for each.
2. Run the tasks in parallel.
3. Update graph.
4. Until single node remains, continue with 1.
La parte difícil es el primer paso: ¿Cómo encontrar el mejor conjunto de componentes conectados?
Una forma sería un algoritmo codicioso que simplemente encuentre el mayor número de componentes en una iteración dada. El algoritmo codicioso maximizará la paralelización al principio pero a costa de muchas iteraciones posteriores.
La solución óptima puede ser traer una buena cantidad de componentes conectados en cada iteración para maximizar la paralelización y minimizar el número de iteraciones al mismo tiempo (por lo que hay dos variables en la optimización).
No puedo pensar en ningún algoritmo de optimización que no sea retroceder, es decir, buscar espacio en todas las posibles evoluciones y elegir el que tenga la máxima paralelización.
Se pueden ignorar los pesos de borde, pero la versión mejorada del algoritmo puede tenerlo en cuenta ya que las áreas más grandes requieren más tiempo para mezclarse (por ejemplo, el área de tamaño 200 tomará aproximadamente el doble de tiempo que dos áreas de tamaño 100). Tener en cuenta los pesos puede conducir a una mejor estrategia para seleccionar componentes (tiempo de ejecución general más rápido del algoritmo).
¿Tiene alguna pista para tal algoritmo de optimización, que encuentra la mejor estrategia de seleccionar partes del gráfico para que haya una paralelización máxima y un número mínimo de iteraciones?
Respuestas:
Esto es muy similar a las superposiciones de la secuencia génica en el ensamblaje del genoma. Capítulo 4 de la tesis de Ananth .
En paralelo, busca pares prometedores y mantiene una estructura de datos de búsqueda de unión distribuida. Vea a Tarjan y Vishkin por su algoritmo de enlace y acceso directo para colapsar los componentes conectados.
Además, puede probar los métodos de gráficos recientes de DeBrujin en trozos de píxeles de filas de 64 bits. Creo que esto te dará los mejores resultados. Para ayudar con los problemas de cuantización, primero reduciría la dimensión de los píxeles a 16 u 8 bits en blanco y negro. Luego aplica una clasificación paralela de los fragmentos de 64 bits y luego los usa para inferir bordes entre las imágenes.
fuente