Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

2D circular convolution (part 1)

Posted on 2004-11-07
10
Medium Priority
?
1,080 Views
Last Modified: 2008-02-26
Two 2D sequences, each of which is 3 x 4 points in extent, are circularly convolved using (6 x 6)-point 2-D DFTs (Discrete Fourier Transforms). Which samples of the (6 x 6)-output array are identical to the samples of the linear convolution of the two input arrays & which are different??
0
Comment
Question by:mte01
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
  • 5
10 Comments
 
LVL 31

Expert Comment

by:GwynforWeb
ID: 12519116
Frstly could you confirm your defnition of circular definition (I have seen a number of defnitions). Do you mean that A & B have periocity M in the x and N in the y ie that

A(x+M,y+N) = A(x,y)

in which case the results are always the same as the FFT method of convolution since it assumes periodicty in its calculation. This would also mean that if you are defining linear convolultion by not assuming periodicity, and merely padding to the side with zeroes, that for periodicity not to be a factor you would require, if  A=p by q and  B=q by p,  that p+q-2 < max(M,N)

Or am I misunderstanding the question?

0
 
LVL 31

Expert Comment

by:GwynforWeb
ID: 12519160
typo:-      that p+q-2 <= max(M,N)
0
 
LVL 31

Expert Comment

by:GwynforWeb
ID: 12519544
better written as  for linear convolutionto be the same as circular p+q-1<max(M,N)

essentially if I am understanding right the functions when layed edge overlapping edge should not wrap round due to periodicty to intersect on the other side. But still I am not sure if I understand right.
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 3

Author Comment

by:mte01
ID: 12519815
Yes GwynWeb, your last comment is correct.........this is the difference between linear & periodic (circular) convolution. In circular conv., if we are convolving two P x Q sequences in an N x N DFT, we would pad zeros to each signal, so they would become N x N each, then we would apply the DFT to each signal, and multiply the results, and then apply the IDFT of the product, we would get the resultant signal, which would be the same if we were linearly convolving the two signals (the size would be different, but if the larger matrix was spatially aliased, the two result matrices would be identical.
0
 
LVL 3

Author Comment

by:mte01
ID: 12519834
For example, if we were convolving these two 2 x 2 signals:

A:

1 0
2 1

& B:
1 0
1 1

this would be the result of the circular convolution:

0 0 0 0
1 0 0 0
3 2 0 0
2 3 1 0

and this would be the result of the linear convolution:

3 2
4 3

The two results are the same if the larger matrix is spatially aliased to produce a 2 x 2 matrix.

Here because N >= P+Q-1, the number of points different between circular & linear convolution is 0 (like in 2D circular convolution (part 1))
0
 
LVL 31

Expert Comment

by:GwynforWeb
ID: 12520356
the only way I can see the linear and circular convolution (as definied above) being the same is when one of the functions is an impulse function ie a 1 by 1. I tried constucting examples in 1-D and always came back to an impulse function, same for 2x2 functions. Proving this in general would be hard .
0
 
LVL 3

Author Comment

by:mte01
ID: 12520364
No GwynforWeb, I don't want a case where they're equal, if you re-read my question, I only want the number of points which would be common between the 2 convolutions....
0
 
LVL 31

Accepted Solution

by:
GwynforWeb earned 2000 total points
ID: 12521071
I think I am having problems understanding the question ( English is not my first  langauge)

If I now understand you right it is:-  what (x,y) values are the same if you convolute linearly or circularly. In which case

You can think of the convolution of A and B as placing the reflection of B on A  summing then shifing along/up to calculate the terms 1 by 1. For the 2 techniques to be the same in general you require the shifted matrix no to wrap around the region of have a zero interection with A in this case a  6x6 region.  

For a 6X6 region and a pair of 3X4 functions then you when you shift up you have no intersection with A  or do not  wrap around the top of the region  only at y=0,1,2,3.  As you move along the x  same occurs with the left hand side at x=0,1,2. So the points that would be the same are those in the 4 by 3 block in the corner.

(I have placed the corners of the functions A and B at (0,0) here)

Sorry if I still have problem wrong.

 
0
 
LVL 3

Author Comment

by:mte01
ID: 12521276
Yes, now you have understood my question correctly,; I'll be looking into your answer to try to verify it.......
0
 
LVL 3

Author Comment

by:mte01
ID: 12521303
Yes, thinking in a reasonable manner, your answer seems to be the perfect correct answer, but I was not able to prove it (It's hard to do so in the 1st place because you are doing it for two general inputs, so I think your explanation would be enough)........Good Work!!
0

Featured Post

Hire Technology Freelancers with Gigs

Work with freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely, and get projects done right.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article provides a brief introduction to tissue engineering, the process by which organs can be grown artificially. It covers the problems with organ transplants, the tissue engineering process, and the current successes and problems of the tec…
When we purchase storage, we typically are advertised storage of 500GB, 1TB, 2TB and so on. However, when you actually install it into your computer, your 500GB HDD will actually show up as 465GB. Why? It has to do with the way people and computers…
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…

609 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question