<p>This is very similar to overlaps of gene sequence in genome assembly. Chapter 4 of <a href="http://www.eecs.wsu.edu/~ananth/papers/Ananth_dissertation06.pdf" rel="nofollow">Ananth's thesis</a>.</p>

<p>In parallel you search for promising pairs and maintain a distributed union find data structure. See <a href="http://www.umiacs.umd.edu/users/vishkin/TEACHING/ENEE759KS12/TV85.pdf" rel="nofollow">Tarjan and Vishkin</a> for their hook and shortcut algorithm to collapse the connected components.</p>

<p>Also, you can try recent <a href="http://bioinformatics.oxfordjournals.org/content/21/suppl_2/ii79.short" rel="nofollow">DeBrujin graph methods</a> 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. </p>

CC BY-SA 3.0
2013-08-17T13:25:14.887Z
2013-08-17T13:37:31.577Z
2013-08-17T13:37:31.577Z
Chad Brewbaker
<p>I am solving a problem of "blending" sets of overlapping images. These sets can be represented by undirected weighted graph such as this one:</p>

<p><img src="https://i.sstatic.net/b9AKw.gif" alt="7-node graph"></p>

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

<p>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!</p>

<p>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):</p>

<p><img src="https://i.sstatic.net/uTXQU.gif" alt="4-node graph"></p>

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

<p>The parallel version of the algorithm would look like this:</p>

<pre><code>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.
</code></pre>

<p>The tricky part is the first step: <strong>How to find best set of connected components?</strong></p>

<p>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.</p>

<p>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).</p>

<p>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.</p>

<p>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).</p>

<p><strong>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?</strong></p>

CC BY-SA 3.0
2013-12-15T21:22:37.627Z
Connected component is not the right word here. The original graph is connected. Do you mean partition the vertices to $T,S_1,\ldots,S_k$, such that the distance between $S_i$ and $S_j$ is at least 2? There is no restriction on how $S_i$ should look like?(for example I don't see how you "blend" any subgraph). It's also unclear what you mean by iterations.
Chao Xu
<ds.algorithms><graph-theory><graph-algorithms><directed-acyclic-graph><parallel>
Finding optimal parallelization from general weighted undirected graph
Libor
# Finding optimal parallelization from general weighted undirected graph

(Asked by: username_0 on 2013-08-06)

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?

**Tags:** ds.algorithms, graph-theory, graph-algorithms, directed-acyclic-graph, parallel
> **Comments:**
> **username_1**: Connected component is not the right word here. The original graph is connected. Do you mean partition the vertices to $T,S_1,\ldots,S_k$, such that the distance between $S_i$ and $S_j$ is at least 2? There is no restriction on how $S_i$ should look like?(for example I don't see how you "blend" any subgraph). It's also unclear what you mean by iterations.  

---

## 1 answers

### Answer by username_2 on 2013-08-17. Score: 1

This is very similar to overlaps of gene sequence in genome assembly. Chapter 4 of [Ananth's thesis](http://www.eecs.wsu.edu/~ananth/papers/Ananth_dissertation06.pdf).

In parallel you search for promising pairs and maintain a distributed union find data structure. See [Tarjan and Vishkin](http://www.umiacs.umd.edu/users/vishkin/TEACHING/ENEE759KS12/TV85.pdf) for their hook and shortcut algorithm to collapse the connected components.

Also, you can try recent [DeBrujin graph methods](http://bioinformatics.oxfordjournals.org/content/21/suppl_2/ii79.short) 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.


---

