數(shù)字圖像處理實驗報告 (圖像編碼)

第第頁實驗三圖像編碼一、實驗內(nèi)容:用Matlab語言、C語言或C++語言編制圖像處理軟件，對某幅圖像進行時域和頻域的編碼壓縮。二、實驗?zāi)康暮鸵饬x:1.掌握哈夫曼編碼、香農(nóng)-范諾編碼、行程編碼2．了解圖像壓縮國際標(biāo)準(zhǔn)三、實驗原理與主要框架:3.1實驗所用編程環(huán)境:VisualC++6.0（簡稱VC）3.2實驗處理的對象:256色的BMP(BITMAP)格式圖像BMP(BITMAP)位圖的文件結(jié)構(gòu):(如圖3.1)圖3.1位圖的文件結(jié)構(gòu)具體組成圖:3.3數(shù)字圖像基本概念數(shù)字圖像是連續(xù)圖像的一種近似表示，通常用由采樣點的值所組成的矩陣來表示：每一個采樣單元叫做一個像素(pixel)，上式(2.1)中，M、N分別為數(shù)字圖像在橫(行)、縱(列)方向上的像素總數(shù)。在計算機內(nèi)通常用二維數(shù)組來表示數(shù)字圖像的矩陣，把像素按不同的方式進行組織或存儲，就得到不同的圖像格式，把圖像數(shù)據(jù)存成文件就得到圖像文件。圖像文件按其數(shù)字圖像格式的不同一般具有不同的擴展名。最常見的圖像格式是位圖格式，其文件名以BMP為擴展名。圖像數(shù)字化的精度包括兩部分，即分辨率和顏色深度。分辨率指圖像數(shù)字化的空間精細(xì)度，有顯示分辨率和圖像分辨率兩種。數(shù)字圖像的顏色深度表示每一像素的顏色值所占的二進制位數(shù)。顏色深度越大則能表示的顏色數(shù)目越多。顏色深度的不同，就產(chǎn)生不同種類的圖像文件，在計算機中常使用圖像文件的類型有單色圖像、灰度圖像、偽彩色圖像和24位真彩色圖像。它們之間的關(guān)系取決于數(shù)字圖像采用的顏色表示法。常用的顏色表示法有RGB、CMYK、HSL和YUV等。數(shù)字圖像的數(shù)據(jù)容量非常龐大，如以24位真彩色表示像素為640*480的數(shù)字圖像，所需要的數(shù)據(jù)量為900KB，所以需要對數(shù)字圖像進行數(shù)據(jù)壓縮。數(shù)據(jù)壓縮包括數(shù)據(jù)壓縮編碼和壓縮數(shù)據(jù)解碼兩個過程。圖像壓縮的基本原則包括：（1）編碼重復(fù)壓縮：按照編碼重復(fù)的概率大小做壓縮編碼，壓縮重復(fù)概率大的編碼，可以節(jié)省一些存儲空間。（2）像素間重復(fù)壓縮：前后像素間存在的某種程度的相關(guān)，如存在相同的背景圖像等，簡化編碼以節(jié)省空間。（3）視覺重復(fù)壓縮：由于入眼的生理構(gòu)造，就算在像素之間少了幾個像素，眼睛也看不出來。但是，只是在某些情況中才可以允許這種失真性較大的應(yīng)用。主要的數(shù)字圖像壓縮標(biāo)準(zhǔn)是JPEG(JointPictureExpertGroup)標(biāo)準(zhǔn)。數(shù)字圖像的采集設(shè)備主要有掃描儀、數(shù)字相機和圖像采集卡等。通過對數(shù)字圖像進行一定的處理，即圖像處理，可在一定程度上改善圖像的分辨質(zhì)量和形成特殊的視覺效果。數(shù)字圖像處理由數(shù)字圖像處理系統(tǒng)完成，其結(jié)構(gòu)主要包括圖像采集系統(tǒng)、計算機圖像處理系統(tǒng)和圖像輸出系統(tǒng)三部分。3.4圖像的編碼圖像的編碼包括圖像的離哈夫曼編碼、香農(nóng)-范諾編碼、行程編碼，基本框架(如圖3.2)和圖像編碼菜單設(shè)計圖(如圖3.3)如下：圖3.2圖像編碼流程圖圖3.3bmp圖像編碼菜單設(shè)計圖數(shù)字圖像編碼技術(shù):4.1哈夫曼編碼根據(jù)信息論中信源編碼理論，當(dāng)平均碼長R大于等于圖像熵H時，總可設(shè)計出一種無失真編碼。當(dāng)平均碼長大于圖像熵時，表明該編碼方法效率很低；當(dāng)平均碼長等于或很接近于（但不大于）圖像熵時，稱此編碼方法為最佳編碼，此時不會引起圖像失真；當(dāng)平均碼長小于圖像熵時，壓縮比較高，但會引起圖像失真。在變長編碼中，如果碼字長度嚴(yán)格按照對應(yīng)符號出現(xiàn)的概率大小逆序排列，但其平均碼字長度為最小，這就是變長最佳編碼定理。變長最佳編碼定理是哈夫曼編碼的理論基礎(chǔ)。4.1.1哈夫曼編碼基本原理哈夫曼（Huffman）編碼是一種常用的壓縮編碼方法，是Huffman于1952年為壓縮文本文件建立的，是一種效率比較高的變長無失真信源編碼方法。它的基本原理是頻繁使用的數(shù)據(jù)用較短的代碼代替，較少使用的數(shù)據(jù)用較長的代碼代替，每個數(shù)據(jù)的代碼各不相同。由于哈夫曼編碼是以信源概率分布為基礎(chǔ)的，但一般情況下無法事先知道信源的概率分布，因而通常采用對大量數(shù)據(jù)進行統(tǒng)計后得到的近似分布來代替，這樣會導(dǎo)致實際應(yīng)用時哈夫曼編碼無法達到最佳性能。4.1.2哈夫曼編碼步驟下面來介紹哈夫曼編碼方法：（1）將輸入的符號（圖像中的灰度級）按出現(xiàn)概率由小到大排列，即（2）將最小的兩個相加，形成一個新的概率集合（此時壓縮了一個），再按（1）重復(fù)直到只剩下兩個概率為止。下圖給出了一個實際信源符號的縮減過程。表3.1哈夫曼編碼中的信源符號縮減過程原始信源信源符號縮減步驟符號概率123450.020.040.060.060.060.120.120.120.120.160.160.160.160.20.240.20.20.20.240.360.40.40.40.40.40.40.6從最后的兩概率值開始逐步向前給符號分配碼字長，每一步有兩個分支，以相同的規(guī)則各賦予一個二進制碼。編碼過程如表3.2所示。表3.2哈夫曼編碼中的碼字分配過程原始信源按信源符號縮減逆向賦碼字符號概率碼字123450.02011110.04011100.0601110.0601100.0601100.120110.120100.120100.120100.160010.160010.160010.160010.20000.24010.20000.20000.20000.24010.36000.410.410.410.410.410.410.60同時也可以計算與編碼性能相關(guān)的幾個參數(shù)：（1）信源的熵(3.1)（2）哈夫曼編碼的平均碼字長(3.2)（3）哈夫曼編碼的效率(3.3)4.1.3哈夫曼編碼特點用哈夫曼編碼方法壓縮圖像數(shù)據(jù)，對于不同的圖像，其壓縮效果和壓縮效率是不同的。當(dāng)各符號出現(xiàn)概率不同時，編碼效率較高。而當(dāng)各符號出現(xiàn)的概率相等時，實際上此時的哈夫曼編碼就已退化成等長編碼，編碼效率較低。對灰度圖像的無損壓縮算法采用哈夫曼編碼，即對原圖像實行直接的編碼，該算法在恢復(fù)圖像的質(zhì)量上是極好的。但由于該算法對原圖像直接使用不等長編碼壓縮，但沒有處理圖像各個像素間的相關(guān)性，從而使壓縮效率并不是很高,因此必須結(jié)合其它的壓縮方法同時使用以達到更高的壓縮比。4.2香農(nóng)-范諾編碼香農(nóng)-范諾(Shannon-Fannon)編碼也是一種常見的可變字長編碼。與哈夫曼編碼相似，當(dāng)信源符號出現(xiàn)時的概率正好為2-i時，采用香農(nóng)-范諾編碼同樣能達到100%的編碼效果。4.2.1香農(nóng)-范諾編碼基本原理香農(nóng)-范諾編碼的理論基礎(chǔ)是符號的碼字長度Ni完全由該符號出現(xiàn)的概率來決定，即-logDPiNi-logDPi+1，式中D為編碼所用的數(shù)制。4.2.2香農(nóng)-范諾編碼步驟（1）將信源符號Xi按其出現(xiàn)概率Pi從小到大排序：(3.3)（2）將X分成兩個子集(3.4)并且保證成立或差不多成立。在本圖像壓縮編碼設(shè)計中是按前一個子集大于等于總和的一半來計算的。（3）給兩個子集賦不同的碼元值，如X1中的符號賦“1”，X2中的符號就賦“0”。（4）重復(fù)（2）、（3），即對每個子集再一分為二，并分別賦予不同碼元值，直到每個子集僅含一個信源符號為止。下面通過哈夫曼編碼中用過的同樣例子，說明上述編碼過程。將信源(3.5)記為：(3.6)則其編碼過程如表3.3所示。表3.3香農(nóng)-范諾編碼過程碼字符號概率111111X10.02111111111110X20.04011110X30.0601110X40.120110X50.16010X60.200X70.404.2.3香農(nóng)-范諾編碼特點采用以上算法用VC具體實現(xiàn)對某一圖像進行編碼，同時對編碼的有關(guān)評估參數(shù)如圖像熵值、平均碼長、編碼效率進行計算。為了便于編碼的顯示設(shè)計了編碼顯示對話框，在其中進行編碼運算并實現(xiàn)碼字的顯示。4.3行程編碼行程編碼又稱行程長度編碼(RunLengthEncoding,RLE)，是一種熵編碼，其編碼原理相當(dāng)簡單，即將具有相同值的連續(xù)串用其串長和一個代表值來代替，該連續(xù)串就稱為行程，串長稱為行程長度。RLE壓縮編碼尤其適用于計算機生成的圖形圖像，對減少存儲容量很有效果。4.3.1行程編碼基本原理行程編碼分為定長和不定長編碼兩種。定長編碼是指編碼的行程長度所用的二進制位數(shù)固定，而變長形成編碼是指對不同范圍的行程長度使用不同位數(shù)的二進制進行編碼。使用變長行程編碼需要增加標(biāo)志位來表明所使用的二進制位數(shù)。為了達到較好的壓縮效果，一般不單獨采用行程編碼，而是和其他編碼方法結(jié)合使用。例如，在JPEG中，就綜合使用了行程編碼、DCT、量化編碼以及哈夫曼編碼，先對圖像作分塊處理，再對這些分塊圖像進行離散余弦變換(DCT)，對變換后的頻域數(shù)據(jù)進行量化并作Z字形掃描，接著對掃描結(jié)果作行程編碼，對行程編碼后的結(jié)果在作哈哈夫曼編碼。4.3.2行程編碼步驟PCX文件分為文件頭和圖像壓縮數(shù)據(jù)兩個部分。如果是256色圖像，則還有一個256色調(diào)色板存于文件尾部。文件頭全長128字節(jié)，包含了圖像的大小和顏色以及PCX文件的版本標(biāo)志等信息。其中頭信息的具體結(jié)構(gòu)為：typedefstruct{charmanufacturer;charversion;charencoding;charbits_per_pixel;WORDxmin,ymin;WORDxmax,ymax;WORDhres;WORDvres;charpalette[48];charreserved;charcolour_planes;WORDbytes_per_line;WORDpalette_type;charfiller[58]; }PCXHEAD;其中值得注意的是以下幾個數(shù)據(jù)：manufacturer為PCX文件的標(biāo)志，必須為0x0a；xmin為最小的x坐標(biāo)，xmax為最大的x坐標(biāo)，所以圖像的寬度為xmax-xmin+1,同樣圖像的高度為ymax-ymin+1；bits_per_pixel為每個編碼行所占的字節(jié)數(shù)。圖像壓縮數(shù)據(jù)緊跟在文件頭后。如果沒有使用調(diào)色板，那么圖像壓縮數(shù)據(jù)存儲的是實際像素值；否則，存儲的是調(diào)色板的索引值。當(dāng)壓縮數(shù)據(jù)是實際的像素值時，它們按顏色平面和掃描行存儲，即每行先存儲所有R分量，再存儲所有G分量，最后存儲所有B分量，一行數(shù)據(jù)存儲完后，接著存儲下一行數(shù)據(jù)。如果使用了調(diào)色板，則不會分解為單獨的顏色平面存儲。下面以256色的PCX文件為例，說明PCX文件中的行程編碼。256色PCX文件中，每個像素占一個字節(jié)，壓縮數(shù)據(jù)以字節(jié)為單位逐行進行編碼，每行填充到偶數(shù)字節(jié)。PCX文件規(guī)定編碼時的最大行程長度為63，如果行程長度大于63，則必須分多次存儲。對于長度大于1的行程，編碼時先存入其行程長度(長度L加上192即0xC0)，再存入該行程的代碼值，行程長度和行程的代表值分別占一個字節(jié)。對于長度為1的行程，即單個像素，如果該像素的值小于或等于0xC0，則編碼時直接存入該像素值，而不存儲長度信息；否則，先存入0xC1，再存入該像素值，這樣做的目的是為了避免該像素值被誤認(rèn)為長度信息。例如，連續(xù)100個灰度值為0x80的像素，其編碼（以十六進制表示）應(yīng)為FF802580。上面的編碼中出現(xiàn)的FF的長度信息是由63與0xC0相加所得。4.3.3行程編碼特點行程編碼比較適合于二值圖像（即圖像的各像素只有兩個值——黑或者白）的編碼，一般用于量化后出現(xiàn)大量零系數(shù)連續(xù)的場合，用行程來表示連零碼。如果圖像是由很多塊顏色或灰度相同的大面積區(qū)域組成的，那么采用行程編碼可以達到很高的壓縮比。如果圖像中的數(shù)據(jù)非常分散，則行程編碼不但不能壓縮數(shù)據(jù)，反而會增加圖像文件的大小。極端情況如果圖像中每兩個相鄰點的顏色都不同，用這種算法不但不能壓縮，反而數(shù)據(jù)量增加一倍。所以現(xiàn)在單純采用行程編碼的壓縮算法用得并不多，PCX文件算是其中的一種。五、實驗內(nèi)容:5.1哈夫曼編碼5.1.1哈夫曼編碼算法實現(xiàn)資源文件HuffmanCoding.cpp中主要介紹哈夫曼編碼的算法，首先要從視圖類CDImageProcessView中的OnHuffmancoding函數(shù)中得到0-255各灰度值出現(xiàn)的概率，在下面的算法中要基于這個概率值進行哈夫曼編碼。首先要對這個概率值進行從小到大的冒泡排序，然后從概率大于0處開始編碼，灰度值較小的編為1，灰度值較大的編為0，再將最小的兩個灰度值相加，將加后的值與其他灰度值放在一起重新按從小到大排序，重復(fù)以上的步驟直到概率值相加為1。然后計算該圖像的熵值、平均碼字長度及編碼效率。具體算法如下代碼所示：BOOLCHuffmanCoding::OnInitDialog(){//調(diào)用默認(rèn)的對話框初始化函數(shù) CDialog::OnInitDialog(); int i; //循環(huán)變量 int j; //循環(huán)變量 int k; //循環(huán)變量//圖像灰度出現(xiàn)概率中間結(jié)果的數(shù)組 double*temp; //數(shù)組用來存放灰度值和其位置之間的對應(yīng)關(guān)系 int * turn; //分配內(nèi)存 m_strCode=newCString[graygrade]; //分配內(nèi)存 turn=newint[graygrade]; //分配內(nèi)存 temp=newdouble[graygrade]; for(i=0;i<graygrade;i++) {//將grayfreq的值傳給temp temp[i]=grayfreq[i];//記錄灰度位置 turn[i]=i; } //中間變量 doublete; //用冒泡法對進行灰度值出現(xiàn)的概率排序從小到大 //同時改變灰度值位置的映射關(guān)系 for(j=0;j<graygrade-1;j++) {for(i=0;i<graygrade-j-1;i++) {//如果前面的值大于后面的值 if(temp[i]>temp[i+1]) {//二者的值互換te=temp[i]; temp[i]=temp[i+1]; temp[i+1]=te;//將i和i+1灰度的位置值互換 for(k=0;k<graygrade;k++) { if(turn[k]==i) turn[k]=i+1; elseif(turn[k]==i+1) turn[k]=i; } } } } //從灰度概率大于0處開始編碼 for(i=0;i<graygrade-1;i++) {if(temp[i]>0) break; } for(;i<graygrade-1;i++) {//更新m_strCode for(k=0;k<graygrade;k++) {//灰度值是否i if(turn[k]==i){//灰度值較小的碼字加1m_strCode[k]="1"+m_strCode[k];} elseif(turn[k]==i+1){//灰度值較大的碼字加0 m_strCode[k]="0"+m_strCode[k];} } //概率最小的兩個概率相加，保存在temp[i+1]中 temp[i+1]=temp[i]+temp[i+1];//改變映射關(guān)系 for(k=0;k<graygrade;k++) {//將位置為i的灰度值i改為灰度值i+1if(turn[k]==i) {turn[k]=i+1;} }//重新排序從i＋1開始 for(j=i+1;j<graygrade-1;j++) { if(temp[j]>temp[j+1]) { te=temp[j];//互換 temp[j]=temp[j+1]; temp[j+1]=te;//將i和i+1灰度的位置值互換 for(k=0;k<graygrade;k++) { if(turn[k]==j) turn[k]=j+1; elseif(turn[k]==j+1) turn[k]=j; } } else break;//退出循環(huán) } }//計算圖像熵 for(i=0;i<graygrade;i++) { if(grayfreq[i]>0){//計算圖像熵 m_shang-=grayfreq[i]*log(grayfreq[i])/log(2.0);} } //計算平均碼字長度 for(i=0;i<graygrade;i++) { m_length+=grayfreq[i]*m_strCode[i].GetLength();//累加 }//計算編碼效率 m_effection=m_shang/m_length;//保存變動 UpdateData(FALSE);//字符串變量，列表項目的顯示 CString listname;//控件CodingList的ITEM LV_ITEMcodingItem;//保存控件ListCtrl中添加的ITEM編號 int nItem2View; //設(shè)置CListCtrl控件樣式 m_codinglist.ModifyStyle(LVS_TYPEMASK,LVS_REPORT); //給List控件添加Header m_codinglist.InsertColumn(0,"像素灰度",LVCFMT_LEFT,70,0); m_codinglist.InsertColumn(1,"灰度概率",LVCFMT_LEFT,70,0); m_codinglist.InsertColumn(2,"編碼碼字",LVCFMT_LEFT,90,1); m_codinglist.InsertColumn(3,"碼字長度",LVCFMT_LEFT,60,2);//設(shè)置樣式為文本 codingItem.mask=LVIF_TEXT;//添加顯示 for(i=0;i<graygrade;i++) {//第一列顯示 codingItem.iItem=m_codinglist.GetItemCount(); listname.Format("%u",i); codingItem.iSubItem=0;//顯示像素灰度 codingItem.pszText=(LPTSTR)(LPCTSTR)listname; nItem2View=m_codinglist.InsertItem(&codingItem); codingItem.iItem=nItem2View; //第二列顯示 codingItem.iSubItem=1; listname.Format("%f",grayfreq[i]); codingItem.pszText=(LPTSTR)(LPCTSTR)listname; m_codinglist.SetItem(&codingItem); //第三列顯示 codingItem.iSubItem=2; codingItem.pszText=(LPTSTR)(LPCTSTR)m_strCode[i]; m_codinglist.SetItem(&codingItem); //第四列顯示 codingItem.iSubItem=3; listname.Format("%u",m_strCode[i].GetLength()); codingItem.pszText=(LPTSTR)(LPCTSTR)listname; m_codinglist.SetItem(&codingItem); } deleteturn;//內(nèi)存釋放 deletetemp; returnTRUE;//返回TRUE}5.1.2視圖類OnHuffmancoding()函數(shù)此函數(shù)是用來統(tǒng)計各灰度值出現(xiàn)的概率，并以對話框的形式顯示通過算法計算出的結(jié)論值。首先是通過CDib類中的GetBits()函數(shù)來獲取圖像像素的起始位置，因為本程序只支持256色的位圖圖像，所以要進行判斷(如果不是256色的位圖圖像則彈出對話框提示“只支持256色位圖圖像”)。然后通過CDib類中的GetWidth()和GetHeight()函數(shù)返回圖像的寬度和高度，用于計算圖像的像素總和及控制循環(huán)邊界。用兩個for的嵌套循環(huán)對圖像的進行逐行掃描，以統(tǒng)計出每個灰度值出現(xiàn)的次數(shù)，再除以像素總和就可以得到每個灰度值的概率，此概率要參與到哈夫曼編碼算法中。最后要顯示出哈夫曼編碼的結(jié)果，本程序是通過對話框來顯示的。voidCDImageProcessView::OnHuffmancoding(){//獲取文檔 CDImageProcessDoc*pDoc=GetDocument();//指向源圖像的指針 unsignedchar* lpSrc; //指向DIB的指針 LPSTRlpDIB; //指向DIB象素指針 LPSTRlpDIBBits;//圖像灰度等級數(shù) intgraygrade;//鎖定DIB lpDIB=(LPSTR)::GlobalLock((HGLOBAL)pDoc->GetHObject());//找到DIB圖像象素起始位置 lpDIBBits=pDoc->m_dib.GetBits(lpDIB); //判斷是否是8-bpp位圖 if(pDoc->m_dib.GetColorNum(lpDIB)!=256) {//提示用戶 MessageBox("目前只支持256色位圖！","系統(tǒng)提示", MB_ICONINFORMATION|MB_OK); //解除鎖定 ::GlobalUnlock((HGLOBAL)pDoc->GetHObject()); return;//返回 }//灰度等級數(shù)為256 graygrade=pDoc->m_dib.GetColorNum(lpDIB);//各灰度等級出現(xiàn)的概率 double*grayfreq;//圖像寬度 intwidth;//圖像高度 intheight; width=pDoc->m_dib.GetWidth(lpDIB); height=pDoc->m_dib.GetHeight(lpDIB);//更改光標(biāo)形狀 BeginWaitCursor();//分配內(nèi)存 grayfreq=newdouble[graygrade];//像素數(shù)目 intgraySum; inti; intj; graySum=width*height; //計算圖象象素總數(shù) for(i=0;i<graygrade;i++) {//賦零值grayfreq[i]=0.0; }//計算各個灰度值的計數(shù) for(i=0;i<height;i++) { for(j=0;j<width;j++) {//指向圖象指針 lpSrc=(unsignedchar*)lpDIBBits+width*i+j;//相應(yīng)的灰度計數(shù)加1 grayfreq[*(lpSrc)]=grayfreq[*(lpSrc)]+1; } }//計算各個灰度值出現(xiàn)的概率 for(i=0;i<graygrade;i++) { grayfreq[i]=grayfreq[i]/(double)graySum; } //構(gòu)建霍夫曼編碼的碼表，并用對話框顯示霍夫曼碼表 CHuffmanCodingcoding; //創(chuàng)建對話框 coding.grayfreq=grayfreq;//初始化變量值 coding.graygrade=graygrade; coding.DoModal(); //顯示對話框 EndWaitCursor(); //恢復(fù)光標(biāo)5.2香農(nóng)-范諾編碼5.2.1香農(nóng)-范諾編碼算法實現(xiàn)資源文件ShannonCoding.cpp是香農(nóng)-范諾編碼的算法程序。與哈夫曼算法相似地從視圖類中得到每個灰度值出現(xiàn)的概率，針對這個概率進行編碼。首先用冒泡法從小到大對概率進行排序，從概率大于0處開始進行編碼，對概率區(qū)間進行分割，然后對每個灰度值對應(yīng)的編碼數(shù)組進行追加字符，初始時追加為1，當(dāng)超出概率總和的一半時，追加的字符改為0，接著繼續(xù)對上半部分的區(qū)間進行分割，此時概率的總和就改為上半部分的概率總和了，重復(fù)上述操作，完成整幅圖像的編碼。具體代碼如下所示：BOOLCShannonCoding::OnInitDialog(){//調(diào)用默認(rèn)得OnInitDialog()函數(shù) CDialog::OnInitDialog();//字符串變量 CString str; str="1"; int i; int j; //圖像灰度出現(xiàn)概率中間結(jié)果的數(shù)組 double* temp;//數(shù)組用來存放灰度值和其位置之間 int * turn; temp=newdouble[graygrade]; //數(shù)組用來存放灰度值和其位置之間的映射 turn=newint[graygrade];//臨時變量 int temp2;//當(dāng)前編碼區(qū)間的概率和 double effectcum;//初始的概率和為1.0 effectcum=1.0; //已經(jīng)編碼灰度值概率的統(tǒng)計和 double dSum;//初始化為0 dSum=0; //已編碼灰度值 int lCount=0; //起始位置 int lBegin;//指示編碼是否已經(jīng)完成一段 BOOL *bFinished; bFinished=newBOOL[graygrade];//分配內(nèi)存 m_strCode=newCString[graygrade]; for(i=0;i<graygrade;i++) { //初始化為FALSE bFinished[i]=FALSE; //將概率賦值temp數(shù)組 temp[i]=grayfreq[i];//按灰度值大小順序排列 turn[i]=i; }//中間變量 double te;//用冒泡法對進行灰度值出現(xiàn)的概率排序 //同時改變灰度值位置的映射關(guān)系 for(j=0;j<graygrade-1;j++) { for(i=0;i<graygrade-j-1;i++) { if(temp[i]>temp[i+1]) {//互換 te=temp[i]; temp[i]=temp[i+1]; temp[i+1]=te; //將i和i+1灰度的位置值互換 temp2=turn[i]; turn[i]=turn[i+1]; turn[i+1]=temp2; } } } //計算香農(nóng)－弗諾編碼表，從概率大于0處開始編碼 for(lBegin=0;lBegin<graygrade-1;lBegin++) { if(temp[lBegin]>0) {break; } } //開始編碼 while(lCount<graygrade) {//從概率大于零的灰度值開始編碼 lCount=lBegin; //對區(qū)間進行分割，對每個區(qū)間的灰度值編碼 for(i=lBegin;i<graygrade;i++) {//判斷是否編碼完成 if(bFinished[i]==FALSE) {//增加當(dāng)前編碼區(qū)間的概率綜合 dSum+=temp[i];//判斷是否超出總和的一半 if(dSum>effectcum/2.0) {//超出，追加的字符改為0 str="0"; }//追加字符 m_strCode[turn[i]]=m_strCode[turn[i]]+str;//判斷是否編碼完一段 if(dSum==effectcum) {//完成一部分編碼，重新計算effectcum dSum=0;//初始化dSum為0//判斷是不是對所有灰度值已經(jīng)編碼一遍 if(i==graygrade-1) {j=lBegin;} else {j=i+1;} temp2=j;//保存j值 str=m_strCode[turn[j]]; //計算下一編碼區(qū)間的概率總和 effectcum=0; for(;j<graygrade;j++) {//判斷是否是同一段編碼 if((m_strCode[turn[j]].Right(1)!=str.Right(1)) ||(m_strCode[turn[j]].GetLength()!=str.GetLength())) break;//當(dāng)前區(qū)間的概率總和增加 effectcum+=temp[j]; }//碼字增加值為1 str="1"; //判斷該段編碼已經(jīng)完成 if(temp2+1==j) { bFinished[temp2]=TRUE;} } } else {//開始下一輪編碼 lCount++;//重新賦dSum為0 dSum=0;//判斷是不是對所有灰度值已經(jīng)編碼一遍 if(i==graygrade-1) { j=lBegin;} else {j=i+1;} temp2=j;//保存j值 str=m_strCode[turn[j]]; //計算下一編碼區(qū)間的概率總和 effectcum=0; for(;j<graygrade;j++) {//判斷是否是同一段編碼 if((m_strCode[turn[j]].Right(1)!=str.Right(1)) ||(m_strCode[turn[j]].GetLength()!=str.GetLength())) {//退出循環(huán)break; } effectcum+=temp[j];//累加 } str="1";//判斷該段編碼已經(jīng)完成 if(temp2+1==j) bFinished[temp2]=TRUE; } } }//計算圖像熵 for(i=0;i<graygrade;i++) {//判斷概率是否大于0 if(grayfreq[i]>0) {//計算圖像熵 m_shang-=grayfreq[i]*log(grayfreq[i])/log(2.0); } }//計算平均碼字長度 for(i=0;i<graygrade;i++) {//累加 m_length+=grayfreq[i]*m_strCode[i].GetLength(); }//計算編碼效率 m_effect=m_shang/m_length; //保存變動 UpdateData(FALSE); //輸出編碼結(jié)果 //字符串變量，列表項目的顯示 CString listname;//控件ListCtrl的ITEM LV_ITEMcodingItem;//保存控件ListCtrl中添加的ITEM編號 int nItem2View; //設(shè)置CListCtrl控件樣式 m_codinglist.ModifyStyle(LVS_TYPEMASK,LVS_REPORT); //給List控件添加Header m_codinglist.InsertColumn(0,"像素灰度",LVCFMT_LEFT,70,0); m_codinglist.InsertColumn(1,"灰度概率",LVCFMT_LEFT,70,0); m_codinglist.InsertColumn(2,"編碼碼字",LVCFMT_LEFT,90,1); m_codinglist.InsertColumn(3,"碼字長度",LVCFMT_LEFT,60,2); //設(shè)置樣式為文本 codingItem.mask=LVIF_TEXT;//添加顯示 for(i=0;i<graygrade;i++) {//第一列顯示 codingItem.iItem=m_codinglist.GetItemCount(); listname.Format("%u",i); codingItem.iSubItem=0;//顯示像素灰度 codingItem.pszText=(LPTSTR)(LPCTSTR)listname; nItem2View=m_codinglist.InsertItem(&codingItem); codingItem.iItem=nItem2View; //第二列顯示 codingItem.iSubItem=1; listname.Format("%f",grayfreq[i]); codingItem.pszText=(LPTSTR)(LPCTSTR)listname; m_codinglist.SetItem(&codingItem);//第三列顯示 codingItem.iSubItem=2; codingItem.pszText=(LPTSTR)(LPCTSTR)m_strCode[i]; m_codinglist.SetItem(&codingItem);//第四列顯示 codingItem.iSubItem=3; listname.Format("%u",m_strCode[i].GetLength()); codingItem.pszText=(LPTSTR)(LPCTSTR)listname; m_codinglist.SetItem(&codingItem); } deleteturn;//內(nèi)存釋放 deletetemp; deletebFinished; returnTRUE;}5.2.2視圖類處理函數(shù)OnShannonCoding()函數(shù)關(guān)于函數(shù)的調(diào)用部分，在圖像處理的主窗口的菜單欄“圖像編碼”下添加“香農(nóng)-范諾編碼”項，對應(yīng)的處理函數(shù)是CDImageProcessView視圖類中的OnShannoncoding()函數(shù)。OnShannoncoding()函數(shù)實現(xiàn)了圖像灰度概率的計算和編碼對話框的調(diào)用，具體代碼如下：voidCDImageProcessView::OnShannoncoding(){//獲取文檔 CDImageProcessDoc*pDoc=GetDocument();//指向源圖像的指針 unsignedchar* lpSrc; //指向DIB的指針 LPSTRlpDIB; //指向DIB象素指針 LPSTRlpDIBBits;//圖像灰度等級數(shù) intgraygrade;//鎖定DIB lpDIB=(LPSTR)::GlobalLock((HGLOBAL)pDoc->GetHObject());//找到DIB圖像象素起始位置 lpDIBBits=pDoc->m_dib.GetBits(lpDIB); //判斷是否是8位位圖 if(pDoc->m_dib.GetColorNum(lpDIB)!=256) {//提示用戶 MessageBox("目前只支持256色位圖！","系統(tǒng)提示", MB_ICONINFORMATION|MB_OK); ::GlobalUnlock((HGLOBAL)pDoc->GetHObject());//解除鎖定 return;//返回 }//灰度等級數(shù)為256 graygrade=pDoc->m_dib.GetColorNum(lpDIB);//各灰度等級出現(xiàn)的概率 double*grayfreq;//圖像寬度 intwidth;//圖像高度 intheight; width=pDoc->m_dib.GetWidth(lpDIB); height=pDoc->m_dib.GetHeight(lpDIB);//更改光標(biāo)形狀 BeginWaitCursor(); //開始計算各個灰度級出現(xiàn)的概率，如果需要對指定的序列進行哈夫曼編碼, //只要將這一步改成給各個灰度級概率賦值即可 grayfreq=newdouble[graygrade];//分配內(nèi)存 intgraySum;//像素數(shù)目 inti;//循環(huán)變量 intj;//循環(huán)變量//計算圖象象素總數(shù) graySum=width*height; for(i=0;i<graygrade;i++) {//賦零值 grayfreq[i]=0.0; }//計算各個灰度值的計數(shù) for(i=0;i<height;i++) { for(j=0;j<width;j++) {//指向圖象指針 lpSrc=(unsignedchar*)lpDIBBits+width*i+j;//相應(yīng)的灰度計數(shù)加1 grayfreq[*(lpSrc)]=grayfreq[*(lpSrc)]+1; } } for(i=0;i<graygrade;i++) {//計算各個灰度值出現(xiàn)的概率 grayfreq[i]=grayfreq[i]/(double)graySum; } CShannonCodingcoding;//創(chuàng)建對話框 coding.grayfreq=grayfreq;//初始化變量值 coding.graygrade=graygrade; coding.DoModal(); //顯示對話框 EndWaitCursor(); //恢復(fù)光標(biāo)}5.3行程編碼5.3.1行程編碼算法實現(xiàn)函數(shù)PCXCoding()將指定的256色DIB對象保存為256色PCX文件。參數(shù)LPSTRlpDIBBits是指向DIB對象像素的指針；參數(shù)LONGImageWidth是源圖像寬度（像素數(shù)，必須是4的倍數(shù)）；參數(shù)LONGImageHeight是源圖像高度（像素數(shù)）；參數(shù)CFile&file是要保存的文件。BOOLPCXCoding(LPSTRlpDIBBits,LONGImageWidth,LONGImageHeight,CFile&file){ typedefstruct{ charmanufacturer; charversion; charencoding; charbits_per_pixel; WORDxmin,ymin; WORDxmax,ymax; WORDhres; WORDvres; charpalette[48]; charreserved; charcolour_planes; WORDbytes_per_line; WORDpalette_type; charfiller[58]; }PCXHEAD;inti;intj;//中間變量BYTEbChar1;//中間變量BYTEbChar2;//指向源圖像像素的指針BYTE*lpSrc;//指向編碼后圖像數(shù)據(jù)的指針BYTE*lpDst;//重復(fù)像素計數(shù)intiCount;//緩沖區(qū)已使用的字節(jié)數(shù)DWORDdwBuffUsed;//PCX文件頭PCXHEADpcxHeadr;//PCX標(biāo)志碼pcxHeadr.manufacturer=0x0A;//PCX版本號pcxHeadr.version=5;//PCX編碼方式(1表示RLE編碼)pcxHeadr.encoding=1;//像素位數(shù)（256色為8位）pcxHeadr.bits_per_pixel=8;//圖像相對于屏幕的左上角X坐標(biāo)pcxHeadr.xmin=0;//圖像相對于屏幕的左上角Y坐標(biāo)pcxHeadr.ymin=0;//圖像相對于屏幕的右下角X坐標(biāo)pcxHeadr.xmax=ImageWidth-1;//圖像相對于屏幕的右下角Y坐標(biāo)pcxHeadr.ymax=ImageHeight-1;//圖像的水平分辨率pcxHeadr.hres=ImageWidth;//圖像的垂直分辨率pcxHeadr.vres=ImageHeight;for(i=0;i<48;i++){//調(diào)色板數(shù)據(jù)（對于256色PCX無意義，直接賦值為0） pcxHeadr.palette[i]=0;}//保留域設(shè)定為0pcxHeadr.reserved=0;//圖像色彩平面數(shù)目對于256色PCX設(shè)為1pcxHeadr.colour_planes=1;//圖像的寬度（字節(jié)為單位）必須為偶數(shù)pcxHeadr.bytes_per_line=ImageWidth;//圖像調(diào)色板的類型，1表示彩色或者單色圖像，2表示圖像是灰度圖pcxHeadr.palette_type=1;for(i=0;i<54;i++){ pcxHeadr.filler[i]=0;}//寫入頭文件file.Write((LPSTR)&pcxHeadr,sizeof(PCXHEAD));//分配內(nèi)存以保存編碼結(jié)果lpDst=newBYTE[ImageHeight*ImageWidth*2];//指明當(dāng)前已經(jīng)用了多少緩沖區(qū)（字節(jié)數(shù)）dwBuffUsed=0;for(i=0;i<ImageHeight;i++){//指向DIB第i行，第0個像素的指針 lpSrc=(BYTE*)lpDIBBits+ImageWidth*(ImageHeight-1-i);//給bChar1賦值 bChar1=*lpSrc;//設(shè)置iCount為1iCount=1; for(j=1;j<ImageWidth;j++) { lpSrc++; bChar2=*lpSrc; if((bChar1==bChar2)&&(iCount<63)) iCount++; else { if((iCount>1)||(bChar1>=0xC0)) { lpDst[dwBuffUsed]=iCount|0xC0; lpDst[dwBuffUsed+1]=bChar1; dwBuffUsed+=2; } else { lpDst[dwBuffUsed]=bChar1; dwBuffUsed++; } bChar1=bChar2; iCount=1; } } if((iCount>1)||(bChar1>=0xC0)) { lpDst[dwBuffUsed]=iCount|0xC0; lpDst[dwBuffUsed+1]=bChar1; dwBuffUsed+=2; } else { lpDst[dwBuffUsed]=bChar1; dwBuffUsed++; }}file.WriteHuge((LPSTR)lpDst,dwBuffUsed);delete[]lpDst;lpDst=newBYTE[769];*lpDst=0x0C;for(i=0;i<256;i++){ lpDst[i*3+1]=i;lpDst[i*3+2]=i; lpDst[i*3+3]=i;}file.Write((LPSTR)lpDst,769);returnTRUE;}5.3.2視圖類處理函數(shù)OnRleCoding()關(guān)于PCXCoding的函數(shù)調(diào)用部分，在圖像處理的主窗口菜單欄“圖像編碼”下添加“行程編碼”項，對應(yīng)的處理函數(shù)是CDImageProces