如何將影象壓縮10倍？阿里工程師有個大膽的想法

來自：阿里機器智慧

小嘰導讀：如何將單張圖片由120k 壓縮到了平均13k？阿里工程師做到了！並且將歐式距離計算平均耗時做到9微秒。今天，阿里巴巴技術專家蕭冷將公開從初步嘗試到最佳化的過程，希望對你有所幫助。

背景

在手機上使用者隨手拍一張衣服的照片，去找類似圖片的需求比較明顯，以圖搜圖專案目的就是滿足使用者的這部分需求。

該專案初步預計5個類目，每個類目500萬圖片用於檢索。經過特徵提取，每張圖片可以表示為30976維空間中的一個點，即可以用30976個float值表示，為了便於處理，我們將特徵值乘以100000，在不損失float值精度的情況下，用int32_t儲存圖片特徵。

圖片檢索時需要計算query 圖片和索引圖片的歐式距離，圖片之間計算歐式距離的耗時為50微秒，經過cpu指令集最佳化（sse），歐式距離計算耗時減少到13微秒。

在壓縮之前，所有圖片的大小為 3T（ 4 * 30k * 25000000），每臺機器30G記憶體用於儲存圖片，需要100臺機器儲存全量圖片。

需要在計算歐式距離效率不降低的情況下，對圖片進行壓縮，大規模減少機器的佔用。

我們的目標是壓縮到500G左右，即壓縮之後每張圖片20k左右，歐式距離計算耗時為15微秒左右。

歐式距離計算要求耗時在微秒級別，已有的壓縮方法，比如p4delta、valgrind壓縮等在效能上不滿足要求，需要我們根據資料特點自己定製壓縮方法。

成果

目前的壓縮方法單張圖片由120k 壓縮到了平均13k。

歐式距離計算平均耗時為9微秒。

這麼靠譜的成果是如何做到的呢？

初步嘗試

bitmap的方法

觀察資料特點，發現平均每張圖片有7000個數為非0值，其他值都為 0。首先想到的是用bitmap表示30976個值在特定的位置是否是0。bitmap需要30976 / 8= 4k個位元組。然後只儲存非0值，需要7k * 4，壓縮之後平均每張圖片大小為32k。壓縮程式碼大體如下：

int bitmap_len = size / 8 + 8； uint64_t *bitmap = （uint64_t*）（cmpr_buf）； int32_t *data = （int32_t*）（cmpr_buf + bitmap_len）； for（unsigned int i=0；i

但是在計算圖片之間的歐式距離時，需要遍歷30976次bitmap，並判斷特定位的值知否為0，即將bitmap和掩碼陣列進行與操作，比較耗時，計算耗時在100微秒以上。計算兩個壓縮圖片的歐式距離程式碼：

for（i=0； i

採用offset的壓縮方式

我們只儲存非0資料的off_set和value，off_set最大值30975，需要用int16_t來儲存，value的範圍0~100萬，需要int32_t來表示，採用該方法的話，每個圖片佔用空間為42k （7k * （2 + 4））。

for（int i=0； i

計算兩個壓縮圖片的歐式距離的時候，採用按照off_set歸併的方法：

while（p_data1 *p_off2） { olength += *p_data2 * *p_data2； p_data2++； p_off2++； } else { olength += （*p_data1 - *p_data2） * （*p_data1 - *p_data2）； p_data1++； p_data2++； p_off1++； p_off2++； } }

該方法進行歐式距離的耗時為55微秒，我們認為是if 條件比較耗時，於是嘗試了用位掩碼替代if的方式：

while（p_data1 < end1 && p_data2

該方式消除了if 條件判斷，但是耗時為70微秒，效能反而下降了，耗時的原因是cpu的指令增多了。

效能最佳化

場景分析

兩個壓縮圖片計算 ——> 一個壓縮一個非壓縮

目前的最佳化進入了一個瓶頸，如何才能提升效能到10微秒級別呢？我們回過頭來重新考慮了一下應用場景，線上的場景是query圖片和一系列圖片計算距離，離線的場景是中心點圖片和其他一系列圖片計算距離也就是說都是一個圖片和多個圖片進行距離計算，這時一個圖片不需要進行壓縮，完全可以是非壓縮的，即使該圖片是壓縮也可以先解壓計算歐式距離實際上可以轉化為一個非壓縮圖片和多個壓縮圖片計算歐式距離。對這樣的情況，我們需要重新考慮提升效率的問題。

確定採用off_set壓縮方式

對於計算一個壓縮和一個非壓縮圖片歐式距離的問題，比較bitmap的壓縮方式和off_set的壓縮方式，off_set的壓縮方式有明顯的優勢對於bitmap方式，最耗時的地方仍然是訪問30976次bitmap，然後做與操作，來獲取解壓後的值，遍歷30976次bitmap耗時，至少50微秒以上但是off_set的方式儲存了7000個非0資料的off_set，我們只需要遍歷7000次非0 陣列就可以計算出歐式距離。

