李海豐，胡遵河，范龍飛，姜子政，陳新偉

(1.中國民航大學 計算機科學與技術(shù)學院，天津 300300； 2.福建省信息處理與智能控制重點實驗室(閩江學院)，福州 350121)

(*通信作者電子郵箱chenxw_mju@126.com)

基于幾何約束及0-1規(guī)劃的視頻幀間線段特征匹配算法

李海豐1,2，胡遵河1，范龍飛1，姜子政1，陳新偉2*

(1.中國民航大學 計算機科學與技術(shù)學院，天津 300300； 2.福建省信息處理與智能控制重點實驗室(閩江學院)，福州 350121)

(*通信作者電子郵箱chenxw_mju@126.com)

針對線段因遮擋、斷裂以及端點提取不準確等原因造成的線段特征匹配困難問題，特別是現(xiàn)有匹配算法在匹配過程中出現(xiàn)“多配多”時直接采取“最相似匹配”而導致丟失大量真實匹配的問題，提出了一種基于多重幾何約束及0-1規(guī)劃的線段特征匹配算法。首先，基于校正后視頻幀間線段特征的空間相鄰性計算線段匹配的初始候選集；然后，基于極線約束、單應(yīng)矩陣模型約束以及點-線相鄰性約束等多重幾何約束，對候選集進行篩選從而剔除部分錯誤匹配；其次，將線段匹配問題建模為一個大規(guī)模0-1規(guī)劃問題；最后，設(shè)計了一種基于分組策略的兩階段求解算法對該問題進行求解，從而實現(xiàn)線段特征的“一配一”精確匹配。實驗結(jié)果表明，該算法與LS(Line Sigature)、LJL(Line-Junction-Line)方法相比，匹配正確率接近，但匹配線段數(shù)量分別提高了60%和11%。所提算法可以實現(xiàn)視頻幀間的線段特征匹配，為基于線特征的視覺SLAM(Simultaneously Localization and Mapping)奠定基礎(chǔ)。

線段匹配; 幾何約束; 0-1規(guī)劃；特征匹配；視覺SLAM

0 引言

特征匹配是計算機視覺領(lǐng)域研究的核心問題之一。點特征的匹配方法已經(jīng)比較成熟可靠，如尺度不變特征轉(zhuǎn)換(Scale-Invariant Feature Transform, SIFT)[1]、加速魯棒特征(Speeded Up Robust Features, SURF)[2]等。與點特征相比，在同樣的噪聲條件下，圖像中的線特征受噪聲影響更小，且對光照條件和陰影不敏感。因此，基于線特征的視覺SLAM(Simultaneously Localization and Mapping)日益興起[3]。然而，線段端點位置的不準確、遮擋、斷裂等因素使線段特征的匹配極具挑戰(zhàn)性。

近年來，許多學者致力于解決線段特征的匹配問題?？蓪⒕€段匹配算法分為兩大類：個體匹配和組匹配。在個體匹配算法中，線段鄰域的梯度信息[4-5]和顏色信息[6-7]常被用來作為線段的特征描述。然而，基于顏色或梯度信息的線段匹配方法受光照影響比較大，且不適用于場景中線特征的顏色信息很相似的情形。另一類個體匹配算法利用了多種幾何約束信息，如王偉璽等[8]利用不同視圖間線段端點的對極幾何約束，借助點對應(yīng)的相關(guān)性作為衡量線段間相似性的標準來進行線段特征匹配；然而，該方法的準確性不高。婁安穎等[9]利用單應(yīng)矩陣約束實現(xiàn)了遙感圖像中的線段特征匹配。梁艷等[10]和李俊瑤等[11]分別結(jié)合極線約束和單應(yīng)矩陣約束進行線段特征匹配。Fan等[12]提出了基于點對應(yīng)的線特征匹配算法，將不同視圖間線段鄰域內(nèi)的點對應(yīng)作為衡量線段之間相似性的度量，是一種具有較高準確性和魯棒性的線段匹配方法。然而，該方法存在以下問題：當場景中缺少點特征時，很多真實存在的線對應(yīng)無法被找到；點特征的匹配錯誤可能會導致相應(yīng)的線段匹配錯誤。線段的組匹配方法[13-15]將圖像中的多條線段看成一個整體，線段間的相對位置關(guān)系可以為線段的匹配提供一定的幾何約束。其中，文獻[14]提出的LS(Line Signature)方法目前已被廣泛應(yīng)用，而文獻[15]中的LJL(Line-Junction-Line)算法作為一種新的線段匹配算法，已在實驗中取得了較好效果。然而，該類方法具有較高的計算復雜度，且容易受到線段端點位置不準確的影響。

