錢 鷹，王礦生，黃 穎

（重慶郵電大學(xué) 圖形圖像與多媒體實(shí)驗(yàn)室，重慶400065）

0 引 言

圖像重構(gòu)技術(shù)一直是數(shù)字圖像處理的一個(gè)重要分支，重構(gòu)技術(shù)可分成三大類［1］：尺度－空間技術(shù)、時(shí)間－尺度技術(shù)、時(shí)間－頻率技術(shù)。圖像重構(gòu)的常見(jiàn)方法有基于高斯金字塔模型、拉普拉斯金字塔模型和小波變換的多尺度變換與重構(gòu)模型等。

目前，有關(guān)圖像重構(gòu)的算法模型有很多種：在文獻(xiàn)［2］中，楊慧等利用多尺度Gabor小波變換對(duì)人臉圖像進(jìn)行重構(gòu)，在不同尺度上提取人臉特征；在文獻(xiàn) ［3］中，蒯偉等介紹了小波函數(shù)及基于小波變換的圖像分解與重構(gòu)，系統(tǒng)描述了小波變換的優(yōu)點(diǎn)。在文獻(xiàn) ［4］中，周全等利用高斯金字塔模型重構(gòu)模型對(duì)將遙感圖像分解到不同尺度空間，提取遙感云圖的不同尺度特征。在文獻(xiàn) ［5］中，練秋生等利用圖像稀疏的表示的先驗(yàn)知識(shí)，利用負(fù)數(shù)小波進(jìn)行圖像重構(gòu)，且優(yōu)化了算法性能。在文獻(xiàn) ［6］中，易文娟等描述了圖像的另外一種重構(gòu)算法—Contourlet變換的原理和實(shí)際應(yīng)用。

本文利用代數(shù)多重網(wǎng)格算法中的粗網(wǎng)格特性建立一種新穎的圖像重構(gòu)算法，利用代數(shù)多重網(wǎng)格算法提取圖像粗網(wǎng)格，圖像粗網(wǎng)格點(diǎn)的密集程度表征圖像的變化程度，分布均勻說(shuō)明圖像變化不明顯，否則變化明顯，且產(chǎn)生的多網(wǎng)格序列在尺度上和原圖像一致。并與小波算法作了比較，實(shí)驗(yàn)結(jié)果表明代數(shù)多重網(wǎng)格算法具有較好的效果。本文結(jié)構(gòu)安排如下：第一部分是代數(shù)多重網(wǎng)格算法概要描述和代數(shù)多重網(wǎng)格進(jìn)行圖像多分辨率分析的具體算法；第二部分是部分實(shí)驗(yàn)實(shí)例，對(duì)實(shí)驗(yàn)結(jié)果做了簡(jiǎn)要分析，然后與小波算法作了比較，且在圖像融合中應(yīng)用了此重構(gòu)算法；最后對(duì)本文簡(jiǎn)要地作了一下總結(jié)。

1 代數(shù)多重網(wǎng)格算法與圖像重構(gòu)

代數(shù)多重網(wǎng)格方法是求解大型線性方程組和偏微分方程的一種有效方法，僅根據(jù)系數(shù)矩陣直接求解，在不同類型的問(wèn)題求解上表現(xiàn)出很好的穩(wěn)健性，被應(yīng)用在各種實(shí)際計(jì)算中［7］。代數(shù)多重網(wǎng)格不依賴于求解問(wèn)題的幾何特性，僅利用方程組本身的信息來(lái)求解代數(shù)方程組，在松弛步驟上采取自適應(yīng)粗化，允許在無(wú)結(jié)構(gòu)的網(wǎng)格上進(jìn)行求解，能夠在很多問(wèn)題得到應(yīng)用和推廣，比如圖像分析，磁場(chǎng)模擬等。代數(shù)多重網(wǎng)格算法思想于1982年由A.Brandt，S.McCormick和J.Ruge三人提出［8］，直到1986年代數(shù)多重網(wǎng)格算法的理論背景和代數(shù)理論才由A.Brandt系統(tǒng)給出［9］，而后Ruge和Stuben詳細(xì)地描述代數(shù)多重網(wǎng)格算法的基本思路和經(jīng)典理論［8］。

