圖形上的訊號處理與凹口濾波器設計

Signal Processing on Graphs and Notch Filter Design

郭柏毅(Bo-Yi Guo)

指導教授 ： 貝蘇章

國立臺灣大學/電機資訊學院/電信工程學研究所/碩士(2016年)

https://doi.org/10.6342/NTU201801605

摘要

訊號處理在現實生活中有很多的應用，而傳統數位訊號處理的理論可以說是相當完備。然而，隨著人類的進展，資料量的需求越來越大和複雜，傳統數位訊號處理的理論已不適合處理如此龐大且複雜的資料。
近幾年，很多的學者投入研究圖形上的訊號處理。圖形可以是一個不規則且複雜的架構。有別於以往處理的對象都是規則或是歐幾里得空間可以描述的形狀，圖形上的訊號處理的理論則可以被廣泛地應用並解決現今所遭遇的困難，像是如何對龐大的社交網絡的數據進行壓縮與還原。當然，傳統數位訊號處理的理論可以視為圖形上訊號處理理論的一種特例。
在本篇論文的第一部分，我們會先介紹圖形上的基本概念，像是圖形的傅利葉轉換、圖形的旋積、圖形相關的運算子等。接著，專注在討論對圖形的下採樣與還原，並提出一多通道架構來實現對圖形的下採樣與還原。接著與現今的方法做比較，可以發現我們的方法不但能達到完美還原圖形訊號，還能保持下採樣後圖形與原圖形的相似性。亦即，下採樣後的訊號頻譜與原訊號頻譜幾乎一致。
在論文的第二部分，我們專注在凹口濾波器的設計、分析以及如何提升凹口濾波器的效能。採用一個只需一個參數的回授架構，藉由調大該參數便能使各種類形凹口濾波器的效能提升，並用數學證明其合理性。
第一部分和第二部分看似兩個不相干的領域，一個建構在新興的圖形處理上；另一個則是建構在傳統訊號處理上。巧妙地藉由變數的轉換可以讓這兩個領域結合。因此，任何傳統濾波器皆可透過這個方法得到一個圖形上的濾波器。

關鍵字

圖 ； 訊號處理 ； 下取樣 ； 粗化 ； 完美還原 ； 凹口濾波器

並列摘要

Signal processing plays a critical role in many applications such as denoising and communication. It has really wide usages. Classical signal processing has been developed many decades and is a mature and complete field equipping with a lot of useful theories such as the sampling theory and the uncertainty principle. However, as human progress, the demand for data to describe a thing or a situation becomes larger and more complex. The classical DSP is not applicable to such complex and enormous data any more. Hence, some ideas and methods are developed.
In recent years, many researchers devote themselves to developing theories for signal processing on graphs. A graph can be an irregular and complex structure. Differently from the classical signal processing that can only deal with regular structures, the developing theories of signal processing on graphs can be widely utilized and solve difficult problems such as how to compress big data of social network and reconstruct the compressed data back as well as traffic congestion problems. Obviously, the classical DSP is a special case of the emerging graph signal processing (GSP).
In the part one of this thesis, we first introduce basic concepts of signal processing on graphs such as graph Fourier transform, graph convolution and graph-related operators. Next, we will focus on downsampling as well as on reconstructing a graph signal, and then propose an M-channel to decompose a graph signal and then achieve perfect recovery. To demonstrate the effectiveness of our proposed method, the existing method based on sampling theory is compared with ours. It is easy to find that our proposed method can not only perfectly reconstruct graph signals, but also obtain a coarsened graph signal with spectral invariance and a coarsened graph with topological similarity. That is, a coarsened graph signal is strongly related to an original graph signal.
In the part two of this thesis, we concentrate on the notch filter design, analysis and how to improve its performance. A feedback structure is applied to better the performance of any kinds of notch filters. The structure requires only one parameter to adjust filter performance in the frequency domain. Besides, mathematical proof and pole-zero plot are presented to demonstrate the effectiveness of the feedback structure.
The part one and the part two are seemingly unrelated. One is based on the emerging field of signal processing on graph, while the other is established on the classical signal processing. We use a method to combine this two fields. Therefore, any kind of traditional filters can be transformed into a corresponding graph filter via the method.

並列關鍵字

Graphs ； Signal Processing ； Downsampling ； Coarsening ； Perfect Recovery ； Notch Filter

參考文獻

Chapter 1

[1.1] D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega and P. Vandergheynst, “The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains,” IEEE Signal Process. Mag., vol. 30, no. 3, pp.83–98, May 2013.

[1.2] F. Zhang and E. R. Hancock, “Graph spectral image smoothing using the heat kernel,” Pattern Recognit., vol. 41, pp. 3328–3342, Nov. 2008.

[1.3] S. K. Narang, Y. H. Chao, and A. Ortega, “Graph-wavelet filterbanks for edge-aware image processing,” in Proc. IEEE Stat. Signal Process. Workshop, Ann Arbor, MI, Aug. 2012, pp. 141–144.

[1.4] S.-C. Pei, W.-S. Lu and C.-C. Tseng, “Analytical two-dimensional IIR notch filter design using outer product expansion,” IEEE Trans. Circuits Syst. II, Analog Digit. Signal Process., vol. 44, no. 9, pp. 765-768, Sept. 1997.