一、單目初始化中的特征匹配SearchForInitialization

二、跟蹤（TrackwithModel）

TrackReferenceKeyFrame

三、詞袋介紹BoW

1、直觀理解詞袋

2、詞袋基本思想

3、從字典結構到k-d樹

K-means聚類

4、相似度計算TF-IDF

5、總結詞袋模型

四、詞袋大概流程

倍訓檢測：

加速匹配

如何制作、生成BoW？為什么 BOW一般用 BRIEF描述子？

速度方面

在精度方面

可視化效果

離線訓練 vocabulary tree（也稱為字典）

在線影像生成BoW向量

原始碼決議

理解詞袋向量BowVector

理解特征向量FeatureVector

詞典樹的保存和加載

一、單目初始化中的特征匹配SearchForInitialization

計算描述子的距離（漢明距離）距離最短則為匹配點

1、匹配點要大于100才能進行初始化

如上圖所示，找出第二張圖片中對應第一張圖片的特征點，并在特征點周圍以100為半徑，做一個框框，在這個范圍里面找符合要求的特征點，

快速匹配和候選特征點GetFeaturesInArea

2、挑選出來的特征點所屬金字塔必須為第0層

3、剔除那些在所選格子內但是不在搜索范圍內的點

4、最優距離要小于50，計算最優距離和最次距離的比值

5、統計匹配點方向的直方圖

計算第一張圖片FAST特征點方向和第二張圖片FAST特征點方向，并將第一張特征點的方向向量移動到第二張圖片上面，計算兩個方向向量的角度，做一個直方圖，

6、統計特征點數量最多的三個方向

7、判斷第二多的數量＜0.1第一多的數量，符合則證明第一多為主方向

8、判斷第三多的數量＜0.1第一多的數量，符合則證明第一多和第二多的主方向

二、跟蹤（TrackwithModel）

根據勻速模型來計算初始位姿，然后通過投影的形式搜索匹配點

TrackReferenceKeyFrame

1、前面EPnP得到的內容將不再進行跟蹤搜索

2、這里需要估計關鍵幀地圖點在當前在幀影像金字塔的層數

影像金字塔的層數怎么的來：通過地圖點離相機光心的距離計算而來

3、和前面的seachByProjection類似，將關鍵幀地圖點投影到當前幀，然后在一定范圍內搜索

三、詞袋介紹BoW

1、直觀理解詞袋

如何找到匹配的影像

特征匹配

不同的光照強度都會有影響，而且匹配時間較長

詞袋模型（BoW）

2、詞袋基本思想

從單詞概念引入基本思想

如何定量描述

$s(a,b)=1-\frac{1}{W}\left \| a-b \right \|_{1}$

s---評分計算函式

a&b----二進制向量

W---向量維度

1---向量L1范數，各元素絕對值之和

由此定義了描述向量的相似性，即影像的相似程度

3、從字典結構到k-d樹

k：每層的節點數為k

d：數結構一共有d 層

單詞：區域相鄰特征點的集合

功能：把圖片中所有的行人歸到人這個類中

字典：具有一定結構的單詞索引，從大量圖片訓練而來

那么有了一個特征點，如何找到匹配的單詞

從字典結構到K-d樹（兩種索引方式）

K-means聚類

1、首先隨機生成K個聚類中心點

2、根據聚類中心點，將資料分為K類，分類原則是資料離哪個中心點近就將它分為哪一類

3、再根據分好的類別資料，重新計算聚類的類別中心點

4、不斷的重復2和3步，直到中心點不再變化

注：剛開始生成的中心點不同對后面也會有不同的影響

4、相似度計算TF-IDF

TF：某單詞在一副影像中出現的頻率越高，該單詞就更具代表性

IDF：某單詞在字典中出現的頻率越低，就說明該單詞在字典中更具有代表性

圖片維度

$TF_{i}=\frac{n_{i}}{n}$

字典維度

