一種ARGB數(shù)據(jù)無(wú)損壓縮解壓算法的FPGA設(shè)計(jì)

尹 明，孫國(guó)慶

(1.青島科技大學(xué) 信息學(xué)院，山東 青島 266100；2.西安電子科技大學(xué)廣州研究院，廣州 510000)

0 引言

在GPU、AI等芯片設(shè)計(jì)領(lǐng)域，存儲(chǔ)器訪問(wèn)往往是系統(tǒng)性能的瓶頸，提高存儲(chǔ)器的訪問(wèn)效率對(duì)提升芯片性能的意義重大，其中對(duì)顏色緩沖區(qū)數(shù)據(jù)(AGRB)的頻繁讀寫(xiě)性能的影響很大[1]。從數(shù)據(jù)壓縮算法的角度，通過(guò)減少訪問(wèn)顏色緩沖區(qū)的數(shù)據(jù)量來(lái)提高存儲(chǔ)器的帶寬和訪問(wèn)效率[2-3]。

圖像壓縮是一種通過(guò)使用更緊湊的方式來(lái)存儲(chǔ)和傳輸圖像數(shù)據(jù)的技術(shù)。在進(jìn)行無(wú)損圖像壓縮時(shí)，通常會(huì)對(duì)圖像的各個(gè)通道(包括紅色通道(R)、綠色通道(G)、藍(lán)色通道(B)以及透明度通道(A))進(jìn)行處理，這些通道數(shù)據(jù)通常是基于AGRB格式。數(shù)據(jù)壓縮的原理來(lái)自于信息內(nèi)存在的數(shù)據(jù)冗余。文獻(xiàn)[4]提出一種多級(jí)流水的Gzip壓縮設(shè)計(jì)架構(gòu)。利用并行處理窗口的設(shè)計(jì)實(shí)現(xiàn)數(shù)據(jù)壓縮的并行處理，通過(guò)匹配選擇消除了并行處理的相關(guān)性[4]。文獻(xiàn)[5]使用了計(jì)算速度與擬合精度更有優(yōu)勢(shì)的自注意力機(jī)制模型，同時(shí)引入字典編碼的優(yōu)勢(shì)，以字節(jié)對(duì)編碼(Byte-pair Encoding)的形式生成字典，以模型計(jì)算數(shù)據(jù)集統(tǒng)計(jì)信息，輔以算術(shù)編碼AC進(jìn)行壓縮，能夠達(dá)到吞吐率與壓縮比都更高的無(wú)損壓縮模型[5]。文獻(xiàn)[6]提出了一種在FPGA平臺(tái)上實(shí)現(xiàn)Huffman編碼以及高速存入DDR3SDRAM存儲(chǔ)器的研究方案[6]。文獻(xiàn)[7]根據(jù)LZ77和LZW壓縮算法的基本原理，通過(guò)分析多種影響LZ77和LZW壓縮性能的關(guān)鍵因素，提出諸如雙Hash函數(shù)查找方式、并行匹配處理方法、更有效的LZ77數(shù)據(jù)存儲(chǔ)格式、高效數(shù)據(jù)拼接器以及并行Hash函數(shù)查找方式等多種加速方法及其硬件結(jié)構(gòu)，并設(shè)計(jì)出相應(yīng)的LZ77和LZW硬件壓縮電路[7]。但是Deflate壓縮算法有缺陷，Huffman的存儲(chǔ)結(jié)構(gòu)也需要進(jìn)行優(yōu)化。根據(jù)香農(nóng)提出的信息論中的率失真理論，可以利用這種冗余來(lái)實(shí)現(xiàn)圖像的壓縮，即在保持圖像質(zhì)量的前提下，減小圖像數(shù)據(jù)的存儲(chǔ)或傳輸所需的空間或帶寬。通過(guò)壓縮算法和技術(shù)，可以消除圖像中的冗余信息，包括空間冗余(由于圖像中的相鄰像素之間的相似性)和統(tǒng)計(jì)冗余(由于像素值分布的規(guī)律性)，從而實(shí)現(xiàn)高效的圖像壓縮。

對(duì)于GPU而言，對(duì)圖像的訪問(wèn)并不限于整張圖片。GPU具有強(qiáng)大的隨機(jī)訪問(wèn)能力，因此在處理壓縮后的圖像時(shí)，可以?xún)H改變部分區(qū)域而無(wú)需修改整個(gè)圖像[8]。為了實(shí)現(xiàn)這一點(diǎn)，壓縮后的文件需要提供每個(gè)壓縮區(qū)域的位置信息。通過(guò)解壓縮文件并根據(jù)索引找到特定位置，可以修改相應(yīng)區(qū)域的像素?cái)?shù)據(jù)。為了滿(mǎn)足這一需求，開(kāi)發(fā)了一種圖像單元的壓縮算法，該壓縮算法能夠?qū)D像的特定區(qū)域進(jìn)行快速壓縮和解壓縮操作。通過(guò)這種壓縮算法，能夠快速改變圖像的特定區(qū)域，并且有效減小傳輸帶寬的占用。

1 無(wú)損壓縮算法的設(shè)計(jì)思路

1.1 優(yōu)化Deflate壓縮算法流程圖

Deflate壓縮算法的實(shí)現(xiàn)流程如下：

