TLD（Tracking-Learning-Detection）学习与源码理解之（三）
TLD（Tracking-Learning-Detection）學習與源碼理解之（三）
zouxy09@qq.com
http://blog.csdn.net/zouxy09
?
?????? 下面是自己在看論文和這些大牛的分析過程中，對代碼進行了一些理解，但是由于自己接觸圖像處理和機器視覺沒多久，另外由于自己編程能力比較弱，所以分析過程可能會有不少的錯誤，希望各位不吝指正。而且，因為編程很多地方不懂，所以注釋得非常亂，還海涵。
?
從main()函數切入，分析整個TLD運行過程如下：
（這里只是分析工作過程，全部注釋的代碼見博客的更新）
1、分析程序運行的命令行參數；
./run_tld -p ../parameters.yml -s ../datasets/06_car/car.mpg -b ../datasets/06_car/init.txt –r
?
2、讀入初始化參數（程序中變量）的文件parameters.yml；
?
3、通過文件或者用戶鼠標框選的方式指定要跟蹤的目標的Bounding Box；
?
4、用上面得到的包含要跟蹤目標的Bounding? Box和第一幀圖像去初始化TLD系統，
?? tld.init(last_gray, box, bb_file); 初始化包含的工作如下：
?
4.1、buildGrid(frame1, box);
檢測器采用掃描窗口的策略：掃描窗口步長為寬高的 10%，尺度縮放系數為1.2；此函數構建全部的掃描窗口grid，并計算每一個掃描窗口與輸入的目標box的重疊度；重疊度定義為兩個box的交集與它們的并集的比；
?
4.2、為各種變量或者容器分配內存空間；
?
4.3、getOverlappingBoxes(box, num_closest_init);
此函數根據傳入的box（目標邊界框），在整幀圖像中的全部掃描窗口中（由上面4.1得到）尋找與該box距離最小（即最相似，重疊度最大）的num_closest_init（10）個窗口，然后把這些窗口歸入good_boxes容器。同時，把重疊度小于0.2的，歸入bad_boxes容器；相當于對全部的掃描窗口進行篩選。并通過BBhull函數得到這些掃描窗口的最大邊界。
???
4.5、classifier.prepare(scales);
準備分類器，scales容器里是所有掃描窗口的尺度，由上面的buildGrid()函數初始化；
TLD的分類器有三部分：方差分類器模塊、集合分類器模塊和最近鄰分類器模塊；這三個分類器是級聯的，每一個掃描窗口依次全部通過上面三個分類器，才被認為含有前景目標。這里prepare這個函數主要是初始化集合分類器模塊；
集合分類器（隨機森林）基于n個基本分類器（共10棵樹），每個分類器（樹）都是基于一個pixel comparisons（共13個像素比較集）的，也就是說每棵樹有13個判斷節點（組成一個pixel comparisons），輸入的圖像片與每一個判斷節點（相應像素點）進行比較，產生0或者1，然后將這13個0或者1連成一個13位的二進制碼x（有2^13種可能），每一個x對應一個后驗概率P(y|x)= #p/(#p+#n) （也有2^13種可能），#p和#n分別是正和負圖像片的數目。那么整一個集合分類器（共10個基本分類器）就有10個后驗概率了，將10個后驗概率進行平均，如果大于閾值（一開始設經驗值0.65，后面再訓練優化）的話，就認為該圖像片含有前景目標；
后驗概率P(y|x)= #p/(#p+#n)的產生方法：初始化時，每個后驗概率都得初始化為0；運行時候以下面方式更新：將已知類別標簽的樣本（訓練樣本）通過n個分類器進行分類，如果分類結果錯誤，那么相應的#p和#n就會更新，這樣P(y|x)也相應更新了。
pixel comparisons的產生方法：先用一個歸一化的patch去離散化像素空間，產生所有可能的垂直和水平的pixel comparisons，然后我們把這些pixel comparisons隨機分配給n個分類器，每個分類器得到完全不同的pixel comparisons（特征集合），這樣，所有分類器的特征組統一起來就可以覆蓋整個patch了。
特征是相對于一種尺度的矩形框而言的，TLD中第s種尺度的第i個特征features[s][i] = Feature(x1, y1, x2, y2);是兩個隨機分配的像素點坐標（就是由這兩個像素點比較得到0或者1的）。每一種尺度的掃描窗口都含有totalFeatures = nstructs * structSize個特征；nstructs為樹木（由一個特征組構建，每組特征代表圖像塊的不同視圖表示）的個數；structSize為每棵樹的特征個數，也即每棵樹的判斷節點個數；樹上每一個特征都作為一個決策節點；
prepare函數的工作就是先給每一個掃描窗口初始化了對應的pixel comparisons（兩個隨機分配的像素點坐標）；然后初始化后驗概率為0；
?
4.6、generatePositiveData(frame1, num_warps_init);
此函數通過對第一幀圖像的目標框box（用戶指定的要跟蹤的目標）進行仿射變換來合成訓練初始分類器的正樣本集。具體方法如下：先在距離初始的目標框最近的掃描窗口內選擇10個bounding box（已經由上面的getOverlappingBoxes函數得到，存于good_boxes里面了，還記得不？），然后在每個bounding box的內部，進行±1%范圍的偏移，±1%范圍的尺度變化，±10%范圍的平面內旋轉，并且在每個像素上增加方差為5的高斯噪聲（確切的大小是在指定的范圍內隨機選擇的），那么每個box都進行20次這種幾何變換，那么10個box將產生200個仿射變換的bounding box，作為正樣本。具體實現如下：
getPattern(frame(best_box), pEx, mean, stdev);此函數將frame圖像best_box區域的圖像片歸一化為均值為0的15*15大小的patch，存于pEx（用于最近鄰分類器的正樣本）正樣本中（最近鄰的box的Pattern），該正樣本只有一個。
generator(frame, pt, warped, bbhull.size(), rng);此函數屬于PatchGenerator類的構造函數，用來對圖像區域進行仿射變換，先RNG一個隨機因子，再調用（）運算符產生一個變換后的正樣本。
classifier.getFeatures(patch, grid[idx].sidx, fern);函數得到輸入的patch的特征fern（13位的二進制代碼）；
pX.push_back(make_pair(fern, 1));?? //positive ferns <features, labels=1>然后標記為正樣本，存入pX（用于集合分類器的正樣本）正樣本庫；
以上的操作會循環 num_warps * good_boxes.size()即20 * 10 次，這樣，pEx就有了一個正樣本，而pX有了200個正樣本了；
?
4.7、meanStdDev(frame1(best_box), mean, stdev);
統計best_box的均值和標準差，var = pow(stdev.val[0],2) * 0.5;作為方差分類器的閾值。
?
4.8、generateNegativeData(frame1);
???? 由于TLD僅跟蹤一個目標，所以我們確定了目標框了，故除目標框外的其他圖像都是負樣本，無需仿射變換；具體實現如下：
???? 由于之前重疊度小于0.2的，都歸入 bad_boxes了，所以數量挺多，把方差大于var*0.5f的bad_boxes都加入負樣本，同上面一樣，需要classifier.getFeatures(patch, grid[idx].sidx, fern);和nX.push_back(make_pair(fern, 0));得到對應的fern特征和標簽的nX負樣本（用于集合分類器的負樣本）；
??? 然后隨機在上面的bad_boxes中取bad_patches（100個）個box，然后用 getPattern函數將frame圖像bad_box區域的圖像片歸一化到15*15大小的patch，存在nEx（用于最近鄰分類器的負樣本）負樣本中。
這樣nEx和nX都有負樣本了；（box的方差通過積分圖像計算）
?
4.9、然后將nEx的一半作為訓練集nEx，另一半作為測試集nExT；同樣，nX也拆分為訓練集nX和測試集nXT；
?
4.10、將負樣本nX和正樣本pX合并到ferns_data[]中，用于集合分類器的訓練；
?
4.11、將上面得到的一個正樣本pEx和nEx合并到nn_data[]中，用于最近鄰分類器的訓練；
?
4.12、用上面的樣本訓練集訓練 集合分類器（森林） 和 最近鄰分類器：
? classifier.trainF(ferns_data, 2); //bootstrap = 2
對每一個樣本ferns_data[i] ，如果樣本是正樣本標簽，先用measure_forest函數返回該樣本所有樹的所有特征值對應的后驗概率累加值，該累加值如果小于正樣本閾值（0.6* nstructs，這就表示平均值需要大于0.6（0.6* nstructs / nstructs）,0.6是程序初始化時定的集合分類器的閾值，為經驗值，后面會用測試集來評估修改，找到最優），也就是輸入的是正樣本，卻被分類成負樣本了，出現了分類錯誤，所以就把該樣本添加到正樣本庫，同時用update函數更新后驗概率。對于負樣本，同樣，如果出現負樣本分類錯誤，就添加到負樣本庫。
? classifier.trainNN(nn_data);
???? 對每一個樣本nn_data，如果標簽是正樣本，通過NNConf(nn_examples[i], isin, conf, dummy);計算輸入圖像片與在線模型之間的相關相似度conf，如果相關相似度小于0.65 ，則認為其不含有前景目標，也就是分類錯誤了；這時候就把它加到正樣本庫。然后就通過pEx.push_back(nn_examples[i]);將該樣本添加到pEx正樣本庫中；同樣，如果出現負樣本分類錯誤，就添加到負樣本庫。
?
4.13、用測試集在上面得到的 集合分類器（森林） 和 最近鄰分類器中分類，評價并修改得到最好的分類器閾值。
? classifier.evaluateTh(nXT, nExT);
?? 對集合分類器，對每一個測試集nXT，所有基本分類器的后驗概率的平均值如果大于thr_fern（0.6），則認為含有前景目標，然后取最大的平均值（大于thr_fern）作為該集合分類器的新的閾值。
?? 對最近鄰分類器，對每一個測試集nExT，最大相關相似度如果大于nn_fern（0.65），則認為含有前景目標，然后取最大的最大相關相似度（大于nn_fern）作為該最近鄰分類器的新的閾值。
?
5、進入一個循環：讀入新的一幀，然后轉換為灰度圖像，然后再處理每一幀processFrame；
?
6、processFrame(last_gray, current_gray, pts1, pts2, pbox, status, tl, bb_file);逐幀讀入圖片序列，進行算法處理。processFrame共包含四個模塊（依次處理）：跟蹤模塊、檢測模塊、綜合模塊和學習模塊；
?
6.1、跟蹤模塊：track(img1, img2, points1, points2);
track函數完成前一幀img1的特征點points1到當前幀img2的特征點points2的跟蹤預測；
?
6.1.1、具體實現過程如下：
（1）先在lastbox中均勻采樣10*10=100個特征點（網格均勻撒點），存于points1：
bbPoints(points1, lastbox);
（2）利用金字塔LK光流法跟蹤這些特征點，并預測當前幀的特征點（見下面的解釋）、計算FB error和匹配相似度sim，然后篩選出 FB_error[i] <= median(FB_error) 和 sim_error[i] > median(sim_error) 的特征點（舍棄跟蹤結果不好的特征點），剩下的是不到50%的特征點：
tracker.trackf2f(img1, img2, points, points2);
（3）利用剩下的這不到一半的跟蹤點輸入來預測bounding box在當前幀的位置和大小 tbb：
bbPredict(points, points2, lastbox, tbb);
（4）跟蹤失敗檢測：如果FB error的中值大于10個像素（經驗值），或者預測到的當前box的位置移出圖像，則認為跟蹤錯誤，此時不返回bounding box：
if (tracker.getFB()>10 || tbb.x>img2.cols ||? tbb.y>img2.rows || tbb.br().x < 1 || tbb.br().y <1)
（5）歸一化img2(bb)對應的patch的size（放縮至patch_size = 15*15），存入pattern：
getPattern(img2(bb),pattern,mean,stdev);
（6）計算圖像片pattern到在線模型M的保守相似度：
classifier.NNConf(pattern,isin,dummy,tconf);
（7）如果保守相似度大于閾值，則評估本次跟蹤有效，否則跟蹤無效：
if (tconf>classifier.thr_nn_valid) tvalid =true;
?
6.1.2、TLD跟蹤模塊的實現原理和trackf2f函數的實現：
?? TLD跟蹤模塊的實現是利用了Media Flow 中值光流跟蹤和跟蹤錯誤檢測算法的結合。中值流跟蹤方法是基于Forward-Backward Error和NNC的。原理很簡單：從t時刻的圖像的A點，跟蹤到t+1時刻的圖像B點；然后倒回來，從t+1時刻的圖像的B點往回跟蹤，假如跟蹤到t時刻的圖像的C點，這樣就產生了前向和后向兩個軌跡，比較t時刻中 A點和C點的距離，如果距離小于一個閾值，那么就認為前向跟蹤是正確的；這個距離就是FB_error；
bool LKTracker::trackf2f(const Mat& img1, const Mat& img2, vector<Point2f> &points1, vector<cv::Point2f> &points2)
函數實現過程如下：
（1）先利用金字塔LK光流法跟蹤預測前向軌跡：
? calcOpticalFlowPyrLK( img1,img2, points1, points2, status, similarity, window_size, level, term_criteria, lambda, 0);
（2）再往回跟蹤，產生后向軌跡：
? calcOpticalFlowPyrLK( img2,img1, points2, pointsFB, FB_status,FB_error, window_size, level, term_criteria, lambda, 0);
（3）然后計算 FB-error：前向與 后向 軌跡的誤差：
? for( int i= 0; i<points1.size(); ++i )
??????? FB_error[i] = norm(pointsFB[i]-points1[i]);? ???
（4）再從前一幀和當前幀圖像中（以每個特征點為中心）使用亞象素精度提取10x10象素矩形（使用函數getRectSubPix得到），匹配前一幀和當前幀中提取的10x10象素矩形，得到匹配后的映射圖像（調用matchTemplate），得到每一個點的NCC相關系數（也就是相似度大小）。
normCrossCorrelation(img1, img2, points1, points2);
（5）然后篩選出 FB_error[i] <= median(FB_error) 和 sim_error[i] > median(sim_error) 的特征點（舍棄跟蹤結果不好的特征點），剩下的是不到50%的特征點；
filterPts(points1, points2);
?
6.2、檢測模塊：detect(img2);
TLD的檢測分類器有三部分：方差分類器模塊、集合分類器模塊和最近鄰分類器模塊；這三個分類器是級聯的。當前幀img2的每一個掃描窗口依次通過上面三個分類器，全部通過才被認為含有前景目標。具體實現過程如下：
先計算img2的積分圖，為了更快的計算方差：
integral(frame,iisum,iisqsum);
然后用高斯模糊，去噪：
? GaussianBlur(frame,img,Size(9,9),1.5);?
下一步就進入了方差檢測模塊：
?
6.2.1、方差分類器模塊：getVar(grid[i],iisum,iisqsum) >= var
利用積分圖計算每個待檢測窗口的方差，方差大于var閾值（目標patch方差的50%）的，則認為其含有前景目標，通過該模塊的進入集合分類器模塊：
?
6.2.2、集合分類器模塊：
集合分類器（隨機森林）共有10顆樹（基本分類器），每棵樹13個判斷節點，每個判斷節點經比較得到一個二進制位0或者1，這樣每棵樹就對應得到一個13位的二進制碼x（葉子），這個二進制碼x對應于一個后驗概率P(y|x)。那么整一個集合分類器（共10個基本分類器）就有10個后驗概率了，將10個后驗概率進行平均，如果大于閾值（一開始設經驗值0.65，后面再訓練優化）的話，就認為該圖像片含有前景目標；具體過程如下：
（1）先得到該patch的特征值（13位的二進制代碼）：
classifier.getFeatures(patch,grid[i].sidx,ferns);
（2）再計算該特征值對應的后驗概率累加值：
conf = classifier.measure_forest(ferns);???????????
（3）若集合分類器的后驗概率的平均值大于閾值fern_th（由訓練得到），就認為含有前景目標：
if (conf > numtrees * fern_th)? dt.bb.push_back(i);?
（4）將通過以上兩個檢測模塊的掃描窗口記錄在detect structure中；
（5）如果順利通過以上兩個檢測模塊的掃描窗口數大于100個，則只取后驗概率大的前100個；
nth_element(dt.bb.begin(), dt.bb.begin()+100, dt.bb.end(),
CComparator(tmp.conf));
進入最近鄰分類器：
?
6.2.3、最近鄰分類器模塊
（1）先歸一化patch的size（放縮至patch_size = 15*15），存入dt.patch[i];
getPattern(patch,dt.patch[i],mean,stdev);?
（2）計算圖像片pattern到在線模型M的相關相似度和保守相似度：
classifier.NNConf(dt.patch[i],dt.isin[i],dt.conf1[i],dt.conf2[i]);
（3）相關相似度大于閾值，則認為含有前景目標：
if (dt.conf1[i]>nn_th) ?dbb.push_back(grid[idx]);
到目前為止，檢測器檢測完成，全部通過三個檢測模塊的掃描窗口存在dbb中；
?
6.3、綜合模塊：
TLD只跟蹤單目標，所以綜合模塊綜合跟蹤器跟蹤到的單個目標和檢測器可能檢測到的多個目標，然后只輸出保守相似度最大的一個目標。具體實現過程如下：
（1）先通過 重疊度 對檢測器檢測到的目標bounding box進行聚類，每個類的重疊度小于0.5：
clusterConf(dbb, dconf, cbb, cconf);
（2）再找到與跟蹤器跟蹤到的box距離比較遠的類（檢測器檢測到的box），而且它的相關相似度比跟蹤器的要大：記錄滿足上述條件，也就是可信度比較高的目標box的個數：
if (bbOverlap(tbb, cbb[i])<0.5 && cconf[i]>tconf) confident_detections++;
（3）判斷如果只有一個滿足上述條件的box，那么就用這個目標box來重新初始化跟蹤器（也就是用檢測器的結果去糾正跟蹤器）：
if (confident_detections==1)? bbnext=cbb[didx];
（4）如果滿足上述條件的box不只一個，那么就找到檢測器檢測到的box與跟蹤器預測到的box距離很近（重疊度大于0.7）的所以box，對其坐標和大小進行累加：
if(bbOverlap(tbb,dbb[i])>0.7)? cx += dbb[i].x;……
（5）對與跟蹤器預測到的box距離很近的box 和 跟蹤器本身預測到的box 進行坐標與大小的平均作為最終的目標bounding box，但是跟蹤器的權值較大：
bbnext.x = cvRound((float)(10*tbb.x+cx)/(float)(10+close_detections));……
（6）另外，如果跟蹤器沒有跟蹤到目標，但是檢測器檢測到了一些可能的目標box，那么同樣對其進行聚類，但只是簡單的將聚類的cbb[0]作為新的跟蹤目標box（不比較相似度了？？還是里面已經排好序了？？），重新初始化跟蹤器：
bbnext=cbb[0];
至此，綜合模塊結束。
?
6.4、學習模塊：learn(img2);
??? 學習模塊也分為如下四部分：
6.4.1、檢查一致性：
（1）歸一化img(bb)對應的patch的size（放縮至patch_size = 15*15），存入pattern：
? getPattern(img(bb), pattern, mean, stdev);
（2）計算輸入圖像片（跟蹤器的目標box）與在線模型之間的相關相似度conf：
? classifier.NNConf(pattern,isin,conf,dummy);
（3）如果相似度太小了或者如果方差太小了或者如果被被識別為負樣本，那么就不訓練了；
if (conf<0.5)……或if (pow(stdev.val[0], 2)< var)……或if(isin[2]==1)……
?
6.4.2、生成樣本：
先是集合分類器的樣本：fern_examples：
（1）先計算所有的掃描窗口與目前的目標box的重疊度：
grid[i].overlap = bbOverlap(lastbox, grid[i]);
（2）再根據傳入的lastbox，在整幀圖像中的全部窗口中尋找與該lastbox距離最小（即最相似，重疊度最大）的num_closest_update個窗口，然后把這些窗口歸入good_boxes容器（只是把網格數組的索引存入）同時，把重疊度小于0.2的，歸入 bad_boxes 容器：
? getOverlappingBoxes(lastbox, num_closest_update);
（3）然后用仿射模型產生正樣本（類似于第一幀的方法，但只產生10*10=100個）：
generatePositiveData(img, num_warps_update);?
（4）加入負樣本，相似度大于1？？相似度不是出于0和1之間嗎？
idx=bad_boxes[i];
if (tmp.conf[idx]>=1) fern_examples.push_back(make_pair(tmp.patt[idx],0));
然后是最近鄰分類器的樣本：nn_examples：
if (bbOverlap(lastbox,grid[idx]) < bad_overlap)
??????? nn_examples.push_back(dt.patch[i]);
?
6.4.3、分類器訓練：
classifier.trainF(fern_examples,2);
classifier.trainNN(nn_examples);
?
6.4.4、把正樣本庫（在線模型）包含的所有正樣本顯示在窗口上
classifier.show();
至此，tld.processFrame函數結束。
?
7、如果跟蹤成功，則把相應的點和box畫出來：
??? if (status){
????? drawPoints(frame,pts1);
????? drawPoints(frame,pts2,Scalar(0,255,0));? //當前的特征點用藍色點表示
????? drawBox(frame,pbox);
????? detections++;
}
?
8、然后顯示窗口和交換圖像幀，進入下一幀的處理：
??? imshow("TLD", frame);
swap(last_gray, current_gray);
至此，main()函數結束（只分析了框架）。
總結
以上是生活随笔為你收集整理的TLD（Tracking-Learning-Detection）学习与源码理解之（三）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： TLD（Tracking-Learnin
- 下一篇： TLD（Tracking-Learnin