Lepton 無損壓縮原理及性能分析
作者 ｜ vivo 互聯(lián)網(wǎng)數(shù)據(jù)庫團(tuán)隊(duì)- Li Shihai
本文主要介紹無損壓縮圖片的概要流程和原理，以及Lepton無損壓縮在前期調(diào)研中發(fā)現(xiàn)的問題和解決方案。
一、從一個(gè)游戲開始
1.1 游戲找茬
請拿出你的秒表計(jì)時(shí)，在15秒時(shí)間內(nèi)找出下面圖片的差異。
時(shí)間到了，你發(fā)現(xiàn)兩張圖片的差異了嗎？
二、智者的成長
在上面的游戲中，你可能你并沒有發(fā)現(xiàn)兩張圖片間有任何差異，而實(shí)際上它們一張是3.7MB的jpg格式的原圖，另外一張是大小為485KB的jpg格式壓縮圖片，只是大小不同。你可能會(huì)有些生氣，憤憤不平到這是欺騙，然而聰明的你很快在大腦中產(chǎn)生了一連串的疑問，這些問號(hào)讓你層層揭開游戲的面紗，不在為愚弄而悔恨，反而從新知中獲得快樂。
2.1 蘇格拉底助產(chǎn)術(shù)
- 上面圖片為何變小了呢？
- 丟失了的信息去哪了呢？
- 為什么圖片質(zhì)量下降了，我卻看不出來呢？
- 我還能將它變的更小嗎？
- 我能將它還原成原來的大小嗎？
- 為什么要壓縮我的圖片？
上面圖片為何變小了？圖片從3.7MB變成485KB是因?yàn)槲沂褂昧藞D片查看工具將原圖另存成一張新的圖片，在另存的過程中，有一個(gè)圖片質(zhì)量選擇的參數(shù)，我選擇了質(zhì)量最低，保存后便生成了一張更小的圖片?？墒菆D片質(zhì)量下降了，為什么看不出來呢？這就需要了解圖片壓縮的原理。
2.2 探求表象背后的故事
利用人眼的弱點(diǎn)。
人的視網(wǎng)膜上有兩種細(xì)胞，視錐細(xì)胞和視桿細(xì)胞。視錐細(xì)胞用來感知顏色，視桿細(xì)胞用來感知亮度。而相對于顏色，我們對明暗的感知更明顯。
因此可以采取對顏色信息進(jìn)行壓縮來減小圖片的大小。
所以我們在圖片壓縮前會(huì)進(jìn)行顏色空間的變換，JPEG圖片通常會(huì)變換成YCbCr顏色空間，Y代表亮度，Cb藍(lán)色色彩度，Cr紅色色彩度，變換后我們更容易處理色彩部分。然后我們將一張圖片切成一塊塊8*8的像素塊，然后使用離散余弦轉(zhuǎn)換算法(DCT)計(jì)算出高頻區(qū)和低頻區(qū)。
由于人眼對高頻區(qū)的復(fù)雜信息不敏感，因此可以對這一部分進(jìn)行壓縮，這個(gè)過程叫量化。最后再將新的文件進(jìn)行打包。這個(gè)流程下來就完成了圖片的壓縮。
基本流程如下圖：
JPEG壓縮有損。
在上面的流程中，在預(yù)測模塊的顏色空間轉(zhuǎn)換后，通過舍棄部分顏色濃度信息，提高壓縮率。常見選項(xiàng)為4:2:0，經(jīng)過這一步后原來需要8個(gè)數(shù)字表示的信息，現(xiàn)在只需要2個(gè)，直接拋棄了75%的Cb Cr信息，然而這一步驟是不可逆的，也就造成了圖片壓縮的有損。此外在熵編碼模塊，會(huì)進(jìn)一步使用行程長度編碼或Huffman編碼進(jìn)一步對圖片信息進(jìn)行壓縮，而這一部分的壓縮是無損的，是可逆的。
（YCbCr空間轉(zhuǎn)換）
霍夫曼編碼原理如下：
假如待編碼的字符總共38個(gè)符號(hào)數(shù)據(jù)，對其進(jìn)行統(tǒng)計(jì)，得到的符號(hào)和對應(yīng)頻度如下表：
符號(hào) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
頻度 | 10 | 1 | 1 | 11 | 1 | 1 | 8 | 5 |
首先，對所有符號(hào)按照頻數(shù)大小排序，排序后如下圖：
符號(hào) | 0 | 1 | 2 | 3 | 7 | 6 | 0 | 3 |
頻度 | 1 | 1 | 1 | 1 | 5 | 8 | 10 | 11 |
然后，選擇兩個(gè)頻數(shù)最小的作為葉子節(jié)點(diǎn)，頻數(shù)最小的作為左子節(jié)點(diǎn)，另外一個(gè)作為右子節(jié)點(diǎn)，根節(jié)點(diǎn)為兩個(gè)葉子節(jié)點(diǎn)的頻數(shù)之和。
（Huffman 樹）
經(jīng)過上面的步驟，就形成了一顆Huffman樹，Huffman編碼經(jīng)常用在無損壓縮中，其基本思想是用短的編碼表示出現(xiàn)頻率高的字符，用長的編碼來表示出現(xiàn)頻率低的字符，這使得編碼之后的字符串的平均長度、長度的期望值降低，從而實(shí)現(xiàn)壓縮的目的。
三、故事的主角 Lepton
不完美。
上面的JPEG壓縮雖然降低了圖片的大小且質(zhì)量良好以至于人眼很難分辨其差異，但是由于是有損的壓縮，圖片質(zhì)量不能恢復(fù)到原來的品質(zhì)，而且實(shí)際上此時(shí)的jpg圖片仍有壓縮空間。
Lepton便可以在JPEG基礎(chǔ)上進(jìn)一步對圖片進(jìn)行無損壓縮。
3.1 為什么選擇 Lepton
與lepton類似的壓縮工具還有jpegcan，MozJPEG，PackJPG，PAQ8PX。但這些工具都或多或少有一些缺陷，使得不如lepton更加適合工業(yè)生產(chǎn)。
比如PackJPG需要按照全局排序的順序重新排列文件中的所有壓縮像素值。這意味著解壓縮是單線程的，同時(shí)需要整個(gè)圖像放入內(nèi)存中導(dǎo)致處理圖片的時(shí)延較高吞吐較低。
下圖是lepton論文中對幾款工具的比較：
3.2 Lepton進(jìn)行了哪些優(yōu)化。
- 首先在算法上Lepton將圖像分為兩部分header和圖片數(shù)據(jù)本身，header使用DEFLATE進(jìn)行無損壓縮，圖片本身使用算數(shù)編碼替換霍爾曼編碼進(jìn)行無損壓縮。由于JPEG使用Huffman編碼，這使得利用多線程比較困難，Lepton使用"Huffman切換詞"進(jìn)行了改進(jìn)。
- 其次Lepton使用了一個(gè)復(fù)雜的自適應(yīng)概率模型，這個(gè)模型是通過在大量的野外圖像上進(jìn)行測試而開發(fā)的。該模型的目標(biāo)是對每個(gè)系數(shù)的值產(chǎn)生最準(zhǔn)確的預(yù)測，從而產(chǎn)生更小的文件；在工程上允許多線程并發(fā)處理，允許分塊跨多個(gè)服務(wù)器分布式處理，流的方式逐行處理有效的控制了內(nèi)存，同時(shí)還保證了數(shù)據(jù)讀取和輸出的安全。
正是Lepton在上述關(guān)鍵問題的優(yōu)化，使得它目前可以很好的在生產(chǎn)環(huán)境中使用。
3.3 Lepton在vivo存儲(chǔ)中的探索
預(yù)期收益：
目前對象存儲(chǔ)其中的一個(gè)集群大約有100PB數(shù)據(jù)，其中圖片數(shù)據(jù)大概占70%, 而圖片中有90%的圖片都是jpeg類型圖片，如果按照平均23%的壓縮率，那么 100PB * 70% * 90% * 23% = 14.5PB，將實(shí)現(xiàn)大約14.5PB的成本節(jié)約。
同時(shí)由于是無損壓縮，很好的保證了用戶的使用體驗(yàn)。當(dāng)前l(fā)epton壓縮功能的設(shè)計(jì)如下圖：
當(dāng)前遇到的挑戰(zhàn)：
- lepton壓縮與解壓縮對服務(wù)器的計(jì)算性能要求較高、消耗較大。
- 期望充分利用空閑服務(wù)器CPU資源，達(dá)到降本增效的目的。
- 面對潮汐現(xiàn)象具備動(dòng)態(tài)擴(kuò)縮容的能力。
當(dāng)前面臨的主要問題：
- 當(dāng)前大部分圖片的大小在4M-5M， 經(jīng)過測試對于4M-5M大小的文件壓縮時(shí)延在1s左右的情況下，需要服務(wù)器至少16核心、承載5QPS。此時(shí)每個(gè)核心的利用率都在95%以上?？梢?Lepton的壓縮對計(jì)算性能要求很高。當(dāng)前常見的解決方案是使用FPGA卡進(jìn)行硬件加速、以及橫向擴(kuò)容大量的計(jì)算節(jié)點(diǎn)。FPGA的使用會(huì)增加硬件成本，降低壓縮帶來的成本收益。
解決方案：
- 為了解決上述問題及挑戰(zhàn)，我們嘗試采用物理服務(wù)器和Kubernetes混合部署的方式解決計(jì)算資源的使用和動(dòng)態(tài)擴(kuò)所容的問題，架構(gòu)示意圖如下：
對于物理服務(wù)器的管理以及擴(kuò)所容通過服務(wù)的注冊于發(fā)現(xiàn)進(jìn)行彈性擴(kuò)所容、通過此cgroup/Taskset等方式對進(jìn)程的cpu使用進(jìn)行管理。同時(shí)對接使用Kubernetes以容器的方式進(jìn)行管理、容器的靈活性更加適合這種計(jì)算型的服務(wù)。
3.4 性能評測
無論是同步壓縮，還是異步壓縮，通常更加關(guān)注圖片讀取的延時(shí)。大量的圖片讀取會(huì)給服務(wù)器帶來較大的壓力，壓力主要來自于圖片的解壓計(jì)算。為了提高解壓縮效率，以及充分利用公司的資源，我們未來將lepton壓縮服務(wù)以獨(dú)立的服務(wù)模式分布于cpu空閑的服務(wù)器，可以按照資源空閑程度，空閑時(shí)間，充分利用資源的峰谷來提高計(jì)算性能。
壓測數(shù)據(jù)：
我們選取了不同大小的圖片文件，在單機(jī)環(huán)境下進(jìn)行了壓縮與解壓縮測試，測試結(jié)果如下圖：
壓縮比平均保持在22%左右。
上圖是不同大小的文件壓縮與解壓縮時(shí)間比例圖，橙色是解壓時(shí)間，藍(lán)色是壓縮時(shí)間。
上圖是不同大小的圖片，在32線程并發(fā)，每個(gè)線程處理100個(gè)文件的測試數(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的無損壓縮能夠提供比較高的壓縮比，同時(shí)不影響用戶的圖片質(zhì)量和使用體驗(yàn)、在大數(shù)據(jù)量的場景下會(huì)獲得比較明顯的收益。
不足之處是對計(jì)算性能要求較高、只支持jpeg類型的圖片。對于性能的要求行業(yè)內(nèi)也都有比較成熟的解決方案，例如上文提到的FPGA和彈性計(jì)算方案。關(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圖像云存儲(chǔ)研究》
- 《JPEG-Lepton壓縮技術(shù)關(guān)鍵模塊VLSI結(jié)構(gòu)設(shè)計(jì)研究》
