庖丁解牛TLD
一、庖丁解牛TLD——開篇
最近在網上多次看到有關Zdenek Kalal的TLD的文章，說他做的工作如何的帥，看了一下TLD的視頻，感覺確實做的很好，有人夸張的說他這個系統可以和Kniect媲美，我倒是兩者的工作可比性不大，實現的方法也不同。但這個哥們做的真的很棒，最可貴的是人家提供了源碼可以下載。他相關的工作網上一搜一大片，推薦一個鏈接http://www.cvchina.net/article-22-1.html，再給個作者網站的鏈接http://info.ee.surrey.ac.uk/Personal/Z.Kalal/。
看了他的demo視頻頓時心潮澎湃，趕緊下載了他的源代碼后又有些崩潰了。他的工作量還是很大的，得靜下心來慢慢研究。直接看代碼難免云里霧里的，先看看人家的論文吧。
這哥們這幾年可真沒少發paper啊，我比較關注他實現的算法。TLD即Tracking Learning Detector，我認為就是依據跟蹤學習的目標檢測。看了他08年發表的一篇文章，介紹了他的這個算法，那時候還把算法稱為TMD（tracking、modeling、detection），他的tracking工作時基于Lucas-Kanade光流法的。modeling學習的過程有growing和pruning兩方面的工作，可以正負反饋，得到較好的學習結果，對于他的學習過程，他在另一篇文章中又詳細介紹了P-N learning這種學習算法。detection的部分用的是隨機森林的機器學習辦法，加上bootstarps。對于特征的選擇，他提出了一種基于LBP特征的2bit BP特征。幾篇文章下來，我已經有點暈乎了，這些算法都不是太熟悉，看來得結合代碼一個個啃了。
代碼正在一點點啃，有同樣興趣的朋友可以交流指導一下，不勝感激。
二、庖丁解牛TLD——初始化工作（為算法的準備）
我說的初始化，還不是算法的初始化工作，而是讀入圖像，響應鍵盤鼠標之類的工作。作者提供的代碼中的工作包含了從攝像頭讀取和從文件中讀取兩種輸入方案。這里介紹一下從文件輸入的辦法。因為OpenCV從視頻讀取圖像序列的辦法有很好的demo，我這里就不介紹攝像頭的辦法了。TLD下載后有一個文件夾是_input，里面存放著一組圖片組，圖片文件的名字為00001.png、00002.png....。我讀取圖片組的關鍵代碼如下，這段代碼具有普遍意義，可以移植到以后想讀入圖片組的任意程序中：
stringstream fileNameStream; string sourceImageFileName; for(int nFrame=0; nFrame<NUM; nFrame++) {nFrame++;fileNameStream << "_input\\" << setw(5) << setfill('0') << nFrameNum << ".png";sourceImageFileName = fileNameStream.str();fileNameStream.clear();fileNameStream.str("");// 讀取圖像g_src = imread(sourceImageFileName); }這就實現了圖片的讀入工作，再參考camshiftdemo的辦法實現了鼠標和鍵盤的響應。鼠標的響應就是得到目標區域的范圍，用鼠標選中boundingbox。文件讀進來了，目標區域boundingbox也得到了，接下來就是需要對算法進行研究了。
先介紹幾個我研究過的心得，bbox文件夾下面的代碼主要都是對boundingbox的處理。tld文件夾下面的存放的是主干的算法，從run_TLD入手，感覺就是對起始幀進行初始化工作，然后逐幀讀入圖片序列，進行算法處理。還是先分析初始化工作，作者的tldInitSource函數實現的就是基本的初始化，給一些變量賦值，開辟矩陣大小，這個沒什么好講的。tldInitFirstFrame文件完成的工作就是選中boundingbox，這個功能我已經通過鼠標的響應得到了boundingbox，也可以略過不細分析。重點的初始化工作是在tldInit里實現的，這個函數也是我接下來研究的重點，本人Matlab較差，真希望有高人指點啊，一起研究啊
三、庖丁解牛TLD——算法初始化
上一講我提到對于算法的初始化工作主要是在tldInit這個函數里實現的。主要分為如下幾大步驟，1）初始化Detector。2）初始化Trajectory。3）訓練Detector
1)初始化Detector
其中bb_scan為掃描grid區域，該函數輸入為boundingBox，輸出為一系列的RectBox，是根據boundingBox的大小參數對待搜素區域選擇一系列的box作為備選的跟蹤區域，box的位置和尺度都有變化，和RectBox相應的尺度。但RectBox有6個參數，前4個分別為Rect的左上角坐標（x1，y1）和右下角坐標（x2，y2）。后兩個參數求大神解釋（PS：后來在fern函數里找到了解釋，分別為指向對應尺度特征的指針位置、每一行box的數量——用在搜索鄰近box）！對于這個函數內部我還有一個疑惑，就是對ntuples函數功能的使用，哎，怎奈Matlab語法都不熟悉，只能慢慢啃了，感覺作者這里就是把RectBox的左上角的所有可能的坐標值傳入該函數，得到左上角坐標位置的全部組合（不知道理解對了沒）。
接下來的工作時特征的初始化，是在tldGenerateFeature函數里實現的。這個函數相對獨立，作者這里為了產生效果較好的隨機特征真是煞費苦心，輸入的參數有兩個，一個是nTREE = 10，一個是nFEATURE = 13。輸出為nTREE組特征，每組特征為nFEATURE個點對，每一個點對有4個參數，分別兩點坐標（x1，y1），（x2，y2），取值范圍為（0~1）其中第一個點的分辨率為0.1，還不太明白這樣設計的原因，待進一步分析代碼，有高人指點一下更好。值得注意的是產生的點對不是橫坐標相同x1 = x2，就是縱坐標相同y1 = y2。這里用圖片顯示一組特征，線段的兩個端點
下一步工作為初始化detector。這個功能是用強大的fern函數寫的，該函數有多個功能，根據傳入參數的標志分別可以實現clear操作、init操作、update操作、evaluate操作、detect操作、get pattern操作。fern函數是用c寫的，混合編程沒有弄的太明白，還沒能調試一下看看，只能看代碼猜。在初始化detector的工作里，用到的是init操作。
2）初始化Trajectory
這部分沒有什么要說明的，都是些零碎的初始化工作，matlab里面對一些必要的變量開辟一些空間和定義一些變量的值。具體分析Trajectory的工作的時候可以具體再分析
3）訓練Detector
首先得到Target，作者注釋說該Target只是用來顯示，有待我后續驗證。得到Target要調用函數img_patch，img_patch函數是獲得一幅圖像中目標區域box的像素信息patch。
接下來產生正樣本數據集，調用tldGeneratePositiveData。其中第二個參數為RectBox和box的重復區域比例信息，保存在overlap參數中，由函數bb_overlap得到。tldGeneratePositiveData函數首先根據overlap的比例信息選出重復區域比例大于60%并且前num_closet ?= 10個的最接近box的RectBox，相當于對RectBox進行篩選。并通過bb_hull函數得到這些RectBox的最大邊界。接下來的工作比較重要，要得到Pattern，調用的函數為tldGetPattern。初始化的工作就是對最接近box的RectBox區域得到其patch，然后調用tldPatch2Pattern將像素信息轉換為Pattern，具體的說就是歸一化RectBox對應的patch的size（放縮至patch_size = 15*15），將2維的矩陣變成一維的向量信息，然后將向量信息均值設為0，調整為zero mean and unit variance（ZMUV），這個過程調用函數tldPatch2Pattern實現。接下來處理RectBox最大邊界的模糊信息，再次用到img_patch函數，但這次調用的函數有很大的不同，還沒太理解作者要做什么啊，怎么感覺還有平移旋轉矩陣都出來了，暈啦（求高人指點）。該函數最后返回3個參數，pX為處理后的RectBox最大邊界處理后的像素信息，pEx最近鄰的RectBox的Pattern，bbP0為最近鄰的RectBox。
然后再產生負樣本數據tldGenerateNegativeData。得到遠離box（重復區域比例小于20%）的num_patches = 100個Pattern保存到nX中，隨機選中num_patches = 100個RectBox得到對應的patch保存到nEx中。這里調用了fern（5），即該函數的get pattern操作。
接下來對負樣本進行分類，分類到訓練集Training Set和驗證集Validation Set中去。
接下來使用Training Set進行訓練，先調用fern（2），更新，然后調用tldTrainNN最近鄰訓練數據。
接下來評估驗證集Validation Set的閾值。調用tldNN驗證。
至此，初始化的工作基本完成，限于本人水平有限，只能先對函數有個大概的認識，深深覺得先要靜下心來把訓練的算法搞清楚，再回過頭來再看一編代碼。
四、?庖丁解牛TLD——Tracking解析
前幾節都是根據作者的程序流程一步步介紹作者的工作，感覺只是對代碼的一個注釋，這次換一個思路，一部分一部分啃，作者的工作主要就是3部分么，tracking，learning，detection。
這次先介紹Tracking的工作。對于Tracking，作者主要使用的是他提出的Forward-Backward Error的辦法，使用Lucas-Kanade光流法跟蹤，對跟蹤的結果，用Forward-Backward Error做反饋，求FB error的結果與原始位置的歐式距離，把距離過大的跟蹤結果舍棄，他把這種利用FB error舍棄壞值的跟蹤方法叫做Median Flow，是把歐式距離集合中較大的50%的那些跟蹤結果舍棄。作者在他的文章Forward-Backward Error：Automatic Detection of Tracking Failures里提到用FB+NCC（交叉驗證）的方案，可以使跟蹤的結果最佳。作者的Tracking的辦法就是根據我以上介紹的流程實現的。接下來結合代碼再詳細剖析一下
先用bb_points函數在box中均勻采樣10*10個點，注意作者這里設置了采樣點的區域比box的區域少一圈邊界，邊界為5，在后面我會介紹作者這里的獨到用心。然后調用混合編程的lk函數實現lucas-Kanade光流法跟蹤，得到的結果有為這100個點的lk結果，前兩個參數為利用l-k方法得到的點當前的跟蹤位置坐標，第三個參數是利用NCC把跟蹤預測的結果周圍取10*10的小圖片與原始位置周圍10*10（這里取10*10，有心的朋友應該笑了，為什么作者之前在bb_points函數里要設置個邊界5，原來是防止越界哦）的小圖片（使用函數getRectSubPix得到）進行模板匹配（調用matchTemplate），再對匹配的結果歸一化，把這個結果保存在第三個參數中，第四個參數為FB error的歐氏距離。這個lk函數過程中有很多參數可以設置，對最終的結果我想應該應該也是有的，有待實驗驗證。接下來就是利用作者提出的Median Flow，得到NCC和FB error結果的中值，分別去掉中值一半的跟蹤結果不好的點，利用這一半（其實不到50%）的跟蹤點輸入函數bb_predict函數中預測bounding box在當前幀的位置和大小。
這基本就是Tracking工作的主要部分了，至于被遮擋的tracking（tldTrack_occlusion），作者進行了單獨處理，下一次再分析。
PS：很感謝最近有些網友與我一起研究TLD，不過本人能力不足，很多東西還是不理解，對于作者detection和learning的工作，感覺那部分的代碼實在好比天書，沒法拿出來和大家交流了，希望有識之士也能寫出來，和大家分享~~
五、庖丁解牛TLD——井底之蛙啦~
隨著和我交流TLD的朋友越來越多，我漸漸的知道的也多了，才發現我研究的結果只是滄海一粟。
這里先膜拜一下Alan Torres大神，他已經用c++把TLD重新寫好了，而且代碼很規范。他設計的理念有：
1. depends *only* on OpenCV (2.3)?
2. no Matlab!?
3. easy to compile and run (on linux, work in progress on OSX and windows)?
4. fast! (and more potential to be much faster)?
5. No Matlab! (did I say no matlab?)?
沒有matlab，多平臺，更快的速度。真好，就是我想做的，不過他現在這個程序，在我這電腦上實現速度還不行。他代碼的下載地址為https://github.com/alantrrs/OpenTLD，好像打不開，我是在這上面得到的https://github.com/arthurv/OpenTLD。不過是個Linux版本的。大家這么強，改改肯定就可以在xp下跑起來了，反正我是搞定了。
附上他軟件的設計接口。真是賞心悅目啊，不得不說人家做的東西很規范，慚愧慚愧
看不清還是下載下來大家自己看咯，不好意思，我不知道怎么能傳上去看得清晰
從他這個設計圖也可以看出來我之前幾講分析的流程還是可以接受的，init部分和track部分是相對獨立的。而比較復雜的是learning的部分和detect部分。下一步主攻這兩部分了。學習的越深入，越是發現自己很挫，都沒信心繼續寫下去了。硬著頭皮裝大蔥吧~
出處：http://blog.csdn.net/yang_xian521/article/details/6952870
總結
- 上一篇： 如何实现科技论文里面的算法
- 下一篇： Machine Learning wee