楊婷婷+賈樹(shù)文

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

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

doi：10.3969/j.issn.1673 - 0194.2017.14.079

[中圖分類號(hào)]TP399 [文獻(xiàn)標(biāo)識(shí)碼]A [文章編號(hào)]1673-0194（2017）14-0-02

1 研究背景

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

2 MapReduce簡(jiǎn)介

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

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

3 MapReduce問(wèn)題描述

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

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

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

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

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

迭代的圖像計(jì)算處理流程如下。

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

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

第二步，通過(guò)MPI_Alltoall（）實(shí)現(xiàn)各個(gè)節(jié)點(diǎn)間所需信息的交換，每個(gè)節(jié)點(diǎn)把自己所需要的信息交換到后，各個(gè)節(jié)點(diǎn)自行計(jì)算和申請(qǐng)接受信息所需要的存儲(chǔ)空間；

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

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

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

（3）對(duì)生成key/value list進(jìn)行排序：sort

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

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

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

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

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

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

5 結(jié) 語(yǔ)

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

主要參考文獻(xiàn)

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

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

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

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