動機
平滑、銳化、邊緣檢測與模糊,都是把每個像素換成其鄰近像素的加權和,而且各處權重相同。本單元為這一運算給出精確形式,證明刻畫它的特徵,說明如何低成本計算,並把它與頻率聯繫起來。本單元依賴「取樣、混疊與預濾波」一課所引入的平均濾波,並為模糊逆運算與梯度成像等單元提供語言。
定義
先討論一維信號 (),假設在某有限範圍之外為零;影像以同樣的公式、改用兩個指標處理。
定義 9.2.1
(核、相關與卷積)
核是有限支撐的序列 。 與 的相關及卷積為
卷積就是以翻轉的核 作相關。對稱核 的兩者相同。對影像,,形式相同。
定義 9.2.2
(線性平移不變算子)
信號上的算子 若滿足 稱為線性;若與平移 可交換,稱為平移不變。
定義 9.2.3
(頻率響應)
核 的頻率響應為 ( 為實數)。
在影像邊緣,求和會用到不存在的像素。常見做法有:補零(把缺少的像素當作 )、複製邊緣值、鏡射,或只輸出有效部分(只在整個核都落在影像內的位置計算)。下文有關精確公式的結論均假設已指明所用約定;邊界附近的結果隨約定而異。
主要結果
定理 9.2.4
(線性平移不變濾波器的刻畫)
設 是有限支撐信號上的線性平移不變算子。令 ,其中 在 時為 ,其餘為 。則對每個這樣的 ,。
證明
(把信號分解為平移後的脈衝)
每個有限支撐的 都等於有限和 。由線性與平移不變性,。以 代換,得 。
證明透視
一個輸出決定整個算子
每個假設都恰好用一次。有限支撐令脈衝分解成為有限和,所以不需要假設 連續。線性讓 可以穿過這個和與係數 。平移不變把 變成 ,即單一已知輸出 的平移複本。
不顯然的一步,是只在一個信號(脈衝)上測試算子,再由它的平移複本重建所有其他輸出。證明以純粹的重新編號結束,這正是卷積帶有翻轉指標 的原因:位置 的輸出,收集了放在每個輸入位置 的那個 複本。若去掉平移不變性,前兩步仍成立,第三步卻不成立,下一個例子會說明這一點。
核 稱為脈衝響應:對單一亮像素濾波,所得結果就是該核的一個複本。
反例模式
只有線性不足以得到卷積
一個誘人的說法是:每個信號上的線性算子都是與 的卷積。取算子 ,即每隔一個樣本取一個。它是線性的,而 ,所以 。對 ,因為 沒有整數解,所以對每個 都有 ,而 。這個算子並非平移不變:輸入平移一個樣本,輸出並不平移一個樣本。修正方法是要求平移不變;因此降取樣被分析為卷積加上取樣。
命題 9.2.5
(卷積滿足交換律與結合律)
卷積滿足交換律與結合律, 是單位元。因此連續施加的線性濾波可以任意次序進行,且 。
證明
(重新編號各求和式)
交換律由求和式中作代換 得到。結合律:,按 歸併各項,得 ;所有求和皆為有限和。 是單位元,則由 得出。
定理 9.2.6
(可分離核)
若二維核具有形式 ,則 ,其中 沿第一個指標濾波, 沿第二個指標濾波。支撐為 的核具有此形式,當且僅當其矩陣的秩至多為一。
證明
(把第一個指標提到括號內)
,即所述的複合。矩陣 的秩至多為一,而每個秩至多為一的矩陣都等於某個 。
因此 的可分離核每個輸出像素只需 次乘法,而非 次。取樣後的高斯(Gauss)核 恰好可分離。並非每個看似平滑的二維核都可分離,應檢查核矩陣的秩。
定理 9.2.7
(卷積定理(循環情形))
對 週期序列定義 DFT 及循環卷積 。則 。
證明
(拆開指數函數)
。把 寫成 ,固定 先對 求和。由於 與指數函數都以 為週期, 只是置換剩餘類,內層和即 。其餘部分為 。
概念視角分析
濾波器是每個頻率上的乘數
複指數 是每個卷積的本徵函數:。在這種描述下,同一個濾波器不再是滑動加權和,而是一列數 ,說明各頻率被縮放多少。先後套用響應為 的兩個濾波器,頻率 的縮放因子為 ,所以濾波器的複合就變成響應相乘。
例題
例題 9.2.8
(平滑脈衝與濾波複合)
設 (位置 ),(位於 ),補零。每個位置 有 :
例如 ,。核的權重和為 ,所以總和 不變。再者,核 與自身卷積得 ,因為偏移 處的係數,等於各取一個抽頭而和為所需偏移的配對個數,即 對,每對權重為 ;由結合律,兩次三抽頭平均等於一次五抽頭核。
例題 9.2.9
(小塊上的可分離濾波)
設 ,,並取小塊 。直接計算的中心響應(核對稱)為 。分離計算:用 對 的每一列(縱向)濾波,三列分別得 、、;再用 對該行 濾波得 。兩條途徑一致,正如可分離核的結果所言。對 的核,每個輸出像素的乘法由 次減為 次。
例題 9.2.10
(讀出頻率響應)
對 ,。於是 ,,。序列 被完全消去:。以週期為四的信號 驗證 :,,與 及 吻合。
常見錯誤與細微之處
常見錯誤
(混淆相關與卷積)
卷積翻轉核,相關則不翻轉。對導數遮罩這類反對稱核,例如 、、,兩者相差一個正負號。取 (位置 ),在 處,相關給出 ,卷積給出 。
常見錯誤
(忘記正規化)
平滑核的權重和應為 ,以保持平均亮度;導數核的和應為 ,使常數映為 。若模糊核的抽頭為 而沒有除以 ,任何常數影像都會變成原來的四倍亮度,看起來像增益錯誤,而不是平滑。
常見錯誤
(用循環卷積代替線性濾波)
卷積定理針對循環卷積。取 、。線性卷積為 ,有五項;循環卷積則把最後一項繞回第一項,得 。以 DFT 計算線性卷積須先補零至長度至少為五,才不會發生環繞。
習題
練習 9.2.11
(計算 與 的完整卷積,兩者都從指標 開始。)
基礎
解答(2)
- 1
寫出此核的定義和
由於 、,,其中 在 之外為 。
- 2
計算輸出可能非零的每個指標
;;;。所以 。核對:各項之和為 ,等於 。
依據: 完整輸出的長度為 。
練習 9.2.12
(設 (),核為 、、。計算 與 。)
基礎
解答(3)
- 1
計算相關
。
- 2
計算卷積
。
依據: 卷積用 代替 。
- 3
比較兩者
兩者符號相反,任何反對稱核都是如此。
練習 9.2.13
(判斷 與 是否可分離;若可以,給出 與 。)
核心
解答(3)
- 1
檢驗第一個矩陣的秩是否為一
第二列 是第一列 的兩倍,所以秩為一。
- 2
分解為
所以 、。
- 3
檢驗單位矩陣
單位矩陣的行列式為 ,所以秩為二,不可分離。
依據: 可分離表示秩至多為一。
練習 9.2.14
(求 (抽頭位於 )的頻率響應,並在 與 處求值。)
核心
解答(3)
- 1
把指數函數相加
- 2
在兩個頻率處求值
,。
- 3
解讀
常數信號被映為零,交替信號被放大 倍:這是高通的二階差分濾波器。