 |
 |
 |
 |
| Original | 1 pass | 2 passes | 3 passes |
Blurring is a very powerful operation used in image processing and procedural texture generation. Blurs involve calculating weighted averages of areas of pixels in a source image for each pixel of the final blurred image. Computing these weighted averages can be very expensive. For example, to create a blurry image you may need to touch hundreds of pixels for every pixel that you output. In this text, I'll show you some tricks for performing blurs very quickly. These tricks are employed in the blur operator in the tg texture generator.
First let's take a look at a simple blurring algorithm:
function Blur (source, dest, radius) {
for (y = 0; y < height; ++y) {
for (x = 0; x < width; ++x) {
total = 0
for (ky = -radius; ky <= radius; ++ky)
for (kx = -radius; kx <= radius; ++kx)
total += source(x + kx, y + ky)
dest(x, y) = total / (radius * 2 + 1) ^ 2
}
}
}
This function blurs a source image and places the result in the destination image. A parameter of the function is the blur radius to use. This determines the size of the area of source pixels that is averaged for each blurred destination pixel.
Instead of just computing the average, many blurs use a weight for each pixel. By using weights you can give more emphasis to the pixels near the center of the summed area and achieve a more attractive blur. Since we're focused on size and speed we'll stick with just averaging and use multiple passes to achieve different quality levels.
Original 1 pass 2 passes 3 passes
This simple blur algorithm works, but because of the four nested for loops, it is very slow. It's running time is on the order of width * height * radius2.
Ok, the first trick we'll use to achieve a faster blur is to separate the function into horizontal and vertical parts. By this I mean first blurring horizontally along the rows then taking the resulting image and blurring it vertically along the columns.
Original Horizontal pass Vertical pass
function BlurHorizontal (source, dest, radius) {
for (y = 0; y < height; ++y) {
for (x = 0; x < width; ++x) {
total = 0
for (kx = -radius; kx <= radius; ++kx)
total += source(x + kx, y)
dest(x, y) = total / (radius * 2 + 1)
}
}
}
function BlurVertical (source, dest, radius) {
for (x = 0; x < width; ++x) {
for (y = 0; y < height; ++y) {
total = 0
for (ky = -radius; ky <= radius; ++ky)
total += source(x, y + ky)
dest(x, y) = total / (radius * 2 + 1)
}
}
}
function Blur (source, dest, radius) {
BlurHorizontal(source, temp, radius)
BlurVertical(temp, dest, radius)
}
By separating the blur into horizontal and vertical passes we've reduced the number of source pixels touched for each destination pixel from (2 * radius + 1)2 to 2 * radius + 1. This brings the order of the algorithm down to width * height * radius. This is great, but we can do even better.
At each pixel we're summing the blur radius pixels before and after it. If you think carefully, you realize that a lot of work is being repeated. For example let's say the radius is 2 and we're calculating pixel number 4. We have to calculate: p2 + p3 + p4 + p5 + p6. Then at pixel number 5 we calculate p3 + p4 + p5 + p6 + p7. Then at pixel number 6 we calculate p4 + p5 + p6 + p7 + p8. A lot of the terms are the same. This becomes easy to reason about if you think of a window of size radius * 2 + 1 moving across the row of pixels. All the pixels inside the window get summed at each step. As the window moves from one pixel to the next, the left-most pixel in the window leaves and a new pixel enters on the right. So, instead of summing all the pixels in the window at each step we can just subtract the pixel leaving the window and add the pixel entering the window.
function BlurHorizontal (source, dest, radius) {
for (y = 0; y < height; ++y) {
total = 0
// Process entire window for first pixel
for (kx = -radius; kx <= radius; ++kx)
total += source(kx, y)
dest(0, y) = total / (radius * 2 + 1)
// Subsequent pixels just update window total
for (x = 1; x < width; ++x) {
// Subtract pixel leaving window
total -= source(x - radius - 1, y)
// Add pixel entering window
total += source(x + radius, y)
dest(x, y) = total / (radius * 2 + 1)
}
}
}
Here BlurHorizontal has been updated to sum across the full window only for the first pixel of each line. Every other pixel on the line just needs a subtract and an add to update the window total. BlurVertical can be updated in exactly the same way. These changes bring the order of the algorithm down to width * height + radius * (width + height) and we now have a fast blurring function that can handle large radii with ease.
Having both a BlurHorizontal and BlurVertical function can be expensive in terms of code size for intros. To reduce code size you can drop the BlurVertical and just add a transpose function.
function Transpose (image) {
for (y = 0; y < height; ++y)
for (x = y + 1; x < width; ++x)
swap(image(x, y), image(y, x))
}
function Blur (source, dest, radius) {
BlurHorizontal(source, temp, radius)
Transpose(temp)
BlurHorizontal(temp, dest, radius)
Transpose(dest)
}
The Transpose function is much smaller than BlurVertical and can be reused as another (albeit weak) texture generation operation.
For more interesting articles please visit: blackpawn texts.