实验内容

ALPD公司(爱乐普第)名下ALPDOJ(爱乐普第Orange Juice)的销售部小李在系统上尝试添加一个新的产品，但是因为服务器空间寸土寸金，技术员小王限制了产品的示意图只能在500kb，而小李要传的示意图高达3mb，这让他感到很苦恼。于是小李找到小王问能不能提高下文件大小的限制，小王满嘴你知不知道现在硬盘多贵带宽多贵把小李打发走了，这下小李彻底懵了。产品马上就要上市了，网站上可不能没有示意图，走投无路的小李听说你上次为小王压缩了服务器的日志文件，便通过各种渠道又找到了你，希望你能帮帮他压缩一下这些图片，不然消费者看不到示意图销量上不去可是要被炒鱿鱼的。

设计思路与功能描述

项目思路说明

压缩算法思路说明

本次实验的图片压缩算法整体上借鉴同学的分享内容，即主要基于离散余弦变换与huffman编码来进行压缩，该压缩算法的流程框图如下：

通过上述流程框图不难看出，压缩算法主要由6个部分组成，以下将对这六个环节进行逐一说明。

①将图片分割为小块。由于一般的图片信息处理算法都是针对8×8的像素矩阵来说明的，所以应当将原图片划分为多个8×8的小块，进而方便后续压缩、编码过程中能够逐一对每个小块进行操作。

②将图片更换为YCbCr方式存储。由于对于肉眼来说，对于亮度的敏感性远大于对于色调的敏感性，所以当我们以YCbCr方式存储时，就可以在一定程度上忽略Cb、Cr参数的一些“细节”，而只要保证Y参数的准确性即可。从而可以节约一定的文件大小。

③使用离散余弦变换

离散余弦变换是压缩为jpg图片的核心算法，对于8×8像素矩阵中的每一位置，都可以给出该位置经过离散余弦变换后的结果为：

经过上述离散余弦变换之后，就可以使得图片中较为重要的信息置于F矩阵的左上角，而使得右下角的元素尽可能的靠近于0。从而便于在后续的操作中在F矩阵中得到更多的0，从而达到大幅压缩的目的。

④进行数据量化

由于第三步操作的结果往往是一些小数，而计算机中浮点数的存储往往要占据比整数多得多的空间，不利于压缩率的降低。所以此时应当进行一次数据量化，而数据量化的方式就是让F矩阵中的值与量化系数矩阵Q中对应位置的值相除，并四舍五入取整，从而得到新的矩阵B。

值得一提的是，量化系数矩阵Q的选定是任意的，可以根据实际的开发需要进行选取。但在一般情况下，为了保证亮度信息Y能够尽可能多的保留，亮度信息对应的量化系数矩阵的数值一般较小，借以保留更多的亮度信息；同时为了降低压缩率，可以在一定程度上忽略CbCr信息，所以Cb、Cr对应的量化系数矩阵Q中的元素应当较大一些，使得更多的元素变为0。

而在本次试验中，选取的是推荐的标准亮度量化表与标准色差量化表。

⑤使用zigzag处理为向量

由于信息是存储在计算机中的磁盘上的，而磁盘上数据的存储是线性的，所以在这里应当采用某种方法将量化后的二维矩阵转化为便于计算机存储的向量形式。

而在jpg图片压缩中，常使用的是zigzag方法，该方法就是从（0，0）元素开始，依次斜向绕行，碰到边界后就沿着边界延伸一个单位，再沿着反向的斜线折回，直至遍历完数组中的所有元素。

⑥编码压缩

编码压缩的过程主要分为RLE编码与哈夫曼编码两个步骤。首先应当进行的是RLE编码。

由于在第④步中，发现量化后的矩阵只有左上角有较密集的有效信息，右下角的元素基本上均为0；而该矩阵经过第⑤步的zigzag处理后，正好可以让不为0的元素集中在向量头部，而尾部则填充着大量的0元素。

而RLE算法就是将原本的相量转化为一些列数对，每个数对表示相邻两个不为0的元素之间隔着多少个0。这一编码方式恰好与zigzag处理后向量中含有大量连续0的特点契合，从而可以实现较低的压缩率。

在我们得到这一系列数对后，为了进一步降低压缩率，可以采用哈夫曼编码对这些数对进行编码。不同于第一次大作业中哈夫曼编码的定义，本次试验中的哈夫曼编码更像是一种“打表”行为——即按照已经给定好的哈夫曼表，分别查找每一个数对元素对应的编码即可。

在本次实验中，由于上述两种编码可以在对向量从前向后的遍历中同时平行进行。所以在代码实现中，没有采用杨闻笛同学分享的一次编码的方式，而是采用一次遍历同时编码的方式来实现。

JPG格式编码的思路说明

相交于前文中压缩算法的实现，对JPG格式的编码就显得较为简单容易，只需要对照着官方文档的说明依次在对应的位置写入合适的二进制码即可。http://www.biyezuopin.vip

