視頻語(yǔ)義上下文標(biāo)簽樹(shù)及其結(jié)構(gòu)化分析

余春艷， 蘇晨涵

（福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 福州 350108）

視頻高層語(yǔ)義解析是視頻內(nèi)容理解的重要研究?jī)?nèi)容，也是視頻管理、組織、檢索等眾多視頻應(yīng)用的基礎(chǔ)性工作[1]。形式上，視頻呈現(xiàn)為一組靜態(tài)圖像幀的序列；但為了呈現(xiàn)物體運(yùn)動(dòng)、事件發(fā)展等動(dòng)態(tài)信息，視頻在內(nèi)容上具有非常強(qiáng)的時(shí)間關(guān)聯(lián)和邏輯結(jié)構(gòu)[2]。一般認(rèn)為視頻內(nèi)容層次從高到底可分為視頻、場(chǎng)景、鏡頭組、鏡頭等[3]，該層次性模型是視頻內(nèi)容理解的重要基礎(chǔ)。

一般認(rèn)為，由同一攝像機(jī)連續(xù)拍攝得到的若干幀圖像組成鏡頭(shot)是視頻的基本物理單元[4]。可從圖像、音頻等模態(tài)分析鏡頭的底層特征、物理對(duì)象等時(shí)空信息，獲得的語(yǔ)義表征即為鏡頭語(yǔ)義。以視頻鏡頭作為基本單位，將視頻分解形成視頻鏡頭序列，逐一提取其鏡頭語(yǔ)義，形成順序排列的鏡頭語(yǔ)義序列。

從符合人類(lèi)認(rèn)識(shí)理解視頻內(nèi)容的角度來(lái)看，鏡頭語(yǔ)義與鏡頭語(yǔ)義間還隱含著時(shí)間上、語(yǔ)義上、結(jié)構(gòu)上的關(guān)聯(lián)。這種關(guān)聯(lián)稱(chēng)為鏡頭語(yǔ)義上下文。合理地描述和使用這種上下文信息，有助于更好地從局部的鏡頭語(yǔ)義引導(dǎo)至整體的視頻語(yǔ)義，本文主要圍繞著這一問(wèn)題展開(kāi)。

目前，用時(shí)序關(guān)系表征鏡頭語(yǔ)義上下文[5-11]較為普遍，運(yùn)用各種時(shí)序分析方法從鏡頭語(yǔ)義序列中提取上下文，形成鏡頭語(yǔ)義上下文的序列化表征。文獻(xiàn)[7]與文獻(xiàn)[8]以本體論為基礎(chǔ)，構(gòu)建了能夠描述鏡頭語(yǔ)義間時(shí)序關(guān)系的語(yǔ)義本體，并運(yùn)用該語(yǔ)義本體對(duì)足球體育視頻鏡頭語(yǔ)義序列中的時(shí)序上下文進(jìn)行分析；文獻(xiàn)[9-11]分別使用具有時(shí)序信息處理能力的隱馬爾科夫模型(hidden Markov model,HMM)和動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)(dynamic Bayesian network,DBN)實(shí)現(xiàn)視頻鏡頭語(yǔ)義序列中時(shí)序上下文關(guān)系的建模和分析，并較好地運(yùn)用于乒乓球和足球體育視頻。

然而，考慮到以鏡頭為底層基礎(chǔ)的視頻內(nèi)容層次化表征，時(shí)序關(guān)聯(lián)下的鏡頭語(yǔ)義上下文序列化表征并不完備。以視頻內(nèi)容層次化結(jié)構(gòu)為基礎(chǔ)，視頻具有鏡頭、場(chǎng)景等多種粒度；其內(nèi)容感知依賴(lài)于不同粒度層次上語(yǔ)義間上下文交互[12]。因此，鏡頭語(yǔ)義在不同粒度層上的交互可形成上下文的層次化結(jié)構(gòu)，而非時(shí)間維度上的簡(jiǎn)單序列表征。

例如足球視頻中的一個(gè)進(jìn)球片段包含4個(gè)鏡頭，其語(yǔ)義序列為“普通遠(yuǎn)景”、“禁區(qū)遠(yuǎn)景”、“特寫(xiě)”、“回放”。簡(jiǎn)單的時(shí)序關(guān)系局限于“普通遠(yuǎn)景”與“禁區(qū)遠(yuǎn)景”、“特寫(xiě)”與“回放”間的時(shí)空依賴(lài)關(guān)系。事實(shí)上，其中“普通遠(yuǎn)景”與“禁區(qū)遠(yuǎn)景”、“特寫(xiě)”和“回放”又兩兩組合，前一個(gè)組合表征了“比賽進(jìn)行”的內(nèi)容，后一個(gè)組合表征了“比賽暫停”期間的慶祝、歡呼和精彩回放等內(nèi)容。4個(gè)鏡頭組合在一起表征一個(gè)完整的進(jìn)球片段，其鏡頭語(yǔ)義上下文層次化表示如圖1所示。因此，鏡頭語(yǔ)義上下文結(jié)構(gòu)化表征可以得到更顯著的信息增益，有助于視頻內(nèi)容理解的效率和正確性。

圖1 鏡頭語(yǔ)義上下文的層次化結(jié)構(gòu)

為此，本文提出采用一棵帶有上下文標(biāo)簽的視頻語(yǔ)義上下文標(biāo)簽樹(shù)(video semantic context labeled tree,VSCLT)作為鏡頭語(yǔ)義上下文層次結(jié)構(gòu)的表征模型，其根節(jié)點(diǎn)為視頻標(biāo)簽結(jié)點(diǎn)，每個(gè)葉節(jié)點(diǎn)代表一個(gè)鏡頭及其語(yǔ)義，每個(gè)內(nèi)結(jié)點(diǎn)為上下文標(biāo)簽結(jié)點(diǎn)，代表其子節(jié)點(diǎn)間的上下文信息。VSCLT的樹(shù)形結(jié)構(gòu)與視頻內(nèi)容層次化表征形式一致，符合用戶(hù)理解視頻內(nèi)容的方式。

