針對近重復視頻的FD-means聚類清洗算法

付 燕，韓 澤，葉 鷗

西安科技大學計算機科學與技術學院，西安 710054

在我國煤礦行業內，主要通過人工與智能視頻監控技術相結合的方式監控災情隱患。對比單一的人工監控方式，智能視頻監控技術可持續、實時、全面的監控煤炭生產過程中各個環節，減少因煤礦開采造成的人員傷亡和經濟損失。隨著智能視頻監控技術[1]的廣泛應用，井下視頻數據規模不斷增大，近重復視頻數據不斷涌現，視頻數據質量問題越來越突出，視頻數據的維護和管理工作也越來越具有挑戰性，不利于提早發現安全隱患問題以及災后的事故調查。因此，針對視頻數據質量問題研究對保障煤礦安全生產具有重要意義。視頻質量[2]主要關注視頻數據的清晰程度，而視頻數據質量則主要關注視頻數據集的整體質量，強調數據一致性、正確性、完整性和最小性在信息系統中得到滿足的程度，屬于數據質量[3]的概念范疇。近重復視頻的產生不但會影響視頻的數據質量，也會涉及版權保護和視頻檢索等領域正常視頻的應用。因此，如何檢測并自動清洗近重復視頻數據，已成為日益關注的熱點研究問題之一。

近重復視頻檢測技術是發現近重復視頻數據的一種重要技術，也是發現視頻數據質量問題的有效方法。目前近重復視頻檢測的研究主要在特征提取，簽名生成兩個方面。特征提取包括低層特征（如LBP[4]、局部特征[4-5]、顏色直方圖[6]等）以及近年較熱的深度特征[7-9]。簽名生成分為幀級簽名生成方法（如幀間匹配[6]、可視化詞袋[10]）和視頻級簽名生成方法（如聚合特征向量[6]和哈希碼[11]）。盡管目前針對視頻檢測問題的理論成果可以用于發現煤礦井下近重復視頻數據，并反映出視頻數據質量問題，但該類方法較難自動清理隱藏在視頻數據集中的近重復視頻數據。

數據清洗是指檢測數據集合中存在的不符合規范的數據，并進行數據修復，以提高數據質量的過程[12]。數據清洗研究主要包括結構化數據清洗，多媒體數據清洗以及大數據清洗。近重復視頻數據清洗是保證視頻數據質量的有效手段，但目前存在的近重復視頻清洗方法結果易受到滑動窗口尺寸和Hash沖突的影響。為解決上述問題，本文提出了一種融合VGG-16深度網絡與feature distance-means（FD-means）聚類的近重復視頻清洗方法。該方法首先借助MOG2 模型[13]和中值濾波算法對視頻進行背景分割和前景降噪；其次使用預訓練的VGG-16 提取視頻背景與前景的特征；最后提出一種FD-means聚類算法，通過迭代產生的近重復視頻簇，利用優化函數，更新簇類中心點，并最終刪除簇中中心點之外的近重復視頻數據。本文的創新點在于提出利用無監督聚類清洗的思想，融合深度神經網絡和聚類算法，解決近重復視頻的清洗問題。

1 相關理論

近重復視頻指在相同場景下視頻語義相同或者相似的視頻數據[6]。監控視頻數據中的近重復視頻數據，在數據采集、整合和處理過程中都可能會產生不同形式的近重復視頻數據。例如，在數據采集階段，視覺角度的變化、光線的影響、設備自身的因素等情況會產生近重復視頻數據。在視頻數據整合階段，由于數據來源不同，可能存在不同格式、長度的重復視頻數據。在視頻處理階段，人工拷貝、編輯視頻數據等操作可能造成重復或異常臟視頻數據的產生。如圖1 展示了監控視頻中的近重復視頻樣例。

圖1 近重復監控視頻Fig.1 Near-duplicate surveillance video

