ORB-SLAM2源码学习：ORBextractor.cc ：ComputeKeyPointsOctTree计算并分配特征点②

前言

该函数接受一个二维vector的引用vector<vector<KeyPoint> >& allKeypoints。外层的 vector 存储不同层级的特征点，每个内层的 vector<KeyPoint> 存储在该层级中提取到的特征点。该参数的声明是在主入口函数operator（）中进行的。它是在构建完图像金字塔（决定了每层分配多少个特征点）后进行的，是要真正的用特征点去填满金字塔。

1.函数声明

//所有的特征点，这里第一层vector存储的是某图层里面的所有特征点，
//第二层存储的是整个图像金字塔中的所有图层里面的所有特征点
void ORBextractor::ComputeKeyPointsOctTree(vector<vector<KeyPoint> >& allKeypoints)
{....
}

2.函数定义

2.1循环之外的一些准备

 allKeypoints.resize(nlevels);//重新调整图像层数

为vector进行扩容，与金字塔的层数相一致。

const float W = 30;//定义网格单元数量。

为后续计算网格宽度和高度等信息做准备。

2.2外层循环：遍历每一层金字塔

注：我认为ORB-SLAM2源代码中构建的金字塔最后的mvImagePyramid传到这个函数中的并没有进行成功的扩容导致这里理解有误。

ORB-SLAM2源码学习：ORBextractor.cc：ComputePyramid构建图像金字塔①

for (int level = 0; level < nlevels; ++level)// 遍历每一层图像金字塔。{// EDGE_THRESHOLD = 19// 提取FAST特征点而预留的计算半径3。const int minBorderX = EDGE_THRESHOLD-3;const int minBorderY = minBorderX;//请留意这里的mvImagePyramid变量。const int maxBorderX = mvImagePyramid[level].cols-EDGE_THRESHOLD+3;const int maxBorderY = mvImagePyramid[level].rows-EDGE_THRESHOLD+3;vector<cv::KeyPoint> vToDistributeKeys;//声明一个预分配的特征点的容器。vToDistributeKeys.reserve(nfeatures*10);//过量的扩容预留分配空间的大小。// 提取FAST特征点设定的那个特定区域的图像尺寸。const float width = (maxBorderX-minBorderX);const float height = (maxBorderY-minBorderY);// 计算行数和列数const int nCols = width/W;const int nRows = height/W;// 计算实际的宽度和高度（像素）const int wCell = ceil(width/nCols);const int hCell = ceil(height/nRows);......}

2.2.1图像区域：

2.3内层循环：遍历网格

首先遍历y轴方向，计算出每个单元格上下两个边的坐标（iniY、maxY），并对其坐标增加一定的限制，之后遍历x轴方向，重复y轴的计算方式。

for(int i=0; i<nRows; i++)// 遍历在特定区域中划分的每一行网格单元。{const float iniY =minBorderY+i*hCell;// 计算初始 Y 坐标float maxY = iniY+hCell+6;//可能为了确保在特征点检测过程中，有足够的区域覆盖来处理边缘效果或额外的特征点。if(iniY>=maxBorderY-3)//图中的灰色区域continue;if(maxY>maxBorderY)maxY = maxBorderY;for(int j=0; j<nCols; j++){const float iniX =minBorderX+j*wCell;float maxX = iniX+wCell+6;if(iniX>=maxBorderX-6)// 这里为什么是-6？或者是相关结论？我认为这里应该是-3.continue;if(maxX>maxBorderX)maxX = maxBorderX;vector<cv::KeyPoint> vKeysCell;// 定义用于存储在当前网格单元中检测到的关键点。// 调用FAST算法FAST(mvImagePyramid[level].rowRange(iniY,maxY).colRange(iniX,maxX),vKeysCell,//储存FAST提取角点的容器。iniThFAST,//检测阈值true);//使用非极大值抑制，避免提取的角点过度集中。// 如果第一次检测到的关键点为空（即没有找到有效的关键点），则会使用较低的阈值进行第二次检测。if(vKeysCell.empty()){FAST(mvImagePyramid[level].rowRange(iniY,maxY).colRange(iniX,maxX),vKeysCell,minThFAST,true);}if(!vKeysCell.empty())//如果非空则调整坐标。{for(vector<cv::KeyPoint>::iterator vit=vKeysCell.begin(); vit!=vKeysCell.end();vit++)//迭代器指到vKeysCell.begin();{//从在网格中的相对坐标转到相对于整个半径扩充区域的绝对坐标。(*vit).pt.x+=j*wCell;(*vit).pt.y+=i*hCell;vToDistributeKeys.push_back(*vit);}}}}

