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

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

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

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

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

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

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

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

　本文方法主要是基于二視圖的重建方法，當滅點為兩對或更少時可采用多視圖增加約束的方法實現。
　本文主要介紹了分層重建中滅點信息的求取過程中兩個階段的研究，即首先采用直線聚類檢測方法檢測直線，然后將分類后的直線樣本通過改進的RANSAC估計算法類進行滅點估計。將直線檢測與滅點的估計融合在一起，提高了滅點求取算法的效率和魯棒性，使滅點的估計更具有針對性，同時根據得到的滅點信息結果介紹了對應的重建策略。本方法進行了分層重建，并通過模擬實驗得到了理想結果。
參考文獻
[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.