TF-IDF

TF-IDF是一種用于信息檢索的常用加權(quán)技術(shù)，在文本檢索中，用以評估詞語對于一個(gè)文件數(shù)據(jù)庫中的其中一份文件的重要程度。詞語的重要性隨著它在文件中出現(xiàn)的頻率成正比增加，但同時(shí)會(huì)隨著它在文件數(shù)據(jù)庫中出現(xiàn)的頻率成反比下降。像‘的'，‘我們'，‘地'等這些常用詞在所有文章中出現(xiàn)的頻率會(huì)很高，并不能很好的表征一個(gè)文檔的內(nèi)容。

同樣的在圖像檢索中也引入了IF-IDF權(quán)重，

詞頻(Term Frequency,TF) 一個(gè)visual word在一個(gè)圖像中出現(xiàn)的頻率的很高，則說明該visual word 能夠很好的代表圖像的內(nèi)容。

逆文檔詞頻(Inverse Document Frequency，IDF) 一些常見的word，會(huì)在每一圖像出現(xiàn)的頻率都很高，但是這些word并不能很好的表示圖像的內(nèi)容，所以要給這一部分word低一些的權(quán)重。IDF，描述一個(gè)word的普遍重要性，如古歐word在很多的圖像中出現(xiàn)的頻率都很高，則給予其較低的權(quán)重。

將分母+1是為了防止除數(shù)為0的情況出現(xiàn)。從上式中可以看出，包含當(dāng)前word的圖像個(gè)數(shù)越多，IDF的值越小，說明該詞越不重要。反之，該詞越重要。

計(jì)算得到了TF和IDF，則有

\[TF-IDF = TF * IDF\]

從TF和IDF的計(jì)算公式可以看出，IDF是針對整個(gè)圖像數(shù)據(jù)庫而言的，可以在訓(xùn)練完成后計(jì)算一次得到。而TF則是針對具體的某張圖像來說的，需要多次計(jì)算。

將TF-IDF權(quán)值賦給BoW向量,再進(jìn)行\(zhòng)(l_2\)的歸一化，即可得到一個(gè)可用于圖像檢索的向量。

C++實(shí)現(xiàn)

void compute_idf(const vector<<vector<int>> &bow,vector<float> &idf){

    int img_count = bow.size();
    int clu_count = bow[0].size();

    idf = vector<float>(clu_count,1.0);

    for(int i = 0; i < img_count; i ++){
        for(int j = 0; j < clu_count; j ++){
            if(bow[i][j] != 0) idf[j] ++;
        }
    }

    for(int i = 0; i < idf.size(); i ++){
        idf[i] = log(img_count / idf[i]);
    }
}

上面代碼計(jì)算的是圖像庫的IDF（IDF是針對整個(gè)圖像庫而言的）。
針對某一張圖片，都需要計(jì)算一次TF。TF的計(jì)算公式：，可以看著是對圖像的BoW向量進(jìn)行\(zhòng)(l_1\)的歸一化。

void compute_tf(const vector<int> &bow,vector<float> &tf){

    tf = vector<float>(bow.size(),0);

    int sum = 0; // All words in the image
    for(int i = 0; i < bow.size(); i ++){
        sum += bow[i];
    }

    for(int i = 0; i < bow.size(); i ++){
        tf[i] = (float)bow[i] / sum; 
    }
}

RootSift

在Arandjelovic和Zisserman 2012的論文 Three things everyone should know to improve object retrieval 提出了RootSift。

當(dāng)比較直方圖時(shí)，使用歐氏距離通常比卡方距離或Hellinger核時(shí)的性能差，但是在使用sift特征點(diǎn)為什么一直都使用歐氏距離呢？
不論是對sift特征點(diǎn)進(jìn)行匹配，還是對sift特征集合進(jìn)行聚類得到視覺詞匯表，又或者對圖像進(jìn)行BoW編碼，都使用的是歐氏距離。但是sift特征描述子本質(zhì)上也是一種直方圖，為什么對sift特征描述子進(jìn)行比較的時(shí)候要使用歐氏距離呢，有沒有一種更精確的比較方法呢？

sift描述子統(tǒng)計(jì)的是關(guān)鍵點(diǎn)鄰域的梯度直方圖，更詳細(xì)的介紹可以參考圖像檢索(1): 再論SIFT-基于vlfeat實(shí)現(xiàn)

Zisserman 認(rèn)為只所以一直使用歐氏距離來測量sift特征的相似度，是由于在sift提出的時(shí)候，使用的是歐氏距離的度量，可以找出一種比較歐氏距離更為精確的度量方法。Arandjelovic和Zisserman提出了RootSift對sift特征進(jìn)行擴(kuò)展。

