数字图像处理-第3章图像变换及图像编码

1、3.2 图象变换 3.1 概述w由于图象数据量巨大，给存储、处理和传输都带来很多问题。如何采用对图象的新的表示方法以缩小表示一幅图象所需的数据量。图象编码要解决的主要问题就是尽最大可能对冗余性的代码进行压缩。图象变换是许多图象处理和分析的技术基础,介绍一些常用的图象变换和它们的性质。在图象处理和分析技术的发展中，付里叶变换曾经起过并仍在起着重要的作用.3.2 Fourier变换1. 1-D Fourier变换 对一个连续函数f(x)等间隔采样可得到一个离散序列。设采了N个样,则序列可表示为f(0),f(1),f(2),.,f(N-1),借助这种表达,可将离散傅里叶变换对定义为:(x:离散实变量

2、, u:离散频率变量) 可以证明离散傅利叶变换对总是存在的。以下认为f(x)是实函数，但一般F(u)是复函数： F(u)=R(u)+jI(u) (3.2-3) 其中R(u)和I(u)分别为F(u)的实部和虚部。写成指数形式为： 5式幅度函数F(u)又称f(x)的傅利叶频谱，6式为相位角。频谱的平方称为f(x)的功率谱，记为P(u): (3.2-7) )()()()(222uIuRuFuP 1. 1-D Fourier变换)72 . 3(2sin2cos2expuxjuxuxj 式（3.2-1）中的指数项可借欧拉公式写为：每个 u 值都确定所对应的正弦和余弦对的频率，所以成为频率变量。2. 2-

3、D FourierFourier变换变换若图象以正方形网格采样2-D付利叶变换.将式(3.2-1)和(3.2-2)推广: 1. 1-D Fourier变换 与1-D情况类似，2-D傅利叶变换的频谱、相位角和功率谱定义： (3.2-11) (3.2-12),(),(),(),(),(/ ),(tan),(),(),(),(22212/122vuIvuRvuFvuPvuRvuIvuvuIvuRvuF2. 2-D Fourier变换(3.2-13)例：2-D图像及其傅频谱的显示例：灰度图像及其傅频谱的显示djhw例：彩色图像及其傅频谱的显示djhw3.3 快速Fourier变换（FFT） )exp(

4、2NxxNjw令：xNNxNwxfF101)()( ：则12/1)12(212/021) 12(2)2(2NxxNxNNxwxfNwxfN11102) 12(1)2(121MxNxMxMMxNwwxfMwxfMM)()(21oNeFwF1、快速Fourier变换的推导（分成奇数项和偶数项之和）M03.3 快速Fourier变换（FFT）)()(21)(MFwMFMFoMNe)()(21oMNeFwF)exp(2NMNMNNMNjwwwwNNwjw)exp()()(21)(oNeFwFMF3.3 快速Fourier变换（FFT）2、FFT的设计思想 首先，将原函数分为奇数项和偶数项，通过不断的一

5、个奇数一个偶数的相加（减），最终得到需要的结果。 也就是说FFT是将复杂的运算变成两个数相加（减）的简单运算的重复。归纳快速傅立叶变换的思想：（1）通过计算两个单点的DFT，来计算两个点的DFT，（2）通过计算两个双点的DFT，来计算四个点的DFT，以此类推（3）对于任何N=2m的DFT的计算，通过计算两个N/2点的DFT，来计算N个点的DFT快速傅里叶变换(FFT)输入数据的排序：对输入数据的排序可根据一个简单的位对换规则进行. 如用x表示f(x)的1个自变量值，那么它排序后对应的值可通过把x表示成二进制数并对换各位得到. 例如 N=8, f(6)排序后为f(3),因为6110 而0113

6、把输入数据进行了重新排序，则输出结果是正确的次序。反之不把输入数据进行排序，则输出结果需要重新排序才能得到正确的次序地址的排序：按位倒序规则地址的排序：按位倒序规则例如：N = 8计算顺序及地址增量：3.3 快速Fourier变换（FFT）例：设对一个函数进行快速Fourier变换，函数为：76543210,ffffffff分成偶数、奇数为：6420,ffff7531,ffff40, ff62, ff51, ff73, ff0f4f2f6f1f5f3f7f)(1)0(0FF)(1)2(0FF)(1)1(0FF)(1)3(0FF),(,321)0(0FFFF),(,321)1(0FFFF),(

7、,76543210FFFFFFFF例：3.3 快速Fourier变换（FFT）76543210ffffffff6240ffff偶数区7351ffff基数区402021)0()0(fwfF402021)0() 1 (fwfF602221)2()0(fwfF602221)2() 1 (fwfF502121)1()0(fwfF502121)1() 1 (fwfF702321)3()0(fwfF702321)3() 1 (fwfF)0()0()0()2(04)0(21)0(FwFF) 1 () 1 () 1 ()2(14)0(21)0(FwFF)0()0()2()2(04)0(21)0(FwFF) 1

8、 () 1 ()3()2(14)0(21)0(FwFF)0()0()0()3(04)1(21)1(FwFF) 1 () 1 () 1 ()3(14)1(21)1(FwFF)0()0()2()3(04)1(21)1(FwFF) 1 () 1 ()3()3(14)1(21)1(FwFF3.3 快速Fourier变换（FFT）76543210ffffffff) 0 () 0 () 0 () 1 (08)0(21FwFF) 1 () 1 () 1 () 1 (18)0(21FwFF) 2() 2() 2() 1 (28)0(21FwFF) 3 () 3 () 3 () 1 (38)0(21FwFF)

9、0 () 0 () 4() 1 (08)0(21FwFF) 1 () 1 () 5() 1 (18)0(21FwFF) 2() 2() 6 () 1 (28)0(21FwFF) 3 () 3 () 7() 1 (38)0(21FwFF3.3 快速Fourier变换（FFT）3、二维快速Fourier变换 因为2维DFT可以看成是两次的1维DFT变换，即： 所以二维快速Fourier变换实际上是对其进行了2次的一维FFT变换。),(),(yxfffF列行3.4 图象图象n按照解码结果对原图的保真程度，图象压缩编码的可分为两大类：n信息保存型信息保存型：在压缩和解压中无信息损失。因此称为无损压缩，

10、压缩率在2到10之间。常用于图象存档。n信息损失型信息损失型：能获取较高的压缩率，但经过解压缩不能恢复原状。因此称为有损压缩。用于信息损失可容许的场合。3.4 图象图象n信息损失编码也可分为两类：n保真度编码：允许失真条件下和一定保真度准则下进行图象压缩编码。n特征抽取编码：只将图象的特征信息进行提取，并对其编码。显然这将大大压缩图象，是一种非信息保持编码。3.4 n平均信息法。如不等长熵编码中的哈夫曼（Haffman），香农（Shannon）、弗农（fano）编码等。n预测法：通常指线性预测法，如插值脉冲调制DPCM和增量调制法，还有非线性预测法等。n变换法：一般采用正交变换，如Founie

11、r变换， Walsh变换， Hadamard变换等。 M3.4n其他编码法。有内插法中的的取样和亚取样法，如亚行、亚场等。还有针对静止图象或二值图象的方块编码、游程编码，轮廓编码，跳过白色块编码等。3.5 n基本概念：1.图象熵。2.平均码字长度。3.编码效率。1.图象熵（Entropy） 平均信息量 设象素灰度集合为（w1, w2,wk, wM）其对应的概率分别为P1, P2 Pk PM，按信息论中信源信息定义，数字图象的熵H为：图象熵表示各灰度级比特数的统计平均值。MkkkbitPPH12)(log2.平均码字长度n设图象为Bk为数字图象第K个码字Ck的长度（二进制代数的位数），其相应出现

12、的概率为PM，则该数字图象所赋予的码字平均长度为：MkkkbitPBR1)(3.编码效率其中H为图象熵，R为平均码字长度。(%)RH3.5 熵编码方法根据信源编码理论：n当 时，可设计出某种无失真编码的方法。如编码结果RH时，这种编码效率很低，占用bit多。R接近H时，这种状态的编码方法，称为最佳编码。n当RH时，必然丢失信息而引起图象失真。熵编码的目的就是要使编码后的图象平均比特数R尽可能的接近图象熵。HR 3.6哈夫曼（Huffman）编码n哈夫曼编码是根据可变长度最佳编码定理，应用哈夫曼算法而定的一种编码方法。n它的平均码字长度在具有相同输入概率集合的前题下，比其他任何有一种唯一可译码都

13、小。1）将输入灰度级按出现的概率从大到小排序。2）将最小两个概率相加，形成一个新的概率集合，再按1步的方法重排，如此重复进行直到只有两个概率为止。3）分配码字。从最后一步开始反向进行，对最后两个概率分别赋“0”码赋“1”码。如此重复进行，若概率不变使用原码，若概率分裂为2个，其码字前几位依旧用原来的，码字的最后一位码元一个赋“1”，另一个赋“0”。1.编码步骤2.示例2.示例2.示例2.示例2.示例3.6 哈夫曼（Huffman）编码平均码字长度:编码效率：MkkkbitPPH12)(log3.7 有限行程长度压缩编码有限行程长度压缩编码 有限行程长度识别码 识别码由两个字节构成：识别码 3.

14、8 BMP位图格式 该格式是当今应用比较广泛的一种格式。 典型BMP应用程序就是Windows的画笔。 文件几乎不压缩，占用磁盘空间较大，它 的颜色存储格式有1位、4位、8位及24位， 缺点是该格式文件比较大。1. nBMP文件组成 一个文件头 一个位图信息数据 一个调色板数据 一个图像数据 BMP文件头、位图信息数据调色板数据 图象数据2.文件头数据结构BITMAPFILEHEADERname type remark offset(hex)文件类型 WORD 必须是BM 0文件大小 DWORD byte数 2reserved1 WORD must be 0 6reserved2 WORD m

15、ust be 0 8data offset DWORD 点阵位图数据偏移 0a3.位图信息数据BITMAPINFOHEADER name remark offset biSize 本结构所占用的字节数（一般0 x28) 0e biWidth 图像宽度（以像素为单位） 12 biHeight 图像高度（以像素为单位） 16 biPlanes 位平面数 (must be 1) 1a biBitCount 每像素位数(1-双色,4,8 or 24) 1c biCompression 压缩方式(BI_RGB=0, 未压 1e BI_RLE8=1,每像素8位,行程压缩编码 BI_RLE4=2,每像素4位

16、,行程压缩编码） biSizeImage 图像的大小（字节数,一般填0) 22 biXPelsMeter 位图水平分辨率,每毫米像素数 （一般B12h） 26 biYPelsMeter 位图垂直分辨率,每毫米像素数 （一般B12h） 2a biClrUsed 位图实际使用的颜色表中的颜色数（一般填0) 2e biClrImportant 位图显示过程中重要颜色数（填0所有重要） 324.颜色表RGBQUADrgbBlue BYTE rgbGreen BYTE rgbRed BYTE rgbReserved BYTE （must be 0)颜色表RGBQUAD长度由biByteCount （每像