現有的近重復視頻檢測根據視頻特征方法可以劃分如下兩類：（1）基于低層特征的近重復視頻檢測方法，包括方向梯度類特征（LBP[4]、SCSIFT[5]、SIFT[6]），顏色特征（HSV[6-7]、RGB[7]）等。Wu等人[6]先使用視頻的顏色直方圖過濾掉內容差異較大的視頻，再使用SIFT 局部特征通過幀間匹配的方法計算視頻相似度，該方法極大地降低了冗余視頻，但是幀的成對匹配異常耗時。（2）基于深度特征的近重復視頻檢測方法，包括卷積神經網絡[8-9]、循環神經網絡[9]、兩層3D 卷積網絡[10]等。文獻[8]通過融合卷積神經網絡中間層特征，擬合視頻特征映射到歐氏空間的映射函數，使得近重復視頻之間的距離要小于非相似視頻之間的距離，該方法具有出色的性能。

然而，上述近重復視頻檢索方法盡管可以識別出視頻數據集中的近重復視頻，但是較難直接自動清洗近重復視頻數據，改善視頻數據質量。數據清洗技術是改善數據質量的一種重要技術途徑，主要包括結構化數據清洗[14-15]、大數據清洗[16-17]以及多媒體數據清洗[18]。

其中，在結構化數據清洗研究方面，郝爽等人[14]針對數據缺失、數據冗余、數據沖突和數據錯誤四種類型的臟數據介紹了不同的檢測技術，從數據清洗方式上把數據清洗算法分為基于完整性約束的清洗算法、基于規則的清洗算法、基于統計的清洗算法和人機結合的清洗算法，并分析了優點和缺點。文獻[15]基于快速移動窗口和小波分析方法對Urban 行駛數據中的異常及離群數據進行識別清洗，首次將數據清洗用在了自動車牌識別中，并提高交通網絡監控和管理的數據質量。在大數據的廣泛應用中也會產生各種臟數據，文獻[16]介紹了Clean Cloud 大數據清理系統，在每個從服務器上運行補差、實體解析、真相發現以及基于規則修復四個算子，這些算子基于Map-Reduce 實現，對大數據具有良好的適用性。文獻[17]針對冗余計算和同一輸入文件的簡單計算進行合并，減少Map Reduce的輪數，從而減少系統運行的時間。目前，多媒體視頻清洗的研究較少，文獻[18]采用鄰近排序方法（sorted neigh borhood method，SNM）對近重復視頻進行清洗，該方法采用局部敏感哈希（locality sensitive hashing，LSH）方法對特征構建視頻簽名，對視頻簽名進行排序后使用SNM 掃描排序后的特征列表，并剔除其中的近重復視頻。該方法在一定程度上可以有效解決近重復視頻的清洗問題，但是該方法對特征向量的Hash映射，造成部分特征信息的丟失，并且SNM方法過度依賴窗口尺寸。

總的來說，目前視頻數據清洗的研究成果較少，存在算法結果易受到滑動窗口尺寸和Hash 沖突的影響。為解決上述問題，本文融合VGG-16 深度神經網絡和FD-means 聚類算法，以避免特征向量的Hash 映射和固定滑動窗口對近重復視頻清洗的影響，改善近重復視頻清洗的效果。

2 融合VGG-16 深度網絡與FD-means 聚類的近重復視頻清洗方法

由于實際生活中，較難直接獲取到具有代表性的近重復視頻作為先驗知識，為滿足視頻數據集的最小完整性原則，需要通過無監督學習的聚類思想識別具有代表性的近重復視頻數據，以此為基準，刪除視頻數據集中冗余的其他近重復視頻數據。為此，本文提出融合VGG-16 深度網絡與FD-means 聚類的近重復視頻清洗方法，該方法總體思路如圖2所示。

圖2 融合VGG與FD-means的視頻清洗流程框架Fig.2 Framework of video cleaning process combining VGG and FD-means

首先對輸入視頻使用MOG2 模型和中值濾波算法進行背景分割和去噪。在此基礎上，利用VGG-16網絡模型提取視頻的前景及背景特征。通過構建新的FDmeans 算法迭代產生的近重復視頻簇，更新簇類中心點，刪除簇中中心點之外的近重復視頻數據，實現近重復視頻的無監督聚類清洗。

