視訊資料庫之內涵式檢索 Content-based Retrieval for Video Databases

Presentation on theme: "視訊資料庫之內涵式檢索 Content-based Retrieval for Video Databases"— Presentation transcript:

1 視訊資料庫之內涵式檢索 Content-based Retrieval for Video Databases
學生：余平 指導教授：李瑞庭老師

2 影像及視訊資料庫內涵式檢索 資訊科技的快速發展，儲存及顯示大量的影像、音訊、視訊等多媒體資料的技術也大幅提昇 最自然的檢索方式
多媒體資料本身內涵 傳統資料庫系統無法有效管理及檢索 缺乏管理空間及時間關係能力 內涵識別及解譯的能力 缺乏良好內涵模型化的能力 缺乏良好視覺式查詢的能力 影像及視訊中皆具有空間上的關係需予以定義及管理 例如地理資料庫中的影像，所儲存的地圖包含著建築物、電纜線、排水溝、水管等，皆為具有不同意義且可能分開儲存的實體，必需能以空間的關係加以描述並儲存 視訊資料包含時間的關係 要有管理個別的音訊或視訊片斷間時間關係的能力 具有管理空間及時間關係的能力是影像及視訊資料庫重要的特徵之一 將附加在多媒體資料上內涵的資料，適當和分別儲存的原始資料相結合亦是檢索上的問題 要能結合內涵的語意以在檢索時評估相似度 資料庫必需具有解譯原始資料(raw data)到內涵知識的能力，現仍缺乏良好的方法 即使單一媒體的資料亦具有不同內涵的面貌 皆需能實際引用在查詢或結合多項內涵的查詢評估 以往資料庫皆假設文字與數字為其定義域(domain) 檢索這些記錄基本上是由關連式代數或以文字與數字形式的屬性值的比較查詢條件所組成 多媒體資料庫檢索如僅有單純的文字、數字的查詢條件是不足的 提供視覺式的查詢表示是必要的 實例查詢(QBE, Query by Example)可能是最能表示這些資料的檢索形式，因其比數字更能貼近的描述查詢條件

3 內涵式檢索架構 內涵萃取 內涵模型化 原始 資料 影 像 及 視 訊 內 涵 資 料 庫 內涵式檢索 查詢介面 影像 特徵模型化
特徵萃取處理 物件識別處理 物件模型化 語意模型化 語意識別處理 視訊格 關鍵視訊格 空間關係處理 時間關係處理 空間模型化 時間模型化 切割模型化 原始資料 內涵萃取 內涵模型化 瀏覽 查詢結果

4 特徵萃取層 內涵萃取 內涵模型化 原始 資料 影 像 及 視 訊 內 涵 資 料 庫 內涵式檢索 查詢介面 影像 特徵模型化 特徵萃取處理
物件識別處理 物件模型化 語意模型化 語意識別處理 視訊格 關鍵視訊格 空間關係處理 時間關係處理 空間模型化 時間模型化 切割模型化 原始資料 內涵萃取 內涵模型化 瀏覽 查詢結果

5 特徵萃取層 低層次影像處理 常用的影像特徵 顏色 紋理 形狀 低層次的影像處理主要是從資料庫找出與使用者查詢影像相似的影像
在處理的過程中，使用者查詢影像中的特徵向量(feature vector)與已事先儲存在資料庫中的特徵向量做相似度的比較 影像匹配需要找到與其相似或變形下相似的版本，其中影像的變形包括縮放、偏移、旋轉、及描繪草稿等 影像的特徵包括顏色、紋理、形狀等等。這些特徵能夠在數量化後，對映到多維特徵空間，在此空間中允許以相似度的方式來檢索影像。 影像中的特徵在空間上可分類為全域或區域的 全域特徵主要是對整個影像的表示 影像中較細微的部分將予以忽略 顏色直方圖、快速傅利葉轉換等 計算出的值可儲存在多維空間中，以能和經過相同處理的查詢影像來進行相似度的計算 例子如：“找出綠色為主要顏色的影像” 適用以整張影像為查詢的類型 優點：低計算複雜性和簡單的相似度演算法 缺點：查詢的結果會有較高比率的不相關影像 但其可透過用影像合併文字註解的方式來達成較高的查詢精確度。 區域特徵:針對影像中某一區域進行特徵萃取的處理 用在影像中識別出突出物件及萃取出影像更細微部份的更多資訊 並可進一步的識別成一個簡單語意物件 例如“圓形物體”或者“有均勻色彩的地區” 事先制定規則的切割區域被加以處理並萃取出若干特徵，然後再建構成一多維的索引空間 典型特徵包括區域中像素的灰階值、顏色、形狀、和紋理 且能再利用物件識別層的技術作進一步的物件上分析，以把物件用於更高的層次的語意表示。

6 顏色直方圖 可容忍場景改變 白色 : 8/16 藍色 : 4/16 紅色 : 4/16 像素個數 色彩 黑 藍 紅 白 4 8
最基本且常用的特徵向量 完整的顏色直方圖就是將影像的每個像素(pixel)的顏色加以統計分類，製成直方圖 二個顏色直方圖利用每一種顏色具有像素量的絕對差值或方差和來比較 方法簡單並可以容忍場景上的小改變 顏色空間與叢集/量化方法時的問題 將鄰近的顏色合併來減少直方圖的維度，以減少儲存的空間與加快相似度的運算，稱為叢集/量化 實驗結果顯示使用知覺一致(perceptually-uniform)的顏色空間，較能減少顏色資訊在合併時的損失 比較RGB、HSV、C.I.E. L*a*b System與Mathematical Transformation to Munsell (MTM)四種顏色空間 等區間量化法(equalized quantization)、階層式叢集法(hierarchical clustering)、監督式顏色命名叢集法(Color-Naming-System supervised clustering)三種不同的叢集量化方法 實作相當簡單所以相當常被使用 將RGB的值先轉換成相對的HVC值，再由4096平均分成4 levels即可得到64個bins(4×4×4) 階層式叢集法首先將每個顏色皆設為一個cluster(4096)再逐次的將最接近(Euclidean center distance)的cluster合併，到最後剩下64個clusters時結束 監督式顏色命名叢集法是利用Color Naming System(CNS)對顏色命名的方式，將原先的顏色分為267種(CNS level 3)，再將較小的區塊予以合併至64個區塊。 如果顏色資訊損失的值很大，表示叢集量化的方法不好，而影像中顏色的資料將會損失很多。 結果比較 不同叢集量化法顏色資訊損失只能當作參考值 對某一單一的影像來說，使用某種叢集量化得到較低的顏色資訊損失值，並不表示該種叢集分類法比其他的好。 在一般情況下，階層式叢集法保留顏色資訊的能力較好 好的叢集量化法能夠導致好的影像查詢效率 白色 : 8/16 藍色 : 4/16 紅色 : 4/16

