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