iki.fi/o

Circularly symmetric convolution and lens blur

Created by Olli Niemitalo on 2010-09-07, last modified 2013-02-24

This article describes approaches for efficient isotropic two-dimensional convolution with disc-like and arbitrary circularly symmetric convolution kernels, and also discusses lens blur effects.

Keywords: depth of field, circle of confusion, bokeh, circular blur, lens blur, hexagonal blur, octagonal blur, real-time, DOF

Gaussian function approach

The circularly symmetric 2-d Gaussian kernel is linearly separable; the convolution can be split into a horizontal convolution followed by a vertical convolution. This makes 2-d Gaussian convolution relatively cheap, computationally, and "Gaussian blur" has become, partially for this reason, a popular operation in image processing. No other circularly symmetric (isotropic) convolution kernel is linearly separable. But this is only true when the kernel is limited to real numbers. This section of the article introduces complex-valued convolution kernels that are both circularly symmetric and linearly separable, and goes on to show how these can be used to produce arbitrary circularly symmetric 2-d convolutions by 1-d convolutions, in contrast to the use of 2-d Fast Fourier Transform (FFT). Special focus is given to implementation of circular blur, or convolution with a solid disk, which is useful for simulation of bokeh (circle of confusion) of camera lenses with fully open apertures.

A Gaussian convolution kernel, used in Gaussian blur (black = -maximum value, grey = 0, white = maximum value)

To produce circularly symmetric 2-d convolution, the condition that the 1-d kernel function f must satisfy is f(\sqrt{x^2+y^2}) = f(x)\times f(y). The condition may be broken down into a magnitude condition and a phase condition that must both be satisfied. The magnitude condition reads |f(\sqrt{x^2+y^2})| = |f(x) \times f(y)| = |f(x)|\times|f(y)| , meaning that the kernel must have a Gaussian function as its magnitude function. Because in multiplication of complex numbers the phases are summed, the phase (argument) condition reads \theta(\sqrt{x^2+y^2}) = \theta(x)+\theta(y), modulo 2\pi, with the shorthand \theta(x) = \arg(f(x)). The only family of functions to satisfy this is \theta(x) = a x^2. The kernel function can be constructed as the product of a Gaussian function, here called the envelope, and a complex phasor with x^2 as its argument. In one dimension these kernels have the form e^{-a x^2} e^{i b x^2} = e^{- a x^2 + i b x^2} = e^{(- a + b i) x^2}, where i is the imaginary unit, x is the spatial coordinate, a is the spatial scaling constant of the envelope, and b is the spatial scaling constant of the complex phasor. In two dimensions the form is e^{- a x^2 + i b x^2} e^{- a y^2 + i b y^2} = e^{- a (x^2 + y^2) + i b (x^2 + y^2)} = e^{(- a + b i) (x^2 + y^2)}, y being the coordinate in the other dimension. These forms are not normalized to preserve average intensity in image filtering, but to give a value of 1 for x = 0, y = 0. Let's see what these look like.

The real part of a phased Gaussian kernel

The imaginary part of a phased Gaussian kernel

The real part of a phased Gaussian kernel of infinite spatial scale of the magnitude part, showing the phasing only

The imaginary part of the phased Gaussian kernel of infinite spatial scale of the magnitude part, showing the phasing only

Magnitude of a phased Gaussian kernel, identical to the plain Gaussian kernel

Arbitrary circularly symmetric shapes can be constructed by a weighted sum of the real parts and imaginary parts of complex phasors of different frequencies. Fourier series is the standard approach for such designs. These give a repetitive pattern, but the repeats could be diminished by adjusting the spatial scale of the envelope. As necessary, sloping of the envelope can be compensated for in the weights of the sum, but simultaneous optimization of both will give the best results, as it can take advantage of that the envelopes need not be the same for each of the component kernels.

Let's try a 5-component square wave approximation, designed manually with the Fourier series applet of Paul Falstad.

5-component equiripple square wave Fourier series

Real part of a square wave approximated by 5 phased Gaussian components of infinite spatial scale of the magnitude part.

The formula for this series is 0.54100\ +\ 0.66318\ \cos(x)\ -\ 0.20942\ \cos(3 x)\ +\ 0.10471\ \cos(5 x)\ -\ 0.08726\ \cos(7 x). A bit of scaling (by 0.9) and shifting (by -0.01) was then done to make the ripples go evenly around the zero level and to avoid values greater than 1.

This is a pretty good indicator of the capabilities of this approach. The weighted component kernels were:

Component 0

Component 1

Component 2

Component 3

Component 4

By lowering the spatial scale of the magnitude part of each component kernel, one gets a result like this:

First try on a circular convolution kernel

Not so bad! The halos would need to be eliminated, and the disk is also fading a bit toward the edges.

I searched for better circular kernels by global optimization with an equiripple cost function, with the number of component kernels and the transition bandwidth as the parameters. Transition bandwidth defines how sharp the edge of the disk is. The sharper it is, the more ringing there will be both inside and outside the disk. A transition bandwidth setting of 1 means that the width of the transition is as large as the radius of the disk inside. Below, 1-d component kernel formulas are given for a pass band spanning x \in -1..1 and a dual stop band spanning  x\ \in\ -1.2\ ..\ -1\ \cup\ 1\ ..\ 1.2.

Number of components: 1, transition bandwidth: 0.200000, ripple: ±0.232417. Component 0: (cos(x*x*1.624835) * 0.767583 + sin(x*x*1.624835) * 1.862321) * exp(-0.862325*x* x)