7 顏色動差(color moments) 根據顏色分布得到顏色統計的機率分配 影像中第j個像素的第i個顏色組成
為顏色直方圖更進一步的改良，計算相當容易 顏色分布之各階動差作為特徵值 根據顏色分布得到顏色統計之機率分配，即藉由統計方法中求取各階動差的方法，求得顏色機率分配之各階動差，作為影像特徵值

8 顏色空間資訊 萃取顏色分佈的空間資訊 (a) 相同顏色直方圖 (b) 不同影像簽章 (a)0000 0000 1111 1111
只依賴顏色的資訊並不足以充分的顯示出一個影像的特徵 一些新的做法嘗試將顏色的空間資訊捕捉到特徵之中。 Hsu等認為影像的中央部位的資訊特別重要，因此將影像分為整張影像與中央部位 分別對兩者計算其顏色直方圖，然後求出兩個顏色直方圖主要的顏色 但是無法處理物件不在影像中央的查詢

9 顏色相關直方圖 (Color Correlogram)
相同或不同顏色在空間上分布的機率 顏色ci與該點距離k處有一個顏色為cj像素的機率 自動顏色相關直方圖(autocorrelogram) 相同顏色的顏色相關直方圖 距離1: 藍藍:2 /(8×1×2)=0.125 紅紅:14/(8×1×6)=0.292 距離2: 藍藍:0 /(8×2×2)=0 紅紅:28/(8×2×6)=0.389 距離3: 藍藍:6 /(8×3×2)=0.125 紅紅:62/(8×3×6)= 0.431 針對顏色的空間分布資訊來改良 定義I為一個n×n個像素的影像，而組成I的所有顏色分類成c1, …, cm共m種顏色。距離d[1,…n] 顏色相關直方圖定義為對於影像I中顏色為ci的任何一點，表示了「影像中與該點距離k處有一個顏色為cj的像素的機率」。 由此來影像I的自動顏色相關直方圖(autocorrelogram)用以記錄影像中相同顏色的空間相關資訊。這個資訊是相關直方圖的子集合，而且只需要O(md)的空間來儲存。

10 紋理 由重覆 pattern元素e依placement rule(R)所組成 可表為f=R(e)的形式 為一個分析許多種類影像的重要特性
衛星空照多光譜掃描影像的紋理來分析地質或是能源的蘊藏 顯徵鏡影像中的紋理來分析細胞的組成 電腦視覺使用紋理來分析物件表面及戶外場景。 現在為止仍沒有唯一對紋理特徵正規方法及精確的定義存在 對紋理的定義完全是依據所使用的地方及所給的定義而變的 Ehrich等人認為紋理的分析應包括以下三點： 分類:對所給定的紋理區域，能決定出有限數量紋理的分類，也就是以圖形識別來萃取出紋理的特徵。 模型化:對所給定的紋理區域，能決定出對紋理的描述或模型化，也就是要能產生出對特定紋理的模型。 對所給定具有多個紋理的影像，能區分出不同紋理區域間的邊界，也就是要能利用第一及第二所得的結果來切割出影像中的紋理。

11 Tamura定義六種紋理基本特徵 Coarseness Contrast Directionality line-likeness
Coarse vs. fine Contrast High contrast vs. low contrast Directionality Directional vs. non-directional line-likeness Line-like vs. blob like Regularity Regular vs. irregular Roughness Rough vs. smooth D93 D98 D20 D34 D15 D33 D34 D9 Coarseness(coarse vs. fine)粗細度是最基本的紋理特徵，當兩個圖樣只有在scale不同時，放大的稱為粗；當為不同結構時,具有較大元素或重覆次數較少的稱為粗。其計算的方式如下：藉由可變大小的運算子(various sized operator)選取影像中紋理最大的部份來決定粗細度 Contrast(high vs. low Contrast)提高或降低影像全體的gray-level，其只會改變影像的品質而不會改變其結構，但事實上有四種因子會影響contrast：dynamic range of gray-levels,在gray-level histogram黑白極化的分佈，或黑白的比例差太多時。,sharpness of edges,period of repeating patterns Directionality(Directional vs. non-directional)這是對一個所給region的global property，包括element shape及placement rule。其利用區域edge可能具有方向所產生的直方圖來計算輸入紋理影像在整體上所具有的long-line及simple curve Line-likeness(line-like vs. blob like)：此概念在於紋理元素的shape是否具有直線般的關係首先建構出一個方向相關矩陣(direction co-occurrence matrix) ，代表兩個相鄰cell i及j在影像中距離為d的edge上相對的direction code，其中亦設定門檻值t表示如超過某個角度(non-line)則不予計算，其圖示如圖：方向相關矩陣 中(i,j)元素 Regularity(regular vs. irregular)此為placement rule變異所造成的屬性，但亦可用來描述element的變異，特別在元素以整體的方式規律變化時，所以在計算時即利用之前所具有的紋理特徵結果來判斷regularity Roughness(rough vs. smooth)此特徵原本用來定義具立體感(tactile)的紋理，而非視覺上的，但實際上當total energy of changes in gray-levels or due to our imaginary tactile sense時會有此特徵的存在，因當時所具有的研究對於roughness並沒有良好的方式來描述所以其利用contrast及coarseness的和來代表 D9 D98 D98 D34

12 形狀 難由影像中切割出有興趣的物件 探測出具有物件及位置化 處理演算法會相依於不同的特定領域影像
利用邊探測(edge detection)技術 原始影像 邊影像 形狀影像 影像檢索問題中最困難的問題之一 主要是很難由影像中切割出有興趣的物件 通常受限於是否能從影像中順利的區別出物件， 通常這些預先處理的演算法或過濾器會相依於不同的特定影像上，如皮膚、腦部腫瘤、人、花、或飛機等需要不同的演算法 且如物件影像的背景相對於物件比較暗的話，還可用一個簡單的密度邊界值方法來分離物件，但如具有更複雜的背景時則可能需要一些雜訊去除及比例、旋轉不變的轉換 一旦物件被探測出及位置化，其邊界可以利用邊探測(edge detection)的技術，找出影像中兩個像素間具有明顯gray level intensity差異情形 如相鄰的像素皆具有相同的差異即可組合成一個edge，其可用一些gradient edge detector的mask對整張影像處理而得出，如紋理中所提的Canny operator(如圖)及邊界延續演算法等 但如果物件被其它東西所遮蔽或具有陰影則將難以探測出來，如圖中的輪胎和背景中牆壁的紋理在分辨時將難以區分，如以此edge來形成形狀將導致不正確的結果 一旦物件的邊界決定出來,其形狀即可利用如區域(area)、離心率(eccentricity)，即主軸和副軸的比例)、偏心率(circularity),相同區域圓的接近程度)、形狀簽章(一系列邊界相對中心的成員)、形狀動量、碎形維度(自我相似的程度)等來找出形狀。所有的這些特徵皆可以數量的方式來表示，並以此為關鍵值形成多維的索引結構，並於的檢索時使用。 形狀可以如上節中的方法來特徵化，並以n維的數值向量來表示即變成空間中的多個點 另一種方式是利用事先所定義的簡單形狀來近似形狀，如以triangulation或rectangular block的重疊來表示一個不規則的形狀 形狀即利用一連串的三角形及矩形來近似，且其維度及位置會記錄下來 好處是儲存空間的需求相當低而比較時亦較簡單而原始形狀重建時亦只有較小的錯誤 此方法可以和上一種方法合併使用以同時具有彼此的優點。 而基於使用者描繪圖案的檢索，可以考量為一種特定的形狀檢索例子，即由使用者所描繪的單一的物件形狀或整個影像的物件空間配置所組合成的形狀。此種形狀的檢索可利用將被查詢的影像相對於描繪形狀間的區域以窄化(shrinking)的邊來進行比對 窄化是一種利用影像處理mathematical morphology技術所產生的的二元邊影像(黑為邊及白為非邊)，其可以大量的減少在儲存及比較時所需的資訊量，如圖中對灰階影像中形狀以窄化的方法所得的結果。

13 物件識別層 內涵萃取 內涵模型化 原始 資料 影 像 及 視 訊 內 涵 資 料 庫 內涵式檢索 查詢介面 影像 特徵模型化 特徵萃取處理
物件識別處理 物件模型化 語意模型化 語意識別處理 視訊格 關鍵視訊格 空間關係處理 時間關係處理 空間模型化 時間模型化 切割模型化 原始資料 內涵萃取 內涵模型化 瀏覽 查詢結果

14 物件識別層 分析低層萃取特徵在影像中識別出物件 匹配品質：物件樣板精準度及詳細程度
物件模型是描述特定物件的樣板(template)，包含物件所具有的各種特徵 匹配品質：物件樣板精準度及詳細程度 二種類型的樣板匹配方法 固定樣板匹配 可變形的樣板匹配 分析下層中所萃取出的特徵在影像識別出物件 主要的考量是如何萃取出查詢影像中的物件特徵並與儲存在資料庫中的物件模型相匹配 物件模型是描述特定物件的樣板(template)，在樣版中包含物件所具有的各種特徵 在匹配過程間，需檢查每一個樣板以找到「最相關」的匹配物件 但要能精確的識別出物件間的相似度通常需要極高的計算代價，且匹配結果的品質取決於由物件樣板提供的精準度及詳細的程度 如查詢影像中的物件的有所變形或具有類似物件的假特徵時，將會減少檢索的精確度 大致可區分為二種類型的樣板匹配方法：固定樣板匹配和可變形的樣板匹配 物件形狀不隨照相機觀察角度變化 影像相減方法：利用影像及樣板間各階層顏色或是灰階強度(intensity)差值來識別是否有物件的存在 需要比相互關係技術較少的計算時間，需在影像具有相同狀態的限制環境下才能得到較好的結果 相互關係匹配技術：是在一個樣板和影像之間利用正規化交叉相互關係(cross-correlation)的頂點位置來找出最好匹配 此技術通常用來降低影像中雜訊(noise)及亮度改變的影響 因需對整個樣板來計算相互關係，而較減法技術有更高的計算複雜度 只對特定選擇或較小量的點來計算相互關係，將能減少計算的複雜度

15 固定樣板匹配:影像相減方法 查詢影像 目標影像 紅色 鐵灰色 顏色相減 臉部的識別是影像資料庫在物件識別方法中的另一個重要應用
人類臉部具固有的明確結構 通常具有下述的三個步驟：1.在影像中找到臉；2.對臉部的各部分特徵的探測及萃取；3.以臉部所識別出的特徵由臉部模型的資料庫中檢索出這個人 現有系統大部份針對面部中較獨特的部份，如眼睛、鼻子、和嘴識別，進而將臉部分解為量化特徵表示 此種技術首先收集面部影像中的各種變化再予以編碼，並比較個體間的差異來表示所具有的特徵。 亦有系統是使用輪廓(contour)形成的方法，首先儲存各種臉部影像中的詳細結構，如鼻子尺寸和方向等，在檢索時則首先找出查詢臉部輪廓上特定的區域點形成特定的結構，並以此和事先所儲存資料比較來找出特定的候選人。

16 可變形的樣板匹配範例 移動 旋轉 縮小 物件因剛性(rigid)與非剛性的變形造成變化
一個樣板的是利用類似二位元圖(黑白影像)的表示法來描述一個物件形狀特徵的輪廓或邊 其運用雛型樣版輪廓的機率轉換使樣板變形以配合輸入影像所具有的突出邊 目標函數會藉由不斷更新轉換參數的迭代法(iteration)以得到物件的最佳匹配 改變樣板形狀目標函數的轉換參數可反映出轉換所具有的計算複雜度 可變形樣板匹配技術亦可應用在視訊格中物件移動的探測及手寫文字的識別上，因此兩者所具有的物件通常具有變形的情形 良好的物件萃取，是發展大型一般目的影像資料庫管理系統時的重要基本功能 但缺少精確模型來陳述物件及處理影像時的高複雜度演算法，仍是發展全自動的影像管理及內涵式檢索系統時的一大的挑戰。 旋轉 縮小

