FRG图像文件格式(四):编码技术

FRG图像文件格式(四):编码技术

作者: HouSisong

FRG是一种优化从磁盘加载和解码到显示需要的时间的图像文件格式.

这里介绍FRG涉及到的一些编码技术.

Alpha通道的处理:

  Alpha通道独立压缩,现在的实现是无损压缩;

  如果图像的alpha通道只有一个值(或没有alpha通道),则只需要储存一个alpha值就可以了;

  如果不是单色alpha,数据压缩使用RLE行程压缩算法(格式简单,编解码快速), 由于数据中一般来说0和255的值居多,所以进行了特殊处理; 

  编码分成控制数据和未压缩alpha数据;  

    控制数据按照: "类型\长度\类型\长度\…\类型\长度"来编码;

    "类型"占用2个bit位, 00表示后面存的压缩0数据, 01表示后面存的压缩255数据, 10表示后面存的压缩数据(alpha数据包中只需储存一个字节数据), 11表示后面存的未压缩数据 ("未压缩alpha数据"中连续原样储存多个字节数据);  "长度"用的变长编码,1个bit来表示后面的字节是否被用于编码,"类型"占用的那个字节剩余的6bit也用于长度编码(也就是如果"长度"值<=5bit则可以和"类型"共享一个字节);

RGB数据的处理:

  基本方案：将图片分成8x8的块；对一个8x8的块找到能够最精确的描述这64个像素的16个或以下不同的颜色(称为局部调色板)；对于原来的64个像素的每一个像素只保存一个4bit的索引值来指向一个最接近的局部调色板颜色(如果颜色数较少就会使用更小的bit位来储存索引,单颜色的调色板不需要储存索引); 将得到的局部调色板颜色储存到一个公共调色板中;  

  无损压缩:

     将64个颜色压缩到16个颜色的过程中, 8x8的块颜色数超过16,而要求无损失储存或强制压缩颜色数会造成损失过于严重,这时可以使用无损压缩方案；直接将64个颜色存入公共调色板,而不存储索引数据;

  调色板优化：

    储存该单元的局部调色板的时候,先在公共调色板中查找有没有一段颜色和该调色板等价;从而不需要储存该局部调色板;

       算法:  长度n的调色板在公共调色板中查找匹配到一段(1<<getBit(n))长的颜色数据位置;这和字符串的查找匹配算法类似,但这里的挑战在于匹配时n个颜色无顺序;甚至颜色相等的判断可以允许有小的误差; (ps:如果让你实现该算法, 时间可以做到可接受级别吗? )

  重复图像的优化:

     一幅图像中可能有很多区域可能都是重复的(重复方式可能是平移\左右对称\上下对称等),这在美工作出的图像中很常见; 那么可以不用储存这些区域;

    算法: 在处理当前的8x8的块的时候,先在当前区域前面的整幅图片中查找重复的区域位置,重复方式可能是平移\左右对称\上下对称等 (其他重复方式较少见而没有特别处理);  该算法很简单,难度只在于实现的匹配速度;

BytesZip压缩算法:

  为了进一步压缩RLE生成的Alpha通道编码数据,开发了一种能够快速解压的通用字节流压缩算法BytesZip; (当要求输出较小的编码数据时,BytesZip也被用于RGB的编码数据的进一步压缩);  BytesZip的设计目的是生成一种能够快速解压的压缩数据格式,而不太在意压缩时的时间和内存空间占用;  

  不使用zip\LZMA等通用的数据压缩算法是因为这些算法的解压对FRG的要求来说是实在是太慢了;

  尝试过专门为快速编解码应用而设计的lzo算法,压缩率和解压速度曲线 比BytesZip差些;

  BytesZip的编码分成控制数据和未压缩字节数据;

     控制数据按照: "类型\长度[\前移匹配]\类型\长度[\前移匹配]\…\类型\长度[\前移匹配]"来编码;

     "类型"占用1个bit位, 0表示后面存的未压缩数据("未压缩字节数据"中连续原样储存多个字节数据;控制数据中无"前移匹配"数据), 1表示后面存的压缩(替代)数据(在控制数据中储存向前匹配的距离数据)

     "长度"用的变长编码,1个bit来表示后面的字节是否被用于编码,"类型"占用的那个字节剩余的7bit也用于长度编码(也就是如果"长度"值<=6bit则可以和"类型"共享一个字节);

     "前移匹配"也用的变长编码; 代表从当前位置向前移动该距离处拷贝"长度"的数据; (这就是BytesZip压缩能力的来源,当前的一段数据用前面已有的相同的数据代替);

  可以看到, BytesZip是一种异常简单的数据压缩编码格式,它的解码器实现只需要40行以内的源代码,却能够提供不错的压缩率,并且能够快速的解压缩数据.  (编码算法现在的实现也较简单,用后缀数组的最长子串算法实现)

  ps: 阻止BytesZip取得更大的压缩率的原因在于"长度"和"前移匹配"数据的储存,这里是有可能做进一步处理的,比如对前面的重复数据作出统计,按几率生成更短的编码(按一定规则维护一个动态码表); 那控制数据只需要存储编码就可以了;但这样的设计就回到了常规压缩算法的设计想法里,可能会牺牲解码性能;