李美燕，歐元漢

（廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧530004）

0 引 言

運(yùn)動(dòng)獲取結(jié)構(gòu)［1］（structure from motion，SFM）是由運(yùn)動(dòng)的相機(jī)獲取的多視圖像集估計(jì)相機(jī)外部參數(shù) （motion）并重建場(chǎng)景結(jié)構(gòu) （structure）的過程，它是計(jì)算機(jī)視覺領(lǐng)域中的一個(gè)核心問題。近年來，國內(nèi)外在SFM 的研究上有很大的發(fā)展，已成功應(yīng)用于大數(shù)據(jù)集的自動(dòng)重建［2］。而計(jì)算機(jī)視覺與攝影測(cè)量在技術(shù)上相近［3］，許多研究嘗試將SFM 流程引入到航空攝影測(cè)量中進(jìn)行空中三角解算，以提高航測(cè)的自動(dòng)化程度［4］。目前使用最廣泛的SFM 方法是Bundler［5］，增量的綁定調(diào)整 （bundler adjustment，BA）主要用于完成互聯(lián)網(wǎng)上非結(jié)構(gòu)化圖像的三維重建，而在恢復(fù)無人機(jī)航拍圖像3D 點(diǎn)時(shí)，BA 產(chǎn)生的累積誤差會(huì)導(dǎo)致特征點(diǎn)的重投影誤差不均勻，中間的點(diǎn)誤差較小，外圍點(diǎn)誤差卻非常大，精度很難達(dá)到攝影測(cè)量規(guī)范的要求［6］。BA 的結(jié)果很大程度上取決于初始圖像對(duì)的選擇和后續(xù)圖像的添加順序，因此找到精確的匹配點(diǎn)和準(zhǔn)確的tarcks信息對(duì)SFM結(jié)果的精確度有重要的影響。

傳統(tǒng)SFM 使用SIFT［7］進(jìn)行特征點(diǎn)的提取和匹配，許多文章驗(yàn)證了SIFT 能在原圖提供很好的匹配結(jié)果，但它的運(yùn)行時(shí)間較長(zhǎng)，內(nèi)存開銷很大，因此在基于海量航拍圖像的三維重建中很難實(shí)現(xiàn)可擴(kuò)展性。分層匹配方法有效解決了這一問題，通常金字塔第n＋1層的圖像分辨率比第n層的要低4倍，SIFT 運(yùn)行時(shí)間要比第n層少，由此減少程序運(yùn)行時(shí)間和內(nèi)存開銷，實(shí)現(xiàn)BA 的可擴(kuò)展性。然而，如果僅僅在圖像金字塔第三層 （或以上）執(zhí)行SIFT 特征檢測(cè)和匹配會(huì)出現(xiàn)大量匹配不準(zhǔn)確或錯(cuò)配。楊化超等［8］提出的SIFT 改進(jìn)算法在匹配相似灰度的圖像時(shí)，正確匹配率得到了一定的提高，但該算法在原圖執(zhí)行SIFT 后僅使用NCC將一定閾值內(nèi)的錯(cuò)配點(diǎn)剔除，并未修正錯(cuò)配特征點(diǎn)中心位置，也未能印證該匹配算法的可擴(kuò)展性和對(duì)圖像三維重建精確度的影響。Jose L.Lerma等［9］提出的自動(dòng)定位和3D 建模方法最終得到較好的匹配結(jié)果和重建精度，但該方法未考慮旋轉(zhuǎn)圖像對(duì)歸一化互相關(guān)匹配的影響，而無人機(jī)航拍過程中很容易受到風(fēng)力等自然條件的影響導(dǎo)致圖像存在旋轉(zhuǎn)。孫卜郊等［10］改進(jìn)的NCC匹配算法利用參考圖進(jìn)行多個(gè)角度旋轉(zhuǎn)，以一定步長(zhǎng)進(jìn)行旋轉(zhuǎn)搜索，從而達(dá)到匹配的目的，但是搜索的時(shí)間代價(jià)非常大不利于大數(shù)據(jù)的三維重建。