$IDF_{i}=lg\frac{n}{n_{i}}$

權重

$\eta _{i}=TF_{i}\times IDF_{i}$

相似度計算 BoW向量（bog of words）

BoW向量組成如下，兩元素分別為單詞和權重

$A=\left [ \left ( \omega _{1} ,\eta _{1}\right ),\left (\omega _{2} ,\eta _{2}\right ) ... \left (\omega _{N} ,\eta _{N}\right )\right ]=v_{A}$

該向量描述了一張影像，包含影像中有哪些單詞，以及對應的權重是多少，進而，通過人為規定范數的形式，就能夠計算出兩張圖片的相似程度

5、總結詞袋模型

step1、從大量的圖片中提取特征采用聚類法生成單詞構建字典

step2、處理某一幀圖片，采用TF-IDF計算單詞權重

step3、生成該幀的BoW向量，更新正向索引和倒排索引的內容

生成BoW向量就是圖片的新名片，可以用來回環檢測、匹配影像、優化位姿、尋找特征點等

四、詞袋大概流程

為什么叫 bag of words 而不是 list of words 或者 array of words？

因為丟棄了Word出現的排列順序、位置等因素，只考慮出現的頻率，大大簡化了表達，節省了存盤空間，在分析對比相似度的時候非常高效

倍訓檢測：

核心就是判斷兩張圖片是否是同一個場景，也就是判斷影像的相似性，

如何計算兩張圖片的相似性

Bag of words 可以解決這個問題，是以影像特征集合作為visual words，只關心影像中有沒有這些 words，有多少次，更符合人類認知方式，對不同光照、視角變換、季節更替等非常魯棒，

加速匹配

ORB-SLAM2代碼中使用的 SearchByBoW（用于關鍵幀跟蹤、重定位、倍訓檢測SIM3計算），以及區域地圖里的SearchForTriangulation，內部實作主要是利用了 BoW中的FeatureVector 來加速特征匹配，

使用FeatureVector 避免了所有特征點的兩兩匹配，只比較同一個節點下的特征點，極大加速了匹配效率，至于匹配精度，論文《Bags of Binary Words for Fast Place Recognition in Image Sequences 》中提到在26292 張圖片里的 false positive 為0，說明精度是有保證的，實際應用中效果非常不錯，

缺點

需要提前加載離線訓練好的詞袋字典，增加了存盤空間，但是帶來的優勢遠大于劣勢，而且也有不少改進方法比如用二進制存盤等來壓縮詞袋，減少存盤空間，提升加載速度，

如何制作、生成BoW？為什么 BOW一般用 BRIEF描述子？

速度方面

因為計算和匹配都非常快，論文中說大概一個關鍵點計算256位的描述子只需要 17.3μs 因為都是二進制描述子，距離描述通過漢明距離，使用異或操作即可，速度非常快，而SIFT, SURF 描述子都是浮點型，需要計算歐式距離，會慢很多，

在Intel Core i7 ，2.67GHz CPU上，使用FAST+BRIEF 特征，在26300幀影像中特征提取+詞袋位置識別耗時 22ms 每幀，

在精度方面

先上結論：倍訓效果并不比SIFT, SURF之類的高精度特征點差，

具體來看一下對比：以下對比來自論文《2012，Bags of Binary Words for Fast Place Recognition in Image Sequences， IEEE TRANSACTIONS ON ROBOTICS》

三種描述子 BRIEF,，SURF64 ，U-SURF128 使用同樣的引數，在訓練資料集NewCollege，Bicocca25b 上的 Precision-recall 曲線

其中SURF64：帶旋轉不變性的 64 維描述子

U-SURF128：不帶旋轉不變性的128維描述子

在兩個資料中，SURF64 都明顯比 U-SURF128 表現的好（曲線下面積更大），可以看到在Bicocca25b 資料集上，BRIEF明顯比 U-SURF128 好，比SURF64 也稍微好一些，在NewCollege 資料集上 SURF64 比 BRIEF 更好一點，但是BRIEF也仍然不錯，

