ImageMagick v6 Examples --
Morphology and Convolution

Index

ImageMagick Examples Preface and Index

Morphology Introduction

• Morphology Operator
• Basic Built-In Kernels
  • Square,  Diamond,  Disk,  Plus,  Rectangle
  • User Defined Kernel
• Iterating (Repeating) Morphology Operations
• Verbose Output of Changes (for monitoring)
• Displaying the Generated Kernel (for debugging purposes)

Convolution and Correlation (Weighted Average of the Neighbourhood)

• Convolve Kernel Scaling and Normalization
• Convolve vs Correlate (and asymmetric kernel effects)
• Correlate
• Convolve Kernels
  • Mean or Average Filtering using Shape Kernels
  • Gaussian,  Blur,  Comet, 
• Gaussian vs Blur Kernels
• Output result Bias Control
• Normalization for Zero average Kernels
• Other Convolution Kernels

Basic Morphology Methods

• Erode,  Dilate,  Open,  Close
• Morphological Smoothing
• Basic Morphology and channels
• Flat Grey-scale Morphology
• True Grey-scale or 3-dimensional Morphology
• Intensity Variant of Basic Methods
• Granularity of a Collection of Shapes
• Asymmetric Kernel Effects (method tests)

Subtractive Morphology Methods

• Edge-In,  Edge-Out,  Edge,  Top-Hat,  Bottom-Hat

Distance Morphology Method

• Distance Kernels, 
  • Chebyshev,  Manhatten,  Euclidean (knight),  Euclidean, 
  • Comparison of Distance Kernels
  • Special User defined Distance Kernels
• Distance with an anti-aliased shape

Generating Skeletons from Shapes. Under Construction

• Distance to Skeleton

These operators make changes to images one pixel at a time, based on the nearby local 'neighbourhood' of the other pixels that surround it. This in turn can provide a huge range of effects, from the 'blurs' seen in the previous section, to modifying shapes or searching or specific patterns or other objects within the image.

---

Morphology Introduction

Morphology was originally developed as a method by which the structure of shapes within an image could be cleaned up and studied. It works by comparing each pixel in the image against its neighbours in various ways, so as to either add or remove, brighten or darken that pixel. Applied over a whole image, specific shapes and be found and/or removed and modified.

For example if an pixel is white and completely surrounded by other white pixels, then that pixel is obviously not on the edge of the image. You may then like to make that pixel black, so as to leave only edge pixels turned on. A method known as 'EdgeIn'.

The whole process actually depends on the definition of a 'Structuring Element' or 'Kernel', which defines what pixels are to be classed as 'neighbours' for the morphological method. Exactly what size and shape this 'neighbourhood' should be often depends on just what you are trying to achieve.

Here are some examples of various kernels, defining 'neighbourhoods' around the central pixel, 'origin'. The images have been scaled to make them easier to see the individual pixels, as typically the neighbourhoods are very small.

Note that these are only examples of small neighbourhoods. Each of the shapes can be made larger, typically by increasing a 'radius' argument that is specific for the kernel being selected or defined. For simple kernels such as the first three a morphological method could be repeated (iterated) to increase the effective of pixels further away from the 'origin' of the neighbourhood, though this does not always work.

The final size and shape of a 'Structuring Element', as a kernel is termed in morphology, is important as a means of locating and enhancing or deleting image elements that are larger or smaller than this shape. This is what makes morphology extremely powerful as a means of sorting out various elements within images. However the larger the kernel, the longer the morphological methods will take, so it is better to keep the kernels small.

Note that all but the last kernels are actually shaped. The parts not displayed were specifically flagged as not being part of the actual 'neighbourhood'. That is they will do not actually have any value, and will not take part in any of the morphology calculations at all.

Also note how the second last kernel not only has a 'on' value but also an 'off' value as as part of its 'shape'. Both values are important to the Hit-n-Miss method (see below), while this specific kernel is one of a number used for 'pruning' the ends of lines within images.

The last 'kernel' shown above is not 'shaped', but fully defined over the kernels full rectangular (square) area. The actual values however range from maximum (white or 1.0) at the center to a zero value (black or 0.0) as it approaches the edges. This is important as the values can be used by the specific morphologically method to indicate how much of an effect each pixel in the surrounding neighbourhood has on the final result.

This type of kernel is especially important in 'Convolution', a special method that has been around far longer than morphology itself. In fact IM has a large number of built-in kernels specifically for this method.

A more exact way of looking at the actual values of a kernel is to use the special 'showkernel' expert option. (see below).

Morphology Operator

The "-morphology" operator is a very complex, as it provides the user with a lot of controls over its actions.

Note that you need to provide at lest two items, the morphology 'method', telling the operator type of operation you want to apply to the image, and a 'kernel' specifying the how the 'neighbouring' pixels should effect the final result. Both are equally important and can have far reaching consequences.

The 'plus' form of the operator will use a internal default 'kernel' that is the most appropriate for that operator. However their are some morphological methods that can only be specified using the 'plus' syntax, due to the specific nature of the method.

You can get a list of the methods that are available using "-list morphology". A list of the built-in kernels that we have included in IM can be see with "-list kernel". We will go though the various methods and more specialized kernels they may use later.

Basic Built-In Shape Kernels

As the kernel is common to all the morphology methods, and the results of the various methods depend heavily on the actual kernel selected, we will first look at how you can define or select a kernel to use.

A good selection of kernels have already predefined for you and often you need look no further than these. You can get a list of the pre-defined built-in kernels by using "-list kernel" All kernels have a specific size, typically a square which has a odd number of pixels per size, the center of which is the 'origin' of the kernel. However as you will see the "-morphology" operator is not restricted to this limitation.

The most common kernel_argument used for built-in kernels, and generally the first argument given is a 'radius'. This defines how big the typical odd-sized square neighbourhood of the kernel will be. The final kernel size will generally be twice the radius plus one (for the center pixel). That is a 'radius' of '2' will create a kernel that is 5×5 pixels square.

While a 'radius' typically defines the size of the final kernel, and thus the overall speed of the morphological operation over the images, it may not be the most important factor, especially for Convolution Kernels where the values have a greater effect than the kernels size.

If a 'radius' set to 0, or left undefined the 'radius' will automatically default to some reasonable or most commonly used value, depending on the kernel involved.

Diamond

A simple way to look at the basic kernel is to use a Dilate morphology method, on an image containing a single white pixel on a black background. This basically expands the single pixel into the 'shape' of the kernels neighbourhood.

For example, here is the result of using 'Dilate' with the minimal 'Diamond' built-in kernel.

Remember all the kernel image results in this area of IM examples have been enlarged to allow you to see the individual pixels. In reality all the kernels and the results we show here are very small, as they should be. In this case the image being dilated only 11×11 pixels in size and has been scaled 8 times for display.

This is actually a fairly good kernel for morphological operations, and basically defines the most minimal practical neighbourhood: the original pixel, plus the four pixels in direct contact. Another name for this type of kernel is a 'Z₄' structuring element. It looks rather like a tiny 'plus' sign. The diamond shape only becomes apparent as the radius increases.

The optional kernel_arg for this kernel can take two values, like this...

For all the shape kernels the most important argument is radius and as mentioned before is an integer that represents the distance from the center 'origin' to the nearest edge.

As such the final 'Diamond' kernel is a square (2 times radius plus 1) containing the diamond shape. Here is the results of using a larger radius to generate a large kernel.

The other kernel_argument is scale which defaults to a value of 1.0. Typically this is used to change the actual values used by the kernel to form the shape. This is generally only important to special methods such as Convolve, and Grey-scale Morphology.

