小嘰導讀：如何將單張圖片由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 if(list[i] != 0) { data[index++] = list[i]; bitmap[i/64] |= bit_mask_tab[i % 64]; } }但是在計算圖片之間的歐式距離時，需要遍歷30976次bitmap，并判斷特定位的值知否為0，即將bitmap和掩碼數組進行與操作，比較耗時，計算耗時在100微秒以上。計算兩個壓縮圖片的歐式距離代碼： for(i=0; i64; i++) { for(int j=0; j<64; j++) { a = 0; b = 0; if((bitmap1[i] & bit_mask_tab[j])) { a = data1[index1++]; } if((bitmap2[i] & bit_mask_tab[j])) { b = data2[index2++]; } olength += (a - b) * (a - b); } }

• 采用offset的壓縮方式

我們只保存非0數據的off_set和value，off_set最大值30975，需要用int16_t來保存，value的范圍0~100萬，需要int32_t來表示，采用該方法的話，每個圖片占用空間為42k (7k * (2 + 4))。 for(int i=0; i if(list[i] != 0) { index++; } } *(int16_t*) cmpr_buf = index; int16_t *p_off = (int16_t*)cmpr_buf + 1; int32_t *p_data = (int32_t*)(((char *)cmpr_buf) + sizeof(int16_t) * index + sizeof(int16_t)); index = 0; for(int i=0; i if(list[i] != 0) { p_off[index] = i; p_data[index] = list[i]; index++; } }計算兩個壓縮圖片的歐式距離的時候，采用按照off_set歸并的方法：while(p_data1<end1 && p_data2 < end2){ if(*p_off1 < *p_off2) { olength += *p_data1 * *p_data1; p_data1++; p_off1++; } else if(*p_off1 > *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 a = ((*p_off1 - *p_off2) <= 0); b = ((*p_off2 - *p_off1) <= 0); tmp1 = -a & *p_data1; tmp2 = -b & *p_data2; p_off1 += a; p_off2 += b; p_data1 += a; p_data2 += b; tmp = tmp1 - tmp2; olength += tmp * tmp; }該方式消除了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 olength += (data1[i] - data2[off1[i]]) * (data1[i] - data2[off1[i]]); olength += sqrt[off[i] - 1] - sqrt[off[i-1]]; }平方差展開

• 有沒有更優化的方法呢？

歐式距離的計算公式為(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:108c.每次查詢 query 圖片計算一次 平方和， 壓縮圖片的平方和在壓縮的時候，計算好，并存儲。d.遍歷壓縮數組

• multi += 6 * 0
• multi += 6 * 4
• multi += 6 * 0

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

• 效率 ：11微秒

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

• 代碼

for(int i=0; iint64_t)p_data1[i] * (int64_t)p_data2[p_off1[i]]; } olength += sqrt1 + sqrt2 - 2 * multi;壓縮比優化基本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 的值。各個方法的效果總結：「 更多干貨，更多收獲?」

多視圖多標記算法SIMM

10億節點異構網絡中，GCN 如何應用？

當個不“佛系”的推薦系統，CTR 預估要做哪些？

關注機器智能把握未來可能

總結

以上是生活随笔為你收集整理的如何把照片压缩到20k一下_如何将图像压缩10倍？阿里工程师有个大胆的想法！...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。