基于LCS算法的EDL可視化比對工具研究

鄭曉發(fā) 李垚瑞

（1. 北京郵電大學(xué) 數(shù)字媒體與設(shè)計(jì)藝術(shù)學(xué)院，北京100876）

（2.中南民族大學(xué) 文學(xué)與新聞傳播學(xué)院，湖北 武漢430074）

1 引言

EDL （Edit Decision List，編輯決策列表）文件是在不同編輯系統(tǒng)之間傳輸項(xiàng)目編輯信息最基本的交換文件格式之一。在最基本的EDL文件中，某一素材在時(shí)間線上的使用信息一般按照序號 （鏡頭號）——卷號——軌道類型——轉(zhuǎn)場類型——源片段入點(diǎn)時(shí)碼——源片段出點(diǎn)時(shí)碼——時(shí)間線入點(diǎn)時(shí)碼——時(shí)間線出點(diǎn)時(shí)碼——源素材片段文件的順序依次排列，例如 “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的鏡頭在剪輯時(shí)間線中的相關(guān)信息。

EDL文件已廣泛應(yīng)用在當(dāng)下數(shù)字電影后期制作中。圖1是數(shù)字電影后期制作的基本流程，包含素材轉(zhuǎn)碼、低碼率文件剪輯、EDL 或XML 交互文件跨軟件協(xié)作、成片輸出等環(huán)節(jié)。其中，低碼率文件可以使剪輯部門采用一般硬件配置計(jì)算機(jī)就能進(jìn)行流暢剪輯，而剪輯部門輸出的EDL 或XML 文件作為編輯信息交換文件，可以使后期時(shí)間線傳遞和管理更加高效。

在上述流程中，如果剪輯部門對已經(jīng)交付給調(diào)色部門的時(shí)間線進(jìn)行了修改，例如新增、刪除了鏡頭，改變了鏡頭順序，或是修改了鏡頭長度，而此時(shí)調(diào)色部門已經(jīng)利用舊版時(shí)間線進(jìn)行了大量調(diào)色工作，那么尋找和修改調(diào)色時(shí)間線上的鏡頭會(huì)變成一個(gè)較為繁雜的工作。由于幾乎所有的非線性編輯軟件都可以輸出EDL 文件，因此利用EDL 文件進(jìn)行時(shí)間線比對，發(fā)現(xiàn)并標(biāo)識(shí)有調(diào)整的鏡頭，這對于提升后期各部門協(xié)同工作效率有較大幫助。

圖1 數(shù)字電影后期制作流程圖

本文根據(jù)現(xiàn)有數(shù)字電影后期制作需求及EDL文件的特點(diǎn)，擬開發(fā)EDL可視化比對工具。在第2部分，本文初步提出了基于 “C++ 和Qt Creator”進(jìn)行文本比對及結(jié)果可視化開發(fā)的設(shè)計(jì)方案；第3部分根據(jù)設(shè)計(jì)方案進(jìn)行EDL 比對工具的實(shí)際開發(fā)，以實(shí)現(xiàn)EDL 文件讀取、EDL 文件中源素材片段信息修改點(diǎn)比對、比對結(jié)果可視化及輸出功能。

2 EDL可視化比對工具設(shè)計(jì)

利用EDL進(jìn)行可視化信息比對，需要將發(fā)生變化的源片段素材單獨(dú)提取出來，同時(shí)將該片段的變動(dòng)信息輸出到文本文檔，以方便查看不同剪輯版本中源片段素材變動(dòng)的詳細(xì)信息。因此，該EDL比對工具的功能需求為：

（1）實(shí)現(xiàn)EDL文件內(nèi)容讀取；

（2）比對出兩個(gè)EDL文件中發(fā)生變動(dòng)的源片段信息；

（3）直接在比對工具界面顯示比對結(jié)果；

（4）將出現(xiàn)變動(dòng)的源片段信息匯總，并輸出文本文檔，以便參與后期協(xié)同制作的相關(guān)工作人員使用。

2.1 EDL文件變動(dòng)讀取原理

當(dāng)剪輯時(shí)間線上的素材發(fā)生變動(dòng)時(shí)，EDL 文件里每條素材的信息相應(yīng)也會(huì)發(fā)生變動(dòng)。通過比對兩個(gè)EDL文件內(nèi)容的區(qū)別即可讀出時(shí)間線上素材發(fā)生變動(dòng)的情況。例如：

（1）當(dāng)某一素材在剪輯時(shí)間線上的位置發(fā)生變化時(shí)，鏡頭序號以及素材錄制出入點(diǎn)會(huì)發(fā)生變化，素材片段名稱不變；

（2）當(dāng)某一素材被其它素材片段替換時(shí)，素材片段名稱會(huì)發(fā)生變化，鏡頭序號、素材錄制出入點(diǎn)信息不變；

（3）當(dāng)剪輯時(shí)間線上添加新素材時(shí)，文本文件中的總行數(shù)會(huì)發(fā)生變化。