一個(gè)代數(shù)多重網(wǎng)格算法分為兩部分：一是預(yù)備部分（setup），這部分是從系數(shù)矩陣構(gòu)造出五個(gè)求解分量：網(wǎng)格點(diǎn)集Ωm，插值算子，限制算子，粗網(wǎng)格算子Am＋1，光滑算子Gm；另一部分是標(biāo)準(zhǔn)的多重網(wǎng)格循環(huán)過(guò)程：先在細(xì)網(wǎng)格上做松弛迭代，然后將誤差投影到粗一層網(wǎng)格上去，在粗網(wǎng)格上又做松弛迭代，依次類推，直到最粗的一層。在最粗一層用直接法求解，然后，用插值算子將所求得的誤差返回到細(xì)網(wǎng)格上去，用以修正原有結(jié)果，直到最細(xì)的一層。

代數(shù)多重網(wǎng)格法的求解對(duì)象是滿足一定條件的線性問(wèn)題。首先，定義最細(xì)的網(wǎng)格為Ω0，構(gòu)造一個(gè)網(wǎng)格序列使得ΩnΩn－1… Ωk… Ω0。

代數(shù)多重網(wǎng)格法的較粗網(wǎng)格Ωm＋1＝Cm是它的較細(xì)網(wǎng)格Ωm的一個(gè)真子集，記Fm＝Ωm－Cm。一般情況下，Cm和Fm的選取規(guī)則為：

（1）對(duì)任意i∈Fm，j∈Smi（表示網(wǎng)格中點(diǎn)i強(qiáng)聯(lián)結(jié)的點(diǎn)），那么j∈Cmi或者j與Cmi的一個(gè)點(diǎn)強(qiáng)聯(lián)結(jié)；

（2）Cm是非強(qiáng)聯(lián)結(jié)點(diǎn)構(gòu)成的最大點(diǎn)集合。

目前Ron Kimmel和Irad Yavneh運(yùn)用代數(shù)多重網(wǎng)格算法求解計(jì)算機(jī)視覺(jué)中具有奇異系數(shù)的橢圓方程［11］；史培林等利用代數(shù)多重網(wǎng)格算法很好的求解CT投影數(shù)據(jù)重構(gòu)圖像問(wèn)題［12］；Leo Grady利用代數(shù)多重網(wǎng)格算法求解圖像分析中的泊松問(wèn)題［13］；代數(shù)多重網(wǎng)格法在圖像運(yùn)用中的基本上是代數(shù)多重網(wǎng)格算法能夠很好的求解線性方程組的特性。

代數(shù)多重網(wǎng)格求解過(guò)程中，粗網(wǎng)格的變化是不規(guī)則的，粗網(wǎng)格矩陣大小在改變，點(diǎn)數(shù)也在變化，沒(méi)有規(guī)律可循，因此將粗網(wǎng)格運(yùn)用到圖像重構(gòu)中的最大難題是粗網(wǎng)格圖像還原到原始圖像大小，而解決這個(gè)問(wèn)題的前提是將粗網(wǎng)格中的點(diǎn)對(duì)應(yīng)到原始圖像中的像素點(diǎn)。

算法描述：在代數(shù)多重網(wǎng)格圖像粗網(wǎng)格提取中，采用python語(yǔ)言的pyamg包來(lái)實(shí)現(xiàn)代數(shù)多重網(wǎng)格算法，可以得到粗化后的第1、2…N層數(shù)據(jù)，對(duì)應(yīng)于原始圖像中部分像素點(diǎn)，可采用某種插值函數(shù)插值，如最近鄰法，線性插值法等，可以得到重構(gòu)圖像。

根據(jù)以上的討論，本文設(shè)計(jì)的代數(shù)多重網(wǎng)格圖像重構(gòu)算法為：

（1）根據(jù)代數(shù)多重網(wǎng)格得到網(wǎng)格序列：對(duì)原始圖像I進(jìn)行代數(shù)多重網(wǎng)格粗化得到N層粗化網(wǎng)格Ω1，Ω2…ΩN；