然而，VSCLT的層次化構(gòu)建是一個(gè)具有挑戰(zhàn)性的問(wèn)題。該問(wèn)題以順序排列的鏡頭語(yǔ)義序列為基礎(chǔ)，需要分析鏡頭語(yǔ)義在不同粒度層上復(fù)雜的依賴(lài)關(guān)系，本質(zhì)上是以鏡頭語(yǔ)義為基本元素的結(jié)構(gòu)化分析。該結(jié)構(gòu)化分析問(wèn)題的重點(diǎn)在于鏡頭語(yǔ)義從其序列結(jié)構(gòu)——鏡頭語(yǔ)義序列向樹(shù)形層次結(jié)構(gòu)——VSCLT的轉(zhuǎn)化。前述的時(shí)域邏輯本體、HMM或DBN鏡頭語(yǔ)義上下文分析方法僅適用于解決鏡頭語(yǔ)義序列中的時(shí)序關(guān)系，均無(wú)法完成鏡頭語(yǔ)義上下文的結(jié)構(gòu)化分析。

Tsochantaridis等[13-15]提出了結(jié)構(gòu)化支持向量機(jī)(SVM-Struct)用于結(jié)構(gòu)化數(shù)據(jù)分析，利用分解與選塊的思想對(duì)數(shù)據(jù)內(nèi)部元素之間的依賴(lài)關(guān)系進(jìn)行分析，實(shí)現(xiàn)數(shù)據(jù)內(nèi)部結(jié)構(gòu)的預(yù)測(cè)。例如，SVM-Struct可應(yīng)用于句子的句法分析以生成對(duì)應(yīng)的句法樹(shù)，實(shí)現(xiàn)單詞序列結(jié)構(gòu)空間到句法樹(shù)型結(jié)構(gòu)空間的映射[13-17]。

為此，本文為VSCLT的構(gòu)建，引入了SVM-Struct的分析方法，根據(jù)鏡頭語(yǔ)義序列和VSCLT的聯(lián)合特性構(gòu)造了語(yǔ)義上下文結(jié)構(gòu)化函數(shù)和損失函數(shù)，基于SVM-Struct實(shí)現(xiàn)了鏡頭語(yǔ)義上下文的結(jié)構(gòu)化分析，并應(yīng)用于足球體育視頻。實(shí)驗(yàn)結(jié)果表明，VSCLT在時(shí)序性、結(jié)構(gòu)性、領(lǐng)域性、邏輯性等方面表征能力良好；基于SVM-Struct的結(jié)構(gòu)化分析方法準(zhǔn)確率、召回率和F1值上性能良好。

1 結(jié)構(gòu)化支持向量機(jī)

結(jié)構(gòu)化數(shù)據(jù)的復(fù)雜性在于構(gòu)成其整體的內(nèi)部數(shù)據(jù)元素之間存在較為復(fù)雜的依賴(lài)關(guān)系，例如樹(shù)形結(jié)構(gòu)[15-16]。結(jié)構(gòu)化數(shù)據(jù)分析的目的在于對(duì)輸入結(jié)構(gòu)化數(shù)據(jù)x∈X給出其結(jié)構(gòu)y∈Y，其關(guān)鍵是映射函數(shù)f:X→Y。SVM-Struct的基本思路就是根據(jù)標(biāo)注數(shù)據(jù)集S找到映射函數(shù)f:X→Y。

為此，假定映射函數(shù)形為[13]：

其中，判別函數(shù)F可以表示為F(x,y;w)=＜w,ψ(x,y)＞，w是權(quán)向量，結(jié)構(gòu)化函數(shù)ψ(x,y)代表了輸入的結(jié)構(gòu)化數(shù)據(jù)與輸出的結(jié)構(gòu)彼此之間特性合并的一個(gè)向量，一般根據(jù)具體應(yīng)用問(wèn)題結(jié)合輸入與輸出數(shù)據(jù)特性提取得到[13-15]。

SVM-Struct的訓(xùn)練目標(biāo)設(shè)定為找到映射函數(shù)f，使得期望風(fēng)險(xiǎn)最小化。其中，P(x,y)為樣本的分布，Δ(y,f(x))為量化預(yù)測(cè)結(jié)構(gòu)損失度的損失函數(shù)[13]。

通常樣本分布P(x,y)無(wú)法直接獲得，只能計(jì)算訓(xùn)練數(shù)據(jù)集S={(x,y)∈(X×Y)n:i=1,…,n}的經(jīng)驗(yàn)風(fēng)險(xiǎn)并使之最小化[13-14]。

在訓(xùn)練數(shù)據(jù)集S上訓(xùn)練SVM-Struct得到權(quán)向量w，使得：

其中，δψi(y)≡ψ(xi,yi)-ψ(xi,y)。

采用最大間隔法，并引入松弛變量ξi后，訓(xùn)練SVM-Struct的軟間隔最優(yōu)化問(wèn)題為：

其中，C＞0為設(shè)定的懲罰因子。

結(jié)構(gòu)化數(shù)據(jù)的通常很大，因此式(3)不適用于求解訓(xùn)練SVM-Struct的軟間隔最優(yōu)化問(wèn)題，通常采用兩種方法予以修訂[13]：

方法1使用損失函數(shù)Δ(yi,y)調(diào)整松弛變量：

