BOW Model

Bag-of-words model (BoW model) 最早出现在自然语言处理（Natural Language Processing）和信息检索（Information Retrieval）领域.。该模型忽略掉文本的语法和语序等要素，将其仅仅看作是若干个词汇的集合，文档中每个单词的出现都是独立的。BoW使用一组无序的单词(words)来表达一段文字或一个文档.。近年来，BoW模型被广泛应用于计算机视觉中，与应用于文本的BoW 类比，图像的特征（feature）被当作单词（Word）。

基于文本的BoW模型的一个简单例子如下： 首先给出两个简单的文本文档如下：

John likes to watch movies. Mary likes too.

John also likes to watch football games.

基于上述两个文档中出现的单词，构建如下一个词典 (dictionary)：

{"John": 1, "likes": 2,"to": 3, "watch": 4, "movies": 5,"also": 6, "football": 7, "games": 8,"Mary": 9, "too": 10}

上面的词典中包含10个单词, 每个单词有唯一的索引, 那么每个文本我们可以使用一个10维的向量来表示。如下：

[1, 2, 1, 1, 1, 0, 0, 0, 1, 1]

[1, 1, 1, 1, 0, 1, 1, 1, 0, 0]

该向量与原来文本中单词出现的顺序没有关系，而是词典中每个单词在文本中出现的频率。因此BoW模型可认为是一种统计直方图 (histogram)。

TF-IDF Model

TF-IDF（term frequency–inverse document frequency）是一种用于信息检索与数据挖掘的常用加权技术。TF意思是词频(Term Frequency)，IDF意思是逆文本频率指数(Inverse Document Frequency)。

TF-IDF是一种统计方法，用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度。字词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。TF-IDF加权的各种形式常被搜索引擎应用，作为文件与用户查询之间相关程度的度量或评级。除了TF-IDF以外，因特网上的搜索引擎还会使用基于链接分析的评级方法，以确定文件在搜寻结果中出现的顺序。

在一份给定的文件里，词频（term frequency，TF）指的是某一个给定的词语在该文件中出现的频率。这个数字是对词数(term count)的归一化，以防止它偏向长的文件。（同一个词语在长文件里可能会比短文件有更高的词数，而不管该词语重要与否。）对于在某一特定文件里的词语\(t_i\)来说，它的重要性可表示为：

\[ tf_{i,j} = \frac{n_{i,j}}{\sum_k n_{k,j}} \]

以上式子中\(n_{i,j}\)是该词\(t_i\)在文件\(d_j\)中的出现次数，而分母则是在文件\(d_j\)中所有字词的出现次数之和。

逆向文件频率（inverse document frequency，IDF）是一个词语普遍重要性的度量。某一特定词语的IDF，可以由总文件数目除以包含该词语之文件的数目，再将得到的商取对数得到：

\[ idf_i = log \frac{|D|}{|\{ j : t_i \in d_j \}|} \]

其中：

\(|D|\):语料库中的文件总数

\(|\{ j : t_i \in d_j \}|\): 包含词语\(t_i\)的文件数目（即\(n_{i, j} \neq 0\)的文件数目）如果该词语不在语料库中，就会导致被除数为零，因此一般情况下使用\(1 + |\{ j : t_i \in d_j \}|\)

然后

\[ tfidf_{i, j} = tf_{i,j} \times idf_i \]

某一特定文件内的高词语频率，以及该词语在整个文件集合中的低文件频率，可以产生出高权重的TF-IDF。因此，TF-IDF倾向于过滤掉常见的词语，保留重要的词语。

Place Recognition

