ImageMagick v6 Examples --
Convolution of Images

Index

ImageMagick Examples Preface and Index

Introduction to Convolution

• Convolve
• Convolve Kernel Scaling
• Kernel Normalization (Automatic Scaling)
• Zero-Summing Normalization
• Blending Kernel with the Identity Kernel
• Output result Bias Control

Blurring Images (Low-Pass Filtering)

• Blurring Kernels
  • Unity or Identity Kernel
  • Shaped Mean or Average Kernel
  • Gaussian Blurring Kernel
  • Linear 1D Gaussian (Blur)
  • Half Gaussian (Comet)
• Gaussian vs Blur Kernels
• Softened Blurring (blending with original image)
• 'Un-sharpen' Images using Blurs (subtracting from the original image)

Edge Detection Convolutions (High-Pass Filtering)

• Edge Detection Kernels
  • Laplacian Of Gaussians (LoG)
  • Difference Of Gaussians (DoG)
  • Discrete Laplacian Kernels
  • Sobel,  Roberts,  Prewitt,  Compass,  Kirsch,  FreiChen
• Sharpening Images with Edge Detection (enhancing the edges of the original image)

Neighbour Counting

• Counting Neighbours
• The Game of Life

Correlate

• Convolve vs Correlate (asymmetrical kernel effects)
• Correlation and Shape Searching
• Correlate vs HitAndMiss

Convolution uses the local 'neighbourhood' of pixels to modify images. It does this by merging and averaging all the color values around each pixel to blur images, to highlight edges and boundaries, and sharpen images. The convolution variation, 'Correlation' is also used for scanning and searching for specific patterns, producing a image denoting how closely images matches.

---

Introdution to Convolution

The 'Convolve' and the closely related 'Correlate' methods, are is many ways very similar to Morphology. In fact they work in almost the exactly the same way, matching up a heighbourhood 'kernel' at each location, making them a just another special 'method' of morphology.

In fact, they also use much of the same code and even the same kernel defintions that was defined in Basic Kernels and User Defined Kernels. For more specific kernels designed for use by this operator, (and there are many), I refer you to Blurring Kernels, and Edge Detection Kernels. The most important kernel being the 'Gaussian' kernel.

However, convolution is much older than morphology, and it generates more grey-scale gradient effects, rather than the binary shape studying effects that morphology typically generates. This is why it is often regarded as a very different or separate operation to morphology and one that is more central to image processing.

Basically a convolution or correlation performs a 'weighted average' of all the pixels in the neighbourhood specified. That is, it multiplies the value of each nearby pixel by the amount given in the kernel, then adds all those values together to produce the final result.

As such, each pixel in the final image will generally contain at least a small part of all the other pixels locally surrounding it in the source image. Looking at it another way, the color of each pixel in the image will be either added to (blurred) or subtracted from (sharpen/edge detection) the colors of all its near by neighbours, as defined by then kernel used.

Both 'convolve' and 'correlate' are the same operation, except in a very minor but important way, and for the examples and controls that we will now look, you can treat them as being basically the same thing. Later (See Convolution vs Correlation) we will examine exactly how the two operators really differ and why they differ in such a minor way. But in most circumstances they are the same method.

Convolve   ( )

As was mentioned above the 'Convolve method works by weighting each of the pixels in the local neighbourhood, according to the floating point values in the kernel. The weighted values are then simply added together to produce the new replacement pixel in the resulting image.

For example lets convolve a single pixel, using a very small User Defined convolution kernel. I also set the special Show Kernel Setting, so you can see the details of the kernel being defined and used.

As you can see the single pixel in the image has now expanded to produce 50% pixels around it.

That is, when the kernel's 'origin' (it's center in this case) is positioned next to the single pixel in the original image, only that pixel has a non-zero value, this is then weighted by the '0.5' value of the kernel, and the resulting 'half-bright' pixel is added to the resulting image.

Simularly when the kernel's origin is position exactly over the original pixel, it will get a value of '1.0' reproducing the original pixel with no other values (black) adding any component to the result.

Note that any kernel value of '0.0' will take no part in the final calculation. Zero values are effectively not part of the 'neighbourhood', just as any 'Nan' value in morphology kernels take no part. As such this kernel only contains a 5 element neighbourhood.

The syntax of a convolution operation is...

But you can also use an older, more direct operator...

Before IM v6.5.9 the older "-convolve" did not understand morphology kernel definitions. It would only accept the 'old style' of user defined kernels, consisting of just a string of comma separated values to produce to some odd-sized square kernel. It will now accept the 'new' style' convolution kernels defintions. However it is still restricted to 'odd sized' square kernels. And will remain that way until it starts to make use of the new 'morphology' convolution method.

The older "-convolve" operator is not exactly the same as the newer Morphology 'convolve' Method". Thus here is how the older -convolve" operator differs... The operator is implemented as a Correlation rather than a true convolve. This means the kernel is not overlaid on the source image in its reflected form. See Convolve vs Correlate for the effects this has on results. It only accepts odd sized square kernels. It will always Normalize Kernels without any user control over kernel Kernel Scaling of the kernel. Nor does it allow any form of Blending with the Identity Kernel, though result Output Bias is performed as normal. It will however make use of fast 'GPU Convolutions' if the host computer has such facilities. Currently other convolution related operators, such as "-gaussian_blur", "-blur", "-sharpen", "-unsharp", use the same code as the old -convolve" operator. By default it will only convolve against the color channels (as defined by the -channel" setting. If you convolve with a -channel RGBA" setting it will also weight the kernel values by the alpha channel to ensure correct blurring with regards to transparency. The Morphology 'convolve' method will automatically handle transparency weighting of the color channels by default. That is image blurring using it will treat transparent colors as transparent, and thus avoid the Blur Transparency Bug, by default. However if the user modifies the default "-channel" setting (by not including the special 'Sync' flag), then it will handle the convolution on a purely channel greyscale bases. See the "-channel" setting documentation, or look at Image Channel Mathematics whcih uses the same flag, for more information. Eventually most of the above differences will change as it things merge with the newer Morphology 'convolve' Method".

If you like to see some great examples of how 'Convolve' actually does works, I recommend you also have a look at EECE \ CS 253 Image Processing, Lecture 7, Spatial Convolution.

The Wikipedia, Convolve artical has some nice 1-D animations of the convolution process.

Convolve Kernel Scaling

The above example works well for a mostly black image such as a single pixel, but if you were to apply this to a real image, you will have a problem...

As you can see the resulting image is very bright (3 times brighter in fact) as the original image.

What happened is that each pixel is being shared 3 times. 4 × '0.5' on the sides, plus a full copy of the original pixel. That is the addition of all the values in the kernel is 3, making the resulting image three times as bright!

If you go back and look at the 'showkernel' output above, you will see that it listed this kernel as having a "convolution output range from 0 to 3". Which shows that this kernel will in general brighten an image 3 times.

To fix this you would want to divide all the values in the kernel by 3. That is a value of '0.5' should really have been about '0.1667' while the central value of '1.0' should have been '0.3333'. This is a process known as 'Kernel Normalization'.

For example here is manually 'normalized' result, and the kernel definition...

As you can see you get a very slightly blurred version of the face image, as each pixel was spread out to each of its immediate neighbours.

The 'kernel image' that is shown in the above (generated using a special Kernel 2 Image Script) also shows the resulting normalized kernel. As you can see the kernel itself is now very dark, as all its values are also dark, though they all add up to a value of '1.0'. From this point on all convolution kernel images shown will always be adjusted so the maximum value is set to white, otherwise all you will generally see is a dark, and basically useless, 'Kernel Image'.

Normalizing the kernel yourself is not pleasant, and as you saw it makes the resulting kernel definition a lot harder to understand. As such, alternative ways are provided.

