一文穿透多媒体过往前沿上篇——无损压缩

文章转发自51CTO【ELT.ZIP】OpenHarmony啃论文俱乐部——一文穿透多媒体过往前沿

1. LZ 编码的概述

最流行的 LZ（编者注：Lempel-Ziv ）算法实现是最初由 Phil Katz 设计的 deflate 算法。Deflate 是一种无损数据压缩算法，使用 LZ 算法和霍夫曼编码的组合，它是由 Jean-loup Gailly 和 Mark Adler 开发的流行 zlib库的一部分。Jean-loup Gailly 也在广泛使用的 gzip 算法中使用 deflate。deflate 算法也被用于 PNG （编者注：可移植网络图形 Portable Network Graphic 的缩写）图像格式。

2. LZ 编码的历史

2.1 UNIX compress 命令

是 LZW 最早的应用之一。字典的大小是可以适应的。我们从大小为 512 的字典开始。这意味着传输的码字长度为 9 位。一旦字典填满，字典的大小将增加一倍，达到 1024 个条目。此时传输的码字有 10 位。字典越填越大，其大小逐渐增加一倍。通过这种方式，在编码过程的前一部分，当字典中的字符串不是很长时，用来编码它们的码字也会有更少的位。码字的最大大小 bmax 可由用户到 9 到 16 之间，16 位是默认值。一旦字典包含 2bmax 条目，压缩就成为一种静态字典编码技术。此时，算法监视压缩比。如果压缩比低于阈值，则将刷新字典，并重新启动字典构建过程。这样，词典总是反映了源的地方特征。

2.2 图像压缩 png 格式

2.2.1 它是如何工作的？

好问题！上传 PNG（编者注：可移植网络图形 Portable Network Graphic 的缩写）文件时，图像中的相似颜色将组合在一起。这种技术称为“量化”。通过减少颜色数量，24 位 PNG 文件可以转换为小得多的 8 位索引彩色图像。所有不必要的元数据也被剥离。结果更好的PNG文件，100%支持透明度。

在上图中，文件大小减小了70%以上。我有极好的视力，但也无法发现差异！使用优化的图像来节省带宽和加载时间。

2.2.2 PNG的发展历史

