基于組合區域形狀特征的物體檢測算法

王 晏 孫 怡

①(大連理工大學信息與通信工程學院 大連 116024)

②(公安海警學院基礎部 寧波 315801)

1 引言

基于特征的目標檢測是計算機視覺領域中一個重要的研究方向。其基本方法主要包括兩類：第1類方法是對整幅圖像進行特征變換，在特征圖像中搜索符合待檢目標特征的片斷，通過片斷之間的聯系確定待檢目標的位置等信息。典型的算法如Vittorio等人[1,2]提出的基于局部輪廓特征的目標檢測算法。在后續的研究中，作者用支持向量機分類的方法代替了特征匹配方法[3]，用主動形變模型替代了手繪模型[4]。孫顯等人[5]也作了相關的研究。此類方法雖然取得了較好的檢測效果，但其算法結構相對復雜，對分割的要求較高。第2類方法是用多尺度窗遍歷圖像，判斷窗內是否含有待檢測目標或目標的一部分[6]。典型的算法如 Felzenszwalb等人[7]提出的一種基于多尺度、可變形物體部件模型的目標檢測算法。作者后續針對固定尺度模型提出了可變尺度混合模型[8]，又提出層級結構解決了速度問題[9]。類似的方法還有如張正等人[10]提出的基于部件的自動目標檢測方法。但這類算法還是存在一些需要改進的方面：(1)不能給出目標的具體輪廓；(2)目標結構相對固定，針對不同復雜圖案的目標存在一定的局限；(3)并非所有其他基于窗遍歷的方法都能解決速度瓶頸問題。鑒于以上分析，本文實現了一種基于組合區域形狀特征的目標檢測算法，降低了對分割的要求，可得到目標的準確輪廓信息，不要求目標內部結構相對固定；同時，通過訓練并聯支持向量機分類器和對目標特征循環移位檢測，保證了目標特征的旋轉不變性。

2 組合區域形狀特征提取

2.1 候選目標選取

采用矩形框遍歷的方法不能標示出目標輪廓信息，耗時較長；而直接將圖像分割的方法對圖像分割要求較高。因此，本文實現了一種根據圖像分割區域之間的關系提取候選目標的方法。將待檢測圖像分割成不同的單連通域，則待檢目標一定是其中某些單連通域的組合。因此，本文在可能的單連通域組合中提取候選目標，過程如圖1所示，圖1(a)為原始圖像，圖1(b)為待檢目標，圖1(c)為圖1(a)的分割結果，圖1(d)為分割后的單連通區域，圖1(e)為所有單連通區域可能的組合圖像，圖1(f)為本文所提取的候選目標。

首先，將圖像分割成不同的單連通域。采用本文之前完成的自適應 Mean shift 算法[11]將圖像分割。傳統Mean shift 算法用于圖像分割時沒有討論采樣點權重的影響，常采用固定帶寬，即使運用自適應帶寬，也是完全從數據優化方面考慮的，沒有考慮人眼的主觀視覺特性。本文之前完成的自適應Mean shift 算法根據圖像的顏色分布信息自適應選取了空域帶寬。在此基礎上，將評價圖像質量的客觀標準即頻域結構相似度，與圖像方差結合起來，建立了選擇值域帶寬的目標函數，從而使所選擇帶寬對應的分割圖像更符合人眼的視覺特性，使分割的區域不會太細或太粗，正確表達了待檢測目標的整體性。分割算法詳見文獻[11]，分割結果如圖1(c)所示，將分割后的每個單連通區域記為ri(i=1,2,…,n)，如圖1(d)所示，n表示所分割的單連通域總數，n=1 4。

其次，在n個單連通域中，任意選取p個形成一個新圖像，記為Ik(k=1,2,…,n um)，例如，r2,r8和r14可以組合成新圖像I1，組合后的新圖像如圖1(e)所示，p取值為1,2,3,…,n-1,num表示所有新圖像總數目，即

圖1 候選目標示意圖

表示從n個單連通域中任選p個進行組合的數目。在新圖像中，有些含有多個連通域，如圖1(e)中的I4，有些含有空洞，如圖1(e)中的I2。本文特征提取中，只需要目標的外邊界信息，因此，只將新圖像中連通域個數為1并且不含空洞的圖像作為候選目標，結果如圖1(f)所示。可以看出，總會存在一種組合圖像與待檢目標相吻合。進而可以通過后續的特征提取，運用支持向量機分類器對候選目標進行檢測。上述候選目標選取方法降低了分割要求，最終得到的不是表示目標位置和大小的矩形框信息，而是目標本身。

2.2 目標形狀特征提取

常用特征中，顏色特征[12,13]和紋理特征[14]容易受到目標表面顏色或紋理以及光線的影響。圖像變換特征[15,16]，容易受到目標表面圖案或形變的影響。因此，對于一般的目標檢測，形狀特征的適應性相對更好。形狀特征分為全局特征和局部特征，全局特征如幾何不變矩，對圖像的局部變化比較敏感[17]。局部形狀特征[18-20]都是基于邊界采樣點定義的，采用的是點匹配方法。在采用基于學習的分類方法時，存在待檢目標特征向量的維數及元素順序與樣本特征向量不一致的問題，從而不能保證目標特征的旋轉不變性。

為此，本節目的是尋找一種相對簡單的形狀特征，既能有效表達目標，又便于分類器的學習。如圖2(a)所示，在目標的邊界曲線上，以dot點為起點，將目標邊界按順時針方向分成等弧長m段，將每段弧順序標記為sj(j=1,2,…,m),sj對應的弦記為lj,lj為有向線段，走向為順時針方向。定義θj為從線段lj到lj+1按順時針方向的夾角。如果以第1段弧s1為起始弧，則相鄰線段之間的夾角序列為θ=[θ1,θ2,…,θm]，將此序列稱為夾角鏈碼[21]，它能準確地描述目標的整體形狀特征，并且不容易受到局部噪聲的干擾。但每一段弧對應的形狀特征并沒有表達在夾角鏈碼中，因此，本文定義了弧sj到弦lj的距離最大值與弦長的比值，即弧弦距比作為目標的另一個特征，即

其中dj表示弧sj到弦lj的最大距離。如果以第 1段弧s1為起始弧，由rj構成的序列為r=(r1,r2,…,rm)，它可以有效表達弧sj的彎曲程度。將θ和r共同構成的向量作為目標特征向量，記為v，即v=(θ,r)。

在上述特征提取過程中，如果起點不同，對應分段就不同，則相鄰兩段夾角不同。在起點相同的情況下，如果選擇的起始弧不同，則特征向量中元素順序不同，不同起始弧對應的特征向量之間存在一個相移。因此，要保證目標特征的旋轉不變性，則要求待檢目標與樣本起點與起始弧一致，但在實際檢測中很難做到這一點。因此，本文通過構造并聯支持向量機實現待檢目標與樣本起點一致，通過對特征向量進行循環移位來克服起始弧不一致所導致的相移問題。

3 支持向量機分類器

如上所述，要保證目標特征的旋轉不變性，則要求待檢目標與樣本的分段一致，并且計算特征向量時對應起始弧一致。

首先分析分段一致性問題，如圖2(a)所示，如果以dot為起點，則分段后的段點依次為 d ot1,dot2,…,d otj-1,…,d otm-1，由于采用等弧長分段，因此，起點分別為 d ot1,dot2,…,d otj-1,…,d otm-1時對應的分段情況與以dot為起點時的分段情況是一致的。同理，在第1段弧s1上等弧長地取N個點 d ot1,dot2,…,d otN，如圖2(b)所示，以這N個點中任意點為起點的分段情況和以其他段相應位置點為起點的分段情況是一致的。因此，本文在提取樣本特征時，只取弧s1上的N+1個點，即 d ot,dot1,dot2,…,d otN作為分段所有情況。然后分別計算上述N+ 1 個起點分段對應的樣本特征向量，記為vt0,vt1,…,vtN，分別訓練不同的支持向量機分類器SVM0,SVM1,…,S VMN，如圖3所示。其中，假設每個支持向量機對應的樣本總數為a，則vt0,vt1,…,vtN分別是一個a行的矩陣，每一行對應一個樣本特征向量。這種并聯的支持向量機分類器結構可以保證，以待檢目標邊界上任意一點為起點對應的分段情況與訓練樣本的分段情況都是一致的。但是，即使在分段一致的情況下，如果計算特征向量時所選取的起始弧不同，則特征向量元素的順序就不同，不同起始弧對應的特征向量之間存在相移。例如，在以圖2(a)中的dot為起點分段的情況下，如果起始弧為s1，則對應的鏈碼夾角向量為[θ1,θ2,…,θm]，如果以s2為起始弧，對應的鏈碼夾角向量為[θ2,θ3,…,θm,θ1]。為此，在提取候選目標特征后，將其特征向量進行m-1次循環移位，如圖3所示的vd0,vd1,…,vdm-1，其中，vd1是將vd0進行一次循環移位的結果，同理，vdm-1是將vd0進行m-1次循環移位的結果，移位過程如式(3)所示，其中，θ和r的含義同本文2.2節中所述相同。