Square

The 'Square' is the most commonly used kernel for morphology.

By default the 'Square' kernel generates a 3x3 pixel square around the 'center'. convert pixel.gif -morphology Dilate Square kernel_square.gif

Basically this means that all 8 neighbours of the original pixel will be classed as part of that pixels neighbourhood. As a result it is a good kernel for averaging pixels, or expanding/shrinking some shape by one pixel.

As with all the shape kernels it takes the same kernel_arguments as shown for the Diamond Kernel above, with the first argument radius being the most important.

The default (radius=1) for this kernel as mentioned is a 3×3 square, and is commonly known as a 'Z₈' structuring element (for the number of immediate neighbours involved).

Disk

The 'Disk' kernel is as you would expect, a circular shape. And is commonly used for when a very large morphological kernel is needed.

However the radius argument for a disk can be a floating point number, which allows you to produce a quite a range of shapes, using small radii.

The final size of the kernel containing the disk is the 'radius' value rounded down, times 2 plus 1. As such the 'Disk:4.5' kernel has a kernel size radius of 4, making the final kernel size 4 times 2 plus 1, and generating a 9×9 kernel to hold the disk shape.

Note that a value less than one (but not zero) will always produce a single pixel kernel, though that is not very useful.

The default 'Disk:3.5' kernel is a particularly useful as it produces a very regular looking octagonal shaped kernel. This is especially good for generally rounding and smoothing of image shapes.

The most important thing to note is that a disk with a fractional radius works a lot better than one integer radius. Adding a fraction of about 0.3 to 0.5 is generally recommended, to avoid the off looking single pixel on the sides.

Plus

The 'Plus' kernel is actually a little different to the other morphological shape kernels, in that it is designed to represent a specific 'shape' rather than a simple 'neighbourhood' around a pixel. convert pixel.gif -morphology Dilate Plus kernel_plus.gif

Using a larger 'radius' with this kernel does not simply increase the size of the kernel, but lengthens the arms of the resulting plus sign. The thickness of the arms however does not increase.

You may notice that the default size of a 'Plus' kernel is actually a radius of 2 rather than 1 as in the previous kernels. In fact a 'Plus:1' kernel happens to be the same as a 'Diamond' kernel.

Note that a 'Plus' kernel is a generally not a good morphological kernel, and should be avoided for such purposes. However it is a very useful if you are wanting to find and highlight single points in an image. Basically it provides an alternative to Drawing Symbols, without needing to know exactly where the individual 'points' are.

Rectangle

The 'Rectangle' kernel is closely related to the 'Square' kernel above, and by default produces the same square 3x3 kernel. But rather than a simple radius argument, you can give is a 'geometry' argument to specify the exact size of the kernel wanted.

For example here we specify a 7x3 rectangle kernel. convert pixel.gif -morphology Dilate Rectangle:7x3 kernel_rect:7x3.gif

By default the kernel will try to set the 'origin' of the neighbourhood to the exact 'center' of the kernel. But for an even-sized rectangle, it will pick the point to the immediate top and/or left of the center as appropriate. convert pixel.gif -morphology Dilate Rectangle:6x3 kernel_rect:4x2.gif

However if you don't want the kernel's origin to be 'centered' you can specify your own 'origin' for the neighbourhood. For example here we pixk the left most pixel of a long single pixel high kernel for the 'Dilation' of the original single pixel. convert pixel.gif -morphology Dilate Rectangle:5x1+0+0 \ kernel_rect:5x1+0+0.gif

At this time you can not provide a scale factor for a rectangle. All its kernel values will be set to 1.0 only.

User Defined Kernels

You are not restricted to just the built-in kernels, but can also specify your own kernel, and giving the exact values you want the kernel to use...

The 'geometry' specification is basically exactly like that of the argument previous 'Rectangle' kernel. It gives the size of the kernel, and even the 'offset' of the neighbourhood 'origin'. If only one number is supplied for the 'geometry', a square kernel will be assumed. Remember this is NOT a 'radius' argument.

After the ':' (which is required after a 'geometry' specification) you then supply width × height floating point values separated by commas and/or spaces. A special value of 'nan' (meaning "Not a Number") or a '-' on its own, can be used to specify that this point in the kernel is not part of the neighbourhood.

If no 'geometry' or ':' is specified, then you are using a 'old' style specification, and a odd sized square kernel big enough to hold all the values given will be generated. This is not recommended and only provided for backward compatibility with older versions of ImageMagick.

For example here is a specification for a square kernel of width 3, that can be used as for convolution blurring of the single pixel image. convert pixel.gif -morphology Convolve \ "3: 0.3,0.6,0.3 0.6,1.0,0.6 0.3,0.6,0.3" \ kernel_user:3.gif

With a single pixel Convolve works almost the same as Dilate but works with the kernels values, rather the kernel shape. It generally has the same result.

Note how you can add extra spacing to the input string so as to separate the the individual rows of the rectangular kernel definition.

By default a "-morphology Convolve" does not do any normalization, scaling, or biasing of the results of the convolution method. If the above was done was done using the older "-convolve" operator (before IM v6.5.9) the result would be much darker due to its automatic normalization of the input kernel. For more details see the Convolve method below.

And here I defined a 5×3 rectangular area, but use the special 'nan' (not a number) values to cut off the corners to make an oval shaped kernel... convert pixel.gif -morphology Dilate \ "5x3: nan,1,1,1,nan 1,1,1,1,1 nan,1,1,1,nan " \ kernel_user:5x3.gif

And finally here is an example of specifying a rectangular neighbourhood, that forms a 'L' shape around the 'origin'. The origin of the kernel is not only that is not only not central, but the origin pixel is not even part of the neighbourhood! convert pixel.gif -morphology Dilate \ "2x3+1+1: 1,- 1,- 1,1 " kernel_lshape.gif

Note that instead of 'nan' I used '-' to specify the parts that is not part of the kernel. Of course the '-' must be surrounding by spaces or commas so it does not get confused with an actual minus sign.

As you can see user kernel specification is very flexible, allowing you to specify just about any type of kernel you like, whether it is a convolution kernel with lots of fractions, or a shaped kernel for morphological methods.

Iterating (Repeating) Morphology Operations

As you seen from the above you can generate a larger kernel, so as to apply a morphology over a larger neighbourhood.

However in some cases a faster alternative to using a larger kernel is to simply repeat (iterate or loop) the morphology operator multiple times. This means that the effect of that operator will be carried further, having the same basic effect as a using a larger kernel, but without the added computational cost of using a larger kernel.

For example, to produce the same result as a 'Diamond:3' you could repeat the operation three times using the default radius 1 kernel...

convert pixel.gif -morphology Dilate Diamond \ -morphology Dilate Diamond \ -morphology Dilate Diamond kernel_diamond_x3.gif

Now remember you are still only using a very small 3x3 kernel, but repeating the basic morphological operation three times to produce the same effect as if you are using a larger kernel. In fact repeating small kernels like this is actually a good deal faster than using the much larger kernel. Because repeating a morphological operation is very common, rather than repeating the operation multiple times, you can just ask IM to loop or iterate the operation, that many times. convert pixel.gif -morphology Dilate:3 Diamond kernel_diamond_3.gif

Using an 'iteration' to make the effective neighbourhood bigger, works for most 'circular' kernels, such as a 'Square' and 'Diamond'. But it does not work for all kernel types. For example for a non-convex kernel such as a 'Plus' (which is not a convex shape) it will produce a very unusual results.

For example... convert pixel.gif -morphology Dilate:2 Plus kernel_plus_2.gif

