多相同最小能量值線路下基于線裁剪的圖像縮放算法研究

陳小娥，李慧敏

（福建船政交通職業(yè)學(xué)院信息工程系，福州350007）

多相同最小能量值線路下基于線裁剪的圖像縮放算法研究

陳小娥，李慧敏

（福建船政交通職業(yè)學(xué)院信息工程系，福州350007）

針對(duì)線裁剪圖像縮放算法中可能同時(shí)存在多條能量值最小的線路且當(dāng)其數(shù)量多于待提取的線路時(shí)，選擇不同的提取路線將產(chǎn)生不一樣的縮放效果的情況，提出一種改進(jìn)的能量值線路提取方法，通過(guò)增加約束條件計(jì)算具有相同最小能量值線路的位置偏移差，在能量值相等的情況下優(yōu)先提取位置偏移差最小的線路。實(shí)驗(yàn)結(jié)果證明，改進(jìn)的算法提取的線路定位更為合理，視覺(jué)關(guān)注重點(diǎn)區(qū)域出現(xiàn)扭曲變形的問(wèn)題得到改善，可較好地應(yīng)用于各種風(fēng)格屬性的圖像縮放，特別是簡(jiǎn)筆畫，能獲得更好的裁剪結(jié)果。

線裁剪；圖像縮放；位置偏移差；簡(jiǎn)筆畫

0 引言

隨著多媒體技術(shù)和信息技術(shù)的不斷發(fā)展，日常生活中常用的數(shù)碼設(shè)備越來(lái)越多，隨處可見，尺寸不一。那么對(duì)于同一張圖像在不同的顯示設(shè)備上，如何自適應(yīng)地改變圖像大小來(lái)適應(yīng)新的顯示設(shè)備，方便人們對(duì)圖像的理解，使圖像的表現(xiàn)形式更加人性化，就成為當(dāng)前圖像處理領(lǐng)域研究的熱點(diǎn)問(wèn)題之一。這類問(wèn)題的研究即為圖像的放大和縮小，即通過(guò)一定的技術(shù)手段在保證圖像質(zhì)量的情況下，改變圖像尺寸的過(guò)程。

傳統(tǒng)的圖像縮放方法通常采用插值算法或直接裁剪算法。插值算法對(duì)于圖像縮小和放大均可適用，但由于原始圖像和顯示縱橫比不同，插值算法通常會(huì)導(dǎo)致原始圖像中的重要內(nèi)容在縮放過(guò)程中產(chǎn)生較大變形。而直接剪裁算法則適用于圖像縮小，很多情況下會(huì)改變圖像內(nèi)容，可能剪掉圖像中的重要內(nèi)容。

2003年，Suh等［1］提出基于內(nèi)容感知的裁剪縮放方法。該方法首先計(jì)算原始圖像的顯著度圖，并利用貪婪算法搜索含有顯著度點(diǎn)百分比最多的裁剪窗口，然后根據(jù)所搜索的窗口進(jìn)行裁剪。同時(shí)加上了人臉檢測(cè)機(jī)制，彌補(bǔ)傳統(tǒng)直接裁剪法容易刪除重要內(nèi)容的缺陷。2007年，Avidan等［2］首次提出了基于線裁剪的圖像縮放方法。針對(duì)圖像縮小問(wèn)題，該方法采取一次去除一條能量值最低的像素帶的策略，然后逐次刪減，直到最終達(dá)到目標(biāo)尺寸。該算法以梯度的一階范數(shù)確定每個(gè)像素的能量值，并利用累積能量反映每條線路對(duì)視覺(jué)感知的重要性，在具體優(yōu)化過(guò)程中，采用動(dòng)態(tài)規(guī)劃的方法選出能量值最低的像素帶。國(guó)內(nèi)也有眾多學(xué)者在數(shù)字圖像智能縮放方面做出了出色的貢獻(xiàn)。2010年雷勵(lì)星［3］研究了基于混合能量的內(nèi)容敏感圖像縮放方法，該方法旨在保持圖像縮放前后重要特征區(qū)域盡量相似的前提下，通過(guò)約束重要區(qū)域的旋轉(zhuǎn)使得圖像縮放前后效果盡量一致；該方法具有保全局和局部特征、重要物體不易旋轉(zhuǎn)、能夠高效地得到扭曲較小的結(jié)果等優(yōu)點(diǎn)。2014年聶棟棟等［4］提出了新線路能量函數(shù)下基于線裁剪的圖像自適應(yīng)縮放算法，該算法通過(guò)定義新增能量項(xiàng)衡量刪除線路上像素點(diǎn)后圖像局部區(qū)域的走樣變形，并引入最大像素能量項(xiàng)降低隨機(jī)紋理區(qū)的線路能量，從而使得重點(diǎn)對(duì)象細(xì)節(jié)部分走樣的問(wèn)題也更少。