1)通過(guò)使用LZ77算法，找到輸入數(shù)據(jù)中的重復(fù)片段，并用指針和長(zhǎng)度來(lái)表示這些重復(fù)片段。

2)使用哈夫曼編碼對(duì)指針和長(zhǎng)度進(jìn)行編碼，將它們轉(zhuǎn)換為更短的比特序列。

3)在進(jìn)行哈夫曼編碼之前，還會(huì)構(gòu)建一個(gè)動(dòng)態(tài)的哈夫曼樹(shù)，根據(jù)輸入數(shù)據(jù)的頻率來(lái)調(diào)整編碼方式，以實(shí)現(xiàn)更高效地壓縮。

4)將編碼后的數(shù)據(jù)和一些元數(shù)據(jù)一起打包成壓縮數(shù)據(jù)格式，并輸出壓縮結(jié)果。

通過(guò)這一系列的步驟，Deflate壓縮算法能夠?qū)崿F(xiàn)對(duì)數(shù)據(jù)的高效壓縮，以減小數(shù)據(jù)的存儲(chǔ)空間占用。

將圖像的特定區(qū)域稱(chēng)為“tile”，并實(shí)現(xiàn)了對(duì)該區(qū)域的壓縮和解壓縮功能。設(shè)置了不同大小的tile，包括4×4、8×8和16×16像素的塊，對(duì)應(yīng)的字節(jié)大小分別為64、256和1 024字節(jié)。主要目的是實(shí)現(xiàn)對(duì)圖片區(qū)域的壓縮和解壓縮，所以每次壓縮的數(shù)據(jù)量并不大，僅限于這3種字節(jié)大小。

針對(duì)Deflate壓縮算法，在進(jìn)行LZ77壓縮之后，如果按照傳統(tǒng)方式使用Huffman算法進(jìn)行壓縮，保存Huffman編碼表所需的內(nèi)存空間較大。所以Huffman再對(duì)LZ77壓縮的結(jié)果進(jìn)行壓縮提升的壓縮率不明顯。為此，對(duì)Deflate算法進(jìn)行了優(yōu)化，將LZ77和Huffman算法的執(zhí)行過(guò)程并行化，以提高壓縮效率[9]。

本算法的流程如圖1所示。

圖1 該壓縮算法流程圖

使用v4頭部格式的位圖文件。v4bmp是一種位圖文件格式的擴(kuò)展，它具有更豐富的信息和功能，特別適用于支持RGBA顏色空間的圖像。包含AGRB共4個(gè)顏色的通道。對(duì)文件的壓縮和解壓基于此文件展開(kāi)壓縮和解壓的。

算法開(kāi)始之后，對(duì)bmp文件的文件頭進(jìn)行讀取并保存，獲得了圖片的高度和寬度，然后按順序讀取所有的AGRB像素?cái)?shù)據(jù)并保存。再?gòu)谋４娴腁GRB數(shù)據(jù)中讀取一個(gè)圖像區(qū)域，對(duì)其進(jìn)行差分預(yù)測(cè)編碼之后再進(jìn)行LZ77壓縮，并且對(duì)此圖像區(qū)域進(jìn)行Huffman壓縮，比較兩個(gè)壓縮算法完成后的文件大小，判斷其是否都小于256字節(jié)，如果都小于256字節(jié)，那么就將其中較小的寫(xiě)入壓縮文件，否則就直接把原始的圖像區(qū)域?qū)懭雺嚎s文件，這樣可以獲得較小的壓縮率。

壓縮后的文件給出了圖像的寬度和高度，以便解壓時(shí)可以完整地還原原始的圖像信息。應(yīng)該注意到壓縮后的文件中的TileCount和DataInfo兩個(gè)數(shù)據(jù)，正如之前所說(shuō)的GPU具有強(qiáng)大的隨機(jī)訪問(wèn)的性能，在某些領(lǐng)域的圖像更改不需要改變所有的圖像信息。因此，當(dāng)某個(gè)圖像區(qū)域需要改變時(shí)，只需要知道壓縮后其所在壓縮圖像的位置，將其從壓縮后的文件中取出后解壓并改變像素?cái)?shù)據(jù)即可。TileCount和DataInfo便是找到壓縮后圖像數(shù)據(jù)所在位置的關(guān)鍵信息，他能夠起到索引作用。

1.2 差分預(yù)測(cè)編碼

對(duì)于給定的圖像，可以將其AGRB數(shù)據(jù)進(jìn)行區(qū)域劃分，主要介紹按照8*8像素的單位進(jìn)行劃分。這意味著將圖像劃分為許多8*8的小塊，如果需要對(duì)圖像進(jìn)行修改，也需要按照這個(gè)8*8像素的單位進(jìn)行變動(dòng)[10-11]。圖像劃分格式如圖2所示。

圖2 壓縮塊示例

每個(gè)圖像的“tile”，也就是8*8的小塊，包含了64個(gè)像素?cái)?shù)據(jù)。按照8*8像素的方式對(duì)圖像進(jìn)行讀取，這樣就可以獲取256個(gè)字節(jié)的AGRB數(shù)據(jù)。需要注意的是，這64個(gè)像素并不是按照順序排列的，而是按照?qǐng)D2所示的方式進(jìn)行讀取。采取這樣的讀取方式是因?yàn)閷?duì)于一張圖片來(lái)說(shuō)，這樣的區(qū)域內(nèi)的像素之間具有較高的相關(guān)性。因此，獲取并壓縮這樣的數(shù)據(jù)單元可以達(dá)到較好的壓縮效果。在得到一個(gè)單元的AGRB數(shù)據(jù)之后，進(jìn)行差分預(yù)測(cè)編碼。

