摘 要：介紹了一種新的視頻鏡頭變換類型檢測方法，利用局部線性嵌入算法提取鏡頭變換的一維流形特征，用K近鄰分類器確定漸變鏡頭變換的類型。實(shí)驗(yàn)表明，本算法鏡頭變換類型的識(shí)別率為97.5%以上。
關(guān)鍵詞：鏡頭邊界檢測; 漸變；流形學(xué)習(xí);局部線性嵌入
隨著日益豐富的視頻數(shù)據(jù)的出現(xiàn)，人們迫切期望能在大量視頻數(shù)據(jù)中方便、快速地檢索到自己感興趣的視頻段。而要實(shí)現(xiàn)視頻檢索，通常是先將視頻分割成獨(dú)立的視頻鏡頭。鏡頭是指一個(gè)攝像機(jī)鏡頭連續(xù)拍攝的一組內(nèi)在相關(guān)的連續(xù)幀，用來表現(xiàn)在時(shí)空上連續(xù)的一組運(yùn)動(dòng)，是視頻檢索的基本單元。鏡頭之間的變換通常分為切變（Cut）和漸變（Gradual）兩大類,其中漸變鏡頭變換又可分為溶解（Dissolve）、掃換（Wipe）、淡入（Fade in）與淡出（Fade out）[1-3]等。檢測出不同類型的鏡頭變換是對(duì)視頻高層內(nèi)容分析、分類、檢索和其他應(yīng)用的基礎(chǔ)，因此，對(duì)鏡頭類型變換檢測準(zhǔn)確性的高低將直接影響到后續(xù)處理效果。
視頻鏡頭類型檢測算法，從對(duì)視頻研究時(shí)起就得到廣泛的重視，主要表現(xiàn)在閾值選取[4]和特征度量[5]等兩個(gè)方面。其中閾值選取又分為固定閾值和自適應(yīng)閾值兩種，固定閾值選擇常常存在選擇閾值過高或過低的問題，造成查全率和誤檢率之間的矛盾；而自適應(yīng)閾值，在視頻處理過程中它的值要不斷調(diào)整，這要花費(fèi)大量時(shí)間用于計(jì)算合適的閾值。因此對(duì)鏡頭變換檢測算法的研究，特別是漸變鏡頭變換檢測依然是視頻分析與處理所研究的難點(diǎn)。
由于視頻鏡頭變換的多樣性以及視頻幀高維性的特點(diǎn)，很難從高維中尋找到它們內(nèi)在的特征，但通過選擇恰當(dāng)?shù)乃惴ㄔ诒３指呔S特征的情況下，把高維降到低維，然后通過分析低維中的數(shù)據(jù)，得出高維視頻變換的特征數(shù)據(jù)。根據(jù)流形學(xué)習(xí)的特性和視頻數(shù)據(jù)的特點(diǎn)，把視頻表示成一幅幅圖像隨著時(shí)間變化而變化的一個(gè)高維空間，圖像之間在時(shí)間軸上是局部相關(guān)的，圖像之間呈現(xiàn)出特有的分布，把這種分布，看成是一個(gè)低維的流形嵌入到高維空間中進(jìn)行處理。
1 基于局部線性嵌入（LLE）的視頻鏡頭變換學(xué)習(xí)
局部線性嵌入LLE（Locally Liner Embedding）[6]是流形學(xué)習(xí)中的一種。流形學(xué)習(xí)是從觀測到的現(xiàn)象中尋找事物的本質(zhì)，找到產(chǎn)生數(shù)據(jù)的內(nèi)在規(guī)律。本文用它來提取鏡頭之間的特征，以期得到對(duì)各種鏡頭分類的效果。
1.1 基于LLE特征提取
LLE算法是從流形的局部入手，一個(gè)局部鄰域上的流形可以近似看成是具有線性特征，在這個(gè)小的局部鄰域上的一個(gè)點(diǎn)就可以用它的相鄰點(diǎn)在最小二乘意義下最優(yōu)的線性表示，通過連接的鄰域就可以從局部逐步擴(kuò)展到整體，處理過程如下。
給定視頻Video，把視頻看成是由幀序列{f1,f2,…,fn}構(gòu)成的。
(1)將視頻幀序列fi（i=1，…，n）轉(zhuǎn)化為M×N(M、N為視頻的行數(shù)、列數(shù))的一維向量Fi，轉(zhuǎn)換后視頻幀變成n個(gè)f向量；
(2)用LLE算法提取鏡頭變換特征。
保存原流形中局部鄰域間的相互關(guān)系，將高維數(shù)據(jù)映射到一維全局坐標(biāo)系中，具體算法如下：
步驟1：鄰域點(diǎn)搜索。計(jì)算出每個(gè)向量Fi的鄰域點(diǎn)，通常取歐式距離最小的K個(gè)點(diǎn)為鄰域或者固定半徑ε的球狀鄰域。
步驟2：求重構(gòu)誤差最小。在Fi的鄰域中，計(jì)算能重構(gòu)每個(gè)Fi的權(quán)值Wij，使重構(gòu)誤差最小，即式(1)的值最小。
(3)特征提取
根據(jù)上面算法的步驟，把視頻中得到的n個(gè)f向量數(shù)據(jù)作為數(shù)據(jù)源，用到LLE算法中，經(jīng)過局部嵌入學(xué)習(xí)，求出一維向量Y，根據(jù)Y向量的值畫出如圖1所示的特征圖。
因LLE對(duì)K值敏感，不同的K值，即使特征值不同也有可能得到相同的特征曲線，圖1中算法的K值都取固定值15。對(duì)于2個(gè)鏡頭之間是切變變換，兩鏡頭變換處的2幀之間形成一個(gè)突然上升或下降的級(jí)躍，如圖1(a)所示；對(duì)于溶解型鏡頭變換，特征曲線表現(xiàn)為一個(gè)向下或向上的的光滑曲線，如圖1(b)所示；對(duì)于掃換型鏡頭變換，特征曲線表現(xiàn)為一個(gè)不光滑的鋸齒型曲線，如圖1(c)所示；對(duì)于淡入淡出型鏡頭變換，特征曲線成一個(gè)“n”形或類似于“n”形曲線，如圖1(d)所示。
為了便于特征的提取并能正確地反映鏡頭變化的過程，在提取特征時(shí)需選擇合適的點(diǎn)數(shù)（即幀數(shù)），本文選擇21個(gè)數(shù)據(jù)點(diǎn)作為鏡頭之間變換的過程進(jìn)行實(shí)驗(yàn)。如果鏡頭變換過程中幀的數(shù)目多于21幀，則要對(duì)其進(jìn)行抽樣，采用等間距地抽取數(shù)據(jù)點(diǎn)，如淡入淡出鏡頭變換特征曲線，變換過程中共有71幀，如圖2中的帶星號(hào)線所示，經(jīng)過抽樣等距點(diǎn)后，變換成圖2中左邊的無星號(hào)的特征曲線，仍然保持原來漸變過程變換的特征。
1.2 K近鄰視頻鏡頭學(xué)習(xí)
有了一維流形Y向量的數(shù)據(jù)，得到了視頻幀序列的一維線性曲線。根據(jù)線性曲線的特點(diǎn)，用K近鄰法對(duì)視頻序列進(jìn)行學(xué)習(xí)，找出鏡頭變換的類型。算法的流程如圖3所示。
(1)預(yù)處理鏡頭類型檢測；
(2)將步驟(1)中處理的數(shù)據(jù)分為兩部分，一部分作為學(xué)習(xí)集，另一部分作為測試集；
(3)提取鏡頭類型一維流形的特征，并根據(jù)預(yù)處理的鏡頭類型作相應(yīng)類型標(biāo)簽；
(4)通過K近鄰分類器測試測試集中鏡頭類型，并分出相應(yīng)類別的識(shí)別率。
2 實(shí)驗(yàn)與分析
2.1 選擇數(shù)據(jù)源
為了驗(yàn)證本文所述方法的有效性，在開放式視頻庫（www.open-video.org）中下載幾段視頻，各段視頻幀數(shù)、鏡頭類型數(shù)和鏡頭數(shù)量如表1所示。
2.2 實(shí)驗(yàn)比較與分析
從表1中抽取每種鏡頭數(shù)各30個(gè)，共120個(gè)，然后從120個(gè)鏡頭變換中隨機(jī)抽取每種各20個(gè)作為學(xué)習(xí)數(shù)據(jù)，剩下作為測試數(shù)據(jù)。用KNN分類器進(jìn)行分類，驗(yàn)證上述方法的實(shí)驗(yàn)結(jié)果及其受K值的影響情況。取相應(yīng)的 K值，實(shí)驗(yàn)結(jié)果數(shù)據(jù)如表2所示，不同K值實(shí)驗(yàn)結(jié)果如圖4所示。
圖4縱坐標(biāo)數(shù)值表示鏡頭變換類型的識(shí)別率，橫坐標(biāo)表示K近鄰分類器的不同K值。當(dāng)K值為3時(shí)，除溶解的識(shí)別率為90％外，其他三種變換類型的識(shí)別率都達(dá)到了100％。從圖4中可以看出，漸變識(shí)別率隨著K值的增加而下降。這是因?yàn)樵谔崛∏€特征，因幀數(shù)過多，間隔提取幀值時(shí)，造成漸變鏡頭特征曲線相互靠近，使?jié)u變鏡頭類型特征曲線可能互串。從平均識(shí)別率看，在K值為3時(shí)，識(shí)別可達(dá)97.5%；在K值為9時(shí)，識(shí)別率為77.5%。
本文提出了一種基于流形學(xué)習(xí)和K近鄰分類器相結(jié)合的鏡頭類型檢測方法。通過流形學(xué)習(xí)獲得了視頻幀的原始特征，便于把高維變換到低維來分析、處理。
今后還要做的工作有：針對(duì)漸變或漸變中的一種采用流形實(shí)現(xiàn)鏡頭變換的檢測；實(shí)現(xiàn)一個(gè)能自動(dòng)處理視頻鏡頭分割的系統(tǒng)，為關(guān)鍵幀提取、視頻摘要做好堅(jiān)實(shí)的基礎(chǔ)。
參考文獻(xiàn)
[1] 黃茜,張海泉,楊文亮，等. 基于灰度和直方圖的閾值自適應(yīng)鏡頭邊界檢測[J].科學(xué)技術(shù)與工程,2008,8(14):3787-3792.
[2] 耿玉亮,須德,馮松鶴.一種快速有效的視頻鏡頭邊界檢測方法[J].電子學(xué)報(bào),2006,34(12):2272-2277.
[3] 楊碧天,王煦法.一種漸變鏡頭檢測方法[J].計(jì)算機(jī)工程與應(yīng)用,2005(20):37-39.
[4] SZE K W , LAM K M ,QIU G .Scene cut detection using the colored pattern appearance model [A].IEEE ICIP-2003[C].Barcelona,Spain:IEEE Press,2003(2):1017-1020.
[5] YOUM S ,KIM W .Dynamic threshold method for scene change detection[A].IEEE ICME-2003[C].Baltimore,Maryland:IEEE Press,2003:337-340.
[6] 尹峻松,肖健,周宗潭，等.非線性流形學(xué)習(xí)方法的分析與應(yīng)用[J].自然科學(xué)進(jìn)展,2007,17(8):1015-1025.