一類可分離的視頻游動字幕檢測算法

摘 要：視頻數(shù)據(jù)中游動字幕的檢測是現(xiàn)代智能監(jiān)播系統(tǒng)中的一個重要問題，同時(shí)也是后續(xù)諸多視頻數(shù)據(jù)處理的一個基本前提和出發(fā)點(diǎn)。將基于內(nèi)容的數(shù)據(jù)檢索技術(shù)應(yīng)用于視頻游動字幕的檢測算法，設(shè)計(jì)了游動字幕矢量化方法，給出了相似度的準(zhǔn)則，提出了游動字幕的檢測算法，并給出了相應(yīng)的數(shù)值實(shí)驗(yàn)及算法的復(fù)雜度分析。實(shí)驗(yàn)證明結(jié)果是正確和有效的。

關(guān)鍵詞：視頻游動字幕； 智能監(jiān)播系統(tǒng)； 基于內(nèi)容的檢索

中圖分類號：TP391.41 文獻(xiàn)標(biāo)志碼：A

文章編號：10013695(2008)09285603

Algorithm on kind of separable mobile text on video data

DONG Jianmin1， ZHOU Mingquan2， GENG Guohua1

(1. Institute of Visualization Technology， Northwest University， Xi’an 710069， China； 2. College of Information Science Technology， Beijing Normal University， Beijing 100085， China)

Abstract:Detecting the mobile text in video data is a key problem for it is the first step of other processing or applications on video data.The paper proposed， contentbased image retrievel(CBIR) algorithm which was including the construction of vectorization method and similar rule， description with pseudocode. Finally， the numerical experiments show that the alogrithm is accurate and effective .

Key words：video mobile text; intelligent watching system; contentbased image retrievel(CBIR)

隨著數(shù)字化的大力發(fā)展，過去的二十年中我國廣播電視事業(yè)遇到了千載難逢的發(fā)展機(jī)遇。當(dāng)前，廣播電視事業(yè)已經(jīng)走上了一個快速發(fā)展的軌道。據(jù)來自廣電總局的網(wǎng)站消息^[1]，截至2005年底，我國的電視臺總數(shù)已接近2 000個之多。這對我國的對外信息發(fā)布，傳遞以及弘揚(yáng)正氣，宣傳先進(jìn)文化起到了不可估量的作用，為指導(dǎo)我國各地方部門正確地進(jìn)行社會管理和工農(nóng)業(yè)生產(chǎn)做出了不可磨滅的貢獻(xiàn)。當(dāng)然，我國廣播電視事業(yè)的發(fā)展，不但弘揚(yáng)了我國建設(shè)和諧社會的主旋律，堅(jiān)持了正確的輿論導(dǎo)向，而且贏得了為自己生存發(fā)展的經(jīng)濟(jì)基礎(chǔ)，同樣來自于國家廣電總局的消息，僅2005年電視總收入就有931億之多，而在這么多的收入中，電視廣告收入占到45%以上。然而，廣播電視的發(fā)展同時(shí)也暴露出諸多問題：a)各省市電視臺播出節(jié)目的質(zhì)量和內(nèi)容有待于進(jìn)一步規(guī)范化，尤其要剔除那些不符合我國倡導(dǎo)的精神文明的內(nèi)容。作為國家廣電事業(yè)的最高行政管理部門，面對全國的電視臺幾乎每天24 h的播出，如何對這些電視臺進(jìn)行有效、高效和科學(xué)的管理，是一項(xiàng)十分艱巨的任務(wù)。b)在利益的驅(qū)動下，各地方電視臺甚至是某些省的衛(wèi)視頻道違規(guī)播出掛角廣告、游動字幕廣告等。對于廣播電視的行政管理部門來說，實(shí)時(shí)監(jiān)測這類圖像信息，已經(jīng)是當(dāng)前必須解決的問題之一。目前普遍采用的就是利用視頻數(shù)據(jù)卡采集數(shù)據(jù)后人工的監(jiān)測，當(dāng)然這樣的正確率無須置疑，但大大加大了人的體力和腦力勞動。本文就是針對一類可分離的游動字幕，利用視頻卡實(shí)時(shí)地采集數(shù)據(jù)，給出一個工程上可實(shí)用的游動字幕的自動檢測算法，為以后對于類似問題的識別作一些基礎(chǔ)的探索。

1 算法設(shè)計(jì)

1.1 有關(guān)概念與記號