圖2 特征提取示意圖

圖3 支持向量機分類器

通過選取不同起點對應的樣本特征向量vt0,vt1,…,vtN分別訓練多個支持向量機分類器SVM0,S VM1,…,S VMN，以及對候選目標特征向量進行循環移位檢測，保證了目標特征的旋轉不變性。

4 實驗結果分析

算法采用Matlab語言編寫，實驗環境為酷睿2 CPU(2 GHz),2 G內存。訓練樣本為實際拍攝圖像，運用本文2.1節中的方法將單連通域組合成新圖像，人工從中挑選出目標圖像作為正樣本，其他圖像作為負樣本。檢測圖像一部分來源于 ETHZ圖像類庫[1]，另一部分來源于實際拍攝圖像。實驗中，將樣本和候選目標大小均歸一化為150×150像素，為了保證目標不變，將目標外接矩形的長邊歸一化為150像素，短邊按照與長邊相同的比例進行縮放，其他像素位置補 0。根據歸一化后目標的大小，將分段參數設置為m=2 0,N=1 0是比較合理的。

(1)本文特征與Hu矩對比 為了說明本文所選特征的有效性，將其與經典的Hu矩[22]進行了對比。因為是兩種特征之間的對比，不適于用傳統類間距與類內間距對比，因此，將提取的夾角鏈碼和7個Hu矩用2維曲線畫在圖中。圖4是同一類目標的夾角鏈碼特征與Hu矩特征，圖4(a),4(b)為2幅不同角度的塑料管和鴨子圖像，圖4(c1)，圖4(d1)是其夾角鏈碼特征，圖4(c2)，圖4(d2)是其Hu矩特征，實線和虛線分別表示不同角度的圖像特征。可以看出夾角鏈碼特征和 Hu矩特征都能較有效地表達同一類目標。圖5是不同類目標的夾角鏈碼特征和Hu矩特征，其中圖5(a),5(b)分別為塑料管、面包、鴨子和杯子的原始圖像，圖5(c1)，圖5(d1)是夾角鏈碼特征，圖5(c2)，圖5(d2)是Hu矩特征。實線和虛線分別表示不同的目標。從圖5中可以看出，對于不同類的目標，Hu矩特征的區分能力不如夾角鏈碼好。

圖4 同類目標特征對比

圖5 不同類目標特征對比

此外，本文分別采用 Hu矩特征和鏈碼夾角特征進行了樣本檢測。Hu矩特征的檢測率是87%，而本文特征的檢測率是94%。從檢測率方面相比，本文的特征也優于Hu矩特征。

(2)分割結果對檢測的影響分析 本文采用3組參數下的Mean shift分割算法[11]對目標為杯子的圖像進行分割和檢測，圖6(a),6(b),6(c)分別為3組不同參數下的檢測結果，杯子以白色輪廓標示。參數r,w分別為Mean shift算法的空域帶寬和值域帶寬，本文設置r=8，分別取w=0 .29Wx,w=0.13Wx,w=0 .05Wx,Wx為采樣點與被平滑點差的平均值。

針對3組不同參數，分割單連通域個數不同，但本文方法降低了分割要求，只要目標外邊界輪廓分割沒有嚴重失真，通過單連通域組合，總有一個組合情況與杯子相對應，因此，即使目標內部分割錯誤，也不影響最終檢測結果，只在杯子邊緣部分稍有不同。

此外，表1列出了不同參數對應的單連通域個數、選取候選目標所用的時間和候選目標數，并與基于可變尺度矩形框選取候選目標的方法所用的時間和所確定的候選目標數做了比較。其中，實驗圖像大小為261×349像素，遍歷矩形框初始大小為50 × 50像素，終止大小為200 × 200像素，遍歷步長為2像素。可以看出隨著值域帶寬w減小，分割區域數增加，選取候選目標的時間增多，候選目標數增大。但是，確定候選目標的時間基本不會超過1 s，并不會很大程度上增加檢測時間。而矩形框遍歷的方法所用的時間和確定的候選目標數遠大于本文方法。

