# スタンフォード/CS131/宿題4-2 最適シーム探索

スポンサーリンク

## Finding optimal seams¶

Using the cost maps we found above, we can determine the seam with the lowest energy in the image.
We can then remove this optimal seam, and repeat the process until we obtain a desired width.

### Backtrack seam¶

Implement function backtrack_seam.

import numpy as np
import matplotlib.pyplot as plt
from matplotlib import rc
from skimage import color,io, util
from time import time
from IPython.display import HTML
from __future__ import print_function
from seam_carving import compute_cost,energy_function

%matplotlib inline
plt.rcParams['figure.figsize'] = (15.0, 12.0) # set default size of plots
plt.rcParams["font.size"] = "17"
plt.rcParams['image.interpolation'] = 'nearest'
plt.rcParams['image.cmap'] = 'gray'
def backtrack_seam(paths, end):
"""Backtracks the paths map to find the seam ending at (H-1, end)
To do that, we start at the bottom of the image on position (H-1, end), and we
go up row by row by following the direction indicated by paths:
- left (value -1)
- middle (value 0)
- right (value 1)
Args:
paths: numpy array of shape (H, W) containing values -1, 0 or 1
end: the seam ends at pixel (H, end)
Returns:
seam: np.array of indices of shape (H,). The path pixels are the (i, seam[i])
"""
H, W = paths.shape
seam = np.zeros(H, dtype=np.int)
# Initialization
seam[H-1] = end
for i in range(H,1,-1):
seam[i-2] = seam[i-1]+paths[i-1,seam[i-1]]
# Check that seam only contains values in [0, W-1]
assert np.all(np.all([seam >= 0, seam < W], axis=0)), "seam contains values out of bounds"
return seam
# Let's first test with a small example
test_energy = np.array([[1.0, 2.0, 1.5],
[3.0, 1.0, 2.0],
[4.0, 0.5, 3.0]])

vcost, vpaths = compute_cost(_, test_energy, axis=1)

cost = np.array([[1.0, 2.0, 1.5],
[4.0, 2.0, 3.5],
[6.0, 2.5, 5.0]])

paths = np.array([[ 0,  0,  0],
[ 0, -1,  0],
[ 1,  0, -1]])

# Vertical Backtracking
end = np.argmin(cost[-1])
seam_energy = cost[-1, end]
seam = backtrack_seam(vpaths, end)

print('Seam Energy:', seam_energy)
print('Seam:', seam)

assert seam_energy == 2.5
assert np.allclose(seam, [0, 1, 1])
Seam Energy: 2.5
Seam: [0 1 1]
img = util.img_as_float(img)
energy = energy_function(img)
vcost, vpaths = compute_cost(img, energy)

# Vertical Backtracking
start = time()
end = np.argmin(vcost[-1])
seam_energy = vcost[-1, end]
seam = backtrack_seam(vpaths, end)
end = time()
print("Backtracking optimal seam: %f seconds." % (end - start))
print('Seam Energy:', seam_energy)

# Visualize seam
vseam = np.copy(img)
for row in range(vseam.shape[0]):
vseam[row, seam[row], :] = np.array([1.0, 0, 0])

plt.title('Vertical Seam')
plt.axis('off')
plt.imshow(vseam)
plt.show()
Backtracking optimal seam: 0.000337 seconds.
Seam Energy: 2.4439484313725472

In the image above, the optimal vertical seam (minimal cost) goes through the portion of sky without any cloud, which yields the lowest energy.

### Reduce¶

We can now use the function backtrack and remove_seam iteratively to reduce the size of the image through seam carving.
seam carvingによる画像サイズ縮小に、関数backtrackremove_seamを繰り返し使うことができる

Each reduce can take around 10 seconds to compute, depending on your implementation.
If it’s too long, try to vectorize your code in compute_cost to only use one loop.

