玄幻小说排行榜,完美世界

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案

Lepton無損壓縮原理及性能分析

作者｜ vivo 互聯(lián)網(wǎng)數(shù)據(jù)庫團隊- Li Shihai

本文主要介紹無損壓縮圖片的概要流程和原理，以及Lepton無損壓縮在前期調(diào)研中發(fā)現(xiàn)的問題和解決方案。

一、從一個游戲開始

1.1 游戲找茬

請拿出你的秒表計時，在15秒時間內(nèi)找出下面圖片的差異。

時間到了，你發(fā)現(xiàn)兩張圖片的差異了嗎？

二、智者的成長

在上面的游戲中，你可能你并沒有發(fā)現(xiàn)兩張圖片間有任何差異，而實際上它們一張是3.7MB的jpg格式的原圖，另外一張是大小為485KB的jpg格式壓縮圖片，只是大小不同。你可能會有些生氣，憤憤不平到這是欺騙，然而聰明的你很快在大腦中產(chǎn)生了一連串的疑問，這些問號讓你層層揭開游戲的面紗，不在為愚弄而悔恨，反而從新知中獲得快樂。

2.1 蘇格拉底助產(chǎn)術(shù)

上面圖片為何變小了呢？
丟失了的信息去哪了呢？
為什么圖片質(zhì)量下降了，我卻看不出來呢？
我還能將它變的更小嗎？
我能將它還原成原來的大小嗎？
為什么要壓縮我的圖片？

上面圖片為何變小了？圖片從3.7MB變成485KB是因為我使用了圖片查看工具將原圖另存成一張新的圖片，在另存的過程中，有一個圖片質(zhì)量選擇的參數(shù)，我選擇了質(zhì)量最低，保存后便生成了一張更小的圖片?？墒菆D片質(zhì)量下降了，為什么看不出來呢？這就需要了解圖片壓縮的原理。

2.2 探求表象背后的故事

利用人眼的弱點。

人的視網(wǎng)膜上有兩種細胞，視錐細胞和視桿細胞。視錐細胞用來感知顏色，視桿細胞用來感知亮度。而相對于顏色，我們對明暗的感知更明顯。

因此可以采取對顏色信息進行壓縮來減小圖片的大小。

所以我們在圖片壓縮前會進行顏色空間的變換，JPEG圖片通常會變換成YCbCr顏色空間，Y代表亮度，Cb藍色色彩度，Cr紅色色彩度，變換后我們更容易處理色彩部分。然后我們將一張圖片切成一塊塊8*8的像素塊，然后使用離散余弦轉(zhuǎn)換算法(DCT)計算出高頻區(qū)和低頻區(qū)。

由于人眼對高頻區(qū)的復(fù)雜信息不敏感，因此可以對這一部分進行壓縮，這個過程叫量化。最后再將新的文件進行打包。這個流程下來就完成了圖片的壓縮。

基本流程如下圖：

JPEG壓縮有損。

在上面的流程中，在預(yù)測模塊的顏色空間轉(zhuǎn)換后，通過舍棄部分顏色濃度信息，提高壓縮率。常見選項為4:2:0，經(jīng)過這一步后原來需要8個數(shù)字表示的信息，現(xiàn)在只需要2個，直接拋棄了75%的Cb Cr信息，然而這一步驟是不可逆的，也就造成了圖片壓縮的有損。此外在熵編碼模塊，會進一步使用行程長度編碼或Huffman編碼進一步對圖片信息進行壓縮，而這一部分的壓縮是無損的，是可逆的。

（YCbCr空間轉(zhuǎn)換）

霍夫曼編碼原理如下：

假如待編碼的字符總共38個符號數(shù)據(jù)，對其進行統(tǒng)計，得到的符號和對應(yīng)頻度如下表：

符號	0	1	2	3	4	5	6	7
頻度	10	1	1	11	1	1	8	5

首先，對所有符號按照頻數(shù)大小排序，排序后如下圖：

符號	0	1	2	3	7	6	0	3
頻度	1	1	1	1	5	8	10	11

然后，選擇兩個頻數(shù)最小的作為葉子節(jié)點，頻數(shù)最小的作為左子節(jié)點，另外一個作為右子節(jié)點，根節(jié)點為兩個葉子節(jié)點的頻數(shù)之和。

（Huffman 樹）

經(jīng)過上面的步驟，就形成了一顆Huffman樹，Huffman編碼經(jīng)常用在無損壓縮中，其基本思想是用短的編碼表示出現(xiàn)頻率高的字符，用長的編碼來表示出現(xiàn)頻率低的字符，這使得編碼之后的字符串的平均長度、長度的期望值降低，從而實現(xiàn)壓縮的目的。

三、故事的主角 Lepton

不完美。

上面的JPEG壓縮雖然降低了圖片的大小且質(zhì)量良好以至于人眼很難分辨其差異，但是由于是有損的壓縮，圖片質(zhì)量不能恢復(fù)到原來的品質(zhì)，而且實際上此時的jpg圖片仍有壓縮空間。

Lepton便可以在JPEG基礎(chǔ)上進一步對圖片進行無損壓縮。

3.1 為什么選擇 Lepton

與lepton類似的壓縮工具還有jpegcan，MozJPEG，PackJPG，PAQ8PX。但這些工具都或多或少有一些缺陷，使得不如lepton更加適合工業(yè)生產(chǎn)。

比如PackJPG需要按照全局排序的順序重新排列文件中的所有壓縮像素值。這意味著解壓縮是單線程的，同時需要整個圖像放入內(nèi)存中導(dǎo)致處理圖片的時延較高吞吐較低。

下圖是lepton論文中對幾款工具的比較：

