基于單目AR環(huán)境下的目標(biāo)識別與跟蹤算法

郭陽陽，孫 涵

(南京航空航天大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，江蘇 南京 211106)

0 引 言

增強現(xiàn)實技術(shù)(augmented reality，AR)是一種把原本在現(xiàn)實世界的一定時間空間范圍內(nèi)很難體驗到的實體信息(如視覺信息、聲音、味道、觸覺等)，通過科學(xué)技術(shù)模擬仿真后再疊加到現(xiàn)實世界被人類感官所感知，從而達(dá)到超越現(xiàn)實的感官體驗的技術(shù)。這種技術(shù)的目標(biāo)是在屏幕上把虛擬世界套在現(xiàn)實世界并進(jìn)行互動。

增強現(xiàn)實技術(shù)的應(yīng)用可以給人們的生活帶來很多便利，比如在城市規(guī)劃以及房產(chǎn)開發(fā)中，開發(fā)者可以使用增強顯示技術(shù)模擬城市開發(fā)以及房屋建造的過程，有利于設(shè)計與管理人員對各種規(guī)劃方案進(jìn)行輔助設(shè)計與方案評審，規(guī)避設(shè)計風(fēng)險。同樣，增強現(xiàn)實技術(shù)也可以給人們的生活帶來很多樂趣，如Pokemon Go就是一款利用增強現(xiàn)實技術(shù)設(shè)計而成的游戲。

三維配準(zhǔn)[1-3]是增強現(xiàn)實技術(shù)中的最核心技術(shù)。在增強現(xiàn)實技術(shù)中配準(zhǔn)的目的是對影像數(shù)據(jù)進(jìn)行幾何上的精確理解。這樣，要疊加的數(shù)據(jù)的定位問題就成了增強現(xiàn)實技術(shù)中最關(guān)鍵的問題。其中，數(shù)據(jù)的定位可以用旋轉(zhuǎn)平移矩陣來表示，而求取旋轉(zhuǎn)平移矩陣就是文中要研究的主要內(nèi)容。

流程如圖1所示。

圖1 流程圖

1 相關(guān)工作

1.1 李群與李代數(shù)

AR是一種基于3D模型的技術(shù)，文中采用的圖片位置的表示方法為旋轉(zhuǎn)矩陣和平移矩陣，因此主要介紹三維歐氏群SE(3)以及對應(yīng)的李代數(shù)se(3)。

SO(3),t∈R3}

(1)

其中，R為旋轉(zhuǎn)矩陣；t為平移矩陣；SO(3)為三維旋轉(zhuǎn)群。

R滿足屬性RRT=I，I為單位矩陣。將R看作一個隨時間變化的函數(shù)，即R(t),有R(t)R(t)T=I，對等式兩邊求導(dǎo)得：

R(t)'R(t)T+R(t)TR(t)'=0

(2)

于是：

R(t)'R(t)T=-(R(t)'R(t)T)T

(3)

可以看出，R(t)'R(t)T是一個反對稱矩陣。對任意一個3×3反對稱矩陣A，存在一個向量a=[a1,a2,a3]T，滿足Ab=a×b，其中b為任意三維向量，所以有：

(4)

由此可得：

(5)

將SO(3)的結(jié)論推廣到SE(3)，由于SE(3)多了平移的三個自由度，因此，使用p=[p1,p2,p3]來表示平移。

由此可以得到：

(6)

根據(jù)矩陣的指數(shù)映射，使用θ和α表示向量a的模長和方向，可以得到：

exp(θα)=cosθI+(1-cosθ)aaT+

sinθA

(7)

(8)

最終得到：

(9)

1.2 迭代最近鄰點(iterative closest points，ICP)算法

在單目AR的圖像跟蹤中，每一幀都需要計算相對于模板圖片的旋轉(zhuǎn)平移矩陣。假設(shè)已知模板圖片以及當(dāng)前幀兩組匹配的特征點，就可以利用1.1節(jié)中的相關(guān)知識求出旋轉(zhuǎn)平移矩陣。

