基于AFSA－LSSVM的視頻字幕定位模型

陳燕升，任江濤，黃達峰

(1.廣東輕工職業技術學院 a.環境工程系;b.計算機工程系，廣東廣州510300;2.中山大學軟件學院，廣東廣州510275)

隨著網絡技術發展，視頻流劇增，不良的網絡視頻圖像對社會的穩定和人們的身心健康產生不利影響，通過對視頻信息的字幕進行定位，有利于對后續視頻內容進行安全分析和檢測，因此建立精確、高效的視頻字幕定位模型成為了當前研究的熱點［1］。

視頻字幕定位實質上是模式識別中的二分類問題，即指將字幕塊定義為“+l”，非字幕塊定義為“－l”，對于每一個輸入，如果其輸出為正，則表示為字幕塊;若為負，則為非字幕塊。視頻字幕定位主要包括視頻字幕特征自動提取和選擇、視頻字幕分類器設計等步驟［2］。特征選擇是視頻字幕定位的基礎，原始視頻字幕特征包含大量冗余信息和對定位結果起“反作用”的噪聲特征，若對視頻字幕特征不加選擇直接使用，不僅大大削弱了視頻字幕分類器的分類性能，而且增加“維數災難”出現概率，對視頻字幕定位結果產生不利影響［4］。當前視頻字幕特征選擇算法主要有:主成分分析、窮舉算法、遺傳算法、粒子群優化算法、免疫算法以及相關的改進算法［5］。窮舉算法計算量大、搜索效率低，不能滿足視頻字幕定位的實時性;主成分分析可以進行視頻字幕特征降維，但是可解釋性差;遺傳算法、粒子群優化算法、免疫算法等均存在收斂速度慢、極易陷入局部極值等缺陷，難以找到全局最優的視頻字幕特征［6］。人工魚群算法(Artificial Fish Swarm Algorithm，AFSA)是一種模擬魚群覓食行為的群智能算法，具有魯棒性強、簡單、易實現等優點，在組合優化領域取得了不錯的應用效果［7］。視頻字幕特征選擇是一個大規模空間搜索的組合優化問題，因此可借助于AFSA進行求解。當前視頻字幕分類器主要基于機器學習算法進行設計，主要有神經網絡、支持向量機等［8］。神經網絡基于經驗風險最小化原則和“大樣本”理論，當不能滿足“大樣本”要求時，易出現過擬合、分類能力差等缺陷。最小二乘支持向量機(Least Square Support Vector Machine，LSSVM)是一種解決高維、非線性分類問題的機器學習，較好地克服了神經網絡泛化推廣能力差、支持向量機訓練時間長等缺陷，泛化能力優異［9］。因此本研究選擇LSSVM建立視頻字幕定位的分類器。

為了提高視頻字幕定位精度，針對視頻字幕定位特征選擇問題，提出一種AFSA和LSSVM相融合的視頻字幕定位型(AFSA－LSSVM)。首先用近鄰傳播聚類算法對視頻幀進行分解，并用圖像投影方法進行定位得到一個備選字幕區域集，然后提取備選字幕區域的特征參數，并采用AFSA選擇最優的特征子集，最后將最優特征子集輸入到LSSVM進行學習和分類，得到視頻字幕定位的結果。仿真結果表明，AFSA－LSSVM提高了視頻字幕定位精度和效率。

1 視頻字幕定位模型

1.1 獲取備選字幕區域

采用近鄰傳播聚類算法把視頻圖像幀中的邊緣分解到若干個子圖當中，將具有不同顏色的字幕邊緣和背景邊緣分開。通常情況下，字幕區域的邊緣信息比較密集，同時也含有豐富的筆劃信息，可以通過文獻［10］的方法對邊緣子圖進行水平和垂直投影來尋找包含字幕的備選字幕區域，然而這樣檢測到的字幕區域中還包含了一些錯誤的字幕區域，所以需要后續步驟對字幕區域作進一步的識別。視頻幀的分解結果如圖1所示。

圖1 視頻幀的分解結果

1.2 提取備選字幕區域的特征

1)對備選字幕區域進行邊緣檢測，得到 0°，30°，60°，90°，120°以及 150°方向的邊緣圖，共得到 6 個方向的邊緣圖。

2)分別計算6個邊緣圖的均值、方差、能量、熵、慣性矩以及非相似性這6個統計特征，共得到36個特征參數。

設邊緣圖的灰度圖像的大小是M×N，點(i，j)的灰度值為f(i，j)，則字幕區域均值ξ和方差δ2為

