謝曉青，張　妍，姜麗紅，蔡鴻明

(1.上海交通大學(xué) 軟件學(xué)院 上海 200240; 2.上海中興軟件有限責(zé)任公司，上海201203)

基于操作樹的移動視頻編輯方法研究及實現(xiàn)

謝曉青1，張妍2，姜麗紅1，蔡鴻明1

(1.上海交通大學(xué) 軟件學(xué)院 上海 200240; 2.上海中興軟件有限責(zé)任公司，上海201203)

提出一種基于操作樹的移動設(shè)備視頻處理方法和系統(tǒng)實現(xiàn)，將視頻編輯處理從移動端遷移到服務(wù)端，建立了前后端操作公共集并設(shè)計了一種操作樹構(gòu)建算法，根據(jù)操作集實現(xiàn)操作樹的構(gòu)建、解析以及視頻自動處理過程. 經(jīng)實驗驗證，本文提出的方法可將處理效率提高兩個數(shù)量級，豐富了處理類型并解決了移動端無法處理高清視頻的瓶頸.

操作樹；移動設(shè)備；視頻處理

近年來，移動視頻的社會化特征隨著移動用戶的社會化行為逐漸凸顯.國內(nèi)外流行著許多手機視頻編輯軟件，如美拍、Magisto等，視頻處理應(yīng)用的發(fā)展已逐漸從傳統(tǒng)的基于PC的應(yīng)用向以智能手機為代表的移動終端蔓延.當(dāng)前大多數(shù)移動視頻處理應(yīng)用的視頻編輯和處理過程都是直接在移動設(shè)備上進行，由于移動設(shè)備的硬件局限性，其直接進行視頻處理存在一系列問題，如只能支持簡單編輯操作的處理、處理效率低、處理時間長和處理效果較差等.對于復(fù)雜的編輯過程和高清視頻的處理，移動設(shè)備的處理能力難以有效支持.因此，如何克服移動設(shè)備的局限性為視頻編輯處理中的計算密集型服務(wù)提供有效支持成為值得研究的課題.

當(dāng)前移動設(shè)備上的視頻處理主要是通過降低分辨率、壓縮域處理和空間域處理3種方式進行.文獻[1]展示了一個從移動設(shè)備上大量的多媒體內(nèi)容中瀏覽和檢索視頻片段的系統(tǒng)，通過評估移動設(shè)備的屬性生成對應(yīng)的低分辨率視頻片段，從而保證代碼的精簡轉(zhuǎn)化，減少平均代碼轉(zhuǎn)換的延遲.文獻[2]引入一種用于提高HEVC (high efficiency video coding)跳過決策的方法，利用用戶在視頻分辨率、顯示分辨率和視敏度之間的不匹配處判斷出人類視覺系統(tǒng)難以注意到的編碼單元，從而跳過相對應(yīng)的編碼過程，減少編碼時間和比特率，解決了低分辨率顯示器的需求.文獻[3]提出了一個視頻質(zhì)量測量方法MCDE (mean compressed domain error) ，利用源視頻片段中的壓縮域信息在視頻轉(zhuǎn)碼應(yīng)用中客觀地預(yù)測轉(zhuǎn)換視頻的質(zhì)量，以微小的計算復(fù)雜性提供更高的視頻轉(zhuǎn)換質(zhì)量預(yù)測的準(zhǔn)確度.文獻[4]提出了一種在彩色視頻中進行數(shù)據(jù)嵌入的模式，根據(jù)一些像素在每個視頻幀的密度情況將數(shù)據(jù)嵌入相應(yīng)的藍(lán)色或紅色部分中.文獻[5]結(jié)合典型方法中的優(yōu)點，提出一個用于調(diào)整視頻中的對象移動的算法，該算法考慮了時間位置和對象速度，同時保持了不同對象間的交互軌跡，實現(xiàn)了在相同背景下保持同一空間位置中對象交互的前提下修改對象間的交互時間點.

