前回のStanford University/CS131/宿題4-1 シームカービングの続きをやる。今回の宿題は、Finding optimal seams(最適シーム探索)、バックトラックシーム、reduceをやる。
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.
関数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
### YOUR CODE HERE
for i in range(H,1,-1):
seam[i-2] = seam[i-1]+paths[i-1,seam[i-1]]
### END YOUR CODE
# 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])
img = io.imread('imgs/broadway_tower.jpg')
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()
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による画像サイズ縮小に、関数backtrackとremove_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.
各縮小の計算には約10秒かかるが、これは実装の出来による。あまりにも時間が掛かり過ぎるようなら、compute_costのコードを1ループだけ使うようにベクトル化を試みるといい。
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
### YOUR CODE HERE
#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)
### END YOUR CODE
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"
### YOUR CODE HERE
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)
### END YOUR CODE
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]]))
# 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()
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.
幅640ドット〜400ドットへのリサイズが、標準的なリサイズだったなら全てを圧縮しただろう画像の重要な部分のほぼ全て(人と城)を保持することに気付く。
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()
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.
ここでの問題は、城が画像の全高であることから、ほとんどの水平シームが城を通り抜けていることだ。面白いことに、草のほとんどが残っていることに気付く。これは、草が、隣接画素間の差がわずか(一種の多ノイズパターン)な事で高エネルギーになっているためだ。除去されるシームは、画像左側の空を通り抜け、城の下を通っていくらかの草を除去してから低エネルギーの青空へ再び上がって行く。