基于操作树的移动视频编辑方法研究及实现

谢晓青，张　妍，姜丽红，蔡鸿明

(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