本帖最后由 lxyppc 于 2010-3-30 23:46 编辑
维基百科上关于JPEG压缩算法的介绍http://en.wikipedia.org/wiki/JPEG
这里以一个64X64的图片为例子来说明转换过程。如图:
JEPG算法在压缩前会将图像由RGB颜色空间转换成为YUV颜色空间，转换公式如下：
/**
RGB to YUV Conversion
Y = (0.257 * R) + (0.504 * G) + (0.098 * B) + 16
Cr = V = (0.439 * R) - (0.368 * G) - (0.071 * B) + 128
Cb = U = -(0.148 * R) - (0.291 * G) + (0.439 * B) + 128
*/
转换后图片分为YUV三部分，Y为亮度信息(即黑白电视机的信号)，UV为色差信息。
再将整幅图像分为若干个8X8的小格子，不能被8整除的会在后面补齐。这样图片被分成了64个8X8的小格子。
由于人眼对亮度(Y)的变化要比对色差(UV)的变化敏感，因此在Jpeg算法中一般将四个8X8的U(V)格子合成一个16X16的格子，再将相邻四个BYTE像素信息合为一个BYTE，U(V)分量的信息就被压缩成了原来的1/4，用一个8X8的信息块就能够描述16X16的U(V)数据。
此时把原始图像分成16个16X16的格子，可以看出每个格子由4个8X8的亮度数据，1个8X8的U色差数据和1个8X8的V色差数据组成。这样的一个16X16的格子称为一个MCU(Minimum Coded Unit)而一幅压缩后的Jpeg图像就是由这样的一个个MCU组合而成的。这幅图片是由16个这样的MCU组合而成的，并且MCU与MCU之间没有太大的关联，这也是能用Jpeg格式来玩俄罗斯方块的基础。
一个MCU做为压缩算法的一个基本单元，其中包括了4个8X8的Y信息，1个8X8的U信息，1个8X8的V信息，一共六个8X8的信息块，前四个是亮度(Y)信息，后两个是色差(UV)信息。Jpeg算法对每个这样8X8的信息单元进行离散余弦变换，并将变换后的结果除上一个数，这个数也表示了压缩的质量。以此来减少信息所需要的位宽。比如有150,43,72三个数，总共需要24位才能全部表示，但是如果将它们都除以16后，最大的数只需要4位，一共12位就行了。虽然数据在还原的时候会有所失真，但是人眼不会对这种差别很敏感。
结果输出是使用之字型(ZigZag)的顺序输出，这样可以让连续零出现的次数尽可能的多，尽量减小编码的长度。
离散余弦变换(DCT)后结果的第一个值为这个单元的直流分量，后面63个值为此单元的交流分量。直流分量输出时不是直接输出，而是与上一个单元的直流分量做减法后输出差值。YUV分别使用三个不同的值来记录上一个单元的直流分量。由于直流分量输出是以差值的形式，因此就输出结果而言，整个图片输出的时候直流值是相关的。这也是在输出图片的代码中需要一定的计算的原因。
接下来是输出每个8X8单元的63个交流值，交流部分直接输出，Huffman编码使用查表的方式得到，其中连续的零和结尾的零用特殊的编码方式表示，用以减少编码长度。
再完成一个MCU的编码之后继续对下一个MCU进行编码，这幅图片一共分为16个MCU。
俄罗斯方块的基本元素就是一个一个的方块，这正好对应了Jpeg压缩算法中的MCU。一般俄罗斯方块的游戏区域为一个10X20的矩阵，我用一个MCU来表示矩阵中的一个点，这样游戏区域就含有10X20个MCU。在输出图像数据的时候，没有方块的地方，使用当前背景的MCU数据，而有方块的地方，使用代表方块图案的MCU数据，这样就能在背景上画出方块的图案了。
像素不变时，使用Baseline DCT的压缩算法数据头不会因内容的改变而改变，因此每帧图像都使用相同的数据头。只需要根据当前方块位置在指定位置输出不同的MCU即可。
MCU的数据由直流和交流部分组成，交流部分不需要重新计算，只要预先算好，需要时取出即可。而直流部分的输出与上一个单元单的直流部分有关。
生成数据的时候提取出MCU的直流部分的原始值，为一个有符号数，范围与图片有关，在图像输出的时候先作差再编码输出。
由于当前MCU的交流值不与其它MCU相关联，生成数据的时候可以直接输出，在重建图像的时候直接输出即可。
注：MCU是以位的方式输出的。
实际代码如下:
// 将一个8X8的信息块进行输出，每一个MCU由6个这样的信息块组成，4个Y，1个U，1个V
int OutputHuffBlock(const unsigned int* codeTbl, const unsigned char* sizeTbl, int lastDC)
{
int temp1,temp2;
dc_t curDC = (dc_t)(*block++); //得到当前直流分量的值
u32 bitCnt;
temp1 = temp2 = curDC - lastDC; //与上一个直流分量的值作差
if(temp1<0){ //如果差小于零，取其补码作为输出
temp1 = -temp1;
temp2--;
}
bitCnt = 32 - __CLZ(temp1); //计算当前直流差值需要的位数
BitStreamOut(codeTbl[bitCnt],sizeTbl[bitCnt]); //将位数经过Huffman编码后输出
if(bitCnt){
BitStreamOut(temp2,bitCnt); //如果位不为零，输出当前直流分量的差值
}
bitCnt = *block++; //得到当前交流分量的位数
while(bitCnt>=8){
BitStreamOut(*block++,8); //直接输出交流分量的值
bitCnt-=8;
}
if(bitCnt){
u32 tmp = *block++;
tmp >>= 8-bitCnt;
BitStreamOut(tmp,bitCnt); //输出最后不足8位的交流分量值
}
return curDC;
}
一个MCU数据块的内容:
DC0~DC3表示4个亮度(Y)信息的直流部分，为有符号数。由于直流部分是以差值方式输出，此处记录了MCU直流部分的原始值
DC4表示色差U的直流部分
DC5表示色差V的直流部分
ACx Size表示当前AC位流的长度，单位为bit，由于AC部分直接输出，此处保存的是经过编码的交流部分的内容
ACx Stream表示当前AC位流的内容，结果左对齐
static const unsigned char Block_MCU1[] = {
/* DC0: */ 0x1D,
/* AC0 Size: */ 0x89,
/* AC0 Stream */
0xBA, 0xBA, 0x99, 0x2E, 0x19, 0x46, 0xE0, 0x15, 0x86, 0x0E, 0x3E, 0x56, 0x18, 0xE4, 0x67, 0xB1,
0xCD, 0x00,
/* DC1: */ 0x23,
/* AC1 Size: */ 0x68,
/* AC1 Stream */
0x8E, 0x76, 0x79, 0x97, 0x63, 0x6E, 0x8C, 0xA8, 0x6C, 0xE3, 0x04, 0x1F, 0x4A,
/* DC2: */ 0x1C,
/* AC2 Size: */ 0x62,
/* AC2 Stream */
0x6B, 0x7B, 0x88, 0x89, 0x0A, 0xE6, 0x54, 0xDF, 0xBB, 0x69, 0xE3, 0x22, 0x80,
/* DC3: */ 0x20,
/* AC3 Size: */ 0x69,
/* AC3 Stream */
0x95, 0xA5, 0x69, 0xA2, 0x31, 0xC3, 0xC8, 0x60, 0x58, 0x85, 0xC7, 0x1D, 0xC5, 0x00,
/* DC4: */ 0x00,
/* AC4 Size: */ 0x1F,
/* AC4 Stream */
0xAA, 0xD5, 0xD2, 0x88,
/* DC5: */ 0xFA,
/* AC5 Size: */ 0x19,
/* AC5 Stream */
0x4E, 0x49, 0xEA, 0x00,
}; |
楼主
标题置顶
标题高亮
来自 2楼
