分布式高維度多媒體對象匹配算法的研究

楊婷婷+賈樹文

[摘 要]在解決高維度多媒體對象匹配效率問題時，僅僅依靠提高處理器的處理能力和單個計算機的數量來提高指紋匹配效率，勢必會引起成本的巨額增加，并大大降低了靈活性和擴展性。為了解決這個問題，本文提出利用分布式的方式，實現從連續的K幀中提取相聯系指紋的并行處理方式，這樣指紋匹配的任務會被分散到一個個分布式的環境中，使匹配能夠在不同的機器上并行，從而提高視頻指紋匹配的效率。

[關鍵詞]分布式匹配引擎；多媒體；視頻指紋匹配；云計算

doi：10.3969/j.issn.1673 - 0194.2017.14.079

[中圖分類號]TP399 [文獻標識碼]A [文章編號]1673-0194（2017）14-0-02

1 研究背景

隨著數字視頻的爆炸性增長，加上視頻處理軟件的增多，導致復制和盜版者可以很輕松地對視頻進行任意處理，嚴重影響版權所有者的利益。同一視頻資源經過復制或是盜版會出現各種各樣的拷貝視頻，當需要檢索一個數字視頻時，會出現大量與之相似的視頻，這不僅影響了查詢所需視頻的檢索時效，也是對視頻原創者的不尊重。雖然最早用于防偽技術的數字水印技術，通過在視頻中預先插入設計好的數字水印，以起到防偽和拷貝檢測的作用，但隨著網站視頻被復制和轉載數量的急劇增加，數字水印的認證精度無法得到保證，且在視頻中插入數字水印的成本過高，且易被破壞，不合適個人用戶進行使用。尤其是在云計算環境下，使用者通過對原視頻多種方式的變換后，如添加、嵌入、自由裁切，以及對視頻的外觀、色彩、對比度、灰度等進行修改，就可以獲得多個類似視頻的版本，且變換的方式還有很多種，還可以不同的變換方式進行疊加，這些都給視頻的拷貝檢測及匹配帶來了難度，單純通過單一檢測匹配方式是很難完成視頻原創性的檢測和鑒定的，在云計算環境下，為了解決高維度多媒體對象檢測匹配效率的問題，本文提出通過利用分布式的方式，實現檢測匹配效率的提高，利用分布式架構模型MapReduce解決高維度多媒體對象匹配效率問題，從而提高視頻指紋匹配速度和準確度，并降低成本。

2 MapReduce簡介

MapReduce是一種編程模型，可用于大規模的算法圖形并行處理。具體工作思想是：通過指定一個Map（映射）函數，以把一組鍵值對映射成一組新的鍵值對，并指定并發的Reduce（歸約）函數，以保證所有映射的鍵值對中的每一個共享相同的鍵組。其中，Map的操作是可以高度并行的，這對完成高維度的匹配非常關鍵。簡單的理解其工作原理就是，將一些大規模的處理任務分解成許多較小的處理任務，并分散到不同的計算節點上，然后對計算處理的結果進行匯總，從而得到最終想要的結果。將計算任務分散到節點上能夠充分利用數據本地性的優勢。

在MapReduce程序中通過自定義圖像接口ImageInputFormat ImageRecordReader，實現基于MapReduce的大量圖像的在線并行處理。目前，MapReduce可處理的圖像格式還比較少，主要處理的常見圖片格式為bmp、jpg、png等。MapReduce有兩個基本的運算單元Map和Reduce，即通過作業的提交、Map任務的分配和執行、Reduce任務的分配和執行、作業的完成四個過程，實現對圖像的分布式處理。其具體的工作流程如圖1所示。

3 MapReduce問題描述

云安全環境下的多媒體內容檢測是多媒體數據庫中的一項重要應用，在進行多媒體內容檢測時，需要提取的特征向量大都是具有高維度的特性，傳統的索引結果模式不能很好地實現高維度的匹配，基于此，本文提出分布式高維度多媒體對象匹配引擎的設計，這里采用MapReduce來實現。在云安全環境下，將云計算技術引入批量圖像處理領域，不僅充分利用了云端的計算和存儲優勢，還可以極大地提高圖像的處理速度，便于高效地實現分布式高維度多媒體對象的匹配，并能很好地降低圖像的計算成本和存儲成本。MapReduce是為大規模處理圖像而設計開發的，只是用MapReduce處理單個的小圖像體現不出它的優勢，只有用MapReduce處理海量的圖像（至少GB級別以上）時效果明顯，其本身分布式處理的優勢才能體現出來。

MapReduce編程模型目前所采用的圖像輸入格式有兩種：一種是普通圖文件格式：from_vid to_vid這種輸入圖格式，在運行程序時需要選擇“random”的partition方式（分圖方式）。程序的各個進程將會并行且均分讀取文件的相應部分；另一種是metis輸出的子圖格式，為了將全圖的不同部分放到不同的計算節點上進行并行計算，需要將原圖劃分為若干子圖。劃分工具采用開源的Parmetis進行，Parmetis是基于MPI進行大規模的子圖劃分。MapReduce本身所帶的數據格式是不能被直接用來進行大規模圖像處理的，它能夠處理的圖像文件有兩種：一是將要處理的圖像信息進行預處理后，轉換成MapReduce數據能夠識別的二進制串數據；另外一種是通過自定義處理圖像文件接口方式，實現大批量圖像信息的處理。基于MapReduce的圖像處理能夠實現從連續的K幀中提取相聯系指紋的并行處理方式，這樣指紋匹配的任務會被分散到一個個分布式的環境中，使匹配能夠在不同的機器上并行，從而能夠提高視頻指紋匹配的效率。

