FRG是一种优化从磁盘加载和解码到显示需要的时间的图像文件格式. （更多介绍： http://blog.csdn.net/housisong/article/details/9077059 ）
这里介绍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的块的时候,先在当前区域前面的整幅图片中查找重复的区域位置,重复方式可能是平移\左右对称\上下对称等 (其他重复方式较少见而没有特别处理); 该算法很简单,难度只在于实现的匹配速度;
FRZ压缩算法:
为了进一步压缩RLE生成的Alpha通道编码数据,开发了一种能够快速解压的通用字节流压缩算法FRZ; (当要求输出较小的编码数据时,FRZ也被用于RGB的编码数据的进一步压缩); FRZ的设计目的是生成一种能够快速解压的压缩数据格式,而不太在意压缩时的时间和内存空间占用;
不使用zip\LZMA等通用的数据压缩算法是因为这些算法的解压对FRG的要求来说是实在是太慢了;
尝试过专门为快速编解码应用而设计的lzo算法,一般情况下压缩率和解压速度曲线 比FRZ差;
FRZ的更详细介绍和性能测试: http://blog.csdn.net/housisong/article/details/9104643 ; 可以看到FRZ,压缩率中等,编码格式简单(解码器也超简单),解码特别的快(甚至能达到每秒解码1GB以上的数据!)