視頻的每一幀隨時間變化而變化，因此，可以將視頻看作一個隨時間變化的函數(shù)，這就滿足了李群與李代數(shù)的基本條件。下面構(gòu)造矩陣T。由于每次運算是以前一幀的矩陣為初始矩陣，所以矩陣初始化在模板圖像識別過程實現(xiàn)，實驗中，將R矩陣初始化為單位矩陣，t矩陣元素全為0，經(jīng)過多次迭代得到最終矩陣。

假設(shè)a為模板圖像特征點坐標(biāo)，b1為當(dāng)前幀特征點坐標(biāo)，b2為上一幀特征點坐標(biāo)(a、b1、b2都為齊次坐標(biāo))，對視頻函數(shù)求導(dǎo)得：

(10)

對式10變形得：

Gh=b1-b2

(11)

其中：

(12)

h=(a1,a2,a3,p1,p2,p3)T

(13)

由于h有6個參數(shù)，G只有3行，3個方程不能求得6個未知數(shù)，所以需要有多個點參與，最后求得h如下：

h=(GTG)-1GT(b1-b2)

(14)

求得h后，根據(jù)式7～9，即可求出最后的旋轉(zhuǎn)平移矩陣T。

2 目標(biāo)圖像識別

在目標(biāo)跟蹤問題中，目標(biāo)識別是目標(biāo)跟蹤的前提。文中使用的模板目標(biāo)圖片如圖2所示。

圖2 模板圖片

識別過程如下所述。

2.1 提取圖像FREAK特征

常見的圖像特征描述子有SIFT[4]、SURF[5]、ORB以及HOG特征等，但是這些特征描述子有的提取速度慢，有的局限性大，而圖像識別與跟蹤對實時性要求很高，因此這些特征描述子都不能滿足要求。FREAK[6]特征也許精度不如SIFT以及SURF，但是其提取速度快，可以滿足實時性的要求；而對于FREAK特征精度的問題，可以對FREAK特征進(jìn)行多次優(yōu)化，以保證最后得到的匹配點的正確性。

2.2 基于單應(yīng)性矩陣的特征點匹配結(jié)果提純

在提取出模板以及視頻當(dāng)前幀的FREAK特征后，可以得到兩組匹配的特征點，為保證匹配特征點的精確度，要將其中一些匹配錯誤的特征點去掉。具體過程如下：

(1)Hough投票[7-8]。每個特征點的信息中都包含坐標(biāo)、旋轉(zhuǎn)角度以及尺度的四維信息，利用這四維信息對每個特征點進(jìn)行投票，選擇得票最多的bin上的特征點。

(2)計算單應(yīng)性矩陣[9]。單應(yīng)性矩陣為一個3×3的矩陣，表示為：

(15)

矩陣H會將一幅圖像上的點的坐標(biāo)a=(x1,y1,1)映射到另一幅圖像上的點的坐標(biāo)b=(x2,y2,1)。因為圖像坐標(biāo)的Z值都為1，所以由H和cH所得到的b的坐標(biāo)是一樣的，其中c為常數(shù)。因此，將h33固定為1，這樣H就還有8個自由度，根據(jù)每組點對，可以得到2個方程，如下：

(16)

(17)

所以總共需要4組點對來求得H。式16、17經(jīng)過變換后，可以寫成一個矩陣A與一個向量h相乘的形式，如下：

(18)

其中

h=(h11,h12,h13,h21,h22,h23,h31,h32,h33)T

(19)

因為有4組點對，每個點對可以寫成2×9的矩陣，所以可以構(gòu)造出一個8×9的矩陣。矩陣構(gòu)造完成后，要對Ah=0進(jìn)行求解，然后對A進(jìn)行SVD分解，即：

A=U*Σ*VT

(20)

則V的最后一列即為所求的h，將h變形成3×3矩陣，即為H。

(3)選擇最優(yōu)單應(yīng)性矩陣。在步驟1中求得多組匹配的特征點，而求解單應(yīng)性矩陣只需要四組匹配的特征點，因此，可以多次求解單應(yīng)性矩陣，然后尋找其中的最優(yōu)解。

