視頻查詢語言SVQL語法分析模型

盧成浪, 尤衛軍, 吳宗大

(1.西北工業大學 航海學院, 陜西 西安 710072; 2.浙江機電職業技術學院 現代信息技術學院, 浙江 杭州 310000;3.浙江省自然科學基金委辦公室, 浙江 杭州 310000; 4.紹興文理學院 計算機系, 浙江 紹興 312000)

數據查詢語言可以幫助用戶有效描述查詢需求，用戶界面友好是實現數據檢索的有效工具。盡管傳統數據查詢語言(如結構化查詢語言SQL、面向XML數據查詢語言XQuery等[1])已取得巨大成功，但它們無法直接應用于視頻檢索，這是因為視頻數據包含的各類語義信息(如視頻實體之間的時空關系)對視頻查詢語言的描述能力提出了許多新需求。雖然學者已提出了多種多媒體數據查詢語言[2-3]，但它們的語法形式通常較為復雜，難以被普通用戶掌握，并且其視頻查詢表達能力相對較弱，難以滿足多樣化的視頻查詢需求。為此，在前期工作中，提出了一種基于結構化聲明的通用視頻查詢語言SVQL(structured video query language)[4-6]，它不僅擁有簡潔語法形式，而且擁有良好可擴展性，能適應復雜的基于內容的視頻查詢需求，是實現有效視頻檢索的重要工具。

然而，由于SVQL語法的特殊性，其語法分析難以用其他結構化數據查詢語言(如SQL等)的語法分析器[7-10]來完成。為此，本文研究SVQL語言語法分析模型的設計與實現。首先，以巴克斯范式、邏輯代數等工具形式化描述SVQL的文法規則和語義規則，研究構建了多層次SVQL語法分析模型。然后，基于語法分析模型，結合編譯原理理論知識，設計了實現SVQL語法分析工具，從而為SVQL視頻查詢的后續優化奠定了重要前期基礎。另外，本文工作對于其他結構化查詢語言的語法分析模型構建同樣具有重要的參考借鑒作用。

1 語法分析模型

1.1 視頻查詢語言SVQL

SVQL是一種基于結構化聲明的通用視頻查詢語言，能有效支持多種形式視頻查詢，其一般化的語法形式可表述為：

FIND VIDEO(〈視頻對象聲明列表〉〈視頻事件聲明列表〉〈視頻關系聲明列表〉)；

可看出，一個SVQL查詢由視頻對象列表、視頻事件列表和視頻關系列表3個部分組成，其中：①〈視頻對象列表〉負責描述視頻所包含的視頻對象及其屬性應滿足的基本條件；②〈視頻事件列表〉負責描述視頻包含的視頻事件及其屬性應滿足的基本條件；③〈視頻關系列表〉負責描述視頻對象之間、視頻事件之間、視頻對象與視頻事件之間應滿足的各種關系。以下通過一個簡單的例子來說明SVQL查詢的語法形式。

例1.查詢2004年，在北京體育館，劉國梁和孔令輝發生同臺競技事件的所有視頻。

FIND VIDEO(/*FIND VIDEO為關鍵字*/

/* 1、視頻對象聲明列表*/

OBJECT劉國梁(/*OBJECT為對象聲明關鍵字，后面跟著對象名*/類型=運動員;)OBJECT孔令輝(類型=運動員;/*“類別”是對象的屬性*/ )

/* 2、視頻事件聲明列表*/

EVENT比賽事件( /* EVENT為事件聲明關鍵字，后面跟著事件名*/

開始時間>‘2004-01-01 00∶00∶00’;發生地點=北京體育館，/*“時間”和“地點”均為屬性*/ )

/* 3、視頻關系聲明列表*/

劉國梁AgentOf比賽事件;孔令輝AgentOf比賽事件; /*AgentOf為關鍵字*/)

1.2 語法分析模型

SVQL層次化語法分析模型如圖1所示。可看出，SVQL語法規則分為：詞法規則、文法規則和語義規則。其中：詞法規則定義查詢單詞；文法規則定義形式語法；語義規則定義語義邏輯上的語法。

圖1 層次化SVQL語法分析模型