2.1 VGG-16特征提取

VGGNet網絡模型[19]在解決圖像定位與分類問題中表現出優異的性能。該網絡的特點是使用3×3 的卷積核替換較大尺寸的卷積核，這種方式在不影響卷積層感受野的條件下增加決策函數的非線性，并減少了參數數量。此外，深層特征可以更加有效表達原圖所包含的信息。因此，本文利用VGG-16深度網絡模型提取視頻的深度外觀特征，其具體網絡結構如圖3 所示，包含13 個卷積層、5個池化層和3個全連接層。VGG-16中的最后一個全連接層用于分類任務，本文只需要提取特征不用分類，因此本文只保留前兩層全連接層。

圖3 VGG-16網絡結構Fig.3 VGG-16 network structure

在圖3中，Conv3-64、Conv3-128、Conv3-256、Conv3-512 分別表示使用64、128、256、512 個尺寸為3×3 的卷積核進行卷積操作，卷積步長為1；MaxPool表示對上層輸出進行最大池化操作，池化步長為2；FC-4096、FC-1 000 分別表示1×4 096 和1×1 000 的全連接層。此外，本文使用ReLU 函數作為激活函數以增強網絡模型的擬合能力，并對網絡輸出的特征向量進一步進行歸一化處理，加快視頻的聚類清洗速度。

2.2 FD-means聚類算法

傳統的SNM方法容易造成漏刪或者誤刪近重復視頻的問題，并在數據降維過程中損失特征的有效信息。為此，本文借鑒K-means聚類算法提出了一種新的FD-means 聚類算法。盡管K-means 模型由于其本身的聚類效果好、聚類速度快的優點[20]，但該算法需要預先確定參數K值。但在實際應用中，監控系統應用場景數量不一定是固定的，近重復視頻的產生來源多樣，因此K-means 算法模型較難完全適用于近重復視頻清洗的任務。筆者認為，視頻特征能夠描述視頻的內容信息，通過樣本特征間的距離可以反應視頻內容的差異，距離越近差異越小，距離越遠差異越大。為此，本文構建了一個新的FD-means聚類算法模型對視頻進行聚類清洗。該算法根據特征之間的距離進行聚類清洗。如果距離過遠，即構造新的簇；若距離較近，則劃分到本簇。通過該算法，可以對不同類別的視頻特征進行無監督分類，并實現近重復視頻的自動清洗。

其中||?||2表示對象之間的歐氏距離，m、n分別表示V、W中對象的個數，V、W表示由聚類對象組成的向量。

FD-means 的聚類過程，該算法主要由三個部分構成，更新聚類中心，更新簇以及融合簇，當聚類中心不發生改變時聚類結束，輸出聚類結果。以下給出FDmeans聚類部分偽代碼。

算法1 FD-means

FD-means 更新聚類中心過程，首先計算各元素與簇內其他元素距離之和，通過迭代選擇距離之和最小的對象作為該聚類簇的中心，如式（2）：

其中d表示聚類的某個簇，d-xi為差集運算，c表示該簇的中心元素。

在更新簇時，首先計算非聚類中心對象與所有聚類中心之間的歐式距離。在K-means中，所有非中心對象根據最近鄰原則，將對象劃分至最近的聚類中心簇中。與K-means 不同的是，FD-means 將非中心對象與所有聚類中心的距離與特征距離閾值進行比較，如果最小距離不小于距離閾值，則將該對象作為一個新的簇如式（3）；否則，根據最近鄰原則，將對象劃分至最近的聚類中心簇中如式（4），從而實現了自動聚類。

其中ci表示簇di的聚類中心，ci為距離x最近且小于距離閾值Th的聚類中心。

為了消除距離過近的簇，需要對簇進行融合，計算各個聚類中心之間的距離，通過迭代更新優化函數，將距離小于特征距離閾值的簇合并到一個簇，如式（5）所示：

其中ci表示簇di的聚類中心，cj為距離ci最近且小于距離閾值Th的聚類中心，D-dj為差集運算。

