物體偵測與辨識是許多電腦視覺應用中重要的處理工作之一。當影像中存在著多個不同物體的情況下，要使電腦選擇某一特定物體的確切位置並持續追蹤更是一個值得探討的議題。本文提出了一種多物體辨識及目標物追蹤方法，有效地解決這個議題。所提出的演算法首先會由一張輸入影像與一張目標物參考影像，透過特徵點描述子提取及匹配演算法求得特徵點描述子以及特徵匹配點。接著，於參考影像上訂定一個控制點，再使用候選點運算方法將參考影像與輸入影像之間的特徵匹配點計算出候選點在輸入影像中的位置，其會分佈於設定的目標物控制點周圍。此時可使用mean shift演算法將先前算出的控制點進行分群的運算，藉此找到多個候選點群集的中心，其不同的群集中心即代表不同物體的中心點。最後，利用template matching演算法 對參考影像的中心區塊進行視覺追蹤模型訓練，並使用其所訓練出來的模型對物體的中心區塊進行追蹤。在實驗測試中，本文所提出之演算法不僅能成功辨識出多種不同於箱內隨機擺放之堆疊物體，並且在運算速度或辨識準確度上都能達到不錯的效能。當使用GPU平行運算技術加速時，本文所提出的演算法能達到了每秒25張640x480影像的運算速度。

Object recognition and detection play important roles in various computer vision applications. When the image contains different types of objects, detecting and tracking an object-of-interest (OOI) from the multiple objects become a difficult task and a topic worth exploring. In this thesis, a novel multiple object clustering and target tracking algorithm is proposed to address this issue efficiently. The proposed method first employs a keypoint extraction and matching algorithm to extract keypoint descriptor matches between an input image and a target reference image. Next, setting a control point on the target reference image, a candidate point computation method is used to compute the position of each candidate point around the target control point in the input image associated with each keypoint match obtained from the previous stage. Then, the center point of each detected OOI in the image can be seqarated by applying a mean shift clustering approach to classify the computed candidate points into different clusters, each of them indicating an OOI to be tracked. Finally, a template-based visual tracking method is adopted to locate and track the center position of the top OOI detected in the image based on a template matching model trained from the target reference image. Experimental results show that the proposed method not only successfully recognizes each OOI from multiple stacking objects randomly placed in a box, but also achieves high recognition accuracy with real-time performance. When using GPU parallel computing technology to accelerate the proposed method, the entire system reaches about 25 frames per second in processing images with size 640×480 pixels.

目錄
中文摘要： ................................................................................................... I
Abstract: .................................................................................................. II
目錄 ............................................................................................................ III
圖目錄 ........................................................................................................ VI
表目錄 ..................................................................................................... VIII
第一章 序論 ................................................................................................ 1
1.1 研究背景 ........................................................................................ 1
1.2 研究動機與目的 ............................................................................ 3
1.3 論文架構 ........................................................................................ 4
第二章 相關研究........................................................................................ 5
2.1 以特徵點為基礎之物體偵測相關演算法 ....................................... 5
2.1.1 SIFT(Scale-Invariant Feature Transform)演算法 ..................... 5
2.1.2 PCA-SIFT演算法 ..................................................................... 6
2.1.3 ORB(Oriented FAST and Rotated BRIEF)演算法 ................... 6
2.1.4 SURF(Speeded Up Robust Features)演算法 ............................ 8
IV
2.2 以資料點為基礎之分群演算法 ..................................................... 8
2.2.1 K-Mean演算法 ......................................................................... 8
2.2.2 Mean Shift演算法 .................................................................... 9
2.2.3 Support Vector Machine演算法 ............................................ 10
2.3 文獻總結 ....................................................................................... 11
第三章 物體偵測與辨識演算法 ............................................................. 13
3.1 以特徵點為基礎之物體偵測演算法 ........................................... 15
3.1.1 特徵點與特徵描述子 .............................................................. 15
3.1.2 Lp空間 ..................................................................................... 18
3.2 以匹配點訓練為基礎之物體辨識演算法 ................................... 19
3.2.1 基於匹配點之物體分類器訓練 ............................................... 19
3.2.2基於匹配點之物體預測 ............................................................ 27
第四章 以物體特徵點為基礎之堆疊物體分群與追蹤演算法 ............. 28
4.1 堆疊物體分群之候選點分群演算法 ........................................... 28
4.1.1影像特徵點之候選點運算 ........................................................ 29
4.1.2候選點分群 ................................................................................ 30
4.1.3決定上下層物體 ........................................................................ 31
V
4.2 模板匹配追蹤演算法 ................................................................... 32
4.2.1物體運動參數向量計算 ............................................................ 33
4.2.2 物體超平面近似與訓練 ........................................................... 34
第五章 實驗結果與分析 ......................................................................... 36
5.1 軟硬體介紹 ................................................................................... 36
5.2 影像資料庫 ................................................................................... 38
5.3 所提出演算法之特徵量訓練與預測 ............................................. 39
5.3.1 堆疊物體訓練特徵量選取 ....................................................... 39
5.3.2 堆疊物體特徵量訓練 ............................................................... 39
5.3.3 堆疊物體特徵量預測 ............................................................... 40
5.4 堆疊物體辨識與物體追蹤實驗結果 ............................................. 41
5.4.1 相同堆疊物體辨識實驗結果 ................................................... 42
5.4.2 不同堆疊物體辨識實驗結果 ................................................... 45
5.4.3 物體追蹤實驗結果 ................................................................... 47
第六章 結論與未來展望 ......................................................................... 50
參考文獻 .................................................................................................... 51

