Question

Problem 4.2. (Difficulty 3) Seam carving is a real-world application of DP for content- aware image resizing. The simplest way to reduce the size of an image is cropping and scaling, i.e. cutting out parts of the image and scaling down the size. However, cropping leaves visible crop lines of incontinuity while scaling reduces the details of the image. We would like to intelligently reducing the size while accounting for the important contents of the image. Seam carving is a method to achieve such goals, by removing a number of seams, which are paths of "least importance" in the image. The seam carving algorithm works as follows. Given an image with n x m pixels, we view it as a table with n rows and m columns. We first compute the “energy" of each pixel. Usually the energy of a pixel is defined as a gradient of color values. Given this energy image, we first find a seam, which is formally defined as a path with the lowest energy, where: • A path is a sequence of pixels such that it has exactly 1 pixel in each row of the image, and its pixels are connected in the sense that in consecutive rows they have column numbers that vary by at most 1. For example, we use (i,j) to indicate the pixel in row i, column j, thus (1,3) is connected with (2, 2), (2,3), and (2, 4) but not (2,5) or (2, 1). The energy of a path is defined as the sum of the energy of the pixels in this path. Then we remove the seam and stitch the remaining parts together, thus reducing the width of the image by 1 pixel. Therefore if we repeatedly call this algorithm k times we can reduce 30 the width of the image by k pixels. Note that the seams we defined above are vertical: they go from the top to the bottom of the image. We can also find horizontal seams to reduce the height of the image, but for simplicity in this problem we only consider vertical seams. See Figure 1 for a real-world example, where multiple seams obtained by running the algorithm repeatedly are colored in red and removed to reduce the width of the original image. Figure 1: Using Seam Carving to Reduce Width of An Image!

Psuedocode works! DP is dynamic programming for this algorithm