Homework answers / question archive / Graph Cut Images Before you start For your projects you will use github

Graph Cut Images Before you start For your projects you will use github

Computer Science

Share With

Graph Cut Images Before you start For your projects you will use github. You can use your own account and create a private repository for the project. To use the Eigen::Vector3d, add -I/usr/include/eigen3/ to your compilation flags and include . CImg is a great library for image reading and writing. Here is code that simply reads and writes an image. To make sure you do not have last-minute problems, you must commit and push an updated README.txt file to your repository by Tuesday, March 22. You should replace the default entries in the readme file with your own information. The default is: gl_login, full_name I would replace this with: adamb, Adam Bargteil We will be using this data to initialize our grades spreadsheat, so it is important that you use comma separated value format with the correct number of entries in the correct order. The Assignment Graphcut Images Compositing along the minimum seam between two images Requirements You are required to implement a graphcut algorithm as well as take your own photos and apply your algorithm to those images to get full credit. NOTE: You should implement max flow/min cut algorithm on your own as you are not allowed to use library for that. You should also implement either texture synthesis or video synthesis or simple panorama stitching (assuming that all images are aligned and have identical overlaps) using Graphcut to find the seam and Poisson blending to make the seams less apparent. Details When compositing two images, it is often a goal to combine them along a seam (series of pixels) that has the minimal difference between the two images, hereafter referred to as the optimal seam. For this project you will be implementing an algorithm that finds the minimal seam between two images. If you've taken a graphics course at Brown, you've probably heard of Seam Carving. You may have even implemented it. That algorithm uses dynamic programming to find the minimal seam of an image along a specific dimension, and then remove it. Unfortunately, that doesn't generalize as well to finding seams that are not along a single dimension. An algorithm called Graphcut (website), was created to address this problem. The algorithm works by formulating the image as a connected graph with edge weights based on the difference between neighboring pixels. This graph is then treated as a max-flow/min-cut problem where the sources are any pixels to be taken only from the first image and the sinks are any pixels to be taken only from the second image. It's quite simple to formulate the optimal seam search as a max-flow/min-cut problem too. You can easily represent the image graph as an adjacency matrix while each entry in the adjacency matrix can be the flow (or as the paper calls them, "constraint arcs"). The paper suggests using the sum of squared difference between the first image and the second image plus the sum of squared difference of the first image and the second image at the neighboring pixel. • s = current pixel • t = neighboring pixel • A = first image • B = second image You will also need to represent the source and sink edge weights in this problem. One solution is to use a mask that signifies that any pixel under the mask must come from that image. The terminal weight for those pixels is set to infinity (or a large value). Once formulated, you can solve the max-flow/min-cut problem and the output should be a labeling of the pixels as belonging to one side or the other. This is effectively a new mask for the image that you can use for compositing. Write up For this project, just like all other projects, you must do a project report in HTML. In the report you will describe your algorithm and any decisions you made to write your algorithm a particular way. Then you will show and discuss the results of your algorithm. Also discuss any extra credit you did. Feel free to add any other information you feel is relevant. Final Advice • A naive implementation will run slowly because of indexing into a sparse matrix. Test your algorithm on smaller images first. • That part of the algorithm can be made significantly faster by finding all the adjacency matrix values ahead of time and then constructing the sparse matrix; see sparse(i,j,s,m,n,nzmax) What to turn in Turn in this assignment electronically by pushing your source code to your class git repository by 11:59 PM on the day of the deadline. Do your development in the proj1 directory so we can find it. Be sure the Makefile will build your project when we run 'make' (or edit it so it will). Also include a README.txt file telling us about your assignment. Do not forget to tell us what (if any) help did you receive from books, web sites. Check in along the way with useful checkin messages. We will be looking at your development process, so a complete and perfectly working ray tracer submitted in a single checkin one minute before the deadline will NOT get full credit. Do be sure to check in all of your source code, Makefile, README, and updated .gitignore file, but no build files, log files, generated images, zip files, libraries, or other non-code content.