一種基于可變形部件模型的快速對象檢測算法

李春偉 于洪濤 李邵梅 卜佑軍

?

一種基于可變形部件模型的快速對象檢測算法

李春偉*于洪濤 李邵梅 卜佑軍

(國家數字交換系統工程技術研究中心 鄭州 450002)

為了解決可變形部件模型檢測過程中的速度瓶頸問題，該文針對模型的檢測流程，提出一種結合快速特征金字塔計算的級聯可變形部件模型。由于模型的檢測速度主要取決于特征計算以及對象定位這兩個過程，提出一種兩階段的加速算法：首先采用尺度上稀疏采樣的特征金字塔來近似表示精細采樣的多尺度圖像特征，以加快特征計算過程；然后在定位過程中結合級聯算法，以一個序列模型順序地評估各個部件，從而快速剪除大部分可能性較小的對象假設，以加快對象定位過程。在PASCAL VOC 2007和INRIA數據集上的實驗結果表明，該算法可以明顯加快檢測速度，而檢測精度僅略有下降。

快速對象檢測；可變形部件模型；特征計算；級聯檢測

1 引言

對象檢測技術是計算機視覺的關鍵技術和研究熱點之一。可變形部件模型[1](Deformable Part Model, DPM)作為現今最流行的對象檢測算法之一，在對象檢測領域著名的PASCAL VOC競賽中多次取得優異的成績，目前已經擴展應用到人體姿態估計[2]，行人檢測[3]，人臉檢測[4]，以及智能交通[5]等諸多領域。但是DPM模型中涉及的梯度方向直方圖[6](Histogram of Oriented Gradient, HOG)特征金字塔的提取和對象定位兩部分的運算量都較大，導致在單機上處理單張PASCAL數據集中的圖像時，運行時間在10 s左右，無法滿足實際應用需求。為此，近年來研究學者針對DPM的加速問題開展了系列研究。現有的DPM模型加速研究主要集中在以下兩個方面：

單類別加速算法：主要關注于單個類別檢測中DPM模型的加速效果。文獻[7,8]通過較早地剪除無望的對象假設來減少計算量，前者根據部件濾波器的得分，使用中間閾值來剪除得分較低的部件假設。但是需要專門的確認數據集來訓練中間閾值。后者通過使用多分辨率的層次部件模型，逐次對目標假設進行判斷，但是其對于檢測精度有一定的影響。文獻[9]采用一種類似于文獻[7]中的加速策略，通過一種積極的部件選擇策略優化了濾波器評估的順序。文獻[10]在所有可能的圖像區域上搜索全局最優的分類結果，然而該方法使用最大響應的上確界進行搜索窗口的裁剪操作，其有效性極大地依賴于邊界的健壯性。文獻[11]采用GPU實現并行計算，但是對計算機硬件提出了較高的要求；文獻[12]使用快速傅里葉變換來加速檢測過程中卷積計算過程。文獻[13]通過多種加速方法間的組合來構建完整的加速策略。

多類別加速算法：文獻[14]使用大量部件集合中的稀疏線性組合來對可變形部件進行編碼，以此來壓縮模型中所使用的有效部件數；文獻[15]使用少量基本的部件集合的線性組合來近似表示模板中視角、形變、尺度等方面的變化。類似的方法在文獻[16]中也進行了相關研究。這兩種方法都是通過學習得到一組共享的基元部件，來獲取類別層次的檢測效果。文獻[17]提出了基于局部敏感的哈希算法來近似DPM中的卷積計算，處理的對象類別達到了100000種，但是對于檢測精度的影響較大。

綜上，可以看出已有研究中主要關注對象定位加速，并且取得了一些成果，但是對于特征計算加速關注較少。所以想要進一步提高DPM模型的處理速度，就不得不考慮特征計算部分的加速問題。由此，本文提出了一種針對可變形部件模型的兩階段加速算法：首先，采用尺度上稀疏采樣的特征金字塔近似表示精細采樣的多尺度特征金字塔，以此來加快特征計算過程；然后，采用級聯算法來加速對象定位過程。為了便于敘述，后續將本文提出的方法稱之為結合快速特征金字塔的級聯可變形部件模型(Cascade Deformable Part Model with Fast feature pyramid, FCDPM)。

2 基于冪指定律的快速特征金字塔計算

在基于多尺度特征金字塔的滑動窗口模型中為了解決模板尺寸與對象尺寸不一致的問題，需要對目標圖像多次進行下采樣得到不同尺度下的圖像，然后再在逐個尺度的圖像上逐個位置上計算圖像特征，從而生成精細的特征金字塔，該方法得到的特征精度高，但是相應的時間開銷也較大。已有研究人員對特征金字塔進行研究，發現多尺度金字塔尺度間的特征存在一定的關系，且滿足冪指定律[18,19]。由此，本文提出在特征金字塔的計算過程中，利用多尺度特征中的冪指定律有選擇地計算部分尺度圖像的特征，然后基于這些尺度圖像的特征對臨近尺度圖像的特征進行近似計算，從而減少特征計算的運算量。

2.1 多尺度特征間的冪指定律

為了便于描述，本節先簡要介紹一下多尺度圖像間的冪指定律。對于給定的輸入圖像，定義其對應的通道特征為圖像像素的某種線性或是非線性變換的輸出響應：。其中表示某種計算函數，表示輸出響應。定義為的權值加和：,為圖像在尺度上的重采樣圖像，其中的維數是圖像維數的倍。那么就被定義為

2.2基于冪指定律的尺度間HOG特征近似計算

本節將上述定律應用到DPM模型中的HOG特征計算中。在傳統DPM模型中，計算尺度圖像的特征的方法為，其中表示采樣函數，即需要首先將圖像縮放至尺度，然后再計算圖像的HOG特征。根據上述定律，和之間存在對應關系，為此在已知原始尺寸圖像的特征的情況下，可以根據其對進行近似計算，從而提高特征計算的速度。

2.3 基于冪指定律的HOG特征金字塔計算

3 結合級聯算法的可變形部件模型對象定位

3.1 可變形部件模型中對象定位流程

本節首先簡要介紹可變形部件模型中對象定位的處理流程。DPM模型為一個兩層模型，其中根濾波器用于檢測對象的整體輪廓，個部件相對于根濾波器允許有一定的位移，用于描述目標對象的細節特征及其位置偏移導致的形變特征，從而模型在處理大尺度外觀變化時有優勢。第個部件由濾波器以及形變模型進行參數化表示。一個對象假設由進行定義。其中表示根濾波器的位置，表示第個部件的位置。根濾波器以及部件濾波器之間通過圖結構模型進行連接，形變模型用于描述兩者之間的形變特征。為了檢測出圖像中目標對象的位置，在每一個根位置上根據最有可能的部件配置來計算對象假設的整體得分：

3.2結合級聯的快速對象定位

從上述描述中可以看出，基于計算出的多尺度HOG特征，在DPM模型的對象定位過程中，需要逐尺度層采用滑窗搜索進行匹配檢測。但是，事實上對象通常僅出現在圖像場景中的有限位置，圖像尺度空間上的絕大部分窗口對于視覺對象檢測而言是無效的，如果在每個尺度、每個位置都進行完整的匹配操作，這就導致了計算復雜度的增加。由此提出在對象定位過程中結合級聯檢測，迅速減除大部分可能性較小的對象假設，以此來提高定位過程的速度。

首先對原模型中部件進行排序來構建層次結構的新模型。在擁有個部件(其中包括根濾波器)的DPM模型中，采用一個全局閾值和個中間閾值的序列，從而得到一個長度為的序列模型。在計算匹配得分時，部件得分是按照一定的次序逐個匹配，在計算每一個部件表現得分以及相應的變形開銷時都要與中間閾值進行判別，如果小于預設的中間閾值，相應的目標假設就被剪除。

4 結合快速特征金字塔的級聯可變形部件模型

表1 FCDPM算法

圖1 FCDPM算法的示例

5 實驗結果

5.1實驗準備

為了評估所提算法的性能，本文采用平均精度(Average Precision, AP)值作為評價指標，分別在PASCAL VOC 2007數據集以及INRIA數據集上進行了測試，并且與初始的DPM模型以及相關算法進行了比較，AP值定義如下：

5.2 在PASCAL VOC 2007數據集上的實驗結果

PASCAL VOC 2007是一個通用的對象檢測數據集，其測試集中包含20種類別的圖像，共有4952張測試圖片以及14976個人工標注的目標對象。通過上面的敘述，設為在特征金字塔計算中，由每一個基準尺度所外推計算的尺度數，當時，即表示精細采樣的特征金子塔。的取值會影響特征金字塔的計算速度，取值越大，計算速度越快，但是這也會在一定程度上影響特征金字塔的計算精度，首先討論了不同的取值對于AP值以及相對于DPM模型檢測速度的影響，相應的結果如圖2所示。

表2比較了FCDPM算法，與初始的DPM模型以及若干種加速算法，其中包括CSC算法[7]，CF算法[8]，BB算法[10]，在PASCAL2007數據集上的實驗結果，其中FCDPM旁的數字表示的取值。每一種算法在20種類別檢測過程中的平均特征計算時間、對象定位時間以及完整檢測時間如表3所示。

從表3可以發現，CSC算法、CF算法、BB算法相比于初始的DPM模型在PASCAL2007數據集上取得了10倍左右的加速效果，本文算法與之相比，可以3倍快于這些改進算法，但是平均的AP值有一定的下降(特別是與CSC算法相比較)。即當時，可以取得最快的加速效果，相應的精度下降也最多，但是與CF算法和BB算法相比，綜合考慮精度以及速度，具有較大的優勢；而且可以通過調整這一參數，從而在檢測精度和速度之間取得一定的平衡。當時，平均的AP值為31.3%，當時，平均的AP值上升到32.4%，此時與CSC算法僅相差0.4%，檢測速度為CSC算法的1.6倍。

5.3在INRIA數據集上的實驗結果

INRIA數據集是一個常用的行人檢測數據集，其中包含614幅圖像，共有1237個正樣本和1218個負樣本。表4說明了上述算法在該數據集上的實驗結果。在數據集中的運行時間的比較如表5所示。從中可以發現改進算法在行人檢測這一領域也取得了在PASCAL對象檢測數據集中相似的檢測結果。FCDPM算法在該數據集上最快可以取得將近32倍的加速效果。當時，可以取得與CSC算法相接近的AP值，但是檢測速度為CSC算法的兩倍。從而驗證本文算法在行人檢測領域也是適用的。

圖2 nApp的取值對于檢測速度以及精度的影響

表2不同算法在PASCAL2007數據集中20個類別的AP值結果(%)

算法AeroBicycleBirdBoatBottleBusCarCatChairCow DPM32.159.910.613.524.947.748.927.517.427.0 CSC[7]33.658.510.213.425.044.749.228.017.127.2 CF[8]27.658.610.510.616.552.742.127.612.929.1 BB[10]30.653.9 8.710.422.543.238.917.513.522.6 FCDPM935.957.6 8.411.826.944.348.118.014.722.8 FCDPM535.558.610.211.627.446.550.619.416.423.4 FCDPM137.059.610.311.227.444.350.820.617.923.0 DogHorseMbikePersonPlantSheepSofaTableTrainTv平均 14.457.450.038.413.321.036.831.147.542.333.0 13.557.750.038.514.121.636.828.647.442.032.8 15.355.244.626.312.422.738.632.844.832.230.6 9.055.747.227.411.117.128.323.344.538.428.2 8.755.346.033.313.319.229.525.944.536.530.0 9.953.247.036.615.022.832.426.843.138.831.3 11.657.950.839.015.223.534.426.047.041.632.4

6 結束語

針對可變形部件模型的檢測流程，為了加速模型的檢測速度，本文提出了一種兩階段的加速算法，分別采用特征計算中尺度間的冪指定律以及級聯算法加速特征計算以及對象定位過程，從而顯著地提高模型的檢測速度。下一步的工作集中在加速檢測過程中的卷積計算，這與之前的工作[8,11]是互補的，相結合預期可以得到顯著的加速效果；還可以與目前流行的對象建議算法[20]相結合，以進一步提升算法的檢測速度。

表3在PASCAL2007數據集中的平均運行時間(s)

算法特征計算對象定位運行時間之和加速倍數 DPM0.3769.1979.573 1.00 CSC[7]0.3760.4390.81511.74 CF[8]0.5480.4380.986 9.71 BB[10]0.3761.2871.663 5.53 FCDPM90.0900.2510.34128.10 FCDPM50.1100.2750.38524.87 FCDPM10.1930.3180.51118.73

表4不同算法在INRIA數據集上的AP值(%)

算法DPMCSCCFBBFCDPM9FCDPM5FCDPM1 AP值88.788.683.685.583.986.687.7

表5在INRIA數據集中的平均運行時間(s)

算法特征計算對象定位運行時間之和加速倍數 DPM0.76614.42515.1911.00 CSC0.766 0.670 1.44110.54 CF1.242 0.445 1.687 9.00 BB0.766 1.477 2.243 6.77 FCDPM90.157 0.323 0.48031.65 FCDPM50.212 0.354 0.56626.84 FCDPM10.326 0.443 0.76919.75

[1] FELZENSZWALB P, GIRSHICK R, MCALLESTER D,. Object detection with discriminatively trained part based models[J]., 2010, 32(9): 1627-1645. doi: 10.1109/TPAMI.2009.167.

[2] YAO Benjamin, NIE Bruce, LIU Zicheng,. Animated pose templates for modeling and detecting human actions[J]., 2014, 36(3): 436-452. doi:10.1109/TPAMI. 2013.144.

[3] WEN Jia, WANG Xueping, KONG Lingfu,. Using weighted part model for pedestrian detection in crowded scenes based on image segmentation[J]., India Section A: Physical Scienes 2016, 86(1): 125-136. doi: 10.1007/s40010-015- 0231-3.

[4] OROZCO J, MARTINEZ B, and PANTIC M. Empirical analysis of cascade deformable models for multi-view face detection[J]., 2015, 42(1): 47-61. doi: 10.1016/j.imavis.2015.07.002.

[5] OHNBAR E and TRIVEDI M M. Learning to detect vehicles by clustering appearance patterns[J]., 2015, 16(5): 2511-2521. doi: 10.1109/TITS.2015.2409889.

[6] DALAL N and TRIGGS B. Histograms of oriented gradients for human detection[C]. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, San Diego, USA, 2005: 886-893.doi: 10.1109/ CVPR.2005.177.

[7] FELZENSZWALB P, GIRSHICK R, and MCALLESTER D. Cascade object detection with deformable part models[C]. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, San Francisco, USA, 2010: 2241-2248. doi:10.1109/CVPR.2010.5539906.

[8] PEDERSOLI M, VEDALDI A, GONZALEZ J,. A coarse-to-fine approach for fast deformable object detection[J]., 2015, 48(7): 1844-1853. doi: 10.1016/j.patcog.2014.11.006.

[9] ZHU Menglong, ATANASOV N, PAPPAS G J,. Active deformable part models inference[C]. Proceedings of the 13th European Conference on Computer Vision, Zurich, Switzerland, 2014: 281-296. doi: 10.1007/978-3-319- 10584-0_19.

[10] KOKKINOS I. Bounding part scores for rapid detection with deformable part models[C]. Proceedings of the 12th European Conference on Computer Vision, Firenze, Italy, 2012: 41-50. doi: 10.1007/978-3-642-33885-4_5.

