郭云翔，周 軍

（河海大學(xué) 機(jī)電工程學(xué)院，江蘇 常州 213022）

一種基于水下機(jī)器人的構(gòu)筑物場景復(fù)原優(yōu)化方法

郭云翔，周 軍

（河海大學(xué) 機(jī)電工程學(xué)院，江蘇 常州 213022）

為了克服水下構(gòu)筑物場景復(fù)原過程中的累積誤差，有效還原水下構(gòu)筑物的表面結(jié)構(gòu)信息，本文提出了一種基于水下機(jī)器人的構(gòu)筑物場景復(fù)原優(yōu)化方法。通過構(gòu)建最大生成樹，采用基本的圖算法尋找基準(zhǔn)坐標(biāo)系以及完成坐標(biāo)系的轉(zhuǎn)換，并建立了誤差方程，選取L-M迭代算法實(shí)現(xiàn)變換矩陣的最優(yōu)化，采用對比實(shí)驗(yàn)實(shí)現(xiàn)了對該方法的可靠性檢測。實(shí)驗(yàn)結(jié)果表明，采用該優(yōu)化方法后可有效反映整個探測過程的圖像信息，為后續(xù)的機(jī)器視覺處理建立了有效基礎(chǔ)。

水下構(gòu)筑物；累積誤差；優(yōu)化方法；最大生成樹；變換矩陣

隨著水下機(jī)器人的發(fā)展，傳統(tǒng)的人工潛水作業(yè)已逐漸被水下機(jī)器人替代[1]。通過搭載在水下機(jī)器人上的各種傳感器獲得大量的數(shù)據(jù)，包括水深、機(jī)器人姿態(tài)等[2]，而視覺信息是機(jī)器人實(shí)現(xiàn)正確導(dǎo)航以及水下近距離作業(yè)的重要保障，是研究人員對水下環(huán)境以及水下構(gòu)筑物研究的重要參考信息[3]。而視覺信息作為整個機(jī)器視覺系統(tǒng)的一個重要組成部分，有效的視覺信息可以提高后續(xù)判決執(zhí)行部分的可靠性。

水下作業(yè)的重要一環(huán)為水下構(gòu)筑物的探測任務(wù)，包括大壩裂縫、閘門漏洞、管道泄漏等[4]。通過對水下構(gòu)筑物的場景重構(gòu)，可以對水下構(gòu)筑物表面的整體結(jié)構(gòu)與細(xì)節(jié)部分有直接的對比觀察，能更加清晰地判別出是否有安全隱患。場景重構(gòu)技術(shù)的基本思想為：將零碎的細(xì)小的場景組合重構(gòu)為一個完整的大的場景，包括二維場景重構(gòu)和三圍場景重構(gòu)兩部分[5-6]。二維場景重構(gòu)中的圖像拼接技術(shù)是將構(gòu)筑物表面視頻圖像拼接復(fù)原為一副大的全景圖像。

全景圖拼接理念主要分為基于相位和特征相關(guān)兩類圖像拼接方法[7]。由于相位相關(guān)法具有一定的局限性，基于特征相關(guān)的圖像拼接方法是當(dāng)前研究的重點(diǎn)方向。圖像拼接基本流程為：圖像匹配、圖像變換、圖像融合。良好的視覺信息處理有利于更進(jìn)一步的機(jī)器視覺方面的研究。

1 基于視頻圖像的水下構(gòu)筑物場景重建優(yōu)化方法

1.1 圖像匹配

首先提取圖像SURF特征點(diǎn)，構(gòu)建k-d樹建立特征向量索引樹，采用BBF搜索算法實(shí)現(xiàn)特征點(diǎn)對的匹配，并通過RANSAC算法完成匹配圖像之間的單應(yīng)矩陣計(jì)算。

1.2 圖像變換

1.2.1 單應(yīng)矩陣

