一種新型視頻檢索系統

摘要：本文介紹一種新型視頻檢索系統，這種系統包含索引和查詢兩個主要的子系統，主要應用于檢索視頻序列。在索引過程中，一個視頻序列的內容對象往往采用創建時間的三元組來表示與其他對象的時間關系。由于每一個時間三元組都可以從不同的視頻序列中得到，所以在不同的視頻序列中指定一個關鍵數字，就可以確定視頻內容，這就是所謂的關鍵數字分配算法（PNA）。通過給視頻序列設置關鍵數字，可以得到一個標準值，從而能夠檢索每個視頻序列。在查詢過程中，連續模塊操作（SMO）可以確保標準值不會改變，所以經常用于檢索視頻序列。基于上述的PNA和SMO，我們創建了一個實驗性視頻檢索系統。從模擬的結果上看，我們發現查詢能夠在很短時間內完成。

關鍵詞：視頻檢索 視頻索引 時間關系 相似性檢索 模塊化操作

1.介紹

隨著計算機科技的進步，例如CPU的速度增長，存貯設備的容量變大，而且還可以通過各種不同的壓縮方法，使得數字視頻幾乎可以應用于我們生活的每一個方面，包括教育，娛樂，通信等等。由于大量視頻數據快速增長，我們需要設計一種檢索視頻數據的系統。一個視頻檢索系統主要包含索引和查詢兩個主要的子系統。在索引過程中，視頻分割用于分割發送的視頻序列，每一個發送的視頻序列具有相同內容的幀。一旦發送被確認，我們就可以從每次發送的視頻序列中得到關鍵幀。通過使用索引，查詢過程將提供檢索視頻數據的方法。

由于視頻數據的內容變得越來越豐富，傳統的索引和查詢的方法不再是令人滿意的。所以，在最近幾年，基于內容的視頻檢索變得越來越重要。在這種方法中，以視頻數據的內容（對象）作為索引，研究員可以很好地利用對象之間的空間和時間的關系。

在本文中，我們提出了檢索視頻序列的一種框架方法，這種方法是在相似的時間里使用模塊化的操作檢索視頻序列。在索引的過程中，視頻序列的內容通常用于建立時間三元組，這個三元組表示對象的時間關系。為了從不同的視頻序列中得到時間的三元組，一個關鍵數字被分配到由它提出的關鍵數字分配（PNA）算法中。為了每一個視頻序列，我們經常通過設置的關鍵數字來得到一個固定值。在查詢過程中，對不變數值的順序模塊化操作（SMO）經常用于檢索視頻序列。

2.時間的關系和相似性

2.1定義命名范圍

表1：

我們知道多媒體技術中定義了13種時間關系，它們用來描述對象之間的時間關聯。我們從這13種時間關系中提取出7種重要的，如表1所示。這種提取的目的是為了方便用戶正確地使用時間關系。表1中以過去和現在兩個關系為例，當用戶正在查詢的時候，用戶通常認為事件X發生在事件Y之前，而不是認為事件X和事件Y同時發生。所以，我們結合這二個關系使它們成為一個唯一的關系。因為相同的原因，我們也減少將來和現在之間的關系。注意，在這個關系表中，過去和將來兩個關系是相反的。

2.2時間的相似性

時間相似性具有兩種類型：相似性的匹配和相似性的檢索，二者是相關的。

相似性匹配將查詢特征與特征庫中的特征按照匹配算法進行相似匹配。按相似度大小排列，將滿足一定相似性條件的結果，返回給用戶。

至于相似性檢索，它可以根據容量來進行檢索。例如，在子視頻中，通過視頻序列中對象的百分比進行檢索。

3．應用在時間關系上的相似性檢索

應用在時間關系上的相似性檢索由兩個過程完成，分別是索引過程和查詢過程。

3.1索引過程

如圖1所示，索引過程有四步。下面將逐步討論索引過程。

圖1索引流程圖

3.1.1視頻分割

通過一個給出的視頻序列，可以確定發送視頻過程中的變化，從而選擇關鍵幀。如參考文獻［1，3］中提出的分割算法就能在這一步中使用。

3.1.2三元組結構