On the other hand iterating a 'Plus:1' kernel produces the same result as iterating a 'Diamond' kernel as they are really the same kernel shape.

Note that if you use a 'iteration' count of '0', the morphology will do nothing. This is a useful way to 'turn off' the operator when you don't want it to do anything, but do not want to remove it from the command line. See Kernel Debugging Output Display, below for another such use of a zero iteration count.

Using a special value of '-1', will repeat the operation until no more changes are seen in the image. That is the image reaches a point of 'convergence'. This is however dangerous, as in some situations could lead to very long running operations. For an operation such as for 'Dilate' for example it would simply repeat the dilation until the whole image was completely filled with white. Basically producing a sort of runaway 'flood fill'.

Iterating a 'Disk' kernel to produce a larger neighbourhood effect, is also generally not recommended. That is because the 'Disk' kernel becomes a more accurate disk shape as the radius gets larger. As such you may be better off using a larger radius.

However as a 'Disk' radius becomes really large (6 to 15 pixels in size) than a combination of radius and multiple iterations, could produce a faster, acceptable result. Caution and some experimentation with your specific situation may be needed.

Verbose Output of Changes

If you want to watch the iterations, you can set the "-verbose" option, which turns on the Verbose Operational Control. As the morphology operator iterates, it will report the iteration count, and how many pixels in the image were changed for each step, on standard error.

For example lets 'Dilate' the single pixel image using the larger 'Disk' kernel until the whole image has been filled with white (iterate count = '-1' for infinite), and no more changes can be made to the image.

	convert pixel.gif -verbose -morphology Dilate:-1 Disk \ +verbose iterate_disk.gif

Note the number of changes made in each iteration. Initially there were 36 pixels converted from black to white. Then 72 more on the next iteration, and finally the last 12 pixels (actually located in the corners) were also made white. The last dilation (iteration 4) resulted in no more changes to any pixel as all the pixels were now white, so the morphology aborts.

If the number does not reach zero, some limit to the number of iterations was reached. Either the number you provided (1 by default), or the internal limit that was set to prevent a never ending loop (currently the maximum width or height of the image).

Displaying the Kernel Generated (for debugging purposes)

You can see the kernel that was actually generated by using a special expert option "-set option:showkernel 1" (outputting to standard error).

For example, here is the actual values of a 'Disk' kernel...

	convert pixel.gif -set option:showkernel 1 \ -morphology Dilate Disk kernel_disk.gif

The special value of 'nan' in the above has the same meaning as when inputting a User Defined Kernel. It means 'Not A Number' and marks the parts of a kernel that is not part of the neighbourhood, and thus should not be processed during a morphological operation.

Here is another example, of a special 'Comet' kernel.

This is actually half a 1 Dimensional Gaussian Curve (with a default sigma of 1.0), and can provide a nice way of extracting such a curve from ImageMagick.

Note that as I only wanted to show the kernel, I really don't care about the image processing at all. As such I set the morphology 'iteration' to '0' (do nothing), and also discard any image result using a NULL: output file.

The size and spacing of the values in the output can be controlled by the special Precision Operational Control. That was added to IM at about the same time as the morphology operator.

For example here is an example of a 'Euclidean' distance kernel (see the Distance method below for more detail).

and here is the same kernel again, but using "-precision" to limit the number of significant digits from the default of 6 to 4.

The "-precision" option was added to ImageMagick version 6.5.9-1 during the morphology development cycle. As such may be regarded as always present for kernel output.

---

Convolution and Correlation

The 'Convolve' and the 'Correlate' methods are actually much older than morphology, though it is also a type of morphological method. However as you will see its effects are more grey-scale gradient effects, rather than shaping effects that morphology typically is involved with. This is why it is often regarded as a different, or separate operation to morphology.

Basically both of these methods performs a 'weighted average' of all the pixels in the neighbourhood specified. That is it multiplies the value of each pixel in the neighbourhood 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 surrounding it in the source image. Looking at it another way, the color of each pixel in the image will be either added to (blur) or subtracted (sharpen/edge detection) from its near by neighbours, according to the values in the kernel.

The to methods actually only differ in a very minor but important way, and for the examples and controls that we will now looking 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.

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

	convert pixel.gif -set option:showkernel 1 \ -morphology Convolve '3x3: 0.0, 0.5, 0.0 0.5, 1.0, 0.5 0.0, 0.5, 0.0' pixel_spread.gif

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

With convolutions a value of '0.0' in the kernel takes no part in the final calculation. As such this kernel only contains a 5 element neighbourhood. I could also have used 'nan' values, though that is not common practice.

Convolve Kernel Scaling and Normalization

However if you tried to apply this convolution kernel to an actual image you will have a problem.

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 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, 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 koala image, as each pixel was spread out to each of its immediate neighbours.

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 'convolve:scale' allows you to specify a global scaling factor for the kernel, and thus the brightness of the overall result.

convert koala.gif -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' \ koala_spread_scale.png

Rather then working out the scaling factor yourself, you can simply set the scaling option to a value of '0' to get IM to normalize the convolution kernel appropriately.

As the kernel is now automatically scaled and normalized, you can even simplify the kernel definition to remove the fractions.

convert koala.gif -set option:convolve:scale 0 \ -morphology Convolve '3x3: 0,1,0 1,2,1 0,1,0' \ koala_spread_normalize.png

Convolution vs Correlation (And asymmetric 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.

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. 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.

As you can see a 'Convolve' expanded the single pixel in the center to form the 'L' shape around it.

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

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

As you can see 'Correlate' also expanded the single pixel, to form a 'L' shape but it was a 'reflected' '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 'reflected' form. On the other hand 'Convolve' actually does a correlation but using a 'reflected' form of the kernel so as to cancel out the resulting 'reflection'. That is 'Convolve' produces a non-reflected copy of the kernel when given a single pixel.

If you like to see some great examples of how 'Convolve' actually all works, I recommend you have a look at EECE \ CS 253 Image Processing, Lecture 7, Spatial Convolution. The diagram on page 22, where that actually apply the convolve 'reflected' kernel to a single pixel is particular informative.

Correlate

The real use of the 'Correlate' method, (applying the kernel 'as is'), is as a old but simple methods 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...

Note that I performed an automatic Kernel Normalization this time to prevent the final results becoming too bright.

As you can see the 'Correlate' method produced a maximum brightness at the point where the kernel matches the same shape in the image.

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 mitigated by using negative values for areas that should match the dark background of the image instead. However to add these negative values a larger kernel may be needed...

convert lshape_convolve.gif -set option:convolve:scale .25 \ -morphology Correlate '4x5+2+2: -1 -1 -1 0 -1 1 -1 0 -1 1 -1 0 -1 1 1 -1 -1 -1 -1 -1 ' correlation_2.gif

Note that it is important that only the positive values in the kernel is used for the normalization of the kernel. As the provided kernel is negative, the automatic normalization has a tendency to go wrong. As such I manually calculated an appropriate Scaling Factor for the above example.

You may also like to scale the negative values used in the correlation kernel, separately so as to reduce its impact on the final result.

The 'Hit-n-Miss' morphology method, also produces similar results the last 'Correlate' example. however it generates its results in a different way.

However for finding a exact matches of small image within a larger image, the Sub-Image Locating Feature of the "compare" program provide a much better method, by using a 'least squares of differences' method.

FUTURE: pointer to using Convolution with the Fast Fourier Transform for generating very fast image correlations, with very large images.

Built-In Convolution Kernels

From the above you may have already noticed that kernels used for convolution generally has some particular qualities.

First convolution kernels generally involve an array of fractional values that are scaled so as to preserve the average brightness of the original image. That is the kernels are usually 'normalized'. Kernels are normally fully defined with values throughout the kernel array, with a zero value having the same meaning as 'nan' for values that are not part of the convolution neighbourhood. They are typically symmetrical, around the center, but not always. And as you will see below, convolution kernels typically involve a 'Gaussian Curve'. See the Wikipedia entry on the Gaussian filter for more information.

Many of these kernels are actually used by IM in many of its specific image processing operators, such as those already seen in Blurring, and Sharpening Images.

Mean or Average Filtering using Shape Kernels

Now 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 Shape Kernels to simply average the pixels over a given (large) area.

For example here I use a 'Square' kernel, to average the value all the pixels in the 5x5 square surrounding each pixel in an image.

convert koala.gif -set option:convolve:scale 0 \ -morphology Convolve Square:2 koala_square.png

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 as these shaped kernels are not normalized, so we need to ask IM to Normalize or Auto-scale the kernel before it is applied.

However you can also use the second 'scale' argument of the Shape Kernels to scale or normalize them. For example using a scaling factor of 1/25 or '0.04' as part of the kernels definition.

convert koala.gif -morphology Convolve Square:2,0.04 koala_square_2.png

The other Shape Kernels can also be used in the same way, to say average the pixel values over a diamond or a larger disk shape.

However while this constant averaging over a 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 most common use of a convolve is for blurring images. The ideal type of blur is known as a Gaussian Blur, using a 'Gaussian' kernel.

Here is an example of a small 'Gaussian' kernel...

As you can see by the convolution output range, and typical for kernels defined specifically designed for use with the 'Convolve' morphological method, it 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) in the center, with the smallest values toward the edges and the corners.

