視頻節(jié)目層次化搜索和推薦方法的研究

張 赟，沈兵虎，王李冬

(1.浙江傳媒學院 浙江廣播電視技術研究所，杭州 浙江 310018；2.杭州師范大學錢江學院，杭州 浙江 310018)

0 引 言

隨著移動互聯(lián)網(wǎng)和智能手機的普及，多媒體技術、網(wǎng)絡通信、視音頻處理等相關技術的快速發(fā)展，視頻數(shù)據(jù)正在以驚人的速度增長。例如，YouTube每分鐘約有超過100小時的新視頻上傳，其視頻播放次數(shù)已達到每個月50億次以上，而以愛奇藝、優(yōu)酷、騰訊為代表的中國在線視頻市場近年來保持快速增長，用戶數(shù)量不斷激增，它們在節(jié)目資源、內(nèi)容推薦、互動交流等方面具有優(yōu)勢，但是在海量視頻資源的組織和展示方面存在不足。目前，大多數(shù)在線視頻平臺在節(jié)目搜索和推薦過程中主要采用線性結構展示節(jié)目，該方式簡單直觀，但是難以滿足大數(shù)據(jù)時代下用戶對視頻信息的立體全方位需求。面對海量的視頻內(nèi)容和用戶的個性化需求，如何實現(xiàn)視頻節(jié)目的高效組織和展示，以擴大視頻的傳播范圍，提升用戶的滿意度是目前需要解決的主要問題。為了提升用戶的視頻觀看體驗，文中圍繞以下問題展開研究：視頻特征提取與表示、視頻的層次化搜索和層次化推薦。

1 總體設計

圖1給出了系統(tǒng)流程。系統(tǒng)以人工上載和異構系統(tǒng)導入的視頻編目數(shù)據(jù)為輸入，通過用戶行為分析和節(jié)目內(nèi)容聚合，實現(xiàn)視頻的層次化搜索和推薦。系統(tǒng)首先上載新節(jié)目，導入異構系統(tǒng)的媒資編目數(shù)據(jù)，并進一步提取和表示節(jié)目特征；然后，對新媒體媒資庫中的視頻內(nèi)容進行聚合分析及用戶喜好和行為分析；最后，根據(jù)以上分析結果，實現(xiàn)視頻的個性化搜索和推薦，并以層次化方式進行展示。

2 層次化視頻節(jié)目搜索和推薦

2.1 視頻節(jié)目的特征提取與表示

文中主要研究基于文字和圖像特征的節(jié)目特征提取與表示。如圖2所示，視頻節(jié)目的來源主要包括本地節(jié)目人工上載和異構編目數(shù)據(jù)的自動導入。對于本地節(jié)目，需要用戶手動添加標題、關鍵幀、標簽、內(nèi)容描述、節(jié)目看點等信息。為了將電視臺媒資數(shù)據(jù)高效地應用到新媒體平臺，提出了異構編目數(shù)據(jù)的自動導入，此時系統(tǒng)能夠從編目信息中自動提取標題、關鍵幀、標簽、內(nèi)容描述等信息，并且能夠自動將節(jié)目片段轉換為節(jié)目看點。為了實現(xiàn)節(jié)目中重要人物、事件的關聯(lián)性，建立人物事件庫。基于以上編目數(shù)據(jù)和特征庫，進一步在節(jié)目中添加人物、事件，自動提取出人物視頻節(jié)目的縮略圖，并提取節(jié)目中的用戶評論、點贊等UGC信息。下面對以上流程的關鍵步驟進行說明。

圖2 節(jié)目特征提取與表示流程

(1)自動提取節(jié)目看點。

從異構媒資庫中導入的編目數(shù)據(jù)包含節(jié)目層和片段層。如圖3所示，視頻節(jié)目由4個獨立的片段組成，片段間的部分是節(jié)目轉場、廣告之類的無效內(nèi)容。由于經(jīng)過編目的片段很好地表示了節(jié)目中的主要內(nèi)容，因此，直接將每個片段的起始點作為節(jié)目看點(如進度條上的小白點所示)，每個片段的標題作為片段的內(nèi)容描述。

