一種面向海洋監控視頻的索引機制?

田赤英

（中國大洋礦產資源研究開發協會 北京 100860）

一種面向海洋監控視頻的索引機制?

田赤英

（中國大洋礦產資源研究開發協會 北京 100860）

數據作為一種資產其蘊含的價值越來越重要，把收集到的數據存儲下來用于后續的數據分析與挖掘具有重要意義。論文針對海量的海洋監控視頻，提出一種存儲方案來滿足查詢需求。在此基礎上，文中提出一種索引結構RB-Tree，使得基于該索引可實現海量數據的快速檢索。此外，文章從理論層面對索引查詢的時間代價進行分析，并與基于傳統B+Tree、R-Tree索引的查詢時間代價進行對比，說明RB-Tree在海量視頻數據管理上的優勢。

海量視頻數據；監控視頻；B+Tree索引；R-Tree索引；RB-Tree索引

1 引言

海洋調查船是用于海洋科學考察、應用技術研究以及測量或勘探等船舶的統稱［1］。大洋綜合資源調查船是集多學科、多功能、多技術手段為一體、滿足以大洋資源為主同時兼顧相關深海多學科交叉研究需求的全球級現代化海洋調查船，承載海洋地質、海洋地球物理、海洋化學、海洋生物、物理海洋、海洋氣象、海洋聲學等綜合調查任務［2］。在該船的信息化系統中，數據可分為實時采集數據、人工上傳數據和實時視頻數據三大類，其中實時視頻數據包含衛星電視、海底攝像等各種制式的視頻信息。對于各種不同制式的視頻數據，現有系統聚焦于如何將視頻信息實時發送給遠程用戶進行觀看。然而，隨著存儲設備成本的下降，人們更傾向于將所有獲取到的數據存儲下來用于挖掘和分析。

對于海量視頻數據，其價值的完整體現需要多種技術的協同。文件系統提供最底層存儲能力的支持；為了便于數據管理，需要在文件系統之上建立數據庫系統；通過索引等的構建，對外提供高效的數據查詢等常用功能；最終通過數據分析技術從數據庫中的大數據提取出有益的知識［3］。在底層文件系統層，可以借助GFS文件系統［4］實現視頻類大文件的存儲。在文件系統之上，為支持海量數據，采用 NoSQL 方式管理數據［5～6］。典型的 NoSQL數據庫包括基于鍵值對模型、列式存儲模型、文檔模型和圖模型四種類型的數據庫［7～9］，由于視頻文件屬于非結構化數據，查詢并不涉及視頻內容，故可采用鍵值對模型對海量視頻數據進行建模。在利用鍵值對進行建模存儲時，面臨以下挑戰：

1）實時監控產生的視頻數據具有時間段、地理位置等屬性，如何定義視頻數據的鍵，以支持基于時間段、地理位置的查詢；

2）對于海量視頻數據，需要構建索引來加快查詢，如何設計索引結構。

2 數據建模與查詢

實時視頻本身具有時間、地點的屬性，在對這些視頻數據進行查詢時，需要查詢某個時間段內某個區域的視頻。在以鍵值對方式存儲文件時，為支持基于地理區域和時間區間的查詢，定義鍵時需要將這兩種因素考慮在內。此外，由于同一時間可能有多個設備對同一區域進行監控，因此若僅考慮地理區域和時間因素設計的鍵不具有唯一性，此時，需另外考慮設備ID號。因此本文對視頻數據以鍵值對方式進行建模，具體如下：

＜key，value＞=＜設備ID號+地理區域+時間區間，視頻文件的物理存放地址＞

其中，設備ID號是把各種不同設備的標識號映射為長度固定的標識號；地理區域為矩形區域對角點的坐標，即（(x1，y1)，(x2，y2)）；時間區間為［起始時間，結束時間］，時間以“年月日時分秒”來表示。

例1。對于某設備，假定其映射后得到的設備標識號為000001，其在2016年8月8日的16：00：00到 16：10：00分之間對區域（（385，691），（387，689））進行拍攝，所形成的視頻文件的key表示為“000001385691387689201608081600002016080816 1000”。

