鄰域粗糙集約簡(jiǎn)算法在圖像特征選擇中的應(yīng)用

成 婷，張 擴(kuò)，續(xù)欣瑩

（太原理工大學(xué) 信息工程學(xué)院，山西 晉中 030060）

0 引 言

當(dāng)前社會(huì)的數(shù)據(jù)迅速地增長(zhǎng)，且數(shù)據(jù)處于動(dòng)態(tài)更新的狀態(tài)，需要高效準(zhǔn)確地處理這些新增樣本是研究的重點(diǎn)。文獻(xiàn)[1]提出鄰域關(guān)系模型，文獻(xiàn)[2-3]改進(jìn)了該模型，提出代數(shù)觀下基于鄰域模型的數(shù)值型數(shù)據(jù)屬性約簡(jiǎn)算法，但該算法為靜態(tài)約簡(jiǎn)算法?，F(xiàn)在已經(jīng)有學(xué)者在其基礎(chǔ)上提出動(dòng)態(tài)約簡(jiǎn)算法，這些算法都從代數(shù)觀分析其動(dòng)態(tài)更新過(guò)程。而通過(guò)文獻(xiàn)[4]可知信息觀在不一致決策方面要優(yōu)于代數(shù)觀。因此，從信息觀研究基于鄰域粗糙集的動(dòng)態(tài)約簡(jiǎn)算法具有重要的理論意義。

行人檢測(cè)在計(jì)算機(jī)視覺(jué)等領(lǐng)域有著重要的應(yīng)用[4-6]。目前基于計(jì)算機(jī)視覺(jué)的行人檢測(cè)大多是基于特征提取和機(jī)器學(xué)習(xí)的方法[7-9]。運(yùn)用特征描述行人與背景的區(qū)別。經(jīng)過(guò)這些年的科學(xué)發(fā)展，學(xué)者已經(jīng)提出很多有效的行人檢測(cè)算法，如 HOG[10]，LBP[11]，CSS[12]，EOH[13]，Edgelet[14]，Shapelet[15]等。

在以上這些特征中，最具代表性的為Dalal等提出的HOG特征，利用圖像得到相關(guān)區(qū)域的梯度直方圖對(duì)行人進(jìn)行描述。但該特征在某些方面也存在著不足之處：向量維數(shù)高、計(jì)算所需時(shí)間較長(zhǎng)。

針對(duì)上述問(wèn)題，本文提出一種基于增量式場(chǎng)景圖像特征選擇的鄰域粗糙集約簡(jiǎn)算法，該算法在增加圖像樣本后利用HOG特征，求出原圖像集的條件熵，給出新增樣本后條件熵的計(jì)算公式，當(dāng)原圖像樣本約簡(jiǎn)集失效時(shí)，可以知道是新增的圖像樣本集中的某個(gè)或者某些樣本使得條件熵發(fā)生了改變，再進(jìn)行約簡(jiǎn)時(shí)，只需得到這些樣本以及它們的不一致鄰域，然后進(jìn)行約簡(jiǎn)，最后再反向剔除原約簡(jiǎn)集中的冗余特征，得出最終的特征集。

1 相關(guān)知識(shí)

定義 1[16]：給定有限集合U={u1,u2,…,un}，δ＞ 0，對(duì)于U上任意對(duì)象ui，定義其δ鄰域?yàn)椋害?ui)={ |uΔ(u,ui)≤δ}，其中距離函數(shù)Δ滿足：

1）Δ(u1,u2)≥0，Δ(u1,u2)=0當(dāng)且僅當(dāng)u1=u2,?u1,u2∈RN；

2）Δ(u1,u2)=Δ(u2,u1),?u1,u2∈RN；

3）Δ(u1,u2)≤Δ(u1,u2)+Δ(u2,u3),?u1,u2,u3∈RN。

定理1：樣本的相似性可以通過(guò)距離函數(shù)衡量，兩個(gè)樣本的距離越近越相似，兩個(gè)樣本的距離越遠(yuǎn)越不相似。

定理2[17]：同定義2設(shè)定NDT，M?C，則M為C中的約簡(jiǎn)的條件為

定義3[3]：同定義2設(shè)定NDT，B?C，對(duì)?a∈C-B，a相對(duì)于B的重要度定義為：

