基于表面法向差分近似的表面重建新算法

摘 要：提出一種基于表面法向差分的四向加權形狀重建算法。該方法利用不同表面法向差分方法的重建核函數所具有的互補特性，通過對不同重建結果的四向線性加權可以克服經典重建矩陣的奇異性，并能增加算法的抗噪能力。

關鍵詞：表面法向; 形狀重建; 差分法

中圖法分類號：TP391.4 文獻標識碼：A 文章編號：1001-3695(2006)10-0146-02

Weighted Algorithm Based on Surface Normal Approximation

LEI Liping1， ZHENG Yuqi2

(1.College of Automation， Nanjing University of Aeronautics Astronautics， Nanjing Jiangsu 210016， China; 2.Military Authority of the Second Artillery， Luzhou Sichuan 646006， China)

Abstract:Using the intercomplementary speciality of reconstruction kernel function of different surface normal difference approximation， the proposed method combines fourdirectional reconstruction results through corresponding weighted factors. By means of linear weighting and imposing appropriate boundary condition， the new approach would overcome the oddness of traditional reconstruction kernel function， and is more robust to noise.

Key words:Surface Normal; Surface Reconstruction; Difference Approximation

在基于陰影的表面重建算法研究中，一個非常重要的課題在于選取合適的算法并盡量減小重建算法的誤差?；诒砻娣ㄏ虿罘值牡亟ㄋ惴ㄓ捎谟嬎銖碗s度低并且恢復結果較為理想，一直受到許多學者的關注[1，2]，其不足在于圖像中的某些點會產生較大的形狀畸變。因此，本文提出了一種基于邊界補償的四向加權形狀重建算法，該方法不僅計算較為簡單，還能夠克服以往算法中由于矩陣奇異導致的計算誤差，并能夠增加算法的抗噪性。

1 表面法向差分近似

已知物體表面反射模型是標準漫反射模型，稱之為郎伯表面模型[3]。由此可以推導出SFS的成像函數，具體表現為一個非線性的偏微分方程：

E(x，y)=R(p，q)=P×S=psp+qsq+1p2s+q2s+1×p2+q2+1(1)

式（1）中，P和S分別表示單位化的物體表面梯度向量和光源向量，即P=(p，q，1)T/p2+q2+1(2)

S=(ps，qs，1)T/p2s+q2s+1(3)

表面梯度分量p和q分別為p=-z/x和q=-z/y。在Osamu Ikeda的文章[4]中，曾經使用四種最簡單的差分方式代替微分運算，這樣可使得R變為一個關于z變量的非線性函數，然后將f在z(x，y)點線性展開并使用Jacobi迭代，則可以得到概括為如下的矩陣表達式：

-f(n-1)=g(n-1)(z(n)-z(n-1)) n=1，2，3，…(4)

其中，n為迭代次數，f和z分別為f(x，y)和z(x，y)對應的N2維的列向量:

f=(f1，1， f2，1，，…， fN，1，…， f1，N， f2，N，…， fN，N)T

z(n)=(z(n)1，1，z(n)2，1，…，z(n)N，1，…，z(n)1，N，z(n)2，N，…，z(n)N，N)T

g為N2×N2維矩陣，式（4）也可以表示為如下直接求解z的形式：

z(n)=z(n-1)-(g(n-1))-1f(n-1)(5)

通過給定初值z(0)，物體表面高度由上式迭代求得。由于使用不同的差分方法得到的矩陣g不同，恢復出來的表面形狀也略有不同。由于g的特征值為fx，y對zx，y的偏導數:

λx，y=fx，yzx，y x，y=1，2，…，N(6)

則對后向差分，g的逆矩陣有如下形式：

g-1=h1，100…0

h2，1h2，20…0

h3，1h3，2h3，3…0

…

hN，1hN，2hN，3…hN，N（7）

