各位好  研究所助理自即日起更

換為賴郁秀小姐，請各位研究生洽公

逕洽賴小姐 包含畢業口試申請業務及

入學相關業務，謝謝 賴郁秀小姐 

分機4752 

e-mail eitc@cycu.edu.tw

姓名	李祐禎	職稱	辦事員
辦公室	篤信大樓 155	分機	03-2654603
EMAIL
工作職掌	教務方面：全系學期排課、選課、篩選條件及課程大綱等相關事宜;碩專班及博士班招生作業；夜間部延肄生及博士班畢業資格審查;暑修登記及排課、選課資格審查;大一及大二期中考寄發作業;教學問卷相關作業;學期帶課 學務方面：學生相關問題之協助、博士生及研究生獎助學金申請作業、……。 財務方面：管理系友會之財務及系友捐款事宜、系上財產報廢、登錄及異動等相關事宜等。 人事方面：專任教師及助教徵選資料整理及面試安排、提聘及相關人事作業、……。 系務方面：系上自強活動之策劃、兼任教師寄發賀年卡、系友會相關庶務、校友日之活動 配合及聯絡事宜、電子系系友獎學金及獎狀之製作發放作業、主任及行政單位交辦事項…

03-2654054 陳珮寧 院部助理

電子系口試時間地點

電子系口試時間地點

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

論文

首篇論文初期紀錄：

• First proposal:
• 研究如何以最低系統需求去搜尋電視廣告 2008/1
• Second proposal:
• 方向定義 2008/9。
• Paper Search 2008/9/25。
  

JPEG Performance Enhance

• JPEG Performance Enhance
  

• 
  

定義

2008/9 Jack. 實驗步驟

目的：
對於網路日漸盛行的 YouTube、無名等提供開放使用者上傳影音資訊存放而侵犯電影等相關版權議題，研究如何高速影像序列判讀，快速搜尋出兩段相同的影像序列。

實驗步驟：

• 取得影像：
• 目前以 解壓 MotionJPEG 作為目標,以方便取得影像為主，並容易將Decode 流程改進，增加比對速度。

• 單一影像處理：
  

• 縮小化影像：原始影像為640x480, 縮小至160x120。
• 取灰階影像：
• JPEG、MPEG都是以YUV作為影像基礎，取其Y(亮度值)即可。
• 在Decode 時即可省略U/V Decode，並合併第一步驟並省略不需要的Y值Decode程序。
• 取二值化影像：
• 二值化為黑白影像，取出大部輪廓。
• histogram 運用，是否需要？必須整張影像運算，耗時。
• 微分、Laplace 取灰階影像，並取得輪廓。( 這部分運算較高，也許僅作二值化取代)。
• 二階微分(Laplace)。
• Prewitt。
• 其中依影像內容在實驗中，可能需要先期作下列演算法運算
• 細線化：將細部輪廓描述出來。
• Hilditch。
• 遮罩方式、斷線、侵蝕問題。
  
• 膨脹化：將輪廓清晰 ( 膨脹+ 收縮 所需運算較中值少)。
• 膨脹。
• 收縮。
• 中值濾波。
  
• 輪廓比對：其中有幾種方式。
• 最簡單方式：影像直接取差，求得Distortion，依失真率判定影像是否相同。
• 較複雜方式：特徵值、標籤化的運用，目前尚未想到如何運用比較恰當，且比直接取差更有效率。

• 連續影像處理：
• 方法一：longest common subsequence、LCS：不用連續。O(n^2)
• 方法二：Longest Common Substring：連續 ，O(m+n)。
• 方法三：先將A影像序列作分類，在一定的相似度下的影像歸為一個群組，然後將B影像依序與A的每個群組其中一張影像與B影像作比對。
  

Questions:

1. 這些影像技術幾乎都是現有的技術，只是將集合起來並串起來運用，應該如何從中找到能發表的論文？
2. 目前似乎沒有這類可比對的數據、或是參考的應用，如果要針對某個細項去找題目，哪個點較容易發揮？
3. 為了寫出較能自行控制Decode 流程的 Decoder，目前還在JPEG Spec 上打轉，預計暑假結束前能完成一個基本Decoder ，並處理縮小化、灰階運算。
   

Reference:

• ITU T.81 JPEG壓縮 http://www.w3.org/Graphics/JPEG/itu-t81.pdf

• JPEG File Interchange Format V1.02 http://www.w3.org/Graphics/JPEG/jfif3.pdf
• MPEG-7 Overview http://www.chiariglione.org/MPEG/standards/mpeg-7/mpeg-7.htm
  

DirectX

dxguid.lib和ddraw.lib

OpenGL

OpenGL web Site

In Linux：

• yum install freeglut-devel.i386
• 
  

BCB Jpeg show

#include
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
TJPEGImage *jpg=new TJPEGImage;
void __fastcall TForm1::FormCreate(TObject *Sender)
{

jpg->LoadFromFile("test.jpg");

}
//---------------------------------------------------------------------------

void __fastcall TForm1::Button1Click(TObject *Sender){
Image1->Canvas->Draw(0,0,jpg);

Graphics::TBitmap *bmp = new Graphics::TBitmap;
TRect Dect, Sect;
Dect = Rect(0, 0, jpg->Width, jpg->Height);
Sect = Rect(0, 0, jpg->Width, jpg->Height);
//pb->Canvas->Brush->Style = bsClear;

bmp->Width = jpg->Width;
bmp->Height = jpg->Height;
bmp->Canvas->CopyRect(Dect, Image1->Canvas, Sect);

bmp->SaveToFile("c:\\test.bmp");
delete bmp;
delete jpg;

}