（2）擴(kuò)充網(wǎng)格：將N層網(wǎng)格Ω1，Ω2…ΩN還原成原始圖像大小的Ω′1，Ω′2…Ω′N，此時(shí)需要考慮粗網(wǎng)格序列與上一層粗網(wǎng)格位置索引對(duì)應(yīng)關(guān)系，網(wǎng)格中的元素被選中為下一層粗網(wǎng)格的元素值為1，否則為0；

（3）網(wǎng)格與圖像坐標(biāo)對(duì)應(yīng)：粗網(wǎng)格Ω1，Ω2…Ω′N.因?yàn)槭菆D像大小，所以網(wǎng)格與原始圖像I很容易找到對(duì)應(yīng)位置關(guān)系，采取如下策略：

1）如果網(wǎng)格中的數(shù)據(jù)是1，則令對(duì)應(yīng)位置的像素為圖像相應(yīng)位置的灰度值；

2）如果網(wǎng)格中的數(shù)據(jù)是0，則令對(duì)應(yīng)位置的像素等于0，這樣就產(chǎn)生了一系列圖像I1，I2…IN。

（4）插值：在上述I1，I2…IN進(jìn)行插值，可得到插值圖像I′1，I′2…I′N。

2 實(shí) 驗(yàn)

2.1 實(shí)驗(yàn)條件

圖1為本文采用的實(shí)驗(yàn)圖片，灰度級(jí)別均為256，其中圖1 （a）， （e）， （f）為多聚焦圖像，在此感謝文獻(xiàn) ［15］作者高雪妮女士提供的寶貴的實(shí)驗(yàn)圖片，而圖1（b），（c），（d）為 《數(shù)字圖像處理》中的示例圖片。圖1（a）中，大小為512＊512，是一幅包含一部分聚焦，一部分失焦的圖像，所以圖像中左前方的鐘表是模糊不清晰，右后方是對(duì)焦較好，比較清晰。圖1（b），（c），（d）中大小為512＊512。圖1（e），（f）為兩幅多聚焦圖像，大小為480＊640，其中圖1（e）中前景鐘表等部分清晰，而后面書架以及桌子部分模糊；而圖1（f）恰恰相反。

圖1 本文所用的實(shí)驗(yàn)圖片

2.2 圖像重構(gòu)實(shí)驗(yàn)

2.2.1 圖像粗網(wǎng)格序列的提取

通過(guò)運(yùn)用算法步驟1，可以得到一系列粗網(wǎng)格序列，如圖2所示。圖2中 （a）、（b）、（c）依次為圖1中 （a）圖像粗化后的第一層、第二層、第三層圖像。從圖中可以直觀的得出下列結(jié)論：粗網(wǎng)格數(shù)據(jù)能夠較好的保留原始圖像的特征信息，在圖像的顯著區(qū)域 （灰度值變化劇烈的區(qū)域）網(wǎng)格點(diǎn)較密集，在非顯著變化區(qū)域，網(wǎng)格點(diǎn)的分布稀疏均勻。從圖2（b）較好的保留了兩個(gè)鐘表的邊緣和右邊鐘表表盤的指針和數(shù)字，在圖2（b）中可以發(fā)現(xiàn)左邊鐘表輪廓幾乎全部消失，但右邊鐘表邊緣部分和表盤數(shù)字細(xì)節(jié)信息仍保留，在圖2（c）中隱約可見(jiàn)到右邊表盤的數(shù)字輪廓及表針。

在此，為了定量表達(dá)粗化網(wǎng)格能夠較多的保留圖像的有效信息，本文做了粗化網(wǎng)格熵值與源圖像熵值百分比比較。在灰度圖像中，圖像的灰度直方圖可以理解成概率密度函數(shù)，灰度值為i（0≤i≤n）的像素個(gè)數(shù)在整幅圖像中所占的百分比可以表示成Pi，那么圖像的熵值公式為

根據(jù)式 （1），熵值結(jié)果如表1所示。圖1（a）原始圖片的熵值為6.9784，每層粗化后網(wǎng)格中包含像素的熵值所占原圖像熵值比例依次為：36.73%，9.44%，3.17%，均大于每層點(diǎn)數(shù)的比例：29.12%，5.96%，1.72%，這個(gè)現(xiàn)象說(shuō)明代數(shù)多重網(wǎng)格算法粗網(wǎng)格提取的每層圖像粗網(wǎng)格都能夠保留圖像的熵值較大的像素點(diǎn)。

