# DBoW2

## TemplatedVocabulary.h

### TemplatedVocabulary<TDescriptor,F>::transform()
將影像的特徵點轉為BowVector跟FeatureVector
在[Frame::ComputeBoW()](#Frame::ComputeBoW())中引用

#### 定義

void TemplatedVocabulary<TDescriptor,F>::transform(
     const std::vector<TDescriptor>& features,  //影像中所有的特徵點
     BowVector &v,        //輸出 BowVector
     FeatureVector &fv,   //輸出 FeatureVector
     int levelsup         //距離葉子的深度
     ) const

#### 函式流程
1. 將特徵點轉為葉節點的ID與權重
2. 將值存入到BowVector 和 FeatureVector
3. 歸一化

#### 流程詳解

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)    
{

1. 將特徵點轉為葉節點的ID與權重

    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對應的權重 
        // w is the idf value if TF_IDF, 1 if TF

        //  將當前描述子轉化為Word id， Word weight，節點所屬的父節點id（這裡的父節點不是葉子的上一層，它距離葉子深度為levelsup）
        transform(*fit, id, w, &nid, levelsup);

跳到[TemplatedVocabulary<TDescriptor,F>::transform()2](#TemplatedVocabulary<TDescriptor,F>::transform()2)

2. 將值存入到BowVector 和 FeatureVector

        if(w > 0) // not stopped
        { 
            // 如果Word 權重大於0，將其添加到BowVector 和 FeatureVector
            v.addWeight(id, w);
            fv.addFeature(nid, i_feature);
        }
    }

v.addWeight: 跳到[BowVector::addWeight()](#BowVector::addWeight())
fv.addFeature: 跳到[FeatureVector::addFeature()](#FeatureVector::addFeature())

3. 歸一化

    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;
    }
}
else // IDF || BINARY
{
    unsigned int i_feature = 0;
    for(fit = features.begin(); fit < features.end(); ++fit, ++i_feature)
    {
        WordId id;
        NodeId nid;
        WordValue w;
        // w is idf if IDF, or 1 if BINARY

        transform(*fit, id, w, &nid, levelsup);

        if(w > 0) // not stopped
        {
            v.addIfNotExist(id, w);
            fv.addFeature(nid, i_feature);
        }
    }
} // if m_weighting == ...

if(must) v.normalize(norm);

### TemplatedVocabulary<TDescriptor,F>::transform()2
將描述子轉換成word ID
在[TemplatedVocabulary<TDescriptor,F>::transform()](#TemplatedVocabulary<TDescriptor,F>::transform())中引用

#### 定義

void TemplatedVocabulary<TDescriptor,F>::transform(
    const TDescriptor &feature, //特徵描述子
    WordId &word_id,            //word id
    WordValue &weight,          //word 權重
    NodeId *nid,                //node id
    int levelsup                //離葉子的深度
    ) const

#### 函式流程
1. 計算當前節點下的子節點與描述子的距離
2. 確認節點是否在搜索層級下
3. 確認節點是否在葉子節點，不是就重複搜尋
4. 存取距離最小的 Word id 和 weight

#### 流程詳解

// 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;

1. 計算當前節點下的子節點與描述子的距離

do
{
    // 更新樹的深度
    ++current_level;
    
    // 取出當前節點所有子節點的id
    nodes = m_nodes[final_id].children;
    
    // 取子節點中第1個的id，用於後面距離比較的初始值
    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;
        }
    }

2. 確認節點是否在搜索層級下

    // 記錄當前描述子轉化為Word後所屬的 node id，它距離葉子深度為levelsup
    if(nid != NULL && current_level == nid_level)
        *nid = final_id;

3. 確認節點是否在葉子節點，不是就重複搜尋

} while( !m_nodes[final_id].isLeaf() );

4. 存取距離最小的 Word id 和 weight

// 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;

---

## BowVector.cpp

### BowVector::addWeight()
將權重加入 BowVector 裡
在[TemplatedVocabulary<TDescriptor,F>::transform()](#TemplatedVocabulary<TDescriptor,F>::transform())中引用

#### 定義

void BowVector::addWeight(WordId id, 
                          WordValue v)

#### 函式流程
1. 搜尋大於等於id的第一個值的位置
2. 更新權重

#### 流程詳解
1. 搜尋大於等於id的第一個值的位置

BowVector::iterator vit = this->lower_bound(id);

2. 更新權重

if(vit != this->end() && !(this->key_comp()(id, vit->first)))
{
    //如果id = vit->first，gji 說明是同一個word，權重更新
    vit->second += v;
}
else
{
    //如果word id不在BowVector中，就加入
    this->insert(vit, BowVector::value_type(id, v));
}

## FeatureVector::addFeature()
將描述子加入FeatureVector裡
在[TemplatedVocabulary<TDescriptor,F>::transform()](#TemplatedVocabulary<TDescriptor,F>::transform())中引用

#### 定義

void FeatureVector::addFeature(NodeId id,                 //id
                               unsigned int i_feature)    //特徵的索引

#### 函式流程
1. 搜尋大於等於id的第一個值的位置
2. 更新特徵點

#### 流程詳解
1. 搜尋大於等於id的第一個值的位置

 FeatureVector::iterator vit = this->lower_bound(id);

2. 更新特徵點

  // 將同樣node id下的特徵點索引值放在一個向量裡
  if(vit != this->end() && vit->first == id)
  {
    // 如果這個node id已經創建，可以直接插入特徵點索引
    vit->second.push_back(i_feature);
  }
  else
  {
    // 如果這個node id還未創建，創建後再插入特徵點索引
    vit = this->insert(vit, FeatureVector::value_type(id, 
      std::vector<unsigned int>() ));
    vit->second.push_back(i_feature);
  }