4 基于MapReduce的圖像匹配算法的設計實現

在解決高維度多媒體對象匹配效率問題時，僅僅依靠提高處理器的處理能力和單個計算機的數量來提高指紋匹配效率，勢必會引起成本的巨額增加，并大大降低靈活性和擴展性，這也是傳統圖像處理算法的弊端，基于MapReduce的圖像處理算法能夠實現分布式圖像處理，充分利用圖像處理數據的本地性特點，實現圖像高處理速度和大規模圖像的分布式高效化處理。

基于MapReduce的圖像處理主要通過Map函數和Reduce函數的功能實現，MapReduce需要把輸入的圖像信息分成大小相同的數據分片（一般為128 M），并為這些大小相同的分片分別構造一個Map任務，Map（）函數以key/value對（k1，v1）作為圖像信息的輸入，從而會產生另外一系列key/value對（k2，v2），這就是處理過程中的輸出會被保存到本地磁盤，在shuffle階段這些Map的數據輸出（k2，v2）能夠按照k2值進行聚集生成[k2，{v2，…}]，然后MapReduce程序統一將這些聚集生成的數據交給Reduce（）函數處理。Reduce（）函數把k2和聚集生成的對應列表{v2，…}當做輸入，然后把輸入中的每個k2和對應列表中的v2值進行合并，產生另外的一系列數據key/value對（k3，v3），新產生的這些數據最終會被寫入到HDFS中。使用者只需要做好Mapper和Reducer這兩類工作，就能完成分布式圖像處理的程序設計。endprint

迭代的圖像計算處理流程如下。

（1）圖像信息計算數據的交換：

第一步，Map函數階段需先遍歷需要計算的子圖graph與其他相鄰子圖的圖像信息情況，同時需要收集向其他節點發送的信息，并保存到本地磁盤；

第二步，通過MPI_Alltoall（）實現各個節點間所需信息的交換，每個節點把自己所需要的信息交換到后，各個節點自行計算和申請接受信息所需要的存儲空間；

在每個節點內將Map生成的鍵值對按鍵值進行排序。

第四步，每個子圖將自己的邊界頂點發送給其所連接的鄰居節點，采用MPI-Alltlall（）實現，調用MPI_Alltoallv（），將發送緩存中的數據發往各節點。

（2）計算1th/2：map。將子圖graph和接受緩沖區中的數據實例化為頂點Vertex，再調用業務邏輯函數Map，將頂點Vertex生成key/value list。

（3）對生成key/value list進行排序：sort

（4）計算2th/2：reduce。將排序好的key/value list按照業務邏輯函數Reduce進行。

（5）將Reduce計算的結果更新到graph中。根據鍵值，對鍵值相同的鍵值組執行Reduce函數

（6）對Reduce的結果進行排序，并對迭代計算的結束條件進行判斷，如果計算完畢即可給出結果，否則返回到相鄰數據交換處繼續執行迭代計算。

切圖（non-mandatory）為兼容非圖結構的MapReduce計算，框架為了能夠同時支持非圖結構數據的MapReduce計算，需要在函數Map與Reduce之間實現除局部排序之外的全局排序。

圖結構的MapReduce計算和非圖結構的MapReduce計算在計算步驟上并不一樣，其中，圖結構計算步驟為：開始→分圖→鄰居數據交換→局部Map、SortReduce-Reduce結果更新→判斷迭代結束條件，如果判斷結果為未結束，則返回到鄰居數據交換階段→結束。非圖結構計算步驟為：開始→數據分割→Map→全局Sort、Shuffle→Reduce→判斷迭代結束條件，如果判斷結果為未結束，則返回到Map階段→結束。

實驗證明，通過MapReduce程序能夠很好地實現分布式高維度對象的匹配，雖然研究中還有很多問題沒有解決，比如，搜索算法的使用效率問題、并行廣度優先搜索算法的MapReduce實現問題等，但筆者會在以后的研究中逐步進行解決。

5 結 語

隨著信息時代的到來，多媒體數據將會呈現爆炸性的增長，尤其是視頻數據的增加，像3D視頻在生活中的地位越來越高，這對知識產權的保護提升到很高的地位、如何更好地保護視頻原創者的權益、如何更好地檢測和匹配出視頻的不同，都是需要重點研究的內容。對于如何更好地捕獲三維視頻圖像的深度，更好地對檢測的三維視頻圖像進行匹配，本文雖然提出了基于分布式的高維度多媒體對象匹配方式，通過研究證明，分布式的視頻檢測匹配是可行的，需要在此方面進行更加深入的研究；但是具體的應用還有很長的路要走，尋找魯棒性更好、匹配效率更高的方式和高維度索引算法，將會成為視頻產權保護的重要保證措施。

主要參考文獻

[1]李振舉，李學軍，劉濤，等.MapReduce編程模型及其在圖像處理中的應用研究綜述[J].測繪與空間地理信息，2015（4）.

[2]譚臺哲，向云鵬.Hadoop平臺下海量圖像處理實現[J].計算機工程與設計，2017（4）.

[3]張興忠，李皓，張三義.基于關鍵幀多特征融合的視頻拷貝檢測[J].太原理工大學學報，2015（5）.

[4]開源中國社區.基于MapReduce編程模型的圖計算框架[EB/OL].（發表時間不詳）[2017-05-03].http：//git.oschina.net/wdfnst/GraphMapReduce.endprint