欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

图像检索之IF-IDF,RootSift,VLAD

程序员文章站 2022-03-09 23:04:51
tf-idftf-idf是一种用于信息检索的常用加权技术,在文本检索中,用以评估词语对于一个文件数据库中的其中一份文件的重要程度。词语的重要性随着它在文件中出现的频率成正比增加,但同时会随着它在文件数...

tf-idf

tf-idf是一种用于信息检索的常用加权技术,在文本检索中,用以评估词语对于一个文件数据库中的其中一份文件的重要程度。词语的重要性随着它在文件中出现的频率成正比增加,但同时会随着它在文件数据库中出现的频率成反比下降。像‘的',‘我们',‘地'等这些常用词在所有文章中出现的频率会很高,并不能很好的表征一个文档的内容。

同样的在图像检索中也引入了if-idf权重,

词频(term frequency,tf) 一个visual word在一个图像中出现的频率的很高,则说明该visual word 能够很好的代表图像的内容。

图像检索之IF-IDF,RootSift,VLAD

逆文档词频(inverse document frequency,idf) 一些常见的word,会在每一图像出现的频率都很高,但是这些word并不能很好的表示图像的内容,所以要给这一部分word低一些的权重。idf,描述一个word的普遍重要性,如古欧word在很多的图像中出现的频率都很高,则给予其较低的权重。

图像检索之IF-IDF,RootSift,VLAD

将分母+1是为了防止除数为0的情况出现。从上式中可以看出,包含当前word的图像个数越多,idf的值越小,说明该词越不重要。反之,该词越重要。

计算得到了tf和idf,则有

\[tf-idf = tf * idf\]

从tf和idf的计算公式可以看出,idf是针对整个图像数据库而言的,可以在训练完成后计算一次得到。而tf则是针对具体的某张图像来说的,需要多次计算。

将tf-idf权值赋给bow向量,再进行\(l_2\)的归一化,即可得到一个可用于图像检索的向量。

c++实现

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]);
    }
}

上面代码计算的是图像库的idf(idf是针对整个图像库而言的)。
针对某一张图片,都需要计算一次tf。tf的计算公式:图像检索之IF-IDF,RootSift,VLAD,可以看着是对图像的bow向量进行\(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。

当比较直方图时,使用欧氏距离通常比卡方距离或hellinger核时的性能差,但是在使用sift特征点为什么一直都使用欧氏距离呢?
不论是对sift特征点进行匹配,还是对sift特征集合进行聚类得到视觉词汇表,又或者对图像进行bow编码,都使用的是欧氏距离。但是sift特征描述子本质上也是一种直方图,为什么对sift特征描述子进行比较的时候要使用欧氏距离呢,有没有一种更精确的比较方法呢?

sift描述子统计的是关键点邻域的梯度直方图,更详细的介绍可以参考图像检索(1): 再论sift-基于vlfeat实现

zisserman 认为只所以一直使用欧氏距离来测量sift特征的相似度,是由于在sift提出的时候,使用的是欧氏距离的度量,可以找出一种比较欧氏距离更为精确的度量方法。arandjelovic和zisserman提出了rootsift对sift特征进行扩展。

在提取得到sift的描述向量\(x\)后,进行以下处理,即可得到rootsift
1.对特征向量\(x\)进行\(l_1\)的归一化(\(l_1-normalize\))得到\(x'\)
2.对\(x'\)的每一个元素求平方根
3.进行\(l_2-normalize\),可选

最后一步,是否进行\(l_2\)的归一化,有些不一致。 在paper 并没有指出需要进行\(l_2\)的归一化,但是在presentation, 却有\(l_2\)归一化这一步。也有认为,显式地执行l2规范化是不需要的。通过采用l1规范,然后是平方根,已经有l2标准化的特征向量,不需要进一步的标准化。

python实现

# 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++ 实现

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方法,在图像的检索和检索中有这广泛的应用。bow通过聚类,对图像的局部特征进行重新编码,有很强的表示能力,并且使用svm这样基于样本间隔的分类器,也能取得了很好的分类效果。但是在图像规模比较大的情况下,由于视觉词汇表vocabulary大小的限制,bow对图像的表示会越来越粗糙,编码后损失的图像信息较多,检索精度也随之而降低。

2010年,论文aggregating local descriptors into a compact image representation中提出了一对新的图像表示方法,vlad。从三个方面进行改进:

  • 使用vlad表示图像的局部特征
  • pca
  • 索引adc的构建方法

bow的表示方法中,是统计每个特征词汇在图像中出现的频率。vlad则是求落在同一个聚类中心的特征和该聚类中心残差的累加和。公式表示如下:

\[v_{i,j} = \sum_{x\ such\ that\ nn(x)=c_i}x_j - c_{i,j}\]

\(x_j\)是图像的第\(j\)个特征点,\(c_i\)则是和该特征点最近的聚类中心,\(x_j - c_{i,j}\)表示特征点和其最近聚类中心的差。假如使用的是sift特征,视觉词汇表vocabulary的大小为\(k\),则可以得到\(k\)个128维的向量\(v_{i,j}\)。
然后将这\(k*d\)个向量(\(d\)为图像特征的长度,例如sift为128维)\(v_{i,j}\)拉伸为一个\(k*d\)长度的一维向量,再对拉伸后的向量做一个\(l_2\)的归一化就得到图像的vlad表示。

由于,vlad是特征和其最邻近的聚类中心的残差和,该向量的很多分量很多分量都为0,也就是说该向量是稀疏的(sparse,很少的分量占有大部分的能量),所以可以对vlad进行降维处理(例如,pca)能进一步缩小向量的大小。

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实现还是比较简单的。这里使用flannbasedmatchermatch方法来查找特征最邻近的聚类中心(视觉词汇)。可以分为以下三步:

  • subtract计算特征和其最近邻的聚类中心的差值,add将同一个聚类中心的差值累加起来
  • 对上面得到的矩阵的responsehist进行\(l_2\)的归一化处理
  • 使用reshape方法,将矩阵拉伸为一维\(k*d(128)\)的一维向量vlad。

summary

bow通常要搭配tf-idf进行使用,但是由于vocabulary的大小的限制,vlad是一个不错的替代选择。rootsift是对原生sift的扩展。