Dijkstra image seamer

Let I be an image and let ω be a candidate overlap. Each pixel in the overlap is assigned the squared colour discrepancy

c(x,y) = ‖I(x,y) − I(W−ω+x,y)‖²

Adjacent pixels form a weighted grid graph. Dijkstra’s algorithm finds a minimum-cost path from the first row to the last. Pixels on either side of that path are taken from opposite copies of the image; the path itself is averaged unless seam marking is enabled.

s

working resolution relative to the input

ω

least overlap considered during offset search

w

odd window used to select the initial path vertex

δ

sampling step in the offset search

A horizontal pass increases width; a vertical pass increases height. Repeated passes can increase memory use quickly.

Credit

I first saw this idea in a presentation by my maths teacher around 2012. I made my first version without reading a research paper.

Image Quilting for Texture Synthesis and Transfer by Alexei A. Efros and William T. Freeman (2001) shows a similar way to join images. Its pictures look familiar from that presentation, so it was probably the source.