基于排序學習的視頻摘要

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

（1. 山東大學 計算機科學與技術學院，山東 濟南 250101; 2. 山東財經大學 計算機科學與技術學院，山東 濟南250014; 3. 山東大學 軟件學院， 山東 濟南 250101）

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

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

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

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

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

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

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

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

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

1 相關工作

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

大多數的視頻摘要方法都是根據個人經驗構建模型，然后學習各個模型的權重，之后計算視頻幀集合的分數，從中選取分數最高的視頻幀集合作為視頻摘要。對于這類方法，首先要構建模型，模型設計的好壞，模型的個數對摘要的結果有很大的影響。除此之外，還要計算所有視頻幀集合的分數，一個僅有20個幀的視頻就會產生一百多萬種組合，計算復雜度是。

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

2 基于排序學習的視頻摘要

2.1 排序學習

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

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

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

2.2 排序學習視頻摘要方法詳述

視頻摘要是把與視頻相關的視頻幀按照相關性排序并呈現給用戶，不同的視頻時長不一樣。文檔檢索是根據文檔與查詢條件的相關性由高到低排序，把排序后的文檔呈現給用戶，不同的檢索條件相關的文檔數目不一樣。文檔檢索是要學習文檔的順序，自動產生的相關性高的文檔要盡可能與人工標注的一樣，視頻摘要是要學習視頻幀的順序，自動產生的與視頻相關性高的幀要盡可能與人工標注的一樣。在這里視頻相當于查詢條件，視頻幀相當于文檔。基于排序學習的文檔檢索的廣泛應用，證明排序學習可以很好地學習到人工排序的過程，視頻摘要和文檔檢索是如此相似，因此本文提出了基于排序學習的視頻摘要，把視頻摘要建模成視頻幀與視頻的相關性排序。主要分為以下5個步驟：

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

2)特征提取：本文用到的特征是視頻幀的深度特征[10]，是用預訓練的VGG-19卷積神經網絡提取的。VGG-19網絡包含了16個卷積層和3個全連接層。每個視頻幀用預訓練的VGG-19卷積神經網絡提取到4 096維特征，然后用PCA算法對4 096維特征降維，屬于同一個視頻的幀的特征平均后就是該視頻的特征。

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

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

對于視頻摘要來說，沒必要使得預測的概率列表和ground truth的概率列表，相應位置對應的排列中所有視頻幀的順序相同，只要使得分數第一高的幀排在該排列的第一個位置，分數第2高的幀排在排列第2個位置，以此類推，即只要排列中的第1個幀相同即可，即排序學習算法Top k Probability中的k=1。還有，本文的排序函數中特征和權重是線性關系，是指數函數。

之后用梯度下降法求解。

4)打分：前面根據訓練樣本學習到的排序函數被認為是學到了人選取關鍵幀的一個過程，現在可以利用學習到的排序函數

對視頻中的幀打分。

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

3 實驗與結果

3.1 實驗設置

3.1.1 數據集

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

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

3.1.2 評估方法

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

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

3.2 實驗和結果

3.2.1 閾值設置

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

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

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

3.2.2 實驗改進

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

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

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

4 結束語

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