图片上的算法之JPEG压缩

大家好,文章来源于tiankonguse的公众号(tiankonguse-code)。

作者:tiankonguse,曾是一名ACMer,现在是鹅厂视频部门的后台开发。这里主要记录工作中的技术架构与经验、计算机相关的技术、数学、算法、生活上好玩的东西。

前言

听了JPEG图片的压缩算法,发现蛮有意思的,这里分享一下。

一、整体思想

JPEG有损压缩算法是一个可逆的算法,所以这里重点介绍压缩部分,对于逆过程这里就不谈了。

整体压缩流程如下:

  • 色彩空间转换
  • 缩减取样
  • DCT变换
  • 量化
  • 熵编码技术

下面分别讲一下这几部分都是做什么的吧!

这里先强调一个思想: 有损压缩的本质就是抛弃那些不影响大局的信息。 从而做到使用更小的储存来表达对应的信息。

二、色彩空间转换

颜色具体显示的时候需要是RGB的形式,比如每个像素由三个8字节的数字组成。

这样的表示相当于使用三个互相独立的颜色矩阵组合成了一张图片。

每个颜色矩阵是等价的,且任何一个颜色矩阵数据有较大偏差时,我们人眼都能明显感知到。

生物学上,研究发现人眼对亮度差异比较敏感,但是颜色的差异变化并不是那么敏感。 所以就有人想到转化为亮度和颜色的表示形式。

大概有下面几种算法:YIQ,YUV 和 YCrCb, 而这里采用的是YUV转化算法。

Y维度代表一个像素的亮度,U和V维度用来代表颜色。

这个转换的好处是后续的步骤中对Y维度只能稍微抛弃一些的信息,对于UV维度可以大量的抛弃信息。

实际使用中由于小数的精度和性能优化,可能导致实际处理中出现一丢丢数据丢失。

当然这一丢丢数据的丢失我们可以接受,然后就可以进入下一部分了。

三、缩减取样

既然有损压缩代表需要抛弃部分数据,那我们主动抛弃一些数据吧。 比如一整图片像素那么多,常见的方式是在U和V维度隔一行取一个信息. 这样在UV维度上数据直接较少一半了.

这一部分是第一次对数据有损抛弃,两个维度直接减少了一半,整体的话就是减少了三分之一。

四、DCT变换

DCT变换的含义是离散余弦变换。

色彩空间转换小节中我们看到RGB数据三个维度是完全等价的,导致不能尽情的抛弃数据。 于是我们转化为YUV数据,然后就可以对UV维度尽情的抛弃数据还不会影响整体数据质量。

那现在我们遇到同样的问题。 对于YUV每一维度都是一个矩阵,矩阵的每一个点对我们来说还是完全等价的。 我们能不能对矩阵进行转化,然后就可以对矩阵的一部分数据尽情的抛弃数据呢?

这样变换的方法有很多,比如傅里叶变换,Walsh-Hadamard变换,正弦变换,余弦变换,斜变换,哈尔变换,K-L变换等等。

这里采用的是余弦变换。

余弦变换后的效果是矩阵左上角的数据权重较高,对于右下角的数据权重较低。

这些变换和色彩空间转换一样,都是可逆的,无损的。

但是变换后的特性允许我们对不同部分的数据进行不同程度的有损。

五、量化

量化的作用就是对于权重较低的数据进行大量有损抛弃,而对权重较高的数据稍微有损抛弃。

这里实际操作就是对矩阵的每个数据进行若干比例的缩小。

矩阵的数据缩小之后有了另外一个特性:大多连续数据是相同的了,右下角的数据大部分是0了。

这里需要提到的一点是对矩阵等比例缩小实际上就是乘以另外一个矩阵。 而这个矩阵称为量化表,一般这个量化表是固定的。