1 SFM 方法概述

SFM 為每張圖像計(jì)算相機(jī)位姿和3D 點(diǎn)坐標(biāo)。傳統(tǒng)SFM 方法分為兩個(gè)部分，第一部分為特征的提取和匹配，第二部分為相機(jī)位姿估計(jì)和3D 點(diǎn)坐標(biāo)恢復(fù)。第一部分輸入圖像序列，然后對(duì)每張圖像進(jìn)行特征點(diǎn)的檢測(cè)和匹配，使用檢測(cè)到的匹配點(diǎn)進(jìn)行基礎(chǔ)矩陣F 和單應(yīng)矩陣H 的估計(jì)；第二部分輸入上一階段得到的特征匹配對(duì)和相機(jī)內(nèi)部參數(shù)，計(jì)算相對(duì)應(yīng)的tracks，生成連通圖G，依賴G 圖依次估計(jì)相機(jī)外部參數(shù)并恢復(fù)特征點(diǎn)坐標(biāo)，迭代執(zhí)行BA 直至完成整個(gè)場(chǎng)景3D 點(diǎn)的恢復(fù)。

本文提出一種新的SFM 流程，將SIFT、NCC 和LSM相結(jié)合，目的是找到更精確的匹配對(duì)從而提高重建結(jié)果的精度。具體流程如下：在圖像金字塔頂層使用SIFT 進(jìn)行特征點(diǎn)的提取和匹配，減少時(shí)間和內(nèi)存的開銷，使程序更具可擴(kuò)展性；將匹配結(jié)果作為NCC校正的初始匹配集，結(jié)合SIFT 的尺度和旋轉(zhuǎn)信息對(duì)旋轉(zhuǎn)圖像進(jìn)行局部矯正，然后逐層執(zhí)行歸一化互相關(guān)匹配，依次對(duì)錯(cuò)配點(diǎn)位置進(jìn)行修正得到較精確的匹配對(duì)；最后使用最小二乘匹配將圖像匹配的精度進(jìn)一步提高到亞像素級(jí)甚至1／100個(gè)像素。修改特征文件中特征點(diǎn)的位置信息，估計(jì)基礎(chǔ)矩陣F和單應(yīng)矩陣H，從而改變tracks的計(jì)算和連通圖G，最終提高三維重建的精度。同時(shí)，SIFT＋NCC＋LSM 的組合還可以分別設(shè)置閾值，作為一個(gè)過濾器，用來剔除誤配點(diǎn)。

1.1 改進(jìn)NCC匹配

SIFT 檢測(cè)到特征點(diǎn)的三個(gè)信息——位置 （x），尺度（δ）和主方向 （θ）并生成特征描述向量，利用歐氏距離作為度量進(jìn)行特征點(diǎn)的匹配，將匹配的特征點(diǎn)作為NCC 匹配的初始匹配點(diǎn)，縮小NCC匹配范圍。歸一化互相關(guān)方法通過計(jì)算模板窗口和搜索窗口之間的相關(guān)值來確定匹配的程度，當(dāng)互相關(guān)系數(shù)值最大時(shí)搜索窗口的位置決定了模板窗口圖像在待匹配圖像中的位置。

NCC相關(guān) 系數(shù)定義如 下［11，12］

式（1）中：NCC（pi，qj）為 點(diǎn) （pi，qj）處 的NCC 系 數(shù)，（2w＋1）× （2h＋1）為匹配模板的大小，I1（x，y）與I2（x，y）分別表示兩圖像 （x，y）處的灰度值，NCC 系數(shù)越大表示兩幅圖像越相似。

