Projects‎ > ‎


Graph Signal Denoising via Trilateral Filter on Graph Spectral Domain

(IEEE Trans. on Signal and Information Processing over Networks)
1Tokyo University of Agriculture and Technology
2Tokyo Institute of Technology

    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 as
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., as

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 

[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. 
Masaki Onuki,
May 31, 2016, 1:18 AM