由例1可以看到，該key的長度較長，為提高查詢效率，需對key進行壓縮，縮短其長度。對于接收的監控視頻，當緩存中視頻流達到規定的最大長度限制k時，會創建一個文件將其寫入硬盤。因此，每個視頻文件的時長較短。假定一個視頻文件的時長不超過10min，則時間區間可表示為（起始時間，時間長度），其中時間長度位數為三位，最大取值為600（10min×60s/min）。例1中視頻文件的key經壓縮后可表示為“00000138569138768920160808160000600”，縮短了11位。

基于定義的存儲模型，面向海洋監控視頻的查詢定義為：給定一個地理區域s，查詢該區域內包含時間段（t1，t2］之間監控內容的視頻文件。

在查詢某個時間段內某個區域的視頻文件時，要從key中抽取出表示地理區域和時間區間的子串，判斷是否與查詢條件中的區域和時間段有重疊。假定一個查詢，查找時間段2016年8月8日15：45：00到2016年8月8日16：05：00之間在區域（（386，690），（389，688））內拍攝的視頻文件。首先判斷區域（（386，690），（389，688））與key中第7到18位所代表的區域（（385，691），（387，689））是否有重疊；若重疊，則繼續判斷時間區間［2016-08-08 15：45：00，2016-08-08 16：05：00］與key中第19到35位所代表的時間區間是否有重疊。若時間區間也重疊，則返回該視頻文件作為結果。

3 RB-Tree索引

在本文所定義的查詢中，若視頻文件的最大和最小時間點至少有一個位于查詢聲明的時間區間中，且視頻對應矩形監測區域的四個頂點坐標中至少有一個位于查詢聲明的地理區域中，則屬于滿足條件的查詢結果。在傳統的鍵值對＜key，value＞存儲模型中，為了加快key的查找，常常在key上構建B+Tree索引。在B+Tree中，葉子節點中對象取值為其父節點定義的取值范圍內的值。在本文中，每個視頻文件對應一個時間區間，因此要對B+Tree進行修改，構建類B+Tree，其與B+Tree的區別在于葉子節點中對象的值是一個時間區間。對于地理區域的查詢，屬于空間查詢，B+Tree并不適用。此時需考慮利用R-Tree來構建索引。在R-Tree中，每個節點對應存儲一個矩形地理區域中所有對象的指針，若某非葉結點的孩子節點是非葉節點，則其所有孩子節點代表的矩形地理區域均包含在該節點對應的地理區域中。

對于海量視頻數據來說，單純考慮修改B+Tree對時間范圍進行索引或利用R-Tree對地理區域進行索引，雖然在一定程度上可以提高查詢效率，但仍有提升空間。因此，本文提出一種混合索引樹RB-Tree，使得其可以對時間范圍和地理區域同時進行索引，提高查詢效率。

3.1 RB-Tree索引的構建

由于地理區域是固定不變的，可以考慮把地圖以面積為s的矩形進行劃分，每個矩形塊對應的區域稱之為單位地理區域。在構建RB-Tree時，以單位地理區域為最小矩陣區域，構建R-Tree。與傳統R-Tree不同的地方在于，每個視頻文件并不直接作為矩陣區域中的對象。為支持基于時間區間的快速查詢，對每個單位地理區域，為區域內所有視頻文件構建類B+Tree，R-Tree中各節點僅包含對應地理區域中類B+Tree根節點的指針。構建類B+Tree時，把若干連續時間的視頻文件作為對象集，并以這些視頻所在的時間區間作為標識創建葉子節點，然后自底向上依次創建上層節點。至此，完成RB-Tree的構建。下面給出RB-Tree的定義：

定義 1（RB-Tree）：一棵樹是 RB-Tree，需具有以下特征：

1）樹中節點包含的對象是一棵類B+Tree；

2）類B+Tree中每個節點對應一個時間區間，非葉子節點包含時間區間內的n個時間點，存在指針分別指向每個時間點之前和之后的時間區間對應的節點；

3）類B+Tree中每個葉子節點包含一個對象集，對應位于指定時間區間的所有視頻文件的key及其物理地址。

RB-Tree的具體構建算法如下：

1）把視頻文件分組，位于相同單位地理區域的視頻文件分為一組，當某視頻文件的地理區域跨越多個單位地理區域時，將其放入多個對應分組中；

2）對步驟1）得到的每個分組中視頻文件再次進行分組，使得每組包含m個視頻文件（最后一組包含小于等于m個）；

3）為每組視頻文件創建葉子節點，節點把能夠包含組內視頻文件對應時間區間的最小時間區間作為標識，節點中包含指向各視頻文件的指針；