基于PC端的視頻處理相關(guān)研究主要分為高清視頻處理、視頻特效處理和視頻實時處理3個方面.由于 H.264編碼器里的速率控制算法無法解決“盡力服務(wù)”的網(wǎng)絡(luò)上高清視頻的分流需求，因此，文獻[6]提出了動態(tài)恒定速度因素(DCRF)，一種用于H.264高清視頻會議的速度控制(HDVC)算法，從網(wǎng)絡(luò)帶寬、幀大小、PSNR(peak signal to noise ratio)和SSIM (structural similarity)等多個不同的方面進行分析，在給定視頻流實例下根據(jù)當(dāng)前的可用帶寬去調(diào)整視頻碼率，從而為高清視頻會議提供更好的質(zhì)量.文獻[7]提出了一種高清視頻幀速率上轉(zhuǎn)換的自適應(yīng)運動估計(ME)算法，ME算法通過適當(dāng)?shù)厥褂脙?yōu)化的候選搜索位置集和一些計算復(fù)雜度降低技術(shù)來實現(xiàn)計算量的減少和更高的視頻質(zhì)量.文獻[8]提出了一種基于管道的實施視頻渲染方案，在過程管理中使用了管道，視頻的后期效果以過濾器的形式呈現(xiàn)，結(jié)合了微內(nèi)核體系結(jié)構(gòu)、管道、多平臺支持以及 VLC(video LAN client)開源播放器多種技術(shù)，實現(xiàn)有效的管理流程和高效的數(shù)據(jù)處理.文獻[9]中提出了一種快速一致通過的方法用于高清視頻的高運動補償幀插值，基于基本的MCFI(motion compensated frame interpolation)模式實現(xiàn)4倍的幀率轉(zhuǎn)換.

移動終端上的降低分辨率和壓縮域處理的視頻處理方式是通過犧牲視頻質(zhì)量來縮短視頻處理時間，而空間域處理方式所需的處理時間較長.當(dāng)前的高清視頻處理、復(fù)雜特效處理以及視頻實時處理等相關(guān)技術(shù)發(fā)展已較為成熟，但大多是在基于PC機的環(huán)境中實現(xiàn)，其計算量龐大，對應(yīng)的技術(shù)在移動設(shè)備上難以實現(xiàn)良好的支持.本文針對當(dāng)前移動設(shè)備上視頻編輯處理存在的主要問題，提出視頻處理云端遷移方案，以基于操作集的方式進行視頻處理，同時考慮解決操作集中操作間的沖突問題提出構(gòu)建操作樹的算法，最后基于本文研究方法實現(xiàn)移動視頻處理系統(tǒng)，滿足移動設(shè)備下高清視頻以及復(fù)雜的視頻處理需求，并有效提高移動設(shè)備上的視頻處理效率.

1　云環(huán)境下移動視頻處理框架

移動用戶的規(guī)模隨著互聯(lián)網(wǎng)的發(fā)展而高速增長，大量用戶從對互聯(lián)網(wǎng)的訪問轉(zhuǎn)移到移動互聯(lián)網(wǎng)服務(wù). 近年來，視頻編輯處理服務(wù)成為一項服務(wù)熱點，移動終端的功能需求越來越高.視頻的剪切、分割、濾鏡、合成、添加圖片、添加音樂、添加字幕等功能是移動端視頻編輯處理需要滿足的功能需求；同時，移動終端上視頻編輯處理的效率成為了研究者們考慮的另一大因素.對高分辨率的視頻處理、多種視頻編輯操作的組合處理的支持以及視頻處理效率的優(yōu)化和提高是移動設(shè)備上視頻處理著重關(guān)注的性能需求.

