基于排序?qū)W習(xí)的視頻摘要

王鈃潤，聶秀山，楊帆，呂鵬，尹義龍

（1. 山東大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，山東 濟南 250101; 2. 山東財經(jīng)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，山東 濟南250014; 3. 山東大學(xué) 軟件學(xué)院， 山東 濟南 250101）

隨著手機、攝像機等錄像設(shè)備的普及，視頻拍攝越來越簡單方便。一項調(diào)查顯示，在YouTube視頻網(wǎng)站，每天視頻的上傳時長大約是14萬小時[1]，視頻數(shù)據(jù)的爆炸式增長帶來了一些不可避免的問題。對于用戶來說，瀏覽14萬小時的視頻需要不間斷地觀看大約16年時間，同時，存儲如此龐大的視頻數(shù)據(jù)也給網(wǎng)站帶來巨大的壓力,除此之外，視頻檢索也要花費更多時間。由于視頻數(shù)據(jù)快速增長帶來的一系列問題，視頻處理的相關(guān)技術(shù)也逐漸受到人們的重視。

為了解決由于龐大的視頻數(shù)據(jù)造成的問題，人們提出了視頻摘要技術(shù)。視頻摘要是視頻處理的一種技術(shù)，簡單地說，它是從視頻中選取幾個視頻段或者幾張圖片，被選出來的視頻段或圖片可以簡要概括視頻內(nèi)容。在視頻摘要之前，基本上需要花費與視頻等長的時間來瀏覽視頻，但是有了視頻摘要后，人們只需要觀看視頻段或圖片就可以清楚視頻的內(nèi)容，為瀏覽視頻節(jié)省了大量時間。而且，因為視頻段或圖片基本上包含了視頻的主要內(nèi)容，只要存儲視頻段或圖片即可，為網(wǎng)站視頻存儲節(jié)省了大量空間。同時，在搜索視頻時，沒必要花費大量的時間搜索整個視頻，只需檢索相應(yīng)的視頻段或圖片。視頻摘要技術(shù)可以解決視頻數(shù)據(jù)迅猛增長產(chǎn)生的問題，極大地方便了人們的生活。

對于視頻摘要的分類，有很多不同的標準。根據(jù)輸出的摘要類型劃分，可以分為動態(tài)視頻摘要和靜態(tài)視頻摘要[2]。動態(tài)視頻摘要是從視頻中選取一些視頻片段，把這些視頻片段組織連貫起來，形成一段流暢的視頻作為摘要。靜態(tài)視頻摘要是從視頻中選取幾幀重要的視頻幀，將這些視頻幀組織起來構(gòu)成視頻的摘要。這兩種形式的視頻摘要有各自的特點[3]。動態(tài)視頻摘要是一小段視頻，包含了音頻信息和連續(xù)的動作信息，可以幫助用戶更加生動地了解視頻的主要內(nèi)容。靜態(tài)視頻摘要是由圖片組成的，以時間順序呈現(xiàn)在用戶面前，具有更高的瀏覽效率。當然，無論是動態(tài)視頻摘要還是靜態(tài)視頻摘要，都能代表視頻內(nèi)容，都能達到在看過視頻摘要后就可以清楚地知道視頻內(nèi)容的效果。

由于視頻數(shù)據(jù)的增多，根據(jù)視頻內(nèi)容自動提取視頻摘要已經(jīng)是大勢所趨。一般來說，視頻摘要都由以下4個步驟組成：特征提取、視頻鏡頭分割、視頻內(nèi)容重要性評價、視頻摘要生成[2]。特征提取是視頻處理最基礎(chǔ)的一步，提取的視頻幀特征有全局特征(例如顏色、紋理、運動信息)和局部特征(例如尺度不變特征變換SIFT)[4]。近來，也用到了一些高級語義特征和深度特征。視頻鏡頭分割[2]就是把一長段視頻分成幾個小片段，滿足同一片段內(nèi)的視頻內(nèi)容盡可能相似，不同片段間的視頻內(nèi)容盡可能不同，通常是根據(jù)視頻幀之間的相似度進行視頻分段。視頻內(nèi)容重要性評價是指算法按照一些規(guī)則和依據(jù)，對視頻內(nèi)容的重要性進行評價，為后續(xù)提取視頻摘要做準備。生成視頻摘要是根據(jù)重要性評價結(jié)果，將其中比較重要的部分提取出來，作為整個視頻的摘要，其輸出形式可以是動態(tài)的短視頻或者是靜態(tài)的圖片幀。本文的視頻摘要形式是靜態(tài)的視頻幀。

