增強(qiáng)現(xiàn)實(shí)中的視頻對(duì)象跟蹤算法概要

1、229增強(qiáng)現(xiàn)實(shí)中的視頻對(duì)象跟蹤算法陳明，陳一民,黃詩(shī)華,姚爭(zhēng)為（上海大學(xué)計(jì)算機(jī)工程與科學(xué)學(xué)院，上海200072摘要:根據(jù)增強(qiáng)現(xiàn)實(shí)在視頻對(duì)象跟蹤中的應(yīng)用需求，提出一種綜合利用尺度不變 特征變換（SIFT算子、K聚類算法和輪廓檢測(cè)的視頻對(duì)象跟蹤算法。該算法利用簡(jiǎn) 易SIFT獲得輸入圖像的特征點(diǎn)，通過K聚類算法獲得可能的對(duì)象聚類，并采用改進(jìn) 的輪廓處理方法得到對(duì)象邊界，移除孤立點(diǎn),確定對(duì)象特征點(diǎn)，在對(duì)象特征點(diǎn)中獲取增 強(qiáng)現(xiàn)實(shí)應(yīng)用中需要的注冊(cè)點(diǎn)。在關(guān)鍵幀匹配中，只要使用對(duì)象特征點(diǎn)進(jìn)行對(duì)象匹 配。實(shí)驗(yàn)結(jié)果表明，該算法具有運(yùn)行速度快、匹配正確率高的特點(diǎn)，能滿足增強(qiáng)現(xiàn)實(shí) 視頻應(yīng)用的注冊(cè)需求。關(guān)鍵詞:增強(qiáng)現(xiàn)實(shí)

2、；視頻對(duì)象跟蹤；尺度不變特征變換算子；K -means算法;輪廓檢測(cè)Video Object Track ing Algorithm for Augme nted RealityCHEN Mi ng, CHEN Yi-mi n, HUANG Shi-hua, YAO Zhe ng-wei（School of Computer Engin eeri ng and Scie nee, Shan ghai Uni versity, Shan ghai 200072【Abstract 】 According to the application requirement of Augmented Rea

