XIV. Orthogonal Transform and Multiplexing

Presentation on theme: "XIV. Orthogonal Transform and Multiplexing"— Presentation transcript:

1 XIV. Orthogonal Transform and Multiplexing
 14-A Orthogonal and Dual Orthogonal Any M  N discrete linear transform can be expressed as the matrix form: Y = A X inner product

2 Orthogonal: when k  h orthogonal transforms 的例子：  discrete Fourier transform  discrete cosine, sine, Hartley transforms  Walsh Transform, Haar Transform  discrete Legendre transform discrete orthogonal polynomial transforms Hahn, Meixner, Krawtchouk, Charlier

3 為什麼在信號處理上，我們經常用 orthogonal transform?

4 e1 and e2 are orthogonal v = (2,2) e2 = (0,1) e1 = (1,0) e3 and e4 are not orthogonal v = (2,2) e4 = (0,1)

5  If partial terms are used for reconstruction
for orthogonal case, perfect reconstruction: partial reconstruction: K < N reconstruction error of partial reconstruction 由於 一定是正的，可以保證 K 越大, reconstruction error 越小

6 For non-orthogonal case,
perfect reconstruction: partial reconstruction: B = A−1 K < N reconstruction error of partial reconstruction 由於 不一定是正的， 無法保證 K 越大, reconstruction error 越小

7  14-B Frequency and Time Division Multiplexing
傳統 Digital Modulation and Multiplexing：使用 Fourier transform  Frequency-Division Multiplexing (FDM) Xn = 0 or 1 Xn can also be set to be −1 or 1 When (1) t  [0, T] (2) fn = n/T it becomes the orthogonal frequency-division multiplexing (OFDM).

8 Furthermore, if the time-axis is also sampled
t ∈ [0,T] sampling for t-axis t = mT/N, m = 0, 1, 2, ….., N−1 then the OFDM is equivalent to the transform matrix of the inverse discrete Fourier transform (IDFT), which is one of the discrete orthogonal transform. Modulation:

9 Modulation: Demodulation: Example: N = 8 Xn = [1, 0, 1, 1, 0, 0, 1, 1] (n = 0 ~ 7)

10  Time-Division Multiplexing (TDM)
(also a discrete orthogonal transform)

11 思考： 既然 time-division multiplexing 那麼簡單 那為什麼要使用 frequency-division multiplexing 和 orthogonal frequency-division multiplexing (OFDM)?

12  14-C Code Division Multiple Access (CDMA)
除了 frequency-division multiplexing 和 time-division multiplexing，是否還有其他 multiplexing 的方式？ 使用其他的 orthogonal transforms 即 code division multiple access (CDMA) CDMA is an important topic in spread spectrum communication 參考資料 [1] M. A. Abu-Rgheff, Introduction to CDMA Wireless Communications, Academic, London, 2007 [2] 邱國書, 陳立民譯, “CDMA 展頻通訊原理”, 五南, 台北, 2002.

13 CDMA 最常使用的 orthogonal transform 為 Walsh transform
channel 1 channel 2 channel 3 channel 4 channel 5 channel 6 channel 7 channel 8 channel 1

14 當有兩組人在同一個房間裡交談 (A 和B交談)， (C 和D交談) ，
如何才能夠彼此不互相干擾？ (1) Different Time (2) Different Tone (3) Different Language

15 CDMA 分為： (1) Orthogonal Type (2) Pseudorandom Sequence Type Orthogonal Type 的例子： 兩組資料 [1, 0, 1] [1, 1, 0] (1) 將 0 變為 − [1, −1, 1] [1, 1, −1] (2) 1, −1, 1 modulated by [1, 1, 1, 1, 1, 1, 1, 1] (channel 1)  [1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1] 1, 1, −1 modulated by [1, 1, 1, 1, -1, -1, -1, -1] (channel 2)  [1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 1, 1, 1] (3) 相合 [2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, -2, -2, -2, -2, 0, 0, 0, 0, 2, 2, 2, 2]

16 demodulation [2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, -2, -2, -2, -2, 0, 0, 0, 0, 2, 2, 2, 2] [1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1,1] [1, 1, 1, 1, 1, 1, 1, 1] 內積 = 8

17 注意： (1) 使用 N-point Walsh transform 時，總共可以有N 個 channels (2) 除了 Walsh transform 以外，其他的 orthogonal transform 也可以使用 (3) 使用 Walsh transform 的好處