圖3 節(jié)目看點自動提取示意圖

(2)人物和視頻節(jié)目的縮略圖自動提取。

文中研究的層次化視頻節(jié)目搜索和推薦，需要采用基于圖的結構來表示節(jié)目間的關聯(lián)性，其中圖的節(jié)點需要相應的縮略圖來表示其內(nèi)容(視頻節(jié)目或人物)。目前圓形頭像是較為流行的縮略圖形式，但是如果逐個進行人工處理，不僅費時費力，而且效果不佳。文中針對人物照片和視頻關鍵幀進行了縮略圖的自動提取。

對于人物，首先采用Adaboost算法[1-3]，通過多個級聯(lián)的Haar特征弱分類器構建出強分類器，實現(xiàn)人臉的自動準確定位。定位出人臉區(qū)域后，進一步從人臉中心向外擴展一倍距離，實現(xiàn)頭像區(qū)域的準確切割，如圖4所示，文中方法能夠較好地實現(xiàn)人物縮略圖的準確提取。

對于視頻節(jié)目圖像，首先通過重要性區(qū)域檢測，得到圖像中的重要區(qū)域，然后以該區(qū)域的重心為圓心，切割出覆蓋大多數(shù)重要性區(qū)域的圓形縮略圖。為了達到比較好的效果，采用基于區(qū)域對比度的視覺顯著性區(qū)域檢測算法[4-5]，同時考慮全局對比度和空間相關性。如圖4所示，文中提取出的縮略圖，能夠很好地表示節(jié)目的主要信息，通過自動批處理大大減輕了人工勞動。

圖4 人物和視頻節(jié)目的縮略圖自動提取示意圖

2.2 視頻節(jié)目的層次化搜索

首先對搜索關鍵詞進行內(nèi)容分析，如果屬于人物，則搜索與其相關的視頻節(jié)目和人物，如果屬于節(jié)目名稱，則首先找到與該關鍵詞匹配度最高的中心節(jié)目，然后進一步深度搜索相關的視頻節(jié)目和人物，并繪制層次化圖結構表示搜索結果。層次化視頻節(jié)目搜索算法細節(jié)如下所示，該算法的關鍵在于人物和視頻節(jié)目的相似度匹配。

算法：層次化視頻節(jié)目搜索算法。

輸入：搜索關鍵詞K。

輸出：節(jié)目搜索結果多叉樹T。

根據(jù)關鍵詞K，確定關鍵詞類型(人物、節(jié)目名稱)

IF關鍵詞K屬于人物

將人物作為根節(jié)點R加入T

搜索與該人物相關的視頻節(jié)目S

搜索與該人物相關的其他人物P

將相關度較高的視頻節(jié)目和人物節(jié)點作為R的子節(jié)點加入T

ELSE

搜索與K最相關的中心視頻節(jié)目，并作為根節(jié)點R加入T

搜索與中心節(jié)目相關的人物P和節(jié)目S

將相關度較高的視頻節(jié)目和人物節(jié)點作為R的子節(jié)點加入T

從樹的第二層節(jié)點開始，按照層次遍歷順序對每個節(jié)點N(i)都重復以下操作

搜索與N(i)相關的其他人物

搜索與N(i)相關的視頻節(jié)目

將相關度較高的視頻節(jié)目和人物節(jié)點作為N(i)的子節(jié)點

下面詳細說明相似度匹配算法。

(1)給定人物P，搜索與之相關的視頻節(jié)目T。

從媒資數(shù)據(jù)庫中直接搜索包含該人物的視頻節(jié)目，并計算人物與視頻節(jié)目之間的相關度Sim(P,T)。

Sim(P,T)=

