盧 俊，張保明，郭海濤，張宏偉

信息工程大學(xué)地理空間信息學(xué)院，河南 鄭州450052

1 引 言

基于無(wú)序多視影像的場(chǎng)景三維重建已經(jīng)是攝影測(cè)量和計(jì)算機(jī)視覺(jué)領(lǐng)域中的一個(gè)熱點(diǎn)問(wèn)題，重建算法總體上可以分為增量法［1－3］和全局法［4－8］，如果沒(méi)有足夠的先驗(yàn)知識(shí)，一般情況下都需要匹配所有可能的像對(duì)，但由于場(chǎng)景的模糊或者不同場(chǎng)景中存在重復(fù)的紋理，兩視匹配可能會(huì)產(chǎn)生錯(cuò)誤的對(duì)極幾何關(guān)系（epipolar geometry，EG），并且誤判的對(duì)極幾何關(guān)系可能直接造成重建模型的變形甚至發(fā)生漂移現(xiàn)象［1］。

影像集中像對(duì)間的對(duì)極幾何關(guān)系構(gòu)成一個(gè)影像關(guān)系圖G（V，E），其中V代表頂點(diǎn)集，E代表邊集，圖中的每一個(gè)頂點(diǎn)代表一張影像，如果頂點(diǎn)i和頂點(diǎn)j之間存在足夠多的同名像點(diǎn)，則i和j的連線(xiàn)構(gòu)成G的一條邊，每條邊可以通過(guò)對(duì)應(yīng)影像間的相對(duì)方位關(guān)系來(lái)表達(dá)（即兩張影像間的旋轉(zhuǎn)矩陣Rij），誤匹配會(huì)在G中產(chǎn)生很多誤判的邊（即計(jì)算得到錯(cuò)誤的相對(duì)方位關(guān)系）。文獻(xiàn)［9］提出一種像方特征點(diǎn)和物方平面元集成的多視影像密集匹配方法，利用多視影像上特征點(diǎn)投影范圍和平面元位置的制約關(guān)系，實(shí)現(xiàn)特征點(diǎn)和平面元的同時(shí)匹配，可以有效解決影像匹配中由于重復(fù)紋理、斷裂特征等引起的錯(cuò)誤匹配，提高匹配的可靠性。文獻(xiàn)［10］提出一種像方和物方信息相結(jié)合的多影像匹配方法，利用分層匹配策略，對(duì)各立體像對(duì)的匹配結(jié)果進(jìn)行物方融合，能剔除掉部分誤匹配點(diǎn)，但這些算法需要利用影像間空間關(guān)系的先驗(yàn)信息，在沒(méi)有任何先驗(yàn)知識(shí)的前提下并不適用。文獻(xiàn)［11］將貝葉斯抽樣一致性檢驗(yàn)引入SIFT特征匹配，能有效提高匹配的正確率和效率，但對(duì)整體滿(mǎn)足局部一致性的誤匹配沒(méi)有效果。文獻(xiàn)［12—13］利用RANSAC引擎隨機(jī)采樣圖G的生成樹(shù)，通過(guò)遍歷生成樹(shù)計(jì)算對(duì)應(yīng)邊的全局旋轉(zhuǎn)矩陣，然后利用非樹(shù)邊構(gòu)回路，通過(guò)量測(cè)非樹(shù)邊的相對(duì)旋轉(zhuǎn)矩陣與全局旋轉(zhuǎn)矩陣的差異來(lái)檢測(cè)錯(cuò)誤邊，這種算法只能確定到一個(gè)回路中是否存在誤判的邊，無(wú)法直接定位到回路中存在誤判邊的具體位置，并且它屬于隨機(jī)抽樣算法，受制于假設(shè)樣本空間的大小和G的空間結(jié)構(gòu)。文獻(xiàn)［14］首先提取G的最大生成樹(shù)，然后量測(cè)非樹(shù)邊構(gòu)成的回路中所有邊對(duì)應(yīng)旋轉(zhuǎn)矩陣的乘積與單位陣的差異來(lái)檢測(cè)環(huán)路中幾何關(guān)系的一致性，但這些方法都過(guò)于依賴(lài)生成樹(shù)的結(jié)構(gòu)，如果生成樹(shù)本身存在錯(cuò)誤，則可能會(huì)給出錯(cuò)誤的檢測(cè)結(jié)果。

對(duì)于多視影像，利用所有的像對(duì)進(jìn)行相對(duì)定向會(huì)產(chǎn)生很多附加信息，利用這些信息可以檢驗(yàn)影像間幾何關(guān)系的一致性，這在本質(zhì)上相當(dāng)于從帶噪聲污染的數(shù)據(jù)集中檢測(cè)噪聲的具體位置。本文首先將噪聲檢測(cè)轉(zhuǎn)換成概率推論問(wèn)題，通過(guò)圖G中的回路約束和像對(duì)匹配過(guò)程中獲得的先驗(yàn)信息構(gòu)建概率圖模型，然后利用置信傳播算法（belief propagation，BP）直接確定誤判相對(duì)方位關(guān)系的位置。