首先，要確定兩組點的對應(yīng)關(guān)系是否一致，例如：在模板圖像中的四個點可以按照順時針方向連接起來，則視頻幀中對應(yīng)的點也要能夠按照順時針方向連接起來，如果不能，就要重新選取四個點；經(jīng)過多次上述步驟后，可以得到多個單應(yīng)性矩陣，然后將所有點對代入到每個單應(yīng)性矩陣中，計算每個單應(yīng)性矩陣的誤差和，選擇誤差最小的單應(yīng)性矩陣作為最優(yōu)解。

(4)判斷所求的單應(yīng)性矩陣是否滿足條件。將所有匹配的特征點對代入到單應(yīng)性矩陣中，設(shè)定一個誤差閾值，計算點對中誤差小于閾值的數(shù)量，如果數(shù)量大于一定值，則將這些特征點對記錄下來，作為提純后的特征點來計算旋轉(zhuǎn)平移矩陣。

2.3 求解初始旋轉(zhuǎn)平移矩陣

經(jīng)過特征點的匹配及一系列優(yōu)化過程，得到了模板圖片與視頻中圖片的兩組匹配的特征點對，利用ICP[10]算法可以求得初始的旋轉(zhuǎn)平移矩陣。

3 目標(biāo)圖像跟蹤

在第二節(jié)得到了模板圖像所在的第一幀圖像，以及初始的旋轉(zhuǎn)平移矩陣，本節(jié)將要就模板圖片的跟蹤以及求解每一幀的旋轉(zhuǎn)平移矩陣展開討論。

模板圖片跟蹤的實時性要求比識別高，所以就不能使用提取特征點再匹配這樣耗時比較高的方法，然而在跟蹤過程中，視頻前后兩幀模板目標(biāo)圖片所在的位置并不會發(fā)生太大的變化，因此，可以使用模板匹配的方法，在上一幀特征點坐標(biāo)的周圍找到當(dāng)前幀特征點的坐標(biāo)；由1.1節(jié)介紹的李群與李代數(shù)內(nèi)容，可以使用六個自由度的矩陣的導(dǎo)數(shù)來求出旋轉(zhuǎn)平移矩陣，而視頻流可以看作一個隨時間變化的連續(xù)函數(shù)，連續(xù)兩幀的坐標(biāo)差可以看作是函數(shù)的導(dǎo)數(shù)。有了上面這些理論后，就可以利用上一幀求得的特征點坐標(biāo)以及旋轉(zhuǎn)平移矩陣來求得當(dāng)前幀的特征點以及旋轉(zhuǎn)平移矩陣。算法的具體過程如下所述。

3.1 目標(biāo)圖像特征點選擇

為了讓特征點盡量分散以及保證特征點的穩(wěn)定性，選擇以下類型的特征點，如圖3所示(其中圓形特征點為(1)～(4)所選擇的特征點，菱形特征點為(5)選擇的特征點)。

圖3 特征點選取

(1)選擇特征點中距離所有特征點的中心點最遠(yuǎn)的點；

(2)選擇距離(1)中選擇的特征點最遠(yuǎn)的特征點；

(3)選擇距離(1)和(2)選擇的特征點所連成的直線距離最遠(yuǎn)的特征點；

(4)選擇與(1)、(2)和(3)選擇的特征點所圍成的四邊形面積最大的特征點；

(5)選擇圖像上一幀所使用的特征點。

3.2 特征點模板匹配

在上一幀中，已經(jīng)得到了所需要的特征點位置，那么在當(dāng)前幀中得到對應(yīng)的特征點的位置就成了關(guān)鍵性的問題。由于前后兩幀特征點的位置變動不會很大，因此，文中使用模板匹配[11-12]的方法，在上一幀特征點的周圍匹配當(dāng)前幀的特征點。具體過程如下：

(1)選定特征點模板：在模板圖片中，以特征點位置為中心，截取一個12×12(見圖3)的patch，以這個patch作為當(dāng)前特征點模板。

(2)劃定當(dāng)前幀特征點位置范圍：由于前后兩幀特征點位置不會變化很大，因此，以上一幀特征點位置為中心，在當(dāng)前幀中截取一個36×36的patch，作為當(dāng)前幀特征點的范圍。