在計(jì)算機(jī)視覺領(lǐng)域，平面的單應(yīng)性被定義為一個平面到另一個平面的投影映射。因此，常用單應(yīng)矩陣將兩幅圖像變換到同一平面坐標(biāo)系下。假設(shè)點(diǎn)二維平面上一點(diǎn)q（x,y）變換后為Q（x,y），利用齊次坐標(biāo)系，由單應(yīng)矩陣變換有：

式中：s——尺度因子；

H——單應(yīng)矩陣；

m0，m1，m3，m4——旋轉(zhuǎn)角度；

m2，m5——分別表示水平、垂直方向上的位移；

m6，m7——分別表示水平、垂直方向上的形變程度。

通常歸一化尺度后，計(jì)算式（1）兩邊有：

1.2.2 最大生成樹統(tǒng)一坐標(biāo)系

在完成n副圖像的拼接時(shí)，需要統(tǒng)一坐標(biāo)變換矩陣，尋找的基準(zhǔn)坐標(biāo)系在具有穩(wěn)定性的同時(shí)還應(yīng)該減少變換過程中的運(yùn)算量、累積誤差等?？赏ㄟ^選擇合適的準(zhǔn)則構(gòu)建最大生成樹，采取廣度優(yōu)先搜索來尋找基準(zhǔn)坐標(biāo)系，采用深度優(yōu)先搜索來完成各坐標(biāo)系變換路徑的搜索[8]。

最大生成樹（Maximum Spanning Tree）：在無向連通圖G=（V，E）中，選取一個邊集E′使得集合V中所有點(diǎn)被連接，且E′中邊權(quán)值和最小，其中E′∈E。本文構(gòu)建最大生成樹選擇以下幾條作為準(zhǔn)則：

①以待拼接的n副圖像作為頂點(diǎn)組成頂點(diǎn)集V；

②以兩幅圖像之間是否匹配來判別頂點(diǎn)之間是否存在邊e；

③以兩幅圖像之間匹配的特征點(diǎn)對數(shù)目作為邊的權(quán)重值w；

Kruskal算法常用來尋找最小生成樹，是貪心算法的一種，相對應(yīng)的也可以用來尋找最大生成樹。此時(shí)，生成的最大生成樹記為：G=（V，Emax）。整個算法步驟如下：

Step1：初始化圖G=（V，E），輸入鏡頭內(nèi)所有的關(guān)鍵幀圖像生成頂點(diǎn)集V，輸入由所有關(guān)鍵幀之間匹配關(guān)系構(gòu)成的邊生成邊集E；

Step2：新建圖Gmax=（V，Emax），其中Emax=NULL，此時(shí)Gmax中所有頂點(diǎn)都未連接；

Step3：對E中所有邊按權(quán)重值進(jìn)行降序排列，排列后邊集記為Esort；

Step4：loop：遍歷Esort中所有邊

廣度優(yōu)先搜索（Breadth First Search）為基本圖搜索算法的一種，算法步驟如下：

Step1：初始化輸入max_span_tree，葉節(jié)點(diǎn)集合span_tree_leafs；初始化集合max_dist（n，0），n為頂點(diǎn)數(shù)目，0為初始化值；

Step2：loop1：遍歷span_tree_leafs中所有葉節(jié)點(diǎn)由葉節(jié)點(diǎn)開始廣度優(yōu)先搜索，搜索結(jié)果記錄在cur_dist中；

Loop2：遍歷cur_dist和max_dist中元素，當(dāng)前元素記為I，以cur_dist[i]和max_dist[i]中較大的元素更新max_dist[i]；

Step3：遍歷max_dist中所有元素，選擇其中最小的元素記為min_max_dist；

Step4：記max_dist中所有等于min_max_dist的元素為候選基準(zhǔn)坐標(biāo)系集合，若集合中候選基準(zhǔn)坐標(biāo)系大于1，則選擇其中鄰接點(diǎn)最多的元素作為基準(zhǔn)坐標(biāo)系。

如圖1所示為采用Kruskal算法尋找的最大生成樹，左圖為輸入鏡頭內(nèi)所有關(guān)鍵幀圖像之間的匹配關(guān)系，右圖為尋找的最大生成樹。