視頻編輯屬于計算密集型的服務(wù)，而移動設(shè)備自身的計算和存儲能力有限且電池續(xù)航能力較差，在移動終端上若要保證視頻處理服務(wù)在性能上的需求，通常采用的方式是減少部分功能需求,比如針對限制時間長度的微視頻提供服務(wù)，實現(xiàn)微視頻的濾鏡、對微視頻添加音樂等；若要在移動設(shè)備上實現(xiàn)多種視頻處理功能，則在性能上難以滿足需求，比如對長視頻進行合成需要非常長的處理時間，難以達(dá)到令用戶滿意或接受的效率.

因此，本文以在移動設(shè)備上實現(xiàn)更多視頻處理功能需求并滿足性能需求為目標(biāo)，提出了一種移動視頻處理云端遷移的方案.云環(huán)境下移動視頻處理框架如圖1所示，主要包括應(yīng)用層、服務(wù)層和存儲層3部分.應(yīng)用層向服務(wù)層傳輸視頻文件、操作集、圖片和字幕等資源內(nèi)容，服務(wù)層進行視頻的處理過程并在處理完成后向應(yīng)用層返回處理結(jié)果視頻，而服務(wù)層與存儲層之間主要進行視頻文件、圖片、公共集等資源文件的存取交互過程.

圖1　云環(huán)境下移動視頻處理框架圖Fig.1　Mobile video processing framework in cloud environment

框架的3個層次分別包含不同的主要內(nèi)容.應(yīng)用層包含公共集的建立和維護、視頻編輯兩部分，其中的視頻編輯主要進行客戶端編輯視頻操作的捕獲并生成對應(yīng)的操作集.服務(wù)層包含公共集的建立和維護、操作樹的構(gòu)建、基于操作樹的視頻處理3個部分.其中公共集的建立和維護與應(yīng)用層中公共集的建立和維護包含相同的內(nèi)容；操作樹的構(gòu)建過程是根據(jù)從應(yīng)用層中接收的操作集進行操作樹結(jié)點的創(chuàng)建和沖突檢測的過程，最終形成一個對應(yīng)的操作樹；基于操作樹的視頻處理是對操作樹進行解析，并根據(jù)解析結(jié)果執(zhí)行對應(yīng)的視頻處理過程.存儲層包含對視頻、音頻、結(jié)構(gòu)化數(shù)據(jù)、圖像、文本等資源的存儲和管理.

2　基于操作樹的視頻處理

2.1操作公共集

操作公共集的建立能夠為移動端操作集的建立和服務(wù)端操作集的解析提供共同的依據(jù)，客戶端和服務(wù)端維護相同的操作公共集保證了前后端對視頻操作的一致性.

本文的操作公共集結(jié)構(gòu)如圖2所示，主要分為對象類和操作類兩個類別.對象類主要包含視頻、音頻、文字、圖片和水印，每個具體的對象類含有對應(yīng)的對象屬性. 操作類主要包含截取、合成、分割、角度旋轉(zhuǎn)、添加字幕、添加濾鏡、添加圖片、消音、提取音頻、添加水印、添加轉(zhuǎn)場和添加音樂,每種操作類對應(yīng)各自的操作參數(shù).

圖2　操作公共集結(jié)構(gòu)圖Fig.2　Structure of common operation set

2.2視頻操作樹模型

用戶在客戶端進行視頻編輯操作，操作順序的不同對視頻的最終處理結(jié)果有很大影響，如在同一個視頻片段上添加不同大小的Logo，不同的添加順序會導(dǎo)致不同的結(jié)果，而計算機解析出的操作順序和用戶在客戶端的編輯順序很可能不一致.為了有效避免由操作順序不一致引起的問題，本文提出一種視頻操作樹模型用于重新組織操作集中操作的先后順序.

2.2.1操作樹的定義

定義1 操作集(operation set)，指以時間為序列，視頻編輯用戶在一段時間內(nèi)所進行的操作集合.以O(shè)i(i∈[1,n])表示視頻操作，以O(shè)N表示操作集，ON= {Oi|Oi∈{O1，O2，…，On}&i∈[1,n]}.