17、素位数）定 biByteCount 颜色数 1 2 4 16 8 25624 167772165.用VC对BMP图象进行读写操作nVC有关BMP图象操作的函数和数据结构nBITMAPFILEHEADER 文件头nBITMAPINFOHEADER 位图信息数据nRGBQUAD 颜色表nSetDIBitsToDevice（）显示图象 请参考MSDN。1)BITMAPFILEHEADER文件头typedef struct tagBITMAPFILEHEADER WORD bfType; DWORD bfSize; 文件大小 WORD bfReserved1; WORD bfReserved2; DW

18、ORD bfOffBits; 位图数据偏移 BITMAPFILEHEADER, *PBITMAPFILEHEADER;2)BITMAPINFOHEADER位图信息数据typedef struct tagBITMAPINFOHEADER DWORD biSize;本结构所占用的字节数（一般0 x28) LONG biWidth;图像宽度（以像素为单位） LONG biHeight;图像高度（以像素为单位） WORD biPlanes;位平面数 (must be 1) WORD biBitCount; 每像素位数(1双色,4,8 or 24) DWORD biCompression; 压缩方式 D

19、WORD biSizeImage; 图像的大小 LONG biXPelsPerMeter; 位图水平分辨率,每毫米像素数 LONG biYPelsPerMeter; DWORD biClrUsed; 位图实际使用的颜色数（一般填0) DWORD biClrImportant;重要颜色数（填0：所有重要） BITMAPINFOHEADER, *PBITMAPINFOHEADER; 3)RGBQUADtypedef struct tagRGBQUAD BYTE rgbBlue; BYTE rgbGreen; BYTE rgbRed; BYTE rgbReserved; RGBQUAD;4) Set