視頻摘要的方法有很多，聚類[5]是主要方法之一，聚類是把相似的視頻幀聚成一簇，從每一簇里選取幾幀組成視頻摘要。之后出現(xiàn)了對視頻摘要做約束的方法，例如摘要應(yīng)該覆蓋視頻的內(nèi)容，摘要的冗余性應(yīng)該比較低等，針對這些約束各自構(gòu)建了計算公式，然后從視頻幀集合中選取一個分數(shù)最高的子集作為摘要。然而，這些方法有一些缺點，首先要對摘要做約束，這個是要先驗知識的，理解角度不一樣對摘要的約束也不同，對摘要的約束個數(shù)也不同，約束不同繼而構(gòu)造的計算公式也不一樣。還有，摘要是從視頻幀集合中選取根據(jù)約束公式計算的分數(shù)最高的子集。若一個視頻有個 幀，視頻幀集合則有種組合，計算復(fù)雜度是，每增加一幀計算量會呈指數(shù)式增長。針對以上問題，本文提出了一個基于排序?qū)W習(xí)[6](learning to rank)的視頻摘要方法。

本文工作的主要貢獻有以下兩點：

1)本文視頻摘要的方法不依賴于先驗知識的約束。本文把視頻摘要看成是對視頻幀的排序，根據(jù)訓(xùn)練集訓(xùn)練排序算法，使得和視頻相關(guān)的幀排在前面的位置。

2)相比之前的視頻摘要方法，本文方法的計算量大大降低。本文是對視頻幀打分，計算復(fù)雜度是，之前的大多數(shù)方法是對視頻幀集合打分，計算復(fù)雜度是。

本文方法是基于排序?qū)W習(xí)算法來解決關(guān)鍵幀選取問題，把視頻幀選取看成一個排序問題，與視頻相關(guān)性大的幀被排在前面，這些幀被選為關(guān)鍵幀。本文方法依然是按照視頻摘要的4個步驟進行，因為視頻的連續(xù)性，首先對視頻分段，然后提取視頻幀的深度特征，之后用排序?qū)W習(xí)算法對視頻中的幀排序，最后選取排在前面的幀組成視頻摘要。

1 相關(guān)工作

大多數(shù)視頻摘要的方法基于兩個準則，一個是選取的關(guān)鍵幀能盡可能多地包含視頻內(nèi)容，另一個是被選取的關(guān)鍵幀之間盡可能不同?；谶@兩個準則，設(shè)計了不同的計算公式。Guan等[4]提出了基于關(guān)鍵點的關(guān)鍵幀選擇(keypoint-based keyframe selection)算法，是一種無監(jiān)督方法，文中給出覆蓋率和冗余性兩個公式，提取每個視頻幀的SIFT局部特征，把提取到的所有幀的SIFT局部特征組成關(guān)鍵點池，每個視頻幀與關(guān)鍵點池進行匹配，從關(guān)鍵點池中去掉已經(jīng)匹配的關(guān)鍵點，能最多覆蓋關(guān)鍵點池并且可以最小化摘要冗余性的幀被選為關(guān)鍵幀。Chakraborty等[6]設(shè)計了代表性和獨特性兩個公式，代表性是度量關(guān)鍵幀集合與視頻的相似性，獨特性是量化關(guān)鍵幀集合中幀之間的相似性，賦予代表性和獨特性合適的權(quán)重來計算候選集合的得分，得分最高的集合被選為關(guān)鍵幀集合。Gong等[1]提出了seqDPP(sequential determinantal point process)模型，它是一個概率模型，是基于DPP模型做了改進。DPP模型可以確保選擇的關(guān)鍵幀之間互不相同，但是卻沒有考慮到視頻的時序性。例如，一個視頻中開始部分包含了吃早餐的鏡頭，結(jié)束部分包含了吃晚餐的鏡頭。如果使用DPP模型它只會從早餐和晚餐里選一個鏡頭，但是因為吃早餐和吃晚餐是兩件不同的事情，而且相隔時間比較長，所以這兩個鏡頭應(yīng)該都被選為關(guān)鍵幀。為了彌補這個缺陷，Gong等先把視頻分割成幾個小片段，在每個小片段里使用DPP算法，在當前片段里選取關(guān)鍵幀時要考慮到前一片段中已經(jīng)選取的關(guān)鍵幀，避免當前片段選取的關(guān)鍵幀與前一片段選取的關(guān)鍵幀過于相似。Li等[5]提出了4個模型，分別是重要性、代表性、多樣性和故事性，重要性是指選取的關(guān)鍵幀要包含重要的人和物，代表性是指選取的關(guān)鍵幀能代表視頻內(nèi)容，多樣性是指選取的關(guān)鍵幀要盡可能不同，故事性是指選取的關(guān)鍵幀故事性比較強，用戶能比較容易理解視頻內(nèi)容。相應(yīng)地構(gòu)建了4個公式并且學(xué)習(xí)得到關(guān)于4個模型的權(quán)重，最終用于計算關(guān)鍵幀集合的分數(shù)，分數(shù)最高的關(guān)鍵幀集合被選為視頻摘要。Hu等[7]提出了用多個屬性和圖片質(zhì)量來提取摘要，在文中提出了9個屬性和一個計算圖片質(zhì)量的方法。Hu等認為摘要中的幀應(yīng)該是清楚的、清晰的，而視頻中的一些幀質(zhì)量不是高的，有可能是失真的、模糊的，這些圖片不應(yīng)該被選擇到摘要中，所以計算了每幀的質(zhì)量作為這一幀可以被選為關(guān)鍵幀的權(quán)重。Sun等[8]提出了SASUM(semantic attribute assisted video SUMmarization)的視頻摘要方法，學(xué)習(xí)了一個深度神經(jīng)網(wǎng)絡(luò)用來提取每一幀的語義特征，用得到的語義特征把圖片聚成幾組，選取每組的中心片段組成最終的視頻摘要。

