應(yīng)用C-C 語言編寫灰度圖像霍夫曼編碼的程序

華東交大理工學(xué)院課程設(shè)計課設(shè)名稱應(yīng)用C/C++語言編寫灰度圖像霍夫曼編碼的程序所屬課程數(shù)字圖像處理課程設(shè)計班級05計算機2班姓名麻仕偉學(xué)號31號指導(dǎo)教師俞慧娟2008華東交大理工學(xué)院_2021-2021_學(xué)年第_一_學(xué)期課程設(shè)計安排方案班級：05計算機2班課程：_數(shù)字圖像處理課程設(shè)計課程設(shè)計題目：應(yīng)用C/C++語言編寫灰度圖像霍夫曼編碼的程序設(shè)計內(nèi)容及要求：用C/C++語言完成設(shè)計，在計算機上調(diào)試程序；上機課時：8課時；列出設(shè)計結(jié)果，并提交課程設(shè)計報告。設(shè)計方法與步驟：統(tǒng)計一幅BMP格式的灰度圖像的概率，并顯示相應(yīng)的灰度值和概率；對這幅圖像做霍夫曼編碼；并列出編碼結(jié)果。計算平均碼長和熵值，算出編碼效率。所有的結(jié)果都要求顯示出來。設(shè)計時間安排：2008年12月29日〔星期一〕3、2008年12月30日〔星期二〕1、2008年12其他需說明的事項〔課設(shè)如到本部做，請注明實驗室名稱；還有學(xué)校需提供的軟件和硬件環(huán)境〕指導(dǎo)老師：余慧娟時間：2008-12-2目錄一.正文………………….........................4統(tǒng)計一幅BMP格式的灰度圖像的概率，并顯示相應(yīng)的灰度值和概率………………….………41.2霍夫曼編碼方法的產(chǎn)生背景,具體方法………....5計算平均碼長和熵值，算出編碼效率………………6二.小結(jié)…………………...7三.附錄…………………...........................83.1源程序……………….83.2程序運行結(jié)果……...153.3參考文獻(xiàn)…………...17正文統(tǒng)計一幅BMP格式的灰度圖像的概率在實現(xiàn)數(shù)字圖象處理的過程中，主要是通過對圖像中的每一個像素點運用各種圖像處理算法來到達(dá)預(yù)期的效果，所以進(jìn)行圖像處理的第一步，也是我們最關(guān)心的問題，是如何得到圖像中每一個像素點的亮度值；為了觀察和驗證處理的圖像效果，另一個需要解決的問題是如何將處理前后的圖像正確的顯示出來。BMP灰度圖像作為Windows環(huán)境下主要的圖像格式之一，以其格式簡單，適應(yīng)性強而倍受歡送。正如我們在上一講中介紹過的那樣，這種文件格式就是每一個像素用8bit表示，顯示出來的圖像是黑白效果，最黑的像素的灰度〔也叫作亮度〕值為“0〞，最白的像素的灰度值為“255〞，整個圖像各個像素的灰度值隨機的分布在“0〞到“255〞的區(qū)間中，越黑的像素，其灰度值越接近于“0〞，越白〔既越亮〕的像素，其灰度值越接近于“255〞；與此對應(yīng)的是在該文件類型中的顏色表項的各個RGB分量值是相等的，并且顏色表項的數(shù)目是256個。在進(jìn)行圖像處理時，操作圖像中的像素值就要得到圖像陣列；經(jīng)過處理后的圖像的像素值需要存儲起來；顯示圖像時要正確實現(xiàn)調(diào)色板、得到位圖的尺寸信息等。，BMP位圖包括位圖文件頭結(jié)構(gòu)BITMAPFILEHEADER、位圖信息頭結(jié)構(gòu)BITMAPINFOHEADER、位圖顏色表RGBQUAD和位圖像素數(shù)據(jù)四局部。處理位圖時要根據(jù)文件的這些結(jié)構(gòu)得到位圖文件大小、位圖的寬、高、實現(xiàn)調(diào)色板、得到位圖像素值等等。這里要注意的一點是在BMP位圖中，位圖的每行像素值要填充到一個四字節(jié)邊界，即位圖每行所占的存儲長度為四字節(jié)的倍數(shù)，缺乏時將多余位用0填充。為此，我們充分利用了程序的文檔視圖結(jié)構(gòu)，在程序中直接使用了一些API函數(shù)來操作圖像。在微軟的MSDN中有一個名為Diblook的例子，該例子演示了如何操作Dib位圖.啟動VisualC++，生成一個名為Dib的多文檔程序，將CDibView類的基類設(shè)為CscrollView類，這樣作的目的是為了在顯示位圖時支持滾動條，另外在處理圖像應(yīng)用程序的文檔類〔CDibDoc.h〕中聲明如下宏及公有變量：#defineWIDTHBYTES(bits)(((bits)+31)/32*4)//計算圖像每行象素所占的字節(jié)數(shù)目；HANDLEm_hDIB;//存放位圖數(shù)據(jù)的句柄；CPalette*m_palDIB;//指向調(diào)色板Cpalette類的指針；CSizem_sizeDoc;//初始化視圖的尺寸，該尺寸為位圖的尺寸；最后將程序的字符串表中的字符串資源IDR_DibTYPE修改為：“\nDib\nDib\nDibFiles(*.bmp;*.dib)\n.bmp\nDib.Document\nDibDocument〞。這樣作的目的是為了在程序文件對話框中可以選擇BMP或DIB格式的位圖文件。霍夫曼編碼方法的產(chǎn)生背景和具體方法Huffman在1952年根據(jù)香農(nóng)〔Shannon〕在1948年和范假設(shè)〔Fano〕在1949年闡述的這種編碼思想提出了一種不定長編碼的方法，也稱霍夫曼〔Huffman〕編碼?；舴蚵幋a的根本方法是先對圖像數(shù)據(jù)掃描一遍，計算出各種像素出現(xiàn)的概率，按概率的大小指定不同長度的唯一碼字，由此得到一張該圖像的霍夫曼碼表。編碼后的圖像數(shù)據(jù)記錄的是每個像素的碼字，而碼字與實際像素值的對應(yīng)關(guān)系記錄在碼表中?；舴蚵幋a是可變字長編碼(VLC)的一種。Huffman于1952年提出一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長度最短的碼字，有時稱之為最正確編碼，一般就稱Huffman編碼。定理：在變字長編碼中，如果碼字長度嚴(yán)格按照對應(yīng)符號出現(xiàn)的概率大小逆序排列，那么其平均碼字長度為最小。霍夫曼編碼的具體方法：先按出現(xiàn)的概率大小排隊，把兩個最小的概率相加，作為新的概率和剩余的概率重新排隊，再把最小的兩個概率相加，再重新排隊，直到最后變成1。每次相加時都將“0〞和“1〞賦與相加的兩個概率，讀出時由該符號開始一直走到最后的“1〞，將路線上所遇到的“0〞和“1〞按最低位到最高位的順序排好，就是該符號的霍夫曼編碼計算平均碼長和熵值，算出編碼效率設(shè){v1,v2,v3,v4,…..,vm}為一個離散無記憶信源,有個N消息,其中消息vi出現(xiàn)的概率為Pi(i=1,2,3,…..N).如下,此信源X的熵為H(X)=-∑Pilog2Pi平均碼長為:Lp=∑PiLi編碼效率為:M=(H(X)/Lp)×100%二.小結(jié)Huffman〔哈夫曼〕編碼是統(tǒng)計編碼的一種，屬于無損壓縮編碼。該編碼是在1952年為文本文件建立的，編碼方法簡單且有效，因而得到廣泛的應(yīng)用。現(xiàn)在已經(jīng)派生出很多變體。它的根本原理是用較短的代碼代替出現(xiàn)概率較高的數(shù)據(jù)，用較長的代碼代替出現(xiàn)概率較低的數(shù)據(jù)，所有代碼都采用二進(jìn)制碼，其碼的長度是可變的，且每個數(shù)據(jù)的代碼各不相同。它提出的這種編碼也稱為最正確變長碼，其優(yōu)點是編碼的效率高，但這種編碼依賴于源的統(tǒng)計特性，同時我們看到，Huffman編碼只能通過查表的方法建立消息和碼字之間的關(guān)系，所以如果消息數(shù)很大，需要存儲的碼表也需很大，從而會影響存儲量、編碼以及譯碼速度等各個方面的性能。通過此次課程設(shè)計我理解了什么是Huffman〔哈夫曼〕編碼，并通過此次課程設(shè)計學(xué)會了如何運用C/C++語言編寫灰度圖像霍夫曼編碼的程序。了解了Huffman〔哈夫曼〕編碼的具體方法，學(xué)會了如何計算平均碼長和熵值，并計算出編碼效率。三.附錄3.1源程序1、讀取灰度BMP位圖可以根據(jù)BMP位圖文件的結(jié)構(gòu)，操作BMP位圖文件并讀入圖像數(shù)據(jù)，為此我們充分利用了VC的文檔視圖結(jié)構(gòu)，重載了文擋類的OnOpenDocument〔〕函數(shù)，這樣用戶就可以在自動生成程序的翻開文件對話框中選擇所要翻開的位圖文件，然后程序?qū)⒆詣诱{(diào)用該函數(shù)執(zhí)行讀取數(shù)據(jù)的操作。該函數(shù)的實現(xiàn)代碼如下所示：BOOLCDibDoc::OnOpenDocument(LPCTSTRlpszPathName){LOGPALETTE*pPal;//定義邏輯調(diào)色板指針；pPal=newLOGPALETTE;//初始化該指針；CFilefile;CFileExceptionfe;if(!file.Open(lpszPathName,CFile::modeRead|CFile::shareDenyWrite,&fe)){//以“讀〞的方式翻開文件；AfxMessageBox("圖像文件打不開！");returnFALSE;}DeleteContents();//刪除文擋；BeginWaitCursor();BITMAPFILEHEADERbmfHeader;//定義位圖文件頭結(jié)構(gòu)；LPBITMAPINFOlpbmi;DWORDdwBitsSize;HANDLEhDIB;LPSTRpDIB;//指向位圖數(shù)據(jù)的指針；BITMAPINFOHEADER*bmhdr;//指向位圖信息頭結(jié)構(gòu)的指針dwBitsSize=file.GetLength();//得到文件長度if(file.Read((LPSTR)&bmfHeader,sizeof(bmfHeader))!=sizeof(bmfHeader))returnFALSE;//讀取位圖文件的文件頭結(jié)構(gòu)信息；if(bmfHeader.bfType!=0x4d42)//檢查該文件是否為BMP格式的文件；returnFALSE;hDIB=(HANDLE)::GlobalAlloc(GMEM_MOVEABLE|GMEM_ZEROINIT,dwBitsSize);//為讀取圖像文件數(shù)據(jù)申請緩沖區(qū)if(hDIB==0){returnFALSE;}pDIB=(LPSTR)::GlobalLock((HGLOBAL)hDIB);//得到申請的緩沖區(qū)的指針；if(file.ReadHuge(pDIB,dwBitsSize-sizeof(BITMAPFILEHEADER))!=dwBitsSize-sizeof(BITMAPFILEHEADER)){::GlobalUnlock((HGLOBAL)hDIB);hDIB=NULL;returnFALSE;}//此時pDIB數(shù)據(jù)塊中讀取的數(shù)據(jù)包括位圖頭信息、位圖顏色表、圖像像素的灰度值；bmhdr=(BITMAPINFOHEADER*)pDIB;//為指向位圖信息頭結(jié)構(gòu)的指針賦值；::GlobalUnlock((HGLOBAL)hDIB);if((*bmhdr).biBitCount!=8)//驗證是否為8bit位圖{AfxMessageBox("該文件不是灰度位圖格式！");returnFALSE;}m_hDIB=hDIB;//將內(nèi)部變量數(shù)據(jù)賦于全局變量；//下面是記錄位圖的尺寸；m_sizeDoc.x=bmhdr->biWidth;m_sizeDoc.y=bmhdr->biHeight;//下面是根據(jù)顏色表生成調(diào)色板；m_palDIB=newCpalette;pPal->palVersion=0x300;//填充邏輯顏色表pPal->palNumEntries=256;lpbmi=(LPBITMAPINFO)bmhdr;for(inti=0;i<256;i++){//每個顏色表項的R、G、B值相等，并且各個值從“0”到“255Pal->palPalentry[i].peRed=lpbmi->bmiColors[i].rgbRed;pPal->palPalentry[i].peGreen=lpbmi->bmiColors[i].rgbGreen;pPal->palPalentry[i].peBlue=lpbmi->bmiColors[i].rgbBlue;;pPal->palPalentry[i].peFlags=0;}m_palDIB->CreatePalette(pPal);//根據(jù)讀入的數(shù)據(jù)得到位圖的寬、高、顏色表;if(pPal)deletepPal;EndWaitCursor();SetPathName(lpszPathName);//設(shè)置存儲路徑SetModifiedFlag(FALSE);//設(shè)置文件修改標(biāo)志為FALSEreturnTRUE;}上面的方法是通過CFile類對象的操作來讀取位圖文件的，它需要分析位圖中的文件頭信息，從而確定需要讀取的圖像長度。這種方法相對來說有些繁瑣，其實還可以以一種相對簡單的方法讀取位圖數(shù)據(jù)，首先在程序的資源中定義DIB類型資源，然后添加位圖到該類型中，將圖像數(shù)據(jù)以資源的形式讀取出來，這時候就可以根據(jù)所獲取的數(shù)據(jù)中的位圖信息結(jié)構(gòu)來獲取、顯示圖像數(shù)據(jù)了。下面的函數(shù)實現(xiàn)了以資源形式裝載圖像文件數(shù)據(jù)，該函數(shù)的實現(xiàn)代碼如下所示：HANDLELoadDIB(UINTuIDS,LPCSTRlpszDibType){LPCSTRlpszDibRes=MAKEINTRESOURCE(uIDS);//根據(jù)資源標(biāo)志符確定資源的名字；HINSTANCEhInst=AfxGetInstanceHandle();//得到應(yīng)用程序的句柄；HRSRChRes=：：FindResource(hInst,lpszDibRes,lpszDibType);//獲取資源的句柄，這里lpszDibType為資源的名字“DIB〞;If(hRes==NULL)returnNULLHGLOBALhData=：：LoadResource(hInst,hRes);//轉(zhuǎn)載資源數(shù)據(jù)并返回該句柄；returnhData;}2、灰度位圖數(shù)據(jù)的存儲為了將圖像處理后所得到的像素值保存起來，我們重載了文檔類的OnSaveDocument〔〕函數(shù)，這樣用戶在點擊Save或SaveAs子菜單后程序自動調(diào)用該函數(shù)，實現(xiàn)圖像數(shù)據(jù)的存儲。該函數(shù)的具體實現(xiàn)如下:BOOLCDibDoc::OnSaveDocument(LPCTSTRlpszPathName){CFilefile;CFileExceptionfe;BITMAPFILEHEADERbmfHdr;//位圖文件頭結(jié)構(gòu)；LPBITMAPINFOHEADERlpBI;//指向位圖頭信息結(jié)構(gòu)的指針；DWORDdwDIBSize;；if(!file.Open(lpszPathName,CFile::modeCreate|CFile::modeReadWrite|CFile::shareExclusive,&fe)){AfxMessageBox("文件打不開")；returnFALSE;}//以讀寫的方式翻開文件；BOOLbSuccess=FALSE;BeginWaitCursor();lpBI=(LPBITMAPINFOHEADER)::GlobalLock((HGLOBAL)m_hDIB);if(lpBI==NULL)returnFALSE;dwDIBSize=*(LPDWORD)lpBI+256*sizeof(RGBQUAD);//圖像的文件信息所占用的字節(jié)數(shù)；DWORDdwBmBitsSize;//BMP文件中位圖的像素所占的字節(jié)數(shù)dwBmBitsSize=WIDTHBYTES((lpBI->biWidth)*((DWORD)lpBI->biBitCount))*lpBI->biHeight;//存儲時位圖所有像素所占的總字節(jié)數(shù)dwDIBSize+=dwBmBitsSize;//BMP文件除文件信息結(jié)構(gòu)外的所有數(shù)據(jù)占用的總字節(jié)數(shù)；lpBI->biSizeImage=dwBmBitsSize;//位圖所有像素所占的總字節(jié)數(shù)//以下五句為文件頭結(jié)構(gòu)填充值bmfHdr.bfType=0x4d42;//文件為"BMP"類型bmfHdr.bfSize=dwDIBSize+sizeof(BITMAPFILEHEADER);//文件總長度bmfHdr.bfReserved1=0;bmfHdr.bfReserved2=0;bmfHdr.bfOffBits=(DWORD)sizeof(BITMAPFILEHEADER)+lpBI->biSize+256*sizeof(RGBQUAD);//位圖數(shù)據(jù)距離文件頭的偏移量；file.Write((LPSTR)&bmfHdr,sizeof(BITMAPFILEHEADER));//向文件中寫文件頭信息；file.WriteHuge(lpBI,dwDIBSize);//將位圖信息〔信息頭結(jié)構(gòu)、顏色表、像素數(shù)據(jù)〕寫入文件；::GlobalUnlock((HGLOBAL)m_hDIB);EndWaitCursor()；SetModifiedFlag(FALSE)；//將文檔設(shè)為“干凈〞標(biāo)志，表示此后文檔不需要存盤提示；returnTRUE；}霍夫曼編碼的程序structHaffNode//哈夫曼樹的結(jié)點結(jié)構(gòu){ intweight; //權(quán)值 intflag; //標(biāo)記 intparent; //雙親結(jié)點下標(biāo) intleftChild; //左孩子下標(biāo) intrightChild; //右孩子下標(biāo)};structCode//存放哈夫曼編碼的數(shù)據(jù)元素結(jié)構(gòu){ intbit[MaxN]; //數(shù)組 intstart; //編碼的起始下標(biāo) intweight; //字符的權(quán)值};voidHaffman(intweight[],intn,HaffNodehaffTree[])//建立葉結(jié)點個數(shù)為n權(quán)值為weight的哈夫曼樹haffTree{ intj,m1,m2,x1,x2; //哈夫曼樹haffTree初始化。n個葉結(jié)點的哈夫曼樹共有2n-1個結(jié)點 for(inti=0;i<2*n-1;i++) { if(i<n)haffTree[i].weight=weight[i]; elsehaffTree[i].weight=0; haffTree[i].parent=0; haffTree[i].flag=0; haffTree[i].leftChild=-1; haffTree[i].rightChild=-1; } //構(gòu)造哈夫曼樹haffTree的n-1個非葉結(jié)點 for(i=0;i<n-1;i++) { m1=m2=MaxValue; x1=x2=0; for(j=0;j<n+i;j++) { if(haffTree[j].weight<m1&&haffTree[j].flag==0) { m2=m1; x2=x1; m1=haffTree[j].weight; x1=j; } elseif(haffTree[j].weight<m2&&haffTree[j].flag==0) { m2=haffTree[j].weight; x2=j; } } //將找出的兩棵權(quán)值最小的子樹合并為一棵子樹 haffTree[x1].parent=n+i; haffTree[x2].parent=n+i; haffTree[x1].flag=1; haffTree[x2].flag=1; haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight; haffTree[n+i].leftChild=x1; haffTree[n+i].rightChild=x2; }}voidHaffmanCode(HaffNodehaffTree[],intn,CodehaffCode[])//由n個結(jié)點的哈夫曼樹haffTree構(gòu)造哈夫曼編碼haffCode{ Code*cd=newCode; intchild,parent; //求n個葉結(jié)點的哈夫