12.3.3 Convolutions Using the Accumulation Buffer

 

The convolution operation may be implemented using the accumulation buffer. The input image is stored in the color buffer and read by the glAccum() function. The output image is built up in the accumulation buffer. For each kernel entry G[i][j], we translate the input image by (-i, -j) from its original position. The translation may be accomplished using the glCopyPixels() command. We then accumulate the translated image using the command glAccumGL_ACCUM, G[i][j](GL_ACCUM, G[i][j]). width * height translations and accumulations must be performed.

Here is an example of using the accumulation buffer to convolve using a Sobel filter, commonly used to do edge detection. This filter is used to find horizontal edges, and is defined as:

Since the accumulation buffer can only store values in the range (-1..1), we first modify the kernel such that at any point in the computation the values do not exceed this range. Assuming the input images values are in the range (0..1), the modified kernel is:

The operations needed to apply the filter are:

1. Draw the input image
2. glAccumGL_LOAD, 1/4(GL_LOAD, 1/4)
3. Translate the input image left by one pixel
4. glAccumGL_ACCUM, 2/4(GL_ACCUM, 2/4)
5. Translate the input image left by one pixel
6. glAccumGL_ACCUM, 1/4(GL_ACCUM, 1/4)
7. Translate the input image right by two pixels and down by two pixels
8. glAccumGL_ACCUM, -1/4(GL_ACCUM, -1/4)
9. Translate the input image left by one pixel
10. glAccumGL_ACCUM, -2/4(GL_ACCUM, -2/4)
11. Translate the input image left by one pixel
12. glAccumGL_ACCUM, -1/4(GL_ACCUM, -1/4)
13. Return the results to the frame buffer (glAccumGL_RETURN, 4(GL_RETURN, 4))

In this example, each pixel in the output image is the combination of pixels in the 3 by 3 pixel square whose lower left corner is at the output pixel. At each step, the image is shifted so that the pixel that would have been under the kernel element with the value used is under the lower left corner. As an optimization, we ignore locations where the kernel is equal to zero.

A general algorithm for the 2D convolution operation is:

Draw the input image
for (j = 0; j < height; j++) {
  for (i = 0; i < width; i++) {
    glAccum(GL_ACCUM, G[i][j]*scale);
    Move the input image to the left by 1 pixel
  }
  Move the input image to the right by width pixels
  Move the input image down by 1 pixel
}
glAccum(GL_RETURN, 1/scale);

scale is a value chosen to ensure that the intermediate results cannot go outside a certain range. In the Sobel filter example, scale = 4. Assuming the input values are in (0..1), scale can be naively computed using the following algorithm:

float minPossible = 0, maxPossible = 1;
for (j = 0; j < height; j++) {
  for (i = 0; i < width; i++) {
    if (G[i][j] < 0) {
       minPossible += G[i][j];
    } else {
       maxPossible += G[i][j];
    }
  }
}
scale = 1.0 / ((-minPossible > maxPossible) ? 
               -minPossible : maxPossible);

Since the accumulation buffer has limited precision, more accurate results could be obtained by changing the order of the computation and computing scale accordingly. Additionally, if the input image can be constrained to a smaller range, scale can be made larger, which may also give more accurate results.

For separable kernels, convolution can be implemented using width + height image translations and accumulations. A general algorithm is:

Draw the input image
for (i = 0; i < width; i++) {
  glAccum(GL_ACCUM, Grow[i]);
  Move the input image to the left 1 pixel
}
glAccum(GL_RETURN, 1);
for (j = 0; j < height; j++) {
  glAccum(GL_ACCUM, Gcol[j]);
  Move the frame buffer image down by 1 pixel
}
glAccum(GL_RETURN, 1);

In this example, we have assumed that the row and column filters have been constructed such that the accumulation buffer values will never go out of range. For the general case, a scale value may be needed. More accurate results may be obtained if scale values are computed independently for the row and column steps. An accumulation buffer multiply in between the two steps may be required.