通過一個給出的視頻序列，可以根據在對象之間所選擇的關鍵幀的時間關系創建時間的三元組。在大部分的相關研究中，我們都是采用手工計算并創建出時間的三元組。這里，我們提出一種半自動的方法來創建時間三元組。在創建階段初始階段，首先設計一個交互式注釋接口(IAI)，它用來描述哪些對象出現在哪些幀中。然后為了圖像和視頻的需要，設計許多圖解的用戶界面，這種設計方法也可以用于組成IAI。在圖2中就使用IAI說明了四個帶注釋的視頻序列。在自動階段，采用一種三元組結構（TC）的算法用于產生時間的三元組（Oi，Oj，rij），其中Oi和Oj是二個對象，rij代表在Oi和Oj之間的時間關系；表1中定義了七個關系，而rij就是其中的一個。

在圖3中，我們描述了TC算法的流程圖。對于一個帶注釋的視頻序列，我們通過一個位字符串來描述其每個對象，一個位字符串的長度要與選擇的關鍵幀的數目匹配。如果一個關鍵幀包含這個對象，與之對應的位被設置到1; 否則為0。所有的位串以遞減次序進行排序。為了創建時間的三元組，按位與（）的操作在對象Oi的位串Bi和對象Oj的位串Bj之間進行。按位與（）的操作通過遞減次序成對地被執行。通過使用的排序和成對的為操作，可以推導出下列的觀點：

(1) If (Bi and Bj) = Bi = Bj， then Oi is equal to Oj;三元組為(Oi， Oj， 7)。

(2) If (Bi and Bj) = 0， then Oi is before Oj; 三元組為(Oi， Oj， 1)。

(3) If (Bi and Bj) = Bi p Bj， then Oi contains Oj; 三元組為(Oi， Oj， 5)。

(4) Otherwise， Oi overlaps Oj; 三元組為(Oi， Oj， 3)。

圖2帶注釋的視頻序列

圖3三元組結構算法流程圖

3.1.3主要數據賦值

由于每一個時間三元組都是通過輸入的視頻序列產生的，所以需要對主要的數據進行賦值。為此，這里采用一種PNA算法，這種算法的設計原則是盡可能地使用少量的主要數據，規則如下：

(1) 視頻序列的時間三元組的數量越多，主要數據的賦值就越少。因此，就必須在具有視頻序列的時間三元組的數量最多的時候開始賦值。

(2) 視頻序列的時間三元組出現的頻率越大，主要數據的賦值就越少。

(3) 若同一個視頻序列中只出現一次的那些三元組，則他們的主要數據相同，因為他們可能被認為是一個三元組。

(4) 位于不同時間序列中的三元組，其主要數據可以相同。

下面介紹PNA算法的具體步驟。首先，PNA算法調整時間的三元組。為特定的三元組(Oi，Oj，rij)，在字母順序中，如果Oj小于Oi，三元組被調整為(Oj，Oi，rji)，rji是rij相反關系。

其次，我們為每個視頻序列vi計算出它的Ei和Gi，其中Ei代表三元組數據出現的頻率，而Gi比Ei更大。

再次，視頻序列被分組；具有相同數量的三元組的視頻序列被分為同一個小組。例如，圖4中的V1和V2就在一個小組（小組1）中；而V2和V3在另一個小組(小組2)中。

最后，從具有最大數量的時間三元組的視頻序列的小組開始，PNA算法就為三元組的主要數據賦值。

圖4帶注釋的視頻序列的時間三元組

為了確定首先被選擇的時間三元組，可以首先給三元組(Oi，Oj，rij)確定了一個權函數，如下所示：

在所有輸入視頻序列中，freq (Oi，Oj，rij)代表出現的三元組(Oi，Oj，rij)的數量，Gk視頻序列中G的值屬于三元組(Oi，Oj，rij)。在這里，首先要選擇具有最大W值的三元組。

至于在同一個視頻序列中只出現一次的那些三元組，它們具有同樣的主要數據。

以圖4為例，小組1作為第一小組被選擇，然后V1被選擇，因為它有最大的G值。因而，我們要計算公式W(A，C，3) = 3+［(2+1)+ (1+1)+(2 + 1)］=11和W(A，B，1)=2+［(2+1)+(2+1)］=8的取值。由于W(A，C，3)>W(A，B，1)，所以主要數字2和3將分別賦值為(A，C，3) 和 (A，B，1)。在圖5中，顯示了關于圖4的視頻序列V1、V2、V3和V4的主要數據的賦值情況。

圖5視頻序列關鍵字的設定

3.1.4哈希表結構

為了提高查詢的速度，我們需要在時間的三元組和它的主要數據的賦值方面創建一個快速的映射機制。于是，我們就提出了一種兩級映射算法。在第一階段，兩個對象間的關系被引入對應的哈希表。在第二個階段，我們提出完善的哈希算法。這種算法把一組n的完全不同的對象(Oi，Oj)映射到一組連續的地址m中，地址=v1(Oi)+v2(Oj)，其中Oi，和Oj是二個對象，而v1和v2是二個函數的賦值。從而驗證了這種算法的查詢時間是很短的。

3.1.5固定值的產生

我們通過一個固定值(SV)來確定每個視頻序列，這個固定值與視頻序列的三元組的主要數據的賦值相匹配。在圖6中列出了圖5中的4個固定值（V1、V2、V3和V4）。

然而，由于計算機寄存器的局限性，SV溢出是一個比較麻煩的問題。為了解決這個問題，我們使用一個整數鏈表而不是一個整數來表示SV。如下所示：

其中svij表示視頻序列i的固定jth值。按照下列方法，我們可以計算SV的值：首先，視頻序列i的所有主要數據以遞增方式進行排序；然后，從最小數據開始，我們可以計算固定值。只有當產生溢出的時候，我們才可以從新計算出一個新的固定值。

圖6 V1~V4中的4個固定值

3.2查詢過程

查詢是基于索引過程中計算的固定值進行的。查詢過程包括四個步驟：交互式注釋，三元組變換，哈希表查詢和連續模塊化操作。計算三元組變換的算法和哈希表查詢的算法相同，所以，下面我們只詳細介紹交互式注釋和連續模塊化操作。

3.2.1交互式注釋

在“查詢實例”中，注釋程序與3.1節所描述的相同。如果一個用戶要使用“查詢組合”，就要熟悉查詢對象之間的關系。我們只有在關鍵幀上作出標記。

3.2.2連續模塊化操作

3.4討論

在查詢過程中使用主要數據和模塊化的操作，這樣的優點是可以迅速地對查詢作出反應。但是也存在局限性，即在一個新的視頻序列加入到數據庫的時候，每次都要重新計算所有的原始數據。

4.結論

本文主要介紹了一種用于視頻檢索的新方法。位于對象和原始數據的賦值之間的時間關系形成了索引過程的依據。在查詢過程中，連續模塊化操作可以在很短的時間內完成，其中，三元組結構的算法為得到時間的三元組提供了一種半自動的方法，增加了檢索的效率。

參考文獻：

［1］H.J. Zhang， A. Kankanhalli， S.W. Smoliar， Automatic partitioning of full-motion video， ACM Multimedia Systems 1 (1) (1993) 10—28.

［2］U. Gargi， R. Kasturi， S. Strayer， Performance characterization of video-shot-change detection methods， IEEE Transactions on Circuits and Systems for Video Technology 10 (1)(2000) 1—13.

［3］C.C. Lo， S.J. Wang， Video segmentation using a histogrambased fuzzy c-means clustering algorithm， Computer Standards Interfaces 23 (2001) 429—438.

［4］A.K. Jain， A. Vailaya， X. Wei， Query by video clip， Multimedia Systems 7 (1999) 369—384.

［5］Y.J. Zhang， H.B. Lu， A hierarchical organization scheme for video data， Pattern Recognition 35 (2002) 2381—2387.

［6］S.W. Smoliar， H.J. Zhang， Content-based video indexing and retrieval， IEEE Multimedia， (1994) 62—71.

［7］S.K. Chang， C.W. Yan， D. Dimitrof， T. Arndt， An intelligent image database system， IEEE Transactions on Software Engineering 14 (1988) 681—688.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”