# Seam Carving

The material presented here is inspired from:

Don’t hesitate to check these links if you have any doubt on the seam carving process.

The whole seam carving process was covered in lecture 8, please refer to the slides for more details to the different concepts introduced here.

• 实现图像裁剪
• 实现图像扩大
• 其他实验

Sean Carving 的基本思路

1. 计算图像能量图
2. 寻找最小能量线
3. 移除得到的最小能量线，让图片的宽度缩小一个像素
The autoreload extension is already loaded. To reload it, use:
%reload_ext autoreload

## Image Reducing using Seam Carving

Seam carving is an algorithm for content-aware image resizing.
To understand all the concepts in this homework, make sure to read again the slides from lecture 8: http://vision.stanford.edu/teaching/cs131_fall1718/files/08_seam_carving.pdf

### Energy function (5 points)

We will now implemented the energy_function to compute the energy of the image.
The energy at each pixel is the sum of:

• absolute value of the gradient in the $x$ direction
• absolute value of the gradient in the $y$ direction

The function should take around 0.01 to 0.1 seconds to compute.

Image (channel 0):
[[1.  2.  1.5]
[3.  1.  2. ]
[4.  0.5 3. ]]
Energy:
[[3.   1.25 1.  ]
[3.5  1.25 1.75]
[4.5  1.   3.5 ]]
Solution energy:
[[3.   1.25 1.  ]
[3.5  1.25 1.75]
[4.5  1.   3.5 ]]
Computing energy function: 0.007591 seconds.

### Compute cost (10 points)

Now implement the function compute_cost.
Starting from the energy map, we’ll go from the first row of the image to the bottom and compute the minimal cost at each pixel.

We’ll use dynamic programming to compute the cost line by line starting from the first row.

The function should take around 0.05 seconds to complete.

Energy:
[[1.  2.  1.5]
[3.  1.  2. ]
[4.  0.5 3. ]]
Cost:
[[1.  2.  1.5]
[4.  2.  3.5]
[6.  2.5 5. ]]
Solution cost:
[[1.  2.  1.5]
[4.  2.  3.5]
[6.  2.5 5. ]]
Paths:
[[ 0  0  0]
[ 0 -1  0]
[ 1  0 -1]]
Solution paths:
[[ 0  0  0]
[ 0 -1  0]
[ 1  0 -1]]
Computing vertical cost map: 0.051953 seconds.

Computing horizontal cost map: 0.049583 seconds.

## 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 (5 points)

Implement function backtrack_seam.

Seam Energy: 2.5
Seam: [0 1 1]
Backtracking optimal seam: 0.000705 seconds.
Seam Energy: 2.443948431372548

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 (25 points)

We can now use the function backtrack and remove_seam iteratively to reduce the size of the image through seam carving.

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.

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.]]
Reducing width from 640 to 400: 9.738185 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.

Reducing height from 434 to 300: 7.296496 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.

## Image Enlarging

### Enlarge naive (10 points)

We now want to tackle the reverse problem of enlarging an image.
One naive way to approach the problem would be to duplicate the optimal seam iteratively until we reach the desired size.

Original image (channel 0):
[[0. 1. 2.]
[3. 4. 5.]
[6. 7. 8.]]
Enlarged image (channel 0): we see that seam [0, 4, 7] is duplicated
[[0. 0. 1. 2.]
[3. 4. 4. 5.]
[6. 7. 7. 8.]]
Enlarging(naive) height from 640 to 800: 8.824498 seconds.

The issue with enlarge_naive is that the same seam will be selected again and again, so this low energy seam will be the only to be duplicated.

Another way to get k different seams is to apply the process we used in function reduce, and keeping track of the seams we delete progressively.
The function find_seams(image, k) will find the top k seams for removal iteratively.

The inner workings of the function are a bit tricky so we’ve implemented it for you, but you should go into the code and understand how it works.
This should also help you for the implementation of enlarge.

Finding 160 seams: 7.296915 seconds.

### Enlarge (25 points)

We can see that all the seams found are different, and they avoid the castle and the person.

One issue we can mention is that we cannot enlarge more than we can reduce. Because of our process, the maximum enlargement is the width of the image W because we first need to find W different seams in the image.

One effect we can see on this image is that the blue sky at the right of the castle can only be enlarged x2. The concentration of seams in this area is very strong.
We can also note that the seams at the right of the castle have a blue color, which means they have low value and were removed in priority in the seam selection process.

