一種新的基于四點插值細(xì)分的圖像修復(fù)算法

韓翠英，段琳琳

HAN Cui-ying1，DUAN Lin--lin2

（1.安陽工學(xué)院，安陽 455000；2.鄭州大學(xué)，鄭州 450001）

0 引言

圖像破損以及數(shù)據(jù)丟失是圖像經(jīng)壓縮、傳輸、解壓縮過程中經(jīng)常遇到的問題，這一問題已經(jīng)引起圖形圖像處理研究人員的廣泛關(guān)注，圖像破損中較為嚴(yán)重的情況是像素群丟失，如圖像經(jīng)編碼后在傳輸中受到干擾而出現(xiàn)解碼后的像素群丟失，或由解碼技術(shù)本身決定的圖像不能完全復(fù)原。針對單像素丟失，常見的解決方法為簡單的鄰點平均法和中指濾波法。對像素群丟失的情況則問題比較復(fù)雜，只能根據(jù)待修復(fù)區(qū)域適當(dāng)范圍內(nèi)的像素所含信息通過建立的修復(fù)規(guī)則進(jìn)行修復(fù)，要想完全修復(fù)是不可能的。

1 基于四點插值細(xì)分模式的修復(fù)算法

1.1 細(xì)分細(xì)則

插值面分裂型細(xì)分方法是指用于規(guī)則四邊形網(wǎng)格時，其細(xì)分規(guī)則是曲線四點插值細(xì)分模式通過張量積形式的自然推廣，對于非正規(guī)四邊形網(wǎng)格采取特殊的細(xì)分規(guī)則。通過一定規(guī)則作用到舊網(wǎng)格上產(chǎn)生新網(wǎng)格，通過網(wǎng)格不斷加細(xì)最終生成光滑曲面。該插值面分裂型細(xì)分方法的細(xì)分規(guī)則是曲線四點插值細(xì)分模式通過張量積形式的自然推廣，對于非正規(guī)四邊形網(wǎng)格采取特殊的細(xì)分規(guī)則。通過一定規(guī)則作用到舊網(wǎng)格上產(chǎn)生新網(wǎng)格，通過網(wǎng)格不斷加細(xì)最終生成光滑曲面。新網(wǎng)格的生成規(guī)則包括兩部分，即幾何點的產(chǎn)生和拓?fù)浣Y(jié)構(gòu)的建立。新的幾何點包括新邊點、新頂點、新面點，新邊點是對應(yīng)邊的兩端鄰近四個頂點的加權(quán)平均；新頂點等于舊頂點；新面點是對應(yīng)面上所有頂點及周圍的一些點的加權(quán)平均。其拓?fù)浣Y(jié)構(gòu)依如下規(guī)則建立，連接每一新面點與其周圍的新邊點；連接每一新頂點與其周圍的新邊點。

1.2 對破損圖像區(qū)域的預(yù)處理

設(shè)二元函數(shù)z=f（x,y），定義區(qū)域為D，值域為G。我們把圖像中的像素點位置集合視為空間曲面的定義區(qū)域，即二元函數(shù)z=f（x,y）中的D；把圖像中像素點處的灰度值與空間曲面的函數(shù)值相對應(yīng)，即二元函數(shù)z=f（x,y）中的G。由于圖像所反映的是現(xiàn)實的世界，因此除邊緣（輪廓）部分外，圖像中像素的灰度值一般可看作是連續(xù)變化的，這樣就可以采用曲面四點插值細(xì)分模式的細(xì)分規(guī)則。進(jìn)行插值，恢復(fù)其灰度值。這樣做的優(yōu)點在于能夠合理而有效地利用破損像素塊周圍像素灰度特點構(gòu)造未知像素的灰度值，且由四點插值細(xì)分理論，二元函數(shù)z=f（x,y）在該部分的灰度函數(shù)具有一階連續(xù)性。但如果破損像素塊包含邊緣像素時，利用曲面細(xì)分模式進(jìn)行插值修復(fù)，導(dǎo)致修復(fù)后圖像邊緣被過度光滑，修復(fù)效果不理想。因此，在進(jìn)行圖像修復(fù)前，需要對圖像進(jìn)行預(yù)處理，判斷破損區(qū)域是否存在邊緣像素。

利用求破損圖像周圍的各鄰點（所謂鄰點是指距破損區(qū)域邊緣最近的非丟失的像素點）梯度的方法，判斷破損圖像周圍像素的灰度變化情況，即檢測出在破損圖像區(qū)域中可能包含的邊緣像素點。如果存在邊緣點，找出其邊緣的走向，利用四點插值細(xì)分規(guī)則的邊點計算方法對邊緣像素進(jìn)行修復(fù)，然后再用曲面細(xì)分規(guī)則對其它區(qū)域進(jìn)行修復(fù)。若破損圖像區(qū)域中不包含邊緣點，則直接利用曲面細(xì)分規(guī)則對破損區(qū)域進(jìn)行修復(fù)。

圖1 假設(shè)破損圖像區(qū)域

假設(shè)破損圖像區(qū)域如圖1所示。圖中陰影部分為破損區(qū)域，為了便于處理，將破損區(qū)域外推成矩形區(qū)域，并視為待修復(fù)的破損區(qū)域，該區(qū)域所包含的像素為 。設(shè)破損區(qū)域的某一鄰點A的坐標(biāo)為（i,j），破損圖像區(qū)域的左上角的坐標(biāo)為（iu,jl），右下角的坐標(biāo)為（id,jr）如圖1所示。

當(dāng)按（1）、（2）式給出的i，j值，可以取遍破損圖像區(qū)域的所有鄰點。對像素點A（i,j），求其梯度幅值和其梯度幅角為：