(1)

(2)給定人物P，搜索與相關的人物P'。

首先從媒資數(shù)據(jù)庫中搜索出與人物P相關的所有視頻節(jié)目，然后從這些節(jié)目中找出其他人物，并計算出人物之間的相關度Sim(P,P')。將人物P'出現(xiàn)在不同地方的次數(shù)進行加權可以得到P和P'的相關性。

(2)

其中，n1為出現(xiàn)在標題的次數(shù)；n2為出現(xiàn)在主要人物字段的次數(shù)；n3為出現(xiàn)在其他位置的次數(shù)。

(3)給定視頻節(jié)目T，搜索與之相關的其他視頻節(jié)目T'。

節(jié)目間的相似性度量比較復雜，需要綜合考慮類型、標題、標簽、人物等信息，通過向量余弦相似度來度量其相似性，如式3所示。由于標題和內(nèi)容描述是整段文字，無法直接比較，文中利用TF-IDF算法[6-7]對標題、內(nèi)容描述進行分詞，然后提取出各自的關鍵詞，生成各自的詞頻向量。然后，對標題、標簽、人物分別計算其余弦向量值，并加權平均，從而得到節(jié)目之間的相似性。

(3)

文中首先對多個節(jié)點相似性度量進行歸一化和加權，然后根據(jù)多叉樹每個層次的子節(jié)點與父節(jié)點的相似性進行節(jié)點排序，將排名靠前的節(jié)點作為子節(jié)點，其余節(jié)點將優(yōu)先出現(xiàn)在下一層次。為了得到更好的可視化效果，每個層次顯示的節(jié)點數(shù)需要控制在一定范圍。通過層次化搜索，能夠得到表示搜索結果的多叉樹，實現(xiàn)節(jié)目多叉樹的展示，如圖5所示。其中虛線標出的白色圓圈表示中心根節(jié)點，灰色圓圈表示視頻節(jié)目節(jié)點，黑色圓圈表示人物節(jié)點。由于多叉樹的形狀不規(guī)則，節(jié)點數(shù)量多，需要合理布局才能呈現(xiàn)較好的可視化效果。根據(jù)節(jié)點包含的子節(jié)點的個數(shù)來確定邊的長度，并且通過模擬節(jié)點間的彈性碰撞檢測避免節(jié)點的重合，并產(chǎn)生合理的空間布局。文中采用集成于Qt的OpenGL圖形庫進行多叉樹的繪制[8]，將節(jié)點作為圖形元素，用戶通過點擊查看節(jié)點所代表的人物或視頻信息，可以拖動節(jié)點以改變多叉樹的空間布局。

圖5 層次化視頻節(jié)目展示效果

2.3 視頻節(jié)目的層次化推薦

用戶登錄后，首先進行用戶喜好登記和用戶行為分析，然后根據(jù)以上分析向用戶推薦其可能喜歡的視頻節(jié)目和人物，再進一步地針對推薦的節(jié)目深度搜索相關視頻，最后繪制出層次圖結構呈現(xiàn)推薦結果。

首先采用基于傳統(tǒng)的推薦算法[9-11]得到用戶感興趣的視頻節(jié)目和人物，然后對推薦結果進行聚類，此時的聚類中心就是第一層次推薦結果，第二層次推薦結果即各聚類對應的結果，之后進一步深度搜索產(chǎn)生更多層次的推薦結果。下面重點介紹推薦算法和推薦結果的聚類。

綜合考慮用戶喜好和用戶行為數(shù)據(jù)進行協(xié)同過濾推薦，在用戶相似性計算中考慮用戶喜好的相似性。相似性計算考慮以下兩個方面：(1)兩個用戶喜好的相似性，包括喜歡節(jié)目類型和用戶標簽的相似性；(2)兩個用戶觀看節(jié)目中相同節(jié)目數(shù)量，即兩個用戶觀看的相同節(jié)目越多其相似度越高。

文中通過計算向量余弦相似度來量度用戶相似性，如式4所示，用戶相似度是兩個向量余弦的加權平均。其中第一項表示用戶喜好相似性的余弦值，第二項表示用戶觀看節(jié)目數(shù)量的余弦值。為了更好地表示用戶行為，不僅計算共同觀看的節(jié)目數(shù)量，還要比較其觀看時間，因為用戶短暫瀏覽的節(jié)目大多是不感興趣的。若用戶a或b對某節(jié)目的觀看時長很短，則不認為該節(jié)目是共同觀看過的節(jié)目；若用戶a和b觀看的時長都較長，則該節(jié)目是兩者共同觀看過的節(jié)目，需要增加其權重。對于用戶喜歡的人物，主要從用戶喜好的標簽、節(jié)目評論、觀看記錄來分析，或某人物在用戶行為和喜好中重復出現(xiàn)，則說明用戶對與該人物和與之相關的視頻節(jié)目感興趣。

(4)

得到用戶的推薦結果后，采用AP方法[12]進一步對推薦節(jié)目進行聚類。該方法無需預先指定聚類中心，魯棒性強且準確性高，在數(shù)據(jù)量不大時效率較高(推薦節(jié)目的數(shù)量一般小于50)。聚類算法的輸入是所有數(shù)據(jù)樣本兩兩比較的相似性矩陣，其關鍵是定義節(jié)目間的相似性S(i,j)。文中根據(jù)節(jié)目標簽、標題、類型、內(nèi)容描述、人物等信息定義節(jié)目間的相似性，通過向量余弦相似度表示。

3 實驗結果及分析

文中開發(fā)了軟件系統(tǒng)，能夠實現(xiàn)視頻節(jié)目的特征提取與表示、層次化的視頻節(jié)目搜索和推薦。在視頻節(jié)目上載過程中，用戶可以添加標題、分類、標簽、人物、看點等主要信息，添加好的看點會在進度條上生成相應的“小白點”，并從系統(tǒng)人物庫中添加重要人物和事件。對于異構的編目數(shù)據(jù)，用戶通過簡單操作就可以自動將異構系統(tǒng)的數(shù)據(jù)遷移到新系統(tǒng)，并自動生成節(jié)目看點。

在層次化搜索過程中，系統(tǒng)能夠通過多叉樹結構直觀高效地展示出搜索結果，為了顯示效果，初始給出兩層搜索結果，用戶可以通過點擊交互進一步深入搜索。多叉樹中每個節(jié)點都是人物或視頻節(jié)目的縮略圖，用戶通過鼠標點擊可以方便地了解視頻節(jié)目或人物的詳情。

在層次化推薦過程中，用戶登錄后，系統(tǒng)根據(jù)當前用戶的個人喜好、觀看記錄等信息，給出層次化的推薦結果，且推薦結果具有一定的代表性和準確性，能夠更好地滿足用戶的個性化視頻觀看需求。

4 結束語

提出了視頻節(jié)目的層次化搜索和推薦方法，能夠實現(xiàn)視頻節(jié)目的特征提取與表示、視頻節(jié)目的層次化搜索和推薦。開發(fā)的系統(tǒng)在浙江廣電集團和桐鄉(xiāng)市電視臺的新媒體部門進行了試運行，結果表明系統(tǒng)操作簡單、運行高效，能夠實現(xiàn)海量視頻節(jié)目的高效搜索和推薦，層次化的交互方式也得到了大多數(shù)用戶的好評。

今后，將進一步利用大數(shù)據(jù)分析[13]、深度學習[14-15]等方法實現(xiàn)更好的視頻節(jié)目的搜索和推薦，為用戶提供更加高質(zhì)量的個性化服務。在交互展示方面，將繼續(xù)研究更加友好的節(jié)目交互和展示方式，從而不斷提升用戶的節(jié)目觀看體驗。