基於異常檢測演算法的圖片異常檢測

背景介紹

隨著「安防技術」的不斷發展以及市場需求的不斷擴大，視頻監控系統已成為當代社會安全防範中不可獲取的一部分。目前我國各行業各種規模大小的視頻監控系統已經非常普遍，例如在銀行、社區、工廠、學校以及大型園區等場所均已安裝了視頻監控系統。在視頻監控系統中，攝像頭在外界環境以及人為惡意破壞等影響下，傳輸的畫面質量時常會出現問題，例如：視頻信號中斷，視頻畫面偏色或者亮度對比度異常等等。這些視頻質量問題嚴重影響了監控系統的效能，如果問題不能夠及發現和處理，很可能被有心之人或不法分子利用，造成進一步的經濟損失。

為了快速發現視頻質量異常的攝像頭，並進行處理，防止因攝像頭視頻異常產生的損失。本文通過對攝像頭拍攝的圖片進行異常圖像檢測來判斷攝像頭是否出現異常情況。

研究內容

對於異常圖像的檢測，我們之前已經提供過解決方案：「基於圖像塊HSV特徵的監控攝像頭異常檢測」和「基於PHA的異常攝像頭圖像識別」。這兩種方法的前提是正、異常圖片數量分佈相對比較均勻。然而在實際業務場景中我們發現，攝像頭絕大多數時間是在正常情況下工作的，也就是說異常圖片非常之少，故我們從另一個角度提出了新的方法 ：基於異常檢測演算法來檢測異常圖像。

何為異常圖片

下圖中第一行為攝像頭正常工作時拍攝的圖片，第二行為攝像頭轉動，單色等異常情況下拍攝到的圖片，即為異常圖像。

圖像特徵

無論是對圖像中物體的識別，還是圖像異常識別都需要用一些特徵對圖像進行描述，進而根據特徵之間的共性和差異來識別圖像。

這裡我們提取了圖像的顏色矩特徵。在提取特徵之前，我們先將圖像從RGB空間轉換到HSV空間。

圖像的顏色矩一共需要9個分量(3個顏色分量，每個分量上3個低階矩)

註：公式中，N 表示圖片中的總的像素數，p_ij 表示第 j 個像素在第 i 個顏色通道上的像素值，E_i 表示第 i 個顏色通道上所有像素的均值，σ_i 表示第 i 個顏色通道上所有像素的標準差，s_i 表示第 i 個顏色通道上所有像素的斜度(skewness)的3次方根。

從圖像中提取的特徵值如下，每行代表一張圖像。

[ 30.17 36.96 106.27 22.79 24.66 62.56 32.07 35.77 75.64][ 28.85 37.26 107.4 21.97 23.34 53.53 32.5 33.34 68.65][ 37.12 42.56 102.93 34.64 31.28 60.05 44.65 42.93 74.1 ][ 34.56 41.42 101.71 30.92 28.62 59.78 40.66 40.35 73.91][ 37.15 40.7 100.76 32.52 28.17 60.05 39.79 38.91 74.27][ 29.73 35.84 104.79 23.79 22.15 57.57 33.65 32.45 71.56][ 31.01 37.82 102.27 25.53 24.99 60.71 35.59 35.01 75.4 ][ 31.21 37.75 103.17 25.46 23.33 53.22 35.4 31.64 68.62][ 34.34 36.41 105.24 30.87 23.45 56.33 39.83 32.96 70.94][ 34.89 41.46 101.77 28.53 23.37 63.5 36.28 33.37 76.71]

由於無法顯示所有的維度，我們僅展示了圖像的一階矩特徵散點圖(分別為上述特徵的第一、第四、第七個分量)，如下圖所示。

異常數據的分佈特點

用視覺直觀的感受一下如下圖所示，對於 C1 集合的點，整體間距，密度，分散情況較為均勻一致，可以認為是同一簇；對於 C2 集合的點，同樣可認為是一簇。o1、o2點相對孤立，可以認為是異常點或離散點。

異常檢測演算法的應用場景

  • 數據預處理
  • 病毒木馬檢測
  • 工業製造產品檢測

在上述場景中，異常的數據量都是很少的一部分，像SVM、邏輯回歸等分類演算法都不適用，因為：

「監督學習演算法適用於有大量的正向樣本，也有大量的負向樣本，有足夠的樣本讓演算法去學習其特徵，且未來新出現的樣本與訓練樣本分佈一致。」

異常檢測演算法

基於統計與數據分佈

假設數據集應滿足正態分佈,即：

給定一個新的數據x，如果x的值大於4或者小於-4，都可以認為是異常值。

箱線圖分析

股票成交量的箱線圖如下圖所示。

大體可知，該股票在成交量小於20000，或者成交量大於80000時，就應該提高警惕了。

基於距離/密度

典型的演算法是：「局部異常因子演算法-Local Outlier Factor」，該演算法通過引入「k-distance，第k距離」、「k-distance neighborhood，第k距離鄰域」、「reach-distance，可達距離」、以及「local reachability density，局部可達密度 」和「local outlier factor，局部離羣因子」，來發現異常點。

基於劃分思想

典型的演算法是「孤立森林， Isolation Forest」，其思想是：

假設我們用一個隨機超平面來切割（split）數據空間（data space）, 切一次可以生成兩個子空間（想像拿刀切蛋糕一分為二）。之後我們再繼續用一個隨機超平面來切割每個子空間，循環下去，直到每子空間裡面只有一個數據點為止。直觀上來講，我們可以發現那些密度很高的簇是可以被切很多次才會停止切割，但是那些密度很低的點很容易很早的就停到一個子空間了。

本文所用演算法

本文分別使用了基於劃分的異常檢測演算法——孤立森林演算法和基於距離/密度的異常檢測演算法——LOF演算法來做異常圖像的檢測，並在最後對這兩種方法做個比較。

異常檢測演算法 — 孤立森林

孤立森林原理

與隨機森林由大量決策樹組成一樣，iForest森林也由大量的樹組成。iForest中的樹叫isolation tree，簡稱iTree。iTree樹和決策樹不太一樣，其構建過程也比決策樹簡單，因為其中就是一個完全隨機的過程。

假設數據集有N條數據，構建一顆iTree時，從N條數據中均勻抽樣(一般是無放回抽樣)出ψ個樣本出來，作為這顆樹的訓練樣本。

在樣本中，隨機選一個特徵，並在這個特徵的所有值範圍內(最小值與最大值之間)隨機選一個值，對樣本進行二叉劃分，將樣本中小於該值的劃分到節點的左邊，大於等於該值的劃分到節點的右邊。

這樣得到了一個分裂條件和左、右兩邊的數據集，然後分別在左右兩邊的數據集上重複上面的過程，直接達到終止條件。終止條件有兩個，一個是數據本身不可再分(只包括一個樣本，或者全部樣本相同)，另外一個是樹的高度達到log2(ψ)。不同於決策樹，iTree在演算法裡面已經限制了樹的高度。當然不限制也可以，只是演算法為了效率考慮，只需要達到log2(ψ)深度即可。

把所有的iTree樹構建好了，就可以對測數據進行預測了。預測的過程就是把測試數據在iTree樹上沿對應的條件分支往下走，直到達到葉子節點，並記錄這過程中經過的路徑長度h(x)，即從根節點，穿過中間的節點，最後到達葉子節點，所走過的邊的數量(path length)。

最後，將h(x)帶入，計算每條待測數據的異常分數(Anomaly Score)，其計算公式為：

其中

是二叉搜索樹的平均路徑長度，用來對結果進行歸一化處理, 其中的H(k)可以通過公式

來估計，ξ是歐拉常數，其值為0.5772156649

h(x) 為路徑長度，E(h(x)) 為森林中所有iTree樹的平均路徑長度。

使用異常分數，具有以下性質：

1、如果分數越接近1，其是異常點的可能性越高；

2、如果分數都比0.5要小，那麼基本可以確定為正常數據；3、如果所有分數都在0.5附近，那麼數據不包含明顯的異常樣本。

註：在python sklearn中對於異常分數計算跟上述有些不同

上述步驟可總結為兩步：

訓練：從訓練集中進行採樣，並構建iTree樹；

測試：對iForest森林中的每顆iTree樹進行測試，記錄path length，然後根據異常分數計算公式，計算每條測試數據的anomaly score。

孤立森林演算法流程如下：

孤立森林演算法驗證

根據上述孤立森林原理可知，孤立森林演算法通過計算每張圖片的異常分數來判斷該圖片是否為異常圖片。這裡，給定一個閾值t，若異常分數value>t，則我們認為該數據為異常數據。

為了找出最佳的t，我們將t取為-3.0~3.2,差值為 0.2的等差數列：

t = np.arange(-3.0, 3.2 0.2)

並且得到在不同異常值分割點：t 下的預測正確率，x軸為t，y軸為正確率.

在構建森林時，為了分析異常圖片所佔比例對預測結果的影響，我們分別構建了三種數據模型：1).數據模型100張圖片中，包含30張異常圖片；

2).數據模型100張圖片中，包含5張異常圖片；

3).數據模型100張圖片中，包含0張異常圖片。

並使用全部的圖片（100張正常圖片和56張異常圖片）來做預測，得到不同數據模型下的預測結果，如下圖所示。其中，正確率為演算法所有圖片的識別能力，召回率為演算法對正常圖片的識別能力，特效度為演算法對異常圖片的識別能力。

a、數據模型中有70張正常圖片和30張異常圖片。測試圖片中有100張正常圖片和56張異常圖片。

b、數據模型中有95張正常圖片和5張異常圖片。測試圖片中有100張正常圖片和56張異常圖片。

c、數據模型中有100張圖片且全部為正常圖片。測試圖片中有100張正常圖片和56張異常圖片。

由上述三幅曲線圖可知，模型中數據越純正（正常圖片比例越高），對預測的效果就越好。

異常檢測演算法 — LOF運算元

LOF演算法相關定義

1. d(p,o):兩點p和o之間的距離

2. k_distance：第K距離

對於點p的第k距離 d_k(p)=d(p,o),並且滿足：

a) 在集合中至少有不包括p在內的k個點o∈C{x≠p},滿足 d(p,o) <= d(p,o); b) 在集合中最多有不包括p在內的k-1個點o j∈C{x≠p},滿足 d(p,o) < d(p,o); p的第k距離，也就是距離p第k遠的點的距離，不包括p。 如下圖。

3. k_distance neighbourhood of p:第k距離鄰域

點p的第k距離鄰域 N_k(p) ，就是p的第k距離及以內的所有點，包括第k距離。因此p的第k鄰域點的個數 |N_K(p)| >= k (可以有多個第k距離遠的點).

4.reach_distance:可達距離

點o到點p的第k可達距離定義為：

也就是，點o到點p的第k可達距離，至少是o的第k距離，或者為o、p的真實距離。這也意味著，距離o最近的k個點，o到它們的可達距離被認為相等，且都等於 d_k(o)。如下圖，o1到p的第5可達距離為 d(p,o1), o2 到 p 的第5可達距離為 d_5(o2)。

5.local reachability density:局部可達密度：

點p的局部可達密度表示為：

表示點p的第k鄰域內點到p的平均可達距離的倒數。 注意，是p的鄰域點 N_k(p) 到p的可達距離，不是p到 N_k(p) 的可達距離，一定要弄清楚關係。並且，如果有重複點，那麼分母的可達距離之和可能為0，則會導致 lrd 變為無限大，下面還會繼續提到這一點。

這個值的含義可以這樣理解，首先這代表一個密度，密度越高，我們認為越可能屬於同一簇；密度越低，越可能是離羣點。如果p和周圍領域點是同一簇，那麼可達距離越可能為較小的 d_k(o)，導致可達距離之和較小，密度值較高；如果p和周圍鄰居點較遠，那麼可達距離可能都會取較大值 d(p,o)，導緻密度較小，越可能是離羣點。

6.local outlier factor:局部離羣因子

點p的局部離羣因子表示為：

表示點p的鄰域點 N_k(p) 的局部可達密度與點p的局部可達密度之比的平均數。

如果這個比值越接近1，說明p的其鄰域點密度差不多，p可能和鄰域同屬一簇；如果這個比值越小於1，說明p的密度高於其鄰域點密度，p為密集點；如果這個比值越大於1，說明p的密度小於其鄰域點密度，p越可能是異常點。

LOF演算法驗證

這裡，我們將t作為一個閾值，若value>t，則我們認為該數據為異常數據。

為了找出最佳的t，我們將t取為1.0~5.2,差值為 0.2的等差數列：

t = np.arange(1.0, 5.2 0.2)

這裡我們取k=5，並且得到在不同異常值分割點：t 下的預測正確率，x軸為t，y軸為正確率：

為了分析異常圖片所佔比例對預測結果的影響，我們分別構建了三種數據模型：

1).數據模型100張圖片中，包含30張異常圖片；

2).數據模型100張圖片中，包含5張異常圖片；

3).數據模型100張圖片中，包含0張異常圖片。

並使用全部的圖片（100張正常圖片和56張異常圖片）來做預測，得到不同數據模型下的預測結果，如下圖所示。其中，正確率為演算法所有圖片的識別能力，召回率為演算法對正常圖片的識別能力，特效度為演算法對異常圖片的識別能力。

a、數據模型中有70張正常圖片和30張異常圖片。測試圖片中有100張正常圖片和56張異常圖片。

b、數據模型中有95張正常圖片和5張異常圖片。測試圖片中有100張正常圖片和56張異常圖片。

c、數據模型中有100張圖片且全部為正常圖片。測試圖片中有100張正常圖片和56張異常圖片。

由上述三幅曲線圖可知，模型中數據越純正（正常圖片比例越高），對預測的效果就越好。

孤立森林與LOF比較

通過上述實驗我們得知，隨著正常圖片在訓練數據集所佔比例升高，這兩種演算法表現越來越好，可以看出它們非常適合異常樣本很少或者沒有的場景。 我們在這兩種演算法最好的表現的情況下，從正確率，召回率，特效度以及所需時間來對其進行比較。

可以發現LOF演算法在正確率、召回率和特效度上都比IF演算法（隨機森林）表現的稍好，但是IF要比LOF快得多，可以達到實時要求。

參考文獻：

異常檢測概覽——孤立森林 效果是最好的 (cnblogs.com/bonelee/p/7)

iForest （Isolation Forest）孤立森林 異常檢測 入門篇 (jianshu.com/p/5af3c66e0)


推薦閱讀：
相關文章