摘  要： 滅點(diǎn)是分層重建過程的重要信息，其求解的準(zhǔn)確程度直接關(guān)系到最后三維重建的效果。提出了一種基于Hough算法的直線聚類檢測方法求取圖像中的直線信息以及基于RANSAC的由直線信息估計滅點(diǎn)信息的改進(jìn)算法，以提高估計滅點(diǎn)的魯棒性。經(jīng)試驗(yàn)證明，將所提出的算法應(yīng)用到分層重建的系統(tǒng)中，在僅有兩幅圖像的情況下能準(zhǔn)確地對目標(biāo)模型進(jìn)行重建。
關(guān)鍵詞： Hough；直線聚類檢測；滅點(diǎn)；分層重建；RANSAC

　三維重建是計算機(jī)視覺研究的核心問題之一。早期的三維重建主要利用黑白棋盤等結(jié)構(gòu)已知的標(biāo)定物事先進(jìn)行標(biāo)定，求得攝像機(jī)內(nèi)參數(shù)，但這種方法只能應(yīng)付靜止和已知環(huán)境條件下的重建工作。1992年，F(xiàn)augeras[1]提出自定標(biāo)和分層重建等概念成為三維重建中最活躍的一個研究領(lǐng)域，之后許多學(xué)者在這一領(lǐng)域進(jìn)行了進(jìn)一步的研究[2-4]。分層重建將重建分成以下三個層次：射影重建、仿射重建和度量重建，重建過程相對早期傳統(tǒng)標(biāo)定更具有實(shí)用性好、靈活性強(qiáng)的特點(diǎn)。
　本文在僅有兩幅圖且沒有攝像機(jī)運(yùn)動的情況下，提出了基于Hough直線聚類檢測方法。該方法將直線有目的性地按角度進(jìn)行分組，以減少參與滅點(diǎn)估計的直線樣本，降低估計算法復(fù)雜度；然后提出一種改進(jìn)的RANSAC算法[5]。該算法結(jié)合極線幾何約束的評價函數(shù)，重新構(gòu)造了代價函數(shù)，進(jìn)而提高了原RANSAC算法估計滅點(diǎn)的魯棒性；最后闡述了根據(jù)不同的滅點(diǎn)對數(shù)情況構(gòu)建變換矩陣進(jìn)行分層重建的方法。
由于沒有場景信息時，重建結(jié)果與真實(shí)模型相差一個全局縮放因子，而這并不影響視覺效果，因此，本文提到的歐氏重建均是指相差一個常數(shù)因子的重建。
1 重建方法
1.1 滅點(diǎn)
　空間上的一組平行線經(jīng)過透視投影成像后，在成像平面上交于一點(diǎn)，稱為滅點(diǎn)，滅點(diǎn)圖如圖1所示。圖中，xp(p=1，2，3)即為滅點(diǎn)。滅點(diǎn)信息一般用于攝像機(jī)參數(shù)的求解，是非標(biāo)定重建(如分層重建)的重要圖像信息。滅點(diǎn)可以由直線檢測算法求取獲得。

