數(shù)字圖像處理-第3章圖像變換與圖像編碼課件

1、第三章圖像變換與圖像編碼3.2 圖象變換 3.1 概述由于圖象數(shù)據(jù)量巨大，給存儲、處理和傳輸都帶來很多問題。如何采用對圖象的新的表示方法以縮小表示一幅圖象所需的數(shù)據(jù)量。圖象編碼要解決的主要問題就是盡最大可能對冗余性的代碼進(jìn)行壓縮。圖象變換是許多圖象處理和分析的技術(shù)基礎(chǔ),介紹一些常用的圖象變換和它們的性質(zhì)。在圖象處理和分析技術(shù)的發(fā)展中，付里葉變換曾經(jīng)起過并仍在起著重要的作用.3.2 Fourier變換1. 1-D Fourier變換 對一個(gè)連續(xù)函數(shù)f(x)等間隔采樣可得到一個(gè)離散序列。設(shè)采了N個(gè)樣,則序列可表示為f(0),f(1),f(2),.,f(N-1),借助這種表達(dá),可將離散傅里葉變換對定

2、義為:(x:離散實(shí)變量, u:離散頻率變量) 可以證明離散傅利葉變換對總是存在的。以下認(rèn)為f(x)是實(shí)函數(shù)，但一般F(u)是復(fù)函數(shù)： F(u)=R(u)+jI(u) (3.2-3) 其中R(u)和I(u)分別為F(u)的實(shí)部和虛部。寫成指數(shù)形式為： 5式幅度函數(shù)F(u)又稱f(x)的傅利葉頻譜，6式為相位角。頻譜的平方稱為f(x)的功率譜，記為P(u): (3.2-7) 1. 1-D Fourier變換 式（3.2-1）中的指數(shù)項(xiàng)可借歐拉公式寫為：每個(gè) u 值都確定所對應(yīng)的正弦和余弦對的頻率，所以成為頻率變量。2. 2-D Fourier變換若圖象以正方形網(wǎng)格采樣2-D付利葉變換.將式(3.2

3、-1)和(3.2-2)推廣: 1. 1-D Fourier變換 與1-D情況類似，2-D傅利葉變換的頻譜、相位角和功率譜定義： (3.2-11) (3.2-12)2. 2-D Fourier變換(3.2-13)例：2-D圖像及其傅頻譜的顯示例：灰度圖像及其傅頻譜的顯示djhw例：彩色圖像及其傅頻譜的顯示djhw3.3 快速Fourier變換（FFT） 1、快速Fourier變換的推導(dǎo)（分成奇數(shù)項(xiàng)和偶數(shù)項(xiàng)之和）3.3 快速Fourier變換（FFT）3.3 快速Fourier變換（FFT）2、FFT的設(shè)計(jì)思想 首先，將原函數(shù)分為奇數(shù)項(xiàng)和偶數(shù)項(xiàng)，通過不斷的一個(gè)奇數(shù)一個(gè)偶數(shù)的相加（減），最終得到需要

4、的結(jié)果。 也就是說FFT是將復(fù)雜的運(yùn)算變成兩個(gè)數(shù)相加（減）的簡單運(yùn)算的重復(fù)。歸納快速傅立葉變換的思想：（1）通過計(jì)算兩個(gè)單點(diǎn)的DFT，來計(jì)算兩個(gè)點(diǎn)的DFT，（2）通過計(jì)算兩個(gè)雙點(diǎn)的DFT，來計(jì)算四個(gè)點(diǎn)的DFT，以此類推（3）對于任何N=2m的DFT的計(jì)算，通過計(jì)算兩個(gè)N/2點(diǎn)的DFT，來計(jì)算N個(gè)點(diǎn)的DFT快速傅里葉變換(FFT)輸入數(shù)據(jù)的排序：對輸入數(shù)據(jù)的排序可根據(jù)一個(gè)簡單的位對換規(guī)則進(jìn)行. 如用x表示f(x)的1個(gè)自變量值，那么它排序后對應(yīng)的值可通過把x表示成二進(jìn)制數(shù)并對換各位得到. 例如 N=8, f(6)排序后為f(3),因?yàn)?110 而0113 把輸入數(shù)據(jù)進(jìn)行了重新排序，則輸出結(jié)果是正

