图像数据压缩

cW ← first Character ofDictionary[cW]

Dictionary[j]← Prefix.cW

j ← n+1

pW ← cW

else

Prefix ← Dictionary[pW]

cW ← first Character of Prefix

Charstream← Prefix.cW

Dictionary[j]← Prefix.C

pW ← cW

j ← n+1

end

[例] 编码字符串如(表3.4)所示，编码过程如(表3.5)所示。现说明如下：

“步骤”栏表示编码步骤；

“位置”栏表示在输入数据中的当前位置；

“词典”栏表示添加到词典中的缀-符串，它的索引在括号中；

“输出”栏表示码字输出。

表3.4 被编码的字符串

表3.5 LZW的编码过程

(表3.6)解释了译码过程。每个译码步骤译码器读一个码字，输出相应的缀-符串，并把它添加到词典中。例如，在步骤4中，先前码字(2)存储在先前码字(pW)中，当前码字(cW)是(4)，当前缀-符串string.cW是输出(“A B”)，先前缀-符串string.pW (“B”)是用当前缀-符串string.cW (“A”)的第一个字符，其结果(“B A”) 添加到词典中，它的索引号是(6)。

表3.6 LZW的译码过程

LZW算法得到普遍采用，速度比使用LZ77算法的速度快，因为LZW算法不需要执行那么多的缀-符串比较操作。对LZW算法进一步的改进是增加可变的码字长度，以及在词典中删除老的缀-符串。在GIF图像格式和UNIX的压缩程序中已经采用了改进措施之后的LZW算法。

4算法实现

本算法采用离散余弦变换DCT(Discrete Cosine Transform).

以下是压缩中产生的数据:

Input matrix (原始数据)

155 159 162 180 177 163 170 178

161 164 168 217 206 175 166 175

170 161 165 200 196 187 192 180

161 155 155 166 204 206 204 218

156 156 156 156 176 212 219 213

152 158 153 156 160 185 221 198

152 161 152 152 156 158 191 212

157 154 154 152 152 162 172 186

Output matrix after forward DCT (DCT变换之后的数据)

123 -22 1 0 1 00 0

6 4 -6 0 20 0 0

-7 5 0 -2 10 0 0

-1 -1 1 0 -10 0 0

0 -1 0 0 00 0 0

0 0 1 0 00 0 0

0 0 0 0 00 0 0

0 0 0 0 00 0 0

Output matrix after reverse DCT (对上面矩阵反变换后的输出)

'>'后的数据是原始数据,失真不是很大.

看到上面的矩阵中大多数元数都是零,

对上述矩阵应用游程编码后将获得很高的压缩率.

157 157 168 184 180 164 165 181

>155 159 162 180 177 163 170 178

160 158 173 196 195 175 167 177

>161 164 168 217 206 175 166 175

167 159 168 191 200 190 185 192

>170 161 165 200 196 187 192 180

162 157 160 176 194 204 208 209

>161 155 155 166 204 206 204 218

149 154 157 164 184 208 214 207

>156 156 156 156 176 212 219 213

152 158 155 150 164 191 206 203

>152 158 153 156 160 185 221 198

159 159 153 145 150 169 190 200

>152 161 152 152 156 158 191 212

152 151 153 155 155 159 176 193

>157 154 154 152 152 162 172 186

#define N 8

N 是DCT变换的块的大小,JPEG小组推荐使用8x8的矩阵,

下面的程序块太大,运算就会很大.

太小则压缩率太小.

#define quality 2

quality 是量化因子,取值从1到25,quality控制压缩率.

使用photoshop等软件将图片存为JPG格式时,

选择图像质量,就是修改这个变量.

quality为1时,图像质量最好,压缩率最低.

quality为25时,图像退化的非常厉害,压缩率最高.

#define uchar unsigned char

float C[N][N], Ct[N][N];

uchar quantum[N][N];

// Initialize cosine transform matrix and quality factor

// 初始化余弦变换矩阵和量化因子

void InitCTM()

{

int i, j;

for (i=0; i<N; i++)

{

C[0][i] = 1.0 / sqrt(N);

Ct[i][0] = C[0][i];

}

for (i=1; i<N; i++) for (j=0; j<N; j++)

{

C[i][j] = sqrt(2.0/N) * cos((2.0*j+1.0)*i*M_PI/(2.0*N) );

Ct[j][i] = C[i][j];

}

for (i=0; i<N; i++) for (j=0; j<N; j++)

quantum[i][j] = 1 + (1+i+j) *quality; // 量化因子

}