圖1 Kruskal算法構(gòu)建最大生成樹過程

以圖1為例，采用廣度優(yōu)先搜索Step2中描述方法，由每個葉節(jié)點(diǎn)進(jìn)行廣度優(yōu)先搜索，各葉節(jié)點(diǎn)cur_dist記錄值數(shù)據(jù)如下：

表1 cur_dist中記錄數(shù)據(jù)

比較后可得到到max_dist數(shù)據(jù)由a至f分別為：2、2、3、3、3、3，顯而易見max_dist中最小的值為2，此時(shí)候選的基準(zhǔn)坐標(biāo)系集合為：a、b。由Step4中描述方法，最后選擇b為基準(zhǔn)坐標(biāo)系。簡單的驗(yàn)證可知：

選a時(shí)，變換總次數(shù)：1+2+2+2=7次；

選b時(shí)，變換總次數(shù)：1+2+1+1=5次；

由于深度優(yōu)先搜索（Breadth First Search）的目的為記錄從其他坐標(biāo)系變換到基準(zhǔn)坐標(biāo)系的路徑，因此采用改進(jìn)的深度優(yōu)先搜索方法：從基準(zhǔn)坐標(biāo)系以外的點(diǎn)出發(fā)，依次遞歸深度優(yōu)先訪問它的鄰接點(diǎn)，記錄搜索過程中的每一步路徑，已訪問的不再記錄，直到搜索到基準(zhǔn)坐標(biāo)系為止。

1.2.3 基于L-M算法最優(yōu)化變換矩陣

若直接將輸入的n幅圖像變換到同一坐標(biāo)系下會發(fā)現(xiàn)n幅圖像之間的配準(zhǔn)誤差較大，在圖像拼接縫隙處有明顯的錯位現(xiàn)象。這是由于，單個變換矩陣只是圖像兩兩匹配之間的結(jié)果，盡管其局部誤差較小，對于n幅圖像的統(tǒng)一變換而言，其累計(jì)誤差較大，從而影響變換后結(jié)果。

以1.2.2節(jié)中統(tǒng)一坐標(biāo)變換系的過程中產(chǎn)生的累積誤差建立數(shù)學(xué)模型，即誤差方程。如圖2所示，將B變換到C時(shí)，先將B變換到A，再變換到C。假設(shè)：（x1，y1）、（x2，y2）、（x3，y3）分別為A、B、C中提取的特征點(diǎn)，其中（x1，y1）->（x2，y2）匹配，點(diǎn)（x1，y1）->（x3，y3）匹配。由1.2.1節(jié)中式（1）計(jì)算變換后點(diǎn)對之間的誤差可得：

圖2 變換誤差示意圖

式中：r為變換誤差，Hba為圖像B變換到A的單應(yīng)矩陣，Hca為圖像C變換到A的單應(yīng)矩陣。

因此，對于n幅圖像變換，計(jì)算其所有匹配關(guān)系以及所有匹配點(diǎn)對之間的累積誤差模型建立如下：

式中：E——累積誤差；

i——第i副圖像；

n——輸入帶拼接的圖像總數(shù)；

g（i）——所有與圖像i匹配的集合；

j——集合g（i）中第j副與i匹配的圖像；

m（i，j）——圖像i、j匹配的特征點(diǎn)對集合；

k——第k對匹配的特征點(diǎn)；

Hi、Hj——圖像i、j變換到基準(zhǔn)坐標(biāo)系的單應(yīng)矩陣。

最優(yōu)化問題為：求解變量{H1，H2，……，Hn}，使得累積誤差E最小。由1.2.1節(jié)中式（1）知單應(yīng)矩陣為8參數(shù)變換矩陣，考慮到各圖像變換尺度不同，對于n副圖像未知參數(shù)最多為9×n。又由式知（2）計(jì)算一對匹配點(diǎn)誤差，本質(zhì)為計(jì)算其x、y方向上的誤差，即可由兩個未知方程組成的方程組f表示。因此，對于所有匹配點(diǎn)對誤差方程組合為向量函數(shù)f：R2×K→R9×n。最優(yōu)化問題轉(zhuǎn)為求解：

