JPEG算法概述及实现

本文将简单介绍下JPEG算法的实现流程,包括图像分割、颜色空间转换、DCT、Quantization、Huffman coding等。

JPEG概述

图像压缩很重要。有这么几种压缩算法:

  • JPEG(非常基本的算法,以DCT和quantization为基础,在25比1的压缩比情况下非图像专家很难发现区别)
  • JPEG-LS(无损压缩算法,以预测技术为基础,视频的压缩也参照了预测技术)
  • JPEG-2000(最新的标准,采用wavelet算法)

JPEG步骤

概述

  1. 图像分割。分割成8*8的小块
  2. 颜色空间转换。从RGB到Y,Cb,Cr。
  3. DCT(Discrete cosine transform)
  4. Quantization(数据量化,压缩很大一部分是在这里的)
  5. Huffman coding(对数据进行编码,进一步压缩)

下面,将以我们可爱的高圆圆的照片,来看一下压缩算法。

图像分割

首先,将图像分成8*8的小块,分成这么大是有原因的:

  1. 太大的话进行矩阵操作复杂度上升
  2. 太小的话包含的信息太少,在DCT中不能实现很好地压缩

下面,以高圆圆图片左上角为例,取8*8的元素

看,就是这么一小块啦!

颜色空间转换

首先,简单介绍下颜色空间,其就是表达颜色的数学模型。比如最普通的RGB,高圆圆图片的RGB分解如下:

不同的颜色空间有不同的应用场景,RGB颜色空间适合像显示器这样的自发光图案。然而在JPEG压缩算法中,通常转换成YCbCr空间,这里Y表示亮度,Cb和Cr分别表示绿色和红色的色差值。

“色差”这个概念起源于电视行业,最早的电视都是黑白的,那时候传输电视信号只需要传输亮度信号,也就是Y信号即可,彩色电视出现之后,人们在Y信号之外增加了两条色差信号以传输颜色信息,这么做的目的是为了兼容黑白电视机,因为黑白电视只需要处理信号中的Y信号即可。 对于人眼来说,图像中明暗的变化更容易被感知到,这是由于人眼的构造引起的。视网膜上有两种感光细胞,能够感知亮度变化的视杆细胞,以及能够感知颜色的视锥细胞,由于视杆细胞在数量上远大于视锥细胞,所以我们更容易感知到明暗细节。比如说下面这张图 ——摘自参考文献

其转换公式为:

转换后的图像是:

容易看到,RGB颜色空间中,每个颜色尺度上图像的信息都是差不多的。但是在YCbCr中,Y中包含的信息(也就是图形细节)更多,因此后面就可以根据信息的丰富程度做不同的数据压缩处理。比如对Y分量压缩地少,对另外两个分量压缩地多。

DCT

前文中,我们已经得到了8*8的小方块,接着需要对小方块进行DCT变换,DCT变换的实质就是将原来的8*8小块投影到新的空间(也就是下面的图片)。

经过DCT变换后,杂乱的数据变得工整了(这里可以类别矩阵的EIG、SVD分解等)。举个极端的例子,如果每个元素都一样,那么只有左上角(也就是位置(1,1))的方格有值,其他都是零。

DCT变换的公式是: 元素公式:

矩阵公式:

下面还是以前文中的8*8小方块为例(只看Y分量):

s_y =

  118  118  120  122  122  121  125  128
  117  118  120  122  123  123  128  132
  121  121  121  121  121  121  125  130
  124  123  120  118  116  117  122  126
  124  122  118  114  113  116  123  127
  130  127  122  117  114  117  124  128
  138  135  129  122  117  119  123  126
  141  138  133  125  120  121  124  126

>> dct2(s_y)