前段时间google宣传提高了JPEG的压缩率,实际上就是找到了一个整体情况更好的量化表(应该是这样)。 由于最终有损压缩出的图片很难使用机器或算法来判断是否优劣,所以这里就没有更好的方法来自动计算最优的量化表了。 google之所以得到了更好的量化表,是使用数据挖掘(机器学习?神经网络?)模拟了人眼,然后用这个人眼来反馈图片的压缩质量,最终找到更好的量化表。

六、熵编码技术

我们使用量化表抛弃了很多影响不大的信息,但是我们并没有进行任何压缩,只是为这一步的压缩准备了条件。

上面提到了,量化后有个特性:大多连续数据是相同的。

于是我们就需要编排数据,然后使用Huffman算法进行无损压缩。

是的,这一步的优化也是无损可逆的。

而且实际处理中为了性能,我们往往是已经有一个经验码表。

这样就不需要进行Huffman概率计算了。

唯一的缺点就是JPEG中没有储存这个码表,这样导致这个码表用于没办法更新了。 当然,码表也比较大,如果储存起来也极大可能导致压缩后数据更大的可能性了吧。

七、总结

经过上面五大步操作,JPEG图片就完成了压缩。

可以看到这个压缩算法分工很明确:

算法上:

色彩空间转换,DCT变换都是无损可逆的转换算法。 缩减取样和量化是有损可逆的算法。 熵编码技术是无损可逆压缩算法。

依赖上:

色彩空间转换算法为缩减取样与量化做好了准备:维度的轻重分离。 DCT变换也为量化做好准备:矩阵的轻重分离。 量化为熵编码技术做好了准备:重复数据连续性特点。

这个算法挺有意思的,后续遇到其他有意思的算法继续分享给大家。

八、参考资料

  1. 主要是部门的分享,了解了这个算法的思想。
  2. wikipedia JPEG。
  3. 论文 Digital Signal Processing(微信号中可索要此论文)。

原创声明,本文系作者授权云+社区-专栏发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

tiankonguse的专栏

1 篇文章1 人订阅

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏运维前线

CentOS 6.X 安装中文字体

由于业务需要,需要对CentOS6.9添加中文字体支持 安装工具包 yum install -y fontconfig mkfontscale 安装完成后...

2096
来自专栏Android干货

Android项目实战(八):列表右侧边栏拼音展示效果

2745
来自专栏牛肉圆粉不加葱

ResourceManager HA无法连接Spark TrackUi现象解决方案

在对ResourceManager做了基于Zookeeper的HA后, 在YARN集群上执行Spark application后, 打开Spark Applic...

682
来自专栏闵开慧

Failed to set permissions of path

12/09/04 16:46:34 INFO support.ClassPathXmlApplicationContext: Refreshing org...

2477
来自专栏Ryan Miao

国家语言,语言代码,locale id对应表

国家语言,语言代码,locale id对应表。比如 en_US对应的id为1033, 中文的locale=zh_CN,id=2052. LocaleLang...

9157
来自专栏IT技术精选文摘

深入分析Spring 与 Spring MVC容器

public WebApplicationContext initWebApplicationContext(ServletContext servletCon...

2036
来自专栏SAP最佳业务实践

SAP S/4 HANA新变化-CO物料帐(for Ver.1610)

Material Ledger Actual Costing has been activated already in the system before t...

3985
来自专栏Golang语言社区

Knapsack problem algorithms for my real-life carry-on knapsack

I'm a nomad and live out of one carry-on bag. This means that the total weight o...

932
来自专栏高性能服务器开发

(八)高性能服务器架构设计总结3——以flamigo服务器代码为例

再看filezilla,一款ftp工具的服务器端,它采用的是Windows的WSAAsyncSelect模型(代码下载地址:https://github.com...

3366
来自专栏生信技能树

基因名变化太快,比如PAM50

当然准备把这些基因跟ensembl数据库的ID对应的时候我发现少了3个,然后我搜索发现它们的symbol其实被修改了,可以说变化比较快啦,才几年时间,3 of ...

872

扫码关注云+社区