Method for estimating parameters of a graph spectral filter using training data

Abstract

A method processes a signal represented as a graph by first determining a graph spectral transform based on the graph. In a spectral domain, parameters of a graph filter are estimated using a training data set of unenhanced and corresponding enhanced signals. The graph filter is derived based on the graph spectral transform and the estimated graph filter parameters. Then, the signal is processed using the graph filter to produce an output signal. The processing can enhance signals such as images by denoising or interpolating missing samples.

Claims

1. A method for processing an input signal represented as a graph, comprising: employing a processor executing computer executable instructions stored on a computer readable memory to facilitate performing the steps of: acquiring the input signal, wherein the input signal is an image that is an unenhanced image including noise; acquiring a training data set, wherein the training data set includes pairs of training signals, wherein each pair of training signals includes an unenhanced training signal with noise and a corresponding enhanced training signal with reduced noise, and wherein the training signals are in a form of images; determining a graph spectral transform as an orthogonal set of eigenvectors based on the graph, wherein the graph includes vertices connected by edges having associated weights, and wherein the weights are based on a guidance signal in a form of a guidance texture image; estimating, in a graph spectral domain, parameters of a graph filter based on the training data set; deriving the graph filter based on the graph spectral transform and the graph filter parameters; and processing the input image using the graph filter to produce an output image, wherein the output image is an enhanced image with reduced noise that provides an increased understanding of a displayed image over an unenhanced displayed image with noise.

2. The method of claim 1, wherein the estimating uses a least square procedure.

3. The method of claim 2, wherein the least square procedure comprises: obtaining an error image E from the pairs of training signals; generating a image y based on the graph spectral transform U.sup.t and the error image E; generating a matrix A from the training signals and the graph spectral transform U.sup.t; and estimating H.sub.1 A.sup.y, where represents a pseudo-inverse of the matrix A.

4. The method of claim 3, wherein the error image E is a difference between the enhanced image and the corresponding unenhanced images.

5. The method of claim 3, wherein the error image E is the enhanced image.

6. The method of claim 1, wherein the graph filter is H or UH.sub.1U.sup.t, where U.sup.t is the graph spectral transform.

7. The method of claim 1, wherein the weights are joint bilateral weights.

8. The method of claim 1, wherein the signal is a depth image, the guidance signal is a corresponding texture image of samples, and the weights are derived from a spatial distance between two samples and an intensity difference of two collocated samples in the corresponding texture image.

9. The method of claim 1, wherein processing removes noise from the signal, and further comprising: setting a scaling parameter to a predetermined value .sub.0; and constructing the graph filter as (I+H.sup.tH).sup.1, wherein I is an identity matrix.

