走樣與反走樣（Aliasing/Anti-Aliasing）：Basics

時域、頻域、傅里葉變換（Time Domain, Frequency Domain, Fourier Transform）

信號有兩種表示方法，一種是表示成時間的函數，另一種是表示成頻率的函數。這兩種表示方法的橋樑就是傅里葉變換。通過傅里葉變換，任何時域信號，都可以表示為不同頻率的正弦波信號的疊加。（傅立葉變換，時域，頻域）

傅里葉變換將原先難以處理的時域信號轉換成易於分析的頻域信號（又被稱為頻譜）。在頻域有大量工具可以對信號頻譜做一系列加工處理。信號轉換到頻域加工，然後再轉換回時域，這是信號分析的重要手段。

將信號從時域轉換到頻域的另一個好處是方便存儲。可以用聲音存儲來舉例。最初的音樂製作是存儲的模擬信號，即時域信號。所謂模擬，就是把聲音對空氣的震動模擬成電流再通過磁頭把磁場偏轉記錄在磁帶上。在數字媒體時代，連續的聲音信號則首先經過了採樣，轉換成數字信號再存儲起來。（http://graphics.cs.cmu.edu/courses/15-463/2011_fall/Lectures/SamplingReconstruction.pdf）

將聲音信號採樣然後存儲的過程是有損的。最好的聲音編碼演算法也只能做到高保真，無法絕對保真。但是有損是可以接受的，這是因為原始信號中有大量的雜訊和冗餘信號，去除這些信息並不影響我們欣賞音樂。（音頻編碼_百度百科）

聲音是一維的，而圖像是二維的（或多維的）。圖像的分析又稱為空域分析（Spatial Domain）。場景中的幾何物體投射到屏幕上的過程，實際就是對虛擬場景的採樣。所以也可以把圖像當作信號來分析。由於存儲空間和顯示設備解析度的限制，圖像的採樣過程也是有損的。

用頻域的觀點來看，信號由高頻信號和低頻信號疊加而成。簡單來說，高頻信號就是在時域空間定義區域內取值變化比較快的信號。相對的，低頻信號就是變化比較慢的信號。對圖像來說，顏色變化劇烈的地方屬於高頻，通常出現在物體的邊緣。圖像中的噪點也因為和周圍的顏色有較大差別，也屬於高頻。

狄拉克 函數（Dirac Delta Function）

定義在時域的函數 ，經傅里葉變換到頻域後為 。如果 定義在時域，那麼其轉換到頻域後則為 。傅里葉變換的這種性質稱為對稱性。時域和頻域對同一個函數的表示稱作一個函數對，下面列出一些重要的函數對：

1）Box: if ; , otherwise

Sinc:

2）Constant:

Delta:

3）Shah:

Shah:

其中， 函數和Shah函數用於採樣（http://www.pbrt.org/chapters/pbrt_chapter7.pdf），因為 函數具有如下性質：

，且 for all

由於傅里葉變換的對稱性，函數對中的函數具有如下特點：如果時域函數的周期為 ，那麼頻域函數的周期為 。非周期信號的傅里葉變換所得頻域信號是連續的，而周期信號的傅里葉變換所得頻域信號是離散的。

採樣和重建（Sampling and Reconstruction）

所謂採樣和重建，就是從連續函數 中取離散樣本，然後用這些樣本重建連續信號 ，目標是讓重建後的信號和原始連續信號儘可能一致。

一個頻率穩定（採樣間隔穩定）的採樣過程，可以形式化的寫成：

而利用濾波器（Filter） 和樣本做卷積（ ）可以重建信號：

傅里葉變換滿足卷積定理，即函數卷積的傅里葉變換是函數傅里葉變換的乘積。也就是說，時域函數的卷積相當於其頻域函數的乘積，時域函數的乘積等價於其頻域函數的卷積。下面，我們用卷積定理來分析一下採樣和重建的過程。

