以图搜图怎么弄：特征、度量与索引
文本检索那套为什么直接搬不过来
文本搜索有现成的成熟套路：分词、倒排索引、BM25打分。核心前提是文本天然带着"词"这个离散单元，词相同就能命中。图片没有这个运气，一张jpg在计算机眼里就是几百万个像素值，两张内容一样的图，只要分辨率差一档或者jpeg质量参数不同，像素层面对不上号。所以图像检索的第一步，也是灵魂一步，是把图片压成一个能代表它内容的特征向量，让"看起来像"变成"向量距离近"。
特征向量的两代方案
第一代是手工特征时代，代表作SIFT。思路是在图上找那些角点、斑块之类的关键点，每个点周边的梯度信息聚合成一个局部描述子。一张图能提几百上千个这种局部描述子，但搜索单图对多图没法直接比，于是有了词袋模型（BoW）：拿几十万个局部描述子做kmeans聚类，每个聚类中心当一个"视觉单词"，一张图的所有局部特征往词典上一映射，统计词频直方图，就变成了一个固定长度的向量。后来VLAD、Fisher Vector把这个思路做得更精细，本质都是局部特征的聚合统计。
第二代是深度学习时代。2012年AlexNet在ImageNet上炸场之后，大家发现CNN卷积网络天然就是个特征提取器：拿掉最后的分类层，倒数第二层那个输出直接当整图的特征向量用，效果就把精心设计了十年的手工特征拍在了沙滩上。后续的改进主要在聚合方式上，比如R-MAC把特征图分区取最大再聚合，GeM把平均池化换成广义均值池化，让"整图特征"对局部目标的表达能力更强。到今天工业界做以图搜图的基线，基本就是一个预训练ResNet提特征，简单粗暴效果好。
拿什么衡量像不像
向量有了，就是度量问题，最常用两个：
$$ d_{\cos}(a, b) = 1 - \frac{a \cdot b}{\lVert a \rVert \, \lVert b \rVert} \quad\quad d_{E}(a, b) = \lVert a - b \rVert_2 $$
余弦相似度只看方向不看长度，CNN特征先做个L2归一化之后，两者实际上等价，工业界一般都走这条路。值得注意的是这时的"像"完全取决于特征本身的语义表达能力：ResNet的特征，语义类别像（都是狗）就会近，纯色调构图像不一定近，这一点和人的直觉有偏差，做产品时要心里有数。
几百万图库，暴力扫是扫不动的
特征和度量都定了，剩下检索环节。库里有五百万张图，每张2048维float，来一张查询图挨个算距离，单次查询就是百亿级浮点运算，QPS稍微一上来就跪了。
经典的解法是KD树这类空间划分树，低维的时候很美好，但图像特征动辄几百上千维，高维空间里KD树的剪枝基本失效，最后退化成还是全库扫。这个坑有个专门的名字，叫维度灾难，跟蒙特卡洛那篇提到的高维积分问题是同一个妖怪。
真正在工业界扛住量级的是近似最近邻检索（ANN），思想是牺牲一点精度换几个数量级的速度。最主流的乘积量化（PQ）思路非常聪明：把2048维向量切成32段，每段64维，各段独立做kmeans聚类建小码本；这样每个向量就被编码成32个聚类中心的编号，一个字节一段，存储从8KB压到32字节。查询时距离用"查询向量各段到对应码本中心的距离表"拼出来，快而且省内存。在这个基础上再套一层倒排（IVF），先把全库粗分成1024个簇，查询时只扫最近的几个簇，百万级图库毫秒级出结果。
Facebook 2017年把这些东西开源成了Faiss库，直接站在巨人肩膀上：
import faiss
import numpy as np
d = 2048 # ResNet50倒数第二层的维度
xb = np.random.random((100000, d)).astype('float32') # 模拟图库特征
faiss.normalize_L2(xb) # 归一化后内积即余弦
# 暴力检索基线, 准但库大了扛不住
index = faiss.IndexFlatIP(d)
index.add(xb)
# 乘积量化+倒排: nlist粗簇数, 32段, 每段8bit
quantizer = faiss.IndexFlatL2(d)
index_pq = faiss.IndexIVFPQ(quantizer, d, 1024, 32, 8)
index_pq.train(xb)
index_pq.add(xb)
D, I = index_pq.search(xb[:1], 10) # 查最相似的10张, 返回距离和下标十万级图库一个普通CPU进程就能跑出可观QPS，这个性价比在手工时代不敢想。
写在最后
Faiss里还有个叫HNSW的图索引，多层跳表式的近邻图结构，召回率和速度都很能打，GPU版的Faiss更是把建索引和检索都搬到了显卡上，量级再往上走可以研究。另外提特征这步如果是批量离线做，记得把图片解码放到多进程里，不然CPU时间全耗在jpeg解码上，模型还在旁边空转，这种事踩过的人都懂。