式中：f：R2×K→R9×n，2×K＞9×n；m為n個單應(yīng)矩陣未知參數(shù)組成的向量，最多為9×n；K為所有匹配點(diǎn)對總數(shù)。

迭代法為解非線性最小二乘問題的基本方法，迭代條件為：f（xk+1）＜f（xk），也稱為下降法。常用的有：最速下降法、牛頓法、高斯-牛頓法、Levenberg-Marquardt算法。

將向量函數(shù)f：R2×K→R9×n，在x處泰勒展開[9]有：

式中：迭代步長h=[h1，h2，……，h9×n]，J（x）為f（x）的雅克比矩陣

則式（7）中F（m）在x處的梯度為：

F（m）在x處的Hessian矩陣為：

將式（7）在x處泰勒展開有：

分析可知，已知x，可求得矩陣f（x）、J（x）分別記為f、J。此時(shí)式（12）可看作以h為變量的向量函數(shù)L（h）：

L（h）的梯度與Hessian矩陣分別為：

高斯-牛頓法以L（h）的極小值點(diǎn)hgn為步長進(jìn)行迭代，提取SRUF特征點(diǎn)時(shí)采用Hessian矩陣[10]來檢測極值點(diǎn)，其較小值判定條件為：△f（m）=0，且H（M）是正定矩陣。該方法同樣適用于檢測L（h）的極值點(diǎn)，由式（14）知L″（h）只與J相關(guān)，若J為滿秩矩陣，則L″（h）是正定矩陣，因此對高斯-牛頓法步長hgn求解得：

高斯-牛頓迭代法公式有：

Levenberg-Marquardt算法是高斯-牛頓法的改進(jìn)算法[11]，Levenberg-Marquardt算法中加入阻尼因子[12]來約束迭代步長，其迭代公式為：

式中：I為單位矩陣，μ＞0。

μ初始化與A0=J（x0）TJ（x0）中各元素值的范圍有關(guān)，常?。?/p>

式中：τ由用戶選擇，與初始化點(diǎn)相關(guān)，在本文中初始化點(diǎn)x0為統(tǒng)一變換矩陣后的各單應(yīng)矩陣參數(shù)組成的向量。在1.1節(jié)中采用RANSAC算法計(jì)算得到的各單應(yīng)矩陣具有一定的精度，因此本文取τ=1。

μ隨著迭代次數(shù)而更新，由式（12）與式（13）的變化程度的比值θ確定：

②當(dāng)μ很小時(shí)，hlm≈hgn，適用于當(dāng)前跌打參數(shù)離最優(yōu)值較近的情況；

迭代終止條件：g=F′（x*）=J（x*）Tf（x*）=0，然而實(shí)際應(yīng)用中往往不符合這一要求，因此迭代終止條件常用：||g||∞≤□1，其中□1是足夠小的正數(shù)，有用戶決定的。另外，為了避免無限循環(huán)，還應(yīng)設(shè)置最大迭代次數(shù)，當(dāng)?shù)螖?shù)超過最大迭代次數(shù)時(shí)終止迭代。

Levenberg-Marquardt算法偽碼如下：

2 實(shí)驗(yàn)結(jié)果與分析

2.1 圖像匹配

采用1.1節(jié)中基于SURF特征點(diǎn)的圖像匹配算法，快速準(zhǔn)確的實(shí)現(xiàn)了鏡頭中提取的9幅關(guān)鍵幀圖像之間的匹配[13]。實(shí)驗(yàn)場景圖如圖3所示。

圖3 實(shí)驗(yàn)場景圖

2.2 圖像變換

以兩幅圖像匹配的特征點(diǎn)對數(shù)目為權(quán)重值構(gòu)建的最大生成樹[14]。如圖4所示，有：

圖4 鏡頭中關(guān)鍵幀圖像構(gòu)成的最大生成樹