1) 詞法規則：詞法規則負責定義SVQL查詢單詞。SVQL單詞可分為關鍵字、固定符號(標點、運算符等)、符號(變量、屬性等)、常量(布爾值、數字、日期、字符串等)等類型。其中，關鍵字和固定符號可直接枚舉。以下僅給出符號(以變量、屬性為代表)和常量(以數字、字符串為代表)的正則表達式描述。

<符號>::=[a-zA-Z0-9-u4e00-u9fa5]+

<數字>::=[0-9]+([E][+-]?[0-9]+)?|[0-9]+"."[0-9]*([E][+-]?[0-9]+)?

<字符串>::=′[^′ ]*′

基于詞法規則，詞法分析部件可以從SVQL查詢文本中識別出所有實義單詞，并過濾無實義詞(空白、注釋等)。據此形成的單詞流是文法分析部件的輸入。

2) 文法規則：負責定義SVQL形式語法，并不考慮視頻對象變量和視頻事件變量的具體語義問題。以下分別給出SVQL查詢各個子句文法約束的巴克斯范式描述。

(1) 視頻對象聲明列表的文法規則

<視頻對象聲明列表>::=<視頻對象聲明>[{;<視頻對象聲明>}];

<視頻對象聲明>::=OBJECT<視頻對象變量>(<屬性條件項>[{;<屬性條件項>}]);

<屬性條件項>::=<視頻對象變量>.<屬性項><比較算符><比較值>;

<視頻對象變量>::=<符號>;<屬性項>::=<符號>;

<比較值>::=<布爾值>|<數字>|<日期>|<字符串>;

<比較算符>::= =|<>|>|>=|<|<=;

視頻對象列表用于描述視頻包含的視頻對象以及視頻對象應滿足的屬性條件。該規則要求：視頻對象聲明列表由若干個視頻對象聲明構成(各個聲明用分號隔開)。

(2) 視頻事件聲明列表的文法規則

<視頻事件聲明列表>::=<視頻事件聲明>[{;<視頻事件聲明>}];

<視頻事件聲明>::=EVENT<視頻事件變量>(<屬性條件項>[{;<屬性條件項>}]);

<屬性條件項>::=<視頻事件變量>.<屬性項><比較算符><比較值>;

<視頻事件變量>::=<符號>;<屬性項>::=<符號>;

<比較值>::=<布爾值>|<數字>|<日期>|<字符串>;

<比較算符>::==|<>|>|>=|<|<=;

視頻事件列表用于描述視頻包含的視頻事件以及視頻事件應滿足的屬性條件。

(3) 視頻關系聲明列表的文法規則

<視頻關系聲明列表>::=<視頻關系聲明>[{;<視頻關系聲明>}];

<視頻關系聲明>::=<視頻對象關系聲明>|<視頻事件關系聲明>|<事件對象關系聲明>;

<事件對象關系聲明>::=

<視頻對象變量>AgentOf<視頻事件變量>[{;<事件對象關系聲明>}];

<視頻對象關系聲明>::=

<視頻對象變量><關系算符>[X|Y|Z|T]<視頻對象變量>[{;<視頻對象關系聲明>}];

<視頻事件關系聲明>::=

<視頻事件變量><關系算符>[X|Y|Z|T]<視頻事件變量>[{;<視頻事件關系聲明>}];

<關系算符>::=BEFORE|MEETS|OVERLAPS|DURING|STARTS|FINISHES|EQUALS;

視頻關系聲明列表用于描述視頻對象之間、視頻事件之間、視頻對象與事件之間以及其他實體之間的語義關系。

3) 語義規則：負責定義SVQL語義邏輯上的語法，它考慮各個視頻變量具體含義。語義分析需要用到視頻實體及其屬性等模式信息，因而，定義視頻實體數據模式如下：SVQL查詢基于視頻對象表VOS和視頻事件表VES。其中，視頻對象表模式可抽象表示為：VOS={|attrName為視頻對象屬性名，attrType為視頻對象屬性類型}。類似地，可定義視頻事件表模式VES。據此，以下給出SVQL語義約束的邏輯代數描述。

(1) 視頻對象聲明語義：視頻對象變量跟隨的各個屬性條件項須合法，即視頻對象應確實包含相應屬性項，并且屬性項與比較值相匹配。記VOD為<視頻對象聲明列表>各個屬性條件項所關聯單詞的集合，即VOD={|attrName和attrValue分別對應<屬性條件項>中的<屬性項>和<比較值>}，則視頻對象聲明的語義規則可表述如下：