3.2 Lepton進行了哪些優(yōu)化。

首先在算法上Lepton將圖像分為兩部分header和圖片數(shù)據(jù)本身，header使用DEFLATE進行無損壓縮，圖片本身使用算數(shù)編碼替換霍爾曼編碼進行無損壓縮。由于JPEG使用Huffman編碼，這使得利用多線程比較困難，Lepton使用"Huffman切換詞"進行了改進。
其次Lepton使用了一個復(fù)雜的自適應(yīng)概率模型，這個模型是通過在大量的野外圖像上進行測試而開發(fā)的。該模型的目標(biāo)是對每個系數(shù)的值產(chǎn)生最準(zhǔn)確的預(yù)測，從而產(chǎn)生更小的文件；在工程上允許多線程并發(fā)處理，允許分塊跨多個服務(wù)器分布式處理，流的方式逐行處理有效的控制了內(nèi)存，同時還保證了數(shù)據(jù)讀取和輸出的安全。

正是Lepton在上述關(guān)鍵問題的優(yōu)化，使得它目前可以很好的在生產(chǎn)環(huán)境中使用。

3.3 Lepton在vivo存儲中的探索

預(yù)期收益：

目前對象存儲其中的一個集群大約有100PB數(shù)據(jù)，其中圖片數(shù)據(jù)大概占70%, 而圖片中有90%的圖片都是jpeg類型圖片，如果按照平均23%的壓縮率，那么 100PB * 70% * 90% * 23% = 14.5PB，將實現(xiàn)大約14.5PB的成本節(jié)約。

同時由于是無損壓縮，很好的保證了用戶的使用體驗。當(dāng)前l(fā)epton壓縮功能的設(shè)計如下圖：

當(dāng)前遇到的挑戰(zhàn)：

lepton壓縮與解壓縮對服務(wù)器的計算性能要求較高、消耗較大。
期望充分利用空閑服務(wù)器CPU資源，達到降本增效的目的。
面對潮汐現(xiàn)象具備動態(tài)擴縮容的能力。

當(dāng)前面臨的主要問題：

當(dāng)前大部分圖片的大小在4M-5M，經(jīng)過測試對于4M-5M大小的文件壓縮時延在1s左右的情況下，需要服務(wù)器至少16核心、承載5QPS。此時每個核心的利用率都在95%以上?？梢?Lepton的壓縮對計算性能要求很高。當(dāng)前常見的解決方案是使用FPGA卡進行硬件加速、以及橫向擴容大量的計算節(jié)點。FPGA的使用會增加硬件成本，降低壓縮帶來的成本收益。

解決方案：

為了解決上述問題及挑戰(zhàn)，我們嘗試采用物理服務(wù)器和Kubernetes混合部署的方式解決計算資源的使用和動態(tài)擴所容的問題，架構(gòu)示意圖如下：

對于物理服務(wù)器的管理以及擴所容通過服務(wù)的注冊于發(fā)現(xiàn)進行彈性擴所容、通過此cgroup/Taskset等方式對進程的cpu使用進行管理。同時對接使用Kubernetes以容器的方式進行管理、容器的靈活性更加適合這種計算型的服務(wù)。

3.4 性能評測

無論是同步壓縮，還是異步壓縮，通常更加關(guān)注圖片讀取的延時。大量的圖片讀取會給服務(wù)器帶來較大的壓力，壓力主要來自于圖片的解壓計算。為了提高解壓縮效率，以及充分利用公司的資源，我們未來將lepton壓縮服務(wù)以獨立的服務(wù)模式分布于cpu空閑的服務(wù)器，可以按照資源空閑程度，空閑時間，充分利用資源的峰谷來提高計算性能。

壓測數(shù)據(jù)：

我們選取了不同大小的圖片文件，在單機環(huán)境下進行了壓縮與解壓縮測試，測試結(jié)果如下圖：

壓縮比平均保持在22%左右。

上圖是不同大小的文件壓縮與解壓縮時間比例圖，橙色是解壓時間，藍色是壓縮時間。

上圖是不同大小的圖片，在32線程并發(fā)，每個線程處理100個文件的測試數(shù)據(jù)。

四、圖片壓縮的常見問題

4.1 通過文件格式區(qū)分有損和無損壓縮

有損壓縮格式	JPEG、JPG、WMF、等
無損壓縮格式	BMP、PCX、TIFF、GIF、TGA、PNG、RAW等

4.2 常見的無損壓縮算法

無損壓縮	Run-Length Encoding 游程編碼、Shannon-Fano Coding、Huffman Coding、Arithmetic Coding、Burrow-Length Transform 布魯斯-惠勒變換

五、總結(jié)

Lepton的無損壓縮能夠提供比較高的壓縮比，同時不影響用戶的圖片質(zhì)量和使用體驗、在大數(shù)據(jù)量的場景下會獲得比較明顯的收益。

不足之處是對計算性能要求較高、只支持jpeg類型的圖片。對于性能的要求行業(yè)內(nèi)也都有比較成熟的解決方案，例如上文提到的FPGA和彈性計算方案。關(guān)鍵在于根據(jù)企業(yè)需求選擇合理的方案。

引用：

《The Design, Implementation, and Deployment of a System to Transparently Compress Hundreds of Petabytes of Image Files For a File-Storage Service》
《基于深度學(xué)習(xí)的JPEG圖像云存儲研究》
《JPEG-Lepton壓縮技術(shù)關(guān)鍵模塊VLSI結(jié)構(gòu)設(shè)計研究》

當(dāng)前題目：Lepton無損壓縮原理及性能分析
本文鏈接：http://m.fisionsoft.com.cn/article/cohcjho.html

新聞中心

一、從一個游戲開始