基于非負矩陣分解的陰影檢測方法

周鵬宇, 楊 欣, 周大可, 劉 加

(南京航空航天大學(xué) 自動化學(xué)院, 南京 210016)

0 引 言

在計算機視覺領(lǐng)域中, 陰影的存在往往對后續(xù)研究產(chǎn)生不利影響。陰影不僅影響人們視覺判讀效果, 而且在諸如圖像匹配研究中, 將直接影響圖像匹配精度。

近年來, 關(guān)于陰影檢測算法的研究有很多。這些算法大致可以分為兩類: 基于模型方法和基于陰影特征方法?；谀Ｐ头椒俣繕?biāo)的三維幾何結(jié)構(gòu)和光源已知, 而后通過模型計算陰影形狀和位置。該方法適用于某些較簡單的特定場合, 主要原因在于其存在以下兩方面不足[1]： 首先, 對于形狀復(fù)雜物體, 建立模型十分困難； 其次, 該方法需要的光源和目標(biāo)三維形狀的先驗知識難以得到。

基于陰影特征方法是依據(jù)陰影區(qū)域亮度、 顏色和幾何特征實現(xiàn)陰影檢測[2-7]。如, 文獻[2]在3維RGB空間中設(shè)計了計算顏色模型, 通過此模型分離色度和亮度兩個分量, 再通過對比前景和背景對應(yīng)像素點的這兩個分量實現(xiàn)陰影檢測； 文獻[3]中將3個顏色分量看成多光譜影像的3個波段, 而后使用K-L變換, 最終通過分類特性檢測陰影； 文獻[4]先把RGB圖像轉(zhuǎn)化為HSI圖像, 而后通過比對前景與背景對應(yīng)點H、S、I3個分量檢測陰影?；陉幱疤卣鞣椒ㄅc基于模型方法相比, 具有更廣泛的適用性。目前, 大部分研究都屬于第2種方法, 筆者所用方法也屬于此類。

非負矩陣分解(NMF: Non-negative Matrix Factorization)是一種新矩陣分解算法, 與傳統(tǒng)的矩陣分解方法相比, 該方法能保證分解結(jié)果不含負值, 更適用于解決實際問題, 目前已被應(yīng)用于圖像識別領(lǐng)域[8-10]。如, 在文獻[8]中使用NMF算法進行人臉識別, 并對比了3種NMF算法的識別效果； 文獻[9]中對原有NMF算法進行改進, 通過余弦相似分類器和最大相關(guān)分類器實現(xiàn)人臉識別。

雖然NMF算法在模式識別方面具有較好應(yīng)用前景, 但目前其在陰影檢測方面應(yīng)用并不多見。筆者正是針對這一情況, 詳細研究在HSI空間中使用NMF以及BNMF(Block Non-negative Matrix Factorization )進行陰影檢測, 提出了完整的基于NMF和BNMF的陰影檢測算法。實驗結(jié)果表明, 該方法能有效地檢測陰影區(qū)域。

1 基于NMF的陰影檢測

1.1 NMF基本原理

NMF算法由Lee等[11]于1999年提出, 其基本思想描述如下。

對于任意給定的m×n非負矩陣X, 通過NMF算法能找到m×r矩陣W(非負)和r×n矩陣H(非負), 使

Xm×n≈Wm×rHr×n

(1)

其中r一般滿足r

Xj≈h1,jW1+h2,jW2+…+hr,jWr

(2)

NMF算法的一般實現(xiàn)過程如下。

首先, 隨機生成基矩陣W(m×r)和系數(shù)矩陣H(r×n)；而后, 計算WH與原矩陣X的誤差, 如果誤差不滿足要求, 則不斷更新W與H中元素, 直至滿足要求為止。矩陣W與矩陣H的更新方式如下。

更新H一行元素

(3)

更新W相應(yīng)的一列元素

(4)

1.2 基于NMF的陰影檢測算法