方法2使用損失函數(shù)Δ(yi,y)調(diào)整分類(lèi)間隔：

由于約束條件規(guī)模非常大，因此需要將上述的軟間隔最優(yōu)化問(wèn)題改寫(xiě)為對(duì)偶形式：

其中，αiy是拉格朗日乘子。為了處理線(xiàn)性不可分情況，SVM-Struct同樣使用核函數(shù)在高維空間計(jì)算2個(gè)向量的內(nèi)積。

SVM-Struct根據(jù)式(6)訓(xùn)練后得到權(quán)向量w后，即可確定映射函數(shù)f。

給定結(jié)構(gòu)信息未知的數(shù)據(jù)x，通過(guò)SVM-Struct進(jìn)行結(jié)構(gòu)預(yù)測(cè)時(shí)，首先生成測(cè)試數(shù)據(jù)的所有候選結(jié)構(gòu){,…,}，然后將所有候選結(jié)構(gòu)輸入式(1)，將具有最優(yōu)值的候選結(jié)構(gòu)作為預(yù)測(cè)的結(jié)構(gòu)y。

SVM-Struct的學(xué)習(xí)和預(yù)測(cè)過(guò)程中，結(jié)構(gòu)化函數(shù)和損失函數(shù)的構(gòu)造和具體應(yīng)用問(wèn)題緊密相關(guān)。首先，結(jié)構(gòu)化函數(shù)的構(gòu)造依賴(lài)于輸入數(shù)據(jù)與其內(nèi)部結(jié)構(gòu)特點(diǎn)，不同的應(yīng)用問(wèn)題，其數(shù)據(jù)內(nèi)部元素的依賴(lài)關(guān)系是各不相同的。其次，傳統(tǒng)的0-1損失在SVM-Struct中不再適用，通常需要以數(shù)據(jù)內(nèi)部節(jié)點(diǎn)為單位計(jì)算損失，因此，需針對(duì)具體應(yīng)用合理設(shè)計(jì)損失函數(shù)[13-17]。

2 視頻語(yǔ)義上下文標(biāo)簽樹(shù)

按照視頻內(nèi)容理解的層次，視頻可以分為鏡頭、鏡頭組、場(chǎng)景和視頻等。圖1中，鏡頭“普通遠(yuǎn)景”和“禁區(qū)遠(yuǎn)景”組合為一個(gè)表征“比賽進(jìn)行”的鏡頭組；鏡頭“特寫(xiě)”和“回放”組合為一個(gè)表征“比賽暫停”的鏡頭組；兩個(gè)鏡頭組組合為一個(gè)場(chǎng)景。

視頻分解為鏡頭序列后，每一個(gè)鏡頭可提取其語(yǔ)義標(biāo)簽，形成順序化鏡頭語(yǔ)義序列。鏡頭語(yǔ)義上下文層次結(jié)構(gòu)需要標(biāo)記鏡頭間、鏡頭組間、場(chǎng)景間的依賴(lài)關(guān)系及鏡頭與鏡頭組間、鏡頭組和場(chǎng)景間、鏡頭與場(chǎng)景間、場(chǎng)景和視頻間的層次關(guān)系。因此，鏡頭語(yǔ)義上下文層次結(jié)構(gòu)涉及4種不同類(lèi)型的標(biāo)簽：鏡頭語(yǔ)義標(biāo)簽、普通上下文標(biāo)簽、場(chǎng)景標(biāo)簽scene和視頻標(biāo)簽video。其中后3種為上下文標(biāo)簽。鏡頭語(yǔ)義標(biāo)簽由鏡頭語(yǔ)義決定，所有鏡頭語(yǔ)義標(biāo)簽組成鏡頭語(yǔ)義標(biāo)簽集合L，所有普通上下文標(biāo)簽組成普通上下文標(biāo)簽集合NL。鏡頭語(yǔ)義上下文依賴(lài)關(guān)系可根據(jù)形如p:cp←c1,…,cj(j＞1,cj∈L∪NL,cp∈video∪scene∪NL)的上下文生成規(guī)則判定。

給定鏡頭語(yǔ)義標(biāo)簽集合L，給定n個(gè)鏡頭組成的視頻V={shot1,…,shotn}，鏡頭shoti具有語(yǔ)義標(biāo)簽li。Lv={l1,…,ln}是視頻V對(duì)應(yīng)的鏡頭語(yǔ)義序列，其中l(wèi)i∈L。給定上下文生成規(guī)則集P，即可生成得到Lv所對(duì)應(yīng)的視頻語(yǔ)義上下文標(biāo)簽樹(shù)VSCLTV，具體過(guò)程如下：

(1) 鏡頭語(yǔ)義序列Lv中每一個(gè)鏡頭語(yǔ)義標(biāo)簽li依次生成一個(gè)葉節(jié)點(diǎn)，從左到右生成初始標(biāo)簽節(jié)點(diǎn)序列Curr={c1,…,cn}，其中ci=li，序列Curr長(zhǎng)度為n；

(2) 從左到右遍歷標(biāo)簽節(jié)點(diǎn)序列Curr，對(duì)于其中子序列{ck,…,ck+m}，若符合上下文生成規(guī)則p∈P，以子序列中每一個(gè)標(biāo)簽節(jié)點(diǎn)為子節(jié)點(diǎn)，以標(biāo)簽cp生成的新標(biāo)簽結(jié)點(diǎn)為父節(jié)點(diǎn)，{ck,…,ck+m}中每個(gè)節(jié)點(diǎn)為標(biāo)簽節(jié)點(diǎn)cp的子節(jié)點(diǎn)，并以cp替換Curr序列中{ck,…,ck+m}部分；