大多數(shù)的視頻摘要方法都是根據(jù)個人經(jīng)驗構(gòu)建模型，然后學(xué)習(xí)各個模型的權(quán)重，之后計算視頻幀集合的分數(shù)，從中選取分數(shù)最高的視頻幀集合作為視頻摘要。對于這類方法，首先要構(gòu)建模型，模型設(shè)計的好壞，模型的個數(shù)對摘要的結(jié)果有很大的影響。除此之外，還要計算所有視頻幀集合的分數(shù)，一個僅有20個幀的視頻就會產(chǎn)生一百多萬種組合，計算復(fù)雜度是。

本文的視頻摘要方法是對視頻幀打分，使得自動產(chǎn)生的分數(shù)分布與人工標記的分數(shù)分布盡可能吻合。學(xué)習(xí)打分的過程是基于排序?qū)W習(xí)算法，該算法不僅考慮到幀與視頻的關(guān)系，也考慮到幀與幀之間的關(guān)系。本文的方法直接利用人工標記的摘要訓(xùn)練學(xué)習(xí)器，不依賴先驗知識的約束。而且，本文的方法是對視頻幀打分，計算復(fù)雜度是，相比于對幀集合打分的方法，復(fù)雜度大大降低。

2 基于排序?qū)W習(xí)的視頻摘要

2.1 排序?qū)W習(xí)

排序?qū)W習(xí)被廣泛應(yīng)用于文檔檢索，給予一個查詢條件，排序?qū)W習(xí)算法會給出與查詢條件相關(guān)的文檔關(guān)于相關(guān)性的一個由高到低的排序，排在越前面的文檔是越符合查詢條件的文檔。排序?qū)W習(xí)算法有基于點、基于文檔對[9]、基于文檔列表3種方法。視頻摘要與基于文檔列表排序的思想更切合，在視頻摘要中借鑒的是基于文檔列表的方法。

Listwise方法對文檔的排序結(jié)果進行優(yōu)化，使得預(yù)測的排序與ground truth的排序更接近。在訓(xùn)練階段，把排序函數(shù)自動產(chǎn)生的分數(shù)與ground truth中的分數(shù)轉(zhuǎn)換成概率，衡量兩個概率分布的誤差，誤差越小說明自動排序結(jié)果和ground truth排序結(jié)果越接近。預(yù)測時直接用訓(xùn)練好的排序函數(shù)對文檔打分，分數(shù)越高說明與查詢條件越相關(guān)。

在Listwise方法里有兩種概率模型，分別是Permutation Probability和 Top k Probability，概率模型把文檔得分轉(zhuǎn)換成概率，計算所有排列的概率組成概率列表。構(gòu)建的概率模型應(yīng)該滿足與ground truth分布越接近的分布發(fā)生的概率越大。每種排列對應(yīng)一個概率，所有可能的排列的概率之和為1。Permutation Probability考慮了所有文檔的排列，Top k Probability僅考慮了k個文檔的排列。本文采用的是Top k Probability，用公式表示為

