丁建均 (Jian-Jiun Ding) National Taiwan University

Presentation on theme: "丁建均 (Jian-Jiun Ding) National Taiwan University"— Presentation transcript:

1 丁建均 (Jian-Jiun Ding) National Taiwan University
辦公室：明達館723室， 實驗室：明達館531室 聯絡電話： (02) Major：Digital Signal Processing Digital Image Processing

2 Research Fields (1) Image Compression (page 3)
(2) Segmentation (page 13) (3) Pattern Recognition (Face, Character) (page 19) (4) Time-Frequency Analysis (page 22) (5) Music Signal Analysis (page 34) (6) Bioinformatics (page 38) (7) ECG Signal Analysis (page 42) 專題研究相關規定 (page 47)

3 1. Image Compression 要學習的項目： (1) 影像處理的基本技巧 (2) JPEG 程式的編寫 (3) 誤差的量測方式
(4) 其他影像壓縮的技術 (5) 查資料和做研究的方法和技巧

4 Conventional JPEG method:
Separate the original image into many 8*8 blocks, then using the DCT to code each blocks. DCT: discrete cosine transform

5 壓縮的基本原理： 影像在經過 discrete cosine transform (DCT) 之後，大部分的能量都集中在低頻 DCT

6 問題：壓縮率高的時候，會產生 blocking effect
JPEG 是當前最普及的影像壓縮格式。 問題：壓縮率高的時候，會產生 blocking effect Compression ratio = RMSE =

7 New Method: Edge-Based Segmentation and Compression
和小時候畫圖的方法類似

8 Image Segment Compression
Segmentation-based image compression Boundary Boundary Compression Image Segmentation Bit stream An image Image Segment Compression Image Segment

9 Original Image By JPEG By Proposed Method An 100x100 image Bytes: 1295, RMSE: 2.39 Bytes: 456, RMSE: 2.54

10 原圖 (10000 bytes) 使用 JPEG (692 bytes) 使用 JPEG (233 bytes) 使用新方法 (165 bytes)

11 折衷的方法： 既不按照 88 的方格來做切割，也不完全按照物體的形狀 Triangular and Trapezoid (梯形) Block Segmentation

12 技術上的問題： (1) 如何找到物體的邊緣並切割？(努力中) (2) 如何針對不規則的區域，找到 orthogonal transform (已解決) (3) 如何避免讓邊緣區域的高頻成分影響到壓縮的結果 (已解決) (4) 如何用最小的資料量，對邊界的部分做紀錄 (已解決) (5) 如何用最小的資料量，對內部的部分做紀錄 (努力中) (6) 減少壓縮和解壓縮的運算時間 (努力中)

13 2. Segmentation Important for compression biomedical engineering
object identification 要學習的項目： (1) 影像處理的基本技巧 (2) Image segmentation 程式的編寫 (3) Image segmentation 的應用 (4) 查資料和做研究的方法和技巧

14 Conventional method: 97.87 sec New method: 1.02 sec

15 未受過傷的老鼠肌肉纖維 受過傷的老鼠肌肉纖維

16 未受過傷的老鼠肌肉纖維「分區」的結果

17 受過傷的老鼠肌肉纖維「分區」的結果

18 大腦核磁共振影像 (Brain MRI Image)
(a) Brain MRI Image (b) White Matter (白質) (c) Gray Matter (灰質) (d) 腦髓液蛋白，頭蓋骨

19 3. Pattern Recognition including face recognition (子題目一)
character recognition (子題目二) 二選一 應用很廣： security, identification, computer vision ………… 要學習的項目： (1) 影像處理的基本技巧 (2) 特徵擷取的技術 (角，邊緣，骨架 …) (3) Pattern 判斷的方式 (4) 查資料和做研究的方法和技巧

20 Category “A” Category “B” Classification Clustering

21 最簡單的方法： matched filter
但技術上的問題頗多………. scaling shadow rotation partially distortion 目前較常用的方法： Feature Extraction + Machine Learning 臉有哪些特徵？

22 4. Time-Frequency Analysis
要學習的項目： (1) 使用 Fourier transform 來分析信號頻譜的正確方式 (2) 聲音信號處理的基本知識和技巧 (3) Short-time Fourier transform 的編寫 (4) Hilbert-Huang transform 的編寫 (5) 其他時頻分析的方法 (6) 查資料和做研究的方法和技巧

23 Fourier transform (FT)
Time-Domain  Frequency Domain Some things make the FT not practical: (1) Only the case where t0  t  t1 is interested. (2) Not all the signals are suitable for analyzing in the frequency domain. It is hard to analyze the signal whose instantaneous frequency varies with time.

24 Example: x(t) = cos( t) when t < 10,
x(t) = cos(2 t) when t  (FM signal)

25 Using Time-Frequency analysis
x(t) = cos( t) when t < 10, x(t) = cos(3 t) when 10  t < 20, x(t) = cos(2 t) when t  (FM signal) Left：using Gray level to represent the amplitude of X(t, f) Right：slicing along t = 15 f -axis t -axis t -axis

26 Several Time-Frequency Distribution
Short-Time Fourier Transform (STFT) with Rectangular Mask Gabor Transform avoid cross-term less clarity Wigner Distribution Function with cross-term high clarity Gabor-Wigner Transform (Proposed) avoid cross-term high clarity Hilbert-Huang Transform

27 Applications of Time-Frequency Analysis
(1) Finding Instantaneous Frequency (2) Music Signal Analysis (3) Sampling Theory (4) Modulation and Multiplexing (5) Filter Design (6) Random Process Analysis (7) Signal Decomposition (8) Electromagnetic Wave Propagation (9) Optics (10) Radar System Analysis (11) Signal Identification (12) Acoustics (13) Biomedical Engineering (14) Spread Spectrum Analysis (15) System Modeling (16) Image Processing (17) Economic Data Analysis (18) Signal Representation (19) Data Compression (20) Seismology (21) Geology

