基于改進MGR融合算法的視頻信息融合框架

李 梅，王 晶，樊劉娟

（1.太原理工大學 計算機科學與技術(shù)學院，太原 030024；2.中國郵政儲蓄銀行 山西省分行，太原 030024)

近年來，隨著計算機技術(shù)和信息化進程的發(fā)展，各種類型的信息逐漸遍及于我們的工作、學習和生活中。大量的信息一方面極大的豐富了我們的工作和生活，但是另一方面如何從眾多信息中快速尋找到我們需要的信息也并非易事。藉此，國外有研究人員提出了多媒體信息檢索（MIR)的概念，所謂多媒體信息檢索就是從各種類型的資源（包括文本、圖像、視頻、音頻等)中尋找到所需信息的過程［1］。早年的多媒體信息檢索通常采用基于計算機視覺的算法［2］，它聚焦于多媒體各種不同特征（例如圖像、音頻等)的相似性研究。不久，該類檢索也開始應用于基于網(wǎng)絡的圖像搜索引擎及企業(yè)型數(shù)據(jù)庫中。20世紀90年代中期，發(fā)展為基于內(nèi)容的多媒體檢索。21世紀初，研究人員注意到未來演變的系統(tǒng)需要了解語義查詢，并不僅僅在低維空間計算潛在的特征，這就是我們常說的“語義鴻溝”。要跨越“語義鴻溝”就必須獲取更多有效的信息，分析出原始數(shù)據(jù)的語義。這就需要對視頻數(shù)據(jù)中各種有效信息進行融合分析，以便提取出可以表示語義信息的關(guān)鍵信息。

Jana Kludas認為多媒體信息的多模態(tài)性質(zhì)產(chǎn)生了信息融合的本質(zhì)需要［3］，然而進行信息融合時，同處一個空間的事實也會影響到其他任務，比如對象的識別。在過去幾十年間，信息融合只建立在狹窄獨立的研究領(lǐng)域里，至今仍未有一個通用的描述信息融合的理論框架?，F(xiàn)有的視頻分析工具大多只分析多媒體信息的一種模態(tài)特征，然而，關(guān)于同一信息點的多種模態(tài)特征在很大程度上具備關(guān)聯(lián)性。因此，需要一種方法對視頻的多模態(tài)信息進行有效的融合分析，增加對視頻信息分類檢索的準確性。筆者提出了一種改進的MGR分類器融合算法，并采用這一改進后的算法通過實驗進行融合分析，仿真結(jié)果表明該方法能夠有效提高分類識別的效率，提升系統(tǒng)的整體。

1 分類器融合算法

由于多媒體信息的多模態(tài)性，分類器融合對處理多媒體信息具有十分特殊的意義。在處理多媒體信息的過程中，會產(chǎn)生很多不同的分類，且描述這些類具有復雜、高維的特性，兼具一定的變化性，這就導致相關(guān)分類器有較高的錯誤率。有相關(guān)研究表明，不同模態(tài)所固有的一些相關(guān)性信息與待分析的被標注圖像的視覺及文字特征具有一致性。因此，有效的信息融合算法和框架可以極大地提高檢索、索引或分類方法的性能。

1.1 MGR分類器融合算法

目前，常見的融合算法有：BC融合算法（Borda Count)［4］、HR 融合算法（Highest Rank)［5］、LR 融合算法（Logistic Regression)［6］和元分類策略 MC融合算法（Meta-Classification)［7］等。

BC融合算法在區(qū)分各分類器的性能和專長方面很欠缺，在實際應用中有些刻板、不靈活。HR融合算法雖然不需要訓練過程，但是對噪聲的考慮不夠全面。MC融合算法（Meta-classification)雖然適用于任何需要進行多個分類器融合的情形，但是由于各分類器產(chǎn)生的概率或相似度分數(shù)并不能保證傳送所有信息。和HR融合算法一樣，LR融合方法需要一個訓練過程，該算法能動性較好，可以主動學習，并能綜合考慮到所有的分類器，但該算法對訓練樣本要求比較高，如果選擇不恰當就會嚴重影響融合效果；且LR算法不論序號值大還是小，序號值發(fā)生變化時對融合結(jié)果的影響是一樣的。而實際應用中，當序號值較大時，序號的變化對置信度的影響較??；相反，當序號值較小時，序號的變化對置信度的影響較大［8］。

