CS 7321 Winter 1998 -- PS#1 Solutions

Tahia Infantes Morris
CS7321
Implementation of "Multiresolution Spline With Application to Image Mosaics" Paper

Index

How I solved it
Assumptions and Weaknesses
How it can be improved
Results
Code

How I solved it

First I began with the reduce and expand funtions. The expand funtion basically took the image pixels and moved each of them over and down two places so that they were separated from their neighbor pixel by a cluster of four. For example, lets say that the pixels in a 4x4 image is like illustrated below. Then after a couple of for loops, it would look like:

                         12 ==>   102
                         22        000
                                   202

The first run basically moves the pixels to the right two places, this is when a 1X5 kernel of a=4 is convolved with the image. Then we move the pixel down by two and we convolve again with the transpose of the kernel -in other words a 5X1 kernel. So, for the expand function, we now have an image that is double the size of the original. The reduce funtion works the opposite way. Each pixel at the bottom right corner of a group of 4 neighbor pixels is copied into a new image. As explained above, first the pixel is shifted left by two places, convolved, then shifted up two places and convolved with the transpose kernel.

Next, I wrote the make pyramid function which creates a structure to contain the Gaussian and Laplacian pyramid images. It figures how many times it needs to expand and reduce based on the image size. I assumed that all images will be same in size for conveniance, that way I could pad them to the 2^Nx2^M format which my algorithm is written around. So, basically, I implemented the left half of the chart that was provided to us in class. In other words, I started with the original image, put it in the Gaussian list and then reduced it, placed it also in the Gaussian list and so on, until the image was down to a size of about 4x4. I had trouble working with the image if it was smaller than 4X4 because the reduce and expand functions needed some padding/borders and so the padding could not be bigger than the image dimensions. So, after the Gaussian list of images was created, It went upwards in the struct and started with the last Gaussian image and expanded it and subtracted it from the Gaussian image above it to obtain the Laplacian image. This was iterated until the algorithm reached the original Gaussian image in the list. This function then sent back the structure which contained both the Gaussian and Laplacian pyramids. I had to send both to the make pyramid function. However, let me explain a little more about what I did......

I originally was only working with gray images to make the problem easier to begin with. I also tried splining down the middle and it worked quite fine. However, what stumped me was how to average the borders of curvy boundaries without having to pull out my dusty-old calc book. I obviously missed a vitle little paragraph in the paper which explained how to include the mask into the algorithm for variable shape splining. This was cool. And, it saved me a lot of work. What I did was take the two images and made a third mask image. I then sent all three images to the make pyramid function and obtained the pyramid for all three of them. Next, I had to put a small for loop to implement the averaging around the variable edges. It was a whole '1' line of code, but this is what killed processor time because it was going pixel by pixel. I ran the little one-liner on all the Laplacian images and created another Laplacian pyramid consisting of the combined images and the mask. I then expanded out the Pyramid at each level and added them to obtain the output image. For color images, I had to run the entire procedure explained above three times to cover the set of three images that make up the color image. I then copied all output images into a 2nX2mX3 array to come up with the color output image.

to TOP

What I learned

Um, lesson #1. Not to sit at the computer hacking away for hours/days. I should have taken a break and some sleep because it would have proven much more efficient. I had a problem with my code which took me three entire days of playing with my code to figure out. I finally figured it out, when I decided to just "screw it" and go to bed. I finally found out that all my problems were due to a misplaced abs() in my code! In either case, the extra time I spent working with this thing made me reread the paper several times and led to discovery of using a mask as a third input image. This made the assignment much more fun - as you will see below. I also learned how to do the 5X5 convolusion to the images thanks to much research on the net. I really think all this filtering stuff is kind of neat, now that I have a "better" understanding (the exam sure proved the opposite). I also learned a lot more of how to use matlab - in particular, about structs and the uint8 and double issues when manipulating and displaying images. Also, I learned how useful the web is - again in finding helpful hints when it comes to figuring out how to define kernels and convolve.

to TOP

Assumptions and Weaknesses

I made the following assumptions

The two images to be splined and mask would be of the same size
The splining would be done with the two images overlapping exactly
I am posting the solution that will take 256x256x3 images because I thought the images wouldn't take up so much room on posting them. The algorithm can take any image 2^Nx2^M.

I think the major weakness of my solutions are:

The waeknesses: I assumed that all images would be the exact size and overlap. This makes the user have to go through and do a lot of manual labor to make sure that the area to be splined aligns exactly with the mask and the other image. The other weakness is the statement I mentioned above about this version assuming that the images are 2^nx2^n. In the driver I have provided below, I didn't pad any of the images I used to fit the 2^NX2^M format because I was too lazy to type a whole 10 lines more of code to find the largest image and pad it and the other images.

to TOP

Improvements and Possible Future Work

I probably could make my code more efficient by taking out some for loops and throwing in some more bit shifting to do divide and multiply. I tried it in a couple of spots. I could also rewrite it to take images of variable sizes.. In other words, let image A be a different size than image B - same with the mask. If I did this, then I would have to assume that some commom corner or point in the images would be where the images will overlap to be splined. I really cannot think of anything else.

to TOP

Results

"I am Irfan of Borg - Resistance is Futile"


The Splined image	Original Irfan Image	Original Locutus Image

The Mask used to create the Spline

The Gaussian Pyramid of one of the three array of images in the original color image

The Laplacian Pyramid of one of the three array of images in the original color image


Hey. Always wanted to know what I'd look like in short hair. =)	That's me	That's someone off the web.

to TOP

Source Code

run_it : the driver to read the images
make_pyramid : creates a structure of Gaussian and Laplacian Pyramid
merge_image: takes the structures of the 2 images and the mask and expands out the output image
expand: function to expand image
reduce: function to reduce image
my_convolve: adds padding to image and calls the convolution operator