線段因遮擋、斷裂以及端點提取不準確等造成線段特征匹配的“多配多”匹配問題。為了獲得線段的“一配一”匹配，現(xiàn)有方法絕大多數(shù)在匹配階段采用相似度最大原則，即匹配時取相似度最大的一對線段作為匹配結(jié)果。然而，對于線段相似度接近的場景，上述方法容易發(fā)生錯配，在初始匹配階段就采用相似度最大原則也容易丟失大量真實匹配；而且相似度最大原則實質(zhì)上是一種局部最優(yōu)匹配，并未考慮線段匹配的全局最優(yōu)。特征編組[16]及圖優(yōu)化[17]等方法被一些學者用于了線段的全局匹配并取得了一定的效果。

本文針對視頻幀間線段特征匹配問題，設(shè)計了一種基于多重幾何約束及0-1規(guī)劃的線段匹配算法。視頻幀間特征匹配實質(zhì)上是一種短基線特征匹配問題。本文算法結(jié)合了多種幾何約束，同時將匹配的點特征及線段間距離作為一種線段相似度對匹配結(jié)果進行篩選，最后構(gòu)建了0-1規(guī)劃模型對“多配多”匹配問題進行建模和求解，實現(xiàn)了優(yōu)化的“一配一”線段特征匹配。

1 問題描述

三維空間中的同一線段，在攝像機以不同視角采集的兩幅圖像中所呈現(xiàn)的投影線段，稱為一組匹配線段。本文所要解決的線段特征匹配定義如下：

定義1 線段特征匹配。兩幅圖像中的一對線段特征，如果該對線段特征在三維空間中共線并且有重合，則稱該對線段是一對匹配的線段特征。

基于上述符號定義，本文所研究問題的定義如下：

定義2 給定視頻幀序列υ，提取關(guān)鍵幀集合κ，對于任意相鄰的關(guān)鍵幀F(xiàn)k,Fk+1∈κ，提取線段特征并進行一一對應(yīng)的匹配，最終獲得Lk,k+1。

2 本文算法

本文設(shè)計了基于多重幾何約束的視頻幀間線段特征匹配算法。如圖1所示，首先，對視頻中的關(guān)鍵幀進行提取，以達到避免病態(tài)對極幾何和消除信息冗余的目的；然后，利用SIFT算法[1]及LSD(Line Segment Detector)算法[18]分別提取關(guān)鍵幀中的點特征和線段特征，并對線段特征進行刪除、合并等預處理；最后，基于空間相鄰性、單應(yīng)矩陣模型以及點-線相鄰性等幾何約束對線段特征進行匹配、篩選，并最終基于0-1規(guī)劃實現(xiàn)線段的優(yōu)化匹配。

圖1 匹配算法流程Fig. 1 Flowchart of the matching algorithm

2.1 基于多重幾何約束的線段初始匹配

在提取了線段特征之后，本文基于多重幾何約束進行線段的初始匹配及篩選。首先基于空間相鄰性獲取初始的線段匹配候選集；然后分別基于極線約束、單應(yīng)矩陣模型約束以及點-線相鄰性約束等幾何約束對初始匹配集進行篩選，刪除部分錯誤匹配。

2.1.1 基于空間相鄰性求解線段特征初始匹配集

攝像機在采集相鄰關(guān)鍵幀時平移量較小，而如果在沒有旋轉(zhuǎn)變化的情況下，較小的攝像機平移所產(chǎn)生的特征在圖像中的變化也較小。因此，本文首先基于基本矩陣估計出相鄰關(guān)鍵幀間攝像機的旋轉(zhuǎn)變換；然后通過對后一關(guān)鍵幀施加該旋轉(zhuǎn)變換的逆變換而使其與前一關(guān)鍵幀之間只有平移變化；最后，比較變換后兩關(guān)鍵幀間的線段特征位置以確定線段的初始匹配結(jié)果。

基本矩陣的估計方法為：在隨機抽樣一致(RANdom Sample Consensus, RANSAC)框架下，利用SIFT點特征，通過最小化重投影誤差[19]完成。

然后，通過式(1)對基本矩陣F進行分解，從而獲得攝像機在兩幀之間的旋轉(zhuǎn)變換R。

