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.
Wednesday, December 10, 2008
報告
Wednesday, October 1, 2008
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 -
Memo:
Questions:
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，在比較相似的圖.
- 他的目的也是想利用搜索引擎來找出類似視頻版權內容的法律 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 對於他的公式建議.
- 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).
Tuesday, September 23, 2008
FingerPrint Research
2008/9/24.
FingerPrint
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
- 具車牌辨識功能之四通道即時數位監視系統之研製 [電機工程] 博碩士論文 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.
- Data Clustering and Plate Reconition. Jyh-Shing Roger Jang（張智星）Associate Professor CS Dept., Tsing Hua University, Taiwan
- 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 演算設計.
- Dynamic Time Warping.
Monday, September 22, 2008
研究如何以最低系統需求去搜尋電視廣告
研究如何以最低系統需求去搜尋電視廣告
資工碩專一 陳建芳 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…..
利用xvid 讀取 VOS、VOL、VOP..等Header ( 測試階段採用Only ).
當xvid decode 步驟完成 Huffman、zigzag scan 完成 bitplant 還原後，在IDCT之前，將整個畫面的Block存起來，P15 DCT取法採做快速作法，直接延用之前I1 所遺留之Block，完全不計算Inter、Intra、Predict、MV等運算( P1 – P14 所作的Intra IDCT 更動也納入改變)。
實驗結果:
直接抓取 2040 與19076 ( 以下簡稱 A、B frame ) 的Block，僅比較所有Block的DC值，(Block 區塊共 22x15x4 =1320)。
當沒有誤差值時，共有1192塊不相同、錯誤率約90%。
Error[1320.000000] DC=1192.000000 (90.303030)%
當誤差值小於8時，共有1108塊不相同、錯誤率約89%。
Error[1320.000000] DC=1108.000000 (83.939394)%
當誤差值小於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來，所以這樣的做法不可行。
分析:
Video reconstruction時, 許多使用 MV Forward的方式不用再透過IDCT轉換，導至此一實驗所抓取的值不正確。
數據的取得為 Y 的 DCT block , UV 未納入考量(減少Performance損耗)，然而仔細看2040、19076圖，為相同廣告卻還是約略有所不同。
誤差值增加到 + - 16 以屬高，再加下去恐有誤判。
下期研究方向:
Source Frame 重新壓製? 使其起始影像為IFrame , 提升 比對的正確性。
加大第一階誤差值，進入第二階段後，以相鄰Block(n個) 為一組，若誤差同為 某數X即判定相同。
當PFrame 採用Inter Prediction 時，無法由歷史資料得到該Block 正確IDCT前的資料, 找方式把Predict後的資料取回。
若只能從 prediction 後再 DCT回來, 則將損耗時間，若花費時間大於整張PFrame的Decode , 則沒有義意。
若由臨近的block predict 而來，用臨近的Block 值取代(少量誤差)。
若3、4點能提升識別、則可由 Frame 序列的相關性再提升辨識度。
- PFrame 2039
- PFrame 2040
- PFrame 19075
- PFrame 19076
定義
2008/9 Jack. 實驗步驟
目的：
對於網路日漸盛行的 YouTube、無名等提供開放使用者上傳影音資訊存放而侵犯電影等相關版權議題，研究如何高速影像序列判讀，快速搜尋出兩段相同的影像序列。
實驗步驟：
Questions:
Reference:
目的：
對於網路日漸盛行的 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:
- 這些影像技術幾乎都是現有的技術，只是將集合起來並串起來運用，應該如何從中找到能發表的論文？
- 目前似乎沒有這類可比對的數據、或是參考的應用，如果要針對某個細項去找題目，哪個點較容易發揮？
- 為了寫出較能自行控制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
Monday, July 7, 2008
Tuesday, July 1, 2008
Friday, June 6, 2008
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;
}
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;
}
Subscribe to:
Comments (Atom)