一個壓縮一個非壓縮

做法

首先計算好非壓縮圖片的累加平方和，每次查詢計算多次歐式距離，只計算一次累加平方和。

遍歷壓縮圖片陣列，計算該值和另一張非壓縮圖片的對應off_set的差值的平方。

對於壓縮圖片的為0的那些值來說，歐式距離只需要加上非壓縮圖片那些值的平方和。

舉例：

a。非壓縮圖片：［0 2 3 0 4 0 0 5 6 0 0］ ，壓縮圖片：［0 0 0 6 6 6 0 0 ］

b。事先計算好非壓縮圖片的特定位之前的所有值的平方和：sqrt［0 4 13 13 29 29 29 54 90 90 90］

c。壓縮的陣列為 off［3 4 5］， data［6 6 6 ］

d。遍歷off和data陣列

olength += （6 - 0） * （6 - 0） olength += （sqrt［2］ - sqrt［0］）

olength += （6 - 4） * （6 - 4）olength += （sqrt［3］ - sqrt［3］）

olength += （6 - 0） * （6 - 0） olength += （sqrt［4］ - sqrt［4］）

效率：20微秒

該方法只需要遍歷7000次陣列， 進行7000次相減 平方操作和 7000次訪問sqrt 陣列操作，大大簡化了複雜度。

程式碼如下：

data1為壓縮資料，data2為非壓縮資料：

for（int i=0； i

平方差展開

有沒有更最佳化的方法呢？

歐式距離的計算公式為（a［1］-b［1］）*（a［1］-b［1］） + （a［2］-b［2］）*（a［2］-b［2］） + 。。。 +（a［n］-b［n］）*（a［n］-b［n）。

經過展開可得a［1］*a［1］ + a［2］*a［2］ + 。。。 +a［n］*a［n］+ b［1］*b［1］ + b［2］ *b［2］ + 。。。 b［n］*b［n］ - 2*（a［1］*b［1］ + a［2］*b［2］ + 。。。 + a［n］*b［n］）。

而a［1］*a［1］ + 。。。 a［n］*a［n］和b［1］*b［1］ + 。。。 + b［n］*b［n］可以在壓縮的時候先計算並儲存起來，因為壓縮的耗時可以多一些。所以計算歐式距離只需要計算a［1］*b［1］ + a［2］*b［2］ + 。。。 + a［n］*b［n］即可。

舉例，上面的例子：

a。非壓縮圖片：［0 2 3 0 4 0 0 5 6 0 0］ ，壓縮圖片：［0 0 0 6 6 6 0 0 ］

b。計算壓縮圖片和非壓縮圖片的平方和。sqrt1 ：90 sqrt2：108

c。每次查詢 query 圖片計算一次 平方和， 壓縮圖片的平方和在壓縮的時候，計算好，並存儲。

d。遍歷壓縮陣列

multi += 6 * 0

multi += 6 * 4

multi += 6 * 0

e。歐式距離 = 90 + 108 - 2 * multi

效率 ：11微秒

該方法只計算7000次相乘，效率相對於上面的方法提高了一倍。

程式碼

for（int i=0； i

壓縮比最佳化

基本off_set壓縮

方法

基本的off_set壓縮前面已經講過。

效果

每張圖片壓縮到42k。

舉例

圖片 ：［ 5 5 8 0 0 。。。 0 7 6 3 0 0 0 0］ （（8 和 7 之間500個0），其中208為平方和，6 為非0元素個數。

off_set最佳化

方法

基本的方法利用int16_t來儲存非0資料的off_set，每個非0 value的off_set佔用2個位元組，如何減少off_set 的空間佔用呢？

很自然的我們想到了儲存該資料的off_set與上一個非0資料的off_set的差值，這樣的話，該值就會大大減小，一般的情況下會小於255，則我們可以用uint8_t來儲存off_set的差值。

但是如果off_set的差值大於255的話，該怎麼辦呢？

我們多存了一些0，作為非0值來儲存，如果兩個非0值之間的off_set大於255，則第一個非0值的off_set+255個off_set的位置存一個作為非0值的0。

如果0的off_set 與下一個非0的off_set 的差值小於255，則儲存下一個非0值，否則再加一個非0值。

經過統計，每個圖片平均有2個off_set差值大於255的非0值，對效能基本沒有影響。

效果

採用該方法的話，off_set部分佔用一個位元組，則壓縮之後，圖片大小為：7k * （1+4） = 35k。

舉例：

圖片 ： ［5 5 8 0 0 。。。 0 7 6 3 0］ （8 和 7 之間500個0）。

如下圖所示非0元素的個數變成了7，元素7和8之間由於off_set差值大於255，故多加了一個0，作為非0值，這樣off_set的差值就小於255了，在計算歐式距離時沒有影響。

value最佳化

方法

