一種新的基于四點(diǎn)插值細(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ù)原。針對單像素丟失，常見的解決方法為簡單的鄰點(diǎn)平均法和中指濾波法。對像素群丟失的情況則問題比較復(fù)雜，只能根據(jù)待修復(fù)區(qū)域適當(dāng)范圍內(nèi)的像素所含信息通過建立的修復(fù)規(guī)則進(jìn)行修復(fù)，要想完全修復(fù)是不可能的。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2）以p,q為步長，以S點(diǎn)為基準(zhǔn)，在破損區(qū)域周圍取如下16個(gè)已知像素點(diǎn)（取點(diǎn)是按曲面四點(diǎn)細(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）。然后計(jì)算面點(diǎn)S的灰度值。

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

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

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

1.4 算法仿真結(jié)果

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

圖3 對本文算法的驗(yàn)證圖

2 結(jié)論

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

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

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

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