總之，BRIEF 和 SURF64 效果基本相差不大，可以說打個平手，

可視化效果

可視化看一下效果

下圖左邊圖片對是BRIEF 在vocabulary 中同樣的Word下的回環匹配結果，同樣的特征連成了一條線，

下圖右邊影像對是同樣資料集中SURF64 的倍訓匹配結果，

第一行來看，盡管有一定視角變換，BRIEF 和 SURF64 的匹配結果接近

第二行：BRIEF成功進行了倍訓，但是SURF64 沒有倍訓，原因是SURF64 沒有得到足夠多的匹配關系，

第三行：BRIEF 倍訓失敗而SURF64倍訓成功，

我們分析一下原因：主要和近景遠景有關，因為BRIEF相比SURF64沒有尺度不變性，所以在尺度變換較大的近景很容易匹配失敗，比如第三行，而在中景和遠景，由于尺度變化不大，BRIEF 表現接近甚至優于SURF64

不過，我們通過影像金字塔可以解決上述BRIEF的尺度問題，論文中作者也提到了ORB + BRIEF的特征點主要問題是沒有旋轉不變性和尺度不變性，不過目前都解決了，

總之，BRIEF的倍訓效果值得信賴！

離線訓練 vocabulary tree（也稱為字典）

首先影像提取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，訓練集里出現的次數越多，說明辨別力越差，給與的權重越低，

在線影像生成BoW向量

1、對新來的一幀影像進行ORB特征提取，得到一定數量（一般幾百個）的特征點，描述子維度和 vocabulary tree中的一致

2、對于每個特征點的描述子，從離線創建好的vocabulary tree中開始找自己的位置，從根節點開始，用該描述子和每個節點的描述子計算漢明距離，選擇漢明距離最小的作為自己所在的節點，一直遍歷到葉子節點，

整個程序是這樣的，見下圖，紫色的線表示一個特征點從根節點到葉子節點的程序，

原始碼決議

一個描述子轉化為Word id， Word weight，節點所屬的父節點（距離葉子深度為level up深度的節點） id 對應的實作代碼見：

/**
* @brief 將描述子轉化為Word id， Word weight，節點所屬的父節點id（這里的父節點不是葉子的上
一層，它距離葉子深度為levelsup）
* @tparam TDescriptor
* @tparam F
* @param[in] feature 特征描述子
* @param[in & out] word_id Word id
* @param[in & out] weight Word 權重
* @param[in & out] nid 記錄當前描述子轉化為Word后所屬的 node id，它距離
葉子深度為levelsup
* @param[in] levelsup 距離葉子的深度
*/
template<class TDescriptor, class F>
void TemplatedVocabulary<TDescriptor,F>::transform(const TDescriptor &feature,
WordId &word_id, WordValue &weight, NodeId *nid, int levelsup) const
{
// propagate the feature down the tree
vector<NodeId> nodes;
typename vector<NodeId>::const_iterator nit;
// level at which the node must be stored in nid, if given
// m_L: depth levels, m_L = 6 in ORB-SLAM2
// nid_level 當前特征點轉化為的Word 所屬的 node id，方便索引
const int nid_level = m_L - levelsup;
if(nid_level <= 0 && nid != NULL) *nid = 0; // root
NodeId final_id = 0; // root
int current_level = 0;
do
{
++current_level;
nodes = m_nodes[final_id].children;
final_id = nodes[0];
// 取當前節點第一個子節點的描述子距離初始化最佳（小）距離
double best_d = F::distance(feature, m_nodes[final_id].descriptor);
// 遍歷nodes中所有的描述子，找到最小距離對應的描述子
for(nit = nodes.begin() + 1; nit != nodes.end(); ++nit)
{
NodeId id = *nit;
double d = F::distance(feature, m_nodes[id].descriptor);
if(d < best_d)
{
best_d = d;
final_id = id;
}
}
// 記錄當前描述子轉化為Word后所屬的 node id，它距離葉子深度為levelsup
if(nid != NULL && current_level == nid_level)
*nid = final_id;
} while( !m_nodes[final_id].isLeaf() );
// turn node id into word id
// 取出 vocabulary tree中node距離當前feature 描述子距離最小的那個node的 Word id 和
weight
word_id = m_nodes[final_id].word_id;
weight = m_nodes[final_id].weight;
}

