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

華東交大理工學(xué)院課程設(shè)計(jì)課設(shè)名稱應(yīng)用C/C++語言編寫灰度圖像霍夫曼編碼的程序所屬課程數(shù)字圖像處理課程設(shè)計(jì)班級(jí)05計(jì)算機(jī)2班姓名麻仕偉學(xué)號(hào)31號(hào)指導(dǎo)教師俞慧娟2008華東交大理工學(xué)院_2021-2021_學(xué)年第_一_學(xué)期課程設(shè)計(jì)安排方案班級(jí)：05計(jì)算機(jī)2班課程：_數(shù)字圖像處理課程設(shè)計(jì)課程設(shè)計(jì)題目：應(yīng)用C/C++語言編寫灰度圖像霍夫曼編碼的程序設(shè)計(jì)內(nèi)容及要求：用C/C++語言完成設(shè)計(jì)，在計(jì)算機(jī)上調(diào)試程序；上機(jī)課時(shí)：8課時(shí)；列出設(shè)計(jì)結(jié)果，并提交課程設(shè)計(jì)報(bào)告。設(shè)計(jì)方法與步驟：統(tǒng)計(jì)一幅BMP格式的灰度圖像的概率，并顯示相應(yīng)的灰度值和概率；對(duì)這幅圖像做霍夫曼編碼；并列出編碼結(jié)果。計(jì)算平均碼長和熵值，算出編碼效率。所有的結(jié)果都要求顯示出來。設(shè)計(jì)時(shí)間安排：2008年12月29日〔星期一〕3、2008年12月30日〔星期二〕1、2008年12其他需說明的事項(xiàng)〔課設(shè)如到本部做，請注明實(shí)驗(yàn)室名稱；還有學(xué)校需提供的軟件和硬件環(huán)境〕指導(dǎo)老師：余慧娟時(shí)間：2008-12-2目錄一.正文………………….........................4統(tǒng)計(jì)一幅BMP格式的灰度圖像的概率，并顯示相應(yīng)的灰度值和概率………………….………41.2霍夫曼編碼方法的產(chǎn)生背景,具體方法………....5計(jì)算平均碼長和熵值，算出編碼效率………………6二.小結(jié)…………………...7三.附錄…………………...........................83.1源程序……………….83.2程序運(yùn)行結(jié)果……...153.3參考文獻(xiàn)…………...17正文統(tǒng)計(jì)一幅BMP格式的灰度圖像的概率在實(shí)現(xiàn)數(shù)字圖象處理的過程中，主要是通過對(duì)圖像中的每一個(gè)像素點(diǎn)運(yùn)用各種圖像處理算法來到達(dá)預(yù)期的效果，所以進(jìn)行圖像處理的第一步，也是我們最關(guān)心的問題，是如何得到圖像中每一個(gè)像素點(diǎn)的亮度值；為了觀察和驗(yàn)證處理的圖像效果，另一個(gè)需要解決的問題是如何將處理前后的圖像正確的顯示出來。BMP灰度圖像作為Windows環(huán)境下主要的圖像格式之一，以其格式簡單，適應(yīng)性強(qiáng)而倍受歡送。正如我們在上一講中介紹過的那樣，這種文件格式就是每一個(gè)像素用8bit表示，顯示出來的圖像是黑白效果，最黑的像素的灰度〔也叫作亮度〕值為“0〞，最白的像素的灰度值為“255〞，整個(gè)圖像各個(gè)像素的灰度值隨機(jī)的分布在“0〞到“255〞的區(qū)間中，越黑的像素，其灰度值越接近于“0〞，越白〔既越亮〕的像素，其灰度值越接近于“255〞；與此對(duì)應(yīng)的是在該文件類型中的顏色表項(xiàng)的各個(gè)RGB分量值是相等的，并且顏色表項(xiàng)的數(shù)目是256個(gè)。在進(jìn)行圖像處理時(shí)，操作圖像中的像素值就要得到圖像陣列；經(jīng)過處理后的圖像的像素值需要存儲(chǔ)起來；顯示圖像時(shí)要正確實(shí)現(xiàn)調(diào)色板、得到位圖的尺寸信息等。，BMP位圖包括位圖文件頭結(jié)構(gòu)BITMAPFILEHEADER、位圖信息頭結(jié)構(gòu)BITMAPINFOHEADER、位圖顏色表RGBQUAD和位圖像素?cái)?shù)據(jù)四局部。處理位圖時(shí)要根據(jù)文件的這些結(jié)構(gòu)得到位圖文件大小、位圖的寬、高、實(shí)現(xiàn)調(diào)色板、得到位圖像素值等等。這里要注意的一點(diǎn)是在BMP位圖中，位圖的每行像素值要填充到一個(gè)四字節(jié)邊界，即位圖每行所占的存儲(chǔ)長度為四字節(jié)的倍數(shù)，缺乏時(shí)將多余位用0填充。為此，我們充分利用了程序的文檔視圖結(jié)構(gòu)，在程序中直接使用了一些API函數(shù)來操作圖像。在微軟的MSDN中有一個(gè)名為Diblook的例子，該例子演示了如何操作Dib位圖.啟動(dòng)VisualC++，生成一個(gè)名為Dib的多文檔程序，將CDibView類的基類設(shè)為CscrollView類，這樣作的目的是為了在顯示位圖時(shí)支持滾動(dòng)條，另外在處理圖像應(yīng)用程序的文檔類〔CDibDoc.h〕中聲明如下宏及公有變量：#defineWIDTHBYTES(bits)(((bits)+31)/32*4)//計(jì)算圖像每行象素所占的字節(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〞。這樣作的目的是為了在程序文件對(duì)話框中可以選擇BMP或DIB格式的位圖文件?；舴蚵幋a方法的產(chǎn)生背景和具體方法Huffman在1952年根據(jù)香農(nóng)〔Shannon〕在1948年和范假設(shè)〔Fano〕在1949年闡述的這種編碼思想提出了一種不定長編碼的方法，也稱霍夫曼〔Huffman〕編碼?；舴蚵幋a的根本方法是先對(duì)圖像數(shù)據(jù)掃描一遍，計(jì)算出各種像素出現(xiàn)的概率，按概率的大小指定不同長度的唯一碼字，由此得到一張?jiān)搱D像的霍夫曼碼表。編碼后的圖像數(shù)據(jù)記錄的是每個(gè)像素的碼字，而碼字與實(shí)際像素值的對(duì)應(yīng)關(guān)系記錄在碼表中。霍夫曼編碼是可變字長編碼(VLC)的一種。Huffman于1952年提出一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長度最短的碼字，有時(shí)稱之為最正確編碼，一般就稱Huffman編碼。定理：在變字長編碼中，如果碼字長度嚴(yán)格按照對(duì)應(yīng)符號(hào)出現(xiàn)的概率大小逆序排列，那么其平均碼字長度為最小。霍夫曼編碼的具體方法：先按出現(xiàn)的概率大小排隊(duì)，把兩個(gè)最小的概率相加，作為新的概率和剩余的概率重新排隊(duì)，再把最小的兩個(gè)概率相加，再重新排隊(duì)，直到最后變成1。每次相加時(shí)都將“0〞和“1〞賦與相加的兩個(gè)概率，讀出時(shí)由該符號(hào)開始一直走到最后的“1〞，將路線上所遇到的“0〞和“1〞按最低位到最高位的順序排好，就是該符號(hào)的霍夫曼編碼計(jì)算平均碼長和熵值，算出編碼效率設(shè){v1,v2,v3,v4,…..,vm}為一個(gè)離散無記憶信源,有個(gè)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)計(jì)編碼的一種，屬于無損壓縮編碼。該編碼是在1952年為文本文件建立的，編碼方法簡單且有效，因而得到廣泛的應(yīng)用?，F(xiàn)在已經(jīng)派生出很多變體。它的根本原理是用較短的代碼代替出現(xiàn)概率較高的數(shù)據(jù)，用較長的代碼代替出現(xiàn)概率較低的數(shù)據(jù)，所有代碼都采用二進(jìn)制碼，其碼的長度是可變的，且每個(gè)數(shù)據(jù)的代碼各不相同。它提出的這種編碼也稱為最正確變長碼，其優(yōu)點(diǎn)是編碼的效率高，但這種編碼依賴于源的統(tǒng)計(jì)特性，同時(shí)我們看到，Huffman編碼只能通過查表的方法建立消息和碼字之間的關(guān)系，所以如果消息數(shù)很大，需要存儲(chǔ)的碼表也需很大，從而會(huì)影響存儲(chǔ)量、編碼以及譯碼速度等各個(gè)方面的性能。通過此次課程設(shè)計(jì)我理解了什么是Huffman〔哈夫曼〕編碼，并通過此次課程設(shè)計(jì)學(xué)會(huì)了如何運(yùn)用C/C++語言編寫灰度圖像霍夫曼編碼的程序。了解了Huffman〔哈夫曼〕編碼的具體方法，學(xué)會(huì)了如何計(jì)算平均碼長和熵值，并計(jì)算出編碼效率。三.附錄3.1源程序1、讀取灰度BMP位圖可以根據(jù)BMP位圖文件的結(jié)構(gòu)，操作BMP位圖文件并讀入圖像數(shù)據(jù)，為此我們充分利用了VC的文檔視圖結(jié)構(gòu)，重載了文擋類的OnOpenDocument〔〕函數(shù)，這樣用戶就可以在自動(dòng)生成程序的翻開文件對(duì)話框中選擇所要翻開的位圖文件，然后程序?qū)⒆詣?dòng)調(diào)用該函數(shù)執(zhí)行讀取數(shù)據(jù)的操作。該函數(shù)的實(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;}//此時(shí)pDIB數(shù)據(jù)塊中讀取的數(shù)據(jù)包括位圖頭信息、位圖顏色表、圖像像素的灰度值；bmhdr=(BITMAPINFOHEADER*)pDIB;//為指向位圖信息頭結(jié)構(gòu)的指針賦值；::GlobalUnlock((HGLOBAL)hDIB);if((*bmhdr).biBitCount!=8)//驗(yàn)證是否為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++){//每個(gè)顏色表項(xiàng)的R、G、B值相等，并且各個(gè)值從“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è)置存儲(chǔ)路徑SetModifiedFlag(FALSE);//設(shè)置文件修改標(biāo)志為FALSEreturnTRUE;}上面的方法是通過CFile類對(duì)象的操作來讀取位圖文件的，它需要分析位圖中的文件頭信息，從而確定需要讀取的圖像長度。這種方法相對(duì)來說有些繁瑣，其實(shí)還可以以一種相對(duì)簡單的方法讀取位圖數(shù)據(jù)，首先在程序的資源中定義DIB類型資源，然后添加位圖到該類型中，將圖像數(shù)據(jù)以資源的形式讀取出來，這時(shí)候就可以根據(jù)所獲取的數(shù)據(jù)中的位圖信息結(jié)構(gòu)來獲取、顯示圖像數(shù)據(jù)了。下面的函數(shù)實(shí)現(xiàn)了以資源形式裝載圖像文件數(shù)據(jù)，該函數(shù)的實(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ù)的存儲(chǔ)為了將圖像處理后所得到的像素值保存起來，我們重載了文檔類的OnSaveDocument〔〕函數(shù)，這樣用戶在點(diǎn)擊Save或SaveAs子菜單后程序自動(dòng)調(diào)用該函數(shù)，實(shí)現(xiàn)圖像數(shù)據(jù)的存儲(chǔ)。該函數(shù)的具體實(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;//存儲(chǔ)時(shí)位圖所有像素所占的總字節(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)、顏色表、像素?cái)?shù)據(jù)〕寫入文件；::GlobalUnlock((HGLOBAL)m_hDIB);EndWaitCursor()；SetModifiedFlag(FALSE)；//將文檔設(shè)為“干凈〞標(biāo)志，表示此后文檔不需要存盤提示；returnTRUE；}霍夫曼編碼的程序structHaffNode//哈夫曼樹的結(jié)點(diǎn)結(jié)構(gòu){ intweight; //權(quán)值 intflag; //標(biāo)記 intparent; //雙親結(jié)點(diǎn)下標(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é)點(diǎn)個(gè)數(shù)為n權(quán)值為weight的哈夫曼樹haffTree{ intj,m1,m2,x1,x2; //哈夫曼樹haffTree初始化。n個(gè)葉結(jié)點(diǎn)的哈夫曼樹共有2n-1個(gè)結(jié)點(diǎn) 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個(gè)非葉結(jié)點(diǎn) 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個(gè)結(jié)點(diǎn)的哈夫曼樹haffTree構(gòu)造哈夫曼編碼haffCode{ Code*cd=newCode; intchild,parent; //求n個(gè)葉結(jié)點(diǎn)的哈夫