后來，Melnik等人又提出了一種MGR（Mixed Group Ranks)融合算法［9］。該融合算法高度總結(jié)了HR，LR和BC三種算法的設計規(guī)則，嘗試著平衡置信度和優(yōu)先權(quán)，該方法通過設置各個分類器的優(yōu)先權(quán)，使不同的分類器對融合結(jié)果的影響不同，增強了小序號值對融合結(jié)果的影響。

MGR算法在置信度和優(yōu)先權(quán)兩方面達到了較為理想的折中，該算法將排序空間分成兩個部分，一部分使得ANM優(yōu)于UMD的分類器排序，另一部分則剛好相反。另一方面，它給序號值較小的分類器設置一個較大的權(quán)重。這一策略比LR和HR算法更具有一般性和普遍性，更有利于接收確定的分類器信息，合理整合不同分類器的信息。

1.2 改進的MGR分類器融合算法

MGR算法分數(shù)函數(shù)的每一項都是一個子集，隨著分類器數(shù)量的增多計算量也將大大增加，在分類器較多的情形下，不具備現(xiàn)實的實現(xiàn)意義。劉明等人提出了一種雙目標排序?qū)尤诤纤惴ǎ?］，該算法對MGR算法進行了改進，減少了算法中的參數(shù)個數(shù)，簡化了分類器間的關(guān)系，在基本分類器相互獨立的情況下能夠取得非常不錯的融合效果，其融合規(guī)則為：

但當各分類器間存在相關(guān)性時，該算法的融合效果并不明顯，甚至差于其他融合算法。在視頻處理過程中，各個分類器通常是相關(guān)的，一般表示同一事物的不同特征。為此，我們在Melnik等人設計的融合框架的基礎上，嘗試在置信度和優(yōu)先權(quán)方面進行優(yōu)化，提出了一個基于融合分數(shù)函數(shù)改進的MGR算法。該算法較其他融合算法相比，優(yōu)勢在于增強了小序號對置信度的影響。

改進后的MGR算法融合規(guī)則如下：

其中，權(quán)值λj≥0，函數(shù)是單調(diào)遞減的凸函數(shù)。

容易證明改進后的算法符合融合框架的性質(zhì)，所設計的函數(shù)是單調(diào)遞減的凸函數(shù)，且置信度函數(shù)僅與對應的序號值相關(guān)。

上式中0＜cj＜1，且cj是待確定的未知參數(shù)。

具體到融合函數(shù)中，有：

該函數(shù)不僅顧及到了分類器權(quán)值，而且傾向于序號值小的置信度，基本上滿足Melnik等人對融合框架的要求。

2 視頻融合分析框架

2.1 視頻特征提取

處理視頻數(shù)據(jù)，首先需要對原始的視頻數(shù)據(jù)進行結(jié)構(gòu)化處理。視頻融合分析的流程如圖1所示。

圖1 視頻融合分析處理過程

提取視頻特征需在原視頻的數(shù)據(jù)里對所屬視頻進行數(shù)據(jù)子集的提?。?0］。其所具有的特征有視聽信息和語義信息，所以在對視頻進行特征提取過程中，需要對底層特征及高層語義特征進行區(qū)分。底層特征的內(nèi)容有視覺、聽覺和文字內(nèi)容。高層語義的特征需要建立在對底層特征提取的基礎上，對原視頻所包含的語義進行分析。當下作為監(jiān)督模式的分類問題對視覺語義特征提取，通?？梢圆捎梅诸惸Ｊ交蛘邫C器學習的方法。不過對底層特征尤其是視頻，所涉及到的多模態(tài)特性必須要有效率較高的算法達到高效的特征選取，通過高效的融合算法將底層特征映射，對于不同的情況選擇不同的融合算法，才能高效的識別視頻。

2.2 降維過程