1.2 基于Hough的直線聚類檢測方法
　傳統(tǒng)算法中，主要由Burns提出了相位編組法(一種基于點(diǎn)梯度聚類的直線檢測方式[6])，其算法易實(shí)現(xiàn)但目的性不強(qiáng)。本文采用受噪聲和曲線間斷的影響均較小的Hough[7]變換檢測直線方法，獲取直線垂線和x軸正向的夾角(參數(shù)空間下的θ)，然后將參數(shù)空間的角度范圍由[-90°，90°]轉(zhuǎn)化為[0°，180°]，得到直線按照角度分類的統(tǒng)計直方圖，橫坐標(biāo)為角度，縱坐標(biāo)為在某角度范圍內(nèi)直線的個數(shù)。統(tǒng)計前一般需要對直線之間的間斷進(jìn)行預(yù)處理，通過設(shè)置間隔值減少參加估計滅點(diǎn)直線樣本的數(shù)量。具體步驟如下：
　(1)將參數(shù)空間對應(yīng)的像素位置旋轉(zhuǎn)90-θ°，以便使其大概位于一條垂線上。
　(2)按旋轉(zhuǎn)的程度(如x值)來對這些像素位置排序。
　(3)利用一階微分函數(shù)找到裂口，忽視掉小裂口，合并間隔小的相鄰線段。
　(4)返回比設(shè)置的閾值長的線段信息，并記錄θ。
　(5)設(shè)立直方圖進(jìn)行聚類。
　Hough變換的缺點(diǎn)是既耗時又占空間，因此，本文采用概率Hough變換(PHT)改進(jìn)方法，減少了時間消耗和儲存空間的占用。
　獲得統(tǒng)計直方圖后需要對不同方向上的直線進(jìn)行總體方向上的聚類(本文假設(shè)為三個方向。兩個方向的情況與此相似，本文不予介紹)。聚類采用了下面的迭代方法：
　(1)對統(tǒng)計直方圖進(jìn)行曲線擬合(如高次樣條函數(shù))。正常情況下一般可以獲得非邊緣2個局部最小值(波谷)作為圖像的分割閾值，即初始值T1、T2(T1<T2)。
　(2)設(shè)將直線按角度分為n組，采用T1、T2分割后得到直線集按角度由小到大依次為G1、G2、G3，求得G1、G2、G3范圍內(nèi)每條直線平均角度為μ1、μ2、μ3，然后重新求分割閾值：
　T1=(μ1+μ2)/2，T2=(μ2+μ3)/2
　(3)重復(fù)步驟(2)，直到T1、T2不再變化。一般迭代2~3次就可收斂。
1.3 改進(jìn)的魯棒估計滅點(diǎn)算法
　Schaffalitzky[8]、Rother[9-10]、陳付幸等人在利用直接信息檢測估計滅點(diǎn)時都引入了隨機(jī)抽樣一致性RANSAC算法，一定程度上提高了單視圖求滅點(diǎn)的效率與準(zhǔn)確度。
本文基于二視圖極線幾何的關(guān)系，根據(jù)幾何約束調(diào)整代價函數(shù)，改進(jìn)了RANSAC估計滅點(diǎn)算法，同時保證了算法的魯棒性與準(zhǔn)確性。
　假設(shè)m1、m2互為匹配的滅點(diǎn)且為某無窮遠(yuǎn)點(diǎn)M到二視圖圖像的投影點(diǎn)的齊次坐標(biāo)，則m1~H∞m2(“~”表示相差一個常數(shù)因子)，且有mT2Fm1≈0，即滅點(diǎn)在二視圖中仍然受到極線幾何約束，且僅符合極線幾何關(guān)系的點(diǎn)才能考慮匹配。其中F(3×3)稱為基本矩陣，其描述了雙攝像機(jī)的射影幾何關(guān)系。

