The requirements for this project can be found on the course website.
I first determine the importance of each pixel in the image using an energy function. For the energy function, I first converted the image to grayscale and used the gradient() function in matlab and then squared each entry in the matrix. I then using dynamic programming to calculate the lowest cumulative cost path from the top to the bottom of the image. I then backtracked the path to remove one pixel from each row. This effectively removed one pixel column from the image.
To remove X pixel columns, I iteratively ran the above algorithm. The energy matrix and the DP table of cumulative costs are re-calculated on every iteration.
This algorithm is slow to execute as the energy values need to be re-calculated on every iteration. The energy function works for most images with a uniform background. The algorithm does not work 100% well for image which have diagonal lines. For instance, we notice that the line edges of the roof of the lincoln memorial (below) is now curved due to seams being removed from the pixels that make up the memorial.
First, I calculated the energy matrix using the same energy function described earlier.
To get X seams, where X is the number of columns I wanted to insert, I did the following:
I used the DP algorithm to look for the seam with the lowest cumulative cost.
I backtracked through the DP table and recorded down the the coordinates of this seam.
As I backtracked, I also set the corresponding entry in the energy matrix to Inf.
I then re-ran the DP algortihm for the next iteration.
Once I had the X lowest seams, I inserted the X seams all at one go through each row. I took the average of the pixels on the right and left of the new pixel to be inserted.
Note that in the above, I had to set the corresponding seam in the energy matrix to a high value (Inf) as I did not want to re-use data from the same left/right pixels. Otherwise, this would result in new seams of the same pixels grouped together. This is due to the DP property that the optimal cumulative cost is based on data from the previous row.
I tried object removal using seam removal and insertion. First, I ask the user to select a polygon area to remove. From the binary image generated, I add negative weights to the affected cells in the associated energy matrix. I then remove X seams where X is the max width of the polygon. As each iteration only removed a seam, I had to re-calculate the energy matrix for each iteration. This meant that for each iteration, I had to remove the seam in the grayscale image, calculate the energy matrix, and repatch the energy matrix with the correct negative weights. Then I added X seams back using the seam insertion algorithm.
I found that the technique worked well with objects that are in a background of uniform texture. The artifacts around the object removed became apparent when the object was in an area of high detail. Smaller objects are also noticeably easier to remove.
