4

I have a matrix a=[[1 2 3]; [4 5 6]; [7 8 9]] and a submatrix b=[[5 6];[8 9]].

Is there a method in matlab for deconvolving (a,b) ?

I am looking for a method fo recognize the presence of a submatrix in a possible giant matrix. By a sort of deconvolution I expect to obtain something like a matrix with zeros all around and 1 in the place where the submatrix is present.

In the above example, a 1 in the right-down corner.

Royi
  • 4,433
  • 6
  • 42
  • 58
no_name
  • 1,265
  • 2
  • 15
  • 20
  • 2
    It's really unclear where convolution entered the discussion. Are you saying that you have a matrix `c=conv2(a,b)` and you want to literally deconvolve? If not can you use a more accurate term than "deconvolve"? Seems that this is just finding a submatrix within a matrix. – Chris A. Jun 27 '12 at 14:33
  • O.K. There are 2 problems in one. The first one is about matlab. If I have `c=conv2(a,b)`, how can I recover b by deconvolving c and a ? The second one is more "philosophical". Suppose `a` is the result of interaction (convolution) between objects. Suppose you do not know these objects. Just model a representation of one of them. I would like to apply a sort of deconvolution between `a` (the big picture) and my hypothetical representation of an object. My goal is to obtain a matrix (with the same size as `a`), with ones where/if the object could be present in `a`. – no_name Jun 27 '12 at 15:05
  • 1
    Unfortunately, neither of those two questions came across clearly. Ask more precise questions if you actually want answers. – Chris A. Jun 27 '12 at 15:18
  • Also check out : http://dsp.stackexchange.com/questions/2969/deconvolution-of-1d-signals/3560#3560 – Andrey Rubshtein Oct 05 '12 at 13:16

2 Answers2

6

There is a better explanation here.

Let's talk about 1D deconvolution for simplicity sake.

Your signal can be represented as a vector, and convolution is multiplication with a tridiagonal matrix.

For example:

Your vector/signal is:

    V1
    V2
    ...
    Vn

Your filter (convolving element) is:

  [b1 b2 b3];

So the matrix is nxn: (Let it be called A):

[b2 b3 0  0  0  0.... 0]
[b1 b2 b3 0  0  0.... 0]
[0  b1 b2 b3 0  0.... 0]
.....
[0  0  0  0  0  0...b2 b3]

Convolution is:

  A*v;

And de-convolution is

  A^(-1) * ( A) * v;

Obviously, in some cases de-convolution is not possible. Then you will have singular A. But if A^-1 exists, you need to compute it, and apply it on the result.

For 2D case, it is a bit more complex, but the idea is the same.

Community
  • 1
  • 1
Andrey Rubshtein
  • 20,557
  • 10
  • 65
  • 102
  • `A` seems like a Toeplitz matrix. It is known that if we have two signals `a` and `b`, `c=conv2(a,b)=A*b'`, where `A` is the toeplitz matrix of `a`. The problem is that the # of columns of `A` have to be equal to the # of columns of `b`, and `A` has to be square if we want to deconvolve `c,A` by `b'=A^-1*c`. It is not so clear to me how manipulate these sizes... – no_name Jun 27 '12 at 19:50
  • 1
    @NasserM.Abbasi, A is square - it is the size of the signal in both dimensions. The filter size is the amount of non-zero diagonals. – Andrey Rubshtein Jun 28 '12 at 06:34
3

If you want to find the presence, or the likelihood of presence, of small matrix inside another, then you're looking for correlation, not deconvolution.

The simplest method would be to use normxcorr2, which return a matrix of values [-1..1], where 1 means the pixel where the small matrix is found.

The drawback/benefit is that normxcorr2 is not sensitive to gain, meaning if you're looking for [1 2 3 4] then you'll also find [2 4 6 8]

Yanai Ankri
  • 431
  • 4
  • 11