楊 曼，何 鵬，齊懷琴，安井然

（齊齊哈爾大學(xué) 通信與電子工程學(xué)院，黑龍江 齊齊哈爾 161006）

基于Map/Reduce的海量視頻圖像檢索系統(tǒng)設(shè)計(jì)

楊 曼，何 鵬，齊懷琴，安井然

（齊齊哈爾大學(xué) 通信與電子工程學(xué)院，黑龍江 齊齊哈爾 161006）

齊齊哈爾市公安視頻監(jiān)控系統(tǒng)中每天所產(chǎn)生的大量視頻數(shù)據(jù)對(duì)視頻圖像的檢索、管理及安全產(chǎn)生了迫切的需求，視頻圖像的檢索存在兩個(gè)急需解決的問(wèn)題，一是視頻檢索的準(zhǔn)確度問(wèn)題，二是檢索效率的問(wèn)題。面對(duì)海量的視頻數(shù)據(jù)庫(kù)，提出了基于Map/Reduce分布式計(jì)算模型與關(guān)鍵幀算法結(jié)合的方法，既提高了檢索效率，又提高了檢索準(zhǔn)確率。

Map/Reduce；關(guān)鍵幀；視頻檢索

近年來(lái)，視頻監(jiān)控系統(tǒng)在公安、交通、銀行等重要領(lǐng)域大規(guī)模應(yīng)用，尤其在公安監(jiān)控領(lǐng)域扮演著必不可缺的重要角色。通過(guò)視頻監(jiān)控系統(tǒng)打擊違法犯罪行為屢見(jiàn)不鮮。然而隨著攝像頭的增加，產(chǎn)生的視頻數(shù)據(jù)也呈爆炸式上漲。如果以一個(gè)普通攝像頭進(jìn)行錄像為例，一小時(shí)視頻存儲(chǔ)容量大小約為150 Mbyte，連續(xù)錄12 h則數(shù)據(jù)儲(chǔ)存量將達(dá)1.8 Gbyte，齊齊哈爾市約有2 500個(gè)攝像頭，視頻數(shù)據(jù)保存的周期一般約為15天，經(jīng)過(guò)計(jì)算得知，在視頻存儲(chǔ)的周期中約產(chǎn)生1 320 Tbyte的數(shù)據(jù)，然而特殊的情況之下視頻數(shù)據(jù)量可達(dá)到PB級(jí)。

在實(shí)際應(yīng)用的過(guò)程中，工作人員希望可以快速準(zhǔn)確地從這些海量數(shù)據(jù)中找到所需要的圖像。然而傳統(tǒng)的視頻存儲(chǔ)對(duì)服務(wù)器的容量有很高的要求，這使得監(jiān)控系統(tǒng)的造價(jià)增加。傳統(tǒng)的基于時(shí)間的視頻檢索[1]方式，面對(duì)視頻特殊的非結(jié)構(gòu)化數(shù)據(jù)以及日益增長(zhǎng)所形成的龐大的視頻數(shù)量，對(duì)于海量視頻數(shù)據(jù)的挖掘往往無(wú)能為力，因此如何快速準(zhǔn)確地進(jìn)行智能檢索就成為大型視頻監(jiān)控系統(tǒng)急需解決的重要課題。

針對(duì)海量視頻中提高檢索的準(zhǔn)確度和效率問(wèn)題，本文采用計(jì)算幀運(yùn)動(dòng)量的方法對(duì)監(jiān)控視頻進(jìn)行分類，去掉冗余視頻數(shù)據(jù)，提取有運(yùn)動(dòng)目標(biāo)的視頻，采用SIFT算法對(duì)視頻進(jìn)行關(guān)鍵幀[2]特征計(jì)算，將提取的關(guān)鍵幀存入數(shù)據(jù)庫(kù)，將視頻存入分布式文件系統(tǒng)（HDFS）中，將Map/Reduce分布式計(jì)算模型應(yīng)用于關(guān)鍵幀提取的檢測(cè)算法中。這樣既解決了海量視頻的存儲(chǔ)容量問(wèn)題，通過(guò)Map/Reduce編程模型與關(guān)鍵幀的提取又提高了檢索效率與準(zhǔn)確度，有助于監(jiān)控人員實(shí)時(shí)檢索視頻信息，盡快找到所需數(shù)據(jù)。

1 系統(tǒng)總體設(shè)計(jì)

