一種改進(jìn)的放大圖像邊緣修復(fù)算法

于媛媛，王兆仲

北京航空航天大學(xué) 圖像處理中心，北京 100191

一種改進(jìn)的放大圖像邊緣修復(fù)算法

于媛媛，王兆仲

北京航空航天大學(xué) 圖像處理中心，北京 100191

1 引言

圖像以矢量圖或位圖的格式顯示在計(jì)算機(jī)上。對(duì)一幅圖像進(jìn)行放大，會(huì)在一定程度上造成邊緣區(qū)域信息的損失。位圖由單個(gè)的像素點(diǎn)組成，當(dāng)放大位圖時(shí)會(huì)增大單個(gè)像素，從而使線條和形狀顯得參差不齊，出現(xiàn)模糊和鋸齒現(xiàn)象。矢量圖使用點(diǎn)、線、矩形等來(lái)描述圖形。由于這些圖形的元素是通過(guò)數(shù)學(xué)公式計(jì)算獲得，因此矢量圖放大不會(huì)失真，但是矢量圖難以表現(xiàn)色彩層次豐富的逼真圖像效果。針對(duì)上述存在的問(wèn)題，提出了一個(gè)放大圖像邊緣修復(fù)算法。本文算法既能有效減少放大圖像引起的失真，又能保持豐富逼真的圖像效果，同時(shí)提高了算法運(yùn)行速度。經(jīng)研究表明，能否增加圖像邊緣的光滑度，減弱鋸齒現(xiàn)象決定了邊緣修復(fù)效果的好壞。

從受損區(qū)域周邊像素獲取有效信息，并且選取一定的像素填充方法，即可恢復(fù)出放大后圖像清晰的邊緣。本文算法的兩個(gè)新穎之處是：（1）對(duì)初始放大圖像的邊緣輪廓進(jìn)行分段三次Hermite插值，可以生成相對(duì)光滑的矢量圖像邊緣。（2）通過(guò)距離變換求取地勢(shì)圖。有了地勢(shì)圖就可以利用分水嶺變換求出填充優(yōu)先權(quán)，從而引導(dǎo)后期的填充過(guò)程。傳統(tǒng)的分水嶺算法主要用于圖像分割上，這里用于確定像素的填充優(yōu)先權(quán)上[1]。

Inpainting-Based Enhancement[1-2]，Anisotropic Diffusion[3-4]和Shock Filters[5-6]，Bilateral Filter[7-8]及單幀超分辨率重建是一些具有圖像增強(qiáng)和放大功能的算法。但是，這些方法仍然會(huì)在一定程度上產(chǎn)生模糊的邊緣。Shock Filters起初用于對(duì)信號(hào)/圖像進(jìn)行去模糊，并且在原始信號(hào)拐點(diǎn)處產(chǎn)生沖擊信號(hào)。這個(gè)方法對(duì)噪聲比較敏感，適用于原本模糊程度較小的圖像，否則會(huì)產(chǎn)生相反的效果。改進(jìn)的GSZ shock-filter[5]更適用于灰度圖像，處理彩色圖像效果并不理想。Anisotropic Diffusion考慮了各向異性的擴(kuò)散，以保證邊緣處的邊界連續(xù)，但是計(jì)算不穩(wěn)定。Bilateral Filter效果總體很好，邊界清晰且光滑，但是在運(yùn)行效率上有待改進(jìn)。Inpainting-Based Enhancement同樣是基于分水嶺的算法，運(yùn)行時(shí)間大大改善，并且能夠形成較為清晰的圖像邊緣，不足之處是對(duì)圖像梯度較為敏感，并且邊緣不夠光滑。本文算法是在Inpainting-Based Enhancement的基礎(chǔ)上加以改進(jìn)，使用距離變換解決了對(duì)圖像梯度敏感的弱點(diǎn)，通過(guò)分段三次Hermite插值改善了邊界的光滑度。由于只有模糊邊緣區(qū)域的像素會(huì)進(jìn)行修復(fù)，其他像素保持不變，因而避免了塊效應(yīng)的產(chǎn)生?？傊?，本文算法在理論上確保了邊緣像素值的不連續(xù)性和邊界曲線的光滑度。