定義1 可分離的游動字幕。它是指游動的字幕和背景畫面可以被計(jì)算機(jī)自動地分割出來，即存在一個算子P，使得當(dāng)游動字幕出現(xiàn)時(shí)，算子P可以將畫面分成兩類數(shù)據(jù)，即字幕數(shù)據(jù)（用相應(yīng)點(diǎn)的顏色信息表示）和背景數(shù)據(jù)（一般用特定灰度表示）。通常算子P是預(yù)先固定的。

圖1和2分別表示字幕與背景是可分離與不可分離的。

這主要是因?yàn)樽帜缓捅尘爱嬅嫱耆诤显谝黄穑瑫r(shí)背景畫面具有不可預(yù)知性。本文主要討論的是類似于圖1的這種可以將游動字幕從背景畫面中分離出來的視頻數(shù)據(jù)。當(dāng)然，考慮到系統(tǒng)設(shè)計(jì)時(shí)往往具有實(shí)時(shí)性，所謂可分離的這種說法是相對的，也就是說，游動的字幕可以從背景中利用事先設(shè)定好的算法很容易得到。

定義2 字幕圖像。設(shè)f(x，y，t)是一個定義在Ω×[0，∞)上面的函數(shù)。其中點(diǎn)(x，y)屬于Ω，f(x，y，t)函數(shù)值是t時(shí)刻（x，y）點(diǎn)的顏色屬性，取值范圍為非負(fù)數(shù)，Ω=[a，b]×[c，d]是經(jīng)過算子P的前期處理后得到游動字幕的畫面區(qū)域。

為了簡單起見，將該游動字幕矢量化的公式如下：

定義3 函數(shù)f(x，y，t)在t時(shí)刻y方向上的投影：

V(x，t)=∫dcf(x，y，t)dy(1)

其中：x∈[a，b]，y∈[c，d]。當(dāng)然，相應(yīng)的離散化形式為:設(shè)在[a，b]上取的離散點(diǎn)的個數(shù)為W個，在[c，d]取的離散點(diǎn)的個數(shù)為H個，且離散化的步長取值為1，則離散化的計(jì)算公式為

V（m，t)=∑Hn=1f(m，n，t)(2)

其中：m=1，2，…，W。

定義4 記號。

S（V，t)={x｜V(x，t)＞0，x∈[a，b]}(3)

是指S(V，t)的支撐集合，記號s=supS(V，t)≠表示該集合的上確界，其相應(yīng)的離散化形式為

SD(V，t)={m｜V(m，t)＞0，m=1，2，…，W}（4）

其中：W是V的元素個數(shù)

SD=supSD(V，t)≠(SD(V，t))(5)

定義5 建立坐標(biāo)系。坐標(biāo)原點(diǎn)在所選區(qū)域的左下角，然后向右和向上分別為x與y的正方向，如圖3所示。

‖V‖t0=∫dcV(x，t0)2 dx(6)

其離散形式為‖V‖t0=∑Mk=1V2(k，t0)

（7）

其中：M為V的元素個數(shù)。

定義6 算子。

E（V（x，t0)，s，d)=V(x，t0)，s≤x≤s+d（8）

其作用是提取出函數(shù)V(x，t0)中在s與s+d之間的函數(shù)值，其相應(yīng)的離散形式則是取出矢量V(m，t0)位于s與s+d之間的d個分量。其中包括第s個分量但不包含s+d個分量，即

E(V(m，t0)，s，d)=V(m，t0)（9）

其中：m=s，s+1，…，s+d-1。

一般而言，由于中文的閱讀習(xí)慣，游動字幕的移動方向是從右向左。

1.2 算法的基本框架

第一部分：區(qū)域字幕數(shù)據(jù)的矢量化方法，參見圖4。

第二部分：決策部分。根據(jù)算子P分離得到的給定區(qū)域的矢量函數(shù)值集合，設(shè)出現(xiàn)游動字幕事件為p1，其依賴于隨機(jī)變量e，p1(e＜ε)=0.999 9；ε是預(yù)先給定的一個經(jīng)驗(yàn)值，通常是足夠小的。為了與本算法結(jié)合，取

e(t0)=∫dcV(x，t0)dx（10）

第三部分：水平游動字幕的監(jiān)測部分。設(shè)四個連續(xù)的時(shí)間點(diǎn)的畫面指定區(qū)域的矢量數(shù)據(jù)分別為V(x，t0)、V（x，t1)、V(x，t2)，時(shí)間間隔為t s，移動速度v像素/s的勻速向左移動，d=vt。在不混淆的前提下，分別簡記為V0、V1、V2，參見圖5流程圖。

