前言
2002年P(guān)aul Viola等人在《Robust Real-time Object Detection》利用積分圖算法，將矩形內(nèi)像素值累加簡(jiǎn)化為四個(gè)點(diǎn)的加減座柱，大大提升訓(xùn)練與檢測(cè)速度晰骑，從而實(shí)現(xiàn)實(shí)時(shí)人臉檢測(cè)。筆者嘗試將該算法思路引入易盾反作弊指標(biāo)計(jì)算趟济，規(guī)避隱含的大量重復(fù)計(jì)算戴差，用空間換時(shí)間的方法提升計(jì)算速度送爸。同時(shí)，本文提出一種基于動(dòng)態(tài)時(shí)間系數(shù)的方案，量化時(shí)間與空間的收益比碱璃，實(shí)現(xiàn)性能與空間的Tradeoff弄痹。
人臉檢測(cè)的積分圖計(jì)算
該論文利用Adaboost算法將多個(gè)若分類(lèi)器組合成強(qiáng)分類(lèi)器饭入，每個(gè)迭代需要選擇當(dāng)前誤差最小的弱分類(lèi)器嵌器。假設(shè)圖片窗口為24*24，那么一共有45396個(gè)潛在的haar-like特征值谐丢。每個(gè)特征值的生成爽航，需要計(jì)算矩形范圍內(nèi)所有像素之和。
早在2001年乾忱，SIFT算法尚未發(fā)展成熟讥珍，神經(jīng)網(wǎng)絡(luò)還處于比較寂靜的時(shí)期，當(dāng)時(shí)人臉檢測(cè)算法最大的難度是實(shí)時(shí)計(jì)算窄瘟。為了能夠快速的計(jì)算Haar-like特征數(shù)據(jù)衷佃，Paul Viola等人提出Intergreted Image算法，將矩形內(nèi)所有像素之和簡(jiǎn)化為四個(gè)點(diǎn)的加減蹄葱。
對(duì)于小圖片而言氏义，求累加值比較快。但是图云，如果圖片比較大惯悠，且每次迭代選擇最優(yōu)分類(lèi)器時(shí)都要計(jì)算矩形和，計(jì)算量將非常大竣况。積分圖顧名思義就是將圖像做一層積分變換克婶。對(duì)于點(diǎn)(x,y)的積分值ii(x,y），等于點(diǎn)(1,1)到點(diǎn)(x,y)矩形范圍內(nèi)的像素值累加丹泉。如圖所示情萤，矩形A的像素之和，等于A+D-B-C摹恨。
指標(biāo)計(jì)算的數(shù)學(xué)模型
實(shí)時(shí)統(tǒng)計(jì)的各維度用戶指標(biāo)數(shù)據(jù)紫岩，最常見(jiàn)的分為：求累加值、去重計(jì)數(shù)睬塌。
求累加值計(jì)算類(lèi)型泉蝌，就是計(jì)算某個(gè)時(shí)間窗口內(nèi)的數(shù)值累加，比如計(jì)算最近一周內(nèi)每個(gè)用戶的消費(fèi)金額總和揩晴。為了簡(jiǎn)化計(jì)算模型勋陪，我們將一個(gè)指標(biāo)計(jì)算窗口分為10個(gè)步長(zhǎng)，對(duì)于一個(gè)窗口的求值轉(zhuǎn)化為為最近10個(gè)步長(zhǎng)數(shù)據(jù)累加硫兰。
去重計(jì)算計(jì)算類(lèi)型诅愚，統(tǒng)計(jì)某個(gè)維度的下高頻統(tǒng)計(jì)，比如某個(gè)用戶一周切換ip的個(gè)數(shù)。簡(jiǎn)單理解违孝，就是把最近一周時(shí)間內(nèi)的ip都存下來(lái)刹前，然后去重計(jì)數(shù)。
積分圖思想引入指標(biāo)計(jì)算
去重累加基本可以完全套用原始積分圖的思想雌桑，將二維降為一位喇喉，原始數(shù)據(jù)的求累加操作轉(zhuǎn)化為兩個(gè)數(shù)的減法。如下圖所示校坑，原需要累加10次拣技，使用積分圖只要減一次，大大降低了計(jì)算次數(shù)耍目。
求累加值可以用數(shù)據(jù)公式概況
再進(jìn)一步解釋?zhuān)瑃+1計(jì)算結(jié)果result(t+1)其實(shí)可以分解為t時(shí)刻計(jì)算的結(jié)果result(t) + g(t+1)-g(t-9)膏斤，是不是很熟悉，其實(shí)就是動(dòng)態(tài)規(guī)劃邪驮，將本次計(jì)算的結(jié)果直接帶入下一次的迭代計(jì)算省掉重復(fù)計(jì)算莫辨。近幾年神經(jīng)網(wǎng)絡(luò)很火熱，訓(xùn)練時(shí)用到的反向傳播算法毅访，本質(zhì)上也是一個(gè)意思沮榜，就是把t次迭代求導(dǎo)梯度計(jì)算的結(jié)果，作為中間結(jié)果直接帶入到下一層迭代計(jì)算俺抽。
去重計(jì)數(shù)的如何解決敞映？
由于去重計(jì)算不想簡(jiǎn)單的累加，需要把多個(gè)集合的數(shù)據(jù)合并磷斧，返回集合的大小振愿。由于步長(zhǎng)間可能有重讀數(shù)據(jù)，不能簡(jiǎn)單轉(zhuǎn)換為兩個(gè)點(diǎn)的減法弛饭。于是我們想出一個(gè)改進(jìn)方案冕末，對(duì)于每個(gè)步長(zhǎng)第一個(gè)數(shù)據(jù)，去合并前面10各步長(zhǎng)的集合侣颂，標(biāo)記為tmp_result档桃，并將其過(guò)期時(shí)間設(shè)置為一個(gè)步長(zhǎng)。如果步長(zhǎng)內(nèi)后續(xù)有數(shù)據(jù)過(guò)來(lái)憔晒，那么直接把數(shù)據(jù)加到tmp_result,并返回改set的size藻肄，不在需要sunion每個(gè)步長(zhǎng)集合。合并所有步長(zhǎng)操作算法復(fù)雜度是O(n)拒担，往一個(gè)集合里面加一個(gè)數(shù)據(jù)的算法復(fù)雜度是O(1)嘹屯，因此該優(yōu)化方案將計(jì)算整體算法復(fù)雜度從O(n)降到O(1)。
內(nèi)存與性能的Tradeoff
原始優(yōu)化方案从撼，臨時(shí)set有效期時(shí)間為步長(zhǎng)t州弟，預(yù)期內(nèi)存使用漲一倍。
1.可以考慮有效期時(shí)間，在步長(zhǎng)基礎(chǔ)上乘以一個(gè)系數(shù) ratio 婆翔，0 < ratio <= 1拯杠， expiredtime = ratio * t。每次sunionstore重新設(shè)置相對(duì)過(guò)期時(shí)間啃奴。
2.因此正常情況下潭陪，預(yù)計(jì)內(nèi)存增長(zhǎng)ratio倍，這樣可以調(diào)整ratio大小纺腊，量化犧牲多大內(nèi)存換取多大的rt收益畔咧。ratio可以設(shè)置在配置文件里面茎芭，上線初期可以設(shè)置小一點(diǎn)揖膜，比如0.1，根據(jù)內(nèi)存增長(zhǎng)情況調(diào)整大小梅桩。
3.ratio越大對(duì)內(nèi)存占用越大壹粟， 預(yù)計(jì)rt減少約明顯。那么就要找到合適的系數(shù)ratio宿百，讓內(nèi)存增長(zhǎng)在合理范圍內(nèi)趁仙，同時(shí)獲取比較好的rt收益。
根據(jù)經(jīng)線上經(jīng)驗(yàn)數(shù)據(jù)數(shù)據(jù)量較大時(shí)一次sunion時(shí)間大概50ms垦页，一個(gè)正常情況的時(shí)間大概2ms雀费，可以計(jì)算平均rt和ratio的關(guān)系式，N為一個(gè)步長(zhǎng)內(nèi)的總數(shù)據(jù)量痊焊。
如下圖所示盏袄，選擇性?xún)r(jià)比最高的elbow point，用相對(duì)比較小的raio獲取比較大的性能提升薄啥。對(duì)N=100來(lái)說(shuō)辕羽，raion等于0.1已經(jīng)有比較好的預(yù)期。如果對(duì)rt有一定的性能要求垄惧，也可以根據(jù)具體的目的來(lái)確定ratio系數(shù)大小刁愿。
有幾個(gè)好處：
1.正常情況下數(shù)據(jù)比較稀疏，臨時(shí)數(shù)據(jù)不需要存太長(zhǎng)時(shí)間
2.被刷或者壓測(cè)的時(shí)候到逊，一般數(shù)據(jù)會(huì)在短時(shí)間內(nèi)集中過(guò)來(lái)铣口，臨時(shí)數(shù)據(jù)較小的過(guò)期時(shí)間也夠用了
3.ratio的值可以根據(jù)redis內(nèi)存容量的情況調(diào)整，以達(dá)到靈活折中效果
