第 7 章　图像搜索

第 7 章　图像搜索

本章将展示如何利用文本挖掘技术对基于图像视觉内容进行图像搜索。本章阐明了提出利用视觉单词的基本思想，并解释了完整的安装细节，还在一个示例数据集上进行了测试。

7.1　基于内容的图像检索

在大型图像数据库上，CBIR（Content-Based Image Retrieval，基于内容的图像检索）技术用于检索在视觉上具相似性的图像。这样返回的图像可以是颜色相似、纹理相似、图像中的物体或场景相似；总之，基本上可以是这些图像自身共有的任何信息。

对于高层查询，比如寻找相似的物体，将查询图像与数据库中所有的图像进行完全比较（比如用特征匹配）往往是不可行的。在数据库很大的情况下，这样的查询方式会耗费过多时间。在过去的几年里，研究者成功地引入文本挖掘技术到 CBIR 中处理问题，使在数百万图像中搜索具有相似内容的图像成为可能。

从文本挖掘中获取灵感——矢量空间模型

矢量空间模型是一个用于表示和搜索文本文档的模型。我们将看到，它基本上可以应用于任何对象类型，包括图像。该名字来源于用矢量来表示文本文档，这些矢量是由文本词频直方图构成的 1。换句话说，矢量包含了每个单词出现的次数，而且在其他别的地方包含很多 0 元素。由于其忽略了单词出现的顺序及位置，该模型也被称为 BOW 表示模型。

1经常可以看到用“术语”替代“词”，两者在矢量空间模型中表达的意义相同。

通过单词计数来构建文档直方图向量 v，从而建立文档索引。通常，在单词计数时会忽略掉一些常用词，如“这”“和”“是”等，这些常用词称为停用词。由于每篇文档长度不同，故除以直方图总和将向量归一化成单位长度。对于直方图向量中的每个元素，一般根据每个单词的重要性来赋予相应的权重。通常，数据集（或语料库）中一个单词的重要性与它在文档中出现的次数成正比，而与它在语料库中出现的次数成反比。

最常用的权重是 tf-idf（term frequency-inverse document frequency，词频 - 逆向文档频率)，单词 w 在文档 d 中的词频是：

$\text{tf}_{w,d}=\frac{n_w}{\sum_jn_j}$

n_w 是单词 w 在文档 d 中出现的次数。为了归一化，将 n_w 除以整个文档中单词的总数。

逆向文档频率为：

$\text{idf}_{w,d}=\log\frac{|(D)|}{|{d:w\in d\}|}$

|D| 是在语料库 D 中文档的数目，分母是语料库中包含单词 w 的文档数 d。将两者相乘可以得到矢量 v 中对应元素的 tf-idf 权重。关于 tf-idf，详见 http://en.wikipedia.org/wiki/Tf-idf。

上面就是我们目前需要掌握的知识。接下来让我们看看怎样将该模型应用到基于视觉内容的图像索引及搜索中。

7.2　视觉单词

为了将文本挖掘技术应用到图像中，我们首先需要建立视觉等效单词；这通常可以采用 2.2 节中介绍的 SIFT 局部描述子做到。它的思想是将描述子空间量化成一些典型实例，并将图像中的每个描述子指派到其中的某个实例中。这些典型实例可以通过分析训练图像集确定，并被视为视觉单词。所有这些视觉单词构成的集合称为视觉词汇，有时也称为视觉码本。对于给定的问题、图像类型，或在通常情况下仅需呈现视觉内容，可以创建特定的词汇。

从一个（很大的训练图像）集提取特征描述子，利用一些聚类算法可以构建出视觉单词。聚类算法中最常用的是 K-means2，这里也将采用 K-means。视觉单词并不高端，只是在给定特征描述子空间中的一组向量集，在采用 K-means 进行聚类时得到的视觉单词是聚类质心。用视觉单词直方图来表示图像，则该模型便称为 BOW 模型。

2或在更加高级的场合下使用层次 K-means。

我们首先介绍一个示例数据集，并利用它来说明 BOW 概念。文件 first1000.zip 包含了有肯塔基大学物体识别数据集（或称“ukbench”）的前 1000 幅图像。完整的数据集、公布的基准和一些配套代码参见 http://www.vis.uky.edu/~stewe/ukbench/。该 ukbench 数据集有很多子集，每个子集包含四幅图像，这四幅图像具有相同的场景或物体，而且存储的文件名是连续的，即 0 . . . 3 属于同一图像子集，4 . . . 7 属于另外同一图像子集，以此类推。图 7-1 展示了数据集中的一些图像，附录 B.4 给出了该数据集的细节以及获取方法。

