Finding optimal parallelization from general weighted undirected graph

Question

I am solving a problem of "blending" sets of overlapping images. These sets can be represented by undirected weighted graph such as this one:

Each node represents an image. Overlapping images are connected by an edge. Edge weight represents overlap area size (blending larger overlap sooner leads to better overall quality).

The algorithm generally removes edges. It can do it sequentially or in parallel. However, when blending occurs, the nodes merge and the graph structure changes. So parallelization is possible only on connected components that are themselves not overlapping!

Such non-overlapping components are D-B and F-E-G. We can run the blending algorithm on these components safely in parallel. The result is the following graph (merged nodes are displayed in green):

Now there is no further parallelization possible because any two connected components are overlapping (they have an edge directly between them).

The parallel version of the algorithm would look like this:

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.

The tricky part is the first step: How to find best set of connected components?

One way would be a greedy algorithm that simply finds the largest number of components at a given iteration. The greedy algorithm will maximize parallelization in the beginning but at the cost of many iterations later.

The optimal solution may be bringing good amount of connected components in each iteration to maximize parallelization and minimize number of iterations at the same time (so there are two variables in the optimization).

I can't think of any optimization algorithm other than backtracking, i.e. search space of all possible evolutions and choose the one with maximum parallelization.

Edge weights can be ignored, but improved version of the algorithm may take it into account as larger areas takes more time to blend (e.g. area of size 200 will take roughly twice the time to blend than two areas of size 100). Taking weights into account may lead to better strategy on selecting components (faster overall running time of the algorithm).

Do you have any clues for such optimization algorithm, that finds the best strategy of selecting parts of graph so that there is maximum parallelization and minimum number of iterations?

Answer 1

This is very similar to overlaps of gene sequence in genome assembly. Chapter 4 of Ananth's thesis.

In parallel you search for promising pairs and maintain a distributed union find data structure. See Tarjan and Vishkin for their hook and shortcut algorithm to collapse the connected components.

Also, you can try recent DeBrujin graph methods on 64 bit row chunks of pixels. I think this will give you the best results. To help with quantization problems I would first reduce dimension of the pixels to 16 or 8 bit black/white. You then apply a parallel sort the 64 bit chunks, and then use them to infer edges between images.