需要注意的是，以上幾個(gè)例子僅僅是討論了最簡單的幾種情況，在實(shí)際剪輯中參數(shù)的變化有可能會(huì)更為復(fù)雜。例如，某一素材可能同時(shí)發(fā)生時(shí)間線上位置的變化和自身時(shí)長的變化；時(shí)間線上原本沒有變動(dòng)的其它素材有可能會(huì)因?yàn)槟承┧夭牡淖兓a(chǎn)生錄制出入點(diǎn)的變化；此外，時(shí)間線上素材片段數(shù)量的增加或減少也會(huì)帶來原有素材片段部分參數(shù)的變化，例如錄制出入點(diǎn)、鏡頭序號等。針對這種情況，需要首先判斷時(shí)間線變動(dòng)前后素材片段的數(shù)量有無增加或減少，再根據(jù)實(shí)際情況進(jìn)行每條素材片段實(shí)際變化情況的判斷。

綜上所述，當(dāng)時(shí)間線上的素材發(fā)生變動(dòng)時(shí)，最先要讀取的一般是總行數(shù)，接下來是每一行的內(nèi)容，最后才是每一行中的具體參數(shù)。對于簡單的時(shí)間線信息變動(dòng)而言，最簡單的比對方式是以行為單位進(jìn)行比對。先通過比對總行數(shù)查找新增鏡頭與刪除鏡頭，再通過比對每一行的內(nèi)容讀出是否有素材的替換或時(shí)長的變動(dòng)。

2.2 EDL比對工具開發(fā)方案設(shè)計(jì)

基于EDL文件內(nèi)容的特點(diǎn)，結(jié)合后期工作的需求，提出如下開發(fā)方案：

（1）比對時(shí)以行為單位：在實(shí)際EDL文件比對中，需要體現(xiàn)的除了 “時(shí)間線上的源片段素材有變動(dòng)”，更多要體現(xiàn)的是“某一源片段素材在不同剪輯版本中發(fā)生了怎樣的變化”。因此，比起以一整條時(shí)間線為單位進(jìn)行整體判斷，單獨(dú)比較每一條源素材片段的變動(dòng)情況更能直觀體現(xiàn)整體時(shí)間線的變動(dòng)。

（2）采用LCS算法進(jìn)行比對：在比對兩個(gè)EDL文件時(shí)，需要在新的EDL文件中搜索原有的素材片段在新剪輯時(shí)間線上的位置。因此，基于LCS算法將EDL文件中的每一行作為一個(gè)被比對的元素，進(jìn)行逐行比對和匹配子串搜索。為了精簡算法，實(shí)際比對中可先判斷EDL文件前后編輯版本中行數(shù)是否相同，再根據(jù)LCS比對算法，在回溯過程中逐個(gè)提取符合要求的行。

（3）調(diào)取Qt庫實(shí)現(xiàn)圖形界面和結(jié)果可視化：可使用Python語言或C++語言進(jìn)行EDL 文件的讀取和比較，再調(diào)取Qt庫完成圖形界面和比對結(jié)果可視化的開發(fā)，從而使EDL文件的比對結(jié)果更加直觀且具有可讀性。

3 EDL可視化比對工具開發(fā)

3.1 EDL文件讀取

Qt提供了可直接用于輸入、輸出二進(jìn)制文件的QFile類，支持對文本文件或純數(shù)據(jù)文件的讀寫，可直接調(diào)用file（）語句打開文件。

為了使用上更加方便，一般在實(shí)際操作中會(huì)搭配QDataStream 流或QTextStream 流使用。其中，QDataStream 流一般用于讀取內(nèi)容是純二進(jìn)制數(shù)據(jù)的文件。在讀取EDL 文件時(shí)，使用了QText-Stream 流讀取文件內(nèi)容，將其中的信息作為文本字符處理。

在實(shí)際運(yùn)用中，首先以QFile file （QIODevice∶∶Read Only|QIODevice∶∶Text）語句以只讀方 式 打 開 EDL 文 件， 再 調(diào) 用 QTextStream in.readline（）命令按行讀取EDL 文件。圖2所示是Qt讀取EDL中內(nèi)容的顯示結(jié)果。

圖2 將EDL文件內(nèi)容按行讀取到文本框中

3.2 EDL文件內(nèi)容比對

根據(jù)LCS比對算法，在回溯過程中逐個(gè)提取符合要求的行，最終執(zhí)行實(shí)現(xiàn)比對EDL文件內(nèi)容的功能。比對流程圖如圖3所示。

EDL文本比對時(shí)，需將提取匹配的子串添加到相應(yīng)類型的子串中，并保存為一個(gè)自定義類。該類除了保存子串本身外，還同時(shí)保存子串比對結(jié)果。比對規(guī)則如下：

（1）若回溯到左上角單元格，則說明被比對的行完全相同，即這兩行源素材信息是完全相同的，將比對結(jié)果設(shè)置為“same”；

圖3 比對流程圖

