以碎形正交基底和時間情境圖為基礎進行之視訊檢索 Video retrieval based on fractal orthogonal bases and temporal graph 阿凡達 研究生：張敏倫 指導教授：蔣依吾博士 國立中山大學資訊工程學系

視訊檢索 關鍵字-檔名 Content based video retrieval(CBVR) 人工定義-見解不同定義有所差別 關鍵字意義不同 Content based video retrieval(CBVR) 傳統方法–影片摘要 缺乏視訊結構上觀點 本論文 視訊結構-時間情境圖 視訊內容-碎形正交基底

Li Gao and Zhu Li, “An Efficient Video Indexing and Retrieval Algorithm Using the Luminance Field Trajectory Modeling,” IEEE Trans. on circuits and systems for video technology, vol. 19, no. 10, p.1566~1570, Oct. 2009. 2009 C.-W. Su, H.-Y. Mark Liao, K.-C. Fan, C.-W. Lin and H.-R. Tyan, ”Motion Flow-Based Video Retrieval,” IEEE Trans. Multimedia, Vol. 9, No. 6, pp. 1193-1201, 2007. 2007 W. Hu, D. Xie, Z. Fu, W. Zeng, and S. Maybank, “Semantic-Based Surveillance Video Retrieval,” IEEE Trans. Image Processing, Vol. 16, No. 4, April 2007 X. Zhu, A. K. Elmagarmid, X. Xue, L. Wu, and Ann Christine Catlin, “InsightVideo: Toward Hierarchical Video Content Organization for Efficient Browsing, Summarization and Retrieval,” IEEE Trans. Multimedia , vol. 7, no. 4, pp. 648~665, Aug. 2005. 2005 影像從人工關鍵字到CBIR 再到 CBVR有下列重點: 時間複雜度極高-分析階段，組織階段，比較(影像序列:如監視影像、或運動影像) 有效果的搜尋 解釋這四篇之意義 – Video retrieval 降低時間複雜度 搜尋時間 提出新的概念 Camera motion

分鏡 關鍵影像擷取 群集 場景 相似性量測 測試序列 K-d Tree N(Q) is the total number of frames in the leaf nodes traversed by Q N is the total number of frames in the database Open Video 無Scene分割 目的:降低搜尋時間 舉例:database裡有10個種類 輸入影片為3種類 只要找三個種類即可

分鏡 關鍵影像擷取 群集 場景 相似性量測 測試序列 Motion-tolerant dissolve detection algorithm[1] and Shot change detection based on the Reynolds transport theorem [2] 以trajectory來取代Key-frame

分鏡 關鍵影像擷取 群集 場景 相似性量測 測試序列 Query-Keyword Multiple object queries Query by sketch Surveillance video

分鏡 關鍵影像擷取 群集 場景 相似性量測 測試序列 Frame Level Similarity Shot Level Similarity Shot-Length Matching Average Color Histogram Matching Camera Motion Matching Key-frame Matching Group Level Similarity Scene Level Similarity Video Level Similarity Open video

依據比率失真度準則進行shot segment並擷取關鍵影像 影片序列輸入 Shot 內變異數達預設比率 N NCut分群 建立時間情境圖 有向圖轉字串 相似性量測: 1. 視訊結構 2. 視訊結構和視訊內容 FOB frame String Video Y HSV粗略分割 字串剖析

依據比率失真度準則進行shot segment並擷取關鍵影像 影片序列輸入 Shot 內變異數達預設比率 N NCut分群 建立時間情境圖 有向圖轉字串 FOB frame String Video Y HSV粗略分割 字串剖析 相似性量測: 1. 視訊結構 2. 視訊結構和視訊內容

HSV粗略分割-降低複雜度 HSV初始分割 影像之HSV histogram 交集定義影像之間相似度 令 為第x張影像之彩色直方圖，影像x與影像y之色彩相似度定義為

擷取關鍵影像 根據失真變異度 每個分鏡選取一張關鍵影像 若分鏡差異失真度大於threshold則分割 2 3 4 5 6 8 9 1 7 2 2 3 4 5 6 8 9 10 11 12 13 1 7 14 2 3 4 5 6 8 9 10 11 12 13 1 7 14

motion compensated current frame reference frame reconstructed frame

Rate- distortion criterion

Rate- distortion criterion

依據比率失真度準則進行shot segment並擷取關鍵影像 影片序列輸入 Shot 內變異數達預設比率 N NCut分群 建立時間情境圖 有向圖轉字串 FOB frame String Video Y HSV粗略分割 字串剖析 相似性量測: 1. 視訊結構 2. 視訊結構和視訊內容

Clustering Using Normalized Cut 每個segment代表節點，邊(edge)上之權重值為 解公式(1)藉由合適特徵值所對應之特徵向量 分群概念 數字涵義