2 增量式特征選擇

2.1 基于條件熵的屬性約簡(jiǎn)

文獻(xiàn)[18]提出基于信息熵的屬性約簡(jiǎn)算法（簡(jiǎn)稱為ARACE算法），該算法是基于信息熵下的啟發(fā)式約簡(jiǎn)算法，算法流程圖如圖1所示。

圖1 ARACE算法流程圖Fig.1 Flowchart of ARACE algorithm

文獻(xiàn)[19]在文獻(xiàn)[18]的基礎(chǔ)上對(duì)算法進(jìn)行改進(jìn)，給出新的信息熵模型，提出ADEAR算法，該算法能夠得到更好的約簡(jiǎn)結(jié)果以及約簡(jiǎn)精度。

2.2 基于鄰域系統(tǒng)下條件熵的增量式屬性約簡(jiǎn)

2.2.1 批量增加樣本后條件熵的計(jì)算公式

定義4：同定義2設(shè)定NDT，B?C是條件屬性集，為屬性B的條件熵，δB(x)為樣本x在屬性集B上的鄰域，δD(x)為樣本x在屬性集B上的決策類，增加一個(gè)樣本x后，新的條件熵為：

推論1：同定義4的設(shè)定條件，當(dāng)批增加m個(gè)樣本Um后，得到的條件熵為：

證明：用迭代法進(jìn)行求證。

當(dāng)加入其中一個(gè)樣本后，條件熵變?yōu)椋?/p>

令U1=U∪{x1}，再加入一個(gè)樣本后，條件熵變?yōu)椋?/p>

最后當(dāng)增加第m個(gè)對(duì)象xm后，條件熵變?yōu)椋?/p>

2.2.2 批量增加樣本后約簡(jiǎn)算法分析

批量增加樣本之后，可以利用上述的條件熵公式，再通過(guò)基于信息熵下的屬性約簡(jiǎn)算法對(duì)新增樣本后的樣本集進(jìn)行屬性約簡(jiǎn)，接下來(lái)對(duì)算法進(jìn)行相關(guān)分析。

定理3：同定義2設(shè)定NDT，原約簡(jiǎn)集red0，增加的樣本集x，當(dāng)新增樣本在red0下不存在不一致鄰域，新樣本集下的約簡(jiǎn)集為red0。

證明：由 red0? C，得到δred0-D(x)?δC-D(x)，如果δC-D(x)為?，則δred0-D(x)為?，即：

EU?{x}(D| RED0)=EU?{x}(D|C)，red0為新樣本集下的約簡(jiǎn)集。

定理4：同定義2設(shè)定NDT，原約簡(jiǎn)集red0，當(dāng)red0不再有效，運(yùn)用算法得到新約簡(jiǎn)集red1，并將red0冗余去除得到red2，則red2?red1為新約簡(jiǎn)集。

證明：red0可以區(qū)分U-δred0-D(x)，而 red2可區(qū)分δred0-D(x)，所以red2? red1可區(qū)分U?{x}。

2.3 HOG特征提取

在計(jì)算HOG特征時(shí)，首先提出HOG描述子概念，它由圖像劃分出互相不相交的像素塊（cell）表示，進(jìn)而通過(guò)相關(guān)公式計(jì)算梯度方向來(lái)描述圖像中的局部特征[8]。

將圖像分成m×t個(gè)cell塊，將n×n的cell組成一個(gè)block塊，相鄰的block塊可以重疊，這樣block塊之間能夠銜接起來(lái)，而不是徹底劃分開(kāi)。然后將各block塊中cell的梯度方向進(jìn)行歸一化處理，經(jīng)過(guò)歸一化處理的梯度方向形成了圖像的所有的HOG特征。HOG特征提取的具體過(guò)程如下：

1）輸入圖像；

2）將圖像劃分成cell塊；

3）求每個(gè)cell的梯度方向；

4）將cell組成bolck塊；

5）將block塊中的所有梯度方向進(jìn)行歸一化；

6）獲得HOG特征。