2 多視影像相對(duì)方位關(guān)系的概率圖模型

對(duì)無(wú)序影像集V，由于缺少影像間空間關(guān)系的先驗(yàn)信息，本文首先利用SIFT特征匹配算法［15］匹配所有可能的像對(duì)，然后在RANSAC引擎下利用五點(diǎn)算法［16］計(jì)算像對(duì)間的相對(duì)方位，并剔除外點(diǎn)（文中外點(diǎn)指無(wú)法適應(yīng)RANSAC假設(shè)模型的匹配點(diǎn)，而內(nèi)點(diǎn)指滿(mǎn)足RANSAC假設(shè)模型的匹配點(diǎn)），如果通過(guò)RANSAC檢測(cè)之后獲得的匹配點(diǎn)對(duì)數(shù)量過(guò)少，則認(rèn)為這兩張影像不相關(guān)，對(duì)任意相關(guān)的兩張影像vi和vj，計(jì)算出的旋轉(zhuǎn)矩陣Rij構(gòu)成一種估算的相對(duì)方位關(guān)系，但這種關(guān)系并不一定可靠，如圖1，兩張影像分別對(duì)應(yīng)公寓的左右兩側(cè)，屬于不同的場(chǎng)景，沒(méi)有重疊部分，但可以獲得51對(duì)匹配像點(diǎn)，這可能會(huì)給出錯(cuò)誤的相對(duì)方位關(guān)系。

圖1 紋理重復(fù)造成場(chǎng)景的誤匹配Fig.1 Mismatches caused by repeated texture

以二值變量?i表示E中第i條邊ei對(duì)應(yīng)兩張影像間相對(duì)方位關(guān)系的正確性，將正確的相對(duì)方位關(guān)系記為?i＝1，誤判的相對(duì)方位關(guān)系記為?i＝0。由于這種誤判的相對(duì)方位關(guān)系滿(mǎn)足局部一致性，僅僅利用兩張影像本身的信息很難檢測(cè)其正確性，但誤判的相對(duì)方位關(guān)系不具備全局一致性，利用其他附加的信息可以對(duì)其進(jìn)行檢測(cè)。

2.1 基于回路約束的概率圖模型

對(duì)影像集對(duì)應(yīng)的關(guān)系圖G（V，E），如果邊集E中存在回路，在沒(méi)有誤判的前提下，將回路中所有邊對(duì)應(yīng)的旋轉(zhuǎn)矩陣順序相乘應(yīng)該等于單位陣。假設(shè)G中的某個(gè)回路為C＝（e1，e2，…，ek），則理論上存在

式中，I表示單位陣。但由于影像中噪聲的存在以及數(shù)值計(jì)算中的舍入誤差等影響，RC與單位陣I之間會(huì)存在一定的差異，本文以ΔRC來(lái)表示RC與I之間的差異，如果ΔRC過(guò)大，則認(rèn)為回路C中至少有一條邊存在誤判，反之則認(rèn)為C中所有的邊都滿(mǎn)足正確的相對(duì)方位關(guān)系。以變量?C表示整個(gè)回路上的相對(duì)方位關(guān)系，記?C＝min（?1，?2，…，?k），顯然，?C＝0表示回路中至少有一條邊存在誤判。

圖2表示4張影像構(gòu)成的關(guān)系圖，圖中包含6條邊、5個(gè)回路。

圖2 4張影像構(gòu)成的關(guān)系圖Fig.2 Relation graph composed of 4images

ΔRC的取值與回路中所有邊對(duì)應(yīng)的?相關(guān)，以表示在整個(gè)回路相對(duì)方位關(guān)系為?C的條件下ΔRC發(fā)生的概率。同樣，邊ei對(duì)應(yīng)的旋轉(zhuǎn)矩陣與其對(duì)應(yīng)的相對(duì)方位關(guān)系?i也存在一定的內(nèi)部聯(lián)系，記在相對(duì)方位關(guān)系?i的條件下發(fā)生的概率為，于是可以將關(guān)系圖G（V，E）轉(zhuǎn)換成貝葉斯網(wǎng)絡(luò)，圖3表示與圖2對(duì)應(yīng)的貝葉斯網(wǎng)絡(luò)，箭頭方向代表概率依賴(lài)關(guān)系，每一個(gè)回路C對(duì)應(yīng)的ΔRC節(jié)點(diǎn)依賴(lài)于構(gòu)成其回路的所有邊對(duì)應(yīng)的?節(jié)點(diǎn)。

