CV崗位面試題：DPM（Deformable Parts Model）算法流程
文 | 七月在線
編 | 小七
解析1：
將原圖與已經(jīng)準備好的每個類別的“模板”做卷積操作，生成一中類似熱力圖（hot map）的圖像，將不同尺度上的圖合成一張，圖中較量點就是與最相關(guān)“模板”相似的點。
拓展：
* SGD(stochastic gradient descent)到training里
* NMS(non-maximum suppression)對后期testing的處理非常重要
* Data mining hard examples這些概念至今仍在使用
解析2：
DPM算法由Felzenszwalb于2008年提出，是一種基于部件的檢測方法，對目標的形變具有很強的魯棒性。目前DPM已成為眾多分類、分割、姿態(tài)估計等算法的核心部分，F(xiàn)elzenszwalb本人也因此被VOC授予"終身成就獎"。
DPM算法采用了改進后的HOG特征，SVM分類器和滑動窗口(Sliding Windows)檢測思想，針對目標的多視角問題，采用了多組件（Component）的策略，針對目標本身的形變問題，采用了基于圖結(jié)構(gòu)（Pictorial Structure）的部件模型策略。此外，將樣本的所屬的模型類別，部件模型的位置等作為潛變量（Latent Variable），采用多示例學習（Multiple-instance Learning）來自動確定。
1、通過Hog特征模板來刻畫每一部分，然后進行匹配。并且采用了金字塔，即在不同的分辨率上提取Hog特征。
2、利用提出的Deformable PartModel，在進行object detection時，detect window的得分等于part的匹配得分減去模型變化的花費。
3、在訓練模型時，需要訓練得到每一個part的Hog模板，以及衡量part位置分布cost的參數(shù)。文章中提出了LatentSVM方法，將deformable part model的學習問題轉(zhuǎn)換為一個分類問題：利用SVM學習，將part的位置分布作為latent values，模型的參數(shù)轉(zhuǎn)化為SVM的分割超平面。具體實現(xiàn)中，作者采用了迭代計算的方法，不斷地更新模型。
rootfilters根濾波器數(shù)組，其每個元素表示一個組件模型的根濾波器的信息，每個元素包括3個字段：
size：根濾波器的尺寸，以cell為單位，w*h
w：根濾波器的參數(shù)向量，維數(shù)為(w*h)*31
blocklabel：此根濾波器所在的數(shù)據(jù)塊標識
濾波器(模版)就是一個權(quán)重向量，一個w * h大小的濾波器F是一個含w * h * 9 * 4個權(quán)重的向量(9*4是一個HOG細胞單元的特征向量的維數(shù))。所謂濾波器的得分就是此權(quán)重向量與HOG金字塔中w * h大小子窗口的HOG特征向量的點積(DotProduct)。
DPM的特征
de
DPM采用了HOG特征，并對HOG特征進行了一些改進。
Hog特征提取的過程：
1.對原圖像gamma校正，img=sqrt(img);
2.求圖像豎直邊緣，水平邊緣，邊緣強度，邊緣斜率。
3.將圖像每16*16（取其他也可以）個像素分到一個cell中。對于256*256的lena來說，就分成了16*16個cell了。
4.對于每個cell求其梯度方向直方圖。通常取9（取其他也可以）個方向（特征），也就是每360/9=40度分到一個方向，方向大小按像素邊緣強度加權(quán)。最后歸一化直方圖。
5.每2*2（取其他也可以）個cell合成一個block，所以這里就有（16-1）*（16-1）=225個block。
6.所以每個block中都有2*2*9=36個特征，一共有225個block，所以總的特征有225*36個。
當然一般HOG特征都不是對整幅圖像取的，而是對圖像中的一個滑動窗口取的。
DPM改進后的HOG特征取消了原HOG中的塊(Block)，只保留了單元（Cell），如上圖所示，假設(shè)一個8*8的Cell，將該細胞單元與其對角線臨域的4個細胞單元做歸一化操作，所以效果和原HOG特征非常類似。計算梯度方向時可以計算有符號（0-360°）或無符號（0-180°）的梯度方向，有些目標適合使用有符號的梯度方向，而有些目標適合使用無符號的梯度，作為一種通用的目標檢測方法，DPM與原HOG不同，采用了有符號梯度和無符號梯度相結(jié)合的策略。
提取有符號的HOG梯度，0-360度將產(chǎn)生18個梯度向量，提取無符號的HOG梯度，0-180度將產(chǎn)生9個梯度向量。如果直接將特征向量化，一個8*8的細胞單元將會產(chǎn)生（18+9）*4=108，維度有點高 。
Felzenszwalb提取了大量單元的無符號梯度，每個單元共 維特征，并進行了主成分分析（Principal Component Analysis，PCA），發(fā)現(xiàn)使用前11個特征向量基本上可以包含所有的信息，不過為了快速計算，作者由主成分可視化的結(jié)果得到了一種近似的PCA降維效果。
具體來說：首先，只提取無符號的HOG梯度，將會產(chǎn)生4*9=36維特征，將其看成一個4*9的矩陣，分別將行和列分別相加，最終將生成4+9=13個特征向量，得到13維特征，基本上能達到HOG特征36維的檢測效果。為了提高那些適合使用有符號梯度目標的檢測精度，作者再對18個有符號梯度方向求和得到18維向量，也加進來，這樣，一共產(chǎn)生13+18=31維梯度特征。實現(xiàn)了很好的目標檢測。
DPM的檢測模型
DPM V3版本的目標檢測模型由兩個組件構(gòu)成，每一個組件由一個根模型和若干部件模型組成。上圖（a）和（b）是其中一個組件的根模型和部件模型的可視化的效果(這個只是可視化的結(jié)果，不要認為是用這個當做模板與原圖特征圖做卷積?。?，真正與原圖特征圖做卷積計算的是檢測算子，即SVM分類模型系數(shù)w)，每個單元內(nèi)都是SVM分類模型系數(shù)w對梯度方向加權(quán)疊加，梯度方向越亮的方向可以解釋為行人具有此方向梯度的可能性越大。
上圖（a），根模型比較粗糙，大致呈現(xiàn)了一個直立的正面/背面行人。
上圖（b）所示，部件模型為矩形框內(nèi)的部分，共有6個部件，分辨率是根模型的兩倍，這樣獲得更好的效果。從中，我們可以明顯地看到頭、手臂等部位。為了降低模型的復雜度，根模型和部件模型都是軸對稱的。
上圖（c）為部件模型的偏離損失，越亮的區(qū)域表示偏離損失代價越大，部件模型的理想位置的偏離損失為0。
DPM檢測流程
DPM采用了傳統(tǒng)的滑動窗口檢測方式，通過構(gòu)建尺度金字塔在各個 尺度搜索。下圖為某一尺度下的行人檢測流程，即行人模型的匹配過程。某一位置與根模型/部件模型的響應得分，為該模型與以該位置為錨點（即左上角坐標）的子窗口區(qū)域內(nèi)的特征的內(nèi)積。也可以將模型看作一個濾波算子，響應得分為特征與待匹配模型的相似程度，越相似則得分越高。
左側(cè)為根模型的檢測流程，跟模型響應的圖中，越亮的區(qū)域代表響應得分越高。右側(cè)為各部件模型的檢測過程。首先，將特征圖像與模型進行匹配得到部件模型響應圖。然后，進行響應變換：以錨點為參考位置，綜合考慮部件模型與特征的匹配程度和部件模型相對理想位置的偏離損失，得到的最優(yōu)的部件模型位置和響應得分。
如上圖所示，對于任意一張輸入圖像，提取其DPM特征圖，然后將原始圖像進行高斯金字塔上采樣放大原圖像，然后提取其DPM特征圖（2倍分辨率）。將原始圖像的DPM特征圖和訓練好的Root filter做卷積操作，從而得到Root filter的響應圖。對于2倍圖像的DPM特征圖，和訓練好的Part filter做卷積操作，從而得到Part filter的響應圖。然后對其精細高斯金字塔的下采樣操作。這樣Root filter的響應圖和Part filter的響應圖就具有相同的分辨率了。然后將其進行加權(quán)平均，得到最終的響應圖，亮度越大表示響應值越大。
回顧精品內(nèi)容
推薦系統(tǒng)
1、干貨 | 基于用戶的協(xié)同過濾推薦算法原理和實現(xiàn)
2、超詳細丨推薦系統(tǒng)架構(gòu)與算法流程詳解
機器學習
自然語言處理(NLP)
1、AI自動評審論文，CMU這個工具可行嗎？我們用它評審了下Transformer論文
2、Transformer強勢闖入CV界秒殺CNN，靠的到底是什么"基因"
計算機視覺(CV)
1、9個小技巧讓您的PyTorch模型訓練裝上“渦輪增壓”...
GitHub開源項目：
1、火爆GitHub！3.6k Star,中文版可視化神器現(xiàn)身
2、兩次霸榜GitHub！這個神器不寫代碼也可以完成AI算法訓練
3、登頂GitHub大熱項目 | 非監(jiān)督GAN算法U-GAT-IT大幅改進圖像轉(zhuǎn)換
每周推薦：
1、本周優(yōu)秀開源項目分享：無腦套用格式、開源模板最高10萬贊
2、本周優(yōu)秀開源項目分享：YOLOv4的Pytorch存儲庫、用pytorch增強圖像數(shù)據(jù)等7大項目
七月在線學員面經(jīng)分享：
1、 雙非應屆生拿下大廠NLP崗40萬offer：面試經(jīng)驗與路線圖分享