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

前回の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])
Seam Energy: 2.5
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()
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.
各縮小の計算には約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]]))
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.
幅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()
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.
ここでの問題は、城が画像の全高であることから、ほとんどの水平シームが城を通り抜けていることだ。面白いことに、草のほとんどが残っていることに気付く。これは、草が、隣接画素間の差がわずか(一種の多ノイズパターン)な事で高エネルギーになっているためだ。除去されるシームは、画像左側の空を通り抜け、城の下を通っていくらかの草を除去してから低エネルギーの青空へ再び上がって行く。