2.3.1示意图

为什么要加6呢？

结合图片我们可以很轻易的理解，是因为要提取FAST特征点而在提取的单元格外套一个3像素的壳子，之后该单元格的整体的y的像素值就要加6

2.3.2FAST提取特征点

FAST(mvImagePyramid[level].rowRange(iniY,maxY).colRange(iniX,maxX),vKeysCell,iniThFAST,true);// 调用FAST算法

说明：

从图像金字塔的当前层（level）中提取出一个特定的矩形区域，矩形区域的左上角坐标为 (iniX, iniY)，右下角坐标为 (maxX, maxY)。这代表了当前网格单元的区域。

iniThFAST这是FAST算法的初始阈值，用于决定是否将某个像素点作为关键点。

非极大值抑制：将参数设置为 true 意味着在检测每个关键点时，算法不仅会确定其是否为关键点，还会计算出其强度。

2.3.3 检查提取的特征点的情况

如果第一次检测到的关键点为空（即没有找到有效的关键点），则会使用较低的阈值(minThFAST)进行第二次检测。

if(vKeysCell.empty()){FAST(mvImagePyramid[level].rowRange(iniY,maxY).colRange(iniX,maxX),vKeysCell,minThFAST,true);}if(!vKeysCell.empty()){.......}

2.4最内层循环：调整坐标

遍历每一个单元格，调整特征点的坐标：将从每个网格单元检测到的关键点坐标调整到整个图像的坐标系中。

for(vector<cv::KeyPoint>::iterator vit=vKeysCell.begin(); vit!=vKeysCell.end();vit++)//迭代器指到vKeysCell.begin();{(*vit).pt.x+=j*wCell;(*vit).pt.y+=i*hCell;vToDistributeKeys.push_back(*vit);}

举例说明：

一个图像的宽度是 300 像素，高度是 300 像素。W 设置为 30，则将图像分为 10x10 的网格单元（nCols = nRows = 10）。每个网格单元的宽度和高度 wCell 和 hCell 均为 30 像素。如果在第 (i, j) 网格单元（例如第 2 行第 3 列）中提取到一个关键点，其相对坐标为 (5, 10)，即在这个网格单元内的坐标，则：j * wCell = 3 * 30 = 90（第 3 列的起始位置）i * hCell = 2 * 30 = 60（第 2 行的起始位置）。

因此，关键点的新绝对坐标将是：x = 5 + 90 = 95、 y = 10 + 60 = 70。

2.5为每一层分配特征点

其中调用DistributeOctTree（）函数进行分配。

注：不过这个分配的坐标系可能不一样。

vector<KeyPoint> & keypoints = allKeypoints[level];keypoints.reserve(nfeatures);keypoints = DistributeOctTree(vToDistributeKeys, //？注意：这里即将分配特征点的坐标系与下方区域的坐标系不一样。minBorderX,maxBorderX,minBorderY,maxBorderY,mnFeaturesPerLevel[level],//储存这一层金字塔希望分配的特征点数。level);//某层。const int scaledPatchSize = PATCH_SIZE*mvScaleFactor[level];// Add border to coordinates and scale information//获取剔除过程后保留下来的特征点数目const int nkps = keypoints.size();for(int i=0; i<nkps ; i++){//对每一个保留下来的特征点，恢复到相对于当前图层“边缘扩充图像下”的坐标系的坐标keypoints[i].pt.x+=minBorderX;keypoints[i].pt.y+=minBorderY;keypoints[i].octave=level;keypoints[i].size = scaledPatchSize;}

2.6计算每一层金字塔的特征点的方向

这里ComputeKeyPointsOctTree（）函数调用computeOrientation()函数对金字塔每一层的特征点们进行计算方向，而computeOrientation()函数调用的是IC_Angle函数对单个特征点进行方向的计算。

ORB-SLAM2源码学习：ORBextractor.cc：IC_Angle 利用灰度质心法求解关键点方向角

// compute orientations//然后计算这些特征点的方向信息，注意这里还是分层计算的for (int level = 0; level < nlevels; ++level)computeOrientation(mvImagePyramid[level],	//对应的图层的图像allKeypoints[level], 	//这个图层中提取并保留下来的特征点容器umax);					//以及PATCH的横坐标边界
}