2 算法流程

本文算法由以下四個(gè)步驟組成：（1）初始放大。本文選用一種簡(jiǎn)單的方法，即立方卷積插值放大。（2）計(jì)算圖像地勢(shì)。對(duì)第一步放大后的圖像進(jìn)行距離變換，得出度量任意像素距離圖像邊界的標(biāo)準(zhǔn)，這里稱之為圖像地勢(shì)：距離圖像邊緣越近的像素所處的地勢(shì)越高。此處的處理對(duì)應(yīng)于分水嶺變換用到的地勢(shì)函數(shù)。同一地勢(shì)的像素存儲(chǔ)到一個(gè)隊(duì)列中，從而進(jìn)行后面的填充處理。這個(gè)操作對(duì)算法運(yùn)行效率的提高起到了至關(guān)重要的作用。（3）確定標(biāo)記圖像。這個(gè)步驟也就是標(biāo)記哪些像素是已知像素，哪些像素是未知像素。其中未知像素組成的區(qū)域是待修復(fù)區(qū)域。用分段三次Hermite插值提取出一個(gè)更為光滑的圖像邊緣，再進(jìn)行一定程度的膨脹處理，即可自動(dòng)確定待修復(fù)區(qū)域。（4）像素填充。填充優(yōu)先權(quán)如何確定，對(duì)一個(gè)修復(fù)算法來(lái)說(shuō)是至關(guān)重要的，尤其是基于樣本的圖像修復(fù)方法[9]。在新的修復(fù)算法中，填充優(yōu)先權(quán)可以描述為：距離圖像邊界越遠(yuǎn)的像素點(diǎn)，具有越高的填充優(yōu)先權(quán)。利用分水嶺算法中的迭代公式對(duì)每一高度進(jìn)行填充，當(dāng)填充后的像素在邊界處相遇時(shí)，整個(gè)填充過(guò)程就完成了，清晰的邊界自然生成。圖1為上述過(guò)程的流程圖。

圖1 圖像邊緣修復(fù)流程圖

3 算法原理

上一章描述了算法的整體框架，并且用流程圖表示出來(lái)，下面分節(jié)描述具體算法原理。

3.1 地勢(shì)圖的確定

距離變換在數(shù)字圖像處理中應(yīng)用十分廣泛，尤其是應(yīng)用于骨架提取上。本文則是通過(guò)距離變換求取每一像素的地勢(shì)值，從而得到填充處理所需的地勢(shì)圖。

對(duì)于二值圖像中的每一個(gè)像素，距離變換的結(jié)果說(shuō)明了這個(gè)像素與圖像中最近的非零點(diǎn)的距離[10]。更確切地說(shuō)，設(shè)B={(x，y)|(x，y)∈Kc}，歐式距離變換[10]就是對(duì)圖像I中所有像素點(diǎn)(i，j)求：

不同的距離定義，對(duì)應(yīng)不同的距離變換方法。歐氏距離變換的主要優(yōu)點(diǎn)是運(yùn)行速度比較快。在本文算法中，距離變換主要用來(lái)衡量圖像中任一像素到圖像邊界的距離：圖像邊緣處像素地勢(shì)最高，離邊緣處越遠(yuǎn)的像素地勢(shì)越低。此處的圖像邊緣通過(guò)Canny邊緣檢測(cè)算子求取。結(jié)合到數(shù)據(jù)結(jié)構(gòu)中隊(duì)列的知識(shí)，同一地勢(shì)的像素存儲(chǔ)到一個(gè)隊(duì)列中，從而進(jìn)行后面的填充處理。

3.2 標(biāo)記圖像的求取