18  Orthogonal Transform 共通的問題: 需要同步 synchronization
但是某些 basis, 就算不同步也近似 orthogonal <R1[n], R1[n]> = 8, <R1[n], Rk[n]> = 0 if k  1 <R1[n], Rk[n1]> = 2 or 0 if k  1. 這裡的shift為circular shift

19 Pseudorandom Sequence Type
不為 orthogonal，capacity 較少 但是不需要同步 (asynchronous) Pseudorandom Sequence 之間的 correlation b1p(t+ 1) + b2p(t + 2) recovered: (若 C(0) = 1, C(2  1)  0) 1, 2 不必一致 C() -axis

20 CDMA 的優點： (1) 運算量相對於 frequency division multiplexing 減少很多 (2) 可以減少 noise 及 interference的影響 (3) 可以應用在保密和安全傳輸上 (4) 就算只接收部分的信號，也有可能把原來的信號 recover 回來 (5) 相鄰的區域的干擾問題可以減少

21 相鄰的區域，使用差距最大的「語言」，則干擾最少
B 區 A 區 假設 A 區使用的 orthogonal basis 為 k[n], k = 0, 1, 2, …, N−1 B 區使用的 orthogonal basis 為 h[n], h = 0, 1, 2, …, N−1 設法使 為最小 k = 0, 1, 2, …, N−1, h = 0, 1, 2, …, N−1

22 附錄十五 常用的影像修飾方法 (1) Lightening and Darkening Input YCbCr Yo = f(Y)
附錄十五 常用的影像修飾方法 (1) Lightening and Darkening Input YCbCr Yo = f(Y) Output RGB to YCbCr YCbCr to RGB Cb unchanged Cr unchanged Example:  = 0.5  < 1: lightening  = 2  > 1: darening

23 附錄十五 常用的影像修飾方法 original image lighten darken original image lighten
附錄十五 常用的影像修飾方法 original image lighten darken original image lighten darken

24 附錄十五 常用的影像修飾方法 (2) Morphology (i) erosion

25 附錄十五 常用的影像修飾方法 (2) Morphology (2-1) Erosion (去除區域外圍)
附錄十五 常用的影像修飾方法 (2) Morphology (2-1) Erosion (去除區域外圍) Erosion for a Non-binary Image

26 附錄十五 常用的影像修飾方法 (2-2) Dilation (擴大區域) Dilation for a Non-binary Image

27 附錄十五 常用的影像修飾方法 (2-3) Closing (Hole Filling)
附錄十五 常用的影像修飾方法 (2-3) Closing (Hole Filling) closing = dilation k times + erosion k times input dilation 3 times then erosion 3 times

28 附錄十五 常用的影像修飾方法 (2-4) Opening
附錄十五 常用的影像修飾方法 (2-4) Opening opening = erosion k times + dilation k times input erosion 3 times then dilation 3 times

29 附錄十五 常用的影像修飾方法 (3) Edge enhancement Original image
附錄十五 常用的影像修飾方法 (3) Edge enhancement Original image With edge enhancement

30 附錄十五 常用的影像修飾方法 (4) Dehaze (除霧)
附錄十五 常用的影像修飾方法 (4) Dehaze (除霧) He, Kaiming, Jian Sun, and Xiaoou Tang. "Single image haze removal using dark channel prior." IEEE Trans. Pattern Anal. Mach. Intell., vol. 33,  pp , 2011.

31 附錄十五 常用的影像修飾方法 Haze Model J(x): scene, I(x): observed image
附錄十五 常用的影像修飾方法 Haze Model J(x): scene, I(x): observed image t(x): transmission, A: intensity for the whole-haze case A(1- t(x)): airlight 定義 dark channel Jdark(x) (x) : some patch (a small region) Dark channel 為一個影像在一個小範圍區域當中，RGB 的最小值 一個正常影像的 dark channel 大多近於 0 一個受 haze 影響的影像，dark channel 常常不為 0

32 附錄十五 常用的影像修飾方法 Dehaze 的方法與流程 find the transmission t(x)
附錄十五 常用的影像修飾方法 Dehaze 的方法與流程 find the transmission t(x) A: the 95% largest intensity of I(x) recover the original image He, Kaiming, Jian Sun, and Xiaoou Tang. "Single image haze removal using dark channel prior." IEEE Trans. Pattern Anal. Mach. Intell., vol. 33,  pp , 2011.

33 期末的勉勵  人生難免會有挫折，最重要的是，我們面對挫折的態度是什麼  長遠的願景要美麗，短期的目標要務實

34 祝各位同學暑假愉快！ 各位同學在研究上或工作上，有任何和 digital signal processing 或 time frequency analysis 方面的問題，歡迎找我來一起討論。