非負矩陣分解是一種新矩陣分解方法, 與傳統(tǒng)的矩陣分解方法(如奇異值分解等)相比, NMF能保證分解結(jié)果一定是非負的。從數(shù)學(xué)角度看, 分解結(jié)果存在負值是合理的。但在實際問題中, 負值元素往往沒有意義。例如, 在圖像中, 不存在負值的像素點； 在文檔統(tǒng)計中, 負值也無法解釋?；谝陨显? 考慮到目前還沒有關(guān)于NMF的陰影檢測研究, 筆者給出了基于NMF的陰影檢測方法。

陰影檢測可看成是一種識別問題, 只要識別出陰影所在區(qū)域便可實現(xiàn)陰影檢測。基于NMF的識別步驟如下。

4) 使用分類準(zhǔn)則, 確定x的類屬C(x), 即當(dāng)j=arg ming(x,Li)時,C(x)=j。

1.3 陰影區(qū)范圍的確定

使用上述算法前, 必須考慮陰影區(qū)范圍的確定、 參數(shù)r以及判別函數(shù)的選取問題。在通常情況下, 陰影點與非陰影點的區(qū)分都是依據(jù)亮度、 顏色等特征。這些特征在經(jīng)過NMF分解后, 最終都是通過W、H兩個矩陣體現(xiàn)。然而, 由于矩陣W(m×r)和矩陣H(r×n)維數(shù)與原矩陣維數(shù)(m×n)不同, 如果不能對應(yīng)原圖像矩陣中陰影點的位置, 則進行分類是沒有意義的。為此, 筆者提出了兩種解決方案。

方法1通過公式

(5)

找出W、H和X矩陣坐標(biāo)的對應(yīng)關(guān)系。

式(5)是以式(2)為基礎(chǔ)推導(dǎo)得出的。分析式(5)可以看出,H中的一列元素結(jié)合W的一行元素才能確定一個點。此外, 由于一幅圖像中像素點非常多, 如果每個點都通過式(5)定位, 算法非常復(fù)雜。鑒于上述原因, 筆者采用了第2種方法。

方法2是先將圖像矩陣分解為若干大小相同的小塊, 而后分別對每小塊進行NMF分解。分解后判別類屬, 對應(yīng)的矩陣塊就劃分為陰影區(qū)或非陰影區(qū)。第2種方法的難點在于將原矩陣分解為尺寸合適的小塊, 如果矩陣小塊尺寸偏大, 則檢測誤差變大。如果尺寸偏小, 則會使計算量變大。在該研究中, 為更好地解決該問題, 考慮將原矩陣分解為8×8的小塊。這樣做的目的在于8×8的小塊可以繼續(xù)細分解為4×4或2×2的矩陣塊。在實驗時, 首先使用NMF或BNMF對8×8的小塊進行陰影檢測。而后, 對于誤差較大或暫時不能確定類別的矩陣塊, 可將其細分為4×4或2×2的矩陣塊后繼續(xù)使用NMF或BNMF分類。

1.4 參數(shù)r以及判別函數(shù)的選取

對于參數(shù)r的選取問題, 目前的研究還沒有給出較好的方法。r值的大小反映了特征子空間的維數(shù), 當(dāng)r與實際數(shù)據(jù)集特征空間的維數(shù)基本一致時, 得到的NMF特征子空間對數(shù)據(jù)的夾逼性最好。筆者仿真時選用了多個r值, 而后根據(jù)結(jié)果選出最適合的r。

由于采用基于NMF的陰影檢測, 因此, 實驗所用判別函數(shù)融合了NMF的特點, 即

(6)

2 基于分塊非負矩陣分解的陰影檢測

2.1 分塊非負矩陣分解

NMF算法的分解結(jié)果都是非負的, 因此不同類別系數(shù)矩陣的列向量必然不是正交的。在這種情況下, 由于不能消除不同類別間的相關(guān)性, 檢測結(jié)果必然會受到影響。此外, NMF算法在訓(xùn)練樣本或類別增加時要重復(fù)學(xué)習(xí)。上述的兩個方面, 限制了NMF的實際應(yīng)用。筆者針對這些不足, 引入了分塊非負矩陣分解算法。BNMF算法屬于非負矩陣分解的改進型, 其基本思想如下。