圖2 提取的三層粗網(wǎng)格

表1 粗化網(wǎng)格中定量評(píng)價(jià)信息量

2.2.2 由粗網(wǎng)格序列進(jìn)行圖像重構(gòu)

在粗化數(shù)據(jù)上，進(jìn)行算法步驟3，4的操作，將圖1中三層粗網(wǎng)格進(jìn)行插值，得到重構(gòu)圖像如圖3（a）、（b）、（c）所示，與原圖像比較，主觀的認(rèn)為前兩層插值圖像的質(zhì)量較好，第三層插值的圖像質(zhì)量降低，這是由于用于圖像插值的數(shù)據(jù)量急劇減少的原因。但是存在這樣一個(gè)現(xiàn)象：重構(gòu)的圖像都能較好的保證了圖像的細(xì)節(jié)部分，整體效果很好，這也證實(shí)了表1中的粗網(wǎng)格數(shù)據(jù)能夠保留圖像有效信息的結(jié)論。

圖3 粗網(wǎng)格序列插值結(jié)果

2.3 與小波重構(gòu)算法對(duì)比實(shí)驗(yàn)

本文對(duì)比了四幅圖片的結(jié)果，圖片依次為圖1中的（a），（b）， （c）， （d），分別對(duì)其進(jìn)行小波重構(gòu)與代數(shù)多重網(wǎng)格算法重構(gòu)。采取的評(píng)價(jià)量度為均方誤差 （Mean Square Error），均方誤差越小，表明重構(gòu)圖像與源圖像越接近，重構(gòu)效果就好，反之則差，故可以用均方誤差來(lái)衡量圖像重構(gòu)算法的優(yōu)劣。設(shè)兩幅大小為M＊N圖像I1和I2，定義均方誤差為

根據(jù)式 （2），得到如表2中均方誤差評(píng)價(jià)參數(shù)，從數(shù)據(jù)上來(lái)看，代數(shù)多重網(wǎng)格重構(gòu)算法與小波重構(gòu)算法的MSE是在同一個(gè)數(shù)量級(jí)上；而且它們都呈現(xiàn)出相同的變化趨勢(shì)：變化較一致，沒(méi)有出現(xiàn)突異。由表2中每幅圖像的MSE值可以看出在每一層的數(shù)據(jù)集合上，代數(shù)多重網(wǎng)格算法能夠達(dá)到較好的效果，且比小波重構(gòu)算法的MSE值小，說(shuō)明代數(shù)多重網(wǎng)格算法圖像重構(gòu)質(zhì)量較好。

2.4 應(yīng)用實(shí)例

利用代數(shù)多重網(wǎng)格進(jìn)行重建，結(jié)合區(qū)域檢測(cè)方法進(jìn)行多聚焦圖像融合，來(lái)進(jìn)一步驗(yàn)證圖像重構(gòu)的有效性。實(shí)驗(yàn)圖片為圖1中 （e）， （f）兩幅多聚焦圖像。圖4（a）結(jié)合了圖1（a）和圖1（b）的邊緣得到的邊緣集合，其中邊緣由Canny算子檢測(cè)出來(lái)。圖4（b）是通過(guò)參考文獻(xiàn) ［14］中列出的邊緣主動(dòng)生長(zhǎng)方法將進(jìn)行邊緣連接，將圖4（a）中出現(xiàn)的一些斷點(diǎn)連接起來(lái)，以便得到封閉的區(qū)域。圖4（c）是將圖4（b）中面積較小的區(qū)域消除掉后得到的輪廓圖像，這樣可以將圖像分為若干個(gè)閉合區(qū)域，對(duì)每個(gè)區(qū)域進(jìn)行代數(shù)多重網(wǎng)格算法重構(gòu)，取第一層重構(gòu)結(jié)果圖像與原圖做均方誤差比較，選擇均方誤差較大的源圖像區(qū)域添加到結(jié)果融合中，邊緣處的像素點(diǎn)用兩幅圖像的均值替代，得到圖4（d），從主觀上看融合效果較好，每個(gè)區(qū)域內(nèi)都選擇了正確的清晰塊作為融合結(jié)果，而在邊緣部分也沒(méi)有跳變點(diǎn)。