As of IM v6.5.9-2 the special expert option "-set option:convolve:scale {kernel_scale}' allows you to specify a global scaling factor for the kernel, and thus adjust the brightness of the overall result.

convert face.png -set option:convolve:scale 0.33333 \ -morphology Convolve '3x3: 0.0,0.5,0.0 0.5,1.0,0.5 0.0,0.5,0.0' \ face_spread_scale.png

Actually what this does is adjusts the overall intensity of the kernel results. As you will see in later examples, you will probably want to make the convolution result more or less powerful. This 'kernel_scale' factor lets you do that.

Kernel Normalization (automatic scaling)

Rather then working out the scaling factor (as above), you can simply ask the IM to work out this 'normalize scaling factor' internally by giving it the special '!' normalization flag.

convert face.png -set option:convolve:scale \! \ -morphology Convolve '3x3: 0,1,0 1,2,1 0,1,0' \ face_spread_normalize.png

The '!' character is also sometimes used for special purposes by various UNIX command line shells. So you may have to escape the character using a backslash, even in quotes. Caution is advised.

Note that as the kernel is now normalized, I can define it in a simplier fashion using whole numbers. The normalized kernel will still be the same as previous 'scaled' kernel.

Typically you will always want to normalize the kernel, and because of this the simplier "-convolve" variant will automatically do this normalization.

You can have IM normalize the kernel, then scale it further again by a given amount to adjust its output range. To make this even easier you can specify the scaling factor as a percentage.

For example here I normalize the kernel but then re-scale the values to 50% the calculated size, so as to produce a darker result.

convert face.png -set option:convolve:scale 50%\! \ -morphology Convolve '3x3: 0,1,0 1,2,1 0,1,0' \ face_spread_norm_half.png

Note that using a value of '!' is actually equivelent to using '1!' or even '100%!'. You can even use a negative scaling factor if you want to flip the positive and negative values within the kernel. For an example of this see 'Un-Sharpening' Images using Blurs.

If the kernel has been normalized in this way the Show Kernel output will tell you that it is normalized.

How Normalization Works

The actual way 'Kernel Normalization' works is that all the kernel values are added together (including any negative values which is also posible). If the result is non-zero, then scale all the values so that their combined value adds up to a value of one ('1.0').

Note that, if you have negative values, this could actually create a kernel with a value larger than one, typically at the origin. It specifically happens with Un-Sharp kernels. The important point, however, is that the kernel as a whole adds to '1.0', so that the final image is not made darker or lighter by the 'Convolution.

If the result of the addition is Zero ('0.0'), then the kernel is assumed to be a special Zero-Summing Kernel. In that case the kernel is scaled to make all positive values equal to '1.0', and by the same token, all negative values will then add up to '-1.0'. These kernels are especially prevelent with Edge Detection techniques.

The Show Kernel output will also specify that it is zero-summing, if the kernel is in this form, even if not actually a normalized zero-summing kernel, though that will also be easilly seen by the other numbers displayed.

Most mathematically determined kernels are pre-normalized. This includes the mathematically derived kernels: 'Unity', 'Gaussian', 'LoG', 'DoG', 'Blur', 'Comet'.

Discrete Constant Kernels, however are are not pre-normalized, so you will have to do this using the Kernel Normalization Setting (above). This includes the kernels: 'Laplacian', 'Sobel', 'Roberts', 'Prewitt', 'Compass', 'Kirsch', 'FreiChen'.

Note that the 'FreiChen' kernel has sub-types that are specially pre-weighted for more specific purposes. The FreiChen kernels should not be normalized, but used as is.

Zero-Summing Normalization

Not all convolution kernels use only positive values. You can also get kernels that use a mix of positive and negative values and often the values of these kernels are meant to add up to zero to produce a Zero-Summing Kernels. Such kernels are very important to more advanced Image Convolutions, as they provide techniques of Edge Detection and Sharpening Images.

As I mentioned in the last section, the usual normalization flag '!' will work with such kernels. But sometimes due to special situations you want to ensure that the kernel does remain 'zero-summing'.

The special '^' normalization method just provides a way to ensure the kernel is 'zero-summing' in situations such as...

1. If the user's kernel definition is not precise enough to ensure zero-summing. For example you can not specify 1/3' or any other fractional factor of 3 as a floating point decimal number.

2. The mathematical curve gets 'clipped' by the kernels size (radius) so it may no longer be zero summing. For example, this occurs in a 'LoG' or 'DoG' kernels. IM actually uses it for this purpose internally on these kernels.

3. Ensure that a Correlation 'shape mask' is zero summing, so that in the search, IM can look for both positive and negative matches. See Correlation Shape Searching below.

What happens is that it will normalize the positive and negative values of the kernel separatally. Basically it will scale all the negative values to add up to '-1.0' and all the positive values to add to '+1.0'. The result is that the kernel will as a whole add up to zero.

Note that for an all-positive kernel such as 'Gaussian' you will still get a properly normalized kernel. As such this form of normalization can still be used with Blurring Kernels. However it should not be used to normalize directly defined Sharpening or even Un-Sharpening kernels.

Blending Kernel with the Identity Kernel

The full syntax of the Kernel Scaling Setting is...

The normalization flags '!' or '^" will be applied to the user defined or built in kernel first (if requested).

After that, the kernel will scaled by the 'kernel_scale' factor either increasing or decreasing the effective 'power' of the convolution on the results. Default scaling factor is '1.0'.

Lastly the 'origin' value of the kernel will have the number after a comma added to it. Default 'origin_addition' is '0.0'.

This last step effectifally 'adds' a Unity Kernel that has been 'scaled' by the given amount to the previously normalized and scaled kernel.

What this does is allow you to...

• Soften the effects of a Blurring Kernel.

• Or convert such a kernel into one that can be used to directly Un-Sharpen an Image.

• It can also allow you to convert Edge Detection Kernel into a Image Sharpening Kernel.

Note that if you give a percent ('%') flag, that percentage will be applied to BOTH the 'kernel_scale' factor and the 'origin_addition'.

For Example...
    -set option:convolve:scale '!50%,100%'  -morphology Convolve Laplacian:2

Then IM will...

   Generate the requested kernel  Laplacian:2
        0  -1   0
       -1   4  -1
        0  -1   0

   Normalizate it ('!' flag)
        0    -0.25    0
      -0.25    1    -0.25
        0    -0.25    0

   Scale by 50%
        0     -0.125    0
      -0.125    0.5   -0.125
        0     -0.125    0

   Add a Unity kernel (add 100% to origin value)
        0      -0.125     0
      -0.125     1.5    -0.125
        0      -0.125     0

And you get convolve using a Laplacian:2
being used as a sharpening kernel, but with only 50% of the power.

NOTE: any '%' flag given anywhere in the scale setting, will make both values
percentages.  If not present both values are just simple multipliers.
For example all these scaling options are equivelent
     50,100%     50%,100    %50,100      .5,1      0.5,1.0

Basially you can not specify one scaling factor as a percentage and the other
as a multiplier.

The same goes for the two normalization flags.  They can appear anywhere in
the convole scaling setting, but they will always be applied first before any
other scaling takes place.

Output result Bias Control

When you are dealing with a kernel that contains negative values, some pixels in the resulting image should be assigned a negative value. This is especially the case with Zero-Summing Kernels (see below).

Unfortunatally, unless you have a specially built HDRI Version of ImageMagick, to preserve the negative values that were generated, any negative result will be clipped to zero (black). You will only get thge positive results from the convolution. It just can not be stored in a normal image format, leaving you with half the result.

You could build HDRI Version of ImageMagick to preserve the negative values that were generated, and then extract the information you want. Alternately, you can negate the kernel by using a negative scaling factor. For example using... However then you only get the negative results with the positive results becomming clipped.

However by using the IM setting "-bias" you can still preserve both positive and negative results.

The settings to use for non-HDRI version of IM is...

