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

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

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

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

1 算法設計

1.1 有關概念與記號

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

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

這主要是因為字幕和背景畫面完全融合在一起，同時背景畫面具有不可預知性。本文主要討論的是類似于圖1的這種可以將游動字幕從背景畫面中分離出來的視頻數(shù)據(jù)。當然，考慮到系統(tǒng)設計時往往具有實時性，所謂可分離的這種說法是相對的，也就是說，游動的字幕可以從背景中利用事先設定好的算法很容易得到。

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

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

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

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

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

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)≠表示該集合的上確界，其相應的離散化形式為

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 建立坐標系。坐標原點在所選區(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ù)值，其相應的離散形式則是取出矢量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。

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

1.2 算法的基本框架

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

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

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

第三部分：水平游動字幕的監(jiān)測部分。設四個連續(xù)的時間點的畫面指定區(qū)域的矢量數(shù)據(jù)分別為V(x，t0)、V（x，t1)、V(x，t2)，時間間隔為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時刻指定區(qū)域的畫面圖像、游動速度， P為分離算子，E為出現(xiàn)游動字幕的概率，兩個矢量相似度函數(shù)。

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

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

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

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

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

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

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

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

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

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

c)構造一個函數(shù):[0，+∞)｜→[0，1]，其值單調不增，然后令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經常采用的是常見的圖像分割算法，有時就干脆利用閾值分割^[4]算法。

2 算法實現(xiàn)

2.1 算法的數(shù)值實驗結果

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

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

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

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

2.2 算法的復雜度分析

首先，很容易得到如下結論：

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

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

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

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

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

3 結束語

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

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