第 7 章　图像搜索 - 图3

图 7-1：ukbench（肯塔基大学物体识别数据集）数据集中的一些图像

创建词汇

为创建视觉单词词汇，首先需要提取特征描述子。这里，我们使用 SIFT 特征描述子。如前面一样，imlist 包含的是图像的文件名。运行下面的代码，可以得到每幅图像提取出的描述子，并将每幅图像的描述子保存在一个文件中：

nbr_images = len(imlist)
featlist = [ imlist[i][:-3]+'sift' for i in range(nbr_images)]
for i in range(nbr_images):
  sift.process_image(imlist[i],featlist[i])

创建名为 vocabulary.py 的文件，将下面代码添加进去。该代码创建一个词汇类，以及在训练图像数据集上训练出一个词汇的方法：

from scipy.cluster.vq import 
import vlfeat as sift
class Vocabulary(object):
  def __init__(self,name):
    self.name = name
    self.voc = []
    self.idf = []
    self.trainingdata = []
    self.nbr_words = 0
  def train(self,featurefiles,k=100,subsampling=10):
    """ 用含有k 个单词的K-means 列出在featurefiles 中的特征文件训练出一个词汇。对训练数据下采样可以加快训练速度"""
    nbr_images = len(featurefiles)
    # 从文件中读取特征
    descr = []
    descr.append(sift.read_features_from_file(featurefiles[0])[1])
    descriptors = descr[0] # 将所有的特征并在一起，以便后面进行K-means 聚类
    for i in arange(1,nbr_images):
      descr.append(sift.read_features_from_file(featurefiles[i])[1])
      descriptors = vstack((descriptors,descr[i]))
    # K-means: 最后一个参数决定运行次数
    self.voc,distortion = kmeans(descriptors[::subsampling,:],k,1)
    self.nbr_words = self.voc.shape[0]
    # 遍历所有的训练图像，并投影到词汇上
    imwords = zeros((nbr_images,self.nbr_words))
    for i in range( nbr_images ):
      imwords[i] = self.project(descr[i])
    nbr_occurences = sum( (imwords > 0)1 ,axis=0)
    self.idf = log( (1.0*nbr_images) / (1.0*nbr_occurences+1) )
    self.trainingdata = featurefiles
  def project(self,descriptors):
    """ 将描述子投影到词汇上，以创建单词直方图"""
    # 图像单词直方图
    imhist = zeros((self.nbr_words))
    words,distance = vq(descriptors,self.voc)
    for w in words:
      imhist[w] += 1
    return imhist

Vocabulary 类包含了一个由单词聚类中心 VOC 与每个单词对应的逆向文档频率构成的向量，为了在某些图像集上训练词汇，train() 方法获取包含有 .sift 描后缀的述子文件列表和词汇单词数 k。在 K-means 聚类阶段可以对训练数据下采样，因为如果使用过多特征，会耗费很长时间。

现在在你计算机的某个文件夹中，保存了图像及提取出来的 sift 特征文件，下面的代码会创建一个长为 k ≈ 1000 的词汇表。这里，再次假设 imlist 是一个包含了图像文件名的列表：

import pickle
import vocabulary
nbr_images = len(imlist)
featlist = [ imlist[i][:-3]+'sift' for i in range(nbr_images) ]
voc = vocabulary.Vocabulary('ukbenchtest')
voc.train(featlist,1000,10)
# 保存词汇
with open('vocabulary.pkl', 'wb') as f:
  pickle.dump(voc,f)
print 'vocabulary is:', voc.name, voc.nbr_words

代码最后部分用 pickle 模块保存了整个词汇对象以便后面使用。

7.3　图像索引

在开始搜索之前，我们需要建立图像数据库和图像的视觉单词表示。

7.3.1　建立数据库

在索引图像前，我们需要建立一个数据库。这里，对图像进行索引就是从这些图像中提取描述子，利用词汇将描述子转换成视觉单词，并保存视觉单词及对应图像的单词直方图。从而可以利用图像对数据库进行查询，并返回相似的图像作为搜索结果。

这里，我们使用 SQLite 作为数据库。SQLite 将所有信息都保存到一个文件，是一个易于安装和使用的数据库。由于不涉及数据库和服务器的配置及其他超出本书范围的细节，它很容易上手。SQLite 对应的 Python 版本是 pysqlite，可以从 http://code.google.com/p/pysqlite/ 获取，或在 Mac 和 Linux 系统中通过软件源获取。SQLite 使用 SQL 查询语言，所以如果想用别的数据库，这个转换过程非常简单。

