摘要：關(guān)鍵幀提取和目標(biāo)分割通常是分離獨(dú)立執(zhí)行的，這是由于它們處于不同的語義層面并且涉及到不同的特征。在本文中，我們通過為這兩個(gè)過程構(gòu)造一個(gè)統(tǒng)一的特征空間來實(shí)現(xiàn)關(guān)鍵幀提取和目標(biāo)分割，這里將關(guān)鍵幀提取看成是在基于混合高斯模型視頻建模背景下為目標(biāo)分割進(jìn)行的特征選擇過程。值得一提的是這里引入兩個(gè)基于分歧的標(biāo)準(zhǔn)到關(guān)鍵幀提取中。其中一個(gè)將關(guān)鍵幀提取定義為在混合高斯模型組件中引入配對(duì)組內(nèi)分歧，另一個(gè)則限度的利用那些顯示幀內(nèi)平均密度變化的相對(duì)分歧。這里提出的方法可以為目標(biāo)分割提取出有代表性的關(guān)鍵幀，同時(shí)關(guān)鍵幀中一些令人感興趣的特征也會(huì)被討論到。本文就為基于內(nèi)容的視頻分析提供一個(gè)獨(dú)一無二的范例。
1. 引言
如何填補(bǔ)低層次特征和高層次概念之間的語義鴻溝已經(jīng)是基于內(nèi)容的視頻分析中長(zhǎng)期存在的問題了（文獻(xiàn)[1]-[3]）。在本文中，我們將在融合學(xué)習(xí)兩種視頻分析任務(wù)中著重關(guān)注這個(gè)問題，這兩個(gè)任務(wù)就是關(guān)鍵幀提取和目標(biāo)分割。關(guān)鍵幀就是那些對(duì)理解視頻內(nèi)容非常重要的幀，它的定義比較主觀。關(guān)鍵幀與運(yùn)動(dòng)、目標(biāo)或事件有關(guān)。目標(biāo)通常指的是具有同類特征（例如顏色，運(yùn)動(dòng)）的區(qū)域，或者是有意義的客觀世界的實(shí)體，這些實(shí)體可能是由一個(gè)或多個(gè)區(qū)域構(gòu)成（文獻(xiàn)[4]）。在本文中提到的目標(biāo)指的是前者。通常關(guān)鍵幀提取和目標(biāo)分割是使用不同的特征分離獨(dú)立執(zhí)行的，低層次顏色和運(yùn)動(dòng)特征常常用于關(guān)鍵幀的提?。ㄎ墨I(xiàn)[5]），這對(duì)于時(shí)間敏感的應(yīng)用來說在計(jì)算上效率非常高的。提取出來的關(guān)鍵幀一般都指出了特征空間中有意義的改變，并且特征空間具有有限的語義。如果關(guān)鍵幀可以暗示某些與目標(biāo)有關(guān)的行為或事件的話，我們就認(rèn)為這些關(guān)鍵幀在語義上是有意義的。監(jiān)督式的方法通常通過并入某些模板或領(lǐng)域內(nèi)的信息（文獻(xiàn)[2]，[3]例如消息，運(yùn)動(dòng)等等）來豐富關(guān)鍵幀的語義。如果在關(guān)鍵幀提取中包含目標(biāo)信息的話，那么非監(jiān)督式的處理也能夠提取出在語義上有意義的關(guān)鍵幀（文獻(xiàn)[1]，[6]）。盡管具有更大的挑戰(zhàn)性，但是目標(biāo)分割較關(guān)鍵幀提取在視頻數(shù)據(jù)方面可以提供更好的解釋性和可操作性。在文獻(xiàn)[7]中，大多數(shù)目標(biāo)分割方法都被歸為三類：空間優(yōu)先性分割，時(shí)間優(yōu)先性分割和空時(shí)混合分割，其中空時(shí)混合分割在公眾中吸引越來越多的注意力（文獻(xiàn)[8]-[10]）?？諘r(shí)混合視頻分割與人類視覺特性是相一致的，都可以同時(shí)在時(shí)間和空間上識(shí)別顯著的結(jié)構(gòu)（文獻(xiàn)[11]）。文獻(xiàn)[8]中提出用Mean-Shift聚類方法在空間和時(shí)間上分割目標(biāo)。文獻(xiàn)[9]用混合高斯模型來作為空時(shí)混合視頻的描述。文獻(xiàn)[10]中建議使用圖形分割理論的方法來進(jìn)行空時(shí)混合視頻建模。
如果這兩個(gè)過程聯(lián)合起來考慮會(huì)有令人感興趣的情況出現(xiàn)。例如當(dāng)目標(biāo)在特征空間中被描繪成聚類時(shí)，聚類的空時(shí)關(guān)系就會(huì)暗示某些目標(biāo)行為或事件，比如離開與接近，出現(xiàn)與消失，擴(kuò)張與收縮等等，同時(shí)提取到的關(guān)鍵幀可能包含這些目標(biāo)行為。文獻(xiàn)[1]中指出，通常在分割區(qū)域的位置提取關(guān)鍵幀，這個(gè)地方目標(biāo)混合在一起。文獻(xiàn)[6]中指出用形狀特征來提取包含人體姿勢(shì)改變的關(guān)鍵幀。此外需要注意的是，在基于混合高斯模型的視頻建模環(huán)境下關(guān)鍵幀或許可以減少目標(biāo)分割的困難（文獻(xiàn)[12]），這里首次選擇基于顏色直方圖作為關(guān)鍵幀的初始設(shè)置，并且該初始設(shè)置在目標(biāo)分割中被用于估計(jì)混合高斯模型，并且分割的結(jié)果和受訓(xùn)的高斯混合模型將進(jìn)一步用于完善初始的關(guān)鍵幀。這個(gè)方法可以大大降低計(jì)算量和提高視頻分割的魯棒性。由于關(guān)鍵幀提取和目標(biāo)分割是在不同特征空間中和不同的標(biāo)準(zhǔn)下獨(dú)立執(zhí)行的（文獻(xiàn)[12]）。該方法被稱為“組合的”方法。
本文通過擴(kuò)展文獻(xiàn)[12]先前所做的工作提出一種融合關(guān)鍵幀提取和目標(biāo)分割的方法。這種方法就是在統(tǒng)一的特征空間中將關(guān)鍵幀提取構(gòu)想成為目標(biāo)分割的特征選擇過程。在基于混合高斯模型的視頻建模中（文獻(xiàn)[9],[13]），視頻序列由空時(shí)特征聚類表征，這些集群由多元的混合高斯模型描述。在混合高斯模型中高斯分量間的可分離性是由集群分歧估計(jì)的，引起集群分離性的那些幀就被提取出來作為關(guān)鍵幀。這兩種分歧標(biāo)準(zhǔn)使用如下：平均組內(nèi)K-L距離和相對(duì)分歧，其中相對(duì)分歧定義為每個(gè)相對(duì)類條件密度和均值間的平均距離（文獻(xiàn)[14]）。與之前的基于高斯混合模型的視頻分割方法相比（文獻(xiàn)[9],[12],[13]），具有大的集群分歧的關(guān)鍵幀有利于基于高斯混合模型的視頻建模并且可以提供更好的魯棒性和同性質(zhì)的目標(biāo)分割結(jié)果。更有趣的是，由于關(guān)鍵幀提取受基于分歧的聚類標(biāo)準(zhǔn)支配，提取出來的關(guān)鍵幀很可能包含某些目標(biāo)行為或事件的信息，這些信息往往都是由那些空時(shí)聚類表示的。這里提出的方法和文獻(xiàn)[9],[12],[13]中提到的都具有一個(gè)主要的局限性，那就是高斯混合模型不足以處理不同低水平特征（例如顏色和運(yùn)動(dòng)）的混合目標(biāo)。不過這只是早期視覺的第一步，通過包含基于區(qū)域的特征就可以進(jìn)一步與互補(bǔ)方法結(jié)合起來，從而產(chǎn)生更多在語義上有意義的結(jié)果（文獻(xiàn)[4],[15]）。本文主要的目的就是要通過尋找用于混合高斯模型估計(jì)的或次優(yōu)的關(guān)鍵幀集合來提高目標(biāo)分割的性能，這里關(guān)鍵幀是副產(chǎn)物。本文是針對(duì)基于內(nèi)容的視頻分析新工具的初始研究，這些研究或許可以為MPEG-4/7標(biāo)準(zhǔn)引入一些新的幀或目標(biāo)的描述符和函數(shù)。
2. 融合關(guān)鍵幀提取和目標(biāo)分割
上面已經(jīng)集中對(duì)關(guān)鍵幀提取和目標(biāo)分割進(jìn)行討論了。我們首先簡(jiǎn)單的回顧一下幾個(gè)相關(guān)的方法。文獻(xiàn)[9]提出一種用于空時(shí)視頻建模的概率框架，這里在空時(shí)特征空間中用高斯“blob”表征目標(biāo)（同性質(zhì)的區(qū)域），該空間包含顏色（L，a，b），時(shí)間（t），坐標(biāo)（x和y）。用M階高斯混合模型對(duì)具有M個(gè)目標(biāo)的視頻進(jìn)行建模。用EM算法來估計(jì)模型參數(shù)，用MDL標(biāo)準(zhǔn)來尋找合適的M值。經(jīng)過高斯混合模型估計(jì)之后，通過MAP分類將視頻分割成M個(gè)空時(shí)塊。文獻(xiàn)[9]提出用分段執(zhí)行來處理非線性和非凸的運(yùn)動(dòng)模型。這種方法主要的瓶頸就是具有很高的計(jì)算負(fù)荷量，因?yàn)樵诨旌细咚鼓Ｐ凸烙?jì)時(shí)要涉及到所有的視頻幀。
文獻(xiàn)[12]提出一種融合關(guān)鍵幀提取和目標(biāo)分割的方法，用該方法來提高高斯混合模型估計(jì)的效率和魯棒性。首先利用逐幀的16×8二維色調(diào)和飽和度的顏色直方圖來提取得到初始關(guān)鍵幀（文獻(xiàn)[5]），并用得到的關(guān)鍵幀估計(jì)高斯混合模型。目標(biāo)分割之后，每個(gè)初始的關(guān)鍵幀都要用高斯混合模型進(jìn)行建模，這里實(shí)際上是用高斯混合模型對(duì)關(guān)鍵幀進(jìn)行修正。這種方法大幅度的減少了計(jì)算量，同時(shí)通過包含許多不同的關(guān)鍵幀的緊湊特征集提高了模型估計(jì)的魯棒性。另外，基于高斯混合模型的關(guān)鍵幀修正可能會(huì)得到更多的緊湊的關(guān)鍵幀。這種融合的方法帶來三個(gè)有趣的問題：1）在高斯混合模型估計(jì)或目標(biāo)分割方面如何保證提取到關(guān)鍵幀是的？2）我們可以同時(shí)使關(guān)鍵幀提取和目標(biāo)分割化嗎？3）如果問題2）的答案是肯定的話，那么提取到的關(guān)鍵幀是否有在語義上有用的信息呢（比如目標(biāo)的行為）？在本文中，我們將主要關(guān)注這些問題，具體是通過提出一種融合關(guān)鍵幀提取和目標(biāo)分割的方法來探索兩種之間可能的聯(lián)系和協(xié)同關(guān)系。
2.1問題描述
與用不同特征執(zhí)行關(guān)鍵幀提取和目標(biāo)分割相反，本文提出利用統(tǒng)一的特征空間來實(shí)現(xiàn)它們。
在這個(gè)N幀的視頻鏡頭包含三個(gè)主要的目標(biāo)，這三個(gè)目標(biāo)在特征空間中分別由聚類表征。通常，一個(gè)鏡頭中的數(shù)個(gè)幀表征一個(gè)空間和時(shí)間上連續(xù)的行為，并且共享公共的視覺和與語義有關(guān)的特征。因此就存在極大的冗余。另外那些可能隨機(jī)出現(xiàn)在幀邊界處的表示噪聲和無意義的目標(biāo)的不相關(guān)的異常值增加了特征空間中集群的重疊部分。冗余性和不相干性降低了統(tǒng)計(jì)建模的效率，因此可以通過去除冗余、不相干的數(shù)據(jù)和特征來提高建模的性能，換句話說可以通過選擇最緊密相關(guān)的數(shù)據(jù)和特征來進(jìn)行訓(xùn)練學(xué)習(xí)處理（文獻(xiàn)[17]）。在基于高斯混合模型視頻分割中，可以通過選擇更相關(guān)的關(guān)鍵幀進(jìn)行視頻建模，例如將關(guān)鍵幀提取構(gòu)想成目標(biāo)分割的特征選擇過程。
在文獻(xiàn)[18]中已經(jīng)就特征選擇方法進(jìn)行集中討論。給定一個(gè)初始候選特征集合
，特征選擇主要的目的就是從中選擇一個(gè)子集以便與分類性能有關(guān)的準(zhǔn)則判別函數(shù)可以優(yōu)化為：
（1）
選擇一個(gè)適當(dāng)?shù)氖呛苤匾?。一種常用的準(zhǔn)則就是選擇特征來近似真實(shí)的密度而不是去提取差別的特征。盡管希望這個(gè)準(zhǔn)則可以在不同的等級(jí)間產(chǎn)生較好的差別，但是這個(gè)假設(shè)并不總是有充分根據(jù)的，同時(shí)對(duì)于魯棒性分級(jí)，文獻(xiàn)[19]中提出基于分歧的特征選擇準(zhǔn)則。接下來我們將為特征選擇引入兩個(gè)基于分歧的準(zhǔn)則，然后在此基礎(chǔ)上得到新的融合關(guān)鍵幀提取和目標(biāo)分割的方法。
2.2平均組內(nèi)Kullback Leibler 距離（MAIKLD）
K-L距離（KLD）可以度量為聚類建模的兩個(gè)高斯分量的距離或相異性。給定由M個(gè)高斯組件表征的M個(gè)聚類，平均組內(nèi)KLD（AIKLD）定義如下：
（2）
這里是兩個(gè)高斯函數(shù)和的KLD距離，。理想情況下，AKLD越大，聚類間的獨(dú)立性就越大。由于關(guān)鍵幀提取被構(gòu)想為特征選擇過程，因此希望提取出具有平均組內(nèi)集群分歧的關(guān)鍵幀。假設(shè)是具有N幀的原始視頻鏡頭，這個(gè)鏡頭由具有基數(shù)的集合表示。再假設(shè)是的任一具有基數(shù)的子集。如果鏡頭中有M個(gè)目標(biāo)，那么目標(biāo)函數(shù)就定義為
（3）
這里是在MAIKLD方面的子集。根據(jù)文獻(xiàn)[20]，在最小貝葉斯誤差意義上說MAIKLD是的。如果使用0-1分類代價(jià)函數(shù)，就會(huì)產(chǎn)生后驗(yàn)概率估計(jì)。因此等式（3）的解決方式會(huì)得到的關(guān)鍵幀集合，這些關(guān)鍵幀可以使得目標(biāo)分割的差錯(cuò)率最小。窮舉搜索可以保證得到的，不過對(duì)于大的，這是計(jì)算昂貴且不切實(shí)際的，因?yàn)樾枰囼?yàn)個(gè)幀子集。因此次佳的但是計(jì)算量上更有效的解決方法將更為實(shí)際。這里使用文獻(xiàn)[21]中提到的確定性特征選擇方法，該方法叫做連續(xù)前向浮動(dòng)選擇（SFFS），并利用連續(xù)前向選擇（SFS）方法對(duì)SFFS進(jìn)行初始化（文獻(xiàn)[18]）。當(dāng)N不是非常大的話，SFFS可以找到的。本文中的關(guān)鍵幀都是從的候選關(guān)鍵幀中提取出的。高斯混合模型估計(jì)包含MDL方面的估計(jì)后，高斯函數(shù)和的KLD將由下式近似計(jì)算得到：
這里是所有待測(cè)候選關(guān)鍵幀的像素特征向量，表示第i個(gè)高斯組件的參數(shù)。然后利用式（2）計(jì)算AIKLD。這個(gè)搜索過程如下：（1）首先給定空集，n是的基數(shù)，即，且n的初始值為0；（2）使用SFS算法產(chǎn)生具有AIKLD的兩個(gè)候選關(guān)鍵幀的組合，并得到；（3）搜索一個(gè)在時(shí)具有AIKLD的候選關(guān)鍵幀，并把搜索到的加入集合中，同時(shí)令n=n+1；（4）如果n>2，就從中去除一個(gè)候選關(guān)鍵幀并對(duì)剩下的候選關(guān)鍵幀計(jì)算AIKLD，然后繼續(xù)（5），否則的話回到（3）；（5）確定去除一個(gè)候選關(guān)鍵幀后AIKLD是否增加。如果答案是肯定的話，就令n=n-1，然后回到（4），否則回到（3）。
當(dāng)n達(dá)到一個(gè)預(yù)定義的值時(shí)或在反復(fù)出現(xiàn)給定的值后，搜索就會(huì)停止。除了比文獻(xiàn)[9]使用所有幀效率更高外，該方法還有兩個(gè)主要的優(yōu)勢(shì)：1）可以提取出在MAIKLD方面或次優(yōu)的關(guān)鍵幀用于模型估計(jì)，與用顏色直方圖提取出的關(guān)鍵幀相比，這些關(guān)鍵幀可以為基于高斯混合模型的目標(biāo)分割提供更好的可辨別性（文獻(xiàn)[12]）；2）該算法比較靈活且?guī)缀鯖]有任何限制。不過有些問題還需要進(jìn)一步考慮，首先是當(dāng)很大的時(shí)候SFFS就無效了；其次，在關(guān)鍵幀提取前的基于MDL的高斯混合模型估計(jì)對(duì)時(shí)間敏感。有一個(gè)可供選擇的方法就是執(zhí)行基于高階高斯混合模型的SFFS，并且基于MDL的高斯混合模型估計(jì)只對(duì)關(guān)鍵幀執(zhí)行。但是如果基于高階高斯混合模型的話，視頻就會(huì)分段過多，從而導(dǎo)致更多的聚類源于同個(gè)語義目標(biāo)。為了增加同一目標(biāo)中聚類間的分歧，MAIKLD允許幀具有更多的異常值，這些異常值常導(dǎo)致遭受關(guān)鍵幀。不過要從待測(cè)的候選集中去除多余的候選關(guān)鍵幀是不可能的，為了降低計(jì)算量，我們提出另外一種基于分歧的準(zhǔn)則。
2.3相對(duì)分歧
文獻(xiàn)[14]提出相對(duì)分歧（MMD）準(zhǔn)則來進(jìn)行有效的基于熵原理的特征選擇，這是要在最小化信息冗余時(shí)維持輸入行為的信息的化。在分類的背景下，該方法往往選擇那些特征和類標(biāo)簽間互信息量的特征（文獻(xiàn)[14]）。如果將熵原理運(yùn)用到本文，那么目標(biāo)函數(shù)就可以寫成
（4）
這里是關(guān)鍵幀子集X和分類標(biāo)簽Y={1，2，...，M}間的互信息量。
考慮到I（X，Y）=H（Y）-H（Y|X），這里H（Y）是分類標(biāo)簽的熵。H(Y|X)是條件熵，有關(guān)貝葉斯誤差的下界和H（Y|X）的聯(lián)系來源于文獻(xiàn)[14]。這個(gè)關(guān)系表明最小化H(Y|X)(熵原理)等價(jià)于最小化貝葉斯誤差的下界。I(X,Y)可以如文獻(xiàn)[14]寫成：
（5）
這里，且。稱為相對(duì)分歧（MD），表示平均密度方差。文獻(xiàn)[14]的解釋表明，如果特征間的互信息量不受分類標(biāo)簽影響的話，那么I（X，Y）就可以用MD值的累加來近似，如。這樣一來的MI就變成了MMD。正如文獻(xiàn)[14]總結(jié)的，這個(gè)條件來自于目前對(duì)圖形統(tǒng)計(jì)學(xué)的研究，它可以表明一些圖形特征間的樣式屬性結(jié)構(gòu)也遵從一般的獨(dú)立于分類標(biāo)簽的統(tǒng)計(jì)學(xué)規(guī)則。這些特征通過各種生物學(xué)上的圖形變換提取出來，比如小波變換。雖然這個(gè)條件并不總是嚴(yán)格成立，但至少它表明MMD在最小貝葉斯誤差方面是近似的。
如果把MMD應(yīng)用到關(guān)鍵幀提取中，那么具有MD值的幀將被提取作為關(guān)鍵幀。類似于MAIKLD，MMD關(guān)鍵幀提取是在初始高斯混合模型估計(jì)之后執(zhí)行。不過MAIKLD需要測(cè)試不同的候選關(guān)鍵幀組合，而MMD只考慮每個(gè)幀的分歧忽略了交互幀的依賴性。候選關(guān)鍵幀的MD值可以如下近似計(jì)算：
這里是所有的像素特征向量，具有MD值的幀被選作關(guān)鍵幀。可以預(yù)定義，或自適應(yīng)確定一個(gè)MD值的門限。我們使用所有候選關(guān)鍵幀的平均MD值作為門限值，對(duì)于MD值大于門限的任何候選關(guān)鍵幀都被選作關(guān)鍵幀。
2.4提出算法
輸入的候選關(guān)鍵幀要么是一個(gè)鏡頭的所有幀，要么是最初由顏色直方圖選擇出來的關(guān)鍵幀（文獻(xiàn)[5],[12]）。顏色特征（Y，u，v），空間位置x-y，時(shí)間t一起組成統(tǒng)一的特征空間。用由EM算法和MDL準(zhǔn)則估計(jì)的高斯混合模型對(duì)輸入的視頻進(jìn)行建模。初始建模之后，利用MAIKLD或MMD指導(dǎo)關(guān)鍵幀的提取。提取出來的關(guān)鍵幀用于對(duì)高斯混合模型的重估計(jì)。即使進(jìn)行了初始的高斯混合模型估計(jì)，但是關(guān)鍵幀提取和模型重估計(jì)仍然是分離獨(dú)立執(zhí)行的，通過解釋它們?cè)诮y(tǒng)一的特征空間中的相互影響可以看出整個(gè)過程是統(tǒng)一的。與文獻(xiàn)[9]使用所有幀的方法或使用文獻(xiàn)[12]從顏色直方圖提取關(guān)鍵幀的方法相比，我們期望本文提出的方法不僅可以通過最小化特征冗余來提高計(jì)算效率，而且可以通過降低特征不相干性來增強(qiáng)視頻建模的魯棒性。
正如之前提到的，MAIKLD提取出具有聚類分歧的關(guān)鍵幀，并通過計(jì)算一組候選關(guān)鍵幀的AIKLD來考慮聚類的的統(tǒng)計(jì)特性，但是通過假設(shè)幀獨(dú)立對(duì)每個(gè)幀估計(jì)MD值，同時(shí)利用MMD選擇那些具有MD值的作為關(guān)鍵幀。因此就可以選擇出不同的關(guān)鍵幀，盡管都是由貝葉斯誤差限定下界。在基于高斯混合模型視頻建模的背景下，MAIKLD較MMD可以提取出更多有判別力的關(guān)鍵幀，因?yàn)槠骄芏确讲顩]有必要增大聚類分歧或降低聚類間的重疊。而MMD冒著忽略幀間附屬性質(zhì)的風(fēng)險(xiǎn)只考慮每個(gè)幀的聚類分歧。盡管如此，MMD在計(jì)算上仍然比MAIKLD具有更高的效率，因?yàn)椴恍枰M合搜索。
2.5關(guān)鍵幀特征
到此為止我們已經(jīng)討論了第二節(jié)提出的前兩個(gè)問題，現(xiàn)在將就基于新方法提取出的關(guān)鍵幀的特征繼續(xù)研究第三個(gè)問題。顯示了特征空間中的兩個(gè)聚類，該特征空間由空間（x-y），時(shí)間（t）以及兩個(gè)時(shí)間片（幀A和幀B）定義，這兩個(gè)時(shí)間片分別處于t=a和t=b的兩個(gè)聚類的空間位置，從而使得整個(gè)特征空間被分成三個(gè)部分。兩個(gè)聚類當(dāng)它們?cè)趨^(qū)域II（陰影區(qū)域）的x-y平面部分重疊時(shí)是空間最靠近的。如果聚類分別與兩個(gè)實(shí)體有關(guān)，那么實(shí)體在區(qū)域II的幀中也是空間臨近的，而在區(qū)域I或III的幀中則是遠(yuǎn)離的。通過理解MAIKLD或MMD用于關(guān)鍵幀提取的原理，我們可以確定低層次特征和高層次概念之間的聯(lián)系MAIKLD與最小化貝葉斯誤差是等價(jià)的，這是由特征空間中的聚類重疊引起的。為了最小化貝葉斯誤差，聚類分歧應(yīng)該化。因此MAIKLD往往在聚類具有最小重疊的地方提取關(guān)鍵幀，例如區(qū)域I和區(qū)域III。當(dāng)應(yīng)用MMD時(shí)，每個(gè)幀的MD值都要計(jì)算。平均密度具有充分大的差異的任何幀或換句話說聚類分散在x-y平面的任何幀將被提取作為關(guān)鍵幀。
1. 引言
如何填補(bǔ)低層次特征和高層次概念之間的語義鴻溝已經(jīng)是基于內(nèi)容的視頻分析中長(zhǎng)期存在的問題了（文獻(xiàn)[1]-[3]）。在本文中，我們將在融合學(xué)習(xí)兩種視頻分析任務(wù)中著重關(guān)注這個(gè)問題，這兩個(gè)任務(wù)就是關(guān)鍵幀提取和目標(biāo)分割。關(guān)鍵幀就是那些對(duì)理解視頻內(nèi)容非常重要的幀，它的定義比較主觀。關(guān)鍵幀與運(yùn)動(dòng)、目標(biāo)或事件有關(guān)。目標(biāo)通常指的是具有同類特征（例如顏色，運(yùn)動(dòng)）的區(qū)域，或者是有意義的客觀世界的實(shí)體，這些實(shí)體可能是由一個(gè)或多個(gè)區(qū)域構(gòu)成（文獻(xiàn)[4]）。在本文中提到的目標(biāo)指的是前者。通常關(guān)鍵幀提取和目標(biāo)分割是使用不同的特征分離獨(dú)立執(zhí)行的，低層次顏色和運(yùn)動(dòng)特征常常用于關(guān)鍵幀的提?。ㄎ墨I(xiàn)[5]），這對(duì)于時(shí)間敏感的應(yīng)用來說在計(jì)算上效率非常高的。提取出來的關(guān)鍵幀一般都指出了特征空間中有意義的改變，并且特征空間具有有限的語義。如果關(guān)鍵幀可以暗示某些與目標(biāo)有關(guān)的行為或事件的話，我們就認(rèn)為這些關(guān)鍵幀在語義上是有意義的。監(jiān)督式的方法通常通過并入某些模板或領(lǐng)域內(nèi)的信息（文獻(xiàn)[2]，[3]例如消息，運(yùn)動(dòng)等等）來豐富關(guān)鍵幀的語義。如果在關(guān)鍵幀提取中包含目標(biāo)信息的話，那么非監(jiān)督式的處理也能夠提取出在語義上有意義的關(guān)鍵幀（文獻(xiàn)[1]，[6]）。盡管具有更大的挑戰(zhàn)性，但是目標(biāo)分割較關(guān)鍵幀提取在視頻數(shù)據(jù)方面可以提供更好的解釋性和可操作性。在文獻(xiàn)[7]中，大多數(shù)目標(biāo)分割方法都被歸為三類：空間優(yōu)先性分割，時(shí)間優(yōu)先性分割和空時(shí)混合分割，其中空時(shí)混合分割在公眾中吸引越來越多的注意力（文獻(xiàn)[8]-[10]）?？諘r(shí)混合視頻分割與人類視覺特性是相一致的，都可以同時(shí)在時(shí)間和空間上識(shí)別顯著的結(jié)構(gòu)（文獻(xiàn)[11]）。文獻(xiàn)[8]中提出用Mean-Shift聚類方法在空間和時(shí)間上分割目標(biāo)。文獻(xiàn)[9]用混合高斯模型來作為空時(shí)混合視頻的描述。文獻(xiàn)[10]中建議使用圖形分割理論的方法來進(jìn)行空時(shí)混合視頻建模。
如果這兩個(gè)過程聯(lián)合起來考慮會(huì)有令人感興趣的情況出現(xiàn)。例如當(dāng)目標(biāo)在特征空間中被描繪成聚類時(shí)，聚類的空時(shí)關(guān)系就會(huì)暗示某些目標(biāo)行為或事件，比如離開與接近，出現(xiàn)與消失，擴(kuò)張與收縮等等，同時(shí)提取到的關(guān)鍵幀可能包含這些目標(biāo)行為。文獻(xiàn)[1]中指出，通常在分割區(qū)域的位置提取關(guān)鍵幀，這個(gè)地方目標(biāo)混合在一起。文獻(xiàn)[6]中指出用形狀特征來提取包含人體姿勢(shì)改變的關(guān)鍵幀。此外需要注意的是，在基于混合高斯模型的視頻建模環(huán)境下關(guān)鍵幀或許可以減少目標(biāo)分割的困難（文獻(xiàn)[12]），這里首次選擇基于顏色直方圖作為關(guān)鍵幀的初始設(shè)置，并且該初始設(shè)置在目標(biāo)分割中被用于估計(jì)混合高斯模型，并且分割的結(jié)果和受訓(xùn)的高斯混合模型將進(jìn)一步用于完善初始的關(guān)鍵幀。這個(gè)方法可以大大降低計(jì)算量和提高視頻分割的魯棒性。由于關(guān)鍵幀提取和目標(biāo)分割是在不同特征空間中和不同的標(biāo)準(zhǔn)下獨(dú)立執(zhí)行的（文獻(xiàn)[12]）。該方法被稱為“組合的”方法。
本文通過擴(kuò)展文獻(xiàn)[12]先前所做的工作提出一種融合關(guān)鍵幀提取和目標(biāo)分割的方法。這種方法就是在統(tǒng)一的特征空間中將關(guān)鍵幀提取構(gòu)想成為目標(biāo)分割的特征選擇過程。在基于混合高斯模型的視頻建模中（文獻(xiàn)[9],[13]），視頻序列由空時(shí)特征聚類表征，這些集群由多元的混合高斯模型描述。在混合高斯模型中高斯分量間的可分離性是由集群分歧估計(jì)的，引起集群分離性的那些幀就被提取出來作為關(guān)鍵幀。這兩種分歧標(biāo)準(zhǔn)使用如下：平均組內(nèi)K-L距離和相對(duì)分歧，其中相對(duì)分歧定義為每個(gè)相對(duì)類條件密度和均值間的平均距離（文獻(xiàn)[14]）。與之前的基于高斯混合模型的視頻分割方法相比（文獻(xiàn)[9],[12],[13]），具有大的集群分歧的關(guān)鍵幀有利于基于高斯混合模型的視頻建模并且可以提供更好的魯棒性和同性質(zhì)的目標(biāo)分割結(jié)果。更有趣的是，由于關(guān)鍵幀提取受基于分歧的聚類標(biāo)準(zhǔn)支配，提取出來的關(guān)鍵幀很可能包含某些目標(biāo)行為或事件的信息，這些信息往往都是由那些空時(shí)聚類表示的。這里提出的方法和文獻(xiàn)[9],[12],[13]中提到的都具有一個(gè)主要的局限性，那就是高斯混合模型不足以處理不同低水平特征（例如顏色和運(yùn)動(dòng)）的混合目標(biāo)。不過這只是早期視覺的第一步，通過包含基于區(qū)域的特征就可以進(jìn)一步與互補(bǔ)方法結(jié)合起來，從而產(chǎn)生更多在語義上有意義的結(jié)果（文獻(xiàn)[4],[15]）。本文主要的目的就是要通過尋找用于混合高斯模型估計(jì)的或次優(yōu)的關(guān)鍵幀集合來提高目標(biāo)分割的性能，這里關(guān)鍵幀是副產(chǎn)物。本文是針對(duì)基于內(nèi)容的視頻分析新工具的初始研究，這些研究或許可以為MPEG-4/7標(biāo)準(zhǔn)引入一些新的幀或目標(biāo)的描述符和函數(shù)。
2. 融合關(guān)鍵幀提取和目標(biāo)分割
上面已經(jīng)集中對(duì)關(guān)鍵幀提取和目標(biāo)分割進(jìn)行討論了。我們首先簡(jiǎn)單的回顧一下幾個(gè)相關(guān)的方法。文獻(xiàn)[9]提出一種用于空時(shí)視頻建模的概率框架，這里在空時(shí)特征空間中用高斯“blob”表征目標(biāo)（同性質(zhì)的區(qū)域），該空間包含顏色（L，a，b），時(shí)間（t），坐標(biāo)（x和y）。用M階高斯混合模型對(duì)具有M個(gè)目標(biāo)的視頻進(jìn)行建模。用EM算法來估計(jì)模型參數(shù)，用MDL標(biāo)準(zhǔn)來尋找合適的M值。經(jīng)過高斯混合模型估計(jì)之后，通過MAP分類將視頻分割成M個(gè)空時(shí)塊。文獻(xiàn)[9]提出用分段執(zhí)行來處理非線性和非凸的運(yùn)動(dòng)模型。這種方法主要的瓶頸就是具有很高的計(jì)算負(fù)荷量，因?yàn)樵诨旌细咚鼓Ｐ凸烙?jì)時(shí)要涉及到所有的視頻幀。
文獻(xiàn)[12]提出一種融合關(guān)鍵幀提取和目標(biāo)分割的方法，用該方法來提高高斯混合模型估計(jì)的效率和魯棒性。首先利用逐幀的16×8二維色調(diào)和飽和度的顏色直方圖來提取得到初始關(guān)鍵幀（文獻(xiàn)[5]），并用得到的關(guān)鍵幀估計(jì)高斯混合模型。目標(biāo)分割之后，每個(gè)初始的關(guān)鍵幀都要用高斯混合模型進(jìn)行建模，這里實(shí)際上是用高斯混合模型對(duì)關(guān)鍵幀進(jìn)行修正。這種方法大幅度的減少了計(jì)算量，同時(shí)通過包含許多不同的關(guān)鍵幀的緊湊特征集提高了模型估計(jì)的魯棒性。另外，基于高斯混合模型的關(guān)鍵幀修正可能會(huì)得到更多的緊湊的關(guān)鍵幀。這種融合的方法帶來三個(gè)有趣的問題：1）在高斯混合模型估計(jì)或目標(biāo)分割方面如何保證提取到關(guān)鍵幀是的？2）我們可以同時(shí)使關(guān)鍵幀提取和目標(biāo)分割化嗎？3）如果問題2）的答案是肯定的話，那么提取到的關(guān)鍵幀是否有在語義上有用的信息呢（比如目標(biāo)的行為）？在本文中，我們將主要關(guān)注這些問題，具體是通過提出一種融合關(guān)鍵幀提取和目標(biāo)分割的方法來探索兩種之間可能的聯(lián)系和協(xié)同關(guān)系。
2.1問題描述
與用不同特征執(zhí)行關(guān)鍵幀提取和目標(biāo)分割相反，本文提出利用統(tǒng)一的特征空間來實(shí)現(xiàn)它們。
在這個(gè)N幀的視頻鏡頭包含三個(gè)主要的目標(biāo)，這三個(gè)目標(biāo)在特征空間中分別由聚類表征。通常，一個(gè)鏡頭中的數(shù)個(gè)幀表征一個(gè)空間和時(shí)間上連續(xù)的行為，并且共享公共的視覺和與語義有關(guān)的特征。因此就存在極大的冗余。另外那些可能隨機(jī)出現(xiàn)在幀邊界處的表示噪聲和無意義的目標(biāo)的不相關(guān)的異常值增加了特征空間中集群的重疊部分。冗余性和不相干性降低了統(tǒng)計(jì)建模的效率，因此可以通過去除冗余、不相干的數(shù)據(jù)和特征來提高建模的性能，換句話說可以通過選擇最緊密相關(guān)的數(shù)據(jù)和特征來進(jìn)行訓(xùn)練學(xué)習(xí)處理（文獻(xiàn)[17]）。在基于高斯混合模型視頻分割中，可以通過選擇更相關(guān)的關(guān)鍵幀進(jìn)行視頻建模，例如將關(guān)鍵幀提取構(gòu)想成目標(biāo)分割的特征選擇過程。
在文獻(xiàn)[18]中已經(jīng)就特征選擇方法進(jìn)行集中討論。給定一個(gè)初始候選特征集合
，特征選擇主要的目的就是從中選擇一個(gè)子集以便與分類性能有關(guān)的準(zhǔn)則判別函數(shù)可以優(yōu)化為：
（1）
選擇一個(gè)適當(dāng)?shù)氖呛苤匾?。一種常用的準(zhǔn)則就是選擇特征來近似真實(shí)的密度而不是去提取差別的特征。盡管希望這個(gè)準(zhǔn)則可以在不同的等級(jí)間產(chǎn)生較好的差別，但是這個(gè)假設(shè)并不總是有充分根據(jù)的，同時(shí)對(duì)于魯棒性分級(jí)，文獻(xiàn)[19]中提出基于分歧的特征選擇準(zhǔn)則。接下來我們將為特征選擇引入兩個(gè)基于分歧的準(zhǔn)則，然后在此基礎(chǔ)上得到新的融合關(guān)鍵幀提取和目標(biāo)分割的方法。
2.2平均組內(nèi)Kullback Leibler 距離（MAIKLD）
K-L距離（KLD）可以度量為聚類建模的兩個(gè)高斯分量的距離或相異性。給定由M個(gè)高斯組件表征的M個(gè)聚類，平均組內(nèi)KLD（AIKLD）定義如下：
（2）
這里是兩個(gè)高斯函數(shù)和的KLD距離，。理想情況下，AKLD越大，聚類間的獨(dú)立性就越大。由于關(guān)鍵幀提取被構(gòu)想為特征選擇過程，因此希望提取出具有平均組內(nèi)集群分歧的關(guān)鍵幀。假設(shè)是具有N幀的原始視頻鏡頭，這個(gè)鏡頭由具有基數(shù)的集合表示。再假設(shè)是的任一具有基數(shù)的子集。如果鏡頭中有M個(gè)目標(biāo)，那么目標(biāo)函數(shù)就定義為
（3）
這里是在MAIKLD方面的子集。根據(jù)文獻(xiàn)[20]，在最小貝葉斯誤差意義上說MAIKLD是的。如果使用0-1分類代價(jià)函數(shù)，就會(huì)產(chǎn)生后驗(yàn)概率估計(jì)。因此等式（3）的解決方式會(huì)得到的關(guān)鍵幀集合，這些關(guān)鍵幀可以使得目標(biāo)分割的差錯(cuò)率最小。窮舉搜索可以保證得到的，不過對(duì)于大的，這是計(jì)算昂貴且不切實(shí)際的，因?yàn)樾枰囼?yàn)個(gè)幀子集。因此次佳的但是計(jì)算量上更有效的解決方法將更為實(shí)際。這里使用文獻(xiàn)[21]中提到的確定性特征選擇方法，該方法叫做連續(xù)前向浮動(dòng)選擇（SFFS），并利用連續(xù)前向選擇（SFS）方法對(duì)SFFS進(jìn)行初始化（文獻(xiàn)[18]）。當(dāng)N不是非常大的話，SFFS可以找到的。本文中的關(guān)鍵幀都是從的候選關(guān)鍵幀中提取出的。高斯混合模型估計(jì)包含MDL方面的估計(jì)后，高斯函數(shù)和的KLD將由下式近似計(jì)算得到：
這里是所有待測(cè)候選關(guān)鍵幀的像素特征向量，表示第i個(gè)高斯組件的參數(shù)。然后利用式（2）計(jì)算AIKLD。這個(gè)搜索過程如下：（1）首先給定空集，n是的基數(shù)，即，且n的初始值為0；（2）使用SFS算法產(chǎn)生具有AIKLD的兩個(gè)候選關(guān)鍵幀的組合，并得到；（3）搜索一個(gè)在時(shí)具有AIKLD的候選關(guān)鍵幀，并把搜索到的加入集合中，同時(shí)令n=n+1；（4）如果n>2，就從中去除一個(gè)候選關(guān)鍵幀并對(duì)剩下的候選關(guān)鍵幀計(jì)算AIKLD，然后繼續(xù)（5），否則的話回到（3）；（5）確定去除一個(gè)候選關(guān)鍵幀后AIKLD是否增加。如果答案是肯定的話，就令n=n-1，然后回到（4），否則回到（3）。
當(dāng)n達(dá)到一個(gè)預(yù)定義的值時(shí)或在反復(fù)出現(xiàn)給定的值后，搜索就會(huì)停止。除了比文獻(xiàn)[9]使用所有幀效率更高外，該方法還有兩個(gè)主要的優(yōu)勢(shì)：1）可以提取出在MAIKLD方面或次優(yōu)的關(guān)鍵幀用于模型估計(jì)，與用顏色直方圖提取出的關(guān)鍵幀相比，這些關(guān)鍵幀可以為基于高斯混合模型的目標(biāo)分割提供更好的可辨別性（文獻(xiàn)[12]）；2）該算法比較靈活且?guī)缀鯖]有任何限制。不過有些問題還需要進(jìn)一步考慮，首先是當(dāng)很大的時(shí)候SFFS就無效了；其次，在關(guān)鍵幀提取前的基于MDL的高斯混合模型估計(jì)對(duì)時(shí)間敏感。有一個(gè)可供選擇的方法就是執(zhí)行基于高階高斯混合模型的SFFS，并且基于MDL的高斯混合模型估計(jì)只對(duì)關(guān)鍵幀執(zhí)行。但是如果基于高階高斯混合模型的話，視頻就會(huì)分段過多，從而導(dǎo)致更多的聚類源于同個(gè)語義目標(biāo)。為了增加同一目標(biāo)中聚類間的分歧，MAIKLD允許幀具有更多的異常值，這些異常值常導(dǎo)致遭受關(guān)鍵幀。不過要從待測(cè)的候選集中去除多余的候選關(guān)鍵幀是不可能的，為了降低計(jì)算量，我們提出另外一種基于分歧的準(zhǔn)則。
2.3相對(duì)分歧
文獻(xiàn)[14]提出相對(duì)分歧（MMD）準(zhǔn)則來進(jìn)行有效的基于熵原理的特征選擇，這是要在最小化信息冗余時(shí)維持輸入行為的信息的化。在分類的背景下，該方法往往選擇那些特征和類標(biāo)簽間互信息量的特征（文獻(xiàn)[14]）。如果將熵原理運(yùn)用到本文，那么目標(biāo)函數(shù)就可以寫成
（4）
這里是關(guān)鍵幀子集X和分類標(biāo)簽Y={1，2，...，M}間的互信息量。
考慮到I（X，Y）=H（Y）-H（Y|X），這里H（Y）是分類標(biāo)簽的熵。H(Y|X)是條件熵，有關(guān)貝葉斯誤差的下界和H（Y|X）的聯(lián)系來源于文獻(xiàn)[14]。這個(gè)關(guān)系表明最小化H(Y|X)(熵原理)等價(jià)于最小化貝葉斯誤差的下界。I(X,Y)可以如文獻(xiàn)[14]寫成：
（5）
這里，且。稱為相對(duì)分歧（MD），表示平均密度方差。文獻(xiàn)[14]的解釋表明，如果特征間的互信息量不受分類標(biāo)簽影響的話，那么I（X，Y）就可以用MD值的累加來近似，如。這樣一來的MI就變成了MMD。正如文獻(xiàn)[14]總結(jié)的，這個(gè)條件來自于目前對(duì)圖形統(tǒng)計(jì)學(xué)的研究，它可以表明一些圖形特征間的樣式屬性結(jié)構(gòu)也遵從一般的獨(dú)立于分類標(biāo)簽的統(tǒng)計(jì)學(xué)規(guī)則。這些特征通過各種生物學(xué)上的圖形變換提取出來，比如小波變換。雖然這個(gè)條件并不總是嚴(yán)格成立，但至少它表明MMD在最小貝葉斯誤差方面是近似的。
如果把MMD應(yīng)用到關(guān)鍵幀提取中，那么具有MD值的幀將被提取作為關(guān)鍵幀。類似于MAIKLD，MMD關(guān)鍵幀提取是在初始高斯混合模型估計(jì)之后執(zhí)行。不過MAIKLD需要測(cè)試不同的候選關(guān)鍵幀組合，而MMD只考慮每個(gè)幀的分歧忽略了交互幀的依賴性。候選關(guān)鍵幀的MD值可以如下近似計(jì)算：
這里是所有的像素特征向量，具有MD值的幀被選作關(guān)鍵幀。可以預(yù)定義，或自適應(yīng)確定一個(gè)MD值的門限。我們使用所有候選關(guān)鍵幀的平均MD值作為門限值，對(duì)于MD值大于門限的任何候選關(guān)鍵幀都被選作關(guān)鍵幀。
2.4提出算法
輸入的候選關(guān)鍵幀要么是一個(gè)鏡頭的所有幀，要么是最初由顏色直方圖選擇出來的關(guān)鍵幀（文獻(xiàn)[5],[12]）。顏色特征（Y，u，v），空間位置x-y，時(shí)間t一起組成統(tǒng)一的特征空間。用由EM算法和MDL準(zhǔn)則估計(jì)的高斯混合模型對(duì)輸入的視頻進(jìn)行建模。初始建模之后，利用MAIKLD或MMD指導(dǎo)關(guān)鍵幀的提取。提取出來的關(guān)鍵幀用于對(duì)高斯混合模型的重估計(jì)。即使進(jìn)行了初始的高斯混合模型估計(jì)，但是關(guān)鍵幀提取和模型重估計(jì)仍然是分離獨(dú)立執(zhí)行的，通過解釋它們?cè)诮y(tǒng)一的特征空間中的相互影響可以看出整個(gè)過程是統(tǒng)一的。與文獻(xiàn)[9]使用所有幀的方法或使用文獻(xiàn)[12]從顏色直方圖提取關(guān)鍵幀的方法相比，我們期望本文提出的方法不僅可以通過最小化特征冗余來提高計(jì)算效率，而且可以通過降低特征不相干性來增強(qiáng)視頻建模的魯棒性。
正如之前提到的，MAIKLD提取出具有聚類分歧的關(guān)鍵幀，并通過計(jì)算一組候選關(guān)鍵幀的AIKLD來考慮聚類的的統(tǒng)計(jì)特性，但是通過假設(shè)幀獨(dú)立對(duì)每個(gè)幀估計(jì)MD值，同時(shí)利用MMD選擇那些具有MD值的作為關(guān)鍵幀。因此就可以選擇出不同的關(guān)鍵幀，盡管都是由貝葉斯誤差限定下界。在基于高斯混合模型視頻建模的背景下，MAIKLD較MMD可以提取出更多有判別力的關(guān)鍵幀，因?yàn)槠骄芏确讲顩]有必要增大聚類分歧或降低聚類間的重疊。而MMD冒著忽略幀間附屬性質(zhì)的風(fēng)險(xiǎn)只考慮每個(gè)幀的聚類分歧。盡管如此，MMD在計(jì)算上仍然比MAIKLD具有更高的效率，因?yàn)椴恍枰M合搜索。
2.5關(guān)鍵幀特征
到此為止我們已經(jīng)討論了第二節(jié)提出的前兩個(gè)問題，現(xiàn)在將就基于新方法提取出的關(guān)鍵幀的特征繼續(xù)研究第三個(gè)問題。顯示了特征空間中的兩個(gè)聚類，該特征空間由空間（x-y），時(shí)間（t）以及兩個(gè)時(shí)間片（幀A和幀B）定義，這兩個(gè)時(shí)間片分別處于t=a和t=b的兩個(gè)聚類的空間位置，從而使得整個(gè)特征空間被分成三個(gè)部分。兩個(gè)聚類當(dāng)它們?cè)趨^(qū)域II（陰影區(qū)域）的x-y平面部分重疊時(shí)是空間最靠近的。如果聚類分別與兩個(gè)實(shí)體有關(guān)，那么實(shí)體在區(qū)域II的幀中也是空間臨近的，而在區(qū)域I或III的幀中則是遠(yuǎn)離的。通過理解MAIKLD或MMD用于關(guān)鍵幀提取的原理，我們可以確定低層次特征和高層次概念之間的聯(lián)系MAIKLD與最小化貝葉斯誤差是等價(jià)的，這是由特征空間中的聚類重疊引起的。為了最小化貝葉斯誤差，聚類分歧應(yīng)該化。因此MAIKLD往往在聚類具有最小重疊的地方提取關(guān)鍵幀，例如區(qū)域I和區(qū)域III。當(dāng)應(yīng)用MMD時(shí)，每個(gè)幀的MD值都要計(jì)算。平均密度具有充分大的差異的任何幀或換句話說聚類分散在x-y平面的任何幀將被提取作為關(guān)鍵幀。