# 課程資訊
作業
* 影像嵌入與合成
* 資料視覺化分析
* 音訊分析與處理
* 人臉重建與辨識
* 多媒體創意發想

大專校院資訊應用服務創新競賽

# Overview
多媒體的定義很廣泛，包括
* 文字
* 圖
* 聲音
* 影片
* 動畫

# 數位媒體的儲存跟壓縮
## Analog data v.s. Digital data
* Analog data (類比)
連續值的資料，通常沒有data loss，故品質較高

* Digital data (數位)
離散值的資料，有一定程度的data loss，但大小較小且較為可靠

要將Analog data轉換成Digital data，可以根據Sampling以及Quantization來達成
### Sampling(取樣)
針對原始資料，取出某些點以代表原資料
* sampling rate(取樣率) 越高，越能貼近原始資料
* Undersampling : 取樣率跟不上原始資料的變化
* Aliasing: 由於undersampling，導致無法重建出原始資料
* 為了避免Aliasing的現象發生，sampling rate至少要是原始資料的兩倍 (根據Nyquist Theorem)

### Quantization(量化)
將一定範圍的連續值離散化成整數，在一定範圍內的數字都會被量化成一個整數


ex:
fmin=0(資料的最小值)
fmax=800(資料的最大值)
L=8(想要將資料切成8段)
f=80(還未量化的值)

則可以計算出
Q=100 (每個區間長100)
Qi(f)= 0 (代表量化後的index為0)
Q(f)=50 (代表量化後的值為50)

bit depth(量化段數儲存所需的bit): 3 (2的三次方等於8)

Quantization error: 30(原始值跟量化後之值的差距，加絕對值)

## Compression
* Compression Rate: 壓縮後資料大小/壓縮前資料大小

壓縮的方法可以分成兩類
* lossless compression: 無損壓縮，可以復原成壓縮前的樣子
* Run-Length encoding
* Entropy encoding
* Arithmetic encoding
* lossy compression: 有損壓縮，無法復原成壓縮前的樣子(ex: jpg)
* Transform encoding
### Run-Length encoding (RLE)
1. 將二維的圖展開成一維
2. 用pair的方式記錄某個數字連續出現了幾次

ex:

注意: (255,1000) 應該被拆成 (255,255),(255,255),(255,255),(255,235)， 因為一個數字最多只能有8 bit來存

注意: 壓縮後不一定會變得比較小

### Entropy(熵) Encoding
Shannon’s Equation:

* pi代表該像素顏色出現的頻率 (標準化後)，所有顏色的pi相加總合為1
ex:

算出來的值是"平均要花幾個bit來儲存每個顏色"的理論最佳解

### Shannon-Fano algorithm:
1. 針對每個顏色跟出現頻率建表
2. 對出現頻率排序
3. 每次都嘗試將當前table分成frequency盡量相同的兩半；table 左半部分配0，右半部分配1
4. 不斷遞迴進行第三步，直到當前table大小為1；此時分配的bit便是編碼

ex:
* 將table分成[block, yellow, orange, green], [white, blue, red, green]，兩邊的frequency 相差0，已是最小
* 遞迴進行左邊的table，分成[block], [yellow, orange, green]，兩邊的frequency 相差72，已是最小
* 此時已可得出Block的編碼為00(被分配在了兩次左邊)

### Transform Encoding
在有損壓縮的過程中，通常會用到以下兩種常見的方法
* Discrete Cosine Transform (DCT)
* Discrete Fourier Transform (DFT)

但DCT或DFT操作本身並不會丟失資料，是有損壓縮中的其他步驟才會丟失資料

# Digital Image Representation
## Bitmap
* 使用像素來儲存圖片

以下三張照片分別顯示
* 原圖
* Sampling rate過低
* Quantization過低

名詞介紹
Pixel dimensions: 圖片包含的總像素量 ( w*h )
Resolution: 每inch的像素量 ( r )，200ppi代表每平方itch中有200*200個像素
Image size: 物理上的圖片大小。a = w/r , b = h/r
Frequency: 顏色值變動的程度；Frequency越高，顏色變化越平滑

