Finding optimal parallelization from general weighted undirected graph
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.