按照网上查阅到的官方文档的说明，JPG文件编码的文件头主要包括如下内容：

①SOI（0xFFD8）

表示图像的开始，此时只需要写入0xFFD8即可。

②APP0（0xFFE0）

这里是应用程序的标记，应当留0。此时在写入完APP0后，应该依次写入应用标志长度与标志（“JFIF”）。之后再依次输入主次版本号、单位、水平与竖直分辨率以及水平与竖直点数。

③DQT（0xFFDB）

这里是说明该图片的量化表，在写入完DQT后，首先写入标志长度，在本实验中为132，其次应当逐次以Z型输入本图片使用的量化表。

④SOF0（0xFFC0）

该命令用于表示帧图像开始标记，应当依次写入参数长度、采样精度、行列数、分量数、分量标记、采样因子。使用的量化表以及对应的比例值。

⑤DHT（0xFFC4）

该命令用于定义本张图片所使用的哈夫曼表，在写入完该命令标志与标志长度后，就应当按照高四位表示编码，第四位表示标志的方式进行输入。值得一提的是，高四位中0开头表示DC，1开头表示AC；而第四位中，0开头表示Y，1开头表示C。

⑥SOS（0xFFDA）

该命令表示开始扫描，自此往后，开始向jpg文件写入之前编好码的图片信息，也是图片的主体信息。

⑦EOI（0xFFD9）

该命令表示JPG图片文件写入结束，即作为终结符。

功能描述

压缩文件生成说明

将本次实验编码得到的.exe文件与lena.tiff文件置于同一个文件夹中，再通过windows的cmd窗口进入到对应文件夹，即可执行将该文件转化为.jpg文件的操作。

具体流程演示如下：

①将.exe文件与lena.tiff文件置于同一个文件夹

②在cmd窗口使用cd命令进入该目录

③在cmd窗口输入compress命令

发现弹出提示语，同时在平行目录下生成了对应的lena.jpg

④用windows自带的图片查看器查看图片，发现可以成功打开并显示

图片展示命令说明

在上述操作的基础上，可继续在cmd窗口中使用-read命令

可以使用easyX自带的框架查看该图片

按下任意键后可退出查看。

项目亮点与情况说明

项目亮点

①本次大作业实现了A组方法3与B组方法2，自认为以较高的完成度（90%）完成了本次大作业；

②本次大作业的最终程序Z_3.exe并没有写死，可以用于转换、查看多种不同规格的jpg文件；

③在编码的部分，采用了一次遍历同时进行RLE编码与哈夫曼编码的方式来替代原有的两次遍历过程；

④以lena.tiff为例，本程序将原本769KB的图片在肉眼可接受的范围内压缩至48KB，压缩比为6.24%，远低于OJ要求的70%。http://www.biyezuopin.vip

诸多情况说明

①没有使用分享课上同学给出的DC、AC表

在程序开发的初期，我是按照杨闻笛同学分享课上给出的推荐编码表（https://www.cnblogs.com/buaaxhzh/p/9119870.html）来进行编写的。但在调试的过程中，发现不论如何调整，图片都是乱码，如下图所示：

这一bug我加起来调试了两三天，在重写其他模块依旧无解的情况下，我只好选择放弃推荐编码表重写这一模块。

在最终程序中使用的编码表参考了中AcTarjan先生的编码表。在对照着AcTarjan先生的代码重写了SOS哈夫曼编码模块后，没有再出现该色块的bug。

经过我个人的思考，我认为出现这种bug的原因可能是我在使用推荐编码表的过程中，对其中的转换方式没有参透，导致出现了纰漏，最终产生bug。

②没有实现B组方法3。

方法3本质上就是jpg图片的解码，该过程本身并不是很难。但正如前文所述，我在哈夫曼编码的过程中debug花费了过长的时间，并多次重写了诸多模块，导致最后并没有余下足够的时间来实现方法3。

但在总体上，我认为本次大作业的完成度较好。

遇到的问题与解决方法

遇到的问题

在重写完上述哈夫曼模块后，运行程序可以看到生成的.jpg文件没有了乱码，但色调与亮度明显不合适——我愿称之为“阴间配色”。

解决方法

解决方法类似于之前大作业一的解决方法，我使用二进制查看器对我自己代码生成的图片与现有程序生成的jpg图片进行逐字节比对，最终发现了问题的根源。

我在编写代码时，只是注意到了jpg文件中每个像素的大小为1个字节，使用了char类型来存储对应值；但却忽略了该类型值不能为负的前提，没有使用unsigned修饰。

这就使得一些本来高亮的色块，因为其亮度值大于127，而“被迫”变为负值，最终使得整个图片看起来较为阴暗。添加了unsigned修饰后的代码为：

在修改代码后，即可生成正确的lena图片。