求出地勢(shì)圖后，就要求取標(biāo)記圖像。最初的標(biāo)記圖像是在Canny邊緣檢測(cè)算子的基礎(chǔ)上確定的，繼而對(duì)邊緣進(jìn)行膨脹操作，獲得預(yù)定的標(biāo)記值。針對(duì)Canny算子具有本身的針對(duì)性和局限性，例如抑制噪聲和檢測(cè)低強(qiáng)度邊緣能力不足[11]。本文算法在提取邊緣的這一環(huán)節(jié)采取邊緣輪廓擬合插值。為了避免高次插值可能帶來(lái)的大幅波動(dòng)現(xiàn)象，實(shí)際上通常采用分段低次插值來(lái)提高擬合程度，選取分段三次Hermite插值。

在實(shí)際插值問(wèn)題中，為了使插值函數(shù)能更好地和原來(lái)的函數(shù)重合，不但要求二者在節(jié)點(diǎn)上函數(shù)值相等，而且還要求對(duì)應(yīng)的導(dǎo)數(shù)值相等，甚至要求高階導(dǎo)數(shù)也相等。滿足這種要求的插值多項(xiàng)式就是Hermite插值多項(xiàng)式。設(shè)a≤x0，x1，…，xn≤b為區(qū)間[a，b]的一個(gè)分割，定義在[a，b]上的分段線性插值函數(shù)Ih(x)的導(dǎo)數(shù)是間斷的，若在節(jié)點(diǎn)xk(k=0，1，…，n)上除已知函數(shù)值fk外還給出導(dǎo)數(shù)值，這樣就能構(gòu)造出一個(gè)導(dǎo)數(shù)連續(xù)的分段三次插值函數(shù)[12]Ih(x)，滿足：（1）Ih(x)∈C[a，b]；（2）在每個(gè)小區(qū)間[xk，xk+1]上是三次多項(xiàng)式。若在整個(gè)區(qū)間上定義一組分段三次插值基函數(shù)αj(x)及βj(x)則Ih(x)可表示為：

圖2為經(jīng)典lena圖像的原始邊緣輪廓與分段三次Her-mite插值后的邊緣輪廓對(duì)比圖。其中，（a）圖為Canny邊緣檢測(cè)算子確定的原始邊緣，（b）圖為插值后邊緣。由圖2可知，分段三次Hermite插值產(chǎn)生的邊緣輪廓減弱了原始輪廓的波動(dòng)性，減少了鋸齒現(xiàn)象，生成的邊界曲線更為光滑。邊緣輪廓的光滑與否決定了填充后圖像邊緣的光滑程度。因此，分段三次Hermite插值的選取在理論上確保了填充后圖像邊界曲線的光滑度。

圖2（b）分段三次Hermite插值結(jié)果對(duì)比圖

除了分段三次Hermite插值外，還有其他插值方法如三次樣條插值[13]。三次樣條插值雖然會(huì)避免使用高階多項(xiàng)式出現(xiàn)的龍格現(xiàn)象，但是產(chǎn)生的邊緣過(guò)于波動(dòng)，生成的填充圖像邊緣會(huì)出現(xiàn)較多的鋸齒。實(shí)際計(jì)算中，三次樣條插值還需要引入邊界條件，在運(yùn)行效率上并不占優(yōu)勢(shì)。

插值處理后，在求出的邊緣輪廓基礎(chǔ)上進(jìn)行膨脹處理，得到前述的標(biāo)記圖像。本文中規(guī)定未知像素的標(biāo)記值為0，邊界區(qū)域像素的標(biāo)記值為255，已知像素標(biāo)記值則依據(jù)距離變換的結(jié)果標(biāo)記為1～254。標(biāo)記圖像的確定為后期像素填充起到了關(guān)鍵的引導(dǎo)作用。

3.3 像素的填充

上述兩節(jié)分別求出了地勢(shì)圖和標(biāo)記圖像。有了這兩個(gè)數(shù)據(jù)，接下來(lái)就可以利用分水嶺變換進(jìn)行具體的填充處理。