NCC互相關(guān)系數(shù)的分子本質(zhì)上是代表灰度圖的兩個(gè)矩陣中對(duì)應(yīng)各點(diǎn)的像素值兩兩相乘再求和。在沒有旋轉(zhuǎn)的情況下，它可以得到較好的結(jié)果，但是NCC 對(duì)旋轉(zhuǎn)非常敏感，如果圖像存在旋轉(zhuǎn)NCC 將會(huì)面臨以下問題：首先，同樣大小的模板窗口與對(duì)應(yīng)匹配點(diǎn)選取的搜索窗口覆蓋的圖像已經(jīng)不同，像素相差有可能很大；其次，窗口中除了中心點(diǎn) （即特征點(diǎn)）的像素之外，窗口內(nèi)的像素不再存在一一對(duì)應(yīng)關(guān)系 （如圖1所示）；因此，NCC不適用于圖像存在旋轉(zhuǎn)的情況。而基于地面航拍圖像的三維重建中，數(shù)據(jù)的采集是通過小型無人機(jī)按照一定的軌道拍攝所得。由于風(fēng)力等自然條件的影響，小型無人機(jī)在航拍過程中會(huì)出現(xiàn)航線偏移或晃動(dòng)，使得獲取的圖像存在旋轉(zhuǎn)。因此在計(jì)算NCC系數(shù)之前要對(duì)圖像進(jìn)行局部校正。SIFT 特征點(diǎn)描述算子的過程中，將坐標(biāo)軸旋轉(zhuǎn)到關(guān)鍵點(diǎn)的主方向上，從而確保特征點(diǎn)的旋轉(zhuǎn)不變性 （如圖2所示）。因此，本文利用特征點(diǎn)主方向 （θ）將搜索模板做相對(duì)旋轉(zhuǎn)校正以解決NCC不適用的情況。

圖1 相關(guān)窗口

圖2 sift特征點(diǎn)主方向

假設(shè)有匹配對(duì) （pi，qj），其中特征點(diǎn)qj的主方向與特征點(diǎn)pi的主方向的相對(duì)夾角為β＝θi－θj，則圖像旋轉(zhuǎn)后坐標(biāo)為

經(jīng)過旋轉(zhuǎn)校正后利用NCC算法的原理，將初始匹配點(diǎn)作為窗口的中心，待匹配的特征點(diǎn)從搜索窗口中心開始向四周移動(dòng)，每次移動(dòng)一個(gè)單位，遍歷整個(gè)搜索窗口，分別求出 （2w＋1）× （2h＋1）個(gè)NCC 系數(shù)，NCC 系數(shù)最大時(shí)中心點(diǎn)位置為該匹配點(diǎn)的最終位置 （如圖3所示）。如果該點(diǎn)為原初始匹配點(diǎn)的位置，則不對(duì)該特征點(diǎn)的位置信息做改變；否則修改特征點(diǎn)文件，將新的匹配點(diǎn)位置 （m＋x，n＋y）作為匹配點(diǎn)中心位置。

提高企業(yè)工作效能，增加利潤(rùn)，并不是只有與生產(chǎn)、銷售等工作直接相關(guān)的人員和部門才負(fù)有的責(zé)任，企業(yè)應(yīng)該從上到下樹立一種效能思維，凡事都應(yīng)該以提高工作效率，降低時(shí)間成本為目標(biāo)進(jìn)行。

圖3 NCC遍歷過程

1.2 LSM 匹配

無人機(jī)航拍采集圖像時(shí)會(huì)受到光照、視角的影響，僅利用NCC對(duì)特征點(diǎn)位置進(jìn)行初步調(diào)整不能得到完全精確的匹配位置，需要進(jìn)一步對(duì)其進(jìn)行精確調(diào)整。最小二乘匹配方法 （LSM）利用了圖像窗口內(nèi)的信息進(jìn)行平差計(jì)算，可以將圖像匹配的精度進(jìn)一步提高到1／10 甚至1／100像素［13］。

對(duì)提取到的初始匹配點(diǎn)進(jìn)行進(jìn)一步匹配時(shí)，要為模板窗口與實(shí)際窗口引入變形系數(shù)，由于圖像采集所使用的相機(jī)已標(biāo)定，因此在只考慮幾何畸變的情況下，將幾何畸變看成是 仿射變換，即有［14，15］