(3) 遍歷結(jié)束生成新的標(biāo)簽節(jié)點(diǎn)序列Curr；

(4) 回到步驟(2)，直至Curr序列長(zhǎng)度為1。

圖2給出了VSCLT示例。以上步驟構(gòu)建的上下文標(biāo)簽樹(shù)一定以視頻標(biāo)簽video為根節(jié)點(diǎn)，根結(jié)點(diǎn)有若干棵子樹(shù)，均以scene標(biāo)簽為子樹(shù)根節(jié)點(diǎn)，以鏡頭語(yǔ)義標(biāo)簽為葉結(jié)點(diǎn)，剩余內(nèi)部節(jié)點(diǎn)為普通上下文標(biāo)簽；因此，整個(gè)樹(shù)形結(jié)構(gòu)表征了鏡頭語(yǔ)義之間的層次關(guān)系。此外，鏡頭語(yǔ)義標(biāo)簽生成葉節(jié)點(diǎn)時(shí)，從左到右按照時(shí)序關(guān)系依次排列；因此，上下文標(biāo)簽樹(shù)中每一個(gè)層次的內(nèi)部結(jié)點(diǎn)間從左到右具有時(shí)序排列的特點(diǎn)。

圖2 視頻語(yǔ)義上下文標(biāo)簽樹(shù)示例圖

VSCLT由鏡頭語(yǔ)義序列采用自底向上的方式逐層構(gòu)建而成，可采用BNF范式自頂向下形式化定義如下：

VSCLT::="video"＜scene標(biāo)簽樹(shù)＞{＜scene標(biāo)簽樹(shù)＞}

＜scene標(biāo)簽樹(shù)＞::="scene"(＜普通上下文標(biāo)簽樹(shù)＞|＜鏡頭語(yǔ)義標(biāo)簽＞){＜普通上下文標(biāo)簽樹(shù)＞|＜鏡頭語(yǔ)義標(biāo)簽＞}

＜普通上下文標(biāo)簽樹(shù)＞::=＜普通上下文標(biāo)簽＞(＜普通上下文標(biāo)簽樹(shù)＞|＜鏡頭語(yǔ)義標(biāo)簽＞){＜普通上下文標(biāo)簽樹(shù)＞|＜鏡頭語(yǔ)義標(biāo)簽＞}

3 面向VSCLT的SVM-Struct構(gòu)建

已知上下文生成規(guī)則集P，給定視頻V={shot1,…,shotn}及其鏡頭語(yǔ)義序列Lv={l1,…,ln}，若鏡頭語(yǔ)義間上下文依賴(lài)關(guān)系已知，則可根據(jù)第2節(jié)中自底向上的VSCLT生成方法，將Lv轉(zhuǎn)化為VSCLT層次結(jié)構(gòu)。

實(shí)際應(yīng)用中，Lv語(yǔ)義上下文關(guān)系有待分析。因此，本文引入SVM-Struct構(gòu)建方法實(shí)現(xiàn)鏡頭語(yǔ)義上下文的結(jié)構(gòu)化分析，實(shí)現(xiàn)鏡頭語(yǔ)義從鏡頭語(yǔ)義序列到VSCLT的轉(zhuǎn)化。

根據(jù)SVM-Struct的基本原理，構(gòu)建視頻V對(duì)應(yīng)的上下文標(biāo)簽樹(shù)VSCLTV需要解決2個(gè)核心問(wèn)題，一是結(jié)構(gòu)化函數(shù)的構(gòu)造；二是損失函數(shù)的構(gòu)造。

考慮到鏡頭語(yǔ)義序列到VSCLT的轉(zhuǎn)化是一種序列結(jié)構(gòu)空間向樹(shù)結(jié)構(gòu)空間的映射。其中序列結(jié)構(gòu)空間的特點(diǎn)以節(jié)點(diǎn)之間的先后順序關(guān)系為體現(xiàn)，而樹(shù)結(jié)構(gòu)空間的特點(diǎn)主要以父節(jié)點(diǎn)和子節(jié)點(diǎn)之間的層次關(guān)系為表征。VSCLT中，上下文生成規(guī)則不僅描述了其父、子節(jié)點(diǎn)間的層次關(guān)系，還描述了子節(jié)點(diǎn)彼此間的先后順序關(guān)系。因此，本文將結(jié)構(gòu)化函數(shù)ψ(x,y)構(gòu)造成VSCLTV結(jié)構(gòu)中上下文生成規(guī)則應(yīng)用頻數(shù)的向量，具體形式如下：

其中，D是P中上下文生成規(guī)則的總數(shù)，pd與ad(d∈[1,D])分別是其中第d條規(guī)則及其在VSCLTV結(jié)構(gòu)中應(yīng)用的頻數(shù)。

結(jié)構(gòu)化問(wèn)題中，通常以數(shù)據(jù)內(nèi)部節(jié)點(diǎn)為單位計(jì)算預(yù)測(cè)結(jié)果的損失度。為了在訓(xùn)練過(guò)程中計(jì)算預(yù)測(cè)結(jié)構(gòu)y的損失度，還需要計(jì)算預(yù)測(cè)結(jié)構(gòu)y和真實(shí)結(jié)構(gòu)yi的相似度。通常計(jì)算樹(shù)結(jié)構(gòu)數(shù)據(jù)的相似度的評(píng)價(jià)指標(biāo)有準(zhǔn)確率(P)、召回率(R)與F1值，具體計(jì)算方法見(jiàn)式(7)：

其中，E(yi)為yi的邊集，E(y)為y的邊集。