5、確的次序。反之不把輸入數(shù)據(jù)進(jìn)行排序，則輸出結(jié)果需要重新排序才能得到正確的次序地址的排序：按位倒序規(guī)則地址的排序：按位倒序規(guī)則例如：N = 8計(jì)算順序及地址增量：3.3 快速Fourier變換（FFT）例：設(shè)對一個(gè)函數(shù)進(jìn)行快速Fourier變換，函數(shù)為：分成偶數(shù)、奇數(shù)為：例：3.3 快速Fourier變換（FFT）偶數(shù)區(qū)基數(shù)區(qū)3.3 快速Fourier變換（FFT）3.3 快速Fourier變換（FFT）3、二維快速Fourier變換 因?yàn)?維DFT可以看成是兩次的1維DFT變換，即： 所以二維快速Fourier變換實(shí)際上是對其進(jìn)行了2次的一維FFT變換。3.4 圖象壓縮的編碼方法按照解碼結(jié)果對

6、原圖的保真程度，圖象壓縮編碼的可分為兩大類：信息保存型：在壓縮和解壓中無信息損失。因此稱為無損壓縮，壓縮率在2到10之間。常用于圖象存檔。信息損失型：能獲取較高的壓縮率，但經(jīng)過解壓縮不能恢復(fù)原狀。因此稱為有損壓縮。用于信息損失可容許的場合。3.4 圖象壓縮的編碼方法信息損失編碼也可分為兩類：保真度編碼：允許失真條件下和一定保真度準(zhǔn)則下進(jìn)行圖象壓縮編碼。特征抽取編碼：只將圖象的特征信息進(jìn)行提取，并對其編碼。顯然這將大大壓縮圖象，是一種非信息保持編碼。3.4 圖象壓縮的編碼方法平均信息法。如不等長熵編碼中的哈夫曼（Haffman），香農(nóng)（Shannon）、弗農(nóng)（fano）編碼等。預(yù)測法：通常指線性

7、預(yù)測法，如插值脈沖調(diào)制DPCM和增量調(diào)制法，還有非線性預(yù)測法等。變換法：一般采用正交變換，如Founier變換， Walsh變換， Hadamard變換等。 3.4圖象壓縮的編碼方法其他編碼法。有內(nèi)插法中的的取樣和亞取樣法，如亞行、亞場等。還有針對靜止圖象或二值圖象的方塊編碼、游程編碼，輪廓編碼，跳過白色塊編碼等。3.5 熵編碼方法基本概念：1.圖象熵。2.平均碼字長度。3.編碼效率。1.圖象熵（Entropy） 平均信息量 設(shè)象素灰度集合為（w1, w2,wk, wM）其對應(yīng)的概率分別為P1, P2 Pk PM，按信息論中信源信息定義，數(shù)字圖象的熵H為：圖象熵表示各灰度級比特?cái)?shù)的統(tǒng)計(jì)平均值。

8、2.平均碼字長度設(shè)圖象為Bk為數(shù)字圖象第K個(gè)碼字Ck的長度（二進(jìn)制代數(shù)的位數(shù)），其相應(yīng)出現(xiàn)的概率為PM，則該數(shù)字圖象所賦予的碼字平均長度為：3.編碼效率其中H為圖象熵，R為平均碼字長度。3.5 熵編碼方法根據(jù)信源編碼理論：當(dāng) 時(shí)，可設(shè)計(jì)出某種無失真編碼的方法。如編碼結(jié)果RH時(shí)，這種編碼效率很低，占用bit多。R接近H時(shí)，這種狀態(tài)的編碼方法，稱為最佳編碼。當(dāng)RH時(shí)，必然丟失信息而引起圖象失真。熵編碼的目的就是要使編碼后的圖象平均比特?cái)?shù)R盡可能的接近圖象熵。3.6哈夫曼（Huffman）編碼哈夫曼編碼是根據(jù)可變長度最佳編碼定理，應(yīng)用哈夫曼算法而定的一種編碼方法。它的平均碼字長度在具有相同輸入概率集

9、合的前題下，比其他任何有一種唯一可譯碼都小。1）將輸入灰度級按出現(xiàn)的概率從大到小排序。2）將最小兩個(gè)概率相加，形成一個(gè)新的概率集合，再按1步的方法重排，如此重復(fù)進(jìn)行直到只有兩個(gè)概率為止。3）分配碼字。從最后一步開始反向進(jìn)行，對最后兩個(gè)概率分別賦“0”碼賦“1”碼。如此重復(fù)進(jìn)行，若概率不變使用原碼，若概率分裂為2個(gè)，其碼字前幾位依舊用原來的，碼字的最后一位碼元一個(gè)賦“1”，另一個(gè)賦“0”。1.編碼步驟2.示例2.示例2.示例2.示例2.示例3.6 哈夫曼（Huffman）編碼平均碼字長度:編碼效率：3.7 有限行程長度壓縮編碼1、RLE8有限行程長度壓縮法以兩個(gè)字節(jié)代表一串相同象素:第一字節(jié)代表

