用于圖像重構的代數多重網格算法

錢 鷹，王礦生，黃 穎

（重慶郵電大學 圖形圖像與多媒體實驗室，重慶400065）

0 引 言

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

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

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

1 代數多重網格算法與圖像重構

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

一個代數多重網格算法分為兩部分：一是預備部分（setup），這部分是從系數矩陣構造出五個求解分量：網格點集Ωm，插值算子，限制算子，粗網格算子Am＋1，光滑算子Gm；另一部分是標準的多重網格循環過程：先在細網格上做松弛迭代，然后將誤差投影到粗一層網格上去，在粗網格上又做松弛迭代，依次類推，直到最粗的一層。在最粗一層用直接法求解，然后，用插值算子將所求得的誤差返回到細網格上去，用以修正原有結果，直到最細的一層。

代數多重網格法的求解對象是滿足一定條件的線性問題。首先，定義最細的網格為Ω0，構造一個網格序列使得ΩnΩn－1… Ωk… Ω0。

代數多重網格法的較粗網格Ωm＋1＝Cm是它的較細網格Ωm的一個真子集，記Fm＝Ωm－Cm。一般情況下，Cm和Fm的選取規則為：

（1）對任意i∈Fm，j∈Smi（表示網格中點i強聯結的點），那么j∈Cmi或者j與Cmi的一個點強聯結；

（2）Cm是非強聯結點構成的最大點集合。

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

代數多重網格求解過程中，粗網格的變化是不規則的，粗網格矩陣大小在改變，點數也在變化，沒有規律可循，因此將粗網格運用到圖像重構中的最大難題是粗網格圖像還原到原始圖像大小，而解決這個問題的前提是將粗網格中的點對應到原始圖像中的像素點。

算法描述：在代數多重網格圖像粗網格提取中，采用python語言的pyamg包來實現代數多重網格算法，可以得到粗化后的第1、2…N層數據，對應于原始圖像中部分像素點，可采用某種插值函數插值，如最近鄰法，線性插值法等，可以得到重構圖像。

根據以上的討論，本文設計的代數多重網格圖像重構算法為：

（1）根據代數多重網格得到網格序列：對原始圖像I進行代數多重網格粗化得到N層粗化網格Ω1，Ω2…ΩN；

（2）擴充網格：將N層網格Ω1，Ω2…ΩN還原成原始圖像大小的Ω′1，Ω′2…Ω′N，此時需要考慮粗網格序列與上一層粗網格位置索引對應關系，網格中的元素被選中為下一層粗網格的元素值為1，否則為0；

（3）網格與圖像坐標對應：粗網格Ω1，Ω2…Ω′N.因為是圖像大小，所以網格與原始圖像I很容易找到對應位置關系，采取如下策略：

1）如果網格中的數據是1，則令對應位置的像素為圖像相應位置的灰度值；

2）如果網格中的數據是0，則令對應位置的像素等于0，這樣就產生了一系列圖像I1，I2…IN。

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

2 實 驗

2.1 實驗條件

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

圖1 本文所用的實驗圖片

2.2 圖像重構實驗

2.2.1 圖像粗網格序列的提取

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

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

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

圖2 提取的三層粗網格

表1 粗化網格中定量評價信息量

2.2.2 由粗網格序列進行圖像重構

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

圖3 粗網格序列插值結果

2.3 與小波重構算法對比實驗

本文對比了四幅圖片的結果，圖片依次為圖1中的（a），（b）， （c）， （d），分別對其進行小波重構與代數多重網格算法重構。采取的評價量度為均方誤差 （Mean Square Error），均方誤差越小，表明重構圖像與源圖像越接近，重構效果就好，反之則差，故可以用均方誤差來衡量圖像重構算法的優劣。設兩幅大小為M＊N圖像I1和I2，定義均方誤差為

根據式 （2），得到如表2中均方誤差評價參數，從數據上來看，代數多重網格重構算法與小波重構算法的MSE是在同一個數量級上；而且它們都呈現出相同的變化趨勢：變化較一致，沒有出現突異。由表2中每幅圖像的MSE值可以看出在每一層的數據集合上，代數多重網格算法能夠達到較好的效果，且比小波重構算法的MSE值小，說明代數多重網格算法圖像重構質量較好。

2.4 應用實例

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

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

根據平均誤差 （D）、峰值信噪比 （PSNR）、相關系數（REL）、空間頻率 （SF）四種方法進行評價［15］，得到的各項參數為表3所示，其中小波融合采取的4層Haar小波。D、PSNE、REL都反映了融合結果和標準圖像的差異程度。D越小，PSNR越大，REL越大融合效果越好，SF越大，說明圖像保留的高頻信息越多。從表3的數值來看，本文融合結果效果較小波圖像融合效果好。

從該實例可以看出，利用代數多重網格算法進行重構，可以較好的反應原始圖像中的細節信息。當圖像越清晰，細節信息越豐富，代數多重網格能夠將更多的細節信息保持到下一級粗網格中；而圖像越模糊，細節信息越稀少，因此代數多重網格重構結果放大了圖像中的細節信息部分，也能說明代數多重網格圖像重構算法能較好的保留原始圖像的有用信息。

表3 融合結果評價參數比較

圖4 通過應用實例進一步驗證AMG圖像重構算法的有效性

3 結束語

本文研究了代數多重網格算法中粗網格算子的提取過程，并將其應用到在圖像的重構中，提出了一種基于代數多重網格的圖像重構算法。本文算法提取的圖像的粗網格的密集程度能夠表征圖像的變化的劇烈程度，網格保留了圖像的有效信息部分像素點。實驗結果表明本文算法不僅能夠取得較好的重構效果，且與傳統的小波圖像算法相比具有一定的優勢，并在圖像融合中應用了此圖像重構算法，與小波融合相比，效果較好。代數多重網格算法的其它特性在圖像的其它領域比如圖像壓縮，圖像分割，圖像融合等的應用將是下一步的研究方向。

［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）.［席志紅，張越，邵欣.小波結合偏微分插值的圖像超分辨率重構算法 ［J］.探測與控制學報，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變換的人臉識別算法優化 ［J］.電子測量技術，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）.［蒯偉，段佳佳.基于小波變換的圖像重構算法研究 ［J］.電子測試，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］.遙感技術與應用，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）. ［練秋生，高彥彥，陳書貞.基于兩步迭代收縮法和負數小波的壓縮傳感圖像重構［J］.儀器儀表學報，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］.計算機應用研究，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）.［郭飛宵，楊力，劉榮，等.大型稀疏法方程組的代數多重網格解法 ［J］.測繪科學技術學報，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）.［史培林.代數多重網格法及其在圖像重構中的應用 ［D］.北京：中國科學院，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）. ［馮子亮，王翠芹，施關民.一種基于主動生長的邊緣連接算法［J］.計算機應用研究，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］.電子學報，2011，39 （3）：690－694.］