考慮到F1值是統(tǒng)一了P與R的評(píng)價(jià)指標(biāo)，本文使用F1值為預(yù)測(cè)VSCLT與真實(shí)VSCLT間相似度的評(píng)價(jià)指標(biāo)。參考文獻(xiàn)[13]、[14]中的方法，令損失函數(shù)為Δ(yi,y)=(1-F1(yi,y))。當(dāng)yi與y相等時(shí)Δ(yi,y)=0，否則Δ(yi,y)＞0。

結(jié)構(gòu)化函數(shù)與損失函數(shù)構(gòu)造完成后，面向VSCLT構(gòu)建的SVM-Struct具體訓(xùn)練步驟[13]如下：

步驟1.輸入訓(xùn)練樣本S={(x,y)∈(χ×γ)n:i=1,…,n}，設(shè)置參數(shù)C,ε，其中xi為鏡頭語(yǔ)義序列，yi為對(duì)應(yīng)的VSCLT。

步驟2.確定表示鏡頭語(yǔ)義序列和VSCLT聯(lián)合特性向量的ψ(x,y)和計(jì)算預(yù)測(cè)VSCLT損失度的Δ(yi,y)，并令H(y)≡(1-〈δψi(y),w〉)Δ(yi,y)。

步驟3.初始化工作集Qi為空集。

步驟4.計(jì)算H(y)，其中權(quán)向量

步驟5.計(jì)算

步驟6.如果H(y?)≥ξi+ε則Qi←Qi∪{y?}，Q=∪iQi，在Q上繼續(xù)二次優(yōu)化更新αQ，返回步驟4。否則轉(zhuǎn)至步驟7。

步驟7.完成訓(xùn)練，輸出權(quán)向量w。

訓(xùn)練結(jié)束，得到權(quán)向量w并確定式(1)所表示的映射函數(shù)。

給定視頻V={shot1,…,shotn}及其鏡頭語(yǔ)義序列Lv={l1,…,ln}，鏡頭語(yǔ)義上下文結(jié)構(gòu)未知，為預(yù)測(cè)其語(yǔ)義標(biāo)簽樹(shù)VSCLTv，首先通過(guò)CKY算法[10]生成鏡頭語(yǔ)義序列可能的候選VSCLT集r為候選結(jié)構(gòu)的總數(shù)。然后將候選結(jié)構(gòu)集合輸入式(1)，選取具有最優(yōu)值的候選上下文標(biāo)簽樹(shù)作為預(yù)測(cè)結(jié)果。

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)設(shè)置

本文以足球比賽視頻為實(shí)驗(yàn)數(shù)據(jù)，采集了2010年南非世界杯的五場(chǎng)比賽（共400個(gè)視頻片段）的鏡頭語(yǔ)義序列，其中每個(gè)鏡頭語(yǔ)義序列平均包含25個(gè)鏡頭語(yǔ)義；進(jìn)一步采用VSCLT結(jié)構(gòu)對(duì)每個(gè)鏡頭語(yǔ)義序列進(jìn)行人工標(biāo)注，由此得到400個(gè)樣本數(shù)據(jù)。

鏡頭語(yǔ)義是分析語(yǔ)義上下文的基礎(chǔ)，根據(jù)足球視頻的領(lǐng)域特點(diǎn)[7,9-10]，實(shí)驗(yàn)中提取的鏡頭語(yǔ)義見(jiàn)表1。

圖3(a)～(f)為6個(gè)鏡頭語(yǔ)義及關(guān)鍵幀實(shí)例。

表1 鏡頭語(yǔ)義標(biāo)簽

圖3 鏡頭語(yǔ)義及關(guān)鍵幀實(shí)例

足球賽視頻中存在大量比賽規(guī)則和視頻編輯規(guī)范。如回放鏡頭出現(xiàn)在精彩事件后，球員犯規(guī)后裁判會(huì)吹哨暫停比賽等。這些規(guī)則有助于鏡頭語(yǔ)義上下文信息的獲取。根據(jù)足球視頻特有的比賽規(guī)則和視頻編輯規(guī)范，本文所使用的普通上下文標(biāo)簽見(jiàn)表2，部分上下文生成規(guī)則見(jiàn)表3。

表2 上下文標(biāo)簽

表3 部分上下文生成規(guī)則

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

實(shí)驗(yàn)分為2個(gè)層次：①就視頻語(yǔ)義標(biāo)簽樹(shù)作為鏡頭語(yǔ)義層次化表征模型的表征能力進(jìn)行了對(duì)照分析；②就SVM-Struct構(gòu)建VSCLT有效性和準(zhǔn)確性進(jìn)行了驗(yàn)證分析。

4.2.1 足球視頻語(yǔ)義上下文標(biāo)簽樹(shù)表征能力

通常，鏡頭語(yǔ)義的表征最為基本的方式按其時(shí)序順序排列；文獻(xiàn)[18]指出視頻的語(yǔ)義結(jié)構(gòu)化解析是視頻高層語(yǔ)義分析的一部分，比如可以就體育視頻進(jìn)行結(jié)構(gòu)化分析，粗粒度地組合為play/break鏡頭組，類(lèi)似地，結(jié)合不同體育節(jié)目的不同領(lǐng)域知識(shí)可以得到更具體、有意義的結(jié)構(gòu)，比如網(wǎng)球視頻可以粗粒度地組合為“分/局/盤(pán)”鏡頭組；本文方法將鏡頭語(yǔ)義序列解析為VSCLT，以此作為鏡頭語(yǔ)義層次化表征結(jié)構(gòu)。圖4給出了一個(gè)足球視頻的鏡頭語(yǔ)義序列和對(duì)應(yīng)VSCLT實(shí)例。