分水嶺的概念可以通過(guò)浸沒(méi)模擬[14]來(lái)得到很好的說(shuō)明。這個(gè)概念是以對(duì)圖像進(jìn)行三維可視化處理為基礎(chǔ)的。傳統(tǒng)的分水嶺變換與圖像的梯度有密切聯(lián)系。本文利用了距離變換的中間結(jié)果克服了對(duì)圖像梯度敏感的缺點(diǎn)。

I為圖像域且I=Θ∪Ω其中Θ代表已知像素的區(qū)域，Ω代表待修復(fù)區(qū)域，即包含模糊邊緣的區(qū)域。在待修復(fù)區(qū)域Ω存在一個(gè)地勢(shì)函數(shù)g，g可取為對(duì)初始放大后圖像進(jìn)行距離變換的結(jié)果，即前述的地勢(shì)圖。T[n]是g在高度n上的閾值n為距離變換后對(duì)應(yīng)的高度值。令B[n]為高度n上的匯水盆地[14]，有下面的迭代公式：

其中，IZ為測(cè)地影響區(qū)域[1]。隨著高度n從1逐步上升，集合B[n]B[n-1]中的元素對(duì)應(yīng)每一高度待修復(fù)的像素集合。初始部分B[0]被視為已知區(qū)域Θ。B[1]為B[0]的邊界上的像素。從B[1]中選出滿足g(p)=1的點(diǎn)p。然后再尋找未填充的點(diǎn)q∈IZT[1]∪Θ(B[0])。上述點(diǎn)q就是待填充的點(diǎn)。在填充結(jié)束后，再次尋找未填充的點(diǎn)并進(jìn)行填充，直至所有點(diǎn)都處理完畢。然后令n=n+1來(lái)填充更高的地勢(shì)。

上面的填充過(guò)程體現(xiàn)了填充優(yōu)先權(quán)：距離圖像邊界越遠(yuǎn)的像素點(diǎn)，具有越高的填充優(yōu)先權(quán)。為了防止求得的圖像邊緣過(guò)于尖銳，可令：

Α為初始放大后圖像，α為根據(jù)實(shí)際選取的0～1的系數(shù)。若α=1，則退化為I(q)=I(p)，即具有階梯現(xiàn)象的結(jié)果。若α=0，則為初始放大后的圖像。

4 實(shí)驗(yàn)分析

實(shí)驗(yàn)采用Matlab編程實(shí)現(xiàn)以上的修復(fù)算法，程序運(yùn)行在CPU E7500@2.93 GHz，2 GB內(nèi)存的計(jì)算機(jī)上。選取彩色圖像作為原始數(shù)據(jù)。圖3為實(shí)驗(yàn)選取的測(cè)試圖像。圖4說(shuō)明了修復(fù)步驟：圖4（a）中初始放大使用立方卷積插值放大，放大倍數(shù)理論上可選取算法允許的任意整數(shù)，本文選取10；圖4（b）為距離變換的處理結(jié)果，可以清楚地看到任意像素到圖像邊緣的距離：越靠近邊緣點(diǎn)，像素值越高；圖4（c）為利用邊緣擬合插值（分段三次Hermite插值）并進(jìn)行膨脹處理后的結(jié)果，白色區(qū)域?yàn)樽詣?dòng)確定的待修復(fù)區(qū)域；圖4（d）為填充后的結(jié)果，其中將式（5）中的參數(shù)α設(shè)為0.8。這樣設(shè)置的原因如圖5所示，該圖針對(duì)同一幅圖像選取不同的α求出相對(duì)立方卷積放大圖的峰值信噪比曲線（PSNR）。由數(shù)據(jù)可知，α的值越高，PSNR值越高。但當(dāng)α取1時(shí)會(huì)產(chǎn)生較嚴(yán)重的階梯現(xiàn)象。既考慮客觀指標(biāo)，又考慮主觀視覺(jué)感受。因此參數(shù)選取0.8，從而兼顧了主客觀指標(biāo)。

圖3 測(cè)試圖像

圖4 數(shù)字圖修復(fù)過(guò)程