3.整体代码的实现

void ORBextractor::ComputeKeyPointsOctTree(vector<vector<KeyPoint> >& allKeypoints)
{allKeypoints.resize(nlevels);const float W = 30;//定义网格单元数量。for (int level = 0; level < nlevels; ++level)// 遍历每一层图像金字塔。{// EDGE_THRESHOLD = 19// 提取FAST特征点而预留的计算半径3。const int minBorderX = EDGE_THRESHOLD-3;const int minBorderY = minBorderX;const int maxBorderX = mvImagePyramid[level].cols-EDGE_THRESHOLD+3;const int maxBorderY = mvImagePyramid[level].rows-EDGE_THRESHOLD+3;vector<cv::KeyPoint> vToDistributeKeys;vToDistributeKeys.reserve(nfeatures*10);// 提取FAST特征点设定的那个特定区域。const float width = (maxBorderX-minBorderX);const float height = (maxBorderY-minBorderY);const int nCols = width/W;const int nRows = height/W;// 计算实际的宽度和高度const int wCell = ceil(width/nCols);const int hCell = ceil(height/nRows);for(int i=0; i<nRows; i++)// 遍历在特定区域中划分的每一行网格单元。{const float iniY =minBorderY+i*hCell;// 计算初始 Y 坐标float maxY = iniY+hCell+6;//可能为了确保在特征点检测过程中，有足够的区域覆盖来处理边缘效果或额外的特征点。if(iniY>=maxBorderY-3)continue;if(maxY>maxBorderY)maxY = maxBorderY;for(int j=0; j<nCols; j++){const float iniX =minBorderX+j*wCell;float maxX = iniX+wCell+6;if(iniX>=maxBorderX-6)// 这里为什么是-6？或者是相关结论？continue;if(maxX>maxBorderX)maxX = maxBorderX;vector<cv::KeyPoint> vKeysCell;// 定义用于存储在当前网格单元中检测到的关键点。// 从图像金字塔的当前层（level）中提取出一个特定的矩形区域，矩形区域的左上角坐标为 (iniX, iniY)，右下角坐标为 (maxX, maxY)。// 这代表了当前网格单元的区域。// iniThFAST这是FAST算法的初始阈值，用于决定是否将某个像素点作为关键点。// 将参数设置为 true 意味着在检测每个关键点时，算法不仅会确定其是否为关键点，还会计算出其强度。// 这可以帮助后续的特征描述和匹配过程选择更具代表性的特征点，提高整体性能和效果。FAST(mvImagePyramid[level].rowRange(iniY,maxY).colRange(iniX,maxX),vKeysCell,iniThFAST,true);// 调用FAST算法// 如果第一次检测到的关键点为空（即没有找到有效的关键点），则会使用较低的阈值进行第二次检测。if(vKeysCell.empty()){FAST(mvImagePyramid[level].rowRange(iniY,maxY).colRange(iniX,maxX),vKeysCell,minThFAST,true);}if(!vKeysCell.empty()){for(vector<cv::KeyPoint>::iterator vit=vKeysCell.begin(); vit!=vKeysCell.end();vit++)//迭代器指到vKeysCell.begin();{(*vit).pt.x+=j*wCell;(*vit).pt.y+=i*hCell;vToDistributeKeys.push_back(*vit);}}}}vector<KeyPoint> & keypoints = allKeypoints[level];keypoints.reserve(nfeatures);keypoints = DistributeOctTree(vToDistributeKeys, minBorderX, maxBorderX,minBorderY, maxBorderY,mnFeaturesPerLevel[level], level);const int scaledPatchSize = PATCH_SIZE*mvScaleFactor[level];// Add border to coordinates and scale informationconst int nkps = keypoints.size();for(int i=0; i<nkps ; i++){keypoints[i].pt.x+=minBorderX;keypoints[i].pt.y+=minBorderY;keypoints[i].octave=level;keypoints[i].size = scaledPatchSize;}}// compute orientationsfor (int level = 0; level < nlevels; ++level)computeOrientation(mvImagePyramid[level], allKeypoints[level], umax);
}