[ptx] new reference for stitching algorithms

[Andrew C Mihal]

On Mon, 9 May 2005, Pablo d'Angelo wrote:

> PS. I believe the "smartblend"
> http://www.minorlogic.com/projects/smartblend/index.htm
> software uses a very similar approach as your stitcher.

My guess is that smartblend is using a shortest path algorithm on a cost 
function based on the difference between pixel values in the overlap 
region. That is, it tries to avoid running the seam through places in the 
intersection region where the images disagree.

To test this, I did a simple blend of two images - a left image and a 
right image that overlap in the middle. I overlayed the original left 
image over the blending result with the overlay mode set to difference. 
I did this for both smartblend and enblend. This lets you compare the set 
of pixels that each tool changes.

On the left side of the difference image, there are no changed pixels as 
you would expect. As you get closer to the middle of the difference image 
you begin to see some pixels being changed. This is where the tool is 
gradually blending the left image into the right image. The changes 
increase in density until you hit the seam line. After this point, the 
difference image is very intense because this is the region where the 
right image is more heavily weighted. You can see the shape of the seam 
line clearly with this technique.

The enblend seam line runs exactly down the middle of the intersection 
region. The smartblend line has the same start and end points, but weaves 
around in a noisy fashion. I had tried using a shortest path algorithm for 
seam line generation in enblend last year. The general qualities of the 
smartblend seam are the same as I got from the shortest path algorithm in 
my experiments.

I was interested in using a more complex cost function than just the
mismatch between the two images. In addition to that, I wanted the seam
line to not stray too far from the middle of the intersection region. I
also wanted a seam to avoid straight sections, because straight lines tend
to catch the eye. These constraints are not easy to encode into a shortest 
path algorithm. Instead, I formulated the seam line as an active contour 
and I solve for a low-energy seam using simulated annealing. This is still 
pretty experimental. If anyone is interested I can point you to the devel 
branch in the enblend cvs repository.

The graph cut approach that Aseem is using looks very interesting, but I
have not read the referenced paper yet. Also the gradient domain blending
looks exciting. Aseem, can you comment on how big of an overlap region
this technique can handle? I just skimmed the math but it looks like you
have a linear system with one variable for each pixel in the overlap
region. Does this get out of control with really large images?

Andrew

---------------------------------
Andrew Mihal
www-cad.eecs.berkeley.edu/~mihal
mihal at eecs.berkeley.edu