夏德芳+劉傳才

摘 要： 增強現(xiàn)實是一種虛實信息融合的技術(shù)。隨著智能手機的普及，移動平臺增強現(xiàn)實的應(yīng)用開發(fā)成了熱點。在智能手機硬件計算資源有限的情況下，基于人工標(biāo)識的移動增強現(xiàn)實系統(tǒng)存在標(biāo)識檢測識別算法計算量大、配準(zhǔn)跟蹤實時性較差等缺陷。針對上述不足，提出了利用水漫填充法和外接矩形的幾何特征快速檢測標(biāo)識4個角點，設(shè)計了基于海明編碼特征的人工標(biāo)識，提高了標(biāo)識的識別速度，并具有一定的抗局部遮擋性能。為了精確快速地求解攝像機位姿，系統(tǒng)采用Levenberg?Marquardt算法優(yōu)化求出的平面單應(yīng)性矩陣。最終根據(jù)優(yōu)化的單應(yīng)性矩陣求解出攝像機位姿，并根據(jù)求出的位姿對虛擬物體加載渲染。實驗結(jié)果表明該系統(tǒng)有良好的實時性和有效性。

關(guān)鍵詞： 移動增強現(xiàn)實； 人工標(biāo)識； 角點檢測； 位姿估計

中圖分類號： TN911?34； TP391 文獻標(biāo)識碼： A 文章編號： 1004?373X（2015）08?0026?05

Fiducial marker based registration algorithm for mobile augmented reality

XIA De?fang， LIU Chuan?cai

（School of Computer Science and Engineering， Nanjing University of Science and Technology， Nanjing 210094， China）

Abstract： Augmented reality is the false and true information fusion technology. With the popularity of smart phones， application development of the mobile platform augmented reality has become a hot spot. Because the mobile augmented reality system based on fiducial marker has some defects of mass calculation and poor rectification tracking real?time performance of identification detection recognition algorithm in the case of limit hardware calculation resource of smart phone， a scheme to detect four corner points quickly by means of the flood?fill method and geometrical characteristics of bounding rectangle is proposed to reduce computation time. The fiducial marker based on hamming code was designed to improve the marker identification speed. In order to quickly and accurately compute the camera external parameters， the plane homography matrix was optimized by using Levenberg?Marquardt iterative algorithm， and then the rendering is loaded on the virtual object on fiducial marker according to the obtained camera external parameters. The experimental results show that the system has perfect real?time performance and effectiveness.

Keywords： mobile augmented reality； fiducial marker； corner detection； pose estimation

0 引 言

增強現(xiàn)實（Augmented Reality，AR）是伴隨著計算機圖形學(xué)、計算機視覺、多傳感器技術(shù)和人機交互技術(shù)等領(lǐng)域的發(fā)展而產(chǎn)生的。增強現(xiàn)實系統(tǒng)借助上述技術(shù)將計算機生成的虛擬物體融合到用戶周圍的真實場景中去，使得用戶從感官效果上確信虛擬物體是其周圍真實場景的組成部分。早期的增強現(xiàn)實系統(tǒng)都是基于桌面電腦和頭戴式顯示設(shè)備。近些年，隨著智能手機硬件和軟件不斷地升級換代，現(xiàn)有的智能手機包含了常用的傳感器和攝像頭顯示屏等，使得智能手機天然地成為了移動增強現(xiàn)實（Mobile Augmented Reality，MAR）系統(tǒng)應(yīng)用推廣的最佳平臺，如圖1所示左邊是一款移動增強現(xiàn)實投籃游戲、右上圖是宜家公司推出的家具增強現(xiàn)實應(yīng)用、右下圖是奔馳公司推出的增強現(xiàn)實應(yīng)用。

圖1 移動增強現(xiàn)實應(yīng)用