一幅影像里所有特征點轉化為兩個std::map容器 BowVector 和 FeatureVector 的代碼見：

/**
* @brief 將一幅影像所有的特征點轉化為BowVector和FeatureVector
*
* @tparam TDescriptor
* @tparam F
* @param[in] features 影像中所有的特征點
* @param[in & out] v BowVector
* @param[in & out] fv FeatureVector
* @param[in] levelsup 距離葉子的深度
*/
template<class TDescriptor, class F>
void TemplatedVocabulary<TDescriptor,F>::transform(
  const std::vector<TDescriptor>& features,
  BowVector &v, FeatureVector &fv, int levelsup) const
{
  v.clear();
  fv.clear();
  if(empty()) // safe for subclasses
  {
    return;
  }
// normalize
// 根據選擇的評分型別來確定是否需要將BowVector 歸一化
LNorm norm;
bool must = m_scoring_object->mustNormalize(norm);
typename vector<TDescriptor>::const_iterator fit;
if(m_weighting == TF || m_weighting == TF_IDF)
{
  unsigned int i_feature = 0;
  // 遍歷影像中所有的特征點
  for(fit = features.begin(); fit < features.end(); ++fit, ++i_feature)
  {
    WordId id; // 葉子節點的Word id
    NodeId nid; // FeatureVector 里的NodeId，用于加速搜索
    WordValue w; // 葉子節點Word對應的權重
   // 將當前描述子轉化為Word id， Word weight，節點所屬的父節點id（這里的父節點不是葉的上一層，它距離葉子深度為levelsup）
   // w is the idf value if TF_IDF, 1 if TF
   transform(*fit, id, w, &nid, levelsup);
   if(w > 0) // not stopped
   {
   // 如果Word 權重大于0，將其添加到BowVector 和 FeatureVector
   v.addWeight(id, w);
   fv.addFeature(nid, i_feature);
   }
 }
  if(!v.empty() && !must)
  {
    // unnecessary when normalizing
    const double nd = v.size();
    for(BowVector::iterator vit = v.begin(); vit != v.end(); vit++)
       vit->second /= nd;
  }
 }
// 省略掉了IDF || BINARY情況的代碼
if(must) v.normalize(norm);
}

相當于將當前影像資訊進行了壓縮，并且對后面特征點快速匹配、倍訓檢測、重定位意義重大，這兩個容器非常重要，下面一個個來解釋：

理解詞袋向量BowVector

它內部實際存盤的是這個

std::map<WordId,Woedvalue>

其中 WordId 和 WordValue 表示Word在所有葉子中距離最近的葉子的id 和權重（后面解釋），同一個Word id 的權重是累加更新的，見代碼

void BowVector::addWeight(WordId id, WordValue v)
{
  // 回傳指向大于等于id的第一個值的位置
  BowVector::iterator vit = this->lower_bound(id);
  // http://www.cplusplus.com/reference/map/map/key_comp/
  if(vit != this->end() && !(this->key_comp()(id, vit->first)))
  {
  // 如果id = vit->first, 說明是同一個Word，權重更新
  vit->second += v;
  }
  else
  {
  // 如果該Word id不在BowVector中，新添加進來
  this->insert(vit, BowVector::value_type(id, v));
  }
}

理解特征向量FeatureVector

內部實際是個

std::map <Nodeid,std:;vector<unsigned int>>