(3)確定特征點位置大概范圍[13]：特征點的位置在36×36的小patch中，但是如果對36×36的每一個點都進(jìn)行模板匹配，這樣效率無疑會很低，因此，可以選取一個特定步長，先大致確定特征點的范圍，以提升效率。在36×36的范圍內(nèi)，以3為步長，比較以當(dāng)前點為中心截取的12×12的patch與模板patch的差異，選出兩個差異最小的點。選取兩個差異最小的點，是為了保證得到的結(jié)果是全局最小，而不是局部最小。

(4)確定特征點位置：在步驟3中，得到了兩個5×5的特征點范圍，對這兩個5×5的patch中的每一個點與模板patch進(jìn)行模板匹配，選取差異最小的一個點作為特征點位置。

由于確定每個特征點位置的過程是獨立的，因此可以使用多線程來進(jìn)行加速，進(jìn)一步提高算法運行速度。

3.3 當(dāng)前幀旋轉(zhuǎn)平移矩陣計算

在3.2節(jié)中，計算出了與模板圖片特征點對應(yīng)的當(dāng)前幀中特征點的位置，這樣就得到了兩組匹配的特征點[14]，可以使用1.2節(jié)中的ICP算法進(jìn)行求解。在ICP算法中，以上一幀旋轉(zhuǎn)平移矩陣為初始矩陣，兩幀之間特征點位置的差作為導(dǎo)數(shù)，ICP算法的條件得以滿足，可以求得當(dāng)前幀的旋轉(zhuǎn)平移矩陣。然后將當(dāng)前幀作為上一幀，迭代求出每一幀的旋轉(zhuǎn)平移矩陣。

4 實驗結(jié)果

實驗運行環(huán)境為Windows10，處理器頻率為3.60 GHz，鏡頭分辨率設(shè)為480×360。實驗中圖片識別和圖片跟蹤在兩個線程下進(jìn)行，其中，圖片識別的過程在60 ms左右，圖片跟蹤如果在單線程下運行，每一幀的跟蹤時間大概為20 ms左右，如果模板匹配過程在多線程下運行，跟蹤速度明顯加快。實驗效果如圖4所示。

首先對目標(biāo)圖片識別過程進(jìn)行時間復(fù)雜度分析。在特征點匹配過程中使用了暴力匹配的方法，則匹配過程時間復(fù)雜度為O(n2)；求解單應(yīng)性矩陣每4個特征點為一組，求解出n個單應(yīng)性矩陣，則時間復(fù)雜度為O(kn)；求解出單應(yīng)性矩陣后，每個特征點都與多個單應(yīng)性矩陣計算誤差，則時間復(fù)雜度為O(kn)；ICP算法過程中，選出的n特征點迭代地更新矩陣，直至收斂，則時間復(fù)雜度為O(kn)。

圖4 圖片識別與跟蹤效果圖

目標(biāo)圖片跟蹤過程的時間復(fù)雜度為：特征點選擇過程時間復(fù)雜度為O(n)；特征點模板匹配過程中，n個特征點中的每個點都要與patch中的k個點進(jìn)行模板匹配，則時間復(fù)雜度為O(kn)。

5 結(jié)束語

文中提出了一種基于單目AR[15]的圖像檢測及跟蹤算法。該算法首先對模板圖像提取FREAK特征，然后在視頻的每一幀中提取FREAK特征與模板圖像特征進(jìn)行比較，通過Hough投票、計算單應(yīng)性矩陣等過程優(yōu)化特征點的匹配結(jié)果，利用ICP算法求得圖像的初始旋轉(zhuǎn)平移矩陣，完成檢測過程；對于圖像的跟蹤過程，利用視頻上一幀中使用的特征點，通過模板匹配求得本幀中對應(yīng)特征點的位置，然后利用ICP算法迭代求出視頻每一幀的旋轉(zhuǎn)平移矩陣。實驗結(jié)果表明，該算法能夠快速對目標(biāo)圖片進(jìn)行識別并且能夠?qū)崟r跟蹤目標(biāo)圖片的位置，對于AR中目標(biāo)圖片的識別與跟蹤具有重要意義。