Azuma將增強現(xiàn)實總結(jié)為3大特點：虛實結(jié)合、實時交互、三維配準(zhǔn)[1]。增強現(xiàn)實中要做到虛實結(jié)合的無縫性和實時性，就必須精確實時地計算出虛擬圖形在真實世界中的位置（Position）和姿態(tài)（Pose），稱之為位姿估計。位姿計算的方法主要有3種：基于傳感器的跟蹤技術(shù)，基于計算機視覺的跟蹤技術(shù)和基于前兩者技術(shù)的混合跟蹤技術(shù)[1]。第1種方法利用各種傳感器的信息獲得用戶或顯示設(shè)備在真實環(huán)境中的位置和方向，常用的傳感器有：GPS、加速度計和電子羅盤等；第2種方法基于計算機視覺的跟蹤技術(shù)則是通過攝像頭捕獲的視頻圖像計算得到攝像機的位姿來實現(xiàn)虛擬結(jié)合。

基于視覺跟蹤配準(zhǔn)的增強現(xiàn)實系統(tǒng)中又可以分為基于標(biāo)識的跟蹤配準(zhǔn)技術(shù)和無標(biāo)識的跟蹤配準(zhǔn)技術(shù)。基于標(biāo)識跟蹤配準(zhǔn)的增強現(xiàn)實系統(tǒng)，為了達到實時的、魯棒的跟蹤效果，一般是通過在場景中預(yù)先布置標(biāo)識物來實現(xiàn)，標(biāo)識物可分為人工標(biāo)識和自然標(biāo)識。人工標(biāo)識易于識別跟蹤，但破壞了場景的真實性。如由Hirokazu Kato博士開發(fā)、華盛頓大學(xué)HIT Lab維護的增強現(xiàn)實開發(fā)包ARToolKit是此類增強現(xiàn)實系統(tǒng)的典型代表[4]。自然特征標(biāo)識的跟蹤配準(zhǔn)技術(shù)基于不變量的局部描述算子的特征識別及匹配方法，如SIFT，SURF和Freak等算法，克服了人工標(biāo)識局部遮擋后無法識別的缺點，同時自然標(biāo)識的使用使系統(tǒng)更加真實。但是自然標(biāo)識的跟蹤配準(zhǔn)計算量大，智能手機有限的計算能力很難對自然標(biāo)識進行實時跟蹤。無標(biāo)識的跟蹤技術(shù)則可以實時地對環(huán)境進行特征檢測、定位和重建，這種方法不需要預(yù)先存儲標(biāo)識的特征信息，適用于未知環(huán)境，計算更為復(fù)雜，其中SLAM和PTAM/M是此類技術(shù)的典型代表[5]。

因為智能手機計算資源有限，為了獲得實時性的跟蹤，本系統(tǒng)采用人工標(biāo)識的跟蹤技術(shù)。在基于人工標(biāo)識的配準(zhǔn)跟蹤技術(shù)中，都是通過檢測正方形4個角點的位置來估算攝像機的位姿，從而進行虛擬物體的加載。為了能夠在智能手機上體驗到實時的增強現(xiàn)實，提出了利用水漫填充法和外接矩形的幾何特征直接快速檢測標(biāo)識4個角點，并采用Levenberg?Marquardt算法來優(yōu)化求出的平面單應(yīng)性矩陣。最終，根據(jù)優(yōu)化的單應(yīng)性矩陣，求解出攝像機的位姿為虛擬物體加載渲染。

1 攝像機模型

在增強現(xiàn)實系統(tǒng)中，為了使計算機產(chǎn)生的虛擬物體精確地加載到真實世界中，必須知道攝像機在真實世界坐標(biāo)系中的位姿。如圖2所示，在增強現(xiàn)實系統(tǒng)中，虛實配準(zhǔn)常涉及3個坐標(biāo)系的轉(zhuǎn)換關(guān)系：世界坐標(biāo)系、攝像機坐標(biāo)系和圖像坐標(biāo)系。其中，圖像坐標(biāo)系又分為圖像物理坐標(biāo)系和圖像像素坐標(biāo)系。齊次坐標(biāo)是計算機視覺和計算機圖形學(xué)中重要的表示手段之一，它既能夠用來明確區(qū)分向量和點，也能在仿射（線性）幾何變換中使用[6]。齊次坐標(biāo)是將原本n維的向量用一個n+1維向量表示。