鏡頭語(yǔ)義表征模型的表征能力可以從時(shí)序有效性、結(jié)構(gòu)完整性、領(lǐng)域關(guān)聯(lián)性和邏輯劃分性等方面[19]進(jìn)行評(píng)估。鏡頭語(yǔ)義時(shí)序序列、鏡頭組表征和VSCLT表征模型的表征能力評(píng)價(jià)結(jié)果見(jiàn)表4。

圖4 足球視頻VSCLT實(shí)例

表4 語(yǔ)義模型表征能力評(píng)價(jià)

鏡頭語(yǔ)義之間的時(shí)序關(guān)系是最重要的上下文信息之一，常作為推理復(fù)雜視頻語(yǔ)義的主要依據(jù)[1,7-11]。時(shí)序有效性指表征模型能否有效表達(dá)鏡頭語(yǔ)義之間的時(shí)序關(guān)聯(lián)關(guān)系。鏡頭語(yǔ)義的時(shí)序序列、鏡頭組表征以及VSCLT均能有效描述鏡頭語(yǔ)義間的時(shí)序上下文，具備時(shí)序有效性。

如前所述，視頻在不同的粒度層會(huì)形成鏡頭組、場(chǎng)景、視頻等層次結(jié)構(gòu)。因此，鏡頭語(yǔ)義之間的層次關(guān)系稱(chēng)為結(jié)構(gòu)上下文。結(jié)構(gòu)完整性指表征模型能否合理描述鏡頭語(yǔ)義間的層次關(guān)系。鏡頭語(yǔ)義時(shí)序序列中層次關(guān)系是完全缺失的；鏡頭組表征中將語(yǔ)義相關(guān)的鏡頭語(yǔ)義組合為一個(gè)鏡頭組，描述了鏡頭和鏡頭組間的層次關(guān)系，但是未能進(jìn)一步描述鏡頭組與場(chǎng)景、場(chǎng)景與視頻間的層次關(guān)系，僅具有部分結(jié)構(gòu)完整性。VSCLT利用樹(shù)形結(jié)構(gòu)對(duì)視頻不同粒度層間的層次關(guān)系進(jìn)行完整地描述。圖4中前兩個(gè)鏡頭語(yǔ)義標(biāo)簽“nv”、“nvga”具有共同的父節(jié)點(diǎn)“pl”，表示這兩個(gè)鏡頭語(yǔ)義組合隸屬于“比賽進(jìn)行”鏡頭組；第一個(gè)“cu”的父節(jié)點(diǎn)是“st”，表示該“cu”鏡頭獨(dú)立成組，表征“比賽暫停”；同時(shí)，“pl”與“st”具有共同的父節(jié)點(diǎn)“scene”，表示“nv”、“nvga”與“cu”隸屬同一個(gè)場(chǎng)景。

鏡頭語(yǔ)義與鏡頭語(yǔ)義上下文具有非常強(qiáng)的領(lǐng)域性。同樣為體育視頻，足球視頻的鏡頭組可采用“play/break”組合，而網(wǎng)球視頻的鏡頭組需采用“分/局/盤(pán)”組合。類(lèi)似的領(lǐng)域知識(shí)有助于鏡頭語(yǔ)義上下文描述的準(zhǔn)確度。領(lǐng)域關(guān)聯(lián)性表示表征模型能夠合理引入領(lǐng)域知識(shí)以幫助鏡頭語(yǔ)義上下文分析。鏡頭語(yǔ)義時(shí)序序列只強(qiáng)調(diào)其時(shí)序關(guān)系排列，不具有領(lǐng)域相關(guān)性。鏡頭組表征需引入鏡頭組語(yǔ)義組合，而VSCLT則可根據(jù)領(lǐng)域知識(shí)構(gòu)建上下文標(biāo)簽和上下文生成規(guī)則，具有較強(qiáng)的領(lǐng)域關(guān)聯(lián)性。

鏡頭語(yǔ)義之間的依賴(lài)關(guān)系，可作為視頻邏輯單元?jiǎng)澐值闹饕罁?jù)。邏輯劃分性表示表征模型能否描述鏡頭語(yǔ)義之間的依賴(lài)關(guān)系并輔助邏輯單元?jiǎng)澐帧ｇR頭語(yǔ)義時(shí)序序列本身來(lái)自鏡頭劃分和語(yǔ)義提取，無(wú)法為邏輯單元?jiǎng)澐痔峁┻M(jìn)一步的輔助；鏡頭組表征將語(yǔ)義相關(guān)的鏡頭語(yǔ)義組合，其組合可以為視頻提供更高層次的邏輯劃分輔助；VSCLT對(duì)視頻結(jié)構(gòu)描述完整，其結(jié)構(gòu)化上下文信息能為視頻劃分提供豐富的信息增益。

綜合時(shí)序有效性、結(jié)構(gòu)完整性、領(lǐng)域關(guān)聯(lián)性和邏輯劃分性四方面指標(biāo)，VSCLT表征模型蘊(yùn)含了更豐富的上下文信息，具有更優(yōu)秀的上下文表達(dá)能力，有助于充分理解視頻語(yǔ)義內(nèi)容，提高視頻內(nèi)容分析的準(zhǔn)確率。

4.2.2 面向VSCLT的SVM-Struct構(gòu)建性能結(jié)果與分析

為了進(jìn)一步檢驗(yàn)，采用SVM-Struct方法構(gòu)建的VSCLT的有效性及魯棒性，本文從400個(gè)樣本數(shù)據(jù)中隨機(jī)抽取一定數(shù)量的樣本組成了10個(gè)訓(xùn)練集和5個(gè)測(cè)試集。其中訓(xùn)練集1～5樣本數(shù)為70，訓(xùn)練集6～10樣本數(shù)為100；測(cè)試集1～5對(duì)應(yīng)由訓(xùn)練集6～10選取后的剩余300個(gè)樣本而組成。