### 1D Discrete Cosine Transform
目的: 將一維的原始數據序列轉換為「頻域表示係數」(一組餘弦函數的權重)

基本公式:
* F( u ): 頻域表示係數 (答案)
* f( r ): 原始數據序列 (輸入)
* M: 一維的像素數量
* u: 頻率，決定要使用哪個Basis function來轉換原始數據序列
* r: 位置，決定要使用Basis function上的哪個位置

其中，為了簡化計算，將公式中的這部分稱為**Basis function**，只會隨著u不同而改變

ex:
**給定原始數據序列**:
[f(0), f(1), f(2), f(3), f(4), f(5), f(6), f(7)] =
[0, 0, 0, 153, 255, 255, 220, 220]

該原始數據序列代表的實際一維圖像如下

從**原始數據序列中可得知M=8**

這時候先計算F(0)，也就是u=0的情況
**u=0時的Basis function**如下圖所示
上圖顯示**根據不同r，Basis function轉換出來的餘弦數值** (橫軸為r，可能值為0-7； 縱軸為轉換出來的餘弦數值，可能值為0-1)

接著根據公式，因為u=0，故此時的**C(u)= √2 / 2**

最後，公式該有的都有了，便可以根據公式**計算出F(0)約等於389.97了**
(可以看到在這個例子中，Basis function轉換出來的餘弦數值，不管r如何變動都是1，故第二行算式中便可以將cos那項直接替換成1)

計算F(1)、F(2)...的方法以此類推
最終答案為
[F(0), F(1), F(2), F(3), F(4), F(5), F(6), F(7)] =
[389.97, -280.13, -93.54, 83.38 , 54.09, -20.51, -19.80, -16.34]

觀察可以發現，最終計算的結果「F(u), 0 <= u < 8」，其實可以想成**將原圖暴露在不同頻率(u)下的敏感程度**；也就是說，F(0)代表的是: 在包含8個像素的一維圖中，頻率參數(u)為0的情況下的敏感程度

其中，將F(0)稱為DC component，F(1)~F(7)稱為AC component

### 2D Discrete Cosine Transform

### Compression using DCT
DCT轉換的其中一個目的便是用於壓縮

1. 將原圖經由DCT轉換成

2. 透過Quantization Table 量化這些值，此時會發現多出了許多0
3. 使用Zigzag Scan將二維

期中考題: 將s Zero Run-Length Encoding 重建回原始圖像

### Bayer Color Filter
為了降低感知器成本，每個像素都會加上一個特定顏色的Bayer Color Filter，只儲存特定顏色的強度資訊，最後再藉由**Demosaicing**的步驟還原顏色

* 因為人眼對綠色較敏感，故綠色感知器數量占了整體的一半

* Nearest neighbor Algorithm 是實作Demosaicing的其中一種方法
* 取某個像素點周圍一圈"目標顏色感知器"的平均數值作為該點"目標顏色"的數值

ex:
1. 給定原始圖像、Bayer Color Filter，欲估算出位置A的顏色 (使用Nearest neighbor Algorithm)
* 計算G chennel: 位置A本身的感知器是G，而真實顏色是紅色，故可確定位置A的G chennel為0 ->A(?, 0, ?)
* 計算R chennel:位置A周圍有兩個R 感知器，其感知出來的值分別為255、255，固可猜測位置A的R chennel為$\frac{255+255}{2}$ ->A(255, 0, ?)
* 計算B chennel:位置A周圍有兩個B 感知器，其感知出來的值分別為255、255，固可猜測位置A的B chennel為$\frac{255+255}{2}$ ->A(255, 0, 255)

當採樣率不足時，這種方法可能會導致Aliasing的問題(計算出來的顏色跟原始顏色不一致)

### Anti-aliasing
一種用來解決斜線Aliasing的演算法

用某像素黑跟白的占比來計算該格像素的灰階值，便可以使直線看起來更直

## Color
顏色的三大特徵:
1. Hue: 色調
2. Saturation: 飽和度 (顏色純度)
3. Luminance: 亮度 (明度)

