Seam Carving 算法是2007年siggraph上的一篇paper，名為《Seam Carving for Content-Aware Image Resizing》，這篇paper提出了一種內(nèi)容感知的圖像縮放算法，繼這篇paper的思想，后來近幾年siggraph上面也有好幾篇都是內(nèi)容感知的圖像縮放算法。內(nèi)容感知的圖像縮放算法一般用于圖像的裁剪，就是有的時(shí)候，你覺得一張照片有點(diǎn)大，你希望把它裁剪的小一些，但是你又想保留照片中的物體，這個(gè)時(shí)候就要用到內(nèi)容感知的突刺昂縮放算法了。

? ??
原圖 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 裁剪結(jié)果
垂直方向裁剪
該開始學(xué)習(xí)這個(gè)算法的時(shí)候，看起來好像很高深莫測(cè)的樣子，理論看起來好像牛逼哄哄，什么能量，動(dòng)態(tài)規(guī)劃，都把我嚇到了，最后理論的東西我實(shí)在是受不鳥了，于是果斷直接解讀代碼，看了代碼以后，才知道這個(gè)算法其實(shí)非常簡(jiǎn)單，難度就比普通的圖像縮放難那么一點(diǎn)點(diǎn)，其實(shí)算法的原理很簡(jiǎn)單。廢話不多說，這邊只介紹縮小算法，且是圖像寬度縮小的算法，對(duì)于圖像高度縮小，只需對(duì)圖像轉(zhuǎn)置處理，總之paper中其它功能的實(shí)現(xiàn)，大同小異，整個(gè)過程說的簡(jiǎn)單一點(diǎn)就是通過尋找一條線，如上面的圖1所示，找到了線以后，把那條線上的像素點(diǎn)全部刪除，從而實(shí)現(xiàn)縮小操作。

該過程是通過迭代實(shí)現(xiàn)的，每次只能移除一列，迭代直到寬度滿足要求。下面介紹尋找移除能量線的方法，需要注意的是，每次移除一列，都要重新計(jì)算能量圖，也就是說，梯度圖要重新計(jì)算，才能進(jìn)行下一輪的移除工作。

算法流程

1、算法第一步：計(jì)算圖像能量圖?

能量圖一般是圖像像素的梯度模值，為了簡(jiǎn)化計(jì)算可先轉(zhuǎn)換成灰度圖像，然后直接采用如下公式(直接用x、y方向上的差分取絕對(duì)值，然后相加)，其實(shí)這一步就是相當(dāng)于邊緣檢測(cè)算法一樣：

2、算法第二步：尋找最小能量線

最小能量線指的是需要被移除的那一列：首先需要以圖像第一行或最后一行為開始行進(jìn)行迭代。下面實(shí)現(xiàn)的為從圖像最后一行開始，往上迭代，

?

[c++]?view plaincopy

//先找出圖片最底部的一行中，能量最小的像素點(diǎn)作為起始點(diǎn)??

int?min_x?=?0;??

int?width?=?(*Source).Width();??

int?height?=?(*Source).Height();??

for(?int?x?=?0;?x?<?width;?x++?)??

{??

????if(?(*Source)(x,height-1)->energy?<?(*Source)(min_x,height-1)->energy?)??

????{??

????????min_x?=?x;??

????}??

}??

找出最后一行需要被移除的像素點(diǎn)后，設(shè)其坐標(biāo)為P(x,y)，然后往上一行尋找，尋找的點(diǎn)為P點(diǎn)的在y-1行中的三個(gè)相鄰像素點(diǎn)中的能量最小值像素。也就是尋找的坐標(biāo)為(x-1,y-1)、(x,y-1)、(x+1,y-1);

?

[c++]?view plaincopy

?//min_x是圖片最底部的一行的能量值最小的像素點(diǎn)?因此遍歷的時(shí)候，要往上尋找??

void?Generate_Path(?CML_image_ptr?*?Energy,?int?min_x,?int?*?Path?)??