1-d view

Number of components: 2, transition bandwidth: 0.200000, ripple: ±0.075459. Component 0: (cos(x*x*5.268909) * 0.411259 + sin(x*x*5.268909) * -0.548794) * exp(-0.886528*x *x) Component 1: (cos(x*x*1.558213) * 0.513282 + sin(x*x*1.558213) * 4.561110) * exp(-1.960518*x* x)

1-d view of the components and their sum (magenta)

Number of components: 3, transition bandwidth: 0.200000, ripple: ±0.026297. Component 0: (cos(x*x*5.043495) * 1.621035 + sin(x*x*5.043495) * -2.105439) * exp(-2.176490*x *x) Component 1: (cos(x*x*9.027613) * -0.280860 + sin(x*x*9.027613) * -0.162882) * exp(-1.019306* x*x) Component 2: (cos(x*x*1.597273) * -0.366471 + sin(x*x*1.597273) * 10.300301) * exp(-2.815110* x*x)

1-d view of the components and their sum (cyan)

Number of components: 4, transition bandwidth: 0.200000, ripple: ±0.010843. Component 0: (cos(x*x*1.553635) * -5.767909 + sin(x*x*1.553635) * 46.164397) * exp(-4.338459* x*x) Component 1: (cos(x*x*4.693183) * 9.795391 + sin(x*x*4.693183) * -15.227561) * exp(-3.839993* x*x) Component 2: (cos(x*x*8.178137) * -3.048324 + sin(x*x*8.178137) * 0.302959) * exp(-2.791880*x *x) Component 3: (cos(x*x*12.328289) * 0.010001 + sin(x*x*12.328289) * 0.244650) * exp(-1.342190* x*x)

1-d view of the components and their sum (brown)

Close-up

Number of components: 5, transition bandwidth: 0.200000, ripple: ±0.004062. Component 0: (cos(x*x*1.685979) * -22.356787 + sin(x*x*1.685979) * 85.912460) * exp(-4.892608 *x*x) Component 1: (cos(x*x*4.998496) * 35.918936 + sin(x*x*4.998496) * -28.875618) * exp(-4.711870 *x*x) Component 2: (cos(x*x*8.244168) * -13.212253 + sin(x*x*8.244168) * -1.578428) * exp(-4.052795 *x*x) Component 3: (cos(x*x*11.900859) * 0.507991 + sin(x*x*11.900859) * 1.816328) * exp(-2.929212* x*x) Component 4: (cos(x*x*16.116382) * 0.138051 + sin(x*x*16.116382) * -0.010000) * exp(-1.512961 *x*x)

1-d view of the components and their sum (magenta)

Close-up

Close-up of the pass band

Close-up of the stop band

The last one of the above, with 5 component kernels, is good enough for most practical applications as the ripple is as small as 1/250, about as much as the least significant bit for 8-bits-per-channel graphics, so invisible in almost all situations. As the number of components is increased, the components have an increasingly large weighted amplitude, as much as 36 times their sum for the 5-component system. This may become a practical problem if one aims for convolution kernel shapes with sharp transitions. A construction via Fourier series would probably give better-behaving components, but require more components than abusing the Gaussian envelope for ripple control as seems to be the case in the above given composite kernels.

Here's a bonus, with 6 components:

Number of components: 6, transition bandwidth: 0.200000, ripple: 0.001918. Component 0: (cos(x*x*2.079813) * -82.326596 + sin(x*x*2.079813) * 111.231024) * exp(-5.14377 8*x*x) Component 1: (cos(x*x*6.153387) * 113.878661 + sin(x*x*6.153387) * 58.004879) * exp(-5.612426 *x*x) Component 2: (cos(x*x*9.802895) * 39.479083 + sin(x*x*9.802895) * -162.028887) * exp(-5.98292 1*x*x) Component 3: (cos(x*x*11.059237) * -71.286026 + sin(x*x*11.059237) * 95.027069) * exp(-6.5051 67*x*x) Component 4: (cos(x*x*14.810520) * 1.405746 + sin(x*x*14.810520) * -3.704914) * exp(-3.869579 *x*x) Component 5: (cos(x*x*19.032909) * -0.152784 + sin(x*x*19.032909) * -0.107988) * exp(-2.20190 4*x*x)

The 1-d composite kernel can be truncated to range x \in -(\textrm{pass band radius + transition bandwidth}\ ..\ \textrm{pass band width + transition bandwidth}). This only necessitates a stop band equiripple condition for |x| \in \textrm{pass band radius + transition bandwidth}\ ..\ \sqrt{2}(\textrm{pass band radius+ transition bandwidth}) to ensure a flat stop band in the corners of the 2-d convolution kernel square. However, at least for up to the above given 5th order composite kernel, the stop band ripples start to slope out already within that range, so no savings can be made.

Let's see the 5-component circular blur in action.

The standard test image, Lena

Lena after 5-component circular blur with a disk diameter of 128 pixels and an additional transition band of 25.6 + 25.6 pixels . (contrast adjusted manually)

Gaussian blur of similar size

With halved blur disk radius, 32 pixels (contrast set manually)

Gaussian blur of similar size

With 16 pixels disk radius (contrast set manually)

Gaussian blur of similar size

The circular blur here is the weighted sum of the real and imaginary parts of the 5 component convolutions.

Let's try another image, one which will better show the blur disks.

Hubble Deep View

Hubble Deep View after 5-component circular blur (arbitrary contrast)

