您的位置: 首页  >  文章  >  struct跟踪算法

struct跟踪算法

分类: 文章 • 2024-06-14 12:13:10

博客：http://blog.****.net/qianxin_dh


     《Struck:Structured Output Tracking with Kernels》是 Sam Hare, Amir Saffari, Philip H. S. Torr等人于2011年发表在Computer Vision (ICCV)上的一篇文章。Struck与传统跟踪算法的不同之处在于：传统跟踪算法(下图右手边)将跟踪问题转化为一个分类问题，并通过在线学习技术更新目标模型。然而，为了达到更新的目的，通常需要将一些预估计的目标位置作为已知类别的训练样本，这些分类样本并不一定与实际目标一致，因此难以实现最佳的分类效果。而Struck算法(下图左手边)主要提出一种基于结构输出预测的自适应视觉目标跟踪的框架，通过明确引入输出空间满足跟踪功能，能够避免中间分类环节，直接输出跟踪结果。同时,为了保证实时性，该算法还引入了阈值机制，防止跟踪过程中支持向量的过增长。

struct跟踪算法


      最后,大牛作者们也提供了c++版源代码，有兴趣的朋友可以下载下来，体验下该算法的强大。代码下载地址：https://github.com/gnebehay/STRUCK，代码调试需要Opencv2.1以上版本以及Eigen v2.0.15。


         在论文理解以及代码调试的过程中，主要参考了以下资料，感到获益匪浅，列举如下：
        
         1） Eigen的安装及学习
         
         2） 支持向量机通俗导论（理解SVM的三重境界）

               http://blog.****.net/v_july_v/article/details/7624837

第二部分

目前在目标检测任务中，由于svm自身具有较好的推广能力以及对分类的鲁棒性，得到了越来越多的应用。 Struck算法便使用了在线结构输出svm学习方法去解决跟踪问题。不同于常规算法训练一个分类器，Struck算法直接通过预测函数：struct跟踪算法,来预测每帧之间目标位置发生的变化,其中struct跟踪算法表示搜寻空间，例如，struct跟踪算法，上一帧中目标的新位置为Pt-1,则在当前帧中,目标位置就为struct跟踪算法（可见struct跟踪算法其实就是表示帧间目标位置变化关系的集合）。因此，在Struck算法中，已知类型的样本用（x，y）表示,而不再是（x，＋1）或者（x，－1）了。

        那么y预测函数struct跟踪算法怎么获得呢？这就需要用到结构输出svm方法了（svm基本概念学习可参考我上篇文章中给出的svm三重境界的链接）,它在该算法中引入了一个判别函数struct跟踪算法,通过公式struct跟踪算法找到概率最大的struct跟踪算法对目标位置进行预测，也就是说，因为我们还不知道当前帧的目标位置,那么我们首先想到在上一帧中的目标能够通过一些位置变化关系，出现在当前帧中的各处，但是呢，实际的目标只有一个，所以这些变换关系中也必然只有一个是最佳的，因此，我们需要找到这个最佳的，并通过struct跟踪算法，就可以成功找到目标啦～，至于搜寻空间struct跟踪算法如何取，在程序解读时大家就会看到了。

       那么如何找到struct跟踪算法呢？我个人理解是：将判别函数形式转换为：struct跟踪算法，其中，struct跟踪算法表示映射函数，是从输入空间到某个特征空间的映射，进而实现对样本线性可分。因为当分类平面(输入空间中的超平面)离数据点的“间隔”越大，分类的确信度越大，所以需让所选择的分类平面最大化这个“间隔”值，这里我们通过最小化凸目标函数struct跟踪算法来实现，该函数应满足条件：struct跟踪算法和struct跟踪算法，其中，struct跟踪算法，struct跟踪算法（struct跟踪算法表示两个框之间的覆盖率）。优化的目的是确保F(目标)>>F(非目标)。
        
       接下来问题又来了，如何获得最小的w？？文中采取的求解方式是利用拉格朗日对偶性，通过求解与原问题等价的对偶问题(dual problem),得到原始问题的最优解。通过给每一个约束条件加上一个拉格朗日乘子alpha，定义拉格朗日函数L(w,b,alpha)。一般对偶问题的求解过程如下：1）固定alpha，求L关于w，b的最小化。2）求L对alpha的极大。3）利用SMO算法求得拉格朗日乘子alpha。为了简化对偶问题求解，这里定义了参数beta，可见论文中的Eq.(8)。

算法主要流程：

1.   首先读入config.txt，初始化程序参数，这一过程主要由Config类实现；


2.   判断是否使用摄像头进行跟踪，如使用摄像头进行跟踪，则initBB=(120,80,80,80)；

      若使用视频序列进行跟踪，initBB由相应txt文件给出；


3.   将读入的每帧图像统一为320*240。


4.   由当前第一帧以及框initBB,实现对跟踪算法的初始化。


4.1   Initialise(frame,bb)

        由于我们之前获取的initBB的坐标定义为float型，在这里首先将其转换为int型。
        程序中选取haar特征，gaussian核函数, 初始化参数m_needsIntegralImage=true,m_needsIntegralHist=false。因此在这里，ImageRep image()主要实现了积分图的计算（如果特征为histogram，则可实现积分直方图的计算）。ImageRep类中的类成员包括frame，积分图，积分直方图。

4.2   UpdateLearner(image)

       该函数主要实现对预测函数的更新，首先通过RadialSamples()获得5*16=80个样本，再加上原始目标，总共含有81个样本。之后判断这81个样本是否有超出图像边界的，超出的舍弃。将剩余的样本存入keptRects,其中，原始目标样本存入keptRects[0]。定义一个多样本类MultiSample，该类中的类成员主要包括样本框以及ImageRep image。并通过Update(sample,0)来实现预测函数的更新。

4.3 Update(sample,0)

       该函数定义在LaRank类下，文章中参考文献《Solving multiclass support vector machines with LaRank》提到了这种算法。当我们分析LaRank头文件时，可看到struck算法重要步骤全部聚集在这个类中。该类中的类成员包括支持模式SupportPattern，支持向量SupportVector，Config类对象m_config，Features类对象m_features，Kernel类对象m_kernel，存放SupportPattern的m_sps，存放SupportVector的m_svs，用于显示的m_debugImage，目标函数中的系数m_C,矩阵m_K。

       查看SupportPattern的定义，我们知道该结构主要包括x(存放特征值),yv(struct跟踪算法，存放目标变化关系),images(存放图片样本),y(索引值，表明指定样本存放位置),refCount(统计sv的个数？？)。同样，查看SupportVector的定义可知，该结构包括一个SupportPattern，y(索引值，表明指定样本存放位置)，b(beta)，g(gradient)，image(存放图片样本)。

       在函数Update(sample,0)中，定义了一个SupportPattern＊ sp。首先对于每个样本框，其x，y坐标分别减去原始目标框的x，y坐标，将结果存入sp->yv。然后对于每个样本框内的图片统一尺寸为30*30，并存入sp->images。对于每个样本框，计算其haar特征值，并存入sp->x。令sp->y=y＝0，sp->refCount=0，最后将当前sp存入m_sps。


4.3.1  ProcessNew(int ind)

       之后执行ProcessNew(int ind),其中ind＝m_sps.size()-1。由于每处理一帧图像，m_sps的数量都增加1，这样定义ind能够保证ProcessNew所处理的样本都是最新的样本。在ProcessNew处理之前，首先看函数AddSupportVector(SupportPattern* x,int y,double g)的定义：
         SupportVector* sv=new SupportVector;定义了一个支持向量。
       为支持向量赋初值:sv->b=0.0，sv->x=x，sv->y=y，sv->g=g，并将该向量存入m_svs。接下来通过调用Kernel类中的Eval()函数更新核矩阵，即m_K，以后用于Algorithm 1计算。

