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

相关文章

来自专栏数据小魔方

sparklines迷你图系列16——Distribution(Spread)

今天跟大家分享sparklines迷你图系列16——Distribution(Spread)。 这种图表用中文翻译是在费解,没有特别合适的叫法,但是实际上它是一...

2786
来自专栏机器人网

分布式深度学习原理、算法详细介绍

介绍 无监督的特征学习和深度学习已经证明,通过海量的数据来训练大型的模型可以大大提高模型的性能。但是,考虑需要训练的深度网络模型有数百万甚至数十亿个参数需要训练...

38911
来自专栏CreateAMind

运动信息向量的神经网络学习 code、ppt、视频ok

官方代码还未开放, http://visualdynamics.csail.mit.edu/

592
来自专栏AI研习社

你在数据预处理上花费的时间,是否比机器学习还要多?

Nuts-ml 是一个新的 Python 数据预处理库,专门针对视觉领域的 GPU 深度学习应用。 它以独立、可复用的单元模块的形式,提供主流数据预处理函数。...

3668
来自专栏人工智能LeadAI

梯度下降法快速教程 | 第三章:学习率衰减因子(decay)的原理与Python实现

前言 梯度下降法(Gradient Descent)是机器学习中最常用的优化方法之一,常用来求解目标函数的极值。 其基本原理非常简单:沿着目标函数梯度下降的方向...

3635
来自专栏量子位

GitHub上大热的Deep Photo终于有TensorFlow版了!

王小新 编译整理 量子位 出品 | 公众号 QbitAI Prisma这个应用,你可能很熟悉。这是一个能将不同的绘画风格,迁移到照片中,形成不同艺术风格的图片。...

3786
来自专栏量子位

如何用sklearn创建机器学习分类器?这里有一份上手指南

原作:Kasper Fredenslund 林鳞 编译自 Data Science Central 量子位 出品 | 公众号 QbitAI 分类器是数据挖掘中对...

34316
来自专栏应兆康的专栏

16. 清理贴错标签的开发集和测试集样本

1131
来自专栏深度学习那些事儿

浅谈深度学习中超参数调整策略

深度学习中,设计模型以及保证模型的正确性是首要需要考虑的。当模型设置完成时,理论上模型不存在问题,实现效果也通过计算可以复现出来。一切准备就绪后,那么接下来需要...

28311
来自专栏北京马哥教育

深度学习 + OpenCV,Python实现实时目标检测

使用 OpenCV 和 Python 上对实时视频流进行深度学习目标检测是非常简单的,我们只需要组合一些合适的代码,接入实时视频,随后加入原有的目标检测功能。 ...

7507

扫码关注云+社区