在提取得到sift的描述向量\(x\)后，進(jìn)行以下處理，即可得到RootSift
1.對特征向量\(x\)進(jìn)行\(zhòng)(l_1\)的歸一化(\(l_1-normalize\))得到\(x'\)
2.對\(x'\)的每一個(gè)元素求平方根
3.進(jìn)行\(zhòng)(l_2-normalize\)，可選

最后一步，是否進(jìn)行\(zhòng)(l_2\)的歸一化，有些不一致。 在paper 并沒有指出需要進(jìn)行\(zhòng)(l_2\)的歸一化，但是在presentation, 卻有\(zhòng)(l_2\)歸一化這一步。也有認(rèn)為，顯式地執(zhí)行L2規(guī)范化是不需要的。通過采用L1規(guī)范，然后是平方根，已經(jīng)有L2標(biāo)準(zhǔn)化的特征向量，不需要進(jìn)一步的標(biāo)準(zhǔn)化。

Python實(shí)現(xiàn)

# import the necessary packages
import numpy as np
import cv2

class RootSIFT:
    def __init__(self):
        # initialize the SIFT feature extractor
        self.extractor = cv2.DescriptorExtractor_create("SIFT")

    def compute(self, image, kps, eps=1e-7):
        # compute SIFT descriptors
        (kps, descs) = self.extractor.compute(image, kps)

        # if there are no keypoints or descriptors, return an empty tuple
        if len(kps) == 0:
            return ([], None)

        # apply the Hellinger kernel by first L1-normalizing and taking the
        # square-root
        descs /= (descs.sum(axis=1, keepdims=True) + eps)
        descs = np.sqrt(descs)
        #descs /= (np.linalg.norm(descs, axis=1, ord=2) + eps)

        # return a tuple of the keypoints and descriptors
        return (kps, descs)

來自 https://www.pyimagesearch.com/2015/04/13/implementing-rootsift-in-python-and-opencv/

C++ 實(shí)現(xiàn)

for(int i = 0; i < siftFeature.rows; i ++){
        // Conver to float type
        Mat f;
        siftFeature.row(i).convertTo(f,CV_32FC1);

        normalize(f,f,1,0,NORM_L1); // l1 normalize
        sqrt(f,f); // sqrt-root  root-sift
        rootSiftFeature.push_back(f);
    }

VLAD

局部聚合向量（Vector of Locally Aggregated Descriptors，VLAD）

前面介紹的BoW方法，在圖像的檢索和檢索中有這廣泛的應(yīng)用。BoW通過聚類，對圖像的局部特征進(jìn)行重新編碼，有很強(qiáng)的表示能力，并且使用SVM這樣基于樣本間隔的分類器，也能取得了很好的分類效果。但是在圖像規(guī)模比較大的情況下，由于視覺詞匯表Vocabulary大小的限制，BoW對圖像的表示會(huì)越來越粗糙，編碼后損失的圖像信息較多，檢索精度也隨之而降低。

2010年，論文Aggregating local descriptors into a compact image representation中提出了一對新的圖像表示方法，VLAD。從三個(gè)方面進(jìn)行改進(jìn)：

• 使用VLAD表示圖像的局部特征
• PCA
• 索引ADC的構(gòu)建方法

BoW的表示方法中，是統(tǒng)計(jì)每個(gè)特征詞匯在圖像中出現(xiàn)的頻率。VLAD則是求落在同一個(gè)聚類中心的特征和該聚類中心殘差的累加和。公式表示如下：

由于，VLAD是特征和其最鄰近的聚類中心的殘差和，該向量的很多分量很多分量都為０，也就是說該向量是稀疏的（sparse,很少的分量占有大部分的能量），所以可以對VLAD進(jìn)行降維處理（例如，PCA）能進(jìn)一步縮小向量的大小。

void Vocabulary::transform_vlad(const cv::Mat &f,cv::Mat &vlad)
{
    // Find the nearest center
    Ptr<FlannBasedMatcher> matcher = FlannBasedMatcher::create();
    vector<DMatch> matches;
    matcher->match(f,m_voc,matches);


    // Compute vlad
    Mat responseHist(m_voc.rows,f.cols,CV_32FC1,Scalar::all(0));
    for( size_t i = 0; i < matches.size(); i++ ){
        auto queryIdx = matches[i].queryIdx;
        int trainIdx = matches[i].trainIdx; // cluster index
        Mat residual;
        subtract(f.row(queryIdx),m_voc.row(trainIdx),residual,noArray());
        add(responseHist.row(trainIdx),residual,responseHist.row(trainIdx),noArray(),responseHist.type());
    }

    // l2-norm
    auto l2 = norm(responseHist,NORM_L2);
    responseHist /= l2;
    //normalize(responseHist,responseHist,1,0,NORM_L2);

    //Mat vec(1,m_voc.rows * f.cols,CV_32FC1,Scalar::all(0));
    vlad = responseHist.reshape(0,1); // Reshape the matrix to 1 x (k*d) vector
}

借助于OpenCV實(shí)現(xiàn)還是比較簡單的。這里使用FlannBasedMatcher的match方法來查找特征最鄰近的聚類中心（視覺詞匯）。可以分為以下三步：

• subtract計(jì)算特征和其最近鄰的聚類中心的差值，add將同一個(gè)聚類中心的差值累加起來
• 對上面得到的矩陣的responseHist進(jìn)行\(zhòng)(l_2\)的歸一化處理
• 使用reshape方法，將矩陣?yán)鞛橐痪S\(k*d(128)\)的一維向量VLAD。

Summary

Bow通常要搭配TF-IDF進(jìn)行使用，但是由于Vocabulary的大小的限制，VLAD是一個(gè)不錯(cuò)的替代選擇。RootSift是對原生sift的擴(kuò)展。

最新評論