首先, 將一個大矩陣按類別分成若干塊; 而后, 對每塊小矩陣進行NMF分解, 進而得到各自的基矩陣與系數(shù)矩陣; 最后, 將各類基矩陣和系數(shù)矩陣進行合成, 得到總的基矩陣與系數(shù)矩陣。

假設(shè)共有C類樣本, 每類樣本維數(shù)為m×n0,xi為第i類樣本(i=1,2,…,C)。如果有(xi)m×n0≈(Wi)m×r0(Hi)r0×n0, 則BNMF分解結(jié)果可以表示為

(7)

BNMF分解結(jié)果的形式特殊, 如果需要加入新的訓(xùn)練樣本或是新的類別, 可按照如下規(guī)則。

(8)

(9)

分析式(7)可看出, BNMF分解結(jié)果包含所有類別的基矩陣和系數(shù)矩陣, 由于總的系數(shù)矩陣是由各類系數(shù)矩陣對角構(gòu)成。因此, 各類系數(shù)矩陣列向量相互正交, 能消除不同類別間的相關(guān)性, 進而能提高陰影區(qū)和非陰影區(qū)的識別效果。式(8)和式(9)也表明BNMF算法能方便地實現(xiàn)增量的學(xué)習(xí)。更多關(guān)于BNMF的內(nèi)容可以參考文獻[13]。

2.2 基于BNMF的陰影檢測算法

使用BNMF檢測陰影前, 同樣要考慮陰影區(qū)范圍的確定、 參數(shù)r以及判別函數(shù)的選取問題。前兩個問題的解決方法與NMF算法相同, 但由于BNMF形式特殊, 式(6)所示改進判別函數(shù)不再適用?；贐NMF的陰影檢測算法的詳細過程如下:

1) 抽取陰影區(qū)和非陰影區(qū)兩類訓(xùn)練樣本, 每類訓(xùn)練樣本寫成矩陣形式, 即(Xi)m×n0,i=1,2；

2) 使用NMF分解每個(Xi)m×n0, 求出各自的Wi矩陣與Hi矩陣；

h=W+x=(WTW)-1WTx

(10)

3 實驗與分析

圖1 原圖

筆者采用基于陰影特征的陰影檢測方法, 先將RGB圖像轉(zhuǎn)化為HSI圖像, 再根據(jù)圖像的I分量判定是否為陰影。實驗選用一段交通視頻中的第150幀圖像進行算法驗證, 為了便于圖像矩陣分塊, 將原圖尺寸調(diào)整為200×320(見圖1)。由于進行NMF分解時需要初始化基矩陣W和系數(shù)矩陣H, 為減弱不同初始值對算法的影響, 每組實驗都重復(fù)進行5次。NMF算法和BNMF算法的迭代次數(shù)都設(shè)為100次。

具體實驗過程如下：

1) 原圖像轉(zhuǎn)化為HSI圖像, 將圖像中的I分量矩陣從第1行第1列開始, 按8×8依次分塊(I范圍轉(zhuǎn)換為0～255), 分塊結(jié)果作為測試樣本；

2) 抽取尺寸為8×8的陰影、 非陰影兩類訓(xùn)練樣本, 通過NMF或BNMF求取各個類別的基矩陣和系數(shù)矩陣(r=5)；

3) 以各類別的基矩陣為特征基, 求出特征基對應(yīng)的系數(shù)矩陣；

4) 設(shè)定閾值, 根據(jù)判別函數(shù)分類, 并標(biāo)記已分類別的部分, 不能確定類別的部分細分為4×4(r=3)或2×2(r=2)的矩陣塊繼續(xù)使用NMF或BNMF分類。

3.1 實驗1

a 第1次分類結(jié)果 b 最終分類結(jié)果

a 第1次分類結(jié)果 b 最終分類結(jié)果

3.2 實驗2

該實驗分別采用NMF算法和BNMF算法檢測陰影, 實驗時兩種算法選用的判別函數(shù)類型相同, 都是通過計算測試樣本與訓(xùn)練樣本系數(shù)矩陣間的歐氏距離判定陰影。實驗結(jié)果如圖4和圖2所示。

a 第1次分類結(jié)果 b 最終分類結(jié)果

比較圖4a和圖2a可看出, 在判別函數(shù)類型相同的情況下, NMF算法第1次分類陰影區(qū)誤差大于BNMF算法第1次分類結(jié)果。從圖4b和圖2b中陰影的形狀可看出, BNMF的檢測細節(jié)要好于NMF的最終結(jié)果。在進行實驗時, BNMF算法的復(fù)雜度比NMF算法小, 文獻[13]中通過對比NMF與BNMF復(fù)雜度也證實了此結(jié)論。此外, 分析式(7)可看出, 各類別系數(shù)矩陣形成的H矩陣, 其列向量相互正交, BNMF能消除不同類別間的相關(guān)性。因此, 與傳統(tǒng)的NMF相比, 在判別函數(shù)類型相同的情況下, BNMF的效果更佳。

圖5所示為4種方法的檢測結(jié)果[14], 通過在HSV空間利用陰影區(qū)域亮度和色調(diào)的特點, 可得到如圖5a所示結(jié)果。對比圖5中陰影形狀以及道路中白線的消除可得出以下結(jié)論：

1) BNMF算法雖然存在一些誤差, 但與前兩種方法相比, 檢測細節(jié)更清晰；

2) 改進判別函數(shù)后, NMF算法檢測結(jié)果與前兩個結(jié)果相比, 更加清晰, 效果較好；

3) 在判別函數(shù)類型相同的情況下, BNMF檢測結(jié)果好于NMF的結(jié)果。

a 文獻[14] b 奇異值分解 c NMF判別函數(shù)1

d NMF判別函數(shù)2 e BNMF

由此可見, 與其他矩陣分解方法相比, 非負矩陣分解由于其自身的特點, 更加貼近實際應(yīng)用。

4 結(jié) 語

筆者使用NMF算法實現(xiàn)了陰影檢測, 討論了不同判別函數(shù)對檢測結(jié)果的影響, 對比了NMF算法和BNMF算法的兩種陰影檢測效果。實驗結(jié)果表明, NMF算法和BNMF算法均能有效檢測陰影區(qū)域, 但BNMF算法較NMF算法步驟少, 細節(jié)更清晰。今后的研究工作將主要集中于判別函數(shù)的改進以及其他改進非負矩陣分解方法的應(yīng)用。

參考文獻：

[1]陳柏生, 陳鍛生. 基于歸一化RGB彩色模型的運動陰影檢測 [J]. 計算機應(yīng)用, 2006, 26(8): 1879-1881.

CHEN Bai-sheng, CHEN Duan-sheng. Normalized RGB Color Model Based Shadow Detection [J]. Computer Applications, 2006, 26(8): 1879-1881.

[2]郭建波, 周劍利, 韓鴻哲, 等. 背景差法中的陰影消除方法 [J]. 遼寧工程技術(shù)大學(xué)學(xué)報, 2005, 24(1): 104-106.

GUO Jian-bo, ZHOU Jian-li, HAN Hong-zhe, et al. Shadow Suppression Method for Background Subtraction [J]. Journal of Liaoning Technical University, 2005, 24(1): 104-106.

[3]王樹根, 王軍利, 郭麗艷. 基于K-L變換的彩色航空影像陰影檢測 [J]. 測繪信息與工程, 2004, 29(2): 21-22.

WANG Shu-gen, WANG Jun-li, GUO Li-yan. Shadow Detection of Color Aerial Images Based on K-L Transformation [J]. Journal of Geomatics, 2004, 29(2): 21-22.

[4]潘翔. 基于彩色信息和邊緣特征的運動陰影檢測 [J]. 浙江大學(xué)學(xué)報, 2004, 38(4): 389-391.

