Project 3, Part A: Seam Carving & Part B: Mini-Project Solution

Instructions




Seam Carving is an individual project. ’Individual’ means each student must hand in their own answers, and each student must write their own code in the homework. It is admissible for students to collaborate in solving problems. But to help you actually learn the material, what you write down must be your own work, not copied from any other individual. You must also list the names of students (maximum two) you collaborated with.



The Open Ended Mini-Project is a team project. The maximum size of a team is two students.



A team is not allowed to collaborate with another team. Only one individual from each team must submit the code for this part along with the code for the first one.

Maximum late days allowed for this part of the project is the average of the late days of the two students in the team. The late days used will be subtracted from the individual tally of late days for each student.




Part C will be released before October 20th. This will be due on November 7th. Part C is Video Mosaicing. It’s a group project as well. The teams for Part C and Part B should be consistent.



If you prefer, you can do the entire part on your own. However, completion of the project is MANDA-TORY and no extra credit will be offered if you do it individually.



You must make two submissions on Canvas. We recommend that you include a README.txt file in both submissions to help us execute your code correctly.



– Place your code, resulting images and videos for part A into a folder named "Seam_Carving". Submit this as a zip file named <Pennkey_seam.zip




– Before you submit, you need to register your group in Canvas. Students who prefer to do the project individually must join a group too. Team members should join the same empty group or create a new one in case. Each group must have at most two people. This group will continue through part C of project 3. Place your project proposal, project report, code, resulting images and videos for part B into a folder named "Mini-Project". Submit this as a zip file named <Group_Number_Project3B.zip




Your submission folder should include the following:



– your .m or .py scripts for the required functions.




– .m or .py scripts for generating the seam carving video.




– any additional .m or .py files with helper functions you code.




– the images and videos you used




– video files generated for seam carving.




– Any other files required for your mini-project.




This handout provides instructions for two versions of the code: MATLAB and Python. You are free to select either one of them for this project.



Feel free to create your own functions as and when needed to modularize the code. For MATLAB, ensure that each function is in a separate file and that all files are in the same directory. For Python, add all functions in a helper.py file and import the file in all the required scripts.



Start early! If you get stuck, please post your questions on Piazza or come to office hours!



Follow the submission guidelines and the conventions strictly! The grading scripts will break if the guidelines aren’t followed.



Project 3, Part A: Seam Carving




For this part of the project, you will be implementing image resizing utilizing scene carving. The structure of this part of the project is based heavily on the methods outlined by Avidan & Shamir in their paper:




"Seam Carving for Content-Aware Image Resizing"; Avidan, S. & Shamir, A.; 2007




You are strongly encouraged to read this paper prior to starting this part of the project (a link to the paper will be made available on the course wiki).




You are tasked with filling in 5 functions: carv.m/.py, cumMinEngVer.m/.py, cumMinEngHor.m/.py, rmVerSeam.m/.py, rmHorSeam.m/.py




We begin by computing the energy map, e(I) = | ∂∂xI |+| ∂∂yI |. We have provided a function, genEdgeMap.m which computes this for you, in order to maintain consistency in the method by which the energy map is computed. Your task is to fill in the code that follows. For this project, we will be testing you strictly on shrinking an image (making it smaller), though the ideas applied towards enlarging an image are very similar to those of shrinking one.







You must create a video depicting the image resizing operation. You can pad the resized images with zeros to maintain dimensionality.




1 Computing Cumulative Minimum Energy:




You need to complete the code for the functions cumMinEngVer.m and cumMinEngHor.m, which correspond to computing the cumulative minimum energy over the vertical and horizontal seam directions, respectively. The function cumMinEngHor.m has the following structure:

[My, Tby] = cumMinEngHor(e)




(INPUT) e: n ⇥ m matrix representing the energy map.



(OUTPUT) My: n ⇥ m matrix representing the cumulative minimum energy map along horizontal direction.



(OUTPUT) Tby: n ⇥ m matrix representing the backtrack table along horizontal direction.



You’ll notice that Avidan & Shamir, as well as our class notes, define seams for an n ⇥ m image, I as follows:




• A vertical seam sx = {sxi}ni=1 = {(x(i), i)}ni=1, s.t 8i, |x(i) − x(i − 1)| 1, where x is a mapping x : [1, ...., n] ! [1, ...., m] i.e. the corresponding column for a seam pixel at row i along an 8-connected




path from the top to the bottom of the image.




Note that for any vertical seam, there only exists one seam pixel per row.