// 进行DCT变换

void ForwardDCT(uchar *input, int *output)

{

float temp[N][N], t;

int i, j, k;

for (i=0; i<N; i++) for (j=0; j<N; j++)

{

temp[i][j] = 0.0;

for (k=0; k<N; k++) temp[i][j] +=Ct[k][j]*(input[i*N+k]-128);

}

// 时间复杂性为O(N^3),是做浮点乘法, N不能太大了.

for (i=0; i<N; i++) for (j=0; j<N; j++)

{

t = 0.0;

for (k=0; k<N; k++) t += C[i][k]* temp[k][j];

output[i*N+j] = t / quantum[i][j];// 除上量化因子,高频将近似到0

}

}

// 反变换

void InverseDCT(int *input, uchar *output)

{

float temp[N][N], t;

int i, j, k;

for (i=0; i<N; i++) for (j=0; j<N; j++)

{

temp[i][j] = 0.0;

for (k=0; k<N; k++)temp[i][j]+=C[k][j]*input[i*N+k]*quantum[i][k];

}

for (i=0; i<N; i++) for (j=0; j<N; j++)

{

t = 0.0;

for (k=0; k<N; k++) t +=Ct[i][k]*temp[k][j];

t += 128.0;

if ( t<0 ) output[i*N+j] = 0;

else if ( t>255 ) output[i*N+j] =255;

else output[i*N+j] = t;

}

}

使用方法:

uchar pixel[8][8];

for (i=0; i<8; i++) memcpy(pixel[i], v+i*320, 8);// save first 8x8 block

//在模式0x13下,将左上角的一块图片数据存放到pixel

//注意已经将0x13模式下的调色板改成灰度.

bioskey(0);

InitCTM(); //初始化余弦变换矩阵

int iDCT[N][N];

uchar oDCT[N][N];

ForwardDCT(pixel[0], iDCT[0]); //DCT变换

InverseDCT(iDCT[0], oDCT[0]); //反变换

for (i=0; i<8; i++) memcpy(v+i*320, oDCT[i], 8); //save first 8x8 block

//把反变换后的数据显示到屏幕上,观察区别.

//要压缩,在运行ForwardDCT后,对iDCT中的数据按ZigZag顺序

//用游程编码压缩。

结论

对图象数据进行数据压缩是实现实时有效地处理 、传输和存储图象数据的首要问题和根本方法.视频图像压缩的出发点是利用各种算法将数据冗余压缩到最少,以保留尽可能少的有用信息.为了使压缩后的数据能够互换 ,必须规定通用的标准格式.国际上静止图像压缩标准是JPEG,而活动图像压 缩标准是 MPEG 1,MPEG 2和正在试验阶段的 MPEG 4 .到目前为止,尽管图像压缩技术已很成熟 、并得到了广泛的应用,但是人们仍在继续研究,如采用小波分析的方法和分形的方法进行压缩,以追求更高的压缩效率和更好的图像质量。

参考文献
[1]陈传波,金先级. 数字图像处理[M]. 北京：电子工业出版社，2004.15-55.
[2]何东健,耿楠,张义宽. 数字图像处理[M]. 西安：西安电子科技大学出版社，2003.20-56.
[3]李朝晖,张弘,王京文. 数字图像处理[M].北京：机械工业出版社,2004.1-70.
[4]精英科技.视频压缩与音频编码技术[M]. 北京：中国电力出版社，2001.15.
[5]Shsprio J.M. Emeddedimage coding using zerotrees of wavelet coefficients.IEEE Trans［J］. SP, 1993(12).3445-3462.
[6] Qingtang Jiang.Orthogonal multiwavelets with optimum time-frequency resolution, IEEE Trans[M].1998.830-844.
[7]HweeHuat Tan,New biorthogonal multiwavelets for image compression[M].1999.45-65.
[8]BoonlockYeo.OnFastMicroscopicBrowsingofMPEGCompressedVideo[M].2002.22-39.
[9]Sethuraman(Panch) Panchanathan.Architectural Approaches for Mult imedia Processing［J］.Computer Science,1999(10).196.
 

 5/5   首页 上一页 3 4 5