17 空間關係層 內涵萃取 內涵模型化 原始 資料 影 像 及 視 訊 內 涵 資 料 庫 內涵式檢索 查詢介面 影像 特徵模型化 特徵萃取處理
物件識別處理 物件模型化 語意模型化 語意識別處理 視訊格 關鍵視訊格 空間關係處理 時間關係處理 空間模型化 時間模型化 切割模型化 原始資料 內涵萃取 內涵模型化 瀏覽 查詢結果

18 空間關係層 2D String 參考點為物件的重心(centroid) 運算子 ”<” left-right及below-above
”=” 相同位置 ”:” 相同集合 影像空間關係的建立通常藉由將物件間相對的空間關係來建立，並利用二元式的關係運算來表示二維物件間的空間關係 Chang[CSY87]將物件投射於座標系統中，並以2D String的形式表達這些物件在二維投射所得出的部份順序(partial ordering)結果 對於查詢的處理，則可用2D strings子序列間的相似度來做比較 2D strings 表示影像投射於一維空間時，符號物件(symbolic object)間的空間關係，此些物件在原始影像中是以最小矩形(minimum bounding rectangle, MBR)所包含，其中具有相互正交(orthonogal)關係的物件可以在投射出的符號照片中予以切割，而參考點為物件的重心(centroid)。 2D String的好處在於可以在影像資料庫中以圖像式的索引並建立相對的空間關係，且可以由符號物件快速的重新建構出原來的影像，2D String所定義物件間關係的運算子有三種，分別為”<”代表left-right及below-above的空間關係、”=”代表在相同位置的關係、而”:”代表在相同集合中的關係。上圖為組符號物件及其2D String。 Lee等人[LH90]利用2D String的概念以物件相互重疊時予以切割(cutting mechanism)的概念發展出2D C-String，此切割物件的方法能減少以2D String處理複雜物件時的困難，進而降低所需的儲存空間，因重疊的物件己不存在 因2D C-String並沒有表示出物件的大小及其間的距離資訊仍會造成在重構影像時的混淆，所以Huang等學者提出2D C+-String加入相關數量的資訊，以能更準確的描述物件間的相對空間關係及重構出原始影像

19 RS-String 物件在環形方向(ring-direction: R-String)及扇形方向(sector-direction: S-String)的相對空間關係 R-String：A<B=C S-String：A %(B<C) 0o A B C Huang在後續的研究中提出更具描述空間關係及壓縮資訊的RS-String 利用極座標的概念來描述物件在環方向(ring-direction: R-String)及扇形方向(sector-direction: S-String)的空間相對關係 但當圖旋轉一個角度RS-String沒有任何改變但2D C-String卻改變成下面的形式，形成旋轉上的變異。 所以RS-String對辨識具有旋轉變異影像將有較好的效益，但同樣的影像中具有偏移現象時，如選取不同的中心點將會造成不同的檢索結果。

20 語意表示層 內涵萃取 內涵模型化 原始 資料 影 像 及 視 訊 內 涵 資 料 庫 內涵式檢索 查詢介面 影像 特徵模型化 特徵萃取處理
物件識別處理 物件模型化 語意模型化 語意識別處理 視訊格 關鍵視訊格 空間關係處理 時間關係處理 空間模型化 時間模型化 切割模型化 原始資料 內涵萃取 內涵模型化 瀏覽 查詢結果

21 語意表示層 空間語意(semantic)事件和影像資料結合 查詢通常為描述性
限制式方法論(constraints-based methodology) 語意由一組限制(constraint)和一些formal expression所組成 主要功能是能讓表示空間語意(semantic)的事件和影像資料結合 查詢通常為描述性，並強調影像資料中的語意表示。 大部份的方法空間語意是基於若干物件相對位置上”空間事件“的描述，並以這些語意作為影像索引及內涵式檢索 所謂空間事件如包含(contain)、相同(same as)、重疊(overlapping)、相對大小(larger than)等空間語意的表示 如應用在放射學影像上時，因此類影像中物件在空間上所具有相對尺寸及位置對醫療診斷相當重要，即可利用如："找出腦中具有大腫瘤的所有影像"或者"找出影像中其主動脈的40%是阻塞"的查詢例子來輔助醫生做正確的診斷。 通常需具有較低層次的精確結果，一旦物件在較低層次中被識別出來，並以邊界的方塊或體積予以記錄時，即可用物件間所具有的空間關係來推斷出物件間的空間語意。其中空間關係可以使用各種語意表示的方式來加以編碼 現已有幾種方法發展出來，如語意網路(semantic network)、限制式方法論(constraints-based methodology)、及包含式階層(inclusion hierarchies)等 語意網路廣泛用於人工智慧的應用上 首先說明表示”概念”(concept)的句子中名詞及其間關係的語意所代表的意思 以圖式的方法表示這些概念及關係，如以節點的部份表示概念，而節點間連接的弧線則表示概念間的關係。 一個語意網路是否有效率通常決定於概念間是否能緊密的相互參考而來，而非關係中的物件是否被精 確的命名，因所重視的是相互的空間關係 亦需能發展出有效的空間語意搜尋策略(searching strategy)。

22 constraint 原始影像 影像理解組件 自然語言處理組件 控制組件 影像標題: 在電機館前Francis在Jaehyung的左邊
此方法中領域語意的表示是由一組限制(constraint)和一些formal expression所組成，其中expression為敘述式的圖樣或計算、限制則用來表示二個以上物件間的一種關係。 PICTION系統 架構由一個自然語言處理NLP(natural language processing)組件、影像理解IU(image understanding)組件、和一個控制組件所組成 利用文字註解和臉部識別處理技術的結合。首先利用IU組件鑑別出影像中人物的相對位置，並利用NLP組件由這些圖片標題得到了一組稱為視覺語意(visual semantics)的限制，再利用控制組件將這些限制與所識別出的臉部資料鑑別出人物間的空間關係 constraint 獲取語意: Francis右邊為Jaehyung且在電機館前

23 視訊切割 內涵萃取 內涵模型化 原始 資料 影 像 及 視 訊 內 涵 資 料 庫 內涵式檢索 查詢介面 影像 特徵模型化 特徵萃取處理
物件識別處理 物件模型化 語意模型化 語意識別處理 視訊格 關鍵視訊格 空間關係處理 時間關係處理 空間模型化 時間模型化 切割模型化 原始資料 內涵萃取 內涵模型化 瀏覽 查詢結果

24 視訊切割層-關鍵視訊格 兩大類鏡斷點探測方法 視每個視訊格如影像 對壓縮視訊資料處理
以上述特徵萃取方式，如像素的比較(pixel-level comparison)、顏色直方圖(color histogram) 通常越複雜的方法其計算的成本也越高 對壓縮視訊資料處理 對壓縮的結果來處理，計算成本遠較其它方法好 壓縮視訊切割方法，雖有計算低成本，但受限於現有標準中所能提供的資訊 視訊切割主要是利用2.1中的影像處理技術，即由個別視訊格中萃取重要全域特徵，並以一連串視訊格特徵值的重要變化來標示出幕(scene)的變化。此過程亦可用來對視訊資料做較詳細的切割成數個鏡(shot)或幕。 文獻中已經提出兩大類鏡斷點的發現方法 第一類是對原始視訊中如同影像的每個視訊格的特徵來處理，包括：像素的比較(pixel-level comparison)、相似程度的比例(likelihood ratio)、顏色直方圖(color histogram)、及2直方圖(2 histogram) 第二類主要是對壓縮的視訊來進行處理，在壓縮的領域中，以MPEG標準壓縮時所產生的DCT係數為比較視訊格是否為不同的方法最為熱門，因在計算量上是以壓縮的結果來處理，所以在計算複雜度上遠較其它方法為好 在像素層次的比較方法中，是對兩個不同視訊格中的相應位置上來處理 如對各像素的灰階值在連續或一個固定的區域距離予以相減，並且把絕對值用作在像素之間不相似性的評量上 所得的結果如超過某個門檻值，則認為這個像素灰階值已改變。而視訊格間不相似性的測量即為像素改變的百分比，如超過所設定的門檻值則認為具有幕(scene)改變或鏡斷點的情形。 像素層次的比較方法對幾個因素相當敏感，包括數位化過程所產生的雜訊、物件運動、及相機操作等。 修正方法是把這些視訊格再細分成較小的區域，並在處理時僅選擇某些區域，類似在影像處理技術中樣版匹配時增進效率的方法 將視訊格分成區塊，並基於強度值的一些統計特徵(如強度的平均值)來比較兩個連續視訊格的相對區塊 在具有雜訊及物件運動時比像素層次的比較方法更穩定。 顏色直方圖方法利用如上述的影像處理方法 把顏色空間分成稱為bin的離散顏色，並以計算每個bin中像素數目的方式來分析視訊格，例如每個視訊格皆以R、G、B各部份的顏色所產生的分離直方圖為來表示。但亦需注意所損失的資訊量，所以可以使用正規化方法使大小差別間的結果更加顯著，如2直方圖的方法

25 切割結果範例(59個關鍵視訊格)

26 視訊切割 內涵萃取 內涵模型化 原始 資料 影 像 及 視 訊 內 涵 資 料 庫 內涵式檢索 查詢介面 影像 特徵模型化 特徵萃取處理
物件識別處理 物件模型化 語意模型化 語意識別處理 視訊格 關鍵視訊格 空間關係處理 時間關係處理 空間模型化 時間模型化 切割模型化 原始資料 內涵萃取 內涵模型化 瀏覽 查詢結果

27 時間關係模型化 時間上物件行為的表示 簡單事件： 複雜事件： 觀察一個物件在視訊片斷中的描述 由簡單事件遞迴定義出來
時間模型化是用來在視訊資料中構造複雜景觀或描述事件 事件是由在某時間上有形物件集體行為的解釋來予以表達 簡化的作法中，則是僅由觀察一個物件在一個給定的視訊片斷中出現的持續時間描述這個行為 例如，一個查詢是希望能在一個運動視訊片斷中找出灌籃事作，模型化此特定事件至少需要識別包括在灌籃完成和選手拿到球二個子事件間選手精確的運動軌跡，尤其當球接近籃框時可能是此事件的開始搜尋前後子事件的起始點 創作出一個灌籃事件需要若干子事件的前後時間上的關係，其能夠用一連串視訊格中的各種空間事件邏輯形式的組成來表示 更複雜的時間事件亦能以其中子事件持續的遞迴定義出來。 視訊資料模型化中的一個主要挑戰 需要從與這些物件的運動有關的一連串視訊格中鑑別出物件更高層次的抽象來萃取內涵 文獻中已經提出了幾種方法 第一種技術使用MPEG的壓縮演算法的修改版本，以鑑別及追蹤突出物件的運動 第二種方法利用方向圖模型去捕捉物件和人在空間和時間上的屬性，此種模型稱為視訊語意方向圖形(VSDG, Video Semantic Directed Graph)模型 第三種則是延續2.3節中二元式空間關係在時間上的擴展

28 視訊事件語意表示 Name: 分數 SuperClass: #table[NBA,實況,比賽] SubClass: void
球員 遊戲 訪問 個人 教練 公司 場次 地點 分數 動量 練習 廠商 難度 Name: 分數 SuperClass: #table[NBA,實況,比賽] SubClass: void Instance: 100比107 Description: 湖人對金磚,湖人勝 Video: demo.mpg Smoliar和Zhang[SZ94]利用新聞廣播的已知領域架構具有的知識庫來建立基本視訊語意事件的索引，並將結果儲存在資料庫中，供後續的檢索及瀏覽使用，此系統希望能克服下列問題： 定義一個能管理視訊內涵並將其特性化(characterize)的架構； 發展能識別及表示視訊內涵的軟體工具及技術； 應用知識表示的技術來發展索引建構及檢索的工具； 發展一個能處理視訊中物件的互動環境 視覺及語意的索引皆建立後，使用者即可利用語意文字或是視覺特性等來檢索及瀏覽資料庫 建立索引的方式是基由知識庫中的物件稱為frame-based knowledge base 強調的是上階層的語意能明確的表示出下階層所具有的語意，通常會使用第二章語意網路的方式，下圖及表為範例 其中根部表示一個大學中工程研究室的語意結構，除了一般性的活動外(如學術及非學術的活動)，並包括所事的研究工作(如所能生產的視訊類型)，而此種語意上的表示讓使用者可以逐步的藉由知識庫導引來檢索各種不同的視訊事件

29 代數式時間事件 萃取出物件追蹤其軌跡 建立<object、trajectory、location>的triple
<O, T, L> where: O is defined as (Global_ID:23456, Shot_ID: ), World_name:{“ball”, ”basketball”,…}, Real_Color:<200,120,35> Picture:2.gif, shape: round,…) T is the chain code represented as (4,4,4,3,2,2,1,1,7) L is the centroid of the region occupied by (.42, .12) 1 8 2 視訊處理的過程是先將視訊切割成鏡，再利用事先建立好的知識庫識別出背景及像機方向及位置，再用其中keyframes來表示此視訊片斷 在萃取出物件後再將追蹤其軌跡進而用這些資訊建立<object、trajectory、location>的triple object是以各種屬性來表示，如視覺或文數字上的，並以物件導向的形式儲存； trajectory則提供多種的表示，如chain code、directional vector、或polynomial spines等以2D的形式來表示物件的運動 location以grid所組成的region表示 一個籃球物件的例子如下圖 3 R:0 7 6 4 5

30 3D-List X-string: A  B 可利用增加數量資訊改進 Y-string: B |3 A 視訊1:A3 B1
time-string: A  B 可利用增加數量資訊改進 視訊1:A3 B1 視訊2:A1 B3 A B 視訊1 視訊2 延續由影像處理時以符號物件及空間關係來表示影像的作法 Liu[LC]提出一個基於2D String的3D String 除了將物件在x、y軸上的投射外，亦加入在時間軸(time)上的投射資訊 利用記錄物件的中心點及起始、結束視訊格來代表物件，並新增兩個運算子來增強關係的表示，其分別為”|n”代表物件間在各軸x,y,t)的距離，而””則表示同位的關係(appositional relationship) 但因其缺乏物件在視訊格間運動及大小改變的數量資訊，以至於在分辨不同視訊時會造成混淆 此方面的問題可以加以改進，如加入物件運動軌跡的數量資訊，以能更進一步以更簡單及精確的方式來分析、儲存、及檢索視訊。

31 空間-時間邏輯 Temporal assertion： Spatial assertion： S1 S2 S3 S4 防守球員(p1) x
y z 球員(p8) time 相對於p8的p1運動軌跡 球員(p1) S=<V,Obj,F> V:維度數 Obj:S中所具物件 F: 物件座標點 Temporal assertion： Bimbo等人所提的方法中，使用符號來表示幕(scene)中所確認的突出物件，並且用在幕中物件投射所獲得的幾何學關係中的一系列state assertions來表示幕 物件投射的方式是採用Symbolic projection如在影像處理中二元式空間方法(2D String) assertion用來描述這些物件在視訊格間移動的動態變化 其為Symbolic projection 的Spatial Logic及Temporal Logic結合成的一種稱為Spatio-Temporal Logic(STL)的視訊表示語言，即由spatial/temporal assertion間在時間上的布林結合來表示 例如temporal-until可表示兩個幕間的前後關係 以往時間邏輯已很廣泛的應用在平行及同作(concurrent)系統中來表示一連串活動在時間上的順序 空間時間邏輯是由時間邏輯(temporal logic)發展而來，強調能在時間及空間上對一序列的影像內涵得到唯一的表示 時間屬性是以時間邏輯斷言(temporal logic assertion)來表示在單一視訊框中空間上相對於時間上的關係 空間的關係上亦可用空間邏輯(spatial logic)來表示，其由symbolic projection而來。 首先由state assertion來表示個別state的屬性 再藉由時間操作(temporal operation)結合成sequence assertions來表示其間的順序 現已有許多研究發展出自動驗証的演算法來檢查在temporal logic assertions中抽象的屬性，相對於concrete system model此種model稱為state transition systems 其並利用上述的基本操作發展出許多具更高層語意的時間和空間上操作如temporal/spatial eventually or always用來結合較低層次的STL 因由所定義出的多層斷言可以處理空間關係上的模糊不清和不完全的描述，並能提供一般性到特別詳細的事件規格，所以相當適合用來檢索及視訊的編輯 Spatial assertion：

32 視訊語意方向圖形 視訊片斷 V1 V2 V3 O11 O21 O31 O12 O22 O32 t1 t2 t3 t4 O23 O33
利用方向圖模型去捕捉物件和人在空間和時間上的屬性，稱為視訊語意方向圖形(VSDG, Video Semantic Directed Graph)模型 一旦物件由影像處理技術確定後，此模型就被用來維護其時間上的資訊 VSDC模型是認為在一段視訊中的空間及時間資訊皆可利用有向圖來表示，其範例如下圖所示 其中V1、V2、…、Vn表示所切割的視訊片斷 主要是表示有新物件加入或舊物件消失 圓形Oi表示並加上所具有的屬性 方塊的ti則代表改變的時間點 每個視訊片斷中的物件皆建立其中的關係以用來做後續的檢索 利用結合視訊格順序及其中物件邊框所形成3D投射參數的變化來加以記錄，即Oi的形式如下： Bounding Volume (Z) = (Bounding rectangular, centroid, depth) Bounding rectangular (Y) = (width, height, x, y) 此方法在最低的層次中對每一個視訊格記錄這些變化，雖然這樣的運動軌跡對視訊格式的索引是理想的，所需的計算開支是相當可怕 在效率的改善上，可利用分析事先所選擇固定時間距離的視訊格來產生運動軌跡的，而此距離可以取決於事件的複雜性，但主要的取捨在事件存儲的數量及對詳細資訊的需求間 上述的這些方法皆可用來描述更高層次內涵，其將在下面的部分中討論。 O12 O22 O32 t1 t2 t3 t4 O12球 O22球 O22球 O23 O33 O21球員2 O33球員3

33 空間-時間邏輯：n-ary關係 針對每個關鍵視訊格建立簡單空間事件 O:Overlap ; C:Contains
Day等人所提出的視訊資料的時間模型化方法為一種不具特殊領域的普遍化時間關係間隔表示法 所建立的空間-時間事件識別流程如下圖所示： 一個普遍化的空間關係是基於Symbolic projection在物件間的關係表示 時間關係亦同樣的利用這些關係來表示 稱為n-ary關係，其由n個標示由1到n的時間間隔排列而成，其假設連續兩個的時間間隔會滿足相同的時間關係，並用來建立出視訊語意的階層架構