With halved radius, 32 pixels

disk radius halved once more, now 16 pixels (the bands at the top and at the bottom are due to some programming bug)

Looks like an out-of-focus camera, doesn't it?

Recursive approximations

The examples presented above were done with 1-d finite impulse response (FIR) filters of which I now have a FFT-based implementation. More efficient would be to use identical pairs of complex 1-d causal and anti-causal infinite impulse response (IIR) filters to achieve a symmetric composite filter. Early results:

First attempt at tail-truncated parallel poles approximation of phased Gaussian components of a 3-component composite kernel (on the right). 3 complex poles were used for each direction, employing the structure: (left+right)*(up+down) and identical coefficient sets for all directions. The coefficients used have not yet been re-optimized to increase the resulting kernel quality directly.

The "exact" composite kernel. Note that the ringing outside the disc is suppressed in the approximation (on the left) due to tail truncation. The transition band spans -1.2..-1 and 1..1.2.

The above first attempt filter is quite heavy, about 110 complex multiplications (some of which involve real numbers) per color channel per pixel. But it is independent of the size of the blur (disregarding boundary conditioning that may add a penalty proportional to the radius times the number of edge pixels in the image).

Perhaps circular blur is not the best use for the phased Gaussian kernels, as no sharp edges can be achieved. How about constructing an airy disc for anisotropic low-pass filtering of the image in a manner that gives an equal upper frequency limit for features in diagonal, horizontal, vertical, or any direction? Food for thought...

Circular blur using prefix sums and summed area tables

Circular blur done using the phased gaussian kernels is not perfect because it has the transition band. A completely different approach would be to calculate each blurred output pixel separately by summing the pixels that fall within the disk radius from the position of the pixel. There is a very efficient way to do this. The area of the disk can be subdivided into a minimum number of rectangular pieces and a summed area table can be used to efficiently calculate the sum of pixels within each rectangle. Here is an illustration of the idea:

A circle packed with a small number of rectangles.

Kyle McDonald has been working on the same problem and shows a more efficient packing with his Processing application:

A more efficient packing by Kyle McDonald, requiring for this particular circle 60 summed area table lookups (or alternatively a total of 40 summed area table or sum table lookups).

A somewhat simpler way would be to subdivide the circle into one-pixel-height strips. The sum of the pixel values of a strip could be calculated from the prefix sum over the length of each column, requiring only two lookups per strip. The number of rows would be roughly the diameter of the circle, and the number of lookups roughly four times the radius, or 4r.

By combining the use of summed area tables and horizontal and vertical prefix sums we get a rather boring-looking hybrid approach that appears to be the most efficient:

A packing requiring less lookups than McDonald's if both summed area tables and row and column prefix sums are used. For this particular circle a total of 32 summed area table or prefix sum lookups are required.

For large r, the hybrid approach takes about (8-\frac{4}{\sqrt{2}})r \approx 2.34\ r lookups: 4 for the rectangle (from a summed area table) but dominated for large r by 2 for each stripe (from horizontal or vertical prefix sum). In comparison, Kyle McDonald's approach takes about (12-4\sqrt{5})r \approx 3.06\ r table lookups with both summed area tables and prefix sums available and about (16-\frac{24\sqrt{5}}{5})r \approx 5.27\ r table lookups with only the summed area table available. The latter result is identical for the hybrid approach. If the whole image is convolved with a disc of constant radius, the center rectangle in the hybrid approach can be done with a constant complexity box blur and a summed area table will not be needed, relieving requirements for the bit depth used in the calculations.

To get an anti-aliased edge for the circle, the edge pixels can be summed or subtracted with weights separately, doable in the ready-for-prefix-sum representation. The number of pixels that should receive anti-aliasing is about (4\sqrt{2} + 16 - \frac{24\sqrt{5}}{5})r \approx 10.9\ r, increasing the total cost of the algorithm to (24 - \frac{24\sqrt{5}}{5})r \approx 13.27\ r. Each weight will be shared by 8 edge pixels, which may give some computational savings. In conclusion, anti-aliased or not, the complexity of this way of blurring will be proportional to the radius of the disc times the number of pixels in the image. The decompositions (lookup recipes) of different size blurs could be stored in tables, which would allow also the use of a depth map to blur different parts of the image with a different disk size.

Alternatively to exact antialising, one could approximate the longer monotonic antialias gradations as linear, by use of two horizontal prefix sum passes in series and two vertical prefix sum passes in series. The slope of each linear section would be thrown in first, then after calculation of the first prefix sum, the constant term of the linear section would be added, along with a value that terminates the section. Either of these would coincide with the values that define where the flat section of the disc starts for that horizontal or vertical stripe. The method could be made more accurate by increasing the number of linear sections, perhaps up to two per monotonous gradation.

If different size blurs are used in the same image, then one decision must be made on how the result should look: whether the blur scatters or gathers. Let's demonstrate with a square box blur, increasing the blur size towards the top of the image:

Input image for box blur, just a single bright pixel on black background. Size of the box blur will vary by row as indicated by the width of the blue area

Scattering box blur with a width of 5, as designated for the position of the bright input pixel, scatters the intensity of the pixel to the surrounding 5 times 5 pixel area.

Gathering box blur resulting from outputting at each position the average intensity of surrounding input pixels from an area the size of which is dictated by the output position.

With a variable blur kernel, scattering blur is more correct, because it preserves average image intensity, unlike gathering blur. With smooth blur size gradations, gathering blur should also look okay.