差分預(yù)測(cè)編碼的實(shí)現(xiàn)：差分預(yù)測(cè)編碼(Differential Predictive Coding)是一種常用的無(wú)損壓縮技術(shù)，用于壓縮數(shù)字信號(hào)和圖像數(shù)據(jù)。差分預(yù)測(cè)編碼的基本思想是通過(guò)對(duì)信號(hào)或圖像中的樣本進(jìn)行預(yù)測(cè)，然后用預(yù)測(cè)值與實(shí)際值之間的差異進(jìn)行編碼。它利用了信號(hào)或圖像中的相鄰樣本之間的相關(guān)性，將差分值進(jìn)行編碼，而不是直接對(duì)原始樣本進(jìn)行編碼。

觀察到這些數(shù)據(jù)沒(méi)有重復(fù)項(xiàng)，這意味著在壓縮算法中存在很少的冗余。為了充分利用數(shù)據(jù)的特點(diǎn)，采用了差分預(yù)測(cè)編碼的方法。通過(guò)差分預(yù)測(cè)編碼，可以對(duì)每個(gè)像素值與其相鄰像素值之間的差異進(jìn)行編碼。這樣可以進(jìn)一步提高數(shù)據(jù)的冗余性，并提高壓縮算法的效率。差分預(yù)測(cè)編碼是一種算法，在該算法中，通過(guò)獲取一個(gè)像素值后，利用預(yù)測(cè)方法來(lái)預(yù)測(cè)下一個(gè)像素的值。采用了使用上一個(gè)像素的值作為本次讀取像素的預(yù)測(cè)，并計(jì)算本次讀取的像素值與上一次讀取的像素值之間的差值。這種方式可以有效地減少數(shù)據(jù)的冗余性，并實(shí)現(xiàn)對(duì)圖像數(shù)據(jù)的壓縮。通過(guò)差分預(yù)測(cè)編碼，引入了更多的重復(fù)數(shù)據(jù)，增加了數(shù)據(jù)的冗余度。然而，這種冗余度的增加使得壓縮變得更加容易。利用這些重復(fù)的數(shù)據(jù)，可以更有效地進(jìn)行壓縮，因?yàn)橹貜?fù)的數(shù)據(jù)可以被更緊湊地表示和存儲(chǔ)，從而達(dá)到更高的壓縮率。

1.3 LZ77壓縮算法

Deflate壓縮算法是由Abraham Lempel和Jacob Ziv提出，是基于字典的無(wú)損壓縮算法的基礎(chǔ)，也是無(wú)損壓縮領(lǐng)域中的主流算法。LZ77算法基于字典匹配的原理，通過(guò)尋找重復(fù)出現(xiàn)的數(shù)據(jù)序列并用指向其前一個(gè)出現(xiàn)位置和長(zhǎng)度的指針來(lái)表示，從而實(shí)現(xiàn)數(shù)據(jù)的壓縮[12-13]。

LZ77算法會(huì)先創(chuàng)建一個(gè)字典區(qū)和待編碼區(qū)。LZ77 壓縮是一個(gè)循環(huán)迭代的過(guò)程，LZ77編碼器在字典區(qū)查找，直到找到匹配的字符串。匹配字符串的開(kāi)始位置與離字典區(qū)右邊的距離稱(chēng)為“偏移值”，匹配字符串的長(zhǎng)度稱(chēng)為“匹配長(zhǎng)度”。LZ77在編碼時(shí)，會(huì)一直在字典區(qū)中搜索，直到找到最大匹配字符串，然后輸出一個(gè)三元組(off，len，char)，off表示偏移值，len表示匹配長(zhǎng)度，char為待編碼區(qū)第一個(gè)等待編碼的字符。編碼輸出為(0，0，A)，接著，文本序列會(huì)向前移動(dòng)，編碼輸出為：(1，1，A)。文本序列繼續(xù)前移一位，編碼輸出為：(0，0，B)。文本序列繼續(xù)前移一位，編碼輸出為：(3，1，B)。文本序列繼續(xù)前移，直到待編碼區(qū)為空。所以最后的文本輸出為：

(0，0，A)，(1，1，A)，(0，0，B)，(0，0，C)，(2，1，B)，(3，1，B)，(5，3，A)

經(jīng)過(guò)上面的編碼會(huì)發(fā)現(xiàn)，實(shí)際輸入的文本共有9個(gè)字節(jié)，而輸出共有7×3=21個(gè)字節(jié)，這就會(huì)導(dǎo)致壓縮后的數(shù)據(jù)膨脹，并沒(méi)有實(shí)現(xiàn)壓縮的功能。以上只是LZ77算法的基本原理，根據(jù)以上原理進(jìn)行了算法的改動(dòng)。