自Avidan提出基于線裁剪的圖像縮放算法之后，很多學(xué)者對(duì)于圖像縮放問(wèn)題的研究都是基于該算法的進(jìn)一步改進(jìn)，且很多是基于能量函數(shù)的計(jì)算方法。如，Rubinstein等［5］提出計(jì)算刪除每條線路上的像素后的前向能量；Achanta等［6］通過(guò)區(qū)域顯著性提取算法計(jì)算像素能量；Han等［7］對(duì)小波分解后的高頻分量進(jìn)行混合計(jì)算像素能量。共同點(diǎn)是如何找出圖像中各個(gè)像素或者各條路線的視覺(jué)重要性的計(jì)算方法。這些算法在一些攝影圖片中均取得了不錯(cuò)的裁剪效果。本文針對(duì)SC算法中提取的最小能量值線路可能同時(shí)多條存在，且當(dāng)其數(shù)量多于待提取線路數(shù)量時(shí)，選擇不同的最小能量值線路對(duì)縮放結(jié)果存在一定影響的情況，提出一種改進(jìn)的縮放算法，通過(guò)新的提取方式，即新增計(jì)算線路的位置偏移差，優(yōu)先提取能量值最小且線路的位置偏移差也最小的路線。該算法使得提取的線路更為合理，且同等情況下，改進(jìn)的算法能避免提取的線路盡量較少通過(guò)視覺(jué)關(guān)注重點(diǎn)區(qū)域，因而可以較好地改善重點(diǎn)對(duì)象出現(xiàn)扭曲變形的問(wèn)題，同時(shí)在各種風(fēng)格屬性的圖片中得到更好的裁剪效果，特別是簡(jiǎn)筆畫圖像，因其圖像內(nèi)容相對(duì)比較簡(jiǎn)單，可能存在大量相同的能量值最小的情況，因此簡(jiǎn)筆畫圖片在本文改進(jìn)算法的作用下，取得了更優(yōu)的縮放效果。

1 算法原理

1．1 Seam Carving算法

基于SC（Seam Carving）的算法，其基本思路是，每次按一定的規(guī)律插入或者抽取圖像中能量值最低的橫向或者縱向的一條像素帶。由于選擇的是一條條的像素帶，所以SC方法首先定義了像素帶和它的能量。

像素帶，簡(jiǎn)記為S。對(duì)于一幅n×m的圖像I，垂直方向的S定義為：

這里x是一個(gè)映射，即x：［1，…，n］→［1，…，m］。這條垂直方向的S從第一個(gè)像素點(diǎn)開始，在每個(gè)像素點(diǎn)的8領(lǐng)域范圍尋找一條自上而下的縫。類似的，可以定義一條水平方向的像素帶：

式中y是一個(gè)映射，即y：［1，…m］→［1，…，n］。

以垂直的S為例，SC的過(guò)程如下：S在圖像I中表示為：

同時(shí)，需要定義每條S的能量，作為挑選S的定量依據(jù)。算法中使用的能量函數(shù)e如下：

于是，S能量定義的一般形式為E（s）＝E（Is）＝然后通過(guò)尋找最優(yōu)解s＊使得E（s）最小。每次被挑選的S可以通過(guò)動(dòng)態(tài)規(guī)劃算法找出。整個(gè)過(guò)程需要從圖像的第二行到最后一行遍歷，累積每個(gè)像素點(diǎn)的能量得到一個(gè)最小能量M，對(duì)于任意輸入點(diǎn)（i，j）能量表示為

最后，可以從最小值位置進(jìn)行回溯找到整條最優(yōu)路徑。同理，我們可以求得水平方向最小值和最優(yōu)路徑。

1．2 存在的問(wèn)題分析

由于SC算法主要是通過(guò)各種能量的定義，選出并改變圖像中相對(duì)比較不引人注意的像素帶，并保持改變后的部分與周圍的環(huán)境能協(xié)調(diào)。該算法對(duì)于內(nèi)容相對(duì)復(fù)雜的圖片是適用的，如很多學(xué)者研究的攝影圖片，裁剪效果相對(duì)傳統(tǒng)的裁剪算法也取得了較好的效果。