If the kernel is constant, blurring can be described mathematically by convolution of the input image by the blur kernel: o = i*K, where o is the output image, i is the input image and K is the blur kernel. There are two ways to directly implement the convolution: In the scattering way, first the output image is cleared to zero, and then for each input pixel, a copy of the kernel K is multiplied by the intensity of the input pixel, spatially shifted to the position of the input pixel, and added to the output image. In the gathering way each output pixel is formed by shifting a copy of the kernel reversed along each axis, to the position of the output pixel, and setting the output pixel to the sum of products of the pixel intensities in the shifted and reversed kernel and the input image. If the same kernel is used throughout the image, both ways of doing convolution will be identical. But if the size of the blur varies, we must acknowledge whether we do a scattering or a gathering convolution by K. We denote these by \hat{*} for a scattering and \check{*} for a gathering convolution by the variable kernel. The mnemonic is that the arrowhead points away to indicate scattering.

We define the order of calculation of written formulas to be from left to right with the exception that multiplication and convolution are calculated first and addition and subtraction last. The convolution operator * has the following algebraic properties :

  • Commutativity: A*B = B*A
  • Associativity: A*B*C = A*(B*C)
  • Distributivity: A*C+B*C = (A+B)*C
  • Associativity with scalar multiplication: a(A*B) = aA*B = A*(aB), where a is a constant.

With scattering convolution \hat{*} and gathering convolution \check{*} by a variable kernel we have a drastically limited set of algebraic properties:

  • Distributivity: A\ \hat{*}\ C+B\ \hat{*}\ C = (A+B)\ \hat{*}\ C for scattering convolution and A\ \check{*}\ C+B\ \check{*}\ C = (A+B)\ \check{*}\ C for gathering convolution.
  • Distributivity, again: C\ \hat{*}\ A+C\ \hat{*}\ B = C\ \hat{*}\ (A+B) for scattering convolution and C\ \check{*}\ A+C\ \check{*}\ B = C\ \check{*}\ (A+B) for gathering convolution. This can be used for simplification of the calculation if both A and B are sparse, because then (A+B) will also be sparse and some coincident values may cancel.
  • Associativity with scalar multiplication: a(A\ \hat{*}\ B) = aA\ \hat{*}\ B = A\ \hat{*}\ (aB) for scattering convolution and a(A\ \check{*}\ B) = aA\ \check{*}\ B = A\ \check{*}\ (aB) for gathering convolution.

When utilizing a summed area table, the constant-kernel calculation can be written as: o = i*S_{xy}*K_{xy} = i*K_{xy}*S_{xy}, where o is the output image, i is the input image, S_{xy} is such a function that convolution with it gives the summed area table, and K_{xy} is the sparse representation of the blur kernel that gives the blur kernel if convolved with S_{xy} (or vice versa). It turns out that with a variable blur kernel, scattering convolution requires the scattering-friendly order of calculation: o = i\ \hat{*}\ K_{xy}*S_{xy}, and gathering convolution the gathering-friendly order o = i*S_{xy}\ \check{*}\ K_{xy}. Using the wrong order with a variable blur kernel would give rather unpredictable results and is not recommended. As a rule, if the kernel is not constant, scattering convolution should operate directly on the input image and gathering convolution should not be followed by further convolutions.

The computational complexity of the whole calculation is independent of the order of convolutions. Convolving something with S_{xy} is cheap. It is also cheap to convolve something with K_{xy}, because it is sparse, that is, zero in all but a few places, amounting to a sum of shifted copies of the function that is being convolved. Rather than discussing the number of table lookups, the computational complexity of the blur can be described by the number of non-zero elements in the sparse representation of its kernel.

For box blur, the order of calculation does not affect the computational complexity, but if we use (for example to calculate circular blur) in addition to a summed area table also prefix sums, calculable by convolution by S_x for the horizontal prefix sum and by S_y for the vertical prefix sum, and noting that S_{xy} = S_x*S_y, we can optimize the gathering-friendly calculation o = i*S_x*S_y\ \check{*}\ K_{xy} + i*S_x\ \check{*}\ K_x + i*S_y\ \check{*}\ K_y, where \{K_x, K_y, K_{xy}\} is a sparse representation of the blur kernel, from 4 prefix sums and 4 steps in a fully parallelized implementation to 3 prefix sums and 4 steps, noting that the term i*S_x appears twice and need only be calculated once. For the scattering-friendly calculation o = i\ \hat{*}\ K_{xy}*S_x*S_y+ i\ \hat{*}\ K_x*S_x + i\ \hat{*}\ K_y*S_y = i\ \hat{*}\ K_{x}*S_x + (i\ \hat{*}\ K_y + i\ \hat{*}\ K_{xy}*S_x)*S_y, we can get from 4 prefix sums and 4 steps to 3 prefix sums and 5 steps by utilizing distributivity of convolution. A mixed-order calculation o = ((i*S_x)*K_{xy} + i*K_y)*S_y + (i*S_x)*K_x can be implemented with 2 prefix sums and 5 steps. With a constant kernel, any of the orderings could be used.

Hexagons

On a hexagonal grid, kernels shaped like a regular hexagon are cheap:

A regular hexagon made from two columns with ends oriented along two of the axes.

We are quite close to a circle already, with a constant number of non-zero elements in the kernel representation, but let's side-track for a bit and think that we actually want a hexagonal lens blur kernel, because for sure some cameras have 6 aperture blades. So we could create hexagonal blur by resampling from the normal square grid (lattice) to a hexagonal grid, doing the convolution with the hexagonal kernel, and then resampling back to the square grid. All three steps can be done in a constant number of computational operations per image pixel.