13 算法的描述

算法輸入：f(x，y，t0)，f(x，y，t1)，f(x，y，t2)，f(x，y，t3)，v，P，E，，v各自代表在t0~t3時(shí)刻指定區(qū)域的畫面圖像、游動速度， P為分離算子，E為出現(xiàn)游動字幕的概率，兩個矢量相似度函數(shù)。

算法輸出：t0~t3是否出現(xiàn)游動字幕以及相似矢量的分量。

a)算法初始化。根據(jù)輸入的視頻數(shù)據(jù)，計(jì)算第一幅畫面指定區(qū)域f(x，y，t0)的矢量化V0， 由式（10）計(jì)算游動字幕出現(xiàn)的概率p1（p1>E），則算法轉(zhuǎn)入b);否則，輸出沒有游動字幕的信息，算法結(jié)束。

b)設(shè)f(x，y，t1)、f(x，y，t2)、f(x，y，t3)表示在連續(xù)三個時(shí)間點(diǎn)的指定區(qū)域的時(shí)間點(diǎn)畫面數(shù)據(jù)，f(x，y，t1)，f(x，y，t2)，f(x，y，t3)分別表示經(jīng)過分離算子P處理后的數(shù)據(jù)。根據(jù)式（1）分別計(jì)算這些指定區(qū)域的矢量值，用V1，V2，V3來表示，轉(zhuǎn)入c)。

c）對于V1、V2、V3，利用V1得到可能字幕的起點(diǎn)s，根據(jù)游動字幕速度v，計(jì)算連續(xù)畫面之間的游動距離d，抽取V（1）P=E（V2，s，d)，V（2）P=E（V3，s+d，s+2d)，轉(zhuǎn)d）。

d）計(jì)算Ｖ（１）p、V(2)p之間的相似度。如果滿足一定的相似數(shù)量關(guān)系，則輸出檢測到游動字幕的信息，持續(xù)時(shí)間為t3-t0；否則，輸出沒有檢測到游動字幕的信息，算法結(jié)束。 

14 算法常用的相關(guān)參數(shù)設(shè)置

實(shí)際的數(shù)據(jù)采集中，經(jīng)常采用的是CIF^[2]編碼規(guī)則，處理彩色畫面的問題主要有兩種：a)將彩色畫面灰度化，按照當(dāng)前點(diǎn)的灰度計(jì)算公式。b)在實(shí)際數(shù)據(jù)采集中，直接利用其數(shù)據(jù)的色調(diào)和亮度部分?jǐn)?shù)據(jù)。

相關(guān)性函數(shù)的設(shè)置主要分為以下幾種：

a)計(jì)算兩個矢量的Hausdorf距離^[3]；

b)計(jì)算兩個矢量元素的相同數(shù)目；

c)構(gòu)造一個函數(shù):[0，+∞)｜→[0，1]，其值單調(diào)不增，然后令y=‖V(1)p-V(2)p‖，代入到該函數(shù)中。如果函數(shù)值越靠近1，說明兩者的相似程度越大；相反，則說明兩者的差異越大。常見的該函數(shù)的取法有

非線性函數(shù)(y)=e-y/a，y≤a0，y＞a（11）

線性函數(shù)(y)=-y/a+1，y≤a0，y＞a（12）

其中：a是一個事先確定好的常數(shù)。

分離算子P經(jīng)常采用的是常見的圖像分割算法，有時(shí)就干脆利用閾值分割^[4]算法。

2 算法實(shí)現(xiàn)

2.1 算法的數(shù)值實(shí)驗(yàn)結(jié)果

筆者的實(shí)驗(yàn)數(shù)據(jù)利用專業(yè)的視頻采集卡，采集了某衛(wèi)視頻道的一些帶有游動字幕的視頻數(shù)據(jù)，通過利用該算法，得到了以下的數(shù)值結(jié)果：

對于分離算子采用了閾值分割算法，計(jì)算時(shí)CIF畫面的數(shù)據(jù)采用了幀率為25 fps，隨機(jī)截取了25個帶有游動字幕的測試視頻數(shù)據(jù)各30 s，25個沒有游動字幕的測試視頻數(shù)據(jù)各30 s，根據(jù)各自離散化的公式，利用配置位P4 3.0 512 MB RAM的Windows XP 平臺上的MATLAB 7.0編程實(shí)現(xiàn)，Ｅ＝２０，閾值取140進(jìn)行計(jì)算機(jī)的自動分割。對于彩色數(shù)據(jù)，筆者直接采用了畫面每一個點(diǎn)的色度信息，移動速度是連續(xù)v=50像素/s。由于篇幅的原因，筆者任選了一個移動字幕數(shù)據(jù)的執(zhí)行顯示，分別通過圖6~10顯示。

