Thursday, February 19, 2015

Combining Convolution Kernels

So not only can you, if you get rid of the idea of the center of a convolution kernel and always write the results into the corner. Allowing you to perform the operation in the same memory space, you current reside in. But, you can also COMBINE the convolution kernels before hand.

For example:

private static final int[][] twoboxblurs = new int[][]{
        { 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 }
    };
 
Applies the same thing as two box blurs (assuming there was no dividing error for the first time). It's the number of times each of those pixels down and to the right plays a role in the result. So that's the combination of:

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

and

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

Since each pixel would add a pixel each time to all the pixels down and to the right. You can get the sum of the them combined and properly expand out the kernel. Since you're not looking for data you won't already have you can do such a thing.

You can use the source code here:
http://pastebin.com/bk0A2Z5D

For a convolution that applies without memory foot print. It also means you can just link the results together. The pixel 2 over and 1 down, needs 1 copy of the pixel 2 over and 1 down from it. Recursive call all those pixels and you're good.

This is why doing a blur and then an emboss is different than emboss then blur. The problem here is that the way convolution is done is wrong. I was busy trying to figure out clever ways to do a convolution of an image in the same space as the image memory and came across a solution. That you can always do a convolution in the same memory footprint if and only if, the "center pixel" is located in the upper left corner. And then you iterate right to left, top to bottom. So long as you're not requiring non-overwritten data from the area above or to your left, this is fine.

Now, how this gets to your problem. Removing the dependency on the previous pixels means that you can not only do it in the same memory but merge kernels. If you use convolution with the results pixel located in the upper left, then it is the case that pixel X doesn't need the location of that pixel, any pixels that are going to be used for the convolution are located down and to the right, so it is the case that you can create the correct answer by performing both kernels at the same time and putting them into that results pixel. Which can be done by way of a kernel.

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.

As there is no longer dependency on previous pixels.

The problem isn't with the kernels but with how it's always implemented where you place the results in the middle of the field. I'm not sure why this is historically but really it would be easier to just shift the pixels over and down by one if it was extremely required, after the fact.

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

Update: Eh, not really that cool. You can totally get the same answer faster doing it with the smallest kernels you have. 9 + 9 < 25. So it's still faster to blur than sharpen.

No comments: