DPM(Deformable Parts Model)--原理(一)
申明：本文非筆者原創，原文轉載自：http://blog.csdn.NET/ttransposition/article/details/12966521
DPM(Deformable Parts Model)
Reference:
Object detection with discriminatively trained partbased models. IEEE Trans. PAMI, 32(9):1627–1645, 2010.
"Support Vector Machines for Multiple-Instance Learning,"Proc. Advances in Neural Information Processing Systems,2003.
作者主頁：http://www.cs.berkeley.edu/~rbg/latent/index.html
補充 and 修正：
HOG特征（畢業論文節選）
DPM目標檢測算法(畢業論文節選)
大體思路
DPM是一個非常成功的目標檢測算法，連續獲得VOC（Visual Object Class）07,08,09年的檢測冠軍。目前已成為眾多分類器、分割、人體姿態和行為分類的重要部分。2010年Pedro Felzenszwalb被VOC授予"終身成就獎"。DPM可以看做是HOG（Histogrrams of Oriented Gradients）的擴展，大體思路與HOG一致。先計算梯度方向直方圖，然后用SVM（Surpport Vector Machine ）訓練得到物體的梯度模型（Model）。有了這樣的模板就可以直接用來分類了，簡單理解就是模型和目標匹配。DPM只是在模型上做了很多改進工作。
上圖是HOG論文中訓練出來的人形模型。它是單模型，對直立的正面和背面人檢測效果很好，較以前取得了重大的突破。也是目前為止最好的的特征（最近被CVPR20 13年的一篇論文 《Histograms of Sparse Codes for Object Detection》 超過了）。但是， 如果是側面呢？所以自然我們會想到用多模型來做。DPM就使用了2個模型，主頁上最新版本Versio5的程序使用了12個模型。
?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????
?????????????????????????????????????????????????????????????????
?
?
上圖就是自行車的模型，左圖為側面看，右圖為從正前方看。好吧，我承認已經面目全非了，這只是粗糙版本。訓練的時候只是給了一堆自行車的照片，沒有標注是屬于component 1，還是component 2.直接按照邊界的長寬比，分為2半訓練。這樣肯定會有很多很多分錯了的情況，訓練出來的自然就失真了。不過沒關系，論文里面只是把這兩個Model當做初始值。重點就是作者用了多模型。
?
上圖右邊的兩個模型各使用了6個子模型，白色矩形框出來的區域就是一個子模型。基本上見過自行車的人都知道這是自行車。之所以會比左邊好辨識，是因為分錯component類別的問題基本上解決了，還有就是圖像分辨率是左邊的兩倍，這個就不細說，看論文。
有了多模型就能解決視角的問題了，還有個嚴重的問題，動物是動的，就算是沒有生命的車也有很多款式，單單用一個Model，如果動物動一下，比如美女搔首弄姿，那模型和這個美女的匹配程度就低了很多。也就是說，我們的模型太死板了，不能適應物體的運動,特別是非剛性物體的運動。自然我們又能想到添加子模型，比如給手一個子模型，當手移動時，子模型能夠檢測到手的位置。把子模型和主模型的匹配程度綜合起來，最簡單的就是相加，那模型匹配程度不就提高了嗎？思路很簡單吧！還有個小細節，子模型肯定不能離主模型太遠了，試想下假如手到身體的位置有兩倍身高那么遠，那這還是人嗎？也許這是個檢測是不是鬼的好主意。所以我們加入子模型與主模型的位置偏移作為Cost,也就是說綜合得分要減去偏移Cost.本質上就是使用子模型和主模型的空間先驗知識。
?
好了，終于來了一張合影。最右邊就是我們的偏移Cost,圓圈中心自然就是子模型的理性位置，如果檢測出來的子模型的位置恰好在此，那Cost就為0，在周邊那就要減掉一定的值，偏離的越遠減掉的值越大。
其實，Part Model 早在1973年就被提出參見《The representation and matching of pictorial structures》（木有看……）。
另外HOG特征可以參考鄙人博客：Opencv HOG行人檢測 源碼分析，SIFT特征與其很相似，本來也想寫的但是，那時候懶，而且表述比較啰嗦，就參考一位跟我同一屆的北大美女的系列博客吧。【OpenCV】SIFT原理與源碼分析
?
總之，DPM的本質就是彈簧形變模型，參見 1973年的一篇論文 ?The representation and matching of pictorial structures
2.檢測
檢測過程比較簡單：
綜合得分：
是rootfilter (我前面稱之為主模型)的得分，或者說是匹配程度，本質就是和的卷積，后面的partfilter也是如此。中間是n個partfilter（前面稱之為子模型）的得分。是為了component之間對齊而設的rootoffset.?為rootfilter的left-top位置在root feature map中的坐標，為第個partfilter映射到part feature map中的坐標。是因為part feature map的分辨率是root feature map的兩倍，為相對于rootfilter left-top 的偏移。
?的得分如下：
上式是在patfilter理想位置,即anchor position的一定范圍內，尋找一個綜合匹配和形變最優的位置。為偏移向量，為偏移向量，為偏移的Cost權值。比如則即為最普遍的歐氏距離。這一步稱為距離變換，即下圖中的transformed response。這部分的主要程序有train.m、featpyramid.m、dt.cc.
3.訓練
3.1多示例學習（Multiple-instance learning）
3.1.1 MI-SVM
一般機器學習算法，每一個訓練樣本都需要類別標號（對于二分類：1/-1）。實際上那樣的數據其實已經經過了抽象，實際的數據要獲得這樣的標號還是很難，圖像就是個典型。還有就是數據標記的工作量太大，我們想偷懶了，所以多只是給了正負樣本集。負樣本集里面的樣本都是負的，但是正樣本里面的樣本不一定都是正的，但是至少有一個樣本是正的。比如檢測人的問題，一張天空的照片就可以是一個負樣本集；一張某某自拍照就是一個正樣本集（你可以在N個區域取N個樣本，但是只有部分是有人的正樣本）。這樣正樣本的類別就很不明確，傳統的方法就沒法訓練。
疑問來了，圖像的不是有標注嗎？有標注就應該有類別標號啊?這是因為圖片是人標的，數據量特大，難免會有些標的不夠好,這就是所謂的弱監督集（weakly supervised set）。所以如果算法能夠自動找出最優的位置，那分類器不就更精確嗎？ 標注位置不是很準確，這個例子不是很明顯，還記得前面講過的子模型的位置嗎？比如自行車的車輪的位置，是完全沒有位置標注的，只知道在bounding box區域附件有一個車輪。不知道精確位置，就沒法提取樣本。這種情況下，車輪會有很多個可能的位置，也就會形成一個正樣本集，但里面只有部分是包含輪子的。
針對上述問題《Support Vector Machines for Multiple-Instance Learning》提出了MI-SVM。本質思想是將標準SVM的最大化樣本間距擴展為最大化樣本集間距。具體來說是選取正樣本集中最像正樣本的樣本用作訓練，正樣本集內其它的樣本就等候發落。同樣取負樣本中離分界面最近的負樣本作為負樣本。因為我們的目的是要保證正樣本中有正，負樣本不能為正。就基本上化為了標準SVM。取最大正樣本（離分界面最遠），最小負樣本（離分界面最近）：
對于正樣本：?為正樣本集中選中的最像大正樣本的樣本。
對于負樣本：可以將max展開，因為最小的負樣本滿足的話，其余負樣本就都能滿足，所以任意負樣本有：
目標函數：
也就是說選取正樣本集中最大的正樣本，負樣本集中的所有樣本。與標準SVM的唯一不同之處在于拉格朗日系數的界限。
而標準SVM的約束是：
最終化為一個迭代優化問題:
思想很簡單:第一步是在正樣本集中優化；第二步是優化SVM模型。與K-Means這類聚類算法一樣都只是簡單的兩步，卻爆發了無窮的力量。
這里可以參考一篇博客Multiple-instance learning。
關于SVM的詳細理論推導就不得不推薦我最為膜拜的MIT Doctor pluskid:?支持向量機系列
關于SVM的求解：SVM學習——Sequential Minimal Optimization
SVM學習——Coordinate Desent Method
此外，與多示例學習對應的還有多標記學習（multi-lable learning）有興趣可以了解下。二者聯系很大，多示例是輸入樣本的標記具有歧義（可正可負），而多標記是輸出樣本有歧義。
3.1.2 Latent SVM
1）我覺得MI-SVM可以看成?Latent-SVM的一種特殊情況。首先解釋下Latent變量，MI-SVM決定正樣本集中哪一個樣本作為正樣本的就是一個latent變量。不過這個變量是單一的，比較簡單，取值只是正樣本集中的序號而已。而LSVM 的latent變量就特別多，比如bounding box的實際位置x,y，在HOG特征金字塔中的某level中，樣本component ID。也就是說我們有了一張正樣本的圖片，標注了bounding box，我們要在某一位置，某一尺度，提取出一個區域作為某一component 的正樣本。
直接看Latent-SVM的訓練過程：
這一部分還牽扯到了Data-minig。先不管，先只看循環中的3-6,12.
3-6就對于MI-SVM的第一步。12就對應了MI-SVM的第二步。作者這里直接用了梯度下降法，求解最優模型β。
2）現在說下Data-minig。作者為什么不直接優化，還搞個Data-minig干嘛呢？因為，負樣本數目巨大，Version3中用到的總樣本數為2^28，其中Pos樣本數目占的比例特別低，負樣本太多，直接導致優化過程很慢，因為很多負樣本遠離分界面對于優化幾乎沒有幫助。Data-minig的作用就是去掉那些對優化作用很小的Easy-examples保留靠近分界面的Hard-examples。分別對應13和10。這樣做的的理論支撐證明如下：
3）再簡單說下隨機梯度下降法（Stochastic Gradient Decent）：
首先梯度表達式：
梯度近似：
優化流程：
這部分的主要程序：pascal_train.m->train.m->detect.m->learn.cc
3.2 訓練初始化
LSVM對初始值很敏感，因此初始化也是個重頭戲。分為三個階段。英語方面我就不班門弄斧了，直接上截圖。
下面稍稍提下各階段的工作，主要是論文中沒有的Latent 變量分析：
Phase1:是傳統的SVM訓練過程，與HOG算法一致。作者是隨機將正樣本按照aspect ration（長寬比）排序，然后很粗糙的均分為兩半訓練兩個component的rootfilte。這兩個rootfilter的size也就直接由分到的pos examples決定了。后續取正樣本時，直接將正樣本縮放成rootfilter的大小。
Phase2:是LSVM訓練。Latent variables 有圖像中正樣本的實際位置包括空間位置（x,y）,尺度位置level，以及component的類別c，即屬于component1 還是屬于 component 2。要訓練的參數為兩個 rootfilter，offset（b）
Phase3:也是LSVM過程。
先提下子模型的添加。作者固定了每個component有6個partfilter，但實際上還會根據實際情況減少。為了減少參數，partfilter都是對稱的。partfilter在rootfilter中的錨點（anchor location）在按最大energy選取partfilter的時候就已經固定下來了。
這階段的Latent variables是最多的有：rootfilter（x,y,scale）,partfilters(x,y,scale)。要訓練的參數為 rootfilters, rootoffset, partfilters, defs(的偏移Cost)。
這部分的主要程序：pascal_train.m
4.細節
4.1輪廓預測（Bounding Box Prediction）
仔細看下自行車的左輪，如果我們只用rootfilter檢測出來的區域，即紅色區域，那么前輪會被切掉一部分，但是如果能綜合partfilter檢測出來的bounding box就能得到更加準確的bounding box如右圖。
這部分很簡單就是用最小二乘（Least Squres）回歸，程序中trainbox.m中直接左除搞定。
4.2 HOG
作者對HOG進行了很大的改動。作者沒有用4*9=36維向量，而是對每個8x8的cell提取18+9+4=31維特征向量。作者還討論了依據PCA（Principle Component Analysis）可視化的結果選9+4維特征，能達到HOG 4*9維特征的效果。
這里很多就不細說了。開題一個字都還沒寫，要趕著開題……主要是features.cc。有了下面這張圖，自己慢慢研究下：
?
?
源碼分析：
DPM(Defomable Parts Model) 源碼分析-檢測
DPM(Defomable Parts Model) 源碼分析-訓練
轉載于:https://www.cnblogs.com/ocean1100/articles/7289512.html
與50位技術專家面對面20年技術見證，附贈技術全景圖總結
以上是生活随笔為你收集整理的DPM(Deformable Parts Model)--原理(一)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 20170804 - 今日技能封装 -
- 下一篇： 变位词程序的实现