开发者学堂课程【高校精品课-华中科技大学 -智能媒体计算：高维特征索引】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/811/detail/15709
高维特征索引
图像检索，已经讲到了第三部分就是高维特征的索引，在数据库里面是讲的索引，可以回忆一下。高维特征索引就是前面讲的就是局部特征，深度的局部特征。怎么来对它进行检索，索引目的是快速查询一个二维表,索引字，索引项。每个索引字对应的一个索引项的列表，建索引的目的是为了查询速度快，过滤掉不相关的特征，仅需要访问一部分所影响，就是把相关的把它找聚合在一起，去查询的时候只去跟相关的这个特征的索引值而不是全部。
类别：
有以树为基础的对比，像 B 树， KD 树，D 加树，树的变种有很多。特征索引它的问题是当维数很大的时候会发生维数灾难，另外一种就是以哈希为基础的，比如 SH ， LSH ，KMH ，ITQ ，特点是它的压缩率很高但它的准确率很低。
用于视觉上的图像还有基于视觉单词的倒排表，其实就是在搜索引擎里面讲到的词然后导到 ID ，而视觉单词其实就是图像的特征把特征像单词一样把它分隔开。典型的就像 BOF , BOW 等视觉单词，对它进行倒排文件的建立。包括像 IVF 倒排文件是一维的，多维的 IMI-PQ , c-MI.
树的结果与哈希相比相比它的压缩率很大同时它的准确率也较高,因此在图像，视频的这种高维索引主要用基于视觉单词的倒排表，关于索引发展几年前写了综述，可以看看参考文献了解整个图像检索里面索引的发展脉络。
基于视觉单词倒排表为例来看如何来构建高维索引：
一维索引叫 IVF-BOW ，它是以一个码字作为随机，二维索引像 IMI-PQ , c-MI ,这种多特征的索引又加了 PQ ，用 PQ 做量化来生成索引码字，码字是一个二元组， C1 , C2 二元组。 c-MI 是耦合了多维的索引，是以 HSV 特征还有 SIFT 特征结合在一起的这个二元素作为索引字的多特征索引。
索引字生成：
可以用向量量化的方法来对这个码书进行构建。比如说一维里面可以用 k-means ,向量量化，二维我们可以通过 PQ ，就是分段量化，或者是残差向量量化，这就是 RVQ ,最后生成的索引项就是图像的 ID 和特征的编码。反过来就是特征的编码后面是图像的 ID
讲一个这个非常经典的一维的加 PQ 的，就是通过 PQ 去生成的码字，就是索引项。有个倒排文件叫 IVF-PQ 这个索引系统，目前用的很多，IVF 是倒排文件，PQ 是量化。
步骤：
是通过粗训练来学习索引的码书，码书训练。构建的阶段呢就是在索引的码数里面找到 C1 接近的码字，细量化就是对残差进行量化编码。这样做不仅知道他是在哪个集合里面，还可以知道离至心，中心的距离，从而进行排序。
整个流程，在训练阶段通过这个数据集来训练码书，粗量化就是 k-means 可以得到索引的码书 C1 ，如果说跟它的特征，在跟码书的中心求一个残差就成了残差量化，可以从 PQ 残差量化的值再进行量化，这就形成了码书 C2 。
码书训练完了之后， C1 , C2 有了，每一个特征图像库里面的数据。怎么去把它的这个索引构建起来，就去查找到与它对应的这个两个码字，一个是 C1 ，一个是 C2 ,找到 C1 就是粗量化。
然后再细化，叫求残差，也就是细量化，通过 PQ 进行量化找到量化编码 C2 ，这样一做就把整个量化编码找到了，再把编码写到索引文件里边去。
粗量化学习方法，使用 VQ ，一维的 k-means 量化器用于生成索引的码书，这里边的码书要足够的大，比如说 4096，有点要更大，就相当于把这个图像它的这种特征分成了很多很多小的聚类，这个K越大分的组就越多，如果组多到一定程度上其实达到一张图片就是一个组。大到一定程度，在每一个组（ class 里边）图像是接近的，大到一定程度，不去求残差，组内足够接近就不用求残差。因此在很多图像检索系统里到了这一步过程， K 取的足够大，如果对它的精度没有更高的要求，后面残差量化的过程可以省略，如果对精度没有更高的要求。
对特征空间进进行一个粗略的划分，每个码子对应一个索引的列表。这个时候一个组里面其实是没有排序的，所谓的粗就是因为这个。如果索引到此为止，找图像就找到了最近的那个 C ，执行找到把里面的相关的这些元素找出来排序随机就行，
如果要再进行细化，叫 PQ 量化，就在对它的残差进行分段的量化，再把它串联起来，在上一讲里面已经讲过了，用于对粗量化器的每一个子空间进行更细力度的划分来减少量化误差，也便于取出这个索引项之后进一步排序，得到精确的检索结果。
索引生成表，前面训练好了之后，就对这个数据粗量化，找到 C1 ，寻找特征集及码书里面 C1的最近的这个码字。
求残差，通过 PQ 对这个残差进行压缩变化，最后生成索引项，将图像的 ID 和编码放在索引项里边一一对应，对未来的检索提供服务，这就是构建的图像索引的过程，对整个的这个不同的索引方法如果想进一步了解就取看后面的关于索引的那一篇综述。
