一種改進的放大圖像邊緣修復算法

于媛媛，王兆仲

北京航空航天大學 圖像處理中心，北京 100191

一種改進的放大圖像邊緣修復算法

于媛媛，王兆仲

北京航空航天大學 圖像處理中心，北京 100191

1 引言

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

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

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

2 算法流程

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

圖1 圖像邊緣修復流程圖

3 算法原理

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

3.1 地勢圖的確定

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

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

不同的距離定義，對應不同的距離變換方法。歐氏距離變換的主要優點是運行速度比較快。在本文算法中，距離變換主要用來衡量圖像中任一像素到圖像邊界的距離：圖像邊緣處像素地勢最高，離邊緣處越遠的像素地勢越低。此處的圖像邊緣通過Canny邊緣檢測算子求取。結合到數據結構中隊列的知識，同一地勢的像素存儲到一個隊列中，從而進行后面的填充處理。

3.2 標記圖像的求取

求出地勢圖后，就要求取標記圖像。最初的標記圖像是在Canny邊緣檢測算子的基礎上確定的，繼而對邊緣進行膨脹操作，獲得預定的標記值。針對Canny算子具有本身的針對性和局限性，例如抑制噪聲和檢測低強度邊緣能力不足[11]。本文算法在提取邊緣的這一環節采取邊緣輪廓擬合插值。為了避免高次插值可能帶來的大幅波動現象，實際上通常采用分段低次插值來提高擬合程度，選取分段三次Hermite插值。

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

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

圖2（b）分段三次Hermite插值結果對比圖

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

插值處理后，在求出的邊緣輪廓基礎上進行膨脹處理，得到前述的標記圖像。本文中規定未知像素的標記值為0，邊界區域像素的標記值為255，已知像素標記值則依據距離變換的結果標記為1～254。標記圖像的確定為后期像素填充起到了關鍵的引導作用。

3.3 像素的填充

上述兩節分別求出了地勢圖和標記圖像。有了這兩個數據，接下來就可以利用分水嶺變換進行具體的填充處理。

分水嶺的概念可以通過浸沒模擬[14]來得到很好的說明。這個概念是以對圖像進行三維可視化處理為基礎的。傳統的分水嶺變換與圖像的梯度有密切聯系。本文利用了距離變換的中間結果克服了對圖像梯度敏感的缺點。

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

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

上面的填充過程體現了填充優先權：距離圖像邊界越遠的像素點，具有越高的填充優先權。為了防止求得的圖像邊緣過于尖銳，可令：

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

4 實驗分析

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

圖3 測試圖像

圖4 數字圖修復過程

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

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

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

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

表2 四種方法運行時間s

圖7 字母圖修復效果對比

5 結論

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

[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]車武軍.距離變換與中軸變換在變形問題中的應用研究[D].杭州：浙江大學，2003.

[11]賀強，晏立.基于LOG和Canny算子的邊緣檢測算法[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]許小勇，鐘太勇.三次樣條插值函數的構造與Matlab實現[J].兵工自動化，2006（11）：76-78.

[14]岡薩雷斯.數字圖像處理[M].北京：電子工業出版社，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

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

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

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.

國家自然科學基金（No.60803071）；教育部博士點基金項目（No.200800061067）。

于媛媛（1988—），女，碩士研究生，主要研究方向為圖像處理；王兆仲（1975—），男，博士，碩士生導師。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