向量量化

向量量化其实就是找附近既定的点，来当作一个区间的代表，从而简化资料量。参见下图，在-1到1的数值都会近似为0，在1到3的数值都会近似为2，以此类推，这些数值都会以0, 2, 4, 6的整数表示出来，以二进制编码可以用二位元表示之，从而压缩了资料。然而，若是资料并非平均分散在-1到7之间，而是有疏密分布，这样的话把量化点取在0, 2, 4, 6便会造成误差变大。为了要求失真达到最低，需要一个可以计算出使失真最小的少数代表向量(码向量)，这组码向量称之为编码簿(codebook)。

•  

  向量量化，一维的例子

映射

为了要产生量化的编码簿，需要以下是先定义及给定的资料：

1. 已知的向量源，作为训练的样本
2. 误差测量方法，可以是方均根误差等方法。
3. 编码簿的大小，意即要把向量空间切分为几个区域，量化为多少个值。

而计算的目的，就是为了寻找具有最小误差的编码簿，以二维的向量为例，如下图，便是寻找那些红色星星(编码)与画分空间的方法(蓝色线段)。假设给定的向量样本共有M个，每个的维度皆是k维，这些向量可以表示如下：${\displaystyle x_{m}={x_{(}m,1),\ \ x_{(}m,2),\ \ldots ,\ x_{(}m,k)\ },\ m=1,\ 2,\ \ldots ,\ M}$ 

而要对应过去的目标向量，也就是编码簿，假定编码簿大小为N，也就是将划分为N个区块，同样可以表示如下：

${\displaystyle y_{n}=\left\{y_{n,1},\ \ y_{n,2},\ \ldots ,\ y_{n,k}\right\},\ n=1,\ 2,\ \ldots ,\ N}$ 

每个编码簿里的码向量${\displaystyle y_{n}}$ 都有一个对应的区块${\displaystyle S_{n}}$ , 只要${\displaystyle x_{m}}$ 落在${\displaystyle S_{n}}$ 区块内，就会透过向量量化对应到${\displaystyle y_{n}}$ 。整个空间以${\displaystyle S}$ 表示，${\displaystyle S_{i}}$ 表示分割的子空间，对应函数为${\displaystyle Q}$ ，这样的映射表示如下：

${\displaystyle S=\left\{S_{1},\ S_{2},\ldots ,\ S_{n}\right\}}$ 

${\displaystyle Q\left(x_{m}\right)=y_{n}\ \ \ \ if\ x_{m}\in S_{n}}$ 

误差计算

经过映射后产生的${\displaystyle y_{n}}$ 与原本的${\displaystyle x_{m}}$ 之间存在一个非负值的误差，计为${\displaystyle d(x_{m},y_{n})}$ ，这个误差便是前述的误差测量方法算出来的值。将所有d的加总写为${\displaystyle D}$ ，为求表示简便，这里使用最常见且最广用的平方误差做为范例：

${\displaystyle \textstyle D=\sum _{m=1}^{M}\|x_{m}-Q(x_{m})\|^{2}\displaystyle }$ 
当然误差的计算可以随时更换，如增加权重、使用其他范数(norm)等等。这些误差测量的方法的共通点为，他们的计算都是从误差向量${\displaystyle x_{m}-Q(x_{m})}$ 出发的，故这些误差均可表示成此误差向量的函数。而更复杂的误差计算方法同样的在其他资料压缩领域有被使用，例如语音讯号处理等。
经过以上的步骤，向量量化的问题可以写为：

给定向量样本及编码簿大小，找到使平均误差最小的编码簿及空间划分。

上述使误差最小的映射函数，意即编码簿，需要透过样本向量的训练最佳化。基本的步骤如下：

1. 随机选一个样本点P
2. 将最靠近的量化向量质心朝向该样本点移动一小距离
3. 回到步骤一

为了确保所有在编码簿里面的量化向量都使用到，可以增设一个敏感度参数，训练步骤如下：

