1
$\begingroup$

Is it possible to combine two convolution kernels (convolution in terms of image processing, so it's actually a correlation) into one, so that covnolving the image with the new kernel gives the same output as convolving it with the first, and then the second kernel?

For example, if I want to convolve an image with 1st 3x3 kernel and then 2nd 3x3 kernel, apparently I should be able to combine those two kernels and convolve my image with this new kernel. What is the size of my new kernel? Is it 3x3? If so, there's something worrying me about that. Let me explain.

Let's say I'm convolving Input image with Kernel 1, then convolving the result with Kernel 2.

Pixel marked X depends on value of pixel P2 (convolving the image with kernel 2). Pixel P2 lies on the new image that was produced by convolving input image with Kernel 1. So the value of P2 was calculated with taking P1 into account.

Now, X relies on values of P1 and P2. That's what stops me from believing I could achieve the same result with convolving my original image with a 3x3 kernel combining kernel 1 and kernel 2. Pixel X cannot "know" anything about pixel at location P1.

$\endgroup$
3
$\begingroup$

Let's assume the original image is $x[n_1,n_2]$ and two kernels are $h_1[n_1,n_2]$ and $h_2[n_1,n_2]$. Convolution associative law says that:

$$(x[n_1,n_2]*h_1[n_1,n_2])*h_2[n_1,n_2] = x[n_1,n_2]*(h_1[n_1,n_2]*h_2[n_1,n_2])$$

So covnolving the image with the new kernel will always produce the same output as convolving it with the first, and then the second kernel. To get the new kernel just use the 2-dimensional convolution definition:

$$h_3[n_1,n_2]=h_1[n_1,n_2]*h_2[n_1,n_2]=\sum_{i=-\infty}^{+\infty} \sum_{j=-\infty}^{+\infty} h_1[i,j] h_2[n_1-i,n_2-j] $$

$\endgroup$
  • $\begingroup$ But how do we know we have to convolve the two kernels to get one kernel doing the same thing? The convolution in image processing is so called only because it's similar to mathematical convolution. Moreover we are dealing with discrete domain here. I'm just looking for justification of the fact that we have to convolve these kernels. $\endgroup$ – user4205580 Nov 16 '14 at 20:07
  • $\begingroup$ It does not matter if we are in continuous or discrete domain. You will just need to use their corresponding definition. About the justification you might be interested in this $\endgroup$ – Sina Nov 16 '14 at 21:16
2
$\begingroup$

The answer is yes.

The kernel you would use is simply these operations combined. So blur:

1,1,1
1,1,1
1,1,1

combined with blur:

1,2,3,2,1
2,4,6,4,2
3,6,9,6,3
2,4,6,4,2
1,2,3,2,1

It is assume all points not used has a zero. And in each of those 9 spaces you do another copy of the kernel. And add up the different parts needed by a multiple in that section.

The reason you don't run into is that it's slower. You're doing MN work times K1, and MN work times K2. But, MN * K1 * K2 > MN * K1 + MN * K2. So the typically desire is to separate the kernels. You can do this same 5x5 blur (25 operations per pixel) as two [1,1,1] kernels both horizontal and vertical, so (12 operations per pixel).

In straight math, you won't have lossy operations. So the order of the convolution can matter if you have lossy operations. This is why doing a blur and then an emboss is different than emboss then blur. Which isn't to say the kernels aren't associative, but that the error in them can be. But, for blurs you won't have this edge condition as strongly.

You will however lose the rounding bias and fail to compound it. value / 81 rather than (value / 9) / 9 (in floored integer division) could make your resulting matrix slightly more correct than it would have otherwise been.

$\endgroup$
  • $\begingroup$ "Because image convolution kernels are not associative." Are you sure? $\endgroup$ – uohzxela Feb 25 '17 at 2:45
  • $\begingroup$ I suppose I'm wrong. Though in practice lossy operations like emboss break the associative properties. You really can blur then emboss and the result is different than emboss then blur, but not because of the kernels themselves but because emboss is highly lossy. When it crimps everything into gamut. $\endgroup$ – Tatarize Feb 25 '17 at 11:52
1
$\begingroup$

The answer is as simple as this: convolution is associative:

$$ a \ast (b\ast c) = (a \ast b ) \ast c. $$

$\endgroup$
  • $\begingroup$ Ok, but as I said in image processing the term convolution is not exactly a convolution, but a correlation (that's what I've read). So we can't use convolution properties for this. $\endgroup$ – user4205580 Dec 20 '14 at 19:34
  • $\begingroup$ There is no special meaning of convolution for image processing; it's the same as anywhere else. Also, the only difference between a convolution and a correlation is a sign reversal of one of the arguments, i.e.$f(x+h)$ vs. $f(x-h)$. Here is a good answer for a similar question that might help clear things up for you. $\endgroup$ – AnonSubmitter85 Dec 20 '14 at 19:47
  • $\begingroup$ Could you please check my updated original question? $\endgroup$ – user4205580 Dec 21 '14 at 20:48
  • $\begingroup$ @user4205580 Have you tried writing out the equation for pixel X? If you do, you'll see that they are the same. Just remember that $P1 \ast P2$ will be $5 \times 5$ and not $3 \times 3$. $\endgroup$ – AnonSubmitter85 Dec 21 '14 at 23:35
  • $\begingroup$ P1 and P2 are just pixel locations. Did you mean kernel 1 and kernel 2? If yes, how is it possible that convolution of two 3x3 kernels gives a 5x5 kernel? $\endgroup$ – user4205580 Dec 22 '14 at 6:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.