The first setting scales the output to half the size you would normally get (after it is normalized), so as to make room for both positive and negative results. Then it will add a 50% gray to the pixel output before saving the result back into an image.

With these settings, any 'zero' result will become pure gray with negative results darker than this and positive result lighter than this. Black will represent '-1.0' and white will mean '+1.0'.

One example of doing this is show below in the Correlate Shape Search Method below.

---

Blurring Images (low-pass filtering)

Another section of IM examples, specifically Blurring, and Sharpening Images, actually deals with practical aspects of this subject. Here we look at more specific details.

First however, we will describe the basic kernels and how you can use them directly without modification. Later we will look at ways of modifying the bluring to generate other effects.

Blurring Kernels

Unity

This is a special kernel that actually does nothing. Only one kernel element is specified, and as a result each pixel is replace by itself without change.

The kernel has no arguments.

This exact same single element kernel can also be generated using 'Disk:0.5', which also allow you to specify a scaling argument as part of the kernels generation.

For example here is a no-op Convolution...

A similar kernel (for Convolution) can also be generated by the a 'Gaussian' kernel generator, whenever 'sigma' is zero, but producing a 3x3 pixel version, consisting of a central '1.0' value surrounding by 8 '0.0' values.

That same form can also be generated by a 'Peaks:1.5' kernel used for Hit-And-Miss Morphology Method.

Mean or Average Filtering using Shape Kernels

While most convolution kernels defined below generally involve the use of a Gaussian Curve in some way, you can still use one of the previous Morphology Shape Kernels to simply average the pixels over a given (large) area.

For example, here I use a smaller 'Disk' kernel, to average the value using all the pixels found within the disk surrounding each pixel in the image, including the original pixel.

The result is that the value of each pixel is spread out equally over all 25 pixels in the defined neighbourhood. That is, it is equivelent to a 'mean' or 'averaging' filter over the given shape.

Of course, these shaped kernels are not normalized, so we need to ask IM to Normalize or Auto-scale the kernel before it is applied.

If you want to exclude the original pixel from that average, only using the surrounding pixels, then you can use a 'Ring' kernel (supplying only one radii).

The other Shape Kernels can also be used in the same way to, say, average the pixel values over a 'Diamond' or 'Square' shape and to whatever size you want.

However while this constant averaging over an shaped area does blur images, it has a tendency to produce unusual artifacts (specifically aliasing effects) in the resulting image. This is caused by the sharp edges of such kernels.

Gaussian Kernel (2d gaussian blur)

As you may have gathered, the 'Gaussian' kernel is the most commonly used kernel to Convolve an image. This is the mathematical ideal type of blurring that you can achieve.

Here for example is the Show Kernel of a small 'Gaussian' kernel (they can get very large very quickly)...

I did not actually want to apply a convolution to the above, as I only wanted to show the kernel that it was going to use. As such I used a ':0' Iteration Count, so it does nothing. Similarly I junk the resulting image output using the special 'null:' file format.

As you can see by the convolution output range, a 'Gaussian' kernel has already been normalized (scaled) for you. However you will also notice that it is still quite a large kernel, filled completely with small fractional values. If you look closer you will find the largest value (also listed on the first line) is in the center, with the smallest values toward the edges and the corners.

Here typical Gaussian blur using a convolution...

The kernels syntax is straight forward...

These arguments are in fact exactly the same as that used by the "-gaussian-blur" operator, which actually performs a Convolution using this kernel.

The first number, like most Morphology Kernels, is the 'radius' or size of the kernel. This is just an integer, with a minimum value of 1, making the smallest kernel posible 3x3 elements in size. The best idea is to always specify zero, which allows ImageMagick to calculate an appropriate radius for the 'sigma' value provided.

The second more important argument is 'sigma' which defines how blurred or 'spread out' each pixel should become. The larger the value the more blurry a image will become. It is a floating-point value. The sigma value MUST be provided.

If a sigma value of '0.0' is given you will end up with a fairly useless 'Unity' kernel (of the given radius, or a radius of 1, so producing a 3x3 kernel of a single '1.0' value surrounded by '0.0' values.). As you saw above, convolving with any type of 'Unity' kernel does nothing to the image!

If you do specify a 'radius' it is generally a good idea to make it at lest twice as big as the 'sigma', IM usally calculates a radius that is approximatally 3 times as big (actually the largest radius that will provide meaningful results), though it depends on the Compile-time Quality of your specific IM installation.

For more information on the effect of the 'Gaussian' kernel arguments, and on blurring images in general, see... Blurring Images.

Blur Kernel (1d gaussian blur)

The 'Blur' kernel is very similar to the Gaussian Kernel, and even takes the same arguments (see below). But where gaussian is a 2-dimensional curve, the 'Blur' kernel produces a 1-dimensional curve. That is to say it generates a long thin single row of values.

Here is a Show Kernel output of a small 'Blur' kernel.

	convert xc: -set option:showkernel 1 \ -morphology Convolve:0 Blur:0x0.8 null:

