視頻物體追蹤使用在各種應用上是個具有挑戰的問題，例如：視頻編輯、視頻監視、視頻壓縮、視頻萃取…等。一般的追蹤物體演算法可能會因為物體頻繁的疊合、相似的物體外型、錯失偵測、錯誤回應、明暗度變化而造成資料遺失，使得追蹤系統變得不容易執行。本論文中，我們提出一種新的物體追蹤演算法，此演算法透過結構式輸出支持向量機與獎勵收集斯坦利樹。首先，給予物體位置一個初始邊界框，我們會將其切割成預設尺寸的子區塊。接著我們萃取子區塊中的特徵值，將其特徵值設定為結構式輸出預測分類器的輸入資料。我們將邊界框的子區塊視為正樣本，接著以隨機方式在邊界框周圍的特定範圍選取出負樣本，所以預測的子區塊分數皆由正樣本與負樣本中所取得。接著，將子區塊視為一個節點、分類器分數視為權重值的方式建構出範圍圖，透過此方式追蹤每一張視頻畫面的物體。最後，使用PCST取得用於連續視頻的物體追蹤的最佳解。在我們的實驗結果中顯示，本論文的效能優於目前幾種最先進的物體追蹤演算法。

Object tracking in video is a challenging problem in various applications, such as video editing, video surveillance, video compression, video retrieval, and etc. Tracking object is in general not trivial due to loss of information caused by frequent occlusions, similar target appearances, missed detection, inaccurate responses and illumination change. In this thesis, we present a novel object video tracking algorithm via structured output prediction classifier integrated with Prize-Collecting Steiner Tree (PCST). Given an initial bounding box with its position, we first divide it into sub-blocks with a predefined size. And then we extract the features from each sub-blocks with a structured output prediction classifier. We treat the sub-blocks obtained from the initial bounding box as positive samples and then randomly choose negative samples from search windows defined by the specific area around the bounding box. We obtain prediction scores for each sub-blocks both from positive and negative samples. After that, we construct a region-graph with sub-blocks as nodes and classifier's score as weight to detect the target object in each frame. We then employ PCST to obtain the optimal solution for tracking the object in the consecutive video. Our experimental results show that the proposed method outperforms several state-of-the-art object tracking algorithms.

[1] P. Sherrod, “Support vector machines.” http://www.dtreg.com/svm.htm.
[2] I. Ljubic, “The prize-collecting steiner tree problem.” http://homepage.univie.ac.at/ivana.ljubic/research/pcstp/.
[3] Z. Kalal, K. Mikolajczyk, and J. Matas, “Tracking-learning-detection,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 34, no. 7, pp. 1409–1422, 2012.
[4] S. Hare, A. Saffari, and P. H. Torr, “Struck: Structured output tracking with kernels,” in IEEE International Conference on Computer Vision(ICCV), pp. 263–270, IEEE, 2011.
[5] S. Avidan, “Support vector tracking,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 8, pp. 1064–1072, 2004.
[6] S. Vijayanarasimhan and K. Grauman, “Efficient region search for object detection,” in IEEE Conference on Computer Vision and Pattern Recognition
(CVPR), pp. 1401–1408, IEEE, 2011.
[7] C. H. Lampert, M. B. Blaschko, and T. Hofmann, “Beyond sliding windows: Object localization by efficient subwindow search,” in IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1–8, IEEE, 2008.
[8] A. Lehmann, B. Leibe, and L. Van Gool, “Feature-centric efficient subwindow search,” in International Conference on Computer Vision (ICCV), pp. 940–947, IEEE, 2009.
[9] T. Yeh, J. J. Lee, and T. Darrell, “Fast concurrent object localization and recognition,” in IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 280–287, IEEE, 2009.
[10] P. Viola and M. Jones, “Rapid object detection using a boosted cascade of simple features,” in IEEE Conference on Computer Vision and Pattern Recognition
(CVPR), vol. 1, pp. I–511, IEEE, 2001.
[11] B. Leibe, A. Leonardis, and B. Schiele, “Combined object categorization and segmentation with an implicit shape model,” in Workshop on Statistical Learning in Computer Vision (ECCV), vol. 2, p. 7, 2004.
[12] C. Gu, J. J. Lim, P. Arbelaez, and J. Malik, “Recognition using regions,” in IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1030–1037, IEEE, 2009.
[13] K. Murphy, A. Torralba, D. Eaton, and W. Freeman, “Object detection and localization using local and global features,” in Toward Category-Level Object Recognition, pp. 382–400, Springer, 2006.
[14] A. Bordes, L. Bottou, P. Gallinari, and J. Weston, “Solving multiclass support vector machines with larank,” in Proceedings of the 24th International Conference on Machine learning, pp. 89–96, ACM, 2007.
[15] D. Wang, H.-C. Lu, and M.-H. Yang, “Online object tracking with sparse prototypes,” IEEE Transactions on Image Processing, 2013.
[16] A. Yilmaz, O. Javed, and M. Shah, “Object tracking: A survey,” ACM Computing Surveys (CSUR), vol. 38, no. 4, p. 13, 2006.
[17] Q. Wang, F. Chen, W. Xu, and M.-H. Yang, “Object tracking via partial least
squares analysis,” IEEE Transactions on Image Processing, 2012.
[18] W. Zhu, S. Wang, R.-S. Lin, and S. Levinson, “Tracking of object with svm
regression,” in IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), vol. 2, pp. II–240, IEEE, 2001.
[19] M. Tian, W. Zhang, and F. Liu, “On-line ensemble svm for robust object tracking,” in Asian Conference on Computer Vision (ACCV), pp. 355–364, Springer,
2007.
[20] L. Li, Z. Han, Q. Ye, and J. Jiao, “Visual object tracking via one-class svm,” in Asian Conference on Computer Vision (ACCV), pp. 216–225, Springer, 2011.
[21] O. Zoidi, A. Tefas, and I. Pitas, “Visual object tracking based on local steering kernels and color histograms,” IEEE Transactions on Circuits and Systems for Video Technology, 2013.
[22] I. Ljubic, R. Weiskircher, U. Pferschy, G. W. Klau, P. Mutzel, and M. Fischetti, “Solving the prize-collecting steiner tree problem to optimality,” in ALENEX/ANALCO, pp. 68–76, 2005.
[23] P. Viola and M. Jones, “Rapid object detection using a boosted cascade of simple features,” in IEEE Conference on Computer Vision and Pattern Recognition (CVPR), vol. 1, pp. I–511, IEEE, 2001.
[24] A. Bordes, N. Usunier, and L. Bottou, “Sequence labelling svms trained in one pass,” in Machine Learning and Knowledge Discovery in Databases, pp. 146–
161, Springer, 2008.
[25] J. Platt et al., “Sequential minimal optimization: A fast algorithm for training support vector machines,” MIT Press, 1998.
[26] I. Ljubić, R. Weiskircher, U. Pferschy, G. W. Klau, P. Mutzel, and M. Fischetti, “An algorithmic framework for the exact solution of the prize-collecting steiner tree problem,” Mathematical Programming, vol. 105, no. 2-3, pp. 427–449, 2006.
[27] J. Kwon and K. M. Lee, “Tracking of a non-rigid object via patch-based dynamic appearance modeling and adaptive basin hopping monte carlo sampling,” in IEEE Conference on Computer Vision and Pattern Recognition(CVPR), pp. 1208–1215, IEEE, 2009.