其中NodeId 并不是該葉子節點直接的父節點id，而是距離葉子節點深度為level up對應的node 的id，對應上面 vocabulary tree 圖示里的 Word's node id，為什么不直接設定為父節點？因為后面搜索該 Word 的匹配點的時候是在和它具有同樣node id下面所有子節點中的Word 進行匹配，搜索區域見圖示中的 Word's search region，所以搜索范圍大小是根據level up來確定的，level up 值越大，搜索范圍越廣，速度越慢；level up 值越小，搜索范圍越小，速度越快，但能夠匹配的特征就越少，另外 std::vector 中實際存的是NodeId 下所有特征點在影像中的索引，見代碼

void FeatureVector::addFeature(NodeId id, unsigned int i_feature)
{
  FeatureVector::iterator vit = this->lower_bound(id);
  // 將同樣node id下的特征放在一個vector里
  if(vit != this->end() && vit->first == id)
  {
  vit->second.push_back(i_feature);
  }
  else
  {
   vit = this->insert(vit, FeatureVector::value_type(id,
     std::vector<unsigned int>() ));
   vit->second.push_back(i_feature);
 }
}

FeatureVector主要用于不同影像特征點快速匹配，加速幾何關系驗證，比如 ORBmatcher::SearchByBoW 中是這樣用的