圖3 貝葉斯網(wǎng)絡(luò)Fig.3 Bayes network

貝葉斯網(wǎng)絡(luò)是描述特征之間因果關(guān)系的有向無(wú)環(huán)圖（DAG），由節(jié)點(diǎn)和表示因果關(guān)系的有向邊組成，每一條邊都由父節(jié)點(diǎn)指向子節(jié)點(diǎn)，表示節(jié)點(diǎn)間的概率依賴(lài)關(guān)系，每一個(gè)節(jié)點(diǎn)都代表一個(gè)變量，對(duì)應(yīng)一個(gè)條件概率表（CPT），表示子節(jié)點(diǎn)在父節(jié)點(diǎn)取值下的條件概率，若某個(gè)節(jié)點(diǎn)不包含父節(jié)點(diǎn)，則其條件概率為其先驗(yàn)概率分布。記a（v）為節(jié)點(diǎn)v的父節(jié)點(diǎn)集，則貝葉斯網(wǎng)絡(luò)可以表示為一個(gè)概率分布函數(shù)

如果a（vi）＝φ（即節(jié)點(diǎn)vi沒(méi)有父節(jié)點(diǎn)），則記，于是圖3對(duì)應(yīng)的概率分布為

式中，x為節(jié)點(diǎn)Re的個(gè)數(shù)；y為節(jié)點(diǎn)ΔRC的個(gè)數(shù)（即關(guān)系圖G中的回路數(shù)）；z為節(jié)點(diǎn)?的個(gè)數(shù)。由于G中每條邊e對(duì)應(yīng)的旋轉(zhuǎn)矩陣Re只與構(gòu)成該條邊的兩張影像相關(guān)，所以概率圖中x＝z。

2.2 回路構(gòu)建

圖G（V，E）中的每一個(gè)回路都包含一個(gè)旋轉(zhuǎn)矩陣乘積閉合約束，理論上窮舉G中的所有回路得出的計(jì)算結(jié)果最可靠，但在圖形較為復(fù)雜的情況下很難構(gòu)建所有的回路，本文利用生成樹(shù)算法構(gòu)建圖G中的部分回路。

生成樹(shù)是指圖G中包含所有頂點(diǎn)，但沒(méi)有回路的聯(lián)通子圖，影像關(guān)系圖中一般以每條邊對(duì)應(yīng)兩張影像的匹配點(diǎn)對(duì)數(shù)量作為該邊的權(quán)值，最大（小）生成樹(shù)為權(quán)重之和最大（?。┑纳蓸?shù)，理論上最大生成樹(shù)是關(guān)系圖中最穩(wěn)健的生成樹(shù)［14］。本文首先對(duì)G中的每條邊e賦權(quán)值w（e）。w（e）為這條邊對(duì)應(yīng)兩幅圖像的匹配點(diǎn)數(shù)量的倒數(shù)，于是得到一個(gè)新的帶權(quán)關(guān)系圖G，很明顯G的最小生成樹(shù)即為G的最大生成樹(shù)。然后利用貪心算法［17］計(jì)算G的最小生成樹(shù)：假設(shè)G中頂點(diǎn)數(shù)為n，T＝（U，Ew）為G的最小生成樹(shù)，首先置U的初值等于V（即包含有G中的全部頂點(diǎn)），Ew的初值為空集，將圖G中的邊按權(quán)值從小到大的順序依次選取，若選取的邊未使生成樹(shù)T形成回路，則加入Ew；否則舍棄，直到Ew中包含（n－1）條邊為止，便獲得了G的最小生成樹(shù)T，而T即是G的最大生成樹(shù)。

圖4是構(gòu)建最大生成樹(shù)的一個(gè)示意圖，每條邊上的數(shù)值代表其對(duì)應(yīng)兩個(gè)頂點(diǎn)間匹配點(diǎn)對(duì)的數(shù)量，實(shí)線(xiàn)部分代表生成樹(shù)，G中每一條生成樹(shù)之外的邊與生成樹(shù)中的部分邊產(chǎn)生一個(gè)回路，并且這個(gè)回路的路徑是唯一的。同時(shí)本文利用窮舉法構(gòu)建所有三元視圖組的回路，在影像集的所有n張影像中隨機(jī)取3張，如果其中任意兩張影像都相關(guān)，則其構(gòu)成一個(gè)回路。依據(jù)本文的方法，圖4中包含9個(gè)回路（非樹(shù)邊6個(gè)，三元視圖組6個(gè)，減去重復(fù)的3個(gè)三元視圖組回路）。

圖4 最大生成樹(shù)Fig.4 Maximum spanning tree

2.3 貝葉斯網(wǎng)絡(luò)中的先驗(yàn)概率