Original image (channel 0):
[[0. 1. 3.]
[0. 1. 3.]
[0. 1. 3.]]
Enlarged naive image (channel 0): first seam is duplicated twice.
[[0. 0. 0. 1. 3.]
[0. 0. 0. 1. 3.]
[0. 0. 0. 1. 3.]]
Enlarged image (channel 0): first and second seam are each duplicated once.
[[0. 0. 1. 1. 3.]
[0. 0. 1. 1. 3.]
[0. 0. 1. 1. 3.]]
Enlarging width from 640 to 800: 10.235673 seconds.

Finding 160 seams: 9.089754 seconds.

Enlarging height from 434 to 600: 14.027314 seconds.

As you can see in the example above, the sky above the castle has doubled in size, the grass below has doubled in size but we still can’t reach a height of 600.
The algorithm then needs to enlarge the castle itself, while trying to avoid enlarging the windows for instance.

## Other experiments on the image

Feel free to experiment more on this image, try different sizes to enlarge or reduce, or check what seams are chosen…

Reducing by a 2x factor often leads to weird patterns.
Enlarging by more than 2x is impossible since we only duplicate seams. One solution is to enlarge in mutliple steps (enlarge x1.4, enlarge again x1.4…)

Reducing width from 640 to 200: 16.882833 seconds.

## Faster reduce (extra credit 0.5%)

Implement a faster version of reduce called reduce_fast in the file seam_carving.py.

We will have a leaderboard on gradescope with the performance of students.

The autograder tests will check that the outputs match, and run the reduce_fast function on a set of images with varying shapes (say between 200 and 800).

Normal reduce width from 640 to 400: 9.237779 seconds.
Faster reduce width from 640 to 400: 8.685472 seconds.

## Reducing and enlarging on another image

Also check these outputs with another image.

## Forward Energy (20 points)

Forward energy is a solution to some artifacts that appear when images have curves for instance.

Implement the function compute_forward_cost. This function will replace the compute_cost we have been using until now.

$$M(i,j) = E(i,j) + min \left\{ \begin{array}{lr} M(i-1,j-1) \\ M(i-1,j) \\ M(i-1,j+1) \end{array} \right.$$

Forward能量图的定义为

$$M(i,j) = E(i,j) + min \left\{ \begin{array}{lr} M(i-1,j-1) + C_L(i,j), & C_L(i,j) = |I(i,j+1) - I(i,j-1)| + |I(i-1,j) - I(i,j-1)|\\ M(i-1,j) + C_V(i,j), & C_V(i,j) = |I(i,j+1) - I(i,j-1)| \\ M(i-1,j+1)+C_R(i,j), , & C_R(i,j) = |I(i,j+1) - I(i,j-1)| + |I(i-1,j) - I(i,j+1)|\ \end{array} \right.$$

Image:
[[1.  1.  2. ]
[0.5 0.  0. ]
[1.  0.5 2. ]]
Energy:
[[0.5 1.5 3. ]
[0.5 0.5 0. ]
[1.  1.  3.5]]
Cost:
[[0.5 2.5 3. ]
[1.  2.  3. ]
[2.  4.  6. ]]
Solution cost:
[[0.5 2.5 3. ]
[1.  2.  3. ]
[2.  4.  6. ]]
Paths:
[[ 0  0  0]
[ 0 -1  0]
[ 0 -1 -1]]
Solution paths:
[[ 0  0  0]
[ 0 -1  0]
[ 0 -1 -1]]

We observe that the forward energy insists more on the curved edges of the image.

Old Solution: 5.034606 seconds.

The issue with our standard reduce function is that it removes vertical seams without any concern for the energy introduced in the image.

In the case of the dinosaure above, the continuity of the shape is broken. The head is totally wrong for instance, and the back of the dinosaure lacks continuity.

Forward energy will solve this issue by explicitely putting high energy on a seam that breaks this continuity and introduces energy.

Forward Energy Solution: 8.092415 seconds.

## Object removal (extra credit 0.5%)

Object removal uses a binary mask of the object to be removed.

Using the reduce and enlarge functions you wrote before, complete the function remove_object to output an image of the same shape but without the object to remove.

• 如何进行标记，从而每次删除能量线的时候，都能删到并且尽可能多的删到带有标记的能量线？同时坐标下标不会混乱。
• 如何在删除目标之后保持和原图同样的尺寸

/home/ubuntu/anaconda3/lib/python3.6/site-packages/skimage/util/dtype.py:118: UserWarning: Possible sign loss when converting negative image of type float64 to positive image of type bool.
.format(dtypeobj_in, dtypeobj_out))