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

郭陽(yáng)陽(yáng)，孫 涵

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

0 引 言

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

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

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

流程如圖1所示。

圖1 流程圖

1 相關(guān)工作

1.1 李群與李代數(shù)

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

SO(3),t∈R3}

(1)

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

R滿足屬性RRT=I，I為單位矩陣。將R看作一個(gè)隨時(shí)間變化的函數(shù)，即R(t),有R(t)R(t)T=I，對(duì)等式兩邊求導(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是一個(gè)反對(duì)稱(chēng)矩陣。對(duì)任意一個(gè)3×3反對(duì)稱(chēng)矩陣A，存在一個(gè)向量a=[a1,a2,a3]T，滿足Ab=a×b，其中b為任意三維向量，所以有：

(4)

由此可得：

(5)

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

由此可以得到：

(6)

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

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

sinθA

(7)

(8)

最終得到：

(9)

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

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

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

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

(10)

對(duì)式10變形得：

Gh=b1-b2

(11)

其中：

(12)

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

(13)

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

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

(14)

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

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

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

圖2 模板圖片

識(shí)別過(guò)程如下所述。

2.1 提取圖像FREAK特征

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

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

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

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

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

(15)

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

(16)

(17)

所以總共需要4組點(diǎn)對(duì)來(lái)求得H。式16、17經(jīng)過(guò)變換后，可以寫(xiě)成一個(gè)矩陣A與一個(gè)向量h相乘的形式，如下：

(18)

其中

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

(19)

因?yàn)橛?組點(diǎn)對(duì)，每個(gè)點(diǎn)對(duì)可以寫(xiě)成2×9的矩陣，所以可以構(gòu)造出一個(gè)8×9的矩陣。矩陣構(gòu)造完成后，要對(duì)Ah=0進(jìn)行求解，然后對(duì)A進(jìn)行SVD分解，即：

A=U*Σ*VT

(20)

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

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

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

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

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

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

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

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

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

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

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

圖3 特征點(diǎn)選取

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

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

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

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

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

3.2 特征點(diǎn)模板匹配

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

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

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

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

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

由于確定每個(gè)特征點(diǎn)位置的過(guò)程是獨(dú)立的，因此可以使用多線程來(lái)進(jìn)行加速，進(jìn)一步提高算法運(yùn)行速度。

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

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

4 實(shí)驗(yàn)結(jié)果

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

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

圖4 圖片識(shí)別與跟蹤效果圖

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

5 結(jié)束語(yǔ)

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