　其中，C1為滅點(diǎn)位于直線上的最小化，C2為滅點(diǎn)位于極線上的最小化，C3為滅點(diǎn)到直線的距離和最小化，C4為滅點(diǎn)到對應(yīng)極線距離和最小化。相比較而言，C1、C3之間和C2、C4之間都有相近最小化的代數(shù)意義，但是C3、C4比數(shù)值上的最小化C1、C2代價函數(shù)更具有幾何意義，更能反映極線幾何約束關(guān)系，所以本文選擇C3、C4為評價滅點(diǎn)的雙重代價函數(shù)。
　本文改進(jìn)后的滅點(diǎn)估計算法步驟如下：
　(1)從檢測到的直線中按照方向進(jìn)行聚類，將分類中方向大致相同的直線隨機(jī)選擇M組數(shù)據(jù)樣本，每組樣本的大小為3[8]，在一定的置信概率下，保證M組樣本中至少有一組樣本不包含錯誤直線。
　(2)分別估計M組樣本的滅點(diǎn)，并用所有直線段來檢驗(yàn)消失點(diǎn)(全數(shù)據(jù)檢驗(yàn))，通過C=C3C4代價函數(shù)選擇包含最多直線的滅點(diǎn)作為最優(yōu)滅點(diǎn)，將最優(yōu)滅點(diǎn)包含的直線作為局內(nèi)直線(inliers)。本步驟需要反復(fù)進(jìn)行。
　(3)用劃分的inliers直線數(shù)據(jù)重新計算滅點(diǎn)，搜索附近外直線參加計算滅點(diǎn)。此步也可以重復(fù)進(jìn)行。
　(4)由步驟(3)獲得的穩(wěn)定的數(shù)據(jù)作為正確的inliers 直線數(shù)據(jù)來估計最終消失點(diǎn)。
1.4 射影重建、仿射重建及歐氏重建
　本文根據(jù)獲取滅點(diǎn)信息的不同情況，分別進(jìn)行分層重建。分層重建即按照射影幾何的層次關(guān)系依次實(shí)現(xiàn)射影重建、仿射重建和歐氏重建。當(dāng)求得基礎(chǔ)矩陣后就可以獲得射影空間中的三維模型Xp，其與真實(shí)場景模型Xe之間相差一個射影變換T，則有：
　Xp=TAETAP Xe
　即確定無窮遠(yuǎn)平面π∞的位置(3個自由度)，獲得變換矩陣TAP，將射影重建升級為仿射重建，然后確定無窮遠(yuǎn)平面上絕對二次曲線ω的位置(5個自由度)，獲得變換矩陣TAE，從而將仿射重建升級為歐氏重建。
當(dāng)有3對滅點(diǎn)時，可線性求解π∞，根據(jù)其滅點(diǎn)正交性線性求解ω；當(dāng)少于3對滅點(diǎn)時，則采用模約束[2]等方式求解π∞及其對應(yīng)的單應(yīng)矩陣H∞，由w=HT∞ ωH∞，根據(jù)至少一對正交的滅點(diǎn)求解ω。對于單滅點(diǎn)的情況一般在多視圖下重建。
1.5 誤差檢驗(yàn)
　本文采用反投影方法進(jìn)行誤差驗(yàn)證。當(dāng)歐氏重建結(jié)束后，通過非線性最小化將空間點(diǎn)反投影到平面，將投影后的點(diǎn)信息與原點(diǎn)的歐式距離作為評價誤差，則有：

　其中，i為視圖數(shù)，j為每個視圖上的特征點(diǎn)數(shù)。根據(jù)誤差評價重建效果，若誤差較大可進(jìn)一步縮小1.2節(jié)和1.3節(jié)算法的閾值，以增加準(zhǔn)確度。
2 實(shí)驗(yàn)過程
　實(shí)驗(yàn)一：對一張如圖2所示的640×480的建筑物圖片，采用本文的直線聚類檢測算法進(jìn)行處理，實(shí)驗(yàn)中分組數(shù)為180。圖3為處理直線中小于5個像素的間斷連接的聚類情況(T1=46.380 9，T2=132.707 2)，圖4為圖3按單位度數(shù)進(jìn)行統(tǒng)計的直方圖。對間斷點(diǎn)進(jìn)行處理，對間斷小于20像素的直線進(jìn)行合并，間斷點(diǎn)處理后直線提取如圖5所示，其統(tǒng)計圖如圖6所示。圖4、圖6的橫坐標(biāo)表示直線方向(單位為度)，縱坐標(biāo)表示按某個組間間隔分組的每組直線數(shù)量。本文按角度分為180組，即組間間隔為1°。

　由圖5、圖6可以看到，通過直線段的連接，調(diào)整間隔連接為15個像素，可使直線的數(shù)量減少，達(dá)到合并和減少樣本的目的(T1=46.303 9，T2=132.638 4)。
　實(shí)驗(yàn)二：采用實(shí)驗(yàn)室系統(tǒng)來模擬分層重建[11]，生成空間以XW為頂點(diǎn)物體(形如小房子)并沿z軸平移5個單位，隨機(jī)增加0~0.002的噪音。模擬如表1、表2的初始內(nèi)參A，通過A將三維點(diǎn)信息投影到模擬的二視圖平面(模擬攝像機(jī)位置)上，讓其中一個攝像機(jī)位于坐標(biāo)軸中心，其分層重建模型如圖7所示。本文所有實(shí)驗(yàn)使用同一觀察視角(函數(shù)view(200，20))。圖7~圖11(x，y，z)為坐標(biāo)系模擬物體所在的三維空間，單位為數(shù)值1。