其中，hi， j（i=1，2，…，N， j=1，2，…，N）為N×N的子矩陣。每行的子矩陣hi+k， j（i=1，2，…，N-k）的結構相似，隨著行數k的增加，子矩陣的結構復雜度也隨著增加。SNDA方法的主要誤差產生原因為： 當(p，q)接近(1．0，1．0)時，三個偏導數的值全部變小接近0。由于fx，y/zx，y的值與矩陣g的特征值有直接的關系，一個接近零的特征值會給逆矩陣造成較大的擾動，甚至出現病態值，即當(p，q)＝(1．0，1．0)，g成為奇異矩陣，無法求逆。這會造成在該點的運算出現較大的誤差，反映到形狀重建結果上，就是當待重建物體表面方向與光照方向一致時，即圖像的最亮點處，由于矩陣g的奇異導致迭代法在該點失效，重建的形狀會出現較大的畸變。

2 重建核函數及重建系統分析

通過式(5)可以看出，在給定了初值z(0)以后，矩陣g-1直接決定了重構出的表面形狀，因此，將g-1稱為重建矩陣。對于四種差分方式，g矩陣中的非零元素均分布在三條平行與主對角線的斜線上，并且四個g矩陣都是嚴格對角占優的。然而，四種重建矩陣具有完全不同的形式。仔細觀察可以發現，對于前向差分的矩陣g和g-1做轉置操作，可以得到與后向差分的矩陣g和g-1相同的結構。同樣地，對后前向差分的矩陣g和g-1做轉置操作，可以得到與前后向差分的矩陣g和g-1相同的結構。通過對它們各自積分區域的觀察發現，XY平面內陰影區的元素作為f的權重，前向差分和后向差分的分布情況正好對稱，對于這種對稱，我們可以稱之為積分域互補特性。同理，后前向差分和前后向差分也存在這種對稱。因此可以設想，若利用四種算法之間兩兩互補的特性，可以尋找到一種更加魯棒的算法來提高四種差分方法單獨使用時的精度。

3 基于線性加權的形狀重建算法

利用重建核函數兩兩互補的特性，本文提出一種雙向加權方法克服傳統SNDA方法中產生的誤差，具體過程如下所述。

由于傳統的SNDA求解z的方法是利用Jacobi迭代式：

z(n)=z(n-1)-(g(n-1))-1f(n-1)(8)

這樣，通過給定初值z(0)，物體表面高度可由式（8）迭代求得。由于重建矩陣的特征值在物體表面梯度方向平行于光照方向時變成零值，導致g-1出現奇異性而造成形狀畸變。考慮到廣義逆矩陣的概念，將g-1變為廣義逆矩陣能夠增加其特征值的分量數目，對于防止矩陣出現奇異性起到了一定積極作用。由此，可將式(8)變為

z(n)=z(n-1)-G(n-1)F(n-1)(9)

其中G(n-1)=g(n-1)Tg(n-1)(10)

F(n-1)=g(n-1)Tf(n-1)(11)

由于G的特征值含有三個非負項，相比原先的一個特征值，避免了在物體表面方向平行于光照方向時出現零特征值的情況，這對防止矩陣出現奇異性有重要作用。

由于前向差分和后向差分的積分域互補，并且前后向差分和后前向差分的積分域互補，因此若結合四種算法的加權算法應該得到最優的效果。

對于一幅圖像，分別使用四種差分方法得出重建后的形狀，然后通過線性加權平均。

z(n)=z(n)-(G(n))-1F(n)(12)

z=η1(z1+z2)+η2(z3+z4)(13)

其中ω1(x，y)=1-x+y-22(N-1)， ω2(x，y)=x+y-22(N-1)

ω3(x，y)=1-N-x+y-22(N-1)， ω4(x，y)=N-x+y-22(N-1)

η1和η2為決定兩類互補方法間的形狀加權參數。在實驗中，通常取為η1=0．4，η2=0．6。

4 實驗結果及分析