Similarly, a horizontal seam is defined as sy = {syj}mj=1 = {(y( j), j)}mj=1, s.t 8 j, |y( j) −y( j −1)| 1, where y is a mapping y : [1, ...., m] ! [1, ...., n] As with the vertical seam, there exists one seam pixel per column along an 8-connected seam path.



For a vertical seam, the seam cost is defined as:




n

E(sx) = E(Isx ) = Âe(I(si))




i=1




For horizontal seam, the seam cost is defined as:




m

E(sy) = E(Isy ) = Â e(I(s j ))

j=1




. We seek to identify the optimal seam, s⇤, that minimizes the seam cost, i.e. s⇤ = mins E(s)




To quote Avidan & Shamir:




The optimal seam can be found using dynamic programming. The first step is to traverse the image from the second row to the last row and compute the cumulative minimum energy M for all possible connected seams for each entry (i, j):




Mx(i, j) = e(i, j) + min !Mx(i − 1, j − 1), Mx(i − 1, j)Mx(i − 1, j + 1)"




My(i, j) = e(i, j) + min !My(i − 1, j − 1), Mx(i, j − 1), Mx(i + 1, j − 1)"




At the end of this process, the minimum value of the last row in Mx will indicate the end of the minimal connected vertical seam. Note that you have to record a backtrack table along the way. Hence, in the second step we backtrack from this minimum entry on Mx to find the path of the optimal seam. Also, in order to maintain consistency, if the minimum value is found at multiple indices, choose the smaller index. The definition of My for horizontal seams is similar.




2 Removing a Seam




For this task, you will fill in the two functions, rmVerSeam.m and rmHorSeam.m, which remove vertical and horizontal seams respectively. This task should be fairly simple. You should identify the pixel from Mx or My from which you should begin backtracking in order to identify pixels for removal (rmIdx), and remove those pixels from the input image. You will receive two inputs to each function, the corresponding cumulative minimum energy map, and the image. Utilizing these, you should output an image with one (appropriate) seam removed. The function rmVerSeam.m has the following structure:




[Iy, E] = rmHorSeam(I, My, Tby)




(INPUT) I: n ⇥ m ⇥ 3 matrix representing the input image.



(INPUT) My: n ⇥ m matrix representing the cumulative minimum energy map along the horizontal direction.



(INPUT) Tby: n ⇥ m matrix representing the backtrack table along horizontal direction.



(OUTPUT) Iy: (n-1) ⇥ m ⇥ 3 matrix representing the image with the row removed.



(OUTPUT) E: the cost of seam removal.



3 Discrete Image Resizing




Now that you’re able to handle finding seams of minimum energy, and seam removal, we shall now tackle resizing images when it may be required to remove more than one seam, sequentially and potentially along different directions. When resizing an image from size n ⇥ m to n’ ⇥ m’ (we will assume n0 < n and m0 < m), the sequence of removing vertical and/or horizontal seams is important.




For this task, fill in the function carv.m, making use of the method described below. Utilizing recursive calls of the functions completed in the previous 2 tasks, complete this function to output the resized image.




[Ic, T] = carv(I, nr, nc)







You can add any other features that you wish to.



You can only re-use the codes of your teammate.



Come talk to the TAs and the Professor if you want ideas! The general rules regarding logistics are as follows:
The maximum size of a team is two students.



The teams will be consistent for Part C as well. This applies to individual students too. If you do Part B individually, you must do Part C individually as well.



You must form groups by 22nd October, 11:59 PM



All team members must join ONE EMPTY group on Canvas. If no groups are empty, create an empty one and join it.



Each team should submit a project proposal detailing your proposed project. This should be submitted by 24th October, 11:59 PM. This should be a maximum of 2 pages and should contain: Abstract, Related Work, Proposed Methodology, Expected Results and Expected Applications/Future work.



Each team should submit a project report detailing the project. This should be a maximum of 6 pages and should contain: Abstract, Introduction, Related Work, Implemented Methodology, Comparison with your proposed methodology, achieved results, analysis of comparison with expected results, future work and references. A section detailing the contributions of each member of the team should be included.



Each team will be graded on the validity of their project idea, it’s uniqueness, approach and results.



At a later date, we might announce a short survey asking each member about the contributions of themselves AND their team member. Grades will be adjusted accordingly.



5 Extra Credits:




The following tasks are for extra credit. Implementing any or all of them are optional.




Seam Insertion. Using the same principles of seam removal, you can insert seams to enlarge an image without too much distortion to the "important regions" of the image.



Testing and Submission



Use different kinds of images for seam carving. Experiment with the number of horizontal and vertical seams you remove and how it affects the resultant image.