定義2 操作樹結(jié)點(node)，是構(gòu)成操作樹的基本單元，用N表示操作樹結(jié)點，N用一個四元組來表示：

N=

(1) O(operations)，O=Oi,i∈[1,n]表示在該結(jié)點中對應(yīng)的視頻操作.

(2) PN(parents nodes)，PNi=Nj，j∈[1,n]，表示結(jié)點i的父結(jié)點Nj，每個操作樹結(jié)點至多有一個父結(jié)點.

(3) CN(children nodes)，CNi=(N1,N2,…，Nj)，j∈[1,n]，表示結(jié)點i的所有子結(jié)點.

(4) L(layer)，表示該結(jié)點在操作樹中對應(yīng)的層次，從第0層開始.

定義3 操作樹(operation tree, OT)，指根據(jù)視頻操作集生成的多叉樹.以O(shè)T表示操作樹，OT =(N0,N1,…,Nn)，即包含構(gòu)成操作樹的所有操作樹結(jié)點Ni，i∈[1,n].

2.2.2操作結(jié)點沖突檢測和處理

用戶進行的所有視頻編輯操作之間可能存在時間沖突和空間沖突.時間沖突指兩個操作對相同對象的視頻編輯點存在時間上的交叉.空間沖突指兩個操作對相同對象的編輯位置發(fā)生了重疊.針對這兩種沖突，本文通過改變操作結(jié)點間的關(guān)系進行處理，即根據(jù)操作在操作集上的先后順序，在構(gòu)建操作樹時后操作作為先操作的子結(jié)點.

2.2.3操作樹的構(gòu)建

本文提出一種操作樹的構(gòu)建算法，根據(jù)用戶的編輯操作所生成的操作集來構(gòu)建操作樹，算法流程的偽代碼如圖3所示.首先獲取操作集ON并創(chuàng)建一個操作樹的根結(jié)點N0，當(dāng)未到達(dá)操作集ON的末尾時，將ON中的每個操作Oi創(chuàng)建一個新的對應(yīng)操作樹結(jié)點Ni，然后對當(dāng)前的操作樹進行先序遍歷，遍歷過程中對每個遍歷的當(dāng)前結(jié)點Nk和結(jié)點Nj中對應(yīng)的操作進行沖突檢測，若存在沖突，則將Nj作為Nk的子結(jié)點添加到操作樹中，否則繼續(xù)以先序遍歷的形式遍歷操作樹并進行結(jié)點的沖突檢測，若遍歷結(jié)束后仍未檢測到?jīng)_突結(jié)點，則將Nj作為根結(jié)點N0的子結(jié)點添加到操作樹中.

圖3　操作樹構(gòu)建算法Fig.3　Construction algorithm of operation tree

2.3基于操作樹的視頻處理

通過2.2.3節(jié)所述的方法可由操作集構(gòu)建對應(yīng)的操作樹，再根據(jù)操作樹執(zhí)行基于操作樹的視頻處理，處理流程步驟如下：

(1) 獲取操作樹OT；

(2) 對操作樹OT進行廣度優(yōu)先遍歷，得到對應(yīng)的操作樹結(jié)點序列N1,N2,…,Nn；

(3) 對操作樹結(jié)點序列N1,N2,…,Nn進行操作序列的提取，得到對應(yīng)的視頻操作序列Oi,Oj,…,Ok；

(4) 從步驟(3)得到的視頻操作序列中讀取一個操作O；

(5) 判斷所讀取的操作是否為空，若為空，則表示操作序列已被全部讀取，結(jié)束視頻的處理流程；否則,解析讀取的操作，進入步驟(6)；

(6) 根據(jù)步驟(5)解析操作的結(jié)果進行相應(yīng)的視頻處理的調(diào)用；

(7) 回到步驟(4)，繼續(xù)從操作序列中讀取未被解析的操作.

2.4實例分析

以一個視頻處理實例進行基于操作樹的視頻處理過程的詳細(xì)說明.對一個時長為30 s的視頻myvideo進行如下編輯，其中的音樂1長度為5 s.

O1：截取(myvideo，00:01，13 s)；

O2：添加字幕(myvideo，00:01，2 s，[x=10，y=50]，“字幕1”)；

O3：截取(myvideo，00:03，8 s)；

O4：添加圖片(myvideo，00:02，3 s，[x=10，y=50]，“圖片1”)；

O5：添加音樂(myvideo，00:03，“音樂1”)；

O6：消音(myvideo，00:04，2 s)；

O7：添加字幕(myvideo，00:04，2 s，[x=10，y=50]，“字幕2”)；

上面的7個操作中，O3與O1存在時間沖突，O4與O2存在時間沖突和空間沖突，O7與O4存在時間沖突和空間沖突，O6和O5存在時間沖突.按2.2.3節(jié)所述方法構(gòu)建的操作樹如圖4所示.解析操作樹得到的結(jié)點序列為{N0, N1, N2, N5, N3, N4, N6, N7}，其中N0為根結(jié)點，不對應(yīng)任何視頻操作，所以結(jié)點序列對應(yīng)的操作序列為{ O1, O2, O5, O3, O4, O6, O7}，服務(wù)端再根據(jù)此操作序列執(zhí)行視頻處理過程.

圖4　操作樹示例圖Fig.4　A sample of operation tree

3　系統(tǒng)實現(xiàn)及驗證

3.1系統(tǒng)功能架構(gòu)

系統(tǒng)功能架構(gòu)如圖5所示，移動客戶端包含視頻編輯模塊，服務(wù)端主要包含用戶管理模塊、視頻管理模塊、權(quán)限管理模塊和視頻處理模塊，存儲層主要為資源存儲模塊.

圖5　系統(tǒng)功能架構(gòu)圖Fig.5　System functional architecture

3.2系統(tǒng)界面

系統(tǒng)實現(xiàn)界面包含安卓移動客戶端的實現(xiàn)界

面、操作集記錄界面以及后臺視頻管理界面.

3.3系統(tǒng)支持處理的視頻

系統(tǒng)支持常見手機視頻格式的視頻處理，包括MP4、 AVI、 MPEG以及MOV；支持不同分辨率的視頻處理，包括分辨率為640×480、 1 280×720和1 920×1 080的視頻；支持不同時長視頻的處理.當(dāng)前大多數(shù)應(yīng)用主要支持微視頻的處理，視頻時長為8～10 s, 而移動設(shè)備視頻處理應(yīng)用限制的最長拍攝視頻時間一般在30 s左右.因為長視頻的處理容易造成更多處理性能上的問題，因此本系統(tǒng)主要針對時間長度為30 s以內(nèi)的視頻處理進行研究.

3.4系統(tǒng)優(yōu)化效果

基于10 Mbit/s的網(wǎng)絡(luò)傳輸速度，進行5個操作集合(每個操作集合包含10個視頻原操作)對4種不同分辨率視頻的20次重復(fù)處理，分別使用直接在移動終端處理視頻的方法(優(yōu)化前)和本文中提出的基于操作樹的視頻處理方法(優(yōu)化后)進行處理并記錄處理時間，實驗數(shù)據(jù)如表1所示.實驗證明，本文提出的基于操作樹的移動設(shè)備視頻處理方法在效率上提高了兩個數(shù)量級，且能夠?qū)崿F(xiàn)一些在移動設(shè)備上無法實現(xiàn)的處理，如高清視頻的處理.

表1　實驗數(shù)據(jù)和結(jié)果Table 1　Experimental data and results

4　結(jié)　語

如何克服移動設(shè)備的局限性是移動設(shè)備上視頻編輯處理的瓶頸，本文提出的將視頻處理從移動端向服務(wù)端遷移，實現(xiàn)基于操作集的視頻處理，并設(shè)計出構(gòu)建操作樹的算法從而解決操作集中操作間的沖突問題，最后基于本文方法實現(xiàn)一個移動視頻處理系統(tǒng)，并通過實驗對比本文方案與移動終端上直接處理的方法，驗證了視頻處理效率的優(yōu)化效果及移動設(shè)備上實現(xiàn)復(fù)雜視頻編輯處理的可行性.