ans =

  984.6250    2.7093   24.9920   -8.0736    1.1250    0.8013   -0.7458    0.3843
  -12.6773  -25.9635  -12.8348   -0.9374    3.6024   -0.5894   -0.7880    0.6604
   15.0671    5.2086   -4.9383    0.0106    0.0280    0.3999    0.5152    0.2320
   -8.2712   -3.4118    2.7730    0.3084   -0.1410    0.7677   -0.4452    0.1033
   -3.3750    3.0430   -0.1633    0.4712   -0.3750    0.2268   -0.0676    0.1702
    0.5963    5.7983   -0.2067    0.0606    0.2430    0.0231    0.0559   -0.5708
    0.1181    0.0674    0.0152   -0.0561    0.3943    0.0299    0.1883    0.1514
   -0.5753   -0.0467    0.0542    0.2484   -0.0791   -0.3391    0.2906    0.1321

>> idct2(dct2(s_y))

ans =

  118.0000  118.0000  120.0000  122.0000  122.0000  121.0000  125.0000  128.0000
  117.0000  118.0000  120.0000  122.0000  123.0000  123.0000  128.0000  132.0000
  121.0000  121.0000  121.0000  121.0000  121.0000  121.0000  125.0000  130.0000
  124.0000  123.0000  120.0000  118.0000  116.0000  117.0000  122.0000  126.0000
  124.0000  122.0000  118.0000  114.0000  113.0000  116.0000  123.0000  127.0000
  130.0000  127.0000  122.0000  117.0000  114.0000  117.0000  124.0000  128.0000
  138.0000  135.0000  129.0000  122.0000  117.0000  119.0000  123.0000  126.0000
  141.0000  138.0000  133.0000  125.0000  120.0000  121.0000  124.0000  126.0000

可以看到,转换后能量集中于左上角的直流分量(因为这么小的图像一般不会出现大的数值上的跳跃)。

Quantization

前面的变换都是可逆的,也就是数据的信息并没有丢失。 数据的大部分压缩都是在量化这里,有时候保存图片的时候软件会提示你选择保存的精度,其实就是改变量化的程度,或者改变量化系数矩阵乘的倍数。

标准亮度量化表和标准色差量化表见下图:

对于每个单独元素量化的规则是:

T^(u,v)=⌊T(u,v)Q⌋∗Q

\hat{T}(u,v) =\lfloor \frac{T(u,v)}{Q} \rfloor *Q 这么量化的原因是:

有损压缩就是把数据中重要的数据和不重要的数据分开,然后分别处理。DCT系数矩阵中的不同位置的值代表了图像数据中不同频率的分量,这两张表中的数据时人们根据人眼对不不同频率的敏感程度的差别所积累下的经验制定的,一般来说人眼对于低频的分量必高频分量更加敏感,所以两张量化系数矩阵左上角的数值明显小于右下角区域。在实际的压缩过程中,还可以根据需要在这些系数的基础上再乘以一个系数,以使更多或更少的数据变成0。

将原来的8*8小块,根据QY进行量化后,得到的结果是

s_y_dct =

  984.6250    2.7093   24.9920   -8.0736    1.1250    0.8013   -0.7458    0.3843
  -12.6773  -25.9635  -12.8348   -0.9374    3.6024   -0.5894   -0.7880    0.6604
   15.0671    5.2086   -4.9383    0.0106    0.0280    0.3999    0.5152    0.2320
   -8.2712   -3.4118    2.7730    0.3084   -0.1410    0.7677   -0.4452    0.1033
   -3.3750    3.0430   -0.1633    0.4712   -0.3750    0.2268   -0.0676    0.1702
    0.5963    5.7983   -0.2067    0.0606    0.2430    0.0231    0.0559   -0.5708
    0.1181    0.0674    0.0152   -0.0561    0.3943    0.0299    0.1883    0.1514
   -0.5753   -0.0467    0.0542    0.2484   -0.0791   -0.3391    0.2906    0.1321

 uint8(floor(double(s_y_dct)./QY).*QY)

ans =

  255    0   20    0    0    0    0    0
    0    0    0    0    0    0    0    0
   14    0    0    0    0    0    0    0
    0    0    0    0    0    0    0    0
    0    0    0    0    0    0    0    0
    0    0    0    0    0    0    0    0
    0    0    0    0    0    0    0    0
    0    0    0    0    0    0    0    0

