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 条评论
登录 后参与评论

相关文章

来自专栏机器之心

CVPR2018 | 让AI识别语义空间关系:斯坦福大学李飞飞组提出「参考关系模型」

选自arXiv 作者:Ranjay Krishna 等 机器之心编译 参与:张倩、路雪 图像不仅仅是一组目标集合,同时每个图像还代表一个相互关联的关系网。在本文...

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

教程 | 从零开始PyTorch项目:YOLO v3目标检测实现(下)

1292
来自专栏AI科技大本营的专栏

SVM大解密(附代码和公式)

写在之前 支持向量机(SVM),一个神秘而众知的名字,在其出来就受到了莫大的追捧,号称最优秀的分类算法之一,以其简单的理论构造了复杂的算法,又以其简单的用法实现...

7729
来自专栏机器学习算法与Python学习

SVM大解密(附代码和公式)

1495
来自专栏Coding迪斯尼

从零开始构造一个识别猫狗图片的卷积网络

在深度学习的项目实践中,往往会遇到两个非常难以克服的难题,一是算力,要得到精确的结果,你需要设计几千层,规模庞大的神经网络,然后使用几千个GPU,把神经网络布置...

1182
来自专栏郭耀华‘s Blog

MaxPooling的作用

1152
来自专栏AI研习社

手把手教你在浏览器中使用脸部识别软件包 face-api.js

我可以很激动地说,我们终于有可能在浏览器中运行人脸识别程序了!在这篇文章中,我会给大家介绍一个基于 TensorFlow.js 核心的 JavaScript 模...

1011
来自专栏郭耀华‘s Blog

MaxPooling的作用

maxpooling主要有两大作用 1. invariance(不变性),这种不变性包括translation(平移),rotation(旋转),scale(尺...

2747
来自专栏AI研习社

实时识别字母:深度学习和 OpenCV 应用搭建实用教程

这是一个关于如何构建深度学习应用程序的教程,该应用程序可以实时识别由感兴趣的对象(在这个案例中为瓶盖)写出的字母。

621
来自专栏CreateAMind

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

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

442

扫码关注云+社区