基于雙向自適應(yīng)時(shí)空切片的關(guān)鍵幀提取算法

韓震博

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

1 視頻關(guān)鍵幀提取概述

隨著大數(shù)據(jù)時(shí)代的到來，網(wǎng)絡(luò)上的視頻數(shù)量大幅增加，如何快速且有效地在大量的視頻中找到所需要的視頻片段成為人們關(guān)注的熱點(diǎn)問題。

視頻是由連續(xù)變化的圖像幀組合而成，人們將這段連續(xù)的圖像幀中能夠有效地代表視頻主要內(nèi)容的幀稱為關(guān)鍵幀。關(guān)鍵幀提取技術(shù)在視頻處理領(lǐng)域中發(fā)揮著重要作用，通過對(duì)視頻中關(guān)鍵幀的提取，能有效地減少冗余信息，使得需要處理的數(shù)據(jù)量大大減少，為后續(xù)的視頻處理提供便捷。

目前，關(guān)鍵幀提取技術(shù)主要包括以下4類[1]：

（1）基于視頻運(yùn)動(dòng)信息的關(guān)鍵幀提?。?/p>

視頻中包含著大量的運(yùn)動(dòng)信息，可以通過對(duì)視頻中運(yùn)動(dòng)信息的提取及分析，實(shí)現(xiàn)視頻關(guān)鍵幀的提取，具體的方法包括基于運(yùn)動(dòng)特征的關(guān)鍵幀提取方法[2]、基于運(yùn)動(dòng)分析的關(guān)鍵幀提取方法[3]等。

（2）基于視頻內(nèi)容的關(guān)鍵幀提?。?/p>

這類方法使用視頻幀序列中每一幀圖像的紋理、顏色、形狀等底層特征作為關(guān)鍵幀提取的依據(jù)[4]。相鄰幀間特征差異的大小可以有效地反映出視頻內(nèi)容變化的顯著程度，因此可以通過這類方法完成關(guān)鍵幀的提取。

（3）基于視頻鏡頭信息的關(guān)鍵幀提?。?/p>

這類方法首先通過一定的方式，將視頻分割成若干個(gè)獨(dú)立的鏡頭，然后按照一定的規(guī)則在每個(gè)獨(dú)立的鏡頭中完成關(guān)鍵幀的提取。常用的方法有基于像素的關(guān)鍵幀提取方法[5]以及基于直方圖的關(guān)鍵幀提取方法[6]等。

（4）基于聚類的關(guān)鍵幀提?。?/p>

這類方法對(duì)視頻鏡頭間以及視頻鏡頭內(nèi)信息的關(guān)聯(lián)性進(jìn)行充分利用，基于幀間圖像的相似性對(duì)視頻序列進(jìn)行聚類，并從每一類聚類結(jié)果中選出一幀作為關(guān)鍵幀。常用的聚類方法包括K-means算法、層次聚類算法[7]等，各聚類算法有著不同的優(yōu)缺點(diǎn)。

2 基于雙向自適應(yīng)時(shí)空切片的關(guān)鍵幀提取算法

針對(duì)現(xiàn)有關(guān)鍵幀提取算法中常出現(xiàn)的存在漏幀、冗余幀等問題，本文提出了一種基于雙向自適應(yīng)時(shí)空切片的關(guān)鍵幀提取算法。這一部分將對(duì)本文中采用的關(guān)鍵技術(shù)及算法流程進(jìn)行介紹。

2.1 基于活動(dòng)強(qiáng)度圖的時(shí)空切片位置選擇

時(shí)空切片是一種高效的視頻時(shí)空分析方法，具有計(jì)算量低、抗干擾能力強(qiáng)等特點(diǎn)[8]。時(shí)空切片是將視頻幀序列中每一幀在選定的同一位置上的像素信息進(jìn)行提取，并組合成一幅具有完整的視頻時(shí)間維度信息的二維圖像。時(shí)空切片通常有三種取法：垂直切片、水平切片和對(duì)角線切片[9]，如圖1所示。

圖1時(shí)空切片示意圖

在進(jìn)行時(shí)空切片時(shí)，基本都是基于視頻幀中心點(diǎn)橫（縱）向的延伸線作為切片位置，但該切片位置并不一定屬于視頻中物體運(yùn)動(dòng)的區(qū)域，因此，基于該位置提取出的時(shí)空切片并不一定能較好地包含視頻中的物體運(yùn)動(dòng)信息。