下一步的研究工作將包括不同網(wǎng)絡(luò)傳輸條件下對視頻處理效率造成的影響；對構(gòu)建操作樹的算法以及操作樹的解析過程進行優(yōu)化以更進一步符合用戶期望獲得的處理結(jié)果；考慮移動端和服務(wù)端融合處理的模式，對不同操作集進行歸類處理，同時結(jié)合移動端和服務(wù)端的優(yōu)勢來優(yōu)化解決方案.

[1] LIU Y, YANG Z H, DENG X Y, et al. Media browsing for mobile devices based on resolution adaptive recommendation[C]// IEEE International Conference on Communications and Mobile Computing.2009： 285-290.

[2] GARCIA R, ADZIC V, KALVA H. Adapting low bit rate skip mode in mobile environment[C]// IEEE Transactions on Circuits and Systems for Video Technology.2014.

[3] HUANG Y CH, TRAN V A, WANG Y. A compressed domain distortion measure for fast video transcoding[C]// Proceedings of the 15th Ainternational Conference on Multimedia. 2007:787-790.

[4] ASHOURIAN M, HONARMAND S, KAZEMI H. A low complexity data embedding scheme for video signal in the spatial domain[C]// Conference on Innovative Technologies in Intelligent Systems and Industrial Applications. 2009:17-19.

[5] LU S P, ZHANG S H, WEI J, et al. Timeling editing of objects in video[C]// IEEE Transactions on Visualization and Computer Graphics. 2012: 1218-1227.[6] JAVDTALABB A, OMIDYEGANEH M, SHIRMOHAMMANDI S, et al. A rate control algorithm for x264 high definition video conferencing[C]// IEEE International Conference on Multimedia and Expo. 2011:1-6.

[7] CETIN M, HANZAOGLU I. An adaptive true motion estimation algorithm for frame rate conversion of high definition video and its hardware implementations[C]// IEEE Transactions on Consumer Electronics. 2011: 923-931.

[8] LUO J, CHEN J B, HAN L, et al. Video after-effect rendering based on pipelining principle[C]// Sixth International Conference on Internet Computing for Science and Engineering. 2012：102-106.

[9] LEE Y L, NGUYEN T. High frame rate motion compensated frame interpolation in high-definition video processing[C]// IEEE International Conference on Acoustics Speech and Signal Processing. 2010: 858-861.

Research and Implementation of Mobile Video Editing Method Based on Operation Tree

XIEXiao-qing1，ZHANGYan2，JIANGLi-hong1，CAIHong-ming1

(1.School of Software, Shanghai Jiaotong University, Shanghai 200240, China；2.Shanghai Zhongxing Software Co. Ltd., Shanghai 201203，China )

A video processing method and the system implementation are presented based on operation tree that migrates the process of video editing to server . A common operation set of front and rear ends is created and an algorithm of constructing operation tree is proposed. The construction, parsing process of operation tree and the automatic video processing are based on the operation set. The experiment verifies that this method effectively improves the processing efficiency of two orders of magnitude, enriches video processing types and solves the bottleneck of high-definition video processing in mobile devices.

operation tree; mobile device; video processing

1671-0444(2015)04-0467-07

國家自然科學(xué)基金資助項目(61373030，71171132)；上海市自然科學(xué)基金資助項目(13ZR1419800)

謝曉青(1990—)，女，福建廈門人，碩士研究生，研究方向為信息可視化.E-mail：xiexiaoqing@sjtu.edu.cn

張妍(聯(lián)系人)，女，工程師，E-mail:zhang.yanyan1@zte.com.cn

TP 391

A

收稿時期：2015-03-25