編號2、3最大變換次數(shù)都為3，但此時(shí)編號2總變換次數(shù)：1×4+2×3+3=13，編號3總變換次數(shù)：1× 2+2×4+3×2=16。

由基準(zhǔn)坐標(biāo)系尋找規(guī)則，編號2、3最大變換次數(shù)相同，但是編號2總變換次數(shù)較少且鄰接點(diǎn)較多，因此選擇編號2為基準(zhǔn)坐標(biāo)系。最大生成樹樹中邊的各參數(shù)值如表2所示，weight為兩幅圖像匹配的特征點(diǎn)對數(shù)目。圖5為深度搜索統(tǒng)一變換坐標(biāo)系，以及統(tǒng)一后的單應(yīng)矩陣，push后編號表示當(dāng)前圖像到基準(zhǔn)坐標(biāo)系的變換路徑。

表2 最大生成樹中各邊對應(yīng)相關(guān)值

圖5中homography is后面矩陣為未優(yōu)化之前的各圖像到編號2圖像的單應(yīng)矩陣值，直接變換后結(jié)果如圖6a所示，有著明顯的誤差存在。

以各圖像變換模型為例，迭代次數(shù)與迭代時(shí)間實(shí)驗(yàn)結(jié)果如表3所示。

圖5 深度優(yōu)先搜索統(tǒng)一坐標(biāo)系變換路徑

圖6 拼接效果圖

表3 各算法迭代次數(shù)與時(shí)間實(shí)驗(yàn)結(jié)果

由表3可以看出高斯-牛頓法與L-M算法在400次范圍內(nèi)迭代收斂，最速下降法在400次迭代范圍內(nèi)不能達(dá)到收斂條件，且L-M算法較高斯-牛頓法有較少的迭代次數(shù)和耗時(shí)。L-M算法綜合了高斯-牛頓法迭代精度高與最速下降法迭代速度快的優(yōu)點(diǎn)[15]，且L-M算法較高斯-牛頓法有較少的迭代次數(shù)和耗時(shí)[16]。因此，選取L-M算法可以優(yōu)化統(tǒng)一變換矩陣過程中產(chǎn)生的累積誤差。

由1.2.3節(jié)中L-M算法迭代優(yōu)化后的參數(shù)如表4所示，total num為所有匹配點(diǎn)對數(shù)目，且對應(yīng)式中K的值。

表4 L-M迭代優(yōu)化后的參數(shù)

2.3 圖像融合

L-M優(yōu)化后，采用4層拉普拉斯金字塔融合方法結(jié)果如圖6b所示。對比圖6a、6b可以看出，在圖6b中n副圖像之間的配準(zhǔn)誤差已經(jīng)較小，在圖像拼接縫隙處的錯位現(xiàn)象也得到了一定的改善，且過渡平滑。

除了對于圖像的視覺效果的評價(jià)外，本文分別對于融合圖像的信息熵、平均梯度和均方根誤差作為評價(jià)標(biāo)準(zhǔn)對融合后的圖像進(jìn)行評估如表5所示。

表5 優(yōu)化前后的評價(jià)指標(biāo)

由表5可知，優(yōu)化融合后的圖像的均方根誤差小于未優(yōu)化的圖像，均方根誤差越小，匹配誤差越小，融合效果越好。且優(yōu)化融合后的圖像信息熵和平均梯度都增大，融合后的圖像擁有更多的信息量。對比優(yōu)化前后，對于n副圖像的統(tǒng)一變換而言，其累計(jì)誤差得以減小，從而優(yōu)化了水下構(gòu)筑物場景復(fù)原的結(jié)果。

3 結(jié)束語

文章介紹了一種基于水下機(jī)器人的構(gòu)筑物場景復(fù)原優(yōu)化方法，并進(jìn)行了測試。實(shí)驗(yàn)結(jié)果表明，該變換方法可以很好地減少n幅圖像拼接過程中的累計(jì)誤差。最后的水下構(gòu)筑物的復(fù)原結(jié)果能夠較好的反映整個探測過程的圖像信息，為后續(xù)的機(jī)器視覺處理奠定了可靠的基礎(chǔ)。