F=(K)-T[t]×RK-1

(1)

其中:K為攝像機的內(nèi)參數(shù)矩陣，可通過標定獲得；R和t分別為兩幀之間攝像機的旋轉(zhuǎn)矩陣和平移向量；符號[·]×為叉乘運算的斜對稱矩陣表示。

1)方向約束。

根據(jù)線段端點的坐標，求出線段的傾角。匹配線段的方向約束為：

2)位置約束。

其中，Td>0為一設(shè)定閾值。

滿足上述1)、2)兩個約束條件的所有線段構(gòu)成初始匹配集。初始匹配集中可能會包含“一配多”或“多配多”的關(guān)系，即前一關(guān)鍵幀中的一條線段在后一關(guān)鍵幀中可能存在多條與之匹配的線段，反之亦然。此步為線段的初始匹配，目的是找到盡可能多的潛在的匹配線段，本文將在下面的步驟中利用多重幾何約束對此處的初始匹配結(jié)果進行過濾和優(yōu)化。

2.1.2 基于多重幾何約束的候選解篩選

上述初始匹配集中存在錯誤匹配、“一配多”“多配多”等問題，為了減少匹配候選解的個數(shù)、降低后續(xù)優(yōu)化中的變量維度，對初始匹配集進行如下篩選。

2)單應(yīng)矩陣約束。由文獻[19]可知，攝像機在只有旋轉(zhuǎn)運動的情況下，所采集的圖像匹配的特征滿足單應(yīng)矩陣模型。本文所研究的是視頻幀間線段特征匹配，攝像機在采集相鄰關(guān)鍵幀時距離較近，攝像機平移較小，與場景中特征距離攝像機的距離相比該平移可近似忽略，因此關(guān)鍵幀中匹配的線段特征應(yīng)近似滿足同一個單應(yīng)矩陣模型。本文基于RANSAC框架，首先，從線段特征候選匹配集中隨機選擇四組匹配線段組成隨機樣本，根據(jù)歸一化DLT(Direct Linear Transform)算法求得單應(yīng)矩陣H;然后對初始匹配集中的每組匹配線段計算映射之后的歐氏距離d⊥，如果d⊥

2.2 基于0-1規(guī)劃的線段匹配算法

根據(jù)上面的步驟可以從相鄰關(guān)鍵幀中找到包含所有可能的線段匹配的候選集。在該候選集中，任意一條線段可能存在多個與之匹配的線段，即存在“多配多”的匹配關(guān)系。而在實際應(yīng)用中，一條線段在另一幀圖像中最多只能與一條線段匹配。因此，需要從候選集中的“多配多”匹配關(guān)系中尋找最終的“一配一”的匹配結(jié)果。

圖2 點-線相鄰性示意圖Fig. 2 Illustration of point-line adjacency

2.2.1 問題建模

對于候選集中的每對匹配線段，可以通過計算相似度來度量該對線段的匹配程度。相似度越大，表明該對線段的匹配性越好，越有可能是真實的匹配。這樣，上述線段特征匹配問題可以被描述為：從候選解集中選取一些合適的匹配結(jié)果，在滿足上述“一配一”匹配約束的前提下，使匹配結(jié)果的相似度之和最大。

(2)

上述線段全局匹配問題可被定義為如下0-1規(guī)劃問題：

(3)

需要滿足如下約束條件：

(4)

式(4)中的約束條件保證了一條線段在另一幅圖像中最多有一條線段與之匹配。

(5)

2.2.2 問題求解

由于視頻幀中的線段較多，導致式(3)中優(yōu)化變量非常多，直接求解式(3)中的大規(guī)模0-1規(guī)劃問題將非常耗時，甚至無法求出結(jié)果。在上面的候選集確定以及基于幾何約束的匹配線段篩選過程中，已經(jīng)去除了大量不可能的匹配，即已令大量的xi, j=0，從而使待優(yōu)化變量的數(shù)量大大減少。但通過實驗我們發(fā)現(xiàn)剩余的待優(yōu)化變量數(shù)量仍然較大。為了降低運算量，本文提出了基于分組策略的兩階段求解算法。

