理解JEPG原理

JEPG不是一种文件格式,而是一类图像压缩算法.

1.彩色图像

灰度图像

灰度,一个pixel取值0-255.
理解JPEG图像压缩算法,DCT变换

彩色图像

需要比灰度图像更多的存储空间, 事实上, 所有颜色都可以用红绿蓝三原色的组合表示, 彩色图像可用RGB三通道表示.

理解JPEG图像压缩算法,DCT变换

YCbCr

研究发现对于图像压缩, RGB的表示不是最佳的.

人脑对亮度(luminance)和色差(chrominance)的微小变化不敏感. YCbCr用一层亮度和两层色差表示RGB图像. Y是亮度通道, Cb和Cr是色差通道.

RGB转YCbCr是这样定义的,对一个 $(r, g, b)$ 元组, 先归一化 $(r^{'}, g^{'}, b^{'}) = (r / 255, g / 255, b / 255)$ .

通过一下公式得到亮度值 $y :$

y = 0.299 r^{'} + 0.587 g^{'} + 0.114 b^{'}

色差通道通过计算red和blue两颜色通道和参照通道

y

的差得到:

C b = (b^{'} - y) / 1.772

C r = (r^{'} - y) / 1.402

1.772和1.402做分母使Cb和Cr都落在区间

[- 1 / 2, 1 / 2]

.
最后一步, 为了显示将三通道缩放到

[0, 255]

,并取整:

Y = r o u n d (219 y + 16)

C_{b} = r o u n d (224 C b + 128)

C_{r} = r o u n d (224 C r + 128)

理解JPEG图像压缩算法,DCT变换

2.JPEG算法

JPEG不是一种文件格式,而是一类图像压缩算法, 下面我介绍的是JPEG2000,最基础的算法,可以帮助理解整个过程.

首先说一下怎么理解图像压缩, 以huffman编码为例, 对图像每个byte做频率统计, 构造huffman树重新编码, 以减小编码长度. 但是, 直接对图像做huffman编码的压缩并不好, 因为需要对256个像素值都编码, 码长不会显著减小.

如果能将图像变换到一个含有比较少的不同值的空间中, huffman编码效果将会显著提升. 这就是jpeg的核心思想.

2.1 预处理

先将RGB转成YCbCr, 然后把这三层当作灰度图像看就行, 操作是一样的.

然后, 将图像切割成一堆 $8 \times 8$ 的块.

理解JPEG图像压缩算法,DCT变换
所有操作都是独立对这样每一个 $8 \times 8$ 的小块做的.

2.2 DCT变换

考虑一个 $8 \times 8$ 的块, 这个块在原图像中所占的比例是非常小的, 在大部分情况下, 这个块中pixel数值变化是很平滑的. 打个比方,一个块正好罩在一面墙壁上, 这块的pixel值在79-81之间变化, 若要用cos函数的组合去拟合这段离散的数值, 这些函数的频率会很高.

这些变化也被称为高频信息, 而人眼对高频信息不敏感, 对低频信息比较敏感. 如果一个块罩在墙和背景交界的地方, 块的pixel数值会出现不平滑的变化,跨度很大, 这时要用函数组合去拟合这段离散数值时, 就会出现低频.

因此, 再结合图像压缩的核心思想, 用较少的不同数值来表示图像, 就需要找到一种变换, 将图像高频的信息和低频的信息区分开来, 并将人眼不敏感的低频信息映射到接近或等于0.

JPEG用的就是DCT(Discrete Cosine Transformation), 下面就是DCT矩阵, 任何 $8 \times 8$ 块都可以用DCT矩阵表示.

U = \frac{1}{2} [\begin{matrix} \frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2} \\ \cos \frac{π}{16} & \cos \frac{3 π}{16} & \cos \frac{5 π}{16} & \cos \frac{7 π}{16} & \cos \frac{9 π}{16} & \cos \frac{11 π}{16} & \cos \frac{13 π}{16} & \cos \frac{15 π}{16} \\ \cos \frac{2 π}{16} & \cos \frac{6 π}{16} & \cos \frac{10 π}{16} & \cos \frac{14 π}{16} & \cos \frac{18 π}{16} & \cos \frac{22 π}{16} & \cos \frac{26 π}{16} & \cos \frac{30 π}{16} \\ \cos \frac{3 π}{16} & \cos \frac{9 π}{16} & \cos \frac{15 π}{16} & \cos \frac{21 π}{16} & \cos \frac{27 π}{16} & \cos \frac{33 π}{16} & \cos \frac{39 π}{16} & \cos \frac{45 π}{16} \\ \cos \frac{4 π}{16} & \cos \frac{12 π}{16} & \cos \frac{20 π}{16} & \cos \frac{28 π}{16} & \cos \frac{36 π}{16} & \cos \frac{44 π}{16} & \cos \frac{52 π}{16} & \cos \frac{60 π}{16} \\ \cos \frac{5 π}{16} & \cos \frac{15 π}{16} & \cos \frac{25 π}{16} & \cos \frac{35 π}{16} & \cos \frac{45 π}{16} & \cos \frac{55 π}{16} & \cos \frac{65 π}{16} & \cos \frac{75 π}{16} \\ \cos \frac{6 π}{16} & \cos \frac{18 π}{16} & \cos \frac{30 π}{16} & \cos \frac{42 π}{16} & \cos \frac{54 π}{16} & \cos \frac{66 π}{16} & \cos \frac{78 π}{16} & \cos \frac{90 π}{16} \\ \cos \frac{7 π}{16} & \cos \frac{21 π}{16} & \cos \frac{35 π}{16} & \cos \frac{49 π}{16} & \cos \frac{63 π}{16} & \cos \frac{77 π}{16} & \cos \frac{91 π}{16} & \cos \frac{105 π}{16} \end{matrix}]

DCT每一行图示

row0是常数, 可以看出每行频率逐渐增加.

理解JPEG图像压缩算法,DCT变换

仔细看上图, 可以发现每个图橙色的点高度和为0. 这意味着, 对于一个constant vector(向量中每个数相同), 和row 1-7任意一个点乘的结果都是0, 而对近似constant vector点乘的结果接近0.(这就达到了将高频信息转换到接近0的效果)

DCT变换作用在 $8 \times 8$ 矩阵A上表现为 $B = U A U^{T}$ . 首先计算 $C = U A$ , 若A是一个平滑的矩阵(near-constant), $C$ 中往下会出现许多元素接近或等于0. 最终结果 $B = C U^{T}$ , 将 $U$ 转制之后, 原来的row变成了column, 类似的, $B$ 往右会出现许多元素接近或等于0. 总的来看, DCT会将信息往左上角聚拢, 而剩下的信息都是接近或等于0的.

示例

下面是一个 $8 \times 8$ 矩阵 $A$ 只包含值100.

A = [\begin{matrix} 100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\ 100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\ 100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\ 100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\ 100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\ 100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\ 100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\ 100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \end{matrix}]

DCT得到 $B = U A U^{T}$ .

B = [\begin{matrix} 800 & 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 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}]

可以看到整个块的信息除了 $(1, 1)$ 位置都被变换为0. 再看另一个例子, 下面的矩阵 $A$ 只包含值50-52(near-constant), 对于图像来说,是平滑的一块, 包含的是高频信息.

A = [\begin{matrix} 51 & 52 & 51 & 50 & 50 & 52 & 50 & 52 \\ 51 & 52 & 51 & 51 & 50 & 52 & 52 & 51 \\ 50 & 50 & 51 & 52 & 52 & 51 & 51 & 51 \\ 51 & 50 & 50 & 50 & 52 & 50 & 50 & 51 \\ 51 & 50 & 50 & 51 & 50 & 50 & 51 & 50 \\ 50 & 51 & 52 & 52 & 51 & 50 & 50 & 50 \\ 51 & 52 & 51 & 50 & 52 & 50 & 52 & 50 \\ 50 & 51 & 52 & 52 & 50 & 51 & 52 & 51 \end{matrix}]

经过DCT变换(保留小数点后三位), 也可以发现除了左上角407,其他的值都接近0.

B = [\begin{matrix} 407 & 0.058 & - 0.518 & - 0.592 & - 0.5 & 0.118 & - 0.597 & 0.086 \\ 0.352 & - 0.654 & 1.019 & 0.818 & 0.179 & - 1.074 & 1.190 & - 1.194 \\ 1.904 & - 0.116 & 1. & - 0.598 & - 2.174 & - 0.352 & 0.293 & - 1.006 \\ - 0.661 & 1.350 & 0.689 & - 0.055 & - 0.425 & - 0.599 & 0.254 & - 0.412 \\ - 1. & - 0.335 & 1.171 & 0.102 & 0.5 & - 0.020 & 0.868 & - 0.502 \\ - 0.229 & 0.162 & 0.115 & 0.711 & 0.956 & - 1.902 & - 0.108 & 1.454 \\ 0.023 & - 0.173 & - 1.707 & - 1.529 & 0.630 & 0.109 & 1. & - 0.603 \\ - 0.110 & - 0.383 & 0.105 & 0.470 & 0.005 & 0.568 & - 0.470 & 0.111 \end{matrix}]

DCT特点

DCT 矩阵 $U$ 是可逆的, 同时 U是正交的, 有 $U^{T} = U^{- 1}$ .证明
DCT计算 $B = U A U^{T}$ , 这是个相似变换. 可以通过FFT(Fast Fourier Transformation)加速.

2.3 Quantization量化

上一节看到, DCT矩阵是无理数组成的, 而输入矩阵是整数, 输出矩阵一般为实数. 而接下来的编码最好是作用在整数域. 所以JPEG有一步量化.

下面走一下JPEG流程来说明量化的工作机制. 给出一个经过预处理(-127)的block.

A = [\begin{matrix} - 122 & 49 & 66 & 41 & 41 & 43 & 40 & 38 \\ - 121 & 49 & 31 & 45 & 35 & 50 & 41 & 24 \\ - 122 & 40 & 45 & 105 & 31 & - 66 & 18 & 87 \\ - 94 & 52 & 42 & 47 & - 122 & - 122 & 8 & 51 \\ - 119 & - 23 & 53 & 51 & 45 & 70 & 61 & 42 \\ - 64 & - 122 & - 25 & - 26 & 33 & 15 & 6 & 12 \\ - 76 & - 80 & - 64 & - 122 & 53 & 64 & 38 & - 122 \\ - 78 & - 74 & - 84 & - 122 & 57 & 43 & 41 & - 53 \end{matrix}]

经过DCT变换(保留小数点后两位).

B = [\begin{matrix} - 27.50 & - 213.47 & - 149.61 & - 95.28 & - 103.75 & - 46.95 & - 58.72 & 27.23 \\ 168.23 & 51.61 & - 21.54 & - 239.52 & - 8.24 & - 24.50 & - 52.66 & - 96.62 \\ - 27.20 & - 31.24 & - 32.28 & 173.39 & - 51.14 & - 56.94 & 4.00 & 49.14 \\ 30.18 & - 43.07 & - 50.47 & 67.13 & - 14.12 & 11.14 & 71.01 & 18.04 \\ 19.50 & 8.46 & 33.59 & - 53.11 & - 36.75 & 2.92 & - 5.80 & - 18.39 \\ - 70.59 & 66.88 & 47.44 & - 32.61 & - 8.20 & 18.13 & - 22.99 & 6.63 \\ 12.08 & - 19.13 & 6.25 & - 55.16 & 85.59 & - 0.60 & 8.03 & 11.21 \\ 71.15 & - 38.37 & - 75.92 & 29.29 & - 16.45 & - 23.44 & - 4.21 & 15.62 \end{matrix}]

为了量化block

B

, JPEG用一个预设的表

Z

去除

B

(element-wise division)然后取整.

这个矩阵 $Z$ 也体现了JPEG压缩的特点, 左上角的信息压缩的程度小, 右下角的信息压缩的程度大.通过缩放矩阵 $Z$ ,达到控制压缩程度.

Z = [\begin{matrix} 16 & 11 & 10 & 16 & 24 & 40 & 51 & 61 \\ 12 & 12 & 14 & 19 & 26 & 58 & 60 & 55 \\ 14 & 13 & 16 & 24 & 40 & 57 & 69 & 56 \\ 14 & 17 & 22 & 29 & 51 & 87 & 80 & 62 \\ 18 & 22 & 37 & 56 & 68 & 109 & 103 & 77 \\ 24 & 35 & 55 & 64 & 81 & 104 & 113 & 92 \\ 49 & 64 & 78 & 87 & 103 & 121 & 120 & 101 \\ 72 & 92 & 95 & 98 & 112 & 100 & 103 & 99 \end{matrix}]

得到一个新矩阵

Q

, 其中

q_{j k} = r o u n d (b_{j k} / z j k)

for

j, k = 1, . . ., 8

Q = [\begin{matrix} - 2 & - 19 & - 15 & - 6 & - 4 & - 1 & - 1 & 0 \\ 14 & 4 & - 2 & - 13 & 0 & 0 & - 1 & - 2 \\ - 2 & - 2 & - 2 & 7 & - 1 & - 1 & 0 & 1 \\ 2 & - 3 & - 2 & 2 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & - 1 & - 1 & 0 & 0 & 0 \\ - 3 & 2 & 1 & - 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & - 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & - 1 & 0 & 0 & 0 & 0 & 0 \end{matrix}]

因为有取整的操作, JPEG是有损的压缩

逆转过程

要逆转过程, 重新得到原来的block $A$ ,只需先反转除法, 得到 $B^{'}$ , 其中 $b_{j k}^{'} = q_{j k} \times z_{j k}$ . 注意到 $B^{'}$ 和 $B$ 的值是有一点不同的(lossy).

B^{'} = [\begin{matrix} - 32 & - 209 & - 150 & - 96 & - 96 & - 40 & - 51 & 0 \\ 168 & 48 & - 28 & - 247 & 0 & 0 & - 60 & - 110 \\ - 28 & - 26 & - 32 & 168 & - 40 & - 57 & 0 & 56 \\ 28 & - 51 & - 44 & 58 & 0 & 0 & 80 & 0 \\ 18 & 0 & 37 & - 56 & - 68 & 0 & 0 & 0 \\ - 72 & 70 & 55 & - 64 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & - 87 & 103 & 0 & 0 & 0 \\ 72 & 0 & - 95 & 0 & 0 & 0 & 0 & 0 \end{matrix}]

然后作用inverse DCT,

A^{'} = U^{T} B^{'} U

.下面对比一下原图像

A

和恢复的

A^{'}

,可以看出JPEG有损的特点了.

A^{'} = [\begin{matrix} - 128 & 45 & 71 & 63 & 22 & 32 & 22 & 52 \\ - 110 & 39 & 4 & 48 & 41 & 68 & 65 & 13 \\ - 115 & 40 & 50 & 152 & 13 & - 88 & - 4 & 76 \\ - 105 & 51 & 43 & 18 & - 126 & - 99 & 19 & 60 \\ - 116 & - 24 & 56 & 63 & 33 & 80 & 62 & 28 \\ - 67 & - 118 & - 47 & - 24 & 30 & 17 & - 12 & 29 \\ - 67 & - 79 & - 60 & - 116 & 49 & 69 & 12 & - 108 \\ - 78 & - 69 & - 80 & - 138 & 63 & 41 & 49 & - 67 \end{matrix}]

A = [\begin{matrix} - 122 & 49 & 66 & 41 & 41 & 43 & 40 & 38 \\ - 121 & 49 & 31 & 45 & 35 & 50 & 41 & 24 \\ - 122 & 40 & 45 & 105 & 31 & - 66 & 18 & 87 \\ - 94 & 52 & 42 & 47 & - 122 & - 122 & 8 & 51 \\ - 119 & - 23 & 53 & 51 & 45 & 70 & 61 & 42 \\ - 64 & - 122 & - 25 & - 26 & 33 & 15 & 6 & 12 \\ - 76 & - 80 & - 64 & - 122 & 53 & 64 & 38 & - 122 \\ - 78 & - 74 & - 84 & - 122 & 57 & 43 & 41 & - 53 \end{matrix}]

2.4 编码

JPEG最后一步是对变换,量化后的图像进行编码. 用huffman编码或者其他编码方式, 可以显著节省存储空间.

理解JPEG图像压缩算法,DCT变换

理解JEPG原理

1.彩色图像

灰度图像

彩色图像

YCbCr

2.JPEG算法

2.1 预处理

2.2 DCT变换

DCT每一行图示

示例

DCT特点

2.3 Quantization量化

逆转过程

2.4 编码

3. 参考

相关推荐