采用灰度共生矩陣可以描述在角度θ方向上，相距為s、灰度分別為i和j的兩個像素，它們的頻率相關矩陣pij(s，θ)的 θ選擇為 6 個離散的方向 0°，30°，60°，90°，120°，150°，而s可以取從 1 到圖像大小的值N。能量(E)、熵(I)、慣性矩(J)、非相似性(D)定義為

1.3 AFSA選擇最優字幕特征

按照上文所述提取了36個字幕特征，這些特征可能包含大量冗余信息和對定位結果起“反作用”的噪聲特征，若對這些視頻字幕特征不加選擇直接作為分類器的輸入，不僅大大削弱了視頻字幕分類器的分類性能，而且增加“維數災難”出現概率，對視頻字幕定位精度和效率產生不利影響，因此本文采用AFSA進行視頻字幕特征選擇。

1.3.1 人工魚群算法

人工魚群算法(AFSA)模仿魚群的覓食和追尾行為，搜索能力強，且搜索速度快，幾種典型行為如下:

1)覓食行為的數學表達式為

式中:X i為人工魚當前狀態;Yi為食物密度;Rand()為(0，1)范圍內的隨機數;Step為移動步長。

2)聚群行為的數學表達式為

式中:δ為擁擠度因子;nf為伙伴數目;X c為中心位置。

3)追尾行為的數學表達式為

式中，Xmax表示食物濃度最高Yj的人工魚位置。

4)公告板。公告牌是用于記錄最優人工魚的狀態。

1)收集視頻字幕數據，采用近鄰傳播聚類算法對視頻幀進行分解，并用圖像投影方法進行定位得到一個備選字幕區域集。

2)提取備選字幕區域的36個特征參數，并對特征進行歸一化處理

式中，xi和分別為原始特征值和歸一化后的特征值。

3)初始化人工魚參數，主要有位置、移動步長Step、種群規模n、擁擠度因子 δ、最大迭代次數max_iterate等。

4)在可行域范圍內隨機生成n條人工魚，并設置初始迭代次數max_iterate=0。

5)對初始魚群的個體當前位置食物濃度值(FC)進行計算，然后對它們進行排序，選擇FC值最大的人工魚個體進入公告板。

由此看來，在分析新聞語篇時，光注重語篇內部銜接是遠遠不夠的，應把語篇置于社會語境中加以人際意義的分析注解，這樣才能完全吃透文本。

6)評價某條人工魚的覓食、追尾和聚群行為所得的結果，若執行某個行為后，人工魚的狀態優于當前狀態，則該人工魚向此方向前進一步，接著轉到步驟8)執行。

7)產生一個隨機數r，若r＜Pfb，則人工魚執行隨機行為，否則執行反饋行為，向公告牌中最優方向移動一步，并得到當前解域范圍內的最好的人工魚狀態。

8)更新公告牌，將步驟7)中得到的最好人工魚狀態記入公告牌。

9)判斷算法結束條件，如果達到最大迭代次數，則結束算法，并輸出公告牌中的人工魚狀態，即為最優視頻字幕特征子集，否則passed_iterate=passed_iterate+1，轉向步驟6)執行。

10)根據最優視頻字幕特征子集對最優視頻字幕訓練集和測試集進行特征約簡，得到約簡后的訓練集和測試集。

11)將特征約簡后的最優視頻字幕訓練集送到LSSVM進行訓練，建立最優視頻字幕定位模型。

12)將約簡后的測試集輸入到已建立的最優視頻字幕定位模型進行測試，以驗證模型的性能。

1.4 視頻字幕的定位流程

基于AFSA－LSSVM的視頻字幕定位流程為:首先對視頻字幕定位訓練集數據進行預處理并提取原始特征，利用LSSVM建立視頻字幕定位分類器對原始特征子集進行評估，然后通過魚群的覓食、聚群及追尾行為，快速找到最優特征子集，并根據選擇的最優特征子集對訓練集和測試集進行特征約簡，最后將特征約簡后的訓練集送到LSSVM進行訓練，建立視頻字幕定位模型，并對特征約簡后的視頻字幕進行定位檢測。AFSA－LSSVM的視頻字幕定位框架如圖2所示。

圖2 AFSA－LSSVM的視頻字幕定位框架

2 仿真實驗

2.1 數據來源

從中央電視臺選取了1 000幀不同的視頻節目圖像，包括主持人畫面、體育新聞、廣告和比賽畫面，選取800幀組成訓練集，用于建立視頻字幕定位模型，其余200幀作為測試集，用于測試視頻字幕定位模型的有效性。在PIV雙核 CPU 3.0 GHz、2 Gbyte RAM，操作系統為 Windows XP，MATLAB 2012平臺下進行仿真測試。

2.2 對比模型及評價標準