This kernel is the most typical convolution kernel you can get, and its complexity is why a built-in is provided for you, as well as for other IM image processing operators.

The 'kernel_args' to the Gaussian kernel is exactly the same as that of the "-gaussian" operator that normally makes use of this kernel. In fact all these operators are exactly equivalent to each other...

I did say this was a very common image processing operation, and because of this three different ways access the same function has developed.

The more important argument is 'sigma' which defines how blurred or 'spread out' each pixel should become.

The 'radius' argument limits the size of the generated kernel in the same way that it sets the size of the previous morphological kernels (such as 'Square', 'Diamond', and 'Disk'. It should be an integer that is at least twice that of the sigma value, or better still set it to zero ('0') so as to let IM work out the best 'radius' to produce the most accurate Gaussian blur.

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

Here typical Gaussian blur using a convolution...

convert koala.gif -gaussian 0x2 koala_gaussian.png

One final note. The 'plus' form of the 'Convolve' method is equivalent to using the default 'Gaussian' kernel where the sigma value has been set to 1.0.

Blur Kernel (1d gaussian blur)

The 'Blur' kernel is very similar to the Gaussian Kernel. But where gaussian is a 2-dimensional curve, the 'Blur' kernel produces a 1-dimensional curve. That is to say it is a long thin single row of values.

This can be used to to blur an image horizontally.

convert koala.gif -morphology Convolve Blur:0x4.0 koala_blur.png

The 'Blur' kernel_args' can also take a third argument that allows you to rotate the kernel 90 degrees, letting you blur the image vertically.

convert koala.gif -morphology Convolve Blur:0x4.0+90 koala_blur_vert.png

At this time only ninety degrees rotations of the 'Blur' kernel are possible. This may change in a later version of ImageMagick.

Comet Kernel (half 1d gaussian blur)

The 'Comet' kernel is almost exactly the same as a 'Blur' kernel, but is not symmetrical.

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, that is a bit like the tail of a comet, or the trail left by a meteor, or falling star.

convert koala.gif -morphology Convolve Comet:0x5 koala_comet.png

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

convert koala.gif -morphology Convolve comet:0x5+90 koala_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 tend 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. In fact one 'Gaussian' kernel can be replaced by two 'Blur' kernels.

For example the "-gaussian 0x2" of the last 'Gaussian' kernel example can be replicated as follows.

convert koala.gif -morphology Convolve Blur:0x2 \ -morphology Convolve Blur:0x2+90 koala_blur_x2.png

The above produces the exact same results as if I had used a "-blur 0x2 operation. This is in fact how the "-blur" operator works, and represents the

real difference between it and the "-gaussian" operator.

In terms of speed however the "-blur" operator is usually many times faster as it uses a much smaller kernels. The larger the blur (the size of the sigma argument) the bigger the difference between the two operations. As such the "-blur" operator is the recommended one.

The only practical difference in results between the two operators, are small quantum rounding effects (unless you are using HDRI), and edge effects. Both of which is caused by a loss of information between the two separate passes.

Output result Bias Control

The very old IM setting "-bias" can be used to set a 'zero' level in the resulting output image.

That way you can preserve the negative gradients generated, without needing to use a specially built HDRI Version of ImageMagick.

Normalization for Zero average Kernels

If a "-set option:convolve:scale 0" setting is used for automatic normalization of kernels, a zero averaging kernel will be scaled so that its output range occupies a '-0.5' to '+0.5' unit range.

This together with a "bias 50%" will ensure that the resulting image will preserve all the possible output values from the convolution.

Fred...

Perhaps I should also the use of a scale factor of '2!' to mean normalize then scale by 2, so as to produce a -1.0 to +1.0 range, or perhaps I should normalize directly to this range?

Also if you look at the 'Correlate' examples above you will see that it also has some special requirements. That is to normalize only the positive values in the kernel ignoring, or scaling the negative aspects separately. I think some use of normalization flags will be needed.

EG:  simple normalize  (as per the enforced normalization of the old -convolve)
     normalize then scale,
     normalize/scale just positive values.
     normalize/scale positive/negative components separatally.

Your thoughts on this matter? Now is the time to decide!

Other Convolution Kernels

Convolution Kernels...

General Convolution Operator...
  -convolve   -bias

  -convolve 1                   does not modify the image
  -bias {number}  -convolve 1   adds a fixed 'bias' to each pixels result.
  -bias 16384   -convolve .5    half color values, add 1/4 to each pixel
                                reduces black - grey25 and white to grey75

  More info at
    http://www.gamedev.net/reference/programming/features/imageproc/page2.asp
    http://www.dfanning.com/ip_tips/sharpen.html

  Sharpening using a Laplacian convolution 'kernel'
     -1, -1, -1
     -1,  9, -1
     -1, -1, -1
  That is  multiply each pixel by 9, then subtract a copy of each of its 8
  neighbouring pixels.

  A sharpening-mask ???
    -1, -1, -1
    -1,  8, -1
    -1, -1, -1

  Emboss an image
    -1,-1, 1
    -1, 0, 1
     0, 1, 1

  Sobel Edge detection...

    -1 0 1
    -2 0 2
    -1 0 1

  Note that while convolve will automatically scale the kernel by its
  average the last few kernels has a average of zero!  This means that
  convolve has no average value to scale by, so it uses the kernel AS IS!

  That means the user currently has to do the scale and bias himself!!!!

  Taking the Sobel convolve matrix above, it averages to zero, but can produce
  a maximum result of 4  (with a -4 negative, of course). To handle the
  negative we need a bias of 50%,  but than we need to scale the kernel so
  that   4 * white + 50%-grey  will produce white.  That is divide all the
  values by 8.

    -bias 50% -convolve '-0.125,0.0,0.125, -0.25,0.0,0.25, -0.125,0.0,0.125'

  Of course the result will have a predominately grey color (its bias), but
  if we only want the absolute value then we need to negate the colors
  with a negative bais and expand the color range again. That is easy to do
  with -solarize, and -level (with a negation of the range)

    -solarize 50% -level 50%,0%

---

Basic Morphology Methods

Where Convolution basically works with the gradients that is found within an image. All the other Morphology method, and typically what is meant by the term 'morphology operation' is more concerned with the shape of objects within an image. Expanding, shrinking, locating specific shapes, and so on.

The basic Shape Kernels already looked at above, will thus be the neighbourhood defining 'shapes' that will be most commonly used.

Because of this it most commonly works with images containing binary or Thresholded images containing simple black and white shapes. By convention white represents foreground, and black represents background. The method names are thus described according to this convention.

That is not to say the operators will not work with colored images, or have variants designed to work with color images, but their original purpose was to handle binary shapes.

Erode

The 'Erode' method does the opposite of a dilation, it 'eats away' the shape, from any background pixel making it smaller.

Its basic effects is to make any protuberances or points the image may have thinner, or remove them completely, but it also makes any holes that is present (such as caused by this images 'arm') in an image larger. In general the size of kernel, determines how many pixels are removed.

The "+morphology" of the a 'Erode' method defaults to the use of a 'Diamond' kernel. This is in line with the use of 'connectivity' which makes diagonally touching foreground objects and lines to be regards as one object, and separating the background on either side.

Dilate

As the name implies the 'Dilate' method will make a shape bigger according to the kernel (and the number of iterations) specified.

For example here is a simple binary 'man-like' shape that has been dilated (made larger) using a 'Disk' kernel.

Notice how the shape not only becomes larger, but its outlined becomes smoother. The large indent between the 'legs' has been filled in, as was the small single pixel 'hole' the image contained. The size and shape of the kernel determines how many pixels, and were are added around the edges of the image.

The "+morphology" of the a 'Dilate' method defaults to the use of a 'Square' kernel. This is in line with the use of 'connectivity' which makes diagonally touching foreground objects and lines to be regards as one object, and separating the background on either side.

The 'Dilate' and 'Erode' are dual. That is (at least with a symmetrical kernel) by negating the image before and after the applying the morphological method, you will actually perform the other form of the operator. For example here I perform a erosion by using 'Dilate' on the images Negating. convert shape.gif -negate \ -morphology Dilate Disk -negate dilate_shape_neg.gif

Open

This method also smooths the outline shape, but by rounding off any sharp points, and disconnecting 'opening' any thin bridges. However it does not remove any 'holes', or gaps, such as between the shapes 'legs'. Also as previously it does not make the basic 'core' size of the shape larger or smaller.

In actual real terms, what it does is to 'Erode' an image then 'Dilate' it again using the same kernel that was provided convert shape.gif -morphology Erode Disk \ -morphology Dilate Disk open_shape_2.gif

Note that performing a 'Open' on a shape that has already been opened, with the same kernel will result in no further change to the shape. For example...

That is repeating a 'Open' operation any number of times has no effect on the result.

Because of this, any iteration count provided will be applied to the individual dilate and erode sub-methods, and not to the method as a whole. That is a 'Open:2' iteration will actually be applied as a 'Erode:2, followed by an 'Dilate:2' to the image. This has the general effect of making the 'neighbourhood' defined by the kernel larger. convert shape.gif -morphology Open:2 Disk open_shape_x2.gif

Here you can see that the resulting larger neighbourhood did not just smooth the 'feet' of the shape, it removed them completely, while leaving the main body of the shape basically intact, though also smoother in appearance.

The "+morphology" of the a 'Open' method defaults to the use of a 'Diamond' kernel. This is in line with the use of 'connectivity' which makes diagonally touching foreground objects and lines, to be regards as one object, and separating the background on either side.

Close

The basic meaning of the 'Close' method is to reduce or remove any 'holes' or 'gaps' about the size of the kernel 'Structure Element'. That is 'close' parts of the background that are about that size.

The basic effect of this operator is to smooth the outline of the shape, by filling in (closing) any holes, and indentations. It also will form connecting 'bridges' to other shapes that are close enough for the kernel to touch both simultaneously. But it does not make the basic 'core' size of the shape larger or smaller.

In actual real terms, what it does is to 'Dilate' the image then 'Erode' it again using the same kernel that was provided convert shape.gif -morphology Dilate Disk \ -morphology Erode Disk close_shape_2.gif

Similarly as with 'Open', repeating the 'Close' method with the same kernel does not make any further changes to the image, however using an 'iteration' with the operator will repeat the internal sub-methods, so as to produce a stronger rounding effect.

And just as with the 'Dilate' and 'Erode' methods, the 'Open' and 'Close' methods are duals. You can reproduce the effect of the other 'dual' by Negating the image. convert shape.gif -negate -morphology Close Disk -negate close_shape_neg.gif

The "+morphology" of the a 'Close' method defaults to the use of a 'Square' kernel. This is in line with the use of 'connectivity' which makes diagonally touching foreground objects and lines, to be regards as one object, and separating the background on either side.

Morphological Smoothing of Shapes

Using both 'Open' and 'Close' methods are also often used in sequence to completely smooth out the outline of a shape. convert shape.gif -morphology Open Disk \ -morphology Close Disk smoothed_shape.gif

As you can see the indents and points have been smoothed and rounded off according to the size and shape of the kernel, the small default 'Disk' in this case.

The order of the two methods does have an effect on the results, and is usually decided by starting with the method that removes the least desirable aspect of the shape or image first. The above for example is the more typical ordering and will have the effect of first removing any pixel noise, that may be surrounding the shape before removing the holes, and filling in any gaps between components.

Applying the operators in the reverse order will remove indentations and holes first, before rounding off the points.

Basic Morphology and channels

All the above basic morphology methods are channel methods, as such they are applied to the individual channels of an image according to the correct "-channel" setting.

This means you can apply these methods to shape images, provided you are not too fussy about 'color leakage' from undefined transparent areas.

For example lets 'Erode" the alpha channel of the original 'man' overlay image, without modifying the color channels.

Flat Grey-scale Morphology

While essentially all four of the Basic Morphological Methods, and later ones which are defined in terms of these four methods, are specifically designed to work with binary images, they can be applied to both grey-scale and color images (though color images may generate some odd color effects).

Practical Example of Grey-scale Operation Wanted Here

However the kernel itself will always be regarded as a simple 'on' or 'off' neighbourhood. Any kernel value that is either a 'nan' or less than '0.5' will be regards as outside the 'neighbourhood' that it defines.

In more expert terms, the kernel is 'flat' without any 'height' or '3-dimensional' features.

True Gray-scale or 3-dimensional Morphology

True gray-scale or 3-dimensional morphology (as one library put it) will actually take the values found in the kernel and either add or subtract those values from the pixels in the image, before looking for the maximum/minimum values. This usage is very well documented.

Unfortunately I have not found any useful example of using true grey-scale morphology beyond 'flat shaped kernels', other than a comment about its use in 'photometric' processing.

Because of this I have not implemented true 3-dimensional grey-scale morphology. However if people need such non-flat grey-scale morphological operators, please let me know, and I will implement them.

However 'zero value' flat kernel shapes required for such methods can be generated by setting the second 'scale' argument to zero.

Note while the special 'Distance' method is actually similar to a true gray-scale morphology, in that it adds the kernel's value to each pixel value, before taking the smallest 'minimum' value, this does not match either the erode or dilate definitions. It is however closely related.

Intensity Varient for color images

As the above four methods, are grey-scale Channel methods, using them on color images can generate off color effects where one channel is modified, but another isn't. They are really not designed for use with multi-channel color images.

With this in mind I have created 'Intensity' versions of these methods. 'ErodeIntensity', 'DilateIntensity', 'OpenIntensity', 'CloseIntensity'.

These compare the pixels within the defined 'neighbourhood', and replaces the current pixel color according to the pixels intensity. That is the whole pixel color is used, and not the individual channels.

For grayscale images you should still get the same result as the previous normal methods.

This is experimental, and comments or problems with its use is welcome.

Granularity of a collection of Shapes

Note that using 'Erode' or an 'Open' with an image that has a large number of shapes in it is very useful. Any shape in the image that is similar to or smaller, than the given 'structuring element', will actually disappear completely! That means you can use these methods to remove specific elements, leaving 'islands' of pixels where the larger or different shaped elements were.

By doing this repeatedly to the original image with many different types and styles of structuring elements, you can get a idea of the 'granularity' and even the separate out (or 'segment') different areas of texture within an image.

By repeatally eroding the image and counting the number of 'shapes' you can get a good idea of the how many objects of each size is present.

Demonstration of determining the number and size a collection of shapes.

This usage was in fact the original driving force behind the original creation of the basic morphology methods, as used within a Paris mining company, in the 1960's. It allowed the creators to create a automated system to analyse the grain structure of microscopic photos of mineral samples to determine their suitability for mining.

Asymmetric Kernel Effects (Basic Method Tests)

Lets have a look at how these basic method work when used with a kernel which is not symmetrical. For example here I apply a user defined 'L' shape against a special morphological test image (enlarged for viewing individual pixels).

for method in erode dilate open close; do convert test.gif \ -morphology $method '2x3+1+1: 1,- 1,- 1,1 ' test_$method.gif done

Which has the following results...

'Erode' results in any exact match of the kernel shape, becoming a single white pixel at the matching point 'origin'. It will also expand any single pixel 'hole' into that same shape but 'reflected' around the 'origin', that is as if the kernel had been rotated 180 degrees.

'Dilate' As expected produces that same results but for the 'negative' form of the image. A single white pixel expands to the kernel shape, while any matching 'reflected' shaped hole, shrinks down to a single pixel 'hole'.

This brings up a specific point about these two methods. To convert one method into another method you not only need to Negate the image, you also need to rotate or reflate the kernel about the origin. Normally this second aspect can be ignored, if the kernel is 'symmetrical', which is commonly the case, and why it is often not mentioned.

'Open' as mentioned before, generally does not remove any 'holes' in the image, however an exactly matching shape will remain unchanged. Larger shapes (such as the negative half of the test image, may also remain, but perhaps slightly modified.

'Close' is an exact negative result of the previous, but does not need the kernel to be reflected.

One final warning. The boundary between position and negative halves of the image does move as part of the various methods. That is to be expected.

Basic Morphology Alternative for older versions of IM...

  If you want to generate a kernel that is all ones.
  for example a 7x7 array of 1's you can use a extremely large
  sigma and specify the appropriate radius, in a Gaussian blur.

  As such
     -convolve 1,1,1,1,1,.....
  for a total of 49 ones is equivalent to
     -gaussian-blur 3x65535

  This allows you to generate square kernel for binary morphological operators

  'Dilate'   for a 3x3 square kernel (radius=1) is thus
     -gaussian-blur 1x65535 -threshold 0
  'Erode'  is thus
     -gaussian-blur 1x65535 -threshold 99.999%

  As defined above
  'Open' is a 'Dilate' followed by a 'Erode'
  'Close' is a 'Erode' followed by a 'Dilate'

  Larger square kernels can be specified using larger radii
  but the other built-in kernel shapes are not available.

  These methods were implemented in Fred Weinhaus's script "morphology".
  which will work fine with older versions of ImageMagick.

---

Subtractive Morphology Methods

The next level of morphological methods is something I term subtractive morphology. That is each of the basic morphology methods is subtracted (using a composite minus, or composite difference) from either the original image, or another basic morphological result.

Essentially they return the pixels which were either added or removed from the original shape, giving you the outlines, and changes that the original method made to the image. They are essentially a 'Difference' or 'Minus' image compositions.

Edge-In

The 'Edge-In method, also called a 'Internal Gradient', subtracts the Erosion of the shape from its original. As a result the pixels that are closest to the edge, but which are still part of the original shape is returned.

The resulting edge is about half the size of the kernel given, which for a 'Disk' kernel is rather thick. More typically the you would use a much smaller 'Diamond' or 'Square' kernel, to produce a single pixel pixel outline of the shape.

Edge-Out

The 'EdgeOut' method, also called 'External Gradient', subtracts the original image from the Dilation of of that image. As a result the background pixels immediately next to the shape is returned.

Edge or Morphological Gradient

The 'Edge' method returns a 'Morphological Gradient', which can be described as either the addition of the last two 'edge' methods, or more specifically the subtraction of the Eroded shape from its Dilated shape.

As before the size and shape of the kernel defines the thickness of the eroded image. Its thickness is essentially equivalent to that kernel size, minus the center pixel.

Here for example is the 'Edge' outline of the shape using the minimal 'Diamond' kernel. convert shape.gif -morphology Edge Diamond shape_outline.gif The edge is two pixels thick as it contains the pixels that lie on either side of the actual 'pixel edge' of the original shape. The only way to make this edge thiner is actually to offset the whole image diagonally by half-a-pixel.

For more details of getting outlines of shapes in various ways see the section on Edge Detection.

Top-Hat

The 'TopHat' method, or more specifically 'White Top Hat', returns the pixels that were removed by a Opening of the shape, that is the pixels that were removed to round off the point, and those of any bridging connections.

As you can see the pixels often form small highly disjoint islands, with no set of pixels larger that the kernel used.

The methods name 'Top Hat' actually refers to the operators use when applied using the method for gray-scale 3-dimensional morphology, and not with binary images as we have done here.

Bottom-Hat

The 'BottomHat' method, also known as 'Black Top hat' is the pixels that a Closing of the shape added to the image. That is the holes, gaps, and bridges, that were filled in or created.

Again you can see that it also results in highly disjoint 'islands' of pixels, none of which is larger that the kernel used. However they are a completely different set of islands to the previous method.

---

Distance Gradient Morphology

The 'Distance' morphology method is the first of the many specialized methods that is possible. What it does is use a specialized kernel to measure the distance of each foreground pixel from the shapes 'edge'. More specially it measures the pixels distance from a 'zero' or 'black' color value.

It however only works with pure binary (white on black) shapes, though as you will see later you can modify a anti-aliased shape to work with the distance method. And only with specially designed Distance Kernels.

Here is an example of using the 'Distance' method, on our 'man' shape. An 'unlimited' iteration is generally used (unless you are only interested in the 'near-edge' pixels only).

Well that was real exciting, NOT! The problem is that the final images color is very very dark. But if you have a good monitor and can look close you may see a very dark 'ghost' like shape where the 'man' was.

What happened is that, at least for this small image, all the pixels are 'close' to the edge, and so do not get a very large 'distance' value.

A PNG image is recommended for any use of the 'Distance' method. That is because it provides a greater 'depth' than GIF, without any color loss like JPEG). It is also the reason the "+depth" operator was applied to ensure the output is reset to 16-bit depth (for my Q16 version of IM) when the 8-bit GIF image was read in. For users with a Q8 version if IM, I suggest you read about the 'scale' kernel option to adjust the 'color' values used.

By default with the built-in Distance Kernels the color value of 100 × distance_to_edge is assigned to every white pixel in the image. So lets look at at the largest color value that was set in the above image.

That is the largest color value in the resulting image was '1700' making the 'brightest' pixel in the image a very dark 2.5% grey, and its distance from the nearest edge, 17 pixels away, due to the default scaling of '100' in the build-in the kernel.

Lets Normalize the image using "-auto-level" so that this brightest, or most distant pixel is set to white, and allow us to actually see the 'distance gradient' that was generated. convert distance.png -auto-level distance_shape.gif As we no longer care about the exact 'distance' values generated for this image, I can now save and display it using the GIF image file format.

This is what the 'Distance' method does. Generate a gradient across the shape defining how far each pixel is from the nearest edge, according to the Distance Kernel used.

Another way of making the resulting 'distance' image brighter is to actually use a larger distance kernel 'scale' value. convert shape.gif -threshold 50% +depth \ -morphology Distance:-1 Euclidean:0,2000 distance_scaled.gif

This however very much depends on the actual size of the shape you are performing the 'Distance' method on. Too small and it is very dark, too large and the distance may get 'clipped' by the maximum 'QuantumValue' for your the in-memory Quality of your IM. For more details see Distance Kernel section below.

I would like to make one final note about the man-like 'shape' used in these examples. The shape contains a single pixel 'hole' that created a sort of 'gradient well' around it. This results in a very strong effect on upper half of the resulting 'distance gradient' image.

One solution to this is to remove that hole, by using 'Close' on the shape, so as to make it 'clean'. For example...

Of course this also has the effect of also 'closing' the gap between the shapes 'legs' too, which also effects the lower half of the final result.

Distance Kernels

The kernel given is very special, as it is used to define the actual distance measurements that is to be assigned to each pixel. For example here the Show Kernel output of one of the built-in 'Distance Kernels'.

The important thing to note is that the 'origin' (in this case the exact center of the kernel) has a value of zero. This is very important. That 'origin' is then surrounded by larger values, which increase with greater distance from that 'origin'. If the kernel is not defined in this specific way, unexpected and strange effects may result.

The value given in the kernel is the actual 'value' that will be assigned to the 'white' pixels in the image defining how far that pixel is from the edge.

All three of the provided built-in Distance kernels can take two optional kernel_arguments...

The first like all the Shape Kernels is the kernels radius which defines how big to make the generated kernel. By default radius is set to '1' for the built-in distance kernels, resulting in a very small 3 by 3 kernel.

The second argument 'scale' sets the distance 'scale used to represent the distance of one pixel length. As shown in the example above it defaults to a value of '100'. That is a pixel which is given a final pixel or grey-scale value of say '300 should be exactly '3 pixels away from the edge.

As mentioned previously large 'scale' value is used by default so that you can use 'fractional' distances for more 'exact' distance measurements. However only the 'Euclidean' distance kernel uses such 'fractional' values.

But in the previous example the 'largest distance' value assigned was '1700' which would overflow users using a Q8 version of ImageMagick (See Quality, in memory bit depth). A IM Q8, only allows color values to reach a maximum value of 255 (2^Q => 2⁸ => 256 color values, ranging from 0 to 255). As such using a small scale such as '10' or '20' will work better for users using the IM Q8 compile time variant.

Of course any scale can be used for a HDRI version of IM that uses unlimited 'floating-point' in memory color values.

Three different distance measuring kernels are provided, though one can be used in a two different ways, making four distance 'metrics' that have been provided for your direct use.

Chebyshev Distance Kernel

The 'Chebyshev' Distance Kernel is the simplest, and specifies that pixel around the 'origin' is simply 1 distance unit ('100' by default) distant. That is all 8 neighbours are 'next' to each other. That is not only are the immediate four neighbours a distance of 1 unit, but the diagonal neighbours are also 1 unit away.

Here is the actual kernel it generates...

convert xc: -set option:showkernel 1 -precision 4 \ -morphology Distance:0 Chebyshev null:

The name of this kernel is that of the Russian mathematician Pafnuty Chebyshev who first mathematically described this form of distance measurement. You can find out more about this measure on Wikipedia, Chebyshev Distance.

Using a 'Chebyshev' distance measure, the final distance of a pixel is the largest X or Y value to the closest edge. However as the diagonal distance is only 1 unit, the maximum distance within an image is usually smaller than you would expect.

Lets generate a 'distance gradient' using this kernel 'metric'.

	convert shape.gif -threshold 50% +depth -verbose \ -morphology Distance:-1 Chebyshev \ +verbose chebyshev_gradient.png identify -format 'Maximum Distance = %[max]' chebyshev_gradient.png convert chebyshev_gradient.png -auto-level chebyshev_gradient.gif rm chebyshev_gradient.png

I turned on the Verbose flag so that the command will output how many pixels changed on each iterated 'loop' though the image. Then extract the 'maximum' distance generated, before converting that image into a gradient for viewing.

Now the kernel by default has only a radius size of 1. That means that the 'Distance' method will needing to loop though the image multiple times, until all the pixels have been assigned a distance value (less than the maximum). Because of this you can get a good idea of how 'distant' the last pixels were from the edge by the final iteration count. In this case 14 times (the very last loop did not change any pixels).

Not only that but you can see how many pixels were assigned values during each iteration. Specially there are 456 pixels around at least diagonally next to an edge, and not one but 4 pixels at the greatest distance from the edge.

If you were to could up all the pixels that were changed you would get the total number of pixels that are in this shape, though a direct Identify with Verbose could have given you that information directly from original shape.

The last bit of information '1400', the value of the brightest pixels (4 of them in this case) is the maximum distance from an edge (usually multiple edges). As all the distances units in the kernel is '100' then this value should always be a multiple of '100', and will never have any fractional component. You could for example use a simple '1 unit' scale with this kernel without loss of information.

Here is an magnification of the gradient between the shapes 'legs' which highlights the features of the distance gradient generated. convert chebyshev_gradient.gif -crop 25x20+39+69 +repage \ -scale 500% chebyshev_magnify.gif

As you can see the 'Chebyshev' distance kernel produces a very square like gradient. This is the trade of from using such a simple distance metric.

Manhatten Distance Kernel

The 'Manhatten' Distance Kernel, measures the distance by adding the X and Y values to the closest edge. It is basically the distance you need to travel when you are restricted to only grid-like movements, such as a taxi cab on the streets of large cities like Manhatten, New York. Another name for this measure is thus 'Taxi Cab Distance'. You can find out more on Wikipedia, Manhatten Distance.

Here is the actual kernel it generates...

Note that the diagonals now have a value of '200' or 2 units from the center. That is to reach a diagonal pixel you would have to travel through two pixels in the gird-like movements mentioned. As a result of this diagonals tend to be larger than expected, as such the final distance measurements also tends to be larger.

Lets again get extract the maximum distance and the 'distance gradient' image using this 'metric'.

	convert shape.gif -threshold 50% +depth \ -morphology Distance:-1 Manhatten manhatten_gradient.png identify -format 'Maximum Distance = %[max]' manhatten_gradient.png convert manhatten_gradient.png -auto-level manhatten_gradient.gif rm manhatten_gradient.png

I did not output the verbose iterations in this example as it is only really accurate for the previous 'Chebyshev' kernel. However as you can see the final maximum distance for the image is much larger, at '1700' distance units, making the maximum pixel(s) within the shape 17 pixels from the edge.

Like the previous kernel all the values are multiples of the default scale, without any fractional component. As such you can use a simple '1 unit' scale with this kernel without loss of information.

Here is an magnification of the gradient. convert manhatten_gradient.gif -crop 25x20+39+69 +repage \ -scale 500% manhatten_magnify.gif

As you can see the 'Manhatten' distance kernel generated a diamond-like gradient, which is basically what this simple distance metric represents.

Euclidean (Knights Move) Distance Kernel

The 'Euclidean' kernel produces a much more accurate default that the previous two measures. But to do so requires a fractional diagonal distance of square root of 2, a value of 1.4142 distance units (scaled by 100 by default).

Here is the default kernel it generates...

convert xc: -set option:showkernel 1 -precision 4 \ -morphology Distance:0 Euclidean null:

Now using the default radius of 1 while a much bigger improvement on the previous two kernels in terms of accuracy, it still has some limitations. Basically, it provides a distance in terms of just diagonal and orthogonal moves. That is distances are what I like to term 'Knight Move' distances, such as how a 'chess knight' moves.

Here is the maximum distance and the 'distance gradient' image that was created using the default 'Euclidean' or 'Knight Move' kernel.

	convert shape.gif -threshold 50% +depth \ -morphology Distance:-1 Euclidean knight_gradient.png identify -format 'Maximum Distance = %[max]' knight_gradient.png convert knight_gradient.png -auto-level knight_gradient.gif rm knight_gradient.png

As you can see for this specific shape it also generated a distance value of '1700' distance units. Normally the result would be some fractional distance, between the smaller 'Chebyshev' distance, or the larger 'Manhatten' distance. It is just plain luck that it came out as a simple multiple of '100' and that also happened to be the same as the 'Manhatten' distance.

Here is an magnification of the gradient between the shapes 'legs'. convert knight_gradient.gif -crop 25x20+39+69 +repage \ -scale 500% knight_magnify.gif

As you can see the gradient has a much more rounded look to it, though it is in actual fact generating a rough 'octagonal' type of gradient. For general distance work (such as feathering) the default 'Euclidean' or 'knights Move' kernel provides a good result, at the same speed as the both of the previous two kernels. However this is at a cost of generating more 'gray-scale levels' caused by the fractional distance component.

Larger Euclidean Distance Kernel

By increasing the 'radius' of the generated 'Euclidean' kernel you can produce an even more accurate distance measurement.

The larger the radius the more accurate the result, but will take longer for the morphological method to run. Beyond a radius of 4 however you will not get much more accuracy.

Here is a true 'Euclidean' kernel using a radius of 4, and thus generating a 9×9 kernel...

convert xc: -set option:showkernel 1 -precision 4 \ -morphology Distance:0 Euclidean:4 null:

The added advantage of using a radius of 4 is that the kernel also contains the Pythagorean Triangle, which has sides 3,4,5. Though this can reduce the number of fractional components in the resulting image, it is really only a minor effect.

Here is its application...

	convert shape.gif -threshold 50% +depth \ -morphology Distance:-1 Euclidean:4 euclidean_gradient.png identify -format 'Maximum Distance = %[max]' euclidean_gradient.png convert euclidean_gradient.png -auto-level euclidean_gradient.gif rm euclidean_gradient.png

As a result of using this large radius 'Euclidean' kernel, the final maximum distance is the most accurate maximum distance measurement yet. It also makes getting more than one 'brightest' pixel in the image much less likely.

Here is an magnification of the gradient between the shapes 'legs'. convert euclidean_gradient.gif -crop 25x20+39+69 +repage \ -scale 500% euclidean_magnify.gif

As you can see the gradient produces a near-perfect circular gradient around the end of the 'leg gap'.

The cost of using this kernel is as I said above, a slower running time. However internally it was also not iterated as offen as the kernel itself has a much larger area of effect. For larger operations, you may only need to use a single iteration, rather than asking for it to be applied multiple times.

Comparison of Distance Kernels

Here again is a side-by-side comparison of the magnifications. This clearly shows the very different gradients generated each of the four distance kernels.

Chebyshev

Manhatten (Taxi Cab)

Euclidean (Knights Move)

Euclidean (radius=4)

Special User defined Distance Kernels

You are of course not limited to the three distance kernels that have been provided for you. As long as you stick to the rules, of using a zero value at the 'origin', and an increasing distance value surrounding it, you can generate some very interesting distance kernels.

For example here I apply a very small User Defined Kernel that simple says make any pixel to the right larger in value. convert shape.gif -threshold 50% +depth \ -morphology Distance:-1 '2x1+0+0: 0,100 ' \ -auto-level distance_linear.gif

Notice the effect of the gap between the legs, which 'resets' the increasing slowly increasing gradient that it generates.

And here I create a distance gradient from just the two sides, but with different scales for each side! convert shape.gif -threshold 50% +depth \ -morphology Distance:-1 '3x1: 50,0,100 ' \ -auto-level distance_sides.gif

These is just some examples of distance kernel variants that are possible. Can you think of others, please let me know.

Note if you image comes out bad, your origin setting is wrong, or was probably not a 'zero' value.

Distance with an anti-aliased shape

For getting the distance measure of an anti-aliased shape you can do the
following initial processing of the image.

 convert shape.png +level 0,100 -white-threshold 100 ...

This makes a 50% grey anti-aliasing pixel equal to value of 50, (half a the
default distance unit, or half a pixel length from edge) while keeping the
rest of the pure white shape, pure white.

After applying this small transformation, the 'Distance' method can then
assign the rest of the distance measurements to the other non-anti-aliasing
pixels, taking those edge pixels into account.


FUTURE...

Feathering a object Distance Morphology.

Generating Skeletons of shapes.

Definition??

Morphological Skeletion (by erosion?), vs Medial Axis Skeletion (by thinning)

Skeletions are calculated either by repeated thinning,
or by distance transform, and finding the 'creases', or ridges on the 3d surface (watershed transform?).

One defintion of medial axis transform (MAT) uses the intensity of each point to represent the distance ot the boundary. That the skeletion was used as a mask for the distance transform. The distance transform method is more suited to this, and it is probably faster to calcular than by thinning.

SKIZ (SKeleton by Influence Zones) is a skeleton of the background, the negative of the operation. That is dividing the regions closest to each forground object. (generated by thickening)

Identifing shape by their skeletions. distance between furtherest 'end' point, number of 'loops' or regions in image, number of triple points.

Distance to Skeleton

One quick and dirty way to generate a raw 'morphological skeleton' from an image is by applying the 'TopHat' method to the distance gradient.

For example, here is a skeletion of the shape after it is been Opened a little to smooth its outline a bit. convert shape.gif \ -morphology Open Diamond \ -morphology Distance:-1 Chebyshev \ -morphology TopHat Diamond \ -auto-level chebyshev_dist_skel.gif

This is basically a morphological skeletion. It only shows the pixels where a maximal disk could be found, which is why it looks incomplete. However it is still a very raw result with many isolated pixels. Amazingly it does work.

Without the 'Open' the result is very bad, due to the shape having such a rough outline.

Using a Euclidean distance measure produces a better skeletion of the shape. convert shape.gif \ -morphology Open Diamond \ -morphology Distance:-1 Euclidean:4 \ -morphology TopHat Diamond \ -auto-level euclidean_dist_skel.gif

But as you can see you also get more noise and the skeleton while more complete is also very dirty with many grayscale values.

Here is an enlargment of the 'head' of the skeletion, showing how it remains disjointed. convert euclidean_dist_skel.gif -crop 35x28+30+13 +repage \ -scale 400% euclidean_dist_skel_mag.gif

Of course the above could be thresholded and used as a mask with the actual distance gradient that was used to generate it. This will allow you to look up the acutal size (distance radius) of the maximul disks that makes up the skeletion, letting you re-create the original shape.

---

Created: 4 January 2010
Updated: 9 February 2010
Author: Anthony Thyssen, <A.Thyssen@griffith.edu.au>
Examples Generated with:
URL: http://www.imagemagick.org/Usage/morphology/