使用軌跡分段分析的雙向跟蹤的製作方法

2023-05-24 18:58:31 2

專利名稱：使用軌跡分段分析的雙向跟蹤的製作方法
使用軌跡分段分析的雙向跟蹤扭旦 冃足對指定對象(即目標對象)的視覺跟蹤是具有許多有用的應用的計算機視 覺的領域。例如，可以在視頻監控、人機界面、數字視頻編輯等中使用視覺跟 蹤。 一般地，視覺跟蹤在給定觀察(諸如視頻序列)期間跟蹤目標對象。不幸 的是，視覺跟蹤技術在幾種情況下難以跟蹤目標對象。例如， 一種情況是當目標對象經歷突然移動時，諸如來自目標對象自身的 意外動態改變或來自照相機的突然移動，視覺跟蹤技術將難以跟蹤目標對象。 另一種情況是當類似樣子的對象接近目標對象時，視覺跟蹤技術將有困難。在 這種情況下，跟蹤技術難以區分兩個對象中哪個是目標對象。當遮擋發生且目 標對象部分或完全被另一對象遮掩時，視覺跟蹤也是有困難的。總體而言，大多數跟蹤技術基於直至時間t的觀察使用遞歸估計來估計目 標對象在當前時間t的位置。在貝葉斯構架中，跟蹤問題通常被公式化為給定 所有觀察^'情況下，狀態^的時間演化後驗分布的遞歸估計，這樣使得formula see original document page 6(1)遞歸估計有兩個主要的優勢l)高S 的計算；以及2)自然符合實時或在線跟 蹤應用。然而，許多真實世界的應用適合離線跟蹤的類別，諸如視頻監控中的事件 統計、基於對象的視頻壓縮、家庭視頻編輯、視頻評註、視覺動作捕捉等。因 此，也將遞歸方式應用於離線視覺跟蹤。當完成這個時， 一般首先通過指定一 個或多個關鍵幀將長輸入視頻序列分解成短序列。指定的關鍵幀可以是視頻序 列中的任何幀。每個關鍵幀包含指定要跟蹤的對象(即目標對象)的對象模板。 使用這些經分解的短序列的視覺跟蹤通常被稱為基於關鍵幀的跟蹤。遞歸方式 於是以前向或後向中應用到每個短序列。然而，該方法通常在序列中間某處失 敗。當這種情況發生時，就在失敗的位置添加另一關鍵幀。雖然添加新的關鍵幀改進了視覺跟蹤的結果，但是使用試湊法方式添加新 的關鍵幀是極端耗時的。因此，持續需要改善用於離線應用的跟蹤技術。概述本視頻跟蹤技術基於從整體狀態序列的開始和結束關鍵幀獲取的兩個對象模板輸出目標對象的最大後驗(MAP)解答。該技術首先通過在序列的每個幀中生成本地二維模式的稀疏集來最小化序列的整體狀態空間。二維模式被轉 換成三維體中的三維點。使用譜聚技術來群集三維點，其中每個群集對應於目 標對象的可能的軌跡分段。如果在序列中有遮擋，那麼就生成遮擋分段，這樣 可以獲得目標對象的最佳軌跡。提供本概述以便用簡化的形式介紹將在以下詳細描述中進一步描述的一 些概念。本概述並不旨在確定所要求保護的主題的關鍵或必要特徵，也不旨在 用於幫助確定所要求保護的主題的範圍。附圖簡述參考附圖描述了非限制性和非窮盡性的實施例，其中在所有各種視圖中， 除非另外指明，否則相同的參考編號指示相同的部件。為方便起見，參考編號 的最左面的位標識了該參考編號首次出現所在的特定附圖。