本文的目的是推導(dǎo)關(guān)系圖G（V，E）中所有邊對(duì)應(yīng)相對(duì)方位關(guān)系的正確性，通過(guò)貝葉斯網(wǎng)絡(luò)將其轉(zhuǎn)換成了一個(gè)最大后驗(yàn)概率（maximum a posteriori，MAP）的求解問(wèn)題，即確定貝葉斯網(wǎng)絡(luò)中所有?k節(jié)點(diǎn)的值以最大化公式（3），這種概率推論問(wèn)題并不一定需要計(jì)算出嚴(yán)格的分布函數(shù)，只需要式（3）中的因式符合正確的分布趨勢(shì)。

貝葉斯網(wǎng)絡(luò)中節(jié)點(diǎn)?k的取值代表其對(duì)應(yīng)的兩張影像相對(duì)方位關(guān)系的正確性，可以取0和1，在沒(méi)有任何先驗(yàn)信息的前提下，節(jié)點(diǎn)?k取0和1的概率是相等的，都為1/2。

如果這兩張影像的相對(duì)方位關(guān)系存在誤判，即?i＝0，則在這兩張影像上匹配同名像點(diǎn)屬于偶然事件，假設(shè)這種偶然事件發(fā)生的概率為p0，同樣可以認(rèn)為誤判的幾何關(guān)系下，條件概率服從二項(xiàng)分布B（Nlr，p0），即

誤判條件下匹配成功的概率應(yīng)該遠(yuǎn)小于正確對(duì)極幾何關(guān)系的匹配成功的概率，本文取經(jīng)驗(yàn)值p1＝0.1，p0＝0.001。

在回路Cj中所有邊的相對(duì)方位都不存在誤判時(shí)，理論上引起與單位陣差異的因素是噪聲和計(jì)算的舍入誤差，這種影響不會(huì)造成的巨大偏移，文獻(xiàn)［18］在大量樣本統(tǒng)計(jì)的基礎(chǔ)上，得出環(huán)路中的角度閉合差在不存在誤判的條件下大致服從指數(shù)分布，即

式中，ΔRCj以度表示；參數(shù)λ取固定值0.5；文獻(xiàn)［18］中所有環(huán)路中的邊數(shù)量都限制在6條以?xún)?nèi)，而ΔRCj與回路Cj中邊的數(shù)量有關(guān)，邊越多，可能產(chǎn)生的累積誤差就越大，即在回路中是否存在誤判的推論與回路的長(zhǎng)度有關(guān)。文獻(xiàn)［14］證明在大影像集中限制環(huán)路的長(zhǎng)度可能導(dǎo)致部分誤判邊無(wú)法被檢測(cè)出來(lái)，并且回路角度閉合差與環(huán)路長(zhǎng)度的算術(shù)平方根大致成正比關(guān)系，假設(shè)回路Cj中邊的數(shù)量為L(zhǎng)，本文試驗(yàn)中取經(jīng)驗(yàn)值即滿(mǎn)足概率函數(shù)的均值為

如果回路Cj中存在誤判的對(duì)極幾何關(guān)系，旋轉(zhuǎn)矩陣的累積誤差可能在［0，π］上取任意值，所以ΔRCj服從［0，π］上的均勻分布，即

3 基于置信傳播的相對(duì)方位關(guān)系推論

相對(duì)方位關(guān)系檢測(cè)實(shí)際上就是在貝葉斯網(wǎng)絡(luò)中確定所有vi節(jié)點(diǎn)的取值，在已知先驗(yàn)概率分布的前提下，本文利用置信傳播算法來(lái)解算貝葉斯網(wǎng)絡(luò)中的概率推論問(wèn)題。置信傳播算法是20世紀(jì)80年代初提出的一種高效的消息傳播推論算法［19］，文獻(xiàn)［20］最先在編碼領(lǐng)域建立置信傳播算法與貝葉斯網(wǎng)絡(luò)的聯(lián)系，文獻(xiàn)［21—22］在貝葉斯網(wǎng)絡(luò)中應(yīng)用置信傳播算法很好地解決了“turbo編碼”問(wèn)題，現(xiàn)在聯(lián)合使用置信傳播和貝葉斯網(wǎng)絡(luò)已經(jīng)是解決推論問(wèn)題的最重要手段之一。

與馬爾科夫隨機(jī)場(chǎng)（Markov random field，MRF）一樣，貝葉斯網(wǎng)絡(luò)是以因式分解形式來(lái)表示聯(lián)合概率分布，可以將其轉(zhuǎn)換成因子圖。因子圖是一個(gè)表示因式分解結(jié)構(gòu)的二分圖，對(duì)式（2）中的每一個(gè)因式引入一個(gè)函數(shù)節(jié)點(diǎn)，函數(shù)節(jié)點(diǎn)分別連接vi和其父節(jié)點(diǎn)集a（vi），圖5就是貝葉斯網(wǎng)絡(luò)（圖3）對(duì)應(yīng)的因子圖。

