帶有未知匹配的圖像線特征三維重建方法的研究

（中國農業科學院農業信息研究所， 北京 100081）

摘 要：為了解決傳統三維重建過程中線特征匹配速度慢、建模與匹配過程脫節的問題，提出了基于相關系數的圖像線特征匹配的方法，運用此方法對同一物體的三幅圖像進行了特征匹配和三維重建。建立了目標物體的三維模型，達到了對物體線特征匹配與三維重建同步進行的目的。通過對所得實驗數據分析，可以證明此算法對于物體的三維重建是有效的。

關鍵詞：三維重建；特征匹配；三維模型

中圖分類號：TP391文獻標志碼：A

文章編號：1001-3695(2009)04-1557-03

Research of 3D reconstruction of lines withunknown correspondence across images

WANG Jian， ZHOU Guo-min， LIU Li-bo

(Agricultural Information Institute， Chinese Academy of Agricultural Sciences， Beijing 100081， China)

Abstract:During the course of 3D reconstruction from a set of images， there were some limitations: low speed for matching， disjunction of modeling and matching.To resolve these limitations in traditional algorithms，this paper developed a new efficient algorithm of lines correspondence matching based on a new affinity measure.Based on the algorithm of lines，presented mat-ching and reconstruction across images.Through this method， image lines matching and 3D reconstruction could be operated in parallel.Experimental results on synthetic and real data demonstrate the effectiveness of the method.

Key words:3D reconstruction; feature correspondence matching; 3D model

在機器視覺中，三維模型的獲取是一個非常重要的領域。在這一領域中，一個關鍵的問題在于如何從一系列已經校正好的二維圖像中準確地重建出三維模型。立體視覺的出現很好地解決了這一問題，它是探求從二維圖像中恢復三維空間信息的方法，以達到從圖像認識世界的目的。通常的雙目立體視覺是建立在對應特征的視差基礎之上的，因此兩幅圖像中各特征的匹配關系成為雙目立體視覺技術研究中的一個極其重要的問題。然而，通過實際的立體圖像對求解對應問題是極富挑戰性的，可以說它是三維重建中最為困難的一步。通常圖像中最常用的特征是點和線。與點特征比較起來，線特征雖然比較復雜，但是由于線特征的二維屬性，使得以線特征重建的三維圖像更加逼真，景像還原結果更好，因此具有很強的實用價值。

本文主要研究在已知相機位置的情況下確定圖像線特征匹配，并以此獲取目標物體三維特征的問題。給出了測量圖像線特征相關性的算法；論述了以圖像線特征相關（affinity）系數為基礎構建帶權二分圖，并以此計算最大匹配，從而確定圖像線的匹配與其相應的3D線段端點坐標的方法。

1 通過三維虛交線來測量圖像中線特征的相關性

在關于圖像線特征的特征匹配和三角剖分的過程中，比較困難的問題在于相對于點特征來說，線特征則更難以描述相互間的相關性。圖像中的一些線數據可能會破碎或發生意外的遮擋，從而引起圖像線的端點出錯。因此，通常實驗中線特征均在那些方向和位置確定且長度無限的圖像線上選取，并且這些線特征都具有足夠長度。另一方面，由于在兩幅圖像中的線段對的投影面都相交于一個3D線上（如果平行，則說投影面相交于無限遠處），這樣就無法僅僅從兩幅圖像中找出足夠的線索來從無限多的圖像線中找到可能的匹配。在實際匹配過程中，至少需要三幅圖像才能描述出線特征之間的相關性。 

設給定同一物體在不同角度所拍攝的三幅圖像且它們所對應的相機位置已知。在每一幅圖像中隨機選取一個圖像線特征，由此組成一個擁有三個元素的圖像線特征的集合。這樣，此線特征的集合中可能或不可能與場景中的一個3D線段存在著真正匹配。在實驗過程中可以證明：對于任意一組圖像的線特征來說，存在著一個3D虛交線L，使得L到每幅圖像的線特征端點的投影線的相互矩（mutual moments）的平方和最小。在實際搜索對應的匹配時，這樣的計算將會在圖像中大量線特征間進行多次，因此需要大量的系統資源以滿足計算的需求，為解決這一問題需要一種有效率的算法，在保證一定準確率的基礎上提高運算速度。本文采用Cheng等人[1]所提出的算法，這種算法利用極線約束等原理來尋找一個最佳的3D虛交線。實驗證明這種算法是非常快捷和有效的。