圖1是依照一個實施例可以用於實現此處所描述的視頻跟蹤技術的說明 性系統。圖2是示出依照一個實施例有效地減小狀態空間使得可以高效地獲取 MAP解答的示例性視頻跟蹤過程的流程圖。圖3是示出依照一個實施例適用於圖2的視頻跟蹤過程的示例性軌跡分段 分析過程的流程圖。圖4是示出依照一個實施例可以為每個幀獨立執行的二維提取過程的流 程圖。該過程適用於圖3的軌跡分段分析過程。圖5是一組示例性說明，其中頂行顯示來自視頻序列的經簡化的幀，而底 行顯示來自圖4的示例性二維提取過程的結果。圖6是示出依照一個實施例使用譜聚的示例性三維軌跡分段提取過程的 流程圖。該過程適用於圖3的示例性軌跡分段分析過程。圖7是示出依照一個實施例的示例性遮擋分析過程的流程圖。該過程適用於圖2的示例性視頻跟蹤過程。圖8是示出依照一個實施例的示例性雙向樹成長過程的流程圖。該過程適 用於圖7的示例性遮擋分析過程。圖9是描繪圖7所示的遮擋分析過程期間生成的示例性遮擋軌跡的圖表。 圖10-13是示出依照本跟蹤技術的一個實施例，在各個處理階段的結果的 一組示例性圖表。圖14示出依照本跟蹤技術的一個實施例，用作各個處理階段中的輸入的 來自視頻序列的若干個經簡化的示例性幀。在該示例中，各個處理階段生成圖 10-13中的該組圖表。詳細描述以下描述針對基於從整體狀態序列的開始和結束關鍵幀獲取的兩個對象 模板，輸出後標對象的最大後驗(MAP)解答的視頻跟蹤技術。總體而言，該 技術首先通過在序列的每個幀中生成本地二維模式的稀疏集來最小化序列的 整體狀態空伺。二維模式被轉換成三維體中的三維點。使用譜聚技術來群集三 維點，其中每個群集對應於目標對象的可能的軌跡分段。如果在序列中有遮擋， 那麼就生成遮擋分段，這樣可以獲得目標對象的最佳軌跡。本視頻跟蹤技術處 理突然移動、含糊不清以及短/長時段的遮擋。現在詳細描述本視頻跟蹤技術的 這些和其他方面。圖1是依照一個實施例用於實現此處描述的視頻跟蹤技術的說明性系統。 該系統包括諸如計算設備100的計算設備。計算設備100表示任何類型的計算 設備，諸如個人計算機、膝上型計算機、伺服器、遊戲控制臺、手持式或移動 設備(例如蜂窩電話、數字助理)等。在最基本的配置中，計算設備100通常 至少包含一個處理單元102和系統存儲器104。根據確切的配置和計算設備的 類型，存儲器104可以是易失性的(諸如RAM)、非易失性的(諸如ROM、 快閃記憶體等等)或這兩者的某種組合。系統存儲器104通常包括作業系統106、 一 個或多個程序模塊108，並且可以包括程序數據110。對於本視頻跟蹤技術而 言，程序模塊108可以包括用於實現視頻跟蹤技術的一個或多個組件140。此 外，程序模塊108可以包括使用在組件140中實現的視頻跟蹤技術的圖形應用程式142。或者，作業系統106可以包括用於實現視頻跟蹤技術的一個或多個 組件。程序數據110可以包括視頻序列150。在圖1中用虛線112內的那些組 件說明了該基本配置。設備100也可能具有附加的特徵或功能。例如，計算設備100可能也包含 附加的數據存儲設備(可移動的和/或不可移動的)，諸如磁碟、光碟或磁帶。 這種附加的存儲器在圖1中由可移動存儲器120和不可移動存儲器122示出。 計算機存儲介質可以包括易失性和非易失性、可移動和不可移動介質，它們以 任何用於存儲諸如計算機可讀指令、數據結構、程序模塊或其它數據的信息的 方法或技術來實現。系統存儲器104、可移動存儲器120和不可移動存儲器122 都是計算機存儲介質的例子。計算機存儲介質包括但不限於RAM、 ROM、 EEPROM、快閃記憶體或其它存儲技術、CD-ROM、數字通用盤(DVD)或其它光存 儲器、磁性卡帶、磁帶、磁碟存儲器或其它磁性存儲設備、或任何其它可以被 用於存儲期望信息且可由計算設備100訪問的媒質。任何這樣的計算機存儲介 質可以是設備100的部分。計算設備100也可以具有諸如鍵盤、滑鼠、筆、語音輸入設備、觸摸輸入 設備等的輸出設備124。計算設備100也可以包含允許設備諸如通過網絡與其 他計算設備130通信的通信連接128。通信連接128是通信介質的一個示例。 通信介質一般具體化為計算機可讀指令、數據結構、程序模塊或其他數據。通 過示例而非局限，通信介質包含諸如有線網絡或直接連線連接等有線介質以及 諸如聲音、RF、紅外線和其它無線介質等無線介質。計算機可讀介質可以是可 由計算機訪問的任何可用介質。通過示例而非限制，計算機可讀介質可以包括 "計算機存儲介質"和"通信介質"。本申請中所描述的各種模塊和技術可在諸如程序模塊的由一個或多個計 算機或其他設備執行的計算機可執行指令的一般上下文中描述。 一般而言，程 序模塊包括執行特定任務或實現具體抽象數據類型的例程、程序、對象、組件、 數據結構等。這些程序模塊等可以作為本機代碼執行或諸如在虛擬機或可在其 他運行時(Just-in-Time)編譯執行環境中下載和執行。通常，程序模塊的功能 在各個實施例中可以按照需要來組合或分布。這些模塊和技術的實現可以存儲 在某種形式的計算機可讀介質上或通過某種形式的計算機可讀介質發送。在描述本跟蹤技術的細節之前，將描鴻用於本跟蹤技術的狀態模型和觀察 模型。狀態模型和觀察模型應用基於關鍵幀的構架。對於狀態模型，目標對象 被表示為矩形及={/^*叫5*^，其中P是中央矩形，而S是比例因數，ffl和^是 分別是目標模板的固定寬度和高度。該對象的狀態可以被示為x-^力e^，其 中義是狀態空間。狀態《是指第一關鍵幀A中的狀態，而狀態x,是指最後一關 鍵幀/,中的狀態。對於本跟蹤技術，這些狀態》和&都是已知的。觀察模型是目標對象的色彩統計。對象的色彩模型被表示為柱狀圖 /;-",;^，其中在RGB色彩空間中有H (通常H-8X8X8)個柱(bin)。狀 態x。的相關聯的柱狀圖/K;c。)和狀態;c,的相關聯的柱狀圖/z(:c,)之間的巴氏 (Bhattacharyya)距離如下定義^陶竭]=1 -1^") "'). (2) 該模型捕捉全局色彩i計。在另一實施例中，如果有目標對象的某一空一 配置，則可使用最複雜的多部分色彩模型。例如，在一個實現中，使用諸如 Patrick Perez, C. Hue、 J. Vermaak禾卩M. Gangnet在European Conf. on Computer Vision會報巻1， 2002年版中第611-675頁中描述的色彩模型等多部分色彩模 型。對於軌跡優化，在給定視頻序列或觀察7 = ^1，'''，力}和已知的兩個狀態 時，整體狀態序列^ = &2「，xr—J的後驗在一階馬爾可夫獨立假設下可以如下表示formula see original document page 10 (3)其中使用巴氏距離如下定義局^痕跡^UI^、，&):formula see original document page 10(4)其中 2是方差參數。方差參數測量狀態x,的色彩柱狀圖到關鍵幀/t中的W;c,)或關鍵幀4中的;K;c,)之間最近的色彩柱狀圖之間的相似程度。兩個相鄰的狀態之間的勢函數^0c,，x,+》被定義為formula see original document page 10 (5)其中= ||a + A+1||2 ++ &+1||2是狀態JC,和、.之間的相似程度。參數 是 控制平滑強度的方差參數，而-是位置差異和比例差異之間的權重。由此，/ 是對目標對象的整體軌跡;r- {x。，...,訂)的平滑度限制。基於關鍵幀的跟蹤的目標是獲取公式(3)的MAP解答，如下所述 X* = arg max P(X|Y). (6)然而，確定MAP解答的複雜性O是(9(7^7)，其中N是一個幀中離散狀 態的數目，而T是輸入視頻的幀數目。由此，對於320 x 240的視頻，量化狀 態空間即使對於本狀態表示也是非常大的。因此，本雙向跟蹤技術集中在用有 效且高效的方式減小狀態空間。圖2是示出有效地減小狀態空間使得可以高效地獲取MAP解答的示例性 視頻跟蹤過程200的流程圖。在框202處開始視頻跟蹤過程，其中在視頻序列 中指定開始和結束幀。開始和結束幀被稱為關鍵幀。處理繼續到框204。在框204處，從開始幀內獲取目標對象的初始狀態，而從結束幀中獲取目 標對象的最終狀態。初始狀態和最終狀態可以由用戶選擇。例如，用戶可以在 目標對象周圍放置矩形。接著可以基於幀內矩形的位置來確定初始狀態和最終 狀態。處理繼續到框206處。在框206處，執行軌跡分段分析。簡而言之，稍後結合圖3詳細描述的軌 跡分段分析試圖標識視頻序列中目標對象最可能存在的位置(即模式)。為效 率起見，軌跡分段分析首先組合二維模式提取，以便找出目標對象最可能的位 置，接著在這些所標識的位置應用三維軌跡提取。處理繼續到框208處。在框208處，執行遮擋分析。簡而言之，稍後結合圖7詳細描述的遮擋分 析試圖移除由遮擋引起的中斷。這使得可以跟蹤目標對象的完整軌跡。處理繼 續到框210處。在框210處，執行軌跡優化。在獲取軌跡分段(框206)和遮擋分段(框 208)的組後，通過軌跡優化計算兩個關鍵幀之間的單個最佳軌跡。簡而言之， 以由粗到精的方式執行稍後詳細描述的軌跡優化，以便獲取更準確的跟蹤結 果。在粗略軌跡優化過程的一個實施例中，在每個幀中使用三個離散比例因數 來均勻地對所計算的分段周圍的狀態採樣，以便確定最佳軌跡。在精細軌跡優 化過程的一個實施例中，在每個幀中使用五個離散比例因數來對最佳軌跡周圍的狀態採樣。現在將更詳細地描述這些框中的每一個。圖3是示出適用於圖2的視頻跟蹤過程的示例性軌跡分段分析過程300 的流程圖。軌跡分段分析過程300從框302處開始，其中在每個幀中執行二維 提取。簡而言之，稍後結合圖4詳細描述的二維提取過程試圖顯著減小整體狀 態空間，這樣可以對更為稀疏的狀態集執行跟蹤。處理繼續到框304。在框304處，當減小了狀態空間之後，確定少量的三維軌跡分段。總體而 言，二維模式需要被轉換到三維空間，以便獲取目標對象的真正軌跡。簡而言 之，稍後結合圖6詳細描述的三維軌跡分段提取過程試圖從其中分段表示有意 義的軌跡的部分的所有點中提取多個軌跡分段。軌跡分段提取過程試圖獲取每 個分段的可能的最長長度和/或可能的最小分段數目。本視頻跟蹤技術應用譜聚 技術，以便獲取這些三維軌跡分段。 一旦這些軌跡分段被提取，那麼過程300 完成。現在將更為詳細地描述框302和304兩者。圖4示出了適用於圖3所示的過程300的框302的二維提取過程400的流 程圖。為每個幀獨立地執行過程400。 二維提取過程400從框402開始，其中 使用關鍵幀中的對象的色彩柱狀圖預過濾幀，這樣能夠使用較少的採樣。處理 繼續到框404處。在框404處，本跟蹤技術的一個實施例獲取每個幀中的開始位置集。這些 開始位置是通過均勻地對幀中的位置採樣來確定的。可以使用3-5的離散級別 來執行縮放。在進一步的細化(框406)中，基於目標對象大小來設置空間採 樣間隔。例如，可以將空間採樣建設設置為略微小於目標對象的一半大小。處 理繼續到框408處。在框408處，計算出痕跡表面。在一個實施例中，使用巴氏距離來定義局 部痕跡^0,lx,，^x。。接著使用以下公式來計算痕跡表面VO,- I x,.,^,;^) ~ exp(-min(52[/ (x,),/zO》],52[/2(;v;;),/z(;^)]〉/20^)(7)參數C7〗是方差參數。巴氏距離測量狀態JC,的色彩柱狀圖/70C,)到關鍵幀A中的//00或關鍵幀/r中的/Kx》之間最近的色彩柱狀圖之間的相似程度。處理繼續 到框410處。在框410處，基於痕跡表面來標識模式。總而言之，最可能的位置(即模 式)是痕跡表面上的峰值(即局部最大值)處。每個"最可能的"2D模式表示其觀察類似於關鍵幀中的對象模板的狀態;c'。換而言之，局部痕跡 y(少l;c'，;c,，&)為高。為了高效地找到這些模式， 一個實施例(框412)使用均值漂移算法，它是用於尋找點採樣分布的最接近模式的非參數統計方法。總體 而言，給定初始位置，均值漂移算法計使用以下公式用核函數G計算巻積痕跡 表面的梯度方向Ap = ~^-. (8)由此，給定圖像中的初始位置/7，均值漂移依照上述公式計算出新的位置;/ = /7 + AP，其中G是核函數，並且對對象的矩形中的象素《執行求和。均值 漂移向量Ap與使用核函數G的遮蔽計算的巻積表面的梯度方向相反。由於該 特性，確定均值漂移算法提供了用於確定目標對象的局部模式的高效迭代方 法。因此，均值漂移算法獨立於每個開始位置運行。在收斂之後，來自均值漂 移算法的結果是多個局部模式。處理繼續到框408處。在框414處，生成局部二維模式的稀疏集。在一個實施例中(框416)， 如果相應的狀態模式x'具有p(y,l;c') S0.5的局部痕跡，那麼就拒絕模式。在進 一步的細化中(框418)，可以合併很接近的模式。結果是每個幀中局部模式 的稀疏集，如圖5中所示。現在參考圖5，示出了一組圖示。頂行顯示來自視頻序列的簡化幀(例如 幀502、 504、 506)，而底行顯示來自以上在圖4中描述的二維提取過程的結 果(例如局部二維模式512、 514、 516的稀疏集)。簡化幀顯示目標對象510 以及與目標對象相同的另一對象508的(例如相同的顏色、相同的大小)。即 使從簡化幀移除了背景細節，但是本視頻跟蹤技術在處理期間考慮其背景細 節。總體而言，視頻序列示出了在每個幀的左側上個人(未示出)所持有的綠 色杯子510。綠色杯子510是目標對象且正被跟蹤。在每個幀右側上的另一個 人(未示出)持有相同的杯子508。在幀502處，這兩個人都持有他們的杯子， 這樣使得杯子被觸及，並且處於相同的高度。在幀504處，右側的個人放下了 杯子508。在幀506中，右側的個人將杯子508移動通過杯子510的前方，並 且部分地遮擋住了杯子510的左下角。本跟蹤技術分別為每個幀502、 504和 506確定了一組局部二維模式512、 514、 516。局部二維模式512、 514和516 中的分組522、 524、 526分別對應於圖像中的兩個綠色杯子(杯子508和510)。局部二維模式512、 514和516中的分組532、 534、 536分別對應於具有與關 鍵幀中的目標模板(即綠色杯子510)相似的色彩統計的相應幀中的背景區域 (未示出)。依照本跟蹤技術的一個實施例，每個幀中的局部二維模式組接著表示用於 進一步跟蹤目的的狀態空間。如局部二維模式512-516組所示，狀態空間被顯 著地減小。這種狀態空間的減少允許進一步分析以便更為高效地執行跟蹤目 的。相反，其他跟蹤技術使用整體連續狀態序列空間，其由於非線性動力學和 非高斯觀察而具有龐大數目的局部最小值。例如，基於梯度的技術通常在局部 最小值處陷入困境。給定320x240的視頻，使用用離散隱馬爾可夫模型(HMM) 表示的Viterbi算法來計算MAP解答的技術必須處理較大的量化狀態空間。由 此，本跟蹤技術中的二維提取過程提供了用於顯著減小狀態空間的高效技術， 這導致更為高效的跟蹤分析。圖6是示出適用於圖3所示的過程300中的框3054的示例性三維軌跡分段提取過程的流程圖。總體而言，軌跡分段分析過程600使用譜聚。過程600在框602處開始，其中在圖4中所示的二維提取過程期間確定的二維模式點被轉換成三維體。為了獲取目標對象的真正軌跡，尤其是如果目標對象跟隨曲線軌跡，那麼點被轉換成三維體。對於每個二維模式，獲取三維體中的三維點 氣其中凡和/ 分別是空間位置和時間位置(幀數)。處理繼續到框604處。在框604處，給定識3中的點集M = {附 }二 ，構建相似矩陣(affinity matrix)， 其中訴3是三維歐幾裡得空間。在一個實施例中，基本相似矩陣^e識^定義如 下4 =eXp(-|A—巧『/2ct〗—。f/2cT,2) (9)其中比例參數C7p和C7,控制相似矩陣^分別在空間和時間上以多快的速度隨兩點m,和^之間的距離分開。在本跟蹤技術的另一實施例中，可以使用更為復 雜但是昂貴的相似矩陣4'來鼓勵更為緊湊的軌跡分段。該相似矩陣4/可以定 義如下4' = " + (1 - a) exp(-S2 [/z(附,),/ = {7>,, — ,7^}。使用為本視頻跟蹤技術描述的譜聚，產生多個"有用"軌跡 分段。由此，三維軌跡提取過程基於二維局部模式M成功地提取多個三維對 象軌跡7h。每個對象軌跡表示三維體中所跟蹤對象的可能的分段。與其他群集技術相比，譜聚的實施例將單位球體表面的三維數據點嵌入在 由L的K個最大特徵向量確定的K維空間中。這使得可以分割原始三維空間 中的曲線軌跡或流形(manifold)，這導致更為有用的軌跡分段。相反，使用 標準K均值群集確定的每個群集需要是凸區域。由此，如果軌跡是高度彎曲的 和/或軌跡的某些分區不是凸區域，那麼不能獲取"真正"軌跡。一旦提取了軌跡分段，那麼就執行分析以確定目標對象在視頻序列的部分 期間可能被遮擋的概率。現在結合圖7更詳細地描述在圖2的框208中示出的 該分析。如果沒有對目標對象的遮擋，那麼所提取的軌跡分段可以被用於確定 對軌跡優化的狀態空間採樣。然而，通常在輸入視頻的某些部分期間會有對目 標對象的部分或完全遮擋，且處理繼續遮擋推理。圖7是示出適用於圖2的視頻跟蹤過程的示例性遮擋分析過程的流程圖。 因為在輸入視頻中發生的部分或完全遮擋不包括在已經提取的分段中，因此需 要獲取附加的遮擋軌跡分段。這些遮擋軌跡分段接著會對應於遮擋階段期間的 狀態。遮擋分析是基於在分析多個視頻序列的軌跡分段時識別出的若干個觀察的。這些觀察導致對於遮擋分析的雙向、樹成長算法。在描述遮擋分析之前， 首先討論其所基於的觀察。在對象軌跡分段之間推斷和採樣遮擋分段。包括關 鍵幀中的對象模板的軌跡分段是在"真正"對象軌跡中。應該排除與包含對象 模板的分段平行的任何軌跡分段。如果兩個分段之間的重疊時間和最短距離不 超過某些經驗閥值，那麼它們可以被認為是平行的。在沿著時間軸的兩個重疊 軌跡分段之間不存在遮擋分段。對於每個遮擋分段有某些速度和時間限制。基於這些觀察，闡明用於遮擋分析的本雙向、樹成長過程。圖7是示出適用於圖2中所示的視頻跟蹤過程200的框208的示例性遮擋分析過程的流程圖。 過程700從框702處開始，在其中構建樹。在過程700的一個實施例中，使用 自從相應的狀態中的對象模板獲取的兩個狀態(例如初始和最終狀態)中的任 何一個成長的一棵樹執行過程700。在另一實施例中，可以使用多棵樹來執行 過程700。例如，如果構建兩棵樹，那麼一棵樹成長自初始狀態，而另一棵樹 成長自最終狀態。接著樹會相遇以便形成目標對象的完整軌跡。以下討論描述 了使用兩棵樹的過程700。如將要描述的，在該實施例中，來自兩棵樹的信息 可以被共享，以便獲取對完整的軌跡的更好的確定。由此，在框702中，構建 兩棵樹TA和Te。兩棵樹都具有空的根節點。總體而言，樹被用於基於先前標 識的軌跡分段來確定遮擋分段。遮擋分段接著連接脫開的軌跡分段對。這是通 過從樹中排除多個對象軌跡並將多個遮擋軌跡添加到樹上來完成的，如以下將 描述的。處理繼續到框704處。在框704處，定位包含關鍵幀中的對象模板的軌跡分段。在多棵樹實施例中，可以定位兩個這種軌跡分段，並且將軌跡分段之一添加到每棵樹r,和z;，作為活動節點。處理繼續到框706處。在框706處，剩餘的軌跡分段被分類到活動候選列表中。總而言之，活動 候選列表中的分段接著或者被排除，或者被用於確定遮擋分段。過程繼續到框 708處。在框708處，從活動候選列表中移除活動候選列表中的與活動節點平行的 軌跡分段。如果兩個分段之間的重疊時間和最短距離不超過某些經驗閥值，那 麼它們是平行的。在一個示例性實現中，時間閥值是30個幀，而距離閥值是 50個象素。處理繼續到框710處。在框710處，執行雙向樹成長過程。總而言之，稍後結合圖8描述的雙向 樹成長過程每次使樹成長一步直至在樹中沒有活動的葉節點。樹成長過程確定 可能的遮擋分段。 一旦完成了框710，那麼也完成了遮擋分析過程700。圖8是示出適用於圖7中所示的遮擋分析過程的示例性雙向樹成長過程 800的流程圖。對每個沒有子節點的活動葉節點執行過程800。可以對每棵樹 執行過程800。過程從框802處開始。在框802處，從活動候選列表選擇軌跡分段作為當前活動節點(即先前活 動節點的活動葉節點)。所選的活動葉節點此時上不具有子節點。處理繼續到 框804處。在框804處，確定當前活動節點的Q最佳遮擋分段。可以在活動候選列 表中執行前向檢索，以便標識出沿著時間軸與其他軌跡分段重疊的軌跡分段7>*。接著可以在活動葉節點rz的軌跡分段和這些所標識的軌跡分段7>*的每一個之間生成Q最佳遮擋分段。在一個實施例中，基於4+W。，確定Q最佳遮 擋分段，其中y-10是權重因數。丄。和S。是兩個連接的軌跡分段之間假設的B樣條的長度(象素)和最大速度(像素X幀")。總而言之，B樣條被用於生成與在時伺上兩個脫開的軌跡z;和7;相關的缺少的遮擋分段o。給定 ;和 ;中的所有點{附;B樣條被擬合的，其中B樣條K"-2^。^"k使用加權最小平方 ^S二咖;)l卜"/)-附"2 (11) 其中— A)/AT'是幀。中B樣條的時間參數表示。即使B樣條的參數表示是近似值，但是發現它能夠得出好的結果。權重函數"O,)被定義為exp(乂'l卜-巧(12)其中^和《是7V;中的最後一幀數和7>2中的第一幀數。比例參數^被設置成20。 使用權重函數，可以對C^和C"附近的點給予較大的權重。最後，A和7Vi之 間擬合的B樣條被採樣為遮擋分段O。處理繼續到判定框806處。在判定框806處，作出判定在Q最佳遮擋分段中是否有任一個達到另一 端。換而言之，是否有遮擋分段中的之一碰到被設置為另一樹中當前活動節點 的軌跡分段。另一樹中的當前活動節點可以是包含對象模板的軌跡分段或被在 對其他樹的處理期間被設置為活動節點的其他軌跡分段之一。如果Q最佳遮擋 分段之一達到另一端，那麼處理繼續到框814處。否則，處理繼續到判定框808 處。在判定框808處，作出判定Q最佳遮擋分段之一是否是主遮擋分段。該 可選判斷是基於軌跡分段之一是否具有用於￡。 + ^。的值，所述值顯著小於其他軌跡分段的值。如果有主遮擋分段，那麼處理繼續到框810處。否則處理繼續 到框812處。在框810處，添加主Q最佳遮擋分段作為子節點，並且將其設置為當前 活動節點。先前的活動節點被設置為非活動的，因為它現在具有子節點。處理 接著繼續使用該當前活動節點到框804處。在框812處，如果沒有主Q最佳遮擋分段，那麼將Q最佳遮擋分段的每 一個添加到活動候選列表中。通過這樣做，可以連接多個遮擋分段，直至一個 可以與軌跡分段連接。處理接著循環回到框802，以便從活動候選列表選擇"分 段"(遮擋分段或軌跡分段)，並如上所述地繼續。在框814處，如果Q最佳遮擋分段之一達到另一端，那麼將該遮擋分段 添加到樹的另一端。在具有兩棵樹的實施例中，遮擋分段被添加到兩棵樹，並 且被設置為非活動的。遮擋分段則是兩棵樹之間的橋梁。處理繼續到框816處。在框816處，在樹中使用B樣條內插來連接沿著時間軸的中斷。結果是 從初始狀態到最終狀態的可能的軌跡路徑，它包括軌跡分段和遮擋分段。處理 然後完成。對沒有任何子節點的每個子節點執行過程800。 一旦一節點具有子節點 (例如至少一個Q最佳遮擋分段)，那麼對該節點的處理完成。當在任一樹中 不再有任何活動節點或者不再有被標識將初始狀態連接到最終狀態的軌跡，那 麼過程800完成。會注意到軌跡分段與遮擋分段連接，因為在軌跡分段分析過 程300期間，獲取最長的可能軌跡分段。因此，通常，軌跡分段不與其他軌跡 分段相連接。的遮擋分析過程期間生成的遮擋軌跡分段的圖 示。如所示，有兩個軌跡分段7b和7>2。點m;是二維局部模式，而7>/和7>2 是三維視頻體中的三維軌跡分段。O是軌跡分段7>7和7>2之間的推斷出的遮 擋軌跡分段。依照使用軌跡優化的本視頻跟蹤技術(圖2中的框210)，當獲取了對象 軌跡和遮擋軌跡組之後，通過對這些軌跡採樣來計算兩個關鍵幀中的單個最佳 軌跡。本視頻跟蹤技術執行軌跡優化，以便獲取更為準確的跟蹤結果。軌跡優 化用由粗到精的方式執行上述公式(3)。在一個實施例中，為由粗到精的方 式選擇兩個級別。第一級別(即粗略級別)，其中採樣是空間向下採樣的，可 以使用每個幀中的三個離散比例因數對計算出的分段周圍的M (例如 500-1000)個狀態進行均勻地採樣。這些狀態可以在自分段的較小的半徑內選 擇，諸如5個象素的半徑。在該粗略級別中使用常規離散隱馬爾可夫模型 (HMM)來計算最佳軌跡。使用從該粗略級別計算出的最佳軌跡，使用下一 級別(例如精細級別)來確定最終的最佳軌跡。下一級別可以使用每個幀中的 五個離散比例因數來對最佳解答周圍的M個狀態進行採樣。即使精細級別使 用每個幀中的五個離散比例因數，但是計算不是過高的，因為狀態的數目被顯 著地降低了。例如，對於10秒的視頻，軌跡優化大約採用8秒。圖10-13是依照本跟蹤技術示出各個處理階段的結果的一組圖表1000、 1100、 1200和1300。圖14中示出了得出圖1000、 1100、 1200和1300的視頻 序列1400的簡化幀。開始幀(#000)指定目標對象1404的初始狀態1402， 而結束幀(#179)指定目標對象的最終狀態1406。總體而言，視頻序列1400 示出了兩個相同杯子的移動。簡化幀不示出背景，而是集中在相同的杯子彼此 相對的移動上。在幀#000中，個人(未示出)持有兩個相同的杯子1404和1414， 使得杯子1404比杯子1414高大約半個杯子的長度。杯子1414的右下角被部 分地遮擋，並且在視頻序列1400的所有的幀中保持在幾乎相同的位置中。相 反，杯子1404在每個幀中移動。現在描述杯子1404在各幀中的移動。會注意 到每個幀作為矩形框1410，該矩形框1410表示依照本跟蹤技術確定的目標對 象的預測位置。每個幀也示出了表示幀中目標對象的實際位置的陰影區1412。 由於目標對象的遮擋，陰影區域1412的大小根據目標對象遮擋的程度變化。在幀#016中，杯子1404垂直向下移動，使得其在杯子1414下方。在幀 #027中，被子1404向右移動，這樣使得其在杯子1414的右下方。在幀#028-035 期間，杯子1404在持有杯子1414的個人手臂的下移動，並且最終位於杯子1414 右方且稍微高於其的位置處。因為杯子1404在個人的左臂之後，所以相當的 遮擋，如幀#035中所示。在幀弁052中，杯子1404被向上移動，並且大約在 杯子1414的直接上方。在幀#065中，杯子1404被置於與杯子1414相同的高 度，並且在杯子1414的左方，有少量的遮蓋。在幀弁086處，杯子1404被降 低，並且被稍微地移動到幀中的左側。在幀糾98中，杯子1404被置於杯子1414 的下方，並且因杯子1404前方的個人的手(未示出)而被部分地遮擋。在幀 弁105處，杯子1404被移動到持有杯子1414的個人的左臂的後方。由此，杯 子1404幾乎被完全遮擋。然而，有趣的是，預測位置1410準確地預測到杯子 1404將位於的位置。在幀#132中，杯子被稍微舉高，使得可越過個人的左臂 (未示出)看見一小部分。在幀#147中，杯子1404被移動到幀的頂部，並且 被持有杯子1404的個人的手指幾乎完全遮擋。由此，如視頻序列1410所示， 本跟蹤技術準確地預測目標對象的位置，即使當目標對象變為被完全遮蓋。在 圖10中示出了跟蹤技術在各個處理階段本的結果。圖表1000和IIOO示出了三維中兩個二維模式的視圖，其中在本跟蹤技術 的二維提取過程期間生成二維模式點。垂直軸是序列中的幀號。另一軸是每個 幀中目標對象的x、 y位置。向下到中心的相對直線對應於視頻序列1400中的 同一杯子1414。圖表1200示出了在使用譜聚執行三維軌跡分段分析之後獲取 的有用的軌跡分段。因為在視頻序列部分期間目標對象被完全遮擋，所以沒有 從初始狀態到最終狀態的一條軌跡。圖表1300示出了在執行遮擋分析後，目 標對象的最佳軌跡。虛線矩形中的圓圈表示填入的遮擋分段。由此，如所述的，本跟蹤技術成功地處理了部分或完全遮擋。本跟蹤技術 採用新穎的軌跡分段表示來從三維視頻體中可能的對象軌跡獲取少量的軌跡 分段。使用譜聚方法從輸入視頻提取軌跡分段。有了該表示，通過使用軌跡分 段以使用由粗到精的方式採用離散隱馬爾可夫模型來獲取MAP解答。此外， 本跟蹤技術採用遮擋分析過程來健壯地推斷目標對象的可能的遮擋軌跡分段。現在討論可用於本跟蹤技術的典型的參數設置。群集數目K的選擇是群集中的公開問題。因為在本跟蹤技術的遮擋分析中有分組機制，所以確定稍微大於"最佳"的K是可以接受的。因此，可以設置群集數目K，使得K-7或 K=10。在二維模式提取中，G是高斯核函數，其標準偏差卩j以是關鍵幀中目標 對象的大約1/6的大小。在三維軌跡提取中，比例參數^和"'可以分別被設置 成10和20。在軌跡優化中，方差參數 和 可以分別被設置成10和1。如上所述，使用軌跡分析的本雙向跟蹤將整個視頻序列和兩個關鍵幀中信 息作為輸入，並且輸出貝葉斯構架中目標對象的整體狀態序列的MAP解答。 雙向跟蹤是基於軌跡分析的，所述軌跡分析從輸入視頻提取多個三維軌跡，即 對象跟蹤的緊湊表示。接著，在軌跡級別推斷遮擋軌跡。最後，以由粗到細的 方式通過軌跡優化來獲取MAP解答。實驗結果示出了本技術關於突然移動、 含糊不清、短時間和長時間遮擋的健壯性。本雙向跟蹤技術可以被應用於許多離線應用。其中可應用該技術的一個新 的領域是在線廣告。對於該應用，可以"點擊"移動目標以便自動地連結到相 關的網站。因為本雙向跟蹤技術準確地跟蹤目標對象，因為可以將移動目標對 象的位置給予潛在的應用以供其自身使用。可以為本跟蹤技術想像該應用和許 多其他應用。雖然示出和描述了示例性實施例和應用，但是應該理解本發明不限於 上述精確配置和資源。對本領域的技術人員顯而易見的是可以對排列、操 作以及本申請中所公開的系統和方法的細節作出各種修改、改變和變更， 而不背離所作權利要求的發明的範圍。
權利要求
1. 存儲用於執行一方法的計算機可執行指令的至少一種計算機可讀介質，所述方法包括確定視頻序列(1400)的兩個關鍵幀(#000和#179)；獲取(204)目標對象(1404)在所述兩個關鍵幀之一中的第一狀態(1402)以及所述目標對象在另一關鍵幀中的第二狀態(1406)；以及基於所述第一和第二狀態，從所述一個關鍵幀到所述另一關鍵幀跟蹤(200)幀中的所述目標對象。
2. 如權利要求1所述的計算機可讀介質，其特徵在於，其中對所述目標 對象的跟蹤包括對所述幀執行二維提取，以便獲取所述目標對象的多個局部二維(2D) 模式；基於所述局部二維模式的稀疏集執行三維軌跡分段提取，以便獲取所述目 標對象的多個三維軌跡分段；基於所述多個軌跡分段執行遮擋分析，以便獲取連接所述多個軌跡分段的 兩個脫開的軌跡分段的一個遮擋分段；以及基於所述軌跡分段以及所述遮擋分段，用由粗到精的方式執行軌跡優化， 以便獲取所述目標對象的最佳軌跡。
3. 如權利要求2所述的計算機可讀介質，其特徵在於，其中執行所述二 維提取包括計算痕跡表面；以及將均值漂移算法應用於計算所計算出的痕跡表面的梯度方向，得出所述目 標對象的局部二維模式。
4. 如權利要求3所述的計算機可讀介質，其特徵在於，其中三維軌跡分 段提取包括將所述二維模式轉換成三維體中的三維點；使用譜聚技術將所述三維點分割成群集，所述譜聚技術同時為K類群集使用K個特徵向量；以及基於所述群集獲取所述有用的軌跡分段。
5. —種計算機實現的方法，包括指定(202)視頻序列(1400)中的開始(#000)和結束幀(#179);獲取目標對象(1404)在所述開始幀內的初始狀態(1402)以及所述目標 對象在所述結束幀中的最終狀態(1406);對以所述開始幀開始並以所述結束幀結束的幀執行二維提取(302)，以 便基於所述初始狀態和所述最終狀態獲取所述幀中的目標對象的局部二維模 式(512)的稀疏集；以及基於所述局部二維(2D)模式的稀疏集執行三維軌跡分段提取(304)， 以便獲取所述目標對象的多個三維軌跡分段(Tn)。
6. 如權利要求5所述的計算機實現方法，其特徵在於，其中執行所述 二維提取包括計算痕跡表面；以及將均值漂移算法應用於計算所計算出的痕跡表面的梯度方向，得出所述目 標對象的局部二維模式。
7. 如權利要求6所述的計算機實現方法，其特徵在於，還包括在應用 所述均值漂移算法之前使用所述目標對象的色彩柱狀圖來預過濾所述幀。
8. 如權利要求6所述的計算機實現方法，其特徵在於，還包括通過均 勻地採樣所述幀中的位置並且獨立於每個開始位置運行所述均值漂移算法 來確定多個開始位置。
9. 如權利要求8所述的計算機實現方法，其特徵在於，其中均勻採樣 包括將空間採樣間隔設置成稍微小於所述目標對象的一半大小。
10. 如權利要求6所述的計算機實現方法，其特徵在於，還包括如果 所述相應的痕跡小於預定的值，則拒絕所述局部二維模式之一。
11. 如權利要求6所述的計算機實現方法，其特徵在於，還包括當所 述兩個二維模式在彼此之間某個距離以內時，就將所述局部二維模式合併 成一個局部二維模式。
12. 如權利要求5所述的計算機實現方法，其特徵在於，其中執行三 維軌跡分段提取包括-將所述二維模式轉換成三維體中的三維點；使用譜聚技術將所述三維點分割成群集，所述譜聚技術同時為K類群集 使用K個特徵向量；以及基於所述群集獲取所述有用的軌跡分段。
13. 如權利要求12所述的計算機實現方法，其特徵在於，還包括基於 所述多個軌跡分段執行遮擋分析，以便獲取連接所述多個軌跡分段的兩個脫 開的軌跡分段的至少一個遮擋軌跡分段。
14. 如權利要求13所述的計算機實現方法，其特徵在於，其中執行遮 擋分析包括a) 構建一樹，所述樹的根節點為空；b) 將包含所述關鍵幀中的對象模板的一個軌跡添加到所述樹中，作為 活動節點；C)將剩餘的軌跡添加到候選列表中；d) 在所述候選列表中基於所述軌跡是否與對應於所述活動節點的軌跡 平行排除軌跡；e) 當所述樹中有活動節點時，從所述候選列表選出所述軌跡之一作為 當前活動節點；f) 確定至少一個Q最佳遮擋分段；g) 如果所述Q最佳分段沒有達到期望的軌跡分段，那麼將所述至少一 個Q最佳遮擋分段添加到所述候選列表中；以及h) 重複e-g直至Q最佳分段達到所述期望軌跡分段；以及i) 連接所述軌跡和所述Q最佳遮擋分段以作出所述目標對象的完整軌跡。
15. 如權利要求13所述的計算機實現方法，其特徵在於，還包括基於 所述有用的軌跡分段以及所述遮擋軌跡分段，用由粗到精的方式執行軌跡優 化，以便獲取所述目標對象的最佳軌跡。
16. 如權利要求15所述的計算機實現方法，其特徵在於，其中用由粗 到精的方式執行軌跡優化包括空間上向下採樣所述幀並且使用三個離散比例 因數在每個幀中所述軌跡分段周圍的所述位置均勻地採樣以便獲取所述最佳軌跡。
17. 如權利要求5所述的計算機實現方法，其特徵在於，其中用由精 細方式執行軌跡優化包括使用每個幀中的五個離散級別的比例因數來均勻地 對所述優化軌跡周圍的所述位置進行採樣以獲取最終最佳軌跡。
18. —種計算設備，包括 一處理器(102);一存儲器(104)，多個指令(140)被載入到其中，所述多個指令當有所 述處理器執行時，執行用於跟蹤視頻序列(1400)中的目標對象(1404)的方 法(200)，所述視頻序列被分解成若干個短序列，所述較短的序列具有開始 幀(#000)和結束幀(#179)，所述方法包括a) 為一個短序列的每個幀生成(406) —組局部二維模式(512)，每個局 部二維模式標識所述幀中具有與在所述開始幀中標識的所述目標對象類似的視覺統計的位置(HM);b) 基於所述局部二維模式組，獲取(608)所述目標對象的多個三維軌 跡分段(Tr!和Tr2);c) 獲取(208)連接所述多個三維軌跡分段的兩個脫開的軌跡分段(Tn 和Tr2)的至少一個遮擋分段(O);以及d) 基於所述多個三維軌跡分段和所述至少一個遮擋分段，確定(210) 最佳軌跡(1300)。
19. 如權利要求18所述的系統，其特徵在於，其中獲取所述多個三維軌 跡分段包括將所述局部二維模式組轉換成三維體中的三維點、使用譜聚將所述 三維點分割成群集以及基於所述群集獲取所述三維軌跡分段。
20. 如權利要求19所述的系統，其特徵在於，其中獲取所述至少一個遮 擋分段包括執行雙向樹成長過程。
全文摘要
本視頻跟蹤技術基於從整體狀態序列的開始和結束關鍵幀獲取的兩個對象模板輸出目標對象的最大後驗(MAP)解答。該技術首先通過在該序列的每個幀中生成局部二維模式的稀疏集來最小化序列的整體狀態空間。該二維模式被轉換成三維體內的三維點。使用譜聚技術來群集該三維點，其中每個群集對應於該目標對象的可能的軌跡分段。如果在該序列中有遮擋，則生成遮擋分段，使得可以獲取該目標對象的最佳軌跡。
文檔編號G06T7/20GK101283376SQ200680037803
公開日2008年10月8日 申請日期2006年10月13日 優先權日2005年10月14日
發明者H-Y·沈, J·孫, W·張, X·唐 申請人:微軟公司