# Improved Seam Carving using Forward Energy¶

Alexander Xu '19 & Mario Liu '19

In [1]:
from IPython.lib.display import YouTubeVideo


## Introduction¶

2) the original seam carving demo video from 2007:

In [2]:
YouTubeVideo('6NcIJXTlugc')

Out[2]:

and 3) the improved seam carving demo video from 2008:

In [3]:
YouTubeVideo('AJtE8afwJEg')

Out[3]:

I begin by importing everything I need and defining a few helper functions:

In [4]:
%matplotlib inline
import matplotlib.pyplot as plt

from skimage import io, transform, util
import numpy as np
from skimage import filters, color

from scipy import ndimage as ndi
from matplotlib import gridspec

In [5]:
def imread(filename):
"""For convenience since pixels are natively 8 bit ints"""

In [6]:
def seam_carve(img, f, n):
"""
Helper function to recalculate the energy map after each seam removal

:param img: image to be carved
:param f: energy map function
:param n: number of seams to remove
"""
for i in range(n):
eimg = f(img)
img = transform.seam_carve(img, eimg, 'vertical', 1)
return img, eimg


I will be testing on the bench photo from the paper:

In [7]:
bench3 = imread('bench3.png')
print(bench3.dtype)
print(bench3.shape)
plt.imshow(bench3)

float64
(342, 512, 3)

Out[7]:
<matplotlib.image.AxesImage at 0x260bf1574e0>

### Part 1: Dual Gradient Energy (Backward Energy)¶

First I re-implemented the backwards energy function from my class assignment and ran it:

In [8]:
def slow_dual_gradient(img):
height = img.shape[0]
width = img.shape[1]
energy = np.empty((height, width))
for i in range(height):
for j in range(width):
L = img[i, (j-1) % width]
R = img[i, (j+1) % width]
U = img[(i-1) % height, j]
D = img[(i+1) % height, j]

dx_sq = np.sum((R - L)**2)
dy_sq = np.sum((D - U)**2)
energy[i,j] = np.sqrt(dx_sq + dy_sq)
return energy

In [9]:
%time plt.imshow(slow_dual_gradient(bench3))

Wall time: 1.92 s

Out[9]:
<matplotlib.image.AxesImage at 0x260bef84588>

We test it by removing 200 seams.

In [10]:
%time img, eimg = seam_carve(bench3, slow_dual_gradient, 200)
plt.imshow(img)

Wall time: 5min 15s

Out[10]:
<matplotlib.image.AxesImage at 0x260befe6a58>

Looks just like the paper!

### Part 2: Vectorized Dual Gradient Energy¶

Then we take advantage of scipy to represent this same function using 2 1D convolutions for a speedup.

In [11]:
def dual_gradient(img):
rgbx = ndi.convolve1d(img, np.array([1, 0, -1]), axis=1, mode='wrap')
rgby = ndi.convolve1d(img, np.array([1, 0, -1]), axis=0, mode='wrap')

rgbx = np.sum(rgbx**2, axis=2)
rgby = np.sum(rgby**2, axis=2)

return np.sqrt(rgbx + rgby)

In [12]:
%time img, eimg = seam_carve(bench3, dual_gradient, 200)
plt.imshow(img)

Wall time: 4.6 s

Out[12]:
<matplotlib.image.AxesImage at 0x260bf044390>

We quickly compare it to the built-in sobel edge detection algorithm from the seam-carving example.

In [13]:
def backward_energy(img):
return filters.sobel(color.rgb2gray(img))

%time plt.imshow(backward_energy(bench3))

Wall time: 59.8 ms

Out[13]:
<matplotlib.image.AxesImage at 0x260bf099a58>
In [14]:
%time img, eimg = seam_carve(bench3, backward_energy, 200)
plt.imshow(img)

Wall time: 2.67 s

Out[14]:
<matplotlib.image.AxesImage at 0x260bf1366d8>

The built in filter is probably faster since it uses rgb2gray instead of the L2 color difference to calculate pixel intensities.

### Part 3: Forward Energy¶

Then we implemented and ran the forward energy algorithm from the paper, using rgb2gray to calculate pixel intensities:

In [15]:
def slow_forward_energy(img):
height = img.shape[0]
width = img.shape[1]

I = color.rgb2gray(img)
energy = np.zeros((height, width))
m = np.zeros((height, width))

for i in range(1, height):
for j in range(width):
up = (i-1) % height
down = (i+1) % height
left = (j-1) % width
right = (j+1) % width

mU = m[up,j]
mL = m[up,left]
mR = m[up,right]

cU = np.abs(I[i,right] - I[i,left])
cL = np.abs(I[up,j] - I[i,left]) + cU
cR = np.abs(I[up,j] - I[i,right]) + cU

cULR = np.array([cU, cL, cR])
mULR = np.array([mU, mL, mR]) + cULR

argmin = np.argmin(mULR)
m[i,j] = mULR[argmin]
energy[i,j] = cULR[argmin]

return energy

In [16]:
%time plt.imshow(slow_forward_energy(bench3))

Wall time: 1.8 s

Out[16]:
<matplotlib.image.AxesImage at 0x260c022c358>
In [17]:
%time img, eimg = seam_carve(bench3, slow_forward_energy, 200)
plt.imshow(img)

Wall time: 4min 40s

Out[17]:
<matplotlib.image.AxesImage at 0x260c16b5dd8>