視頻故事單元語義相似度算法研究

羅 娜, 魏 維

(成都信息工程學(xué)院計(jì)算機(jī)學(xué)院,四川成都610225)

0 引言

隨著計(jì)算機(jī)技術(shù)、信息數(shù)字化技術(shù)和網(wǎng)絡(luò)技術(shù)和的發(fā)展,人類進(jìn)行信息存儲(chǔ)傳播已從傳統(tǒng)單一的文字描述發(fā)展到數(shù)字視頻、音頻、文字圖片等在內(nèi)的多種方式,其中數(shù)字視頻所占據(jù)的比例越來越大。視頻是文本、圖像、語音等媒體綜合而成的數(shù)據(jù)流,內(nèi)容豐富,能記錄、保留空間和時(shí)間上的各種信息和細(xì)節(jié),成為最重要的信息載體。如何從海量的視頻數(shù)據(jù)中找出需要的視頻,是一件非常困難的事情。因此,對(duì)視頻數(shù)據(jù)組織、管理、分類、檢索等多個(gè)領(lǐng)域,視頻相似度的有效計(jì)算都是進(jìn)行信息處理的關(guān)鍵。

語義(Semantics)提出于20世紀(jì)70年代,主要應(yīng)用在知識(shí)工程、自然語言處理和人工智能等領(lǐng)域。對(duì)視頻數(shù)據(jù)進(jìn)行分析時(shí),借助人類更容易理解的語義能夠使視頻處理相關(guān)領(lǐng)域的成果能夠更好的服務(wù)于人類生活。由于視頻數(shù)據(jù)自身的復(fù)雜性和多樣性,視頻數(shù)據(jù)分析領(lǐng)域的研究者根據(jù)對(duì)視頻“語義”理解的不同,對(duì)視頻語義的獲取經(jīng)歷了手工標(biāo)注[1],底層特征描述[2-3],多模式融合和多層次分析[4-5]等階段。目前對(duì)視頻語義較好的定義是,用人可以描述、理解和表達(dá)的方式描述視頻所包含的對(duì)象(語義物體),對(duì)象的事件,以及對(duì)象間關(guān)系等視頻信息[3,6]。

圖1 視頻語義相似度計(jì)算流程

相似性是一個(gè)復(fù)雜的概念,在語義學(xué)、哲學(xué)和信息理論中被廣泛討論。文中的視頻相似度是指通過特定的算法得出一個(gè)從人類思維角度考慮的評(píng)價(jià)兩段視頻是否相似的評(píng)價(jià)標(biāo)準(zhǔn)。在進(jìn)行視頻相似度計(jì)算前,首先要對(duì)視頻進(jìn)行預(yù)處理,提取出可以表征視頻語義的有關(guān)信息,并對(duì)其進(jìn)行表征。再根據(jù)算法計(jì)算兩段視頻故事單元的語義相似度,最終得到一個(gè)[0,1]的實(shí)數(shù)值,可以很好的表示兩個(gè)視頻故事單元間的語義相似度。圖1所示即為視頻語義相似度計(jì)算的整個(gè)流程。

1 語義表征

1.1 視頻預(yù)處理

在整個(gè)視頻相似度計(jì)算流程中,首先要對(duì)視頻進(jìn)行數(shù)據(jù)結(jié)構(gòu)化和語義特征提取兩個(gè)步驟,已提取出視頻故事單元中的語義信息[7]。

視頻是一組非結(jié)構(gòu)化的數(shù)據(jù)流,對(duì)視頻數(shù)據(jù)結(jié)構(gòu)化是視頻語義分析和表征的基本工作和必要步驟。首先將視頻分割為幀、鏡頭、場景、故事單元等不同層次的邏輯單元,以便在各個(gè)層次上提取出語義信息并對(duì)其進(jìn)行分析。幀是一幅靜態(tài)圖像,是最小的視頻單元。鏡頭是一臺(tái)攝像機(jī)從開機(jī)到關(guān)機(jī)連續(xù)拍攝的幀序列,描繪一個(gè)事件或一個(gè)場面的一部分,不具有或具有較弱的語義信息,強(qiáng)調(diào)構(gòu)成幀的視覺內(nèi)容相似性,通常用一個(gè)或多個(gè)關(guān)鍵幀(代表幀)來表現(xiàn)鏡頭。場景是語義相關(guān)的連續(xù)鏡頭,可以是相同對(duì)象的不同角度、不同技法拍攝,也可以是具有相同主題和事件的鏡頭組合,強(qiáng)調(diào)語義的相關(guān)性。故事單元包含一個(gè)完整的事件或故事,作為最高層的視頻內(nèi)容結(jié)構(gòu),它包括視頻的組成關(guān)系以及對(duì)視頻的摘要、語義和一般性描述等。及時(shí)針對(duì)視頻的故事單元層次進(jìn)行語義表征和相似度計(jì)算,因此文中多提到的視頻均指視頻的故事單元。

