電子系口試時間地點

電子系口試時間地點

7/1 週四 中午 12:00 電子篤信一樓 105

電子系 李小姐 265-4603 sterra@cycu.edu.tw

影像比對

2009/2/16(一)

目的：
目前有一 2HR 影片，隨機抽取其中30 sec 影像，利用程式要找出這30 sec影像位置.
假設這2HR影片來源有可能不是原始的(轉檔過或是再重製過)，壓縮格式可能是MPEG4/H.264.

假設影像大小:

• Resolution: 352x240 ( CIF ).
• FPS : 30 frame per second.
• Compress: H.264.
• 原始影像: 2HR , 108000 Frame.
• 比對影像: 1 sec, 30 Frame.
  

步驟:

• 2HR影像序列，以每秒 30fps，2hr x 60mins/hr x 60 sec/hr = 共108000 frame
• 每個 frame 切成 NxM，以下面例子假設 N=176 : M = 120 ，故一個畫面切成四個Micro Block(之後統稱 MB1/MB2/MB3/MB4 ).
• 將欲比對的資料( 30sec )，以同樣的作法切分(以下稱為 Target Block TB1/TB2/TB3/TB4 ).
  
• 每個MB 取其 R/G/B 平均值，於是每一個Frame 就會有4組 R/G/B平均值.
• 為節省比對時間，先以R為主，有相似後再比G，B以此類推。
• 取出每個Frame的 MB1 ，可以得到 108000 個的資料序列。
  
• 題目所示，將欲比對的30sec，以同樣的作法，取出TB1的30個的資料序列。
• 用 TB1 30個去掃描 MB1的108000，找出相似段落，若有相似:
  
  • 方法一：依序掃描 TB2 及 MB1 該位置是否相似，TB3/TB4相同.若同在作
  • 方法二：先掃描 TB1(G/B)線，在回頭作方法一。

以上為簡略說明：

• 實作上可能不以RGB色彩比對，會改以YUV，Y取亮度較單一R or G or B精準，且解壓縮後無須再轉為RGB.
• block 數切分為 4 Block為範例，4 Block 基本上會造成 normalize而無參考價值。
• 320x240 resolution太小，一般影片為 720x480 ( D1 ).

問題：

• N/M 值該如何取適當，取太小有normalize的問題，取太大則增加比對時間。
• 如何比? 如果原始影像經過重製or 放大縮小，則每個MB 會有誤差的現象發生而不是相同，目前誤差的現象只能以 abs 處理，若誤差絕對值小於 X， X = 5%，則判定相似?
• 如上：連續誤差及雜訊問題。
• 目前把每個點串起來，弄成一個2D圖形，類似一個波型圖，以肉眼觀之是可以區分的，以上述作法應該也可行，但有沒有更好的資料比對方式。
• 目前再學校的圖書館網站找了一些Paper，似乎沒有這樣子的作法，這樣的資料比對可以說是純粹的Data search，而大部分的影像搜尋都是跟contain的Information有關。

報告

• MIPS-Lite CPU Design using SystemC
  

  • 2008/12/10 ESL Midterm Project Design.
  • SystemC Modeling of MIPS-Lite and C/ASM Compiler Coding.

• JPEG Performance Enhance
  

  • 2008/6/30 SOC Design and Implementation Course final project.
  • JPEG En/Decoder SW/HW Implementation on FPGA.

MIPS-Lite CPU Design using SystemC

MIPS-Lite CPU Design using SystemC 2008/12/10

Fast Similarity Search and Clustering of Video Sequences on the World-Wide-Web

Fast Similarity Search and Clustering of Video Sequences on the World-Wide-Web
Sen-ching S. Cheung, Member, IEEE, and Avideh Zakhor, Fellow, IEEE

Abstract -

• 這篇基本上是延續上一篇論文，上一篇提出的一個方法
  
• randomized technique called the video signature (ViSig) method for video similarity
  measurement.
• 拿 4 種方式比較，ViSig 比這四種好.
• PCA, Fastmap, Triangle-Inequality Pruning, and Haar wavelet
  
• 在這篇paper, 主要兩個重點
• 特徵提取的快速相似性搜索
• 以及clustering algorithm來確定類似集群
• 最後提到的方式是針對 local data 找出某個 threshold，在比較相似的圖.