(Reference: http://doriangalvez.com/papers/GalvezTRO12.pdf)

Build Vocabulary Tree

Extracting fast features and compute a BRIEF descriptor.

k-medians clustering(\(k_\omega\)binary clusters).

repeating this operation at subsequent levels.

repeating, we finally obtain a tree with W leaves.

Example

#include <iostream>
#include <stdlib.h>
#include <vector>
#include <DBoW3/DBoW3.h>
#include <opencv2/core/core.hpp>
#include <opencv2/highgui/highgui.hpp>
#include <opencv2/features2d/features2d.hpp>
#include <opencv2/xfeatures2d/nonfree.hpp>
#include <opencv2/xfeatures2d.hpp>
#include <DBoW3/DescManip.h>

bool training(std::string dataset_path, int dataset_size, std::string vocabulary)try
{
    std::vector<cv::Mat> images;
    std::vector<cv::Mat> descriptors;
    // read image
    std::cout << "reading image ..." << std::endl;
    for (auto pos = 0; pos < dataset_size; pos++) {
        char buffer[100];
        std::sprintf(buffer, "%s/%03d.png", dataset_path.c_str(), pos);
        images.push_back(cv::imread(buffer));
    }
    // orb
    std::cout << "orb detecting ..." << std::endl;
    auto orb = cv::ORB::create();
    for (auto &image : images) {
        if (image.empty()) {
            std::cout << "image is empty." << std::endl;
            continue;
        }
        std::vector<cv::KeyPoint> keypoints;
        cv::Mat descriptor;
        orb->detectAndCompute(image, cv::Mat(), keypoints, descriptor);
        descriptors.push_back(descriptor);
        cv::drawKeypoints(image, keypoints, image);
        cv::imshow("debug", image);
        cv::waitKey(150);
    }
    // create vocabulary 
    DBoW3::Vocabulary vocab;
    vocab.create(descriptors);
    std::cout << "vocabulary info: " << vocab << std::endl;
    if (vocab.empty()) {
        return false;
    }
    vocab.save(vocabulary);
    return true;
}
catch (const std::exception &exp) {
    std::cerr << exp.what() << std::endl;
    return false;
}
bool matching(std::string dataset_path, int dataset_size, std::string vocabulary)try
{
    DBoW3::Vocabulary vocab(vocabulary);
    if (vocab.empty()) {
        std::cerr << "vocabulary is empty." << std::endl;
        return false;
    }

    std::vector<cv::Mat> images;
    std::vector<cv::Mat> descriptors;
    // read image
    std::cout << "reading image ..." << std::endl;
    for (auto pos = 0; pos < dataset_size; pos++) {
        char buffer[100];
        std::sprintf(buffer, "%s/%03d.png", dataset_path.c_str(), pos);
        images.push_back(cv::imread(buffer));
    }
    // orb
    std::cout << "orb detecting ..." << std::endl;
    auto orb = cv::ORB::create();
    for (auto &image : images) {
        if (image.empty()) {
            std::cout << "image is empty." << std::endl;
            continue;
        }
        std::vector<cv::KeyPoint> keypoints;
        cv::Mat descriptor;
        orb->detectAndCompute(image, cv::Mat(), keypoints, descriptor);
        descriptors.push_back(descriptor);
        cv::drawKeypoints(image, keypoints, image);
        cv::imshow("debug", image);
        cv::waitKey(150);
    }

    std::cout << "comparing images with images " << std::endl;
    for (int pos = 0; pos < images.size(); pos++) {
        DBoW3::BowVector v1;
        vocab.transform(descriptors[pos], v1);
        for (int counter = pos; counter<images.size(); counter++)
        {
            DBoW3::BowVector v2;
            vocab.transform(descriptors[counter], v2);
            double score = vocab.score(v1, v2);
            std::cout << "image " << pos << " vs image " << counter << " : " << score << std::endl;
        }
        std::cout << std::endl;
    }

    std::cout << "comparing images with database " << std::endl;
    DBoW3::Database db(vocab, false, 0);
    for (int i = 0; i<descriptors.size(); i++)
        db.add(descriptors[i]);
    std::cout << "database info: " << db << std::endl;
    for (int i = 0; i<descriptors.size(); i++)
    {
        DBoW3::QueryResults ret;
        db.query(descriptors[i], ret, 4);      // max result=4
        std::cout << "searching for image " << i << " returns " << ret << std::endl << std::endl;
    }
    std::cout << "done." << std::endl;
    return true;
}
catch (const std::exception &exp) {
    std::cerr << exp.what() << std::endl;
    return false;
}

int main(int argc, const char **argv)
{
    try {
        if (argc != 4) {
            std::cout << argv[0] << "dataset_path dataset_size vocabulary." << std::endl;
            return -1;
        }
        if (!training(argv[1], atoi(argv[2]), argv[3])) {
            return -1;
        }
        if (!matching(argv[1], atoi(argv[2]), argv[3])) {
            return -1;
        }
    }
    catch (const std::exception &exp) {
        std::cerr << exp.what() << std::endl;
    }
#if defined(WIN32) || defined(WIN32_)
    ::system("pause");
#endif
    return 0;
}

---

Reference

https://en.wikipedia.org/wiki/Bag-of-words_model

Galvez-Lopez D, Tardos J D. Real-time loop detection with bags of binary words[C]// IEEE/RSJ International Conference on Intelligent Robots & Systems. 2011:51-58.

Galvez-López D, Tardos J D. Bags of Binary Words for Fast Place Recognition in Image Sequences[J]. IEEE Transactions on Robotics, 2012, 28(5):1188-1197.

https://baike.baidu.com/item/tf-idf/8816134?fr=aladdin

https://github.com/dorian3d/DBow

https://github.com/dorian3d/DBoW2

https://github.com/rmsalinas/DBow3

https://blog.csdn.net/qq_24893115/article/details/52629248

https://blog.csdn.net/wsj998689aa/article/details/47089153

https://mp.weixin.qq.com/s?__biz=MzI5MTM1MTQwMw==&mid=2247487947&idx=1&sn=a161d5ba005adabbfef23ee823c3f34b&chksm=ec10afcfdb6726d9460e3992357b93a50fb622a805c785a9322d7cafb6f8d7d0b02494206fbd&mpshare=1&scene=25&srcid=0120tujPrzQBRJvOMRlHZuAr&pass_ticket=DyCv5iDYNGzqu%2FG5eHjGG4I5gZSFV%2B4a6kb08nDUOcc%3D#wechat_redirect