對(duì)于上述的流程可以發(fā)現(xiàn)，字典區(qū)越長(zhǎng)，待編碼區(qū)的字符在字典區(qū)能夠被搜索到的概率越高，也就是匹配的概率越高。然而也并非將待編碼區(qū)的字符全部替換成(off，len，char)合適。因?yàn)楸４嬉粋€(gè)off要一個(gè)字節(jié)，保存一個(gè)len要一個(gè)字節(jié)，保存一個(gè)char也要一個(gè)字節(jié)，這樣壓縮之后的數(shù)據(jù)就會(huì)變得膨脹。為此，設(shè)置一個(gè)界限，當(dāng)len的長(zhǎng)度大于2的時(shí)候再進(jìn)行編碼，否則進(jìn)行原樣輸出。這樣一來(lái)，壓縮的效率會(huì)大大提高。

同時(shí)，算法所針對(duì)的壓縮數(shù)據(jù)也就是一個(gè)圖像區(qū)域，也就是256個(gè)字節(jié)。倘若再進(jìn)行上節(jié)所講的字典區(qū)為5，待編碼區(qū)為3的算法壓縮，那么很難找到長(zhǎng)度大于2的編碼。為此將256字節(jié)的一部分作為字典區(qū)剩余的另一部分作為待編碼區(qū)，這樣就極大地增加了字符被編碼的概率。

獲得一個(gè)tile之后，先將前兩個(gè)字符設(shè)置為字典，然后再到后面的字符中取字符，在前面的字典區(qū)查找，如果找得到，那么就保存其off偏移值，len長(zhǎng)度，以及字符char。

在這里，定義以下3個(gè)uchar(unsigned char，下同)數(shù)組：

ucharcomplbuff[256]；

ucharcompsignbuff[256]；

ucharcompslbuff [256]；

其中complbuff儲(chǔ)存的是字典區(qū)匹配到的字符，compsignbuff是標(biāo)志位字符，compslbuff是存儲(chǔ)len和off的數(shù)組。對(duì)以上3個(gè)數(shù)組進(jìn)行解釋?zhuān)绻幋a區(qū)的字符在字典區(qū)沒(méi)有找到，那么就將其保存在complbuff中，并將標(biāo)志位符設(shè)置為0，表示字典區(qū)查找不到。如果能在字典區(qū)查找到該字符，并且能匹配到的長(zhǎng)度大于二，那么就對(duì)其保存off和len，并將標(biāo)志符設(shè)置為1，表示能在字典區(qū)找到。

1.4 hash表進(jìn)行對(duì)算法進(jìn)行加速

根據(jù)上述的匹配機(jī)制可知，如果直接對(duì)字典區(qū)和待編碼區(qū)進(jìn)行暴力匹配，那么算法的復(fù)雜度是O(mn)，它的算法復(fù)雜度為O(mn)，其中m是待匹配字符串的長(zhǎng)度，n是目標(biāo)字符串的長(zhǎng)度。在hash算法匹配之前，也嘗試了KMP算法進(jìn)行加速，但是效果不是很好，而hash匹配函數(shù)，可以較好地完成算法加速的功能[14-15]。

Hash加速如下：

依然是使用上面的字符為例，依舊按照上面所述的流程，將字符的前兩個(gè)保存在hash表中，當(dāng)待編碼區(qū)的2過(guò)來(lái)時(shí)，發(fā)現(xiàn)hash里面有2，其位置為2，那么待編碼區(qū)的字符2直接到字典區(qū)的2的位置進(jìn)行匹配，發(fā)現(xiàn)匹配長(zhǎng)度為1，不能作為L(zhǎng)Z77編碼的輸出，那么將待編碼區(qū)的2保存在hash表中，數(shù)據(jù)前移。

繼續(xù)重復(fù)上述的過(guò)程，發(fā)現(xiàn)字符在字典區(qū)沒(méi)有找到，那么直接將其插入到hash表中。當(dāng)下一個(gè)字符2進(jìn)行編碼時(shí)，在hash表中發(fā)現(xiàn)其有位置2、3，那么程序會(huì)執(zhí)行以下過(guò)程，首先在hash表中找字符2的位置，為2，那么就從字典區(qū)的第二個(gè)位置找起。字典區(qū)的指針向后移動(dòng)一個(gè)位置，待編碼區(qū)的指針也向后移動(dòng)一個(gè)位置，直到兩個(gè)指針位置后面的字符不再相等，就停止移動(dòng)，并退出字符匹配。同時(shí)更新hash表。該表表示將待編碼區(qū)已經(jīng)被匹配的2，2字符也插入到了hash表中。

對(duì)于已經(jīng)被匹配的字符2，2使用compslbuff []保存其位置2和長(zhǎng)度2。并設(shè)置標(biāo)志字符為1，并保存在數(shù)組compsignbuff[]中。如果要對(duì)其解壓，就讀取compsignbuff[]數(shù)組，如果值為1，就直接讀取compslbuff[]兩個(gè)字節(jié)即可，讀取的第一個(gè)字節(jié)為位置，第二個(gè)字節(jié)為長(zhǎng)度。

1.5 對(duì)off和len的優(yōu)化

對(duì)于這樣的一個(gè)字符串，a b a b a b a b a b a b a b a b a b a b a b a b a b會(huì)發(fā)現(xiàn)如果按照上面的方式進(jìn)行壓縮，那么輸出的編碼在compslbuff[]的儲(chǔ)存為[0，2][0，4][0，8]......這就導(dǎo)致每來(lái)一個(gè)a，b字符就會(huì)輸出一個(gè)位置和長(zhǎng)度，然而匹配的大小為2，這就導(dǎo)致LZ77算法對(duì)這樣的一個(gè)字符無(wú)能為力。為此需要對(duì)off和len重新設(shè)計(jì)[16]。