首先，基于K-Means算法對候選集Μ中Fk圖像幀中的線段進行聚類分組，使其分為m個距離相近的線段子集。具體做法為：首先從屬于Μ的Fk中的線段任意選擇m個對象作為初始聚類中心；而對于所剩下其他線段，則根據(jù)它們與這些聚類中心的相似度(此處為線段中點的距離)，分別將它們分配給與其最相似的聚類；然后再計算每個所獲新聚類中所有線段中點的幾何中心作為該聚類的聚類中心；不斷重復這一過程直到標準測度函數(shù)開始收斂為止。本文以線段距離聚類中心的均方差作為標準測度函數(shù)。

根據(jù)上述聚類，將候選解集Μ分解為m個子集。然后，分兩個階段對線段全局匹配問題進行求解。在第一階段，分別對每個子集根據(jù)式(3)所示模型對其進行求解。由于每個子集的優(yōu)化變量數(shù)量較少，所以可采用分枝定界算法求解。每個子集求解后，對于子集內(nèi)部的線段會得到“一配一”的匹配關(guān)系。在第二階段，將所有子集求解的結(jié)果合并，保留仍然具有“一配一”匹配關(guān)系的線段作為匹配的最終結(jié)果。對于剩下的那部分因子集求解結(jié)果合并而出現(xiàn)的“一配多”的線段，重新利用式(3)中模型對其求解。此時，由于剩余線段較少，所以問題規(guī)模大幅降低。

下面舉例說明上述求解過程。如圖3所示，線段的候選匹配集為：

圖3 基于分組策略的兩階段線段匹配求解示例Fig. 3 Example of two-stage line matching based on grouping strategy

本文之所以能按照上述方式對候選匹配集進行聚類分組，是因為根據(jù)本文候選集的確定方法，只有位置相鄰的線段才可能具有相同的候選匹配。因此，上述聚類分組方法具有合理性。由于本文采用了基于分組策略的兩階段線段匹配求解算法，分組及合并的過程可能導致無法獲得全局最優(yōu)解。然而，對于線段匹配問題，具有較低計算代價的近似最優(yōu)解是可以接受的。后續(xù)實驗部分將對匹配算法的性能進行驗證。

3 實驗與分析

利用C++語言及計算機視覺庫OpenCV實現(xiàn)了本文算法。硬件為戴爾計算機，i7- 3處理器，4 GB內(nèi)存，500 GB硬盤，攝像機為佳能600D。實驗中，所需參數(shù)的取值分別為：α=100，β=1，Tθ=2°，Td=40，TH=20。

本章首先通過示例實驗，分析本文算法每一步輸出的運行過程及中間結(jié)果，以說明本文算法中幾何約束及優(yōu)化過程的必要性和有效性；然后，對實驗結(jié)果進行分析，給出本文算法針對不同場景中圖像的實驗結(jié)果，并與其他算法進行對比。

3.1 實驗過程分析

圖4(a)為兩幅示例圖像(視圖1和視圖2)，圖4(b)為從圖4(a)中提取出的經(jīng)過預處理后的線段，線段數(shù)量分別為53、49，所有線段均已編號。

圖4 示例圖像及其線段提取結(jié)果Fig. 4 Example images and their line segment extraction results

首先，基于線段特征的空間相鄰性計算線段匹配的初始候選集，得到如圖5(a)所示的匹配矩陣：第1列為圖4(a)視圖1圖像中線段的編號，第1行為圖4(a)視圖2圖像中的線段編號，“1”表示對應(yīng)位置的兩線段匹配，“0”表示不匹配。此時，可以看到一行(或一列)中存在多個值等于1的情況，說明存在大量的“多對多”匹配關(guān)系，此例中共有270個變量需要優(yōu)化。

然后，基于極線約束、單應(yīng)矩陣模型約束以及點-線相鄰性約束等多重幾何約束，對圖5(a)所示候選解集進行篩選并剔除部分錯誤匹配，更新后的匹配矩陣如圖5(b)所示?？梢钥闯觯仃囍兄禐椤?”的元素大大減少，說明大量的錯誤匹配已被剔除；但仍存在一行(或一列)中存在多個值等于1的情況，說明仍存在“多配多”匹配關(guān)系。

圖5 初始候選集與更新后的匹配矩陣示意圖Fig. 5 Schematic diagram of matching matrices for initial and updated candidate set

最后，利用2.2節(jié)的匹配算法進行匹配。此時，盡管該優(yōu)化問題中待優(yōu)化變量的數(shù)量為53×49=2 646個，但從上述匹配矩陣可以看出，大量的元素已被置為0，經(jīng)過多幾何約束之后，真正需要優(yōu)化的變量僅為106個，大大降低了問題求解的復雜度。利用基于0-1規(guī)劃的線段匹配算法所獲得線段的“一配一”匹配結(jié)果如圖6所示。

