Stitch together images with exactly matching (pixel to pixel) overlaps

Question

I have a bunch of images in a folder that are effectively just pieces of one image that was broken into overlapping parts. How can I quickly and programmatically recombine these images to create the original image?

I would prefer a solution that uses python or mathematica (or is an existing application), but I am open to other ideas as well (I am fairly proficient with Java).

Answer 1

Well, I no longer need to do this to do what I want to do, but I will share how I would do this if I were to write it in python (mix of psuedocode and python). Here I assume that the top left corner of subsequent images are always the point of overlap (which was true in my case). If you want to detect overlaps for any corner, you will need to detect which "corner" case you are in and add handling for each case.

images = list of images to be stitched, loaded from directory
stitched_image = images[0]

for (image in images):
    if first image then skip it (continue)
    else combine_images(stitched_image, image)

def combine_images (stitched_image, image_to_add):
    top_left_corner = top left corner of image_to_add 
    // top_left_corner dimensions need to be big enough that you don't have a false positive, 
    // but not so big that the overlap doesn't exist
    coordinates = find_coordinates(stitched_image,top_left_corner)

    new_width = max(stitched_image.width,image_to_add.width + coordinates.x)
    new_height = max(stitched_image.height,image_to_add.width + coordinates.y)
    new_image = new Image(new_width,new_height) // See note 1
    new_image.paste(stitched_image,(0,0))
    new_image.paste(image_to_add,(coordinates.x,coordinates.y))

    stitched_image = new_image

def find_coordinates (image,sub_image):
    // See note 2 below for how to implement

Notes:

1. Creating an image and pasting into it can be accomplised with PIL: http://29a.ch/2009/5/14/concatenating-images-using-python

2. See this question for how to find a sub_image in an image (may need to convert image to another representation): Finding a subimage inside a Numpy image. Also, for any proficient programmer, it wouldn't be at all difficult to manually inspect pixels in the matrix of pixels to find the overlap. You could add in additional optimization if you know roughly where the overlap is likely to occur by simply searching in the more likely areas first.