基于機器視覺的智能導盲系統中關鍵幀提取方法的研究

摘 要：本文提出二次聚類的方法，第一次以鏡頭內相鄰兩幀的相似度為數據樣本進行聚類（分成兩類），計算確定第二次聚類所需的閾值；第2次采用動態聚類的ISODA TA算法，以視頻序列的幀為數據樣本進行聚類，最終獲得聚類結果。實驗結果表明了此算法在鏡頭分割和關鍵幀提取方面的有效性。

關鍵詞：關鍵幀；聚類；自適應閾值

中圖分類號：TP242 文獻標識碼：A 文章編號：1674-7712 （2013） 24-0000-02

一、概述

本文主要研究在基于機器視覺的智能導盲系統中鏡頭捕獲和關鍵幀的提取的部分。目前國內外有很多的關鍵幀提取技術。文獻[1]計算當前幀與已存在的每個聚類中心之間的距離，同預先指定的閾值相比較，若當前幀有所有聚類中心間的距離均大于該閾值，則從該幀開始形成一個新類別，否則將其分配到離它最近的類中。顯然，關鍵幀數有類別數確定，而類別數有取決于制定的閾值。比較文獻[1]中的方法，本文在實現中采用基于自適應閾值自動提取關鍵幀的聚類算法來進行鏡頭分割和關鍵幀提取。

二、鏡頭分割與關鍵幀提取算法

本文采用HSV顏色累積直方圖和MPEG-7中推薦的邊緣直方圖描述符作為視覺特征。將H、S、V分別分為8、4、1個級別，得到一個32維的顏色特征向量，記為fc。再對每幀提取邊緣直方圖，得到一個80維的紋理特征向量，記為ft。為了消除各特征向量取值范圍差異性的影響，對其進行高斯歸一化。Fic.k表示第i幀的第k個顏色分量，Fit.k k表示第i幀的第k個紋理分量，則計算兩幀間相似度的公式為

Sim（Fi，Fj）=w1 （1）。其中，w1和w2分別為顏色特征和紋理特征的權值，在此處取值0.5。

自適應計算閾值的算法，即第1次聚類：（1）設一個鏡頭中有N幀{F1，F2，F3，…，Fn}，連續讀入，利用式（1）求相鄰兩幀的相似度，得到數組Dif={D1，D2，…，DN-1}；（2）以Dif中的元素作為一維數據空間的樣本，進行聚類，分為兩類。為提高算法效率，先對Dif的元素由大到小排序，假設排序后有：D1≥D2≥…≥DN-1，令T=argmin2w （2）。其中，argmin2w=qH2H+qL2L，qH=T，qL=N-T-1，H=i，H=i，2H=2，2L=2，則DT就是所求閾值。

在得到初始的類別數和初始類的劃分后，采用ISODATA算法對鏡頭中的所有幀再進行動態聚類，即第2次聚類，采用自適應確定閾值的方法設置7個參數。K：期望得到的最大聚類數，取值為（每秒視頻包含25幀）；

：一類中的最少樣本數，取值為12（約0.5s）；

：標準偏差參數，取DT所對應那兩幀（和）各特征分量之差的絕對值，即={||，||，….；||}；：合并參數，根據（2）求取預知的算法來求出DT；L：每次迭代允許合并的最大聚類對數，取值；I：允許迭代的次數，本文中取值為5（測試取值可任意）。

參數K，L和I的值與視頻內容無關，對所有鏡頭可以指定相同的值，與頻內容有關的閾值和是通過計算得到的。設初始聚類數為C，初始聚類為{Γi}，各類中心為，i=1，2，…，c。設類中心為的類Γj分裂成兩個類中心分別為mj+和mj-的聚類，應把原來的取消，且令c增1。為了避免手工設定閾值的隨意性，考慮到新的兩類的類中心之間應盡可能相距得遠些，首先求類Γj中相距最遠的兩幀，記為和，然后采用下式計算兩個類中心：mj+=（mj+Fi）/2，mj-=（mj+Fk）/2，

計算類Γj中每幀與兩個新類中心的距離，將其歸入較近的類中。在得到最終聚類后，從每一類中提取離類中心最近的幀作為關鍵幀。實驗證明了該方法行之有效。

三、算法效率及結果分析

設N為視頻序列中的幀數，d是視頻特征的維數，C為類別數，T為迭代次數。本算法中第1次聚類的時間復雜度是O（Nd）；第2次聚類的時間復雜度為O（NdCT）；從理論上分析，本文提出的計算mj+和mj-的算法在最壞情況下時間復雜度為O（N2d），但實際上執行分裂步驟的概率很小，而且需要分裂的類中所包含的幀數比整個鏡頭中所含幀數少得多，故總的時間復雜度為O（NdCT+N2d）。對文獻[2]和文獻[3]中算法的時間復雜度進行分析。參考文獻[1]中，一次K均值聚類的時間復雜度為O（NdCT）。共執行了+10次，總的時間復雜度為O（N2dCT）。

在Windows7環境下，用VC++編程實現本算法。對于不同特點的視頻序列在這里做了大量的測試，現以2個鏡頭為例分析。

圖1（帶前景的目標運動）顯示的是一組視頻序列最終提取的關鍵幀，該幀背景靜止，移動目標在做中速運動，整個過程耗時1分鐘，共304幀。由于目標中速前進，因而相鄰兩幀之間的差別不大，使類分散度的最小閾值在Dif中的排序趨于中間，相應的初始聚類數也會較多。

圖2是一組沒有前景的動作的緩慢鏡頭，它的分割閾值為T=0.81，可以過得看出圖2的鏡頭相對較長，但卻只表明了目標緩慢轉動的這么一個動作，因此抽取圖2中的兩幅，即（a）幀圖片與（d）幀圖片作為該鏡頭的關鍵幀足以。所以，該算法提取出的關鍵幀能夠有效的刻畫鏡頭的主要內容。

四、結束語

用于機器視覺的智能導盲系統的鏡頭分割和關鍵幀提取則采用的是自適應閾值的聚類算法。第2次聚類所需要的閾值是在第一次聚類的基礎上獲得的，避免了人為指定聚類數對實驗結果的影響。從大量的實驗結果來看，該算法取得了較理想的效果。

參考文獻：

[1]陸海斌，章毓晉.一種高效視頻切變檢測算法[J].中國圖像圖形學報，1999（01）.

[2]金紅，周源華.梅承力用非監督式聚類進行視頻鏡頭分割[J].紅外與激光工程，2000（05）.

[3]劉政凱，湯曉鷗.視頻檢索中鏡頭分割方法綜述[J].計算機工程與應用，2002（23）.

[作者簡介]樊瑞蘭（1990.09-），女，陜西寶雞人，本科，研究方向：自適應閾值的關鍵幀提取。

[基金項目]2012年地方高校國家級大學生創新創業訓練計劃項目：基于機器視覺的智能導盲系統（201211080012）。