由于視頻本身內(nèi)容的復(fù)雜性和多樣性,在現(xiàn)有的視頻語義提取技術(shù)條件下不容易自動(dòng)獲取完整的視頻文本描述。早期人們采用的人工標(biāo)注的方式雖然能夠用人可以理解的方式描述視頻中所包含的信息,但其工作量巨大,且不可避免的帶有主觀偏差,所表達(dá)的語義信息往往是不準(zhǔn)確或不完整的。視頻的顏色、紋理、形狀等低層視覺特征,視頻的部分聲音、文字其他底層特征可由計(jì)算機(jī)自動(dòng)提取,這種表征方法雖然大大降低了工作量,但是所表達(dá)的信息與人類的需求存在著巨大差異。隨著視頻語義相關(guān)技術(shù)研究的深入,該領(lǐng)域的研究者們提出了采用多模式融合和多層次分析技術(shù)進(jìn)行視頻語義提取及表征。所謂多模式融合和多層次分析技術(shù)就是對(duì)機(jī)器自動(dòng)提取的多模視頻底層特征(包括視覺、聲音[8]、文字[9]等底層特征),采用概率統(tǒng)計(jì)方法、統(tǒng)計(jì)學(xué)習(xí)方法、基于規(guī)則推理的方法、結(jié)合特定領(lǐng)域特點(diǎn)等方法[10],將視頻的底層特征傳遞、映射和融合,轉(zhuǎn)化為人類可以理解的,對(duì)原視頻高度概括的高層語義信息的技術(shù)。雖然這些方法都取得了一定的成績,但是它們在視頻語義信息提取的正確率和可提取的種類上仍然有一定的局限性,無法實(shí)際應(yīng)用中廣泛使用。因此,在采用多模式融合和多層次分析技術(shù)來提取視頻語義信息以降低手工工作量的同時(shí),還需要借助“人工標(biāo)注”進(jìn)行補(bǔ)充以降低多模式融合和多層次分析技術(shù)的局限性,從而使本研究能夠適用于更廣泛的視頻應(yīng)用領(lǐng)域中。

1.2 視頻語義表征

完善的視頻語義表征模型是對(duì)視頻進(jìn)行語義相似度計(jì)算的基礎(chǔ),好的語義表征模型可以將語義相似度計(jì)算變得更為簡單、有效;差的語義模型不僅會(huì)增加語義相似度計(jì)算的難度,更會(huì)影響最終計(jì)算結(jié)果的準(zhǔn)確性、適用性。

在人類的思維模式中,一個(gè)完整的故事單元一般包含以下四個(gè)特定元素:事件發(fā)生的時(shí)間、地點(diǎn)、所涉及的人物(或?qū)ο?和事件,即4WH[11]。因此在人類理解的基礎(chǔ)上采用一種基于時(shí)間、地點(diǎn)、語義對(duì)象和語義行為的視頻語義表征方法,可用一個(gè)四元組表示為:

VideoSematics={Time,Place,Object,Action}

Time代表視頻故事發(fā)生的時(shí)間,Place代表視頻故事發(fā)生的地點(diǎn),Object代表視頻中包含的語義物體,Action代表視頻中包含的語義行為。

對(duì)上述四元組進(jìn)一步描述如下:

Time={DurationTime},故事發(fā)生的時(shí)間,一般故事單元發(fā)生的時(shí)間在一個(gè)較為接近的時(shí)間范圍內(nèi),這里用時(shí)間區(qū)間集表示。

Place={Place1,Place2,…,Placen},故事發(fā)生的地點(diǎn),整個(gè)故事可能發(fā)生在多個(gè)地點(diǎn),一般情況下一個(gè)故事單元發(fā)生在可以認(rèn)為是一個(gè)地點(diǎn)的一定范圍內(nèi)。