圖5 因子圖Fig.5 Factor graph

將因子圖中的每個(gè)節(jié)點(diǎn)vi與其對(duì)應(yīng)的函數(shù)節(jié)點(diǎn)P（vi｜a（vi））相關(guān)聯(lián)，構(gòu)成一個(gè)變量節(jié)點(diǎn)，并考慮貝葉斯網(wǎng)絡(luò)中的依賴(lài)關(guān)系，可以將因子圖轉(zhuǎn)換成為置信網(wǎng)絡(luò)。設(shè)節(jié)點(diǎn)vi對(duì)應(yīng)的節(jié)點(diǎn)變量為x，記父節(jié)點(diǎn)向子節(jié)點(diǎn)傳遞的消息記為πc（p），子節(jié)點(diǎn)向父節(jié)點(diǎn)傳遞的消息記為λc（p），其中p代表父節(jié)點(diǎn)，c代表子節(jié)點(diǎn)。如圖6表示置信傳播中節(jié)點(diǎn)?2對(duì)應(yīng)的消息傳遞方式，圖中每一個(gè)虛線(xiàn)框代表一個(gè)變量節(jié)點(diǎn)。

圖6 置信傳播中的消息傳遞Fig.6 Messages sent in belief propagation

節(jié)點(diǎn)vi向其任意一個(gè)父節(jié)點(diǎn)a∈a（vi）傳遞的消息為

vi向其任意一個(gè)子節(jié)點(diǎn)d∈d（vi）傳遞的消息為

式中，a（x）＼｛a｝表示集合a（x）中除a外的元素；d（x）＼｛d｝表示集合d（x）中除d外的元素；代表函數(shù)f的第i個(gè)變量取xi時(shí)的邊緣概率［23］，如

式中，A1和A3分別代表x1和x3的值域。

置信網(wǎng)絡(luò)中沒(méi)有有向環(huán)，但卻可能包含無(wú)向環(huán)，如圖5中的?1－Δ1－?2－Δ2－?1，消息可能在環(huán)路中無(wú)限傳播。環(huán)路置信傳播算法（loopy belief propagation，LBP）可以很好地解決這個(gè)問(wèn)題［23—24］。LBP算法的主要思想是讓消息在置信網(wǎng)絡(luò)中迭代傳播，直到獲得穩(wěn)定的置信度。在第t次迭代中，計(jì)算所有子節(jié)點(diǎn)向節(jié)點(diǎn)vi傳送的消息

所有父節(jié)點(diǎn)向vi傳送的消息

第t次迭代中x的置信度為

在第t＋1次迭代中，任意節(jié)點(diǎn)vi向其父節(jié)點(diǎn)a發(fā)送的消息為

向其子節(jié)點(diǎn)d發(fā)送的消息為

置信網(wǎng)絡(luò)中的消息是并行傳播的，每一次迭代中節(jié)點(diǎn)vi發(fā)出的消息都基于上次迭代中其向所有鄰域接收的消息，如果所有節(jié)點(diǎn)在連續(xù)兩次迭代中的置信度差值都小于一個(gè)閾值，則稱(chēng)置信網(wǎng)的消息收斂，即取使節(jié)點(diǎn)vi置信度最大的標(biāo)簽值x＊作為該節(jié)點(diǎn)變量的值。環(huán)路置信傳播在絕大多數(shù)情況下都能達(dá)到收斂，不收斂時(shí)經(jīng)過(guò)多次迭代之后能提供一個(gè)很好的近似［24］。

4 試驗(yàn)結(jié)果

本文對(duì)多組影像集進(jìn)行了試驗(yàn)，這里選取其中的5組，圖7（a）—（e）分別為公寓、平房、天壇、Kapel、Providence影像集中的部分影像，其中公寓和平房影像集為定焦拍攝，Kapel影像集為牛津大學(xué)提供的公開(kāi)測(cè)試數(shù)據(jù)，Providence影像集為美國(guó)Providence部分地區(qū)無(wú)人機(jī)影像測(cè)試數(shù)據(jù)。

圖7 影像集Fig.7 Image sets