多媒體存儲過程中，勢必帶來海量存儲，而在存儲以及使用過程中涉及到的計算以幾何倍數(shù)增加，而且所需存儲空間復雜度也非常大?，F(xiàn)在普遍用來解決此問題的方法需要對高維空間進行分解，映射在低維空間，并且在降維過程中，不能破壞原始數(shù)據(jù)的結(jié)構(gòu)分布，我們把此方法叫做降維。Shuicheng Yan等人針對此問題引入了一種圖嵌入框架［11］，這個框架涉及到了較為全面的降維算法，對于其中所包含的降維算法都認為是一種特例，在限定條件下，考慮為特例。通過使用該框架下的類內(nèi)緊湊和類間分離準則可以解決之前存在的一種缺陷：LDA的數(shù)據(jù)都依賴于高斯分布。在這個情況下，Yan等人提出了邊際fisher分析算法［12］。fisher分析法中有內(nèi)在圖以及懲罰圖，內(nèi)在圖用來表示類內(nèi)緊湊，懲罰圖用來表示類間分離。內(nèi)在圖用來對類內(nèi)點的鄰接關(guān)系進行描述，其中的樣本與所屬同類的K1最近鄰。懲罰圖用來對不同類之間所關(guān)聯(lián)的邊緣點的聯(lián)系進行描述。這樣就不用必須獲取數(shù)據(jù)分布所附屬的先驗信息，同時在映射方面上比LDA要更加好用，比LDA等算法更具有普遍性。

3 實驗

3.1 實驗數(shù)據(jù)

本文中采用的實驗數(shù)據(jù)集來自公共視頻網(wǎng)站www.open-video.org中的公開視頻，我們選擇下載關(guān)于吉他guitar，水water，人people等為主題的6類視頻，并采用IBM公司的自動過媒體分析檢索系統(tǒng)（MARS)自動為視頻片段劃分鏡頭并提取鏡頭中的關(guān)鍵幀進行標注。

3.2 實驗設計原理

實驗中將原始視頻數(shù)據(jù)分為訓練集、檢驗集和測試集三個集合，測試集占40%，其他各占30%。訓練集用來訓練基本分類器；檢驗集用來訓練融合算法；測試集全部用做測試樣本?？紤]到顏色直方圖（color histograms)在全局及局部分布上能有效的刻畫圖像顏色，我們采用顏色直方圖256維的色度、飽和度和亮度三個分量描述關(guān)鍵幀。我們把顏色空間劃分為較小的顏色區(qū)域——箱（bin)，通過計算每個箱內(nèi)的像素數(shù)量確定其顏色直方圖。我們用8個箱量化色度和飽和度，用4個箱量化亮度。我們采用灰度共生矩陣（Co-Occurrence)描述圖像的紋理，在常用的0°方向，45°方向，90°方向和135°方向上計算其各自的灰度共生矩陣。通過提取Mel頻率倒譜系數(shù)表示視頻語音特征信號。提取數(shù)據(jù)25維、第1維為類別標識，后24維為語音特征信號。

每一種底層特征都分別采用邊際fisher分析（MFA)進行降維，轉(zhuǎn)化成24維的特征樣本，再采用SVM分類器進行分類，通過交叉驗證獲得其懲罰參數(shù)c和核函數(shù)參數(shù)g。這樣，根據(jù)輸入數(shù)據(jù)和特征種類可以設計8個SVM分類器，三個數(shù)據(jù)集共可獲得24個基本分類器。對于任意的輸入樣本，每個基本分類器計算該類樣本和每類樣本的最近鄰距離，并根據(jù)距離的大小將各個類進行排序，輸出一組序號，全部基本分類器的輸出序號綜合起來構(gòu)成一個序號矩陣。經(jīng)過各個分類器處理得到的校驗集樣本序號矩陣構(gòu)成融合算法的訓練集，測試集樣本序號矩陣構(gòu)成測試集。

3.3 實驗結(jié)果及分析

用SVM分類器分別對提取的顏色直方圖特征、紋理特征、音頻特征進行分類，對比不同的降維和融合組合識別率結(jié)果識別率有很大差別，不同的特征對待不同類的樣本各有優(yōu)勢。具體的識別效果如圖2所示。

為了對比，再從分類器中選擇4個基本分類器，分別來源于不同的數(shù)據(jù)源，然后進行獨立分類器的實驗。對比實驗的融合結(jié)果如圖3所示。