式中：gl——實(shí)際窗口的灰度值，g2——模板窗口灰度值，h——線性系數(shù)，n1、n2——圖像噪聲，ai、bi（i＝0，l，2）為仿射變換的系數(shù)。上式經(jīng)過線性變化后可得到誤差方程如下

式中：ci（i＝1，...，7）為變形系數(shù)，Δg——窗口像素的灰度差。誤差方程的系數(shù)為

設(shè)未知數(shù)的初始值設(shè)為

在窗口區(qū)域內(nèi)逐像素建立誤差方程，使用CTCX ＝CTΔG 解出幾何變形系數(shù)。根據(jù)幾何變形系數(shù)計(jì)算匹配點(diǎn)的最佳位置

LSM 的過程可分為如下幾步：①采用NCC 相關(guān)系數(shù)對(duì)初始匹配點(diǎn)進(jìn)行修正，得到準(zhǔn)確度較高的初始值，分別對(duì)圖像的匹配點(diǎn)進(jìn)行幾何變形改正；②重復(fù)采樣得到匹配點(diǎn)幾何變形改正后的灰度值；③計(jì)算實(shí)際窗口與搜索窗口間的相關(guān)系數(shù)，判斷是否符合迭代條件 （此處設(shè)置一個(gè)閾值，可用于剔除誤配點(diǎn)）；④計(jì)算系統(tǒng)變形參數(shù)；⑤計(jì)算最佳匹配點(diǎn)位置。

2 實(shí)驗(yàn)與分析

本文選取一組210 張具高分辨率 （6000×4000）的無人機(jī)攝影圖像作為實(shí)驗(yàn)數(shù)據(jù)，圖像存在輕微的旋轉(zhuǎn)，且拍攝場(chǎng)景均為無明顯亮度變化的田地或存在地勢(shì)高度差的山林。實(shí)驗(yàn)分為兩部分：①在相似灰度的圖像金字塔頂層提取高準(zhǔn)確度的特征匹配點(diǎn)；②驗(yàn)證本文方法的重建精度；③驗(yàn)證SFM 新流程的可擴(kuò)展性。

建立圖像金字塔，在金字塔的第3層執(zhí)行SIFT 特征提取和匹配，得到的部分匹配對(duì)如圖4 （a）、（b）所示；從第2層到第0層逐層使用主方向?qū)πD(zhuǎn)圖像進(jìn)行局部校正，然后使用NCC對(duì)特征點(diǎn)坐標(biāo)進(jìn)行調(diào)整，調(diào)整后的匹配點(diǎn)位置如圖4 （c）所示；最后在0層執(zhí)行LSM 對(duì)匹配點(diǎn)的位置進(jìn)一步修正，得到更為精確的匹配點(diǎn)，如圖4 （d）所示。

圖4 特征點(diǎn)匹配位置

從圖4 （a）和圖4 （b）可看出僅在頂層金字塔執(zhí)行SIFT 會(huì)出現(xiàn)匹配不準(zhǔn)確的情況；從圖4 （c）可看出，使用主方向進(jìn)行局部校正后再使用NCC對(duì)匹配點(diǎn)進(jìn)行初步調(diào)整后匹配點(diǎn)中心位置得到改善，結(jié)果表明本文算法的解決了NCC不適用于旋轉(zhuǎn)圖像的問題；從圖4 （d）看出匹配點(diǎn)經(jīng)LSM 進(jìn)一步修正后可得到精確的匹配位置。

為了測(cè)試本文算法的精確度，圖5給出真實(shí)場(chǎng)景中的11個(gè)像控點(diǎn)的位置。設(shè)開源BA 算法恢復(fù)的像控點(diǎn)坐標(biāo)和實(shí)際世界坐標(biāo)的誤差為 （Δx，Δy，Δz），本文算法恢復(fù)的像控點(diǎn)坐標(biāo)和實(shí)際世界坐標(biāo)的誤差為 （Δx’，Δy’，Δz’），兩誤差之間的比較在圖6顯示。