在實(shí)驗(yàn)中的相似度函數(shù)采用的是線性函數(shù)，a=5 000，實(shí)驗(yàn)結(jié)果如表1所示。

如果相似度函數(shù)采用的是非線性函數(shù)：a=5 000，實(shí)驗(yàn)結(jié)果如表2所示。采用非線性函數(shù)的準(zhǔn)確率降低的主要原因是非線性函數(shù)對數(shù)據(jù)的擾動比較敏感。

2.2 算法的復(fù)雜度分析

首先，很容易得到如下結(jié)論：

命題 若被檢測的區(qū)域高為n個，長為m個像素，則算法在矢量化時(shí)計(jì)算復(fù)雜度為O(n)，存儲空間復(fù)雜度為O(n×m)。

定理 若算法采用線性函數(shù)作為相似性判斷準(zhǔn)則，則檢測算法的計(jì)算復(fù)雜度為O(n)，存儲復(fù)雜度為O(n×m)。

證明 從命題可知，算法在矢量化階段的計(jì)算復(fù)雜度為O(n)，存儲復(fù)雜度為O(n×m)。這樣，算法在決策階段的計(jì)算復(fù)雜度僅僅作m次加法運(yùn)算，存儲復(fù)雜度為m+1。在檢測階段，需要計(jì)算四個連續(xù)畫面的矢量，則計(jì)算復(fù)雜度仍然為O(n)，存儲復(fù)雜度為O(n×m)。取出兩個連續(xù)畫面的矢量以及計(jì)算兩者差的復(fù)雜度為O(h)，需要存儲空間為O(h)，然后再代入到相似性函數(shù)中，則需要計(jì)算一次除法運(yùn)算和加法運(yùn)算，注意到h<

推論 若算法采用非線性函數(shù)作為相似性判斷準(zhǔn)則，則檢測算法的計(jì)算復(fù)雜度仍為O(n)，存儲復(fù)雜度為O(n×m)。

從前面的定理證明，其結(jié)論僅僅是檢測函數(shù)的選取不同而導(dǎo)致計(jì)算復(fù)雜度略微的差異，可以忽略。

3 結(jié)束語

本文描述了一種可分離的視頻數(shù)據(jù)游動字幕的檢測方法，給出了其基本原理和檢測的基本算法，并以某電視臺的視頻數(shù)據(jù)作為測試數(shù)據(jù)集，結(jié)果顯示了算法的有效性。同時(shí)，本文算法在實(shí)際的實(shí)時(shí)監(jiān)測系統(tǒng)中，首先對于可分離算子P的選擇十分靈活，如何使P具有很好的抗噪性是十分有意義的。如果字幕是從屏幕自左向右移動時(shí)，只需要將式(4)中的上確界改為下確界；同樣，如果需要檢測屏幕中由上而下或者由下而上的指定區(qū)域的游動字幕的算法，僅僅需要將矢量化的方法略微改動即可，本文不再贅述。對于每一個畫面的指定區(qū)域，其字幕的移動順序需要根據(jù)具體的樣本來設(shè)計(jì)智能學(xué)習(xí)算法而得到移動速度，這對于移動字幕的檢測是至關(guān)重要的，對于那些為藝術(shù)創(chuàng)作而設(shè)置變速游動的字幕檢測將具有挑戰(zhàn)意義。本文所給的算法也同樣適合類似于字幕的圖像數(shù)據(jù)監(jiān)測。

參考文獻(xiàn)：

［1］中華人民共和國廣播電視管理總局.2005年全國廣播影視發(fā)展概況[EB/OL].(20051218) [20070820]. http://www.chinasarft.gov.cn/manage/publishfile/51/3887.html.

［2］InternationalStandard. ISO／IEC i44962， Information technologycoding of audiovisual objects[S].2001．

［3］楊清夙 ，游志勝，張先玉.基于豪斯多夫距離的快速多人臉檢測算法[J]. 電子科技大學(xué)學(xué)報(bào)，2004，33(4):407409.

［4］林定天，蔡光程.改進(jìn)的矩不變閾值分割圖像算法[J].云南民族大學(xué)學(xué)報(bào)：自然科學(xué)版， 2007，16(1):4244.