對任意一組圖像的線特征來說，為了計算出一個確定的值來衡量該組線特征是否與空間中一個3D線相匹配，在本文中，首先使用Cheng所提出的圖像線重建算法來計算它們的虛交線L的位置，然后將L投影回三幅圖中，得到三個無限長的圖像線li（i=1，2，3）。設li可以在像素坐標系中表示為：fiu+giv+hi=0，在2D圖像中的線片斷Ii的端點坐標是(ua，va)和(ub，vb)。一個自然的計算線片斷到投影虛交線li的距離方法是線片斷端點到li的絕對像素距離之和，即

ri=（|fiua+giva+hi|+|fjub+givb+hi|）/f 2 i+g2i(1)

如果三條圖像線片斷是匹配于一個真正的3D直線段，就可以認為這些線片斷都分別“靠近”虛交線的再投影線。這種“靠近”的判斷是建立在對線片斷抽取過程中誤差特征和圖像噪聲等知識的認知基礎之上的。另一方面，如果圖像的線片斷不匹配于一幅場景的線結構，它們到虛交線的距離會很大，這一原理在大多數線片斷組中都成立（除非有一些意外的組合）。因此，這個距離是一個很好的量度以證實選中的圖像線在幾何上是否匹配。

基于上述距離測量方法，在三幅圖像中的線片斷組中二維線段的相關性值sfl(l1，l2，l3)可定義如下：

sfl(l1，l2，l3)=e-(3i=1ri)/6(2)

其中：（3i=1ri）/6的意義是圖像中線特征組的端點到它們相關的虛交線距離的平均值。當sfl(l1，l2，l3)=0時，意味著l1，l2，l3是不匹配的；如果sfl(l1，l2，l3)=1，則意味著l1，l2，l3是完全匹配的。

2 基于雙向權值匹配的三維重建算法

本文引入了一種新的衡量三幅圖像線特征相關性關系的衡量方法，即式（2）中的sfl(l1，l2，l3)函數。這一相關性測量函數體現了圖像線特征間潛在的關系。為了能夠利用這些信息來確定圖像特征的匹配進而實現三維場景的重建，本文又引入了一種雙向權值匹配方法，并將這種方法與圖像線特征的相關性測量方法相結合來解決圖像線特征的匹配問題。

2.1 基于圖像線特征相關性的無向帶權二分圖的構建

在三幅圖I1、I2、I3中選定一組線特征lα、lβ、lχ可以用如下方法構建兩個無向加權圖G1=(V1，E1)和G2=(V2，E2)。首先，創建兩個頂點集合V1和V2，使得V1=I1∪I2，V2=I2∪I3；然后，對于在三個圖中任何一個可行的線匹配lα、lβ、lχ（每一個線特征出自一幅圖中）產生一些邊e1αβ∈E1，

e2βχ∈E2，這些邊的權值等于由公式計算出來sfl(lα，lβ，lχ)的數值，如ω(e1αβ)=ω(e2βχ)=sfl(lα，lβ，lχ)。由此可以得到兩幅無向加權圖G1和G2，這兩幅圖中包含了三幅圖像中所有的線特征組和它們可能存在的匹配。顯然，由于在同一幅圖中的兩個線特征無法被連接，由上述規則所構建的圖G1和G2是一個帶權二分圖。

在構建帶權二分圖的過程中，由于圖像線段的破碎性使得在任意一幅圖像中同樣的兩個節點間可能存在著多重競爭邊，這樣給帶權二分圖的構建帶來了一些困難。例如，在三個圖像中分別存在的線片斷lα、lβ、lχ之間可能存在著一種匹配；與此同時，在線段lα、lβ、l′χ也可能存在著另一種匹配。表面上看來是需要lα、lβ的兩條邊，一條邊的權值由sfl(lα，lβ，lχ)所確定，另一條邊的權值由sfl(lα，lβ，l′χ)所確定。因此，在實際操作中，可以采取一些措施來避免這類細小的沖突，具體方法是在創建帶權二分圖時，如果兩個節點的邊已經存在，那么新的權值就不必加入；否則就加入新的權值。

由帶權二分圖的相關概念可知，對于任意線片斷組lα、lβ、lγ，在二分圖G1中的點lα、lβ之間存在權值e1αβ，在第二個二分圖中，G2的點lβ、lγ之間存在權值e2βχ。在理想情況下，如果這組圖像線是完全匹配的，那么它們的ω(e1αβ)和ω(e2βχ)應當等于最大權值數1。這樣，在最終的匹配決定過程中，只需要確定權值為1的邊數即可確定圖像匹配的總數，即匹配的規模。然而在實際操作的過程中，由于一些錯誤（相機拍攝角度錯誤、圖像點或線位置的選取錯誤等）會造成權值ω(e1αβ)、ω(e2αβ)小于1的情況，這時，可視具體情況來判別圖像線特征組是否匹配。

