Alexander Xu '19 & Mario Liu '19
from IPython.lib.display import YouTubeVideo
YouTubeVideo('6NcIJXTlugc')
and 3) the improved seam carving demo video from 2008:
YouTubeVideo('AJtE8afwJEg')
I begin by importing everything I need and defining a few helper functions:
%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
def imread(filename):
"""For convenience since pixels are natively 8 bit ints"""
return util.img_as_float(io.imread(filename))
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:
bench3 = imread('bench3.png')
print(bench3.dtype)
print(bench3.shape)
plt.imshow(bench3)
float64 (342, 512, 3)
<matplotlib.image.AxesImage at 0x260bf1574e0>
First I re-implemented the backwards energy function from my class assignment and ran it:
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
%time plt.imshow(slow_dual_gradient(bench3))
Wall time: 1.92 s
<matplotlib.image.AxesImage at 0x260bef84588>
We test it by removing 200 seams.
%time img, eimg = seam_carve(bench3, slow_dual_gradient, 200)
plt.imshow(img)
Wall time: 5min 15s
<matplotlib.image.AxesImage at 0x260befe6a58>
Looks just like the paper!
Then we take advantage of scipy to represent this same function using 2 1D convolutions for a speedup.
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)
%time img, eimg = seam_carve(bench3, dual_gradient, 200)
plt.imshow(img)
Wall time: 4.6 s
<matplotlib.image.AxesImage at 0x260bf044390>
def backward_energy(img):
return filters.sobel(color.rgb2gray(img))
%time plt.imshow(backward_energy(bench3))
Wall time: 59.8 ms
<matplotlib.image.AxesImage at 0x260bf099a58>
%time img, eimg = seam_carve(bench3, backward_energy, 200)
plt.imshow(img)
Wall time: 2.67 s
<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.
Then we implemented and ran the forward energy algorithm from the paper, using rgb2gray to calculate pixel intensities:
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
%time plt.imshow(slow_forward_energy(bench3))
Wall time: 1.8 s
<matplotlib.image.AxesImage at 0x260c022c358>
%time img, eimg = seam_carve(bench3, slow_forward_energy, 200)
plt.imshow(img)
Wall time: 4min 40s
<matplotlib.image.AxesImage at 0x260c16b5dd8>
def forward_energy(img, flag=False):
height = img.shape[0]
width = img.shape[1]
I = color.rgb2gray(img)
energy = np.zeros((height, width))
m = np.zeros((height, width))
U = np.roll(I, 1, axis=0)
L = np.roll(I, 1, axis=1)
R = np.roll(I, -1, axis=1)
cU = np.abs(R - L)
cL = np.abs(U - L) + cU
cR = np.abs(U - R) + cU
for i in range(1, height):
mU = m[i-1]
mL = np.roll(mU, 1)
mR = np.roll(mU, -1)
mULR = np.array([mU, mL, mR])
cULR = np.array([cU[i], cL[i], cR[i]])
mULR += cULR
argmins = np.argmin(mULR, axis=0)
m[i] = np.choose(argmins, mULR)
energy[i] = np.choose(argmins, cULR)
return energy
%time img, eimg = seam_carve(bench3, forward_energy, 200)
plt.imshow(img)
Wall time: 7.87 s
<matplotlib.image.AxesImage at 0x260c19a8b00>
A further optimization would be changing the skimage.transform.seam_carve function to accept the accumulated cost matrix (the m matrix in the function) since forward energy calculates it directly. Right now, I calculate the energy matrix backward from the m matrix.
Now I will compare the outputs between the backward and forward energy algorithms.
I write a helper plotting function, but I have no idea if this is the best way to do it...
def compare_energy(img, n, filename):
"""
A helper function to compare backward and forward energy.
:param img: image to carve
:param int n: number of seams to carve
"""
w = img.shape[1]
gs = gridspec.GridSpec(3, 2,
width_ratios=[w, w - n],
height_ratios=[1, 1, 1]
)
plt.figure(figsize=(14, 14))
plt.subplot(gs[0])
plt.imshow(img)
plt.title('Original Image')
plt.subplot(gs[2])
plt.imshow(backward_energy(img))
plt.title('Backward Energy')
plt.subplot(gs[3])
backward_img, _ = seam_carve(img, backward_energy, n)
plt.imshow(backward_img)
plt.title('Backward Carving')
plt.subplot(gs[4])
plt.imshow(forward_energy(img))
plt.title('Forward Energy')
plt.subplot(gs[5])
forward_img, _ = seam_carve(img, forward_energy, n)
plt.imshow(forward_img)
plt.title('Forward Carving')
plt.show()
plt.imsave('samples/' + filename + '_backward.jpg', backward_img)
plt.imsave('samples/' + filename + '_forward.jpg', forward_img)
# Images from paper and number of seams to remove
paper = [
('bench3.png', 200),
('pliers.jpg', 100),
('bench2.png', 400),
('arch.png', 300),
('car1.png', 150),
('ratatouille.png', 250),
('rain.png', 150)
]
paper = [(imread('samples/' + filename), n, filename.split('.')[0]) for filename, n in paper]
# Images we chose
ours = [
('blair.jpg', 200),
('teapot.jpg', 150),
('p_arch.jpg', 350),
('house.jpg', 200)
]
ours = [(imread('samples/' + filename), n, filename.split('.')[0]) for filename, n in ours]
First, we carve a few images from the paper itself.
for img, n, name in paper:
compare_energy(img, n, name)
Then we carve a few of our own images:
for img, n, name in ours:
compare_energy(img, n, name)
I need to implement it horizontally too. And then I'll submit it to scikit-image as the default energy function:
https://github.com/scikit-image/scikit-image/issues/3082
https://github.com/scikit-image/scikit-image/issues/2808
I'll also look into the potential optimizations mentioned in part 4...
Yun Teng '19 and Ji-Sung Kim '19 for numpy help