SGTF

Projects‎ > ‎

Graph Signal Denoising via Trilateral Filter on Graph Spectral Domain

(IEEE Trans. on Signal and Information Processing over Networks)

Masaki Onuki¹ Shunsuke Ono² Masao Yamagishi² Yuichi Tanaka¹

¹Tokyo University of Agriculture and Technology

²Tokyo Institute of Technology

Abstract

This paper presents a graph signal denoising method with the trilateral filter defined in the graph spectral domain. The original trilateral filter (TF) is a data-dependent filter that is widely used as an edge-preserving smoothing method for image processing. However, because of the data-dependency, one cannot provide its frequency domain representation. To overcome this problem, we establish the graph spectral domain representation of the data-dependent filter, i.e., a spectral graph TF (SGTF). This representation enables us to design an effective graph signal denoising filter with a Tikhonov regularization. Moreover, for the proposed graph denoising filter, we provide a parameter optimization technique to search for a regularization parameter that approximately minimizes the mean squared error w.r.t. the unknown graph signal of interest. Comprehensive experimental results validate our graph signal processing-based approach for images and graph signals.

Sample code

SGTF toolbox is available here.

Note: Our code requires the graph signal processing tool box (GSPBox). To run our code, you must download the tool box and place it into our tool box.

Summary of SGTF

The trilateral filter (TF) [1] can be defined by using an adjacency matrix

and a diagonal degree matrix

where

is an input signal and

is the output signal smoothed by TF.

A normalized graph Laplacian matrix is defined as

. Since the normalized graph Laplacian matrix is a positive semidefinite matrix, it is decomposed into an orthogonal matrix consisting of a matrix of eigenvectors

and a diagonal matrix containing eigenvalues

, i.e.,

. In the graph signal processing (GSP) [2], the eigenvectors and eigenvalues provide a similar notion of frequency. From the definitions, the TF can be rewritten as

where

and

, respectively, and, the TF can be regarded as the spectral filtering (SGTF). The spectral response

acts as a low pass filter, and hence, we can replace it so that the spectral response is suitable for an arbitrary application.

In this paper, we adjust SGTF to denoise graph signals

under additive noise represented as

where

is the original signal and

is the noise signal that is independent of the original signal. To enhance the denoising quality, the filter kernel of SGTF is modified by using (Tikhonov) regularization as

where

is a regularization parameter. This parameter influences the denoising quality but its selection generally requires huge computation time. To overcome the problem, SGTF determines the parameter by minimizing the estimation of mean squared error (MSE) [3], i.e.,

where

is a noise variance. The estimation is not exactly equal to the true MSE, but the optimized parameter is almost identical to that giving the lowest MSE.

Experimental Results

1. image denoising

※SGBF: spectral graph bilateral filter [4]

2. graph signal denoising

※graphBior [5]

※OSGFB: oversampled graph filter bank [6]

※SGWT: spectral graph wavelet transform [7]

3. 3D mesh smoothing

References

[1] P. Choudhury and J. Tumblin, “The trilateral filter for high contrast images and meshes,” Eurographics Symp. Rendering, pp. 1-11, 2003.

[2] D. Shuman, S. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, “Signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular data domains,” IEEE Signal Processing Magazine, vol. 30, issue. 3, pp. 83-98, May, 2013.

[3] C. Stein, “Estimation of the mean of a multivariate normal distribution,” Ann. Statist., vol. 9, pp. 1135-1151, 1981.

[4] C. Tomasi and R. Manduchi, “Bilateral filtering for gray and color images,” in Proc. IEEE Int. Conf. Computer Vision (ICCV), pp. 839- 846, Bombay, India, Jan., 1998.

[5] S. K. Narang and A. Ortega, “Compact support biorthogonal wavelet filter banks for arbitrary undetected graphs,” IEEE Trans. on Signal Processing, vol. 61, pp. 4672-4685, 2013.

[6] Y. Tanaka and A. Sakiyama, “M-channel oversampled graph filter banks,” IEEE Trans. Signal Processing, vol. 62, no. 13, pp. 3578–3590, Jul, 2014.

[7] D. Hammond, P. Vandergheynst, and R. Gribonval, “Wavelets on graphs via spectral graph theory,” Applied and Computational Harmonic Anal- ysis, vol. 30, no. 2, pp. 129-150, 2011.

SGTF_toolbox_ver0.1.zip

(414k)

Masaki Onuki,

May 31, 2016, 1:18 AM

v.2

Comments