[#convolve] is used to perform various transformations on images such as blurring, sharpening, finding edges, embossing, cellular automata and many others. this is a separated convolution : first a x-convolution and then a y-convolution. it works because of this : is its own mirror image Therefore the convolution will be symmetric. This means that it will not give the impression that it's shifting more on one side than the other. Any non-symmetric convolution will appear to move towards one side by a (usually fractional) number of pixels. For example, the result using 0 1 1 will appear like it's a half-pixel on the left of the result using 0 2 0 NORMALISATION you are responsible for dividing the image by a suitable number. for example, (3 3 # 1 2 1 2 4 2 1 2 1) is a blur multiplied by 16, because the sum of its elements is 16 : UNIT-SUM CONVOLUTION a unit-sum convolution is one in which the sum of the kernel is one, or, alternately, one in which the sum of the kernel is the value you divide by just after convolving : Thus, this is a combination of a convolution of sum 16, with a division by 16, which as a whole acts as a convolution of sum 1 Where 8 is the half the sum of the #convolve kernel. This may be needed because [# >>] and [# div] are biased : for random inputs, it tends to make the image a tiny bit darker ([# /] is biased in a slightly different way, which is as bad). Most of the time you don't care about that, so you don't need the [# +], but if you have a feedback loop, it can make a big difference. Remember that when dividing by a power of two, [# >>] is a lot faster than [# /], except that it's actually more like [# div] (different kind of rounding). Speaking of rounding, if you want a rather balanced rounding, do it more like : ROUNDING TO NEAREST half-range is usually best because is from 0 to 255 : (255-0+1)/2 = 128 Edge detectors have kernels whose values add up to 0, and in such a case, you can't normalise. You can divide by any number you like, even negative, but doing so only gives you another zero-sum convolution. The sum of the pixels in any image after a zero-convolution is zero. This means that if the image isn't all plain black, it will contain a lot of negative values that get clipped to black by [#clip] later. If you want to see those negative values, add a suitable constant. divide by whatever you like (nonzero) SAME-AXIS SEPARATION note that is the same as or (because of the commutative property) SYMMETRIC CONVOLUTION and this too, because of the commutative property : another proof, x before y proof of separability, y before x by another means note that there has to be enough 0-padding in the grid for this demonstration to work. This is why both grids are 3 3 instead of 1 3 and 3 1 WRAP AROUND CONVOLUTION THEOREM ISOTROPIC CONVOLUTION ZERO-SUM CONVOLUTION (EDGE DETECTORS) SHARPENERS ADDITION OF KERNELS IDENTITY KERNEL is a blur (times a constant) because it has no negative values and because it has several positive values. This blur is called "separable" because you can split it like the following. Very few blurs are separable, but most of the most common ones are. BLUR SEPARABILITY remember that this is how you write down a grid not column by column) (and remember that you have to do it row by row, The kernel that does nothing is the one that has a single one in the middle of an all-zero kernel. It's very much like multiplying by one. There are also multiples of that kernel, with a single non-zero value of your choice instead, and in that case, they're just like using [# *] with a single constant. ZERO KERNEL But there's also the zero kernel, which is all zero, which is like [# * 0], and which means your data is gone. A sum of kernels does the same as the sum of the results of two convolutions : = this provides you with another means of breaking down or consolidating convolutions, apart from composition and decomposition. Sharpeners of the "unsharp mask" kind are made by adding together an identity kernel and a zero-sum edge detector. This gives you a unit-sum edge detector, which is not purely an edge detector anymore. pixels positions outside of the image corresponds to pixels of a tiling of that image. therefore, left of its left edge, you can reach the right edge of the image, and similarly for the other sides. this behaviour is helpful in several ways (but ought to become an option) The argument of [#convolve] will be called a "kernel". The following theory mostly only applies when using the default values for options 'op', 'fold' and 'seed'. The [# *] of the [#fft] of two images of the same size, is the same as the [#fft] of the [#convolve] of those two images (one of which is the convolution kernel). This provides you with a reasonably fast alternative to [#convolve] when your kernel is very large. This theorem only works with wrap-around mode. IMPULSE RESPONSE 8-fold symmetry test Theoretically isotropic filters are impossible with grids of pixels, but can be approximated pretty close. Use the operator spectrum patch to test your kernel : the level curves will look circular if the kernel is near-isotropic. GAUSSIAN BLUR should be all the same Isotropy means that it behaves the same in all directions. A necessary but insufficient condition for that is that the kernel is its own transposition and its own x-reverse and its own y-reverse (an eightfold symmetry: its own mirror along x, y and diagonals). But then this only guarantees that it will not favour up/down/left/right over diagonals or vice-versa.. A gaussian kernel is theoretically one that was made by composing together an infinite number of small kernels. This can be approximated by using rows of the Pascal triangle or by using formulas of the exp(-$f1*$f1/$f2) family. Two-dimensional gaussian kernels are the only kernels to be both separable and isotropic at once, but once it's approximated to work with a pixel grid, it's a little bit off. POLYNOMIAL EQUIVALENCE A convolution is done in exactly the same way as a product of polynomials. It's easier to understand that with greyscale, without wrap-around, and with only one dimension at a time, but even with all those features it's still true. Thus you can use [#convolve] to compute products of polynomials and powers of polynomials. It also works with things that are expressed as compositions of convolutions, sum of convolutions, etc., and also things that aren't expressed as convolutions at all, but amount to the same thing (even when it would mean that the equivalent kernel is impossibly big...) examples/operator_spectrum.pd plots the impulse response of the convolution kernel of your choice using level curves with a x-frequency axis and a y-frequency axis. This shows how much various patterns of stripes of different sizes and directions will be dimmed by a kernel. NONSTANDARD CONVOLUTIONS It's possible to replace the usual operators + and * used inside a convolution, by other operators of your choice. You do that at your own risk :) and note that for most of the possible combinations, the above theory doesn't work. numop used as in [#fold]. (default: +) seed used as in [#fold]. (default: 0) The convolution kernel. This can be any 2-dimensional grid of non-zero size, but be careful, as large kernels are usually slow. numop used as in [#] and [#outer]. (default: *) The * operator may be used as many times as with an [#outer *] with same input grids, which is very many. But if the kernel contains zeroes or ones, the multiplications may be skipped. (for a different choice of 'op', different constants apply...) The + operator may be used as many times as a big [#fold +] on the result of [#outer], but when the kernel contains zeroes, the additions may be skipped. (for a different choice of 'fold', a different constant may apply...) matrix or image to be convolved. convolution will happen on the first two dimensions. kernels are centered, that is, the identity kernel is a one surrounded by zeroes. for even-sized kernels, this is a problem, because the middle of the grid is between the cells. in that case, the centre will be the cell above and/or to left of the centre. Resulting image, of the exact same size. undocumented option... may change soon undocumented option... may change soon One interpretation of the convolution operation, is that each new pixel is made from a neighbourhood of pixels of the original pixel. This means that for a kernel of size 3 by 3, the new pixel in row 42 and column 123 is made from the nine pixels that are in rows 41, 42, 43 and columns 122, 123, 124 The positions in the kernel are relative to those row numbers and column numbers (in reverse) WHOLE IMAGE INTERPRETATION A holistic way to look at the convolution is to think of it as a sum of many slightly-shifted whole images. Thus for a kernel of size 3 by 3, [#convolve] is actually summing 9 images together, using the values in the kernel as multipliers of each image (just like using [# *] with a single number). PIXEL NEIGHBOURHOOD INTERPRETATION