表2 圖像的重建效果MSE 比較

根據(jù)平均誤差 （D）、峰值信噪比 （PSNR）、相關(guān)系數(shù)（REL）、空間頻率 （SF）四種方法進(jìn)行評(píng)價(jià)［15］，得到的各項(xiàng)參數(shù)為表3所示，其中小波融合采取的4層Haar小波。D、PSNE、REL都反映了融合結(jié)果和標(biāo)準(zhǔn)圖像的差異程度。D越小，PSNR越大，REL越大融合效果越好，SF越大，說(shuō)明圖像保留的高頻信息越多。從表3的數(shù)值來(lái)看，本文融合結(jié)果效果較小波圖像融合效果好。

從該實(shí)例可以看出，利用代數(shù)多重網(wǎng)格算法進(jìn)行重構(gòu)，可以較好的反應(yīng)原始圖像中的細(xì)節(jié)信息。當(dāng)圖像越清晰，細(xì)節(jié)信息越豐富，代數(shù)多重網(wǎng)格能夠?qū)⒏嗟募?xì)節(jié)信息保持到下一級(jí)粗網(wǎng)格中；而圖像越模糊，細(xì)節(jié)信息越稀少，因此代數(shù)多重網(wǎng)格重構(gòu)結(jié)果放大了圖像中的細(xì)節(jié)信息部分，也能說(shuō)明代數(shù)多重網(wǎng)格圖像重構(gòu)算法能較好的保留原始圖像的有用信息。

表3 融合結(jié)果評(píng)價(jià)參數(shù)比較

圖4 通過(guò)應(yīng)用實(shí)例進(jìn)一步驗(yàn)證AMG圖像重構(gòu)算法的有效性

3 結(jié)束語(yǔ)

本文研究了代數(shù)多重網(wǎng)格算法中粗網(wǎng)格算子的提取過(guò)程，并將其應(yīng)用到在圖像的重構(gòu)中，提出了一種基于代數(shù)多重網(wǎng)格的圖像重構(gòu)算法。本文算法提取的圖像的粗網(wǎng)格的密集程度能夠表征圖像的變化的劇烈程度，網(wǎng)格保留了圖像的有效信息部分像素點(diǎn)。實(shí)驗(yàn)結(jié)果表明本文算法不僅能夠取得較好的重構(gòu)效果，且與傳統(tǒng)的小波圖像算法相比具有一定的優(yōu)勢(shì)，并在圖像融合中應(yīng)用了此圖像重構(gòu)算法，與小波融合相比，效果較好。代數(shù)多重網(wǎng)格算法的其它特性在圖像的其它領(lǐng)域比如圖像壓縮，圖像分割，圖像融合等的應(yīng)用將是下一步的研究方向。

［1］XI Zhihong，ZHANG Yue，SHAO Xin.Image super－resolution reconstruction algorithm based on wavelet and PDE iterpolation ［J］.Journal of Detection ＆ Control，2011，33 （5）：72－76 （in Chinese）.［席志紅，張?jiān)剑坌?小波結(jié)合偏微分插值的圖像超分辨率重構(gòu)算法 ［J］.探測(cè)與控制學(xué)報(bào)，2011，33 （5）：72－76.］

［2］YANG Hui，HU Jinyan，JIANG Qiufeng.Optimization of face recognition algorithm based on multi－scal Gabor transformation［J］.Electronic Measurement Technology，2011，34 （10）：41－44（in Chinese）. ［楊慧，胡金演，蔣秋峰.基于多尺度Gabor變換的人臉識(shí)別算法優(yōu)化 ［J］.電子測(cè)量技術(shù)，2011，34 （10）：41－44.］

［3］KUAI Wei，DUAN Jiajia.Based on wavelet transform image reconstruction algorithm ［J］.Electronic Test，2011 （9）：1－4（in Chinese）.［蒯偉，段佳佳.基于小波變換的圖像重構(gòu)算法研究 ［J］.電子測(cè)試，2011 （9）：1－4.］