本次實(shí)驗(yàn)選取的圖像集是麻省理工學(xué)院提供的128×64的Pedestrian Data圖像集和128×64 INRIA圖像集，其中將Pedestrian Data有目標(biāo)的圖像集作為正樣本，將無(wú)目標(biāo)的INRIA圖像集作為負(fù)樣本。HOG特征示意圖如圖2所示。圖像原始維數(shù)為128×64，將圖像分成16×8個(gè)cell，每個(gè) cell是8×8像素，每2×2個(gè) cell組成一個(gè) block塊，那么總的block塊數(shù)為15×7=105塊。梯度方向選擇為每20°一個(gè)分區(qū)，一共180°，所以一個(gè)cell可以得到9維HOG特征，一個(gè)block塊得到36維HOG特征，一幅圖像包含105塊block，那么總HOG特征為105×36=3 780維。

雖然圖像集能夠提取3 780維特征，但是特征集存在大量的冗余，極大地影響了運(yùn)行的速度，浪費(fèi)了大量不必要的時(shí)間。為此需要運(yùn)用2.2節(jié)提出的基于鄰域系統(tǒng)下條件熵的批增量式屬性約簡(jiǎn)算法，對(duì)特征集進(jìn)行選擇。

2.4 基于鄰域系統(tǒng)下條件熵的增量式屬性約簡(jiǎn)在場(chǎng)景圖像下的應(yīng)用

由于圖像集采用的HOG特征具有高維的特點(diǎn)，如果直接采用ARACE，ADEAR算法，約簡(jiǎn)過(guò)程會(huì)需要很長(zhǎng)的時(shí)間，使得特征選擇的思想失去了意義，此時(shí)需要將該算法進(jìn)行改進(jìn)，使算法能夠迅速地處理高維特征的數(shù)據(jù)集。采用2.2節(jié)提出的算法能夠解決上述問(wèn)題，將該算法應(yīng)用到圖像集的特征提取中，能夠顯著提升約簡(jiǎn)時(shí)間、約簡(jiǎn)精度等。算法的特征選擇大體流程如下所示：

1）從2.3節(jié)得到圖像集的HOG特征；

2）以block塊為單位進(jìn)行約簡(jiǎn)，得到可以完全表征圖像的 block塊；

3）對(duì)步驟2）得到的block塊進(jìn)行約簡(jiǎn)；

4）得到最終選擇的特征集。

從2.3節(jié)可以知道，整個(gè)HOG特征由block組成，將每一個(gè)block塊（36維特征）作為一個(gè)單元特征，利用2.2節(jié)算法進(jìn)行約簡(jiǎn)之后，對(duì)約簡(jiǎn)后得到的block塊下的所有特征進(jìn)行組合，再運(yùn)用2.2節(jié)算法進(jìn)行約簡(jiǎn)，最終求得特征集。

圖2 HOG特征示意圖Fig.2 Diagram of HOG characteristic

2.5 基于增量式場(chǎng)景圖像特征選擇的鄰域粗糙集約簡(jiǎn)算法描述

通過(guò)以上分析，BIIAR算法描述如下：

選取圖像集，把圖像集打上標(biāo)簽，并將正負(fù)樣本隨機(jī)打亂，通過(guò)2.3節(jié)得到這些圖像集的HOG特征，選取部分樣本，并將其組成鄰域決策系統(tǒng)NDT=＜U,C,D＞，將C中每36維設(shè)為一個(gè)block，并對(duì)這105維block塊進(jìn)行約簡(jiǎn)，得到約簡(jiǎn)集RED，再對(duì)RED進(jìn)行二次約簡(jiǎn)得到該系統(tǒng)的原特征集red0，條件熵EU(D|C)。同時(shí)將剩余樣本分成n份，每份設(shè)為Xi（i=1,2,…,n）。

輸入：鄰域決策系統(tǒng)NDT=＜U,C,D＞，原約簡(jiǎn)集red0，條件熵EU(D|C)，樣本集Xi

輸出：約簡(jiǎn)后圖像集剩余block塊的位置S，特征集red

Step1：初始化距離函數(shù)Δ和鄰域半徑δ

Step2：判斷Xi是否為空集

Step3：計(jì)算新增樣本集Xi在原約簡(jiǎn)集上的red0不一致鄰域δred0-D(Xi)

Step4：計(jì)算新增樣本集Xi在條件屬性集C上的不一致鄰域δC-D(Xi)

Step5：計(jì)算新增樣本集Xi在屬性集RED上的不一致鄰域δRED-D(Xi)