可以看到,大部分元素都变成了0。

Huffman coding

哈弗曼几乎是所有压缩算法的基础,它的基本原理是根据元素的使用频率,调整元素的编码长度,以获得更高的压缩比。

原理可以用下面两张图简单介绍:

可以看到,出现概率越高的符号通过哈弗曼编码用的bit位越少,以便实现更好的数据压缩。

通过Huffman coding,在不丢失信息的前提下,我们实现了数据压缩。

JPEG-LS

上面这张图片简单概述了无损压缩的步骤,无损压缩建立在以下的基础上:

  1. 每个像素之间差别不大,最朴素的方法可以用前一个像素的值来预测后一个像素的值。
  2. 假设图片有256个像素,分别是0——255。那么只需要记录下第一个值0以及增长率1(并且这种特殊情况下增长率都是1,所以可以极大地减少空间)。
  3. 同样地,对于普通的一张图片,因为相邻的像素差别不大,所以对增长率进行编码的话效率更高些,这就是JPEG-LS的核心思想——预测增长率。

同样地,对于视频,背景一般不变,所以也可以用类似的思想(MPEG就是用的这种思想方法)实现对视频的压缩。

参考文献

  1. JPEG算法解密(母校学长的文章,大赞啊)
  2. DCT变换(这里DCT讲的很明白)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI研习社

禅与奶罩识别艺术(上)

在昨天的卷积:如何成为一个很厉害的神经网络 - 知乎专栏中,热心网友提出了这样的问题: ? 该文在卷积神经网络的构成上讲解的比较直观,但是没有深入地探讨数学原理...

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

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

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

1789
来自专栏吉浦迅科技

Tensor Core

Tensor Core,也是Volta架构里面最重磅的特性。 ? Tensor Core实际上是一种矩阵乘累加的计算单元。矩阵乘累加计算在Deep Learn...

4288
来自专栏AI研习社

禅与奶罩识别艺术(下)

编者按:本文接上期禅与奶罩识别艺术(上),作者 Kaiser,景略集智总经理,原文载于集智网专栏,雷锋网 AI 研习社已获授权。 过拟合/欠拟合 之前介绍了...

4047
来自专栏进击的程序猿

如何构建一个简单的神经网络如何构建一个简单的神经网络

最近报名了Udacity的深度学习基石,这是介绍了第二部分神经网络入门,第一篇是线性回归背后的数学. 本文notebook的地址是:https://githu...

923
来自专栏深度学习入门与实践

【深度学习系列】用PaddlePaddle和Tensorflow进行图像分类

  上个月发布了四篇文章,主要讲了深度学习中的“hello world”----mnist图像识别,以及卷积神经网络的原理详解,包括基本原理、自己手写CNN和p...

3985
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

基于模糊集理论的一种图像二值化算法的原理、实现效果及代码

  这是篇很古老的论文中的算法,发表与1994年,是清华大学黄良凯(Liang-kai Huang) 所写,因此国外一些论文里和代码里称之为Huang's fu...

22410
来自专栏梦里茶室

西瓜书概念整理(chapter 1-2)熟悉机器学习术语

括号表示概念出现的其他页码, 如有兴趣协同整理,请到issue中认领章节 完整版见我的github:ahangchen 觉得还不错的话可以点个star ^_^ ...

30310
来自专栏IT派

TensorFlow快餐教程:程序员快速入门深度学习五步法

作为一个程序员,我们可以像学习编程一样学习深度学习模型开发。我们以 Keras 为例来说明。

925
来自专栏达观数据

技术干货丨fastText原理及实践

fastText是Facebook于2016年开源的一个词向量计算和文本分类工具,在学术上并没有太大创新。但是它的优点也非常明显,在文本分类任务中,fastTe...

5199

扫码关注云+社区