10、個(gè)數(shù)，第二字節(jié)代表數(shù)值。 例如：0X07，0XA8 代表7個(gè)A8識別碼識別碼由兩個(gè)字節(jié)構(gòu)成：第一字節(jié)必須為 0 x00第二字節(jié)代表1）00 一行圖像的結(jié)束2）01 一幅圖像的結(jié)束識別碼3）02XY 右移X點(diǎn)下移Y點(diǎn)4）N 有N個(gè)不同灰度值的像素例如：07,07,07,07,07,98,99,A4,A8 壓: 05,07,00,04,98,99,A4,A8,00 3.8 BMP位圖格式 該格式是當(dāng)今應(yīng)用比較廣泛的一種格式。 典型BMP應(yīng)用程序就是Windows的畫筆。 文件幾乎不壓縮，占用磁盤空間較大，它 的顏色存儲格式有1位、4位、8位及24位， 缺點(diǎn)是該格式文件比較大。1. BMP文件格式B

11、MP文件組成 一個(gè)文件頭 一個(gè)位圖信息數(shù)據(jù) 一個(gè)調(diào)色板數(shù)據(jù) 一個(gè)圖像數(shù)據(jù)BMP文件頭、位圖信息數(shù)據(jù)調(diào)色板數(shù)據(jù) 圖象數(shù)據(jù)2.文件頭數(shù)據(jù)結(jié)構(gòu)BITMAPFILEHEADERname type remarkoffset(hex)文件類型 WORD 必須是BM 0文件大小 DWORD byte數(shù) 2reserved1 WORD must be 0 6reserved2 WORD must be 0 8data offset DWORD點(diǎn)陣位圖數(shù)據(jù)偏移 0a3.位圖信息數(shù)據(jù)BITMAPINFOHEADER name remark offsetbiSize 本結(jié)構(gòu)所占用的字節(jié)數(shù)（一般0 x28) 0ebi

12、Width 圖像寬度（以像素為單位） 12biHeight 圖像高度（以像素為單位）16biPlanes 位平面數(shù) (must be 1) 1abiBitCount 每像素位數(shù)(1-雙色,4,8 or 24) 1cbiCompression 壓縮方式(BI_RGB=0, 未壓 1e BI_RLE8=1,每像素8位,行程壓縮編碼 BI_RLE4=2,每像素4位,行程壓縮編碼） biSizeImage 圖像的大?。ㄗ止?jié)數(shù),一般填0) 22 biXPelsMeter 位圖水平分辨率,每毫米像素?cái)?shù) （一般B12h） 26 biYPelsMeter 位圖垂直分辨率,每毫米像素?cái)?shù) （一般B12h） 2a

13、biClrUsed 位圖實(shí)際使用的顏色表中的顏色數(shù)（一般填0)2e biClrImportant 位圖顯示過程中重要顏色數(shù)（填0所有重要） 324.顏色表RGBQUADrgbBlue BYTErgbGreen BYTErgbRed BYTErgbReserved BYTE （must be 0)顏色表RGBQUAD長度由biByteCount （每像素位數(shù)）定biByteCount 顏色數(shù) 1 2 4 16 825624 167772165.用VC對BMP圖象進(jìn)行讀寫操作VC有關(guān)BMP圖象操作的函數(shù)和數(shù)據(jù)結(jié)構(gòu)BITMAPFILEHEADER 文件頭BITMAPINFOHEADER 位圖信息數(shù)據(jù)

14、RGBQUAD 顏色表SetDIBitsToDevice（）顯示圖象 請參考MSDN。1)BITMAPFILEHEADER文件頭typedef struct tagBITMAPFILEHEADER WORD bfType; DWORD bfSize; 文件大小 WORD bfReserved1; WORD bfReserved2; DWORD bfOffBits; 位圖數(shù)據(jù)偏移 BITMAPFILEHEADER, *PBITMAPFILEHEADER;2)BITMAPINFOHEADER位圖信息數(shù)據(jù)typedef struct tagBITMAPINFOHEADER DWORD biSize;

