转发 | 轻翻那些永垂不朽的诗篇 第三章 小波系数图像压缩编码
本期看点
小波系数的各类编码方案大比拼
第三章 小波系数图像压缩编码
3.1 引言
由于多媒体信息和数字化的图像表示形式所带来的网络流量的不断增加，图像压缩已经成为一种刚需。基于小波的图像压缩新算法被开发出来，这些方法取得了实际性进展，如：卓越的低比特率性能、连续音调和比特级压缩、无损和有损压缩、逐像素、精度和分辨率传输等。小波算法最成功的应用之一是基于变换的图像压缩，其重叠特性减轻了块效应（马赛克被放大的场景）；而小波分解的多分辨率特性又使解压后的图像具有更好的感知质量。前期相关文章已经涉及到小波变换的部分内容，这里再继续对其展开详细描述。
3.2 基本原理
大多数图像的共同特征是相邻像素是相关的，所以便包含了很多冗余信息。然后，最重要的任务是找到图像中不太相关的表示。压缩的两个基本组件就是冗余和无关性的减少：
- 冗余减少的目的是消除信号源（图像/视频）的重复。
- 无相性的减少则是忽略了信号接收器即人类视觉系统（HVS）通常不会注意到的部分信号。
另外，通常也有三种类型的冗余：
- 相邻元素之间的空间冗余或相关性。
- 不同颜色平面或光谱带之间的光谱冗余或相关性。
- 图像序列相邻帧之间的时间冗余或相关性（主要就是视频应用）。
因此，图像压缩的目标就是希望尽可能地去除空间和光谱冗余以减少表示图像所需的比特位数。另外，图像压缩还需保证一个基本目标：降低传输或存储比特率的同时保持可接受的保真度或图像质量。
3.3 高低频分离&&量化
大多数自然图像都有平滑的颜色变化，在平滑变化之间，精细的细节被表示为尖锐边缘。从技术上讲，颜色的平滑变化被称为低频变化，尖锐变化被称为高频变化。低频成分构成了图像的基础，高频成分则是为了细化图像。因此，基础比细节相对更重要。类似的，我们在声乐领域也能找到相对应的概念 —— 基音与泛音，基音是波形里振幅最大，频率最小的组成波，它决定了音高；而泛音频率是基音的整数倍，跟基音叠加在一起后整体波形仍是基音的频率，但加入泛音组成后波形的形态不再单纯，可以理解为对基音作了一定的修饰，即决定了音色。
分离多数采用离散小波变换（DWT），通过滤波器组对图像进行一系列类似金字塔型的操作。基于小波的编码在传输和解码错误下具有更强的鲁棒性（编者注：鲁棒性亦称健壮性，是指系统在不调整其初始稳定配置的情况下抵抗更改的能力。），有利于图像的渐进传输（编者注：渐进传输以用户需求驱动，通过分层、分批的数据传输方式，仅向用户传输能满足需求的数据，从而减小冗余数据传输，提高网络带宽利用率，进而提高系统响应速度和性能）。此外，它们也更符合人类视觉系统的特点。
量化，是指用有限的、较小的值集来逼近图像数据中连续的值集的过程。有两种类型的量化，分别是标量量化（编者注：动态范围分为若干小区间，每个区间有一代表值，量化时落入小区间的信号值用代表值代替，称为标量量化。）和矢量量化（编者注：若干标量数据组成一个矢量，把矢量空间氛围若干区域，每个区域有代表矢量，量化时落入小区间的矢量用代表矢量代替，称为矢量量化。）。
3.4 度量指标
两类用于比较各种图像压缩技术的指标是均方误差（MSE）和峰值信噪比（PSNR），MSE值越小，误差越小；PSNR值越大，信噪比越高，其中，“信号”是原始图像，“噪声”是重建时的误差。因此，具有较低MSE和较高PSNR的压缩方案可被认为是较好的压缩方案。
3.5 小波系数的各类编码方案
3.5.1 嵌入式零树小波编码（EZW）
EZW是最早展现基于小波图像压缩的全部能力的算法之一，其编码器基于渐进式编码，将图像压缩成一个bit流。因为渐进编码又叫做嵌入式编码，所以即EZW中的E。下面是EZW算法对大小为512 × 512图像的压缩比和PSNR值的结果：
下一个方案称为 SPIHT，是 EZW 的一种改进形式，比 EZW 有着更好的压缩性能。
3.5.2 多级树集合分裂编码（SPIHT）
SPIHT编码器是EZW编码的一个高度精细化版本，同样可产生嵌入的bit流。对于各类图像，SPIHT可获得最佳结果 —— 给定压缩比下，PSNR值最高。所以，它是图像压缩中最先进的基准算法。
SPIHT不是传统图像压缩算法的简单扩展，它代表了该领域的一个里程碑式进展，具有以下性质：
- 图像质量好，PSNR值高，尤其对于彩色图像
- 是优化好的渐进式图像传输
- 生成一个完全嵌入的编码文件
- 简单量化算法
- 快速编/解码（几乎对称分布）
- 应用范围广、适应性强
- 可用于无损压缩
- 可以编码到精确的比特率或失真
- 高效结合误差保护
SPIHT可以通过对输出信息进行熵编码（编者注：即编码过程中按熵原理不丢失任何信息的编码。）来提高效率，但代价是增加了编/解码的时间。同时为了减少此方案中使用的列表数量，需要形成下一个算法，称为 SPECK。
3.5.3 设置分区嵌入式块编码(SPECK)
SPECK不同于上述的一些方案，它不使用跨越不同子带（编者注：子带编码技术，是将原始信号由时间域转变为频率域，然后将其分割为若干个子频带，并对其分别进行数字编码的技术。子带指子频带）的树，而是以块的形式使用集合。主要思想是利用变换后的图像层次结构中频率和空间能力的聚类，根源还是SPIHT中发展出来的思想。
SPECK具有标量量化显著性测试方案的全部特性：
- 是完全嵌入的 —— 为了实现最好的重建效果，一个编码的比特流可用来解码任何速率小于等于编码速率的图像
- 采用递进传输源样本按其信息内容的降序编码
- 计算复杂度低 —— 算法非常简单，主要是比较，不需要任何复杂的计算
- 较低的动态内存需求 —— 在编码过程中的任何给定时间，只有一个连接区域(完全位于子带内)被处理
- 快速的编/解码 —— 这是由于算法的低复杂度，对应了第3点
- 高效的性能 —— 其效率可与目前可用的其他低复杂度算法相媲美
解码器使用与编码器相同的机制。它接收编码位流的显著性测试结果，并在算法执行过程中建立相同的列表结构。因此，对于不同集合的显著性测试，它能够遵循相同的执行路径，并随着算法的进行逐步重建图像。可以看出，SPECK 具有更高的压缩比。这显示了以块的形式处理集比空间方向树的形式处理集的优势。与 SPIHT 相比，对于相同的分解级别和丢弃的位平面，这些压缩比下的重建图像具有可观的分辨率。
在分解层次较少的情况下，SPECK重建图像的分辨率即清晰度优于 SPIHT。
3.5.4 优化截断的嵌入式块编码（EBCOT）
EBCOT 将每个子带划分为相对较小的样本块，并生成一个独立的高度可伸缩的比特流来表示每个所谓的代码块。该算法展示了最先进的压缩性能，同时产生一个前所未有的特征集的比特流，包括分辨率和信噪比可伸缩性以及随机访问属性。该算法具有适度的复杂性，非常适合于涉及远程浏览大型压缩图像的应用。
可见，在最先进的压缩算法方面，EBCOT显著优于SPIHT。
3.5.5 其他
此外，还有许多小波系数相关衍生编码技术，如小波差约简（WDR）、自适应扫描小波差约简（ASWDR）、空频量化（SFQ）、嵌入式预测小波图像（EPWIC）、可逆嵌入小波压缩（CREW）、堆栈运行（SR）等，这里不再一一赘述，各种编码技术的优缺点详见下表：
| 类型 | 特性 | 不足 |
|---|---|---|
| EZW | 采用渐进和嵌入式传输 / 使用零树概念 / 用单个符号编码树 / 使用预定义的扫描顺序 / 良好的结果反馈 | 系数位置的传输丢失 / 没有真正压缩 / 依赖于算数编码器 |
| SPIHT | 广泛使用 —— 对于各类图像都有较高PSNR值 / 四叉树或层次树被设置为分区树 / 采用空间定向树状结构 / 通过三个列表跟踪索引集的状态：LSP、LIS、LIP / 采用渐进和嵌入式传输 / 在感知图像质量和PSNR值上优于JPEG | 仅隐式定位有效系数的位置 / 由于三个列表致使内存需求更多 / 传输信息只由单个bit组成 / 适合各种自然图像 / 感知质量不是最优的 |
| SPECK | 不使用树 / 使用矩形块区域 / 利用频率和空间的能量聚集 / 采用渐进和嵌入式传输 / 低计算复杂度 / 采用四叉树和倍频带划分 / 由于两个列表致使内存需求低 / PSNR值优于SPIHT | |
| EBCOT | 支持数据包分解 / 基于块的方案 / 适度复杂性 / 比特流由质量层集合组成 / 信噪比具备可伸缩性 / 出色的纹理表现 / 保留SPIHT中丢失的边 | 性能随层数的增加而降低 / 适合远程浏览大型压缩图像 |
| WDR | 采用ROI概念 / 对重要小波变换值的位置进行编码 / 感知图像质量相比SPIHT更好 / 不用像SPIHT那样在四叉树中搜索 / 适合低比特率的低分辨率医学图像 / 低复杂度 / 高边缘相关性 / 高边缘保护性 | PSNR值没有SPIHT高 |
| ASWDR | 与WDR相比更改了扫描顺序 / 可预测新关键值的位置 / 动态适应边缘细节的位置 / 相比WDR能编码更多关键值 / PSNR值优于SPIHT和WDR / 感知图像质量优于SPIHT、略优于WDR / 边缘相关性略优于WDR / 保留更多细节 / 适合如侦察或医疗类的高压缩率图像 | |
| SFQ | 其量化模式直接利用了高频系数的空间聚类 / 均匀量化+熵编码提供了几乎最优的效率 | |
| CREW | 适合于需要高质量的灵活性应用如医疗图像、固定速率大小的程序(ATM)、印前图像、连续色调传真、图像档案、万维网图像、卫星图像等 | |
| SR | 通过光栅扫描工作从而寻址复杂度相比其他算法较低 |
本章缩略语汇总
| 缩写 | 英文 | 中文 |
| ASWDR | Adaptively Scanned Wavelet Difference Reduction | 自适应扫描小波差约简 |
| ATM | Asynchronous Transfer Mode | 异步传输模式 |
| CR | Compression Ratio | 压缩比 |
| CREW | Compression with Reversible Embedded Wavelets | 可逆嵌入小波压缩 |
| DWT | Discrete Wavelet Transform | 离散小波变换 |
| EBCOT | Embedded Block Coding with Optimised Truncation | 优化截断的嵌入式块 |
| EPWIC | Embedded Predictive Wavelet Image Coder | 嵌入式预测小波图像 |
| EZW | Embedded Zerotree Wavelets | 嵌入式零树小波 |
| GW | Geometric Wavelet | 几何小波 |
| HVS | Human Visual System | 人类视觉系统 |
| LIP | List of Insignificant Pixels | 不重要像素列表 |
| LIS | List of Insignificant Sets | 不重要集合列表 |
| LSP | List of Significant Pixels | 重要像素列表 |
| MSE | Mean Square Error | 均方误差 |
| PSNR | Peak SignaN-to-noise Ratio | 峰值信噪比 |
| ROI | Region Of Interest | 感兴趣区域 |
| SFQ | Space Frequency Quantization | 空频量化 |
| SPECK | Set Partitioned Embedded bloCK | 设置分区嵌入式块 |
| SPIHT | SetPartitioning in Hierarchical Trees | 多级树集合分裂 |
| SR | Stack Run | 堆栈运行 |
| WDR | Wavelet Difference Reduction | 小波差约简 |
前期回顾
第一章：数据压缩理论缘起——摩斯密码开创编码领域先河，信息熵用数学语言阐明了概率与信息冗余度的关系
第二章：Huffman码——用生活中的烹饪视角解析Huffman编码过程
后期预告
第四章 第二代图片压缩技术——8大压缩算法的大比拼
第五章：计算机视觉中的女神 —— Lenna——带你走进女神
第六章：无线传感器网络数据压缩——实践是检验真理的唯一标准
ELT.ZIP是谁？
ELT<=>Elite(精英)，.ZIP为压缩格式，ELT.ZIP即压缩精英。
成员：
上海工程技术大学大二在校生
合肥师范学院大二在校生
清华大学大二在校生
成都信息工程大学大一在校生
黑龙江大学大一在校生
山东大学大三在校生
ELT.ZIP是来自6个地方的同学，在OpenHarmony成长计划啃论文俱乐部里，与来自华为、软通动力、润和软件、拓维信息、深开鸿等公司的高手一起，学习、研究、切磋操作系统技术…
技术DNA
数据压缩的历史
图片来源：https://visual.ly/community/Infographics/computers/history-data-compression
ELT.ZIP（III部压缩算法）技术地图
智慧场景
参考文献
[1] Vitter, Scott J . Design and analysis of dynamic Huffman codes[J]. Journal of the Acm, 1987, 34(4):825-845.
https://dl.acm.org/doi/10.1145/31846.42227
[2] Peng J , Kim C S , Kuo C C J . Technologies for 3D mesh compression: A survey[J]. Journal of Visual Communication & Image Representation, 2005, 16(6):688-733.
http://mcl.usc.edu/wp-content/uploads/2014/01/200503-Technologies-for-3D-triangular-mesh-compression-a-survey.pdf
[3] Holtz K . The evolution of lossless data compression techniques[C]// Wescon/93 Conference Record. IEEE, 1993.
https://ieeexplore.ieee.org/document/488424
[4] Kimura N , Latifi S . A survey on data compression in wireless sensor networks[C]// International Conference on Information Technology: Coding and Computing (ITCC’05) – Volume II. IEEE, 2005.
[5] Sudhakar R , Karthiga M R , Jayaraman S . Image compression using coding of wavelet coefficients–a survey[J]. A Survey”, ICGST-GVIP Journal, Volume (5), Issue, 2005(6):25-38.
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.463.1615&rep=rep1&type=pdf
[6] Li W C , Ang L M , Seng K P . Survey of image compression algorithms in wireless sensor networks[C]// International Symposium on Information Technology. 2008.
[7] Hamming R W . Coding and information theory (2. ed.)[M]. DBLP, 1986.
https://dblp.org/rec/books/daglib/0068879.html
[8] 高锐智, 华成英. 汉字字形结构式压缩方法的研究和实现[J]. 计算机科学, 2003, 30(005):78-81.
https://www.jsjkx.com/CN/article/openArticlePDF.jsp?id=15270
[9] Zhang C N , Wu X . A hybrid approach of wavelet packet and directional decomposition for image compression[J]. Wiley Subscription Services, Inc. A Wiley Company, 2002, 12(2):51-55.
https://ieeexplore.ieee.org/document/808039
[10] Kunt, M, Ikonomopoulos, et al. Second-generation image-coding techniques[J]. Proceedings of the IEEE, 1985.
https://dl.acm.org/doi/abs/10.1145/248621.248622
写在最后：
OpenHarmony 成长计划—“啃论文俱乐部”（以下简称“啃论文俱乐部”）是在 2022年 1 月 11 日的一次日常活动中诞生的。截至 3 月 31 日，啃论文俱乐部已有 87 名师生和企业导师参与，目前共有十二个技术方向并行探索，每个方向都有专业的技术老师带领同学们通过啃综述论文制定技术地图，按“降龙十八掌”的学习方法编排技术开发内容，并通过专业推广培养高校开发者成为软件技术学术级人才。
啃论文俱乐部的宗旨是希望同学们在开源活动中得到软件技术能力提升、得到技术写作能力提升、得到讲解技术能力提升。大学一年级新生〇门槛参与，已有俱乐部来自多所高校的大一同学写出高居榜首的技术文章。
如今，搜索“啃论文”，人们不禁想到、而且看到的都是我们——OpenHarmony 成长计划—“啃论文俱乐部”的产出。
OpenHarmony开源与开发者成长计划—“啃论文俱乐部”学习资料合集
1）入门资料：啃论文可以有怎样的体验
https://docs.qq.com/slide/DY0RXWElBTVlHaXhi?u=4e311e072cbf4f93968e09c44294987d
2）操作办法：怎么从啃论文到开源提交以及深度技术文章输出https://docs.qq.com/slide/DY05kbGtsYVFmcUhU
3）企业/学校/老师/学生为什么要参与 & 啃论文俱乐部的运营办法https://docs.qq.com/slide/DY2JkS2ZEb2FWckhq
4）往期啃论文俱乐部同学分享会精彩回顾：
同学分享会No1.成长计划啃论文分享会纪要（2022/02/18） https://docs.qq.com/doc/DY2RZZmVNU2hTQlFY
同学分享会No.2 成长计划啃论文分享会纪要（2022/03/11） https://docs.qq.com/doc/DUkJ5c2NRd2FRZkhF
同学们分享会No.3 成长计划啃论文分享会纪要（2022/03/25）
https://docs.qq.com/doc/DUm5pUEF3ck1VcG92?u=4e311e072cbf4f93968e09c44294987d
现在，你是不是也热血沸腾，摩拳擦掌地准备加入这个俱乐部呢？当然欢迎啦！啃论文俱乐部向任何对开源技术感兴趣的大学生开发者敞开大门。
后续，我们会在服务中心公众号陆续分享一些 OpenHarmony 开源与开发者成长计划—“啃论文俱乐部”学习心得体会和总结资料。记得呼朋引伴来看哦。
扫码添加 OpenHarmony 高校小助手，加入“啃论文俱乐部”微信群