但是該算法對(duì)于一些其他風(fēng)格屬性的圖片，特別是內(nèi)容相對(duì)簡(jiǎn)單的，如簡(jiǎn)筆畫圖片，裁剪效果就不盡人意。原因就在于，一般情況下，若圖片內(nèi)容相對(duì)比較復(fù)雜，累積每個(gè)像素點(diǎn)的能量得到的像素帶的能量值千差萬(wàn)別。因而，每次挑選像素帶最小能量值的時(shí)候，一般只有一條或者極少數(shù)幾條像素帶能量值相等的情況。而對(duì)于簡(jiǎn)筆畫圖片，可能存在大量相同的最小能量值的像素帶，那么對(duì)于相同最小能量值的像素帶，如何選擇合理的裁剪順序就會(huì)直接影響裁剪的效果。

1．3 改進(jìn)的算法思想及分析

對(duì)于一些圖像內(nèi)容信息相對(duì)比較簡(jiǎn)單的圖片，可能存在大量相同的最小能量值。SC算法本身一次刪除或者增加一條視覺(jué)信息重要度最低的像素帶，即能量值最小的像素帶，當(dāng)存在多條相同最小能量值的時(shí)候，選擇哪一條最小能量值，策略不同，結(jié)果圖就不一樣。如圖1所示，假設(shè)以下是一幅9×6的圖片，而其中橫條紋、豎條紋和斜條紋所在的方格組成的路線是經(jīng)過(guò)動(dòng)態(tài)規(guī)劃算法得出的能量值相同且都最小的路徑。對(duì)于圖1而言，當(dāng)要提取或者刪除的圖片的列數(shù)小于3的時(shí)候，對(duì)于橫條紋、豎條紋或者斜條紋的像素帶選擇哪一條或者哪2條進(jìn)行刪除，所得到縮放結(jié)果圖是不同的。

圖1 不同路徑相同最小能量值示意圖

以一個(gè)簡(jiǎn)單的圖形——圓為例，如圖2所示，圖2（a）和圖2（b）分別為圓及其能量值對(duì)應(yīng)的01矩陣示意圖，由圖2（b）可以看出存在多條路徑能使能量值和得到最小值0。當(dāng)要將圖像的寬度減少2時(shí)，選擇不同的裁剪路徑得到的結(jié)果圖是不一樣的，圖2（c）和圖2（d）就為2種不同的提取方式以及對(duì)應(yīng)的縮放效果，圖中數(shù)字加著重點(diǎn)形成的路線為其中一條最小能量值路徑，數(shù)字加下劃線所形成的路線為另一條最小值路徑，它們所在的路徑的能量值和都為最小值0，圖2（c）和圖2（d）因提取的線路不一樣，所得到的縮放結(jié)果圖也不一樣，由圖可看出圖2（c）的縮放結(jié)果更為理想，更能保持原圖的整體特征。

圖2 圓的縮放過(guò)程示意圖

為解決這個(gè)問(wèn)題，本文提出了以下2個(gè)策略對(duì)SC算法進(jìn)行改進(jìn)：

1）當(dāng)具有多條最小能量值的路徑存在時(shí)，為了使得縮放結(jié)果更符合人類視覺(jué)特征，也不破壞圖像中視覺(jué)關(guān)注重點(diǎn)區(qū)域，可盡量選擇跟裁剪方向一致的像素帶，即如果要減少圖像的寬度，則提取的線路在滿足式（5）的前提下盡量選擇相對(duì)較垂直的；如果要減少圖像的高度，提取的線路則同樣盡量選擇相對(duì)較水平方向的，由此可以減少重點(diǎn)對(duì)象發(fā)生扭曲變形的概率。由式（5）可知，從任意點(diǎn)（i，j）出發(fā)，每次其左上、正上及右上3個(gè)方向（如圖3所示）的像素點(diǎn)能量的累加，就可以依次找到圖像中能量最低的一條縫。以垂直縫為例，根據(jù)SC算法中縫的定義，像素帶在圖像中的每一行只取一個(gè)像素點(diǎn)，這樣在形式上形成一條貫穿圖像的像素帶，而當(dāng)其左上、正上及右上3個(gè)點(diǎn)能量值相等的時(shí)候，取不同點(diǎn)作為回溯的點(diǎn)，將形成不同的縫。對(duì)于垂直縫，為使計(jì)算得到的縫盡量保持垂直的方向，我們?nèi)≈虚g正上方向的點(diǎn)作為找到最優(yōu)路徑之后回溯時(shí)（i，j）點(diǎn)的前一個(gè)點(diǎn)，如圖3中加粗線所示。水平方向所求的水平縫以此類推。