圖5 像控點(diǎn)位置

圖6 改進(jìn)算法與BA 回算3D 點(diǎn)的誤差比較

從圖6中可看出回算平面坐標(biāo) （x，y）時(shí)本文算法的誤差略小于BA 的誤差，但兩者相差不大，誤差都能保持在0.3～0.5之間，不能體現(xiàn)本文算法的優(yōu)勢(shì)。然而，在回算高程時(shí)本文算法體現(xiàn)了其高精確度。BA 回算的11個(gè)像控點(diǎn)的z坐標(biāo)與像控點(diǎn)實(shí)際坐標(biāo)相差都在1.5m 以上，最大的誤差出現(xiàn)在g109這個(gè)點(diǎn)，達(dá)到3.8m，這已超出了實(shí)際測(cè)量的誤差范圍。而本文算法經(jīng)絕對(duì)定向得到的高程誤差能保持在1m 左右，其中有5個(gè)像控點(diǎn)的誤差在0.5 m以內(nèi)，只有g(shù)99－1這個(gè)像控點(diǎn)的誤差達(dá)到1.5m。由此可驗(yàn)證本文算法在重建精度上優(yōu)于BA，在實(shí)際的攝影測(cè)量中有較高的應(yīng)用價(jià)值。

圖7是3000張無人機(jī)航拍圖像使用本文SFM 方法估計(jì)出的相機(jī)位姿和恢復(fù)的3D 點(diǎn)云，其重投影誤差平均在0.5～0.7之間，運(yùn)行時(shí)間為360min48s。實(shí)驗(yàn)表明本文方法具有可擴(kuò)展性，能夠自動(dòng)、有效的處理海量數(shù)據(jù)，在海量數(shù)據(jù)航空攝影測(cè)量中有一定的實(shí)際應(yīng)用價(jià)值。

圖7 密集3D 點(diǎn)云

3 結(jié)束語

本文研究一種新的SFM 流程，使用分層匹配方法節(jié)省SIFT 特征點(diǎn)提取和匹配的時(shí)間和內(nèi)存開銷，使用特征點(diǎn)主方向?qū)πD(zhuǎn)圖像進(jìn)行處理，使NCC 適用于無人機(jī)航拍圖像。采用改進(jìn)后的NCC和LSM 依次對(duì)SIFT 初始匹配點(diǎn)的中心位置進(jìn)行調(diào)整，有效的改善了匹配點(diǎn)的位置，提高匹配精度。利用這一匹配結(jié)果進(jìn)行相機(jī)標(biāo)定并回算3D 點(diǎn)坐標(biāo)，為后續(xù)的三維重建提供高精確度的密集點(diǎn)云。實(shí)驗(yàn)結(jié)果表明，ABM 與FBM 結(jié)合的SFM 方法在基于無人機(jī)海量航拍圖像的三維重建中具有高精確度和可擴(kuò)展性，在攝影測(cè)量行業(yè)中具有一定的應(yīng)用價(jià)值。

［1］Richard Szeliski.Computer vision：Algorithms and applications［M］.AI Haizhou，transl.Beijing：Tsinghua University Press，2012：265－273（in Chinese）.［Richard Szeliski.計(jì)算機(jī)視覺－－算法與應(yīng)用［M］.艾海舟，譯.北京：清華大學(xué)出版社，2012：265－273.］

［2］Sameer Agarwal，Yasutaka Furukawa，Noah Snavely.Building Rome in a day ［J］.Communications of the ACM，2011，54 （10）：105－112.

［3］ZHANG Zuxun.On informatization of surveying and mapping from the development of digital photogrammetry ［J］.Geomatics and Information Science of Wuhan University，2008，33（2）：111－115 （in Chinese）.［張祖勛.由數(shù)字?jǐn)z影測(cè)量的發(fā)展談信息化測(cè)繪 ［J］.武漢大學(xué)學(xué)報(bào)·信息科學(xué)版，2008，33 （2）：111－115.］