首先將視頻序列分割[3]為若干個(gè)鏡頭序列，然后在各個(gè)鏡頭序列中找到若干個(gè)關(guān)鍵幀，視頻序列被結(jié)構(gòu)化之后，提取各關(guān)鍵幀的視覺(jué)特征（紋理、顏色、形狀等），存入特征數(shù)據(jù)庫(kù)中；用戶可以通過(guò)相似性匹配模塊查詢，在視頻數(shù)據(jù)庫(kù)中尋找相符合的圖像。由于視頻監(jiān)控存儲(chǔ)容量大，采用Hadoop架構(gòu)，將視頻存儲(chǔ)在分布式文件系統(tǒng)，關(guān)鍵幀存于分布式的、面向列的開(kāi)源數(shù)據(jù)庫(kù)（HBase）中。系統(tǒng)結(jié)構(gòu)如圖1所示。

圖1 系統(tǒng)結(jié)構(gòu)

2 視頻圖像關(guān)鍵幀的提取

現(xiàn)如今，關(guān)鍵幀技術(shù)主要應(yīng)用在視頻內(nèi)容檢索上。關(guān)鍵幀能反映出視頻內(nèi)容的主要信息，由于視頻信息的復(fù)雜性，一般一段視頻信息會(huì)包含多個(gè)關(guān)鍵幀。關(guān)鍵幀是靜態(tài)圖像，但能反映監(jiān)控視頻中的動(dòng)態(tài)變化。在公安偵查過(guò)程中，往往包含犯罪嫌疑人體貌和行為特征，車輛的外形特征圖像作為關(guān)鍵幀。目前在提取視頻關(guān)鍵幀上有很多方法，但是每種方法都有自己適用的范圍。針對(duì)固定攝像機(jī)拍攝監(jiān)控視頻的特性，不只希望可以看到運(yùn)動(dòng)信息，更希望看到運(yùn)動(dòng)過(guò)程。結(jié)合監(jiān)控視頻特性，本文采用基于圖像顏色特征，計(jì)算圖像顏色直方圖，比較相鄰幀相似性來(lái)提取關(guān)鍵幀。

2.1 運(yùn)動(dòng)檢測(cè)

從一段大小為p×q視頻中提取背景圖公式如下

式中：B（x，y）為得到的背景圖；Fi（x，y）為視頻中任意一幀。

2.2 視頻分段

很顯然，幀運(yùn)動(dòng)量范圍在0到1之間。設(shè)Dt表示t時(shí)刻對(duì)應(yīng)的灰度視頻圖像，幀運(yùn)動(dòng)量設(shè)為Mt。

根據(jù)判斷Mt的大小來(lái)對(duì)視頻進(jìn)行分類

針對(duì)上述問(wèn)題，本文提出將視頻按照幀運(yùn)動(dòng)量大小分為3類，對(duì)視頻中的當(dāng)前幀進(jìn)行標(biāo)記，類別符號(hào)記為Si，i取0，1，2這3個(gè)整數(shù)，分別為

顏色直方圖表示將光譜顏色量化后，每一個(gè)顏色范圍中所包含的圖像像素個(gè)數(shù)[4]。顏色直方圖能夠直觀表示出圖像中顏色分布的顏色特征，描述不同顏色在圖像中所占的比例。顏色直方圖適用于所有的圖像，對(duì)于單色圖像，可以計(jì)算出灰度直方圖，對(duì)于彩色圖像，可以對(duì)每一個(gè)通道分別計(jì)算顏色直方圖。

對(duì)于兩幅相同大小的圖像Ii和Ij（Ii和Ij為相鄰兩幀），首先計(jì)算出圖像Ii和Ij顏色直方圖，然后比較前后兩幀圖像對(duì)應(yīng)點(diǎn)的像素值（p，q），求其最小值得出兩幀圖像同一點(diǎn)像素值的相似性，然后累加求和，最后計(jì)算出兩幀圖像每一個(gè)通道相似的像素點(diǎn)數(shù)占后一幀圖像該通道總像素點(diǎn)的比例。

對(duì)于彩色圖像，進(jìn)行相似度與設(shè)定閾值對(duì)比，應(yīng)用三基色RGB與d（灰度）公式

相鄰兩幀的相似性d∈（0，1]，經(jīng)多次驗(yàn)證，閾值設(shè)定為T(mén)=0.85，如果d小于設(shè)定的閾值，說(shuō)明兩幀的相似度過(guò)小，設(shè)定后一幀為新的關(guān)鍵幀。

對(duì)于灰度圖像，直接將求出的比例與設(shè)定的閾值進(jìn)行對(duì)比，判斷后幀是否為關(guān)鍵幀。

3 實(shí)驗(yàn)過(guò)程

3.1 關(guān)鍵幀提取具體步驟

