VSLAM系列原创04讲四叉树实现ORB特征点均匀化分布：原
理+代码
本⽂系ORB-SLAM2原理+代码实战系列原创⽂章，对应的视频课程见：
⼤家好，从今天开始我们陆续更新ORB-SLAM2/3系列的原创⽂章，以⼩⽩和师兄对话的形式阐述背景原理+代码解析，喜欢的点个赞分享，⽀持的⼈越多，更新越有动⼒！如有错误欢迎留⾔指正！
代码注释地址：
接上回继续。。。
四叉树实现特征点均匀化分布
师兄：四叉树实现特征均匀化分布的⽅法是重点，也是⼀个难点，我先讲⼀下步骤和原理：
第1步：⾸先确定初始的节点（node）数⽬。根据图像宽⾼⽐取整来确定，所以⼀般的VGA () 分辨率图像刚开始的时候只有⼀个节点，也是四叉树的根节点。
下⾯我们⽤⼀个具体的例⼦来分析四叉树是如何帮助我们均匀化选取特定数⽬的特征点的。假设初始节
点只有1个，那么所有的特征点都属于该节点。我们⽬标是均匀的选取 25 个特征点，那么后⾯我们就需要分裂出25个节点，然后从每个节点中选取⼀个代表性的特征点。
第2步：节点第1次分裂，1个根节点分裂为4个节点。如下图所⽰，分裂之后根据图像的尺⼨划分节点
的区域，对应的边界为 ，分别对应左上⾓、右上⾓、左下⾓、右下⾓的四个坐标。有些坐标会被多个节点共享，⽐如图像中⼼点坐标就同时被 四个点共享。落在某个节点区域范围内的所有特征点都属于该节点的元素。
然后统计每个节点⾥包含特征点的数⽬，如果某个节点⾥特征点数⽬为 0，则删掉该节点，如果某个节点⾥特征点数⽬为 1，则该节点不再进⾏分裂。判断此时的节点总数是否超过设定值 25，如果没有超过则继续对每个节点分裂。
这⾥需要注意的是⼀个母节点分裂为 4 个⼦节点后，需要在节点链表⾥删掉原来的母节点，所以实际上⼀次分裂净增加了 3 个节点。所以下次分裂后节点的总数我们是可以提前预估的，计算⽅式为：（当前节点总数 + 即将分裂的节点总数 3 ），对于图⽰来说，下次分裂最多可以得到 个节点，显然还是没有达到 25 的要求，需要继续分裂。
第3步：对上⼀步得到的 4 个节点分别进⾏⼀分为四的操作，然后统计分裂后的每个节点⾥包含特征点的数⽬，我们可以看到已经有 2 个节点⾥的特征点数⽬为 0，于是在节点链表⾥删掉这 2 个节点（
下图中标记为 ）。如果某个节点⾥特征点数⽬为 1，则该节点不再进⾏分裂。此次分裂总共得到 14 个节点。
第4步：上⼀步得到的 14 个节点继续进⾏⼀分四的操作。预计这次分裂最多可以得到 个节点，已经超过我们需要提取 25 个特征点数⽬的需求。此时需要注意了，我们不需要把所有的节点都进⾏分裂，我们只需要在分裂得到的所有节点数⽬刚刚达到 25 时，即可停⽌分裂，这样操作的⽬的⼀⽅⾯是可以避免多分裂后再删除⽽做⽆⽤功，另⼀⽅⾯，因为是指数级分裂，所以也⼤⼤加速了四叉树分裂的过程。
那么，如何选取分裂的顺序呢？源码⾥采⽤的策略是对所有节点按照内部包含的特征点数⽬进⾏排列，优先分裂特征点数⽬多的节点，这样做的⽬的是使得特征密集的区域能够更加细分。对于包含特征点较少的节点，有可能因为提前达到要求⽽不再分裂。下图中绿⾊⽅框内的节点就是因为包含的特征点数⽬太少（这⾥包括只有 1 个也不再分裂的情况），分裂的优先级很低，最终在达到要求的节点数⽬前没有再分裂。
第5步：上⼀步中我们已经得到了所需要的 25 个节点，只需要从每个节点中选出⾓点响应值最⾼的特征点，作为该节点的唯⼀特征点，该节点内其他低响应值的特征点全部删掉。这样我们就得到了均匀化后的、需要数⽬的特征点。
玉米发糕
以上就是使⽤四叉树对图像特征点进⾏均匀化的原理，详细注释代码见：
/**
* @brief 使⽤四叉树法对⼀个图像⾦字塔图层中的特征点进⾏平均和分发
减肥记录表
*
* @param[in] vToDistributeKeys 等待进⾏分配到四叉树中的特征点
* @param[in] minX 当前图层的图像的边界
* @param[in] maxX
* @param[in] minY
* @param[in] maxY
* @param[in] N 希望提取出的特征点个数
* @param[in] level 指定的⾦字塔图层
* @return vector<cv::KeyPoint> 已经均匀分散好的特征点容器
*/
vector<cv::KeyPoint> ORBextractor::DistributeOctTree(const vector<cv::KeyPoint>& vToDistributeKeys, const int &minX,
const int &maxX, const int &minY, const int &maxY, const int &N, const int &level)
{
// Step 1 根据宽⾼⽐确定初始节点数⽬
//计算应该⽣成的初始节点个数，根节点的数量nIni是根据边界的宽⾼⽐值确定的，⼀般是1或者2
// ! bug: 如果宽⾼⽐⼩于0.5，nIni=0, 后⾯hx会报错
const int nIni = round(static_cast<float>(maxX-minX)/(maxY-minY));
//⼀个初始的节点的x⽅向有多少个像素
const float hX = static_cast<float>(maxX-minX)/nIni;
//存储有提取器节点的链表
list<ExtractorNode> lNodes;
//存储初始提取器节点指针的vector
师德师风调查问卷
vector<ExtractorNode*> vpIniNodes;
//重新设置其⼤⼩
艳丽造句
// Step 2 ⽣成初始提取器节点
for(int i=0; i<nIni; i++)
{
//⽣成⼀个提取器节点
ExtractorNode ni;
//设置提取器节点的图像边界
ni.UL = cv::Point2i(hX*static_cast<float>(i),0); //UpLeft
ni.UR = cv::Point2i(hX*static_cast<float>(i+1),0); //UpRight
ni.BL = cv::Point2i(ni.UL.x,maxY-minY); //BottomLeft
ni.BR = cv::Point2i(ni.UR.x,maxY-minY); //BottomRight
//重设vkeys⼤⼩
冰菜的功效与作用
ve(vToDistributeKeys.size());
//将刚才⽣成的提取节点添加到链表中
lNodes.push_back(ni);
//存储这个初始的提取器节点句柄
vpIniNodes[i] = &lNodes.back();
}
// Step 3 将特征点分配到⼦提取器节点中
for(size_t i=0;i<vToDistributeKeys.size();i++)
{
//获取这个特征点对象
const cv::KeyPoint &kp = vToDistributeKeys[i];
//按特征点的横轴位置，分配给属于那个图像区域的提取器节点（最初的提取器节点）
vpIniNodes[kp.pt.x/hX]->vKeys.push_back(kp);
}
// Step 4 遍历此提取器节点列表，标记那些不可再分裂的节点，删除那些没有分配到特征点的节点
list<ExtractorNode>::iterator lit = lNodes.begin();
while(lit!=d())
{
红楼梦原文//如果初始的提取器节点所分配到的特征点个数为1
if(lit->vKeys.size()==1)
{
//那么就标志位置位，表⽰此节点不可再分
lit->bNoMore=true;
//更新迭代器
lit++;
}
//如果⼀个提取器节点没有被分配到特征点，那么就从列表中直接删除它
el if(lit-&pty())
//注意，由于是直接删除了它，所以这⾥的迭代器没有必要更新；否则反⽽会造成跳过元素的情况 lit = a(lit);
el
//如果上⾯的这些情况和当前的特征点提取器节点⽆关，那么就只是更新迭代器
lit++;
附件}
//结束标志位清空
bool bFinish = fal;
//记录迭代次数，只是记录，并未起到作⽤
int iteration = 0;
//声明⼀个vector⽤于存储节点的vSize和句柄对
//这个变量记录了在⼀次分裂循环中，那些可以再继续进⾏分裂的节点中包含的特征点数⽬和其句柄
vector<pair<int,ExtractorNode*> > vSizeAndPointerToNode;
//调整⼤⼩，这⾥的意思是⼀个初始化节点将“分裂”成为四个
// Step 5 利⽤四叉树⽅法对图像进⾏划分区域，均匀分配特征点
while(!bFinish)
{皮蛋瘦肉粥的功效和作用
