开发者学堂课程【高校精品课-华中科技大学 -智能媒体计算：图像检索方法】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/811/detail/15710
图像检索方法
继续讲基于内容的图像检索，前面讲到的第四部分就是图像的检索算法，提了特征对特征进行量化编码，也能做了特殊的索引，检索里面最核心的其实就是查询的图像与待查询图像的距离的计算。
常用的查询方法：
有一种叫线性扫描，其实就是穷举法，就是有一张图片查询就跟库里的所有的每一张图像去对比，看看哪一个跟这张图像的特征更近，它不需要进行构建索引。
它速度很慢，一张一张的来，它不符合实时的要求，它达不到实时，但是它有个好处，准确率很高。很便利，一张一张的来，来进行的查询，图像很少的情况下是没问题的，但是这种海量的大数据里边这种查询方法显然是不适合的。
普遍使用的是基于索引表的，就是取若干最相关的索引列表，不相关的就不去进行相似度计算，这样它这个速度提升一百倍呢根据数据量多少来讲，它可以呈指数的提升，大约仅需要保证百分之一的这种数据就可以达到相应的准确度，因此它可以提升查询的速度，但是它准确率，根据不同的索引算法或者是量化算法，实际上它的准确度的下降程度是不同的，因此基于索引的这种查询算法，它的精度其实取决于它的索引，而索引是跟量化编码相反的，前面在讲索引的时候其实已经讲过。这叫提前构建索引，就是说我们、、互联网这些东西，提取特征之后，要对这些特征进行这个量化，提前构建索引，在查询的时候就可以了基于这个索引的文件进行查询。
在图像检索里面，计算这个距离通常有两种算法：
一种叫做对称的距离计算，把它简写叫做 SDC。所谓的对称的是指量化不仅量化待查询这个向量，也就是库里图像的特征。同时还量化查询的向量，比如输入一张图像，待查询的图像其特征也要进行量化，用码字来代替原来的 XY 这种特征。这种就是信息的损失较大，误差相对量化比较大，非对称量化就是对待查询的图像，就是已经建设了索引，一定是对它进行量化，但对查询的图片的特征不再进行量化，也就是量化待查询。而这个查询的就是输入这个查询的需求，这个图像不量化，这叫非对称，就是量化一段。
这个好处就是它信息的损失相对对称的这种距离计算来讲要小一些，而待查询的这个向量它这个量化再构建索引处已经完成，查询的时候只需要在索引项里面把它找到就可以。
这两张图左边这是一个对称的距离计算， XY 分别通过量化器进行量化，而右边这个只量化了待查询，输入的这个向量不进行量化。从这个图里面可以看到量化的误差，实际上是这个距离误差的上界，它们两个相减的是距离，距离平方米它小于等于 dy ，查询就待检索距离的平方，这样就算它这个误差的最大值是多少，也就是如何进行隔空，取决于这个查询向它的量化误差。
基于上次课讲的这 IVFPQ 这个索引去进行查询，对查询的向量要进行粗量化，这里面为了得到更好的结果呢通常使用的一个多分配的策略，所谓的多分配，就是不是找到了查询向量的最接近的一个 clust ,而是取 K 个它接近的码字表，那么这个码子对应的这个集合，这个倒排表是取多少个。要的结果多，可以取得大一点，如果希望结果不多，也可以取得小一点，也就是 K 的近邻查询。
它距离的计算也可以选择两种:
一种叫对称距离的计算，它叫量化查询向量,非对称的就是不量化查询向量，它的整个流程来讲查询向量进来以后进行粗量化，码字就可以找到相应的倒排表，这个时候去求残差。如果你有系列继续的，非对称的是不需要再对它进行量化的，直接粗量化，k-means 就完了，对它不再进行 PQ 的量化，直接就得到了。如果是需要对称的运算的话，距离计算要去求残差，然后再对它进行 PQ 的量化，PQ量化之后再有量化编码，再有查询。
也就是距离的计算里面， SDC 和 ADC 的区别就是 ADC 里面其实就是少了一个 PQ 量化这一步，少这一步相当于查询输入的这个请求这里面误差会小一点。
后面再进行排序，取了 K 个相邻倒排表，这里面再根据这个它这个残差的值去返回需要的最前面的 N 个最需要的值。
影响查询算法性能的有哪些因素:
第一个就是空间开销，就是索引的码数大小，空间分割的细致程度越大，它这个码数就越大。码长就是量化的码数的大小 K2，也就是VQ 它整个是这样，PQ 是这样，它不同的量化方法他整个的这个空间开销还是不同的。
所以说在考虑这个这个查询性能的时候要看到查询的准确度的提高是牺牲的什么，比如通常需要牺牲这个空间的开销，第二个，其实就是查询的准确率，准确率就是说返回候选结果呢，前 N 个最接近的，这里面的准确的该返回来。
另外还有一个是准确率，还有一个是召回率，就是本来有多少是跟它接近的结果找了多少。另外一个就是查询的速度，速度越快越好，做查询的最好是越快越好，像搜索引擎一样按回车结果就出来了，图像相对要复杂，概率，时间，速度也要越快越好。通常也应该在一秒之内返回结果。
速度：
这个速度的影响也跟向量量化的方法有关系。量化倒排索引建的好，候选集少，那做计算的次数就少，还有一个跟距离的计算算法有关系，是浮点运算还是整数的运算，还是布尔然的运算都影响查询速度。另外计不计算距离，如果不计算距离，只是找准它的一个一个集合直接出来，只要计算距离，就要引入浮点运算还是每一步都算什么，和这个向量是否量化有关系。
加速方法：
既然速度很重要，就看一看这个距离的这个度量函数，它是否有一个加速方法。就以这个非对称距离的计算，这个 ADC 为例，看一看怎么对它进行加速，展开这个距离函数，这是一个近似展开，第一项，第二项，第三项后，看一看哪一个是可以提速。
第一项是查询向量的模长，其实对所有的数据库里的向量它都一样。因此这个是可以忽略的，第二个项是跟码字有关，这个 CI ，可事先把它算出来，可以把它放到这个索引项，就是去取的时候直接把它就取出来了。用查找表缓存内积项，这个SI和 CM 的内积，就是查询缓存，放的缓存比，这样的查询向量与码字的内积，对所有的数据库向量它只需要计算一次。计算的公式上面的这个。这样就是大幅提升速度，真正的查询其实就是这样的，这样看通过量化，通过建索引，通过这样加速以后即使都在索引里边实现，而且这个索引呢把它放在内存放在缓存里那么其实这样的点内积的因素。无论是它的计算的复杂度，还是参与计算的这个数量，其实都来自于它乘积，都比原来加固，这样尽可能保证查询的速率。
以 PQ 量化，前面讲这个例子讲一下查询的过程。查询图片来了以后提取它的特征进行分组，分成了四大组，然后分别对他进行 k- means 。这个时候就可以把它形成了查询的向量，这个查询的向量，在于库里面的去求计算，求距离的计算，如果对这个不再进行残差的量化的话，这里呢就是非对称，如果要对这个残差进行量化的那就是对称。所以说整个查询的过程就是说提这种图像的特征变化，和每库里面的每一次生成它的索引项它的过程是一致的。
这是一个在同一个数据库上，不同的算法的性能的区别：
这个图像的检索算法，索引算法，包括特征量化算法，通常都是这样的，对比的性能对比的结果来反映整个算法的性能。
基于内容的图像选择，参考的主要文献在这里，比如说有些文献在这里是索引的文献做出的。还有一些其它的框架，有时间，尤其是准备的在这方面啊，图像检索方面做一些深入研究的，可以把最近几年的 CVP R，ICCV，ECCV，naps 等等，这些会议上的论文吧去看一看那么每年都有相应的算法提出来。