圖6 示例圖像中線段匹配結(jié)果Fig. 6 Line segment matching results for example images

3.2 實驗結(jié)果及分析

分別采用公共數(shù)據(jù)集HRBB[20]和筆者采集的數(shù)據(jù)集進行實驗。實驗數(shù)據(jù)共包含10對圖像作為代表性的視頻關(guān)鍵幀：HRBB中室內(nèi)走廊場景4對，自采集室內(nèi)辦公場景1對，室外校園場景5對。

線段匹配部分圖像的結(jié)果如圖7所示，圖中同一行的兩幅圖像為一對，其中具有相同標號的線段為一組匹配的線段。

為了進一步說明本文算法的性能，將本文算法與目前被廣泛應(yīng)用的LS方法[14]和最新的LJL方法[15]進行對比，對比實驗的統(tǒng)計結(jié)果如表1所示。由表1可知，本文算法和LS方法、LJL方法的平均匹配準確率接近(95.3%與97.4%、98.2%),平均運行時間相差不大(14.9 s與13.5 s、13.6 s)；但本文算法所提取的匹配線段數(shù)量分別高出LS和LJL方法60%和11%，如圖8所示。本文算法之所以能夠找到更多的匹配線段，原因在于：本文算法并未采用其他絕大多數(shù)匹配方法為了獲得“一配一”結(jié)果所采用的“最大相似性”以及“左右一致性”匹配原則，明顯降低了在匹配中間環(huán)節(jié)中丟失真實匹配的數(shù)量。需指出，雖然在上述實驗中LS和LJL方法的綜合性能不及本文算法，但上述兩個方法可用于長基線(long base-line)圖像的線段匹配問題，應(yīng)用范圍比本文算法更大。

圖7 線段匹配部分結(jié)果Fig. 7 Partial result of line segment matching

圖8 線段匹配數(shù)量對比Fig. 8 Amount comparison of line segment correspondences

4 結(jié)語

本文設(shè)計了一種基于多重幾何約束及0-1規(guī)劃的視頻幀間線段特征匹配算法。首先，針對視頻幀間特征在圖像空間中平移較小的特點，通過除攝像機旋轉(zhuǎn)變換差異并結(jié)合待匹配特征的空間相鄰性，獲得了線段匹配的初始候選匹配集；然后，基于極線約束、單應(yīng)矩陣模型約束以及點-線相鄰性約束等對候選解集進行篩選從而剔除了部分錯誤匹配；最后，將線段匹配問題建模為一個大規(guī)模0-1規(guī)劃問題，并設(shè)計了一種基于分組策略的兩階段求解算法對該問題進行求解，從而實現(xiàn)了線段特征的“一配一”精確匹配。該算法可以解決線段因遮擋、斷裂以及端點提取不準確等造成的線段特征匹配困難，特別是現(xiàn)有匹配算法在匹配過程中出現(xiàn)“多配多”時直接采取“最相似匹配”而導致丟失大量真實匹配等問題。

表1 實驗對比結(jié)果Tab. 1 Comparison of experimental results

本文所述算法實際上是一種面向短基線(short base-line)圖像序列的線段匹配方法。當采集兩幅圖像時的攝像機之間基線較長時，特征在圖像空間中的位置變化較大，不能直接依據(jù)本文所提的空間相鄰性來確定初始候選匹配集。可考慮首先基于點特征估計基本矩陣，然后分解該基本矩陣獲得攝像機的平移向量和旋轉(zhuǎn)矩陣，據(jù)此計算旋轉(zhuǎn)變換矩陣以使兩幅圖像具有相同的視角；此時，再利用空間相鄰性可獲得線段匹配的候選解集。

此外，長基線的圖像對不再滿足本文所述的單應(yīng)矩陣約束。但是對于室內(nèi)或者城市環(huán)境等人造場景，由于場景中存在大量的平面，而每個平面內(nèi)的線段特征符合由該平面誘導的單應(yīng)矩陣模型約束。在此類場景中，可考慮基于RANSAC方法迭代估計所有平面的單應(yīng)矩陣模型，分別尋找每個平面內(nèi)的匹配線段。這樣，不僅可以剔除不符合任意單應(yīng)矩陣模型的錯誤匹配，同時可以根據(jù)線段所處平面對其進行分組。

