基于LCS算法的EDL可视化比对工具研究

郑晓发 李垚瑞

（1. 北京邮电大学 数字媒体与设计艺术学院，北京100876）

（2.中南民族大学 文学与新闻传播学院，湖北 武汉430074）

1 引言

EDL （Edit Decision List，编辑决策列表）文件是在不同编辑系统之间传输项目编辑信息最基本的交换文件格式之一。在最基本的EDL文件中，某一素材在时间线上的使用信息一般按照序号 （镜头号）——卷号——轨道类型——转场类型——源片段入点时码——源片段出点时码——时间线入点时码——时间线出点时码——源素材片段文件的顺序依次排列，例如 “004 AX AA C 00∶01∶08∶23 00∶07∶27∶17 00∶00∶00∶00 00∶06∶18∶24*FROM CLIP NAME：09.mp4”，代表了镜头号为004，源片段文件为09.mp4的镜头在剪辑时间线中的相关信息。

EDL文件已广泛应用在当下数字电影后期制作中。图1是数字电影后期制作的基本流程，包含素材转码、低码率文件剪辑、EDL 或XML 交互文件跨软件协作、成片输出等环节。其中，低码率文件可以使剪辑部门采用一般硬件配置计算机就能进行流畅剪辑，而剪辑部门输出的EDL 或XML 文件作为编辑信息交换文件，可以使后期时间线传递和管理更加高效。

在上述流程中，如果剪辑部门对已经交付给调色部门的时间线进行了修改，例如新增、删除了镜头，改变了镜头顺序，或是修改了镜头长度，而此时调色部门已经利用旧版时间线进行了大量调色工作，那么寻找和修改调色时间线上的镜头会变成一个较为繁杂的工作。由于几乎所有的非线性编辑软件都可以输出EDL 文件，因此利用EDL 文件进行时间线比对，发现并标识有调整的镜头，这对于提升后期各部门协同工作效率有较大帮助。

图1 数字电影后期制作流程图

本文根据现有数字电影后期制作需求及EDL文件的特点，拟开发EDL可视化比对工具。在第2部分，本文初步提出了基于 “C++ 和Qt Creator”进行文本比对及结果可视化开发的设计方案；第3部分根据设计方案进行EDL 比对工具的实际开发，以实现EDL 文件读取、EDL 文件中源素材片段信息修改点比对、比对结果可视化及输出功能。

2 EDL可视化比对工具设计

利用EDL进行可视化信息比对，需要将发生变化的源片段素材单独提取出来，同时将该片段的变动信息输出到文本文档，以方便查看不同剪辑版本中源片段素材变动的详细信息。因此，该EDL比对工具的功能需求为：

（1）实现EDL文件内容读取；

（2）比对出两个EDL文件中发生变动的源片段信息；

（3）直接在比对工具界面显示比对结果；

（4）将出现变动的源片段信息汇总，并输出文本文档，以便参与后期协同制作的相关工作人员使用。

2.1 EDL文件变动读取原理

当剪辑时间线上的素材发生变动时，EDL 文件里每条素材的信息相应也会发生变动。通过比对两个EDL文件内容的区别即可读出时间线上素材发生变动的情况。例如：

（1）当某一素材在剪辑时间线上的位置发生变化时，镜头序号以及素材录制出入点会发生变化，素材片段名称不变；

（2）当某一素材被其它素材片段替换时，素材片段名称会发生变化，镜头序号、素材录制出入点信息不变；

（3）当剪辑时间线上添加新素材时，文本文件中的总行数会发生变化。

需要注意的是，以上几个例子仅仅是讨论了最简单的几种情况，在实际剪辑中参数的变化有可能会更为复杂。例如，某一素材可能同时发生时间线上位置的变化和自身时长的变化；时间线上原本没有变动的其它素材有可能会因为某些素材的变化而产生录制出入点的变化；此外，时间线上素材片段数量的增加或减少也会带来原有素材片段部分参数的变化，例如录制出入点、镜头序号等。针对这种情况，需要首先判断时间线变动前后素材片段的数量有无增加或减少，再根据实际情况进行每条素材片段实际变化情况的判断。

综上所述，当时间线上的素材发生变动时，最先要读取的一般是总行数，接下来是每一行的内容，最后才是每一行中的具体参数。对于简单的时间线信息变动而言，最简单的比对方式是以行为单位进行比对。先通过比对总行数查找新增镜头与删除镜头，再通过比对每一行的内容读出是否有素材的替换或时长的变动。

2.2 EDL比对工具开发方案设计

基于EDL文件内容的特点，结合后期工作的需求，提出如下开发方案：

（1）比对时以行为单位：在实际EDL文件比对中，需要体现的除了 “时间线上的源片段素材有变动”，更多要体现的是“某一源片段素材在不同剪辑版本中发生了怎样的变化”。因此，比起以一整条时间线为单位进行整体判断，单独比较每一条源素材片段的变动情况更能直观体现整体时间线的变动。

（2）采用LCS算法进行比对：在比对两个EDL文件时，需要在新的EDL文件中搜索原有的素材片段在新剪辑时间线上的位置。因此，基于LCS算法将EDL文件中的每一行作为一个被比对的元素，进行逐行比对和匹配子串搜索。为了精简算法，实际比对中可先判断EDL文件前后编辑版本中行数是否相同，再根据LCS比对算法，在回溯过程中逐个提取符合要求的行。