試驗(yàn)中首先利用SIFT特征匹配算法對(duì)影像集中所有的像對(duì)進(jìn)行匹配，將匹配點(diǎn)對(duì)數(shù)量不少于16的像對(duì)列為相關(guān)影像，將所有的相關(guān)影像相連構(gòu)建原始的影像關(guān)系圖G，如圖8（a）—（e）的左一圖。對(duì)任意兩張相關(guān)影像（i，j），在RANSAC引擎中利用五點(diǎn)算法計(jì)算像對(duì)的本質(zhì)矩陣（包括旋轉(zhuǎn)矩陣Rij和位移向量tij），以影像寬或高中較大值（單位為像素）的0.5%作為內(nèi)點(diǎn)的閾值，取內(nèi)點(diǎn)最多的一組樣本為最佳樣本，如果其中內(nèi)點(diǎn)數(shù)量少于16或者內(nèi)點(diǎn)率小于50%（內(nèi)點(diǎn)數(shù)量少于初始匹配點(diǎn)數(shù)的一半），則認(rèn)為像對(duì)不相關(guān)。在G中將所有RANSAC檢測(cè)出的不相關(guān)像對(duì)的對(duì)應(yīng)邊剔除，構(gòu)成新的影像關(guān)系圖G′，如圖8（a）—（e）的左二圖。然后利用本文的檢測(cè)算法對(duì)G′中的相對(duì)方位關(guān)系進(jìn)行檢測(cè)。最后剔除G′中檢測(cè)出的誤判相對(duì)方位關(guān)系并對(duì)影像集進(jìn)行三維場(chǎng)景重建，并將重建結(jié)果與部分現(xiàn)有的重建算法進(jìn)行對(duì)比，以檢驗(yàn)本文算法的有效性。

試驗(yàn)中將置信網(wǎng)絡(luò)中所有消息都初始化為1，由于理論上環(huán)路置信傳播算法并不能保證收斂，本文試驗(yàn)中將迭代次數(shù)設(shè)置為100，迭代的置信度限差的閾值設(shè)置為10－6，如果連續(xù)兩次迭代中置信度之差小于閾值便停止迭代。為了提高檢測(cè)的可靠性，本文在試驗(yàn)中使用迭代檢測(cè)方法，每次迭代中首先利用LBP算法檢測(cè)誤判邊，然后在影像關(guān)系圖中將誤判邊剔除，接下來(lái)在新獲得的影像關(guān)系圖中再次利用LBP算法進(jìn)行檢測(cè)，直到獲得穩(wěn)定的影像關(guān)系圖為止。

本文的5組試驗(yàn)中都在2次LBP迭代內(nèi)便獲得了穩(wěn)定的影像關(guān)系圖。圖8（a）—（e）左二圖中的紅色部分代表第一次LBP檢測(cè)出的誤判邊，圖8（a）—（e）左三圖是剔除第一次LBP檢測(cè)誤判邊之后新的影像關(guān)系圖，其中藍(lán)色部分為第二次LBP檢測(cè)出的誤判邊，圖8（a）—（e）左四圖是利用文獻(xiàn)［14］中算法檢測(cè)誤判邊后得到的最終影像關(guān)系圖。

圖9（a）—（e）中的左圖為增量法［1］得到的重建結(jié)果，增量法［1］沒(méi)有使用誤判邊檢測(cè)（本文中誤判邊指滿(mǎn)足局部一致性，但不滿(mǎn)足全局一致性的邊），中圖為利用本文算法剔除誤判邊后的重建結(jié)果，右圖為文獻(xiàn)［14］算法得到的重建結(jié)果，這3種算法中都使用了RANSAC檢測(cè)。從試驗(yàn)結(jié)果可以看出，誤判的相對(duì)方位關(guān)系對(duì)重建結(jié)果產(chǎn)生了很大的影響。增量法［1］中公寓、平房、Kapel和Providence的重建結(jié)果都發(fā)生了明顯的漂移現(xiàn)象，天壇影像集重建結(jié)果雖然沒(méi)有明顯的漂移，但有部分場(chǎng)景無(wú)法得到重建，原因是重建過(guò)程中每張影像的射影矩陣是在RANSAC引擎下計(jì)算的，部分誤判的邊能通過(guò)檢測(cè)，從而得到錯(cuò)誤的空間結(jié)構(gòu)，如公寓、平房、Kapel和Providence影像集（特別是Providence影像集，其中只有少量的誤判邊，但對(duì)重建結(jié)果卻產(chǎn)生了很大的影響），但當(dāng)這些通過(guò)RANSAC檢測(cè)的誤判邊處于影像集中的弱連接處時(shí)，即使少量計(jì)算錯(cuò)誤的空間點(diǎn)坐標(biāo)也可能會(huì)導(dǎo)致新加入的影像無(wú)法通過(guò)RANSAC檢測(cè)，從而大量的影像將會(huì)被排除，如天壇影像集，實(shí)際參與重建的僅僅有48張影像。文獻(xiàn)［14］算法對(duì)部分影像集的重建結(jié)果相比增量法［1］有較大改進(jìn)（如公寓、天壇和Providence影像集），其中Providence影像集與本文的檢測(cè)和重建結(jié)果幾乎一致（差異可能源于計(jì)算過(guò)程中部分閾值的設(shè)定不同），但公寓和平房影像集發(fā)生了漂移（圖9（a）和（b）的右圖），天壇和 Kapel影像集只有部分場(chǎng)景完成重建（圖9（c）和（d）的右圖，原因是其對(duì)應(yīng)的影像關(guān)系圖被分割成了若干個(gè)不聯(lián)通的子圖，如圖8（c）和（d）的左四圖，而重建結(jié)果基于其中的最大聯(lián)通子圖）。本文算法則更加穩(wěn)健，從圖9中也可以看出利用本文算法能夠得到更可靠的重建結(jié)果。

