接缝裁剪
此条目没有列出任何参考或来源。 (2017年6月4日) |
此条目翻译品质不佳。 (2017年6月4日) |
接缝裁剪(Seam carving),是一个可以针对图像内容做正确缩放的算法(由Shai Avidan和Ariel Shamir所发表)。概念上,算法会找出一系列的接缝(seam)(接缝是在图像中最不重要的一连串像素),接著利用接缝对图像做缩放。如果是要缩小图像,则移除这些接缝,若是放大,则在这些接缝的位置上,插入一些像素。接缝裁剪可以人工定义一些不会被修改的像素区域,也可以从图像中移除整个物体。
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cb/Broadway_tower_edit.jpg/274px-Broadway_tower_edit.jpg)
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/a/a3/Broadway_tower_edit_scale.png/186px-Broadway_tower_edit_scale.png)
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/e/ef/Broadway_tower_edit_cropped.png/186px-Broadway_tower_edit_cropped.png)
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/e/ed/Broadway_tower_edit_Seam_Carving.png/186px-Broadway_tower_edit_Seam_Carving.png)
接缝裁剪算法的主要目的是图像重定向(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