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

Research Fields [A. Image Processing] (1) Image Compression (page 4) (2) Edge and Corner Detection (page 14) (3) Segmentation (page 17) (4) Pattern Recognition (Face, Character, Video) (page 24) (5) Optical Image Processing (page 29) (6) Others: Biomedical Image Processing, Banknote Reconstruction, Dehaze, Scene Classification (page 38) [B. Time-Frequency Analysis] (7) Time-Frequency Analysis (page 45) (8) Music Signal Analysis (page 62) (9) Wavelet Transform (page 66) 紅字是目前有同學在研究的領域

[C. Fast Algorithms] (10) Integer Transforms (including Walsh transforms, Number Theory) (page 68) [D. Applications of Signal Processing] (11) 3-D Accelerometer (page 74) (12) ECG Signal Analysis (page 77) [E. Other Topics] (13) Structure Similarity, Quaternion, Filter Design, …… 實驗室的規定 (page 81)

1. Image Compression Conventional JPEG method: Separate the original image into many 8*8 blocks, then using the DCT to code each blocks. DCT: discrete cosine transform PS: 感謝 2008年畢業的黃俊德同學

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

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

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

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

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

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

既不按照 88 的方格來做切割，也不完全按照物體的形狀 折衷的方法： 既不按照 88 的方格來做切割，也不完全按照物體的形狀 Triangular and Trapezoid (梯形) Block Segmentation J. J. Ding, Y. W. Huang, P. Y. Lin, S. C. Pei, H. H. Chen, and Y. H. Wang, "Two-dimensional orthogonal DCT expansion in trapezoid and triangular blocks and modified JPEG image compression," IEEE Trans. Image Processing, vol. 22, issue 9, pp. 3664-3675, Sept. 2013

(1) 如何找到物體的邊緣並切割？(努力中) (2) 如何針對不規則的區域，找到 orthogonal transform (已解決) 技術上的問題： (1) 如何找到物體的邊緣並切割？(努力中) (2) 如何針對不規則的區域，找到 orthogonal transform (已解決) (3) 如何避免讓邊緣區域的高頻成分影響到壓縮的結果 (已解決) (4) 如何用最小的資料量，對邊界的部分做紀錄 (已解決) (5) 如何用最小的資料量，對內部的部分做紀錄 (已解決) (6) 減少壓縮和解壓縮的運算時間 (努力中) (7) 減少 buffer size 的需求，讓演算法能在手機中執行 (努力中) (8) 如何在少影響人眼視覺的前提下，讓資料量減少至極限？ (努力中) J. J. Ding, P. Y. Lin, J. D. Huang, T. H. Lee, and H. H. Chen, “Morphology-based shape adaptive compression,” Lecture Notes in Computer Science, vol. 6524, pp. 168-176, Jan. 2011 J. J. Ding, H. H. Chen, and W. Y. Wei, “Adaptive Golomb code for joint geometrically distributed data and its application in image coding,” IEEE Trans. Circuits Syst. Video Technol., vol. 23, issue 4, pp. 661-670, Apr. 2013

什麼是影像壓縮技術的極限？

2. Edge and Corner Detection Why should we perform edge and corner detection? --Segmentation --Compression --Efficient for Processing

The most efficient way to trace an object in video: (1) Edges (2) Corners (3) SIFT Points (4) SURF, FAST, BRISK, ORB, FREAK….. Other Feature Points 當前 edge detection 技術 已經有很好的效果 (Ex: Canny’s algorithm) 但 corner detection 的結果，仍常受到 noise 影響

 Corner Detection by Harris’ algorithm by proposed algorithm

3. Segmentation Important for (i) compression (ii) biomedical engineering (iii) pattern recognition, object identification

2009年的成果 Conventional method: 97.87 sec New method: 1.02 sec

2015 年的成果 (These results are obtained without tuning any parameter)

Some segmentation results (These results are obtained without tuning any parameter)