15、本結(jié)構(gòu)所占用的字節(jié)數(shù)（一般0 x28) LONG biWidth;圖像寬度（以像素為單位） LONG biHeight;圖像高度（以像素為單位） WORD biPlanes;位平面數(shù) (must be 1) WORD biBitCount; 每像素位數(shù)(1雙色,4,8 or 24) DWORD biCompression; 壓縮方式 DWORD biSizeImage; 圖像的大小 LONG biXPelsPerMeter; 位圖水平分辨率,每毫米像素?cái)?shù) LONG biYPelsPerMeter; DWORD biClrUsed; 位圖實(shí)際使用的顏色數(shù)（一般填0) DWORD biClrImp

16、ortant;重要顏色數(shù)（填0：所有重要） BITMAPINFOHEADER, *PBITMAPINFOHEADER; 3)RGBQUADtypedef struct tagRGBQUAD BYTE rgbBlue; BYTE rgbGreen; BYTE rgbRed; BYTE rgbReserved; RGBQUAD;4) SetDIBitsToDevice函數(shù)顯示圖象int SetDIBitsToDevice( HDC hdc, / handle to DC int XDest, / x-coord of destination upper-left corner int YDest,

17、 / 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 corner int YSrc, / y-coord of source lower-left corner UINT uStartScan, / first scan line in array UINT cScanLines, / number of scan

18、lines CONST VOID *lpvBits, / array of DIB bits CONST BITMAPINFO *lpbmi, / bitmap information UINT fuColorUse / RGB or palette indexes);6. BMP文件的讀取#define DIB_HEADER_MARKER (WORD)(M8)|B)bool read_dib_file( const char *file, int width, int height, void *buffer )FILE *fp = fopen(file, rb ); if( !fp ) r

19、eturn false; /read bitmap file headerBITMAPFILEHEADER bmfHeader;if( fread( (void*)&bmfHeader, sizeof(bmfHeader), 1, fp ) 1 )return false;if( bmfHeader.bfType != DIB_HEADER_MARKER )return false;/read bitmap info headerBITMAPINFOHEADER bmiheader;if( fread( (void*)&bmiheader, sizeof(bmiheader), 1, fp )

20、 1 )return false; if( bmiheader.biBitCount != 8 ) return false;if( bmiheader.biWidth != width ) return false;if( bmiheader.biHeight != height ) return false;/skip the color pallettefseek( fp, 256*sizeof(RGBQUAD), SEEK_CUR );/read bitmap bits data ( inverse the order of rows )char *ptemp = (char*)buf

21、fer + bmiheader.biWidth * (bmiheader.biHeight-1);for( int i=0; ibmiheader.biHeight; i+ ) if( fread( ptemp, bmiheader.biWidth, 1, fp ) 1 )return false;ptemp -= bmiheader.biWidth;7. BMP圖象的存儲bool save_dib_file( const char *file, int width, int height, void *buffer )strcpy( fname, io_path ); strcat( fna

22、me, file );FILE *fp = fopen(file, wb ); if( !fp ) return false; /write bitmap file headerBITMAPFILEHEADER bmfheader;bmfheader.bfType = DIB_HEADER_MARKER;bmfheader.bfOffBits = sizeof(bmfheader) + sizeof(BITMAPINFOHEADER) + 256*sizeof(RGBQUAD);bmfheader.bfSize = bmfheader.bfOffBits + width*height;bmfh

23、eader.bfReserved1 = 0;bmfheader.bfReserved2 = 0;if( fwrite( (void*)&bmfheader, sizeof(bmfheader), 1, fp ) 1 )return false;/write bitmap info headerBITMAPINFOHEADER bmiheader;memset( &bmiheader, 0, sizeof(bmiheader) );bmiheader.biSize = sizeof(bmiheader);bmiheader.biBitCount = 8;bmiheader.biWidth = w

24、idth;bmiheader.biHeight = height;bmiheader.biPlanes = 1;bmiheader.biXPelsPerMeter = 2880;bmiheader.biYPelsPerMeter = 2880;bmiheader.biClrUsed = 256;if( fwrite( (void*)&bmiheader, sizeof(bmiheader), 1, fp ) 1 )return false;/write the color palletteRGBQUAD col_pal256;for( n=0; n256; n+ )col_paln.rgbBl

25、ue = 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.biWidth, 1, fp ) 1 )return false;ptemp -= bmiheader.biWidth;fclose( fp );return true;8. BMP圖象的顯示HDC hdc = Ge