圖3 垂直縫的走向

2）在SC算法動(dòng)態(tài)規(guī)劃求解過(guò)程中，增加一個(gè)控制偏移量的約束條件。即由上自下或者從左至右計(jì)算最小能量值的時(shí)候，同時(shí)計(jì)算路徑上的位置偏移差，其計(jì)算方法如公式（6）所示。從圖像的第二行到最后一行遍歷，累積每個(gè)像素點(diǎn)的能量得到一個(gè)最小能量M的同時(shí)，累積每個(gè)像素點(diǎn)的位移偏差，對(duì)于任意輸入點(diǎn)（i，j）位移偏差表示為

該式的計(jì)算受公式（5）條件的約束，即offset（i，j）的計(jì)算依賴于M（i，j）的計(jì)算，具體約束關(guān)系如下：當(dāng)式（5）中的M（i－1，j－1）使得M（i，j）取最小值時(shí)，offset（i，j）的計(jì)算就取第一個(gè)式子offset（i－1，j－1）＋1；當(dāng)M（i－1，j）使得M（i，j）取最小值時(shí)，offset（i，j）的計(jì)算就取第二個(gè)式子offset（i－1，j）；當(dāng)M（i－1，j＋1）使得M（i，j）取最小值時(shí)，offset（i，j）的計(jì)算就取第三個(gè)式子offset（i－1，j＋1）＋1。當(dāng)有多條最小能量值相同的情況下，優(yōu)先選擇位置偏移差最小的路徑。

2 實(shí)驗(yàn)結(jié)果分析

算法測(cè)試在Visual Studio 2015C＃環(huán)境下進(jìn)行，主要完成了SC算法及本文的改進(jìn)算法，核心算法均是采用動(dòng)態(tài)規(guī)劃算法，根據(jù)式（4）定義的能量函數(shù)，提取能量最小的線路。同時(shí)，本文提出的改進(jìn)算法加上了式（6）的約束條件。以下分3個(gè)方面分析實(shí)驗(yàn)測(cè)試效果。

2．1 簡(jiǎn)筆畫圖片的縮放效果比較

通過(guò)實(shí)驗(yàn)，本文改進(jìn)算法在對(duì)簡(jiǎn)筆畫的縮放效果方面明顯優(yōu)于文獻(xiàn)［2］的算法。如圖4所示，其中圖4（a）、圖4（d）為原始圖像，經(jīng)過(guò)文獻(xiàn)［2］算法縮放處理后的效果圖分別為圖4（b）和圖4（e），由圖可以看出，圖像中的視覺(jué)重要區(qū)域發(fā)生了嚴(yán)重的扭曲變形，而一些視覺(jué)非重要區(qū)域卻未被提取和刪除。圖4（c）、圖4（f）是采用本文改進(jìn)后的算法實(shí)現(xiàn)的圖像收縮，能較好地保留了原始圖像的重要信息內(nèi)容。

圖4 簡(jiǎn)筆畫圖像在不同算法下縮放效果比較圖

2．2 與傳統(tǒng)圖像縮放算法比較

由于本文算法核心思想還是采用基于SC的算法原理，因此算法結(jié)果仍具有原本SC算法的優(yōu)點(diǎn)。如圖5所示，將本文算法與傳統(tǒng)圖像縮放方法進(jìn)行比較。其中圖5（a）為原始圖像，圖像尺寸為300× 200，圖5（b）、圖5（c）、圖5（d）為縮放后的結(jié)果圖，圖像尺寸為180×200，分別為傳統(tǒng)圖像縮放算法的均勻縮放、直接裁剪和本文算法。由圖5可以看出采用傳統(tǒng)均勻縮放算法處理后，兩只小狗被明顯壓縮變形；傳統(tǒng)的直接裁剪算法，使得圖像中右邊小狗的一些重要圖像信息沒(méi)有顯示出來(lái)；本文自適應(yīng)圖像縮放處理后，提取并刪除的線路都位于不受視覺(jué)關(guān)注的區(qū)域，所以能夠較好地保護(hù)圖像的整體顯示效果。

圖5 本文算法與傳統(tǒng)圖像縮放算法的比較

2．3 在各種風(fēng)格屬性圖片的應(yīng)用