PAN Xiang. Moving Shadow Detection Based on Color Information and Edge Features [J]. Journal of Zhejiang University, 2004, 38(4): 389-391.

[5]喬振民, 邢立新, 李淼淼, 等. 遙感影像的云及其陰影覆蓋區(qū)光譜重構(gòu) [J]. 吉林大學(xué)學(xué)報: 信息科學(xué)版, 2012, 30(1): 35-39.

QIAO Zhen-min, XING Li-xin, LI Miao-miao, et al. Spectral Reconstruction of Remote Sensing Image’s Clouds and Its Shadow Coverage [J]. Journal of Jilin University: Information Science Edition, 2012, 30(1): 35-39.

[6]李子龍, 劉偉銘. 基于組合特征和HSI顏色空間的陰影檢測 [J]. 微電子學(xué)與計算機, 2011, 28(3): 66-69.

LI Zi-long, LIU Wei-ming. Shadow Detection Based on Mixed Feature and HSI Color Space [J]. Microelectronics & Computer, 2011, 28(3): 66-69.

[7]董蓉, 李勃, 陳啟美. 路況視頻中HSV彩色不變量陰影檢測法研究與改進 [J]. 中國圖像圖形學(xué)報, 2009, 14(12): 2483-2488.

DONG Rong, LI Bo, CHEN Qi-mei. Research and Improvement on Shadow Detectionin Expressway Videos Using HSV Color Model [J]. Journal of Image and Graphics, 2009, 14(12): 2483-2488.

[8]郭建虎. 非負矩陣分解方法及其在人臉識別中的應(yīng)用 [D]. 蘭州: 蘭州理工大學(xué)計算機與通信學(xué)院, 2010.

GUO Jian-hu. Non-Negative Matrix Factorization and Its Applications to Face Recognition [D]. Lanzhou: School of Computer and Communication, Lanzhou University of Technology, 2010.

[9]李勇智, 楊靜宇. 基于非負矩陣分解新的人臉識別方法 [J]. 系統(tǒng)仿真學(xué)報, 2008, 20(1): 111-116.

LI Yong-zhi, YANG Jing-yu. Novel Methods of Face Recognition Based on Non-Negative Matrix Factorization [J]. Journal of System Simulation, 2008, 20(1): 111-116.

[10]郝紅. 非負矩陣分解在遙感圖像識別中的應(yīng)用 [D]. 杭州: 浙江農(nóng)林大學(xué)環(huán)境與資源學(xué)院, 2011.

HAO Hong. Application of Non-Negative Matrix Factorization Method in Remote Sensing Image Recognition [D]. Hangzhou: School of Environmental and Resource Sciences, Zhejiang A & F University, 2011.

[11]LEE D D, SEUNG H S. Learning the Parts of Objects by Non-Negative Matrix Factorization [J]. Nature, 1999, 401(6755): 788-791.

[12]趙玲. 基于獨立分量分析和非負矩陣分解的人臉識別研究 [D]. 蘭州: 蘭州大學(xué)信息學(xué)院, 2006.

ZHAO Ling. Face Recognition Studying Based on ICA and NMF [D]. Lanzhou: School of Information Science & Engineering, Lanzhou University, 2006.

[13]潘杉杉, 陳文勝, 徐晨. 基于分塊非負矩陣分解人臉識別增量學(xué)習(xí) [J]. 計算機應(yīng)用研究, 2009, 26(1): 117-120.

PAN Shan-shan, CHEN Wen-sheng, XU Chen. Incremental Learning of Face Recognition Based on Block Non-Negative Matrix Factorization [J]. Application Research of Computer, 2009, 26(1): 117-120.

[14]陳柏生. HSV彩色空間的室內(nèi)外運動人檢測與陰影消除 [J]. 華僑大學(xué)學(xué)報, 2007, 28(1): 30-33.

CHEN Bai-sheng. Indoor and Outdoor People Detection and Shadow Elimination by Exploiting HSV Color Information [J]. Journal of Huaqiao University, 2007,28(1): 30-33.