DPM(Deformable Parts Model)

目标檢測方法

（1）基于cascade的目标檢測

cascade的級聯思想可以快速抛棄沒有目标的平滑窗（sliding window）,因而大大提高了檢測效率，但也不是沒缺點，缺點就是它僅僅使用了很弱的特征，用它做分類的檢測器也是弱分類器，僅僅比随機猜的要好一些，它的精度靠的是多個弱分類器來實行一票否決式推舉（就是大家都檢測是對的）來提高命中率，确定分類器的個數也是經驗問題。這節就來說說改進的特征，盡量使得改進的特征可以檢測任何物體，當然Deep Learning學習特征很有效，但今天還是按論文發表順序來說下其他方法，（伺服器還沒配置好，現在還不能大批跑Deep Learning ）,。

（2）基于形變部件的目标檢測

形變部件模型檢測方法是現在除了深度學習之外的還相對不錯的目标檢測方法，先來看下為什麼要使用形變部件，在下圖1中，同一個人的不同姿态，試問用前面幾節中的什麼方法可以檢測到這些不同姿态的人？門檻值不行，廣義霍夫變換行嗎？人的姿态是變換無窮的，需要太多的模闆。霍夫森林投票？貌似可以，但是霍夫森立的特征是圖像塊，隻适用于一些形變不大的物體，當圖像塊内的形變很大時同樣不太适用。那麼ASM可以嗎？想想也是和廣義霍夫變換一樣，需要太多的均值模闆。歸根結底就是我們沒有很好的形狀描述方法，沒有好的特征。而Pedro幾乎每發表一篇論文就改進一下形狀描述的方法，最終由簡單的表示方法到文法形式的表示方法，其演化過程可以在參考文獻[4]中看出，參考文獻[4]是Pedro的博士論文。

圖1

1 思路

DPM是一個非常成功的目标檢測算法，連續獲得VOC（Visual Object Class）07,08,09年的檢測冠軍。目前已成為衆多分類器、分割、人體姿态和行為分類的重要部分。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，在周邊那就要減掉一定的值，偏離的越遠減掉的值越大。

參考文獻[1]、[2]、[3]分别講述了如何利用形變模型描述物體（特征階段）、如何利用形變部件來做檢測（特征處理+分類階段）、如何加速檢測。文獻[1]的形變部件。在Deformable Part Model中，通過描述每一部分和部分間的位置關系來表示物體（part+deformable configuration）。其實早在1973年，Part Model就已經在 “Therepresentation and matching of pictorial structures” 這篇文章中被提出了。

圖2

         Part Model中，我們通過描述a collection of parts以及connection between parts來表示物體。圖2表示經典的彈簧模型，物體的每一部分通過彈簧連接配接。我們定義一個energy function，該函數度量了兩部分之和：每一部分的比對程度，部分間連接配接的變化程度（可以想象為彈簧的形變量），與模型比對最好的圖像就是能使這個energy function最小的圖檔。

形式化表示中，我們可以用一無向圖 G=(V,E) 來表示物體的模型，V={v1,…,vn} 代表n個部分，邊 (vi,vj)∈E 代表兩部分間的連接配接。物體的某個執行個體的configuration可以表示為 L=(l1,…,ln)，li 表示為 vi 的位置（可以簡單的将圖檔的configuration了解為各部分的位置布局，實際configuration可以包含part的其他屬性）。

給定一幅圖像，用 mi(li) 來度量vi 被放置圖檔中的 li 位置時，與模闆的不比對程度；用 dij(li,lj) 度量 vi,vj 被分别放置在圖檔中的 li,lj位置時，模型的變化程度。是以，一副圖像相對于模型的最優configuration，就是既能使每一部分比對的好，又能使部分間的相對關系與模型盡可能的相符的那一個。同樣的，模型也自然要描述這兩部分。可以通過下面的（公式一）描述最優configuration：

公式1 

        優化公式1其實就是馬爾科夫随機場中的經典問題求解，可以用上面說的BP算法求解。說的理論些就是最大化後驗機率（MAP），因為從随機場中很容易轉換到機率測度中（gibbs measure）,相關理論可以學習機率圖模型（probabilistic graphical model）。識别的時候采用就是采用部件比對，并且使得能量最小，這有點類似于ASM,但是ASM沒有使用部件之間的關系，隻是單純的讓各比對點之間的代價和最小。比對結果如圖3所示：

圖3

       上面的方法沒有用到機器學習，另外部件的尋找也不是一件容易的事情，因為首先要大概預估部件的位置，是以這個方法也有缺點，但這個形變部件的思想可以用來作為特征，接着就來看下Pedro的第二篇文獻[2]如何用它來做目标檢測。

