Seam Carving for Content-Aware Image Resizing ACM Transactions on Graphics, Volume 26, Number 3, SIGGRAPH 2007 姓名：王俊富 指導老師：萬書言 副教授

Seam Carving Effective resizing of images should not only use geometric constraints, but consider the image content as well. A seam is a connected path of low energy pixels crossing the image from top to bottom, or from left to right. Seam-carving is a simple image operator that can change the size of an image.

Image reduction & Image enlarging For image reduction, seam selection ensures that while preserving the image structure, we remove more of the low energy pixels and fewer of the high energy ones. For image enlarging, the order of seam insertion ensures a balance between the original image content and the artificially inserted pixels.

Image reduction Results of 5 different strategies for reducing the width of an image. (b)有最高能量的子視窗 (c)移除每行有最低能量 (d)Seam removal (e)每行移除相同數的低能量 (f)由低能量刪除，慢慢往上

The Operator Energy function: (gradient) let I be an n×m image and define a vertical seam to be: horizontal seam is: Optimal seam s* that minimizes this seam cost :

Energy Preservation Measure Randomly removing pixels should keep the average unchanged, but content-aware resizing should raise the average as it removes low energy pixels and keeps the high energy ones.

Image Energy Function(1/2) Taking the maximum of the HoG at the denominator attracts the seams to edges in the image. Use an 8-bin histogram computed over a 11×11 window around the pixel.

Image Energy Function(2/2) As expected, no single energy function performs well across all images but in general they all accommodate a similar range for resizing. We found either e1 or eHoG to work quite well.

Aspect Ratio Change(1/2) 影像縮減： Left: Seam removals Center: Scaling Right: Cropping

Aspect Ratio Change(2/2) 影像拉寬： In both examples the original image is widened by seam insertion.

Image Enlarging(1/2) 影像縮減是一直將最低能量的seam刪去 影像拉寬是一直增加最低能量的seam? NO 先找出要拉寬的長度，找出對應長度的k條seam 接下來有幾種做法： 1.直接複製seam 2.由seam的左右兩邊鄰居取平均 3.取seam的能量值與其中一邊鄰居(左或右)的能量值 做平均(即時運算)

Image Enlarging(2/2) (a)Original (b)最低的Seam 延伸(c)Inserting the seams in order of removal (d)50% enlargement (e)一次放大100% 等同標準scaling(f)兩次放大50% (g)前圖的enlargement

Content Amplification 內容物放大能透過結合seam caving與scaling完成。 先以傳統Scaling 放大影像，再用Seam Carving 縮減為 原圖大小。

Object Removal(1/2) The system can automatically calculate the smaller of the vertical or horizontal diameters (in pixels) of the target removal region and perform vertical or horizontal removals accordingly . 用簡單的UI讓使用者 描繪出要移除的物件

Object Removal(2/2) 找得到不見的鞋嗎?(原圖左上) 越複雜的圖越難看出差異

Multi-size Image(1/3) 使用者通常無法清楚知道自己要調整影像大小到多少 比較適合。 調整影像大小從400×500 到100×100 約需要 2.2 秒。 因此，若要能即時處理出數以百條的seam 是件困難 的工作。 若先經由pre-processing 步驟，就可使影像即時處理。 透過index map，找出被刪除的次序。

Multi-size Image(2/3) Index map： An image with its vertical and horizontal seam index maps V and H, colored by their index from blue (first seams) to red (last seams).

Multi-size Image(3/3) 若要縮減影像，從index map依序刪除seam

Seam Carving in the gradient domain combine seam carving with Poisson reconstruction ([Perez et al. 2003]). 左上：Original 右上：Seam carving 右下：結合Poisson 左下：放大比較

Retargeting with Optimal Seams-Order(1/4) 影像I 從n×m的大小 retarget為n’×m’，且m’<m and n’<n ，seam carving的次序該如何決定? Remove vertical seams first? Horizontal seams first? Or alternate between the two? Define the search for the optimal order as an optimization of the following objective function: where k = r+c, r = (m−m’), c = (n−n’) and ai is used as a parameter that determine if at step i we remove a horizontal or vertical seam: ai {0,1}

Retargeting with Optimal Seams-Order(2/4) k = r+c, r = (m−m’), c = (n−n’) {0,1} ：vertical ：horizontal Find the optimal order using a transport map T Entry T(r,c) holds the minimal cost needed to obtain an image of size n−r×m−c.

Retargeting with Optimal Seams-Order(3/4) Starting at T(0,0) = 0 we fill each entry (r,c) choosing the best of two options - either removing a horizontal seam from an image of size n−r×m−c+1 or removing a vertical seam from an image of size n−r+1×m−c:

Retargeting with Optimal Seams-Order(4/4) Top is the original image and it’s transport map T. 右上： optimal path (white path on T) 左上： Alternating between vertical and horizontal 左下： vertical seams first 右下： horizontal seams first

Limitations(1/3) Combined with a face detector we get much better results.

Limitations(2/3) 上排左至右Original、Cropped、Scaled 下排左至右simple bottom up、face protect、face and flower

Limitations(3/3) 若影像太過單調，且不包含不太重要的部分，則不太 適用此方法，用傳統的scaling 反而會比較好。

實作方式(1/2) 先計算原始影像的gradient值，可以採用Sobel opertaor 算完之後計算energy map image，(i,j)值為gradient 的 current 值加上之前三個比較的最小值 i.e. min((i-1,j-1),(i-1,j),(i-1,j+1)) 最左及最右只有兩個 最上設為初始的gradient (i-1,j-1) (i-1,j) (i-1,j+1) (i,j-1) (i,j) (i,j+1) (i+1,j-1) (i+1,j) (i+1,j+1)

實作方式(2/2) 算出energy map後，找出optimal seam 由最後一行找出最小值，依序往上找出三個鄰居的最 小值，完成後即為vertical的optimal seam，horizontal seam同理可推 移除optimal seam即可達到影像縮減的效果 Seam insertion可插入seam的兩個鄰居平均值，若要即 時運算可用seam與其中一邊鄰居的能量平均值 因此限制每次最多增大ㄧ倍-1的pixel值

影片Demo

Reference Seam carving for content aware image resizing: MATLAB http://danluong.com/2007/12/21/seam-carving-matlab- implementation-tutorial/ liquid-resize http://www.thegedanken.com/retarget/ CAIR code http://code.google.com/p/seam-carving-gui/ Rsizr線上 http://cn.rsizr.com/ 簡單小程式 http://swieskowski.net/carve/

The End Thanks for your listening!