（2）若回溯到上邊單元格，則說明該行信息可能出現(xiàn)了時(shí)間長度的增減、素材的替換或素材的刪除。此時(shí)，需對該行信息的內(nèi)容進(jìn)行判斷：如該行信息是時(shí)間碼所在行，則說明該源素材片段出現(xiàn)了時(shí)間長短上的變動(dòng)；如該行信息是文件名所在行，則說明該源素材片段可能被其它素材所替換。此時(shí)，將比對結(jié)果設(shè)置為 “modify”；若同時(shí)存在行數(shù)變動(dòng)，則說明素材已遭刪除，此時(shí)，將比對結(jié)果設(shè)置為“delete”；

（3）若回溯到左邊單元格，則說明修改后的EDL文件中的時(shí)間線上增加了新的素材。此時(shí)，將比對結(jié)果設(shè)置為“Add”。

3.3 比對結(jié)果可視化顯示

Qt庫中提供了QPainter類，可用于在QWidget上繪制各種幾何圖形。在繪制幾何圖形時(shí)，要通過類對象的paint Event（）函數(shù)實(shí)現(xiàn)繪制功能。同時(shí)，Qt庫中還提供了文本塊QTextBlock類，可調(diào)用命令從文本文檔中直接創(chuàng)建。一個(gè)文本塊相當(dāng)于一個(gè)段落。文本塊顧名思義相當(dāng)于一個(gè)矩形框架，用于將一段段的文本 “框”在其中。通過調(diào)用QRect F命令可直接在文本塊上方創(chuàng)建矩形，再通過QPainter類中的draw Rect（）命令繪制矩形，用setPen （）命令調(diào)整所繪制矩形的顏色。

圖4 可視化開發(fā)流程圖

本EDL文件比對工具結(jié)果可視化開發(fā)的思路如圖4所示。根據(jù)之前在執(zhí)行比對命令時(shí)保存的差異所在處創(chuàng)建文本框，在文本塊上方繪制相應(yīng)顏色的矩形標(biāo)注。為了使比對結(jié)果的可視化效果更加直觀，可使用draw Line （）命令繪制直線，將EDL 文件新版本較之舊版本產(chǎn)生的變動(dòng)以連線的方式在舊版本EDL文件中進(jìn)行定位，方便查看。

圖5 比對界面最終效果

根據(jù)上述開發(fā)思路，實(shí)現(xiàn)了以不同顏色標(biāo)識(shí)鏡頭變動(dòng)的可視化顯示效果。最終比對結(jié)果可視化效果如圖5所示。

3.4 比對結(jié)果文本輸出

圖6 輸出保存比對結(jié)果流程圖

在實(shí)現(xiàn)變動(dòng)信息可視化顯示的基礎(chǔ)上，需實(shí)現(xiàn)變動(dòng)信息的文本輸出，具體思路如下：在EDL文件比對過程中，發(fā)生變動(dòng)的源片段信息已根據(jù)不同的變動(dòng)類型分類保存，因此輸出文本時(shí)可根據(jù)不同類型，分類到不同的變換信息中，并調(diào)取相應(yīng)的源片段鏡頭號即可。流程圖如圖6所示。

比對結(jié)果包含發(fā)生變動(dòng)的EDL文件內(nèi)容行及該條源素材信息發(fā)生變動(dòng)的類型二者一同作為用戶自定義類ZFileDiff Model被存放在了QList中。

QList是鏈表類，不能直接輸出在其中存放的字符串。因此，若想輸出被存放為自定義結(jié)構(gòu)體ZFileDiff Model當(dāng)中的比對結(jié)果信息到文本文檔，首先要遍歷存放在QList中的所有對象，然后將每個(gè)對象逐條提出，接著通過QDataStream 類中命令將每條信息寫入新建的文本文件，最后調(diào)用QFile（）命令保存。

由于原先存放在QList中的元素是自定義結(jié)構(gòu)體ZFileDiff Model，因此在使用QDataStream 命令前需要重載“和”操作符，使之可以適用于自定義結(jié)構(gòu)體ZFileDiff Model。

圖7 輸出比對結(jié)果為txt文檔

本輸出算法最終實(shí)現(xiàn)了EDL變動(dòng)信息的文本輸出。圖7所示為測試案例比對結(jié)果輸出的txt文檔。其中“add：001 005 006”表示新EDL 文件相對于舊文件新增了鏡頭001、005、006， “modify：002 003 004”表示鏡頭002、003、004修改了剪輯點(diǎn)。

4 結(jié)語

本文基于LCS最大公共子串比對算法執(zhí)行EDL文件比對功能，設(shè)計(jì)并開發(fā)了針對EDL文件特點(diǎn)的按行比對工具，通過編寫程序?qū)崿F(xiàn)了比對結(jié)果的可視化。本方案最終實(shí)現(xiàn)了EDL 文件的讀取、比對、比對結(jié)果可視化及文本輸出。后續(xù)研究中，可擴(kuò)展比對文件至AAF、XML 文件，以滿足更多部門、更多設(shè)備的不同需求。目前成果可為相關(guān)從業(yè)人員提高后期工作效率提供參考。