另一方面，由圖表理論可以證明，在一個給定的無向圖中，匹配集合M是邊E的子集，即ME。對于一個節點v∈V來說，如果M集合中的一些邊經過v，則說點v存在著匹配點，反之則稱v不匹配。本文所研究的最大權值匹配是一個匹配集合Mω，Mω中所有邊的權值和大于其他任一個匹配集合中邊的權值之和。因此，確定圖像線特征匹配的問題可以用二分圖中的最大權值匹配法來解決。

3.2 最大權值二分匹配的求解

在帶權二分圖中求解權值匹配的問題是一個比較復雜的過程，但就其求解思想來說，則是集合論中一個比較普遍的算法，即從一個空集開始，在一定規則下反復迭代，最終找到目標集合。

假設給定一個帶權二分圖G=(V，E)，一個匹配集合M如圖1(a)所示，設M中的邊(1，a)、(2，b)、(3，c)、（4，e）是相匹配的；邊(4，d)和(5，e)是不匹配的。在這個二分圖G中，若有一條簡單路徑，其起點與終點不匹配，且其中所包含的邊有的在M中、有的在E-M中，則稱這條簡單路徑為關于匹配M的增廣路徑（augmenting path）。如圖1（b）所示，路徑p＝{(5，e)，(4，e)，(4，d)}是增廣路徑，它的起點和終點d、5是不匹配的，其邊（5，e）在集合E-M中，（4，e）在集合M中。

令p代表一個關于匹配M的增廣路徑，P表示p中所有的邊的集合，MP稱為集合M和P的對稱差。對于MP而言，它也表示一個集合，這個集合中的元素是只存在于集合M或P，即MP=(M-P)∪(P-M)。MP有如下性質：

a)它是一種匹配；

b)|MP|=|M|+1。

在圖1(c)中表示了MP的對稱差，即MP={（1，a），(2，b)，(3，c)，(4，e)，(5，d)}，并且|MP|=4+1=5。

對一個給定的匹配集合M，它的所有權值和可定義為ω(M)=e∈Mω(e)，令M′表示一個邊的集合；權值的增量ΔM′為在集合M′中不匹配的邊的總權值減去匹配邊的總權值，即ΔM′=ω(M′-M)-ω(M′∩M)。從ΔM′的定義中可知，對關于匹配M的增廣路徑p，可設ΔP表示在增廣p之后匹配權值網絡的變化，即ω(MP)=ω(M)+ΔP。

為了構建一個最大權值匹配，通常使用一種迭代的算法，即先設定一個空匹配集合M，對M進行迭代。在每一次迭代過程中，如果發現一個具有最大權值增量ΔP的增廣路徑p時，就將p加入匹配集合M；重復這一迭代過程，直到不存在關于M的增廣路徑為止。可以證明，反復使用這種基于最大權值增量的增廣路徑迭代算法可以得到最大權值匹配集合Mw。另一方面，由增廣路徑的定義可知，任一條增廣路徑都存在著一對不匹配的節點作為該路徑的起點和終點，這對不匹配的節點分別在左圖和右圖中。因此，當在帶權二分圖G中搜索關于匹配M的增廣路徑p時，一般從一幅圖像中的未匹配節點開始構建增廣路徑，即用一種廣度優先的方式從左圖中未匹配的節點來搜索所有可能的路徑，以此來找到合適的增廣路徑。

2.3 匹配算法

通過以上的分析可知，對于圖像的線特征匹配和重建步驟如下：

a）計算圖像線段l1、l2、l3的一個虛交線。

b）用式（2）來計算l1、l2、l3的sfl(l1，l2，l3)值。

c）設定一個閾值，當sfl(l1，l2，l3)的值小于這個閾值時，該線段組將被去除。

d）構建帶權二分圖G1=(V1，E1)和G2=(V2，E2)。

e）在G1和G2中找到最大權值匹配Mw。

f）從最大匹配Mw中確定圖像點的匹配和它們相應的3D線。

本文所研究的圖像點特征的匹配與重建的流程如圖2所示。

3 實驗結果

本文提出的算法已經在實際中得到了驗證，應當指出的是，只有利用好的三維重建算法才能夠通過三角測量法得到精確的3D線段，繼而得到很好的重建效果。本文采用了Cheng等人[1]的三維重建算法，這種算法計算效率高、抗噪聲能力強，能夠很好地配合本文提出的圖像線特征的匹配算法。在算法的實際操作過程中，是從三幅圖像中抽取線段作為輸入，計算圖像線特征的匹配性并利用三角法測量出的相應3D線段作為輸出。

本文所設計的實驗中，實際圖像從Cannon PowerShot A620數碼照相機（2 048×1 536）獲得，相機的各項參數和位置已知。根據獲得的實驗結果，本文利用三角測量的方法得到圖像線特征的各項數據（方向向量、線段長度）與真實值相比較，從而驗證本算法的有效性。