?e(e∈VOD→?u(u∈VOS∧u.attrName=e.attrName∧isType(e.atrrValue,u.attrType))

(2) 視頻事件聲明語義：視頻事件變量跟隨的各個屬性條件項須合法。記VED為<視頻對象聲明列表>各個屬性條件項所關聯文法單詞的集合，即VED={|attrName和attrValue分別對應<屬性條件項>中的<屬性項>和<比較值>}，則視頻事件聲明的語義規則可表述如下：

?e(e∈VED→?u(u∈VES∧u.attrName=e.attrName∧isType(e.atrrValue,u.attrType))

(3) 視頻關系聲明語義：視頻關系聲明中出現變量須被視頻對象聲明過或被視頻事件聲明過。記VOV為視頻對象聲明出現的所有視頻對象變量集合，記VOP為<視頻對象關系聲明>關聯的視頻對象變量集合，即VOP={| videoObj1和videoObj2為同1個<關系算符>所關聯的2個<視頻對象變量>}，則視頻對象關系聲明的語義規則可表述如下：

?e(e∈VOP→?u?v(u∈VOV∧v∈VOV∧u=e.videoObj1∧=e.videoObj2))

記VEV為視頻事件聲明出現過的所有視頻事件變量集合，記VEP為<視頻事件關系聲明>關聯的視頻事件變量集合，即VEP={|videoEve1和videoEve2為同一個<關系算符>所關聯的2個<視頻事件變量>}，則視頻事件關系聲明的語義規則可表述如下：

?e(e∈VEP→?u?v(u∈VEV∧v∈VEV∧u=e.videoEve1∧v=e.videoEve2))

記VOE為<事件對象關系聲明>關聯的視頻變量集合，即VOE={|videoObj和videoEve分別為同一個AgentOf關系算符所關聯的<視頻對象變量>和<視頻事件變量>}，則視頻事件對象關系聲明的語義規則可表述如下：

?e(e∈VOE→?u?v(u∈VOV∧v∈VOV∧u=e.videoObj∧v=e.videoEve))

為了支持多種形式的視頻內容查詢，SVQL語法規則比較繁雜，本節僅給出部分主要語法規則描述，其余細節語法規則不再贅述。

2 語法分析工具

基于前文構建的語法分析模型，以下設計實現SVQL語法分析工具，其實現框架如圖2所示。

圖2 SVQL語法分析工具框架

其中：①詞法分析器負責將SVQL查詢轉換為記號集；②語法分析器負責根據文法規則，將記號集轉化為語法樹和符號表；③語義分析器由一系列數據結構及其處理函數組成，負責對語法樹進行語義檢查，生成中間結構(即初步查詢計劃)。

1) 詞法分析器：利用正則表達式所描述的詞法規則，識別出SVQL查詢中的單詞。此外，還要剔除無意義詞(如空白字符等)，并檢查詞法(給出錯誤信息)。SVQL詞法分析器借助LEX[11]實現，其輸入是以正則表達式所描述的詞法規則。詞法分析器核心是getToken函數，不斷調用它即可獲取SVQL查詢包含的所有單詞。

2) 文法分析器：從詞法分析器持續獲取記號，并依據文法規則進行分析處理，以生成語法樹和相應語義信息表。SVQL文法分析器借助YACC[12]實現，其輸入是前文語法分析模型利用巴克斯范式所描述的文法規則。若SVQL查詢存在文法錯誤，文法分析器會給出有指導性的文法錯誤描述，否則將輸出語義信息表。據此，文法分析器可進一步生成語法樹結構，它將是后續語義分析器的輸入。

3) 語義分析器：語法分析模型利用邏輯代數形式化描述了語義約束規則集，據此，語義分析器負責構建算法，并對基于語法樹結構和語義信息表所生成的各個語義項進行語義檢查。其中語義項主要包括：VOD語義項、VED語義項、VOP語義項、VEP語義項、VOE語義項等，分別對應：視頻對象聲明、視頻事件聲明、視頻對象關系聲明、視頻事件關系聲明、事件對象關系聲明等。限于篇幅，以下僅討論VOP語義項和VOE語義項的語義分析檢查算法(其他語義項的檢查算法與之類似)。

