乘积量化（Product Quantization）算法原理

一、简介

乘积量化（PQ）算法是和VLAD算法是由法国INRIA实验室一同提出来的，为的是加快图像的检索速度，所以它是一种检索算法，在矢量量化（Vector Quantization，VQ）的基础上发展而来，虽然PQ不算是新算法，但是这种思想还是挺有用处的。

它原文中是接在VLAD算法后面，假设我们使用VLAD算法获得了1M（1024K）的图像表达向量，向量的维度为D=128，则对于一幅查询图像来说，我们需要计算1M（1024K）个余弦距离，这样实时性就比较差。

所以如何加快这种距离的计算速度就是PQ算法所要完成的任务。当然为了解决这个问题，已经有很多算法被提出了，如KDTree，LSH，ITQ等都是为解决这个问题而提出的，属于KNN或ANN范畴。

二、空间切分

首先，PQ先将D维空间切分成M份：即将128维空间切分成M个D/M维的子空间，如下图所示M=8（在原文中，作者由于是在PCA之后进行的PQ检索，所以进行了一个随机旋转，因为PCA之后特征值的顺序是按照从大到小排列的）。

用代码表示就是把向量维度切分：