實(shí)驗(yàn)1～實(shí)驗(yàn)10分別在訓(xùn)練集1到10上訓(xùn)練得到SVM-Struct后在測(cè)試集1～測(cè)試集5上評(píng)估其預(yù)測(cè)能力（懲罰因子C設(shè)為1.0）。實(shí)驗(yàn)采用的評(píng)價(jià)準(zhǔn)則為精確率、召回率及F1值，其定義見(jiàn)式(7)。由于F1是將P與R統(tǒng)一到一個(gè)全面的度量尺度中的評(píng)價(jià)指標(biāo)，因此實(shí)驗(yàn)將F1值作為主要的評(píng)價(jià)準(zhǔn)則，在每組實(shí)驗(yàn)中計(jì)算5個(gè)測(cè)試集上的F1值的平均值和方差。實(shí)驗(yàn)結(jié)果見(jiàn)表5，其中num表示訓(xùn)練樣本數(shù)，CO表示集合中的上下文生成規(guī)則數(shù)的完備度，數(shù)值上等于該訓(xùn)練集中包含的上下文生成規(guī)則數(shù)除以數(shù)據(jù)集中總的上下文生成規(guī)則數(shù)（本文從視頻數(shù)據(jù)中提取上下文生成規(guī)則的總數(shù)為81）。

從中可以看出，當(dāng)訓(xùn)練集樣本數(shù)相同時(shí)，預(yù)測(cè)結(jié)果的平均F1值正相關(guān)于訓(xùn)練集中上下文生成規(guī)則的完備度CO，說(shuō)明CO對(duì)SVM-Struct構(gòu)建方法的平均性能影響較大，訓(xùn)練集中上下文生成規(guī)則越完備本文方法的有效性就越高。從SVM-Struct構(gòu)建方法的魯棒性來(lái)看，F(xiàn)1的方差隨著CO的降低而急劇升高，說(shuō)明CO越高SVM-Struct構(gòu)建方法的魯棒性就越強(qiáng)。其原因主要是當(dāng)測(cè)試數(shù)據(jù)中出現(xiàn)了訓(xùn)練集中未學(xué)習(xí)到的上下文生成規(guī)則，SVM-Struct將生成錯(cuò)誤節(jié)點(diǎn)較多的VSCLT，甚至不能生成VSLCT。

此外，實(shí)驗(yàn)10的訓(xùn)練樣本數(shù)比實(shí)驗(yàn)5的訓(xùn)練樣本數(shù)多43%，但F1平均值僅略高于實(shí)驗(yàn)5的F1平均值。這說(shuō)明訓(xùn)練集包含完備的上下文生成規(guī)則時(shí)，SVM-Struct繼承了傳統(tǒng)SVM小樣本學(xué)習(xí)特點(diǎn)，在訓(xùn)練樣本數(shù)較小的情況下依然能夠獲得較好的預(yù)測(cè)能力。

SVM-Struct構(gòu)建VSCLT標(biāo)的過(guò)程中需要在眾多候選VSCLT中選擇最優(yōu)結(jié)構(gòu)才能保證其性能。因此，為了驗(yàn)證SVM-Struct構(gòu)建VSCLT方法最優(yōu)選擇機(jī)制的有效性，實(shí)驗(yàn)11在訓(xùn)練集10上采用隨機(jī)選取的方式從候選VSCLT中隨機(jī)選取一個(gè)作為預(yù)測(cè)結(jié)果，作為對(duì)照。

對(duì)比實(shí)驗(yàn)5、實(shí)驗(yàn)10與實(shí)驗(yàn)11可以看出，VSCLT隨機(jī)選擇方法性能不佳，實(shí)驗(yàn)5與實(shí)驗(yàn)10的F1平均值均達(dá)到95%，顯著高于實(shí)驗(yàn)11。即，當(dāng)訓(xùn)練集上下文生成規(guī)則完備時(shí)，SVM-Struct構(gòu)建VSCLT時(shí)能夠有效地從候選VSCLT中選取最優(yōu)的VSCLT作為預(yù)測(cè)結(jié)構(gòu)。

表5 基于SVM-Struct的VSCLT構(gòu)建實(shí)驗(yàn)結(jié)果

式(3)中C是錯(cuò)誤樣本的懲罰因子，一般經(jīng)驗(yàn)值為1.0[13]。本文選擇不同的C值以考察其對(duì)于結(jié)構(gòu)預(yù)測(cè)結(jié)果的影響。實(shí)驗(yàn)結(jié)果見(jiàn)表6，其中訓(xùn)練集11樣本數(shù)為54，訓(xùn)練集12樣本數(shù)為100，兩個(gè)訓(xùn)練集上下文生成規(guī)則完備度CO均為100%，表中P/R/F1為5個(gè)測(cè)試集上的實(shí)驗(yàn)均值。實(shí)驗(yàn)結(jié)果表明，懲罰因子對(duì)于結(jié)構(gòu)預(yù)測(cè)結(jié)果影響并不顯著，其中部分原因在于結(jié)構(gòu)預(yù)測(cè)中損失度的計(jì)算并非傳統(tǒng)的0-1損失。

綜合來(lái)看，訓(xùn)練集中上下文生成規(guī)則的完備度對(duì)于文中SVM-Struct方法構(gòu)建的VSCLT的性能影響最為顯著。因此，實(shí)際應(yīng)用中，應(yīng)盡可能地選擇具有較完備上下文生成規(guī)則的樣本集作為訓(xùn)練集，這是保證結(jié)構(gòu)預(yù)測(cè)性能的重要前提。