圖8 相對(duì)方位關(guān)系檢測(cè)中的影像關(guān)系圖Fig.8 Image relation graphs in detection of relative orientation relations

表1對(duì)5組試驗(yàn)的結(jié)果進(jìn)行了統(tǒng)計(jì)。

表1 誤判邊檢測(cè)結(jié)果Tab.1 Detection results of false positive edges

圖9 剔除誤判邊前后的重建結(jié)果Fig.9 Reconstruction results without and with rejecting of false positive edges

通過(guò)以上試驗(yàn)可以發(fā)現(xiàn)，場(chǎng)景中的重復(fù)紋理可能會(huì)導(dǎo)致誤判的相對(duì)方位關(guān)系，造成場(chǎng)景重建失敗。增量法［1］由于沒(méi)有進(jìn)行誤判相對(duì)方位關(guān)系檢測(cè)，最容易產(chǎn)生錯(cuò)誤的重建結(jié)果。文獻(xiàn)［14］算法受影像關(guān)系圖結(jié)構(gòu)的影響較大，當(dāng)影像集的空間關(guān)系較為簡(jiǎn)單時(shí)，該算法能有效檢測(cè)出部分誤判相對(duì)方位關(guān)系，改善重建結(jié)果，但算法不夠穩(wěn)健，當(dāng)影像關(guān)系圖的最大生成樹(shù)中存在誤判邊時(shí)可能會(huì)給出錯(cuò)誤的檢測(cè)結(jié)果，從而導(dǎo)致重建結(jié)果發(fā)生漂移。從圖9中可以看出利用本文算法剔除誤判邊之后的重建結(jié)果得到明顯改善，這也證明了本文算法的有效性。從表1中也可以看出，一般情況下環(huán)路置信傳播算法經(jīng)過(guò)較少的迭代便能達(dá)到收斂，同時(shí)由于變量的標(biāo)簽空間很?。?的取值為0或者1），本文算法具有較高的計(jì)算效率。

5 結(jié)束語(yǔ)

本文利用全局一致性約束來(lái)檢測(cè)影像間的相對(duì)方位關(guān)系，除了利用文獻(xiàn)［14］中的最大生成樹(shù)構(gòu)建回路之外，還加入了三元視圖組回路約束，極大地降低了影像關(guān)系圖的結(jié)構(gòu)對(duì)檢測(cè)結(jié)果的影響，可以有效避免由于紋理重復(fù)或場(chǎng)景模糊而造成的誤匹配，進(jìn)而改善場(chǎng)景三維重建的效果。目前，直接利用影像信息來(lái)重建場(chǎng)景的應(yīng)用需求越來(lái)越廣泛，而大量場(chǎng)景中都存在重復(fù)紋理（特別是人工建筑物），因此本文提出的算法在相關(guān)領(lǐng)域?qū)⒕哂休^好的應(yīng)用前景。

［1］SNAVELY N，SEITZ S M，SZELISKI R.Modeling the World from Internet Photo Collections［J］.International Journal of Computer Vision，2008，80（2）：189－210.

［2］SNAVELY N，SEITZ S M，SZELISKI R.Skeletal Graphs for Efficient Structure from Motion［C］∥IEEE Conference on Computer Vision and Pattern Recognition.Anchorage，AK：IEEE，2008：1－8.

［3］AGARWAL S，F(xiàn)URUKAWA Y，SNAVELY N，et al.Building Rome in a Day［J］.Communications of the ACM，2011，54（10）：105－112.

［4］KAHL F.Multiple View Geometry and the L∞－norm［C］∥Tenth IEEE International Conference on Computer Vision.Beijing：IEEE，2005，2：1002－1009.

［5］SINHA S N，STEEDLY D，SZELISKI R.A Multi－stage Linear Approach to Structure from Motion［M］∥KUTULAKOS K N ed.Trends and Topics in Computer Vision.Berlin：Springer，2012：267－281.