4）葉子節點根據時間先后順序用指針進行關聯；

5）把節點按其時間范圍排序，以相鄰m個為一組進行分組，對應每組創建一個父親節點，把包含分組內節點對應時間區間的最小時間區間作為父親節點的標識，以各孩子節點時間區間的最大邊界值形成時間點集合T；

6）在集合T中任意兩個相鄰時間點之間創建一個指針，指向時間區間在兩個時間點之間的孩子節點；

7）對于集合T最鄰近所屬節點時間區間最大和最小邊界值的兩個時間點，分別創建指向時間區間在邊界值和相鄰時間點之間的節點的指針；

8）以5）中創建的節點為孩子，構建上層父節點，使得每個父節點的孩子個數為m（同一層中最后一個節點的孩子數小于等于m），若新創建的節點個數大于1，轉5），否則，轉9）；

9）為每個單位地理區域創建一個節點，節點中包含指向該區域中的類B+Tree根節點的指針，并記錄每個根節點對應的時間區間。

10）以存在公共交點的相鄰m′個單位地理區域為單元，創建上層節點，直至完成R-Tree的構建。其中，非葉節點包含指向孩子節點的指針及其對應的地理區域。

值得注意的是，在查詢某地理區域內位于某時間區間的視頻文件時，既可以先基于地理區域進行條件過濾，也可以先基于時間區間進行條件過濾。由RB-Tree的構建可以看到，本文傾向于先基于地理區域進行條件過濾。這樣做是因為地理區域是固定不變的，而時間是一直變化的。若先基于時間區間構建類B+Tree，再對葉子節點中包含的對象構建R-tree，則需頻繁構建新的R-Tree。而先基于地理區域構建R-Tree，則每次只需對若干個B+Tree進行插入節點的操作，而對多個B+Tree進行插入操作更易并行化，從而加快更新速度。

在RB-Tree中，類B+Tree的每一層之所以都僅有一個節點包含的指向孩子節點或視頻文件的指針數量小于等于m，是因為在RB-Tree中不存在修改和刪除操作，僅隨時間推移而不斷插入新的對象，在后續章節會詳細介紹RB-Tree的更新。

3.2 RB-Tree索引的查詢

在進行查詢時，由于不關心設備ID號，僅以地理區域和時間區間為查詢條件，且在RB-Tree構建過程中，地理區域是基于單位地理區域進行劃分的，因此，構建樹的過程中僅需考慮key中時間區間相關的部分。基于RB-Tree的查詢算法具體如下：

1）根據查詢條件中給定的地理區域s，從RB-Tree根節點開始，逐層向下，尋找與s有重疊的子節點，直至葉子節點為止；

2）檢索葉子節點中記錄的各個類B+Tree的時間區間，根據指向類B+Tree的指針獲取特定的類B+Tree的根節點；

3）對于查詢條件中給定的時間區間（t1，t2］，依次把t1、t2與節點包含的時間點集中各時間點進行比較，找出所有與時間區間（t1，t2］有重疊的下層孩子節點，若孩子節點是非葉節點，轉3），否則，轉4）；

4）順序讀取節點中包含的key，判斷該key對應的時間區間是否與（t1，t2］有重疊，若重疊，則根據key對應的value返回視頻文件。

3.3 RB-Tree索引的更新

監控視頻文件隨時間不斷增加，不存在修改或刪除，因此只需考慮增加新的視頻文件后如何進行RB-Tree的更新。RB-Tree包含R-Tree和類B+Tree，插入新的視頻文件會引起類B+Tree葉子節點的更新，該更新會逐層向上傳遞，直至類B+Tree的根節點。

在RB-Tree中，類B+Tree的非葉節點至多包含m個孩子，當某節點隨時間推移插入的孩子節點達到m時，在此插入會導致新的非葉節點的創建。RB-Tree索引的更新算法如下：

1）新增一個視頻文件時，根據其所屬單位地理區域找到相應的類B+Tree；

2）找到類B+Tree中與插入的視頻文件時間區間最接近的葉子節點i；

3）若節點i中對象個數小于m，則更新對應葉子節點信息，插入該視頻文件的指針；

（1）更新其父節點中對應該節點的時間區間，若父節點為根節點，轉2），否則，以其父節點作為當前節點，轉1）；