在時域，採樣是 函數和 的乘積。這等價於頻域中 和 的卷積。而 函數和 的卷積，相當於在 函數的中心位置複製了一個 。那麼 和 的卷積，就相當於以周期 複製了無數個 ，用圖像可以表示如下：（http://www.pbrt.org/chapters/pbrt_chapter7.pdf）

信號重建就是要從這無數個 中選出一個，然後變換到時域的過程。

這個挑選的過程，等價於，乘上一個box函數 。而函數 在時域中就是 。所以理想的重建過程，就是在時域對樣本用sinc函數做卷積的過程。

從以上分析的採樣和重建過程可以得出一些有趣的結論：

1）重建過程（或者說卷積），就是以每個樣本為中心，計算帶權重的reconstruction filter的過程。也可以理解成在樣本之間插值的過程。

2）若Shah函數在時域的周期為 ，那麼其在頻域的周期為 。所以時域中採樣頻率越低，在頻域中， 副本就越密。

3） 函數的定義域是 ，所以時域中用sinc函數重建信號需要用到所有的樣本。

走樣和採樣定理（Aliasing and Sampling Theory）

從信號的採樣和重建過程，我們可以發現，採樣間隔與原始信號的頻率有密切的聯繫。如果採樣率過低，頻域中 副本就會重疊，用box函數無法濾出 ，也就是發生了走樣。

所謂走樣，就是高頻信息重建成了低頻信息併疊加到原有信號所包含的低頻信息上，導致信息失真。在聲學領域，走樣表現為生成虛假低頻信息的方式。人耳所能聽到的聲音處於某個特定的範圍，如果過高頻率的聲音還原到了人耳聽覺範圍，就會導致本來能聽清的聲音卻聽不清了。

香農採樣定理指出，要想還原原始信號，採樣率必須是原始信號的最高頻率的兩倍或更高。這又被稱為Nyquist定理。某個採樣率所能表達的信號最高頻率又被稱為Nyquist上限。比如說，為了生產一張用44Khz採樣率採樣模擬信號生成的音樂CD-ROM，那麼模擬信號（即聲音）的最高頻率是22Khz。高於22Khz的信息必須從輸入的模擬信號中去除，否則就會存儲成一個低頻聲音，也就是會走樣。

根據採樣定理，某個採樣和重建過程所能正確處理的信號的頻率上限是有限的。自然界聲音的頻率可以認為是無限的，所以任何採樣和重建過程都不可能完全保真。

為了防止原始信號頻率過高導致的走樣，其中一個手段就是在採樣之前先把超出上限的高頻信息過濾掉，這就是pre filtering。相應的，重建過程使用的reconstruction filter又被稱為post filtering。

圖像繪製也是對模擬信號進行採樣，所以也會導致走樣。

Post Aliasing

上一節，採樣定理指出，若採樣頻率低於原始信號最高頻率的兩倍，就會發生走樣，也被稱為pre aliasing。而信號重建導致的走樣又被稱為post aliasing。

Post aliasing的根源是使用了不完美的reconstruction filter。用sinc函數重建信號需要用到所有的樣本，這在實踐中是不現實的。所以實踐中不存在完美的filter，即post aliasing一定會發生。在處理圖像時，由於圖像由離散的像素點組成，重建後的圖像也會因此而走樣。

此前，我們介紹了採樣率過低導致的pre aliasing現象。下圖給出了由於reconstruction filter不完美導致post aliasing的波形圖（頻域）：（http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.99.6947&rep=rep1&type=pdf）

Reconstruction Filters

正因為不存在完美的reconstruction filter，很自然的一個問題是，實踐中應該採用哪種濾波器以達到最好的重建效果。答案也很簡單，和sinc函數越接近，效果就越好，但是通常計算量就越大。這裡列出一些常見的filter：（部分filter有特殊用途）

1）box filter: nearest neighbour interpolation

2）triangle/tent filter: bilinear interpolation

3）cubic spline filter: bicubic interpolation

5）windowed-sinc

6）mitchell

7）gaussian

8）sobel filter: high pass

參考資料：

Reconstruction filter

http://graphics.cs.cmu.edu/courses/15-463/2011_fall/Lectures/SamplingReconstruction.pdf