[Zcuv1=αx0u000αyv000010RT0T1XwYwZw1] （1）

式（1）為真實世界坐標(biāo)系到圖像像素坐標(biāo)系的轉(zhuǎn)換公式，包括世界坐標(biāo)系到攝像機坐標(biāo)系的剛體轉(zhuǎn)換、攝像機坐標(biāo)系到圖像物理坐標(biāo)系的透視投影轉(zhuǎn)換和圖像物理坐標(biāo)系到圖像像素坐標(biāo)系的轉(zhuǎn)換。[αx=fdx，αy=fy]，其中f是攝像機固有的焦距，[αx， αy， u0， v0]都是攝像機內(nèi)部參數(shù)，用K表示，這些參數(shù)只與攝像頭內(nèi)部結(jié)構(gòu)有關(guān)系，可以通過標(biāo)定技術(shù)得到這些內(nèi)部參數(shù)[7]。R是一個3×3 正交矩陣，T是3×1的平移變量。攝像機相對于標(biāo)識物的位置和方向就可以由旋轉(zhuǎn)矩陣R和平移變量T來表示，這兩個變量就是攝像機外部參數(shù)。

2 人工標(biāo)識的設(shè)計和快速檢測識別

2.1 人工標(biāo)識的設(shè)計

人工標(biāo)識的跟蹤包括檢測和識別。檢測意味著檢測到了候選標(biāo)識，需進一步判斷識別候選標(biāo)識。因為不同的標(biāo)識渲染可能對應(yīng)不同的虛擬物體。目前人工標(biāo)識的識別方法主要分為2種：基于圖像模板匹配的標(biāo)識識別和基于編碼特征的標(biāo)識識別[8]。基于圖像模板匹配的標(biāo)識具有可讀性，標(biāo)識本身帶有一定的信息，例如ARToolKit中使用的標(biāo)識，但需要將校正后的候選圖像與3種光照條件下的4個方向上的標(biāo)準(zhǔn)圖像模板進行逐一匹配，當(dāng)候選標(biāo)識有N個，則需要進行12×N次的模板匹配，這種方法計算量很大，影響增強現(xiàn)實系統(tǒng)實時性。

基于編碼特征的標(biāo)識識別通過對圖像內(nèi)部進行解碼來識別標(biāo)識，不僅提高了標(biāo)識的識別速度，也增強了標(biāo)識的可擴展性[8]。為了提高標(biāo)識的識別效率，本文設(shè)計了一種基于編碼特征的標(biāo)識，如圖3所示。

本系統(tǒng)中所用的人工標(biāo)識如圖3所示：標(biāo)識最外圍一圈是黑色邊界，用于快速檢測是否為候選標(biāo)識。標(biāo)識中心是5×5的柵格，每一行都是海明編碼，第3位和第5位是有效碼，其余3位是校驗碼，可以用來確定標(biāo)識的方向和標(biāo)識內(nèi)的編碼。這種設(shè)計方法總共可以標(biāo)識1 024種不同標(biāo)識ID。

2.2 人工標(biāo)識的快速檢測識別