2.2 排序?qū)W習(xí)視頻摘要方法詳述

視頻摘要是把與視頻相關(guān)的視頻幀按照相關(guān)性排序并呈現(xiàn)給用戶，不同的視頻時長不一樣。文檔檢索是根據(jù)文檔與查詢條件的相關(guān)性由高到低排序，把排序后的文檔呈現(xiàn)給用戶，不同的檢索條件相關(guān)的文檔數(shù)目不一樣。文檔檢索是要學(xué)習(xí)文檔的順序，自動產(chǎn)生的相關(guān)性高的文檔要盡可能與人工標注的一樣，視頻摘要是要學(xué)習(xí)視頻幀的順序，自動產(chǎn)生的與視頻相關(guān)性高的幀要盡可能與人工標注的一樣。在這里視頻相當于查詢條件，視頻幀相當于文檔?；谂判?qū)W習(xí)的文檔檢索的廣泛應(yīng)用，證明排序?qū)W習(xí)可以很好地學(xué)習(xí)到人工排序的過程，視頻摘要和文檔檢索是如此相似，因此本文提出了基于排序?qū)W習(xí)的視頻摘要，把視頻摘要建模成視頻幀與視頻的相關(guān)性排序。主要分為以下5個步驟：

1)視頻預(yù)處理：由于視頻的連續(xù)性，不能直接對視頻視頻使用排序?qū)W習(xí)算法。如果直接使用排序?qū)W習(xí)算法會導(dǎo)致選出來的摘要中有太多相似的圖片，這與摘要中的幀應(yīng)盡可能不同相悖。所以，在排序?qū)W習(xí)算法之前需要對視頻分段，在本文中是把視頻2 s分為一段。

2)特征提?。罕疚挠玫降奶卣魇且曨l幀的深度特征[10]，是用預(yù)訓(xùn)練的VGG-19卷積神經(jīng)網(wǎng)絡(luò)提取的。VGG-19網(wǎng)絡(luò)包含了16個卷積層和3個全連接層。每個視頻幀用預(yù)訓(xùn)練的VGG-19卷積神經(jīng)網(wǎng)絡(luò)提取到4 096維特征，然后用PCA算法對4 096維特征降維，屬于同一個視頻的幀的特征平均后就是該視頻的特征。

3)學(xué)習(xí)排序函數(shù)：在對視頻每一幀打分之前，首先要根據(jù)訓(xùn)練樣本學(xué)習(xí)排序函數(shù)，有了排序函數(shù)后再對視頻中的每一幀打分。

在本文的符號表示中，上角標表示視頻幀id，下角標表示視頻id。視頻集合，視頻的視頻幀列表，表示視頻第個視頻幀。每個視頻幀列表都有一組相關(guān)性分數(shù)，表示視頻幀與視頻的相關(guān)程度的得分。

對于視頻摘要來說，沒必要使得預(yù)測的概率列表和ground truth的概率列表，相應(yīng)位置對應(yīng)的排列中所有視頻幀的順序相同，只要使得分數(shù)第一高的幀排在該排列的第一個位置，分數(shù)第2高的幀排在排列第2個位置，以此類推，即只要排列中的第1個幀相同即可，即排序?qū)W習(xí)算法Top k Probability中的k=1。還有，本文的排序函數(shù)中特征和權(quán)重是線性關(guān)系，是指數(shù)函數(shù)。

之后用梯度下降法求解。

4)打分：前面根據(jù)訓(xùn)練樣本學(xué)習(xí)到的排序函數(shù)被認為是學(xué)到了人選取關(guān)鍵幀的一個過程，現(xiàn)在可以利用學(xué)習(xí)到的排序函數(shù)

對視頻中的幀打分。

5)提取關(guān)鍵幀：本文生成摘要的方法是把視頻幀看成一個排序問題，和視頻相關(guān)性大的幀排在前面。利用前面學(xué)到排序函數(shù)對視頻中的幀打分，得分高的幀就被選為關(guān)鍵幀，計算復(fù)雜度是。大多數(shù)視頻摘要方法，把生成摘要看成一個優(yōu)化的問題，從所有的視頻幀集合中找出一個得分最高的集合作為視頻摘要，計算復(fù)雜度是。

3 實驗與結(jié)果

3.1 實驗設(shè)置

