# Gaussian blur - convolution algorithm

My program uses graphics convolution, an algorithm that processes pixels to make them round, soft and blurred. This particular algorithm is well-known, but its slowing down the operation of the whole program.

Can you suggest any improvements of this algorithm? I tried following from here, especially "ultimate solution" all the way to the bottom of that page, hoping to reduce the number of for loops one within another, but it did not work.

import perceptron.DoubleBuffer.ImageRenderContext;
import util.ColorUtility;
import java.awt.image.DataBuffer;

public final class Convolution {

DoubleBuffer buffer;
int[] d;
int s, h, e;
int[] temp;

/**
* Constructs new Convolution using the convolution degree and DoubleBuffer as input parameters.
*
* @param std
* @param b
*/
public Convolution(int std, DoubleBuffer b) {
s = 2 * std;
h = s / 2;
e = 256 / h;
d = new int[s];
buffer = b;
for (int i = 0; i < s; i++) {
d[i] = (int) (256 * gaussian(i - s / 2, std));
}
temp = new int[b.buffer.W * b.buffer.H];
}

/**
* Optimized power function. Poor quality?
*/
public static double power(final double a, final double b) {
final long tmp = (Double.doubleToLongBits(a) >> 32);
final long tmp2 = (long) (b * (tmp - 1072632447) + 1072632447);
return Double.longBitsToDouble(tmp2 << 32);
}

/**
* Optimized exponent function with little benefit.
*/
public static double exponent(double val) {
final long tmp = (long) (1512775 * val + (1072693248 - 60801));
return Double.longBitsToDouble(tmp << 32);
}

/**
* Calculate the Gaussian for blurring.
*
* @param x
* @param sigma
* @return
*/
static double gaussian(float x, float sigma) {
return exponent(-.5 * (x * x) / (sigma * sigma)) / (sigma * 2.506628);
//return exponent(-.5 * pow(x / sigma, 2)) / (sigma * sqrt(2 * PI));
//return exp(-.5 * pow(x / sigma, 2)) / (sigma * sqrt(2 * PI)); // actual equation
}

/**
* Process the loaded buffer (image).
*
* @param amount
*/
public void operate(int amount) {

ImageRenderContext source = buffer.output;
DataBuffer sourcebuffer = buffer.output.data_buffer;
DataBuffer destbuffer = buffer.buffer.data_buffer;

if (buffer.convolution != 0) {

int W = buffer.output.W;
int H = buffer.output.H;
int Hp = H - h;
// Do X blur
int i = 0;
for (int y = 0; y < H; y++) {
for (int x = 0; x < W; x++) {
int Y = 0, G = 0;
for (int k = 0; k < s; k++) {
int c = source.get_color_for_convolution.getColor(x + k - h << 8, y << 8);
int w = d[k];
Y += w * (c & 0xff00ff);
G += w * (c & 0x00ff00);
}
temp[i++] = (0xff00ff00 & Y | 0x00ff0000 & G) >> 8;
}
}
// Do Y blur
i = 0;
int notamount = 256 - amount;
for (int y = 0; y < h; y++) {
for (int x = 0; x < W; x++) {
int Y = 0, G = 0;
for (int k = 0; k < s; k++) {
int y2 = (y - h + k + H) % H;
int c = temp[x + W * (y2)];
int w = d[k];
Y += w * (c & 0xff00ff);
G += w * (c & 0x00ff00);
}
int c1 = (0xff00ff00 & Y | 0x00ff0000 & G) >> 8;
int c2 = sourcebuffer.getElem(i) << 1;
int r = ((c2 >> 16) & 0x1fe) - ((c1 >> 16) & 0xff);
int g = ((c2 >> 8) & 0x1fe) - ((c1 >> 8) & 0xff);
int b = ((c2) & 0x1fe) - ((c1) & 0xff);
r = r < 0 ? 0 : r > 0xff ? 0xff : r;
g = g < 0 ? 0 : g > 0xff ? 0xff : g;
b = b < 0 ? 0 : b > 0xff ? 0xff : b;
c2 = (r << 16) | (g << 8) | (b);
c2 = ColorUtility.average(c1, amount, c2, notamount);
destbuffer.setElem(i++, c2);
}
}
for (int y = h; y < Hp; y++) {
for (int x = 0; x < W; x++) {
int Y = 0, G = 0;
for (int k = 0; k < s; k++) {
int c = temp[x + W * (y - h + k)];
int w = d[k];
Y += w * (c & 0xff00ff);
G += w * (c & 0x00ff00);
}
int c1 = (0xff00ff00 & Y | 0x00ff0000 & G) >> 8;
int c2 = sourcebuffer.getElem(i) << 1;
int r = ((c2 >> 16) & 0x1fe) - ((c1 >> 16) & 0xff);
int g = ((c2 >> 8) & 0x1fe) - ((c1 >> 8) & 0xff);
int b = ((c2) & 0x1fe) - ((c1) & 0xff);
r = r < 0 ? 0 : r > 0xff ? 0xff : r;
g = g < 0 ? 0 : g > 0xff ? 0xff : g;
b = b < 0 ? 0 : b > 0xff ? 0xff : b;
c2 = (r << 16) | (g << 8) | (b);
c2 = ColorUtility.average(c1, amount, c2, notamount);
destbuffer.setElem(i++, c2);
}
}
for (int y = Hp; y < H; y++) {
for (int x = 0; x < W; x++) {
int Y = 0, G = 0;
for (int k = 0; k < s; k++) {
int y2 = y - h + k;
if (y2 < 0) {
y2 = 0;
else if (y2 >= H) {
y2 = H - 1;
}
int c = temp[x + W * (y2)];
int w = d[k];
Y += w * (c & 0xff00ff);
G += w * (c & 0x00ff00);
}
int c1 = (0xff00ff00 & Y | 0x00ff0000 & G) >> 8;
int c2 = sourcebuffer.getElem(i) << 1;
int r = ((c2 >> 16) & 0x1fe) - ((c1 >> 16) & 0xff);
int g = ((c2 >> 8) & 0x1fe) - ((c1 >> 8) & 0xff);
int b = ((c2) & 0x1fe) - ((c1) & 0xff);
r = r < 0 ? 0 : r > 0xff ? 0xff : r;
g = g < 0 ? 0 : g > 0xff ? 0xff : g;
b = b < 0 ? 0 : b > 0xff ? 0xff : b;
c2 = (r << 16) | (g << 8) | (b);
c2 = ColorUtility.average(c1, amount, c2, notamount);
destbuffer.setElem(i++, c2);
}
}

} else {
buffer.buffer.data_buffer = buffer.output.data_buffer;
}
}
}


Naming naming naming

Your code is very intimidating - it is filled with single letter variable and members (s,h,e,d...). Those which are not single letter are generic and unhelpful (temp, buffer, notamount...). This makes your code very unreadable.

You also use a lot of literal numbers (2, 256, 1072632447, 60801...) which make no sense to a person who is not familiar with your algorithm. Use constants to make your code more readable.

If you want a serious code review, you must make your code readable, break large methods (operate) into smaller ones, etc.

• Thanks buddy! I am now the sole developer of Perceptron and I make my own unholy naming convention that I picked up from the days of my unprofessional involvement in C++. This portion of the code originates from the original author's effort made at his college. In one hand, it is recognizable code offered through computer courses. That's what needs evolution. On the other hand, some details are peculiar, because the pixels are stored as integer numbers in a one-dimensional array. Bitwise operators are a speedup. Optimized functions require long explanation. – GianniTee Feb 20 '14 at 19:00
• Convolution: of function with function. So, Gauss's function gives the bell-shaped curve return exponent(-.5 * (x * x) / (sigma * sigma)) / (sigma * 2.506628); in the simplified form. The other function is the pixel and its neighborhood. We apply Gauss curve to spread out each pixel to make it fuzzy. Seems detrimental, but in a program where chaos makes visual quality worse, pixel interpolation (rounding of pixels, and a separate issue) and convolution (this issue) are important. Constructor makes a lookup table, and std = 1 is the convolution degree. – GianniTee Feb 20 '14 at 19:13
• The integer representations of the coordinates are integers multiplied by 256. The format uses 256=1.0, so the actual pixel value is X/256. The extra 8 bits allow the interpolation without using floating point. – GianniTee Feb 20 '14 at 19:14
• Bitwise operations docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.19 – GianniTee Feb 20 '14 at 19:22
• @GianniTee, you should refactor your code, so that anyone who reads it, and is unfamiliar with the algorithm, could find his hands and feet... organize your code to bite-sized methods, with meaningful names, and with good use of variable and constant names. You are more than welcome to use bitwise operations, and any other feature of the language - but guide your reader through it. (don't explain what it is, but rather how do you use it). – Uri Agassi Feb 20 '14 at 19:24
1. I think the custom power/exponent methods are a probably waste of time when Math.pow and Math.exp would do just as well in this context.

2. The X/Y passes can be identical except the direction the bell curve is applied in. I'm assuming the extra passes are to handle the edges, but I think you might come out ahead by just doing 2 passes and perform clipping as you go.

3. I think I see some bit-hacking tricks to avoid some divides after going through the inner multiplication loops. I'm not convinced that doing this and going through all the averaging stuff is going to be faster than just doing two simple passes using multiples in the inner loop and 3 integer divides when the loop is complete.

4. Some multiplies can also be eliminated when writing to the temp array by making another array containing the offsets for each row. Like this:

temp = new int[w * h];
row = new int[h];

// make row offsets
for(int i = 0; i < h; i++)
row[i] = w * i;

// write a pixel
temp[x + row[y]] = color;