Temporal graph generation 先建立節點 再建立edge 成為有向圖 1 1 2 3 4 2 5 2 6 7 8 9

依據比率失真度準則進行shot segment並擷取關鍵影像 影片序列輸入 Shot 內變異數達預設比率 N NCut分群 建立時間情境圖 有向圖轉字串 相似性量測 FOB frame String Video Y HSV粗略分割 字串剖析

有向圖轉字串- Algorithm [ 0 1 2 6 7 8 9 ] [ 0 1 2 6 7 8 9 [ 2 5 2] ] [ 0 1 2 6 7 8 9 ] [ 0 1 2 6 7 8 9 [ 2 5 2] ] [ 0 1 2 6 7 8 9 [ 2 5 2 [ 2 3 4 2] ] ] [ 0 1 3 4 8 [ 1 2 1] [ 3 5 6 7 4 [ ( 53 45) ] ] ] [ 0 1 3 4 8 [ 1 2 1] [ 3 5 6 7 4 ] ] [ 0 1 3 4 8 [ 1 2 1] ] [ 0 1 3 4 8 ]

依據比率失真度準則進行shot segment並擷取關鍵影像 影片序列輸入 Shot 內變異數達預設比率 N NCut分群 建立時間情境圖 有向圖轉字串 FOB frame String Video Y HSV粗略分割 字串剖析 相似性量測: 1. 視訊結構 2. 視訊結構和視訊內容

相似性量測-視訊結構 利用edit-distance對兩string的主結構字串做相似性量測 single node 有結構node (n-1)/n 1

Edit Distance To find a smallest edit process between two strings. S1: TAGTCAC G S2: AG ACTGTC Operation: DMMDDMMIMII

0 1 2 12 [2 11 2 [ 2 3 2 [ 2 8 9 10 2 [ 2 4 5 6 7 2 ] ] ] ]

University of Maryland, College of Information Studies 影片名稱 時間 種類 影像數 關鍵影像數 出處 New Indians, Segment 02 00:03:28 Documentary 6231 10 University of Maryland, College of Information Studies NASA 25th Anniversary Show, Segment 01 00:03:30 6414 13 NASA 25th Anniversary Show, Segment 03 00:02:22 4718 22 The Colorado, segment 01 of 10 00:03:13 6164 7 Carnegie Mellon University, Informedia Project A New Horizon, segment 05 of 13 00:01:59 4046 17 Bor 00:01:06 Public Service 1989 JHUCCP Drift Ice as a Geologic Agent, segment 7 of 11 00:01:05 1920 11 , Informedia Project Drift Ice as a Geologic Agent, segment 10 of 11 00:03:46 1380 Family Planning TV Spots Around the World: Kyrgyzstan 00:01:14 2442 15 How Water Won the West, segment 03 of 8 00:01:25 2805 19 New Indians, Segment 14 00:01:43 3399 16 NASAKSNN - How Do Space Shuttles Blast Off 00:00:30 Educational 902 6 NASA New Indians, Segment 111 00:01:02 1860 14 of , Studies Senses And Sensitivity, Introduction to Lecture 1 presenter 00:02:20 Lecture 4620 25 University of North Carolina at Chapel Hill, Interaction Design Lab The Voyage of the Lee 00:01:15 2272 12 Geological Survey New Indians, Segment 12 00:02:42 5346 21 NASA Connect - ISS - Space Station Parts 00:04:25 8745 31

視訊結構

碎形正交基底(FOB) 相似影像有相似碎形函數； 相似歸結圖有相似碎形函數； 兩碎形函數不相似，其歸結圖亦不相似； 兩影像不相似，其碎形函數亦不相似； 先敘述四個重點證明 碎形的兩個缺點 FOB簡介 不再由單一個，而是由複數個block線性組合，例如8*8 block 就由64個線性組合 64個區塊式訓練出來的 由一張高複雜度的圖形訓練得來 ，且每個區塊是正交

相似性量測-視訊結構和視訊內容 利用edit-distance對兩string主結構計算互相之distance single node 0+ (n-1)/n+1/n* 1 因此比需修正 Fob(I,J) 0 代表像 fob(I,j) 1 代表不像 1. Single 與 single 結構性距離 為0，但是fob算出來的數值，不見得為0

視訊結構和視訊內容 0 1 2 12 [2 11 2 [ 2 3 2 [ 2 8 9 10 2 [ 2 4 5 6 7 2 ] ] ] ]

0 1 [ 1 2 3 1 [ 3 4 3 ] ]

視訊結構

視訊結構和視訊內容

結論與未來展望 結論 分群準則-影響時間情境圖 時間複雜度-視訊結構和視訊內容 未來展望 依個人喜好建立個人化之影片類別 降低計算時間

報告完畢 謝謝