Seam Carving

Problem Statement

Seam carving is an algorithm that allows for content aware resising of images. The idea with seam carving, is that when you resise an image, you will preserve the features of that image.

The purplish lines above are known as paths of lowest energy and are carved out column-wise when the image is resized horizontally. Formally, we can define the problem as follows:

You are given an $N$ by $N$ 2D integer valued array full of pixel-values (i.e 1 to 256).

A vertical path is simply a set of adjacent pixel elements that starts from the top row of the 2D array and continues downwards to the bottom row. The $i + 1$ st pixel is either diagonally or directly beneath the $i$ th pixel.

Each pixel also has an energy value associated with it, this is a number. This is to be some measure of why we should remove that pixel.

The vertical path of lowest energy is simply a vertical path where the sum of all the energies of each pixel in the path is the smallest.

Your task is twofold:

Define an energy function and justify why you chose it.
Implement an algorithm that finds a vertical path of lowest energy and removes it from this array.

Task 1:

def energy(img, x, y):
	# Your Energy Function Here

Task 2:

def carve_seam(img, energy_fn):
	# Your Code Here

Task 1 Example Solution

Click Here!

Function:

Our Energy Function is defined below:


def energy(img, x, y): 
	# return energy of pixel at location x, y
    delta_x = img[(x+1) % len(img)][y] - img[(x-1) % len(img)][y]
    delta_y = img[x][(y+1) % len(img)] - img[x][(y-1) % len(img)]
    return delta_x**2 + delta_y**2

Justification:

What this energy function does is that it finds the absolute value of difference between the pixels immediately next to the current pixel and squares them in both the $x$ and $y$ directions. The reason for this is that the energy function needs to measure the importance of this pixel. We can say a pixel is unimportant if it does not really affect the neighbors around it. That is, the continuity of the photo from the previous pixel to the next pixel is relatively low.

By taking the sqaured difference between neighboring pixels, we get a measure of how much change goes through the pixel.

We also don’t want to be removing from the ends of the photo as much, so we wrap the photo around itself in both the $x$ and $y$ direction. This is why we mod the length of the image.

Test Case

Note: This case uses the energy function from the above solution.

def test_case_1():
	arr = [[5, 2, 5], [2, 2, 2], [4, 2, 2]]

	seam_carve(arr, energy)

	expected = [[5, 5], [2, 2], [4, 2]]

	assert expected == arr

Task 2 Solution

Click Here!

Algorithm

For each pixel, we will compute the lowest energy vertical path that goes up to the pixel. We will then store this in a separate matrix.

We see that the lowest energy vertical path up to a given pixel is given by the lowest energy vertical path of one of the three pixels above it plus the current energy. In this case, the subproblems considered for each pixel, are the three pixels above it.

We do this for each pixel, row by row until we get to the bottom. The base case for the first row is just the pixel’s energy. For every other row, we use the above subproblem structure to compute the matrix entry.

Once this is done, we will start from the bottom of the matrix finding the minimum energy pixel. Then we will look to the three pixels above it and find the next pixel, and continue as such. As we go, we will remove the relevant indices from the original image.

Code

def seam_carve(img, energy):
	find_seam(img, energy)
	remove_seam(img)

def remove_seam(img): # returns new image with seam removed
    seam_columns = find_seam(img)
    for y in range(len(img)):
        del img[seam_columns[y]][y]
    return img

def find_seam(img, energy): # returns the smallest energy seam as an array of column numbers
	
    def find_matrix(img): # return a matrix of smallest seam values including any given pixel
        M = [[energy(img, 0, y) for y in range(len(img))]]
        for x in range(1, len(img)):
            row = []
            for y in range(len(img)):
                val = min(M[x-1][max(y-1, 0)], M[x-1][y], M[x-1][min(y+1, len(img) - 1)])
                row.append(energy(img, x, y) + val)
            M.append(row)

        return M

    seam_columns = []
    M = find_matrix(img)
    seam_end_y = min(range(len(M)), key=lambda y: M[-1][y])
    cur_y_check = seam_end_y
    seam_columns.insert(0, cur_y_check)
    for x in range(len(M) - 2, -1, -1):
        for y in range(max(cur_y_check - 1, 0), min(cur_y_check + 2, len(M))):
            if M[x+1][cur_y_check] - energy(img, x+1, cur_y_check) == M[x][y]:
                seam_columns.insert(0, y)
                cur_y_check = y
                
    return seam_columns

Runtime Analysis

Computing the matrix $O(N^2)$ time since for each pixel, we are at most taking the min of 3 values, which is a constant.

Tracing back through the matrix to get the seam takes $O(N)$ time and deleting the seam takes $O(N)$ time, so the total runtime is $O(N^2)$ .