為了讓AFSA－LSSVM模型的定位結果具有可比性，選擇表1中的幾種模型進行對比實驗。模型性能評價標準為:視頻字幕定位的正確率、誤判率和定位時間。

表1 對比模型及說明

2.3 實驗結果分析

2.3.1 各模型選擇的特征子集

采用 LSSVM，GA－LSSVM，PSO－LSSVM，AFSA－LSSVM進行特征子集選擇，得到最優特征子集見表2。從表2可知，采用特征選擇方法，有效消除了冗余或無用特征，可以降低特征維數，大大地壓縮了特征空間，因此在訓練集和測試集輸入到分類器進行學習之前，對特征進行選擇是必須的。

表2 各模型對不同類型視頻字幕選擇的特征數

2.3.2 視頻字幕的定位性能對比

根據選擇最優視頻字幕特征子集分別對訓練集和測試集進行視頻字幕特征約簡處理，然后將訓練集輸入到LSSVM進行學習和建模，最后采用建立的視頻字幕定位模型對測試集進行測試，定位結果的正確率和誤判率如圖3和圖4所示。

圖3 各模型的定位正確率對比

圖4 各模型的誤判率對比

從圖3和圖4可知，相對于沒有進行特征選擇的視頻字幕定位模型(LSSVM)，GA－LSSVM、PSO－LSSVM、AFSA－LSSVM均不同程度地提高了視頻字幕定位的正確率，同時降低了誤判率，主要是因為特征選擇可以剔除冗余和不重要的視頻字幕特征，獲得有利于提高視頻字幕定位結果的視頻字幕特征。

同時從圖3和4可以看出，相對于GA－LSSVM和POS－LSSVM模型，AFSA－LSSVM的視頻字幕定位正確率更高，誤判率進一步降低，這有效地表明了AFSA獲得的特征子集可以更加準確地描述視頻字幕區域，AFSA－LSSVM可以獲得更優的視頻字幕定位結果。

2.3.3 訓練和測試時間比較

對于大規模的視頻字幕定位問題，定位速度至關重要，采用tic和toc命令記錄每一個模型的平均訓練時間和平均測試時間，結果見表3。從表3可知，在所有模型中，AFSA－LSSVM的訓練時間和測試時間最短，定位速度最快，對比結果表明采用AFSA對視頻字幕進行選擇后，降低了分類器輸入維數，計算復雜度降低，加快了定位收斂速度，AFSA－LSSVM可以滿足大規模的視頻字幕定位實時性要求。

表3 不同模型的訓練時間和測試時間對比

3 結束語

針對視頻字幕的定位問題，提出了一種采用AFSA選擇特征和LSSVM定位相結合的視頻字幕定位模型，仿真實驗結果表明，AFSA－LSSVM提高了視頻字幕定位的效率與正確率。備選字幕區域的選取優化是一下步將要進行的研究工作，以進一步提高字幕的定位正確率。

［1］ TANG X，GAO X，LIU J.A spatial－temporal approach for video caption detection and recognition［J］.IEEE Trans.Neural Networks，2002，13(4):961－971.

［2］ LEFEVRE S，VINCENT N.Caption localization in video sequences by fusion of multiple detectors［C］//Proc.Eighth International Conference on Document Analysis and Recognition.［S.l.］:IEEE Press，2005:106－110.

［3］葛菲，史萍.基于內容的電視廣告段落檢測系統［J］.電視技術，2010，34(9):106－109.

［4］ ODOBEZ J，CHEN D.Video text recognition using sequential Monte Carlo and error voting methods［J］.Pattern Recogn，Lett.，2005，26(9):1386－1403.

［5］葛菲，史萍，姚彬，等.廣告段落分割系統中的字幕檢測［J］.電視技術，2010，34(2):25－29.

［6］王勇，燕繼坤，鄭輝，一種自適應的視頻幀中字幕檢測定位方法［J］.計算機應用，2004，24(1):134－135.

［7］易劍，彭宇新，肖建國.基于顏色聚類和多幀融合的視頻文字識別方法［J］.軟件學報，2011，22(12):2919－2933.

［8］劉駿偉，吳飛，莊越挺.基于SVM和ICA的視頻幀字幕自動定位與提取［J］.中國圖象圖形學報，2003，8(11):1331－1337.

［9］莊越挺，劉駿偉，吳飛.基于支持向量機的視頻字幕自動定位與提取［J］.計算機輔助設計與圖形學學報，2002，14(8):750－0753.

［10］ LIUM，SONG J，CAIM.A comprehensive method formultilingual video text detection，localization，and extraction［J］.IEEE Trans.Circuits and Systems for Video Technology，2005，15(2):243－255.