1）首先對(duì)視頻A進(jìn)行背景建模，用背景差分法記錄視頻中存在運(yùn)動(dòng)物體的起始幀A1和結(jié)束幀An，取出存在運(yùn)動(dòng)物體的視頻。

2）將取出的視頻每隔25幀提取圖像作為初始關(guān)鍵幀集合。

3）在提取初始關(guān)鍵集合中將首幀A1設(shè)為關(guān)鍵幀F(xiàn)1，F(xiàn)1=A1，i=1。

4）j=i+1，計(jì)算Aj與Ai的相似性，如果得到的d小于閾值，說(shuō)明兩幀的相似性較小，設(shè)Aj為新的關(guān)鍵幀F(xiàn)2。

5）檢測(cè)到最后一幀，計(jì)算結(jié)束，顯示關(guān)鍵幀集合。

3.2 關(guān)鍵幀提取結(jié)果

在運(yùn)動(dòng)檢測(cè)的基礎(chǔ)上進(jìn)行關(guān)鍵幀算法的驗(yàn)證。對(duì)一段含有運(yùn)動(dòng)信息的監(jiān)控視頻進(jìn)行關(guān)鍵幀提取。視頻時(shí)長(zhǎng)為23 s，幀總數(shù)為347幀，文件大小為1.34 Mbyte，視頻分辨率為512×288，文件碼率464 kbit/s。圖4為初始關(guān)鍵幀集合。

圖4 初始關(guān)鍵幀集合

從上述初始關(guān)鍵幀集合中采用基于圖像顏色特征提取出的關(guān)鍵幀如圖5所示。

圖5 基于顏色特征法提取的關(guān)鍵幀

從初始關(guān)鍵幀集合中提取出來(lái)的幀分別為第1，9，12，13，14幀。從圖5可以看出，關(guān)鍵幀能夠很好地反映出物體的運(yùn)動(dòng)趨勢(shì)，并能很好地識(shí)別出物體的特征，并且關(guān)鍵幀的總占用量為117 kbyte，涵蓋了有效的信息，大大節(jié)省了存儲(chǔ)空間，便于用戶瀏覽觀看。

3.3 特征計(jì)算

將提取出的關(guān)鍵幀按照時(shí)間順序分別計(jì)算出每幀的特征，然后組織在一起，構(gòu)成視頻特征。

在特征計(jì)算上，由于在監(jiān)控視頻中主要關(guān)注運(yùn)動(dòng)物體的特征，所以本文采用SIFT特征算法[5-6]進(jìn)行特征提取。通過(guò)尺度空間的極值檢測(cè)，得出關(guān)鍵點(diǎn)。在關(guān)鍵點(diǎn)的確定過(guò)程中，對(duì)于低對(duì)比度的點(diǎn)和邊緣點(diǎn)進(jìn)行了剔除，并采用梯度直方圖來(lái)確定關(guān)鍵點(diǎn)的主方向可以使得算子具備旋轉(zhuǎn)不變性。

SIFT的特征向量由關(guān)鍵點(diǎn)鄰域梯度信息的統(tǒng)計(jì)特性實(shí)現(xiàn)。根據(jù)Lowe的方法，以關(guān)鍵點(diǎn)為中心取16×16的窗口。將其分成一些不重復(fù)的4×4的小塊，在每一個(gè)小塊中統(tǒng)計(jì)8個(gè)方向的梯度方向直方圖，繪制每個(gè)梯度方向的幅值累加值，這樣便可形成一個(gè)種子點(diǎn)，可見(jiàn)，一個(gè)特征點(diǎn)由4×4共16個(gè)種子點(diǎn)組成，每個(gè)種子點(diǎn)有8個(gè)方向的向量信息。然后將這16個(gè)種子點(diǎn)共有128個(gè)方向的向量信息，組合成一個(gè)128維的向量。

本文通過(guò)建立一個(gè)三元組來(lái)表示一個(gè)關(guān)鍵幀（視頻ID，關(guān)鍵幀ID，關(guān)鍵幀特征）。其中，視頻ID和關(guān)鍵幀ID作為Map/Reduce模型中的key值。關(guān)鍵幀的信息通過(guò)這個(gè)三元組能夠被很好地表示出來(lái)。將關(guān)鍵幀存于HBase中，而視頻數(shù)據(jù)存于分布式文件系統(tǒng)中。

3.4 分布式數(shù)據(jù)

分布式數(shù)據(jù)分析是建立在分布式數(shù)據(jù)存儲(chǔ)系統(tǒng)的基礎(chǔ)上的，基于Map/Reduce編程模型[7-9]，其可并行處理多個(gè)任務(wù)，表1為Hadoop系統(tǒng)性能對(duì)比指標(biāo)。