(1) VOP語義檢查：VOP數據結構存儲了<視頻對象關系聲明>所關聯的所有視頻對象變量。VOP語義項的一個基本元素關聯了2個視頻對象變量，因而，VOP語義檢查主要是檢查各元素所關聯的2個視頻對象變量之間的語義合法性，偽碼描述如算法1所示。

(2) VOE語義檢查：VOE數據結構存儲了<時間對象關系聲明>所關聯的所有視頻對象變量和事件變量，其各元素關聯了一個視頻對象變量和一個視頻事件變量。因而，本文主要檢查各VOE元素所關聯的2個視頻變量之間的語義合法性，偽碼描述如算法2所示。

算法1VOP語義檢查

算法描述：

VOV為視頻對象聲明出現的視頻對象變量集合

for (eachEin VOP) {

for (index1=0 to VOV.length) {

if (VOV[index1].name ==E.videoObj1) break;}

for (index2=0 to VOV.length) {

if (VOV[index2].name ==E.videoObj2) break;}

if (index1 == VOV.length) 報告錯誤并返回;

if (index2 == VOV.length) 報告錯誤并返回;

if (index1 == index2) 報告錯誤并返回;

}

算法2VOE語義檢查

算法描述：

VOV為視頻對象聲明出現的視頻對象變量集合

VEV為視頻事件聲明出現的視頻事件變量集合

for (eachEin VOE) {

for (index1=0 to VOV.length) {

if (VOV[index1].name ==E.videoObj) break;}

for (index2 = 0 to VEV.length) {

if (VEV[index2].name ==E.videoEve) break;}

if (index1 == VOV.length) 報告錯誤并返回;

if (index2 == VEV.length) 報告錯誤并返回;

}

3 有效性測試

圖3a)給出了SVQL語法分析工具的用戶界面：①左上部分為查詢輸入框；②右上部分為內部結構信息，給出由詞法分析、文法分析、語義分析所產生的詞法分析表、語法樹、符號集等內部結構信息；③下半部分為結果輸出框，給出SVQL查詢處理結果(或錯誤提示文本)。限于篇幅，以下簡要給出語法分析工具的功能測試結果和性能測試結果。

1) 功能測試：圖3a)給出了來自例1的視頻查詢(即查詢劉國梁和孔令輝在北京體育館同臺競技的所有視頻)的語法分析測試結果。可看出，分析工具右上部分的輸出框，給出了基于該查詢所產生的詞法分析表、語法樹、符號集等內部數據結構，這些是后續查詢處理優化的重要輸入；下半部分的結果輸出框，給出了查詢的處理結果信息(即該查詢無詞法錯誤、無文法錯誤、無語義錯誤等)。圖3b)～3d)給出了3個視頻查詢的語法分析測試結果(這3個視頻查詢分別存在詞法錯誤、文法錯誤和語義錯誤)。可看出，對于存在文法、詞法錯誤的視頻查詢語句，分析工具不僅能給出具有指導作用的錯誤文本，還能給出相應的修改建議。綜上，基于SVQL層次化語法分析模型所構建的語法分析工具能較好地完成對SVQL查詢的詞法、文法和語義檢查，生成內部數據結構和相關提示信息。

圖3 SVQL語法分析器用戶界面和功能測試結果

2) 性能測試：選取多組不同長度的視頻查詢語句對語法分析工具進行性能測試，評估結果如表1所示(10次運行的平均值)。

表1 性能測試結果

可看出，對于短查詢語句(語句少于50行)，語法分析器的執行效率非常高(約為10 ms)，但對于長查詢語句，語法分析器的執行效率有所下降。可看出，每行語句的平均解析速度為0.26 ms，因而分析工具的解析速度處在可接受水平(相比于其他一般性的數據查詢語言解析器)；并且隨著查詢語句規模的增長，每行語句的平均解析速度會有所增加。

4 結 論

研究了SVQL(一種基于結構化聲明的視頻查詢語言)的語言分析模型，并據此討論實現了其語法分析工具。結果表明，研究構建的語法分析工具能有效地檢測出SVQL查詢中的詞法錯誤、文法錯誤或語義錯誤，并給出有指導性的修正建議，為SVQL的后續優化奠定了前期基礎。根據查詢分析模型的輸出，可以有效構建視頻查詢的內部被查詢計劃，因此后續的查詢優化和查詢處理問題將是下一步的重點研究內容。