现在再回到ProcessNew函数：
       第一个AddSupportVector(),将目标框作为参数,增加一个支持向量存入m_svs,此时,m_svs.size()=1,m_K(0,0)=1.0,函数返回ip＝0。
         之后执行MinGradiernt(int ind),求得公式10中的g最小值。返回最小梯度的数值以及对应的样本框存放位置。
         第二个AddSupportVector()，将具有最小梯度的样本框作为参数，增加一个特征向量存入m_svs，此时，m_svs.size()=2,并求得m_K(0,1),m_K(1,0),m_K(1,1)。函数返回in=1。
之后进行SMO算法进行计算，若某向量的beta值为0，则舍弃该支持向量。


4.3.2  BudgetMaintenance()

       再之后执行函数BudgetMaintenance(),保证支持向量个数没有超过100。


4.3.3  Reprocess()

       进行Reprocess()步骤，一个Reprocess()包括1个ProcessOld()和10个Optimize();

       ProcessOld()主要对已经存在的SupportPattern进行随机选取并处理。和ProcessNew不同的地方是，这里将满足梯度最大以及满足struct跟踪算法的支持向量作为正支持向量。负支持向量依然根据梯度最小进行选取。之后再次执行SMO算法，判断这些支持向量是否有效。

       Optimize()也是对已经存在的SupportPattern进行随机选取并处理，但仅仅是对现有的支持向量的beta值进行调整，并不加入新的支持向量。正负支持向量的选取方式和ProcessOld()一样。


4.3.4  BudgetMaintenance()

       执行函数BudgetMaintenance(),保证支持向量个数没有超过100。

5.跟踪模块(Algorithm 2)

       首先通过ImageRep image()实现积分图的计算，然后进行抽样(这里抽样的结果和初始化时的抽样结果不一样，大概抽取几千个样本)。将超出图像范围的框舍弃，剩余的保留在keptRects中。对keptRects中的每一个框，计算F函数，即struct跟踪算法，将结果保存在scores里，并记录值最大的那一个，将其作为跟踪结果。  UpdateDebugImage()函数主要实现程序运行时显示的界面。UpdateLearner(image)同步骤4一致。

6.Debug()   显示样本图像，绿色边框的是正样本，红色边框的负样本。

第三部分 代码