對于所有的破損區(qū)域的所有鄰點，由公式（3）、（4）得到所有破損圖像區(qū)域的鄰點的梯度幅值和梯度方向的集合{G（i,j}和{θ（i,j}。為避免修復(fù)的復(fù)雜性和減少計算量，對梯度幅值設(shè)置一個閩值k，然后，將G（i,j）和闡值k進(jìn)行比較。如果梯度幅值G（i,j）大于k，則該像素點（i,j）被認(rèn)為是階躍點（或稱為邊緣點）；反之則認(rèn)為為光滑點。如果破損圖像區(qū)域位于圖像的邊緣處，通過這樣的比較，即可留下破損圖像區(qū)域鄰點的邊緣像素點。對所有的這樣的像素點進(jìn)行線插補后，再對剩余區(qū)域按曲面插值算法進(jìn)行修復(fù)；如果破損區(qū)域位于圖像的光滑區(qū)域，則跳過線插值修復(fù)，而直接進(jìn)行曲面插值修復(fù)。

1.3 基于四點插值細(xì)分模式的修復(fù)算法

為了說明這種算法，我們假設(shè)有一邊緣破損區(qū)域的圖片，如圖2所示。其中“。”表示待修復(fù)的像素，“。”為破損圖像區(qū)域外圍的己知像素，“。”為面點和邊點，并以已知A的坐標(biāo)，設(shè)圖像的灰度值用f（x，y）表示，x，y為像素的坐標(biāo)；初始層k=0。

圖2 假設(shè)一邊緣破損區(qū)域圖

具體的曲面四點插值細(xì)分模式用于破損圖像修復(fù)的算法如下：

1）根據(jù)破損區(qū)域的像素個數(shù)和破損區(qū)域的外鄰點A求待修復(fù)區(qū)域中的中間像素點（面點）的位置，設(shè)求得面點S的坐標(biāo)為（i,j），距A的距離（像素點個數(shù)）為p，q，則可用面點S的坐標(biāo)和p,q將A點表示為A（i-p,j-q）。

2）以p,q為步長，以S點為基準(zhǔn)，在破損區(qū)域周圍取如下16個已知像素點（取點是按曲面四點細(xì)分規(guī)則進(jìn)行的），即：f（i-3p，j-3q），f（i+3p，j-3q），f（i+3p，j+3q），f（i-3p，j+3q），f（i-p，j-3q），f（i-p，j+3q），f（i+p，j-3q），f（i+p，j+3q），f（j-3P，j-q），f（i-3P，j+q），f（i+3P，j-q），f（i+3P，j+q），f（i-p，j-q），f（j-p，j+q），f（i+p，j-q），f（i+p，j+q）。然后計算面點S的灰度值。

3）以新計算的面點S為已知點，計算面點。該步需要計算出四個新邊點，如圖4所示。具體算法這里以B點為例進(jìn)行說明。為計算邊點B的灰度，首先計算出B點在該行破損區(qū)的位置，該點的坐標(biāo)為（i，j+q/2），然后，按照邊點細(xì)分規(guī)則取如下四點f（i，j-2，），f（i，j-q），f（i，j）（由第二步計算出的面點），f（i，j+q）。再計算出邊點B的灰度值f（i，j+q/2）。同理可計算出其它三個邊點。

4）使k=k+1，利用第二步和第三步計算的面點、邊點為己知點，計算k+1的面點和邊點。為計算第k+1層的面點、邊點，將破損區(qū)域劃分22k個區(qū)域，并根據(jù)不同的區(qū)域調(diào)整A點的位置，并使p=p/2，q=q/2。

5）返回第一步，計算22k個區(qū)域的面點和邊點，直到p，q的值小于1為止。

1.4 算法仿真結(jié)果

為驗證算法的有效性，本文對lena圖進(jìn)行了人為的損壞，破損區(qū)域大小均為7×7，并包含了平滑區(qū)域和含有邊緣區(qū)域，如圖3所示。由圖中可以看出，修復(fù)后的圖像和原始圖像的效果非常接近，因此驗證了本文所提出的四點插值細(xì)分模式用于破損圖像的修復(fù)算法是有效的，恢復(fù)后的圖像的質(zhì)量也是優(yōu)良的。

圖3 對本文算法的驗證圖

2 結(jié)論

本文提出一種新的基于四點插值細(xì)分的圖像修復(fù)算法，該方法來源于計算機輔助幾何設(shè)計研究領(lǐng)域中三維空間自由曲線曲面造型技術(shù)。使用該方法不僅可以修復(fù)不規(guī)則像素群，而且修復(fù)邊緣具有很好的平滑過渡性，但如果圖像破損處的灰度有階躍或近似階躍變化時，我們用梯度方法對破損圖像周圍的邊緣像素點進(jìn)行檢測，對破損區(qū)域中包含的邊緣像素點按照四點插值細(xì)分模式中的邊點計算規(guī)則進(jìn)行單獨處理，在破損圖像修復(fù)中得到了較好的結(jié)果。

[1]檀結(jié)慶,汪忠慶.一種新的基于鄰近像素點的圖像修復(fù)算法[J].合肥工業(yè)大學(xué)學(xué)報（自然科學(xué)版）,2006,29（9）：1072-1076.

[2]周春霞,吳錫生.基于方差和邊緣插值的鄰近點圖像修復(fù)算法[J].計算機工程與應(yīng)用,2008,44（14）：184-186.

[3]張智豐,張亞榮.細(xì)分曲線參數(shù)化與累加弦長參數(shù)化的數(shù)值比較[J].湘潭師范學(xué)院學(xué)報（自然科學(xué)版）,2009,31（4）.