def remove_seam(image, seam):
"""Remove a seam from the image.
This function will be helpful for functions reduce and reduce_forward.
Args:
image: numpy array of shape (H, W, C) or shape (H, W)
seam: numpy array of shape (H,) containing indices of the seam to remove
Returns:
out: numpy array of shape (H, W-1, C) or shape (H, W-1)
"""
# Add extra dimension if 2D input
if len(image.shape) == 2:
image = np.expand_dims(image, axis=2)
out = None
H, W, C = image.shape
#out = image[np.arange(W)!=seam[:,None]].reshape(H,W-1,C)
out = np.zeros((H,W-1,C))
for i in range(H):
out[i] = np.delete(image[i], seam[i], axis=0)
out = np.squeeze(out)  # remove last dimension if C == 1
return out
def reduce(image, size, axis=1, efunc=energy_function, cfunc=compute_cost):
"""Reduces the size of the image using the seam carving process.
At each step, we remove the lowest energy seam from the image. We repeat the process
until we obtain an output of desired size.
Use functions:
- efunc
- cfunc
- backtrack_seam
- remove_seam
Args:
image: numpy array of shape (H, W, 3)
size: size to reduce height or width to (depending on axis)
axis: reduce in width (axis=1) or height (axis=0)
efunc: energy function to use
cfunc: cost function to use
Returns:
out: numpy array of shape (size, W, 3) if axis=0, or (H, size, 3) if axis=1
"""
out = np.copy(image)
if axis == 0:
out = np.transpose(out, (1, 0, 2))
H = out.shape[0]
W = out.shape[1]
assert W > size, "Size must be smaller than %d" % W
assert size > 0, "Size must be greater than zero"
for i in range(W-size):
energy = efunc(out)
cost,path = cfunc(out,energy)
seam = backtrack_seam(path,np.argmin(cost[-1]))
out = remove_seam(out,seam)
assert out.shape[1] == size, "Output doesn't have the right shape"
if axis == 0:
out = np.transpose(out, (1, 0, 2))
return out
# Let's first test with a small example
test_img = np.arange(9, dtype=np.float64).reshape((3, 3))
test_img = np.stack([test_img, test_img, test_img], axis=2)
assert test_img.shape == (3, 3, 3)

cost = np.array([[1.0, 2.0, 1.5],
[4.0, 2.0, 3.5],
[6.0, 2.5, 5.0]])

paths = np.array([[ 0,  0,  0],
[ 0, -1,  0],
[ 1,  0, -1]])

# Reduce image width
W_new = 2

# We force the cost and paths to our values
out = reduce(test_img, W_new, cfunc=lambda x, y: (cost, paths))

print("Original image (channel 0):")
print(test_img[:, :, 0])
print("Reduced image (channel 0): we see that seam [0, 4, 7] is removed")
print(out[:, :, 0])

assert np.allclose(out[:, :, 0], np.array([[1, 2], [3, 5], [6, 8]]))
Original image (channel 0):
[[0. 1. 2.]
[3. 4. 5.]
[6. 7. 8.]]
Reduced image (channel 0): we see that seam [0, 4, 7] is removed
[[1. 2.]
[3. 5.]
[6. 8.]]
# Reduce image width
H, W, _ = img.shape
W_new = 400

start = time()
out = reduce(img, W_new)
end = time()

print("Reducing width from %d to %d: %f seconds." % (W, W_new, end - start))

plt.subplot(2, 1, 1)
plt.title('Original')
plt.imshow(img)

plt.subplot(2, 1, 2)
plt.title('Resized')
plt.imshow(out)

plt.show()
Reducing width from 640 to 400: 11.825951 seconds.

We observe that resizing from width 640 to width 400 conserves almost all the important part of the image (the person and the castle), where a standard resizing would have compressed everything.

All the vertical seams removed avoid the person and the castle.

# Reduce image height
H, W, _ = img.shape
H_new = 300

start = time()
out = reduce(img, H_new, axis=0)
end = time()

print("Reducing height from %d to %d: %f seconds." % (H, H_new, end - start))

plt.subplot(1, 2, 1)
plt.title('Original')
plt.imshow(img)

plt.subplot(1, 2, 2)
plt.title('Resized')
plt.imshow(out)

plt.show()
Reducing height from 434 to 300: 9.106174 seconds.

For reducing the height, we observe that the result does not look as nice.

The issue here is that the castle is on all the height of the image, so most horizontal seams will go through it.
Interestingly, we observe that most of the grass is not removed. This is because the grass has small variation between neighboring pixels (in a kind of noisy pattern) that make it high energy.
The seams removed go through the sky on the left, go under the castle to remove some grass and then back up in the low energy blue sky.
ここでの問題は、城が画像の全高であることから、ほとんどの水平シームが城を通り抜けていることだ。面白いことに、草のほとんどが残っていることに気付く。これは、草が、隣接画素間の差がわずか(一種の多ノイズパターン)な事で高エネルギーになっているためだ。除去されるシームは、画像左側の空を通り抜け、城の下を通っていくらかの草を除去してから低エネルギーの青空へ再び上がって行く。

スポンサーリンク
スポンサーリンク

フォローする