Step6：設(shè)δRED-D(Xi)與新增樣本集Xi組成樣本集Y，計(jì)算樣本Y在條件屬性集C上的不一致鄰域δC-D(Y)

Step7：對(duì)樣本Y建立條件屬性為C-RED的臨時(shí)鄰域決策系統(tǒng)，并將C-RED以block塊為單元，求該臨時(shí)鄰域決策系統(tǒng)的約簡(jiǎn)RED1，令REDnew=RED1? RED

Step8：將RED分成block塊為Zt（t=1，2，…，n），計(jì)算條件熵EY(D|Zt)，并按該條件熵大小對(duì)Zt降序排列

按照上述排列順序計(jì)算EY(D|REDnew-Zi)

Step9：得出REDnew對(duì)應(yīng)的圖像集中block塊的位置S

Step10：將U與新增樣本集Xi組成樣本集W，并建立條件屬性REDnew的臨時(shí)鄰域決策系統(tǒng)，并對(duì)臨時(shí)鄰域決策系統(tǒng)約簡(jiǎn)，得到特征集red

Step11：輸出red

REDnew對(duì)應(yīng)的block塊即為加入樣本集Xi后可以完全表征新圖像的block塊，red為新圖像集可以表征圖像的特征。

Step8中二次約簡(jiǎn)的算法流程如下：

輸入：將δred0-D(Xi)與新增樣本集Xi組成樣本集R，樣本集W，令E=EW(D|C)，REDnew

輸出：特征集red

Step1：初始化距離函數(shù)Δ和鄰域半徑δ

Step2：在REDnew中尋找與red0相等的特征，記為F

Step3：計(jì)算樣本R在條件屬性集F上的不一致鄰域δF-D(R)，

Step4：對(duì)樣本集R，建立條件屬性為C-F的臨時(shí)鄰域決策系統(tǒng)，并求該臨時(shí)鄰域決策系統(tǒng)的約簡(jiǎn)red2，令red=F?red2

Step5：對(duì)?ai∈F計(jì)算條件熵EW(D|C)，并按該條件熵大小對(duì)ai降序排列

按照上述排列順序計(jì)算EW(D|red-{aj})

Step6：輸出red

算法時(shí)間復(fù)雜度分析：設(shè)U中的樣本數(shù)為m，Xi中的樣本數(shù)為m1，原數(shù)據(jù)集條件屬性個(gè)數(shù)為N，原數(shù)據(jù)集中含有的block數(shù)為N1，原數(shù)據(jù)集的約簡(jiǎn)個(gè)數(shù)為N2，Xi在U下的不一致鄰域的樣本個(gè)數(shù)為m2，Xi在RED上的不一致鄰域的樣本個(gè)數(shù)為m3，樣本m3與Xi不一致鄰域的樣本個(gè)數(shù)為m4，REDnew中樣本組成的block個(gè)數(shù)為N3，REDnew中與red0相等的特征個(gè)數(shù)為N4，RED中樣本組成的 block個(gè)數(shù)為N5，red2中樣本的N4個(gè)數(shù)為N6。

3 實(shí)驗(yàn)分析

通過(guò)與ARACE算法、ADEAR算法進(jìn)行實(shí)驗(yàn)對(duì)比驗(yàn)證BIIAR的準(zhǔn)確性和高效性。

3.1 約簡(jiǎn)情況

圖3a）和圖4a）表示當(dāng)鄰域閾值δ=0.17時(shí)三種算法每次新增樣本之后約簡(jiǎn)后的特征維數(shù)和block數(shù)，其中圖3a）中三條線分別表示三種算法約簡(jiǎn)后的特征維數(shù)，圖4a）中三條線分別表示三種算法約簡(jiǎn)后的 block數(shù)。從中可以看出三種算法約簡(jiǎn)后的block數(shù)幾乎一致，而且特征維數(shù)也很接近，驗(yàn)證了BIINR算法的有效性。

圖3 當(dāng)鄰域閾值δ分別為0.17和0.21時(shí)三種算法約簡(jiǎn)后的特征維數(shù)對(duì)比圖Fig.3 Comparison of characteristic dimensions after reduction with three algorithms asδ=0.17 andδ=0.21 respectively

圖3b）和圖4b）表示當(dāng)鄰域閾值δ=0.21時(shí)三種算法每次新增樣本之后約簡(jiǎn)的block維數(shù)和特征維數(shù)，其中圖3b）中三條線分別表示三種算法約簡(jiǎn)后的特征維數(shù)，圖4b）中三條線分別表示三種算法約簡(jiǎn)后的 block數(shù)。從中可以看出三種算法約簡(jiǎn)后的block數(shù)基本一致，而且特征維數(shù)基本保持一致。

圖4 當(dāng)鄰域閾值δ分別為0.17和0.21時(shí)三種算法block數(shù)對(duì)比圖Fig.4 Comparison of block number of three algorithms as δ=0.17 and δ=0.21 respectively

總結(jié)：從圖3，圖4可以看出，當(dāng)鄰域閾值δ=0.17時(shí)三種算法約簡(jiǎn)后的block數(shù)遠(yuǎn)少于當(dāng)鄰域閾值δ=0.21時(shí)三種算法約簡(jiǎn)后的block數(shù)。從圖4b）中可以看出，BIINR算法在δ=0.21時(shí)所選擇的43維block塊存在冗余屬性，而且從圖5b）中可以看出，BIINR算法在δ=0.17時(shí)所選擇的9維block塊特征主要集中在行人的頭部和四肢部分，基本能夠表現(xiàn)特征選擇，說(shuō)明鄰域閾值δ=0.17時(shí)得到的結(jié)果更好。最后從得到的結(jié)果來(lái)看，BIINR算法的改進(jìn)思想是可行的，可以實(shí)現(xiàn)動(dòng)態(tài)約簡(jiǎn)。

3.2 運(yùn)行時(shí)間情況

增量式算法的核心思想不僅要求動(dòng)態(tài)約簡(jiǎn)，而且還要求算法的高效性，通過(guò)實(shí)驗(yàn)得到的三種算法約簡(jiǎn)的高效性實(shí)驗(yàn)結(jié)果如圖6所示。

圖5 約簡(jiǎn)得到的block塊示意圖Fig.5 Schematic diagram of the block gotten by reduction

圖6 三種算法約簡(jiǎn)運(yùn)行時(shí)間對(duì)比圖Fig.6 Comparison of running time of three reduced algorithms

圖6a）為當(dāng)鄰域閾值δ=0.21時(shí)三種算法的運(yùn)行時(shí)間，從圖中可以看出BIINR算法在新增樣本后運(yùn)行時(shí)間明顯低于ARACE算法和ADEAR算法，其中BIINR算法在第二個(gè)階段和倒數(shù)第二個(gè)階段新增樣本中斜率明顯偏高，說(shuō)明這兩個(gè)階段中引起約簡(jiǎn)集變化的新增圖像較多，因此算法運(yùn)行時(shí)間相對(duì)長(zhǎng)一些，而ARACE算法、ADEAR算法整體斜率偏高，運(yùn)行時(shí)間較長(zhǎng)。圖6b）為當(dāng)鄰域閾值δ=0.17時(shí)三種算法的運(yùn)行時(shí)間，從圖中可以看出BIINR算法在新增樣本后運(yùn)行時(shí)間明顯低于ARACE算法和ADEAR算法，其中BIINR算法在第四個(gè)階段和后兩個(gè)階段斜率偏高，說(shuō)明這三個(gè)階段中引起約簡(jiǎn)集變化的新增圖像較多，所以算法運(yùn)行時(shí)間相對(duì)長(zhǎng)一些，而ARACE算法和ADEAR算法同圖6a）中的情況基本相同，算法整體斜率偏高，整體運(yùn)行時(shí)間也是比較長(zhǎng)。綜上所述，BIINR算法高效性能方面要明顯優(yōu)于ARACE算法。

3.3 所得特征在分類器下的精度情況

為了驗(yàn)證三種算法約簡(jiǎn)后的block塊和特征，本文通過(guò)SVM和KNN兩種分類器對(duì)三種算法進(jìn)行精度測(cè)試，對(duì)約簡(jiǎn)后block和特征的數(shù)據(jù)集以十折交叉算法求得兩種分類器下的檢測(cè)精度。實(shí)驗(yàn)結(jié)果如圖7，圖8所示。圖7和圖8為鄰域閾值δ分別為0.17，0.21時(shí)三種算法在增加樣本經(jīng)過(guò)約簡(jiǎn)后在各分類器下的精度值。