### RGB color model
C = rR + gG + bB
* R、G、B是根據這三種顏色的波長決定的常數
* r、g、b代表混和的比例
* RGB圖片轉灰階的時候，用以下的參數轉換
L = 0.30R + 0.59G + 0.11B
* 優點: 工程設計容易
* 缺點: 因為只能顯示個顏色的正值，故無法精確顯示出真實的顏色

### CMY(Subtractive Color Mixing) color model
* 用"減法"來實現顏色的混和，所以 (0,0,0)代表的是白色
* RGB與CMY之間的轉換 (R、G、B皆以標準化至0-1間):
* C = 1 – R (青色)
* M = 1-G (洋紅色)
* Y = 1 – B (黃色)

CMY 三種顏色混和後結果理論上是黑色，但實際上會是深棕色的，為了解決這個問題，引入了CMYK model:
1. 設k=min(C,M,Y)
2. 新的CMY值如下
* C_new = C – K
* M_new = M - k
* Y_new = Y – K

* CMYK model常見於印刷方面

### HSV color model
使用**色調、飽和度、亮度**來表示顏色
1. 色調(Hue): 從0度開始，代表紅色，逆時針旋轉增加相對應的值，最大轉360度回到紅色
2. 飽和度(Saturation): 距離六邊形中心的距離(水平)，值落在0-1之間，值為1時為純色
3. 明度 (Value): 值落在0-1之間(垂直)，值為0時為黑色

### YIQ color model
Y、I、Q的值可以經由RGB轉換得到
* 長用於**商業電視廣播**與**影像壓縮**

### CIE color model
* 可表示所有可見色彩
* 在CIE model中，兩個點之間的距離**並不跟**兩種顏色之間的感知差異呈正比


## vctor graphic
另一種儲存圖片的方法，相較於bitmap，各有優缺點跟適用範圍

* Vector graph 由數學公式所描述的幾何圖形(ex: 點、線、曲線和多邊形等)跟顏色組成
* 相較於 bitmap，vctor graphic遇到的aliasing problems較輕微
* Vector graph適用於純色和具有清晰邊緣的圖片

## Parametric Curve (參數曲線)
* 需要n+1 個 control points 來將一個n次多項式轉成Parametric repersentation

Parametric repersentation:
* P(t): 生成的曲線
* x(t)y(t): 曲線上的某點座標
* 𝑎𝑥 𝑎𝑦 𝑏𝑥 𝑏𝑦 𝑐𝑥 𝑐𝑦 𝑑𝑥 𝑑𝑦: 需要確定的係數(control points)

## Bézier curves
* Bézier curves 是一種 Parametric Curve
* Bézier curves 由任意數量的control points 描述而成

計算:
P(t) = [x(t) y(t)] = T * M * G
* P(t): Bézier curves，由x(t)、y(t)組成 (所求)
* T: 次方係數
* M: basis matrix: 固定係數
* G: geometry matrix，由control points組成 (題目給定)

性質觀察(舉一個由四個control points(p0~p3)描述而成的Bézier curves為例):

* Bézier curves的起點跟終點分別是 p0 跟 p3
* 線段p0p1、p2p3是Bézier curves的切線
* p0、p1、p2、p3 對應於t的值分別為0、1/3、2/3、1

Blending Function: general Bézier curves
將P(t)寫成另一種形式後
* 觀察可發現其實係數就是巴斯卡三角形
* 故Bézier curves的general form 可寫成

### de Casteljau algorithm
該演算法方便的手繪Bézier curves
* 根據給定的那四個control points，計算出中間點$p_{01}$、$p_{12}$、$p_{23}$
* 根據$p_{01}$、$p_{12}$計算出$p_{012}$
* 根據$p_{12}$、$p_{23}$計算出$p_{123}$
* 根據$p_{012}$、$p_{123}$計算出$p_{0123}$，此時該點保證落在Bézier curves上

* 接著遞迴取四個點(靠曲線內側)找出其他在Bézier curves上的點

# Digital Image Processing
## Digital image type
1. .bmp (Windows bitmap)
* 支援1~24 bit 的color depth(可選2^24種顏色)
* 若使用alpha channel(透明度)，則color depth為32
2. .gif (Graphics Interchange Format)
* 支援256種顏色，支援透明度，但不能使用alpha channel
* 支援簡單動畫
* 使用 LZW 壓縮
* 支援漸進式下載 (逐漸載入更高清的版本)