DBoW2::FeatureVector::const_iterator f1it = vFeatVec1.begin();
DBoW2::FeatureVector::const_iterator f2it = vFeatVec2.begin();
DBoW2::FeatureVector::const_iterator f1end = vFeatVec1.end();
DBoW2::FeatureVector::const_iterator f2end = vFeatVec2.end();
while(f1it != f1end && f2it != f2end)
{
    // Step 1：分別取出屬于同一node的ORB特征點(只有屬于同一node，才有可能是匹配點)
    if(f1it->first == f2it->first)
       // Step 2：遍歷KF中屬于該node的特征點
       for(size_t i1=0, iend1=f1it->second.size(); i1<iend1; i1++)
       {
          const size_t idx1 = f1it->second[i1];
          MapPoint* pMP1 = vpMapPoints1[idx1];
          // 省略
          // ..........

詞典樹的保存和加載

我們將 vocabulary tree翻譯為詞典樹

如何保存訓練好的詞典樹存盤為txt檔案？

template<class TDescriptor, class F>
void TemplatedVocabulary<TDescriptor,F>::saveToTextFile(const std::string
&filename) const
{
   fstream f;
   f.open(filename.c_str(),ios_base::out);
   // 第一行列印 樹的分支數、深度、評分方式、權重計算方式
   f << m_k << " " << m_L << " " << " " << m_scoring << " " << m_weighting <<
endl;
   for(size_t i=1; i<m_nodes.size();i++)
   {
      const Node& node = m_nodes[i];
      // 每行第1個數字為父節點id
      f << node.parent << " ";
      // 每行第2個數字標記是（1）否（0）為葉子（Word）
      if(node.isLeaf())
        f << 1 << " ";
      else
        f << 0 << " ";
      // 接下來存盤256位描述子，最后存盤節點權重
      f << F::toString(node.descriptor) << " " << (double)node.weight << endl;
     }
     f.close();
}

如何加載訓練好的詞典樹檔案？

/**
* @brief 加載訓練好的 vocabulary tree，txt格式
*
* @tparam TDescriptor
* @tparam F
* @param[in] filename vocabulary tree 檔案名稱
* @return true 加載成功
* @return false 加載失敗
*/
template<class TDescriptor, class F>
bool TemplatedVocabulary<TDescriptor,F>::loadFromTextFile(const std::string
&filename)
{
ifstream f;
f.open(filename.c_str());
if(f.eof())
return false;
m_words.clear();
m_nodes.clear();
string s;
getline(f,s);
stringstream ss;
ss << s;
ss >> m_k; // 樹的分支數目
ss >> m_L; // 樹的深度
int n1, n2;
ss >> n1;
ss >> n2;
   if(m_k<0 || m_k>20 || m_L<1 || m_L>10 || n1<0 || n1>5 || n2<0 || n2>3)
   {
   std::cerr << "Vocabulary loading failure: This is not a correct text
   file!" << endl;
   return false;
   }
m_scoring = (ScoringType)n1; // 評分型別
m_weighting = (WeightingType)n2; // 權重型別
createScoringObject();
// 總共節點（nodes）數，是一個等比數列求和
//! bug 沒有包含最后葉子節點數，應該改為 ((pow((double)m_k, (double)m_L + 2) -
1)/(m_k - 1))
//! 但是沒有影響，因為這里只是reserve，實際存盤是一步步resize實作
int expected_nodes =
(int)((pow((double)m_k, (double)m_L + 1) - 1)/(m_k - 1));
m_nodes.reserve(expected_nodes);
// 預分配空間給 單詞（葉子）數
m_words.reserve(pow((double)m_k, (double)m_L + 1));
// 第一個節點是根節點，id設為0
m_nodes.resize(1);
m_nodes[0].id = 0;
while(!f.eof())
{
string snode;
getline(f,snode);
stringstream ssnode;
ssnode << snode;
// nid 表示當前節點id，實際是讀取順序，從0開始
int nid = m_nodes.size();
// 節點size 加1
m_nodes.resize(m_nodes.size()+1);
m_nodes[nid].id = nid;
// 讀每行的第1個數字，表示父節點id
int pid ;
ssnode >> pid;
// 記錄節點id的相互父子關系
m_nodes[nid].parent = pid;
m_nodes[pid].children.push_back(nid);
// 讀取第2個數字，表示是否是葉子（Word）
int nIsLeaf;
ssnode >> nIsLeaf;
// 每個特征點描述子是256 bit，一個位元組對應8 bit，所以一個特征點需要32個位元組存盤，
// 這里 F::L=32，也就是讀取32個位元組，最后以字串形式存盤在ssd
stringstream ssd;
for(int iD=0;iD<F::L;iD++)
{
string sElement;
ssnode >> sElement;
ssd << sElement << " ";
}
// 將ssd存盤在該節點的描述子
F::fromString(m_nodes[nid].descriptor, ssd.str())
// 讀取最后一個數字：節點的權重（Word才有）
ssnode >> m_nodes[nid].weight;
if(nIsLeaf>0)
{
// 如果是葉子（Word），存盤到m_words
int wid = m_words.size();
m_words.resize(wid+1);
//存盤Word的id，具有唯一性
m_nodes[nid].word_id = wid;
//構建 vector<Node*> m_words，存盤word所在node的指標
m_words[wid] = &m_nodes[nid];
}
else
{
//非葉子節點，直接分配 m_k個分支
m_nodes[nid].children.reserve(m_k);
}
}
return true;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/325430.html

標籤：AI

上一篇：數學建模常用功能

下一篇：計算機視覺可解釋性——卷積神經網路中間層的可視化

ORB_SLAM2 原始碼決議 特征匹配 （五）

一、單目初始化中的特征匹配SearchForInitialization

二、跟蹤（TrackwithModel）

TrackReferenceKeyFrame

三、詞袋介紹BoW

1、直觀理解詞袋

2、詞袋基本思想

3、從字典結構到k-d樹

K-means聚類

4、相似度計算TF-IDF

5、總結詞袋模型

四、詞袋大概流程

倍訓檢測：

加速匹配

如何制作、生成BoW？ 為什么 BOW一般用 BRIEF描述子？

速度方面

在精度方面

可視化效果

離線訓練 vocabulary tree（也稱為字典）

在線影像生成BoW向量

原始碼決議

理解詞袋向量BowVector

理解特征向量FeatureVector

詞典樹的保存和加載

ORB_SLAM2 原始碼決議特征匹配（五）

如何制作、生成BoW？為什么 BOW一般用 BRIEF描述子？