基于操作樹的移動視頻編輯方法研究及實現

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

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

基于操作樹的移動視頻編輯方法研究及實現

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

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

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

操作樹；移動設備；視頻處理

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

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

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

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

1　云環境下移動視頻處理框架

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

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

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

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

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

2　基于操作樹的視頻處理

2.1操作公共集

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

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

圖2　操作公共集結構圖Fig.2　Structure of common operation set

2.2視頻操作樹模型

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

2.2.1操作樹的定義

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

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

N=

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

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

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

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

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

2.2.2操作結點沖突檢測和處理

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

2.2.3操作樹的構建

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

圖3　操作樹構建算法Fig.3　Construction algorithm of operation tree

2.3基于操作樹的視頻處理

通過2.2.3節所述的方法可由操作集構建對應的操作樹，再根據操作樹執行基于操作樹的視頻處理，處理流程步驟如下：

(1) 獲取操作樹OT；

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

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

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

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

(6) 根據步驟(5)解析操作的結果進行相應的視頻處理的調用；

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

2.4實例分析

以一個視頻處理實例進行基于操作樹的視頻處理過程的詳細說明.對一個時長為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節所述方法構建的操作樹如圖4所示.解析操作樹得到的結點序列為{N0, N1, N2, N5, N3, N4, N6, N7}，其中N0為根結點，不對應任何視頻操作，所以結點序列對應的操作序列為{ O1, O2, O5, O3, O4, O6, O7}，服務端再根據此操作序列執行視頻處理過程.

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

3　系統實現及驗證

3.1系統功能架構

系統功能架構如圖5所示，移動客戶端包含視頻編輯模塊，服務端主要包含用戶管理模塊、視頻管理模塊、權限管理模塊和視頻處理模塊，存儲層主要為資源存儲模塊.

圖5　系統功能架構圖Fig.5　System functional architecture

3.2系統界面

系統實現界面包含安卓移動客戶端的實現界

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

3.3系統支持處理的視頻

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

3.4系統優化效果

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

表1　實驗數據和結果Table 1　Experimental data and results

4　結　語

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

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

[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

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

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

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

TP 391

A

收稿時期：2015-03-25