做出如下的改變，使用新的變量jmp和lgth。將壓縮后的文件寫(xiě)成ab[0，12]，這個(gè)的含義是在字典區(qū)的位置為0的字符開(kāi)始，這樣的字符執(zhí)行了12次。

這樣就對(duì)于off和len舍棄使用新的變量進(jìn)行壓縮和解壓縮的表示。

尋找最長(zhǎng)匹配，假如說(shuō)找到這樣的一個(gè)序列：

字典區(qū)：a b c d e f b c d e f g

待編碼區(qū)：a b c d e f g h

目前最佳匹配串：a b c d e f

根據(jù)前面設(shè)定的marethan的大小，發(fā)現(xiàn)最佳匹配串大于了morethan的值，那么就將其保存在對(duì)應(yīng)的數(shù)組之中。那么待編碼區(qū)的字符還剩下g h 兩個(gè)字符，因?yàn)槠溟L(zhǎng)度小于marethan，那么就會(huì)被算法保存在complbuff之中。最終的a b c d e f b c d e f g h a b c d e f g的編碼就會(huì)變成a b c d e f [5，5]g h [13，5]g h 。中括號(hào)前面的5表示距離前面的匹配的字符的距離，后面的5表示匹配長(zhǎng)度。會(huì)發(fā)現(xiàn)，源字符的后7個(gè)字符可以壓縮成a[8，6]。最終的編碼為a b c d e f [5，5]g h a [8，6]，這樣壓縮后的字符編碼會(huì)比之前的更小。

之所以會(huì)造成這樣的浪費(fèi)是因?yàn)樗惴ㄖ魂P(guān)心前面的這個(gè)字符，并不關(guān)心將這個(gè)字符后面的字符作為匹配，為此對(duì)算法的另一個(gè)步驟就是尋找最長(zhǎng)匹配。

當(dāng)前字符在匹配時(shí)產(chǎn)生的匹配長(zhǎng)度(簡(jiǎn)稱(chēng)當(dāng)前匹配長(zhǎng)度)和下一個(gè)字符在匹配時(shí)產(chǎn)生的長(zhǎng)度(簡(jiǎn)稱(chēng)下一個(gè)長(zhǎng)度)有以下幾種關(guān)系：

1)當(dāng)前匹配長(zhǎng)度>下一個(gè)長(zhǎng)度：

例：當(dāng)前上文為a a aa b bb c cc當(dāng)前下文為a a a b bb，當(dāng)前最佳匹配串：a a a b bb

下一個(gè)上文為：a a a b bb c cca下一個(gè)下文為：a a b bb，下一個(gè)最佳匹配串為 a a b bb

在這種情況下，下一個(gè)最佳匹配串的長(zhǎng)度小于當(dāng)前最佳匹配串的長(zhǎng)度。

2)當(dāng)前長(zhǎng)度=下一個(gè)長(zhǎng)度：

例：當(dāng)前上文為a a a b bb a a b bbc，當(dāng)前下文為a a a b bbc，當(dāng)前最佳匹配串：a a a b bb

下一個(gè)上文為：a a a b bb a a b bbc下一個(gè)下文為：a a b b b c，下一個(gè)最佳匹配串：a a b bb c

此時(shí)下一個(gè)最佳匹配串的長(zhǎng)度與當(dāng)前最佳匹配串的長(zhǎng)度相等。

3)當(dāng)前長(zhǎng)度<下一個(gè)長(zhǎng)度：

例：當(dāng)前上文為a a a b bb a a b bb c d，當(dāng)前下文為a a a b bb c d，當(dāng)前最佳匹配串：a a a b bb

下一個(gè)上文為：a a a b bb a a b bb c d a下一個(gè)下文為：a a b bb c d，下一個(gè)最佳匹配串：a a b bb c d

此時(shí)下一個(gè)最佳匹配串的串長(zhǎng)大于當(dāng)前最佳匹配串的串長(zhǎng)。

顯而易見(jiàn)的是：

①在第一種情況下，輸出下一個(gè)最佳匹配串將是多余的。

②在第二種情況下，輸出任何最佳匹配串都不會(huì)造成浪費(fèi)。

③在第三種情況下，輸出當(dāng)前最佳匹配串將是浪費(fèi)的。

因此，只需要對(duì)第三種情況進(jìn)行判斷即可。在獲取當(dāng)前最佳匹配串的同時(shí)，獲取下一個(gè)最佳匹配串，并進(jìn)行判斷。

為此，將此次的字符放入hash表中，并使用下一個(gè)字符作為待編碼區(qū)的起始字符。這樣比較此次字符作為待編碼區(qū)的首字母的匹配長(zhǎng)度和下一字符做待編碼區(qū)首字符的編碼長(zhǎng)度，這兩個(gè)長(zhǎng)度哪個(gè)長(zhǎng)就是用哪一個(gè)長(zhǎng)度保存在壓縮的數(shù)組之中。

在圖2所示的代碼中，對(duì)兩個(gè)匹配長(zhǎng)度進(jìn)行比較，得到長(zhǎng)度最長(zhǎng)的字符串。lgth1是下一字符作為待編碼區(qū)開(kāi)頭字符時(shí)得到的匹配長(zhǎng)度，lgth是此次字符作為待編碼區(qū)開(kāi)頭字符時(shí)得到的匹配長(zhǎng)度。