The gathering-friendly version of unantialiased hexagonal kernel convolution can be written as o = i*S_1*S_2\ \check{*}\ K_{12} + i*S_1*S_3\ \check{*}\ K_{31}, where S_1, S_2, and S_3 are such functions that if one convolves with one of them, the result is a prefix sum along the numbered axis (the columns in the above figure are oriented along axis 1), and \{K_{12}, K_{31}\} is a sparse representation of the hexagonal convolution kernel with a total of 8 non-zero elementsThe calculation involves 3 prefix sums and 4 steps by reusing the factor i*S_1. The scattering-friendly version o = (i\ \hat{*}\ K_{12}*S_2 + i\ \hat{*}\ K_{31}*S_3)*S_1 takes also 3 prefix sums and 4 steps.

For integer size hexagons (measured from center to corner), the hexagonal grid naturally avoids aliasing. To make things perfect, we want antialiasing of non-integral-size hexagons. That can be done by cross-fading between two hexagons that have a size difference of 1 measured from center to corner on the hexagonal grid. The anti-aliased non-integer size hexagon has 16 non-zero elements in the 2-component sparse representation:

An anti-aliased hexagon made by cross-fading between two hexagons of successive integral sizes

Condat, Forster-Heinlein, and Van de Ville show in their paper "H2O: Reversible Hexagonal-Orthogonal Grid Conversion by 1-D filtering" that it is possible to shear the coordinate system a few times to change between the hexagonal and the square (orthogonal) grid. In fact, only two shear operations are needed to move from the square grid to hexagonal:

Conversion from a square grid (yellow) to hexagonal (red) can be done by two shearing steps. The image shows the centers of four neighboring pixels in the square grid (dots), then shearing (along the blue line from dot to box) the rows horizontally by amount a (multiplied by the row index), followed by shearing of each tilted column along their direction by a fraction b of the distance between the tilted column pixels (along the blue line from a box to a cross), yielding with the correct parameters a and b an equal distance between the pixel centers that originated from (0, 0), (0, 1) and (1, 0)

The shear amounts that give equal distances between neighboring pixels as in a proper hexagonal grid, are for the first shear, from the square coordinate system to the intermediate one: a = \frac{12^{1/4}}{2}-\frac{\sqrt{2}\ 3^{3/4}}{6}\approx 0.3933198931 and for the second shear, from the intermediate to the hexagonal coordinate system: b = \frac{1}{2}-\frac{\sqrt{2}\ 3^{3/4}}{4}+\frac{12^{1/4}}{4}\approx 0.1593749806 . Shearing can be implemented by allpass fractional delay filters which are reversible by doing the filtering to the opposite direction. Approximating the shear amounts with rational values a = \frac{2}{5} = 0.4 and b = \frac{1}{6} \approx 0.1667, the number of different filter coefficient sets can be limited to 2 + 3 by abusing negative fractional delays, the fact that the fractional part of the delays will repeat the sequence \{0, \frac{2}{5}, \frac{4}{5}, \frac{1}{5}, \frac{3}{5}\} for successive rows and \{0, \frac{1}{6}, \frac{2}{6}, \frac{3}{6}, \frac{4}{6}, \frac{5}{6}\} for successive tilted columns, and that zero delay needs no fractional delay filter.

The cost of the rational approximation is a slight deformation of the convolution kernel. To assess the amount of distortion due to the rational approximation, we have a look at the triangle between the centers of neighboring sample points in the approximately hexagonal grid to see if it is close to an equilateral triangle:

The triangle connecting the centers of neighboring pixels on the approximately hexagonal grid. Approximate side lengths (in square grid pixel widths) and corner angles are indicated.

The exact lengths of the sides of the triangle are \frac{\sqrt{1049}}{30} for the base, \frac{\sqrt{29}}{5} for the left side, and \frac{\sqrt{41}}{6} for the right side. The angles are within a degree from 60°, and side lengths differ from each other at most by 1.2 %, good enough to be a visually transparent approximation of an equilateral triangle. The base of the triangle is tilted 8.88° counterclockwise from the horizontal axis, the left side is tilted 21.80° clockwise from the vertical axis, and the right side is tilted 6.34° clockwise from the diagonal axis. This means that the resulting hexagonal blur will not be oriented along the vertical, the horizontal, or the diagonal axis of the square grid. This is good as a tilted blur is visually pleasing.

The rational approximation also gives an easy-to-trace opportunity for economically storing the hexagonally sampled image in memory, skipping two more samples from the beginning of every 5th row, and one more sample from the beginning of every 6th column. Whether taking advantage of this is advisable or not depends on how much overhead there will be from the more complicated way of addressing.

With variable-size blur, there is the disadvantage that if the blur sizes are given on a square grid, they need to be resampled as well, but only from square grid to hexagonal. In other aspects, the hexagonal blur algorithm is very appealing for real-time use.

But let's go back to circles:

A large round disc on a hexagonal grid, made from a hexagon, and stripes in three directions to fill in the gaps

The hexagonal grid is very efficient at covering the whole area of a circle with a maximally large hexagon and stripes. To assess the complexity, we must define the grid orientation to equate the radius of the circle in terms of pixel widths in the two coordinate systems. We choose for the hexagonal grid an orientation that gives at least as high resolution in all directions as a square grid:

A definition of a pixel width or step on a hexagonal grid

This differs from the tilted hexagonal grid orientation of the previously presented resampling method based on two shearing steps, but gives perhaps a more fair picture for a complexity analysis. On the hexagonal grid, for a large unantialiased solid circle with a radius r, the number of non-zero elements in the already presented 5-component kernel representation will be about (8\sqrt{3}-12)r \approx 1.86\ r, about 20 % less than with the square grid, but still proportional to the radius. For the benefit of the box blur and stripes, the difference in efficiencies will be offset by the additional work required with the hexagonal grid to do the resampling back and forth.

Octagons

A hexagon got us quite close to a circle, so an octagon should get us even closer. The regular octagon is also a shape that is familiar from camera apertures, and so has value as a blur kernel. An octagon can be created from sections that terminate at right or diagonal angles, and has a sparse representation in the usual square coordinate system if diagonal prefix sums are employed:

An octagon made from three columns with different end shapes: straight, south-east-diagonal and north-east-diagonal.

The scattering-friendly calculation goes o = i\ \hat{*}\ K_{xy}*S_x*S_y + i\ \hat{*}\ K_{y\nearrow}*S_\nearrow*S_y + i\ \hat{*}\ K_{y\searrow}*S_\searrow*S_y, for the sparse representation \{K_{xy}, K_{y\nearrow}, K_{y\searrow}\} with a total of 12 non-zero elements for hexagons that have corners at integer positions. Convolution by S_{\searrow} or by S_{\nearrow} equals calculating a prefix sum. The calculation can be optimized from 6 prefix sums and 5 steps to o = (i\ \hat{*}\ K_{xy}*S_x + i\ \hat{*}\ K_{y\nearrow}*S_\nearrow + i\ \hat{*}\ K_{y\searrow}*S_\searrow)*S_y with 4 prefix sums and 5 steps. The gathering-friendly calculation is o = i*S_y*S_x\ \check{*}\ K_{xy} + i*S_y*S_\nearrow\ \check{*}\ K_{y\nearrow} + i*S_y*S_\searrow\ \check{*}\ K_{y\searrow} with 4 prefix sums and 5 steps, reusing the term i*S_y.

For octagons that have the corners at integer coordinates, it suffices as antialiasing to set the diagonal edge pixels to half intensity. In the scattering-friendly approach, this can be done very easily by subtracting the for the most part already calculated (i\ \hat{*}\ K_{y\nearrow}*S_\nearrow + i\ \hat{*}\ K_{y\searrow}*S_\searrow)/2 from the output image, keeping the number of prefix sums at 4 and increasing the number of steps to 6. Cross-fading between such octagons gives a crude way of anti-aliasing for non-integer-size octagons and doubles the number of non-zero elements in the sparse representation to 24 non-zero elements.

A circle can be approximated using an octagon and horizontal, vertical, and diagonal stripes to fill in the empty spaces:

An octagon used as a starting point to fill a circle, followed by stripes in 4 directions.

The regular octagon is not the ideal choice as a starting point to fill a circle, because it takes more diagonal lines to fill in the same space compared to horizontal or vertical lines. Therefore, the diagonal portion of the hexagon should be shorter. Optimality can be reached by setting one of the corners of the hexagon close to coordinates (\frac{2\sqrt{5}}{5}r, \frac{\sqrt{5}}{5}r) \approx (0.8944271909\ r, 0.4472135954\ r), where r is the radius of the circle centered at (0, 0). For large r, the number of non-zero elements in the representation of the kernel will be about (8\sqrt{2}+8-8\sqrt{5})r \approx 1.43\ r. That is about 40 % less than with the box and stripes method, making the octagon a good starting point for large unantialiased circular blurs.

Source code

Source code for convolution using phased Gaussian kernels, and for optimization of kernel sets: phasegauss1.1.zip. The project is for Dev-C++, for Windows, but shouldn't need much work to compile elsewhere.