在針對近重復視頻進行自動清洗時，為了保證視頻數據集的最小完整性、正確性、唯一性和有效性，不能把聚類得到的近重復視頻全部剔除。為此，需要從近重復視頻中保留一個具有代表性的視頻，并自動刪除其他近似重復視頻數據，以提高視頻數據質量，達到近重復視頻清洗的目的。傳統的圖像去重或者數據清洗中，偏向于保留首次檢測到的數據，去除后面相似的數據，這種保留方式不完全具有代表性。通過FD-means算法將近重復視頻聚類，同一個類內視頻都是近重復的，在該前提下進行視頻清洗，樣本特征間的距離可以反應視頻內容的差異。因此，聚類中心能夠代表聚類簇中的近重復視頻數據，通過保留聚類中心的視頻，刪除聚類中心點之外的視頻，達到近重復視頻清洗的效果，如式（6）所示。

其中，“-”為差集運算。雖然刪除非聚類中心視頻會損失這些視頻的細節信息，但近重復視頻在整體上是相同或者近似的，刪除非中心視頻不會損失這些近重復視頻的主要信息，并且保證了數據集的最小性、一致性、完整性和數據的正確性。

3 實驗結果與分析

3.1 實驗環境與數據集

本文，采用Python 3.6.5版本編程語言，Windows10操作系統，Intel Core?i5-4200H@2.80 GHz×4 處理器和8.0 GB 內存空間的環境實現所提方法。本文分別在煤礦井下監控視頻數據集和CC_WEB_VIDEO 數據集上[6]進行算法對比分析。其中，CC_WEB_VIDEO數據集包含24個場景總共13 129個多媒體視頻。本文隨機選取其中5 個場景（“The Lion Sleeps Tonight”“Evolution of dance”“Folding Shirt”“Cat Massage”“ok go-here it goes again”）共63個視頻來驗證算法有效性。為了進一步驗證本文方法的有效性，使用復雜背景下的煤礦井下監控視頻數據集驗證本文方法。煤礦井下監控視頻數據集包含10個場景共86個視頻，總時長9 678.36 s。

3.2 參數設置與實驗方案

在使用MOG2 模型對測試樣本的視頻數據進行背景分割和中值濾波去噪時，涉及的參數有高斯分量數量NMixtures，背景比率BackgroundRatio 和濾波器尺寸ksize。參數設置如表1所示。

表1 參數設置Table 1 Parameters setting

假設視頻集V={V1,V2,…,Vn} ，FD-means 聚類中心對應的視頻S={S1,S2,…,Sk} ，需要保留的視頻T={T1,T2,…,Tj} 。在近重復視頻的數據清洗過程中，一方面要保證視頻數據集的完整性，另一方面要盡可能的清除近重復視頻數據。為此，本文參考文獻[22]采用準確度Acc、召回率Rec以及F1-score 作為實驗評價指標。

為了驗證本文所提方法的有效性及其性能，本文針對CC_WEB_VIDEO和煤礦井下監控視頻數據集，通過對比VGG-16+FD-means方法、LSH+SNM[12]、背景分割+SNM（BS_SNM）和本文所提方法背景分割+VGG16+FD-means（BS+VGG16+FD-means），進行實驗對比與分析。

3.3 實驗結果及分析

為了分析FD-means算法對近重復視頻清洗結果的影響，首先對K-means與FD-means算法做了對比實驗，如圖4 所示。在給出近重復視頻種類數及最優距離閾值時，在兩個數據集上分別進行5 次實驗，在煤礦井下監控視頻集中FD-means的F1-score在0.71～0.74范圍波動，K-means 的F1-score 在0.58～0.67 范圍波動，在CC_Web數據集上，FD-means的F1-score在0.70～0.76范圍波動，K-means 算法的F1-score 在0.57～0.64 范圍波動。總的來看，FD-means 和K-means 算法均存在初始值敏感問題，但是FD-means 算法波動下限依舊高于K-means算法的波動上限。本文認為這是因為K-means在聚類過程中由于固定的聚類數，將一些差異性較大的數據強行劃分到同一個類別中，從而造成了數據誤刪的情況，這種誤刪容易破壞視頻數據集的完整性，而FD-means 算法在更新聚類簇時，如公式（3）和（4）通過距離閾值盡量避免了強行劃分的問題，從而改善聚類結果。