前面討論了結合邊界補償的加權重建方法，本節將用仿真實驗來驗證上面提出加權算法的效果。實驗所用合成圖像由計算機生成，其表面反射情況基本符合朗伯體假設，且表面反射率為常數?？紤]到重建矩陣的維數較高，實驗使用的合成圖像不能過大，為50×50，光照方向為(1，1，1)，圖像灰度范圍為10~250，如圖1所示。

圖1(a)(1，1，1)光線下的測試原圖象;圖1(b)SNDA算法的計算結果;圖1(c)前向差分的計算結果;圖1(d)后向差分的計算結果;圖1(e)前后向差分的計算結果;圖1(f)后前向差分的計算結果;圖1(g)平均得到的最后結果;圖1(h)根據本文算法生成的光滑表面。圖1(b)為傳統SNDA方法重建出的形狀，使用的差分方法為前向差分。在圖像中的最亮處，由于其表面方向(p，q)非常接近于(1，1)，導致了在重建結果中最亮處對應的形狀附近出現了畸變。另外，圖像中背景區的重構形狀并不平坦，出現了波紋。同樣的情況也出現在圖1(d)、圖1(e)、圖1(f)中，產生的原因在于重建函數存在波浪狀分量，可以理解為系統的形狀噪聲。圖1(c)和圖1(d)分別給出了對測試圖像使用本文的前向差分和后向差分算法恢復出的形狀。經過比較，使用后向差分的形狀畸變略小于前向差分的形狀畸變。圖1(g)為兩種差分算法的加權平均，權函數方向為主對角線方向。類似地，圖1(e)和圖1(f)分別給出了對測試圖像使用本文的前后向差分和后前向差分算法恢復出的形狀。圖1(g)和圖1(h)為最后的加權結果。從視覺效果上不難看出，加權平均對消除形狀誤差有一定的作用。

為了驗證算法的抗噪性而針對噪聲圖像做了一組實驗，如圖2所示。其中，圖2(a)為球的圖像加了5%的高斯噪聲，圖2(b)為使用本文算法的恢復結果，圖2(c)為根據最后結果生成的光滑表面。比較圖1(g)和圖2(b)可見，即使實驗圖像受到噪聲干擾，恢復結果基本沒有太大變化，仍然是令人滿意的。其主要原因是加權平均有平滑濾波的作用，在一定程度上能夠消除噪聲的影響，這對算法的穩定性是有積極意義的。由此不難得出以下結論：使用本文提出的四向線性加權算法能夠較好地恢復出測試圖像的表面形狀。

5 小結

為了克服傳統表面法向差分近似SNDA模型的誤差，本文提出了一種對四種差分方法重建形狀的混合加權算法。該算法能夠有效抑制每種差分算法由于積分域單一造成的重建核函數波紋噪聲，有效地提高了重構精度。同時，加權算法有平滑濾波的作用，在一定程度上能夠消除原始圖像中噪聲對最終重建結果的影響。對提出方法的實驗結果表明，改進的加權SNDA算法能有效地重構出物體的三維形狀，相比傳統方法提高了重建形狀的精度。

參考文獻：

[1]Zhang R， Tsai P S， Cryer J E， et al. Shape from Shading: A Survey[J]. IEEE Trans. Pattern Analysis and Machine Intelligence， 1999，21(8):690-705.

[2]Ikeda O. A Novel Shape from Shading Algorithm Using Jacobi Iterative Method[J]. Proc.of IASTED CGIM， 2002.56-61.

[3]Pentland A P. Linear Shape from Shading[J]. International Journal of Computer Vision， 1991，4(2):153162.

[4]Ikeda O. A Shape from Shading Algorithm Using Jacobi Iterative Method and Forward and Backward Estimation[C]. Proceedings of ITE Winter Annual Convention， 2001.82-96.

作者簡介：

雷莉萍（1980-），女，江西南昌人，碩士研究生，主要研究方向為測試信號處理；鄭鈺琪（1976-），男，四川瀘州人，工程師，碩士，主要研究方向為測試信號處理、轉載設備研制。

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文