由于智能手機計算資源的限制，標(biāo)識的檢測識別算法應(yīng)該快速有效?，F(xiàn)階段常見的標(biāo)識檢測主要步驟是：輸入圖像二值化、連通區(qū)域?qū)ふ?、對連通區(qū)域輪廓進行形狀擬合、直線求交點獲得4個角點，其中常常用到Hough變換、輪廓擬合等復(fù)雜計算量方法。如果簡單地將桌面端的增強現(xiàn)實系統(tǒng)移植到移動平臺，必然會降低系統(tǒng)的實時性能。因為大多數(shù)人工標(biāo)識的增強現(xiàn)實系統(tǒng)都是通過檢測四邊形的四個角點求對應(yīng)單應(yīng)性矩陣的，所以本文提出利用區(qū)域填充法找到標(biāo)識最大外接矩形，然后利用最大外接矩形和連通區(qū)域外輪廓來檢測四個角點。算法主要步驟如下：

（1） 利用全局靜態(tài)閾值將輸入圖像二值化；

（2） 從二值圖像的左上角開始逐行掃描圖像，直到遇到黑色像素為止；

（3） 將掃描到的黑色像素標(biāo)記為已處理并設(shè)置為種子點，并在其周圍創(chuàng)造一個外接矩形；

（4） 依次對種子點上下左右遞歸遍歷，遇到黑色像素點就擴大外接矩形；

（5） 當(dāng)沒有黑色像素點能夠被遞歸發(fā)現(xiàn)的時候，就找到了一個連通區(qū)域的最大外接矩形，這個外接矩形中就可能存在一個標(biāo)識；

（6） 繼續(xù)掃描，當(dāng)再次掃描到未被處理過的黑色像素，則重復(fù)上面的步驟（3）和步驟（5）。

在檢測4個角點之前，先將面積很小、縱橫比較大的外接矩形去除掉。接下來檢測外接矩形內(nèi)連通區(qū)域的外輪廓上可能存在的4個角點。連通區(qū)域的外接矩形可能是正方形也可能是長方形，統(tǒng)一將外接矩形按比例縮放成正方形，然后依次從外接矩形的4個頂點出發(fā)，在連通區(qū)域中的輪廓中尋找距離每個頂點最遠的一個點，作為檢測到的角點。因為之前是將外接矩形尺度化正方形，所以檢測到角點的具體坐標(biāo)位置后，需要利用之前的尺度還原。如下圖4所示是檢測出的標(biāo)識的4個角點。以上檢測的是粗略地估計4個角點，當(dāng)下一步確認標(biāo)識合法以后，會進行角點亞像素級別的精確化檢測。

接著利用4個角點，計算平面與平面之間的平面單應(yīng)性矩陣，將標(biāo)識圖像校正到100×100像素的圖像，并且將其二值化?？梢詫?biāo)識校正為更小的圖像，加快標(biāo)識的校正速度，但這可能會降低標(biāo)識的識別率。隨后，根據(jù)海明編碼規(guī)則，為標(biāo)識的4個方向解碼，確定標(biāo)識的正方向和內(nèi)部編碼。在Android平臺上，實驗檢測了1 000幀的視頻序列，計算了本文所提算法和ARToolKitPlus的平均檢測時間和平均識別時間，結(jié)果如表1所示。

圖5是抗遮擋性方面的對比示意圖。圖5（a）是本文算法實驗結(jié)果，（b）是ARToolKitPlus算法實驗結(jié)果。在抗遮擋性方面，ARToolKitPlus先天不足，因為ARToolKitPlus首先對連通區(qū)域外輪廓進行直線擬合，然后通過直線求交點檢測到角點，所以一旦連通區(qū)域外輪廓形狀發(fā)生細微改變都會檢測失敗。而本文所提出的角點檢測算法并不是通過直線擬合求交點獲得的，所以對標(biāo)識局部遮擋具有一定的魯棒性。本算法和ARToolKitPlus算法在遮擋情況下進行了對比實驗。 本算法在局部淺色小遮擋情況下不會造成標(biāo)識檢測失敗，當(dāng)遮擋物的顏色接近于黑色時候，因為連通區(qū)域?qū)ふ沂?，?dǎo)致標(biāo)識檢測錯誤，如圖5左下角標(biāo)識被黑色鑰匙局部遮擋后效果。 ARToolKitPlus的抗遮擋性能則很差，只要邊緣被遮擋后，直線無法檢測，則最終標(biāo)識無法檢測，如圖5（b）所示。

