Smart and Automated Photomontage Tools (SAPT) based on Poisson Image Editing

I briefly touched on the fact that I was working some photo editing software project back in the fall on my blog, but I never got around to discuss how it works and what it does. The project is called SAPT (Smart and Automated Photomontage Tools) and was the term project that my team and I chose to do for the GTI664 (Traitement de signaux numériques) class. I led a team of four people into making this software. I was responsible for the core algorithm based on the “Poisson Image Editing” paper.

The gist is that this software allows you to load a picture, loosely select a portion of it, load an another picture, drop the selection onto it and let the algorithm do its magic…The algorithm, through some black magic solving of a linear system of Poisson differential equations, seamlessly merges the selection in the background, effectively creating a photomontage.

This was an amazing coding challenge for me as it was quite probably one of the most complicated piece of software that I’ve had to write from scratch. Amazingly enough, our project is still, to this day, the first open implementation of this algorithm.

Now, this algorithm has its flaws as it can’t do a great job at smoothly computing the edges if you happen to hit high-energy chunks of pixels near the borders (i.e where the divergence is too strong). What’s nice is that we’ve designed the software architecture to be really flexible and let us (or others) build upon the existing algorithm. In fact, when I get some spare time I wish to implement a preconditionning algorithm detailed in the “Drag and drop pasting” paper. This preconditionner runs a shortest path algorithm (Dijkstra or A-*) along the edges of the selection (dropping the inner portion) to find the flow of pixels that minimizes the divergence (i.e the Laplacian of the scalar field of pixels). I’m really proud that I was able to come up with an all-Java efficient design (generally selection of 100×100 pixels take less 3 seconds to compute on a Core Duo proc.). Thanks to my use of the Java 5 concurrency framework, it was a breeze to parallelize the computation.

You can try an early beta version, the one that our professor used for correcting the project in december (You’ll need Java 5 or later). As I said, it is far from perfection, but I had a lot of fun developing it last fall.