《老子到此一游系列》之 老子为什么是老子 ——综述视角解读压缩编码 第二章 小波变换(转发)
ELT.ZIP是谁？
ELT<=>Elite(精英)，.ZIP为压缩格式，ELT.ZIP即压缩精英。
成员：
上海工程技术大学大二在校生 闫旭
合肥师范学院大二在校生 楚一凡
清华大学大二在校生 赵宏博
成都信息工程大学大一在校生 高云帆
黑龙江大学大一在校生 高鸿萱
山东大学大三在校生 张智腾
ELT.ZIP是来自6个地方的同学，在OpenHarmony成长计划啃论文俱乐部里，与来自华为、软通动力、润和软件、拓维信息、深开鸿等公司的高手一起，学习、研究、切磋操作系统技术…
本文的梳理来自其中的四名同学：闫旭、楚一凡、赵宏博和高云帆。
前期回顾
第一章：轻松上手——《伟大的计算原理》和《数据压缩技术调查：从数据质量、编码方案、数据类型和应用的角度》
第二章 小波变换（Wavelet Transform）
2.1 引言
小波变换是目前比较流行的图像压缩算法，也是近30年来一个迅速发展的新领域。我们知道，JPEG图像压缩通过舍弃部分人眼基本会忽略的颜色信息位，以减小原始图像的大小，由于无法恢复原始的图像位，因此，常用的JPEG算法是一种有损压缩算法。而小波变换能够巧妙地将空间域和频域特性相结合，从而实现图像的无损压缩，所以小波变换是图像领域的重点和难点。小波变换用于图像压缩的核心是系数编码，压缩的实质是对系数的量化压缩。
2.2 小波变换原理
- 寻求空间L^2(R)上的标准正交小波基。
- 将信号在小波基上分解，便于进行分析和处理。
- 可通过分解系数重建原来的信号。
由于小波变换的多方面特点，导致其在数字信号的处理上不方便，因此实际应用常采用离散小波变换（DWT），同时小波变换也要跟随图像的性质从一维推广到二维。任何图像都可以分为低频（L）和高频（H）部分，低频包含了图像的主要信息，高频主要是图像的细节纹理。小波转换会把图像分为4个子带（Sub Bands）：LL，LH，HL，HH。其中低频子带LL包含图像主要信息，而高频子带（LH，HL，HH）包含了图像的细节信息。LL子带可以再次通过小波转换进行二次转换生成新一级子带，以此类推，形成类似下图的金字塔型分解结构：
将一副图像根据二维小波变换算法进行变换后，将会得到一系列不同分辨率的图像。低频部分部分是表现一幅图像最主要的部分，如果只保留低频部分丢弃高频部分，图像数据便可压缩。
2.3 参考代码
2.4 研究方向
2.4.1 小波系数零树(EZW)的嵌入式图像编码
嵌入式零树小波编码EZW（Embedded Zerotree Wavelets Encoding）是指基于图像小波变换的数学结构，是J.M.Shapiro提出的一种高效的小波图像压缩算法，这个算法中有两个重要的概念：嵌入式编码和零树。
嵌入式编码（Embedded Coding）是指编码器具有这样的特点：一个低比特编码嵌入在码流的开始部分，即从嵌入式码流的起始至某一位置这段码流被取出后，它相当于是一个低码率的完整码流，由它可以解码重构这个图像，与原码流相比，这个部分码流解码出的图像具有更低的质量或分辨率，但解码的图像是完整的。嵌入式码流中的比特的重要性是按次序排列的，排在前边的比特更重要。由于EZW这个特点，不必先验训练和精度率控制，因此嵌入式码流非常适用于图像的渐进传输、图像浏览和因特网上的多媒体图像广播，这是它的优点。
零树结构的目的是为了高效地表示小波变换系数矩阵中非零值的位置（有效值映射）。EZW有如下特性：
- 按重要性创建比特流，产生完全嵌入的代码，因此简单、有效；
- 定义的二进制决策可以将图像与空图像或灰色图像区分；
- 达到目标速率时，可以终止编码和解码过程。
2.4.2 无损加密后压缩(ETC)技术
ETC（Encryption Then Compression）需要先加密后压缩。优点是可在确保图像安全性的同时实现更高的压缩性能。
借助上文的小波变换原理，我们首先利用二维DWT（离散小波变换）将原始数据分割成重要与不重要的部分。这部分的结果为DWT近似子带(LL)和确切的小波子带（LH、HL、HH），其中L代表低，H代表高。分解后，使用伪随机数生成器(PRNG)序列生成的伪随机数对LL进行加密。在对LL进行加密后，再对确切子波带LH、HL、HH进行有效的加密和压缩。近似子带的系数是关键的，而确切子带则被视为不那么关键。LL使用加法模数256进行加密，确切子波带使用系数排列进行加密。加密后，这些条带被排列为LL、LH、HL和HH。该通道提供了一种单独压缩频带的有效技术。首先，利用SVD对加密的子频带进行量化，并利用霍夫曼编码进行无损压缩。
参考文献
[1] J. M. Shapiro, “Embedded image coding using zerotrees of wavelet coefficients,” in IEEE Transactions on Signal Processing, vol. 41, no. 12, pp. 3445-3462, Dec. 1993, doi: 10.1109/78.258085.
https://web.stanford.edu/class/ee398a/handouts/papers/Shapiro%20-%20EZT.pdf
[2] Uthayakumar J , Vengattaraman T , Dhavachelvan P . A survey on data compression techniques: From the perspective of data quality, coding schemes, data type and applications – ScienceDirect[J]. Journal of King Saud University – Computer and Information Sciences, 2018.
https://www.sciencedirect.com/science/article/pii/S1319157818301101
[3] Kumar M , Vaish A . An efficient encryption-then-compression technique for encrypted images using SVD[J]. Digital Signal Processing, 2017, 60:81-89.
https://www.sciencedirect.com/science/article/abs/pii/S1051200416301348
[4] 阳婷, 官洪运, 章文康,等. 基于小波变换的图像压缩算法的改进[J]. 计算机与现代化, 2014(10):4.
https://wenku.baidu.com/view/e51484c0e518964bce847c81?fr=xueshu
缩略语列表
| 缩写 | 英文 | 中文 |
| AC | Alternating Current | 交流 |
| ASWDR | Adaptively Scanned Wavelet Difference Reduction | 自适应扫描小波差约简 |
| ATM | Asynchronous Transfer Mode | 异步传输模式 |
| CR | Compression Ratio | 压缩比 |
| CREW | Compression with Reversible Embedded Wavelets | 可逆嵌入小波压缩 |
| CSS | Cascading Style Sheets | 层叠样式表 |
| DC | Data Compression | 数据压缩 |
| DCT | Discrete Cosine Transform | 离散余弦变换 |
| DWT | Discrete Wavelet Transform | 离散小波变换 |
| EBCOT | Embedded Block Coding with Optimised Truncation | 优化截断的嵌入式块 |
| EC | Embedded Coding | 嵌入式编码 |
| EPWIC | Embedded Predictive Wavelet Image Coder | 嵌入式预测小波图像 |
| ETC | Encryption Then Compression | 加密后压缩 |
| EZW | Embedded Zerotree Wavelets | 嵌入式零树小波 |
| GW | Geometric Wavelet | 几何小波 |
| HVS | Human Visual System | 人类视觉系统 |
| JPEG | Joint Photographic Experts Group | 联合图像专家组 |
| LIP | List of Insignificant Pixels | 不重要像素列表 |
| LIS | List of Insignificant Sets | 不重要集合列表 |
| LSP | List of Significant Pixels | 重要像素列表 |
| LZW | Lempel-Ziv-Welch | 蓝波-立夫-卫曲编码法 |
| LZMA | Lempel-Ziv-Markov chain-Algorithm | |
| MSE | Mean Square Error | 均方误差 |
| MPEG | Motion Pictures Expert Group | 动态图像专家组 |
| PSNR | Peak SignaN-to-noise Ratio | 峰值信噪比 |
| RLE | Run Length Encoding | 游程编码 |
| ROI | Region Of Interest | 感兴趣区域 |
| SB | Sub Bands | 子带 |
| SFQ | Space Frequency Quantization | 空频量化 |
| SPECK | Set Partitioned Embedded bloCK | 设置分区嵌入式块 |
| SPIHT | SetPartitioning in Hierarchical Trees | 多级树集合分裂 |
| SR | Stack Run | 堆栈运行 |
| SVD | Singular Value Decomposition | 奇异值分解 |
| VQ | Vector Quantization | 向量量化 |
| WDR | Wavelet Difference Reduction | 小波差约简 |
| WMSN | Wireless Multimedia Sensor Network | 无线多媒体传感器网络 |
| WSN | Wireless Sensor Networks | 无线传感器网络 |
写在最后：
第三章：Brotli压缩算法——一种开源的压缩算法
第四章 LZ77 压缩算法——基于字典及滑动窗口的无损压缩技术
写在最后：
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 高校小助手，加入“啃论文俱乐部”微信群