［4］Noah Snavely，Steven M Seitz，Richard Szeliski.Modeling the world from internet photo collections［J］.International Journal of Computer Vision，2008，80 （2）：189－210.

［5］Wu CC，Agarwal S，Curless B.Multicore bundle adjustment［C］／／Conference On Computer Vision And Pattern Recognition，2011：3057－3064.

［6］Steve Harwin，Arko Lucieer.Assessing the accuracy of georeferenced point clouds produced via multi－view stereopsis from unmanned aerial vehicle（UAV）imagery ［J］.Remote Sensing，2012，4 （6）：1573－1599.

［7］Sirmacek B，Unsalan C.Urban－area and building detection using SIFT keypoints and graph theory ［J］.IEEE Transactions on Geoscience and Remote Sensing，2009，47 （4）：1156－1167.

［8］YANG Huachao，ZHANG Shubi，ZHANG Qiuzhao.Least squares matching methods for wide base－line stereo images based on SIFT features［J］.Acta Geodaetica et Cartographica Sinica，2010，39 （2）：187－194 （in Chinese）. ［楊化超，張書畢，張秋昭.基于SIFT 的寬基線立體影像最小二乘匹配方法 ［J］.測(cè)繪學(xué)報(bào)，2010，39 （2）：187－194.］

［9］Jose L Lerma，Santiago Navarro，Miriam Cabrelles，et al.Automatic orientation and 3D modelling from markerless rock art imagery ［J］.ISPRS Journal of Photogrammetry and Remote Sensing，2013，76：64－75.

［10］SUN Bojiao，ZHOU Donghua.Rotated image registration method based on NCC ［J］.Transducer and Microsystem Technologies，2008，27 （5）：43－45 （in Chinese）. ［孫 卜郊，周東華.基于NCC 的存在旋轉(zhuǎn)的圖像匹配方法 ［J］.傳感器與微系統(tǒng)，2008，27 （5）：43－45.］

［11］HUANG Zhenbao，CHEN Yang.A fast method for NCC algorithm in image matching ［J］.Informatization Research，2011，37 （2）：48－52 （in Chinese）. ［黃真寶，陳陽.圖像匹配中NCC 算法的一種快速實(shí)現(xiàn)方法 ［J］.信息化研究，2011，37 （2）：48－52.］

［12］WANG Wantong，LIU Pengfei，HAN Zhigang.Multi－sensor image registration method based on SIFT and NCC algorithm［J］.Computer Engineering and Applications，2012，48（3）：10－12 （in Chinese）.［王萬同，劉鵬飛，韓志剛.基于SIFT 和NCC的多源遙感影像配準(zhǔn)方法 ［J］.算機(jī)工程與應(yīng)用，2012，48 （3）：10－12.］

［13］ZHOU Shilun.The research and realization of the least squares image matching algorithm ［J］.Information ＆Communication，2013，27 （4）：35－36 （in Chinese）. ［周時(shí)倫.最小二乘影像匹配算法的實(shí)現(xiàn)與研究 ［J］.信息通信，2013，27 （4）：35－36.］

［14］ZHU Zunshang，ZHU Zhaokun，CHEN Shengyi，et al.An adaptive window affine least squares matching method ［J］.Journal of National University of Defense Technology，2013，35 （4）：46－50 （in Chinese）. ［朱遵尚，朱肇昆，陳圣義，等.自適應(yīng)窗口仿射最小二乘匹配方法 ［J］.國防科技大學(xué)學(xué)報(bào)，2013，35 （4）：46－50.］

［15］KOU Rong.Study on the correlation coefficient and the least square image matching algorithm ［J］.Inner Mongolia Science Technology ＆ Economy，2010 （17）：60－63 （in Chinese）.［寇蓉.相關(guān)系數(shù)與最小二乘影像匹配算法的研究 ［J］.內(nèi)蒙古科技與經(jīng)濟(jì)，2010 （17）：60－63.］