main.cpp
[cpp] view plain copy
  1. /*  
  2. * Struck: Structured Output Tracking with Kernels 
  3. *  
  4. * Code to accompany the paper: 
  5. *   Struck: Structured Output Tracking with Kernels 
  6. *   Sam Hare, Amir Saffari, Philip H. S. Torr 
  7. *   International Conference on Computer Vision (ICCV), 2011 
  8. *  
  9. * Copyright (C) 2011 Sam Hare, Oxford Brookes University, Oxford, UK 
  10. *  
  11. * This file is part of Struck. 
  12. *  
  13. * Struck is free software: you can redistribute it and/or modify 
  14. * it under the terms of the GNU General Public License as published by 
  15. * the Free Software Foundation, either version 3 of the License, or 
  16. * (at your option) any later version. 
  17. *  
  18. * Struck is distributed in the hope that it will be useful, 
  19. * but WITHOUT ANY WARRANTY; without even the implied warranty of 
  20. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the 
  21. * GNU General Public License for more details. 
  22. *  
  23. * You should have received a copy of the GNU General Public License 
  24. * along with Struck.  If not, see <http://www.gnu.org/licenses/>. 
  25. *  
  26. */  
  27.   
  28. #include "Tracker.h"  
  29. #include "Config.h"  
  30.   
  31. #include <iostream>  
  32. #include <fstream>  
  33.   
  34. #include <opencv/cv.h>  
  35. #include <opencv/highgui.h>  
  36.   
  37. #include "vot.hpp"  
  38.   
  39. using namespace std;  
  40. using namespace cv;  
  41.   
  42. static const int kLiveBoxWidth = 80;         
  43. static const int kLiveBoxHeight = 80;        
  44.   
  45. void rectangle(Mat& rMat, const FloatRect& rRect, const Scalar& rColour)  
  46. {  
  47.     IntRect r(rRect);  
  48.     rectangle(rMat, Point(r.XMin(), r.YMin()), Point(r.XMax(), r.YMax()), rColour);  
  49. }  
  50.   
  51. int main(int argc, char* argv[])  
  52. {  
  53.     // 读取文件对程序参数进行初始化  
  54.     string configPath = "config.txt";  
  55.     if (argc > 1)  
  56.     {  
  57.         configPath = argv[1];  
  58.     }  
  59.     Config conf(configPath);       //Config类主要读取config.txt中的参数  
  60.   
  61.     if (conf.features.size() == 0)  
  62.     {  
  63.         cout << "error: no features specified in config" << endl;  
  64.         return EXIT_FAILURE;  
  65.     }  
  66.   
  67.     Tracker tracker(conf);     
  68.   
  69.     //Check if --challenge was passed as an argument  
  70.     bool challengeMode = false;  
  71.     for (int i = 1; i < argc; i++) {  
  72.         if (strcmp("--challenge", argv[i]) == 0) {        //判断是否有挑战模式（vot挑战）  
  73.             challengeMode = true;  
  74.         }  
  75.     }  
  76.   
  77.     if (challengeMode) {    //VOT(Visual object tracking)挑战，它提供了一个公共平台，目标是比较各种跟踪算法再短期跟踪内的性能，讨论视觉跟踪领域的发展。  
  78.         //load region, images and prepare for output  
  79.         Mat frameOrig;  
  80.         Mat frame;  
  81.         VOT vot_io("region.txt", "images.txt", "output.txt");  
  82.         vot_io.getNextImage(frameOrig);  
  83.         resize(frameOrig, frame, Size(conf.frameWidth, conf.frameHeight));  
  84.         cv::Rect initPos = vot_io.getInitRectangle();  
  85.         vot_io.outputBoundingBox(initPos);  
  86.         float scaleW = (float)conf.frameWidth/frameOrig.cols;  
  87.         float scaleH = (float)conf.frameHeight/frameOrig.rows;  
  88.   
  89.         FloatRect initBB_vot = FloatRect(initPos.x*scaleW, initPos.y*scaleH, initPos.width*scaleW, initPos.height*scaleH);  
  90.         tracker.Initialise(frame, initBB_vot);  
  91.   
  92.         while (vot_io.getNextImage(frameOrig) == 1){  
  93.             resize(frameOrig, frame, Size(conf.frameWidth, conf.frameHeight));  
  94.   
  95.             tracker.Track(frame);  
  96.             const FloatRect& bb = tracker.GetBB();  
  97.             float x = bb.XMin()/scaleW;  
  98.             float y = bb.YMin()/scaleH;  
  99.             float w = bb.Width()/scaleW;  
  100.             float h = bb.Height()/scaleH;  
  101.   
  102.             cv::Rect output = cv::Rect(x,y,w,h);  
  103.   
  104.             vot_io.outputBoundingBox(output);  
  105.         }  
  106.   
  107.         return 0;  
  108.     }  
  109.   
  110.       
  111.     ofstream outFile;  
  112.     if (conf.resultsPath != "")  
  113.     {  
  114.         outFile.open(conf.resultsPath.c_str(), ios::out);    //将程序写入resultpath  
  115.         if (!outFile)  
  116.         {  
  117.             cout << "error: could not open results file: " << conf.resultsPath << endl;  
  118.             return EXIT_FAILURE;  
  119.         }  
  120.     }  
  121.   
  122.     // if no sequence specified then use the camera  
  123.     bool useCamera = (conf.sequenceName == "");  
  124.   
  125.     VideoCapture cap;  
  126.   
  127.     int startFrame = -1;  
  128.     int endFrame = -1;  
  129.     FloatRect initBB;  
  130.     string imgFormat;  
  131.     float scaleW = 1.f;  
  132.     float scaleH = 1.f;  
  133.   
  134.     if (useCamera)  
  135.     {  
  136.         if (!cap.open(0))  
  137.         {  
  138.             cout << "error: could not start camera capture" << endl;  
  139.             return EXIT_FAILURE;  
  140.         }  
  141.         startFrame = 0;  
  142.         endFrame = INT_MAX;        /* maximum (signed) int value */  
  143.         Mat tmp;  
  144.         cap >> tmp;  
  145.         scaleW = (float)conf.frameWidth/tmp.cols;  
  146.         scaleH = (float)conf.frameHeight/tmp.rows;  
  147.   
  148.         initBB = IntRect(conf.frameWidth/2-kLiveBoxWidth/2, conf.frameHeight/2-kLiveBoxHeight/2, kLiveBoxWidth, kLiveBoxHeight);  
  149.         cout << "press 'i' to initialise tracker" << endl;  
  150.     }  
  151.     else  
  152.     {  
  153.         // parse frames file  
  154.         string framesFilePath = conf.sequenceBasePath+"/"+conf.sequenceName+"/"+conf.sequenceName+"_frames.txt";  //girl_frames.txt的文件路径，该文件放在girl文件夹里，内容为0，501。  
  155.         ifstream framesFile(framesFilePath.c_str(), ios::in);     
  156.         if (!framesFile)  
  157.         {  
  158.             cout << "error: could not open sequence frames file: " << framesFilePath << endl;  
  159.             return EXIT_FAILURE;  
  160.         }  
  161.       
  162.         string framesLine;  
  163.         getline(framesFile, framesLine);  
  164.         sscanf(framesLine.c_str(), "%d,%d", &startFrame, &endFrame);   //startFrame=0；endFrame=501；  
  165.   
  166.         if (framesFile.fail() || startFrame == -1 || endFrame == -1)     
  167.         {  
  168.             cout << "error: could not parse sequence frames file" << endl;  
  169.             return EXIT_FAILURE;  
  170.         }  
  171.   
  172.         imgFormat = conf.sequenceBasePath+"/"+conf.sequenceName+"/imgs/img%05d.png";  
  173.   
  174.         // read first frame to get size  
  175.         char imgPath[256];  
  176.         sprintf(imgPath, imgFormat.c_str(), startFrame);  //sprintf把格式化的数据写入某个字符串缓冲区(imgPath);  
  177.         Mat tmp = cv::imread(imgPath, 0);  
  178.         scaleW = (float)conf.frameWidth/tmp.cols;   //=1;  
  179.         scaleH = (float)conf.frameHeight/tmp.rows; //=1;  
  180.   
  181.         // read init box from ground truth file  
  182.         string gtFilePath = conf.sequenceBasePath+"/"+conf.sequenceName+"/"+conf.sequenceName+"_gt.txt";  //读取girl_gt.txt文件  
  183.         ifstream gtFile(gtFilePath.c_str(), ios::in);  
  184.         if (!gtFile)  
  185.         {  
  186.             cout << "error: could not open sequence gt file: " << gtFilePath << endl;  
  187.             return EXIT_FAILURE;  
  188.         }  
  189.   
  190.       
  191.         string gtLine;  
  192.         getline(gtFile, gtLine);  
  193.         float xmin = -1.f;  
  194.         float ymin = -1.f;  
  195.         float width = -1.f;  
  196.         float height = -1.f;  
  197.         sscanf(gtLine.c_str(), "%f,%f,%f,%f", &xmin, &ymin, &width, &height);  //128,46,104,127  
  198.   
  199.         if (gtFile.fail() || xmin < 0.f || ymin < 0.f || width < 0.f || height < 0.f)  
  200.         {  
  201.             cout << "error: could not parse sequence gt file" << endl;  
  202.             return EXIT_FAILURE;  
  203.         }  
  204.         initBB = FloatRect(xmin*scaleW, ymin*scaleH, width*scaleW, height*scaleH);  
  205.     }  
  206.   
  207.     if (!conf.quietMode)  
  208.     {  
  209.         namedWindow("result");  
  210.     }  
  211.   
  212.     Mat result(conf.frameHeight, conf.frameWidth, CV_8UC3);  
  213.     bool paused = false;  
  214.     bool doInitialise = false;  
  215.     srand(conf.seed);  
  216.   
  217.     for (int frameInd = startFrame; frameInd <= endFrame; ++frameInd)    //逐帧处理  
  218.     {  
  219.         Mat frame;  
  220.         if (useCamera)   //若使用摄像头  
  221.         {  
  222.             Mat frameOrig;  
  223.             cap >> frameOrig;  
  224.             resize(frameOrig, frame, Size(conf.frameWidth, conf.frameHeight));  
  225.             flip(frame, frame, 1);  
  226.             frame.copyTo(result);  
  227.             if (doInitialise)  
  228.             {  
  229.                 if (tracker.IsInitialised())  
  230.                 {  
  231.                     tracker.Reset();  
  232.                 }  
  233.                 else  
  234.                 {  
  235.                     tracker.Initialise(frame, initBB);  
  236.                 }  
  237.                 doInitialise = false;  
  238.             }  
  239.             else if (!tracker.IsInitialised())  
  240.             {  
  241.                 rectangle(result, initBB, CV_RGB(255, 255, 255));  
  242.             }  
  243.         }  
  244.         else    //若读取图片序列  
  245.         {             
  246.             char imgPath[256];  
  247.             sprintf(imgPath, imgFormat.c_str(), frameInd);  
  248.             Mat frameOrig = cv::imread(imgPath, 0);  
  249.             if (frameOrig.empty())  
  250.             {  
  251.                 cout << "error: could not read frame: " << imgPath << endl;  
  252.                 return EXIT_FAILURE;  
  253.             }  
  254.   
  255.             resize(frameOrig, frame, Size(conf.frameWidth, conf.frameHeight));  //将读取的每帧图像统一为320*240;  
  256.             cvtColor(frame, result, CV_GRAY2RGB);  
  257.                           
  258.                                                     if (frameInd == startFrame)  
  259.             {  
  260.                 tracker.Initialise(frame, initBB);                 //对第一帧进行初始化  
  261.             }  
  262.         }  
  263.   
  264.         if (tracker.IsInitialised())   
  265.         {  
  266.             tracker.Track(frame);                     //开始跟踪  
  267.   
  268.             if (!conf.quietMode && conf.debugMode)  
  269.             {  
  270.                 tracker.Debug();  //用于显示样本图像  
  271.             }  
  272.   
  273.             rectangle(result, tracker.GetBB(), CV_RGB(0, 255, 0));  
  274.   
  275.             if (outFile)  
  276.             {  
  277.                 const FloatRect& bb = tracker.GetBB();  
  278.                 outFile << bb.XMin()/scaleW << "," << bb.YMin()/scaleH << "," << bb.Width()/scaleW << "," << bb.Height()/scaleH << endl;  
  279.             }   //输出跟踪结果坐标  
  280.         }  
  281.   
  282.         if (!conf.quietMode)  
  283.         {  
  284.             imshow("result", result);   //显示跟踪画面  
  285.             int key = waitKey(paused ? 0 : 1);  
  286.   
  287.             if (key != -1)  
  288.             {  
  289.                 if (key == 27 || key == 113) // esc q  
  290.                 {  
  291.                     break;  
  292.                 }  
  293.                 else if (key == 112) // p  
  294.                 {  
  295.                     paused = !paused;  
  296.                 }  
  297.                 else if (key == 105 && useCamera)  
  298.                 {  
  299.                     doInitialise = true;  
  300.                 }  
  301.             }  
  302.             if (conf.debugMode && frameInd == endFrame)  
  303.             {  
  304.                 cout << "\n\nend of sequence, press any key to exit" << endl;  
  305.                 waitKey();  
  306.             }  
  307.         }  
  308.     }  
  309.   
  310.     if (outFile.is_open())  
  311.     {  
  312.         outFile.close();  
  313.     }  
  314.   
  315.     return EXIT_SUCCESS;  
  316. }  