圖6 不同分割結果下的檢測結果

表1 不同方法及分割結果對應的候選目標情況

為了驗證本文算法的適應性，分別對杯子圖像進行了模糊和調節對比度操作，對其中比較模糊、嚴重模糊、對比度較低和對比度很低4種情況的圖像進行了檢測，結果用白色輪廓標示在圖7中，結果表明本文對嚴重模糊和對比度很低的圖像都能正確檢測。實際上，針對不同圖像，很難給出一個確定的閾值用來衡量不能檢測目標時所對應的模糊程度和對比度。

(3)目標檢測結果及分析 本文對 ETHZ圖像類庫中48幅杯子圖像、48幅酒瓶圖像和40幅蘋果標志圖像作了檢測實驗，結果以白色輪廓標示在圖8(a)中，結果表明本文算法可以正確檢測待檢目標。此外，在錯誤目標率為0.3的情況下，在表2中統計了杯子圖像的檢測率。其中，錯誤目標率表示非目標被檢為目標的數目與非目標數目之比，檢測率是指檢測出的目標數目與目標總數之比。除本文檢測率之外，其他數據來自文獻[3]。

(a)計算效率：文獻[3]中，不考慮圖像預處理情況，檢測一幅圖像的時間只需要1 s。本文算法在和文獻[3]采用近似相同條件下，不考慮圖像分割和選取候選目標的過程，檢測較為簡單和較為復雜的圖像所用時間范圍為 0.33～2.7 s，部分圖像的檢測時間比文獻[3]長，但文獻[3]是在工作站實現的，硬件環境要好于本文的實驗環境。

(b)計算復雜度：文獻[3]建立kAS積分直方圖的復雜度為將kAS與碼書對應的復雜度為其中，W×H為圖像大小，r為直方圖的空間分辨率，N為kAS的個數，為碼書的大小，k為所取的相鄰段的個數。本文候選目標提取的復雜度為O((A+ 1)×n+A)，特征提取的復雜度為O(gns+gnT)，其中，n為分割的區域數，A為區域的最大像素數，gn為候選目標數，g為比例系數，s為目標邊界的分段數，本文取s=20,T為邊界分段后每段的像素數的最大值。可以看出，本文的算法復雜度和文獻[3]的算法復雜度同階。

(c)表2中本文檢測率略低于 PAS算法檢測率的主要原因，其一是由于分割造成的誤判和漏檢，其二是由于支持向量機分類器產生的誤判和漏檢。

本文算法復雜度與文獻[3]同階，計算時間與文獻[3]相當，檢測率接近文獻[3]的檢測率，但與其相比，本文算法避免了多尺度矩形窗遍歷圖像的方法，對分割要求不高，算法流程結構比較簡單，更易于實現。

本文算法對ETHZ圖像類庫之外背景相對比較復雜或者目標本身結構比較復雜的圖像也可以正確檢測，如圖8(b)所示。但是，對于目標本身顏色與背景顏色近似的圖像，會出現漏檢，如最后一幅杯子圖像。

總之，造成誤判和漏檢的原因有兩個方面：(1)支持向量機分類器產生的誤判和漏檢；(2)由分割造成的誤判和漏檢。

圖7 模糊和低對比度圖像的檢測結果

圖8 目標檢測結果

表2 檢測率表

5 結論

本文針對基于可變尺度矩形框遍歷的候選目標選取方法中存在的問題，實現了一種在分割基礎上組合選取候選目標的方法，此方法既能降低對分割的要求，同時也能在模糊和低對比度圖像中提取出候選目標，可以得到目標的輪廓信息，而不是表示位置和大小的矩形框信息，并且計算時間遠小于基于矩形框遍歷的方法。在此基礎上，提取了目標的夾角鏈碼特征和弧弦距比特征，構造了并聯支持向量機分類器，從而真正保證了目標特征的旋轉不變性。

[1]Vittorio F,Tinne T,and Van Gool L.Object detection by contour segment networks[C].Proceeding of 9th European Conference on Computer Vision.Graz,Austria,2006：14-28.