3 攝像機參數(shù)求解

標(biāo)識的內(nèi)部編碼決定了加載哪個虛擬物體，攝像機的外參數(shù)則決定了虛擬物體在屏幕中加載的位置。在多標(biāo)識的系統(tǒng)中，每一個標(biāo)識有獨立的坐標(biāo)系。因此，需計算攝像機相對于每一個標(biāo)識的外參數(shù)。ARToolKit是通過標(biāo)識外輪廓的4條邊之間的關(guān)系來求解攝像機的外參數(shù)，往往會因為圖像噪聲導(dǎo)致的直線偏移而不能精確地計算出外參數(shù)[4]。為了精確快速地求解攝像機位姿，首先根據(jù)圖像像素坐標(biāo)系和世界坐標(biāo)系對應(yīng)的4對點，采用Levenberg?Marquardt算法來優(yōu)化求出的平面單應(yīng)性矩陣。最終，根據(jù)優(yōu)化的單應(yīng)性矩陣求解出攝像機位姿，并根據(jù)求出的位姿為虛擬物體加載渲染。在標(biāo)識的角點檢測過程中，由于角點的位置精度不夠，需要精確地定位角點位置。使用OpenCV中的cornerSubPix函數(shù)將之前檢測的4個角點位置精度提高到亞像素級別。

因為標(biāo)識的4個角點都在世界坐標(biāo)系Zw=0的平面上，所以可將式（1）改寫為：

[Zcuv1=KR1R2T001XwYw1=HXwYw1H=h11h12h13h21h22h23h31h32h33] （2）

式中：H是3×3的平面單應(yīng)性矩陣。將式（2）中的齊次系數(shù)Zc消去，可得式（3）：

[XwYw1000-uXw-uYw-u000XwYw1-vXw-vYw-vh11h12h13h21h22h23h31h32h33=0] （3）

式（3）是一個形如Ah=0的矩陣方程。當(dāng)有n對對應(yīng)的像素坐標(biāo)系點和世界坐標(biāo)系點時，則A是一個2n×9的矩陣。顯然這是個線性齊次方程組，只需要4對圖像像素點和世界坐標(biāo)系點，就能解出H單應(yīng)性矩陣。當(dāng)超過4個相對應(yīng)點的時，形成的是一個超定方程組，這是一個最優(yōu)解問題?？梢灾苯忧蠼釧矩陣的奇異值分解（SVD），對應(yīng)于最小特征值的單位特征矢量即是解h矩陣。奇異值分解方法經(jīng)常用來解決最小平方誤差問題，這種方法算出來的h并沒有考慮攝像機成像過程中的非線性畸變問題，為了提高精度，非線性最優(yōu)化算法不可避免[8]。

采用Levenberg?Marquardt算法來優(yōu)化單應(yīng)性矩陣，這個算法是解決非線性最小二乘法的有效方法。它是Marquardt在Levenberg工作的基礎(chǔ)上提出的一種迭代策略，是對Gauss?Newton方法的改進，相當(dāng)于Gauss?Newton和梯度下降法的結(jié)合，具有良好的穩(wěn)定性。可以建立以下優(yōu)化目標(biāo)函數(shù)：

[fh=ipi-HPi2] （4）

單應(yīng)性矩陣優(yōu)化旨在使通過單應(yīng)性矩陣投影到圖像的點與實際獲得的圖像點之間的幾何誤差最小，即式（4）中[pi]對應(yīng)圖像中實際測得的點，[HPi]則是世界坐標(biāo)系中的點通過單應(yīng)性矩陣投影到像素坐標(biāo)系的坐標(biāo)。

迭代增量式如式（5）所示：