Tracker.cpp
[cpp] view plain copy
  1. #include "Tracker.h"  
  2. #include "Config.h"  
  3. #include "ImageRep.h"  
  4. #include "Sampler.h"  
  5. #include "Sample.h"  
  6. #include "GraphUtils/GraphUtils.h"  
  7.   
  8. #include "HaarFeatures.h"  
  9. #include "RawFeatures.h"  
  10. #include "HistogramFeatures.h"  
  11. #include "MultiFeatures.h"  
  12.   
  13. #include "Kernels.h"  
  14.   
  15. #include "LaRank.h"  
  16.   
  17. #include <opencv/cv.h>  
  18. #include <opencv/highgui.h>  
  19.   
  20. #include <Eigen/Core>  
  21.   
  22. #include <vector>  
  23. #include <algorithm>  
  24.   
  25. using namespace cv;  
  26. using namespace std;  
  27. using namespace Eigen;  
  28.   
  29. Tracker::Tracker(const Config& conf) :      //构造函数，对参数进行初始化  
  30.     m_config(conf),  
  31.     m_initialised(false),  
  32.     m_pLearner(0),  
  33.     m_debugImage(2*conf.searchRadius+1, 2*conf.searchRadius+1, CV_32FC1),  
  34.     m_needsIntegralImage(false)  
  35. {  
  36.     Reset();  
  37. }  
  38.   
  39. Tracker::~Tracker()  
  40. {  
  41.     delete m_pLearner;  
  42.     for (int i = 0; i < (int)m_features.size(); ++i)  
  43.     {  
  44.         delete m_features[i];  
  45.         delete m_kernels[i];  
  46.     }  
  47. }  
  48.   
  49. void Tracker::Reset()               //因为初始化为haar特征核高斯核函数，所以m_needsIntegralImage = true，m_needsIntegralHist = false;  
  50. {  
  51.     m_initialised = false;  
  52.     m_debugImage.setTo(0);  
  53.     if (m_pLearner) delete m_pLearner;  
  54.     for (int i = 0; i < (int)m_features.size(); ++i)  
  55.     {  
  56.         delete m_features[i];  
  57.         delete m_kernels[i];  
  58.     }  
  59.     m_features.clear();  
  60.     m_kernels.clear();  
  61.       
  62.     m_needsIntegralImage = false;  
  63.     m_needsIntegralHist = false;  
  64.       
  65.     int numFeatures = m_config.features.size();  
  66.     vector<int> featureCounts;  
  67.     for (int i = 0; i < numFeatures; ++i)  
  68.     {  
  69.         switch (m_config.features[i].feature)  
  70.         {  
  71.         case Config::kFeatureTypeHaar:  
  72.             m_features.push_back(new HaarFeatures(m_config));  
  73.             m_needsIntegralImage = true;  
  74.             break;            
  75.         case Config::kFeatureTypeRaw:  
  76.             m_features.push_back(new RawFeatures(m_config));  
  77.             break;  
  78.         case Config::kFeatureTypeHistogram:  
  79.             m_features.push_back(new HistogramFeatures(m_config));  
  80.             m_needsIntegralHist = true;  
  81.             break;  
  82.         }  
  83.         featureCounts.push_back(m_features.back()->GetCount());  
  84.           
  85.         switch (m_config.features[i].kernel)  
  86.         {  
  87.         case Config::kKernelTypeLinear:  
  88.             m_kernels.push_back(new LinearKernel());  
  89.             break;  
  90.         case Config::kKernelTypeGaussian:  
  91.             m_kernels.push_back(new GaussianKernel(m_config.features[i].params[0]));  
  92.             break;  
  93.         case Config::kKernelTypeIntersection:  
  94.             m_kernels.push_back(new IntersectionKernel());  
  95.             break;  
  96.         case Config::kKernelTypeChi2:  
  97.             m_kernels.push_back(new Chi2Kernel());  
  98.             break;  
  99.         }  
  100.     }  
  101.       
  102.     if (numFeatures > 1)  
  103.     {  
  104.         MultiFeatures* f = new MultiFeatures(m_features);  
  105.         m_features.push_back(f);  
  106.           
  107.         MultiKernel* k = new MultiKernel(m_kernels, featureCounts);  
  108.         m_kernels.push_back(k);       
  109.     }  
  110.       
  111.     m_pLearner = new LaRank(m_config, *m_features.back(), *m_kernels.back());  
  112. }  
  113.       
  114.   
  115. void Tracker::Initialise(const cv::Mat& frame, FloatRect bb)  
  116. {  
  117.     m_bb = IntRect(bb);//将目标框坐标转为int型  
  118.     //该类主要实现了积分图计算  
  119.     ImageRep image(frame, m_needsIntegralImage, m_needsIntegralHist);  //后两个参数分别为true，false  
  120.     for (int i = 0; i < 1; ++i)  
  121.     {  
  122.         UpdateLearner(image);// 更新预测函数  
  123.     }  
  124.     m_initialised = true;  
  125. }  
  126.   
  127. void Tracker::Track(const cv::Mat& frame)  
  128. {  
  129.     assert(m_initialised);  
  130.       
  131.     ImageRep image(frame, m_needsIntegralImage, m_needsIntegralHist);   //获得当前帧的积分图  
  132.       
  133.     vector<FloatRect> rects = Sampler::PixelSamples(m_bb, m_config.searchRadius);  //抽样  
  134.       
  135.     vector<FloatRect> keptRects;  
  136.     keptRects.reserve(rects.size());  
  137.     for (int i = 0; i < (int)rects.size(); ++i)  
  138.     {  
  139.         if (!rects[i].IsInside(image.GetRect())) continue;  
  140.         keptRects.push_back(rects[i]);        //将超出图像范围的框舍弃，剩余的保留在keptRects中  
  141.     }  
  142.       
  143.     MultiSample sample(image, keptRects);     //多样本类，主要包括样本框以及ImageRep image  
  144.       
  145.     vector<double> scores;  
  146.     m_pLearner->Eval(sample, scores);     //scores里存放的是论文中公式（10）后半部分  
  147.       
  148.     double bestScore = -DBL_MAX;  
  149.     int bestInd = -1;  
  150.     for (int i = 0; i < (int)keptRects.size(); ++i)  
  151.     {         
  152.         if (scores[i] > bestScore)  
  153.         {  
  154.             bestScore = scores[i];  
  155.             bestInd = i;              //找到bestScore  
  156.         }  
  157.     }  
  158.       
  159.     UpdateDebugImage(keptRects, m_bb, scores);//更新debug图像，用于显示  
  160.       
  161.     if (bestInd != -1)  
  162.     {  
  163.         m_bb = keptRects[bestInd];  
  164.         UpdateLearner(image);  
  165. #if VERBOSE       
  166.         cout << "track score: " << bestScore << endl;  
  167. #endif  
  168.     }  
  169. }  
  170.   
  171. void Tracker::UpdateDebugImage(const vector<FloatRect>& samples, const FloatRect& centre, const vector<double>& scores)  
  172. {  
  173.     double mn = VectorXd::Map(&scores[0], scores.size()).minCoeff();   //Map:将现存的结构映射到Eigen的数据结构里，进行计算  
  174.     double mx = VectorXd::Map(&scores[0], scores.size()).maxCoeff();   //R.minCoeff()=min(R(:)), R.maxCoeff()=max(R(:));  
  175.     m_debugImage.setTo(0);     //置为全黑色  
  176.     for (int i = 0; i < (int)samples.size(); ++i)  
  177.     {  
  178.         int x = (int)(samples[i].XMin() - centre.XMin());  
  179.         int y = (int)(samples[i].YMin() - centre.YMin());  
  180.         m_debugImage.at<float>(m_config.searchRadius+y,m_config.searchRadius+x)=(float)((scores[i]-mn)/(mx-mn));//scores得分越大的框，会在m_debugImage上具有越大的值，即该点越亮（类似于置信图）  
  181.     }  
  182. }  
  183.   
  184. void Tracker::Debug()  
  185. {  
  186.     imshow("tracker", m_debugImage);   //显示m_debugImage图像  
  187.     m_pLearner->Debug();  
  188. }  
  189.   
  190. void Tracker::UpdateLearner(const ImageRep& image)     //更新预测函数  
  191. {  
  192.     // note these return the centre sample at index 0  
  193.     vector<FloatRect> rects = Sampler::RadialSamples(m_bb, 2*m_config.searchRadius, 5, 16);//5*16=80,加上一个原始rect，共包含81个rect  
  194.     //vector<FloatRect> rects = Sampler::PixelSamples(m_bb, 2*m_config.searchRadius, true);  
  195.       
  196.     vector<FloatRect> keptRects;  
  197.     keptRects.push_back(rects[0]); // 原始目标框  
  198.     for (int i = 1; i < (int)rects.size(); ++i)  
  199.     {  
  200.         if (!rects[i].IsInside(image.GetRect())) continue;   //判断生成的样本框是否超出图像范围，超出的舍弃  
  201.         keptRects.push_back(rects[i]);  
  202.     }  
  203.           
  204. #if VERBOSE       
  205.     cout << keptRects.size() << " samples" << endl;  
  206. #endif  
  207.           
  208.     MultiSample sample(image, keptRects);      //多样本类对象sample，包含ImageRep& image，以及保留下来样本框  
  209.     m_pLearner->Update(sample, 0);       //更新，在LaRank类下实现  
  210. }  