value用的是int32_t儲存，經過統計，平均有6個值大於65535，則採用uint16_t來儲存value的值，超過65535的值，放在壓縮buff的尾部，用int32_t儲存。

效果

壓縮之後每個圖片大小為7k*（2+1） = 21k。

舉例

圖片 ：［5 5 8 0 0 0 0 7 67676 66666 0 0 0］。

如下圖，其中9024396695 為平方和；4 為 uint16_t的值的個數， 2為大於uint16_t的值的個數，前面的非0值採用uint16_t儲存，佔兩個位元組，後面的67676、66666由於大於65535，用int32_t型別儲存，佔用4個位元組，平均每個圖片大於65535的值的個數為6個，故大大減少了空間佔用。

去掉重複值

還有沒有繼續壓縮的可能呢？

方法

經過分析資料，發現了圖片中的相鄰的非0數值，很多都是相同的，經過統計平均每張圖片有2400個相鄰的值不相同，有4300個相鄰值是相同的，其中700個值是相鄰的兩個值相同，3600個值是相鄰的三個值相同。

例：0 1 1 1 0 0 3 3 3 2 2 0 0。

如果將上面的1 1 1 和 3 3 3 和 2 2 歸一，只儲存 1、3、2和 該值的有幾個，則可以進一步壓縮空間將每個值有幾個存在哪裡呢？存在off_set 陣列中， 現在的off_set用8個bit儲存，最大儲存255的off_set差值，將這8個off_set拆分，6個bit儲存off_set差值，最大儲存差值為63，剩下的2個bit儲存該值有幾個相同的值，可以儲存的相同值的個數為：0 （不會用到）、1 、2 、3。

經過統計，平均每條query中的off_set差值大於63的值的個數為250個，也就是需要額外儲存200多個0值，對空間佔用影響不是特別大。

效果

透過該方法將圖片壓縮到13k，約等於 ：2。4k * 3 + （1。2+0。3）k * 3 其中2。4k為 相鄰不重複的值的個數，1。2k為相鄰且重複值為3的值的個數， 0。3k為相鄰且重複值為2 的值的個數，3 為 一位元組的off_set + 2位元組的value。

off_set 差值大於63的和value值大於65535的對空間影響很小。

計算歐式距離的耗時變為了35微秒，效率變慢的原因主要是int8_t位元組 被拆成了6bit 和 2bit。

舉例

圖片 ： ［0 1 1 1 0 0 3 3 3 2 2 0 0 ］

其中38表示平方和、3表示有3個值，0表示有0個大於65535的值，（1：3）用一個uint8_t表示， 前6個bit儲存1，表示off_set是1，後2個bit存3，表示相同的值有3個。（5：3） 和前面的類似，表示off_set差值是5，3個相同的值。（3：2）類似。後面的1 3 2為非0的值，與前面的方法不同的是不存重複的值。相鄰相同的值，只存一個。

去掉重複值最佳化

上面的方法雖然壓縮比高了，但是效率降低了，能不能將效率提高上來呢？

方法

上面的方法，效率降低是因為off_set拆成了6個bit和2個bit，在計算歐式距離時，需要做 與 操作，增大了複雜度。

能不能不拆分呢？

我們在儲存的時候將沒有重複的值存在一起，兩個重複的值存在一起，將重複3個重複的存在一起，這樣在計算歐式距離的時候，遍歷到3個重複的值的時候，只需要計算三次相乘的值就可以了，就不需要儲存重複值的個數了。

這樣的方法off_set的差值發生了變化，不是非0值之間的off_set差值，而是沒有重複值的off_set差值，和重複3個的值之間的off_set差值，這個off_set會增大，經過統計沒有重複值之間的off_set差值大於255的為4個，兩個重複值的off_set差值大於255的為25個，3個重複的off_set之間的差值大於255的為5個。2個重複值的之所以大於255的比較多，是因為2個重複的值比較少，300個值左右，故他們之間相隔比較遠，即off_set差值比較大，所以我們將2個重複的值作為不重複的值考慮。

效果

該方法將圖片壓縮為14k左右。（2。4k + 0。7k） * 3 + 1。3k * 3， 其中2。4k為不重複的值的總和，0。7k為重複數為2的值的總和，1。3k為重複數為3的值的個數之和，3 為off_set位元組+value 位元組，其他值大小對總空間影響忽略不計。

效能：9微秒， 在11微秒的基礎上減少了2微秒，因為重複數為3 的值時，不需要重複遍歷陣列。遍歷的陣列的次數不是7000，而是3000 + 1300 = 4300次。

舉例

圖片 ： ［0 1 1 1 0 0 3 3 3 2 2 0 0 ］。

其中38表示平方和、2表示有2不重複的值，後面的2表示有2個重複數為3 的值， 0表示有0個大於65535的值，9 和 1 表示不重複的值的off_set 差值， 2 和2 表示不重複的值，1和5表示重複數為3 的off_set差值，1 和3表示重複數為3 的值。

各個方法的效果總結：