　進(jìn)行分層重建的步驟如下：
　(1)射影重建：根據(jù)模擬照相機(jī)中的二維點(diǎn)求取基礎(chǔ)矩陣后進(jìn)行射影重建，其效果圖如圖8所示。
　(2)仿射重建：原物體XW點(diǎn)附近隨機(jī)添加帶噪聲點(diǎn)10個，以這些點(diǎn)連接的直線作為樣本，然后通過本文算法估計3個正交方向3對滅點(diǎn)，根據(jù)無窮遠(yuǎn)性質(zhì)獲得變換矩陣進(jìn)而完成仿射重建，其效果如圖9、圖10所示。

　(3)歐氏重建：由3對滅點(diǎn)線性求得絕對二次曲線的圖像進(jìn)行歐氏重建(相差一個常數(shù)因子)，其結(jié)果如圖11所示，實(shí)驗(yàn)結(jié)果如表2所示。
　通過與傳統(tǒng)代價函數(shù)只有C3算法作為評價比較，其重建效果如圖12所示，由圖可以得出本文算法能夠獲得較準(zhǔn)確的估計滅點(diǎn)，從而獲得更好的分層重建效果。估計滅點(diǎn)的比較如表3所示。

　本文方法主要是基于二視圖的重建方法，當(dāng)滅點(diǎn)為兩對或更少時可采用多視圖增加約束的方法實(shí)現(xiàn)。
　本文主要介紹了分層重建中滅點(diǎn)信息的求取過程中兩個階段的研究，即首先采用直線聚類檢測方法檢測直線，然后將分類后的直線樣本通過改進(jìn)的RANSAC估計算法類進(jìn)行滅點(diǎn)估計。將直線檢測與滅點(diǎn)的估計融合在一起，提高了滅點(diǎn)求取算法的效率和魯棒性，使滅點(diǎn)的估計更具有針對性，同時根據(jù)得到的滅點(diǎn)信息結(jié)果介紹了對應(yīng)的重建策略。本方法進(jìn)行了分層重建，并通過模擬實(shí)驗(yàn)得到了理想結(jié)果。
參考文獻(xiàn)
[1] FAUGERAS O D. Stratification of 3-D vision： projective， affine and metric representations[J]. Journal Optical Society of America， 1995，12(3)：465-484.
[2] POLLEFEYS M， GOOL V L， OOSTERLINCK A. The modulus constraint： A new constraint for self-calibration[C]. Proceedings  of  International Conference on Pattern Recognition， Vienna， Austria， 1996： 349-353.
[3] TRIGGS B. Auto-calibration and the absolute quadric[C].Proceedings of IEEE Conference on Computer Vision and Pattern Recognition， Puerto Rico， USA， 1997：610-614.
[4] HARTLEY R I. Euclidean reconstruction and invariants from multiple images[J].IEEE Transactions on Pattern Analysis and Machine Intelligent，1994，16(10)： 1020-1041.
[5] FISCHLER M A， BOLLES R C . Random sample consensus： a paradigm for model fitting with applications to image analysis and automated cartography[J]. Communications of the ACM， 1981，24(6)： 380-395.
[6] BURNS J B， HANSON A R. RISEMAN E M. Extracting straight lines[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，1986(4).
[7] LINGWORTH J， KITTLER J.A survey of the Hough transforms [J]. CVGIP， 1988，44：87-116.
[8] SCHAFFALITZKY F， ZISSERMAN A. Planar grouping for automatic detection of vanishing lines and points [J]. Image and Vision Computing， 2000，18(9)： 645-658.
[9] ROTHER C. A new approach for vanishing point detection in architectural environments[C]. British Machine Vision Conference (BMVC)， Bristol， UK， 2000： 382-392.
[10] ROTHER C . Multi-view reconstruction and camera recovery using a real or virtual reference plane[C]. PhD thesis， Royal Institute of Technology， Sweden， 2003.
[11] Yi Ma. An invitation to 3d vision[EB/OL]. http：//vision.ucla. edu/MASKS，2010-12-10.