Some segmentation results (These results are obtained without tuning any parameter)

原圖來自於 Berkeley segmentation database 我們的方法

我們的方法 原圖來自於 http://www.indonetwork.co.id/ud_barokah_co/1196034

4. Pattern Recognition including face recognition character recognition action recognition : 應用很廣： security, identification, computer vision …………

文字辨識： (1) 辨識所寫的文字 (2) 辨識筆跡 (辨識書寫者) 這部分的研究，和政府機關合作 文字辨識 A B 1

人臉辨識 Class 1 Class 2 Class 3

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

Machine learning methods for classification: (i) Nearest Neighbor, k Nearest Neighbors (kNN) (ii) Support Vector Machine (SVM) (iii) Neural Network (iv) Convolutional Neural Network (CNN)

5. Optical Image Processing 這部分的研究，目前正在和工研院以及 Qualcomm 合作 Depth recovery: 如何由照片由影像的模糊程度，來判斷物體的距離 並且進一步重建出清楚的影像

Model for Blurred Images i[m, n]: the original image b[m, n]: blurred image k[m, n]: some point spread function *: convolution σ[m, n]: noise A blurred image may cause from (1) defocus (和工研院合作) (2) hand-shaking (和 Qualcomm 合作)

Simplest way What is the problem? Alternative ways: (1) Wiener filter (2) Richardson-Lucy Methods (3) Fourier Optics (4) Norm-Prior Based Methods (Levin, Krishnan) (5) Others

Blurred Image Reconstructed Image Blurred Image Reconstructed Image W. D. Chang, J. J. Ding, Y. Chen, C. W. Chang, and C. C. Chang, “Edge-membership based blurred image reconstruction algorithm,” APSIPA Annual Summit and Conference, Hollywood, USA, Dec. 2012

Blurred Image

Reconstructed Image Y. Chen, J. J. Ding, W. S. Lai, Y. J. Chen, C. W. Chang, and C. C. Chang, “High quality image deblurring scheme using the pyramid hyper-Laplacian L2 norm priors algorithm,” Advances in Multimedia Information Processing, Lecture Notes in Computer Science, vol. 8294, pp. 134-145, Dec. 2013

手晃動造成的手機模糊影像還原 Blurred: Deblurred:

lens, (focal length = f) free space, (length = z1) free space, (length = z2) f = z1 = z2  Fourier Transform f  z1, z2 but z1 = z2  Fractional Fourier Transform f  z1  z2  Fractional Fourier Transform multiplied by a chirp

Light Field Camera

6. Other Applications of Image Processing (1) Biomedical Image Processing (曾經和應力所、光電所合作) (2) Banknote Reconstruction (曾經和政府機關合作) (3) 環場相機 (目前和中強光電合作) (4) Image Dehaze (影像去霧去霾，曾經和 Qualcomm 合作) (5) Scene Classification (目前和 Qualcomm 合作) (6) Motion Identification by Videos (目前和 Qualcomm 合作)

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

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

受過傷的老鼠肌肉纖維「分區」的結果 J. J. Ding, Y. H. Wang, L. L. Hu, W. L. Chao, and Y. W. Shau, “Muscle injury determination by image segmentation,” VCIP, accepted, Tainan, Nov. 2011

大腦核磁共振影像 (Brain MRI Image) (a) Brain MRI Image (b) White Matter (白質) (c) Gray Matter (灰質) (d) 腦髓液蛋白，頭蓋骨 http://mouldy.bic.mni.mcgill.ca/brainweb/

Banknote Reconstruction

Dehaze 將受到霾害或是霧的影響所照出來的照片，還原成和沒有霧的情形一樣 Scene Classification Mountain River Outdoors Ocean Images Street Indoors