1. 将每一量化向量质心${\displaystyle c_{i}}$ 敏感度${\displaystyle s_{i}}$ 增加相同的量
2. 随机选择一个样本点${\displaystyle P}$ 
3. 令选取之样本点与各个量化向量质心的欧氏距离为${\displaystyle d(P,c_{i})}$ 
4. 寻找能使距离减敏感度${\displaystyle d(P,c_{i})-s_{i}}$ 为最小的量化向量${\displaystyle c_{i}}$ 
5. 将该质心${\displaystyle c_{i}}$ 朝向${\displaystyle P}$ 移动一小段距离
6. 将该质心之敏感度${\displaystyle s_{i}}$ 设为0
7. 回到步骤一

上述的步骤需搭配迭代门槛使解答收敛，如模拟退火法。

LBG算法

实际上的向量量化算法首先在1980由Y. Linde, A. Buzo, R. M. Gray 三位学者提出的^[1]，现在被称为LBG算法。此算法与k-means算法雷同，内容为不断调整映射范围及量化向量位置，使误差趋近于区域最小值。其迭代步骤如下：

1. 给定训练样本以及误差阈值
2. 订定初始码向量
3. 将迭代计数器归零
4. 计算总误差值，若不为第一次，则检查与前一次误差值差距是否小于阈值。
5. 根据每一个训练样本与码向量的距离d，找其最小值，定义为映射函数Q
6. 更新码向量：将对应到同一个码向量的全数训练样本做平均以更新码向量。

${\displaystyle c_{n}^{i+1}={\frac {\sum _{Q\left(x_{m}\right)=c_{n}^{i}}x_{m}}{\sum _{Q\left(x_{m}\right)=c_{n}^{i}}1}}}$ 

1. 迭代计数器加一
2. 回到步骤四，重复至误差小于阈值。

LBG算法十分依赖起始编码簿，产生起始编码簿的方法有以下几种：

乱码

随机挑选要求数量的码向量作为起始编码簿

分裂法

1. 先算出所有样本向量的重心(平均值)
2. 将目前的重心分裂成二倍个向量，并前后挪动一点距离使其分隔
3. 将新的向量作为丛聚的分类准则，重新分出二群样本向量
4. 再次将样本的分群中心算出
5. 回到步骤二，直至有足够数量个码向量。

最近相临集结法

1. 先将样本向量中每一个向量视为一个丛聚
2. 计算每个丛聚之间距离，取最小距离的二个丛聚合并之
3. 重复步骤二直至丛聚数量等于要求的编码簿大小。

向量量化常使用在有损资料压缩，这个方法可以将多为度的向量空间压缩至有限的离散子空间，向量维度同时被降低(仅需索引)，减少储存空间，因而压缩了资料。因为此方法会随着资料密度分布的变化影响权重，其压缩的失真比例会随着资料密度成反比。其具有简单的解码方式，仅须透过索引进行查表(Table lookup)即完成解码。压缩程度亦高，有较低的位元率。

编码簿设计与压缩需要耗费较多的时间，多数花费在寻找最近的码向量以及计算向量距离；且压缩后的影像品质与编码本的好坏关联度大，针对拥有不同统计特性的讯号，往往需要设计不同的编码簿，才能够实际使用上。

在80年代，向量量化亦使用于语音辨识，近年亦有研究将之使用在签名识别及影像特征搜寻上。实际应用上，训练完成的编码簿之中，与被识别目标(如语音讯号等)有最小误差的码向量，其对应的索引即代表识别的目标(使用者)。

1. ^ Linde, Y.; Buzo, A.; Gray, R. An Algorithm for Vector Quantizer Design. IEEE Transactions on Communications. 1980-1, 28 (1): 84–95 [2021-01-15]. ISSN 0090-6778. doi:10.1109/TCOM.1980.1094577. （原始内容存档于2020-10-20）.  请检查|date=中的日期值 (帮助)