34 空間-時間邏輯法 簡單時間事件可用n-ary關係將空間事件結合起來 複雜時間事件用簡單時間事件結合 首先針對每個關鍵視訊格建立簡單的空間事件
例如棒球比賽中”player holding the ball”的空間事件，可表為： 其中 及 表示物件player 1在x,y軸上bounding box的投射結果， 及 則代表球，且滿足M(meets),O,C,S,CO,E等關係， 代表logical operator，此 即可用來表示在此frame中的一個空間事件。 當每個frame中的空間事件建立後，簡單時間事件即可用n-ary的各種時間關係將有關係的空間事件結合起來 例如”holding the ball”及”passing of a ball between two players”兩個有前後時間關係的空間事件即可結合成一簡單時間事件 其中B代表在n-ary中時間before前後的關係； 代表空間事件i的duration，可用VSDG模型的方式來獲得 更複雜的合成時間事件 即可利用簡單時間事件結合起來，如”三次傳球”其可表為 其中 代表簡單時間事件I

35 代數視訊模型 實況轉播 遊戲 得分事件 傳球事件 灌籃事件 灌籃事件 得分 得分 灌籃 灌籃 傳球 階層式時間結合
Algebraic video 得分事件 Algebraic video Algebraic video Algebraic video 傳球事件 灌籃事件 灌籃事件 實況轉播 遊戲 得分 得分 R. Weiss等人提出另一種型式的代數視訊模型，主要的想法是認為以往的研究有下列兩個缺點： 無法提供視訊內涵存取 缺乏階層化或巢狀化的能力 以至於僅是timeline的存取，對具重疊性質的視訊無法有效的存取 因視訊本身即為非結構化視訊、音訊片斷的資料，無法僅用簡單的結構表示。 提出一個代數視訊模型(algebraic video model) 將video expression以高階語意描述(high-level semantic descriptions)階層式的組合起來表示視訊片斷的幕或事件 video expression可為用變數來命名，可將最基礎的視訊片斷(presentation)以複雜的邏輯結構組合起來，可具有描述式的資訊及所具有presentation在播放時的情狀說明，且可分享相同視訊的資料。 代數模型則以video expression為基本組成單元，並以一些數學定理來組合有意義的單元，如聯集、差集等 視訊代數(video algebra)可分為四大類，分別為： creation：用來將原始資料建構成video expression； composition：定義在video expression組合間的時間關係； output：定義video expression的空間位置及音訊輸出； description：用來結合video expression所具有的內涵屬性 利用下表的video algebra將video形成如下圖般的階層式架構，越高的階層其抽象的層次越高： 由這些代數操作可用來產生複雜視訊的表達，如根據某種所希望語意和描述的視訊片斷 內涵式的資料檢索則由管理每一個視訊presentation的description結合由使用者所查詢的名稱及數值而來 灌籃 灌籃 傳球 200 288 300 325 360 1290 1380 1700 階層式時間結合 具重疊及結合性質的VIDEO EXPRESSION Create、Description、union 的代數運算子運用 C1=Create NBA.場次.200,300 C2=Create NBA.場次300,360 C3=Create NBA.場次1290,1700 D1 =Description C1 “傳球‘ D2 =Description C2 “灌籃‘ D3 =Description C3 “灌籃‘ 得分事件= D1∪D2∪D3

36 無綱目視訊物件描述模型 OVID(Object-Oriented Video Information Database)
視訊物件是語意上有意義的幕 每個視訊皆具有獨立的性質，無法用以往關聯式資料庫事先定義屬性的方式來掌控，且其亦無法提供動態的schema evaluation 建構schemaless的物件導向資料庫 可以動態的增刪減物件複雜的屬性及具有繼承及封裝的優點 Oomoto等人所提的OVID(Object-Oriented Video Information Database)中，代數模型對所建構出的視訊物件為操作對象 此方法中的一個視訊物件，是語意上有意義的幕及一致事件所得出的視訊表達 主要的概念是認為每個視訊皆具有獨立的性質，無法用以往關聯式資料庫事先定義屬性的方式來掌控，且其亦無法提供動態的schema evaluation 所以OVID的目的是在建構一個schemaless的物件導向資料庫，可以動態的增刪減物件複雜的屬性及具有繼承及封裝的優點 因OODBMS並沒有提供視訊資料庫所需的time-interval inclusion relationship所以亦需提供interval inclusion inheritance的能力 其定義許多操作如下：”Evaluation of Interval Inheritance by a Single Object”、”Evaluation of Interval Inclusion Inheritance by Multiple Objects” 而物件階層亦需能利用generalization hierarchy(is-a)產生出來 所定義的操作有：”Least Upper Bound of Value”、”Greatest Lower Bound of Values” 且其使用產生物件的實例(instances)而非由物件分類上的定義而來，這樣的產生允許叢集具有相同語意的視訊片斷，而物件層次上的繼承則基於時間間隔上的包含關係 例如在視訊物件A的屬性/值對可為B所繼承，所定義的相關作有：”Interval Projection Operation”、Merge and Overlap of Interval Sets”、”Merge of Video-Objects”、”Overlap of Video-Objects”，皆可用來編輯視訊資料及定義出視訊物件的新實例