表1 Hadoop系統(tǒng)性能對(duì)比指標(biāo)

其中測(cè)試了Hadoop集群與Non-Hadoop集群在搜索性能上的差異。

本文提出利用Map/Reduce模型計(jì)算相似度，在分布式計(jì)算框架中，其中一臺(tái)作為Master的NameNode和JobTracker，另外3臺(tái)作為Slave的DataNode和TaskTracker。

串行方法和Map/Reduce方法在時(shí)間上的對(duì)比如表2所示。

表2 串行和Map/Reduce在時(shí)間上的對(duì)比

該實(shí)驗(yàn)表明，基于Map/Reduce的分布式計(jì)算方法，使得檢索效率顯著提高。當(dāng)分布式存儲(chǔ)系統(tǒng)的Slave主機(jī)數(shù)量增加的同時(shí)運(yùn)行時(shí)間也明顯減低，如圖6所示。

圖6 Slave主機(jī)數(shù)量與運(yùn)行時(shí)間對(duì)比

4 結(jié)論

本文主要研究面向海量視頻數(shù)據(jù)的檢索方法，如何快速準(zhǔn)確地進(jìn)行智能檢索成為大型視頻監(jiān)控系統(tǒng)所要急需解決的問(wèn)題。本文通過(guò)對(duì)關(guān)鍵幀的提取，并利用Map/Reduce編程模型，在一定程度上提高了檢索效率并且減少了檢索時(shí)間。在公安視頻監(jiān)控中使用此方法，能夠快速、準(zhǔn)確地找出可用圖片，使人們能夠安居樂(lè)業(yè)。

[1]李子青.海量視頻智能分析研判系統(tǒng)[J].中國(guó)公共安全：綜合版，2012（19）：180-185.

[2] 馮珺，高新波，楊益敏，等.視頻鏡頭關(guān)鍵幀重構(gòu)算法及其在檢索中的應(yīng)用[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2008，20（6）：775-780.

[3] 朱登明，王兆其.基于運(yùn)動(dòng)序列分割的運(yùn)動(dòng)捕獲數(shù)據(jù)關(guān)鍵幀提取[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2008，20（6）：787-792.

[4] 苗立剛.視頻監(jiān)控中的圖像拼接與合成算法研究[J].儀器儀表學(xué)報(bào)，2009，30（4）：857-861.

[5]楊勝，鐘玉琢.一種從MPEG壓縮視頻流中提取關(guān)鍵幀的方法[J].中國(guó)圖象圖形學(xué)報(bào)：A輯，2001，6（3）：254-258.

[6] GUDIVADA V N，RAGHAVAN V V.Content based image re?trieval systems[J].Computer，1995，28（9）：18-22.

[7] RUI Y，HUANG T S，CHANG S F.Image retrieval：current techniques，promising directions，and open issues[J].Journal of Visual Communication And Image Representation，1999，10（1）：39-62.

[8]PRATT B，HOWBERT J J，TASMAN N I，et al.MR-tandem：parallel Xtandem using hadoop MapReduce on amazon web ser?vices[J].Bioinformatics，2012，28（1）：136-137.

[9] LEE Y，KANG W，LEE Y.Traffic monitoring and analysis[M].Berlin：Springer，2011.

Huge Amounts of Video Image Retrieval Technology Research Based on Map/Reduce

YANG Man,HE Peng,QI Huaiqin,AN Jingran
（Communication and Electronic Engineering Institute,Qiqihar University,Heilongjiang Qiqihar 161006,China）

With the rapid development of Internet and multimedia technology,city public security video monitoring system produce a large number of video data every day,many problems need to be solved as video image retrieval, management and safety of the pressing demand.In general there are two points,one is the video retrieval accuracy problem,the other is the issue of retrieval efficiency.In the face of huge amounts of video database,the method is proposed based on the Map/Reduce distributed computing model combined with algorithm of key frames,which improve the efficiency and accuracy of retrieval.

Map/Reduce;key frames;video retrieval

TN911.73

A

10.16280/j.videoe.2015.04.009

楊 曼（1988— ），女，碩士研究生，主研圖像處理與視頻監(jiān)控技術(shù)；

2014-08-07

【本文獻(xiàn)信息】楊曼，何鵬，齊懷琴，等.基于Map/Reduce的海量視頻圖像檢索系統(tǒng)設(shè)計(jì)[J].電視技術(shù)，2015，39（4）.

科技部科技惠民計(jì)劃項(xiàng)目（2013GS230301)

何 鵬（1970— ），教授，博士，主研圖像處理。

責(zé)任編輯：閆雯雯