圖7 鄰域閾值δ為0.17時(shí)三種算法約簡(jiǎn)后在KNN，SVM分類器下的精度對(duì)比Fig.7 Comparison of thethree algorithms′accurate values detected by KNN and SVM classifiers after reduction of added sample asδ=0.17

圖8 鄰域閾值δ為0.21時(shí)三種算法約簡(jiǎn)后在KNN，SVM分類器下的精度對(duì)比Fig.8 Comparison of the three algorithms′accurate values detected by KNN and SVM classifiers after reduction of added sample asδ=0.21

從圖7，圖8可以看出，無(wú)論鄰域閾值δ為何值，三種算法約簡(jiǎn)后的檢測(cè)精度都十分接近。下面進(jìn)行簡(jiǎn)要分析：

1）當(dāng)鄰域閾值δ=0.17時(shí)

從圖7a）可以看出，KNN分類器下BIINR算法約簡(jiǎn)后的特征以及block塊的平均精度要稍高于ARACE算法、ADEAR算法；從圖7b）可知，SVM分類器下BIINR約簡(jiǎn)后的特征以及block塊的平均精度要基本上都稍高于ARACE算法，ADEAR算法。ARACE算法、ADEAR算法約簡(jiǎn)后的特征平均精度達(dá)到97.44%，98.03%，block塊的平均精度達(dá)到98.02%，98.59%。而B(niǎo)IINR算法約簡(jiǎn)后的特征平均精度達(dá)到98.53%，block塊的平均精度達(dá)到99.15%。

綜上，BIINR算法約簡(jiǎn)后的特征平均精度、約簡(jiǎn)后block的平均精度都要高于ARACE算法、ADEAR算法。

2）當(dāng)鄰域閾值δ=0.21時(shí)

從圖8a）可以看出，KNN分類器下BIINR算法約簡(jiǎn)后的特征平均精度要高于ARACE算法、ADEAR算法，兩種算法約簡(jiǎn)后的block塊的精度相同；從圖8b）可知，在SVM分類器下BIINR約簡(jiǎn)后的特征平均精度要稍微高于ARACE算法、ADEAR算法。ARACE算法、ADEAR算法約簡(jiǎn)后的特征平均精度達(dá)到99.62%，99.51%，BIINR約簡(jiǎn)后的特征平均精度達(dá)到99.69%，三種算法約簡(jiǎn)后的block塊的精度基本相同，ADEAR算法約簡(jiǎn)后的block塊的精度略小于其他兩種算法。

綜上，BIINR算法約簡(jiǎn)后的特征平均精度要高于ARACE算法、ADEAR算法，三種算法約簡(jiǎn)后的block塊的精度基本相同。而且可以知道的是約簡(jiǎn)后的特征平均精度要高于基于block塊約簡(jiǎn)后的平均精度，主要原因是基于三種算法約簡(jiǎn)后的特征去除了block塊中的干擾特征，所以導(dǎo)致三種算法約簡(jiǎn)后的特征平均精度比較高。

4 結(jié) 論

傳統(tǒng)的行人檢測(cè)方法為靜態(tài)特征提取方法，本文提出一種基于增量式場(chǎng)景圖像特征選擇的鄰域粗糙集約簡(jiǎn)算法。首先將圖像集歸一化為樣本集，并打上相應(yīng)的標(biāo)簽；其次在信息觀的角度下結(jié)合圖像數(shù)據(jù)集，給出新增樣本后計(jì)算條件熵的統(tǒng)一公式，并驗(yàn)證了公式的準(zhǔn)確性。當(dāng)有新樣本加入時(shí)，首先判斷是否需要重新約簡(jiǎn)，隨后運(yùn)用提出的算法對(duì)數(shù)據(jù)集進(jìn)行增量計(jì)算，提高了算法的效率，得到更新后的約簡(jiǎn)集以及block塊。通過(guò)實(shí)驗(yàn)與ARACE算法、ADEAR算法進(jìn)行比較，BIINR算法在特征選擇、運(yùn)行時(shí)間、精度這幾個(gè)方面都有著不錯(cuò)的結(jié)果，驗(yàn)證了BIINR算法是可行有效的。