圖目錄
圖2. 1、平均值偏移示意圖 ................................................................... 9
圖2. 2、SVM超平面示意圖 ............................................................... 10
圖3. 1、物體偵測與辨識演算法流程圖 ............................................. 14
圖3. 2、SURF特徵點匹配流程圖 ...................................................... 14
圖3. 3、SURF特徵點與特徵點描述子建立流程圖 .......................... 15
圖3. 4、近似積分影像示意圖 ............................................................. 15
圖3. 5、像素特徵值比較示意圖 ......................................................... 16
圖3. 6、Harr-like feature 示意圖 ........................................................ 16
圖3. 7、SURF特徵點描述子示意圖 .................................................. 17
圖3. 8、SURF特徵點匹配結果 .......................................................... 19
圖3. 9、實驗場景圖 ............................................................................. 20
圖3. 10、特徵量訓練步驟流程圖 ....................................................... 20
圖4. 1、堆疊物體分群之候選點分群演算法流程圖 ......................... 28
圖4. 2、影像特徵點之候選點結果圖 ................................................. 30
圖4. 3、候選點群集與群集中心點結果 ............................................. 31
圖4. 4模板匹配追蹤演算法流程圖 .................................................... 33
圖5. 1、POINT GREY Flea 3 高速攝影機 ........................................ 37
VII
圖5. 2、參考影像區塊訓練影像 ......................................................... 47

表目錄
表2. 1、特徵點演算法比較表 ............................................................. 12
表3. 1、SVM訓練正向物體特徵量標籤表(1) .................................. 21
表3. 2、SVM訓練正向物體特徵量標籤表(2) .................................. 22
表3. 3、SVM訓練正向物體特徵量標籤表(3) .................................. 22
表3. 4、SVM訓練正向物體特徵量標籤表(4) .................................. 23
表3. 5、SVM訓練正向物體特徵量標籤表(4) .................................. 23
表3. 6、SVM訓練反向物體特徵量標籤表(1) .................................. 24
表3. 7、SVM訓練反向物體特徵量標籤表(2) .................................. 25
表3. 8、SVM訓練反向物體特徵量標籤表(3) .................................. 25
表3. 9、 SVM訓練反向物體特徵量標籤表(4) ................................ 26
表3. 10、SVM訓練反向物體特徵量標籤表(5) ................................ 26
表5. 1、電腦規格表 ............................................................................. 37
表5. 2、攝影機規格表 ......................................................................... 37
表5. 3、使用軟體版本 ......................................................................... 37
表5. 4、實驗用之參考影像資料庫 ..................................................... 38
表5. 5、辨識標準評估表 ..................................................................... 40
表5. 6、相同堆疊物體辨識準確度(1) ................................................ 42
表5. 7、相同堆疊物體辨識準確度(2) ................................................ 43
IX
表5. 8、相同堆疊物體辨識準確度(3) ................................................ 43
表5. 9、相同堆疊物體辨識準確度(4) ................................................ 44
表5. 10、相同堆疊物體辨識準確度(5) .............................................. 44
表5. 11、不同堆疊物體辨識準確度(1) .............................................. 46
表5. 12、不同堆疊物體辨識準確度(2) .............................................. 46
表5. 13、辨識物體與追蹤實驗結果 ................................................... 48
表5. 14、辨識物體與追蹤實驗CPU版本與GPU版本花費時間 ... 49