{??

????int?min;??

????int?x?=?min_x;//起始行的能量最小點(diǎn)??

????int?height?=?(*Energy).Height();??

//從底部往上尋找最小能量線??

????for(?int?y?=?height?-?1;?y?>=?0;?y--?)?//從下往上??

????{??

????????min?=?x;?//首個(gè)頂點(diǎn)迭代更新??

????????//計(jì)算上一行中??三個(gè)鄰接像素中能量值最小的像素點(diǎn)?作為上一行的能量最小點(diǎn)??

????????int?Maxy=??Get_Max(?Energy,?min,?y?);??

????????if(?Get_Max(?Energy,?x-1,?y?)?<?Maxy?)?//??

????????{??

????????????min?=?x?-?1;??

????????}??

????????if(?Get_Max(?Energy,?x+1,?y?)?<?Maxy?)?//up-right??

????????{??

????????????min?=?x?+?1;??

????????}??

????????Path[y]?=?min;??

????????x?=?min;??

????}??

}??

3、算法第三步：移除得到的最小能量線，讓圖片的寬度縮小一個(gè)像素

移除最小能量線，同時(shí)所有位于最小能量線右邊的像素點(diǎn)左移一個(gè)單位，從而實(shí)現(xiàn)圖像縮小寬度縮小一個(gè)單位。

移除的時(shí)候?為了讓圖像看起來自然，需要在移除縫線的地方進(jìn)行平均，假設(shè)移除坐標(biāo)為P(x,y),那么移除后P(x-1,y)的像素值為P(x-1,y)與P(x,y)的像素值的平均。P(x+1,y)的像素值為P(x-1,y)與P(x,y)的像素值的平均，然后才能把P(x+1,y)移動(dòng)到P(x,y)的位置。

?

[c++]?view plaincopy

int?height=(*Source).Height();??

????int?width=(*Source).Width();??

????//移除函數(shù)??

????for(?int?y?=0;?y?<?height;?y++?)??

????{??

????????int?remove?=?(Path)[y];??

????????(*(Source))(remove,y)->removed?=?true;??

????????//移除的時(shí)候?為了讓圖像看起來自然，需要在移除縫線的地方進(jìn)行平均，假設(shè)移除坐標(biāo)為P(x,y),那么??

????????//移除后P(x-1,y)的像素值為P(x-1,y)與P(x,y)的像素值的平均??

????????//P(x+1,y)的像素值為P(x-1,y)與P(x,y)的像素值的平均，然后才能把P(x+1,y)移動(dòng)到P(x,y)的位置??

????????if(?(remove?-?1)?>?0?)??

????????{??

????????????if(?(*(Source))(remove,y)->weight?>=?0?)??

????????????{??

????????????????(*(Source))(remove-1,y)->image?=?Average_Pixels(?(*(Source))(remove,y)->image,??

????????????????????(*(Source)).Get(remove-1,y)->image?);??

????????????}??

????????????(*(Source))(remove-1,y)->gray?=?Grayscale_Pixel(?&(*(Source))(remove-1,y)->image?);??

????????}??

??

????????if(?(remove?+?1)?<?(*(Source)).Width()?)??

????????{??

????????????if(?(*(Source))(remove,y)->weight?>=?0?)???

????????????{??

????????????????(*(Source))(remove+1,y)->image?=?Average_Pixels(?(*(Source))(remove,y)->image,??

????????????????????(*(Source)).Get(remove+1,y)->image?);??

????????????}??

????????????(*(Source))(remove+1,y)->gray?=?Grayscale_Pixel(?&(*(Source))(remove+1,y)->image?);??

????????}??

????????(*(Source)).Shift_Row(?remove?+?1,?y,?-1?);??

????}??

?對(duì)于圖像的放大算法原理一樣，先找到最小能量線，設(shè)能量線上點(diǎn)的坐標(biāo)為P(x,y),則在P(x,y)、P(x+1,y)中心位置插入新的像素，像素值為P(x,y)與P(x+1,y)的平均。本文地址：http://blog.csdn.net/hjimce/article/details/44916869?? ?作者：hjimce ? ? 聯(lián)系qq：1393852684 ? ? ? ? ? ? ?更多資源請(qǐng)關(guān)注我的博客：http://blog.csdn.net/hjimce? ? ? ? ? ? ? ? ?原創(chuàng)文章，版權(quán)所有，轉(zhuǎn)載請(qǐng)保留這幾行信息

總結(jié)

以上是生活随笔為你收集整理的图像处理（二）Seam Carving算法-Siggraph 2007的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。