在开始之前，我们需要创建表、索引和索引器 Indexer 类，以便将图像数据写入数据库。首先，创建一个名为 imagesearch.py 的文件，将下面的代码添加进去：

import pickle
from pysqlite2 import dbapi2 as sqlite
class Indexer(object):
  def __init__(self,db,voc):
    """ 初始化数据库的名称及词汇对象 """
    self.con = sqlite.connect(db)
    self.voc = voc
  def __del__(self):
    self.con.close()
  def db_commit(self):
    self.con.commit()

首先，我们需要用 pickle 模块将这些数组编码成字符串以及将字符串进行解码；SQLite 可以从 pysqlite2 模块中导入（安装细节参见附录 A）。Indexer 类连接数据库，并且一旦创建（调用 __init__() 方法）后就可以保存词汇对象。__del__() 方法可以确保关闭数据库连接，db_commit() 可以将更改写入数据库文件。

我们仅需一个包含三个表单的简单数据库模式。表单 imlist 包含所有要索引的图像文件名；imwords 包含了一个那些单词的单词索引、用到了哪个词汇、以及单词出现在哪些图像中；最后，imhistograms 包含了全部每幅图像的单词直方图。根据矢量空间模型，我们需要这些以便进行图像比较。表 7-1 展示了该模式。

表7-1：一个用于存储图像及视觉单词的简单数据库模式

`imlist`	`imwords`	`imhistograms`
rowid	imid	imid
filename	wordid	histogram
	vocname	vocname

下面 Indexer 类中的方法用于创建表单及一些有用的索引以加快搜索速度：

def create_tables(self):
  """ 创建数据库表单"""
  self.con.execute('create table imlist(filename)')
  self.con.execute('create table imwords(imid,wordid,vocname)')
  self.con.execute('create table imhistograms(imid,histogram,vocname)')
  self.con.execute('create index im_idx on imlist(filename)')
  self.con.execute('create index wordid_idx on imwords(wordid)')
  self.con.execute('create index imid_idx on imwords(imid)')
  self.con.execute('create index imidhist_idx on imhistograms(imid)')
  self.db_commit()

7.3.2　添加图像

有了数据库表单，我们便可以在索引中添加图像。为了实现该功能，我们需要在 Indexer 类中添加 add_to_index() 方法。将下面的方法添加到 imagesearch.py 中：