[2]Vittorio F,Frederic J,and Cordelia S.Accurate object detection with deformable shape models learnt from images[C].Proceeding of IEEE Computer Society Conference on Computer Vision and Pattern Recognition,Minneapolis,USA,2007：564-571.

[3]Vittorio F,Loic F,Frédéric J,et al..Groups of adjacent contour segments for object detection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2008,30(1)：36-51.

[4]Vittorio F,Frederic J,and Cordelia S.From images to shape models for object detection[J].International Journal of Computer Vision,2010,87(3)：284-303.

[5]孫顯,王宏琦,楊志峰.基于形狀統計模型的多類目標自動識別方法[J].電子與信息學報,2009,33(11)：2626-2631.Sun Xian,Wang Hong-qi,and Yang Zhi-feng.Automatic multi-categorical objects recognition using shape statistical models[J].Journal of Electronics＆Information Technology,2009,33(11)：2626-2631.

[6]Mohan A,Papageorgiou C,and Poggio T.Example-based object detection in images by components[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2001,23(4)：349-361.

[7]Felzenszwalb P F,McAllester D,and Ramanan D.A discriminatively trained,multiscale,deformable part model[C].IEEE Conference on Computer Vision and Pattern Recognition,Anchorage,Alaska,USA,2008：1-8.

[8]Felzenszwalb P F,Girshick R B,McAllester D,et al..Object detection with discriminatively trained part-based models[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2010,32(9)：1627-1645.

[9]Felzenszwalb P F,Girshick R B,and McAllester D.Cascade object detection with deformable part models[C].IEEE Conference on Computer Vision and Pattern Recognition,San Francisco,USA,2010：2241-2248.

[10]張正,王宏琦,孫顯,等.基于部件的自動目標檢測方法研究[J].電子與信息學報,2010,32(5)：1017-1022.Zhang Zheng,Wang Hong-qi,Sun Xian,et al..An automatic method for targets detection using a component-based model[J].Journal of Electronics＆Information Technology,2010,32(5)：1017-1022.

[11]王晏,孫怡.自適應mean shift算法的彩色圖像平滑與分割算法[J].自動化學報,2010,36(12)：1637-1644.Wang Yan and Sun Yi.Adaptive mean shift based image smoothing and segmentation[J].Acta Automatica Sinica,2010,36(12)：1637-1644.

[12]Chen Xi-lin,Yang Jie,Zhang Jing,et al..Automatic detection and recognition of signs from natural scenes[J].IEEE Transactions on Image Processing,2004,13(1)：87-99.

[13]Chang Shyang-lih,Chen Li-shien,Chung Yun-chung,et al..Automatic license plate recognition[J].IEEE Transactions on Intelligent Transportation Systems,2004,5(1)：42-53.

[14]Kim Kwang-in,Jung Keechul,Park Se-hyun,et al..Support vector machines for texture classification[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(11)：1542-1550.

[15]Begum N,Alam M,and Islam M I.Application of canny filter and DWT in fingerprint detection[C].13th International Conference on Computer and Information Technology,Cape Town,South Africa,2010：256-260.

[16]Li He-xi,Wang Guo-rong,Shi Yong-hua,et al..The automatic recognition of welding targets based on normalized svd of image matrix[C].Proceeding of the 2007 IEEE International Conference on Mechatronics and Automation,Harbin,China,2007：3100-3104.

[17]Xu Chun-jing,Liu Jian-zhuang,and Tang Xiao-ou.2D shape matching by contour flexibility[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2009,31(1)：180-186.

[18]Chetverikov D.A simple and efficient algorithm for detection of high curvature points in planar curves[C].Proceeding of 10th International Conference on Computer Analysis of Images and Patterns,Groningen,The Netherlands,2003,(2756)：746-753.

[19]Belongie S,Malik J,and Puzicha J.Shape matching and object recognition using shape contexts[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(4)：509-522.

[20]Grigorescu C and Petkov N.Distance sets for shape filters and shape recognition[J].IEEE Transactions on Image Processing,2003,12(10)：1274-1286.

[21]趙宇,陳艷秋.曲線描述的一種方法：夾角鏈碼[J].軟件學報,2004,15(2)：300-307.Zhao Yu and Chen Yan-qiu.Included angle chain：a method for curve representation[J].Journal of Software,2004,15(2)：300-307.

[22]Hu Ming-kuei.Visual pattern recognition by moment invariants[J].IRE Transactions on Information Theory,1962,8(2)：179-187.