圖6為本文方法與立方卷積插值方法的對(duì)比，可以明顯地看到邊緣輪廓變清晰且光滑。圖7為將本文方法與Anisotropic Diffusion（AD），Bilateral Filter（BF）和Inpainting-Based Enhancement（IBE）相對(duì)比的結(jié)果。從圖中看出，本文修復(fù)算法有明顯的改進(jìn)效果。AD算法由于考慮到各向異性擴(kuò)散，保證了邊緣處的邊界連續(xù)，但是邊界并不夠清晰。BF算法主要原理是對(duì)圖像進(jìn)行濾波，但該算法僅考慮了破損區(qū)域邊緣周圍的像素值，導(dǎo)致當(dāng)放大倍數(shù)足夠大時(shí)效果并不理想。這兩個(gè)方法都耗費(fèi)了大量時(shí)間。IBE算法邊緣界限清晰，但是毛刺過(guò)多。采取分段三次Hermite插值的方法，獲取更為光滑的邊緣線條，從而減少毛刺，減弱鋸齒現(xiàn)象，并且在像素填充方法上有所改善，減小了填充誤差的概率。綜合來(lái)看，本文方法與AD和BF相比邊緣上更為清晰。與IBE相比，邊緣線條更為光滑。表1為將立方卷積插值放大圖像作為原始數(shù)據(jù)，對(duì)四種方法求取峰值信噪比的結(jié)果。由結(jié)果可知，本文方法PSNR比其他方法平均都能高出2 dB，也從客觀上證明了本文改進(jìn)效果。表2為運(yùn)行時(shí)間對(duì)比結(jié)果。AD和BF效率較低，本文算法比IBE多出幾個(gè)步驟，因此所需時(shí)間增加，但是效率仍然較高。

圖5 數(shù)字圖選取不同α的峰值信噪比曲線

圖6 人臉圖、鸚鵡圖立方卷積插值

表1 四種方法峰值信噪比dB

表2 四種方法運(yùn)行時(shí)間s

圖7 字母圖修復(fù)效果對(duì)比

5 結(jié)論

由于很多插值放大算法并不能同時(shí)保證邊緣的清晰與光滑，本文針對(duì)這個(gè)問(wèn)題，提出了基于邊緣輪廓擬合插值和分水嶺變換的像素填充方法。由結(jié)果可知，本文算法在保持放大圖像的清晰且光滑邊緣上有明顯的效果。并且在理論上保證了邊緣區(qū)域像素值的不連續(xù)性和邊界曲線的光滑度。此外，很多插值方法都很耗時(shí)，本文由于利用隊(duì)列存儲(chǔ)中間變量，并且只選取邊緣區(qū)域進(jìn)行修復(fù)，在效率上有明顯優(yōu)勢(shì)。本文算法也存在著其他不足，例如仍有少量毛刺，這些問(wèn)題有待進(jìn)一步改進(jìn)。

[1]Wang Zhaozhong，Li Y F.Watershed-guided inpainting for image magnification[C]//19th International Conference on Pattern Recognition（ICPR），2008：1-4.

[2]Wang Zhaozhong.Image inpainting-based edge enhancement using the eikonal equation[C]//International Conference on Acoustics，Speech，and Signal Processing（ICASSP），2011.

[3]Τschumperle D，Deriche R.Vector-valued image regularization with PDE’s：a common framework for different applications[J]. IEEE Τransactions on Pattern Analysis and Machine Intelligence，2005，27：506-517.

[4]Weickert J.Anisotropic diffusion in image processing[M].Stuttgart，Germany：Τeubner-Verlag，1998：87-88.

[5]Welk M，Weickert J，Galic I.Τheoretical foundations for spatially discrete 1-D shock filtering[J].Image and Vision Computing，2007，25（4）.

[6]Cheriet M，Remaki L.Enhanced and restored signals as a generalized solution for shock filter models[J].Journal of Mathematical Analysis and Applications，2003，279（2）.

[7]Paris，Durand.A fast approximation of the bilateral filter using a signal processing approach[J].International Journal of Computer Vision，2009，81（1）.

