接縫裁剪
此條目沒有列出任何參考或來源。 (2017年6月4日) |
此條目翻譯品質不佳。 (2017年6月4日) |
接縫裁剪(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