[11] LIU Qi, HUANG Zi, and HU Fuqiao. Accelerating convolution-based detection model on GPU[C]. Proceedings of the IEEE Estimation, Detection and Information Fusion, Harbin, China, 2015: 61-66. doi: 10.1109/ICEDIF.2015. 7280163.

[12] DUBOUT C and FLEURET F. Exact acceleration of linear object detectors[C]. Proceedings of the 12th European Conference on Computer Vision, Firenze, Italy, 2012: 301-311. doi: 10.1007/978-3-642-33712-3_22.

[13] YAN Junjie, LEI Zhen, WEN Longyin,. The fastest deformable part model for object detection[C]. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition,Columbus, USA, 2014: 2497-2504. doi: 10.1109/CVPR.2014.320.

[14] SONG H O, GIRSHICK R, ZICKLER S,. Generalized sparselet models for real-time multiclass object recognition[J]., 2015, 37(5): 1001-1012. doi: 10.1109/TPAMI. 2014.2353631.

[15] PIRSIAVASH H. Steerable part models[C]. Proceedings of the 2012 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Providence, USA, 2012: 3226-3233. doi: 10.1109/CVPR.2012.6248058.

[16] KOKKINOS I. Shufflets: shared mid-level parts for fast object detection[C]. Proceedings of the 14th International Conference on Computer Vision, Sydney, Australia, 2013: 1393-1400. doi: 10.1109/ICCV.2013.176.

[17] DEAN T, RUZON M, SEGAL M,. Fast, accurate detection of 100,000 object classes on a single machine[C]. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Portland, USA, 2013: 1814-1821. doi: 10.1109/CVPR.2013.237.

[18] RUDERM D L. The statistics of natural images[J]., 2009, 5(4): 517-548. doi: 10.1088/0954-898X_5_4_006.

[19] DOLLAR P, APPEL R, BELONGIE S,. Fast feature pyramids for object detection[J]., 2014, 36(8): 1532-1545. doi: 10.1109/TPAMI.2014.2300479.

[20] HOSANG J, BENENSON R, DOLLAR P,. What makes for effective detection proposals?[J]., 2016, 38(4): 814-830. doi: 10.1109/TPAMI.2015.2465908.

Rapid Object Detection Algorithm Based on Deformable Part Models

LI Chunwei YU Hongtao LI Shaomei BU Youjun

(&,450002,)

To solve the speed bottleneck of deformable part models in the detection process, this paper proposes a cascade deformable part model with rapid computation of feature pyramids for the detection process of the model. Because the speed of the detection is mainly determined by the two processes of the feature computation and the object location, a two-stage speedup algorithm is proposed. Firstly, sparsely-sampled feature pyramids on the scale are utilized to approximate finely-sampled multi-scale image features to speed up the process of feature computation. Then combined with the cascade algorithm in the location process, a sequence model is utilized to evaluate individual parts sequentially so as to rapidly prune most object hypotheses of small possibilities in order to speed up the process of object location. The experimental results on PASCAL VOC 2007 dataset and INRIA dataset show that the algorithm in the paper apparently speeds up the speed of detection with minor loss in detection precision.

Rapid object detection; Deformable part model; Feature computation; Cascade detection

TP391.4

A

1009-5896(2016)11-2864-07

10.11999/JEIT160080

2016-01-19；改回日期：2016-06-08；

2016-09-01

李春偉 lichunwei15@126.com

國家自然科學基金(61572519, 61521003)

The National Natural Science Foundation of China (61572519, 61521003)

李春偉： 男，1991年生，博士，研究方向為圖像處理、計算機視覺.

于洪濤： 男，1970年生，研究員，研究方向為通信、信息系統、社交網絡.

李邵梅： 女，1982年生，講師，研究方向為通信，信息系統、圖像處理.

卜佑軍： 男，1978年生，講師，研究方向為通信、信息系統.