20、DIBitsToDevice函数显示图象int SetDIBitsToDevice( HDC hdc, / handle to DC int XDest, / x-coord of destination upper-left corner int YDest, / y-coord of destination upper-left corner DWORD dwWidth, / source rectangle width DWORD dwHeight, / source rectangle height int XSrc, / x-coord of source lower-left co

21、rner int YSrc, / y-coord of source lower-left corner UINT uStartScan, / first scan line in array UINT cScanLines, / number of scan lines CONST VOID *lpvBits, / array of DIB bits CONST BITMAPINFO *lpbmi, / bitmap information UINT fuColorUse / RGB or palette indexes);6. BMP文件的读取#define DIB_HEADER_MARK

22、ER (WORD)(M8)|B)bool read_dib_file( const char *file, int width, int height, void *buffer )FILE *fp = fopen(file, rb ); if( !fp ) return false; /read bitmap file headerBITMAPFILEHEADER bmfHeader;if( fread( (void*)&bmfHeader, sizeof(bmfHeader), 1, fp ) 1 )return false;if( bmfHeader.bfType != DIB_

23、HEADER_MARKER )return false;/read bitmap info headerBITMAPINFOHEADER bmiheader;if( fread( (void*)&bmiheader, sizeof(bmiheader), 1, fp ) 1 )return false; if( bmiheader.biBitCount != 8 ) return false;if( bmiheader.biWidth != width ) return false;if( bmiheader.biHeight != height ) return false;/ski