37 o1 球隊:隊1,… 下一場:遊戲1 賽程:全部比賽 o2 球隊:g1,… 下一場:無 賽程:全部比賽 NBA轉播 i1 遊戲1 i2 o3
球隊:隊1,隊2 下一場:實況2 賽程:對抗賽 球隊:隊2,隊3 下一場:實況3 賽程:季後賽 o5 球隊:g1,g2 賽程:總決賽 o4 實況轉播1 i3 實況轉播2 i4 i5 遊戲1 o6 o7 活動:得分 o8 活動:得分 活動:得分 i6 得分事件1 i7 i8 得分事件2 o9 o10 o12 得分事件3 o11 o13 活動:傳球 活動:灌籃 活動:傳球 活動:灌籃 活動:灌籃 i9 i10 i11 i12 i14 中場事件 前場事件 中場事件 前場事件 前場事件 時間軸 其提供一個VideoChart為瀏覽的介面，讓使用者可便利的完成Video-Object如play、inspect、disaggregate、merge、overlap的操作 在查詢上VOID採用VideoSQL，所得的結果為滿足查詢限制的一組Video-Object，語法如下。 SELECT語法和原先SQL的相當不同，主要是僅用來指定所要查詢video-objects的分類，具有Continuous、Incontinuous、及anyObject，其中Continuous表示video-objects 需滿足只為單一連續視訊格序列的；Incontinuous表示video-objects可為多個不連續視訊格序所組成；及anyObject不管是連續或不連續的皆可。 FROM的語法則用在指定資料庫中的name。 WHERE語法用來設定conditions、consisting of attribute/value pairs、comparison operators，現所提供的有下列三種。 [attribute] is [value | video-object]:用來找出符合所指定video-object中attribute值的video-object ，例如”Action is daily life”，而is-a的關係亦可用來查詢。 [attribute] contains [value | video-object]:主要是用在set-type attributes所具有的範圍。 definedOver [video sequence | video frame]：用來找出所指定的video sequence或frame，例如”definedOver frame(15000)” 此外其亦支援多種查詢的結合，以能更進一步提供視訊索引的功能

38 視訊資料庫模型化方法比較 模型 空間-時間模型(事件表示) 模型化方法 萃取語意的模式 查詢方法 Smoliar [SZ94]
事先定義的SCD-based model 分析及切割 自動 視覺式瀏覽工具 Yeung [YYW95] 階層式Scene transition mraph 人工或自動 Chen [CTD98] 無 Golshani [DKG00] Algebraic 物件識別及運動分析 Algebraic expression Day [DDI95] Spatio-temporal logic using object & event 人工輔助 Logical expression Bimbo [BVZ95] By sketch Oomoto [OT93] Algebraic using Video Objects 基於語意的切割 人工 Visual SQL-eased Wiess [WDG95] Algebraic using video expression Liu [LC] 3D-List H.Yu [YW97] 切割及物件識別 物件lookup table 表中亦可看出，能夠對視訊資料使用視覺式的查詢及瀏覽，是資料庫必須提供的一個重要特徵。特別是在以代數和邏輯表達中空間-時間的語意，如僅提供描述和形式化查詢時會有一定程度的困難。 在[BVZ95]中使用一個直覺界面提供視覺查詢的方式，但在視訊資料的空間-時間的模型化在本質上具有某種程度的不精準性 為了管理這樣的不精準性，其對物件間的空間關係使用不同水準精準度 在[DDI95]中，僅支援最精確和細微的陳述。 [DKG00]中所介紹的代數模型具有局限性，因其必須由使用者定義視訊物件與語意間的聯繫 兩個代數方法[OT93][WDG95]，必須按照物件軌跡讓使用者來參與定義這些視訊的語意 這些方法在鑑別語意時提供靈活性，但同時它們需遭受語意不同質性的挑戰，但同時由人工介入的高費用使得大規模視訊資料庫來使用這些方法變的不切實際。

39 結論及未來研究方向 發展有效率的內涵萃取方法 發展有效率的內涵式檢索演算法 視覺式的查詢及瀏覽
比較上Liu[LC]所提出利用2D-String概念擴展至視訊表示的方式較可行 因其可利用符號物件與低層內涵結合的方式得出更精確的檢索結果，並避免語意不同質的問題 在儲存、索引的數量具有相當的優勢，並能配合未來在更新一代MPEG視訊(MPEG4、MPEG7)內涵檢索的研究方向，但其語意所具有的模糊性應予以解決。 除影像處理所列出的挑戰外，還有幾個是視訊資料內涵所需探討 事件的語意模型化 空間-時間劇情說明的知識表示 查詢的表達等 皆是視訊資料庫未來在探討檢索議題上需廣泛研究的關鍵性問題

40 研究方向 發展有效率的視訊內涵萃取模型 發展有效率的視訊內涵檢索演算法 發展有效率的視訊查詢模型 由低層特徵到高層語意的表示
現有的研究除特徵向量能應用以往在高維向量的索引及檢索方法外，大部份都需發展針對本身所能萃取內涵的索引或檢索方法 如何建立出具有整合性的索引系統需加以探討，與如何將結合時間特徵的視訊語意內涵利用更有效率的方式精確檢索出來，仍需相當的努力。 且此前題是需具有能精確或標準化的萃取出影像及視訊的語意，但除非能自動產生出語意式的描述，否則資料庫建構者或使用者查詢所產生出語意不同質性的問題依然存在 所以如何將具相似性的語意查詢出來後再結合較低層次的內涵進行更準確的查詢是必要的。 在此考量下，如何合併一個新的內涵到現有的索引及查詢架構中，亦需加以考量，因在多媒體資料各種特徵萃取研究不斷精進下，不斷有更有效率的影像或視訊特徵被發展出來。 MARS所提的特徵向量模型中，要增加一個新的特徵相當的簡單，只要所有的特徵評估模組皆符合一致性的界面，一個組件幾乎可以即時增加的 此方法對高維度視訊內涵式資料檢索特別有幫助。因其一致性的介面避免因結合多種不同質性內涵在查詢時的容忍度問題 此一致性的界面主要是對特徵中(intra-feature)及特徵間(inter-feature)的向量進行正規化(normalization)的結果。 如何在模型中由使用者以比重將查詢各部分的相對重要性通知給系統 這些比重在查詢中描述的方法，及這些比重策略對檢索品質所造成影響，如不同影像及視訊的各種特徵內涵是否能提昇檢索品質等問題皆為未來這方面的檢索系統需加以研究的課題 在查詢介面上如何同時提供使用者視覺及語意上的查詢，PHOTOBOOK及VIDEOBOOK在這方面提供一個回饋式的介面製作，將是未來發展檢索系統的查詢介面時可以考慮的方向 本文主要針對多媒體資料在資料模型化和檢索方面的主要技術問題和方法 以影像及視訊資料為重點，並強調由在為多媒體資料管理形式時語意表示的重要作用，因其對使用者而言將是最具親和力的檢索方法 提供影像及視訊資料庫內涵式檢索問題的一個全景景觀及提出未研究的方向後，相信在各種多媒體數量不斷成長下，將會有更多此領域的研究發展出來，並提供更多元化的應用。