郭陽陽，孫 涵

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

0 引 言

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

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

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

流程如圖1所示。

圖1 流程圖

1 相關工作

1.1 李群與李代數(shù)

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

SO(3),t∈R3}

(1)

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

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

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)的結論推廣到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的圖像跟蹤中，每一幀都需要計算相對于模板圖片的旋轉平移矩陣。假設已知模板圖片以及當前幀兩組匹配的特征點，就可以利用1.1節(jié)中的相關知識求出旋轉平移矩陣。

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

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

(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，即可求出最后的旋轉平移矩陣T。

2 目標圖像識別

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

圖2 模板圖片

識別過程如下所述。

2.1 提取圖像FREAK特征

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

2.2 基于單應性矩陣的特征點匹配結果提純

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

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

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

(15)

矩陣H會將一幅圖像上的點的坐標a=(x1,y1,1)映射到另一幅圖像上的點的坐標b=(x2,y2,1)。因為圖像坐標的Z值都為1，所以由H和cH所得到的b的坐標是一樣的，其中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的矩陣，所以可以構造出一個8×9的矩陣。矩陣構造完成后，要對Ah=0進行求解，然后對A進行SVD分解，即：

A=U*Σ*VT

(20)

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

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

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

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

2.3 求解初始旋轉平移矩陣

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

3 目標圖像跟蹤

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

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

3.1 目標圖像特征點選擇

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

圖3 特征點選取

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

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

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

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

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

3.2 特征點模板匹配

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

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

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

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

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

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

3.3 當前幀旋轉平移矩陣計算

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

4 實驗結果

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

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

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

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

5 結束語

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