接縫裁剪

接縫裁剪（Seam carving），是一個可以針對图像內容做正確縮放的算法（由Shai Avidan和Ariel Shamir所發表）。概念上，算法會找出一系列的接缝（seam）（接缝是在图像中最不重要的一連串像素），接著利用接缝對图像做縮放。如果是要縮小图像，則移除這些接缝，若是放大，則在這些接缝的位置上，插入一些像素。接缝裁剪可以人工定义一些不会被修改的像素区域，也可以从图像中移除整个物体。

這是一張需要變窄的照片

使用图像伸缩的結果，城堡的形狀變了

使用图像裁剪的結果，城堡的一部份被切掉了

接缝裁剪的結果

接缝裁剪算法的主要目的是图像重定向（image retargeting），將图像无失真的显示在各種大小的螢幕或位置上，比如說，手機、投影幕等等。

接缝（Seams）

接缝有兩種形式，水平或垂直的。接缝本身是一条由像素构成的路径，水平的接缝连接图像的左侧和右侧，路径中的像素个数和图像的列数一致。垂直接缝则类似，连接图像的顶部和底部，像素个数和图像的行数一致。接缝上每个像素都有存在一个称为重要性或者能量的指标，这个指标的值是根据像素的邻接像素计算得到的。一个像素和周边像素的相似度越高，则其重要性或者说能量就越低。

算法

1. 首先，我們拿到一張需要縮小的照片（這裡以縮小舉例）

 

2. 接著我們計算照片中每一個像素的強度（energy），這一步可以由很多演算法完成，這裡以gradient magnitude為例。

 

3. 有了每一個pixel的強度後，我們可以利用一些演算法，像是dynamic programming等等，找到圖中數條強度較低的seams。

Seams 在gradient magnitude圖中的樣子:

 

Seams 在原始圖片中的樣子:

 

（從seams在原始圖中的樣子，我們可以看到所謂強度低的seam，基本上就可以表達照片中相對不重要的部分）

4. 接著我們把這些seams拿掉，就可以拿到一張縮小後的照片。

 

5. 若是我們需要放大圖片，則我們可以在這些我們找到的seam的旁邊，增加pixel，而pixel的value可以簡單的取附近的pixel的平均。

計算 seams

在這個演算法中，我們每次要找出一條照片中能量最小的seam，這裡的能量可以想成是頻率低，或者是照片中較為不重要的pixel。而找出seam的方法有很多種，我們可以利用dynamic programming或者其他演算法完成。

動態規劃

以下為matlab的ref code，示範的是找出水平的seam後，放大圖片。

function srcImg = seam_carving(srcImg, targetH)  % srcImg為原始的圖片, targetH為想要放大到的高  % h, w為原始圖片的長和寬 [ h, w, ~ ] = size( srcImg ); while h < targetH  % 將原始圖片轉成灰階後，算出gradient magnitude grayImg = rgb2gray( srcImg ); [ gMag, gDir ] = imgradient( grayImg );  % dp儲存從左到右在每一個pixel累積的最小可能強度  % from則是紀錄若要走最小強度的path，每一個pixel的上一個是從哪裡來 dp = zeros( h, w ); from = zeros( h, w ); for i = 1 : h dp( i, 1 ) = gMag( i, 1 ); end  % dynamic programming: 找出最小強度的path for i = 2 : w for j = 1 : h minNeighbor = dp( j, i - 1 ); from( j, i ) = j; if j > 1 && dp( j - 1, i - 1 ) < minNeighbor minNeighbor = dp( j - 1, i - 1 ); from( j, i ) = j - 1; end if j < h && dp( j + 1, i - 1 ) < minNeighbor minNeighbor = dp( j + 1, i - 1 ); from( j, i ) = j + 1; end dp( j, i ) = gMag( j, i ) + minNeighbor; end end  % 在最右側的column找出最小強度的path的終點 mn = 10 ^ 18; idx = -1; for i = 1 : h if dp( i, w ) < mn mn = dp( i, w ); idx = i; end end  % backtrace，找出整條path path = 0; for i = w : -1 : 1 if path == 0 path = [ idx ]; else path = [ idx path ]; end idx = from( idx, i ); end  % 增加一條row addRow = srcImg( 1, :, : ); srcImg = [ addRow; srcImg ];  % assign新的row正確的值 for i = 1 : w for j = 1 : path( 1, i ) srcImg( j, i, : ) = srcImg( j + 1, i, : ); end if path( 1, i ) + 2 > h srcImg( path( 1, i ) + 1, i, : ) = srcImg( path( 1, i ), i, : ); else srcImg( path( 1, i ) + 1, i, : ) = srcImg( path( 1, i ), i, : ) / 2 + ... srcImg( path( 1, i ) + 2, i, : ) / 2; end end  % 取得新的長和寬 [ h, w ] = size( srcImg ); end end