1.6 優(yōu)化Huffman算法

霍夫曼壓縮算法的簡(jiǎn)要步驟如下：

1)統(tǒng)計(jì)符號(hào)頻率：遍歷待壓縮的數(shù)據(jù)，統(tǒng)計(jì)每個(gè)符號(hào)(如字符、字節(jié)等)出現(xiàn)的頻率。

2)構(gòu)建霍夫曼樹(shù)：根據(jù)符號(hào)頻率構(gòu)建一顆霍夫曼樹(shù)。頻率較低的符號(hào)作為葉子節(jié)點(diǎn)，頻率較高的符號(hào)位于樹(shù)的較低層。通過(guò)合并最小頻率的節(jié)點(diǎn)來(lái)構(gòu)建樹(shù)，直到只剩下一個(gè)根節(jié)點(diǎn)。

3)分配編碼：從根節(jié)點(diǎn)開(kāi)始，沿著樹(shù)的路徑為每個(gè)符號(hào)分配唯一的二進(jìn)制編碼。一般而言，向左子樹(shù)走表示編碼為0，向右子樹(shù)走表示編碼為1。

4)生成編碼數(shù)據(jù)：遍歷原始數(shù)據(jù)，將每個(gè)符號(hào)替換為對(duì)應(yīng)的編碼，生成壓縮后的編碼數(shù)據(jù)。

5)存儲(chǔ)壓縮數(shù)據(jù)：將壓縮后的編碼數(shù)據(jù)保存到文件或傳輸給接收方。

6)解壓縮時(shí)，使用相同的霍夫曼樹(shù)和編碼表，根據(jù)編碼逐步還原原始數(shù)據(jù)。

霍夫曼壓縮算法通過(guò)根據(jù)符號(hào)頻率賦予不同長(zhǎng)度的編碼，實(shí)現(xiàn)了高頻符號(hào)使用短編碼的效果，從而在保證數(shù)據(jù)完整性的前提下，實(shí)現(xiàn)了較高的數(shù)據(jù)壓縮率。它廣泛應(yīng)用于文件壓縮、圖像壓縮、音頻壓縮等領(lǐng)域。

以下是Huffman壓縮編碼的一個(gè)舉例：

假設(shè)我們有以下字符串需要進(jìn)行壓縮：“ABBCCCDDDDEEEEE”。

1)統(tǒng)計(jì)符號(hào)頻率：統(tǒng)計(jì)每個(gè)符號(hào)的出現(xiàn)頻率。

‘A’：1

‘B’：2

‘C’：3

‘D’：4

‘E’：5

2)構(gòu)建霍夫曼樹(shù)：根據(jù)符號(hào)頻率構(gòu)建霍夫曼樹(shù)。

從最小頻率開(kāi)始構(gòu)建樹(shù)：

①合并頻率為1的‘A’和‘B’，得到新節(jié)點(diǎn)‘AB’：頻率=3

②合并頻率為3的‘AB’和‘C’，得到新節(jié)點(diǎn)‘ABC’：頻率=6

③合并頻率為4的‘D’和‘ABC’，得到新節(jié)點(diǎn)‘DABC’：頻率=10

④合并頻率為5的‘E’和‘DABC’，得到新節(jié)點(diǎn)‘E(DABC)’：頻率=15

得到以下霍夫曼樹(shù)：

3)分配編碼：從根節(jié)點(diǎn)開(kāi)始，沿著左子樹(shù)走為0，沿著右子樹(shù)走為1，為每個(gè)符號(hào)分配編碼。

‘A’：編碼為：0000

‘B’：編碼為：0001

‘C’：編碼為：001

‘D’：編碼為：01

‘E’：編碼為：1

4)生成編碼數(shù)據(jù)：使用編碼表，將原始數(shù)據(jù)替換為對(duì)應(yīng)的編碼。

原始數(shù)據(jù)：“ABBCCCDDDDEEEEE”

替換為編碼：“00000001_00010010_01001010_1010 1111_11”

通過(guò)霍夫曼壓縮算法，原始字符保存下來(lái)共需要15個(gè)字節(jié)，現(xiàn)在只需要5個(gè)字節(jié)就可以。現(xiàn)在原始字符串被壓縮為較短的編碼字符串，從而實(shí)現(xiàn)了數(shù)據(jù)的壓縮。在解壓縮時(shí)，使用相同的霍夫曼樹(shù)和編碼表，根據(jù)編碼逐步還原原始數(shù)據(jù)。

主要是改進(jìn)Huffman的存儲(chǔ)結(jié)構(gòu)，由于是對(duì)某一圖像區(qū)域進(jìn)行壓縮，因此這個(gè)區(qū)域的字節(jié)數(shù)不會(huì)太大，對(duì)于8*8的tile塊，設(shè)定的是256字節(jié)。如果根據(jù)上面的分析可知，壓縮和解壓縮都需要得到字符出現(xiàn)的概率，以便構(gòu)建Huffman樹(shù)和獲得Huffman編碼。但是由于如果保存一個(gè)字符，一個(gè)出現(xiàn)的概率，那么如果256個(gè)字節(jié)中出現(xiàn)了N種字符，那么就需要至少2N的字節(jié)保存Huffman字符頻率，如果N大于128，那么編碼表都比原字符要大了，這樣就造成了浪費(fèi)。于是設(shè)置一個(gè)標(biāo)記位，在統(tǒng)計(jì)到2N+0.5N>256時(shí)，就不在使用Huffman壓縮算法，從而保證了壓縮速度。同時(shí)計(jì)算出Huffman文件的大小，如果壓縮后的數(shù)據(jù)大于tile的大小，直接給(*outputsize)賦予一個(gè)大于tile的值。