為了獲取視頻中內(nèi)容變化的區(qū)域及強(qiáng)度，本文定義了活動(dòng)強(qiáng)度圖，其計(jì)算方式如下：首先，對(duì)圖像幀序列進(jìn)行灰度化處理；其次，從第一幀開始，計(jì)算相鄰兩幀在同一像素點(diǎn)上灰度值的差值，當(dāng)該值的絕對(duì)值大于設(shè)定的閾值時(shí)，則認(rèn)為該像素點(diǎn)在相鄰兩幀間變化明顯；如果同一像素點(diǎn)在相鄰兩幀間灰度值的差值的絕對(duì)值大于設(shè)定的閾值，那么將此值進(jìn)行累加，并將得到的值稱為該像素點(diǎn)的灰度變化累加值；最后將各個(gè)像素點(diǎn)的灰度變化累加值歸一化到[0,255]，即可得到活動(dòng)強(qiáng)度圖。活動(dòng)強(qiáng)度圖的計(jì)算公式如下：

式（4）中，I(x,y)為最終得到的活動(dòng)強(qiáng)度圖。

對(duì)一段“投擲鉛球”的視頻進(jìn)行活動(dòng)強(qiáng)度圖的提取，提取結(jié)果如圖2所示。

圖2活動(dòng)強(qiáng)度圖

在活動(dòng)強(qiáng)度圖中，灰度值越大的點(diǎn)代表該像素點(diǎn)的信息變化強(qiáng)度越大。因此在進(jìn)行時(shí)空切片時(shí)，可以選擇信息變化強(qiáng)度最大的行（列），作為時(shí)空切片的位置，使得提取到的時(shí)空切片中能夠包含更多的視頻信息。

2.2 基于切片位置自適應(yīng)的雙向時(shí)空切片方法

基于時(shí)空切片的關(guān)鍵幀提取效果在很大程度上受時(shí)空切片包含視頻中物體運(yùn)動(dòng)的信息量的影響，也就是說，為了得到更好地關(guān)鍵幀提取效果，時(shí)空切片中就要盡可能多地包含視頻中的物體運(yùn)動(dòng)信息。

本文提出的基于切片位置自適應(yīng)的雙向時(shí)空切片方法能夠有效地解決這一問題，一方面，基于活動(dòng)強(qiáng)度圖的時(shí)空切片位置選擇能夠保證在單一方向的時(shí)空切片中包含更多的圖像信息；另一方面，采用雙向時(shí)空切片可以在一定程度上解決單一方向的時(shí)空切片時(shí)空間信息匱乏的問題。仍以上述“投擲鉛球”的視頻為例，本文提取出的雙向時(shí)空切片圖像如圖3所示。

圖3雙向時(shí)空切片圖像

2.3 算法描述

下面是本文算法的整體步驟：

步驟一：提取視頻幀序列的活動(dòng)強(qiáng)度圖

對(duì)灰度化處理后的視頻幀序列進(jìn)行活動(dòng)強(qiáng)度圖的提??；

步驟二：選擇最佳時(shí)空切片位置

統(tǒng)計(jì)活動(dòng)強(qiáng)度圖中像素值最大的行和列，并將該行和該列分別作為此視頻幀序列進(jìn)行水平切片及垂直切片的位置；

步驟三：提取出視頻的雙向時(shí)空切片

根據(jù)最佳時(shí)空切片位置，提取出視頻幀序列的雙向時(shí)空切片；

步驟四：通過改進(jìn)K-means算法對(duì)提取出的雙向時(shí)空切片進(jìn)行聚類

使用改進(jìn)K-means算法對(duì)雙向時(shí)空切片圖進(jìn)行聚類。圖4所示為圖3的聚類結(jié)果。

圖4聚類結(jié)果

在聚類結(jié)果中，不同的顏色代表不同的類別。值得注意的是，由于視頻具有時(shí)間上的連續(xù)性，因此，將顏色相同但不連續(xù)的類視為不同的類別。

步驟五：對(duì)連續(xù)視頻幀數(shù)量少的類進(jìn)行處理

在對(duì)雙向的時(shí)空切片進(jìn)行聚類時(shí)，可能會(huì)出現(xiàn)較少數(shù)量的連續(xù)視頻幀被聚為一類的情況，這種情況往往是由于視頻中存在干擾信息所致，因此在這一類中提取出的關(guān)鍵幀往往不能很好地表達(dá)視頻信息。對(duì)此，本文采用如下的處理方案：當(dāng)連續(xù)3幀及以下的視頻幀被分為一類時(shí)，將這一類歸并到其相鄰的類中，若這一類兩側(cè)相鄰的類顏色相同，則將這一類與其兩側(cè)相鄰的類合并為一類；若這一類兩側(cè)相鄰的類顏色不同，則將這一類合并到相鄰兩類中聚類中心間的距離更近的那一類中。

步驟六：候選關(guān)鍵幀的提取

在完成對(duì)雙向時(shí)空切片的聚類后，選取每一類的聚類中心作為候選關(guān)鍵幀。

步驟七：篩選最終的關(guān)鍵幀