Introduction-

• 他的目的也是想利用搜索引擎來找出類似視頻版權內容的法律 issue.
• 又提到（ ViSig ），兩幀之間部分類似的共同序列。 ViSig產生一個 簽名並以database儲存.並可以處裡序列時間大不相同的問題.
• 公式: ( 看來也是要分類進行)
  
• warping distance[3]–[5]
• Hausdorff distance [6]
• template matching[7]
• 他也拿以下公式比較，他的更優，複雜度更低
• 密度參數[ 8 ] -[ 1 0]
• 關鍵幀或中心點[ 6 ]
  
• 基於上一篇ViSig ，本文提出兩個重點
• A. Fast Similarity Search
• 針對大型DB的比對，Elaborate data structures 統稱為spatial access methods（ SAM ）有提出一些公式 [11]–[13].但對於高維度的空間資料並不方便.
• Principal Component Analysis (PCA)已被證明是最佳的近似Euclidean distance[ 15 ].
• Multidimensional dimension scaling (MDS) 可用在高維度相似搜尋並解決了非線性優化問題, 但過於複雜.
• Fastmap mapping 是一種低覆雜度的演算法，由Faloutsos and Lin [18].提出，使用heuristics algorithm 求歐幾里德的近似值. 產生 Fastmap mapping時，時間的覆雜性對於DataBase 的大小呈線性的關系.
• 
  
• 
  
• B. Similarity Clustering
  
• SectionII-A 討論如何做出一個簽名.
• SectionII-B 在 A 架構之下，如何快速搜尋.
• SectionII-C 對於他的公式建議.

Algorithms-

• SectionII A:
• 
  

Memo:

• PCM(Principle Component Analysis:主要成分分析法
• ICA(Independent Component Analysis):獨立成份分析法
• 上面兩種用意皆類似DCT，用意再捨棄變異小的變數，一樣是失真，屬於非高斯分布( nongaussian)實作方式常見於KLT(Karhunan-Loeve Transform)，相較於複雜度高於DCT.
• PCA - Principal Component Analysis with Missing Data
• http://www.cmlab.csie.ntu.edu.tw/~cyy/learning/tutorials/PCAMissingData.pdf
  

Questions:

• Fellow - 研究員?...是指 Avideh Zakhor 是IEEE的 Fellow , Cheung 是 IEEE Member? 很有名氣的意思嗎? 這樣算是 Avideh Zakhor 掛名嗎?
• 在Introduction 有提到受到兩個單位贊助，這個放Introduction?
• Air Force Office of Scientific Research (AFOSR)
• National Science Foundation (NSF).
• 
  

FingerPrint Research

2008/9/24.

FingerPrint

• Biometrics Research Homepage at MSU
• FingerPrint Identification
• Filtering Large Fingerprint Database for Latent Matching. Jianjiang Feng and Anil K. Jain Dec. 2008
• fingerprint classification minutiae pattern matching , NTHU Repository. 433108.pdf
  

Plate Reconition:

• 具車牌辨識功能之四通道即時數位監視系統之研製 [電機工程] 博碩士論文 393408.pdf
• Nearest Image Matching Technique
• 空間投影.
• 動態時間偏移.
• 未使用複雜的特徵向量.
• SIMILARITY-BASED SUBSEQUENCE SEARCH IN IMAGE SEQUENCE DATABASES
• Fast Similarity Search and Clustering of Video Sequences on the World-Wide-Web
• 這篇看來有必要深入瞭解.
• EFFICIENT VIDEO SIMILARITY MEASUREMENT AND SEARCH, Department of Electrical Engineering and Computer Sciences University of California Berkeley, CA 94720{cheungsc, avz
  }@eecs.berkeley.edu ICIP 2000
• ABSTRACT
  We consider the use of meta-data and/or video-domain methods to detect similar videos on the web. Meta-data is extracted from the textual and hyperlink information associated with each video clip. In video domain, we apply an efficient similarity detection algorithm called video signature. The idea is to form a signature for each clip by selecting a small number of its frames that are most similar to a set of random seed images.
• We then apply a statistical pruning algorithm to allow fast detection on very large databases. Using a small ground-truth set, we achieve 90% recall and 95% precision using only 8% of the total number of operations required without pruning.
• For a database of around 46,000 video clips crawled from the web, video signature technique significantly outperforms meta-data in precision and recall. We show that even better performance can be achieved by combining them together. Based on our measurements, each video clip in our database has, on average, 1.53 similar copies.
  
• A fast shot matching strategy for detecting duplicate sequences in a television stream ACM International Conference Proceeding Series; Vol. 16
  要從學校圖書館進去抓.
• ABSTRACT

  This article presents a method for detecting duplicate sequences in a continuous television stream. This is of interest to many applications, including commercials monitoring and video indexing. Repetitions can also be used as a way of structuring television streams by detecting inter-program breaks as a set of duplicate sequences. In this context, we present a shot-based method for detecting repeated sequences efficiently. Experiments show that this fast shot matching strategy allows us to retrieve duplicated shots between a 1 hour long query and a 24 hours database in only 10 ms.

• Searching for repeated video sequences
• ABSTRACT

  In this paper, we propose a new method to search different instances of a video sequence inside a long video and/or video collection. The proposed method is robust to view point and illumination changes which may occur since the sequences are captured in different times with different cameras, and to the differences in the order and the number of frames in the sequences which may occur due to editing. The algorithm does not require any query to be given for searching, and finds all repeating video sequences inside a long video in a fully automatic way. First, the frames in a video are ranked according to their similarity on the distribution of salient points and colour values. Then, a tree based approach is used to seek for the repetitions of a video sequence if there is any. Results are provided on a full length feature movie, Run Lola Run and on commercials of TRECVID 2004 news video corpus.
  

Other:

• Data Clustering and Plate Reconition. Jyh-Shing Roger Jang（張智星）Associate Professor CS Dept., Tsing Hua University, Taiwan
• 歐幾里得距離、餘絃相似度、LCS 講解.
• Ertem Tuncel, H.F., Kenneth Rose, VQ-Index:An Index Structure for Similarity Searching in Multimedia Databases. in ACM Multimedia, ( 2002 ).
• 這篇著重VQ 演算，VQ為類似DCT之演算，為軸坐標轉換，轉換後再做Quantization，由於VQ data partation 並非四方型，其演算複雜度不亞於DCT.
• 用到一些 : k-nearest-neighbor (k-NN) query.
  

結論:

• 大部份比對都區分五類 "Arch"、”Left Loop”、”Right Loop”、”Whorl”和”Others.
• 基本程序:
• 強化、濾波(含constrast、Intensity processing).
  
• histogram.
• Smoothing、Thinning.
  
• 分類 ( 上述五類 )，再根據類別不同，分別判斷.
• Blocking split.
• Ridge
• 指紋跟車牌是應用類似的原理，都事先分類，讀取影像後，將其歸類後再施以固定演算求得：
• 車牌:
• 取出車牌該區影像.
• 跟據 1- 9、A-Z ，每個字的不同特徵( 區塊內空白區)，去判讀
• 指紋:
• 過濾雜訊後，分離出純指紋.
• 將指紋分類( 一般都是5類 ) .
• 根據不同類型，判讀方式不同，各有簡易.
  

問題：

• 比對電視或電影影像並無特定特徵值可 Fix 演算設計.
  

Term:

• Dynamic Time Warping.
  

Paper:

• Upcoming conferences.
• The ACM Digital Library.

研究如何以最低系統需求去搜尋電視廣告

研究如何以最低系統需求去搜尋電視廣告

資工碩專一 陳建芳 2008/1/25

動機:

以某固定廣告片段，去搜尋某個電視台所錄下的影像，找出此一廣告發生的時間長度。

若以單一影像 依YUV去判斷，再作Fuzzy比對，將嚴重拖慢比對時間。

目前的構想是取得MPEG4壓縮檔案後，在處理Entropy Coding、Inverse ZigZag、Huffman Decode Thresholder 之後，Inverse DCT之前, 將Block 資料直接拿來比對，由於在Decode過程中，Huffman 、Zigzag還原僅用到加法及移位運算，而IDCT後用到乘法運算，如此一來即可直接減少大量 IDCT、MV、Predict、Block indegrater 等花費的時間。

目標: 以一台電腦可搜尋 30Channels的連續影像，每一Channel 約30天，並判別 50-100個廣告(約10秒長度)出現的總時間長度，正確度需達95%以上。

目標一: 以每個廣告的第一張拿來辨識，能正確找出影像。

目標二: 能判斷10秒的廣告出現其中的幾秒。

目標三: 10秒的廣告也許被切割成三段, 分別撥出，或是 1+3 等。

系統:

MPEG4( I/P Frame ) Advanced Simple Profile/Level 5 Encoder

Linux 2.6 , GCC-4.1

Xvid-1.1.3 software Decode. ( In Linux )

VLC.( In Windows )

規格:

CIF-352x240 30FPS

MicroBlock 22 x 15 ( (8x8) x 4 dct ) .

實驗步驟:

1. 利用VLC 透過RTSP 將 X牌 IPCAM 電視影像以Element stream錄起來

( 此一步驟乃先期測試用，未來將改以直讀 Encoder , 並自行控制 Index File , 並自定格式，以達提升Performance ).

2. 先用肉眼觀查，尋找相同廣告片段。

影像序列範例EX: I1 P1 P2 P3 P4 P5… ...P13 P14 P15….P29 I2 P21 P22 P23…..

1. 利用xvid 讀取 VOS、VOL、VOP..等Header ( 測試階段採用Only ).

2. 當xvid decode 步驟完成 Huffman、zigzag scan 完成 bitplant 還原後，在IDCT之前，將整個畫面的Block存起來，P15 DCT取法採做快速作法，直接延用之前I1 所遺留之Block，完全不計算Inter、Intra、Predict、MV等運算( P1 – P14 所作的Intra IDCT 更動也納入改變)。

實驗結果:

1. 直接抓取 2040 與19076 ( 以下簡稱 A、B frame ) 的Block，僅比較所有Block的DC值，(Block 區塊共 22x15x4 =1320)。

   1. 當沒有誤差值時，共有1192塊不相同、錯誤率約90%。

Error[1320.000000] DC=1192.000000 (90.303030)%

2. 當誤差值小於8時，共有1108塊不相同、錯誤率約89%。

Error[1320.000000] DC=1108.000000 (83.939394)%

3. 當誤差值小於16時，共有915塊不相同、錯誤率約69%。

Error[1320.000000] DC=915.000000 (69.318182)%

結論:

1.在第2040、19076 偵時，出現相同的廣告，但這兩偵都不是I偵，然而其前一偵卻又不儘相同(圖一)，此台IPCAM無法強制IFrame，故由PFrame 作MB Intra變化，重新做IDCT。

2. P 2040 從圖上看來與P2039 相似度較高，且從Coding 觀察，2040用了許多MV forward(MB Inter)，而19076就少了非常多，forward 表該Block不需要再作IDCT，直接由前一Frame Motion vector forward來，所以這樣的做法不可行。

分析:

1. Video reconstruction時, 許多使用 MV Forward的方式不用再透過IDCT轉換，導至此一實驗所抓取的值不正確。

2. 數據的取得為 Y 的 DCT block , UV 未納入考量(減少Performance損耗)，然而仔細看2040、19076圖，為相同廣告卻還是約略有所不同。

3. 誤差值增加到 + - 16 以屬高，再加下去恐有誤判。

下期研究方向:

1. Source Frame 重新壓製? 使其起始影像為IFrame , 提升 比對的正確性。

2. 加大第一階誤差值，進入第二階段後，以相鄰Block(n個) 為一組，若誤差同為 某數X即判定相同。

3. 當PFrame 採用Inter Prediction 時，無法由歷史資料得到該Block 正確IDCT前的資料, 找方式把Predict後的資料取回。

   1. 若只能從 prediction 後再 DCT回來, 則將損耗時間，若花費時間大於整張PFrame的Decode , 則沒有義意。

   2. 若由臨近的block predict 而來，用臨近的Block 值取代(少量誤差)。

4. 若3、4點能提升識別、則可由 Frame 序列的相關性再提升辨識度。

• PFrame 2039

• PFrame 2040

  

• PFrame 19075
• 

• PFrame 19076