3. .jpg (Joint Photographic Experts Group)
* 適用於連續色調的圖片
* 有損壓縮

4. .png (Portable Network Graphics)
* 支援1~64 bit 的color depth，並支援alpha channel
* 無損壓縮

補充: palette(調色板):
調色板是一個包含了圖像中可能使用的不同顏色選項的表格，圖像中的每個像素通過指向調色板中的特定顏色來表示其顏色。針對那些使用顏色不多的圖片，可以有效節省存儲空間

## Color Quantization
使用**indexed color**的技巧，用 palette(調色板)管理圖片的color以節省空間

目標: 將bit depth 為 n 的原始圖像轉成 bit depth 為 B 的新圖片

1. 確定原始圖像中實際出現的那些顏色
2. **選擇2^b種顏色**作為新圖片用到的顏色
3. 建表儲存index與真實顏色的對應表，並將不存在於新圖中的顏色對應至最接近的顏色(最小平方法)

至於要怎麼選2^b種顏色，以下是幾種可能的演算法
### Popularity algorithm
選擇出現頻率最多的2^n種顏色作為調色板

### Uniform partitioning Algorithm (均勻分割)
1. 將原圖中出現的所有顏色放置於三維空間中，並用一個最小的正方體包住所有點

2. 分割這個正方體的邊界，直到分成2^b種
ex:
3. 在同一小長方體的點會被同化成同一種顏色(可以取小長方體的中心or 使用Popularity algorithm)

缺點: 若有許多顏色都在同一個長方體中，會都變成同一種顏色，導致漸層的效果消失

### Median-cut algorithm (中位數分割)
優化Uniform partitioning Algorithm，解決上述演算法的缺點

1. 在分割正方體邊界時，先沿著較長邊將正方體分成兩個內部點數相同的長方體
2. 遞迴的用上述方法分割小長方體，如此一來便能保證每個長方體中的點數相同


### Octree Algorithm
建樹，
* 每個節點有8個子節點

* 範例的顏色可藉由走訪圖中的節點順序來唯一決定 (每個葉節點便代表一種顏色)

演算法步驟:
1. 針對遇到的前2^b種顏色，建出其從root 到leaf的路徑
2. 當第17種顏色出現時，找最接近的顏色並與其取平均，成為新的顏色

所以這棵樹始終只有2^n個葉節點，並僅包含需要的部分

### Dithering(抖動)
在顏色總量不變的情況下，可以藉由這種方式創建假的新顏色


應用: Noise dithering
1. 針對每個像素，先隨機產生一個在0-255間的數字
2. 若該像素值大於該隨機數，則該像素值設成255；若該像素值小於該隨機數，則該像素值設成0

應用: Average dithering
1. 先計算出所有像素的平均值
2. 若該像素值大於平均值，則該像素值設成255；若該像素值小於平均值，則該像素值設成0

應用: Pattern Dithering
1. 將原圖片分成許多Block，每個block套用一個threshold matrix
2. 若某像素值大於threshold matrix對應位置上的值，則該像素值設成255；若某像素值小於threshold matrix對應位置上的值，則該像素值設成0

* 藉由每一個小區塊中黑與白的比例，可以在視覺上造成灰階的效果

應用: Error Diffusion Dithering(Floyd-Steinberg algorithm)
* 必考

先定義mask，例如

設定變數e
若p<128 則e=p
否則 e=p-255
(效果: 當某像素為深色時，鄰居會被調整成淺色，反之亦然)

將某個像素的結果擴散至其鄰居上(根據mask的權重)，像素的遍歷順序是從左上角起的zip zap

針對每個像素都做一次這種操作

## Image transfromation
指的是改變圖片像素顏色或灰階值的過程

### Gamma Transform

* 當gamma>1 圖片變暗
* 當gamma<1 圖片變亮

### Convolution(捲積運算)

經過捲積運算後，圖片會少一圈，為了解決這個問題，可以事先在原圖中補上一圈0或一圈鄰居值

