《一種產生視頻大綱的方法和系統》是中國科學院計算技術研究所於2008年4月21日申請的專利，該專利的申請號為2008101045841，公布號為CN101262568，授權公布日為2008年9月10日，發明人是陳益強、黃強、紀雯。
《一種產生視頻大綱的方法和系統》提供一種產生視頻大綱的方法，包括如下步驟：對視頻幀進行運動物體檢測，得到運動物體和背景；跟蹤所述運動物體，並生成所述運動物體的軌跡；基於認知心理學方面的知識計算視頻大綱，並依此重排所述運動物體的軌跡；融合所述背景和所述重排後的運動物體軌跡，生成視頻大綱。該方法避免了輸出視頻大綱中的運動物體雜亂無章，使其適合人眼觀察，方便用戶觀察到原視頻中的有效信息；而且在重排時進一步避免了運動物體的碰撞，並且儘量保持了物體原來的時序連貫性。
2016年12月7日，《一種產生視頻大綱的方法和系統》獲得第十八屆中國專利優秀獎。
（概述圖為《一種產生視頻大綱的方法和系統》摘要附圖）
基本介紹
- 中文名：一種產生視頻大綱的方法和系統
- 公布號：CN101262568
- 授權日：2008年9月10日
- 申請號：2008101045841
- 申請日：2008年4月21日
- 申請人：中國科學院計算技術研究所
- 地址：北京市海淀區中關村科學院南路6號
- 發明人：陳益強、黃強、紀雯
- Int.Cl.：H04N5/262(2006.01)、G06F17/30(2006.01)、G06T15/70(2006.01)
- 代理機構：北京泛華偉業智慧財產權代理有限公司
- 代理人：王勇
- 類別：發明專利
專利背景,發明內容,專利目的,技術方案,改善效果,附圖說明,技術領域,權利要求,實施方式,榮譽表彰,
專利背景
視頻摘要是從文本摘要引申出來的一個概念，文本摘要是對一篇文章或者一段文字的簡要總結，所以視頻摘要就是要對一段較長的視頻內容進行相關技術的處理得到一個簡要的總結，也就是以自動或者半自動的方式對視頻的結構和內容進行分析，把原視頻中的有意義的部分提取出來，然後再以某種方式進行組合，形成一個簡潔但是能充分表現視頻內容的概要。這個總結可以是以文本形式來表示的，也可以是一些靜止的圖片或者一段比原視頻短的視頻，現在大部分的視頻摘要技術都是以後者來進行表示。
傳統的視頻摘要技術根據摘要的表現形式的不同主要可以分為兩大類：靜態的視頻摘要，又稱為視頻概要（Video Summary），主要是以靜態的方式來表現原視頻的內容，如標題、關鍵幀、幻燈片、場景轉換圖（STG）等；動態的視頻摘要，又稱為視頻縮略（Video Skimming），它是以動態的視頻序列來表現原視頻的內容，它本身就是一段比原視頻短的視頻，有些還有帶有原視頻中的音頻。視頻概要通常只考慮了視覺信息，以單一靜止的視頻幀或者文字來表示一段視頻，優點在於實現簡單，2008年4月前商用的系統大部分都是採用該方法，如各大視頻網站都會給每個視頻配一幅該視頻中的圖片來標記該段視頻。但是視頻概要極大的損失了視頻的表現力，不符合用戶的感知習慣，視頻縮略在一定程度上彌補了這一缺點，但是視頻縮略的算法都比較複雜，難以實現自動提取，人工合成的成本很高，2008年4月前視頻縮略的方法最常見於專業的影視行業的片段預告製作中。
傳統的視頻摘要技術忽略了很重要的一個方面，即空域-時域之間的結合。正如摘要的定義，視頻摘要的目的在於在有限的空間和時間範圍內提供給用戶儘量多的信息以展現重要的視頻的內容。但是2008年4月前研究人員關注最多的是如何在時間軸上選擇視頻幀，並將它們排列起來展現給用戶。他們理所當然地將視頻幀作為一個不可分割的最小視頻單元。其實這忽略了視頻本身就是一個由兩維的空間和一維的時間組成的三維的流。同時，在這個三維空間中，視頻信息的分布是不均勻的。2008年4月前所有的視頻摘要研究都只是針對的視頻信息在時間軸上的不均勻性，卻忽略了視頻在空間域上也是非均勻分布的。
針對2008年4月前視頻摘要算法存在缺點，AlexRav-Acha等人提出了視頻大綱（VideoSynopsis）方法，該方法把視頻看做是一個在時域-空域上統一的3維體，不僅考慮視頻在時間維上的信息不均勻性，也考慮了視頻在空間上同樣存在信息的分布不均勻。該算法首先對視頻中的有效信息-運動物體進行分析，抽取出運動物體，然後把這些運動物體在重建的背景上進行重新的排列組合，充分利用每一幀的空間，重新融合成一段視頻大綱，生成後的視頻大綱比原視頻要短得多，但是包含了原視頻中幾乎所有的有效信息。視頻大綱的算法流程可以用附圖1所示。
首先進行運動物體的檢測，如附圖1中的101，對每一幀中的每一個像素檢測其屬於運動物體還是屬於背景。
然後進行運動物體的跟蹤，並生成軌跡，如附圖1中的102。在此步驟中進行運動物體的分割，並對每個運動物體進行跟蹤，生成各自的運動軌跡。
運動物體軌跡生成後，進行運動物體的重新的排列組合，如附圖1中的103，即把所有的運動物體軌跡在時間軸上進行重新排列。排列運動物體本質上是找到一個時間域上的映射M，把這些運動物體從原視頻幀中的時間位置映射到輸出視頻中的另外一個時間位置，由於視頻大綱保持運動物體在空間上的不變，所以該映射只作用在時間軸。該模組算法如下：
定義B為所有運動物體的集合，b為其中的一個運動物體，該運動物體在原視頻中的位置是tb=[tbs,tbe],]]>則經過M（b）=b^]]>映射，在輸出視頻中t^b=[t^bs,t^be],]]>其中ts，te分別表示運動物體在原視頻中的開始位置和結束位置，分別表示運動物體在輸出視頻中的開始位置和結束位置。如果運動物體沒有在最終的輸出視頻中出現，則為了找到一個好的映射M，定義了如下的能量損耗公式，能讓公式（1）取得最小值的M就是達到最好效果的映射。
其中Ea是運動信息損失，定義如下：
其中χb（x，y，t）是表示的運動物體b的特徵值，就是運動物體b包含的像素個數。公式（2）表示如果一個運動物體沒有出現在視頻大綱的輸出視頻中，那么該物體的特徵值就要加入運動損失中。
Ec是碰撞損失，定義為在輸出視頻中任意兩個運動物體在時空上的重疊：
其中
表示運動物體b和b’在輸出視頻中同時存在的那段時間，利用公式（3）可以在一定程度上控制運動物體在輸出視頻中的密度。
最後融合運動物體的檢測所得到的背景和重新排列好的運動物體軌跡生成視頻大綱，如附圖1中的104。
上述方法雖然已經考慮了視頻中信息在時空三維上的分布，但是最後得到的結果並不是很理想，在輸出視頻大綱中各種運動物體擁擠在一起，這樣雖然視頻的長度大大縮短了，但是每一幀視頻中的信息量太多，觀察者很難處理這么多信息量，因此需要適當的減少每幀視頻中的信息量。
發明內容
專利目的
《一種產生視頻大綱的方法和系統》目的在於解決2008年4月前技術中視頻大綱單幀內信息量太多、運動物體密度過大的問題，從而提供一種使得輸出視頻大綱符合人眼觀測模式的產生視頻大綱的方法和系統。
技術方案
為了實現上述目的，根據《一種產生視頻大綱的方法和系統》的一個方面，提供了一種產生視頻大綱的方法，包括以下步驟：
1）對視頻幀進行運動物體檢測，得到運動物體和背景；
2）跟蹤所述運動物體，並生成所述運動物體的軌跡；
3）根據數量密度代價計算密度代價Edn（p）和物體方向密度代價Edd（p）利用公式Ed（p）=Edn（p）+Edd（p）計算密度代價Ed（p），其中p是視頻幀，數量密度代價Edn（p）=｜N（p）-Cn｜，N（p）是視頻幀p中運動物體的個數，Cn是視覺運動物體數量容量，物體方向密度代價
，Δ（p）是幀p中所有物體運動的方向個數，Cd是視覺運動物體方向容量；
4）根據
計算變化代價Er（p），其中
，b是運動物體；
5）根據
計算視頻大綱代價，其中α和β是不同時為零的同號實數，P是生成視頻幀集合，並根據所述視頻大綱代價重排所述運動物體的軌跡；
6）融合所述背景和所述重排後的運動物體軌跡，生成視頻大綱。
根據《一種產生視頻大綱的方法和系統》的另一方面，上述方法的步驟4）後還包括步驟a）根據
，
計算碰撞代價Ec（p），其中b ′是運動物體；
且在步驟5）中根據
計算視頻大綱代價，其中λ是非零實數且與α和β同號。
根據《一種產生視頻大綱的方法和系統》的另一方面，上述方法的步驟4）後還包括步驟b）根據
，
計算非連貫性代價Et（p），其中b ′是運動物體，
、
分別是運動物體b和b ′的在所述視頻幀中的開始視覺，
和
分別是運動物體b和b ′的在所述視頻大綱中的開始時間；
且在步驟5）中根據
計算視頻大綱代價，其中δ是非零實數且與α和β同號。
根據《一種產生視頻大綱的方法和系統》的另一方面，上述方法的步驟a）後包括步驟b）根據，
計算非連貫性代價Et（p），其中b ′是運動物體，、分別是運動物體b和b ′的在所述視頻幀中的開始視覺，和分別是運動物體b和b ′的在所述視頻大綱中的開始時間；
且在步驟5）中根據
計算視頻大綱代價，其中δ是非零實數且與α和β同號。
根據《一種產生視頻大綱的方法和系統》的再一方面，上述方法的所述α、β、δ和λ取值範圍是[1，5]。
根據《一種產生視頻大綱的方法和系統》的再一方面，上述方法的所述Cn是4或5。
根據《一種產生視頻大綱的方法和系統》的再一方面，上述方法的所述Cd是3。
根據《一種產生視頻大綱的方法和系統》的又一方面，該發明還提供了一種產生視頻大綱的系統，包括：
運動物體檢測模組，其用於進行運動物體的檢測，得到運動物體和背景；
運動物體跟蹤及軌跡生成模組，其用於跟蹤所述運動物體，並生成所述運動物體的軌跡；
運動物體重排模組，其用於根據數量密度代價Edn（p）和物體方向密度代價Edd（p）利用公式Ed（p）=Edn（p）+Edd（p）計算密度代價Ed（p），其中p是視頻幀，數量密度代價Edn（p）=｜N（p）-Cn｜，N（p）是視頻幀p中運動物體的個數，Cn是視覺運動物體數量容量，物體方向密度代價，Δ（p）是幀p中所有物體運動的方向個數，Cd是視覺運動物體方向容量，根據計算變化代價Er（p），其中，b是運動物體，根據
計算視頻大綱代價，其中α、β是不同時為零的同號實數，p是視頻幀，P是視頻幀集合，並依所述視頻大綱代價重排所述運動物體的軌跡；以及視頻大綱生成模組，用於融合所述背景和所述重排後的運動物體軌跡，生成視頻大綱。
根據《一種產生視頻大綱的方法和系統》的又一方面，上述系統的所述運動物體重排模組，還用於根據，計算碰撞代價Ec（p），其中b ′是運動物體，根據，計算非連貫性代價Et（p），其中b ′是運動物體，、分別是運動物體b和b ′的在所述視頻幀中的開始視覺，和分別是運動物體b和b ′的在所述視頻大綱中的開始時間，並且根據
計算視頻大綱代價，其中δ和λ是與α同號的非零實數。
改善效果
《一種產生視頻大綱的方法和系統》通過上述實施例，充分利用了認知心理學近年來在視覺理論方面的研究成果，通過在視頻大綱代價中考慮密度代價和變化代價等因素，避免了輸出視頻大綱中的運動物體雜亂無章，使其適合人眼觀察，方便用戶觀察到原視頻中的有效信息；而且在重排時進一步避免了運動物體的碰撞，並且儘量保持了物體原來的時序連貫性。
附圖說明
圖1是產生視頻大綱的方法的流程圖。
圖1
圖2是運動方向劃分示意圖。
圖2
技術領域
《一種產生視頻大綱的方法和系統》涉及圖像處理技術領域，進一步涉及視頻摘要領域。
權利要求
1.一種產生視頻大綱的方法，包括如下步驟：
1）對視頻幀進行運動物體檢測，得到運動物體和背景；
2）跟蹤所述運動物體，並生成所述運動物體的軌跡；
3）根據數量密度代價計算密度代價Edn（p）和物體方向密度代價Edd（p）利用公式Ed（p）=Edn（p）+Edd（p）計算密度代價Ed（p），其中p是視頻幀，數量密度代價Edn（p）=｜N（p）-Cn｜，N（p）是視頻幀p中運動物體的個數，Cn是視覺運動物體數量容量，物體方向密度代價，Δ（p）是幀p中所有物體運動的方向個數，Cd是視覺運動物體方向容量；
4）根據計算變化代價Er（p），其中，b是運動物體；
5）根據計算視頻大綱代價，其中α和β是不同時為零的同號實數，P是生成視頻幀集合，並根據所述視頻大綱代價重排所述運動物體的軌跡；
6）融合所述背景和所述重排後的運動物體軌跡，生成視頻大綱。
2.根據權利要求1所述的方法，其特徵在於，所述
步驟4）後還包括步驟a）根據，計算碰撞代價Ec（p），其中b ′是運動物體；
且在步驟5）中根據計算視頻大綱代價，其中λ是非零實數且與α和β同號。
3.根據權利要求1所述的方法，其特徵在於，所述
步驟4）後還包括步驟b）根據，計算非連貫性代價Et（p），其中b ′是運動物體，、分別是運動物體b和b ′的在所述視頻幀中的開始視覺，和分別是運動物體b和b ′的在所述視頻大綱中的開始時間；
且在步驟5）中根據計算視頻大綱代價，其中δ是非零實數且與α和β同號。
4.根據權利要求2所述的方法，其特徵在於，所述
步驟a）後包括步驟b）根據，計算非連貫性代價Et（p），其中b ′是運動物體，、分別是運動物體b和b ′的在所述視頻幀中的開始視覺，和分別是運動物體b和b ′的在所述視頻大綱中的開始時間；
且在步驟5）中根據計算視頻大綱代價，其中δ是非零實數且與α和β同號。
5.根據權利要求4的方法，其特徵在於，所述α、β、δ和λ取值範圍是[1，5]。
6.根據權利要求1所述的方法，其特徵在於，所述Cn是4或5。
7.根據權利要求1所述的方法，其特徵在於，所述Cd是3。。
8.一種產生視頻大綱的系統，包括：
運動物體檢測模組，其用於進行運動物體的檢測，得到運動物體和背景；
運動物體跟蹤及軌跡生成模組，其用於跟蹤所述運動物體，並生成所述運動物體的軌跡；
運動物體重排模組，其用於：根據數量密度代價Edn（p）和物體方向密度代價Edd（p）利用公式Ed（p）=Edn（p）+Edd（p）計算密度代價Ed（p），其中p是視頻幀，數量密度代價Edn（p）=｜N（p）-Cn｜，N（p）是視頻幀p中運動物體的個數，Cn是視覺運動物體數量容量，物體方向密度代價，Δ（p）是幀p中所有物體運動的方向個數，Cd是視覺運動物體方向容量，根據計算變化代價Er（p），其中，b是運動物體，根據
計算視頻大綱代價，其中α、β是不同時為零的同號實數，p是視頻幀，P是視頻幀集合，並依所述視頻大綱代價重排所述運動物體的軌跡；以及視頻大綱生成模組，用於融合所述背景和所述重排後的運動物體軌跡，生成視頻大綱。
9.根據權利要求8所述的系統，其中所述運動物體重排模組，還用於：根據，計算碰撞代價Ec（p），其中b ′是運動物體，根據，計算非連貫性代價Et（p），其中b ′是運動物體，、
分別是運動物體b和b ′的在所述視頻幀中的開始視覺，和分別是運動物體b和b ′的在所述視頻大綱中的開始時間，並且根據計算視頻大綱代價，其中δ和λ是與α同號的非零實數。
實施方式
人眼對信息的反映是屬於認知心理學的研究範疇。認知心理學認為人具有視覺工作記憶（Visual Working Memory），其指對非言語視覺信息的短時存儲，是視覺信息接受進一步處理前的暫時存儲。對視覺工作記憶的研究主要集中對視覺客體信息在工作記憶中的存儲方式和容量的問題上。研究者通過實驗得出由於受限於視覺容量，人們只能追蹤4-5個目標項，存儲大約3個客體的運動方向信息。因此《一種產生視頻大綱的方法和系統》結合此研究結果，提出了一種產生視頻大綱的方法和系統，即能讓視頻大綱的視頻儘可能地短，又能讓觀察者很舒服的進行觀測。
《一種產生視頻大綱的方法和系統》與2008年4月前技術類似，分為4個主要步驟：運動物體檢測、運動物體跟蹤和軌跡生成、運動物體重排和視頻大綱生成。其中運動物體檢測、運動物體跟蹤和軌跡生成和融合前背景的視頻大綱生成都已經有很多相關的研究，具體實現方法可以參考這些研究成果。《一種產生視頻大綱的方法和系統》充分考慮人眼對於運動物體的感知能力，主要詳細介紹基於此的運動物體重排的改進方法。這個模組的輸入是一個運動物體的集合，每個運動物體都包括以下參數：在原視頻中的位置，其用開始幀位置和結束幀位置表示，在每幀中包含的像素點。模組的輸出是每個運動物體在新視頻中的位置，其也用開始幀位置和結束幀位置表示。
假設B是所有的運動物體集合B＝{b1，b2，...，bn}，其中bi表示B中的一個運動物體。設b是B中的一個運動物體，在原來的視頻中的位置為
，運動物體重排可以看作是找到一個時域上的映射M，對每一個物體b，把tb映射到生成的視頻中的某個位置
。根據《一種產生視頻大綱的方法和系統》一個優選實施例，使得下面的視頻大綱代價最小的映射M即是所求。
其中P是最後生成的視頻幀集合，P＝{p1，p2，...，pm}；Ed是密度代價，Er是變化代價，Ec是碰撞代價，Et非連貫性代價；α、β、δ和λ是可由用戶根據試驗設定的參數，用來調整各種代價的重要程度，且α、β、δ和λ是同號實數，且α和β不是同時為零。上述根據《一種產生視頻大綱的方法和系統》優選實施例的視頻大綱代價綜合了密度代價、變化代價、碰撞代價和非連貫性代價4個因素。但是該領域技術人員應該理解只利用密度代價和變化代價計算視頻大綱，或在這兩個代價基礎上增加碰撞代價或非連貫性代價的計算也可同樣實現《一種產生視頻大綱的方法和系統》的優點。
下面逐個對各個代價函式進行描述說明。
由認知心理學可知，在最後生成的視頻中，運動物體的密度不能過大，否則超過了人眼的視覺容量就不能讓觀察者所有的物體都觀察到；但運動物體的密度也不能太小，密度太小就會使得最後生成的視頻中的運動物體稀疏，達不到縮短視頻的目的。所以採用密度代價控制輸出視頻幀中運動物體的密度。根據《一種產生視頻大綱的方法和系統》的一個實施例，密度可以分為兩部分，一部分是物體數量上的密度，一部分是物體運動方向上的密度，並可按照如下方式計算密度代價。但該領域技術人員應該理解，下述密度代價計算方式並不是唯一的，可根據《一種產生視頻大綱的方法和系統》所公開的密度代價的作用以其它方式計算。
Ed（p）＝Edn（p）+Edd（p）（5）
其中Edn是物體數量密度代價，
Edn（p）＝|N（p）-Cn|（6）
N（p）是視頻幀p中運動物體的個數，Cn是視覺運動物體數量容量，優選的取值4或5；Edd是物體方向密度代價，
Δ（p）是視頻幀p中所有物體運動的方向個數，Cd是視覺運動物體方向容量，優選的取值3；
把視野分為八個方向，每個方向45度，如附圖2所示。每個物體的運動方向都在這八個方向中的一個。
由於變化盲視的存在，觀察者對於新物體的出現很敏感，所以最後的重排中應該儘量減少同一時刻中出現新物體超過一個的機會。所以《一種產生視頻大綱的方法和系統》的視頻大綱代價中考慮了變化代價。根據《一種產生視頻大綱的方法和系統》的一個實施例，變化代價可如下式所示進行計算。但該領域技術人員應該理解，下述變化代價計算方式並不是唯一的，可根據《一種產生視頻大綱的方法和系統》所公開的變化代價的功能以其它方式計算。優選的，考慮到人眼需要500毫秒左右的記憶時間，因此新物體出現幀的後500毫秒的時間內的幀都算是該新物體出現的時間。
在最後生成的視頻中，應該在每一幀中儘量減少碰撞的存在，也即儘量減少兩個物體重疊出現，可以用碰撞代價函式來衡量最後碰撞帶來的影響。《一種產生視頻大綱的方法和系統》計算碰撞代價其如下式所示，但該領域技術人員應該理解，下述碰撞代價計算方式並不是唯一的，可根據《一種產生視頻大綱的方法和系統》所公開的碰撞代價的功能以其它方式計算，例如背景技術中所述的方法。
在生成的視頻中，還應該保持物體之間時序上的連貫性。如果在原視頻中物體a出現在物體b之前，在最後的生成的視頻中，物體a也出現在物體b之前，那么我們就說物體a和b保持了時序上的連貫性，否則就沒有保持時序上的連貫性。因此，可以用非連貫性代價函式來計算最後生成視頻中的非連貫性。根據《一種產生視頻大綱的方法和系統》的一個實施例，可根據下式計算非連貫性代價，但該領域技術人員應該理解，下述非連貫性代價計算方式並不是唯一的，可根據《一種產生視頻大綱的方法和系統》所公開的非連貫性代價的功能以其它方式計算，
其中sign（a）是表示a的正負符號。
對於該領域普通技術人員來說，《一種產生視頻大綱的方法和系統》可以採用一種視頻大綱系統來實現，該系統包含如下幾個部分：
運動物體檢測模組，用於進行運動物體的檢測；
運動物體跟蹤及軌跡生成模組，用於進行運動物體的分割，並對每個運動物體進行跟蹤，生成各自的運動軌跡；
運動物體重排模組，用於依上述方法計算視頻大綱，並依此重新排列運動物體軌跡；
視頻大綱生成模組，用於融合背景和重排後的運動物體軌跡，生成視頻大綱。
榮譽表彰
2016年12月7日，《一種產生視頻大綱的方法和系統》獲得第十八屆中國專利優秀獎。
