图片上的算法之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 条评论
登录 后参与评论

相关文章

来自专栏人工智能快报

美国MIT研究人员揭示神经网络运行机制

美国麻省理工学院(MIT)官网报道该校在通用神经网络方面的研究进展可用于揭示神经网络的运行机制。理解神经网络的运行机制可以帮助研究人员增强其性能,并将从中获得的...

3315
来自专栏目标检测和深度学习

这个深度学习课程笔记,吴恩达也转了

去年 6 月,吴恩达宣布 deeplearning.ai 创业项目,8 月,该项目揭晓:一套由5门课组成的深度学习系列课程——Deep Learning Spe...

3355
来自专栏大数据文摘

干货 | 一文带你读懂DeepMind新论文,关联推理为什么是智能最重要的特征

1552
来自专栏机器学习与自然语言处理

Stanford机器学习笔记-7. Machine Learning System Design

7 Machine Learning System Design Content   7 Machine Learning System Design  ...

1809
来自专栏IT大咖说

艺术领域中的Tensorflow应用

摘要 本次演讲内容主要分为三个方面,首先会简单介绍一下Tensorflow,然后简单讲解可以用Tensorflow实现的深度神经网络算法,之后再介绍这些...

3646
来自专栏人工智能头条

这个深度学习课程笔记,吴恩达也转了

1373
来自专栏机器之心

CVPR2018 | CMU&谷歌Spotlight论文:超越卷积的视觉推理框架

选自arXiv 作者:陈鑫磊等 机器之心编译 参与:张倩、李泽南 人类在看到图像时可以进行合理的推理与预测,而目前的神经网络系统却还难以做到。近日,来自卡耐基梅...

2868
来自专栏机器之心

LSTM入门必读:从基础知识到工作方式详解

选自echen 机器之心编译 参与:机器之心编辑部 长短期记忆(LSTM)是一种非常重要的神经网络技术,其在语音识别和自然语言处理等许多领域都得到了广泛的应用。...

3298
来自专栏PPV课数据科学社区

用 TensorFlow 做个聊天机器人

本文结构: 聊天机器人的架构简图 用 TensorFlow 实现 Chatbot 的模型 如何准备 chatbot 的训练数据 Chatbot 源码解读 1. ...

2693

机器学习 - 朴素贝叶斯分类器的意见和文本挖掘

人们倾向于知道他人是如何看待他们和他们的业务的,不管是什么东西,不管是汽车,饭店等产品还是服务本身。如果你知道你的客户如何看待你,那么你可以保持或改善甚至改变你...

2455

扫码关注云+社区