應用: Gaussian blur
目的: 模糊
捲稽核:

應用: edge-detection filter
目的: 邊緣檢測
捲稽核:
* filter後，負值要改成0，正值改成255

應用: Unsharp mask
目的: 銳化
捲稽核:

## Resampling
改變圖片像素總數的過程
* Replication: 單純將1*1的像素放大成2*2的
* row-column deletion: 單純將2*2的像素縮小成1*1的

---期中考線---
# 其他壓縮法
## LZW compression
1. 將圖片中出現的所有顏色建表
2. 從第一格開始sliding window(初始化i=j=1, 1-indexed)，j不斷+1，直到i~j這個區域不在表中
3. 將不在表中的i\~j這個區域寫進表中(table[7]=yy)，將i~j-1代表區域的index寫進答案中，接著i=j=原本的j(本例j=2)，繼續進行第二跟第三步

## Huffman encoding
概念:
* 出現頻率低的顏色會被賦予bit長度更多的編號
* 任兩個編碼結果的前綴一定不一樣

1. 先統計出圖片中所有出現的顏色各自的出現頻率
2. 將這些顏色作為leaf，出現頻率作為node value
3. 每次都挑出node value最小的兩個點，將其連接起來創造新的節點
* ex: 第一輪中，將70跟50連接起來，創造120的節點
4. 不斷重複第三步，直到做出根節點為止
5. 對於每個顏色的編碼，從根節點出發，往左走編號為0，往右走編號為1，走到leaf即為該顏色的編號


## JPEG 壓縮全步驟

# Audio Representation
## 常見名詞介紹
Phase angle(相位角): t=0 時的角度

相位差:

Angular Frequency(角頻率): ω = 2πf
* sin(ω)可用於表示一個波的頻率
* ex: sin(2π) 代表頻率為1的波

Amplitude(振幅):

Decibels(分貝):
* Decibels-sound-pressure-level (dB_SPL): 聲壓級數
* Decibels-sound-intensity-level (dB_SIL): 聲音強度級數

## Audio Dithering
可以讓噪音跟原聲分離

## Noise Shaping
目的: 將噪音的部分轉移至頻率較高的區域，在當前採樣率下，便會因為頻率過高而被丟失；同時不會變動到原本想要保留的聲音

* 定義F_in代表N個未經量化的採樣點
* 定義F_out代表N個量化後的採樣點
* 計算:
* F\_in$_{i}$ = F_in$_{i}$ + D$_{i}$ + cE$_{i-1}$
* E$_{i}$ = F_in$_{i}$ − F_out$_{i}$

## μ-law Function
* 一種 non-linear quantization 的方法
* 原因:
* 震幅越大，quantization error 的效果越不明確
* 若能為低振福的部分做更細的採樣，便能提升品質
* 
* 舉例來說，original value (震幅) 為 6-11 (很小)時，一般的壓縮方法誤差為100%，但non-linear quantization 卻能使誤差降到 26%

公式:

ex:

反函式的公式，可以逆向操作

加分:
類似μ-law Function 的圖片 gamma transform

## 音頻分析
共有三種分析方法

### Time domain
* x 軸: 時間
* y 軸: 震幅

### frequency analysis
* x 軸: 頻率
* y 軸: 當前頻率下的強度 (震幅)

### Spectral view
* x 軸: 時間
* y 軸: 頻率
* 顏色: 當前時間頻率下的強度 (震幅)

## Fourier Series
目的是將複雜的波轉成 "infinite sum of sin and cos function"

* a0: DC component，代表震幅的平均值
* an:

## Discrete Fourier Transform (DFT)
跟之前學過的DCT 不同的是，多了 sin 這一項

計算:
* 將 {8, 4, 8, 0} 轉換成 {5, -i, 3, i}

## Inverse Discrete Fourier Transform

## 計算意義

## FFT
window 大小會在?跟?兩者之間取捨

## Frequency Analysis 的應用
1. 語音識別
2. 語音模仿
3. 音效模擬

* 若一個音的頻率是另一個音的2^n倍，則聽起來只有高低八度(octave)的差別
* 又鋼琴中一個八度間有 12 階，故每一階的平均頻率差值約為 1.059463