將本文算法應(yīng)用到各種風(fēng)格屬性的圖片中，同樣能獲得較好的縮放效果，如圖6所示。其中圖6（a）、圖6（c）、圖6（e）、圖6（g）為原始圖像，分別是國(guó)畫、油畫、水彩、攝影圖片，圖像尺寸都為300×200，圖6（b）、圖6（d）、圖6（f）、圖6（h）為相應(yīng)的裁剪效果圖，其中圖6（b）、圖6（d）縮放后的圖像尺寸為200×200，圖6（f）、圖6（g）縮放后的圖像尺寸為300 ×120。從實(shí)驗(yàn)效果看，本文算法也適用于各種風(fēng)格屬性的圖片。

圖6 本文算法在各種風(fēng)格屬性圖片中的應(yīng)用

3 結(jié)語(yǔ)

自適應(yīng)圖像縮放根據(jù)目標(biāo)圖像的分辨率，選擇并提取原始圖像中對(duì)視覺(jué)感知不太重要的部分進(jìn)行處理，而保護(hù)圖像中視覺(jué)關(guān)注的重點(diǎn)對(duì)象或區(qū)域。本文提出的改進(jìn)的線路選擇方法，與傳統(tǒng)圖像縮放算法相比，能夠自適應(yīng)地根據(jù)圖像內(nèi)容進(jìn)行縮放，有效保護(hù)圖像中的重點(diǎn)對(duì)象的顯示效果。與經(jīng)典的文獻(xiàn)［2］算法比較，本文算法在計(jì)算出最小能量值后，根據(jù)位移偏差選擇最終的提取線路具有更合理的定位，可以有效減少視覺(jué)關(guān)注重點(diǎn)的對(duì)象的扭曲變形。

［1］Sub B，Ling H，Bederson B，et al．Automatic thumbnail cropping and its effectiveness［C］／／UIST＇03Proceedings of the 16th annual ACM symposium on User interface software and technology．ACM NewYork，NY，USA，2003：95－104．

［2］Avidan S，Shamir A．Seam carving for content－aware image resizing［C］／／ACM Transactions on Graphics．ACM New York，NY，USA，2007．

［3］雷勵(lì)星．基于混合能量的內(nèi)容敏感圖像縮放新方法［J］．計(jì)算機(jī)學(xué)報(bào)，2010，33（10）：2015－2021．

［4］聶棟棟，馬勤勇．新線路能量函數(shù)下基于線裁剪的圖像自適應(yīng)縮放［J］．模式識(shí)別與人工智能，2014，27（11）：1040－1046．

［5］Rubinstein M，Shamir A，Avidan S．Improved seam carving for video retargeting［C］／／ACM Transactions on Graphics，ACM New York，NY，USA，2008．

［6］Achanta R，Susstrunk S．Saliency detection for content－aware image resizing［C］／／Proc of the 16th IEEE International Conference on Image Processing．Cairo，Egypt，2009：1005－1008．

［7］Han J W，Choi K S，Wang T S，et al，Wavelet based seam carving for content－aware image resizing［C］／／Proc of the 16th IEEE International Conference on Image Processing．Cairo，Egypt，2009：345－348．

［8］Dong WM，Bao GB，Zhang XP et al．Fast multi－operator image resizing and evaluation［J］．Journal of Computer Science and Technology，27（1）：121－134．

［9］梁云，傅賢超，劉財(cái)興．重要區(qū)域保持的圖像縮放質(zhì)量評(píng)價(jià)方法［J］．中國(guó)圖象圖形學(xué)報(bào)，2014，19（8）：1168－1175．

The Study on an Image Resizing Algorithm Based on Seam Carving with Lots of Same Minimum Energy Value Paths

CHEN Xiao－e，etc．
（Department of Information Engineering，F(xiàn)ujian Chuanzheng Communications College，F(xiàn)uzhou350007，China）

To solve the problem that there are lots of optimum seams with same minimum energy values and its amount is more than to be extracted，and by choosing different extracted seams will lead to different re－sizing results，an improved adaptive image resizing algorithm has been proposed based on Seam Carving．The improve algorithm calculates the position offset of seams and select the minimum one．The experimental results show that the seams extracted by the improved algorithm are more reasonable，and it has fewer aliasing problems in the details of image’s key objects．It is better applying to all kinds of images resizing，and it has a better effect especially in the seam carving of simple stroke drawing．

seam carving；image resizing；position offset；simple stroke drawing

TP391

A

1009－8984（2016）02－0111－05

10．3969／j．issn．1009－8984．2016．02．028

2016－03－08

福建省中青年教師教育科研項(xiàng)目（科技）（JA15657）

陳小娥（1984－），女（漢），福建永春，講師，碩士主要研究圖像處理。