Improved Seam Carving using Forward Energy

Alexander Xu '19 & Mario Liu '19

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

Introduction

For more details on seam carving, please read

1) the readme

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"""
    return util.img_as_float(io.imread(filename))
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>

Much faster! About 70x.

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>