乘积量化（PQ）算法是和VLAD算法是由法国INRIA实验室一同提出来的，为的是加快图像的检索速度，所以它是一种检索算法，在矢量量化（Vector Quantization，VQ）的基础上发展而来，虽然PQ不算是新算法，但是这种思想还是挺有用处的，详见论文：Product Quantization for Nearest Neighbor Search.
PQ 在论文原文中是接在VLAD算法后面，假设使用VLAD算法获得了 1M 的图像表达向量，向量的维度为D=128，则对于一幅查询图像来说，需要计算 1M 个余弦距离，这样实时性就比较差. 所以如何加快这种距离的计算速度就是PQ算法所要完成的任务. 当然为了解决这个问题，已经有很多算法被提出了，如KDTree，LSH，ITQ等都是为解决这个问题而提出的，属于KNN或ANN范畴.
1. 空间切分
首先，PQ先将D维空间切分成M份：即将128维空间切分成M个D/M维的子空间，如下图所示M=8（在原文中，作者由于是在PCA之后进行的PQ检索，所以进行了一个随机旋转，因为PCA之后特征值的顺序是按照从大到小排列的）
用代码表示就是把向量维度切分：
int ds= d / nsq;
for ( int i = 0; i < nsq; i ++ )
{
for ( int j = 0; j < ds; j ++ )
{
vs.push_back( vtrain.row( i*ds + j ) );
}
}
//vtrain的转置是原始128维向量，vs是其中的一个子向量2. 量化
这样就可以在每个子空间内都会有1M个短向量，为每个子空间单独训练一本码书，图中码书规模为k=256，维度d=D/M=128/8=16，代码只要在上面的外循环中添加k-means聚类即可：
kmeans( vs, ks, labelssub,
TermCriteria( CV_TERMCRIT_EPS+CV_TERMCRIT_ITER, 50, 0.001 ),
3, KMEANS_PP_CENTERS, centers );到这里就有了M=8本子码书，下面依次量化每个子空间的数据，量化的过程就是计算每个短向量距离最近的聚类中心，距离就是L2距离，可以调用OpenCV函数，也可以自己写一个距离计算函数，但是要统一，如：
float my_norm_L2( Mat mat1, Mat mat2 )
{
int d = mat1.cols;
float sum_d = 0.0;
for ( int i = 0; i < d; i ++ )
{
float pp = mat1.at<float>( 0, i ) - mat2.at<float>( 0, i );
sum_d = sum_d + pp*pp;
}
return sum_d;
}3. 压缩
现在考虑一个D=128维的原始向量，它被切分成了M=8个d=16维的短向量，同时每个短向量都对应一个量化的索引值，索引值即该短向量距离最近的聚类中心的编号，每一个原始向量就可以压缩成M个索引值构成的压缩向量，只要设计好了数据结构，就可以获得所有1M数据的压缩向量. 压缩向量其实就是M个索引值，每个索引值对应一个聚类中心，所以要同时保存压缩向量和聚类中心.
其实一个向量被8个索引值同时索引，而如果把这8个索引值转换成一个的话是多大呢，k的M次方，这里应该是256的8次方，这是一个很大很大的数，而上面的操作就等效于生成了一个这么大规模的码书. 为什么这么说呢，因为每一个短向量（或称子向量）量化的过程都有k个选择，而一个原始向量有M个选择，类似于8位256进制的数可以表示的最大数值：
对于query图像的原始向量也经过上述流程的切分和量化过程，最后生成同样的M维压缩向量.
4. 距离计算
对于训练数据和测试数据都压缩完成后，接下来就是讨论如何计算两个压缩向量之间的距离呢？而且是快速的计算.
作者提供了两种距离计算方式，分别为 “对称距离计算” 和 “非对称距离计算” ，分别如下左右图所示：
对称距离计算：直接使用两个压缩向量 x，y 的索引值所对应的码字q(x), q(y)之间的距离代替之，而q(x),q(y)之间的距离可以离线计算，因此可以把q(x), q(y)之间的距离制作成查找表，只要按照压缩向量的索引值进行对应的查找就可以了，所以速度非常快；
非对称距离计算：使用x，q(y)之间的距离代替x，y之间的距离，其中x是测试向量. 虽然y的个数可能有上百万个，但是q(y)的个数只有k个，对于每个x，我们只需要在输入x之后先计算一遍x和k个q(y)的距离，制成查找表（因为只有k个，所以速度是非常快的），然后按照y对应的压缩向量索引值进行取值操作就可以了.
Mat sumidxtab( Mat &D, Mat&x, Mat & dis )
{
dis = Mat::zeros( 1, x.rows, CV_32FC1 );
for ( int i = 0; i < x.rows; i ++ )
{
float distmp = 0;
for ( int j = 0; j < D.cols; j ++ )
{
distmp = distmp + D.at<float>( x.at<int>( i, j ), j ) ;//ADC距离计算方式；
}
dis.at<float>( 0, i ) = distmp;
}
return dis;
}
//D为查找表，x为压缩向量，dis为最终的距离 5. 总结
不管哪种计算方法都可以实现快速的距离计算，但是非对称距离计算由于只量化了y，所以计算的距离精度更高，效果也更好. 距离计算过程中只需要存储码书和对应的索引值就可以完全抛弃原始的图像表达向量，实现数据的压缩和距离的快速计算.
但是需要明白的是，这种算法是基于量化的，所以必然存在量化误差，所以距离的计算并不是完全准确的. 通常通过这种算法迅速返回N个结果，然后再在N个结果中进行进一步的匹配计算，得到比较准确的结果.
在原文中，还有基于PQ的非线性计算方法IVFADC，它的速度更快，精度反而更高了，有时间再介绍. 其实后续人们不断改进了PQ算法，如OPQ，Multi-ADC，DPQ，AQ/APQ，TQ，LOPQ等等，其中OPQ，Multi-ADC的提升效果还是比较明显的.
假设我们的图片检索库有100万张图片，每张图片提取多个128维的特征向量，把这128维向量分成8个短向量，每个短向量是16维，也就是说检索库总共包含100万x8 这么多向量（我们暂且称为 8 堆短向量，每一堆有100万个短向量），我们把每一堆短向量都用 k-means 聚类为 256 类. 对于检索库里面的每一张图片都由多个128维的向量表示，把每个128维的向量分为 8 个 16 维的短向量，对于每一个短向量我们都找到他属于一堆短向量的 256 类中的哪一类（可是这里如果归错类了那么查找图片岂不是一步错步步错？又一疑问：如果把大量的库图片归类为这256类呢，而且还要索引好每一张图片的需要以方便查找，k-means算法可以具体实现这一步骤吗？），依此类推，8 个短向量分别在 8 个堆中查找属于256类中的哪一类，这样一张图片 8 个短向量的每一个短向量都有256种选择，即一张图片总共有256的8次方种选择（2的64次方，即相当于一幅图片的特征可以表示为64位（8x8bit）二进制数），这样图片库的数量就可以很大了（2的64次方），而查找query图片时，先在库里面对比 query 图片的第一个八分之一短向量，如果按照最近邻查找的方法（只找出和这个短向量最接近的 “1” 个类），在第一个短向量的判断后就丢弃了库里面不符合的 255/256 张图片，即接下来只要搜索 1/256 库的图片就行了，而在对比query的第二个八分之一短向量的时候又丢弃了 255/256 的图片，一共进行8次丢弃，这样以来查找的工作量就极大地减少了，而不用把query和库里面的每一张图片都对比.
From: https://blog.csdn.net/guanyonglai/article/details/78468673