3、lity(AR in video object track ing, this paper proposes a video object track ing algorithm based on Scale-I nv aria nt Feature Tran sform(SIFT operator, K -mea ns clusteri ng algorithm and con tour detectio n. The reduced SIFT is applied to get the feature poi nts from the in put image. The K -means

4、clustering algorithm is applied to cluster the object feature points approximatively. The improved con tour process is applied to get outl ines from the clustered object feature poin ts, removes isolati on poi nts and determ ines the object feature points. The registered point is got from the object

5、 feature points set. In the key frame, it on ly n eeds to use the object feature points to match the object. Experime ntal results show that the algorithm is fast and accurate. It can meet the n eed of AR registeri ng【Key words 】augme nted reality; video object track ing; Scale-I nv aria nt FeatureT

6、ran sform(SIFT operator; K -mea ns algorithm; con tour detect ion計(jì)算機(jī)工程Computer Engineering第36卷第12期Vol.36 No.12 2010 年 6 月June 2010多媒體技術(shù)及應(yīng)用文章編號(hào)：1000 3428(201012-0229 03文獻(xiàn)標(biāo)識(shí)碼:A中圖分類號(hào):TN911.731概述增強(qiáng)現(xiàn)實(shí)(Augmented Reality, AR是一種對(duì)真實(shí)世界信息和虛擬世界信息進(jìn)行 無(wú)縫集成的新技術(shù)。基于視頻的 AR應(yīng)用成本較低且便于在不同環(huán)境中使用，因此， 近年來(lái)發(fā)展較快。在基于視頻的 AR應(yīng)用中，如何精

7、確跟蹤視頻對(duì)象是一個(gè)重要問 題,因?yàn)樵鰪?qiáng)現(xiàn)實(shí)虛實(shí)融合的關(guān)鍵之一是精確注冊(cè)虛擬物體?；谝曨l的AR應(yīng)用通常需要將虛擬物體跟蹤注冊(cè)在一個(gè)實(shí)時(shí)拍攝的實(shí)際視頻對(duì)象上。視頻對(duì)象跟蹤一直是計(jì)算機(jī)視覺的關(guān)鍵，如果一個(gè)視頻序列的每幅關(guān)鍵幀圖像 都重復(fù)同樣的跟蹤算法，計(jì)算量將十分巨大。對(duì)于運(yùn)動(dòng)對(duì)象跟蹤問題,Moscheni等人 提出利用空間、時(shí)間特性來(lái)描述運(yùn)動(dòng)對(duì)象，并實(shí)現(xiàn)對(duì)運(yùn)動(dòng)對(duì)象的分割與跟蹤方法1 ?，F(xiàn)有視頻運(yùn)動(dòng)跟蹤算法包括基于視頻運(yùn)動(dòng)對(duì)象區(qū)域灰度等特征的跟蹤算法、 基于輪廓特征的跟蹤算法、基于運(yùn)動(dòng)估計(jì)的跟蹤算法和基于視覺學(xué)習(xí)的跟蹤算法等2 。 sn ake活動(dòng)輪廓模型算法(Active Con tour M

8、odel, ACM是一種較好的基于輪廓 跟蹤算法3,它定義一個(gè)與輪廓有關(guān)的能量函數(shù)，輪廓的形狀變化和行為變化趨向于 使該能量函數(shù)值變小，直至能量函數(shù)取最小值時(shí)，輪廓形狀定型且輪廓變化停止。在構(gòu)造能量函數(shù)時(shí)只要正確考慮圖像特征、目標(biāo)特征，sn ake輪廓就能收斂在圖像中的目標(biāo)上。但snake及其改進(jìn)算法與初始輪廓給定的位置密切相關(guān)，若給定的初始形 狀和位置不佳，則不易收斂或形狀演化不正確，且要取得理想的輪廓效果，活動(dòng)輪廓算 法演化時(shí)間較長(zhǎng)，不適合實(shí)時(shí)操作。因此，本文提出先利用特征點(diǎn)等方法求出圖像對(duì) 象的大致位置，再進(jìn)行輪廓處理，而不將其作為確定對(duì)象的方法，僅用來(lái)演化大致輪廓，以去除不是對(duì)象的孤立

9、特征點(diǎn)。尺度不變特征變換（Scale-InvariantFeature Transform, SIFT算法4是優(yōu)秀的特征點(diǎn)計(jì)算與匹配算法，其匹配能力較強(qiáng)，能 處理2幅圖像之間發(fā)生平移、旋轉(zhuǎn)、仿射變換時(shí)的匹配問題，因此,本文采用SIFT方法來(lái)初步計(jì)算對(duì)象特征點(diǎn)。對(duì)于對(duì)象分類問題，采用快速的K聚類方法來(lái)區(qū)分聚 類特征點(diǎn),K -means聚類算法是一種分割式聚類方法，其主要目的是先在大量高維特 征點(diǎn)中找出具有代表性的特征點(diǎn)，這些特征點(diǎn)可以稱為類的中心代表點(diǎn)，然后根據(jù)這 些聚類中心，進(jìn)行后續(xù)處理。采用K聚類算法的原因是該算法簡(jiǎn)單，且已被證明是最 快的聚類算法之一。本文提出 SIFT K 聚類輪廓跟蹤算

10、法（SIFT-K -mea ns Con tour Tracki ng, SIFT-K - CT。采用該算法時(shí)，在關(guān)鍵幀匹配中，只要使用對(duì)象特征點(diǎn)進(jìn)行對(duì)象匹配即可。2 SIFT-K -CT跟蹤算法2.1前提與假設(shè)本文僅在攝像機(jī)固定不變的情況下，檢測(cè)視頻運(yùn)動(dòng)對(duì)象的情況，該情況對(duì)于基于 視覺的AR應(yīng)用是一種常見環(huán)境。2.2 SIFT-K -CT算法流程SIFT-K -CT方法由2個(gè)部分組成:（1對(duì)象初始化識(shí)別?；痦?xiàng)目：國(guó)家科技支撐計(jì)劃基金資助項(xiàng)目（2006BAK13B10;上海市重點(diǎn)學(xué)科建 設(shè)基金資助項(xiàng)目（J50103作者簡(jiǎn)介：陳明（1978-,男，博士研究生，主研方向：多媒體 技術(shù);陳一民，教

11、授、博士 生導(dǎo)師;黃詩(shī)華，碩士研究生;姚爭(zhēng)為，博士研究生收稿日期：2010-01-20 E-mail :cmyes230先利用SIFT算子計(jì)算出圖像的特征點(diǎn)集，再利用K -means聚類算法進(jìn)行聚 類操作。聚類數(shù)目最大的幾個(gè)類作為對(duì)象識(shí)別的基礎(chǔ)，由于K -means算法可能產(chǎn)生一些不在對(duì)象中的孤立點(diǎn)，因此采用snake算法來(lái)約束,僅需做幾次迭代取出大概范 圍即可。由于snake迭代基于K聚類基礎(chǔ)，避免了迭代收斂不正確的問題,且只要利 用其去除不在對(duì)象中的孤立特征點(diǎn)，因此迭代次數(shù)約為10次。（2跟蹤識(shí)別。利用 SIFT識(shí)別出的相關(guān)特征點(diǎn)與第（1部分識(shí)別出的對(duì)象點(diǎn)進(jìn)行跟蹤匹配，如果有3個(gè)以 上的特

12、征點(diǎn)匹配，則認(rèn)為該對(duì)象是目標(biāo)對(duì)象。如果無(wú)法確定目標(biāo)對(duì)象，則認(rèn)為對(duì)象不存在或重新識(shí)別新的對(duì)象。識(shí)別對(duì)象成功后進(jìn)入AR應(yīng)用流程。2.2.1對(duì)象初始化識(shí)別對(duì)象初始化識(shí)別過程如下：（1簡(jiǎn)易SIFT檢測(cè)簡(jiǎn)易SIFT檢測(cè)是加速SIFT特征檢測(cè)的過程，文獻(xiàn)4建議對(duì)每個(gè)關(guān)鍵點(diǎn)使用 4>4共16個(gè)種子點(diǎn)來(lái)描述，對(duì)于一個(gè)關(guān)鍵點(diǎn)就可以產(chǎn)生128個(gè)數(shù)據(jù)，即最終形成128 維的SIFT特征向量。由于下一步要對(duì)特征點(diǎn)進(jìn)行分類，因此可以適度減少特征向量 的維度。對(duì)同一幅關(guān)鍵幀圖像的 20次實(shí)驗(yàn)結(jié)果表明，使用3X3X8共72個(gè)維度即 可。如果過于寬松，特征點(diǎn)數(shù)目增加過多，則必然增加K聚類算法的運(yùn)行時(shí)間。（2K -mea

13、 ns 聚類K -means聚類的目的是為了識(shí)別出對(duì)象的大概分布范圍，為下一步snake運(yùn)算提供初始位置。K聚類算法效率的關(guān)鍵是K的初始值，如下：21arg min |j i Kj i i s S其中,j x表示數(shù)據(jù)點(diǎn)的位置坐標(biāo)向量;K為分類數(shù)目，利用均方差最小進(jìn)行聚對(duì)于增強(qiáng)現(xiàn)實(shí)運(yùn)動(dòng)目標(biāo)跟蹤應(yīng)用，設(shè)置5K =就能完成分類。對(duì)于最大聚類是背 景特征的情況，可以使用簡(jiǎn)單的背景減除技術(shù)來(lái)實(shí)現(xiàn)。原始關(guān)鍵幀圖像如圖1所示,圖2給出了分類后的特征點(diǎn)分布結(jié)果。圖1原始關(guān)鍵幀圖像圖2 SIFT-K-CT聚類后的效果(3sn ake 迭代主動(dòng)輪廓模型又稱為snake模型,它主要定義了 snake積分能量函數(shù)，其

14、能量函 數(shù)包括內(nèi)部能量、圖像能量和外部能量。對(duì)象跟蹤的依據(jù)是使其所有能量函數(shù)積分 最小。Kass等人給出了利用變分法來(lái)求解積分最小的方法，可得能量函數(shù)如下：(,(,(,d d ob gr n n n An BnSe O x y O x y C x y x y =/ / (2其中,(,obn O x y表示視頻對(duì)象;(,gr n O x y表示背景;(,n C x y表示2個(gè)區(qū)域之間的邊界曲線。根據(jù)文獻(xiàn)提出的基于直方圖的snake視頻跟蹤方法，實(shí)際的偏微分方程如下：1220(,(,(,(0ob gr n nn nxP P O x y P O x y C x y n tC C? =+_ ? =?

15、(3其中,1P為變化內(nèi)力；2P為變化外力。根據(jù)式(3,從初始輪廓0C出發(fā)，當(dāng)t充分大時(shí),n C收斂于局部極值,n C就是目標(biāo)輪廓。由于本文使 用snake的目的只是為了移除孤立于對(duì)象的聚類特征點(diǎn)，因此僅需要迭代20次就足 夠了，且不必過分關(guān)心演化情況，所以簡(jiǎn)化方程如下：0(,(,(,(0ob grn n n nx O x y O x y C x y ntC C? =- ? ? =? (4最終對(duì)象的特征點(diǎn)集如下：max (j i i O Sn Km eSift I N =>刀(5其中,j O表示要跟蹤的第j個(gè)對(duì)象;i I表示輸入的第i幀關(guān)鍵幀圖像；eSift函數(shù) 表示簡(jiǎn)易SIFT操作;Km

16、函數(shù)表示K -means聚類操作;max Km表示取最大分類的點(diǎn)集;Sn表示snake移除操作;求和表示移除后的所有有效特征點(diǎn)集;i N表示最少的對(duì) 象點(diǎn)集，為匹配需要，3i N =。0j O表示識(shí)別對(duì)象成功，否則，表示識(shí)別失敗。如圖3 所示，對(duì)象外的孤立特征點(diǎn)已移除，不會(huì)再干擾對(duì)象跟蹤過程。AR注冊(cè)效果如圖4所示圖3 SIFT-K-CT對(duì)象特征識(shí)別效果圖4 AR渲染應(yīng)用效果222對(duì)象跟蹤與匹配關(guān)鍵幀對(duì)象的跟蹤與匹配有基于歐氏距離的方法、RANSAC方法等。歐氏距離法是最常用的方法，該方法利用關(guān)鍵點(diǎn)特征向量的歐式距離作為 2幅圖像中關(guān) 鍵點(diǎn)的相似性判定度量。取一幀圖像中的某個(gè)特征點(diǎn)，并找出其與

17、待匹配圖像中歐式距離最近的前幾個(gè)特征點(diǎn)，在這些點(diǎn)中，如果最近的距離與次近的距離比小于某個(gè) 閾值，則認(rèn)為匹配成功。如果降低這個(gè)閾值，SIFT點(diǎn)匹配成功的數(shù)目會(huì)減少，但更加 穩(wěn)定。RANSAC方法能處理錯(cuò)誤率超過50%的數(shù)據(jù)，是最有效的Robust估計(jì)算法之一,在計(jì)算機(jī)視覺等領(lǐng)域得到了廣泛應(yīng)用。SIFT-K -CT的匹配策略分2步進(jìn)行，先使用RNASAC算法進(jìn)行匹配。如果無(wú)法成功匹配對(duì)象，則進(jìn)行仿射不變特征匹配測(cè) 試。利用馬氏距離的仿射不變性7刪除誤匹配特征對(duì)，如式（6所示。SIFT算法跟蹤匹配效果和 SIFT-K -CT對(duì)象跟蹤231 匹配效果分別如圖5和圖6所示圖5 SIFT算法跟蹤匹配效果圖

18、6 SIFT-K-CT對(duì)象跟蹤匹配效果1(2(1(/4,mi i i i Sd d d d =-其中,m是匹配點(diǎn)的對(duì)數(shù)，取m =1,2即可;Sd表示協(xié)方差和；d i表示馬氏距離;A -1表示A的逆矩陣,A表示協(xié)方差矩陣。根據(jù)馬氏距離定義，應(yīng)有d仁d 2, Sd =0b2.2.3 AR注冊(cè)應(yīng)用AR注冊(cè)應(yīng)用過程是從2D圖像坐標(biāo)系到3D相機(jī)坐標(biāo)系映射的過程，包括注冊(cè) 點(diǎn)的確定和注冊(cè)點(diǎn)方向矢量的確定 2個(gè)步驟。(1注冊(cè)點(diǎn)位置估計(jì)注冊(cè)點(diǎn)位置估計(jì)的目的是找出可能的渲染虛擬物體的位置。本文利用特征點(diǎn)的 距離密度概率求核心點(diǎn)的聚類位置。n 00(n ni i i i Max Max Dpr O = H (7其

19、中,n i Max是估計(jì)的最大周圍密度點(diǎn)；00i i O = E2是 i點(diǎn)周圍半徑n中的所有對(duì)象特征點(diǎn)；Dpr表示靠近模擬中心點(diǎn)的 概率。（2方向估計(jì)方向估計(jì)的目的是按正確的姿態(tài)渲染出虛擬物體。本文根據(jù)核心點(diǎn)周圍特征點(diǎn) 的SIFT梯度平均方向求注冊(cè)點(diǎn)的方向矢量。因此，在匹配時(shí)不宜使用簡(jiǎn)易SIFT操 作。為了有效地表征這些特征點(diǎn)，根據(jù)Lowe提出的方法，先將原圖像轉(zhuǎn)化為梯度圖 像,計(jì)算每個(gè)元素的梯度幅值和方向量，再將所檢測(cè)特征點(diǎn)的相應(yīng)位置映射于梯度圖 像中,并設(shè)定一個(gè)有效的鄰域范圍（8 >8,以區(qū)域內(nèi)元素的梯度變化幅值為權(quán)重，計(jì)算方 向量的直方圖，以此作為相應(yīng)特征點(diǎn)的表征向量。3實(shí)驗(yàn)結(jié)果與

20、分析算法性能主要以跟蹤精確度和時(shí)間效率2個(gè)指標(biāo)來(lái)衡量。3.1算法對(duì)象跟蹤利用SIFT算法獲取少量特征點(diǎn)，作為分類算法的輸入，利用最快的K -means分類算法對(duì)特征點(diǎn)進(jìn)行分類，找到最大分類?？赡艽嬖谧畲蠓诸愂潜尘暗那闆r，可以利用背景差分來(lái)解決。如圖5所示，可以觀察到很多錯(cuò)誤匹配情況，無(wú)法跟蹤對(duì)象。如圖6所示,在背景變化的條件下，本文算法依然成功匹配、跟蹤了手 機(jī)對(duì)象。3.2算法時(shí)間性能SIFT-K -CT算法在跟蹤時(shí)僅需要進(jìn)行 Canny邊緣檢測(cè)，跟蹤效果能夠滿足實(shí)時(shí) 要求。不同算法的平均跟蹤時(shí)間比較如表1所示，比較結(jié)果以10 s視頻設(shè)置30個(gè)關(guān)鍵幀圖像匹配為例。圖像分辨率為 640M80。A

21、CM算法以改進(jìn)的snake模型8為 例。ASIFT算法9的效果優(yōu)于Harris-Affine等算法效果較好，因此，本文以ASIFT為例，不再比較其他類似算法表1不同算法的平均跟蹤時(shí)間比較算法名稱平均運(yùn)行時(shí)間/SSIFT 0.3 ASIFT 30.0snake 0.5 SIFT-K -CT 0.14結(jié)束語(yǔ)本文算法適用于對(duì)象跟蹤精度要求高、有實(shí)時(shí)性要求、存在復(fù)雜背景的情況，如虛擬/增強(qiáng)現(xiàn)實(shí)與視頻融合等環(huán)境。但該算法未考慮噪 聲較大的情況，僅采用簡(jiǎn)易的中值濾波，而沒有預(yù)先進(jìn)行濾波處理。另外，當(dāng)圖像精度 不高時(shí)，該算法跟蹤匹配能力不足。下一步工作將盡量減少算法在對(duì)象跟蹤過程中 對(duì)圖像精度的需要，以提高其適用范圍。參考文獻(xiàn)1 Den zler J, Niema nn H. Comb in atio n of Simple Visio n Modules forRobust Real Time Moti on Tracki ngJ. Europea n Tran sacti ons onTelecommunications, 1995, 6(3: 121-137.2 Trucco E, Plakas K. Video Tracking: A Concise SurveyJ. IEEEJournal of Oceanic Engineering, 2006, 31(2