Pedro在文獻[2]中基于形變模型的目标檢測用到了三方面的知識：1.Hog Features 2.Part Model 3. Latent SVM。

1.      作者通過Hog特征模闆來刻畫每一部分，然後進行比對。并且采用了金字塔，即在不同的分辨率上提取Hog特征。

2.      利用上段提出的Part Model。在進行object detection時，detect window的得分等于part的比對得分減去模型變化的花費。

3.      在訓練模型時，需要訓練得到每一個part的Hog模闆，以及衡量part位置分布cost的參數。文章中提出了Latent SVM方法，将deformable part model的學習問題轉換為一個分類問題。利用SVM學習，将part的位置分布作為latent values，模型的參數轉化為SVM的分割超平面。具體實作中，作者采用了疊代計算的方法，不斷地更新模型。

針對上面三條，發現難題如下：

1）部件從何而來？

2）如何用部件做檢測？

在基于部件做目标檢測之前，PASCAL VOC 2006年Dalal-Triggs的方法是直接用HOG作為特征，然後直接基于不同尺度的滑動視窗做判别，像一個濾波器，靠這個濾波器赢得短時的榮譽，但不能抗大形變的目标。

Pedro改進了Dalal-Triggs的方法，他計算作為一個得分，其中beta是濾波器，phi(x)是特征向量。通過濾波器找到一個根（root）部件p0，根部件有專門的濾波器，另外還有一系列非根部件（parts）p1…pn,然後把他們組成一個星形結構（此時回顧圖1的形變模型思想）。

每個部件用

來表示，其中X,Y是坐标，L表示金字塔級别。當這個星形結構的比對得分減去模型變化的代價得到最終分最高時，就完成了比對，如公式2所示：

公式2

        其中F’表示濾波器的向量化表示,b是偏移項，H表示特征金字塔。

現在假設濾波器解決了部件，完成了比對，解答了第二個疑問，但是濾波器從何而來，簡單的說就是這個濾波器的權重beta是多少？

現在不知道部件，也不知道濾波器，沒有濾波器就沒有部件，沒有部件也求不出濾波器的參數，這就是典型的EM算法要解決的事情，但是作者沒有使用EM算法，而是使用隐SVM（Latent SVM）的方法，隐變量其實就是類似統計中的因子分析，在這裡就是找到潛在部件。

在訓練的時候對部分部件進行打标簽，用他們求beta,然後用beta再來找潛在部件，是以使用coordinatedescent疊代求解，再一次遇到這個求解方法。有了部件和打分，就是尋找根部件和其他部件的結合比對最優問題，可以使用動态規劃，但很慢，具體請參考文獻[2]。

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.

       在文獻[2]中雖然使用了金字塔來加速搜尋速度，但是對星形結構組合的搜尋比對計算量也很大，檢測速度稍慢。

是以接着來看第三篇文獻[3],文獻[3]就是加速檢測過程，對于星形結構模型采用cascade來判斷，來快速抛去沒有有效資訊的part，其實實際中根部件的位置對比對起着很大作用，然後依次對其他部件（n+1）,有了這種關系，取一些部件子集後我們可以采用cascade來修剪、抛去一些不是好配置的部件組合（官方用語叫配置），這樣一些在弱分類器中評分高的組合進入更一步的判斷，類似于cascade的級聯思想，但是要注意形變模型的每個部件應該是相關的，而不應該像上節那樣harr-like特征之間獨立,依次判斷在這裡行不通，這裡其實是個子序列比對問題,文獻[7]提出過一種解決方法，pedro又改進了此方法，在原來n+1個部件的基礎上增加n+1可以快速計算的簡單部件，這樣打亂之後，子序列比對的代價就小了一些。

下面正式進入檢測流程，看看怎麼來加速的，大概流程如圖4所示：

圖4

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。

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) 源碼分析-訓練

參考文獻：

[1] Pictorial Structures for Object Recognition. Pedro F.Felzenszwalb

[2]Object Detection with Discriminatively Trained Part Based Models.Pedro F. Felzenszwalb

[3]Cascade Object Detection with Deformable Part Models. Pedro F.Felzenszwalb

[4]From RigidTemplates To Grammars: Object Detection With Structured Models. Pedro F.Felzenszwalb

[5]Histogramsof oriented gradients for human detection. N. Dalal and B. Triggs

[6] http://bubblexc.com/y2011/422/

[7]A computational model for visual selection.Y. Amit and D.Geman

參考：http://blog.csdn.net/ttransposition/article/details/12966521

更多，請關注http://blog.csdn.net/tiandijun/，歡迎交流！