通過分析所獲得的數據可以證明，由于采取了合適的規則進行篩選，剔除誤匹配，從而使算法的魯棒性得到了增強，即使在圖像質量比較差的情況下，也能達到比較高的正確匹配率。實驗結果表明平均正確匹配率已達到了90％以上，且抗干擾能力強，方向和長度的誤差都在設定范圍以內。尤其是在目標物體形狀比較規則且選取的特征線在物體的棱線附近時，匹配和重建精度更高。圖3所示的是測試所用的三幅圖像，圖中標示出測試所用的像線段，共計六組特征。依據本文所提出的算法所計算出的像點對特征所對應的3D線段與真實3D線段的數據比較如表1所示。

表1 三維重建結果與實際數據比較表

序號

實際的3D線段

uxuyuz

mxmymz

計算得出的3D線段

uxuyuz

mxmymz

11.00-0.00-0.001.00-0.020.10

-0.00-7.039.01-1.05-6.719.10

20.001.000.000.060.99-0.16

11.280.002.9412.63-0.093.44

30.001.000.080.021.000.94

11.850.000.0012.24-0.310.20

40.000.001.000.120.971.20

-5.020.000.00-4.50-1.650.62

50.00-0.021.00-0.01-0.011.00

-5.020.000.00-4.840.35-0.04

60.00-0.031.000.02-0.041.00

-5.34-0.00-0.00-5.490.090.12

4 結束語

本文所提出的這種基于圖像線特征相關性的匹配算法，采用了利用帶權二分圖求取最大匹配的方法，從而準確地進行了圖像線特征的3D坐標的計算和三維重建，改進了傳統的基于極線約束的圖像特征匹配的方法僅僅從2D角度衡量圖像特征的相關性而忽視3D信息的獲取問題。利用圖像線特征的相關性計算與通過帶權二分圖獲取最大匹配方法的結合，可以方便、可靠地實現圖像間線特征的匹配，從而使得圖像的三維重建變得更加容易，重建結果更加精確。實驗結果表明本文算法對于規則形狀的物體既有非常高的正確匹配率，又有很高的三維重建精度，能夠滿足實際工作和研究領域三維重建的需要，得到了比較好的效果，結果令人滿意。

參考文獻：

［1］

CHENG Y Q，WANG X G.Three-dimensional reconstruction of points and lines with uknown correspondence across Images[J].Internatio-nal Journal of Computer Vision，2001，45(2)：129-156.

[2]陳棣湘，羅飛路，潘孟春.立體視覺測量中的圖像匹配策略研究[J].光學技術，2002，28（5）：392-394.

[3]陳志堅，李哲，石磊.一種基于圖像特征塊匹配的電子穩像算法[J]. 科學技術與工程，2007，7（11）：2512-2515.

[4]JOHNSON D S，McGEOCH C C.Network flows and matching:first DIMACS implementation challenge[M].Boston:American Mathematical Society，1993.

［5］ 孟晉宇，舒華忠，鮑旭東.基于形狀的二維灰度圖像插值[J].中國圖象圖形學報，2003，8（3）：311-316.

[6]舒遠，談正，丁禮儒.基于高精度匹配點的對極幾何估計[J]. 工程圖學學報，2005，26（5）：89-92.

[7]童宇，蔡自興. 基于特征匹配的全景圖的生成[J].華中科技大學學報：自然科學版，2004，32（增刊）：77-79.

[8]汪偉，李郝林.基于數碼相機圖像的三維重構[J].上海理工大學學報，2005，27（5）：429-432.

[9]王長海.雙目視覺配準的最優視差連續塊算法[D].西安：西安電子科技大學，2006.

[10]王莉莉，劉嶸.基于圖像的幾何三維重建方法[J].系統仿真學報，2001，13（增刊）：81-85.

[11]向登寧，鄧文怡，燕必希，等.利用極線約束方法實現圖像特征點的匹配[J].北京機械工業學院學報，2002，17（4）：21-25.

[12]楊敏，沈春林.基于對極幾何約束的景象匹配研究[J].南京航空航天大學學報，2004，36（2）：235-239.

[13]楊敏，沈春林.基于場景幾何約束未標定兩視圖的三維模型重建[J].中國圖象圖形學報，2003，8（8）：872-876.

[14]張維中，張麗艷，王曉燕，等.基于標記點的圖像特征匹配的魯棒算法[J].中國機械工程，2006，17（22）：2415-2418.

[15]朱惠萍，黃全義.基于普通數碼相機的核線相關方法[J].測繪信息與工程，2002，27（6）：29-30.