2 壓縮算法的FPGA設(shè)計(jì)

2.1 FPGA平臺(tái)

該算法實(shí)現(xiàn)平臺(tái)是 Xillinx 的 VivadoHLS2019.1 高級(jí)綜合工具。接下來(lái)主要介紹總體設(shè)計(jì)結(jié)構(gòu)的實(shí)現(xiàn)和優(yōu)化、功能仿真結(jié)果和時(shí)序仿真結(jié)果。將前幾章闡述的算法結(jié)構(gòu)進(jìn)行實(shí)現(xiàn)和優(yōu)化，通過(guò)添加C仿真驗(yàn)證算法的正確性，在此基礎(chǔ)上進(jìn)行硬件電路的實(shí)現(xiàn)和優(yōu)化[17-18]。在 HLS 工具中用到的FPGA是Xilinx的Zynq UltraScale+ MPSoC(多處理器系統(tǒng)級(jí)芯片)系列(xczu3cg-sfvc784-1-i)[19-20]。將壓縮設(shè)計(jì)的結(jié)構(gòu)直接通過(guò)高級(jí)綜合工具默認(rèn)的約束進(jìn)行綜合，得到的時(shí)延結(jié)果如圖3所示。

圖3 時(shí)延結(jié)果

2.2 壓縮算法的FPGA功能仿真

對(duì)VIVADO HLS生成的電路進(jìn)行功能仿真。設(shè)置輸入的塊數(shù)據(jù)為：

Unsigned char input[256]={

1,5,1,9,2,0,3,8,3,3,8,4,4,7,8,111,

8,1,4,4,3,8,9,66,74,47,1,3,7,9,5,1,

32,38,47,43,40,1,1,1,1,1,1,2,2,38,1,5,

1,9,2,0,3,8,3,3,8,4,4,7,8,111,1,6,

6,7,8,1,6,9,66,74,47,1,3,7,32,38,47,43,

40,1,1,1,1,1,2,2,3,7,8,100,102,10,15,222,

33,8,65,60,63,44,52,12,14,18,19,1,5,1,9,2,

0,3,8,3,3,8,4,4,7,8,111,1,6,6,7,8,

1,6,9,74,47,1,3,72,7,3,5,9,5,1,32,38,

47,43,40,1,1,1,1,1,1,2,2,3,7,8,1,5,

1,9,2,0,3,8,3,3,8,4,4,7,8,111,1,6,

6,7,8,1,6,9,4,4,3,8,1,3,7,8,2,7,

3,5,9,5,1,32,38,47,43,40,1,1,1,1,1,1,

1,5,1,9,2,0,3,8,3,3,8,4,4,7,8,111,

1,6,6,7,8,1,6,9,4,4,3,8,9,6,78,47,

1,3,7,8,2,7,3,5,9,5,1,32,38,47,43,40}

壓縮后的數(shù)據(jù)為：