24、p the color pallettefseek( fp, 256*sizeof(RGBQUAD), SEEK_CUR );/read bitmap bits data ( inverse the order of rows )char *ptemp = (char*)buffer + bmiheader.biWidth * (bmiheader.biHeight-1);for( int i=0; ibmiheader.biHeight; i+ ) if( fread( ptemp, bmiheader.biWidth, 1, fp ) 1 )return false;ptemp -= bm

25、iheader.biWidth;7. BMP图象的存储bool save_dib_file( const char *file, int width, int height, void *buffer )strcpy( fname, io_path ); strcat( fname, file );FILE *fp = fopen(file, wb ); if( !fp ) return false; /write bitmap file headerBITMAPFILEHEADER bmfheader;bmfheader.bfType = DIB_HEADER_MARKER;bmfheade

26、r.bfOffBits = sizeof(bmfheader) + sizeof(BITMAPINFOHEADER) + 256*sizeof(RGBQUAD);bmfheader.bfSize = bmfheader.bfOffBits + width*height;bmfheader.bfReserved1 = 0;bmfheader.bfReserved2 = 0;if( fwrite( (void*)&bmfheader, sizeof(bmfheader), 1, fp ) 1 )return false;/write bitmap info headerBITMAPINFO

27、HEADER bmiheader;memset( &bmiheader, 0, sizeof(bmiheader) );bmiheader.biSize = sizeof(bmiheader);bmiheader.biBitCount = 8;bmiheader.biWidth = width;bmiheader.biHeight = height;bmiheader.biPlanes = 1;bmiheader.biXPelsPerMeter = 2880;bmiheader.biYPelsPerMeter = 2880;bmiheader.biClrUsed = 256;if( f

28、write( (void*)&bmiheader, sizeof(bmiheader), 1, fp ) 1 )return false;/write the color palletteRGBQUAD col_pal256;for( n=0; n256; n+ )col_paln.rgbBlue = n;col_paln.rgbGreen = n;col_paln.rgbRed = n;if( fwrite( col_pal, 256*sizeof(RGBQUAD), 1, fp ) 1 )return false;/write bitmap bits data ( inverse the order of rows )char *ptemp = (char*)buffer + bmiheader.biWidth * (bmiheader.biHeight-1);for( n=0; nbmiheader.biHeight; n+ ) if( fwrite( ptemp, bmiheader.bi