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

楊婷婷+賈樹文

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

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

doi：10.3969/j.issn.1673 - 0194.2017.14.079

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

1 研究背景

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

2 MapReduce簡介

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

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

3 MapReduce問題描述

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

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

4 基于MapReduce的圖像匹配算法的設(shè)計實現(xiàn)

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

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

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

（1）圖像信息計算數(shù)據(jù)的交換：

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

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

在每個節(jié)點內(nèi)將Map生成的鍵值對按鍵值進行排序。

第四步，每個子圖將自己的邊界頂點發(fā)送給其所連接的鄰居節(jié)點，采用MPI-Alltlall（）實現(xiàn)，調(diào)用MPI_Alltoallv（），將發(fā)送緩存中的數(shù)據(jù)發(fā)往各節(jié)點。

（2）計算1th/2：map。將子圖graph和接受緩沖區(qū)中的數(shù)據(jù)實例化為頂點Vertex，再調(diào)用業(yè)務(wù)邏輯函數(shù)Map，將頂點Vertex生成key/value list。

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

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

（5）將Reduce計算的結(jié)果更新到graph中。根據(jù)鍵值，對鍵值相同的鍵值組執(zhí)行Reduce函數(shù)

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

切圖（non-mandatory）為兼容非圖結(jié)構(gòu)的MapReduce計算，框架為了能夠同時支持非圖結(jié)構(gòu)數(shù)據(jù)的MapReduce計算，需要在函數(shù)Map與Reduce之間實現(xiàn)除局部排序之外的全局排序。

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

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

5 結(jié) 語

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

主要參考文獻

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

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

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

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