（2）更新RB-Tree中指向該類B+Tree根節點的葉子節點中對應的時間區間，停止；

4）若節點i中對象個數等于m，創建新的葉子節點o，記錄指向新增的視頻文件的指針，并令其時間區間為新增視頻文件對應的時間區間；

（1）在上層節點中尋找時間區間與節點o最接近的節點p；

（2）若節點p中孩子節點個數小于m，則為其添加指向節點o的指針，把p的時間區間最大邊界值作為新的時間點插入現有時間點集中并更新p時間區間，令o的時間區間最大邊界值作為p的時間區間的最大邊界值，否則，轉（3）；

（3）創建新的節點q，添加指向o的指針，并更新q的時間區間為o的時間區間；

（4）若p不是根節點，轉（1），否則，創建新的根節點r，令p、q為其孩子節點，添加時間區間和時間點集，并更新RB-Tree葉子節點中指向被更新的類B+Tree的時間區間和地址指針，停止。

4 RB-Tree索引查詢代價分析

為了便于進行查詢代價的分析，本節首先定義如表1所示符號。

表1

在RB-Tree中，葉子節點僅包含指向類B+Tree根節點的指針，磁盤中每次獲取節點需要讀取至少一頁的數據，故當葉子節點中指針數量為「Spage/（ST+Sadd）?時，可以最大程度減少I/O次數。對于非葉節點，除了包含指向其孩子節點的指針外，還包含表示各孩子節點對應的地理區域，因此，當非葉節點包含的孩子節點數量為「Spage/（Sarea+Sadd）?時，可以最大程度減少I/O次數。假定總的葉子節點數量為n，當僅需訪問一個目標葉子節點時，從RB-Tree的根節點開始查找葉子節點，樹中每層均需訪問一個節點，需要I/O的次數為

對于RB-Tree葉子節點所指向的類B+Tree，其葉子節點包含指向視頻文件的指針以及對應視頻文件的key，故當葉子節點中指針數量為「Spage/（Skey+Sadd）?時，可以最大程度減少I/O次數。對于非葉節點，除了包含指向其孩子節點的指針外，還包含一個覆蓋全部孩子節點時間區間的時間區間以及一個時間區間內的時間點集合，時間點集合中時間點的數量為孩子節點數量減一，故當非葉節點包含的孩子節點數量為「（Spage-ST-Sadd）/（St+Sadd）?時，可以最大程度減少I/O次數。在RB-Tree的葉子節點中，假定一棵類B+Tree的葉子節點數量為n′，順序讀取每棵類B+Tree對應的時間區間，當僅需訪問一個類B+Tree中的葉子節點時，從類B+Tree的根節點開始查找葉子節點，樹中每層均需訪問一個節點，需要I/O的次數為

因此，一次查詢需要的I/O的次數為

在上述RB-Tree中，一棵類B+Tree中包含的視頻文件最多有n′×「Spage/（Skey+Sadd）?個，一個RB-Tree中包含的類B+Tree最多有n×「Spage/（ST+Sadd）?個，故一棵RB-Tree中總的視頻文件最多有N=n′×「Spage/（Skey+Sadd）?×n×「Spage/（ST+Sadd）?個。

在最壞情況下，每個RB-Tree葉子節點均包含指向同一時間區間的類B+Tree。若僅用類B+Tree對數據進行索引，葉子節點對應的視頻文件數為n×n′×「Spage/（Skey+Sadd）?，共有N′=「N/（n×n′×「Spage/（Skey+Sadd）?）?個葉子節點，則需要I/O的次數為

根據RB-Tree中葉子節點包含的類B+Tree的數量「Spage/（ST+Sadd）?、每個類B+Tree中包含的視頻文件數量「Spage/（Skey+Sadd）?以及葉子節點的數量n′，

若僅用R-Tree對數據進行索引，共有N′=「N/（「Spage/（ST+Sadd）?×「Spage/（Skey+Sadd）?×n′）?個葉子節點。若訪問某個葉子節點中的視頻文件，則需要I/O的次數為可知RB-Tree中每個葉子節點對應包含的視頻文件數量為

