[發(fā)明專利]一種基于Huffman編碼的圖片無損壓縮方法

無效

• 申請?zhí)枺?/td>: 201110376453.0
• 申請日: 2011-11-22
• 公開（公告）號: CN102438145A
• 公開（公告）日: 2012-05-02
• 發(fā)明（設計）人: 羅笑南;孟思明;譚南;張偉忠
• 申請（專利權）人: 廣州中大電訊科技有限公司
• 主分類號: H04N7/26
• 分類號: H04N7/26
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發(fā)明涉及數(shù)字圖像壓縮領域，具體涉及一種基于Huffman編碼的圖片無損壓縮方法。

背景技術

傳統(tǒng)的圖像編碼技術也稱為第一代編碼技術，主要有預測編碼、變換編碼、信息嫡編碼與矢量量化。預測編碼和變換編碼是當前圖像編碼器最常用的技術，預測和變換的主要目的是降低圖像原始空間域表示中存在的強相關性，使得預測或變換后的數(shù)據(jù)矩陣變成弱相關性矩陣，這樣可以用標量量化和嫡編碼進行有效的壓縮。信息嫡編碼是一種無失真編碼，常用的有哈夫曼編碼(Huffman?Coding)、游程長度編碼(Run?Length?Coding)和算術編碼(Arithmetic?Coding)三種。

隨著我國數(shù)字電視的普及，進一步的上傳并處理數(shù)字電視的綜合測試圖像具有重要的意義，而原始的圖像數(shù)據(jù)量較大，因此為了降低數(shù)據(jù)傳輸帶寬，在傳輸之前，需要對圖像進行無損壓縮。數(shù)據(jù)壓縮的理論就是去掉信息中的冗余，即保留不確定的信息，去掉確定的信息，也就是用一種更接近信息本質(zhì)的描述來代替原來有的冗余的描述。數(shù)據(jù)壓縮是信源編碼的目的。Huffman編碼作為一種最為常見的壓縮技術，它具有非常接近理論極限的壓縮比，該方法自提出后就成了數(shù)據(jù)壓縮領域中的一個研究主題并被廣泛的應用于文本、圖像及視頻的壓縮，如JPEG、MPEG標準都采用Huffman編碼作為其主要的編碼技術。

傳統(tǒng)上采用的Huffman編碼算法需要對原始數(shù)據(jù)進行兩遍掃描：第一遍掃描要精確地統(tǒng)計出原始數(shù)據(jù)中每個值出現(xiàn)的頻率，利用得到的頻率創(chuàng)建Huffman樹，并將樹的有關信息保存起來，便于解壓時使用；第二遍掃描根據(jù)前面得到的Huffman樹對原始數(shù)據(jù)進行編碼，并將編碼信息存儲起來。顯然，這個模型的缺點是對于數(shù)據(jù)量較大的信息，重復掃描要耗費大量時間，而且必須存儲編碼樹以便解碼時構造相同的編碼樹，將耗費大量的空間，降低了壓縮效率。

發(fā)明內(nèi)容

本發(fā)明提出的基于Huffman編碼的圖片無損壓縮方法對傳統(tǒng)的Huffman算法進行了改進，采用減少邏輯判斷的次數(shù)，增加少量的存儲碼表空間實現(xiàn)快速查找，在編碼端和解碼端分別保存編碼表和解碼表，編碼時直接進行查表從而節(jié)省大量的判斷時間。

為了解決上述問題，本發(fā)明提出了一種基于Huffman編碼的圖片無損壓縮方法，采用變字長編碼的最佳編碼定理，按符號出現(xiàn)概率的逆序分配碼字長，可以得到最佳的編碼方法，該方法包括：

步驟1：統(tǒng)計輸入符號的出現(xiàn)概率；

步驟2：將出現(xiàn)的概率由大到小排列，相同概率間的順序可以是任意的；

步驟3：將兩個最小的概率值相加得到一個新的概率值，將該概率值看成是一個新組合符號的概率；

步驟4：重復步驟2和步驟3，直到只有兩個新概率值為止，其中：已進行組合的概率不再參加排序；

步驟5：從最后兩個概率值開始，逐步向前給符號分配碼字長，其中：每一步有兩個分支，以相同的規(guī)則各賦予一個二進制碼，對概率大的賦碼0，對概率小的賦碼為1；或者對概率大的賦碼1，對概率小的賦碼為0，其中：

所述Huffman編碼對每一個符號都給定了一個編碼，形成了一個編碼表，其中：編碼表必須保存，在譯碼時需要參照它才能正確譯碼；由于Huffman編碼是異字頭的編碼，在譯碼時只要一定長度的二進制序列能與編碼表中編碼匹配上，該序列就是一個符號的編碼，從而保證了唯一的可譯性。

所述編碼表和解碼表兩個碼表的生成流程包括：

步驟11：輸入圖像信息；

步驟12：信息符號化，即將輸入的信息分解成一系列的符號；

步驟13：統(tǒng)計各個符號的概率；

步驟14：根據(jù)概率值產(chǎn)生編碼表；

步驟15：根據(jù)編碼表產(chǎn)生解碼表；

步驟16：圖像信息的恢復；

步驟17：圖像信息輸出。

所述生成編碼表時采用Huffman變長編碼和定長編碼相結合的方式。

所述生成編碼表時采用Huffman變長編碼和定長編碼相結合的方式步驟包括：

步驟41：初始化Huffman樹及碼表；

步驟42：統(tǒng)計所有的信息符號Sym；

步驟43：設定一個概率閾值Threshold，將每一個符號的概率值與該閾值進行比較；

步驟44：對大于該閾值的符號按傳統(tǒng)的Huffman編碼方法進行變長編碼，而對其余符號進行定長編碼；

步驟45：得到最長碼字長度L；

步驟46：所有碼字長度加1；