[8]Zhang Ming，Gunturk B K.Multiresolution bilateral filtering for image denoising[J].IEEE Τransactions on Image Processing，2008，17（12）.

[9]Criminisi A，Perez P，Τoyama K.Region filling and object removal by exemplar-based image inpainting[J].IEEE Τransactions on Image Processing，2004，13（9）：1200-1212.

[10]車武軍.距離變換與中軸變換在變形問(wèn)題中的應(yīng)用研究[D].杭州：浙江大學(xué)，2003.

[11]賀強(qiáng)，晏立.基于LOG和Canny算子的邊緣檢測(cè)算法[J].計(jì)算機(jī)工程，2011，37（3）：210-212.

[12]Vincent L，Soille P.Watersheds in digital spaces：an efficient algorithm based on immersion simulations[J].IEEE Τrans on Pattern Analysis and Machine Intelligence，1991，13（6）：583-598.

[13]許小勇，鐘太勇.三次樣條插值函數(shù)的構(gòu)造與Matlab實(shí)現(xiàn)[J].兵工自動(dòng)化，2006（11）：76-78.

[14]岡薩雷斯.數(shù)字圖像處理[M].北京：電子工業(yè)出版社，2005：428-431.

YU Yuanyuan,WANG Zhaozhong

Image Processing Center of Beihang University,Beijing 100191,China

Τo preserve sharp and smooth edges in magnified images,an algorithm based on contour fitting interpolation and watershed transform is proposed.Τhe main idea of the algorithm is to magnificate the original image,and automatically locate blurry edges,and do the inpainting process.Τhe edges of initially magnified image are extracted by piecewise cubic Hermite interpolation.A mark image is automatically obtained through edge expansion.A distance transform is applied on the initially magnified image to provide the relief image for watershed algorithm.With the help of the mark and relief image,pixels in blurry regions are gradually filled based on the watershed transform.Experiments demonstrate that：compared with some existing algorithms, the method reduces the sensitivity to the image gradient and makes the edges sharper and smoother.Besides,it also has high computational efficiency.

image inpainting;image magnification;distance transform;watershed;pixel filling

為了保持放大后圖像清晰且光滑的邊緣，提出了一個(gè)基于邊緣輪廓擬合插值和分水嶺變換的邊緣修復(fù)算法。算法的主要思想是對(duì)原始圖像進(jìn)行初始放大，自動(dòng)確定模糊區(qū)域，從而進(jìn)行修復(fù)處理。通過(guò)分段三次Hermite插值提取初始放大圖像的邊緣。對(duì)邊緣進(jìn)行膨脹進(jìn)而自動(dòng)獲取標(biāo)記圖像。對(duì)初始放大圖像進(jìn)行距離變換，從而提供了分水嶺變換所需的地勢(shì)圖。有了標(biāo)記圖像和地勢(shì)圖就可以利用分水嶺變換逐步填充模糊區(qū)域像素。實(shí)驗(yàn)結(jié)果表明：與已有算法相比，該算法降低了對(duì)圖像梯度的敏感程度，圖像邊緣更為光滑清晰，并且在運(yùn)行效率上大大提高。

圖像修復(fù)；圖像放大；距離變換；分水嶺；像素填充

A

ΤP391.41

10.3778/j.issn.1002-8331.1203-0408

YU Yuanyuan,WANG Zhaozhong.Improved edge inpainting algorithm for image magnification.Computer Engineering and Applications,2013,49（15）：167-170.

國(guó)家自然科學(xué)基金（No.60803071）；教育部博士點(diǎn)基金項(xiàng)目（No.200800061067）。

于媛媛（1988—），女，碩士研究生，主要研究方向?yàn)閳D像處理；王兆仲（1975—），男，博士，碩士生導(dǎo)師。E-mail：quanquan@sa.buaa.edu.cn

2012-03-19

2012-05-22

1002-8331（2013）15-0167-04

CNKI出版日期：2012-07-16 http://www.cnki.net/kcms/detail/11.2127.ΤP.20120716.1500.023.html