10. The method of claim 1, wherein the processing interpolates the signal, and further comprises: setting a scaling parameter to a predetermined value .sub.0; and constructing the graph filter as (J.sup.tJ+H.sup.tH).sup.1, where
J.sub.(mN)=(I.sub.(MN)|0.sub.(M(NM)), where I is an identity matrix, M represents a number of known samples, and N a number of all samples.

11. The method of claim 1, wherein the processing interpolates missing samples in the signal, and further comprising: constructing the graph for each missing sample; estimating the graph filter based on the graph for each missing sample to produce an estimated graph filter; deriving the graph filter using the estimated graph filter to produce a derived graph filter; and interpolating the missing sample using the derived graph filter.

12. The method of claim 11, wherein the constructing of the graph comprises: selecting known samples near to the missing sample; and linking the missing sample to all known samples.

13. The method of claim 1, wherein the processing interpolates missing samples in the signal, and further comprising: partitioning the signal into non-overlapping patches; constructing the graph for each patch; estimating, for each patch, the graph filter based on the graph for the patch to produce an estimated graph filter; deriving the graph filter using the estimated graph filter for each patch to produce a derived graph filter; and interpolating the missing samples using the derived graph filters.

14. The method of claim 13, wherein the graph is constructed by linking each missing sample to all known samples within the patch.

15. The method of claim 14, wherein the graph has links between known samples.

16. The method of claim 1, further comprising: defining categories of the signal; and estimating, for each category, the filter parameters H.sub.1 of the graph filter to classify the signal as one of the categories.

17. The method of claim 16, wherein the signal is an image including blocks, and classifying each block by detecting whether the block includes edges or a flat texture.

Description

BRIEF DESCRIPTION THE DRAWINGS

(1) FIG. 1 is a graph of a spectral response of a conventional identity graph spectral filter;

(2) FIGS. 2 and 3 are flow diagrams of processing a signal using a graph according to embodiments of the invention;

(3) FIG. 4 is a pixel level star graph used by embodiments of the invention;

(4) FIGS. 5 and 6 are a block diagram of a 3D video system using the filtering according to embodiments of the invention;

(5) FIG. 7 is an example block level graph with two missing samples used by embodiments of the invention; and

(6) FIG. 8 is another example block level graph with two missing samples used by embodiments of the invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

(7) The embodiments of the invention provide methods for processing a signal using a graph spectral filter (GSF).

(8) In an example application used to describe the embodiments, the signals are images, for example, noisy images to be enhanced by reducing noise. Specifically, the noisy images can be depth images.

(9) The invention can be used for applications such as image and video processing, and for signal processing in social, energy, transportation, sensor, or neural networks, where high-dimensional data naturally can be represented as vertices of weighted graphs. The invention can also be used to process epidemiological, census, logistics, and medical data.

(10) As described above, the design of a filter H or a functional (H) for a signal represented as a graph, equivalently g(U, H.sub.1)) includes two phases. In a first phase, a graph transform domain is selected, based on the graph G for the signal to be processed, and a graph spectral filter (GSF) filter H.sub.1 is designed in the graph spectral domain using training data. We assume that the graph G is predetermined.

(11) The embodiments of our invention estimate parameters H.sub.1 for the. GSF filter using training, data. The parameters are used to design the graph filter. Though there are many known filter designs that can be used, the selection is based on certain assumptions, e.g., the signal has certain properties or follows a particular distribution, which makes the selection difficult in practice.

(12) Method Overview

(13) FIG. 2 shows one embodiment of the invention. The embodiment includes GSF design 201 and GSF use 202. The steps shown can be performed in a processing device connected to memory and input/output interfaces by buses as known in the art.

(14) Training

(15) It is noted that training data are available for sonic applications. In this case, the selection, is simpler. For example, in a 3D video compression system, noise in depth images can come from down-upsampling due to a mixed resolution coding. If enhanced depth images, before encoding, are available along with the reconstructed depth images, then it is possible to form training data and use the images to train the parameters of the graph filter. Subsequently, the estimated graph filter can be used to denoise the depth images at a decoder without having access to the original depth images.

(16) The embodiments of the invention provide a method for estimating the graph filter H or a GSF filter H.sub.1. It should be understood that the invention can be applied to other graph-based signal processing applications.

(17) Training data includes M image pairs, each image has N=WidthHeight pixels. Each image pair includes a noisy image 212 and a corresponding enhanced (denoised or clean) image 211. The filter design is formulated as determining an optimal graph filter:

(18) $\begin{array}{cc}\stackrel{.}{H}=\underset{H}{\arg \min }{.Math.E_{NM}-{\mathrm{HX}}_{\mathrm{du},NM}.Math.}^2\mathrm{where}{X}_{\mathrm{du}}={\left\{x_{\mathrm{du},1}^t,x_{\mathrm{du},2}^t,\mathrm{.Math.},x_{\mathrm{du},M}^t\right\}}^t& \left(39\right)\end{array}$
represents the noisy training images in columnar form (after down and upsampling (du)), and E represents the errors between the noisy images and the enhanced images.

(19) Given a graph 220, e.g., a bilateral filter or a joint bilateral filter, the graph transform U.sup.t is known. Inserting Eqn. (8) into Eqn. (39) is equivalently to determining a best H.sub.1:

(20) 0$\begin{array}{cc}{\stackrel{.}{H}}_1=\underset{H_1}{\arg \min }{.Math.E-{\mathrm{UH}}_1{U}^t{X}_{\mathrm{du}}.Math.}^2& \left(40\right)\\ {\stackrel{.}{H}}_1=\underset{H_1}{\arg \min }{.Math.U^{t}E-H_1{U}^t{X}_{\mathrm{du}}.Math.}^2& \left(41\right)\\ {\stackrel{.}{H}}_1=\underset{H_1}{\arg \min }{.Math.E^{t}U-X_{\mathrm{du}}^t{\mathrm{UH}}_1.Math.}^2& \left(42\right)\end{array}$
where H.sub.1 is the GSF filter in the graph spectral domain. The filter can be estimated from the training data set by solving the least square (LS) problem.

(21) Because H.sub.1 is a diagonal matrix, we vectorize the martix as
h.sub.1={h(.sub.1), h(.sub.2), . . . , h(.sub.N)
so that a conventional least square solution can be used. For this purpose, the columns of E.sup.tU are stacked, and a vector y is
y={y.sub.1.sup.t, y.sub.2.sup.t, . . . , y.sub.N.sup.t}.sup.t (43)

(22) Similarly, the columns of X.sup.t.sub.duU are used to define a matrix A with (MN) rows and N columns.
A=diag{.sub.1, .sub.2, . . . , .sub.N}(44)

(23) With this notation, Eqn. (42) can be written as

(24) $\begin{array}{cc}{\stackrel{.}{h}}_1=\underset{h_1}{\arg \min }{.Math.y-{\mathrm{Ah}}_1.Math.}^2& \left(45\right)\end{array}$
with a solution
{dot over (h)}.sub.1=A.sup.y (46)
where represents the pseudo-inverse. Thus, we formulate the filter estimation problem in Eqn. (39) and (42) with a solution provided by Eqn. (46),

(25) Filtering Method

(26) The method is shown in the FIG. 2. The method has the one time (off line) training phase 201, and the real-time operating (use) phase 202.

(27) Training

(28) During training, die method first estimates 210 the graph spectral filter (GSF) 203 as follows.

(29) Step 1: A graph G is defined 220 heuristically for an input signal 204.

(30) Step 2: Next, we derive 230 the graph Fourier transform (GFT) U.sup.t, where U.sup.t is an orthogonal set of eigenvectors of the corresponding normalized Laplacian matrix L. The GFT transform is an input for the estimation 210.

(31) Step 3: A normalizer/denormalizer D.sup.1/2 and D.sup.1/2 are derived 240.

(32) Step 4: For each training pair of images, e.g., an enhanced image 205 and a noisy image 205, an error signal E is obtained as a function of the image pairs, e.g. the difference image of the image pair, or simply just the enhanced images.

(33) Step 5: A signal y 206 is obtained as a function of signal U 207 and F. 208.

(34) Step 6: A signal A 209 is obtained as a function of signal U and the noisy training image 205.

(35) Step 7: Given signals y and A as inputs, the GSF filter parameters 211 are estimated by the GSF estimator 210 module using, e.g., a least square procedure.

(36) Then, all the parameters for the modules used during the real time operation as shown on the left of FIG. 2, when the filter is used, can be set accordingly.

(37) Operation

(38) During operation 202 the GSF 203 is used as follows.

(39) Step 1 : Provide an input image 204 to filtered or enhanced by the GSF filter 203.

(40) Step 2: Perform normalization 250 on the input image using Eqn, (3).

(41) Step 3: Perform a GFT transform 260 on the normalized input image using Eqn (1). The image obtained in the transform domain is provided as input for the next step.

(42) Step 4: Conduct GSF filtering using the estimated parameters H.sub.1 of the filter 203.

(43) Step 5: Perform an inverse GFT (iGSF) transform 270 on the filtered image in GFT transform domain using Eqn. (2).

(44) Step 6: Perform denormalization 280 using Eqn. (4).

(45) Step 7: Output 290 the processed image.

(46) In the above, steps 3, 4, and 5 (260, 203, 270) constitute the graph filter H 265 as described above.

(47) Normalization/Denormalization

(48) In another implementation of graph based filtering, the GFT U.sup.t is based on the combinatorial Laplacian matrix , instead, the filtering based on the normalized Laplacian L. In this case, the normalizes and denormalizer are an identity I, or equivalently, the not and denormalization modules are skipped in this case.

(49) Iteration

(50) The invention is not limited to use a closed solution to an LS solution. In a practical application, an iterative solution of the least squares problem may be preferred.

(51) Image Block Classifying

(52) It may be suboptimal to use a single filter parameter set for all images. Hence, we can classify image blocks into different defined categories, e.g., a block with a flat texture or an edge. Then, each category can be associated with one parameter set. Each category maintains one set of parameters for the GSF filter,

(53) High-pass Bilateral Graph Filter

(54) In one embodiment, the graph filter H is used to extract high frequency components from an input image x.sub.out=Hx.sub.in=UH.sub.1U.sup.tx.sub.in. As done in the prior art, the graph G is based on a bilateral filter (BF) with a star structure of the graph as shown in FIG. 4 with nodes i and j and weighted edge w.sub.i,j. This graph can he used to filter the central pixel 400.

(55) The parameters of the high-pass GSF filter H.sub.1 can be estimated using the GSF design according to this invention. In the training data set, the enhanced images 205 are the enhanced versions without high frequency components. The error signal E is set equal to the difference image between the input image and enhanced image. Then Eqn. (46) can he used to solve the parameter estimation for the graph fiber,

(56) Low-Pass Bilateral Graph Filter

(57) Similarly, a low-pass bilateral graph filter can be estimated if the error signal E is the enhanced image rather the difference image.

(58) High-Pass Joint Bilateral Graph Filter (JBF)

(59) In this embodiment, errors in a noisy depth image, e.g. due to coding artifacts, are filtered. In contrast to the bilateral filter, the weights of the joint bilateral filter are determined from a guidance image , e.g., a corresponding texture image. The weights can he represented by Eqn. (47), with x.sub.in replaced by

(60) $\begin{array}{cc}{w}_{\mathrm{ij}}=\exp \left(-\frac{{.Math.p_i-p_j.Math.}^2}{2{}_s^2}\right)\exp \left(-\frac{{\left(\tilde{I}\left[i\right]-\tilde{I}\left[j\right]\right)}^2}{2{}_r^2}\right)& \left(48\right)\end{array}$

(61) Similar to the high-pass bilateral graph filter, our GSF design is applied to estimate the parameters of GSF filter H.sub.1 to filter the noisy depth. The training data set is composed of noisy depth images and enhanced depth images. The error signal E is a difference depth image between the noisy depth and enhanced depth. Eqn. (46) is then used to estimate the parameter for the graph filter.

(62) Filter for Depth Denoising Based on Regularization

(63) In this embodiment, the graph filter is used to denoise an image. This problem can be formulated as a regularization problem:

(64) $\begin{array}{cc}\stackrel{.}{x}=\arg \underset{x}{\min }\underset{\underset{A}{}}{{.Math.x_{\mathrm{du}}-x.Math.}^2}+\underset{\underset{B}{}}{{.Math.\mathrm{Hx}.Math.}^2}& \left(49\right)\end{array}$
where x.sub.du is a noisy image. H is a regularization kernel that is designed as a high-pass graph filter with the underlying graph being a joint bilateral as in Eqn. (48). That is, the weights of the graph are determined from the corresponding texture image.

(65) In Eqn. (49), part A determines the error between the noisy depth and the filtered depth image. Part B is the Euclidean norm of the output of a high pass filter H. Parameter is predetermined, e.g. =.sub.0 to control the weights between the parts A and B. The solution, in closed form, is
{dot over (x)}=(I+H.sup.tH).sup.1x.sub.du (50)

(66) The design of H (or H.sub.1) is as for the high-pass joint bilateral filter described above, and the resulted filter (I+H.sup.tH).sup.1 is referred as a graph-based joint-bilateral filter (GB-JBF).

(67) FIG. 3 shows the correspondingly block diagram where the graph filter 265 of FIG. 2 is replaced by a more general filter module (U.sup.t, H.sub.1) 365, which is specified by a function of the graph transform and GSF filter, i.e., the GB-JBF filter.

(68) For an example of 3D video system, as shown in FIG. 5, the depth map 501 can be coded at a low resolution, which is first upsampled by a bilinear filter 510. The upsampled high resolution depth images 502 and a guidance texture image 505 are used as inputs to the GB-JBF block 365 to remove noise from the coding scheme. The filtered depth map 503 is dilated 520 using a dilation filter before performing view synthesis to yield the high resolution depth image 504. Note that the bilinear filter is an example filter to do upsampling, and other upsampling filters can be selected, for the initial processing. In addition, the dilation filter is an optional post processing step.

(69) Sealing Parameter

(70) It is noted that the scaling parameter in Eqn. (49) may be difficult to determine because it does directly have a physical meaning. One way to avoid setting is to solve the following similar problem:

(71) $\begin{array}{cc}\stackrel{.}{x}=\arg \underset{x}{\min }{.Math.\mathrm{Hx}.Math.}^2,s.t.{.Math.x_{\mathrm{du}}-x.Math.}^2<& \left(51\right)\end{array}$

(72) With this formation, parameter has a clear physical meaning that represents the changes made on the signals that can be tolerated.

(73) GB-JBU Upsampling Based on Regularization

(74) In another embodiment as shown in FIG. 6, when the input is depth image 501 has a low resolution, the graph filter (U.sup.tH.sub.1) 365 can be directly designed to perform upsampling while reducing noise. The regularization problem can be formulated as Eqn. (35), and its solution is given in Eqn. (37). The underlying joint bilateral graph is given as per Eqn. (48). We can also use H.sub.1 and the resulted filter (J.sup.tJ+H.sup.tH).sup.1 is referred as GB-JBU hereinafter. FIG. 3 shows this embodiment with the graph filter being GB-JBU 365, which replaces block 265 in FIG. 2.

(75) Pixel-level Method vs. Block-level Method

(76) In this embodiment, two methods are described for different graphs, namely pixel-level and block-level methods. For the pixel-level method as shown in FIG. 4, one graph is constructed for each missing sample (pixel). For example, in each star graph, is a star graph, the missing sample 400 is at the center. The center pixel is connected to nodes corresponding to known samples or pixels within a predetermined distance. Thus, each missing pixel in the image is associated with one graph, and hence the pixels are interpolated one by one.

(77) For the block-level method, the entire image is partitioned into non-overlapping patches and all missing samples in a patch are linked to other known samples (pixels) within a predetermined distance, and a single graph is constructed for all missing samples (pixels) Within one graph,

(78) FIG. 7 shows one example graph with two missing samples 701 in the image patch. All missing samples are connected to all known samples within the same patch.

(79) FIG. 8 shows another example graph, where all samples are connected, and even the known samples are connected to each other. With such a graph constructed for each image block, all missing samples 801 in a same image patch can he interpolated simultaneously.

(80) Parameter

(81) Similar to Eqn. (51), one way to avoid setting is to solve the following similar problem:

(82) $\begin{array}{cc}\stackrel{.}{x}=\underset{x}{\arg \min }{.Math.\mathrm{Hx}.Math.}^2,s.t.{.Math.J\left(x_{\mathrm{du}}-x\right).Math.}^2<& \left(52\right)\end{array}$

(83) With this formation, parameter has a clear physical meaning that represents the changes made on the known samples that can be tolerated.

(84) Although the invention has been described by way of examples of preferred embodiments, it is to be understood that various other adaptations and modifications can be made within the spirit and scope of the invention. Therefore, it is the object of the appended s to cover all such variations and modifications as come within the true spirit and scope of the invention.