［4］ZHOU Quan，ZHANG Rong，YIN Dong.The extracting of multiscale features of remote sensing cloud images based on gaussian pyramid ［J］.Remote Sensing Technology and Application，2010，25 （5）：604－608 （in Chinese）. ［周全，張榮，尹東.基于高斯金字塔的遙感云圖多尺度特征提取 ［J］.遙感技術(shù)與應(yīng)用，2010，25 （5）：604－608.］

［5］LIAN Qiusheng，GAO Yanyan，CHEN Shuzhen.Compressed sensing image reconstruction based on two－step iterative shrinkage and complex wavelet ［J］.Chinese Journal of Scientific Instrument，2009，30 （7）：1426－1431 （in Chinese）. ［練秋生，高彥彥，陳書貞.基于兩步迭代收縮法和負(fù)數(shù)小波的壓縮傳感圖像重構(gòu)［J］.儀器儀表學(xué)報(bào)，2009，30 （7）：1426－1431.］

［6］YI Wenjuan，YU Mei，JIANG Gangyi.Contourlet efficient directional and multiresolution analytic tool ［J］.Research on Application of Computer，2006 （9）：18－22 （in Chinese）. ［易文娟，郁梅，蔣剛毅.Contourlet一種有效的方向多尺度變換分析方法 ［J］.計(jì)算機(jī)應(yīng)用研究，2006 （9）：18－22.］

［7］GUO Feixiao，YANG Li，LIU Rong，et al.Algebraic multigrid solution of large－scale sparse normal equation ［J］.Journal of Geomatics Science and Technology，2012，29 （1）：5－8 （in Chinese）.［郭飛宵，楊力，劉榮，等.大型稀疏法方程組的代數(shù)多重網(wǎng)格解法 ［J］.測(cè)繪科學(xué)技術(shù)學(xué)報(bào)，2012，29 （1）：5－8.］

［8］Brandt A，McCormick S F，Ruge J.Algebraic multigrid（AMG）for sparse matrix equations ［M］.Evans D J ed.Sparsity and its Applications，Cambridge：Cambridge University Press，1984：257－284.

［9］Brandt A.Algebraic multigrid theory：The symmetric case［J］.App Math Comp，1986，19 （1－4）：23－56.

［10］Ruge J，Stuben K.Algebraic（AMG）［M］.S.F.McCormicked.Frontiers in Appl Math，Philadelphia：SIAM，1987：73－130.

［11］Ron Kimmel，Irad Yavneh.An algebraic multigrid approach for image analysis SIAM ［J］.J Sci Comput，2006，24 （4）：1218－1231.

［12］SHI Peilin.Algebraic multigrid method and its application in image reconstruction ［D］.Beijing：Chinese Academy of Sciences，2003 （in Chinese）.［史培林.代數(shù)多重網(wǎng)格法及其在圖像重構(gòu)中的應(yīng)用 ［D］.北京：中國(guó)科學(xué)院，2003.］

［13］Leo Grady.A lattice－preserving multigrid method for sovling the inhomogeneous posisson equeation used in image analysis［G］.LNCS 5303：ECCV，Part II，2008：252－264.

［14］FENG Ziliang，WANG Cuiqin，SHI Guanmin.Autonomous edge growing algorithm for edge linking ［J］.Application Research of Computers，2009，26 （10）：3954－3956 （in Chinese）. ［馮子亮，王翠芹，施關(guān)民.一種基于主動(dòng)生長(zhǎng)的邊緣連接算法［J］.計(jì)算機(jī)應(yīng)用研究，2009，26 （10）：3954－3956.］

［15］GAO Xueni，YU Zhenming，ZHANG Jun，et al.Multi－focus image fusion based on multi level and iterative method ［J］.Acta Electronica，2011，39 （3）：690－694 （in Chinese）.［高雪妮，于振明，張軍，等.基于多級(jí)分塊迭代法的不同聚焦圖像融合 ［J］.電子學(xué)報(bào)，2011，39 （3）：690－694.］