（信源四）矢量量化算法--LBG

矢量量化，是70年代后期发展起来的一种数据压缩技术是一种高效的有损数据压缩技术，它具有压缩比大、解码简单和失真较小等优点。其基本思想是将若干个标量数据组构成一个矢量，然后在矢量空间给以整体量化，从而压缩了数据而不损失多少信息。矢量量化是香浓信息论在信源编码理论方面的发展，它的理论基础是香浓的率失真理论，率失真理论是一个存在性定理，并非是一个构造性定理，它未给出如何构造，矢量量化器的方法，矢量量化总是优于标量量化，这是因为矢量量化能有效地应用矢量中各，分量之间的4种相互关联性质来消除数据中的冗余度。自从1980年提出矢量量化器码书设计的LBG以来，矢量量化技术已经成功地应用到图像压缩和语音编码中。

LBG算法中的最佳矢量量化器设计的关键是最佳划分和最佳码书的设计。一是给定码书条件下寻找信源空间的最佳划分，使平均失真最小，由码书 和NNR得最佳划分，信源空间中的任一点矢量，如果它和码字的失真小于它和其它码字的失真；二是在给定划分条件下，寻找最佳码书，使平均失真最小。其思想如下所示： 

（1）随意选取n个图像块作为码字； 

（2）由这n个码字对所有的图像块进行划分，即分成n个集合，使每个集合中的图像块，都是与各码字距离中与对应的码字的距离        最小的； 
（3）由这n个集合的重心，得到n个新的码字； 

（4）如果这些个码字与原来的码矢量变化不大（收敛），就完成码书的训练，否则重新进行2、3步。

程序调试：

运行环境win10 VS2015

打开源代码运行是出现错误：无法打开unistd.h文件。

解决方案：在头文件库中新建一个unistd.h文件

#ifndef _UNISTD_H
#define _UNISTD_H 
#include <io.h> 
#include <process.h> 
#endif /* _UNISTD_H */#pragma once

  

此程序调试共分为3个部分：

1. trvqsp_img—获得图像矢量量化的码书（码数以分裂法初始化）

其命令参数为 ts_img codefile [-b cb_size] [-t block_height] [-w block_width] [-x row_size] [-y col_size]

ts_img：是训练图像，也即待量化压缩的图像

Codefile：以二进制格式存放码书的文件，有一个包含12个字节的文件头记录：向量的维度，以及码书的大小

-b cb_size：码书的大小

-t block_height：块的高度（以像素为单位）

-w block_width：块的宽度（以像素为单位）

-x row_size：输入图像的宽

-y col_size：输入图像的高

单步运行代码，命令参数为 earth.img earth_codefile_8_2x2 -b 8 -t 2 -w 2 -x 256 -y 256

tfp 指向输入待压缩图像文件，icb 指向存放码书的文件，( sscanf 与scanf 类似，都是用于输入的，只是后者以键盘(stdin)为输入源，前者以固定字符串为输入源。) 经过while循环，final_codebook_size = 8，blockr = 2，blockc = 2，row_size = 2，col_size = 2，为数据缓冲区 trimg 开辟图像大小的空间（char型），readimage( )函数将图像数据填入缓冲区，向量维数为 2*2 = 4，训练集个数 ts_size 为 256*256/4 = 16384，经过 for 语句循环，training_set （int型）和 trimg 的对应关系如图1（把trimg中一个像素即一个char型的数据转为int型赋给training_set）。

扰动eps固定为10，分裂法实现如下：

假定只有一个类：codebook_size = 1，先将所有训练集视为一个类，计算类中心（均值）作为测试矢量和输出水平，然后用 codebook_size 与 final_codebook_size 比大小，若假定的类的个数小于参数码书大小，则将一个类分裂成两个子类，即 codebook_size = 2*codebook_size，子类中心分别为原父中心的均值加一个扰动及原父中心的均值，vqencode( )函数返回失真较小的码书指针，count用来统计遍历训练集后，哪个码字失真更小的次数，再将每次迭代后的统计次数赋值给store，第一次迭代的失真指标是每次失真码字较小的失真总和除以训练集个数的平均值，从第二次迭代开始，每次都把上一次迭代的失真赋值给total_distortion_old，失真指标变成这一次失真相对于上一次失真减少的百分比，然后重新计算类中心（用new_codebook除以统计次数），再计算失真，循环下去，直到失真指标小于给定的阈值或迭代次数超过100次结束， 再用 codebook_size 与 final_codebook_size 比大小，循环下去，直到codebook_size 大于等于 final_codebook_size结束循环，再向码书文件中记录一些数据：块大小（宽、高），码书大小以及具体码字（大于255的一律记为255）。

其调试输出结果为：

2. vqimg_dec—根据码书文件和压缩后的文件重构原始图像

其命令参数为 [-i cmpfile] [-o imageout]

-i cmpfile：压缩文件名

-o imageout：重建图像文件名

单步运行代码，命令参数为 -i earth_cmp_8_2x2 -o earth_8_2x2.img

从压缩文件中读取码书文件名的长度，为存储文件名开辟空间，再从压缩文件中读取码书文件名赋值给cbfile，然后打开码书文件，再从压缩文件中读取原图像的宽和高，为数据缓冲区outimg开辟存储重建图像数据的空间，从码书文件中读取块的宽和高以及码书大小，计算每个码字需要的比特数，为码书开辟空间，从码书文件中逐字节的读取码字填入刚刚开辟的码书数据缓冲区，unstuff( )函数将压缩文件中的码字索引读入buffer中，然后重建图像，每个图像块先从buffer中读出码书索引，然后将对应的码字赋给该图像块。

其vqimg_dec调试输出结果如下：

3. vqimg_enc—根据码书对图像进行矢量量化

其命令参数为 [-i imagein] [-o cmpfile] [-c codebook] [-x row_size] [-ycol_size]

-i imagein：输入的待编码的图像文件名

-o cmpfile：输出的量化压缩后的文件名

-c cmpfile：码书文件

-x row_size：输入图像的宽

-y col_size：输入图像的高

单步运行代码，命令参数为 -i earth.img -o earth_cmp_8_2x2 -c earth_codefile_8_2x2 -x 256 -y 256ifp 指向输入的待编码的图像文件，ofp 指向输出的量化压缩后的文件，经过一系列赋值之后，将codebook文件名的长度以及文件名、原图像的高和宽写入输出文件，从码书文件中读出块的宽和高以及码书大小分别赋值给各参数，计算每个块需要多少比特来表示，numbits = 3bits，为码书开辟空间，从码书文件中读取码字，然后通过 vqencode( )函数来衡量每个图像块距离最近的码字索引index，stuffit( )函数将一个整字节（8比特）的编码赋值给save，再写入输出文件，filled用来表示一个字节中有几比特码字已经填好，move表示移位的位数，直到16384个训练集都遍历完毕， end_flag = 1，编码完毕，跳出for循环，最后计算平均失真。

其vqimg_enc调试输出结果如下图所示：