Object={Obj1,Obj2,…,Objn},一個(gè)故事單元中常常包含若干個(gè)語義對(duì)象,根據(jù)視頻類型的不同,這些對(duì)象可以是單個(gè)具體的人或物,也可以是人或物的集合,如軍隊(duì)。

Action={Action1,Action2,…,Actionn},一個(gè)故事單元中包含多個(gè)語義行為,這些語義行為構(gòu)成故事單元的事件信息。

在上述語義表征,Time,Place,Object,Action中的元素均為1.1節(jié)中通過多模式融合和多層次分析技術(shù)或人工標(biāo)注的提取出的語義關(guān)鍵詞,采用該視頻表征模型作為后續(xù)視頻語義相似度計(jì)算的輸入。

2 視頻語義相似度計(jì)算算法

2.1 相似度計(jì)算度量方法

相似度計(jì)算用于衡量對(duì)象之間的相似程度,相似度值越大,對(duì)象越相似,反之越小。相似度的計(jì)算方法有很多種,常用的相似度計(jì)算方法有歐氏距離,余弦相似度,皮爾森相關(guān)系數(shù),Jaccard相似系數(shù),調(diào)整余弦相似度等[12]。其中Jaccard相似系數(shù)和歐氏距離公式分別為:

相似度計(jì)算將用到適當(dāng)改進(jìn)后的Jaccard系數(shù)和歐氏距離公式,計(jì)算的最終結(jié)果是一個(gè)[0,1]的數(shù)值。在視頻語義相似度計(jì)算時(shí),這個(gè)數(shù)值并不代表明確的意義,只是數(shù)值越大,其所聯(lián)系的兩段視頻在語義上更相似。

2.2 詞語間的相似度計(jì)算

人類語言形成較早且在不斷的變化,因而有其復(fù)雜性,在視頻語義表征中可能出現(xiàn)同義不同形的情況,應(yīng)建立語義詞典避免由此產(chǎn)生的誤差。自然語言理解研究領(lǐng)域中對(duì)語義的研究較早,相關(guān)領(lǐng)域的研究者已建立起較為成熟的基于本體概念的語義詞典,如Wordnet[13]、Hownet[14]、同義詞詞林[15]等,并在此基礎(chǔ)上形成較為成熟的詞語相似度計(jì)算方法。視頻相似度計(jì)算主要針對(duì)視頻中的語義,其視頻的表征模型使用了自然語言理解領(lǐng)域中的本體概念,而又有其不同于自然語言理解的特點(diǎn),應(yīng)借用或建立合適的語義詞典建立符合視頻語義表征模型特點(diǎn)的相似度計(jì)算方法。

(1)Object,Action語義詞典

對(duì)于語義表征模型中的Object,Action集合中的詞語主要來自于自然語言理解領(lǐng)域中本體概念,因此可選取該領(lǐng)域中較為成熟的語義詞典來衡量Object,Action集合中詞語間的相似度。與Wordnet和Hownet相比,同義詞詞林有可以人工增加或編輯,計(jì)算簡單、高效等好處,因此采用《同義詞詞林》作為語義詞典來計(jì)算 Object,Action集合中詞語間的相似度。

設(shè)有兩個(gè)詞 w1和 w2,分別為:

w1={x1,x2,x3,x4,x5,x6,x7,x8}

w2={y1,y2,y3,y4,y5,y6,y7,y8}

其中 xi,yi分別為兩個(gè)詞在同義詞詞林中的編碼。

則w1和 w2的相似度計(jì)算公式表示為:

(2)地點(diǎn)語義詞典

由于空間地點(diǎn)語義并無收錄詞條,且地理位置間也存在層次包含關(guān)系,并不是簡單的相同或不相同可以衡量的。應(yīng)引入地理知識(shí)來建立地點(diǎn)語義詞典,并在此語義詞典基礎(chǔ)上計(jì)算地點(diǎn)的語義相似度。

語義詞典共分5層:第一層表示各大洲各大洋;第二層為各國家、地區(qū);第三層為各省、直轄市和各大河流、湖泊、山脈等;第四層為個(gè)城市、山峰等;第五層為各縣等。樹種的一個(gè)節(jié)點(diǎn)代表一個(gè)地點(diǎn),如果比較兩地點(diǎn)的相似度,只需計(jì)算它們的共同路徑與總路徑的長度比。

2.3 時(shí)間相似性度量

