Method for graph based processing of signals

Patent metadata

Field	Value
Publication number	US-9600865-B2
Application number	US-201414269527-A
Country	US
Kind code	B2
Filing date	May 5, 2014
Priority date	May 5, 2014
Publication date	Mar 21, 2017
Grant date	Mar 21, 2017

Abstract

A method processes a signal by first constructing a graph from the signal, and then determining a graph matrix from the graph and the signal. A Krylov-based subspace is determined based on the graph matrix and the signal. A filter for the Krylov subspace is determined. The filter transforms the signal to produce a filtered signal, which is output.

First claim

We claim:

1. A method for processing an image signal by an input interface in communication with a non-transitory computer readable storage medium embodied thereon a program executable by a processor for performing the method, comprising:
constructing, by the processor in communication with the input interface, a graph from the image signal, wherein the image signal is acquired by at least one sensor;
determining, by the processor, a graph matrix from the graph and the image signal by adjusting a magnitude of a corresponding graph frequency components;
determining, by the processor, a Krylov-based subspace based on the graph matrix and the image signal;
determining, by the processor, a filter for the Krylov-based subspace, wherein the filter transforms the image signal to produce a filtered image signal; and
outputting the filtered image signal via an output interface in communication with the processor, wherein noise in the filtered image signal is less than noise in the image signal and provides for improved signal processing.

2. The method of claim 1 , wherein the Krylov-based subspace is selected from the group consisting of an approximate Krylov subspace, a rational Krylov subspace, an approximate rational Krylov subspace, and combinations thereof.

3. The method of claim 1 , wherein the filter is selected from the group consisting of a function of the graph matrix and an approximate function of the graph matrix.

4. The method of claim 3 , wherein the function of the graph matrix is selected from the group consisting of a matrix polynomial, an approximate matrix polynomial, a matrix rational function, an approximate matrix rational function, and combinations thereof.

5. The method of claim 4 , wherein the matrix polynomial optimally suppresses graph Fourier spectral components of the image signal on an interval, while emphasizing the graph Fourier spectral components outside of the interval.

6. The method of claim 4 , wherein the matrix polynomial is a combination of polynomials suppressing graph Fourier spectral components of the image signal on one or more non-interlacing intervals, while emphasizing the graph spectral components outside of the one or more non-interlacing intervals.

7. The method of claim 3 further comprising:
determining the filter based on a Chebyshev iterative method using one or a combination of roots of Chebyshev polynomials and recursive formulas for the Chebyshev polynomials.

8. The method of claim 4 , wherein the matrix rational function is based on an inverse of the graph matrix.

9. The method of claim 1 , further comprising:
determining the filter based on a Krylov subspace iterative method.

10. The method of claim 9 , further comprising:
determining the Krylov subspace iterative method based on a conjugate gradient iterative method.

11. The method of claim 3 , wherein the function of the graph matrix is based on an iterative method solving a partial eigenvalue problem for the graph matrix, and wherein the partial eigenvalue problem is a problem of computing a part of eigenvalues, and the number of iterations of the iterative method is determined by a threshold.

12. The method of claim 11 , wherein the iterative method is based on one or a combination of a Krylov subspace and a rational Krylov subspace iterative methods.

13. The method of claim 12 , wherein the Krylov subspace iterative method is based on one or a combination of the Lanczos and conjugate gradient methods.

14. The method of claim 1 , wherein the graph matrix is based on one or a combination of graph adjacency, random walk, and Laplacian matrix, and wherein entries of the graph matrix are determined by weights of edges of the graph.

15. The method of claim 1 , wherein the filter is adaptive to the image signal and the filter is a low pass filter.

16. The method of claim 3 , wherein the function is adaptive to the image signal.

17. The method of claim 5 , wherein the polynomial is adaptive to the image signal.

18. The method of claim 1 , wherein the image signal is selected from the group consisting of an image, a patch in an image, a set of images, a video sequence, a patch in a video sequence, a depth map, and a patch of depth map and combinations thereof, and wherein the graph includes nodes and edges, and further comprising:
determining graph vertices to represent the image signal on individual or groups of image pixels or video voxels; and
determining weights of edges of the graph using the image signal.

19. The method of claim 1 , wherein the image signal is determined by a first image signal selected from the group consisting of an image, a patch in an image, a set of images, a video sequence, and a patch in a video sequence and combinations thereof, and wherein the graph includes nodes and edges, and further comprising:
accessing a depth signal and a second image signal selected from the group of a second set of images, a second video sequence, and a patch in the second video sequence;
warping the second image signal to a viewpoint of the first image signal using depth image based rendering;
determining weights of edges of the graph using the warped image signal.

20. The method of claim 1 , wherein the image signal is noisy having a first distortion, and the filtered image signal has a second distortion, such that the second distortion of the filtered image signal is less than the first distortion of the image signal.

Assignees

• Mitsubishi Electric Res Laboratories Inc

Inventors

• Tian Dong
• Mansour Hassan
• Kniazev Andrei
• Vetro Anthony

Classifications

• G06T11/26

  Drawing of charts or graphs · CPC title

• G06T5/002 Primary

  Physics · mapped topic

• G06T11/206

  Physics · mapped topic

• G06T2207/20072

  Graph-based image processing · CPC title

• G06T5/70 Primary

  Denoising; Smoothing · CPC title