圖4 隨機初始值對最終聚類算法結果的影響Fig.4 Effect of random initial value on final clustering algorithm result

為了說明特征距離閾值對視頻清洗結果的影響，圖5顯示了F1-score隨特征距離閾值Th的變化曲線，可以看出當距離閾值在8～9 之間時結果最佳。本文方法的曲線先增再降，這是由于一開始Th較小，大多數視頻被認為不是近重復，此時召回率高，準確度低。隨著Th的增加，FD-means能夠準確檢測到近重復視頻，從而提高了準確度。當Th持續增大時，不相似視頻被認作近重復視頻造成誤刪，導致算法召回率下降。對比圖中曲線，本文算法明顯優于傳統的LSH+SNM算法。

圖5 各方法的F1-score隨距離閾值的變化曲線Fig.5 Change curve of F1-score with distance threshold for each method

表2 是各方案分別與CC_WEB_VIDEO 數據集在煤礦井下監控視頻下的近重復視頻清洗方法對比的結果。由表2可見，與使用全局特征的VGG-16+FD-means方法相比，本文提出的方案清洗結果更好，這說明使用煤礦井下監控視頻的背景和前景特征能更好的描述視頻特征。

表2 視頻清洗結果對比Table 2 Comparison of video cleaning results

本文方案與BFFS方法相比，采用FD-means方法的視頻清洗結果優于采用SNM 算法的BFFS 方案。本文提出的方法與現有的LSH+SNM方法相比，具有更好的性能。相對于煤礦井下監控視頻的清洗結果，在CC_WEB_VIDEO數據下本文提出的方法清洗結果與LSH+SNM相比F1-score更高。其原因在于CC_WEB_VIDEO中的視頻為多媒體視頻，背景變化復雜多樣，在使用視頻背景檢測近似背景視頻時，出現錯誤結果，從而降低了實驗的準確度和F1-score。

此外，如圖6 所示，分別在煤礦井下監控視頻數據集和CC_WEB_VIDEO數據集上進行視頻清洗，可以減少視頻占用磁盤大小，降低存儲成本。對比圖6，在F1-score 最優時，降低了70%的視頻所需磁盤大小。視頻存儲節約的具體情況依賴于近重復視頻的密度，同一個類內近重復視頻越多，通過視頻清洗節約的存儲越多。在視頻清洗過程中，只保留近重復視頻中的中心視頻，極大降低視頻存儲空間。在兩個不同數據集上進行實驗驗證，使用視頻背景及前景特征進行FD-means 視頻聚類能夠準確檢測到近重復視頻，該方法能夠自動清洗視頻，且清洗結果也優于其他方法，并且能夠有效降低存儲。

圖6 本文方法清洗后結果占用磁盤大小隨距離閾值的變化曲線Fig.6 Change curve of occupies disk size with threshold distance of proposed method cleaning results

4 結束語

本文提出了一種融合VGG-16 深度網絡與FDmeans 聚類的近重復視頻清洗方法，首先，使用MOG2算法對視頻背景建模提取前景目標，其次使用VGG-16網絡模型提取視頻深度特征，最后，提出一種新的FD-means 聚類算法用于進重復視頻檢測及清洗。本文分別在煤礦井下監控視頻集和CC_WEB_VIDEO公共數據集進行實驗，結果表明：使用背景和前景特征描述視頻比全局特征更好；相比于SNM，使用FD-means 進行視頻清洗具有較高的準確率。本文方法在保證視頻集完整性的基礎上，能夠對近重復視頻實現自動清洗。將在后期的工作中對本文的方法加以改進，一方面結合數據密度的度量方法降低FD-means算法對初始值的敏感性，另一方面通過結合視頻的時空特征或結合視頻的其他特征，使其能夠提高視頻清洗的準確度。