視頻故事單元發(fā)生的時(shí)間通常是隱含的,僅僅通過故事發(fā)生的日期是不能判定兩段視頻故事單元語義上是否相似。采用類似文獻(xiàn)[16]中的方法獲取視頻故事單元的時(shí)間區(qū)間序列集。文獻(xiàn)[17]對(duì)時(shí)間區(qū)間進(jìn)行了各種研究,借鑒它們的方法,采用兩個(gè)時(shí)間區(qū)間集的Jaccard相似系數(shù)作為視頻故事單元的時(shí)間相似度。則兩段視頻故事單元的時(shí)間相似度可表示為:

2.4 視頻語義相似度計(jì)算算法

視頻相似度計(jì)算可應(yīng)用于多個(gè)領(lǐng)域。在視頻分類中,相同類別的視頻相似度高,不同類別的視頻度低。在視頻檢索中,對(duì)檢索的結(jié)果按照與樣本視頻的相似度按照從高到低排序,有助于用戶快速找到需要的視頻。

視頻相似度計(jì)算以語義表征模型為輸入,對(duì)四元組的各分量分別進(jìn)行相似度計(jì)算,整個(gè)算法描述如下:

輸入:視頻故事單元A和視頻故事單元B

輸出:一個(gè)[0,1]的數(shù)值。

第1步:分別對(duì)視頻故事單元A和視頻故事單元B進(jìn)行視頻預(yù)處理,生成各自對(duì)應(yīng)的語義表征模型。

第2步:讀取視頻故事單元A和視頻故事單元B的 Time信息并進(jìn)行比較,根據(jù)公式(1)計(jì)算視頻故事單元A和視頻故事單元B的時(shí)間語義相似度,記為Sim(Time)。

第3步:讀取視頻故事單元A和視頻故事單元B的Place信息,根據(jù)地點(diǎn)語義詞典計(jì)算視頻故事單元A和視頻故事單元B的地點(diǎn)語義相似度,記為Sim(Place)。

第4步:讀取視頻故事單元A和視頻故事單元B的Object信息,并計(jì)算計(jì)算視頻故事單元A和視頻故事單元B的Object元素的數(shù)目,記為

第5步:分別對(duì)視頻故事單元A和視頻故事單元B中Object元素進(jìn)行遍歷,兩兩進(jìn)行比較,使用公式

第6步:讀取視頻故事單元A和視頻故事單元B的 Action信息,并計(jì)算計(jì)算視頻故事單元A和視頻故事單元B的Action元素的數(shù)目,記為

第7步:分別對(duì)視頻故事單元A和視頻故事單元B中Action元素進(jìn)行遍歷,兩兩進(jìn)行比較,計(jì)算視頻故事單元A和視頻故事單元B的 Action相似度,使用計(jì)算公式

第8步:視頻故事單元的總相似度用歐氏距離綜合 Time,Place,Object,Act各分量的相似度計(jì)算得出,并通過除數(shù)4使相似度范圍保持在[0,1],即

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

實(shí)驗(yàn)數(shù)據(jù)分別選取籃球、新聞、電影、綜藝等4類視頻故事單元作為測試樣本,這些樣本數(shù)據(jù)主要通過互聯(lián)網(wǎng)下載并手工分割為視頻故事單元,得到各類視頻樣本數(shù)目如表1所示。

表1 實(shí)驗(yàn)樣本數(shù)據(jù)

為了驗(yàn)證文中視頻語義表征模型及相似度計(jì)算算法的效果,采用語義表征模型對(duì)每個(gè)實(shí)驗(yàn)樣本進(jìn)行語義表征。由于同一類別的視頻鏡頭在高層語義結(jié)構(gòu)具有較大的相似性,實(shí)驗(yàn)采用語義相似度算法對(duì)同一類型的視頻兩兩進(jìn)行相似度計(jì)算。且目前視頻語義相似度計(jì)算研究領(lǐng)域尚無評(píng)判標(biāo)準(zhǔn),故以“人的視覺判斷”為標(biāo)準(zhǔn)依據(jù),對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比和測試,得到圖2所示的結(jié)果。

從圖中實(shí)驗(yàn)數(shù)據(jù)可知,人與人之間的判斷標(biāo)準(zhǔn)基本一致,實(shí)驗(yàn)的整體的測試結(jié)果與“人的視覺判斷”比較相符。但不同類型的視頻故事單元對(duì)文中算法的適應(yīng)性具有差異性,如“籃球類”和“電影類”的視頻的語義相似度判斷較為準(zhǔn)確,主要原因是這類視頻故事邏輯性強(qiáng),語義表征模型較適應(yīng)這類視頻故事單元,而對(duì)“綜藝類”視頻故事單元的語義表征不夠完善,因此對(duì)應(yīng)的視頻相似度計(jì)算準(zhǔn)確度要差一些。因此提出的視頻相似度算法對(duì)特定種類的視頻數(shù)據(jù)的組織、管理、分類、檢索等研究和應(yīng)用具有參考性。

