Skip to content

Latest commit

 

History

History
107 lines (78 loc) · 6.07 KB

README.md

File metadata and controls

107 lines (78 loc) · 6.07 KB
Raw

JPEG DECODER

a simple jpeg decoder, implement from zero to learn its compress algorithm.

参考了一些网络上的JPEG文章，并未参考其实现，在实现上均按自己的理解进行，由于是以学习为目的，所以代码尽可能表达解码流程，对内存管理及计算不做任何优化

进度

  1. 区段解析
  2. SOF0解析
  3. DQT解析
  4. DHT解析
  5. SOS解析
  6. 图像解析

目前状态

可以正常解析部分图像了！

lena origin

lena succeed

这个解码器还有哪些工作没有做？

  1. 仅为baseline支持
  2. 未对右侧及下侧超出不满一个block的部分进行处理
  3. 一个DHT段可能包含多个DHT表，这里也没有进行处理
  4. 未对可能出现的RSTn进行处理

为何解码出来的图像不正常？

旧的分析

从上面给出的例子来看，大体上是可以看出基本正确的，但有些色块不正常，目前没有时间进行完善修复了，这里记录当前的分析过程

  1. 在IDCT之后，分别对Cb和Cr分量+了128，最终Cb和Cr分量看起来应该是正确的了
  2. 尝试对Y也+128，但会发现，现在正常的色块与异常的色块会交换
  3. 因此中间得到的一个粗糙的结论是，Y分量部分为-128~127，另一部分为0~255，这明显是不合理的
  4. 回溯分析到读取block结束的部分，此时会获取所有MCU的所有block的直流分量和交流分量，发现是存在一些不正常的：
  • Y分量的直流分量越来越大，到最后已经达到了30000以上，而Cb和Cr均没有这样的情况

分析

问题已经解决了，原因很蠢，就是在处理直流分量时，mask由传入的16位误写为了8位，导致数据异常，就是本来是一个负数，但是经过一个8位的mask之后前面的符号位都被置0了，导致变成了正数，进而导致直流分量错误无限积累。而在这个过程中，Cb和Cr的直流分量的变化量没有那么大，导致最终没有出现异常

粗略写一下解析流程

这部分互联网上资料比较多，也可以参考最下方的文章，因此暂时粗略叙述方便回忆

一些前置知识：

JPEG编码的流程大概为：

  • 颜色空间转换：RGB -> YCbCr，RGB好理解，Y为亮度信息，Cb和Cr为色度和饱和度，人眼对亮度敏感，对色度和饱和度不敏感，因此图像、视频压缩一般都会在这里做文章，举例来说，同尺寸的YCbCr420图像比RGB要少一半的数据量
  • 降采样：444 -> 444/422/420，444即4个Y对应了4个Cb、4个Cr，这种情况就是没有进行降采样，422即4个Y对应2个Cb和2个Cr，420即4个Y对应1个Cb和1个Cr，具体采样方式要看SOF0
  • DCT变换
  • 量化
  • 霍夫曼编码

编码时是以MCU（Minimum Coding Unit），每个MCU中包含多个block，包含几个block要看SOF0，比如说Y分量的采样率为2和2，Cb和Cr的采样率都为1和1，那么一个MCU中将包含6个block，4个Y的，1个Cb的，1个Cr的。

MCU的排列为一行一行一行的，MCU中的block也为一行一行一行的，举例：

  • MCU[0][0].block[Y][0][0]
  • MCU[0][0].block[Y][0][1]
  • MCU[0][0].block[Y][1][0]
  • MCU[0][0].block[Y][1][1]
  • MCU[0][0].block[Cb][0][0]
  • MCU[0][0].block[Cr][0][0]
  • MCU[0][1].block[Y][0][0]
  • MCU[0][1].block[Y][0][1]
  • MCU[0][1].block[Y][1][0]
  • MCU[0][1].block[Y][1][1]
  • MCU[0][1].block[Cb][0][0]
  • MCU[0][1].block[Cr][0][0]
  1. 首先将图像数据读进内存准备处理
  2. JPEG分成了许多段，每个段都以0xFF做分隔，0xFF后面一个字节标识了该段的作用，需要注意的是，在图像的压缩数据部分，也会存在0xFF，但这个0xFF是编码数据，因此JPEG标准中规定，需要对每个0xFF后面填充一个0x00，在解码时需要跳过该填充字节
  3. 主要需要进行解析的有以下几段：
  • SOI(0xD8)：start of image，文件头，没有其它数据
  • EOI(0xD9)：end of image，文件尾，没有其它数据
  • APPn(0xEn)：application n，包含一些元数据，这里不做解析
  • SOF0(0xC0)：start of image 0，0为baseline
  • DQT(0xDB)：define quantization table，量化表数据
  • DHT(0xC4)：define huffman table，霍夫曼表
  • SOS(0xDA)：start of scan，一些图像参数，后面就是图像数据了
  1. 解析DQT，根据参数，按字节（或双字节）依次读取即可，最终得到的就是一个8x8的表，每个表会有一个id，这个读取是比较简单的
  2. 读取DHT，重点在于读取叶子节点个数以及重建霍夫曼表部分。霍夫曼编码是一种变长编码，基本思路是按值的频率，出现频率越高的值，其编码码字越短，其构建方式也可以保证依次按bit读取时不会出现短码字与长码字的冲突，这里会存在一个颜色分量id和直流交流类型，颜色分量id表明不同的颜色分量将使用不同的霍夫曼表来进行解析，直流交流类型表明直流与交流分量也需要使用不同的霍夫曼表，一般会有4个霍夫曼表，分别提供给Y/CbCr以及DC/AC进行解析，另外需要注意，有可能一个DHT段中包含多个霍夫曼表，也可能一个段中只包含一个，本项目中只处理了后面一种简单的情况
  • 首先从0开始，没有长度为1的码字，然后继续分析
  • 如果相同长度还有码字，那么+1，比如长度为2的有3个，则分别为00、01、10，接下来
    • 如果存在长度为3的码字，那么长度为3的码字将由110开始，即长度为2的最后一个码字+1再在后面补一个0
    • 如果不存在长度为3的码字，存在长度为4的码字，那么长度为4的码字将由1100开始
  • 也就是说，当前长度层如果存在码字，那么下一长度将由当前长度的最后一个码字+1再补0，如果不存在，则直接补0，考虑霍夫曼编码原理，是可以理解这样处理的原因的

IDCT:

$$ result[i][j] = \frac{1}{4}\sum{{x=0} ^7}\sum{{y=0} ^7}C_x C_y cos(\frac{(2i + 1)x\pi}{16}) cos (\frac{(2j + 1)y\pi}{16}) block[x][y] $$ $$ C_0 = \frac{1}{\sqrt{2}}​ $$ $$ C_i = 1, \forall i > 0 $$