在進行查詢時，由于需要同時考慮地理區域和時間區間兩個條件，在利用類B+Tree進行檢索時，若位于同一時間區間內的視頻文件數過多，會使得獲取一個葉子節點中所有數據需要多次I/O操作，使得查詢效率下降。在利用R-Tree進行檢索時，若位于同一地理區域內的視頻文件數過多，也會使得獲取一個葉子節點中所有數據需要多次I/O操作，使得查詢效率下降。通過本章節提出的I/O代價計算公式，可以算出當視頻數據數量多大規模時，利用RB-Tree可以顯著提高查詢效率。

5 結語

本文討論了海量海洋監控視頻的建模存儲，并提出一種索引結構RB-Tree來提高視頻檢索的效率。文中對RB-Tree的查詢復雜度進行深入分析，在此基礎上，對在何種情況下利用該索引可以有效提高查詢效率進行了探討。

本文主要從理論層面分析了利用RB-Tree進行索引查詢的復雜度，下一步，將結合具體的硬件對其查詢效率進行深入的分析。

［1］李尉尉，王慧祺，夏登文，等.中國海洋調查船現狀及發展思考［J］.海洋開發與管理，2012，29（5）：41-43.LI Weiwei，WANG Huiqi，XIA Dengwen，et al.Reflections on the Status Quo and Development of Chinese Marine Survey Vessels［J］.Ocean Development and Management，2012，29（5）：41-43.

［2］劉健中，管義鋒.大洋綜合資源調查船全船結構強度有限元分析［C］//船舶與海洋結構學術會議暨中國鋼結構協會海洋鋼結構分會成立三十周年紀念學術會議.長沙：中國造船工程學會，中國鋼結構協會，2015：178-185.LIU Jianzhong，GUAN Yifeng.Whole Structure Strength Analysis of Oceanographic Research Vessel［C］//Conference on Ship and Ocean Structure and the 30th Anniversary Conference of China Steel Structure Association.Changsha：China Shipbuilding Engineering Society，China Steel Construction Society，2015：178-185.

［3］孟小峰，慈祥.大數據管理：概念、技術與挑戰［J］.計算機研究與發展，2013，50（1）：146-169.MENG Xiaofeng，CI Xiang.Big Data Management Concepts，Techniques and Challenges［J］.Journal of Computer Research&Development，2013，50（1）：146-169.

［4］Ghemawat S，Gobioff H，Leung S T.The Google file system［C］//ACM Symposium on Operating Systems Principles.New York：ACM，2003：29-43.

［5］Li Y，Manoharan S.A performance comparison of SQL and NoSQL databases［C］//Pacific Rim Conference on Communications，Computers and Signal Processing.Washington D C：IEEE Computer Society，2013：15-19.

［6］Chen M，Mao S，Liu Y.Big data：a survey［J］.Mobile Networks and Applications，2014，19（2）：171-209.

［7］Han J，Haihong E，Le G，et al.Survey on NoSQL database［C］//International Conference on Pervasive computing and applications.Washington D C：IEEE Computer Society，2011：363-366.

［8］He C.Survey on NoSQL Database Technology［J］.Journal of Applied Science and Engineering Innovation，2015，2（2）：50-54.

［9］Sharma V，Dave M.SQL and NoSQLDatabases［J］.International Journal of Advanced Research in Computer Science and Software Engineering，2012，2（8）：20-27.

［10］Hadjieleftheriou M，Manolopoulos Y，Theodoridis Y，et al.Encyclopedia of GIS［M］.US：Springer，2008：993-1002.

［11］Chen S，Gibbons P B，Mowry T C，et al.Fractal prefetching B+-Trees：optimizing both cache and disk performance［C］//ACM SIGMOD International Conference on Management of Data.New York：ACM，2002：157-168.

An Index for Ocean Surveillance Video

TIAN Chiying
（China Ocean Mineral Resources Research and Development，Beijing 100860）

The value of data which is considered as a kind of asset has become more and more important.Storing collected data for subsequent analysis and mining has great significance.In this paper，a storage scheme to meet the query requirement for massive ocean surveillance video is proposed.Propose the index RB-Tree to realize fast query over massive data is also proposed.Besides，the paper theoretically analyzes the time cost of query.The query cost of the RB-Tree with the traditional B+Tree and R-Tree to indicate our advantage on massive ocean video data is furtherly compared.

massive ocean video data，surveillance video，B+Tree index，R-Tree index，RB-Tree index

X85

10.3969/j.issn.1672-9722.2017.11.032

Class Number X85

2017年5月21日，

2017年6月27日

田赤英，女，研究員，研究方向：船載信息系統。