[Δh=JThJh+uI-1JTf1h] （5）

式中：JT（h）是f（h）的雅克比矩陣；Δh是每次迭代的增量。通過迭代，可以最終確定單應(yīng)性矩陣的最優(yōu)解。通過上面計算優(yōu)化出來的單應(yīng)性矩陣以及事先標(biāo)定好的攝像機內(nèi)參數(shù)K，攝像機外參數(shù)可用下式求出：

[r1=ZcK-1h1r2=ZcK-1h2r3=r1×r2t=ZcK-1h3Zc=1K-1h1=1K-1h2] （6）

式中，通常稱Zc為尺度因子；[R=r1r2r3]，單應(yīng)性矩陣[H=h1h2h3]。根據(jù)以上得到的攝像機外參數(shù)將虛擬物體加載到標(biāo)識上，效果如圖6所示。

4 結(jié) 語

隨著智能手機技術(shù)的發(fā)展和普及，移動增強現(xiàn)實技術(shù)必將為日常生活帶來非同凡響的新體驗。移動平臺應(yīng)用實時性等體驗是最需要解決的問題，本文提出了一種基于人工標(biāo)識的快速檢測識別方法，通過實驗，這種方法極大提高了增強現(xiàn)實應(yīng)用的實時性，對于簡單環(huán)境中的增強現(xiàn)實具有良好的用戶體驗。

參考文獻

[1] AZUMA R. A survey of augmented reality [J]. Teleoperators and Virtual Environments， 1997， 6（4）： 355?385.

[2] 李玉，王涌天，劉越.基于彩色標(biāo)志點的增強現(xiàn)實注冊算法研究[J].系統(tǒng)仿真學(xué)報，2008，20（3）：654?656.

[3] BAGGIO Daniel Lélis， EMAMI S， ESCRIV? David Millán. Master OpenCV with practical computer vision projects [M]. [S.l.]： Packt Publishing， 2012： 46?92.

[4] KATO H， BILLINGHURST M. Marker tracking and HMD calibration for a video?based augmented reality conferencing system [C]// Proceedings of 2nd IEEE and ACM International Workshop on Augmented Reality. [S.l.]： IEEE， 1999： 85?94.

[5] DAVISON A J. Real?time simultaneous localisation and mapping with a single camera [C]// Proceedings of the Ninth IEEE International Conference on Computer Vision. [S.l.]： IEEE， 2003： 1403?1406.

[6] 邱子鑒.基于改進隨機蕨的增強現(xiàn)實注冊算法的設(shè)計與實現(xiàn)[D].哈爾濱：哈爾濱理工大學(xué)，2014.

[7] ZHANG Z. Flexible camera calibration by viewing a plane from unknown orientations [C]// Proceedings of International Conference on Computer Vision. Corfu， Greece： ICCV， 1999： 666?673.

[8] GANDY M， MACINTYRE B. Designer's augmented reality toolkit， ten years later： implications for new media authoring tools [C]// Proceedings of the 27th annual ACM symposium on User interface software and technology. New York： ACM， 2014： 627?636.

[9] 張振杰.基于共面特征點的視覺導(dǎo)航位姿測定技術(shù)研究[D].鄭州：解放軍信息工程大學(xué)，2013.

[10] ALAHI A， ORTIZ R， VANDERGHEYNST P. FREAK： Fast retina key point [C]// Proceedings of 2012 IEEE Conference on Computer Vision and Pattern Recognition. [S.l.]： IEEE， 2012： 510?517.

[11] 周國眾.移動增強現(xiàn)實關(guān)鍵技術(shù)及應(yīng)用[J].測繪與空間地理信息，2012，35（9）：141?144.

[12] 馬頌德，張正友.計算機視覺：計算理論與算法基礎(chǔ)[M].北京：科學(xué)出版社，1998.

[13] WANGER D. Handheld augmented reality [D]. Graz： Graz University of Technology， 2007.