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

陳燕升，任江濤，黃達(dá)峰

(1.廣東輕工職業(yè)技術(shù)學(xué)院 a.環(huán)境工程系;b.計(jì)算機(jī)工程系，廣東廣州510300;2.中山大學(xué)軟件學(xué)院，廣東廣州510275)

隨著網(wǎng)絡(luò)技術(shù)發(fā)展，視頻流劇增，不良的網(wǎng)絡(luò)視頻圖像對(duì)社會(huì)的穩(wěn)定和人們的身心健康產(chǎn)生不利影響，通過對(duì)視頻信息的字幕進(jìn)行定位，有利于對(duì)后續(xù)視頻內(nèi)容進(jìn)行安全分析和檢測(cè)，因此建立精確、高效的視頻字幕定位模型成為了當(dāng)前研究的熱點(diǎn)［1］。

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

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

1 視頻字幕定位模型

1.1 獲取備選字幕區(qū)域

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

圖1 視頻幀的分解結(jié)果

1.2 提取備選字幕區(qū)域的特征

1)對(duì)備選字幕區(qū)域進(jìn)行邊緣檢測(cè)，得到 0°，30°，60°，90°，120°以及 150°方向的邊緣圖，共得到 6 個(gè)方向的邊緣圖。

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

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

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

1.3 AFSA選擇最優(yōu)字幕特征

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

1.3.1 人工魚群算法

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

1)覓食行為的數(shù)學(xué)表達(dá)式為

式中:X i為人工魚當(dāng)前狀態(tài);Yi為食物密度;Rand()為(0，1)范圍內(nèi)的隨機(jī)數(shù);Step為移動(dòng)步長(zhǎng)。

2)聚群行為的數(shù)學(xué)表達(dá)式為

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

3)追尾行為的數(shù)學(xué)表達(dá)式為

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

4)公告板。公告牌是用于記錄最優(yōu)人工魚的狀態(tài)。

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

2)提取備選字幕區(qū)域的36個(gè)特征參數(shù)，并對(duì)特征進(jìn)行歸一化處理

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

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

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

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

由此看來，在分析新聞?wù)Z篇時(shí)，光注重語(yǔ)篇內(nèi)部銜接是遠(yuǎn)遠(yuǎn)不夠的，應(yīng)把語(yǔ)篇置于社會(huì)語(yǔ)境中加以人際意義的分析注解，這樣才能完全吃透文本。

6)評(píng)價(jià)某條人工魚的覓食、追尾和聚群行為所得的結(jié)果，若執(zhí)行某個(gè)行為后，人工魚的狀態(tài)優(yōu)于當(dāng)前狀態(tài)，則該人工魚向此方向前進(jìn)一步，接著轉(zhuǎn)到步驟8)執(zhí)行。

7)產(chǎn)生一個(gè)隨機(jī)數(shù)r，若r＜Pfb，則人工魚執(zhí)行隨機(jī)行為，否則執(zhí)行反饋行為，向公告牌中最優(yōu)方向移動(dòng)一步，并得到當(dāng)前解域范圍內(nèi)的最好的人工魚狀態(tài)。

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

9)判斷算法結(jié)束條件，如果達(dá)到最大迭代次數(shù)，則結(jié)束算法，并輸出公告牌中的人工魚狀態(tài)，即為最優(yōu)視頻字幕特征子集，否則passed_iterate=passed_iterate+1，轉(zhuǎn)向步驟6)執(zhí)行。

10)根據(jù)最優(yōu)視頻字幕特征子集對(duì)最優(yōu)視頻字幕訓(xùn)練集和測(cè)試集進(jìn)行特征約簡(jiǎn)，得到約簡(jiǎn)后的訓(xùn)練集和測(cè)試集。

11)將特征約簡(jiǎn)后的最優(yōu)視頻字幕訓(xùn)練集送到LSSVM進(jìn)行訓(xùn)練，建立最優(yōu)視頻字幕定位模型。

12)將約簡(jiǎn)后的測(cè)試集輸入到已建立的最優(yōu)視頻字幕定位模型進(jìn)行測(cè)試，以驗(yàn)證模型的性能。

1.4 視頻字幕的定位流程

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

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

2 仿真實(shí)驗(yàn)

2.1 數(shù)據(jù)來源

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

2.2 對(duì)比模型及評(píng)價(jià)標(biāo)準(zhǔn)

為了讓AFSA－LSSVM模型的定位結(jié)果具有可比性，選擇表1中的幾種模型進(jìn)行對(duì)比實(shí)驗(yàn)。模型性能評(píng)價(jià)標(biāo)準(zhǔn)為:視頻字幕定位的正確率、誤判率和定位時(shí)間。

表1 對(duì)比模型及說明

2.3 實(shí)驗(yàn)結(jié)果分析

2.3.1 各模型選擇的特征子集

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

表2 各模型對(duì)不同類型視頻字幕選擇的特征數(shù)

2.3.2 視頻字幕的定位性能對(duì)比

根據(jù)選擇最優(yōu)視頻字幕特征子集分別對(duì)訓(xùn)練集和測(cè)試集進(jìn)行視頻字幕特征約簡(jiǎn)處理，然后將訓(xùn)練集輸入到LSSVM進(jìn)行學(xué)習(xí)和建模，最后采用建立的視頻字幕定位模型對(duì)測(cè)試集進(jìn)行測(cè)試，定位結(jié)果的正確率和誤判率如圖3和圖4所示。

圖3 各模型的定位正確率對(duì)比

圖4 各模型的誤判率對(duì)比

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

同時(shí)從圖3和4可以看出，相對(duì)于GA－LSSVM和POS－LSSVM模型，AFSA－LSSVM的視頻字幕定位正確率更高，誤判率進(jìn)一步降低，這有效地表明了AFSA獲得的特征子集可以更加準(zhǔn)確地描述視頻字幕區(qū)域，AFSA－LSSVM可以獲得更優(yōu)的視頻字幕定位結(jié)果。

2.3.3 訓(xùn)練和測(cè)試時(shí)間比較

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

表3 不同模型的訓(xùn)練時(shí)間和測(cè)試時(shí)間對(duì)比

3 結(jié)束語(yǔ)

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

［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］葛菲，史萍.基于內(nèi)容的電視廣告段落檢測(cè)系統(tǒng)［J］.電視技術(shù)，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］葛菲，史萍，姚彬，等.廣告段落分割系統(tǒng)中的字幕檢測(cè)［J］.電視技術(shù)，2010，34(2):25－29.

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

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

［8］劉駿偉，吳飛，莊越挺.基于SVM和ICA的視頻幀字幕自動(dòng)定位與提?。跩］.中國(guó)圖象圖形學(xué)報(bào)，2003，8(11):1331－1337.

［9］莊越挺，劉駿偉，吳飛.基于支持向量機(jī)的視頻字幕自動(dòng)定位與提取［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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.