LaRank.h

[cpp] view plain copy
  1. #ifndef LARANK_H  
  2. #define LARANK_H  
  3.   
  4. #include "Rect.h"  
  5. #include "Sample.h"  
  6.   
  7. #include <vector>  
  8. #include <Eigen/Core>  
  9.   
  10. #include <opencv/cv.h>  
  11.   
  12. class Config;  
  13. class Features;  
  14. class Kernel;  
  15.   
  16. class LaRank   //文献《Solving multiclass support vector machine with LaRank》，该类实现了struck算法的主要步骤  
  17. {  
  18. public:  
  19.     LaRank(const Config& conf, const Features& features, const Kernel& kernel);  //初始化参数，特征值，核  
  20.     ~LaRank();  
  21.       
  22.     virtual void Eval(const MultiSample& x, std::vector<double>& results);  
  23.     virtual void Update(const MultiSample& x, int y);  
  24.       
  25.     virtual void Debug();  
  26.   
  27. private:  
  28.   
  29.     struct SupportPattern  
  30.     {  
  31.         std::vector<Eigen::VectorXd> x;   //特征值  
  32.         std::vector<FloatRect> yv;        //变化关系  
  33.         std::vector<cv::Mat> images;      //图像片  
  34.         int y;                            //索引值  
  35.         int refCount;                    //统计sp的个数？  
  36.     };  
  37.   
  38.     struct SupportVector  
  39.     {  
  40.         SupportPattern* x;  
  41.         int y;  
  42.         double b;                //beta  
  43.         double g;                 //gradient  
  44.         cv::Mat image;  
  45.     };  
  46.       
  47.     const Config& m_config;  
  48.     const Features& m_features;  
  49.     const Kernel& m_kernel;  
  50.       
  51.     std::vector<SupportPattern*> m_sps;  
  52.     std::vector<SupportVector*> m_svs;  
  53.   
  54.     cv::Mat m_debugImage;  
  55.       
  56.     double m_C;  
  57.     Eigen::MatrixXd m_K;  
  58.   
  59.     inline double Loss(const FloatRect& y1, const FloatRect& y2) const         //损失函数  
  60.     {  
  61.         // overlap loss  
  62.         return 1.0-y1.Overlap(y2);  
  63.         // squared distance loss  
  64.         //double dx = y1.XMin()-y2.XMin();  
  65.         //double dy = y1.YMin()-y2.YMin();  
  66.         //return dx*dx+dy*dy;  
  67.     }  
  68.       
  69.     double ComputeDual() const;  
  70.   
  71.     void SMOStep(int ipos, int ineg);  
  72.     std::pair<int, double> MinGradient(int ind);  
  73.     void ProcessNew(int ind);  
  74.     void Reprocess();  
  75.     void ProcessOld();  
  76.     void Optimize();  
  77.   
  78.     int AddSupportVector(SupportPattern* x, int y, double g);  
  79.     void RemoveSupportVector(int ind);  
  80.     void RemoveSupportVectors(int ind1, int ind2);  
  81.     void SwapSupportVectors(int ind1, int ind2);  
  82.       
  83.     void BudgetMaintenance();  
  84.     void BudgetMaintenanceRemove();  
  85.   
  86.     double Evaluate(const Eigen::VectorXd& x, const FloatRect& y) const;  
  87.     void UpdateDebugImage();  
  88. };  
  89.   
  90. #endif  

LaRank.cpp