def add_to_index(self,imname,descr):
  """ 获取一幅带有特征描述子的图像，投影到词汇上并添加进数据库"""
  if self.is_indexed(imname): return
  print 'indexing', imname
  # 获取图像id
  imid = self.get_id(imname)
  # 获取单词
  imwords = self.voc.project(descr)
  nbr_words = imwords.shape[0]
  # 将每个单词与图像链接起来
  for i in range(nbr_words):
    word = imwords[i]
    # wordid 就是单词本身的数字
    self.con.execute("insert into imwords(imid,wordid,vocname)
        values (?,?,?)", (imid,word,self.voc.name))
  # 存储图像的单词直方图
  # 用pickle 模块将NumPy 数组编码成字符串
  self.con.execute("insert into imhistograms(imid,histogram,vocname)
        values (?,?,?)", (imid,pickle.dumps(imwords),self.voc.name))

该方法获取图像文件名与 Numpy 数组，该数组包含的是在图像找到的描述子。这些描述子投影到词汇上，并插入到 imwords（逐字）和 imhistograms 表单中。我们使用两个辅助函数：is_indxed() 用来检查图像是否已经被索引，get_id() 则对一幅图像文件名给定 id 号。将下面的代码添加进 imagesearch.py：

def is_indexed(self,imname):
  """ 如果图像名字（imname）被索引到，就返回True"""
  im = self.con.execute("select rowid from imlist where
        filename='%s'" % imname).fetchone()
  return im != None
def get_id(self,imname):
  """ 获取图像id，如果不存在，就进行添加"""
  cur = self.con.execute(
  "select rowid from imlist where filename='%s'" % imname)
  res=cur.fetchone()
  if res==None:
    cur = self.con.execute(
    "insert into imlist(filename) values ('%s')" % imname)
    return cur.lastrowid
  else:
    return res[0]

你是否注意到我们在 add_to_index() 方法中用到了 Pickle 模块？由于 SQLite 的数据库在存储对象或数组时并没有一个标准类型。所以，我们用 Pickle 的 dumps() 函数创建一个字符串表示，并将其写入数据库。因此，从数据库读取数据时，我们需要拆封该字符串，这在下一节有详细介绍。

下面的示例代码会遍历整个 ukbench 数据库中的样本图像，并将其加入我们的索引。这里，假设列表 imlist 和 featlist 分别包含之前图像文件名及图像描述子，vocabulary.pkl 包含已经训练好的词汇：

import pickle
import sift
import imagesearch
nbr_images = len(imlist)
# 载入词汇
with open('vocabulary.pkl', 'rb') as f:
  voc = pickle.load(f)
# 创建索引器
indx = imagesearch.Indexer('test.db',voc)
indx.create_tables()
# 遍历整个图像库，将特征投影到词汇上并添加到索引中
for i in range(nbr_images)[:1000]:
  locs,descr = sift.read_features_from_file(featlist[i])
  indx.add_to_index(imlist[i],descr)
# 提交到数据库
indx.db_commit()

现在我们可以检查数据库中的内容了：

from pysqlite2 import dbapi2 as sqlite
con = sqlite.connect('test.db')
print con.execute('select count (filename) from imlist').fetchone()
print con.execute('select * from imlist').fetchone()

控制台打印结果如下：

(1000,)
(u'ukbench00000.jpg',)

如果你在最后一行用 fetchall() 来代替 fetchone()，会得到一个包含所有文件名的长列表。

7.4　在数据库中搜索图像

建立好图像的索引，我们就可以在数据库中搜索相似的图像了。这里，我们用 BoW（Bag-of-Word，词袋模型）来表示整个图像，不过这里介绍的过程是通用的，可以应用于寻找相似的物体、相似的脸、相似的颜色等，它完全取决于图像及所用的描述子。

为实现搜索，我们在 imagesearch.py 中添加 Searcher 类：

class Searcher(object):
  def __init__(self,db,voc):
    """ 初始化数据库的名称 """
    self.con = sqlite.connect(db)
    self.voc = voc
  def __del__(self):
    self.con.close()

一个新的 Searcher 对象连接到数据库，一旦删除便关闭连接，这与之前的 Indexer 类中的处理过程相同。

如果图像数据库很大，逐一比较整个数据库中的所有直方图往往是不可行的。我们需要找到一个大小合理的候选集（这里的“合理”是通过搜索响应时间、所需内存等确定的），单词索引的作用便在于此：我们可以利用单词索引获得候选集，然后只需在候选集上进行逐一比较。

7.4.1　利用索引获取候选图像

我们可以利用建立起来的索引找到包含特定单词的所有图像，这不过是对数据库做一次简单的查询。在 Searcher 类中加入 candidates_from_word() 方法：

def candidates_from_word(self,imword):
  """ G 获取包含imword 的图像列表"""
  im_ids = self.con.execute(
      "select distinct imid from imwords where wordid=%d" % imword).fetchall()
  return [i[0] for i in im_ids]

上面会给出包含特定单词的所有图像 id 号。为了获得包含多个单词的候选图像，例如一个单词直方图中的全部非零元素，我们在每个单词上进行遍历，得到包含该单词的图像，并合并这些列表 3。这里，我们仍然需要在合并了的列表中对每一个图像 id 出现的次数进行跟踪，因为这可以显示有多少单词与单词直方图中的单词匹配。该过程可以通过下面的 candidates_from_histogram 方法完成：

3如果不想使用所有单词，你可以根据其倒排文档频率权重进行排序，并使用那些权重最高的单词。

def candidates_from_histogram(self,imwords):
  """ 获取具有相似单词的图像列表"""
  # 获取单词id
  words = imwords.nonzero()[0]
  # 寻找候选图像
  candidates = []
  for word in words:
    c = self.candidates_from_word(word)
    candidates+=c
  # 获取所有唯一的单词，并按出现次数反向排序
  tmp = [(w,candidates.count(w)) for w in set(candidates)]
  tmp.sort(cmp=lambda x,y:cmp(x[1],y[1]))
  tmp.reverse()
  # 返回排序后的列表，最匹配的排在最前面
  return [w[0] for w in tmp]

该方法从图像单词直方图的非零项创建单词 id 列表，检索每个单词获得候选集并将其合并到 candidates 列表中，然后创建一个元组列表每个元组由单词 id 和次数 count 构成，其中次数 count 是候选列表中每个单词出现的次数。同时，我们还以元组中的第二个元素为准，用 sort() 方法和一个自定义的比较函数对列表进行排序（考虑到后面的效率）。该自定义比较函数进行用 lambda 函数内联声明，对于单行函数声明，使用 lambda 函数非常方便。最后结果返回一个包含图像 id 的列表，排在列表最前面的是最好的匹配图像。

思考下面的例子：

src = imagesearch.Searcher('test.db', voc)
locs,descr = sift.read_features_from_file(featlist[0])
iw = voc.project(descr)
print 'ask using a histogram...'
print src.candidates_from_histogram(iw)[:10]

该例打印了从索引中查找出的前 10 个图像 id，结果如下（该结果根据你使用的词汇有所不同）：

ask using a histogram...
[655, 656, 654, 44, 9, 653, 42, 43, 41, 12]

查找出来的前 10 个候选图像都是不准确的。不用担心，我们现在可以取出该列表中任意数量的元素并比较它们的直方图。你将会看到，这可以极大地提高检索效率。

7.4.2　用一幅图像进行查询

利用一幅图像进行查询时，没有必要进行完全的搜索。为了比较单词直方图，Searcher 类需要从数据库读入图像的单词直方图。将下面的方法添加到 Searcher 类中：

def get_imhistogram(self,imname):
  """ 返回一幅图像的单词直方图"""
  im_id = self.con.execute(
      "select rowid from imlist where filename='%s'" % imname).fetchone()
  s = self.con.execute(
      "select histogram from imhistograms where rowid='%d'" % im_id).fetchone()
  # 用pickle 模块从字符串解码Numpy 数组
  return pickle.loads(str(s[0]))

这里，为了在字符串和 NumPy 数组间进行转换，我们再次用到了 pickle 模块，这次使用的是 loads()。

现在，我们可以全部合并到查询方法中：

def query(self,imname):
    """ 查找所有与imname 匹配的图像列表"""
    h = self.get_imhistogram(imname)
    candidates = self.candidates_from_histogram(h)
    matchscores = []
    for imid in candidates:
        # 获取名字
        cand_name = self.con.execute(
            "select filename from imlist where rowid=%d" % imid).fetchone()
        cand_h = self.get_imhistogram(cand_name)
        cand_dist = sqrt( sum(self.voc.idf* (h-cand_h)2 ) ) # 用L2 距离度量相似性
        matchscores.append( (cand_dist,imid) )
    # 返回排序后的距离及对应数据库ids 列表
    matchscores.sort()
    return matchscores

该 query() 方法获取图像的文件名，检索其单词直方图及候选图像列表（如果你的数据集很大，候选集的大小应该限制在某个最大值）。对于每个候选图像，我们用标准的欧式距离比较它和查询图像间的直方图，并返回一个经排序的包含距离及图像 id 的元组列表。

我们尝试对前一节的图像进行查询：

src = imagesearch.Searcher('test.db', voc)
print 'try a query...'
print src.query(imlist[0])[:10]

这会再次打印前 10 个结果，包括候选图像与查询图像间的距离，结果应该和下面类似：

try a query...
[(0.0, 1), (100.03999200319841, 2), (105.45141061171255, 3), (129.47200469599596, 708),
(129.73819792181484, 707), (132.68006632497588, 4), (139.89639023220005, 10),
(142.31654858097141, 706), (148.1924424523734, 716), (148.22955170950223, 663)]

这次结果比前一节中打印出来的 10 个结果要好很多。距离为 0 的图像对应查询图像本身；三幅与查询图像具有相同场景的图像有两幅在除查询图像本身外的前两个位置，第三幅则出现在第五个位置。

7.4.3　确定对比基准并绘制结果

为了评价搜索结果的好坏，我们可以计算前 4 个位置中搜索到相似图像数。这是在 ukbench 图像集上评价搜索性能常采用的评价方式。这里给出了计算分数的函数，将它添加到 imagesearch.py 中，你就可以开始优化查询了：

def compute_ukbench_score(src,imlist):
    """ 对查询返回的前4 个结果计算平均相似图像数，并返回结果"""
    nbr_images = len(imlist)
    pos = zeros((nbr_images,4))
    # 获取每幅查询图像的前4 个结果
    for i in range(nbr_images):
        pos[i] = [w[1]-1 for w in src.query(imlist[i])[:4]]
    # 计算分数，并返回平均分数
    score = array([ (pos[i]//4)==(i//4) for i in range(nbr_images)])*1.0
    return sum(score) / (nbr_images)

该函数获得搜索的前 4 个结果，将 query() 返回的索引减去 1，因为数据库索引是从 1 开始的，而图像列表的索引是从 0 开始的。然后，利用每 4 幅图像为一组时相似图像文件名是连续的这一事实，我们用整数相除计算得到最终的分数。分数为 4 时结果最理想；没有一个是准确的，分数为 0；仅检索到相同图像时，分数为 1；找到相同的图像并且其他三个中的两个相同时，分数为 3。

试试下面的代码：

imagesearch.compute_ukbench_score(src,imlist)

进行 1000 次查询需要耗费较长时间，如果你不想等太久，可以将查询集改为上面查询集的子集：

imagesearch.compute_ukbench_score(src,imlist[:100])

当得到的分数接近 3 时，我们可以认为结果很好。目前，ukbench 网站给出的最好结果刚刚超过 3；不过需要注意的是，他们用了更多的图像，所以在大数据集上，你在上面所得到的分数会下降。

最后，用于显示实际搜索结果的函数十分有用。添加该函数到 imagesearch.py 中：

def plot_results(src,res):
    """ 显示在列表res 中的图像"""
    figure()
    nbr_results = len(res)
    for i in range(nbr_results):
        imname = src.get_filename(res[i])
        subplot(1,nbr_results,i+1)
        imshow(array(Image.open(imname)))
        axis('off')
    show()

对于列表 res 中的任意搜索结果数，都可以调用该函数。例子如下：

nbr_results = 6
res = [w[1] for w in src.query(imlist[0])[:nbr_results]]
imagesearch.plot_results(src,res)

定义辅助函数：

def get_filename(self,imid):
    """ 返回图像id 对应的文件名"""
    s = self.con.execute(
        "select filename from imlist where rowid='%d'" % imid).fetchone()
    return s[0]

它可以将图像的 id 转换为图像文件名，以便在显示搜索结果时载入图像。图 7-2 显示了用 plot_results() 在我们的数据集上进行的一些查询实例。

7.5　使用几何特性对结果排序

让我们简要地看一种用 BoW 模型改进检索结果的常用方法。BoW 模型的一个主要缺点是在用视觉单词表示图像时不包含图像特征的位置信息，这是为获取速度和可伸缩性而付出的代价。

第 7 章　图像搜索 - 图4

图 7-2：在 ukbench 数据集上用一些查询图像进行搜索给出的一些结果。查询图像在最左边，后面是检索到的前 5 幅图像

利用一些考虑到特征几何关系的准则重排搜索到的靠前结果，可以提高准确率。最常用的方法是在查询图像与靠前图像的特征位置间拟合单应性。

为了提高效率，可以将特征位置存储在数据库中，并由特征的单词 id 决定它们之间的关联（要注意的是，只有在词汇足够大，使单词 id 包含很多准确匹配时，它才起作用）。然而，这需要大幅重写我们上面的数据库和代码，并复杂化表示形式。为了进行说明，我们仅重载靠前图像的特征，并对它们进行匹配。

下面是一个载入所有模型文件并用单应性对靠前的图像进行重排的完整例子：

import pickle
import sift
import imagesearch
import homography
# 载入图像列表和词汇
with open('ukbench_imlist.pkl','rb') as f:
  imlist = pickle.load(f)
  featlist = pickle.load(f)
nbr_images = len(imlist)
with open('vocabulary.pkl', 'rb') as f:
  voc = pickle.load(f)
src = imagesearch.Searcher('test.db',voc)
# 查询图像的索引号和返回的搜索结果数目
q_ind = 50
nbr_results = 20
# 常规查询
res_reg = [w[1] for w in src.query(imlist[q_ind])[:nbr_results]]
print 'top matches (regular):', res_reg
# 载入查询图像特征
q_locs,q_descr = sift.read_features_from_file(featlist[q_ind])
fp = homography.make_homog(q_locs[:,:2].T)
# 用RANSAC 模型拟合单应性
model = homography.RansacModel()
rank = {}
# 载入搜索结果的图像特征
for ndx in res_reg[1:]:
  locs,descr = sift.read_features_from_file(featlist[ndx])
  # 获取匹配数
  matches = sift.match(q_descr,descr)
  ind = matches.nonzero()[0]
  ind2 = matches[ind]
  tp = homography.make_homog(locs[:,:2].T)
  # 计算单应性，对内点计数。如果没有足够的匹配数则返回空列表
  try:
    H,inliers = homography.H_from_ransac(fp[:,ind],tp[:,ind2],model,match_theshold=4)
  except:
    inliers = []
  # 存储内点数
  rank[ndx] = len(inliers)
# 将字典排序，以首先获取最内层的内点数
sorted_rank = sorted(rank.items(), key=lambda t: t[1], reverse=True)
res_geom = [res_reg[0]]+[s[0] for s in sorted_rank]
print 'top matches (homography):', res_geom
# 显示靠前的搜索结果
imagesearch.plot_results(src,res_reg[:8])
imagesearch.plot_results(src,res_geom[:8])

首先，载入图像列表、特征列表（分别包含图像文件名和 SIFT 特征文件）及词汇。然后，创建一个 Searcher 对象，执行定期查询，并将结果保存在 res_reg 列表中。然后载入 res_reg 列表中每一幅图像的特征，并和查询图像进行匹配。单应性通过计算匹配数和计数内点数得到。最终，我们可以通过减少内点的数目对包含图像索引和内点数的字典进行排序。打印搜索结果列表到控制台，并可视化检索靠前的图像。

输出结果如下：

top matches (regular): [39, 22, 74, 82, 50, 37, 38, 17, 29, 68, 52, 91, 15, 90, 31, ... ]
top matches (homography): [39, 38, 37, 45, 67, 68, 74, 82, 15, 17, 50, 52, 85, 22, 87, ... ]

图 7-3 给出了常规查询和对常规查询重新排序后的一些样例结果。

第 7 章　图像搜索 - 图5

图 7-3：基于几何一致性用单应性对搜索结果进行重排后一些实例搜索结果。在每一个例子中，上一行是没有常规查询的结果，下一行是重排后的结果

7.6　建立演示程序及Web应用

作为本章关于图像搜索的最后一节，我们看一个用 Python 建立演示程序和 Web 应用的简单方法。通过将演示程序变成 Web 页，你便自动获得了跨平台支持，并以最低环境配置需求展示、分享你项目。我们在本节会完整给出一个创建简单图像搜索引擎的示例。

7.6.1　用CherryPy创建Web应用

为了建立这些演示程序，我们将采用 CherryPy 包，参见 http://www.cherrypy.org。CherryPy 是一个纯 Python 轻量级 Web 服务器，使用面向对象模型。CherryPy 的安装和配置细节参见附录 A。这里假设你已经学习了 CherryPy 实例教程，并对 CherryPy 的工作方式有了初步的了解，我们可以以本章创建的图像 Searcher 类为基础，来创建一个图像搜索 Web 演示程序。

7.6.2　图像搜索演示程序

首先，我们需要用一些 HTML 标签进行初始化，并用 Pickle 载入数据。另外，还需要有与数据库进行交互的 Searcher 对象词汇。创建一个名为 searchdemo.py 的文件，并添加下面具有两个方法的 Search Demo 类：

import cherrypy, os, urllib, pickle
import imagesearch
class SearchDemo(object):
  def __init__(self):
    # 载入图像列表
    with open('webimlist.txt') as f:
      self.imlist = f.readlines()
  self.nbr_images = len(self.imlist)
  self.ndx = range(self.nbr_images)
  # 载入词汇
  with open('vocabulary.pkl', 'rb') as f:
    self.voc = pickle.load(f)
  # 设置可以显示多少幅图像
  self.maxres = 15
  # html 的头部和尾部
  self.header = """
    <!doctype html>
    <head>
    <title>Image search example</title>
    </head>
    <body>
    """
  self.footer = """
    </body>
    </html>
    """
  def index(self,query=None):
    self.src = imagesearch.Searcher('web.db',self.voc)
    html = self.header
    html += """
      <br >
      Click an image to search. <a href='?query='>Random selection<a> of images.
      <br ><br >
      """
  if query:
    # 查询数据库并获取靠前的图像
    res = self.src.query(query)[:self.maxres]
    for dist,ndx in res:
      imname = self.src.get_filename(ndx)
      html += "<a href='?query="+imname+"'>"
      html += "<img src='"+imname+"' width='100' >"
      html += "<a>"
  else:
    # 如果没有查询图像，则显示随机选择的图像
    random.shuffle(self.ndx)
    for i in self.ndx[:self.maxres]:
      imname = self.imlist[i]
      html += "<a href='?query="+imname+"'>"
      html += "<img src='"+imname+"' width='100' >"
      html += "<a>"
    html += self.footer
    return html
  index.exposed = True
cherrypy.quickstart(SearchDemo(), '/',
          config=os.path.join(os.path.dirname(__file__), 'service.conf'))

你可以看到，这个简单的演示程序包含了单个类，该类包含一个初始化 __int__() 方法和一个“索引”页面 index() 方法（本例中只有一个页面）。这两个方法可以自动地映射至 URL，并且方法中的参数可以直接传递到 URL 中。index 方法里有一个查询参数，在本例中，该参数是查询图像，用来对其他图像排序。如果该参数是空的，就会随机显示一些图像。

index.exposed = True

这一行使索引 URL 可以被访问，上面 searchsemo.py 中紧接着该行的最后一行通过读取 service.conf 配置文件开启 CherryPy Web 服务器。在这个例子中，我们的配置文件如下：

[global]
server.socket_host = "127.0.0.1"
server.socket_port = 8080
server.thread_pool = 50
tools.sessions.on = True
[/]
tools.staticdir.root = "tmp/"
tools.staticdir.on = True
tools.staticdir.dir = ""

第一部分指定使用的 IP 地址和端口，第二部分确保本地文件夹可以读取（本例中文件夹为 tmp/），注意文件夹下存放的是你的图像库。

如果你打算将它展示给别人看，不要在这个文件夹下存放任何秘密的东西，因为文件夹下所有的内容都可以通过 CherryPy 访问。

从命令行开启你的 Web 服务器：

$ python searchdemo.py

打开浏览器，在地址栏输入 http://127.0.0.1:8080/，你可以看到随机挑选出来的图像的初始页面，类似于图 7-4 中的上图所示。点击一幅图像进行查询，会显示出搜索出来的前几幅图像，在搜索出来的图像中单击某图像可以开始新的查询。此外，页面上有一个链接，点击后可以返回原来随机选择的状态（通过一个空查询）。图 7-4 是一些查询示例。

该例子完整展示了从 Web 页面到数据库查询以及结果显示整个综合过程。当然，这只是一个基本的原型，并且你可以在该基础上进行改进，例如添加样式表使它更漂亮，或使它能够上传图像进行查询。

第 7 章　图像搜索 - 图7

图 7-4：在 ukbench 数据集上进行搜索的示例。上方是开始页面，显示了一些随机选择的图像；下方是一些查询示例。左上角是查询图像，之后的是搜索到的一些结果靠前的图像

练习

尝试只用查询图像中的部分单词构建候选图像列表来加速查询，用 idf 权重作为准则来挑选单词。
在你的词汇中，比如前 10%，实现一个最常用的视觉单词停用词列表，在搜索的时候忽略这些单词，看看搜索结果有何改善？
通过保存所有映射到一个给定单词 id 的所有图像特征，对视觉单词进行可视化。在给定的尺度下，在特征位置环绕处剪切图像块，并将它们画在同一图形窗口中。对于给定的单词，这些图像块看起来一样吗？
在 query() 方法中，用不同的距离度量及加权进行实验，用 compute_ukbench_score() 计算得出的分数度量你的改进是否有效。
在整个章节中，我们的词汇仅用到了 SIFT 特征，正如你在图 7-2 中看到的结果，它完全抛弃了颜色信息。试着添加颜色描述符看你是否能够改进搜索的结果。
对于大量词汇，用数组来表示视觉单词词频效率很低，原因在于数组中很多元素都是 0（比如考虑这样一种情形，有数十万单词，而图像却只有 1000 个特征）。一种克服这种低效的办法是将字典作为稀疏数组表示，用自定义一个稀疏类替代这些数组，并在自定义的稀疏类中添加一些必要的方法。或作为另一种选择，你可以采用 scipy.sparse 模块。
你如果增加词汇的大小，聚类时间也会相应增长，并且特征投影到单词的过程更加缓慢。用层次 K-means 聚类算法实现一个层次词汇，看它是怎样提高可伸缩性的，详情参阅文献 [23]。

第 7 章 图像搜索

第 7 章 图像搜索

7.1 基于内容的图像检索

从文本挖掘中获取灵感——矢量空间模型

7.2 视觉单词

创建词汇

7.3 图像索引

7.3.1 建立数据库

7.3.2 添加图像

7.4 在数据库中搜索图像

7.4.1 利用索引获取候选图像

7.4.2 用一幅图像进行查询

7.4.3 确定对比基准并绘制结果

7.5 使用几何特性对结果排序

7.6 建立演示程序及Web应用

7.6.1 用CherryPy创建Web应用

7.6.2 图像搜索演示程序

练习

第 7 章　图像搜索

第 7 章　图像搜索

7.1　基于内容的图像检索

7.2　视觉单词

7.3　图像索引

7.3.1　建立数据库

7.3.2　添加图像

7.4　在数据库中搜索图像

7.4.1　利用索引获取候选图像

7.4.2　用一幅图像进行查询

7.4.3　确定对比基准并绘制结果

7.5　使用几何特性对结果排序

7.6　建立演示程序及Web应用

7.6.1　用CherryPy创建Web应用

7.6.2　图像搜索演示程序