[1]徐玉如，李彭超.水下機(jī)器人發(fā)展趨勢[J].自然雜志，2011，33（3）：125-132.

[2]唐旭東，龐永杰.基于單目視覺的水下機(jī)器人管道檢測[J].機(jī)器人，2010，32（5）：592-600.

[3]吳國帥.觀測型ROV視覺系統(tǒng)設(shè)計(jì)［D］.青島：中國海洋大學(xué)，2014.

[4]張洪欣，馬 龍.水下機(jī)器人在海洋觀測領(lǐng)域的應(yīng)用進(jìn)展[J].遙測遙控，2015，36（5）：23-27.

[5]趙次郎.基于激光視覺數(shù)據(jù)融合的三維場景重構(gòu)與監(jiān)控[D].大連：大連理工大學(xué)，2014.

[6]趙魏鈺.基于壓縮感知的圖像超分辨率重構(gòu)算法研究[D].吉林：吉林大學(xué)，2014.

[7]王 娟，師 軍，吳憲祥.圖像拼接技術(shù)綜述[J].計(jì)算機(jī)應(yīng)用研究，2008，25（7）：1940-1943.

[8]Thomas H.cormen.算法導(dǎo)論[M].北京：機(jī)械工業(yè)出版社，2013-01.

[9]Richard Szeliski.Computer Vision：Algorithms and Applications[M]. Berlin：Springer，2010.

[10]張 樺.場景圖像拼接關(guān)鍵技術(shù)研究[D].天津：天津大學(xué)，2008.

[11]高 雋，謝 昭.圖像理解理論與方法[M].北京：科學(xué)出版社，2009.

[12]李珊珊.計(jì)算機(jī)視覺中特征與相似性度量研究[D].合肥：中國科學(xué)技術(shù)大學(xué)，2010.

[13]李 珅，廖華麗.基于虛幻引擎的ROV實(shí)時(shí)運(yùn)動仿真[J].計(jì)算機(jī)與現(xiàn)代化，2014，（7）：150-153.

[14]Lowe，D.G.Distinctive Image Featuresfrom Scale-Invariant Keypoints[J].International Journal of Computer Vison，2004.60（2）：91-110.

[15]David G.Lowe.Distinctive Image Features from Scale-Invariant Keypoints[J].International Journal of Computer Vision，2004.60（2）：91-110.

[16]王 娟，師 軍，吳憲祥.圖像拼接技術(shù)綜述[J].計(jì)算機(jī)應(yīng)用研究，2008，25（7）：1940-1943.

A kind of scene reconstruction optimizationmethod for building on the basis of remotely operated vehicles

GUO Yunxiang,ZHOU Jun
（School of Mechanical and Electrical Engineering,Hehai University,Changzhou 213022,Jiangsu China）

In order to overcome the cumulative error in the reconstruction process of underwater building and effectively restore the surface structure information of underwater building,a kind of scene reconstruction optimizationmethod for building on the basis of remotely operated vehicles has been put forward in the text.The maximum spanning tree has been established.The basic graph algorithm has been used to search reference coordinate system and complete the transformation of coordinate system.The error equation has been established.The optimum transformation matrix has been realized by use of L-M iterative algorithm. The reliable detection has been conducted to this method through contrast experiment.The experimental results show that the image information of the whole detection process has been effectively reflected by adopting this optimized method.It provides effective basis for follow-up machine vision processing.

Underwater building;Cumulative error;Optimized method;Max.spanning tree;Transformation matrix

TP391.7

A

10.16316/j.issn.1672-0121.2016.06.030

1672-0121（2016）06-0118-06

2016-07-16；

2016-09-20

江蘇省科技支撐項(xiàng)目（BE2012096）

周 軍（1961-），男，教授，從事微機(jī)測控自動化研究；郭云翔（1992-），男，碩士在讀，主攻計(jì)算機(jī)視覺研究。E-mail：1028596390@qq.com