7. Time-Frequency Analysis http://djj.ee.ntu.edu.tw/TFW.htm 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.

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

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  20 (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

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

Cohen’s Class Distribution where S Transform Hilbert-Huang Transform

自然界瞬時頻率會隨時間而改變的例子 音樂 語音信號 Doppler effect seismic waves Optics radar system, rectangular function, ……………………… In fact, in addition to sinusoid-like functions, the instantaneous frequencies of other functions will inevitably vary with time.

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

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

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

Fractional Fourier Transform Performing the Fourier transform a times (a can be non-integer)  Fourier Transform (FT) generalization  Fractional Fourier Transform (FRFT) ,  = a/2 When  = 0.5, the FRFT becomes the FT. When  = 0.1  performing the FT 0.2 times; When  = 0.25  performing the FT 0.5 times; When  = /6  performing the FT 1/3 times;

 Physical Meaning: Transform a Signal into the Fractional domain, which is the intermediate of the time domain and the frequency domain.

以時頻分析的觀點，傳統濾波器是垂直於 f-axis 做切割的 stop band f0 cutoff line pass band t-axis 而用 fractional Fourier transform 設計的濾波器是，是由斜的方向作切割 f-axis  stop band cutoff line 和 f-axis 在逆時針方向的夾角為  u0 pass band cutoff line

 Gabor Transform for signal + 0.3exp[j0.06(t1)3  j7t] fractional axis t-axis Advantage:  Easy to estimate the character of a signal in the fractional domain  Proposed an efficient way to find the optimal parameter 

註：時頻分析技術的研究，曾經和國家太空中心合作 (福衛六號的分析) Improvement of Time-Frequency Analysis (1) Computation Time (2) Tradeoff of the cross term problem and clarification 註：時頻分析技術的研究，曾經和國家太空中心合作 (福衛六號的分析)

衛星功率信號的時頻圖

時頻分析的應用範圍：從海底到太空 astronomy satellite over 700 km communication signal speech, music, voice vocal signal over 1000m oceanography geology ocean crust

由於硬體和輔體技術的快速提升，時頻分析，是未來信號處理的主要趨勢

8. Music Signal Analysis 目標： 音樂信號搜尋 (Query by Humming) (運用音的高低和拍子) 音樂信號壓縮 (當前 MP3 能將音樂壓縮至原信號的 1/5)

Using the time-frequency analysis 聲音檔：http://djj.ee.ntu.edu.tw/Chord.wav La Fa Re So Mi Do La Mi Do

聲音檔：http://djj.ee.ntu.edu.tw/air.mp3 time-frequency analysis

目前的成果：20秒長度的哼歌，辨識成功率為 100% 但仍有不少精益求精的空間

9. Wavelet Transform 只將頻譜分為「低頻」和「高頻」兩個部分，大幅簡化了 Fourier transform (對 2-D 的影像，則分為四個部分) g[n]  2 x1,L[n] 「低頻」部分 x[n] h[n]  2 x1,H[n] 「高頻」部分 Example: g[n] = [1, 1], h[n] = [1, -1] or

2-D 的情形 g[m]  2 x1,L[m, n] L-points m 低頻, n 低頻 along m g[n]  2 v1,L[m, n] along n h[m]  2 x1,H1[m, n] M ×N m 高頻, n 低頻 x[m, n] along m L-points x1,H2[m, n] g[m]  2 h[n]  2 v1,H[m, n] along m m 低頻, n 高頻 along n  2 x1,H3[m, n] h[m] n m along m m 高頻, n 高頻

10. Integer Transform DFT, DCT 很常用，但是，他們都是無理數….. Discrete Fourier transform (DFT): Discrete cosine transform (DCT): RGB to YCbCr Transform 如果它們的 entries 都是整數 (或是 C/2b) 該有多好

Integer Transform: The discrete linear operation whose entries are summations of 2k. , ak = 0 or 1 or , C is an integer.

Problem: Most of the discrete transforms are non-integer ones. DFT, DCT, Karhunen-Loeve transform, RGB to YCbCr color transform --- To implement them exactly, we should use floating-point processor --- To implement them by fixed-point processor, we should approximate it by an integer transform. However, after approximation, the reversibility property is always lost.

Walsh transform (applied by CDMA)

Integer RGB to YCbCr Transform This is used in JPEG 2000.

[Integer Transform Conversion]: Converting all the non-integer transform into an integer transform that achieve the following 6 Goals: A, A-1: original non-integer transform pair, B, B̃: integer transform pair (Goal 1) Integerization , , bk and b̃k are integers. (Goal 2) Reversibility . (Goal 3) Bit Constraint The denominator 2k should not be too large. (Goal 4) Accuracy B  A, B̃  A-1 (or B  A, B̃  -1A-1) (Goal 5): Less Complexity (Goal 6) Easy to Design

11. 3-D Accelerometer (三軸加速器) 許多儀器(甚至包括智慧型手機) 都有配置三軸加速器 z-axis y-axis x-axis 如何根據 x, y, z 三個軸的加速度的變化，來判斷姿勢和動作

z-axis y: 0 z: -9.8 y-axis tilted by θ z-axis y: -9.8sin θ z: -9.8cos θ y-axis

三軸加速器應用： 動作辨別 (遊戲機) 運動 (訓練，計步器) 醫療復健，如 Parkinson 患者照顧 (目前這部分的研究，和台大公衛學院合作)

12. ECG (心電圖) Signal Analysis 和台大醫院合作 典型心電圖 R R T T P P Q Q S S

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

實際上量測到的心電圖

Q1: Telehealth (遠距醫療) Can we perform health examination by the ibon machine in 7-11 or at home? Q2: Wrist-type Photoplethysmographic (PPG) Signal Analysis (脈膊信號分析)

實驗室研究的規定 (1) 原則上，一週 meeting 一次，方式為老師和同學一對一討論 例外： (a) 為了方便準備期中和期末考，修二門課以上可以選三週不必 meeting， 修一門課每個學期可以選二週不必 meeting (b) 碩二下準備碩士論文口試前的二至四個月，將一週 meeting 二次 (c) 口試後只需再 meeting 一至二週 (d) 農曆新年休息二週 (2) 碩一升碩二的暑假，要參加國內的研討會 CVGIP Take it easy，雖然是學術研討會，就當作是旅行就可以了，費用由老師 補助 (3) 希望每位同學，都有自己創新的新點子 創新，是研究所教育和大學教育之間最大的不同

(4) 碩一上學期和下學期三月以前，同學們可以自由選擇有興趣的題目來研 究，每三個月可以換一次題目 到了碩一下學期三月，則要從我所列出的十幾個研究領域，選擇一個領域 (自由選擇)，來當成將來碩士論文的研究主題 (5) 希望大家至少都能曾經幫忙寫過論文 (6) 每週 meeting 所規定的工作，儘可能達成 但如果已經盡了力仍然難以達成目標，我是可以接受的 (7) 若有事情 meeting 的時間可以自由調整，但不可缺 meeting

(8) 每個學期，將請同學做一次口頭報告。(內容可以是自己的研究，也可以 是任何一個有意思、且你願意和同學們分享的新知) 一方面，訓練演講和報告的能力 一方面，希望同學們除了自己的研究之外，也可以藉此了解他人的研究， 以及各種學術上的新知 (9) 每學期會有二至三次的導生會，歡迎學生多多參加。 (10) 這一屆的同學，第一次 meeting 的時間在 2018年8月初。

研究所的生活，和大學比起來，更有彈性 ，但是也離近入社會更近。 希望各位同學能妥善運用時間，好好充實自已， 並且多訓練自己「創造發明」以及「思考」的能力

歡迎同學們多多展現天馬行空的創意和想像力 鼓勵各位同學多多發揮創意 從不同角度來研究問題 無論是訊號處理和影像處理，都是變化多、富有彈性 很容易創新的領域 歡迎同學們多多展現天馬行空的創意和想像力