19 Comments »

  1. Oletko varma että olet oikealla alalla? ;)

    (lue: luovia matemaatikkoja ei ole ainakaan liikaa)

    Comment by Nti Aalto — 2010-09-07 @ 15:37

  2. This is really an amazing article but I am wondering if you can add the source code for it or you can send it to my email if you do not mind at tariq_0015@hotmail.com because I am really interested to modifay it to work in three 1d kernl instead of two 1d kernel to cover the rotation. Thank you

    Best Regard,

    Tariq

    Comment by Tariq — 2010-12-28 @ 04:10

  3. Great stuff, Olli!

    I've been trying to work out how to do convolution with a disk like this in a separable manner. Fascinating that it is possible as separable 1D FIRs, just by using complex numbers! Can you provide more details? For the discrete FIR, what is the formula for the complex-valued coefficients? The formulas you give for the various components appear to be just real-valued.
    For example, for the one-component version, it says:

    Component 0: (cos(x*x*1.624835) * 0.767583 + sin(x*x*1.624835) * 1.862321) * exp(-0.862325*x* x)

    Is there a missing 'i', i.e. sqrt(-1) somewhere? Otherwise, how exactly are complex numbers being used?

    Also, does your algorithm simply apply complex-valued 1D FIR horizontally, followed by another vertically, and the result is then real-valued again (i.e. no imaginary component)?

    Thanks,
    Matthew

    Comment by Matthew Jones — 2011-09-14 @ 01:46

  4. Matthew, I'm sorry that the article is (as of writing this reply) so vague in explaining how exactly the kernels are to be used. The complex kernel in one dimension x is:

    f(x) = cos(b*x*x) * exp(-a*x*x) + i * sin(b*x*x) * exp(-a*x*x).

    The component as written in your comment is a weighted sum of the real and imaginary parts of f(x):

    A*real(f(x)) + B*imag(f(x)) = (cos(b*x*x) * A + sin(b*x*x) * B) * exp(-a*x*x)

    You should be able to figure out a, b, A, and B from the presented kernels. What you would then do in practice is: 1. Convolve horizontally with f(x). 2. Convolve vertically with f(x). 3. For each pixel, multiply its real part by A, its imaginary part by B, and add them together, giving the real-valued output pixel. 4. If you have multiple components, sum the component outputs.

    Please let me know how it works out!

    I have been thinking that the algorithm could perhaps be changed from parallel component convolutions to serial. This would reduce memory usage as it would be possible to work "in place". (This would require recomputation of the presented kernels.)

    Comment by Olli Niemitalo — 2011-09-14 @ 03:24

  5. Excellent. Thanks for the info!

    As I understand it the memory usage isn't too bad anyway, because you don't need to store
    all the output components (the output from your step 3). Instead you can accumulate them into a single buffer, eg:

    Clear full-size accumulation buffer to zero
    For each component (step 4)
    For each row (step 1) do convolve into full-size temp buffer
    For each column (step 2) convolve the temp buffer into a temp column, combine real/imag (step 3) add results to accumulation buffer (step 4)

    Result is in accumulation buffer

    That would work, wouldn't it? It's a memory/speed tradeoff, avoids N buffers but instead processes the input data N times. Depending on context, could be faster anyway (e.g. because entire working set might fit in faster/cacheable memory).

    Thanks for info. I'm definitely going to try your method!

    Comment by Matthew Jones — 2011-09-14 @ 10:44

  6. p.s. I meant this:

    Clear full-size accumulation buffer to zero
    For each component (step 4) DO
    {
    (1) For each row (step 1) do convolve into full-size temp buffer
    (2) For each column (step 2) convolve the temp buffer into a temp column, combine real/imag (step 3) add results to accumulation buffer
    }

    The nesting was a bit unclear.
    Result is in accumulation buffer

    Comment by Matthew Jones — 2011-09-14 @ 10:48

  7. Yes, that should work, you got the gist of it. Hey, perhaps IIR filters could also be found to do this, like here with the regular Gaussian: http://www.cwp.mines.edu/Meetings/Project06/cwp546.pdf

    Comment by Olli Niemitalo — 2011-09-14 @ 11:15

  8. Exactly! I've actually already implemented that IIR filter. It is done as four passes, left/right/down/up. But of course it gives a soft (approximately) Gaussian kernel.

    Clearly a 1D box kernel is simple, but getting a 2D uniform circle is hard. I considered running the filter a small number of times in parallel with different weights and sigma (similar to your 'components') and trying to use a linear sum of the result to approximate a circle. I was just using real numbers, though.

    But while researching how to approximate a box with a number of Gaussians, and what weights and sigmas should be used, I stumbled across your article. Very interesting that you're able to get such a good fit by using complex FIRs.

    I think the being able to use a fast (i.e. O(1) cost) IIR filter, along with being separable, and giving an approximate box radial profile (i.e. uniform circle kernel), would be great!

    It would be great to combine the good shape of your method, with the speed of an IIR separable filter (presumably using complex numbers). Interesting problem... I wonder if it is possible.

    Comment by Matthew Jones — 2011-09-14 @ 13:32

  9. I too have been wondering if a uniform circle could be approximated with a weighted sum of plain Gaussians centered at the same spot. I thought maybe the best thing to do would be to flatten out the top. So you would start with this plain Gaussian of fixed width:

    e^(-x^2) / sqrt(pi)

    Then you would proceed to pop its top off with a narrower and less tall Gaussian. And you'd re-normalize the composite to compensate for the loss. If you constrain the first 3 derivatives of the composite to be zero at the center (in order to flatten it), then the limiting shape, when the width of the top-popper approaches the width of the victim, is:

    2 e^(-x^2) (x^2 + 1) / (3 sqrt(pi))

    As close to as allowed by the bit depth of your calculations, that's the shape you'd get with two Gaussians. With three Gaussians you'd be able to force the first 5 derivatives to be zero in the middle, giving:

    4 e^(-x^2) (x^4 + 2 x^2 + 2) / (15 sqrt(pi))

    Or further, with four Gaussians and 7 first derivatives:

    8 e^(-x^2) (x^6 + 3 x^4 + 6 x^2 + 6) / (105 sqrt(pi))

    Didn't solve it, but I suppose the next one will follow the same pattern and be:

    16 e^(-x^2) (x^8 + 4 x^6 + 12 x^4 + 24 x^2 + 24) / (945 sqrt(pi))

    We are getting diminishing returns with the demands for numerical accuracy growing, and with the width of the transition remaining to be quite wide. So not much use doing it in this particular way, then.

    Comment by Olli Niemitalo — 2011-09-15 @ 03:54

  10. I added source code, at the end of the article.

    Comment by Olli Niemitalo — 2011-09-15 @ 17:30

  11. Thank you for the extra info and source code. It is very clear now.

    Also, regarding your fitting of multiple Gaussians so that they have a "flat top".. I attempted to get Mathematica to do a best fit of multiple Gaussians to make a box. I might have done something wrong, but it came back with the answer of using just one Gaussian, and it simply turned off the others (they had a weight of zero in the best fit). 

    Perhaps that is related to what you found, and that the problem is a bit degenerate in that the width of the "top-popper" approaches the width of the "victim" (as you put it), and so on for the subsequent curves. So the optimal widths are something like {W,W-e,W-2e,W-3e,...} where W is the width of the victim, and e is a small epsilon value.

    Comment by Matthew Jones — 2011-10-02 @ 00:45

  12. Matthew, yes, that epsilon thing should work as intended.

    I have good news: I found a recursive filter structure that converges very well to the 1-d component kernels: A sum of forward and reverse filters that have identical coefficients, are sums of complex single-pole filters with truncated tails and have impulse responses of identical support. I'll include that stuff in the article when I have useable coefficient sets available.

    Comment by Olli Niemitalo — 2011-10-08 @ 20:13

  13. Hello,

    Thanks a lot for so good article! My straightforward implementation of scatter blur with variable disk kernel was dramatically slow until I found your article.

    By the way, I found a couple of little mistypes in "Circular blur using prefix sums and summed area tables" paragraph:
    1. Commutativity: "A∗B=A∗B" should be replaced with "A∗B=B∗A"
    2. In scattering-friendly equation "o= ... =i ∗ˆ Kxy∗Sx+(i ∗ˆ Ky+i ∗ˆ Kxy∗Sx)∗Sy" the sparse kernel outside of brackets have to be "Kx", not "Kxy". The correct equation is "i ∗ˆ Kx∗Sx+(i ∗ˆ Ky+i ∗ˆ Kxy∗Sx)∗Sy".

    Comment by Vlad — 2012-08-11 @ 10:53

  14. Thanks Vlad, I'm happy for your success! I have fixed those errors, thank you very much for reporting them.

    Comment by Olli Niemitalo — 2012-08-11 @ 11:42

  15. Wow! The generalized Gaussian function approach is really interesting (as well as some of the other methods, like the packing used by Kyle McDonald). I have previously tried to imagine how well you could approximate a circular convolution kernels by using only a linear combination of different Gaussian kernels, but I haven't realized you could add an imaginary part to the exponent coefficient.

    Have you investigated how much you benefit from using generalized Gaussian functions instead of ordinary Gaussian functions? Since with the ordinary ones, you don't have to calculate sine and cosine for the phase, which makes it cheaper to use, even though you would need more components to make an equally good circular kernel. The question is just how many times more components you would need.

    By the way, did you know that you can approximate the ordinary Gaussian blur by repeated use of a box blur? Since you can calculate box blur by the use of summed area tables in O(1) time, the Gaussian blur could also be approximated in O(1) time, and hence also the circular blur, no matter the radius of the circle.

    Achieving the generalized Gaussian blur, though, might be impossible by using box blur a repeated number of times. I haven't investigated it. If it is impossible, using the ordinary Gaussian kernel instead of the generalized one could suddenly turn out to be a good idea because of this.

    Another thing, if you are going to use the circular kernel to smooth out images, the goal should probably not be to make the edge of the circle as sharp as possible, but rather a linear slope, between 0 and whatever value there should be inside of the circle, over a distance which lies somewhere in between 1 and sqrt(2) pixels. This is in order to prevent the edge of the circle to look jagged. Although you are not close to risking that even with 6 components, at least not for the circle size used in the example image.

    Nevertheless, very interesting article. Thank you for writing it!

    Comment by Kristofer — 2014-01-25 @ 15:32

  16. Thanks for your feedback, Kristofer. It is as you say: an imaginary part is added in the exponent coefficient. In that sense these are still Gaussian functions.

    In the comments, the use of ordinary Gaussian functions is discussed, not in too much depth, but it doesn't seem very promising.

    Using repeated box blur to approximate a 2d gaussian blur has the problem that it will be anisotropic: diagonally the blur will be longer.

    A sloping edge is already implied by the optimization criterion as the "stopband" doesn't start exactly at the "passband". What's going to be between them is not optimized for, but it just so happens that there will be a slope, not a linear one but pretty close.

    Comment by Olli Niemitalo — 2014-01-25 @ 18:07

  17. This paper helps much in my research in calculating the imaging of SLR camera's lens-blur,hby using your code, circular light spot can be formed in the high-light area,it's really beautiful!In your paper ,a circle can be approximated using an octagon and horizontal ,but when the camera lens is changed to polygon,such as hexagonal or octagonal, how can polygon flare be formed?This problem trouble me quit a long time , could you give me some advices about this, code or paper all can help. Thank you
    Best wish.
    Wolsley

    Comment by Wolsley — 2014-02-13 @ 11:23

  18. Wolsley, this article also discusses hexagonal and octagonal blurs. I don't have source code.

    Comment by Olli Niemitalo — 2014-02-13 @ 21:04

  19. Hm, if you just use a large enough number of small box blurs to approximate the Gaussian blur, the diagonal stretch would become small enough. But instead of just using a really large number of small boxes, maybe you can use a number of boxes that are rotated in relation to each other, perhaps like 0, 30, and 60 degrees, respectively, if it would be simple enough to create a rotated box blur.

    But if using ordinary Gaussian functions doesn't seem promising, then there is probably no idea in trying to approximate it with box blurs in the first place... :P

    Comment by Kristofer — 2014-02-17 @ 00:54

RSS feed for comments on this post. TrackBack URL

Leave a comment

Powered by WordPress – Hosted by Iggo