如果將本文算法用于視覺SLAM中，雖然特征匹配時間較長，但表1中數(shù)據(jù)表明，完全可以通過在線段提取環(huán)節(jié)挑選出誤差較小、數(shù)量相對較少的線段，從而明顯降低線段匹配所需時間。

References)

[1] LOWE D G. Distinctive image features from scale-invariant keypoints [J]. International Journal of Computer Vision, 2004, 60(2): 91-110.

[2] BAY H, TUYTELAARS T, VAN GOOL L. SURF: Speeded Up Robust Features [C]// ECCV 2006: Proceedings of the 2006 9th Equopean Conference on Computer Vision, LNCS 3951. Berlin: Springer-Verlag, 2006: 404-417.

[3] 武濤,孫鳳池,苑晶,等.一種基于線段特征的室內(nèi)環(huán)境主動SLAM方法[J].機器人,2009,31(2):166-170,178. (WU T, SUN F C, YUAN J, et al. An active SLAM approach based on line segment feature in indoor environment[J]. Robot, 2009, 31(2): 166-170, 178.)

[4] WANG Z, WU F, HU Z. MSLD: a robust descriptor for line matching [J]. Pattern Recognition, 2009, 42(5): 941-953.

[5] ZHANG L, KOCH R. An efficient and robust line segment matching approach based on LBD descriptor and pairwise genometric consistency [J]. Journal of Visual Communication and Image Representation, 2013, 24(7): 794-850.

[6] WANG Z-H, ZHI S-S, LIU H-M. MSHS: the mean-standard deviation curve matching algorithm in HSV space [C]// ICMLC 2012: Proceedings of the 2012 International Conference on Machine Learning and Cybernetics. Piscataway, NJ: IEEE, 2012: 1064-1069

[7] CUI X, KAN J, LI W. A new line matching method based on color invariantsin the RGB orthogonal color space [J]. Journal of Computational Information Systems, 2015, 11(9): 3265-3273.

[8] 王偉璽，安菲佳，王競雪.多重約束條件下的影像直線匹配算法研究[J].測繪科學，2014，39(11):15-19. (WANG W X， AN F J， WANG J X. Line matching algorithm for imagery under multiple constraint conditions [J]. Science of Surveying and Mapping, 2014, 39(11): 15-19.).

[9] 婁安穎，宋偉東，劉薇.基于單應(yīng)矩陣的直線匹配[J].遙感信息，2011(3):9-13. (LOU A Y, SONG W D, LIU W. Matching straight lines on the basic of homography[J]. Remote Sensing Information, 2011(2): 9-13.)

[10] 梁艷，盛業(yè)華，張卡，等.利用局部仿射不變及核線約束的近景影像直線特征匹配[J]. 武漢大學學報(信息科學版)，2014，39(2):299-233. (LIANG Y, SHENG Y H, ZHANG K, et al. Linear feature matching method based on local affine invariant and epiolar constraint close-range images [J]. Geomatics and Information Science of Wuhan University，2014, 39(2): 299-233.)

[11] 李俊瑤,顧宏斌,孫瑾,等.基于多重約束條件的線特征多級匹配方法[J].計算機科學,2014,41(S2): 83-87. (LI J Y, GU H B, SUN J, et al. Multi-lever line matching method based on multiple constraints [J]. Computer Science, 2014, 41(S2): 83-87.)

[12] FAN B, WU F, HU Z. Robust line matching through line-point invariants [J]. Pattern Recognition, 2012, 45(2): 794-805.

[13] KIM H, LEE S. Simultaneous line matching and epipolar geometry estimation based on the intersection context of coplanar line pairs [J]. Pattern Recognition Letters, 2012, 33(10): 1349-1363.

[14] LU W, ULRICH N,SUYA Y. Wide-baseline image matching using line signatures [C]// ICCV 2009: Proceedings of the 2009 IEEE International Conference on Computer Vision. Washington, DC: IEEE Computer Society, 2009:1311-1318.

[15] LI K, YAO J, LU X H. Hierarchical line matching based on Line-Junction-Line structure descriptor and local homography estimation [J]. Neurcomputing, 2016, 184(C): 207-220.

[16] 文貢堅.一種基于特征編組的直線立體匹配全局算法[J].軟件學報,2006,16(12):2471-2484. (WEN G J. A global algorithm for straight line stereo matching based on feature grouping [J]. Journal of Software, 2006, 16(12): 2471-2484.)