表6 懲罰因子C的不同取值對(duì)結(jié)構(gòu)預(yù)測(cè)的影響

5 結(jié) 論

視頻內(nèi)容具有層次結(jié)構(gòu)，該特點(diǎn)意味著將視頻以鏡頭為基本單元?jiǎng)澐趾螅R頭語(yǔ)義與鏡頭語(yǔ)義之間還隱含著時(shí)間上、語(yǔ)義上、結(jié)構(gòu)上的各種上下文關(guān)聯(lián)信息。

著眼于鏡頭語(yǔ)義間上下文信息的合理表描述，本文提出了VSCLT作為鏡頭語(yǔ)義上下文層次化表征模型，從而在時(shí)序有效性、結(jié)構(gòu)完整性、領(lǐng)域關(guān)聯(lián)性、邏輯劃分性等方面保證表征模型的表達(dá)能力。

以鏡頭語(yǔ)義序列為基礎(chǔ)，合理構(gòu)建VSCLT是隨之產(chǎn)生的一個(gè)關(guān)鍵問(wèn)題。該問(wèn)題本質(zhì)上是一個(gè)序列結(jié)構(gòu)空間到樹(shù)結(jié)構(gòu)空間的映射問(wèn)題。本文提出了基于SVM-Struct的VSCLT構(gòu)建方法，該方法根據(jù)鏡頭語(yǔ)義序列和VSCLT的聯(lián)合特性構(gòu)造了語(yǔ)義上下文結(jié)構(gòu)化函數(shù)和損失函數(shù)，足球體育視頻上的實(shí)驗(yàn)結(jié)果表明，精確率、召回率及F1值等多項(xiàng)指標(biāo)表現(xiàn)良好。

[1] Ballan L,Bertini M,Bimbo A D,et al.Event detection and recognition for semantic annotation of video [J].Multimedia Tools and Applications,2011,51(1):279-302.

[2] 鐘岑岑.基于上下文的音視頻標(biāo)注研究 [D].北京: 北京交通大學(xué).2014.

[3] Yong Rui,Huang T S,Mehrotra S.Exploring video structure beyond the shots [C]//Proceedings of IEEE International Conference on Multimedia Computing and Systems.Austin,TX,USA,1998: 237-240.

[4] Dai Xiaowen,Cai Zhiping,Zhong Guiying.An algorithm of video shot detection based on partitioning image wavelet entropy [J].Acta Photonica Sinica,2008,37(7):1492-1496.

[5] Wang Zhiyong,Guan Genliang,Qiu Yu,et al.Semantic context based refinement for news video annotation [J].Multimedia Tools and Applications,2013,67(3):607-627.

[6] Zarka M,Ammar A B,Alimi A M.Fuzzy reasoning framework to improve semantic video interpretation [J].Multimedia Tools and Applications,2015,DOI 10.1007/s11042-015-2537-1.

[7] Liang Bai,Lao Songyang,Jones G J F,et al.Video semantic content analysis based on ontology [C]//International Machine Vision and Image Processing Conference.IMVIP,Maynooth,Ireland,2007,117-124.

[8] Gómez-Romero J,Patricio M A,García J,et al.Ontology-based context representation and reasoning for object tracking and scene interpretation in video [J].Expert Systems with Applications,2011,38(6):7494-7510.

[9] Huang Y P,Chiou C L,Sandnes F E.An intelligent strategy for the automatic detection of highlights in tennis video recordings [J].Expert Systems with Applications,2009,36(6): 9907-9918.

[10] Qian Xueming,Wang Huan,Liu Guizhong,et al.HMM based soccer video event detection using enhanced mid-level semantic [J].Multimedia Tools and Applications,2012,60(1): 233-255.

[11] Huang C L,Shih H C,Chao C Y.Semantic analysis of soccer video using dynamic bayesian network [J].IEEE Transactions on Multimedia,2006,8(4): 749-760.

[12] Xu Gu,Ma Yufei,Zhang Hongjiang,et al.An HMM-based framework for video semantic analysis [J].IEEE Transactions on Circuits and Systems for Video Technology,2005,15(11): 1422-1433.

[13] Tsochantaridis I,Hofmann T,Joachims T,et al.Support vector machine learning for interdependent and structured output spaces [C]//Proceedings of the Twenty-First International Conference on Machine Learning,ICML.Alberta,Banff,Canada,2004,104-111.

[14] Tsochantaridis I,Joachims T,Hofmann T,et al.Large margin methods for structured and interdependent output variables [J].Journal of Machine Learning Research,2005,6(12): 1453-1484.

[15] Nowozin S,Lampert C H.Structured learning and prediction in computer vision [J].Foundations and Trends in Computer Graphics and Vision,2011,6(3-4): 185-365.

[16] Joachims T,Finley T,Yu C N J.Cutting-plane training of structural SVMs [J].Machine Learning Journal,2009,77(1): 27-59.

[17] 肖 鋒,周 杰.訓(xùn)練結(jié)構(gòu)化支持向量機(jī)的優(yōu)化切平面法[J].清華大學(xué)學(xué)報(bào)(自然科學(xué)版),2013,53(7):1053-1063.

[18] 童曉峰,劉青山,盧漢清.體育視頻分析[J].計(jì)算機(jī)學(xué)報(bào),2008,31(7): 1242-1251.

[19] 王 煜,周立柱,邢春曉.視頻語(yǔ)義模型及評(píng)價(jià)準(zhǔn)則[J].計(jì)算機(jī)學(xué)報(bào),2007,30(3): 337-351.