CMT跟蹤算法學習筆記

近期在學習目标跟蹤算法的過程中發現，CMT算法的代碼實測效果非常不錯。對比之前學習過的SCM之類基于稀疏表示的跟蹤算法，CMT的魯棒性雖然不一定比之更高，但稀疏表示的方法普遍耗時很嚴重，導緻其無法應用于實際工程項目，而CMT卻能兼顧實時性和魯棒性。

查閱資料發現，CMT對應的論文曾經拿下了2014年wacv會議的最佳論文獎。作者後來進一步完善了該算法，并在CVPR2015上發表了相關的論文，由此看來，CMT算法确實值得研究研究。值得稱贊的是，作者已經将完整的算法源碼公布在了論文首頁上http://www.gnebehay.com/cmt/，其中包含了C++和Python的全部代碼。由于不懂Python，這幾天仔細讀了一下C++源碼，不得不說，作者的代碼風格非正常範，注釋也寫得非常詳細，讀起來酣暢淋漓。另外，在此網站的首頁上還有作者本人的簡介，其實他就是openTLD代碼的作者，由此可見其程式設計功底之深厚。

順便提一下，之前從網站上下載下傳的C++源碼，可能編譯會通不過，出現M_PI未聲明和int S[2*N-1]中N不是常量之類的錯誤，現在作者已經修改了GitHub上源碼中的這些小錯誤，大家下載下傳最新版的源碼就行。另外，作者在代碼工程中加入了非常友好的指令行參數解析代碼，至于如何使用webcam或者video或者sequence進行測試，源碼檔案夾裡有詳細的說明，在此不再贅述。

結合論文，了解CMT的源碼還是不太困難的，作者在代碼中做了一些工程上的處理，主要展現在關鍵點的兩次比對和融合，看起來簡單但卻很有效。下面我用Visio畫出了整個算法的流程圖，以便更加清晰地了解CMT算法的核心思想和具體實作方法。

void CMT::processFrame(Mat im_gray)函數的處理流程

源碼總結

整個CMT算法的全部函數都在CMT類中實作，其包括4大元件，分别封裝成4個類：Tracker、Matcher、Consensus、Fusion。另外，CMT類中還包括FAST detector和BRISK descriptor。

Tracker – 使用金字塔LK光流法

tracker.track(im_prev, im_gray, points_active, points_tracked, status);           

• 1

• 1

已知第t-1幀中的有效關鍵點points_active，通過計算前向光流（第t-1幀到第t幀）和後向光流（第t幀到第t-1幀），再比較兩次得到的對應關鍵點之間的距離，距離大于門檻值的關鍵點對排除掉，剩下的關鍵點即作為跟蹤到的關鍵點。

Matcher – 采用“BruteForce-Hamming”類型的特征描述比對器

Matcher初始化

matcher.initialize(points_normalized, descs_fg, classes_fg, descs_bg, center);           

• 1

• 1

将第一幀中所有前景和背景關鍵點的特征描述構造成一個特征描述庫database。注意，這裡把背景關鍵點的特征描述desc_bg存儲在前，後面在構造database_potential時，存儲前景關鍵點索引indices_potential時需要再加上背景關鍵點的總個數num_bg_points。

關鍵點全局比對

matcher.matchGlobal(keypoints, descriptors, points_matched_global, classes_matched_global);           

• 1

• 1

将目前幀中檢測器得到的所有關鍵點的特征描述與database進行knnMatch比對（k=2），每個特征描述子在database尋找最佳的2個比對結果，将符合以下條件之一的比對關鍵點排除：

1. 比對到了背景關鍵點；
2. 最佳比對的比對距離大于門檻值0.25；
3. 最佳比對與次佳比對的比對距離之比大于門檻值0.8（比率越小，最佳比對越優于次佳比對）

關鍵點局部比對

matcher.matchLocal(keypoints, descriptors, center, scale, rotation,points_matched_local,
    classes_matched_local);           

• 1
• 2

• 1
• 2

1. 比較目前幀中檢測得到的每一個關鍵點與第一幀中經過旋轉和尺度變換之後的所有前景關鍵點之間的歐氏距離，小于門檻值20則該前景關鍵點是有可能比對上的，将這些可能的前景關鍵點構造成一個特征描述庫database_potential；
2. 将目前幀中檢測得到的每一個關鍵點的特征描述與database_potential進行knnMatch比對，每個特征描述子在database_potential尋找最佳的2個比對結果，排除不穩定的關鍵點的政策與matchGlobal類似。

Consensus – 目标關鍵點的一緻性限制條件

Consensus初始化

consensus.initialize(points_normalized);           

• 1

• 1

計算并儲存第一幀中所有歸一化前景關鍵點points_normalized與x軸的夾角（反正切）angles_pairwise以及關鍵點兩兩之間的距離distances_pairwise。

評估目前的旋轉角度和尺度因子

consensus.estimateScaleRotation(points_fused, classes_fused, scale, rotation);           

• 1

• 1

計算matchGlobal比對後融合得到的關鍵點的夾角以及關鍵點兩兩之間的距離，并與對應的points_normalized關鍵點的夾角求差、距離求商，再分别取平均值，評估出目前幀中目标的尺度因子scale和旋轉角度rotation。

擷取目标位置和inliers關鍵點

consensus.findConsensus(points_fused, classes_fused, scale, rotation, center,
    points_inlier, classes_inlier);           

• 1
• 2

• 1
• 2

1. 計算matchGlobal比對後融合得到的關鍵點的投票，即每一個關鍵點與對應的經過尺度和旋轉變換後的points_normalized關鍵點之間構成的向量；
2. 計算兩兩投票（1中的向量）之間的距離，按距離的大小進行升序排列；
3. 聚類并得到結果中最大的類；（當兩個類之間的距離小于門檻值，合并這兩個類）
4. 将此類中的所有關鍵點作為points_inlier；
5. 将所有points_inlier關鍵點的坐标均值作為目标中心點center。

Fusion – 将兩種關鍵點不重複地融合

關鍵點初步融合

fusion.preferFirst(points_tracked, classes_tracked, points_matched_global, classes_matched_global,
    points_fused, classes_fused);           

• 1
• 2

• 1
• 2

将光流跟蹤到的關鍵點與matchGlobal比對到的關鍵點融合，得到的關鍵點用于評估目标的旋轉角度和尺度，以及投票尋找目标中心位置。

關鍵點二次融合

fusion.preferFirst(points_matched_local, classes_matched_local, points_inlier, classes_inlier,
    points_active, classes_active);           

• 1
• 2

• 1
• 2

将matchLocal比對到的關鍵點與inliers關鍵點融合，得到最終有效的目标關鍵點points_active，這些關鍵點用于下一幀的跟蹤。

下面兩個基本是一樣的，下載下傳以後可以在linux下，cmake編譯成功，codeblocks能成功運作，效果不理想，一動就丢失目标。

trax.cpp是不需要的，

https://github.com/gnebehay/CppMT

http://download.csdn.net/download/wwzh2003/9274339

https://github.com/ArminPCM/OpenCMToolTracking

ios版：

https://github.com/songrotek/Tracking-on-iOS

android版：

https://github.com/cbui005/AndroidCMT_Tracking