ComputeKeyPointsOctTree是ORB特征提取器中計算關鍵點的部分，特別是使用八叉樹（OctTree）方法進行關鍵點分布。
首先，函數參數是vector<vector的引用allKeypoints，用來存儲各層的關鍵點。代碼開頭調整了allKeypoints的大小為nlevels，即金字塔層數。接下來，循環處理每一層圖像金字塔。
在循環內部，首先定義了邊界minBorderX和minBorderY，可能是為了避開邊緣區域，因為邊緣附近的關鍵點可能不完整。然后計算了maxBorderX和maxBorderY，確定當前層的有效區域。接著初始化vToDistributeKeys，預留空間用于存儲待分配的關鍵點。
然后根據寬度和高度劃分網格，每個網格大小為W（30）。這里計算了nCols和nRows，即網格的行列數。wCell和hCell是每個網格的實際大小，可能因為不能整除而向上取整。
接下來是雙重循環遍歷每個網格。對于每個網格，計算初始坐標iniY和iniX，以及最大坐標maxY和maxX。這里有一些條件判斷，確保網格不超過最大邊界。然后在每個網格內使用FAST算法檢測關鍵點，首先使用iniThFAST閾值，如果沒檢測到則改用minThFAST閾值。
檢測到關鍵點后，調整它們的坐標，加上網格的偏移量，并存入vToDistributeKeys。這一步是因為FAST檢測是在網格的子圖像上進行的，所以需要將坐標轉換回原圖的坐標。
之后，調用DistributeOctTree函數，將關鍵點按八叉樹分布，篩選出符合數量要求的關鍵點，并存入當前層的keypoints。這里可能涉及到關鍵點的均勻分布和響應值排序，確保每層的關鍵點數量符合mnFeaturesPerLevel的設置。
接著處理每個關鍵點的坐標，加上minBorderX和minBorderY的偏移，設置octave（金字塔層）和size（根據縮放因子調整的尺寸）。最后，循環結束后，計算每個關鍵點的方向，使用computeOrientation函數。
需要注意的是，代碼中的EDGE_THRESHOLD、mvImagePyramid、PATCH_SIZE、mvScaleFactor等變量可能在類的其他部分定義。此外，DistributeOctTree函數的具體實現細節會影響關鍵點的分布方式，可能涉及四叉樹分割和響應值篩選。
void ORBextractor::ComputeKeyPointsOctTree(vector<vector<KeyPoint> >& allKeypoints)
{allKeypoints.resize(nlevels);const float W = 30;for (int level = 0; level < nlevels; ++level){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);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;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)continue;if(maxX>maxBorderX)maxX = maxBorderX;vector<cv::KeyPoint> vKeysCell;FAST(mvImagePyramid[level].rowRange(iniY,maxY).colRange(iniX,maxX),vKeysCell,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++){(*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);
}以下是 ORBextractor::ComputeKeyPointsOctTree 函數的逐行解析及原理說明，結合 ORB 特征提取的算法設計與實現細節：
功能概述
該函數用于在圖像金字塔各層級上提取并均勻分布 ORB 特征點，通過分塊檢測 FAST 角點并結合四叉樹篩選策略，保證特征點分布的均勻性和尺度不變性。這是 ORB-SLAM 等視覺系統的核心步驟之一。
輸入與輸出
- 輸入：圖像金字塔
mvImagePyramid（通過高斯模糊生成的多尺度圖像集合）。 - 輸出：分層的關鍵點集合
allKeypoints，包含每個金字塔層級的關鍵點信息。
代碼解析
1. 分層處理圖像金字塔
allKeypoints.resize(nlevels);
for (int level = 0; level < nlevels; ++level) {// 各層參數初始化const int minBorderX = EDGE_THRESHOLD - 3;const int maxBorderX = mvImagePyramid[level].cols - EDGE_THRESHOLD + 3;// 類似處理Y方向
}
以下是代碼的逐行解析，結合ORB特征提取及圖像分塊處理邏輯：
代碼功能概述
該代碼段用于在圖像金字塔的指定層級上進行分塊FAST特征點檢測，并通過動態閾值調整和特征點再分配策略實現關鍵點的均勻分布，屬于ORB特征提取流程中的核心步驟。
行級解析
for(int i=0; i<levelRows; i++)
{// 計算當前行的起始Y坐標（考慮邊界擴展3像素）const float iniY = minBorderY + i*cellH - 3;iniYRow[i] = iniY; // 保存當前行的起始Y坐標// 處理最后一行的高度計算if(i == levelRows-1) {hY = maxBorderY + 3 - iniY; // 計算實際高度if(hY <= 0) continue; // 跳過無效行}float hX = cellW + 6; // 列的默認寬度（包含左右各3像素擴展）// 遍歷每一列for(int j=0; j<levelCols; j++) {float iniX;// 第一行初始化X坐標if(i == 0) {iniX = minBorderX + j*cellW - 3;iniXCol[j] = iniX; // 保存列的起始X坐標} else {iniX = iniXCol[j]; // 復用已保存的X坐標}// 處理最后一列的寬度計算if(j == levelCols-1) {hX = maxBorderX + 3 - iniX;if(hX <= 0) continue; // 跳過無效列}// 提取當前單元格圖像塊Mat cellImage = mvImagePyramid[level].rowRange(iniY, iniY+hY).colRange(iniX, iniX+hX);// 預分配內存（避免多次擴容）cellKeyPoints[i][j].reserve(nfeaturesCell * 5);// 使用初始閾值檢測FAST特征點（啟用非極大值抑制）FAST(cellImage, cellKeyPoints[i][j], iniThFAST, true);// 特征點不足時，改用最小閾值重新檢測if(cellKeyPoints[i][j].size() <= 3) {cellKeyPoints[i][j].clear();FAST(cellImage, cellKeyPoints[i][j], minThFAST, true);}// 統計當前單元格特征點數量const int nKeys = cellKeyPoints[i][j].size();nTotal[i][j] = nKeys; // 記錄實際特征點數// 判斷是否需要保留更多特征點if(nKeys > nfeaturesCell) {nToRetain[i][j] = nfeaturesCell; // 保留上限bNoMore[i][j] = false; // 標記可繼續分配} else {nToRetain[i][j] = nKeys; // 保留全部現有特征點nToDistribute += nfeaturesCell - nKeys; // 累計待分配數量bNoMore[i][j] = true; // 標記無法分配更多nNoMore++; // 統計無法分配的單元格數}}
}
關鍵設計原理
-
分塊策略
- 將圖像劃分為
levelRows×levelCols的網格，每個單元格獨立檢測特征點，確保空間均勻性。 - 邊界擴展3像素（
cellW+6和cellH+6），避免邊緣特征遺漏。
- 將圖像劃分為
-
動態閾值調整
- 初始閾值
iniThFAST檢測失敗時，改用更低閾值minThFAST，適應低紋理區域。
- 初始閾值
-
特征點再分配
- 通過
nToDistribute累計需要補充的特征點數，后續步驟可能通過非極大值抑制或四叉樹分割重新分配。
- 通過
-
內存優化
reserve(nfeaturesCell*5)預分配內存，減少動態擴容開銷。
應用場景
- ORB特征提取：用于SLAM（如ORB-SLAM3）、目標跟蹤等需要旋轉不變性和實時性的場景。
- 多尺度處理：
mvImagePyramid支持圖像金字塔，實現多尺度特征檢測。
性能優化點
- 復用坐標：首行初始化
iniXCol[j]，后續行直接復用，減少重復計算。 - 提前終止：
hY<=0或hX<=0時跳過無效區域，減少冗余計算。 - 并行潛力：分塊結構天然適合多線程處理（需注意線程安全）。
- 目的：遍歷金字塔的每一層（
nlevels），處理不同尺度的圖像。 - 邊界處理：
EDGE_THRESHOLD是特征點距圖像邊緣的最小距離，±3的調整用于擴展有效檢測區域，避免邊緣特征不穩定。
2. 網格分塊與FAST角點檢測
const float W = 30;
const int nCols = width / W; // 列方向分塊數
const int nRows = height / W; // 行方向分塊數for (int i = 0; i < nRows; i++) {for (int j = 0; j < nCols; j++) {// 定義當前網格的坐標范圍const float iniY = minBorderY + i * hCell;const float iniX = minBorderX + j * wCell;// 執行FAST角點檢測FAST(mvImagePyramid[level].rowRange(iniY, maxY).colRange(iniX, maxX),vKeysCell, iniThFAST, true);}
}
- 網格劃分：將當前金字塔層級的有效區域劃分為
30x30的網格，每個網格獨立檢測 FAST 角點，確保初步均勻性。 - FAST檢測優化：
- 使用兩種閾值（
iniThFAST和minThFAST），優先用高閾值檢測強角點，若失敗則改用低閾值，平衡特征點數量與質量。 - 檢測到的角點坐標需根據網格位置偏移，轉換為全局坐標（
(*vit).pt.x += j * wCell）。
- 使用兩種閾值（
3. 四叉樹篩選關鍵點
keypoints = DistributeOctTree(vToDistributeKeys, minBorderX, maxBorderX,minBorderY, maxBorderY, mnFeaturesPerLevel[level], level);
- 四叉樹算法：將初步檢測的角點（
vToDistributeKeys）按空間分布均勻性篩選，最終保留mnFeaturesPerLevel[level]個關鍵點。- 原理：遞歸將區域劃分為四個子節點，保留響應最強的角點，避免特征點聚集。
- 終止條件：當子節點中僅剩一個角點或達到預設特征數量時停止分割。
4. 關鍵點屬性設置
const int scaledPatchSize = PATCH_SIZE * mvScaleFactor[level];
keypoints[i].octave = level; // 所屬金字塔層級
keypoints[i].size = scaledPatchSize; // 特征點鄰域直徑（尺度自適應）
- 尺度不變性：
scaledPatchSize根據金字塔層級縮放，高層級特征點對應更大的鄰域，用于后續計算旋轉和描述子。 - 坐標修正：將篩選后的關鍵點坐標還原到原始圖像坐標系（
minBorderX/Y偏移）。
5. 計算關鍵點方向
computeOrientation(mvImagePyramid[level], allKeypoints[level], umax);
- 灰度質心法：通過計算圖像塊的一階矩（
m10和m01），確定關鍵點的主方向，實現旋轉不變性。 - 預計算參數
umax：用于加速圓形區域的像素采樣，確保方向計算的效率。
關鍵設計原理
-
多尺度處理：
- 通過圖像金字塔（
mvImagePyramid）實現尺度不變性，高層級檢測大尺度特征，低層級檢測細節。 - 特征點鄰域大小（
PATCH_SIZE）隨層級縮放，匹配圖像分辨率變化。
- 通過圖像金字塔（
-
均勻分布策略：
- 網格分塊：初步分塊檢測避免特征點過度集中。
- 四叉樹篩選：二次優化分布，保證每層特征數量與質量。
-
效率優化：
- FAST檢測加速：網格化檢測減少無效區域遍歷，雙閾值策略平衡速度與魯棒性。
- 預計算參數：如
umax和金字塔圖像，減少運行時計算量。
應用場景
- ORB-SLAM：用于實時特征提取與匹配，支撐相機位姿估計和地圖構建。
- 目標跟蹤：均勻分布的特征點提升匹配穩定性，減少誤匹配。
擴展說明
- 浮點坐標問題：盡管代碼中關鍵點坐標為整數，但在高層級金字塔中，坐標經縮放后可能為浮點數（如
mvScaleFactor作用）。 - 邊界與異常處理：依賴
EDGE_THRESHOLD避免越界，但未顯式處理極端情況（如全圖無角點），需前置步驟保證魯棒性。
以下是ORBextractor::ComputeKeyPointsOctTree函數的逐行注釋分析：
- 初始化多尺度關鍵點容器
allKeypoints.resize(nlevels); // 根據金字塔層數調整容器維度
const float W = 30; // 網格劃分基準寬度
- 金字塔層級遍歷
for (int level = 0; level < nlevels; ++level) {// 計算有效檢測區域邊界（EDGE_THRESHOLD通常取19像素）const int minBorderX = EDGE_THRESHOLD-3; // 左邊界留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); // 預分配10倍特征數空間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); // 實際網格高度
- 網格遍歷與FAST檢測
for(int i=0; i<nRows; i++) {const float iniY = minBorderY + i*hCell; // 網格起始Y坐標float maxY = iniY + hCell + 6; // 網格終止Y坐標（+6擴展檢測范圍）// 邊界溢出處理if(iniY >= maxBorderY-3) continue;if(maxY > maxBorderY) maxY = maxBorderY;for(int j=0; j<nCols; j++) {const float iniX = minBorderX + j*wCell; // 網格起始X坐標float maxX = iniX + wCell + 6; // 網格終止X坐標// 邊界溢出處理if(iniX >= maxBorderX-6) continue;if(maxX > maxBorderX) maxX = maxBorderX;
- 雙閾值FAST檢測策略
vector<cv::KeyPoint> vKeysCell;// 先使用初始閾值iniThFAST檢測FAST(mvImagePyramid[level].rowRange(iniY,maxY).colRange(iniX,maxX),vKeysCell, iniThFAST, true); // true表示使用非極大值抑制// 若未檢測到，改用更低閾值minThFASTif(vKeysCell.empty()) {FAST(mvImagePyramid[level].rowRange(iniY,maxY).colRange(iniX,maxX),vKeysCell, minThFAST, true);}
- 關鍵點坐標校正
if(!vKeysCell.empty()) {for(auto vit=vKeysCell.begin(); vit!=vKeysCell.end(); vit++) {(*vit).pt.x += j*wCell; // X坐標恢復全局坐標系(*vit).pt.y += i*hCell; // Y坐標恢復全局坐標系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];for(int i=0; i<keypoints.size(); i++) {keypoints[i].pt.x += minBorderX; // 補償初始偏移量keypoints[i].pt.y += minBorderY;keypoints[i].octave = level; // 記錄金字塔層級keypoints[i].size = scaledPatchSize; // 特征點鄰域直徑（尺度自適應）}
- 方向計算
// 對所有層關鍵點計算主方向for (int level = 0; level < nlevels; ++level)computeOrientation(mvImagePyramid[level], allKeypoints[level], umax);
}
核心設計解析：
- 網格化檢測：通過30x30網格劃分實現特征點初步均勻分布，避免特征聚集
- 雙閾值策略：先使用較高閾值(iniThFAST)確保質量，失敗后降閾值(minThFAST)保證數量
- 邊界緩沖：±3像素的邊界處理既避免越界，又保證邊緣特征的有效提取
- 坐標校正：將網格局部坐標轉換為金字塔層全局坐標，保持空間一致性
- 八叉樹分配：通過遞歸區域分割和響應值排序，實現特征點最優空間分布
- 尺度自適應：scaledPatchSize根據金字塔縮放系數調整鄰域大小，實現尺度不變性
注：EDGE_THRESHOLD的取值(通常為19)與ORB描述子計算相關，保證特征點周圍有足夠區域計算描述子。computeOrientation使用灰度質心法計算特征方向，umax為模式匹配預計算表。
)