參考文獻
[1] D. G. Lowe, “Distinctive image features from scale-invariant keypoints,” International Journal of Computer Vision, Vol. 60, No. 2, pp. 91-110, 2004.
[2] Y. Ke, R. Sukthankar, “PCA-SIFT: A More Distinctive Representation for Local Image Descriptors,” Computer Vision and Pattern Recognition, Vol. 2, pp. 506-513, 2004.
[3] S. Hinterstoisser, C. Cagniart, “Gradient Response Maps for Real-Time Detection of Texture-Less Objects,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 34, pp. 876-888, 2012.
[4] S. Hinterstoisser, V. Lepetit, S. llic, P. Fua, “Dominant orientation templates for real-time detection of texture-less objects,” Computer Vision and Pattern Recognition, pp.2257-2264, 2010.
[5] S. Hinterstoisser, S. Holzer, C. Cagniart, “Multimodal templates for real-time detection of texture-less objects in heavily cluttered scenes,” IEEE International Conference on Computer Vision, pp.858-865, 2011.
[6] Mac Queen, J. B., “Some Methods for classification and Analysis of Multivariate Observations,” Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability , Vol. 1, pp. 281-297, 1967.
[7] Cheng, Yizong, “Mean Shift, Mode Seeking, and Clustering,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 17, pp. 790-799, 1995.
[8] F. Jurie, M. Dhome, “Hyperplane Approximation for Template Matching,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 24, pp. 996-1000, 2002.
52
[9] Z. Haladova, E. Šikudo, “Multiple Instances Detection in RGBD images,” Conference of ICCVG, LNCS 8671, pp.246-253, 2014.
[10] S. Zickler, M. Veloso, “Detection and Localization of Multiple Objects,” IEEE-RAS International Conference on Humanoid Robots, pp. 20-25, 2006.
[11] C.-C. Chang, C.-J. Lin, “LIBSVM: a library for support vector machines,” ACM Transactions on Intelligent Systems and Techonology, 2011.
[12] H. Bay, T. Tuytelaars, and L. V. Gool, "SURF：Speeded Up Robust Features," International Conference on Computer Vision, pp. 404-417, 2006.
[13] E. Rublee, V. Rabaud, K. Konolige, G. Bradski, “ORB: An efficient alternative to SIFT or SURF,” IEEE International Conference on Computer Vision(ICCV), pp. 2564-2571, 2011.
[14] Rostern, Edward, Poter, R. Drummond, Tom, “Faster and Better: A Machine Learning Approach to Corner Detection,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 32, pp. 105-119, 2010.
[15] M. Calonder, V. Lepetit, C. Strecha, and P. Fua, “Brief: Binary robust independent elementary features,” In European Conference on Computer Vision, 2010.
[16] R. Lienhart, J. Maydt, “An extended set of Haar-like features for rapid object detection”, International Conference on Image Processing, Vol.1, pp. 900-903, 2002.
[17] T. Menzies, Y. Hu, “Data Mining For Very Busy People,” IEEE Computer, Vol. 36, pp. 22-29, 2003.
[18] N. S. Altman, “An Introduction to Kernel and Nearest-Neighbor Nonparametric Regression,” The American Statistician, Vol. 46, pp. 175-185, 1992.
[19] S. Gupta, R. Girshick, P. Arbelaez, J. Malik, “Learning rich features form
53
RGB-D images for object detection and segmentation,” In ECCV. Springer, 2014.
[20] G. D. Hager, P. N. Belhumeur, “Efficient Region Tracking with Parametric Models of Geometry and Illumination,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 20, No. 10, pp. 1025-1039, 1998.
[21] L. Juan, “A Comparison of SIFT, PCA-SIFT and SURF,” International Journal of Image Processing, Vol. 3, Issue. 4, 2011.