[cpp] view plain copy
  1. #include "LaRank.h"  
  2.   
  3. #include "Config.h"  
  4. #include "Features.h"  
  5. #include "Kernels.h"  
  6. #include "Sample.h"  
  7. #include "Rect.h"  
  8. #include "GraphUtils/GraphUtils.h"  
  9.   
  10. #include <Eigen/Array>  
  11.   
  12. #include <opencv/highgui.h>  
  13. static const int kTileSize = 30;  
  14. using namespace cv;  
  15.   
  16. using namespace std;  
  17. using namespace Eigen;  
  18.   
  19. static const int kMaxSVs = 2000; // TODO (only used when no budget)  
  20.   
  21.   
  22. LaRank::LaRank(const Config& conf, const Features& features, const Kernel& kernel) :  
  23.     m_config(conf),  
  24.     m_features(features),  
  25.     m_kernel(kernel),  
  26.     m_C(conf.svmC)  
  27. {  
  28.     int N = conf.svmBudgetSize > 0 ? conf.svmBudgetSize+2 : kMaxSVs;     //N=100+2，特征向量的个数不能超过这个阈值  
  29.     m_K = MatrixXd::Zero(N, N);            //m_K表示核矩阵，102*102  
  30.     m_debugImage = Mat(800, 600, CV_8UC3);  
  31. }  
  32.   
  33. LaRank::~LaRank()  
  34. {  
  35. }  
  36.   
  37. double LaRank::Evaluate(const Eigen::VectorXd& x, const FloatRect& y) const  //论文中公式10后半部分计算，即F  
  38. {  
  39.     double f = 0.0;  
  40.     for (int i = 0; i < (int)m_svs.size(); ++i)  
  41.     {  
  42.         const SupportVector& sv = *m_svs[i];  
  43.         f += sv.b*m_kernel.Eval(x, sv.x->x[sv.y]);       //beta*高斯核  
  44.     }  
  45.     return f;  
  46. }  
  47.   
  48. void LaRank::Eval(const MultiSample& sample, std::vector<double>& results)  
  49. {  
  50.     const FloatRect& centre(sample.GetRects()[0]);       //原始目标框  
  51.     vector<VectorXd> fvs;  
  52.     const_cast<Features&>(m_features).Eval(sample, fvs);     //fvs存放haar特征值  
  53.     results.resize(fvs.size());  
  54.     for (int i = 0; i < (int)fvs.size(); ++i)  
  55.     {  
  56.         // express y in coord frame of centre sample  
  57.         FloatRect y(sample.GetRects()[i]);  
  58.         y.Translate(-centre.XMin(), -centre.YMin());     //将每个框的横纵坐标分别减去原始目标框的横纵坐标  
  59.         results[i] = Evaluate(fvs[i], y);         //计算每个框的F函数，结果保存在results中。  
  60.     }  
  61. }  
  62.   
  63. void LaRank::Update(const MultiSample& sample, int y)  
  64. {  
  65.     // add new support pattern  
  66.     SupportPattern* sp = new SupportPattern;        //定义一个sp  
  67.     const vector<FloatRect>& rects = sample.GetRects();      //获得所有的样本框  
  68.     FloatRect centre = rects[y];                     //原始目标框  
  69.     for (int i = 0; i < (int)rects.size(); ++i)  
  70.     {  
  71.         // express r in coord frame of centre sample  
  72.         FloatRect r = rects[i];  
  73.         r.Translate(-centre.XMin(), -centre.YMin());   //这就表示帧间目标位置变化关系  
  74.         sp->yv.push_back(r);  
  75.         if (!m_config.quietMode && m_config.debugMode)  
  76.         {  
  77.             // store a thumbnail for each sample  
  78.             Mat im(kTileSize, kTileSize, CV_8UC1);  
  79.             IntRect rect = rects[i];  
  80.             cv::Rect roi(rect.XMin(), rect.YMin(), rect.Width(), rect.Height());  //感兴趣的区域是那些抽取的样本区域  
  81.             cv::resize(sample.GetImage().GetImage(0)(roi), im, im.size());       //0表示通道数，将感兴趣区域统一为30*30，并保存在sp里的images  
  82.             sp->images.push_back(im);  
  83.         }  
  84.     }  
  85.     // evaluate features for each sample  
  86.     sp->x.resize(rects.size());    //有多少个感兴趣的框，就有多少个特征值向量。  
  87.     const_cast<Features&>(m_features).Eval(sample, sp->x);    //将每个样本框计算得到的haar特征存入sp->x，这里关于haar特征的代码不再列出，我将代码提取出来单独写出一篇博客《http://blog.****.net/qianxin_dh/article/details/39268113》  
  88.     sp->y = y;  
  89.     sp->refCount = 0;  
  90.     m_sps.push_back(sp);   //存储sp  
  91.   
  92.     ProcessNew((int)m_sps.size()-1);  //执行该步骤，添加支持向量，并对beta值进行调整  
  93.     BudgetMaintenance();       //保证支持向量没有超出限定阈值  
  94.       
  95.     for (int i = 0; i < 10; ++i)  
  96.     {  
  97.         Reprocess();           //包括processold：增加新的sv；optimize：在现有的sv基础上调整beta值  
  98.         BudgetMaintenance();  
  99.     }  
  100. }  
  101.   
  102. void LaRank::BudgetMaintenance()  
  103. {  
  104.     if (m_config.svmBudgetSize > 0)  
  105.     {  
  106.         while ((int)m_svs.size() > m_config.svmBudgetSize)  
  107.         {  
  108.             BudgetMaintenanceRemove();  //支持向量的个数超出阈值后，找到对于F函数影响最小的负sv，并移除。  
  109.         }  
  110.     }  
  111. }  
  112.   
  113. void LaRank::Reprocess()  
  114. {  
  115.     ProcessOld();       //每个processold步骤伴随着10个optimize步骤。  
  116.     for (int i = 0; i < 10; ++i)  
  117.     {  
  118.         Optimize();  
  119.     }  
  120. }  
  121.   
  122. double LaRank::ComputeDual() const  
  123. {  
  124.     double d = 0.0;  
  125.     for (int i = 0; i < (int)m_svs.size(); ++i)  
  126.     {  
  127.         const SupportVector* sv = m_svs[i];  
  128.         d -= sv->b*Loss(sv->x->yv[sv->y], sv->x->yv[sv->x->y]);  
  129.         for (int j = 0; j < (int)m_svs.size(); ++j)  
  130.         {  
  131.             d -= 0.5*sv->b*m_svs[j]->b*m_K(i,j);  
  132.         }  
  133.     }  
  134.     return d;  
  135. }  
  136.   
  137. void LaRank::SMOStep(int ipos, int ineg)  
  138. {  
  139.     if (ipos == ineg) return;  
  140.   
  141.     SupportVector* svp = m_svs[ipos];    //定义一个正支持向量  
  142.     SupportVector* svn = m_svs[ineg];    //定义一个负支持向量  
  143.     assert(svp->x == svn->x);  
  144.     SupportPattern* sp = svp->x;    //定义一个支持模式sp，将正支持向量的支持模式赋予sp  
  145.   
  146. #if VERBOSE  
  147.     cout << "SMO: gpos:" << svp->g << " gneg:" << svn->g << endl;  
  148. #endif    
  149.     if ((svp->g - svn->g) < 1e-5)  
  150.     {  
  151. #if VERBOSE  
  152.         cout << "SMO: skipping" << endl;  
  153. #endif        
  154.     }  
  155.     else  
  156.     {   //论文中的Algorithm步骤  
  157.         double kii = m_K(ipos, ipos) + m_K(ineg, ineg) - 2*m_K(ipos, ineg);  
  158.         double lu = (svp->g-svn->g)/kii;  
  159.         // no need to clamp against 0 since we'd have skipped in that case  
  160.         double l = min(lu, m_C*(int)(svp->y == sp->y) - svp->b);  
  161.   
  162.         svp->b += l;  
  163.         svn->b -= l;  
  164.   
  165.         // update gradients  
  166.         for (int i = 0; i < (int)m_svs.size(); ++i)  
  167.         {  
  168.             SupportVector* svi = m_svs[i];  
  169.             svi->g -= l*(m_K(i, ipos) - m_K(i, ineg));  
  170.         }  
  171. #if VERBOSE  
  172.         cout << "SMO: " << ipos << "," << ineg << " -- " << svp->b << "," << svn->b << " (" << l << ")" << endl;  
  173. #endif        
  174.     }  
  175.       
  176.     // check if we should remove either sv now  
  177.       
  178.     if (fabs(svp->b) < 1e-8)         //beta为0，该向量被移除  
  179.     {  
  180.         RemoveSupportVector(ipos);  
  181.         if (ineg == (int)m_svs.size())  
  182.         {  
  183.             // ineg and ipos will have been swapped during sv removal  
  184.             ineg = ipos;  
  185.         }  
  186.     }  
  187.   
  188.     if (fabs(svn->b) < 1e-8)  //beta＝0，该向量被移除  
  189.     {  
  190.         RemoveSupportVector(ineg);  
  191.     }  
  192. }  
  193.   
  194. pair<int, double> LaRank::MinGradient(int ind)  
  195. {  
  196.     const SupportPattern* sp = m_sps[ind];  
  197.     pair<int, double> minGrad(-1, DBL_MAX);  
  198.     for (int i = 0; i < (int)sp->yv.size(); ++i)  
  199.     {  
  200.         double grad = -Loss(sp->yv[i], sp->yv[sp->y]) - Evaluate(sp->x[i], sp->yv[i]);//通过公式10找到最小梯度对应的样本框  
  201.         if (grad < minGrad.second)  
  202.         {  
  203.             minGrad.first = i;  
  204.             minGrad.second = grad;  
  205.         }  
  206.     }  
  207.     return minGrad;  
  208. }  
  209.   
  210. void LaRank::ProcessNew(int ind)  //可以添加新的支持向量，增加的正负支持向量(sv)具有相同的支持模式(sp)  
  211. {  
  212.     // gradient is -f(x,y) since loss=0  
  213.     int ip = AddSupportVector(m_sps[ind], m_sps[ind]->y, -Evaluate(m_sps[ind]->x[m_sps[ind]->y],m_sps[ind]->yv[m_sps[ind]->y]));  //处理当前新样本，将上一帧目标位置作为正向量加入  
  214.   
  215.     pair<int, double> minGrad = MinGradient(ind);  //int，double分别是具有最小梯度的样本框存放的位置，最小梯度的数值  
  216.     int in = AddSupportVector(m_sps[ind], minGrad.first, minGrad.second);    //将当前具有最小梯度的样本作为负向量加入  
  217.   
  218.     SMOStep(ip, in);   //Algorithm 1,更新beta和gradient值  
  219. }  
  220.   
  221. void LaRank::ProcessOld()  //可以添加新的支持向量  
  222. {  
  223.     if (m_sps.size() == 0) return;  
  224.   
  225.     // choose pattern to process  
  226.     int ind = rand() % m_sps.size();   //随机选取sp  
  227.   
  228.     // find existing sv with largest grad and nonzero beta  
  229.     int ip = -1;  
  230.     double maxGrad = -DBL_MAX;  
  231.     for (int i = 0; i < (int)m_svs.size(); ++i)  
  232.     {  
  233.         if (m_svs[i]->x != m_sps[ind]) continue;  
  234.   
  235.         const SupportVector* svi = m_svs[i];  
  236.         if (svi->g > maxGrad && svi->b < m_C*(int)(svi->y == m_sps[ind]->y))   //找出符合该条件的，作为y＋，后一个条件保证了y+是从现存的sv中找出，因此不会增加新的向量  
  237.         {  
  238.             ip = i;  
  239.             maxGrad = svi->g;  
  240.         }  
  241.     }  
  242.     assert(ip != -1);  
  243.     if (ip == -1) return;  
  244.   
  245.     // find potentially new sv with smallest grad  
  246.     pair<int, double> minGrad = MinGradient(ind);  
  247.     int in = -1;  
  248.     for (int i = 0; i < (int)m_svs.size(); ++i)  
  249.     {  
  250.         if (m_svs[i]->x != m_sps[ind]) continue;              //找出满足该条件的，作为y－  
  251.   
  252.         if (m_svs[i]->y == minGrad.first)  
  253.         {  
  254.             in = i;  
  255.             break;  
  256.         }  
  257.     }  
  258.     if (in == -1)  
  259.     {  
  260.         // add new sv  
  261.         in = AddSupportVector(m_sps[ind], minGrad.first, minGrad.second);  //将该样本作为负sv加入  
  262.     }  
  263.   
  264.     SMOStep(ip, in);    //更新beta和gradient的值  
  265. }  
  266.   
  267. void LaRank::Optimize()    //  
  268. {  
  269.     if (m_sps.size() == 0) return;  
  270.       
  271.     // choose pattern to optimize  
  272.     int ind = rand() % m_sps.size();   //随机处理现存的sp  
  273.   
  274.     int ip = -1;  
  275.     int in = -1;  
  276.     double maxGrad = -DBL_MAX;  
  277.     double minGrad = DBL_MAX;  
  278.     for (int i = 0; i < (int)m_svs.size(); ++i)  
  279.     {  
  280.         if (m_svs[i]->x != m_sps[ind]) continue;  
  281.   
  282.         const SupportVector* svi = m_svs[i];  
  283.         if(svi->g>maxGrad&&svi->b<m_C*(int)(svi->y==m_sps->[y]))   //将满足该条件的作为y+  
  284.         {  
  285.             ip = i;  
  286.             maxGrad = svi->g;  
  287.         }  
  288.         if (svi->g < minGrad)                       //将满足该条件的作为y－  
  289.         {  
  290.             in = i;  
  291.             minGrad = svi->g;  
  292.         }  
  293.     }  
  294.     assert(ip != -1 && in != -1);  
  295.     if (ip == -1 || in == -1)  
  296.     {  
  297.         // this shouldn't happen  
  298.         cout << "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" << endl;  
  299.         return;  
  300.     }  
  301.   
  302.     SMOStep(ip, in);         //更新beta和gradient  
  303. }  
  304.   
  305. int LaRank::AddSupportVector(SupportPattern* x, int y, double g)  
  306. {  
  307.     SupportVector* sv = new SupportVector;  
  308.     sv->b = 0.0;        //beta初始化为0  
  309.     sv->x = x;  
  310.     sv->y = y;  
  311.     sv->g = g;  
  312.   
  313.     int ind = (int)m_svs.size();  
  314.     m_svs.push_back(sv);  
  315.     x->refCount++;  
  316.   
  317. #if VERBOSE  
  318.     cout << "Adding SV: " << ind << endl;  
  319. #endif  
  320.   
  321.     // update kernel matrix  
  322.     for (int i = 0; i < ind; ++i)    //计算核矩阵  
  323.     {  
  324.         m_K(i,ind) = m_kernel.Eval(m_svs[i]->x->x[m_svs[i]->y], x->x[y]);  
  325.         m_K(ind,i) = m_K(i,ind);  
  326.     }  
  327.     m_K(ind,ind) = m_kernel.Eval(x->x[y]);  
  328.   
  329.     return ind;  
  330. }  
  331.   
  332. void LaRank::SwapSupportVectors(int ind1, int ind2)  
  333. {  
  334.     SupportVector* tmp = m_svs[ind1];  
  335.     m_svs[ind1] = m_svs[ind2];  
  336.     m_svs[ind2] = tmp;  
  337.       
  338.     VectorXd row1 = m_K.row(ind1);  
  339.     m_K.row(ind1) = m_K.row(ind2);  
  340.     m_K.row(ind2) = row1;  
  341.       
  342.     VectorXd col1 = m_K.col(ind1);  
  343.     m_K.col(ind1) = m_K.col(ind2);  
  344.     m_K.col(ind2) = col1;  
  345. }  
  346.   
  347. void LaRank::RemoveSupportVector(int ind)  
  348. {  
  349. #if VERBOSE  
  350.     cout << "Removing SV: " << ind << endl;  
  351. #endif    
  352.   
  353.     m_svs[ind]->x->refCount--;  
  354.     if (m_svs[ind]->x->refCount == 0)  
  355.     {  
  356.         // also remove the support pattern  
  357.         for (int i = 0; i < (int)m_sps.size(); ++i)  
  358.         {  
  359.             if (m_sps[i] == m_svs[ind]->x)  
  360.             {  
  361.                 delete m_sps[i];  
  362.                 m_sps.erase(m_sps.begin()+i);  
  363.                 break;  
  364.             }  
  365.         }  
  366.     }  
  367.   
  368.     // make sure the support vector is at the back, this  
  369.     // lets us keep the kernel matrix cached and valid  
  370.     if (ind < (int)m_svs.size()-1)  
  371.     {  
  372.         SwapSupportVectors(ind, (int)m_svs.size()-1);  
  373.         ind = (int)m_svs.size()-1;  
  374.     }  
  375.     delete m_svs[ind];  
  376.     m_svs.pop_back();  
  377. }  
  378.   
  379. void LaRank::BudgetMaintenanceRemove()  
  380. {  
  381.     // find negative sv with smallest effect on discriminant function if removed  
  382.     double minVal = DBL_MAX;  
  383.     int in = -1;  
  384.     int ip = -1;  
  385.     for (int i = 0; i < (int)m_svs.size(); ++i)  
  386.     {  
  387.         if (m_svs[i]->b < 0.0)           //找到负sv  
  388.         {  
  389.             // find corresponding positive sv  
  390.             int j = -1;  
  391.             for (int k = 0; k < (int)m_svs.size(); ++k)  
  392.             {  
  393.                 if (m_svs[k]->b > 0.0 && m_svs[k]->x == m_svs[i]->x)   //找到同一支持模式下的正sv  
  394.                 {  
  395.                     j = k;  
  396.                     break;  
  397.                 }  
  398.             }  
  399.             double val = m_svs[i]->b*m_svs[i]->b*(m_K(i,i) + m_K(j,j) - 2.0*m_K(i,j));  
  400.             if (val < minVal)       　　//找到对F影响最小的sv  
  401.             {  
  402.                 minVal = val;  
  403.                 in = i;  
  404.                 ip = j;  
  405.             }  
  406.         }  
  407.     }  
  408.   
  409.     // adjust weight of positive sv to compensate for removal of negative  
  410.     m_svs[ip]->b += m_svs[in]->b;    //将负sv移除，其相应的beta值需补偿到正sv上。  
  411.   
  412.     // remove negative sv  
  413.     RemoveSupportVector(in);  
  414.     if (ip == (int)m_svs.size())  
  415.     {  
  416.         // ip and in will have been swapped during support vector removal  
  417.         ip = in;  
  418.     }  
  419.       
  420.     if (m_svs[ip]->b < 1e-8)     //beta值为0，移除该向量  
  421.     {  
  422.         // also remove positive sv  
  423.         RemoveSupportVector(ip);  
  424.     }  
  425.   
  426.     // update gradients  
  427.     // TODO: this could be made cheaper by just adjusting incrementally rather than recomputing  
  428.     for (int i = 0; i < (int)m_svs.size(); ++i)  
  429.     {  
  430.         SupportVector& svi = *m_svs[i];  
  431.         svi.g = -Loss(svi.x->yv[svi.y],svi.x->yv[svi.x->y]) - Evaluate(svi.x->x[svi.y], svi.x->yv[svi.y]);  
  432.     }     
  433. }  
  434.   
  435. void LaRank::Debug()  
  436. {  
  437.     cout << m_sps.size() << "/" << m_svs.size() << " support patterns/vectors" << endl;  
  438.     UpdateDebugImage();  
  439.     imshow("learner", m_debugImage);  
  440. }  
  441.   
  442. void LaRank::UpdateDebugImage()    //该函数主要用于样本显示，与算法关系不大，这里不做分析了  
  443. {  
  444.     m_debugImage.setTo(0);  
  445.       
  446.     int n = (int)m_svs.size();  
  447.       
  448.     if (n == 0) return;  
  449.       
  450.     const int kCanvasSize = 600;  
  451.     int gridSize = (int)sqrtf((float)(n-1)) + 1;  
  452.     int tileSize = (int)((float)kCanvasSize/gridSize);  
  453.       
  454.     if (tileSize < 5)  
  455.     {  
  456.         cout << "too many support vectors to display" << endl;  
  457.         return;  
  458.     }  
  459.       
  460.     Mat temp(tileSize, tileSize, CV_8UC1);  
  461.     int x = 0;  
  462.     int y = 0;  
  463.     int ind = 0;  
  464.     float vals[kMaxSVs];  
  465.     memset(vals, 0, sizeof(float)*n);  
  466.     int drawOrder[kMaxSVs];  
  467.       
  468.     for (int set = 0; set < 2; ++set)  
  469.     {  
  470.         for (int i = 0; i < n; ++i)  
  471.         {  
  472.             if (((set == 0) ? 1 : -1)*m_svs[i]->b < 0.0) continue;  
  473.               
  474.             drawOrder[ind] = i;  
  475.             vals[ind] = (float)m_svs[i]->b;  
  476.             ++ind;  
  477.               
  478.             Mat I = m_debugImage(cv::Rect(x, y, tileSize, tileSize));  
  479.             resize(m_svs[i]->x->images[m_svs[i]->y], temp, temp.size());  
  480.             cvtColor(temp, I, CV_GRAY2RGB);  
  481.             double w = 1.0;  
  482.             rectangle(I, Point(0, 0), Point(tileSize-1, tileSize-1), (m_svs[i]->b > 0.0) ? CV_RGB(0, (uchar)(255*w), 0) : CV_RGB((uchar)(255*w), 0, 0), 3);  
  483.             x += tileSize;  
  484.             if ((x+tileSize) > kCanvasSize)  
  485.             {  
  486.                 y += tileSize;  
  487.                 x = 0;  
  488.             }  
  489.         }  
  490.     }  
  491.       
  492.     const int kKernelPixelSize = 2;  
  493.     int kernelSize = kKernelPixelSize*n;  
  494.       
  495.     double kmin = m_K.minCoeff();  
  496.     double kmax = m_K.maxCoeff();  
  497.       
  498.     if (kernelSize < m_debugImage.cols && kernelSize < m_debugImage.rows)  
  499.     {  
  500.         Mat K = m_debugImage(cv::Rect(m_debugImage.cols-kernelSize, m_debugImage.rows-kernelSize, kernelSize, kernelSize));  
  501.         for (int i = 0; i < n; ++i)  
  502.         {  
  503.             for (int j = 0; j < n; ++j)  
  504.             {  
  505.                 Mat Kij = K(cv::Rect(j*kKernelPixelSize, i*kKernelPixelSize, kKernelPixelSize, kKernelPixelSize));  
  506.                 uchar v = (uchar)(255*(m_K(drawOrder[i], drawOrder[j])-kmin)/(kmax-kmin));  
  507.                 Kij.setTo(Scalar(v, v, v));  
  508.             }  
  509.         }  
  510.     }  
  511.     else  
  512.     {  
  513.         kernelSize = 0;  
  514.     }  
  515.       
  516.       
  517.     Mat I = m_debugImage(cv::Rect(0, m_debugImage.rows - 200, m_debugImage.cols-kernelSize, 200));  
  518.     I.setTo(Scalar(255,255,255));  
  519.     IplImage II = I;  
  520.     setGraphColor(0);  
  521.     drawFloatGraph(vals, n, &II, 0.f, 0.f, I.cols, I.rows);  
  522. }  


相关推荐