［6］ARIE－NACHIMSON M，KOVALSKY S Z，KEMELMACHERSHLIZERMAN I，et al.Global Motion Estimation from Point Matches［C］∥2012Second International Conference on 3DImaging，Modeling，Processing，Visualization and Transmission（3DIMPVT）.Zurich：IEEE，2012：81－88.

［7］MOULON P，MONASSE P，MARLET R.Global Fusion of Relative Motions for Robust，Accurate and Scalable Structure from Motion［C］∥2013IEEE International Conference on Computer Vision（ICCV）.Sydney，NSW：IEEE，2013：3248－3255.

［8］MARTINEC D，PAJDLA T.Robust Rotation and Translation Estimation in Multiview Reconstruction［C］∥IEEE Conference on Computer Vision and Pattern Recognition.Minneapolis，MN：IEEE，2007：1－8.

［9］WANG Jingxue，ZHU Qing，WANG Weixi.A Dense Matching Algorithm of Multi－view Image Based on the Integrated Multiple Matching Primitives［J］.Acta Geodaetica et Cartographica Sinica，2013，42（5）：691－698.（王競(jìng)雪，朱慶，王偉璽.多匹配基元集成的多視影像密集匹配方法［J］.測(cè)繪學(xué)報(bào)，2013，42（5）：691－698.）

［10］YUAN Xiuxiao，MING Yang.A Novel Method of Multi－image Matching Using Image and Space Synthesis Information［J］.Acta Geodaetica et Cartographica Sinica，2009，38（3）：216－222.（袁修孝，明洋.一種綜合利用像方和物方信息的多影像匹配方法［J］.測(cè)繪學(xué)報(bào)，2009，38（3）：216－222.）

［11］JIA Fengman，KANG Zhizhong，YU Peng.A SIFT and Bayes Sampling Consensus Method for Image Matching［J］.Acta Geodaetica et Cartographica Sinica，2013，42（6）：877－883.（賈豐蔓，康志忠，于鵬.影像同名點(diǎn)匹配的SIFT算法與貝葉斯抽樣一致性檢驗(yàn)［J］.測(cè)繪學(xué)報(bào)，2013，42（6）：877－883.）

［12］GOVINDU V M.Robustness in Motion Averaging［M］∥NARAYANAN P J，NAYAR S K，SHUM H Y.Computer Vision：ACCV 2006.Berlin：Springer，2006：457－466.

［13］OLSSON C，ENQVIST O.Stable Structure from Motion for Unordered Image Collections［M］∥HEYDEN A，KAHL F.Image Analysis.Berlin：Springer，2011：524－535.

［14］ENQVIST O，KAHL F，OLSSON C.Non－sequential Structure from Motion［C］∥2011IEEE International Conference on Computer Vision Workshops（ICCV Workshops）.Barcelona：IEEE，2011：264－271.

［15］LOWE D G.Distinctive Image Features from Scale－invariant Key Points［J］.International Journal of Computer Vision，2004，60（2）：91－110.

［16］NISTéR D.An Efficient Solution to the Five－point Relative Pose Problem［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26（6）：756－770.

［17］KRUSKAL J B.On the Shortest Spanning Subtree of A Graph and the Traveling Salesman Problem［J］.Proceedings of the American Mathematical Society，1956，7（1）：48－50.

［18］ZACH C，KLOPSCHITZ M，POLLEFEYS M.Disambiguating Visual Relations Using Loop Constraints［C］∥2010 IEEE Conference on Computer Vision and Pattern Recognition（CVPR）.San Francisco，CA：IEEE，2010：1426－1433.

［19］PEARL J.Probabilistic Reasoning in Intelligent Systems：Networks of Plausible Inference［M］.San Francisco：Morgan Kaufmann，1988.

［20］MACKAY D J C，NEAL R M.Good Codes Based on Very Sparse Matrices［M］∥BOYD C ed.Cryptography and Coding.Berlin：Springer，1995：100－111.

［21］KSCHISCHANG F R，F(xiàn)REY B J.Iterative Decoding of Compound Codes by Probability Propagation in Graphical Models［J］.IEEE Journal on Selected Areas in Communications，1998，16（2）：219－230.

［22］MCELIECE R J，MACKAY D J C，CHENG J F.Turbo Decoding as an Instance of Pearl’s “Belief Propagation”Algorithm［J］.IEEE Journal on Selected Areas in Communications，1998，16（2）：140－152.

［23］KSCHISCHANG F R，F(xiàn)REY B J，LOELIGER H A.Factor Graphs and the Sum－product Algorithm［J］.IEEE Transactions on Information Theory，2001，47（2）：498－519.

［24］MURPHY K P，WEISS Y，JORDAN M I.Loopy Belief Propagation for Approximate Inference：An Empirical Study［C］∥Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence.San Francisco：Morgan Kaufmann Publishers Inc.，1999：467－475.