雙向的時(shí)空切片圖可以在一定程度上彌補(bǔ)單一方向時(shí)空切片的空間信息不足的問題，但二者一般會(huì)包含冗余信息，進(jìn)而導(dǎo)致提取出的候選關(guān)鍵幀存在冗余，因此需要對(duì)候選關(guān)鍵幀進(jìn)行進(jìn)一步的篩選。本文采用的篩選方法是通過計(jì)算相鄰候選關(guān)鍵幀之間的時(shí)間間隔進(jìn)行的，若相鄰候選幀間的時(shí)間間隔大于5幀，則認(rèn)為這兩幀間不存在冗余，均為最終的關(guān)鍵幀；否則，兩幀間存在冗余，保留兩幀中與各自聚類中心距離更近的幀作為最終的關(guān)鍵幀。

算法流程圖如圖5。

圖5算法流程圖

3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

本文實(shí)驗(yàn)環(huán)境如表1所示。

表1 實(shí)驗(yàn)環(huán)境

3.1 實(shí)驗(yàn)數(shù)據(jù)與評(píng)價(jià)指標(biāo)

本文方法是對(duì)整個(gè)視頻區(qū)域進(jìn)行活動(dòng)強(qiáng)度圖的提取，在視頻背景區(qū)域變化較小時(shí)，提取到的活動(dòng)強(qiáng)度圖能更為精確的反映視頻中物體的運(yùn)動(dòng)信息。因此，本文從體育、演講、汽車、太空四類視頻中分別選取三個(gè)視頻背景區(qū)域變化較小的視頻作為測試視頻。實(shí)驗(yàn)數(shù)據(jù)來源于UCF101數(shù)據(jù)集[10]以及開放的標(biāo)準(zhǔn)視頻庫[11]，實(shí)驗(yàn)中使用的測試視頻長度不一、分辨率不同、內(nèi)容差別明顯，能夠充分驗(yàn)證各關(guān)鍵幀提取方法的有效性。

目前，在視頻關(guān)鍵幀提取領(lǐng)域中存在多個(gè)較為通用的評(píng)價(jià)指標(biāo)，本文選取了查全率與查準(zhǔn)率兩個(gè)指標(biāo)來評(píng)價(jià)本文方法的性能。

（1）查全率

該指標(biāo)可以用來衡量關(guān)鍵幀漏檢的程度。計(jì)算公式如下：

式（5）中，Nc為提取正確的關(guān)鍵幀數(shù)量，Nm為漏檢的關(guān)鍵幀數(shù)量。

（2）查準(zhǔn)率

該指標(biāo)可以用來衡量提取到關(guān)鍵幀的準(zhǔn)確程度。計(jì)算公式如下：

式（6）中，Nf為誤檢的關(guān)鍵幀數(shù)量。

3.2 實(shí)驗(yàn)結(jié)果與分析

分別使用本文方法與直方圖法、文獻(xiàn)[12]提出的方法、文獻(xiàn)[13]提出的方法對(duì)測試視頻進(jìn)行關(guān)鍵幀的提取，并通過查全率、查準(zhǔn)率來衡量各方法的性能。實(shí)驗(yàn)結(jié)果如表2所示。

從實(shí)驗(yàn)結(jié)果可以看出，在不同的視頻類別下，本文方法提取關(guān)鍵幀的查全率與查準(zhǔn)率相較于各對(duì)比算法均有明顯的提升。由此可見，本文提出的基于雙向自適應(yīng)時(shí)空切片的關(guān)鍵幀提取算法性能優(yōu)良，使用該算法提取出的關(guān)鍵幀能夠較為準(zhǔn)確地完成對(duì)視頻主要內(nèi)容的表達(dá)。

表2 在不同視頻類別下各方法的查全率與查準(zhǔn)率統(tǒng)計(jì)

4 結(jié)語

本文提出了一種基于雙向自適應(yīng)時(shí)空切片的關(guān)鍵幀提取算法，通過引入活動(dòng)強(qiáng)度圖充分利用視頻的運(yùn)動(dòng)信息，進(jìn)而實(shí)現(xiàn)了垂直與水平方向上切片位置自適應(yīng)的時(shí)空切片方法，在使得后續(xù)聚類結(jié)果具有時(shí)間信息的同時(shí)，解決了傳統(tǒng)的固定位置時(shí)空切片、單一方向時(shí)空切片導(dǎo)致提取信息不足的問題，然后通過改進(jìn)Kmeans算法實(shí)現(xiàn)了閾值自適應(yīng)的候選關(guān)鍵幀提取，最終，對(duì)從兩幅時(shí)空切片圖中提取出的候選關(guān)鍵幀進(jìn)行進(jìn)一步的篩選，得到最終的關(guān)鍵幀。實(shí)驗(yàn)結(jié)果表明，本文方法在能夠保證較低壓縮比的情況下，查全率與查準(zhǔn)率明顯優(yōu)于同類算法，提取出的視頻幀能夠有效地反映視頻的主要內(nèi)容。