[17] FU K-P, SHEN S-H, HU Z-Y. Line matching across views based on multiple view stereo [J]. Acta Automatica Sinica, 2014, 40(8): 1680-1689.

[18] VON G, JAKUBOWICZ J, MOREL J-M, et al. LSD: A fast line segment detector with a false detection control [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(4): 722-732.

[19] HARTLEY R, ZISSERMAN A. Multiple View Geometry in Computer Vision [M]. 2nd ed. New York: Cambridge University Press, 2004: 1-206.

[20] LU Y, SONG D. Visual navigation using heterogeneous landmarks and unsupervised geometric constraints [J]. IEEE Transactions on Robotics, 2015, 31(3): 1-14.

This work is partially supported by the National Natural Science Foundation of China (61305107), the Tianjin Key Research Program of Application Foundation and Advanced Technology (14JCZDJC32500), the Open Fund Project of Fujian Provincial Key Laboratory of Information Processing and Intelligent Control (MJUKF201732), the Fundamental Research Funds for the Central Universities (3122016B006).

LIHaifeng, born in 1984, Ph. D., lecturer. His research interests include computer vision, robot navigation.

HUZunhe, born in 1989, M. S. candidate. His research interests include visual navigation.

FANLongfei, born in 1989, M. S., assistant experimentalist. His research interests include pattern recognition.

JIANGZizheng, born in 1990, M. S. candidate. His research interests include computer vision.

CHENXinwei, born in 1984, Ph. D., lecturer. His research interests include machine learning.

Linesegmentfeaturematchingalgorithmacrossvideoframesbasedongeometricconstraintsand0-1programming

LI Haifeng1,2, HU Zunhe1, FAN Longfei1, JIANG Zizheng1, CHEN Xinwei2*

(1.CollegeofComputerScienceandTechnology,CivilAviationUniversityofChina,Tianjin300300,China；2.FujianProvincialKeyLaboratoryofInformationProcessingandIntelligentControl(MinjiangUniversity),FuzhouFujian350121,China)

To deal with the problems in line segment matching due to occlusion, fragmentation and inaccurate extraction of line segment endpoints, especially when the criteria of “most similar matching” was taken in “multiple-to-multiple” matching which may lead to fateful true correspondences lost, a line segment matching algorithm based on geometric constraints and 0-1 programming was proposed. Firstly, a candidate matching set was initially computed based on the spatial adjacency after correcting the vedio frames. Secondly, the multiple geometric constraints, such as epipolar constraint, homography matrix and point-to-line adjacency, were employed to remove the false positive correspondences. Then, the matching problem was modeled into a large scale 0-1 programming. Finally, a two-stage method based on grouping strategy was designed to solve this problem, so as to realize the “one to one” exact matching of line segment feature. The experimental results show that, compared with LS (Line Sigature) and LJL (Line-Junction-Line) methods, the propsed method has a similar performance in correct matching ratio but a larger matching amount over 60% and 11%, respectively. The proposed method can fulfill the line segment matching across vedio frames, which lays the foundation for line-based visual SLAM (Simultaneously Localization and Mapping).

line segment matching; geometric constraint; 0-1 programming; feature matching; visual SLAM (Simultaneously Localization and Mapping)

TP242

A

2017- 01- 16;

2017- 03- 03。

國家自然科學基金資助項目(61305107)；天津市應(yīng)用基礎(chǔ)與前沿技術(shù)研究計劃重點項目(14JCZDJC32500)；福建省信息處理與智能控制重點實驗室開放課題項目(MJUKF201732)；中央高校基本科研業(yè)務(wù)費資助項目(3122016B006)。

李海豐(1984—)，男，內(nèi)蒙古通遼人，講師，博士，CCF會員，主要研究方向：計算機視覺、機器人導航； 胡遵河(1989—)，男，山東菏澤人，碩士研究生，主要研究方向：視覺導航； 范龍飛(1989—)，男，河北邢臺人，助理實驗師，碩士，主要研究方向：模式識別； 姜子政(1990—)，男，遼寧本溪人，碩士研究生，主要研究方向：計算機視覺； 陳新偉(1984—)，男，福建龍巖人，講師，博士，主要研究方向：機器學習。

1001- 9081(2017)08- 2292- 06

10.11772/j.issn.1001- 9081.2017.08.2292