28 Conventional Sampling Theory
Nyquist Criterion New Sampling Theory (1) t can vary with time (2) Number of sampling points == Area of time frequency distribution

29 假設有一個信號，  The supporting of x(t) is t1  t  t1 + T, x(t)  0 otherwise  The supporting of X( f )  0 is f1  f  f1 + F, X( f )  0 otherwise 根據取樣定理， t  1/F , F=2B, B:頻寬 所以，取樣點數 N 的範圍是 N = T/t  TF 重要定理：一個信號所需要的取樣點數的下限，等於它時頻分佈的面績

30 Modulation and Multiplexing
spectrum of signal 1 -B1 B1 spectrum of signal 2 not overlapped B2 -B2

31 Improvement of Time-Frequency Analysis
(1) Computation Time (2) Tradeoff of the cross term problem and clarification (3) Hilbert-Huang Transform (HHT)

32 An Example of the Hilbert-Huang Transform
Envelopes

33 IMF1 IMF2 x0(t)

34 5. Music Signal Analysis 要學習的項目： (1) 使用 Fourier transform 來分析信號頻譜的正確方式
(2) 聲音信號處理的基本知識和技巧 (3) Query by humming (哼歌辨識)程式的了解 (4) 哼歌辨識程式的改良 (5) 查資料和做研究的方法和技巧

35 Using the time-frequency analysis
聲音檔： La Fa Re So Mi Do La Mi Do

36 聲音檔： time-frequency analysis

37 目標： 音樂信號搜尋 (運用音的高低和拍子) 音樂信號壓縮 目前的成果：20秒長度的哼歌，辨識成功率為 100% 但仍有不少精益求精的空間

38 6. Signal Processing for Bioinformatics
(生物資訊學) 要學習的項目： (1) 使用 FFT 來計算 convolution 和 correlation 的正確方式 (2) 生物資訊學相關的知識 (3) Sequence matching 程式的編寫 (4) 加速 sequence matching 速度的方法 (5) 查資料和做研究的方法和技巧  There are four types of nucleotide in a DNA sequence: adenine (A), guanine (G), thymine (T), cytosine (C)  Unitary Mapping bx[] = if x[] = ‘A’, bx[] =  if x[] = ‘T’, bx[] = j if x[] = ‘G’, bx[] = j if x[] = ‘C’. y = ‘AACTGAA’,  by = [1, 1, j, 1, j, 1, 1].

39  Discrete Correlation Algorithm for DNA Sequence Comparison
For two DNA sequences x and y, if where Then there are s[n] nucleotides of x[n+] that satisfies x[n+] = y[].  Example: x = ‘GTAGCTGAACTGAAC’, y = ‘AACTGAA’, . x = ‘GTAGCTGAACTGAAC’, y (shifted 7 entries rightward) = ‘AACTGAA’.

40  Example: x = ‘GTAGCTGAACTGAAC’, y = ‘AACTGAA’,
s[n] = Checking: x = ‘GTAGCTGAACTGAAC’, y = ‘AACTGAA’ (no entry match) x = ‘GTAGCTGAACTGAAC’, y = (shifted 2 entries rightward) ‘AACTGAA’ (6 entries match) x = ‘GTAGCTGAACTGAAC’, y (shifted 7 entries rightward) = ‘AACTGAA’. (7 entries match)

41  Advantage of the Discrete Correlation Algorithm:
---The complexity of the conventional sequence alignments is O(N2) ---For the discrete correlation algorithm, the complexity is reduced to O(N log2N) or O(N log2N + b2) b: the length of the matched subsequences Experiment: Local alignment for two 3000-entry DNA sequences Using conventional dynamic programming Computation time: 87 sec Using the proposed discrete correlation algorithm: Computation time: 4.13 sec.

42 7. ECG (心電圖) Signal Analysis
要學習的項目： (1) 信號處理的基本知識和技巧 (2) 聲音信號處理的基本技巧 (3) 特徵點擷取程式的編寫 (4) ECG signal analysis 程式的編寫 (5) 查資料和做研究的方法和技巧

43 7. ECG (心電圖) Signal Analysis
典型心電圖 R R T T P P Q Q S S

44 (a) The Original Signal (The First ECG Signal in 9.bmp)
(b) Find the Baseline (c) Subtracted by the Baseline

45 實際上量測到的心電圖

46 Telehealth (遠距醫療) Can we perform health examination by the ibon machine in 7-11 or at home?

47 專題研究相關規定 (1) 原則上，一週 meeting 一次，方式為老師和同學一對一討論
(提早於暑假開始，或是學期第幾週之後再開始皆可) 前八週：學習相關的基礎知識 後六週：會給一個小題目，讓同學們嚐試看看 (3) 研究題目，由第 2 頁所列的題目當中任選一個來研究 (4) 工作內容包括： 看論文，學習相關知識，編寫程式做模擬，幫忙撰寫論文投稿

48 (5) 所需基礎知識： 信號與系統，MATLAB (6) 關於專題研究的定位： a. 從大學 (學習導向)到研究所(創造導向)中間的銜接 b. 寫程式和做研究基本功的練習

49 無論是訊號處理和影像處理，都是變化多、富有彈性
鼓勵各位同學多多發揮創意 從不同角度來研究問題 無論是訊號處理和影像處理，都是變化多、富有彈性 很容易創新的領域 投影片資料下載：