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

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

0 引 言

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

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

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

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

1 相關(guān)知識

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

1）Δ(u1,u2)≥0，Δ(u1,u2)=0當且僅當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：樣本的相似性可以通過距離函數(shù)衡量，兩個樣本的距離越近越相似，兩個樣本的距離越遠越不相似。

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

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

2 增量式特征選擇

2.1 基于條件熵的屬性約簡

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

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

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

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

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

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

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

證明：用迭代法進行求證。

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

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

最后當增加第m個對象xm后，條件熵變?yōu)椋?/p>

2.2.2 批量增加樣本后約簡算法分析

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

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

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

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

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

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

2.3 HOG特征提取

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

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

1）輸入圖像；

2）將圖像劃分成cell塊；

3）求每個cell的梯度方向；

4）將cell組成bolck塊；

5）將block塊中的所有梯度方向進行歸一化；

6）獲得HOG特征。

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

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

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

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

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

2）以block塊為單位進行約簡，得到可以完全表征圖像的 block塊；

3）對步驟2）得到的block塊進行約簡；

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

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

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

2.5 基于增量式場景圖像特征選擇的鄰域粗糙集約簡算法描述

通過以上分析，BIIAR算法描述如下：

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

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

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

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

Step2：判斷Xi是否為空集

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

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

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

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

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

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

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

Step9：得出REDnew對應的圖像集中block塊的位置S

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

Step11：輸出red

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

Step8中二次約簡的算法流程如下：

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

輸出：特征集red

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

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

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

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

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

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

Step6：輸出red

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

3 實驗分析

通過與ARACE算法、ADEAR算法進行實驗對比驗證BIIAR的準確性和高效性。

3.1 約簡情況

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

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

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

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

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

3.2 運行時間情況

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

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

圖6 三種算法約簡運行時間對比圖Fig.6 Comparison of running time of three reduced algorithms

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

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

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

圖7 鄰域閾值δ為0.17時三種算法約簡后在KNN，SVM分類器下的精度對比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時三種算法約簡后在KNN，SVM分類器下的精度對比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可以看出，無論鄰域閾值δ為何值，三種算法約簡后的檢測精度都十分接近。下面進行簡要分析：

1）當鄰域閾值δ=0.17時

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

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

2）當鄰域閾值δ=0.21時

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

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

4 結(jié) 論

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