可適用於具重複圖樣之叢集式特徵追蹤演算法

Abstract

擴增實境 (Augmented Reality) 是一種結合虛擬3D數位資訊與真實世界的創新技術。在結合虛擬3D資訊與真實世界時，各種擴增實境的應用廣泛地採用自然特徵點的物件追蹤演算法，以找出使用者所指定之標的物件。然而，現有的物件追蹤演算法卻存在著計算速度慢及無法穩健地追蹤含有重複圖樣的物件等問題。因此，在本篇論文中，我們針對運算速度與重複圖樣追蹤能力等問題，提出了一個可適用於具重複圖樣之叢集式特徵追蹤演算法（ClusteR-based Algorithm for Feature Tracking，簡稱 CRAFT），先將描述物件的特徵點進行叢級分群，決定每個分群的估算區域，並利用投影矩陣找出這些估算區域在影像上的相對位置。與現有物件追蹤演算法不同的是，本論文所提出之 CRAFT 演算法，僅針對估算區域中的特徵點進行計算與比對。除了能降低計算成本之外，CRAFT 演算法可以更進一步地區分物件中的重複圖樣，以提昇物件追蹤的強健度。在本論文中，我們分別針對精確度與計算速度設計不同的實驗，並分析物件在不同運動狀態與部分遮蔽的情況下，CRAFT 演算法的表現情形。由實驗結果可知，在追蹤含有重複圖樣的物件時，CRAFT 演算法可以更準確、更快速地追蹤標的物件。

Augmented Reality (AR) is an innovative technology, overlaying real-world image with 3D virtual objects, to bridge virtual and real worlds. To overlay the 3D virtual object on a real world object, vision-based object tracking algorithms using natural features are widely used for tracking objects. Unfortunately, most of the existing algorithms of object tracking are not efficient enough for real world scenarios, nor robust enough to deal with objects with repeated patterns. In this thesis, we propose a cluster-based algorithm for feature tracking (CRAFT) to efficiently track an object with repeated patterns in different motions. In our design, the CRAFT algorithm first clusters features derived from the template (object model) and determines the region of each cluster. A projective transformation matrix is then used to locate the corresponding regions in the video frames. Since CRAFT only computes and searches features in the projected regions, it reduces the computational costs and further distinguishes different patterns when recognizing a object with repeated patterns. In this thesis, we conduct several experiments to compare the accuracy and computational performance of the proposed algorithm. Compared with SURF, the experiment results show that CRAFT has consistently excellent accuracy of pose estimation and improves efficiency in recognizing an object by a factor of 2.5.