再次驗證我們采用的降維綜合融合算法的有效性。分別采用LDA降維算法和LR融合算法的組合，以及LDA降維算法和MGR融合算法的組合，MFA＋MGR算法的組合并對比MFA算法和我們改進后的MGR算法的組合。對比我們前面分類手工標注的四類視頻進行識別率對比，結(jié)果如表1所示。

表1 分類器識別率 %

圖2 各種組合策略的識別準確率

圖3 同數(shù)據(jù)源與不同數(shù)據(jù)源的識別錯誤率對比

筆者在設定條件下與方法進行了實驗，結(jié)果表明普遍情況下，用本文所述的改進算法進行分類時準確率優(yōu)于現(xiàn)存的融合方法，通過和Melnik所提出的算法結(jié)果進行比較，發(fā)現(xiàn)也有提高。此分類算法降低了涉及到的分類器所具有的錯誤率。通過實驗可以認為在MGR的各分類器進行融合實驗時，所組成的分類器體現(xiàn)的性能明顯好于LR融合算法和BC融合算法。采用筆者所提到的方法融合基本分類器時，在分類準確率上比其他邏輯同歸和MGR方法要好，尤其是在非獨立關(guān)系的基本分類器之間，此方法比起雙目標排序融合算法要更好一些。通過融合視頻所具有的特征多種模態(tài)，所獲得的平均效果比起單模態(tài)情況要好很多。

4 結(jié)束語

筆者根據(jù)視頻特征的多模態(tài)性質(zhì)以及分類器融合的理論，提出了一種基于改進MGR融合算法的視頻信息融合框架。該框架提取出視頻關(guān)鍵幀圖像的顏色特征、紋理特征及視頻的音頻特征，進行統(tǒng)一的降維處理后輸入到分類器中進行分類，然后對分類器的輸出結(jié)果進行融合分析，并在融合分析中對融合算法MGR進行了改進，減少了融合函數(shù)的參數(shù)并降低了融合算法的計算復雜度。實驗證明整體框架比傳統(tǒng)的方法擁有了更高的分類正確率。

［1］許源.視頻語義特征提取算法研究［D］.上海：復旦大學計算機科學與工程系，2006.

［2］Michael S Lew，Nicu Sebe，Chabane Djeraba，et al.Content-Based Multimedia Information Retrieval：State of the Art and Challenges［J］.ACM Transactions on Multimedia Computing，Communications and Applications，2006，2（1)：1-19.

［3］Jana Kludas，Eric Bruno，Stephane Marchand-Maillet.Information Fusion in Multimedia Information Retrieval［J］.Adaptive Multimedial Retrieval：Retrieval，User，and Semantics，2008：147-159.

［4］Tin Kam Ho.A Theory of Multiple Classifier Systems And Its Application to Visual Word Recognition［D］.New York：Graduate School of State University of New York，1992.

［5］李輝，李存華，王霞.基于特征選擇的網(wǎng)頁排名算法［J］.計算機工程，2010，36（13)：37-39.

［6］鄧妍，張衛(wèi)強，劉佳.語種識別中基于局部多樣性建模的向量空間模型［J］.清華大學學報（自然科學版)，2011，51（2)：161-165.

［7］Ding Guo，Yu Bei，Ghosh，et al.EPIC：Efficient prediction of IC manufacturing hotspots with a unified meta-classification formulation［C］∥In ASP-DAC 2012-17th Asia and South Pacific Design Automation Conference，2012：263-270.

［8］劉明，袁保宗，苗振江.一種雙目標排序?qū)臃诸惼魅诤戏椒ǎ跩］.自動化學報，2007，33（12)：1276-1282.

［9］Ofer Melnik，Yehuda Vardi，Cun-Hui Zhang.Mixed Group Ranks：Preference and Confidence in Classifier Combination［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26（8)：973-981.

［10］馮大淦，蕭允治，張宏江.劉曉冬譯.多媒體信息檢索與管理［M］.北京：清華大學出版社，2009.

［11］Shuicheng Yan，Dong Xu，Benyu Zhang，et al.A General Framework for Dimensionality Reduction［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2007，29（1)：40-51.

［12］Jun Yan，Benyu Zhang，Shuicheng Yan，et al.A scalable supervised algorithm for dimensionality reduction on streaming data［J］.Information Sciences，2006，176（14)：2042-2065.