PNG 标准是在互联网上开发的第一个标准之一。它的开发动机是 Unisys（它已经从 Sperry 那里获得了 LZW （编者注：Lempel–Ziv–Welch）的专利)和 CompuServe 在 1994 年 12 月的一项声明，他们将开始向支持 GIF （编者注：Graphics Interchange Format的缩写）的软件作者收取版税。这一声明导致了数据压缩领域的一场革命，而这场革命正是 Usenet 压缩组的核心。社区决定开发一个无专利的 GIF 替代品，三个月内，PNG 诞生了。(了解更多关于 PNG 和软件的详细历史，请访问由 Greg Roelof 维护的 PNG 网站http://www.libpng.org/pub/png/。)
创建 PNG 格式的动机是，1994 年 12 月 28 日，Unisys 获得了 Unisys 颁发的专利，即图形交换格式 GIF 中使用的 Lempel–Ziv-Welch （LZW）数据压缩算法。该专利要求所有支持GIF的软件支付版税，导致Usenet用户的批评。
其中一位是Thomas Boutell，他于1995年1月4日在Usenet新闻组”comp.graphics”上发布了一个前身讨论线程，其中他设计了一个免费替代GIF的计划。流行的JPEG（编者注：Joint Photographic Experts Group的缩写）查看器QPEG的作者 Oliver Fromme 提出了 PING 名称，最终成为PNG，便携式网络图形（PNG）格式旨在取代较旧，更简单的 GIF 格式，并在某种程度上取代更复杂的 TIFF （编者注：Tag Image File Format的缩写）格式。PNG is Not GIF.
后来实现的其他建议包括Deflate压缩算法和24位颜色支持，GIF中缺乏后者也激励团队创建他们的文件格式。该小组后来被称为PNG开发小组，随着讨论的迅速扩大，它后来使用了与 CompuServe 论坛相关的邮件列表。
PNG的完整规范于1996年10月1日在W3C的批准下发布，后来于1997年1月15日作为 RFC 2083 发布。该规范于1998年12月31日修订为1.1版，解决了伽马和色彩校正的技术问题。1999年8月11日发布的1.2版增加了该块作为规范的唯一变化，1.2的重新格式化版本于2003年11月10日作为W3C标准的第二版发布，并于2004年3月3日作为国际标准（ISO/IEC 15948：2004）发布。
虽然GIF允许动画，但决定PNG应该是单图像格式。
2001年，PNG的开发者发布了多图像网络图形 MNG （编者注：Multiple-image Network Graphics的缩写）格式，支持动画。MNG实现了适度的应用程序支持，但在主流Web浏览器中还不够，并且在网站设计者或发布者中没有使用。
2008年，某些Mozilla开发人员发布了具有类似目标的动画便携式网络图形 APNG 格式。APNG （编者注：Animated Portable Network Graphic的缩写）是一种基于 Gecko 和 Presto 的Web浏览器本机支持的格式，也常用于索尼 PlayStation Portable 系统上的缩略图（使用正常的PNG文件扩展名）。
2017年，基于 Chromium 的浏览器采用了 APNG 支持。2020年1月，Microsoft Edge 开始基于 Chromium ，从而继承了对 APNG 的支持。有了这个，所有主流浏览器现在都支持 APNG 。

2.2.3 PNG的压缩技术

PNG 使用 2 级压缩过程：

预压缩：过滤（Filtering）

压缩：放气（Deflate）

2.2.3.1 过滤（Filtering）

在应用 Deflate 之前，通过预测方法转换数据。当前 PNG 规范中只有一种筛选器方法（表示为方法 0），因此在实践中，唯一的选择是将哪种筛选器类型应用于每行。对于此方法，筛选器根据先前相邻像素的值预测每个像素的值，并从实际值中减去像素的预测颜色。

2.2.3.2 压缩：放气（Deflate）

PNG 使用 Deflate，这是一种非专利的无损数据压缩算法，涉及LZ77和霍夫曼编码的组合。许可DEFLATE实现，如 zlib ，是广泛使用的。

与具有有损压缩的格式（如 JPEG）相比，选择高于平均值的压缩设置会延迟处理，但通常不会导致文件大小明显变小。

编程接口：

Deflate可以免费在很多编程语言中使用。C语言通常使用zlib库。C++语言可以使用7-Zip/AdvanceCOMP。Java语言包含在标准库java.util.zip中。Microsoft .NET Framework 2.0包含在System.IO.Compression命名空间中。

PKZIP：该算法最早的实现。
zlib / gzip：标准参考实现（standard reference implementation），由于其公共可用性，得到了及其广泛的使用。
Crypto++：C++开源实现。
7-Zip/AdvanceCOMP：Igor Pavlov的C++开源自由实现
PuTTY: 一份单独实现
Hyperbac：C++与汇编实现
Zopfli：Google的C实现

2.3 图像压缩 gif 格式

图形交换格式(GIF) 是由 Compuserve 信息服务公司开发的，用于对图形图像进行编码。它是 LZW 算法的另一种实现，非常类似于 Unix 中的 compress 命令。

GIF图像使用 Lempel-Ziv-Welch（LZW）无损数据压缩技术进行压缩，以减小文件大小而不会降低视觉质量。虽然 GIF 不是作为动画媒介设计的，但它在一个文件中存储多个图像的能力自然建议使用这种格式来存储动画序列的帧。

为了便于显示动画，GIF89a规范添加了图形控制扩展（GCE），该扩展允许以时间延迟绘制文件中的图（帧），从而形成视频剪辑。动画 GIF 中的每个帧都由其自己的 GCE 引入，该 GCE 指定在绘制帧后等待的时间延迟。默认情况下，动画仅显示一次帧序列，并在显示最后一帧时停止。

为了使动画能够循环播放，Netscape 在 20 世纪 90 年代使用应用程序扩展块（旨在允许供应商将特定于应用程序的信息添加到 GIF 文件中）来实现 Netscape 应用程序块（NAB）。

这个块放置在动画帧序列之前，指定帧序列应该被播放的次数（1到65535次）或它应该连续重复（0表示永远循环）。对这些重复动画的支持首先出现在 Netscape Navigator 2.0 版本中，然后扩展到其他浏览器。大多数浏览器现在都能识别并支持NAB，尽管它并不是GIF89a规范的严格组成部分。

2.4 MNG 格式

PNG 本身不支持动画。MNG （编者注：Multiple-image Network Graphics的缩写）是 PNG 的扩展，MNG 共享 PNG 的基本结构和块，但它要复杂得多，并且具有不同的文件签名，这会自动使其与标准 PNG 解码器不兼容，这导致 MNG 几乎不支持或大多数 Web 浏览器或应用程序。

2.5 APNG 格式

MNG的复杂性导致了 Mozilla 基金会开发人员提出 APNG（编者注：Animated Portable Network Graphic的缩写）。

它基于 PNG，支持动画，比 MNG 更简单。今天，APNG 格式目前被所有主要的 Web 浏览器广泛支持。在 Firefox 3.0 及更高版本，Pale Moon（所有版本）中支持APNG，最新版本的 Opera 支持 APNG，因为引擎已更改为 Blink、iOS 8 和 Safari 8 for OS X Yosemite 上的最新版本的 Safari，它们使用支持 APNG 的 WebKit 引擎。Chromium 59.0 增加了对 APNG 的支持，紧随其后的是谷歌 Chrome 浏览器。Microsoft Edge 现在通过基于 Chromium 的新引擎支持 APNG。

技术DNA

智慧场景

后期预告

下篇有损压缩，介绍：JPEG、MPEG、AV1和H.266

参考文献

Hosseini M . A Survey of Data Compression Algorithms and their Applications[C]// Applications of Advanced Algorithms. 2012.
- https://www.researchgate.net/publication/270408593_A_Survey_of_Data_Compression_Algorithms_and_their_Applications
Han J , Li B , Mukherjee D , et al. A Technical Overview of AV1[J]. Proceedings of the IEEE, 2021, PP(99):1-28.
- https://ieeexplore.ieee.org/document/9363937/citations
Saldanha M , Correa M , Correa G , et al. An Overview of Dedicated Hardware Designs for State-of-the-Art AV1 and H.266/VVC Video Codecs[C]// 2020 27th IEEE International Conference on Electronics, Circuits and Systems (ICECS). IEEE, 2020.
- http://www.researchgate.net/publication/348023353_An_Overview_of_Dedicated_Hardware_Designs_for_State-of-the-Art_AV1_and_H266VVC_Video_Codecs
AV1编码质量初探
- https://zhuanlan.zhihu.com/p/86890266
H.266/VCC编码标准发布，4K/8K视频大小减半清晰度不变
- https://www.eet-china.com/news/202008181407.html
视频格式与编码压缩标准 mpeg4，H.264.H.265 有什么关系？
- https://blog.csdn.net/lxc1014/article/details/45666281
zlib Home Site
- http://www.zlib.net/
TinyPNG – Compress WebP, PNG and JPEG images intelligently
- https://tinypng.com/

ELT.ZIP是谁？

ELT<=>Elite(精英)，.ZIP为压缩格式，ELT.ZIP即压缩精英。

成员：

上海工程技术大学大二在校生闫旭

合肥师范学院大二在校生楚一凡

清华大学大二在校生赵宏博

成都信息工程大学大一在校生高云帆

黑龙江大学大一在校生高鸿萱

山东大学大三在校生张智腾

ELT.ZIP是来自6个地方的同学，在OpenHarmony成长计划啃论文俱乐部里，与来自华为、软通动力、润和软件、拓维信息、深开鸿等公司的高手一起，学习、研究、切磋操作系统技术…

写在最后：

OpenHarmony 成长计划—“啃论文俱乐部”（以下简称“啃论文俱乐部”）是在 2022年 1 月 11 日的一次日常活动中诞生的。截至 3 月 31 日，啃论文俱乐部已有 87 名师生和企业导师参与，目前共有十二个技术方向并行探索，每个方向都有专业的技术老师带领同学们通过啃综述论文制定技术地图，按“降龙十八掌”的学习方法编排技术开发内容，并通过专业推广培养高校开发者成为软件技术学术级人才。

啃论文俱乐部的宗旨是希望同学们在开源活动中得到软件技术能力提升、得到技术写作能力提升、得到讲解技术能力提升。大学一年级新生〇门槛参与，已有俱乐部来自多所高校的大一同学写出高居榜首的技术文章。

如今，搜索“啃论文”，人们不禁想到、而且看到的都是我们——OpenHarmony 成长计划—“啃论文俱乐部”的产出。