• ORB-SLAM2 ---- ORBmatcher::SearchByBoW函数

    1.本函数的作用        

            匹配两帧中的特征点，与ORBmatcher::SearchForInitialization相比，ORBmatcher::SearchForTriangulation利用了词袋BoW加速了匹配速度。

    ORB-SLAM2 ---- ORBmatcher::SearchForInitialization函数_Courage2022的博客-CSDN博客https://blog.csdn.net/qq_41694024/article/details/126319167?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22126319167%22%2C%22source%22%3A%22qq_41694024%22%7D

    2.词袋原理 Bow

    直观理解词袋

    词袋的形成：

    提取ORB特征点、对描述子进行聚类；有新的一帧传进来时、我们将其在词袋内进行遍历得到很多单词，可以用频率来表示。

    3 如何制作BoW 

    3.1 离线训练

            首先图像提取ORB 特征点，将描述子通过 k-means 进行聚类，根据设定的树的分支数和深度，从叶子节点开始聚类一直到根节点，最后得到一个非常大的 vocabulary tree，

            1、遍历所有的训练图像，对每幅图像提取ORB特征点。

            2、设定vocabulary tree的分支数K和深度L。将特征点的每个描述子用 K-means聚类，变成 K个集合， 作为vocabulary tree 的第1层级，然后对每个集合重复该聚类操作，就得到了vocabulary tree的第2层级，继续迭代最后得到满足条件的vocabulary tree，它的规模通常比较大，比如ORB-SLAM2使用的离线字典就有108万+ 个节点。

            3、离根节点最远的一层节点称为叶子或者单词 Word。根据每个Word 在训练集中的相关程度给定一个权重weight，训练集里出现的次数越多，说明辨别力越差，给与的权重越低。（这个我感觉像哈夫曼树....）

    3.2 在线图像生成BoW向量 

    1、对新来的一帧图像进行ORB特征提取，得到一定数量（一般几百个）的特征点，描述子维度和 vocabulary tree中的一致

    2、对于每个特征点的描述子，从离线创建好的vocabulary tree中开始找自己的位置，从根节点开始， 用该描述子和每个节点的描述子计算汉明距离，选择汉明距离最小的作为自己所在的节点，一直遍历到叶子节点。 整个过程是这样的。紫色的线表示一个特征点从根节点到叶子节点的过程。

    3.3 代码解析： Frame::ComputeBoW函数

    ORB-SLAM2 ---- Frame::ComputeBoW函数_Courage2022的博客-CSDN博客icon-default.png?t=M666https://blog.csdn.net/qq_41694024/article/details/126328833

    4 ORBmatcher::SearchByBoW函数解析

    4.1 该函数的作用及参数

    1. /*
    2.  * @brief 通过词袋，对关键帧的特征点进行跟踪
    3.  * 步骤
    4.  * Step 1：分别取出属于同一node的ORB特征点(只有属于同一node，才有可能是匹配点)
    5.  * Step 2：遍历KF中属于该node的特征点
    6.  * Step 3：遍历F中属于该node的特征点，寻找最佳匹配点
    7.  * Step 4：根据阈值 和 角度投票剔除误匹配
    8.  * Step 5：根据方向剔除误匹配的点
    9.  * @param  pKF               关键帧
    10.  * @param  F                 当前普通帧
    11.  * @param  vpMapPointMatches F中地图点对应的匹配，NULL表示未匹配
    12.  * @return                   成功匹配的数量
    13.  */
    14. int ORBmatcher::SearchByBoW(KeyFrame* pKF,Frame &F, vector &vpMapPointMatches)
    15. {
    16.     // 获取该关键帧的地图点
    17.     const vector vpMapPointsKF = pKF->GetMapPointMatches();
    18.  
    19.     // 和普通帧F特征点的索引一致
    20.     vpMapPointMatches = vector(F.N,static_cast(NULL));
    21.  
    22.     // 取出关键帧的词袋特征向量
    23.     const DBoW2::FeatureVector &vFeatVecKF = pKF->mFeatVec;
    24.  
    25.     int nmatches=0;
    26.  
    27.     // 特征点角度旋转差统计用的直方图
    28.     vector<int> rotHist[HISTO_LENGTH];
    29.     for(int i=0;i
    30.         rotHist[i].reserve(500);
    31.  
    32.     // 将0~360的数转换到0~HISTO_LENGTH的系数
    33.     // !原作者代码是 const float factor = 1.0f/HISTO_LENGTH; 是错误的，更改为下面代码  
    34.     const float factor = HISTO_LENGTH/360.0f;
    35.  
    36.     // We perform the matching over ORB that belong to the same vocabulary node (at a certain level)
    37.     // 将属于同一节点(特定层)的ORB特征进行匹配
    38.     DBoW2::FeatureVector::const_iterator KFit = vFeatVecKF.begin();
    39.     DBoW2::FeatureVector::const_iterator Fit = F.mFeatVec.begin();
    40.     DBoW2::FeatureVector::const_iterator KFend = vFeatVecKF.end();
    41.     DBoW2::FeatureVector::const_iterator Fend = F.mFeatVec.end();
    42.  
    43.     while(KFit != KFend && Fit != Fend)
    44.     {
    45.         // Step 1：分别取出属于同一node的ORB特征点(只有属于同一node，才有可能是匹配点)
    46.         // first 元素就是node id，遍历
    47.         if(KFit->first == Fit->first) 
    48.         {
    49.             // second 是该node内存储的feature index
    50.             const vector<unsigned int> vIndicesKF = KFit->second;
    51.             const vector<unsigned int> vIndicesF = Fit->second;
    52.  
    53.             // Step 2：遍历KF中属于该node的特征点
    54.             for(size_t iKF=0; iKFsize(); iKF++)
    55.             {
    56.                 // 关键帧该节点中特征点的索引
    57.                 const unsigned int realIdxKF = vIndicesKF[iKF];
    58.  
    59.                 // 取出KF中该特征对应的地图点
    60.                 MapPoint* pMP = vpMapPointsKF[realIdxKF]; 
    61.  
    62.                 if(!pMP)
    63.                     continue;
    64.  
    65.                 if(pMP->isBad())
    66.                     continue;
    67.  
    68.                 const cv::Mat &dKF= pKF->mDescriptors.row(realIdxKF); // 取出KF中该特征对应的描述子
    69.  
    70.                 int bestDist1=256; // 最好的距离（最小距离）
    71.                 int bestIdxF =-1 ;
    72.                 int bestDist2=256; // 次好距离（倒数第二小距离）
    73.  
    74.                 // Step 3：遍历F中属于该node的特征点，寻找最佳匹配点
    75.                 for(size_t iF=0; iFsize(); iF++)
    76.                 {
    77.                     // 和上面for循环重名了,这里的realIdxF是指普通帧该节点中特征点的索引
    78.                     const unsigned int realIdxF = vIndicesF[iF];
    79.  
    80.                     // 如果地图点存在，说明这个点已经被匹配过了，不再匹配，加快速度
    81.                     if(vpMapPointMatches[realIdxF])
    82.                         continue;
    83.  
    84.                     const cv::Mat &dF = F.mDescriptors.row(realIdxF); // 取出F中该特征对应的描述子
    85.                     // 计算描述子的距离
    86.                     const int dist =  DescriptorDistance(dKF,dF); 
    87.  
    88.                     // 遍历，记录最佳距离、最佳距离对应的索引、次佳距离等
    89.                     // 如果 dist < bestDist1 < bestDist2，更新bestDist1 bestDist2
    90.                     if(dist
    91.                     {
    92.                         bestDist2=bestDist1;
    93.                         bestDist1=dist;
    94.                         bestIdxF=realIdxF;
    95.                     }
    96.                     // 如果bestDist1 < dist < bestDist2，更新bestDist2
    97.                     else if(dist
    98.                     {
    99.                         bestDist2=dist;
    100.                     }
    101.                 }
    102.  
    103.                 // Step 4：根据阈值 和 角度投票剔除误匹配
    104.                 // Step 4.1：第一关筛选：匹配距离必须小于设定阈值
    105.                 if(bestDist1<=TH_LOW) 
    106.                 {
    107.                     // Step 4.2：第二关筛选：最佳匹配比次佳匹配明显要好，那么最佳匹配才真正靠谱
    108.                     if(static_cast<float>(bestDist1)static_cast<float>(bestDist2))
    109.                     {
    110.                         // Step 4.3：记录成功匹配特征点的对应的地图点(来自关键帧)
    111.                         vpMapPointMatches[bestIdxF]=pMP;
    112.  
    113.                         // 这里的realIdxKF是当前遍历到的关键帧的特征点id
    114.                         const cv::KeyPoint &kp = pKF->mvKeysUn[realIdxKF];
    115.  
    116.                         // Step 4.4：计算匹配点旋转角度差所在的直方图
    117.                         if(mbCheckOrientation)
    118.                         {
    119.                             // angle：每个特征点在提取描述子时的旋转主方向角度，如果图像旋转了，这个角度将发生改变
    120.                             // 所有的特征点的角度变化应该是一致的，通过直方图统计得到最准确的角度变化值
    121.                             float rot = kp.angle-F.mvKeys[bestIdxF].angle;// 该特征点的角度变化值
    122.                             if(rot<0.0)
    123.                                 rot+=360.0f;
    124.                             int bin = round(rot*factor);// 将rot分配到bin组, 四舍五入, 其实就是离散到对应的直方图组中
    125.                             if(bin==HISTO_LENGTH)
    126.                                 bin=0;
    127.                             assert(bin>=0 && bin
    128.                             rotHist[bin].push_back(bestIdxF);       // 直方图统计
    129.                         }
    130.                         nmatches++;
    131.                     }
    132.                 }
    133.  
    134.             }
    135.             KFit++;
    136.             Fit++;
    137.         }
    138.         else if(KFit->first < Fit->first)
    139.         {
    140.             // 对齐
    141.             KFit = vFeatVecKF.lower_bound(Fit->first);
    142.         }
    143.         else
    144.         {
    145.             // 对齐
    146.             Fit = F.mFeatVec.lower_bound(KFit->first);
    147.         }
    148.     }
    149.  
    150.     // Step 5 根据方向剔除误匹配的点
    151.     if(mbCheckOrientation)
    152.     {
    153.         // index
    154.         int ind1=-1;
    155.         int ind2=-1;
    156.         int ind3=-1;
    157.  
    158.         // 筛选出在旋转角度差落在在直方图区间内数量最多的前三个bin的索引
    159.         ComputeThreeMaxima(rotHist,HISTO_LENGTH,ind1,ind2,ind3);
    160.  
    161.         for(int i=0; i
    162.         {
    163.             // 如果特征点的旋转角度变化量属于这三个组，则保留
    164.             if(i==ind1 || i==ind2 || i==ind3)
    165.                 continue;
    166.  
    167.             // 剔除掉不在前三的匹配对，因为他们不符合“主流旋转方向”  
    168.             for(size_t j=0, jend=rotHist[i].size(); j
    169.             {
    170.                 vpMapPointMatches[rotHist[i][j]]=static_cast(NULL);
    171.                 nmatches--;
    172.             }
    173.         }
    174.     }
    175.  
    176.     return nmatches;
    177. }

    4.2  分别取出属于同一node的ORB特征点(只有属于同一node，才有可能是匹配点

    1. // 获取该关键帧的地图点
    2.     const vector vpMapPointsKF = pKF->GetMapPointMatches();
    3.  
    4.     // 和普通帧F特征点的索引一致
    5.     vpMapPointMatches = vector(F.N,static_cast(NULL));
    6.  
    7.     // 取出关键帧的词袋特征向量
    8.     const DBoW2::FeatureVector &vFeatVecKF = pKF->mFeatVec;
    9.  
    10.     int nmatches=0;
    11.  
    12.     // 特征点角度旋转差统计用的直方图
    13.     vector<int> rotHist[HISTO_LENGTH];
    14.     for(int i=0;i
    15.         rotHist[i].reserve(500);
    16.  
    17.     // 将0~360的数转换到0~HISTO_LENGTH的系数
    18.     // !原作者代码是 const float factor = 1.0f/HISTO_LENGTH; 是错误的，更改为下面代码  
    19.     const float factor = HISTO_LENGTH/360.0f;
    20.  
    21.     // We perform the matching over ORB that belong to the same vocabulary node (at a certain level)
    22.     // 将属于同一节点(特定层)的ORB特征进行匹配
    23.     DBoW2::FeatureVector::const_iterator KFit = vFeatVecKF.begin();
    24.     DBoW2::FeatureVector::const_iterator Fit = F.mFeatVec.begin();
    25.     DBoW2::FeatureVector::const_iterator KFend = vFeatVecKF.end();
    26.     DBoW2::FeatureVector::const_iterator Fend = F.mFeatVec.end();
    27.  
    28.     while(KFit != KFend && Fit != Fend)
    29.     {
    30.         // Step 1：分别取出属于同一node的ORB特征点(只有属于同一node，才有可能是匹配点)
    31.         // first 元素就是node id，遍历
    32.         if(KFit->first == Fit->first) 
    33.         {
    34.             // second 是该node内存储的feature index
    35.             const vector<unsigned int> vIndicesKF = KFit->second;
    36.             const vector<unsigned int> vIndicesF = Fit->second;
    class BowVector: public std::map
    class FeatureVector: public std::mapunsigned int> >

            pKF是关键帧、F是当前普通帧。用vpMapPointsKF容器提取关键帧中的地图点。vpMapPointMatches 容器记录匹配关系，建立指向关键帧词袋特征向量的引用vFeatVecKF、匹配数目的指示器nmatches、建立旋转直方图rotHist、建立关键帧和普通帧的FeatureVector的迭代器KFit、Fit、KFend、Fend。

            由Frame::ComputeBoW函数的解析我们知：如果两个描述子要成功匹配，其必属于同一个node。

    4.3  遍历KF中属于该node的特征点

    4.4 遍历F中属于该node的特征点，寻找最佳匹配点

    1. while(KFit != KFend && Fit != Fend)
    2.     {
    3.         // Step 1：分别取出属于同一node的ORB特征点(只有属于同一node，才有可能是匹配点)
    4.         // first 元素就是node id，遍历
    5.         if(KFit->first == Fit->first) 
    6.         {
    7.             // second 是该node内存储的feature index
    8.             const vector<unsigned int> vIndicesKF = KFit->second;
    9.             const vector<unsigned int> vIndicesF = Fit->second;
    10.  
    11.             // Step 2：遍历KF中属于该node的特征点
    12.             for(size_t iKF=0; iKFsize(); iKF++)
    13.             {
    14.                 // 关键帧该节点中特征点的索引
    15.                 const unsigned int realIdxKF = vIndicesKF[iKF];
    16.  
    17.                 // 取出KF中该特征对应的地图点
    18.                 MapPoint* pMP = vpMapPointsKF[realIdxKF]; 
    19.  
    20.                 if(!pMP)
    21.                     continue;
    22.  
    23.                 if(pMP->isBad())
    24.                     continue;
    25.  
    26.                 const cv::Mat &dKF= pKF->mDescriptors.row(realIdxKF); // 取出KF中该特征对应的描述子
    27.  
    28.                 int bestDist1=256; // 最好的距离（最小距离）
    29.                 int bestIdxF =-1 ;
    30.                 int bestDist2=256; // 次好距离（倒数第二小距离）
    31.  
    32.                 // Step 3：遍历F中属于该node的特征点，寻找最佳匹配点
    33.                 for(size_t iF=0; iFsize(); iF++)
    34.                 {
    35.                     // 和上面for循环重名了,这里的realIdxF是指普通帧该节点中特征点的索引
    36.                     const unsigned int realIdxF = vIndicesF[iF];
    37.  
    38.                     // 如果地图点存在，说明这个点已经被匹配过了，不再匹配，加快速度
    39.                     if(vpMapPointMatches[realIdxF])
    40.                         continue;
    41.  
    42.                     const cv::Mat &dF = F.mDescriptors.row(realIdxF); // 取出F中该特征对应的描述子
    43.                     // 计算描述子的距离
    44.                     const int dist =  DescriptorDistance(dKF,dF); 
    45.  
    46.                     // 遍历，记录最佳距离、最佳距离对应的索引、次佳距离等
    47.                     // 如果 dist < bestDist1 < bestDist2，更新bestDist1 bestDist2
    48.                     if(dist
    49.                     {
    50.                         bestDist2=bestDist1;
    51.                         bestDist1=dist;
    52.                         bestIdxF=realIdxF;
    53.                     }
    54.                     // 如果bestDist1 < dist < bestDist2，更新bestDist2
    55.                     else if(dist
    56.                     {
    57.                         bestDist2=dist;
    58.                     }
    59.                 }

            KFit、Fit分别是指向关键帧、普通帧的FeatureVector容器的迭代器。如果他们的nodeID相同则进入匹配，若KFit的node小于Fit的node，则调整迭代器KFit指向大于等于Fit迭代器所指向的node大小的地方，方便下次匹配。

    1.         else if(KFit->first < Fit->first)
    2.         {
    3.             // 对齐
    4.             KFit = vFeatVecKF.lower_bound(Fit->first);
    5.         }
    6.         else
    7.         {
    8.             // 对齐
    9.             Fit = F.mFeatVec.lower_bound(KFit->first);
    10.         }

            若node相同，则依次匹配利用选择排序，和前面讲的就完全一样了。

  • 相关阅读:
    批量归一化(部分理解)
    MySQL索引优化
    java sql字符串解析
    (十三) minAreaRect函数
    uni-fab彩色图标按钮
    ctfshow-web12（glob绕过）
    云原生|kubernetes|k8s下部署SQLServer以及Navicat连接SQLServer报错：远程主机强迫关闭了一个现有的连接 错误的解决
    cartgrapher ukf 代码清晰属实不错
    K8S故障处理指南：网络问题排查思路
    已加载插件：fastestmirror, langpacks /var/run/yum.pid 已被锁定，PID 为 2686 的另一个程序正在运行。
  • 原文地址：https://blog.csdn.net/qq_41694024/article/details/126322962