（3）调取Qt库实现图形界面和结果可视化：可使用Python语言或C++语言进行EDL 文件的读取和比较，再调取Qt库完成图形界面和比对结果可视化的开发，从而使EDL文件的比对结果更加直观且具有可读性。

3 EDL可视化比对工具开发

3.1 EDL文件读取

Qt提供了可直接用于输入、输出二进制文件的QFile类，支持对文本文件或纯数据文件的读写，可直接调用file（）语句打开文件。

为了使用上更加方便，一般在实际操作中会搭配QDataStream 流或QTextStream 流使用。其中，QDataStream 流一般用于读取内容是纯二进制数据的文件。在读取EDL 文件时，使用了QText-Stream 流读取文件内容，将其中的信息作为文本字符处理。

在实际运用中，首先以QFile file （QIODevice∶∶Read Only|QIODevice∶∶Text）语句以只读方 式 打 开 EDL 文 件， 再 调 用 QTextStream in.readline（）命令按行读取EDL 文件。图2所示是Qt读取EDL中内容的显示结果。

图2 将EDL文件内容按行读取到文本框中

3.2 EDL文件内容比对

根据LCS比对算法，在回溯过程中逐个提取符合要求的行，最终执行实现比对EDL文件内容的功能。比对流程图如图3所示。

EDL文本比对时，需将提取匹配的子串添加到相应类型的子串中，并保存为一个自定义类。该类除了保存子串本身外，还同时保存子串比对结果。比对规则如下：

（1）若回溯到左上角单元格，则说明被比对的行完全相同，即这两行源素材信息是完全相同的，将比对结果设置为“same”；

图3 比对流程图

（2）若回溯到上边单元格，则说明该行信息可能出现了时间长度的增减、素材的替换或素材的删除。此时，需对该行信息的内容进行判断：如该行信息是时间码所在行，则说明该源素材片段出现了时间长短上的变动；如该行信息是文件名所在行，则说明该源素材片段可能被其它素材所替换。此时，将比对结果设置为 “modify”；若同时存在行数变动，则说明素材已遭删除，此时，将比对结果设置为“delete”；

（3）若回溯到左边单元格，则说明修改后的EDL文件中的时间线上增加了新的素材。此时，将比对结果设置为“Add”。

3.3 比对结果可视化显示

Qt库中提供了QPainter类，可用于在QWidget上绘制各种几何图形。在绘制几何图形时，要通过类对象的paint Event（）函数实现绘制功能。同时，Qt库中还提供了文本块QTextBlock类，可调用命令从文本文档中直接创建。一个文本块相当于一个段落。文本块顾名思义相当于一个矩形框架，用于将一段段的文本 “框”在其中。通过调用QRect F命令可直接在文本块上方创建矩形，再通过QPainter类中的draw Rect（）命令绘制矩形，用setPen （）命令调整所绘制矩形的颜色。

图4 可视化开发流程图

本EDL文件比对工具结果可视化开发的思路如图4所示。根据之前在执行比对命令时保存的差异所在处创建文本框，在文本块上方绘制相应颜色的矩形标注。为了使比对结果的可视化效果更加直观，可使用draw Line （）命令绘制直线，将EDL 文件新版本较之旧版本产生的变动以连线的方式在旧版本EDL文件中进行定位，方便查看。

图5 比对界面最终效果

根据上述开发思路，实现了以不同颜色标识镜头变动的可视化显示效果。最终比对结果可视化效果如图5所示。

3.4 比对结果文本输出

图6 输出保存比对结果流程图

在实现变动信息可视化显示的基础上，需实现变动信息的文本输出，具体思路如下：在EDL文件比对过程中，发生变动的源片段信息已根据不同的变动类型分类保存，因此输出文本时可根据不同类型，分类到不同的变换信息中，并调取相应的源片段镜头号即可。流程图如图6所示。

比对结果包含发生变动的EDL文件内容行及该条源素材信息发生变动的类型二者一同作为用户自定义类ZFileDiff Model被存放在了QList中。

QList是链表类，不能直接输出在其中存放的字符串。因此，若想输出被存放为自定义结构体ZFileDiff Model当中的比对结果信息到文本文档，首先要遍历存放在QList中的所有对象，然后将每个对象逐条提出，接着通过QDataStream 类中命令将每条信息写入新建的文本文件，最后调用QFile（）命令保存。

由于原先存放在QList中的元素是自定义结构体ZFileDiff Model，因此在使用QDataStream 命令前需要重载“和”操作符，使之可以适用于自定义结构体ZFileDiff Model。

图7 输出比对结果为txt文档

本输出算法最终实现了EDL变动信息的文本输出。图7所示为测试案例比对结果输出的txt文档。其中“add：001 005 006”表示新EDL 文件相对于旧文件新增了镜头001、005、006， “modify：002 003 004”表示镜头002、003、004修改了剪辑点。

4 结语

本文基于LCS最大公共子串比对算法执行EDL文件比对功能，设计并开发了针对EDL文件特点的按行比对工具，通过编写程序实现了比对结果的可视化。本方案最终实现了EDL 文件的读取、比对、比对结果可视化及文本输出。后续研究中，可扩展比对文件至AAF、XML 文件，以满足更多部门、更多设备的不同需求。目前成果可为相关从业人员提高后期工作效率提供参考。