The graph shown above is an actual profile (generated using the Kernel Image generator Script, "kernel2image" and the "im_profile", which shows the 'Gaussian Bell Curve' that this kernel represents.

Here is an example of using this kernel to horizontally blur a image. convert face.png -morphology Convolve Blur:0x4 face_blur.png

The kernel's syntax is exactly like that of 'Gaussian' but with a extra optional rotation angle.

As before the second value 'sigma' is required, and if set to zero you will get the linear equivelent of a 'Unity' kernel.

The 'angle' allows you rotate the kernel by 90 degrees allowing you to blur an image vertically. convert face.png -morphology Convolve Blur:0x4,90 face_blur_vert.png

At this time only a 90 degree rotation is posible. This may change in a later version of ImageMagick.

The purpose of this kernel is actually to create a faster form of 2-dimentional image blurring that the 'Gaussian' kernel produces. See Gaussian vs Blur Kernels below for details of how this is done.

Comet Kernel (half 1d gaussian blur)

The 'Comet' kernel is almost exactly the same as a 'Blur' kernel, but is actually a half a blur.

Here again I generate Show Kernel output of a small 'Comet' kernel.

Note how the defined location of the origin is on the left hand edge, and not in the center of the kernel. This is very unusual for a convolution, and as as such produces a very unusual result.

It blurs the image out in one direction like a finger had smeared the surface of a wet painting, leaving a trail of color. Its a bit like the tail of a comet, or the trail left by a meteor, or falling star.

convert face.png -morphology Convolve Comet:0x5 face_comet.png

It can also can take a third angle argument to rotate the kernel in multiples of 90 degrees about its 'origin'.

convert face.png -morphology Convolve comet:0x5+90 face_comet_vert.png

This kernel is actually the same kernel that is use by the specialized Motion Blur operator, though that operator also does some very fancy coordinate look-up handling to allow the blur to happen at any angle. This, however, is a poor substitute for a properly rotated kernel and tends to produce some 'clumps' of color at large angles, such as 45 degrees.

Hopefully proper kernel rotation will implemented to create better motion blur type effects at angles beyond 90 degrees.

Gaussian vs Blur Kernels

As mentioned the 'Gaussian' and 'Blur' kernels are very closely related, and can in fact to the same job. For example here is repeat of the "-gaussian-blur 0x2" which is equivalent to "-morphology Convolve Gaussian:0x2" operation.

convert face.png -gaussian-blur 0x2 face_gaussian-blur.png

This can be replaced by using two separate Linear or 1 dimensional blurring operations rotated ninety degrees to each other (order does not really matter either)...

convert face.png -morphology Convolve Blur:0x2 \ -morphology Convolve Blur:0x2+90 face_blur_x2.png

Rather than specifying two separate convolutions, you can give both kernels as a kernel list. For example

IM will by default 're-iterate' the result of the first convolve kernel with the second (and later) convolve kernel, as defined by Multiple Kernel Composition setting.

You can even simplify the above even further by ask IM to expand one kernel into a Rotated Kernel List, by using a '>' to do a list of 90 degree rotations (two kernels in this case). For example...

All the above examples are equivalent to each other, and is how the "-blur" operator works. convert face.png -blur 0x2 face_blurred.png

This represents the real difference between "-blur" and "-gaussian-blur" operators. Wether one single large 2-dimensional kernel is used, or two small 1-dimensional kernels are used.

In terms of speed however the "-blur" operator is usually an order of magnitude faster, as it uses two much smaller kernels, rather than one very large one. The larger the blurring argument (the size of the sigma argument) the bigger kernels become, and the larger the difference in speed between the two operations. As such the "-blur" operator is generally the recommended one to use.

The only difference in results between the two operators are small quantum rounding effects (unless you are using HDRI) and edge effects (depending on Virtual Pixel Setting). Both of these being caused by a loss of information between the two separate passes of the 'blur' convolutions. The difference is typically so small as to be invisible and of no concern to any practical usage.

Softened Blurring (blending with original image)

You can soften the impact of any sort of blur by blending it with some of the original image. Especially when applying a very strong blur. For example...

This used the 'Blend' composition method, to mix '60%' of the blurred image (composition source image) with '40%' of the original image (composition destination image) to give a 'soft blur' effect on the final image.

However you can do the same thing directly by Blending the Kernel with the Identity Kernel, using the same ratio.

convert face.png -set option:convolve:scale 60,40% \ -morphology Convolve 'Gaussian:0x3' face_soft_blur2.png

Note that the order of the scaling numbers is the same. The first number ('60%') scales the given kernel so as to reduce its effect on the output, while the second number ('40%') adds enough of the 'Unity' (or 'Identity') kernel to prevent the result from becoming darker.

The important point is that for Blurring Kernels, the two numbers add up to '100%', just as you would for Composite Blending.

You can also use the faster 2-pass blurring (see Gaussian vs Blur above), as blending the kernels in this way does not break the 'separability' aspect required by this technique.

convert face.png -set option:convolve:scale 60,40% \ -morphology Convolve 'Blur:0x3>' face_soft_blur3.png

'Un-sharpen' Images using Blurs (subtracting from the original image)

By taking this blending of kernels further, so that you start to use a negative scaling, you can subtract the blurring effects from the original image. The result is a technique called 'unsharp'. See Unsharp, Wikipedia for how it came to get such an unfortunate name.

convert face.png -set option:convolve:scale -100,200% \ -morphology Convolve 'Blur:0x2>' face_unsharp.png

Note that even though a negative kernel scaling factor is used, the two numbers still adds up to '100%', exactly as it did above. You can also do this with Composite Blending as well.

The above example is actually exactly how the "-sharpen" operator works but with only the 'sigma' blurring control, provided. The blending is exactly as given above.

However uing this technique you can also control the amount of un-sharpening (blending) you want to apply. For example here is a 50% un-sharpening...

convert face.png -set option:convolve:scale -50,150% \ -morphology Convolve 'Blur:0x2>' face_unsharp_50.png

The full "-unsharp" operator provides this type of control. It also provides other controls, such as a difference threshold, so that the sharpening only applied when difference is larger, such as near an actual edge within the image. That threshold can be use to prevent the 'sharpening' small small defects, like wrinkles, or image noise.

FUTURE: reference to where we actually look at unsharp in detail (not done at this time).

---

Edge Detection Convolutions (high-pass filtering)

Edge Detection is another area in which convolutions are heavilly used.

The task here is to highlight or enhance the edges of an image in various ways. This can be to either locate an edge as accuratelly as posible or to determine the angle or direction of slope of each of the edges.

However the job can be made a lot more difficult by the presence of noise in the image, such as that produced by scanners, digital cameras, or even just caused by the lossy compression of the JPEG image file format.

In general, however, larger kernels handle noise better, but at a loss of localizing the edge properly, while smaller kernels produce sharp edge locating results but with more spurious results caused by noise in the image.

There are a lot of small, well-known kernels, that have been developed and studied for edge detection. Most of these are 'named' after the mathematician which studied the mathematics or the developed that specific kernel type. As such, you have kernels such as 'Laplacian', 'Sobel' and 'Prewitt'. These 'named' kernels are generally very small and are defined using whole numbers, so they can be built into specifically designed optimized software and hardware for speed. That is, they are said to be 'discrete' kernels. Because of that, you will need to either Scale or Normalize the kernel as part of their use.

Edge detection also has the side effect of providing ways of sharpening the edges of an image.

Zero-Summing Kernels

All the edge detection kernels have one feature in common. They are all zero-summing. That means they contain negative values, but with all the values in the kernel adding up to zero.

For a smooth flat color image, a Convolution using such a kernel will produce a 'zero' or black image. However for any other image, you will have results that contain both negatative and positive values.

For example here I apply a discrete 'Sobel' edge detector on a image containing some basic shapes...

If you look at the results you will see that the kernel is directional in that only the vertical edges are found (as defined by the 'Sobel' kernel with a zero angle. However it only found on set of the set of slopes, the positive left-to-right slopes.

To get the 'negative' slopes you will need to negate the kernel, by using the Kernel Scaling Setting. For example...

convert shapes.gif -set option:convolve:scale '-1!' \ -morphology Convolve Sobel shapes_sobel_neg.gif

With a 'Sobel' kernel, you can also rotate it 180 degrees to get the same result as the 'scale negation', but not all kernels are symmetrical in this way.

The other solution is to add an Output Bias to the result. That is add 50% grey to the resulting image so that negative values are lighter than this and positive values are brighter. However, you will also need to Scale the Kernel to ensure the results remain 'unclipped' by the 'black' and 'white' limits of the image.

convert shapes.gif -set option:convolve:scale '50%!' -bias 50% \ -morphology Convolve Sobel shapes_sobel_bias.gif

If you don't care about the polarity you can get an absolute value of the results with a little trickiness..

convert shapes.gif -set option:convolve:scale '50%!' -bias 50% \ -morphology Convolve Sobel -solarize 50% -level 50,0% \ shapes_sobel_abs.gif

See the 'Sobel' kernel, for more result handling techniques, especially techniques involving direction determination.

The other alternative to using an Output Bias is to build a special HDRI version of Imagemagick. This stores images in memory using floating point vaules and means that the image values will not be 'clipped' or 'rounded' by the use of integers.

However, even if you do use this special version of IM you will still need to post-process the results before saving to a normal image file format or you will need to use a special floating point enabled image file format. However you will not need to worry about clipping or rounding effects in the intermediate image results, makign things a lot easier.

Edge detection Kernels

LoG: Laplacian Of Gaussians

The 'LoG' or "Laplacian of a Gaussian" is one of the best edge detection kernels you can get. It is also known as a "Mexican Hat" kernel.

Basically is it a 'Laplacian' differential (slope) operator, that has been smoothed by the addition of gaussian blurring. This in turn removes most of the impact of noise in an image, which can be adjusted by the 'sigma' setting.

The Kernel contains negative values that form a ring around a strong central peak. In the 'Kernel Image' shown above, the negatives are shown as the dark (near black) colors with the edges decaying to zero (dark grey) toward the edges.

And here is its effect.. showing how it highlights the edges of the image.

A laplacian kernel is direction-less, but produces both a positive and negative ridge of values on either size of an edge. To locate the edge you would look for the points of zero-crossing, between the positive and negative ridges, a technique known as'Marr and Hildreth Edge Detection.

This kernel is also ideal for Sharpening Images.

DoG: Difference of Gaussians

This will generate a 'DoG' or "Difference of Gaussians" kernel in which the gaussian generated by 'sigma1' will have the gaussian generated by 'sigma2' subtracted from it. Normally 'sigma2' is the larger so that the 'central peak' of the kernel is positive. Reversing the two numbers will effectivally negate the resulting kernel.

One of the major criticisms of a Laplacian of a Gaussian is that it is difficult to implement as it is such an unusual mathematical curve. It is also not a very well documented curve. The other aspect is that it can not be 'separated' into a faster 2-pass solution as you can with a Gaussian, (see Gaussian vs Blur Kernels).

However by generating two 'Gaussian' kernels of slightly different sigma values (in a ratio of approximatally 1.6), and subtracting them from each other you can actually generate a close approximation of a Laplacian of a Gaussian.

The result is that a 'DoG' is much more easilly generated in hardware, than a 'LoG' kernel.

For example here I have placed the Kernel Images of a 'LoG', and a 'DoG' kernel side-by-side for comparison. If you look on the Difference of Gaussian, Wikipedia web page you will see some graphs where they also compare the profile of a 'LoG' (or "Maxican Hat"), with a 'DoG', showing the verly very slight difference between matching curves.

More information wanted on how to map a sigma of a LoG to generate a near equivelent 'DoG'. If you know please Mail Me.

The applied results are also the very similar. convert face.png -set option:convolve:scale '!' -bias 50% \ -morphology Convolve DoG:0,1.8,2.4 face_dog.png

Note that both 'sigma' values should be defined and non-zero, otherwise that specific component will be the equivalent of a 'Unity' kernel.

Remember a sigma value of zero produces a unity kernel. convert face.png -set option:convolve:scale '!' -bias 50% \ -morphology Convolve DoG:0,0,2 face_dog_unity.png

In fact this could be used to generate a 3x3 'Isotropic Laplacian' kernel, meaning a 'Laplacian' kernel which produces equal results in all directions.

	convert face.png -set option:showkernel 1 \ -set option:convolve:scale '!' -bias 50% \ -morphology Convolve DoG:1,0,1 face_laplacian_isotropic.png

The other good point about using a "Difference of Gaussians" is that you can use the much faster "-blur" operator (which internally uses the 'Blur' kernels), to generate the same results. However to do this you will need to generate each of the two 'blurred' images separately, and then subtract the results, with the addition of an appropriate scaling and bias.

For example...

convert face.png \ \( -clone 0 -blur 0x1.8 \) \( -clone 0 -blur 0x2.4 \) -delete 0 \ -compose Mathematics -set option:compose:args 0,-4,4,0.5 -composite \ face_diff_of_blurs.png

The above uses the special Mathematics Composition Method to avoid problems with 'clipping' the subtraction of one blurred image from the other in a non-HDRI version of IM. For more details see Adding Biased Gradients.

The only other difference is the use of a larger scaling factor during the subtraction (the two '4's in the Mathematics Compose argument. This is because subtracting two normalized blurs, does not produce the same magnitude of results that a normalization of the combined gaussian curves that the 'DoG' kernel produces.

However other than the magnitude, this image is equivelent to the first 'DoG' kernel result.

Discrete Laplacian Kernels

There have been many forms of small "Laplacian Kernel" defined (such as calcaulted by the 'LoG' kernel above) and this specific built-in provides you with a way to use the more common ones I have been able to find in the academic literature.

None of the kernels provided here are rotatable, and most are 'anisotropic', meaning they are not perfectly circular, especially in diagonal directions. However see the previous section for a way to generate a true "Isotropic 3x3 Laplacian Kernel".

The first two 'Laplacian:0' and 'Laplacian:1' kernels are the most common form of "Discrete Laplacian Kernel" in use. They are small, meaning they will locate edges very accurately, but are also prone to image noise.

Note that not all 'type' numbers have been defined, leaving spaces for more discrete kernels to be defined in the future.

Laplacian:0

The 8 neighbour Laplacian. Probably the most common discrete Laplacian edge detection kernel.

Here I use Show Kernel to extract the 'discrete' and 'unnormalized' kernel, before showing you thw result of the normalized kernel with a Output Bias.

	convert xc: -set option:showkernel 1 -precision 2 \ -morphology Convolve:0 Laplacian:0 null: convert face.png -set option:convolve:scale '!' -bias 50% \ -morphology Convolve Laplacian:0 face_laplacian_0.png

Sometimes a Laplacian, weather it is a discrete Laplacian, as in the last example, or a generated 'LoG' or 'DoG', generated too many edges. In such cases, generating an unbiased, (without any Output Bias) will work better.

convert face.png -set option:convolve:scale '!' \ -morphology Convolve Laplacian:0 \ -auto-level face_laplacian_positives.png

However edges found may be to one side (inside or outside) of the object.

It also generates interesting 'halo' effects around the images depending on if you capture the positive results (as above) or the negative results.

convert face.png -set option:convolve:scale '-1!' \ -morphology Convolve Laplacian:0 \ -auto-level face_laplacian_negatives.png

As you can see, for this image using the negative size produces stronger edges without the 'twinning' effects the positive results produced. This is because of the use of 'black' edging lines in the image being used.

Laplacian:1

The 4 neighbour Laplacian. Also very commonly used.

	convert xc: -set option:showkernel 1 -precision 2 \ -morphology Convolve:0 Laplacian:1 null: convert face.png -set option:convolve:scale '!' -bias 50% \ -morphology Convolve Laplacian:1 face_laplacian_1.png

The results are not a strong, but are often clearer than the 8-neighbour laplacian.

Laplacian:2

3x3 Laplacian, with center:4 edge:1 corner:-2

	convert xc: -set option:showkernel 1 -precision 2 \ -morphology Convolve:0 Laplacian:2 null: convert face.png -set option:convolve:scale '!' -bias 50% \ -morphology Convolve Laplacian:2 face_laplacian_2.png

Laplacian:3

3x3 Laplacian, with center:4 edge:-2 corner:1

	convert xc: -set option:showkernel 1 -precision 2 \ -morphology Convolve:0 Laplacian:3 null: convert face.png -set option:convolve:scale '400%!' -bias 50% \ -morphology Convolve Laplacian:3 face_laplacian_3.png

Note that the kernel can produce good 'thin' results, though you may have to magnify the results (as I did above) to see them clearly. Also note how vertical edges seemed to vanish in the result.

Laplacian:5

5x5 Laplacian

	convert xc: -set option:showkernel 1 -precision 2 \ -morphology Convolve:0 Laplacian:5 null: convert face.png -set option:convolve:scale '!' -bias 50% \ -morphology Convolve Laplacian:5 face_laplacian_5.png

The rule-of-thumb with laplacian kernels is the larger they are the cleaner the result, especially when errors are involved. However you also get less detail.

Laplacian:7

7x7 Laplacian

	convert xc: -set option:showkernel 1 -precision 2 \ -morphology Convolve:0 Laplacian:7 null: convert face.png -set option:convolve:scale '!' -bias 50% \ -morphology Convolve Laplacian:7 face_laplacian_7.png

Laplacian:15

A Discrete 5x5 LoG (Sigma approximatally 1.4)

	convert xc: -set option:showkernel 1 -precision 2 \ -morphology Convolve:0 Laplacian:15 null: convert face.png -set option:convolve:scale '!' -bias 50% \ -morphology Convolve Laplacian:15 face_laplacian_15.png

Laplacian:19

A Discrete 9x9 LoG (Sigma approximatally 1.4)

	convert xc: -set option:showkernel 1 -precision 2 \ -morphology Convolve:0 Laplacian:19 null: convert face.png -set option:convolve:scale '!' -bias 50% \ -morphology Convolve Laplacian:19 face_laplacian_19.png

Sobel

Sobel:{angle}

We already saw the 'Sobel' kernel above in the discussion of Zero-Summing Kernels.

Unlike all the previous edge detection kernels this is a directional (first derivative) kernel designed to return the slope of a edge in some specific orthogonal direction. By default it is designed for left to right slope detection. So produces an X-derivative of the image.

You can rotate this kernel using the 'angle' argument, generally in multiples of 90 degrees. However you can also rotate it 45 degree multiples, even though it was not designed for this. This is useful for getting 45 degree quantized directional derivatives or the gradient magnitude from the maximum of all 45 degree rotated derivative results.

Here is the result of using default 'Sobel' kernel. convert face.png -set option:convolve:scale '50%!' -bias 50% \ -morphology Convolve Sobel face_sobel.png

Note that it tends to produce a 3 pixel thick by very strong edge. Much stronger than a laplacian edge detector.

Here it is again, but rotated 90 degrees (top to bottom). convert face.png -set option:convolve:scale '50%!' -bias 50% \ -morphology Convolve Sobel:90 face_sobel_90.png

If you look at the kernel you may think that it is declared backwards. In one sense you are actually correct. However this is due to the way 'Convolve actually works. This will be looked at in more detail in Convolve vs Correlate below.

One way to collect all the edges of an image using a 'Sobel' kernel, is to apply the kernel 4 times in all directions, and collect the maximum value seen (using a Lighten Mathematical Composition. This is an approximation to the gradient magnitude.

convert face.png -set option:convolve:scale '!' \ \( -clone 0 -morphology Convolve Sobel:0 \) \ \( -clone 0 -morphology Convolve Sobel:90 \) \ \( -clone 0 -morphology Convolve Sobel:180 \) \ \( -clone 0 -morphology Convolve Sobel:270 \) \ -delete 0 -background Black -compose Lighten -flatten \ face_sobel_maximum.png

ASIDE: The reason you get a blue edge around the yellow star is that the difference between the 'yellow' star, and the 'white' background is a subtraction of blue color. If the background was black, you would get a yellow edge color.

You can simplify the above by making use of the Multiple Kernel Handling features of IM morphology. That is you can create a rotated list of all 90 degree rotations of the 'Sobel' kernel.

convert face.png -set option:convolve:scale '!' \ -set option:morphology:compose Lighten \ -morphology Convolve 'Sobel:>' face_sobel_maximum_2.png

If you want to see exactly what the above is doing add the Show Kernel setting, and the Verbose setting.

A better approximation for the gradient magnitude would be to use the fact that a 180 degree rotation, simply produces the same result as a negating the kernel, and thus the results. As such the X and Y derivative (90 degree rotated convolves), with some trickiness to get the absolute values of the convolution, can achieve such a result with less work image processing.

convert face.png -set option:convolve:scale '50%!' -bias 50% \ \( -clone 0 -morphology Convolve Sobel:0 \) \ \( -clone 0 -morphology Convolve Sobel:90 \) \ -delete 0 -solarize 50% -level 50,0% \ -compose Lighten -composite face_sobel_maximum_3.png

This is typically good enough for most purposes.

A more exact magnitude of all the slopes can be extracted by doing a vector addition of the two X and Y derivatives (as per Pythagorean Theorem).

convert face.png -set option:convolve:scale '50%!' -bias 50% \ \( -clone 0 -morphology Convolve Sobel:0 \) \ \( -clone 0 -morphology Convolve Sobel:90 \) \ -delete 0 -solarize 50% -level 50,0% \ +level 0,70% -gamma 0.5 -compose plus -composite -gamma 2 \ -auto-level face_sobel_magnitude.png

The "-gamma" function in the above use being used to perform a mathematical 'Square' and 'Square Root' of the values returned by the 'Sobel' results. For more detail see Power Of Maths Function. The extra "+level" ensures the Plus Composition does not overflow the image quantum range. See Quantum Effects, non-HDRI vs HDRI for details.

Instead of the magnitude you can extract the direction of the slope from the two edge detection results.

The first "-fx" expression is the one that uses a 'atan()' function to convert a X,Y vector into an angle. This is then colored with the an external Rainbow Gradient Image, as a Color Lookup Table. The second "-fx" expression create a thresholded transparency mask to make any areas without a slope transparent.

However the above technique tends to produce huge mess of information for real images as it does not take into account the magnitude of the slope.

Here is another more complex version. This does almost all the calculations in the green 'G' channel, so as to reduce the amount of image processing needed by a factor of three. It then uses HSB colorspace to create direction (hue) and magnitude (brightness).

convert face.png -colorspace Gray -channel G \ -set option:convolve:scale '50%!' -bias 50% \ \( -clone 0 -morphology Convolve Sobel:0 \) \ \( -clone 0 -morphology Convolve Sobel:90 \) \ -delete 0 \ \( -clone 0,1 -fx '0.5 + atan2(v-0.5,0.5-u)/pi/2' \) \ \( -clone 0 -fill white -colorize 100% \) \ \( -clone 0,1 -fx 'hypot(u-0.5,v-0.5)*2' \) \ -delete 0,1 -separate +channel \ -set colorspace HSB -combine -colorspace RGB \ face_sobel_magnitude_n_direction.png

Roberts

Roberts:{angle}

The 'Roberts' kernel is far simplier that the previous 'Sobel' kernel, and will produce an even tighter edge location (down to 2 pixels). Of course that also makes it more prone to noise effects.

Normally this kernel is represented by a much smaller 2x1 or even a 2x2 kernel, however by implementing it as a 3x3 kernel I can 'cyclically' rotate the kernel in 45 degree increments.

For example here is a 45 degree result, more commonly known as a 'Roberts-Cross' kernel. convert face.png -set option:convolve:scale '50%!' -bias 50% \ -morphology Convolve Roberts:45 face_roberts.png

As with 'Sobel' you can also use Multi-Kernel Handling to generate a maximum slope from all directions. But this time we will get 8 x 45 degree directions, rather than just 4.

convert face.png -set option:morphology:compose Lighten \ -morphology Convolve 'Roberts:@' face_roberts_maximum.png

Note that as rotating this kernel does not generate a negated result (it is offset by a single pixel), you can not simply merge half the number of convolutions, as you can with 'Sobel'.

Basically the slope generated by just one 'Sobel' convolution, is offset by half a pixel from aligning with the actual image. This is the reason why 2x2 kernels are very uncommon.

Prewitt

Prewitt:{angle}

The 'Prewitt' kernel is very similar to a 'Sobel', though much looser on the exact direction of the specific edge detection. The result is thus a little more fuzzy.

convert face.png -set option:convolve:scale '50%!' -bias 50% \ -morphology Convolve Prewitt face_prewitt.png

Compass

Compass:{angle}

This is the 'Prewitt Compass' kernel which has a stronger directional sense than 'Sobel'.

convert face.png -set option:convolve:scale '50%!' -bias 50% \ -morphology Convolve Compass face_compass.png

Kirsch

Kirsch:{angle}

This is another strong direction sensing edge detector.

convert face.png -set option:convolve:scale '50%!' -bias 50% \ -morphology Convolve Kirsch face_kirsch.png

Frei-Chen

Two sets of kernels are provided by this built-in.

The first is a 'Isotropic' (uniform direction) varient of 'Sobel', where the '2' values have been replaced by a Square Root of 2.

Frei-Chen:[{type},][{angle}]

The kernel above is the default unweighted kernel that is the heart of the 'Frei-Chen' kernel.

convert face.png -set option:convolve:scale '50%!' -bias 50% \ -morphology Convolve Frei-Chen face_freichen.png

Like 'Sobel', this kernel should be applied using an angle in multiples of 90 degrees.

To make things easier two kernels (with the same weighting) have been provided, one like the above for orthogonal use, the other for diagonal use.

Frei-Chen:1

Frei-Chen:2

The third set of types consists of 9 specially designed and weighted kernels that is used not only for edge detection in a specific direction, but also for determining the actual angle of a sharp edge.

The 'type' in this can is a number from '11' to '19', allowing you to extract any one of the 9 kernels in the set.

However if you give a 'type' value of '10' you will get a multi-kernel list of all 9, pre-weighted kernels.

The kernels are each applied to the original image, then the results are added
together to generate the edge detection result.

This is best done using a HDRI version of
ImageMagick.

   convert image.png \
           \( -clone 0 -morphology Convolve FreiChen:11 \) \
           \( -clone 0 -morphology Convolve FreiChen:12 \) \
           \( -clone 0 -morphology Convolve FreiChen:13 \) \
           \( -clone 0 -morphology Convolve FreiChen:14 \) \
           \( -clone 0 -morphology Convolve FreiChen:15 \) \
           \( -clone 0 -morphology Convolve FreiChen:16 \) \
           \( -clone 0 -morphology Convolve FreiChen:17 \) \
           \( -clone 0 -morphology Convolve FreiChen:18 \) \
           \( -clone 0 -morphology Convolve FreiChen:19 \) \
           -delete 0 -background Black -compose Plus -flatten \
           result.pfm

If a type of -1 is given then a multi-kernel list of all the weighted kernels
is generated. This lets you use multi-kernel composition to do the above much
more simply...

    convert image.png  -set option:morphology:compose plus \
          -morphology Convolve FreiChen:10 \
          result.pfm

Sharpening Images with Edge Detection (enhancing the edges of the original image)

The 'LoG' and 'DoG' kernels can also be used to sharpen images, as opposed to Un-sharpening Images using Blurs.

However as these kernels are Zero-Summing you will need to simply add 100% of the 'Unity' or "Identity" kernel.

For example... convert face.png -set option:convolve:scale '!,100%' \ -morphology Convolve 'Log:0x2' face_sharpen.png

This is a much broader smoother sharpening of the image than what the Unsharp technqiue generated. That is because it is an actual or true sharpening of the image, and not one faked by the subtraction (masking) of a blur.

Unlike Unsharp, sharpening images in this way can not use a fast 2-pass convolution method. Because of this Un-sharp is usually the more preferred method.

You can also control the amount of sharpening by scaling the kernel component being added.

For example less sharp... convert face.png -set option:convolve:scale '50!,100%' \ -morphology Convolve 'Log:0x2' face_sharpen_50.png

Or more sharp... convert face.png -set option:convolve:scale '150!,100%' \ -morphology Convolve 'Log:0x2' face_sharpen_150.png

---

Neighbour Counting

One of the more unusual things convolution can be put to is known as neighbour counting. That is figuring out how many pixels exist in a particular area surrounding a particular point in an image.

Counting Neighbours

The Game of Life

In 1970 a British mathematician, John Horton Conway, publish in Scientific American, a special simulation which became known as 'Conway's Game of Life.

It was based on a grid of points where each point was either 'alive' 'dead'. What 'cells' were 'alive' or 'dead' in the next 'generation' depended of a set of very simple rules purely based on the number of cells that was alive or dead around them.

• The neighbourhood is the 8 pixels surrounding each 'cell'.
• A 'live' cell continues to live if it has 2 or 3 neighbours.
• A 'dead' cell becomes 'live' (born) if it has exactly 3 neighbours.
• Otherwise the cell becomes or remains 'deadA'.

So lets implement this using ImageMagick.

First to make things easy we will make 'live' cells white, and 'dead' cells black. That way we are only counting 'white' pixels, surrounding each cell, in a 8 pixel neighbourhood. However we could also implemented with black and white swapped, though it would be harder to follow how it is done.

However the rules has a strong dependency on if the central cell is alive or dead. So we need to separate the neighbourhood counts for a 'dead' cell from those of a 'live' cell. That can be simply done by giving the central cell a larger value than the sum of all its neighbours. A value of '10' is good for this. Its nice round number that is larger than the maximum neighbourhood count of 8.

That makes the 'Game of Life' Convolution kernel equivelent to..

'3: 1, 1, 1   1, 10, 1 1, 1, 1'

The result of this will be a count of the 8 neighbours around each pixel (is 'white), plus a value of 10 if the central pixel is 'live' or 'white'. as such the value of this kernel will be either '0' to '8' for dead pixels or '10' to '18' for live pixels.

If we scale this kernel by a value of 20 (or scaled by '0.05, see below), you will generate an image with 21 posible grey-levels. That is you will get a 'black' for a value for the '0' grey-level and a white value for the '21' grey-level, not that the kernel would actually generate such a value.

Now we can encode the 'Game of Life' rules into an Color Lookup Table Image, so as to convert the resulting neighbour count 'grey-level', generated by the above kernel, into the appropriate 'life and death' result according to the 'Life Rules'.

The image is very small, so I used a special Enlarge Image Script to generate a larger version, with each pixel clearly seperated.

Basically the first 10 pixels are what to do for a 'dead cell', the next 10 pixels what to do for a 'live cell', one one more to make it 21 pixels for the number of grey-levels. thus we have a 21 pixel Color Lookup Table.

The first white pixel on the left side (neighbour count = 3 around a dead cell) is a 'birth', while the two white pixels on the right side (neighbour counts 2 and 3 next to a live cell) allows a 'live cell' to continue to live. Any other result leaves the result as black (dead).

In summary, if we divide the convolution kernel by 20, and you will need a CLUT that is 21 pixels long (with Integer Interpolation) to match convolution results (grey-levels) to the right output color value.

So lets apply this to a image containing a 'life' pattern, multiple times to see it in action...

convert -size 15x15 xc:black -fill white \ -draw 'line 3,2 3,4 line 10,10 12,10 point 10,11 point 11,12' \ life_gen_000.gif convert life_gen_000.gif -set option:convolve:scale 0.05 \ -morphology Convolve '3:1,1,1 1,10,1 1,1,1' \ life_clut.gif -interpolate integer -clut \ life_gen_001.gif convert life_gen_001.gif -set option:convolve:scale 0.05 \ -morphology Convolve '3:1,1,1 1,10,1 1,1,1' \ life_clut.gif -interpolate integer -clut \ life_gen_002.gif convert life_gen_002.gif -set option:convolve:scale 0.05 \ -morphology Convolve '3:1,1,1 1,10,1 1,1,1' \ life_clut.gif -interpolate integer -clut \ life_gen_003.gif convert life_gen_003.gif -set option:convolve:scale 0.05 \ -morphology Convolve '3:1,1,1 1,10,1 1,1,1' \ life_clut.gif -interpolate integer -clut \ life_gen_004.gif

As you can see the 'Life' patterns in the enlarged images shown, behave as they should (if you are familar with the patterns). The 'blinker' in the top left corner flips back and forth, while the 'glider' in the bottom moved 1 diagonal step toward it, over 4 'generations' I iterated the life rules.

And here is a larger example where I generate an animation of 60 frames from a special life pattern, known as a 'Glider Gun' (period 30), shown to the right in its original size.

convert glider_gun.gif life_pattern.gif for i in `seq 59`; do convert life_pattern.gif -set option:convolve:scale 0.05 \ -morphology Convolve '3:1,1,1 1,10,1 1,1,1' \ life_clut.gif -interpolate integer -clut \ -write life_pattern.gif miff:- done | convert - -scale 500% \ -set delay 10 -layers Optimize -loop 0 glider_gun_anim.gif convert glider_gun.gif -scale 500% life_pattern.gif

Note that the reason the glider 'explodes' on the bottom edge is because of the default 'Virtual Pixel' handling that convolve uses.

More life pattern images can be found in the Life Pattern Catalog, though you will need to recolor the images for use in the above life processor.

I'll leave it as an exercise for someone to put the above into a script, that can generate a life sequence for some particular input image.

This is just one example of whole range of 'Cellular Automata' that IM could process. Of course their are many faster dedicated programs for 'Life' and 'Cellular Automata' in general, that can do the same thing, but it does show what IM is capable of doing. You can even make use of the other Morphology methods such as Hit and Miss Pattern Searching to search for specific patterns.

---

Correlate   ( )

Where the 'Convolve' method is basically used for image processing, the 'Correlate' method is designed more for pattern matching. This is, it performs a 'Cross-Correlation' of an image with its kernel, looking for that kernel shape within the image.

In reality they are almost exactly the same. The only difference between then is actually very minor, namely, an x and y reflection (equivalent to a 180 \ degree rotation) of the kernel.

The best guide on the how correlation and convolution work and how they differ to each other is Class Notes for CMSC 426, Fall 2005, by David Jacobs.

Convolution vs Correlation (asymmetrical kernel effects)

As I mentioned above the two operators 'Convolve' and 'Correlate' are essentially the same. In fact users often say convolution, when what they really mean is a correlation. Also correlation is actually the simpler method to understand.

For kernels which are symmetrical around a central 'origin', which is very typically the case, the two methods are actually the same. The difference only becomes apparent when you are using a asymmetrical or uneven kernel.

For example, here I use a 'L' shaped 'flat' kernel against our 'single pixel' image.

convert pixel.gif \ -morphology Convolve '3: 1,0,0 1,0,0 1,1,0' convolve_shape.gif

As you can see a 'Convolve' expanded the single pixel in the center to form the 'L' shape around it. Even when the origin itself was not part of the 'neighbourhood'.

Now lets repeat this example but using 'Correlate' instead.

convert pixel.gif \ -morphology Correlate '3: 1,0,0 1,0,0 1,1,0' correlate_shape.gif

As you can see 'Correlate' also expanded the single pixel, to form a 'L' shape but it was a 'rotated' 'L' shape.

This is essentially the only difference between these two methods. The 'Correlate' method applies the kernel 'AS IS' which results in the single pixel expanding into a 'rotated' form. On the other hand 'Convolve' actually uses an 180 degree 'rotated' form of the kernel so that each pixel gets expanded into the same non-rotated shape.

If you like to see some great examples of how 'Convolve' actually does works, I recommend you also have a look at EECE \ CS 253 Image Processing, Lecture 7, Spatial Convolution. The diagram on page 22, where it actually applies the 'reflected' kernel to a single pixel, just as I did above.

This rotation difference may not seem like much, but it means that in terms of the mathematics, a convolve operation (represented by a asterix ('*') symbol) is commutative in that if both kernel and image were treated as just an array of values (or two images), then F * G == G * F. It also means convolve is associtive in that ( F * G ) * H == F * ( G * H ).

Basically 'Convolve' acts more like a mathematical 'multiply', while 'Correlate' does not (unless the kernels involved are x and y reflectively symmetrical). See Convolution Properties, Wikipedia for more information on this.

Correlation and Shape Searching

The real use of the 'Correlate' method, (applying the kernel 'as is'), is an old, but simple method of locating shapes objects that roughly match the shape found in the provided kernel.

For example if we were to use 'Correlate' with an 'L' shaped kernel and attempt to search the image that we created with the convolution method example above, we get...

convert convolve_shape.gif -set option:convolve:scale '1!' \ -morphology Correlate '3: 1,0,0 1,0,0 1,1,0' correlate.gif

Note that I used IM's Kernel Normalization to prevent the final results becoming too bright, and swamping the 'peak' in a sea of white points.

As you can see the 'Correlate' method produced a maximum brightness at the point where the kernel 'origin' exactly matches the same shape in the image. But it also produces less bright results where you only get a partial match of the shape. The more of the shape that matched, the brighter the pixel becomes.

I would warn you however that while 'Correlate' succeeded in this case, it is not really a great way of doing so. For example, it can generate a very large number of false matches in areas of very high brightness.

This problem can be mitigated by using negative values for areas that should match the dark background of the image instead. That is, areas that do not match the background should make the resulting pixel less bright.

convert convolve_shape.gif -set option:convolve:scale 1^ \ -morphology Correlate '4x5+2+2: 0 -1 0 0 -1 +1 -1 0 -1 +1 -1 0 -1 +1 +1 -1 0 -1 -1 0 ' correlate_pattern.gif

ASIDE: To make things clearer, I generated the kernel image so that positive (foreground) values are white, negative (background) values are black and the zero (don't care) values are transparent.

As you can see, the matching peak is much more pronounced, as you are now not only matching forground pixels, but background pixels as well.

Note the use of the special normalization flag '^' in the above. This is important as it will normalize the positive and negative values in the kernel separately. That is you want to search for foreground pixels equally with the background pixels.

This means that you can search for both positive and negative matches of the given shape by using an HDRI version of IM or with the appropriate use of Output Bias (see above).

For example, here I apply the 'L' shape search to a test image containing both positive and negative 'L' shapes.

convert test.gif -bias 50% -set option:convolve:scale 50%^ \ -morphology Correlate '4x5+2+2: 0 -1 0 0 -1 1 -1 0 -1 1 -1 0 -1 1 1 -1 0 -1 -1 0 ' correlate_bias.gif

The Output Bias made the normal output of the search a mid-tone grey, while the matching shapes are given brighter or darker colors, depending on the number of pixels that actually match the 'shape kernel'. If you examine the actual values of the output image only, one pure-white and one pure-black pixel are produced, indicating perfect matches. However there are also quite a number of near-matches as well.

Once you have a 'Correlate' matching image, you need to try to find and matching 'peaks'. This can be done using another Correlation, but does not always work very well.

The better method is to use the more exact pattern matching method, 'HitAndMiss' morphology, with the special 'Peaks' which was created for this purpose. This finds any single pixel that is only surrounded by darker colored pixels. Other 'Peaks' kernels can be used to find 'looser' matches.

convert correlate_bias.gif -morphology hitandmiss peaks:1.9 \ -auto-level correlate_peaks.gif

Future: pointer to a 'peak finding' section , in Image Compares

FUTURE: pointer to using Normalize Cross Correlation with the Fast Fourier Transform for generating very fast image Correlations, with very large images (both source image and sub-image).

Correlation vs HitAnd Miss Morphology

If you compare the kernel image as I represented it to kernels that are used by the Hit-And-Miss Morphology Method, you will find they actually represent the same thing.

	'HitAndMiss'	'Correlate'
Don't Care	A value of 'Nan' or '0.5'	A value of 'Nan' or '0.0'
Background	A value of '0.5'	A value of '-1.0' (before normalization)
Results	Subtracts the minimum of the foreground from the maximum of background. Only exact matches will thus produce positive results and thresholding will produce a binary matching image.	Generates a range of how closely the image matches a shape. It is possible for some background pixels to be larger in value than foreground pixels as long as the overall pattern is present. Can be difficult to locate specific 'matching' peaks. You can also find negative matches.

As you can see they to correspond to each other. Thus a kernel for one could be transformed into a kernel for the other (Posible future addition to IM).

However 'Hit-And-Miss' will only find exact matches with a definite foreground to background difference. As such, it is much less forgiving of noise and near misses than 'Correlate'.

On the other hand 'Correlate' can be performed using linear image processing and more specifically using a Fast Fourier Transform. This can make pattern match with larger patterns and kernels a lot faster, especially when multiple patterns are involved, saving you the cost of transforming images and patterns into the frequency domain.

Which you use is really up to you, and what results you are after.

Note that for finding exact matches of small color images within larger images, the Sub-Image Locating Feature of the "compare" program will provide a much better method than either 'Hit-And-Miss' or 'Correlate' methods. This is because it uses a 'least squares of color vector differences' to do the sub-image matching, which can produce a better metric for match results.

---

Created: 26 May 2010 (Separated from "morphology")
Updated: 13 June 2010
Author: Anthony Thyssen, <A.Thyssen@griffith.edu.au>
Major Input: Fred Weinhaus, <fmw at alink dot net>
Examples Generated with:
URL: http://www.imagemagick.org/Usage/convolve/