Fill This Form To Receive Instant Help

Help in Homework
trustpilot ratings
google ratings


Homework answers / question archive / CMSC 641: Design and Analysis of Algorithms Project 1 Graph Cut Images Before you start For your projects you will use github

CMSC 641: Design and Analysis of Algorithms Project 1 Graph Cut Images Before you start For your projects you will use github

Computer Science

CMSC 641: Design and Analysis of Algorithms

Project 1
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, share the repository with any teammates and the TA.

To use the Eigen::Vector3d, add -I/usr/include/eigen3/ to your compilation flags and include <Eigen/Dense>.

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. (Failure to do so will annoy the TA and cost you 10 points of extra credit.)

The Assignment

image equation

Project 3: Graphcut Images

Compositing along the minimum seam between two images (Kwatra, et al.Website).

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.

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.

graph cut

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.

graph cut

  • 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.

Team Credit

You are free to do whatever extra credit you can think of. The paper has many suggestions: texture synthesis, video synthesis, etc. Another possible extension that one of the TAs has done is a 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. The TAs recommend that you hold off on the more advanced versions of the mentioned extra credit, especially patch-matching texture synthesis and panorama stitching as they will appear in later projects.

You must do at least 1 for of team credit for each additional team member.

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)

 

Credits

Project shamelessly stolen from James Hays 2010 Computational Photography course. That project was derived from Kwatra, et al.website.

Strategy

This is a big assignment. Start NOW, or you will probably not finish. No, really, I promise you will not be able to do it in the last two days.

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 or people other than the instructor and TA.

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.

Only one submission per team please. If you are part of a team, have one person submit the project, other team members should submit a readme that indicates who submitted the project

(This page: www.csee.umbc.edu/~adamb/641/proj1.html)

pur-new-sol

Purchase A New Answer

Custom new solution created by our subject matter experts

GET A QUOTE

Answer Preview

built min flow max cut graph cut algorithm with simple GUI
added a readme file to know how to run the scripts
you can add any 2 images to test the script but change the name to src and target

https://drive.google.com/file/d/1jOBxxvS5kL6o4_5Rzj5ADpzfNGcnZTCw/view?usp=sharing

Related Questions