nsigned char refer[256]={

20,118,82,1,5,1,9,1,4,251,71,189,25,8,217,1,

255,2,5,0,254,0,41,241,2,99,187,30,207,247,251,3,

4,255,251,46,216,254,42,210,0,6,250,253,4,252,214,0,

253,7,252,5,248,1,7,29,250,7,39,218,29,219,0,37,

227,255,252,107,152,2,248,7,6,3,254,36,230,239,251,2,

1,6,1,255,27,4,3,62,193,4,4,58,193,44,210,7,

50,243,223,246,253,0,149,3,73,189,36,98,122,94,208,245,

66,254,193,2,2,255,8,39,217,4,0,2,0,0,34,64,

32,0,16,36,85,14,194,15,183,180,65,18,210,1,2,11,

2,28,5,14,2,52,3,36,3,11,2,50,5,48,3,28,

5,65,2,93,2,88,5,27,2,36,3,72,3,98,3,85,

6,46,2,50,5,119,2,49,3,61,2,113,6,112,3,93,

2,138,6,179,2,139,3,36,3,72,2,98,4,85,5,11,

2,50,5,49,3,113,6,112,3,104,2,138,6,139,3,0,

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

首先利用C語(yǔ)言進(jìn)行仿真，得到的結(jié)果是正確的，然后進(jìn)行FPGA仿真。

壓縮電路的功能仿真結(jié)果如圖4和圖5所示。從圖4和5可以看出功能仿真完成正確。

圖4 對(duì)測(cè)試數(shù)據(jù)1的功能仿真結(jié)果

圖5 對(duì)測(cè)試數(shù)據(jù)1的功能仿真結(jié)果

2.3 解壓縮算法的FPGA功能仿真

對(duì)于C仿真，使用的測(cè)試輸入數(shù)據(jù)如下：

Unsigned char input[256]={

20,118,82,1,5,1,9,1,4,251,71,189,25,8,217,1,

255,2,5,0,254,0,41,241,2,99,187,30,207,247,251,3,

4,255,251,46,216,254,42,210,0,6,250,253,4,252,214,0,

253,7,252,5,248,1,7,29,250,7,39,218,29,219,0,37,

227,255,252,107,152,2,248,7,6,3,254,36,230,239,251,2,

1,6,1,255,27,4,3,62,193,4,4,58,193,44,210,7,

50,243,223,246,253,0,149,3,73,189,36,98,122,94,208,245,

66,254,193,2,2,255,8,39,217,4,0,2,0,0,34,64,

32,0,16,36,85,14,194,15,183,180,65,18,210,1,2,11,

2,28,5,14,2,52,3,36,3,11,2,50,5,48,3,28,

5,65,2,93,2,88,5,27,2,36,3,72,3,98,3,85,

6,46,2,50,5,119,2,49,3,61,2,113,6,112,3,93,

2,138,6,179,2,139,3,36,3,72,2,98,4,85,5,11,

2,50,5,49,3,113,6,112,3,104,2,138,6,139,3}

解壓后的數(shù)據(jù)如下：

Unsigned char refer[256]={

1,5,1,9,2,0,3,8,3,3,8,4,4,7,8,111,

8,1,4,4,3,8,9,66,74,47,1,3,7,9,5,1,

32,38,47,43,40,1,1,1,1,1,1,2,2,38,1,5,

1,9,2,0,3,8,3,3,8,4,4,7,8,111,1,6,

6,7,8,1,6,9,66,74,47,1,3,7,32,38,47,43,

40,1,1,1,1,1,2 ,2,3,7,8,100,102,10,15,222,

33,8,65,60,63,44,52,12,14,18,19,1,5,1,9,2,

0,3,8,3,3,8,4,4,7,8,111,1,6,6,7,8,

1,6,9,74,47,1,3,72,7,3,5,9,5,1,32,38,

47,43,40,1,1,1,1,1,1,2,2,3,7,8,1,5,

1,9,2,0,3,8,3,3,8,4,4,7,8,111,1,6,

6,7,8,1,6,9,4,4,3,8,1,3,7,8,2,7,

3,5,9,5,1,32,38,47,43,40,1,1,1,1,1,1,

1,5,1,9,2,0,3,8,3,3,8,4,4,7,8,111,

1,6,6,7,8,1,6,9,4,4,3,8,9,66,78,47,

1,3,7,8,2,7,3,5,9,5,1,32,38,47,43,40}

解壓電路的功能仿真如圖6和圖7所示。

圖6 解壓?jiǎn)卧獙?duì)測(cè)試數(shù)據(jù)1的功能仿真結(jié)果

圖7 解壓?jiǎn)卧獙?duì)測(cè)試數(shù)據(jù)1的功能仿真結(jié)果

2.4 時(shí)序仿真結(jié)果

HLS導(dǎo)出RTL代碼后進(jìn)行了時(shí)序仿真，在這里設(shè)置的時(shí)鐘頻率是100 MHz。

由圖8可以看出，最壞路徑的建立時(shí)間裕量為2.679 ns，那么可以估計(jì)出單元的最高時(shí)鐘頻率約為136 MHz。

圖8 壓縮單元的時(shí)序仿真結(jié)果

同理對(duì)于解壓縮單元，最壞路徑的建立時(shí)間裕量為6.264 ns，同樣也可以估計(jì)出解壓縮單元的最高時(shí)鐘頻率約為267 MHz。

3 測(cè)試結(jié)果

使用了33張測(cè)試圖片，在Linux系統(tǒng)下對(duì)本算法進(jìn)行了測(cè)試，測(cè)試的圖片和壓縮率如表1所示。

表1 圖片和壓縮率表

在Linux系統(tǒng)下對(duì)Deflate算法進(jìn)行了測(cè)試，測(cè)試的圖片和壓縮率如表2所示。

表2 圖片和壓縮率表

接下來(lái)對(duì)該算法與Deflate算法進(jìn)行相應(yīng)的比較?；谶M(jìn)行的圖片壓縮測(cè)試結(jié)果，本算法在處理那些具有豐富細(xì)節(jié)的圖片時(shí)，其壓縮性能表現(xiàn)相對(duì)較差。然而，當(dāng)處理那些相對(duì)平坦且細(xì)節(jié)不太豐富的圖片時(shí)，該算法展現(xiàn)出了較為出色的壓縮效果。而對(duì)于Deflate算法來(lái)說(shuō)，其壓縮率相對(duì)集中，對(duì)細(xì)節(jié)豐富的圖片壓縮得較好，然而平均壓縮率不如該算法。

4 結(jié)束語(yǔ)

使用C語(yǔ)言實(shí)現(xiàn)了一種針對(duì)圖像的區(qū)域壓縮算法，并采用Huffman算法和LZ77算法分別對(duì)壓縮區(qū)域進(jìn)行壓縮。通過(guò)選擇較小的壓縮文件來(lái)實(shí)現(xiàn)更高的壓縮率。為了驗(yàn)證算法的功能可實(shí)現(xiàn)性使用VIVADO HLS工具進(jìn)行功能仿真驗(yàn)證算法在不同壓縮區(qū)域大小下的壓縮和解壓功能性，從而確保算法在硬件實(shí)現(xiàn)中的功能正確性，為圖像壓縮領(lǐng)域的進(jìn)一步研究和應(yīng)用提供了有力支持。