# Digital Audio Processing
* 常見音樂檔名
* .mp3
* .ogg: 優點是開放性、高音質、壓縮率高

* .wma/ .asf: 過去年代流行的格式

看過那些常見音樂黨名

## Dynamics Processing
* dynamic range: 指的是音檔中"最大"與"最小"聲音之的差距 (也就是動到震幅)

### limiting (clipping)
* 將震幅範圍限制在一定範圍間
* 分成
* hard limiting: 超過範圍的部分會被直接修改成範圍極值
* soft limiting: 能更平滑的將音檔震幅轉換至範圍之內


## Normalization
* 能將聲音平均的放大，通常搭配壓縮使用，以使震幅較小的部分也能一同放大

## Compression and Expansion
* 這邊的 Compression 指的是讓 dynamic range 變小的轉換過程； Expansion 則相反
* Downward: 指的是向下調整部分區域震幅的過程
* Upward: 指的是向上調整部分區域震幅的過程


## Digital Audio Filter
* 相當於應用於音訊處理的捲積運算，目的為
* 提取特徵
### FIR

### IIR Filter
利用遞迴的方式

### 不同 filter 介紹
* 各種不同的 h(n) 達成的效果 (FIR 應用，在 frequency domain 進行)

* Comb filter: 將過去的 output 加到當前的 output 中，以製造回聲效果 (IIR 應用)
* one-fold echo: 單回聲版本
* multiple-fold echo: 多回聲版本

* Shelving filters: **增強或減弱**音檔的**高頻或低頻**部分
* 應用: Equalization(EQ, 均衡化): 增強或減弱特定頻率的過程
* 其中，特定頻率稱為band

* Peaking filter: 比更平滑的 filter

### convolution theorem
在 time domain 做 convolution 相當於在 frequency domain 做相乘

* x(n): 原始資料
* y(n): x(n) 經過 filter 後的結果

### FIR Filter Design
* 儘管根據 convolution theorem， H(n) 可以被轉成 h(n)，但實務上，漂亮的 H(n) 可能會變成很醜的 h(n)
* 可以使用 windowing function，擷取轉換後的 h(n) 的一小部分來做捲積
* 缺點: 經過 windowing function擷取後的 h(n)在轉換後，再轉回 H(n) 時，沒辦法完美還原

## Pitch Shifting
* Harmonics Components: 樂器產生出來的某個音，其實是由一系列不同頻率組成，並分為
* fundamental frequency: 基頻
* harmonics: 協波

* 由於一個八度有12個音階，故調整音高的方法非常直觀

### Simple Idea
1. 將音樂長度擴展為原本的兩倍 (2 稱為 scaling factor)
2. 將頻率變成 scaling factor 即可


### Phase Vocoder

## MPEG Compression
### 心理聲學
* 1000 Hz ~ 5000 Hz 強度不高便能聽到，反之其他頻率則需要更強的強度才能被聽見
* 低頻中頻率的變化較為敏感
* 10 Hz ~ 15 Hz 聽起來的變化較 10000 Hz ~ 10005 Hz 多
* 低頻的 critical band(頻率區段) 較高頻窄
* 若某個頻率的聲音強度非常高，則鄰近的頻率強度必須要更高才能被聽見

### MPEG 壓縮步驟

1. 將 audio file 切成需多 frame，針對每個 frame 執行以下 2~7 步

# Digital Video
## 常見觀念
* Raster scanning:
* Interlaced scanning
* progressive scanning
## aspect ratio
目的是將原圖 resize 成較小的圖片

* 計算原圖的能量圖，當某個像素跟鄰居差異大時，其能量較高
* Crop: 用 sliding window 切出能量總和最大的畫面
* Column: 刪除原圖中的某些欄，保留能量最大的那些欄

### seam carving
概念: 透過每次移除畫面上的縫線 (紅色部分)，以降低原圖中的長寬

定義縫線:
* 相鄰的縫線 pixel 位移不能超過 1

* 找到縫線的演算法
* 使用動態規劃找到一條 energy 最小的縫線，並將其從圖片中移除