圖2 實(shí)驗(yàn)結(jié)果

4 結(jié)束語

建立以時(shí)間、地點(diǎn)、語義對(duì)象和語義行為的四元組表征模型,用改進(jìn)后Jaccard系數(shù)和歐氏距離公式加權(quán)計(jì)算得到兩視頻故事歸一化的語義相似度。該方法實(shí)現(xiàn)了兩視頻故事單元間定量語義相似性計(jì)算,與現(xiàn)有的相關(guān)研究方法相比,文中建立的四元組表征模型和計(jì)算算法全面綜合考慮了故事場景具有豐富時(shí)間空間信息的特性,更適合場景間語義相似性度量計(jì)算,是基于語義視頻組織、管理、傳播和應(yīng)用的關(guān)鍵技術(shù),也為進(jìn)一步提取視頻高層語義奠定了基礎(chǔ)。

該算法還存在的不足是在不同應(yīng)用領(lǐng)域中對(duì)不同語義分量的需求可能不同,這是后續(xù)工作中需要加以完善并實(shí)現(xiàn)的地方。

[1] 孔英會(huì),劉淑榮,張少明,等.基于語義的視頻檢索關(guān)鍵技術(shù)綜述[J].電子科技,2012,25(8):150-153.

[2] 張永華,馮文輝,郭成,等.基于內(nèi)容的檢索中視頻相似度度量方法研究[J].電腦知識(shí)與技術(shù),2009,5(9):2188-2189.

[3] 胡振興.基于內(nèi)容的視頻檢索技術(shù)研究[D].長沙:中南大學(xué),2009.

[4] 呂麗.多層次語義視頻對(duì)象描述模型及提取技術(shù)研究[D].上海:上海交通大學(xué),2007.

[5] 魏維,鄒書蓉,劉鳳玉.多層次視頻語義概念分析與理解[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2008,20(1),85-92.

[6] 周生,胡曉峰.視頻語義相似度網(wǎng)絡(luò)研究[J].計(jì)算機(jī)應(yīng)用,2010,30(7):1963-1966.

[7] 余衛(wèi)宇,謝勝利.語義視頻檢索的現(xiàn)狀和研究進(jìn)展[J].計(jì)算機(jī)應(yīng)用研究,2005,(5):1-7.

[8] Wei W,Liu W Q,Huang M.Quantitative similarity computing for audio effect semantic in video content analy-sis[C].Proc of 2th International Conference on Computer Engineering and Technology(ICCET),2010:123-127.

[9] Jae-Chang Shim,Chitra Dorai,Ruud Bolle.Automatic Text Extraction from Video for Content-Based Annotation and Retrieval[C].Proc of 14th International conference on Pattern Recognition,1998:618-620.

[10] 李德山.基于語義的視頻檢索[D].青島:中國石油大學(xué),2009.

[11] 徐新文.基于內(nèi)容的新聞視頻挖掘方法研究[D].長沙:國防科技大學(xué),2009.

[12] Mihalcea R F,Mihalcea S I.Word sematic for information retrieval:moving one step closer to the semantic web[C].Proc of 13th International conference on Tools with Artificial Intelligence,2001:280-287.

[13] Resnik,P.Using information content to evaluate semantic similarity in a taxonomy[C].Proc of 14th International Joint conference on Artificial Intelligence,1995:448-453.

[14] 葛斌,李芳芳,郭思路,等.基于知網(wǎng)的詞匯語義相似度計(jì)算方法研究[J].計(jì)算機(jī)應(yīng)用研究,2010,27(9):3329-3333.

[15] 程傳鵬.網(wǎng)絡(luò)評(píng)價(jià)傾向性研究[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(25):156-159.

[16] F,S,C.From temporal expressions to temporal information:Semantic tagging of news message[C].Proceedings of the workshop on Temporal and spatioal information processing(ACL),Toulouse,France.2001:65-72.

[17] K,K.On the reliability of unitizing continous data[C].Sociological Methodology,1995:47-76.