Seam Carving

Implementing a content-aware image resizing algorithm.¹

Learning goals

• Solve a real-world graph problem via reduction.

  Reduction is an important tool in computer science theory, but it also has practical applications for solving real-world problems. One of the building blocks of computer science is the idea of abstraction, and reductions represent one of the strongest forms of abstractions by using the solution to one problem as a “black box” for solving a different but somehow related problem.

• Represent problem solutions as states in a graph.

  In class, we presented several graph algorithms for solving a variety of classical graph problems including shortest paths and minimum spanning trees. But in the real-world, problems rarely immediately jump out as solvable with graph algorithms. How we represent the problem as a graph is one of the most important decisions as it determines which algorithms we can employ to solve the problem.

• Apply graph augmentation as a strategy for solving a new class of graph problems.

  After coming up with a graph representation of the problem (an abstraction), we can then formally define the problem in terms of the abstraction. However, our problem still might be hard to solve! In seam carving, we need to find the weighted shortest path from any vertex in a distinguished set S to another set T. One common strategy for solving these problems is by augmenting the graph with additional nodes or edges.

Due Date

Please be forewarned that we will not accept late submissions beyond the 11:59pm due date because of the grade submission deadline.

Getting the Assignment

Task

Pull the skeleton repository to get the seamcarving assignment.

If IntelliJ doesn’t properly recognize the new files or complains about failing to resolve classes or interfaces from previous assignments, refresh Gradle manually through the Gradle tool window (on the right by default):

Feedback Survey

After completing both the programming and experiment portions of the assignment, we’d appreciate if you take a couple minutes to complete the individual feedback survey on Canvas for extra credit. (Each partner needs to submit their own individual response.)

Table of contents

• Intro and Energy - Familiarize yourself with the resizing algorithm and implement the required pre-processing.
• Seam Finding - Implement the logic to find seams to remove.