3.1.1 數(shù)據(jù)集

實驗用的數(shù)據(jù)集是TVSum50數(shù)據(jù)庫[11]，包含50個視頻，10個類別，每個類別有5個視頻，視頻時長2～10 min不等，視頻包含了新聞、紀錄片、用戶拍攝等不同的種類，視頻被每2 s分成一段，每個視頻段由20個用戶打分，產(chǎn)生20個分數(shù)(1～5，5代表該視頻段與視頻最相關(guān)，依次遞減)，分數(shù)高的視頻段中的幀被選為關(guān)鍵幀。就像其他論文中那樣，摘要的長度被限制在小于視頻長度的15%。從每個類別的視頻里隨機選取一個視頻作為測試視頻，剩下的視頻作為訓(xùn)練視頻，也就是40個視頻作為訓(xùn)練集，10個視頻作為測試集。如圖1所示。

圖1 判斷兩個圖片相似的情況，從每個閾值里選取了兩組圖Fig. 1 Judging the similarity between the two pictures and selecting two pairs of pictures from each threshold

3.1.2 評估方法

對于自動產(chǎn)生的摘要A和人工標記的ground truth摘要B，本文是通過計算摘要A和摘要B的匹配程度來判斷摘要A的好壞。從摘要A和摘要B中分別取出一個視頻幀組成一個包含兩個視頻幀的對，若A中有個幀，B中有個幀，則會產(chǎn)生種對。計算每對的距離，若距離小于某個閾值，則認為這個視頻幀對成功匹配，需要注意的是每個視頻幀只能成功匹配一次。精確率、 召回率和F-score定義為

用自動產(chǎn)生的摘要分別與20個人工標記的摘要計算P、R、F-score，之后取平均值作為該視頻的最終結(jié)果。

3.2 實驗和結(jié)果

3.2.1 閾值設(shè)置

視頻幀用不同的特征提取方法得到的幀是不一樣的，判斷兩個視頻幀是否相似的閾值也隨之不同，若閾值設(shè)置太大會產(chǎn)生兩個完全不一樣的圖片被判斷為相似，使得F-score值偏大；反之，若閾值設(shè)置太小會使得F-score值偏小，所以要判斷閾值為為何值時認為兩個幀相似會比較合理。

從圖2中可以看出F-score隨閾值的增大而增加。設(shè)置閾值是為了判斷兩個圖片是否相似，閾值設(shè)置太大就不能解決這個問題，所以要選取合適的閾值。

從圖2中可知，threshold=0時，只有兩個圖片一模一樣才會被判斷相似；threshold=0.04時，觀察發(fā)現(xiàn)兩個不相似的圖片被認定相似，也就是說閾值設(shè)置太大了；最終threshold設(shè)置為0.03。

3.2.2 實驗改進

uniform sample 和random sample都是取樣中的方法，uniform sample是按照固定間隔抽取視頻幀，random sample是隨機抽取關(guān)鍵幀。聚類是從較大的簇中選取視頻幀，用了兩種聚類方法k-均值聚類(k-means cluster)和譜聚類(spectral cluster)。LiveLight (online video highlighting)方法[12]是通過字典衡量冗余信息，刪除冗余信息來選取摘要。sample、cluster和LiveLight都是非監(jiān)督方法，而本文的方法是有監(jiān)督的方法，用人工標記的摘要學(xué)習(xí)排序函數(shù)，學(xué)習(xí)人工打分的過程，實驗結(jié)果表明本文的方法更好，如表1所示。

圖2 閾值取不同值時對應(yīng)的F-score值Fig. 2 F-score value with different threshold

表 1 不同方法在TVSum50上的實驗結(jié)果Table 1 The Results on TVSum50

4 結(jié)束語

由于目前大多數(shù)的視頻摘要方法要對摘要做約束并構(gòu)建相應(yīng)的公式，而且還要從眾多的視頻幀集合中挑選比較好的集合作為摘要，不僅需要先驗知識，由于集合數(shù)目太多，還會增加計算量。本文呈現(xiàn)的視頻摘要的方法，把提取摘要看作是對視頻幀的排序問題，利用人工標記的關(guān)鍵幀訓(xùn)練排序函數(shù)，使得排在前面的幀是人工標記的幀，因此不是對視頻幀集合打分，而是對單個幀打分，這樣可以減少計算量，在TVSum50數(shù)據(jù)集上表現(xiàn)出比其他幾個視頻摘要的方法好。