ImageMagick v6 Examples --
Morphology of Shapes

Index

ImageMagick Examples Preface and Index

Morphology Introduction

• Morphology Operator
• Basic Built-In Morphology Kernels
  • Unity,  Diamond,  Square,  Rectangle Disk,  Plus,  Ring, 
  • User Defined Kernels
• Iterating (Repeating) Morphology Operations
• Verbose Output of Changes (for monitoring)
• Displaying the Generated Kernel (for debugging purposes)
• Generating a Image of the Kernel (for debugging purposes)
• Multiple Kernel List Handling
  • Generating a List of Multiple Kernels
  • Expanding to a Rotated Kernel List
  • Multiple Kernel Results Merging : Re-iterate or Compose

Basic Morphology Methods

• Erode,  Dilate,  Open,  Close,  Smooth
• Flat Grey-scale Morphology
• True Grey-scale or 3-dimensional Morphology
• Intensity Variant of Basic Methods

Difference Morphology Methods

• EdgeIn,  EdgeOut,  Edge,  Top-Hat,  Bottom-Hat

Using Low Level Morphology Methods

• Basic Morphology and Channels
• Granularity of a Collection of Shapes
• Asymmetric Kernel Effects (method testing)

Distance Morphology Method

• Distance Kernels, 
  • Chebyshev,  Manhattan,  Euclidean (knight),  Euclidean, 
  • Comparison of Distance Kernels
  • Special User defined Distance Kernels
• Distance with an Anti-Aliased Shape
• Feathering Shapes using Distance

Hit and Miss (HMT) Pattern Matching

• Hit And Miss
  • Hit and Miss with Grey-Scale Images
• Thicken - Add pixels that match
  • Octagonal Convex Hull
  • Thicken Grey-scale Images
• Thinning - Subtracting pixels that match
  • Thinning Edge Detector Output
  • Thinning down to a Skeleton
  • Pruning Lines
  • Fast Pruning of Lines
  • Thinning Style - Iteration vs Intersection
• Pattern Matching Kernels
  • Peaks,  Edges,  Corners,  LineEnds,  LineJunctions,  Ridges,  ConvexHull,  Skeleton

Generating Skeletons from Shapes. Under Construction

• Distance to Skeleton

Morphology modifies an image based on the nearby 'neighbourhood' of the other pixels that surround it. This in turn can provide a huge range of effects, from 'convolution' techniques that provide blurring and sharpening techniques, which will be exported in the next section, to the discovery and determination of the various shapes of objects found within an 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' (see below).

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 each specific morphological method. Exactly what size and shape this 'neighbourhood' often depends on just what you are trying to achieve, or what you are specifically looking for within the image.

Here are some examples of various kernels that have been converted into images (using a special script "kernel2image"") showing some of the 'neighbourhoods' around a central pixel, 'origin'. The images have been scaled to highly the individual elements of the 'kernel', and as you can see typical kernels are often very small. In fact the 'Disk' kernel real size looks is "". Normally 'kernels' are not images, but are just an array of values with one element specified to be the 'origin' of the kernel. This special element is the location of the pixel 'effected' by the defined neighbourhood.

Note that these are only some examples of possible neighbourhoods. Some kernels can be made larger, typically by increasing a 'radius' argument specific to that kernel. But others are of fixed size.

For simple kernels such as the first three, a morphological method could be repeated (iterated) to increase the effective 'size' of the kernel, so as to effect more pixels further away from the 'origin' (as marked). This does not always work however.

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.

All of the kernels show, but the last kernel one, are actually shaped. The parts that are transparent are 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.

Note how the second last kernel 'Corner #0' not only has a 'on' values but also 'off' values as as part of its 'shape'. Both values, as well as those that are transparent (not part of shape) are important to the Hit-n-Miss method (see below). This specific kernel is only the first of a series of kernels that to locate 'corner' pixels of binary shapes within an image.

The last 'kernel' shown above is fully defined over a larger rectangular (square) area. Also unlike the other kernels which only use values of 1 (white), 0 (black), or a special undefined value, the values of this kernel actually range from near-zero (black) at the edges to a maximum (white) value in the center. However such kernels can also use negative, or even much larger values, beyond the normal expected range.

This type of kernel is especially important in 'Convolution', a special method that has been around far longer than morphology itself. As a result IM a a very large number of built-in, or 'Named' kernels of this type. This will be looked at in more detail in the next section of IM Examples, Convolution of Images'.

Now as I already mentioned, kernels are not really images. They are simply an array of floating point values. We will be looking at these actual values (which was converted into an image for viewing, above) latter, using the Show Kernel expert option, and Kernel Image Script. (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 least 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.

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 the more specialized kernels that those methods 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 k_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.

Unity

This is a special kernel that is specifically used when you need a 'No-Op' kernel. Most morphological methods using this kernel will either re-produce the original image, or nothing at all.

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.

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 k_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 k_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 uses a 3x3 pixel neighbourhood around the 'center'. convert pixel.gif -morphology Dilate Square k_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 k_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).

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.

Here are some specifications and an image of the kernels they produce.

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. However you can also specify off-centered origins as well.

This particular kernel is also good at defining long horizontal and vertical lines, allowing you to search for such objects within images. More on this later.

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

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 using a integer radius. Adding a fraction of about 0.3 to 0.5 is generally recommended, to avoid generating an off looking single pixel on the sides of the disk.

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.

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, producing 2 pixel 'arms' around the central 'origin'. A 'Plus:1' kernel happens to be the same as a 'Diamond' kernel.

Note that a 'Plus' kernel is a generally not used for normal morphological methods, 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, must as I did above to show you what this kernel actually looks like. Basically it provides an alternative to Drawing Symbols, without needing to know exactly where the individual 'points' are located in the image.

Ring

The 'Ring' kernel, like the 'Plus' kernel is also designed as a special 'shape' kernel for marking pixels of generating patterns on images.

However it does not just take one radius, it can take two radii...

What it does it turn 'on' any pixel that falls between the two radii, regardless of the order of the two radii given. If no radii are given it defaults to a radii of '2.5' and '3.5', or the equivalent of using 'Ring:2.5,3.5' (see examples below).

This lets you create a 'ring' of any size and thickness. However if the two radii are within 1 pixel of each other you can also generate a ring consisting of spaced out dots. At smaller scales, box-like kernels can also be generated.

If the second radius is not given it will default to a value of '0.5' which effectively defines a full disk, but without the center 'origin' pixel.

Here are examples of many of the 'Ring' kernels that can be generated...

As you can see you have a lot of possibilities, by carefully adjusting the two radii, and provides a good way of showing locations of interest in an image.

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" \ k_user:3.gif

With a single pixel Convolve works almost the same as Dilate but works with the kernels values, rather the kernel shape. However for a single pixel source image 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 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.

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 " \ k_user:5x3.gif

And finally here is an example of specifying a rectangular neighbourhood, that forms a 'L' shape around the 'origin'. Note that the origin of this kernel is not even part of its own neighbourhood! convert pixel.gif -morphology Dilate \ "2x3+1+1: 1,- 1,- 1,1 " k_lman.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 a numerical 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 Boolean 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 k_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 k_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 k_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 Verbose 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' (see the next example below).

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, where a iterated disk, will enlarge not just the shape but the errors (non-disk shape) of the kernel. As such you may be better off using a larger radius (which is slower) rather than iterating the operation (which produces a more distorted disk) .

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

Verbose Output of Changes

If you want to see the results of iterating (repeating) a morphological operation, you can set the "-verbose" option, which turns on the Verbose Operational Control. As the morphology operator iterates, it will report a incrementing count of the iteration, and how many pixels in the image were changed by each iterated step. The output is to standard error, so that you can still pipe the image results..

For example lets 'Dilate' the single pixel image using the larger 'Disk' kernel until the whole image has been filled with white and no more changes can be made to the image. Remember an iteration limit of '-1' means iterate forever, or until no more changes are seen.

	convert pixel.gif -verbose -morphology Dilate:-1 Disk \ +verbose iterate_infinite.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 in the image had already been changed to white, so the morphology aborts, giving a final number of changes for this stage of the operation.

The an infinite iteration of '-1' does have an internal limit. this is currently the maximum width or height of the image. This is done to prevent ImageMagick from going into a never ending loop, however a large image using a large kernel can still take a very very long time to reach this internal limit.

Some morphology methods are actually defined in terms of simpler more primitive methods. For example a 'Smooth' method is one such compound method. The "-verbose" output that is generated shows this as it steps though multiple steps in the internal processing.

If you look you can see that the 'Smooth' actually iterates, 4 more primate methods, and thus internally processes the image 8 times to perform the requested operation.

Each line consists of..

Smooth:i.s

this shows the high level morphology method being applied to the image, and the iteration count 'i' and primitive 'stage' 's', that IM is processing.

For the 'Smooth' method that first number is always '1', as the user-given 'iteration count' is applied in the lower level primitive method. In other methods, the user-given iteration may be applied at this higher level rather than at the lower level.

The second 'stage' number is the primitive 'stage' count that is being applied. 'Smooth' itself is composed of four such stages, as it implements the 'Open' and 'Close' compound methods.

Dilate*:i.k

This is the primitive method being applied. The first number i is again the user-given iteration count (if it is being applied here). The second number 'k' is the kernel being applied by the primitive morphology method. As there is only one kernel so it is always zero in this case. (See Multi-Kernel Handling below)

The '*' indicating that the kernel was reflected (or rotated 180 degrees around origin) before being applied by the morphological primitive.

#9 => Changed 297 Total 917

This is a report of the results of applying the morphology primitive to the image.

The incremental count of the number of primitive passes though the image, followed by the actual number of pixels modified in the image during that pass. If this is the last of a number of iterations for this specific kernel, a total count of pixel modifications is also output.

From the above you may see that internally IM may have four loops of processing being applied to fully process an given morphology method. However typically most of these loops are only applied once only.

Displaying the Kernel Generated (for debugging purposes)

If you like to actually see the values that was used to define a particular kernel that was generated, you can set a special expert option...

-set option:morphology:showkernel 1

This caused IM to output (to 'standard error') all the information aboout a generated kernel, after the kernel has been completely processed in preparation for its use. (See Convolve Kernel Scaling).

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

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

Remember it is the actual values of a kernel that is important. The image shown on the right was actually created directly from the values listed using a special Kernel to Image Script (see below).

The special floating point 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. These values are ignored by all morphological operations.

Here is another example. This time of a 'Comet' convolution kernel.

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

Also notice that this specific kernel's 'origin' (the pixel that it effects), is off-center, which is unusual.

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

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.

Generating an Image of the Kernel

To make it easier to see kernels, rather than using Dilating or Convolution on a a single pixel image to see what it produces, I created a special script called "kernel2image". This script extracts the exact Show Kernel output, and converts it into a image of the kernel.

The "kernel2image script has lots of options, from output the raw image of the kernel (the default) to specifying the amount of scaling, inter-pixel gaps, montage, labeling, and even coloring of the resultant 'kernel image'.

For example here is how the 'Disk' kernel image, which has now been shown many times in these examples, was actually created. kernel2image -10.1 -m "Disk" kernel_disk.gif

The special option '-10.1' means scale all pixels to 10 pixels in size, but also include a 1 pixel gap between those pixels. If the kernel is scaled enough the 'origin' of the kernel will be marked with some drawn circles. The '-m' then specifies that I it to create a Montage of the image with a identification label of the extracted "Disk" kernel, and shadow effects.

And here I generate a 'kernel image' of the 'L' shaped kernel, I demonstrated previously. kernel2image -20.2 -ml 'L-Shape' "3: 1,-,- 1,-,- 1,1,- " kernel_lman.gif

This script makes it a lot easier to view and understand the various kernels available, and how they are arranged.

Multiple Kernel List Handling

Generating Multiple Kernels

As of IM v6.6.2-0 you can now also specify multiple kernels which will be applied to the image in sequence. To specify multiple kernels you would just append each kernel definition together, separated by a semicolon ';'. the final semicolon is optional.

For example here I define a special kernel list containing a list that can be used for 'pattern matching' corner pixels.

Extra semicolons (';') do not matter, as long as at least one is provided between kernel specifications. Nor does extra white space (including newlines), in any kernel specification.

Here is a Show Kernel Output of this definition.

And here is a Kernel Image of these four kernel using the special "kernel2image" script.

Now this definition actually consists of just the one kernel which has been expanded to form a set of 4 kernels each rotated by 90 degrees.

ASIDE: This definition is actually equivelent to the the special 'Corners' pattern matching kernel (see below).

Expanding to a Rotated Kernel List

As of IM v 6.2.2-0 you can now ask IM to expand a single kernel into a list of rotated kernels by using one of three special flags, in either named or user-defined kernels. The three special flags are...

'@'	Cyclically rotate 3x3 kernels in 45-degree increments, producing a list of up to 8 rotated kernels. (memonic: '@' is circular)
'>'	Rotate (square or linear kernels only) in 90-degree increments. (memonic: the '>' is right angled).
'<'	Also produce 90-degree rotations but in a 'mirror' sequence (rotation angles of 0, 180, -90, +90 ). This special form of rotation expansion works better for morphology methods such as 'Thinning'. (memonic: '<' is a mirror of a right angle).

For example that same kernel above be specified more simply as...

This defines one kernel, which the '>' flag then tells IM to expand into a 90 degree rotated list.

And here is a image of the resulting multi-kernel list

And here I rotate a 3x3 kernel in a 'cyclic' 45 degree rotation, expanding it to a list of 8 kernels.

You can also do the same for any 'single' built-in named kernel IM, using the same flags in the argument section of those kernels. For example here I take a symmetrical 'Blur' kernel and expand it into a 90 degree rotated list using a '>' flag.

Note that only 2 kernels were generated as a third kernel in this sequence would just reproduce the first kernel exactly, so the rotation expansion stops.

However if the 'origin' is off centered, then the full sequence of 4 rotated kernels would have been generated as while the kernel 'shape' matches, the origin location would not be the same.

Many built-in kernel definitions actually automatically generate a multi-kernel list, so you do not need to specify any flags for that purpose. That is the rotation expansion is also 'built-in' to specific kernel definitions. Such kernels typically also provide 'sub-types' of the original single kernel definition that was rotated.

Multiple Kernel Result Merging: Re-iterate or Compose

When you have defined multiple kernels, the morphology method also needs to know how it should have the results generated by multiple kernels. This can be controlled by this special expert setting...

-set option:morphology:compose {compose_method}

The default for most morphology methods is a setting of 'None'. This means that after each kernel has been applied using the morphology method given, the resulting image should be used as the source for next kernel. that is simply 're-iterate' or reuse the results of one kernel with the next kernel.

For example, if I Convolve using 2, 90 degree rotated 'Blur' kernels we get the following.

As you can see both kernels were applied to the image one after the other, so that each kernel works with the result of the previous kernel. That is it 're-iterated' the results.

This is equivalent to doing the two steps like this.

Actually this is how the Blur Operator really works, to generate image blurs more quickly.

Using any other '{compose_method}' will always apply each kernel to the original image, and the resulting images will be then be Composited together using the '{compose_method}' method specified.

For example if I use a 'Lighten' morphology method to generate a Union of the separate results, we would get..

That was equivalent to doing...

If you are not sure what IM is actually doing during a morphology, turn on the Verbose Output of Changes. For example here the verbose output of re-iterating with each kernel...

And here is the verbose output of a Union (Lighten Composition) of each kernel result....

Both of which clearly shows what ImageMagick is doing to generate the final image. The number after the decimal point represents the kernel number that is being applied, at each step. Followed at the end by how it composes the images together according to the 'option:morphology:compose' setting.

Many of the Mathematical Composition Methods and their equivelent Set Theory type operations, can also be used to merge the results of applying each kernel to the original image.

In summery this setting defines how the individual kernels of a multi-kernel list will be applied to the given image. The default is the compose value of 'None' meaning to simply 're-iterate' results, otherwise it will merge all the results based on the compose method given.

---

Basic Morphology Methods

Morphological Methods is a image processing technique for the finding, and analysis of shapes of objects withing an image. Expanding, shrinking, locating specific shapes, and so on.

It was original developed with binary (pure black and white) images in mind, and because of this it most commonly applied to Thresholded images containing simple black and white shapes. By convention white in a binary image represents foreground, while black represents background. The method names are thus described according to this convention.

That is not to say the operators will not work with gray-scale image, or in some cases color images, but their original purpose was to handle binary shapes.

The basic Shape Kernels already looked at above, are the most commonly used neighbourhood defining 'shapes', for morphological methods. Such kernels are often called 'Structure Elements' as they are typically used to determine the structure of the shapes within the image.

Erode   ( )

As the name implies the 'Erode' method 'eats away' the shape, from any background pixel making it smaller. For example here is a simple binary 'man-like' shape that has been eroded using the largish 'Disk' kernel.

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.

Dilate   ( )

The 'Dilate' method is the dual of 'Erode'. It will make a shape bigger according to the kernel (and the number of iterations) specified.

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 were are added around the edges of the image.

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 Negated Images. convert man.gif -negate \ -morphology Dilate Disk -negate dilate_man_neg.gif

Open   ( )

This method also smooths the outline shape, by first rounding off any sharp points, and disconnecting or 'opening' any thin bridges. However it does not remove any 'holes', or gaps, such as between the shapes 'legs'. Also as previously shown 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 man.gif -morphology Erode Disk \ -morphology Dilate Disk open_man_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 man.gif -morphology Open:2 Disk open_man_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.

Close   ( )

The basic use 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 man.gif -morphology Dilate Disk \ -morphology Erode Disk close_man_2.gif

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

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 man.gif -negate -morphology Close Disk -negate close_man_neg.gif

Smooth

The 'Smooth' method applies a 'Open' followed by a 'Close' of the shape, which first removes any 'small objects' then fills in and 'holes' or 'gaps' about the size of the kernel 'Structure Element'. convert man.gif -morphology Smooth Disk smooth_man.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 'Smooth' operator is also often repeated with slowly increasing sized Structure Elements, so as to slowly remove noise from images. If the parts removed are preserved, you get a morphological 'decomposition' of the image which can be used for further study. See Granularity below. The method is particularly good for cleaning up scanned documents.

Note that this is actually applying 4 separate 'primative' operations to the original image. It is thus 4 times slower than just a simple 'Erode' or 'Dilate'.

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 summery, the above operators apply a 'flat' kernel without any 'height' or '3-dimensional' features, but can still be applied to gray-scale images.

True Gray-scale or 3-dimensional Morphology

True gray-scale or 3-dimensional morphology (as one library put it) will actually add or subtract the values found in the kernel from the neighbouring pixels in the image, before looking for the maximum/minimum values as the result. What this means is that it treats a gray-scale image as a 'height field' of a 3-dimensional morphology object and the gray-scale shape of the kernel the smoothing shape to adjust that height field.

While the implementation details of true gray-scale morphology is well documented, is usage in practical situations is not. That is 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 really do need such non-flat grey-scale morphological operators, please let me know, and I will implement the appropriate operators.

Note the special 'Distance' method (see below) is actually similar to how true gray-scale morphology works, in that it adds the kernel's value to each pixel value, before taking the smallest 'minimum' value. However this method does not match either 3D erode (subtract and take minimum) or dilate (add and take maximum) morphology definitions. It is however very closely related, and probably could be implemented using those methods.

Intensity Variant 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, only with grey-scale and binary images.

The result is that for color images, the colors become distorted, becoming a brighter or darker shade depending on the operation.

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 color pixel is copied, and not just the individual channel values.

Because of their nature the Intensity Methods will ignore the current "-channel" setting completely.

The methods also has a short hand naming scheme, by replacing the word 'Intensity' with just a 'I'. As such here I use a 'CloseIntensity' method but use the short hand name of 'CloseI'. For example here I use the four 'Intensity' variants on the built-in rose image (original image to the right).

convert rose: -morphology ErodeI Disk rose_erode_intensity.gif

convert rose: -morphology DilateI Disk rose_dilate_intensity.gif

convert rose: -morphology OpenI Disk rose_open_intensity.gif

convert rose: -morphology CloseI Disk rose_close_intensity.gif

The last two (or perhaps both) may be particularly suitable as a replacement operator for Paint Operator.

These methods are classed as experimental, and comments or problems with its use is welcome.

Basic Morphology Alternatives

For people with older versions of IM you can still implement some basic
morphology methods.

If you generate a kernel that is all ones. For example a 7x7 array of 1's
(radius=3), 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 a simple square kernel for binary morphological
methods.

'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 previously shown above
'Open' is a 'Dilate' followed by a 'Erode'
'Close' is a 'Erode' followed by a 'Dilate'
and Smooth is a 'Open' followed by a 'Close'

Larger square kernels can be specified using larger radii
but the other built-in kernel shapes are not available, without
using the convolve operator to manually define their shape.

This also only truly works for binary morphology. To implement a
flat-greyscale morphology, you will need to use a different technique of
generating a separate image for each pixel in the kernel, and rolling
it for the pixels position.

Both the thresholded-convolve and roll-shift composition methods have been
implemented in Fred Weinhaus's script "morphology", which was created long
before the "-morphology" operator was added to ImageMagick.

See and Download Fred's Weinhaus "Morphology" Script from
  http://www.fmwconcepts.com/imagemagick/morphology/index.php

---

Difference Morphology Methods

The next level of morphological methods is something I term difference morphology. That is the results of these morphology methods is the difference between (subtracted or difference) between one of the previous basic morphology methods, and the original image, or some other morphological methods.

Essentially they return the changes that wwas made to the original image by one of the simpler methods, giving you the outlines, the additions or subtractions between the images. They are essentially a 'Difference' or 'Minus' image compositions.

EdgeIn

The 'EdgeIn method, also called a 'Internal Gradient', find the pixels that an the Erosion removed from the original. As a result the pixels that are closest to the edge, but which were 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.

EdgeOut

The 'EdgeOut' method, also called 'External Gradient', finds the pixels that was added to the original image by a Dilation 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 difference between 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. As such a kernel of radius 3 will generally produce a 'Edge' which 6 pixels thick (kernel size is 7 pixels thick)

Here for example is the 'Edge' outline of the shape using the minimal 'Diamond' kernel. convert man.gif -morphology Edge Diamond man_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 thinner 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.

Future: generating the edge using a 'diagonal line'.

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 points, and the connecting bridged between shapes.

As you can see the pixels often form small highly disjoint islands, with no set of pixels any thicker 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.

This operator is more commonly used with greyscale images.

FUTURE: Example of greyscale top-hat

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 thicker that the kernel used. However they are always a completely different set of islands to the previous method.

FUTURE: Example of greyscale bottom-hat

---

Using Low Level Morphology Methods

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 current "-channel" setting.

This means you can apply these methods to color 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 figure' image, without modifying the color channels.

The 'EdgeIn' method can also be used to extract just the edge pixels from this figure, using a 'Diamond' kernel. convert figure.gif -channel A -morphology EdgeIn Diamond figure_edge.gif Further processing of those pixels, and recombining with the original image can produce interesting results. As seen in Sparse Color as a Fill Operator.

Search for Specific Shapes

Knowledge about an object depends on the manner in which we probe (observe)
it.                    -- Georges Matheron, The Father of Morphology

Using Erode to locate specific shapes from a large correction of shapes.

Restoring objects using Open (smoothed result) or Conditional Dilate
(morphological fill).

Needs some sort of Connected Component Analysis, (Segmentation) to properly
count objects found within an image.

Granularity of a collection of Shapes

By using a series of 'Open' or 'Smooth' methods using a range of various sized structuring elements on an image that has a large number of shapes in it you can quickly get a summery of all the different sizes and shapes of elements within the image.

The resulting information is known as the 'granularity' of the objects within the image. Basically a graph of the sizes and shapes of the objects found.

This can in turn let you separate out (or 'segment') different shapes, or even different textures of the image.

See Granulometry (morphology), Wikipedia.

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, 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 a 'negative' and 'reflected' form of either the image or the kernel. A single white pixel expands to the kernel shape, while any matching 'reflected' shaped hole, shrinks down to a single pixel 'hole'.

Note also that the boundary between positive and negative halves of the test image does move as consequence of applying the above basic morphological methods. That is to be expected.

This brings up a specific point about these two methods. To convert a 'Erode' methods into a 'Dilate' or visa-versa, you not only need to Negate the images before and after, but you also need to rotate or reflect the kernel about the origin. Normally this second aspect can be ignored, as most kernels are 'symmetrical'. It only becomes important with user defined asymmetrical kernels.

'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 is defined such that it does not need the kernel to be reflected (as it is reflected by its initernal defination), only the image negated.

---

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 pixel that is brighter that this 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 '1616' making the 'brightest' pixel in the image a very dark 2.5% grey, and its distance from the nearest edge, 16.16 pixels away.

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 full effect of the 'distance gradient' generated. convert distance.png -auto-level distance_man.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 specific Distance Kernel used.

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

Note that the distance gradient in the above did not cover the full range from black to white, as the distance color values will reach '100%' at about 13 pixels away from the edge.

Alternatively you can specify the maximum distance you are interested in by using the special Distance Scaling Flag, '!'.

For example here we declare we are only interested in a linear distance gradient to a maximum distance of 12 pixels from the edge of the image. convert man.gif -threshold 50% +depth \ -morphology Distance:-1 Euclidean:4,'12!' distance_range.gif

Note that the distance gradient in this case did not cover the whole distance from edge to the center of the shape, leaving an large white area in the center of the image.

The '!' flag will scale the the distance so as to give 'n' grey-scale values before the color range limit is reached. As such a value of 1 will only 'feather' (or make grey) 1 pixel around the edge of the image.

As you can see all the scaling methods however depend heavily on the actual size of the shape you are performing the 'Distance' method on. Too small and it is very dark and may not be accurate for your needs. Too large and the distance may get 'clipped' by the maximum posible color value of your ImageMagick's Compile Time Quality. For more details on the 'scale' factor in the kernel, 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.

An alternative solution is to use a Floodfill method to extract the outside of the image, and convert that into new mask, containing just the image, but without the holes. For example..

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 linearly 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 added to a already 'known' distance, assigned to a pixel if that value is smaller than what is already assigned. The result is that 'white' pixels are made darker the closer they are to an edge, and linearly brighter (adding to previously assigned values) the further it gets from the edge.

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

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

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.

Distance Scaling

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

In the previous examples, the 'largest distance' value assigned was '1700', which would overflow 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 smaller scale such as '10' or '20' will work better for users using the IM Q8 compile time variant. Though it is far less accurate when used with a 'Euclidean' kernel.

Because of this it is recommended that user with Q8 versions of IM, restrict themselves to using the other two 'integer' kernels, with a scale factor of '1.0'.

You can also specify the distance scaling as a percentage of the full color range by including a '%' in the scaling factor. That means if you use a scale of '10%' then you will be able to get a distance metric of at least 10 pixels before the distance overflows the color range limits.

Alternatively you can instead use a '!' which means the scale is a divisor of the color range. That is if you specify a scale of '20!' the distance scaling will be set so that the color range limit will be reached 20 pixels from the edge of the image.

However even with these 'special scaling flags' you will still have severe range accuracy limitation in Q8 versions of IM.

Of course any scale can be accurately used for a HDRI versions of IM, as that uses 'floating-point' to hold color values. Just be sure to rescale the color range appropriately before attempting to save such an image to non-floating point image file formats.

Three different distance measuring kernels are provided, though one can be used in a two different ways, giving you four different 'distance metrics' that is available for specifying the pixel distance.

Chebyshev Distance Kernel

The 'Chebyshev' distance kernel is the simplest, and specifies that pixel around the 'origin' is simply 1 distance unit from its neighbours (a 'scale factor of '100' by default). 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 exactly 1 unit away.

This was also the kernel that was used in the previous examples above.

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 man.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 were 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 15th and last iteration 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 at least diagonally next to an edge, and not just one, but 4 pixels, are at the greatest distance from the edge, using this distance metric.

At the bottom of the verbose output you can see a count of the total number of pixels changed. For this specific distance metric, this give you an accurate count of the number of pixels that was in this shape. However a direct Identify with Verbose could have given you that information directly from original shape.

However be warned that other metrics may not produce an accurate count of the total number of pixels in a shape, as a specific pixel may be modified more than once as a smaller distance is found in a later iteration of the distance metric.

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

Manhattan Distance Kernel

The 'Manhattan' 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 Manhattan, New York. Another name for this measure is thus 'Taxi Cab Distance'. You can find out more on Wikipedia, Manhattan 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 man.gif -threshold 50% +depth \ -morphology Distance:-1 Manhattan manhattan_gradient.png identify -format 'Maximum Distance = %[max]' manhattan_gradient.png convert manhattan_gradient.png -auto-level manhattan_gradient.gif rm manhattan_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 manhattan_gradient.gif -crop 25x20+39+69 +repage \ -scale 500% manhattan_magnify.gif

As you can see the 'Manhattan' 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 the square root of 2, a value of about 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 big improvement on the previous two kernels in terms of accuracy, still has some limitations. Basically, it provides a distance in terms of just 45 degree diagonals and orthogonal (X an Y) moves. That is the distances are what I like to term 'Knight Move' distances, such the distance a 'chess knight' may move.

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

	convert man.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, you also get a distance value of '1700' distance units. Normally the result would be some fractional distance, between the smaller 'Chebyshev' distance, or the larger 'Manhattan' 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 'Manhattan' 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, without the onion-like 'levels' or 'terraces' effect following the outside edge, as we had previously. This is because each pixel is more likely to be assigned individual fractional distance from the edge.

The final shape of the gradient however is actually roughly 'octagonal' in shape. 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.

Larger Euclidean Distance Kernel

By increasing the 'radius' of the generated 'Euclidean' kernel you can produce an even more accurate 'Pythagorean' or true 'Euclidean' distance metric.

The larger the radius the more accurate the result, but will take longer for each of the morphological integrations method to run, though fewer such iterations will be needed. Beyond a radius of 4 however you will not get much more accuracy, but you will be a much greater loss of speed.

Here is a true 'Euclidean' kernel using the recommended radius of 4, which generates a larger 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, or with the default kernel scale, units of 300,400,500. Though this can reduce the number of fractional components in the resulting image, it is really only a minor effect. Still it is a logical choice for more accuracy, with only a minor loss of speed.

Here is its application...

	convert man.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 larger 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 very unlikely unless the shape is very regular.

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 marginally slower running time. However internally it was also not iterated as often 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 by each of each of the four distance metrics used.

Chebyshev (Larger Axis)

Manhattan (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 other very interesting distance effects.

For example here I apply a very small User Defined Kernel that simply says make any pixel to the right larger in value. convert man.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 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 man.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 your image comes out bad, your origin setting is probably wrong, or was not a 'zero' value.

Distance with an Anti-Aliased Shape

The Distance method works very well and a good test, which highlights
any errors that it produces is to generate a distance function of
a 'disk' and then 'shade' it.

  convert -size 256x256 xc: -draw 'circle 127,127 120,5' -negate  disk.png

  convert disk.png -morphology Distance:-1 Euclidean:4 -auto-level \
          -shade 135x30 -auto-level +level 10,90%   show:

You can see from the above that while you do get a nice 'conical' looking
shape, it shows a lot of edges and discontinuities.  Commpare it to
this shaded radial-gradient which produces a perfect 'conical result.

  convert -size 256x256 radial-gradient: \
          -shade 135x30 -auto-level +level 10,90% show:


The problem is that the distance method has no idea about the small 'grey'
anti-aliasing values that this drawn circle has around the edge  (See
Anti-alising).

What we need to do is somehow include those grey edge values in the
result, and this is done using a pre-processing step before the distance
method is applied.

 convert disk.png  -gamma 2 +level 0,100 -white-threshold 99 \
         -morphology Distance:-1 Euclidean:4 -auto-level \
         -shade 135x30 -auto-level +level 10,90%   show:

As you can see almost all the small errors have been fixed, producing
a smoother result.

Using a larger Euclidean kernel wil produce an even smoother result, but at
sever loss of speed..

 convert disk.png  -gamma 2 +level 0,100 -white-threshold 99 \
         -morphology Distance:-1 Euclidean:7 -auto-level \
         -shade 135x30 -auto-level +level 10,90%   show:

As you can see the parts close to the edge is now smooth with only the central
areas showing the errors that still exist.


Deeper explaination....

The distance kernels are scaled so that a distance of a single pixel
is a value of 100.  It uses the kernel to look for a smaller value, than the
one it already has.

So if you have an edge shape like (in a Q16 version of IM)...

   0   0   65535  65535  65535 ...

The distance function will convert it to become...

   0   0   100  200  300 ...

Each value becomming the smallest value in the neibourhood, plus the distance
to that value (according to the kernel).

But an anti-aliased shape may have and edge containing some grey anti-aliasing
pixel.  For example....

       0   32768  65535  65535 65535  ...

That first non-zero edge pixel is 50% grey, and should add some extra distance
to the pixels inside the shape.  However the distance method does not
understand this, and thinks of it as a previously assigned 'distance', for
which their is an obvious smaller 'distance' it can assign.

As a result it would generate...

       0   100  200  300  400  ...

That is it acts like the anti-aliasing grey pixel was just part of the
original shape.  The result is the aliasing effect you saw above.


What we really need to do is pre-process the image so that any 'grey'
anti-aliasing pixels are preserved in the final distance gradient.

This is done by getting their square root, and then compressing them into the
0 to 100 range (appropriate for the distance scale).

    -gamma 2 +level 0,100

That 50% grey pixel (32768) in the above will thus get a value of 70

       0  70  100 100 100 ...

But we don't want to scale the pure white pixels, as their distance value has
not yet been determined.  So we reset them back to white using

     -white-threshold 99

Producing the edge values of

      0  70  65535  65535 65535  ...

Other methods could also have been used for this, too.


The Distance function will never find a value smaller than 100 as it is
already smaller than the smallest non-origin value in the scaled distance
kernel.  As such it would now treat the pre-processed grey-pixels and already
having a correct and smallest distance assigned to them.

So after we apply the distance method to the pre-processed edge,
we will then get....

       0  70  170  270  370 ...

Which is correctly takes into account the distance represented by the grey
anti-aliasing pixels.

Feathering Shapes using Distance

Feathering a object using Distance Morphology.

For example a 5 pixel 'smoothed' feather around an object.
See above for an explaination of the '-gamma/+level/-white-threshold' line.

   convert alpha_man.png \
           \( +clone -alpha extract \
              -gamma 2 +level 0,100 -white-threshold 99 \
              -virtual-pixel black \
              -morphology Distance:-1 Euclidean:4 \
              -level 0,500 -clamp \
              -sigmoidal-contrast 3,0% \
           \) -compose CopyOpacity -composite \
           result.png

This preserves ALL edges, unlike the simpler 'blurred feathering' method.

Note I could have applied the above directly against the alpha channel except
that some operators do not treat the transparency channel as 'alpha values'
but as 'opacity values' (specifically -white-threshold).  As such I extracted
the alpha channel and handle it as a separate grey-scale image, and merge it
back into the final image

I only need to apply the distance morphology once, and once only, as I am only
interested in the pixels closest to the edge.

The -virtual-pixel ensures the image is regarded as surrounded by transparency
(black). This is especially important if parts of the shape touches the edge
of the image.

Once we have assigned linear distance values, a -level operation will spread
the distance values out to cover the full color range of the image.  That is
make any pixel more than 5 pixels from an edge (a value of 500) fully-opaque
(white).  The -clamp is only needed if a HDRI version of IM is used, otherwise
it is simply a no-op.

The linear feathering was then modified and smoothed slightly by using a small
-sigmoidal-contrast operation as a final step on the mask.  The higher the
strength ('3' in the above) the sharper the feathering will be at the edge
(0%).

If you like to have the feather 'taper' into transparency, rather than have
a sharper style of edge change that 0% to 50%.

---

Hit And Miss (HMT) Pattern Matching

Hit-And-Miss   ( )

The 'Hit-And-Miss' morphology method, also commonly known as "HMT" in computer science literature, is a high level morphology method that is specifically designed to find and locate specific patterns in images. It does this by looking for a specific configuration of 'foreground' and 'background' pixels around the 'origin'.

For example we could look for a 'foreground' pixel, which has a 'background' pixel immeditally to its right.

As you can see the small 2 element kernel only matched the pixels, that were on the right side of the image. That is the methdo only returned a specific pixel which matched the given pattern.

The 'Kernel' or 'Structuring Element' used can contain a pattern of 3 types of elements only, A '1' meaning 'foreground', a '0' meaning 'background', and also a thrid element which can be specified as 'Nan', '-' or a value of '0.5' which means 'Don't Care', mening that pixel can be any value at all.

For example this pattern can find pixels which is in a North-West facing corner of an image.

You can of course rotate that kernel to find all the corners in a specific shape. This specific kernel has been already provided as a built-in kernel known as 'Corners'.

convert man.gif -morphology HitAndMiss Corners hitmiss_corners.gif Corners

As you can see the 'Hit-And-Miss' method locates and returns ALL the pixel positions which match any of the kernel patterns provided.

If you were to examine the Verbose Output of the "-morphology" operation above, you will find that the 'Hit-And-Miss' uses a 'Lighten' composition method to create a 'union' of all the pixels that match each of the pattern kernels provided. Unfortunatally the 'changed' pixel count is of the pixels which are turned off. In otherwords the number of pixels in the shape, minus the number of pixels that were matched by each kernel.

By the same token, repeating a the 'Hit-And-Miss' method is usally usless, unless you are somehow including the original image in the results.

You can use a set of kernels that are more selective of what you are specifically interested in. For example suppose you are interested in the points where three lines meet, using the 'LineJunctions' kernel set.

As you can see only a sprinkling of locations match any of the kernels in that set. However the results can make it very difficult to actually see where the matching locations were in the original image. This is especaiily bad if you are dealing with a grey-scale image.

One solution is to expand the matches using 'Dilate' with some Shape Kernel, such as a 'Ring'. For example...

convert lines.gif \( +clone \ -morphology HitAndMiss LineJunctions \ -morphology Dilate Ring \ -background red -alpha shape \ \) -composite hitmiss_match_rings.gif

You can now clearly see locations where this particuler set of kernels found Junctions of 3 or more lines.

Each of the kernels in 'LineJunctions' may only match a couple of specific locations, as such pattern matching in this way can be slow. Still it is very precise and works very well.

HitandMiss - foreground only -> erode

HitandMiss - background only -> negated dilate

Hit And Miss with Greyscale Images

When the 'Hit-And-Miss' method is applied to a greyscale image, that actual value returned will be the difference between the minimum 'foreground' value and the maximum 'background' value. If a negative result occurs (no mathc) the result is 'clipped to zero' as negatives have no real meaning.

In other words it returned the 'minimum separation' of values between the two sets of pixels.

For Boolean shapes, that will be either '0.0' (black) or '1.0' (white). But for greyscale images this is equivelent to the 'gradient' of the matching pixels. It can for example be used to identify just how much contrast is present between a particular foreground and background in the matching pattern.

If you really only want a boolean (on/off) result of what pixels actually match the pattern in a grey-scale image, you should add a "-threshold 0" option after the command.

Thicken (Adding Pixels to a Shape)

The 'Thicken' method will add pixels to the original shape at every matching location.

For example here I look for a background pixel that is two pixels away from the right edge of the shape.

As you can see you ended up with a line of pixels just outside the shapes original boundary. You can iterate this 'Thicken' method a few times to continue the sequence. convert man.gif -morphology Thicken:4 '3x1+2+0:1,0,0' thick_right2.gif

However as pixels are being added, the origin of the pattern matching kernel should match a background pixel. If the origin is a foreground pixel you will essentually be adding a pixel, where a pixel is already present.

Another way to generate a 'Thicken' operation is to generate a Union of the results of 'HitAndMiss' of this kernel with the special 'Unity' kernel so as to include the original image in the results. For example... convert man.gif -set option:morphology:compose Lighten \ -morphology HitAndMiss 'Unity ; 3x1+2+0:1,0,0' hmt_thicken.gif Actually the Multi-Kernel Composition Setting in the above example is not needed as the 'HitAndMiss' method specifically sets this by default, when not defined by the user.

Typically 'Thicken' is used to enlarge shapes such as lines, but without making the lines longer. A special set of kernels known as the 'ConvexHull' kernel, allows you to do this

For example...

Thicken - Octagonal Convex Hull

The actual 'ConvexHull' kernel is really designed to work with image shapes, and will expand a shape into a 'Octogonal Convex Hull'. That is it will try to fill in all the gaps between the extremes until it produces a 'octagonally shaped' object.

You can watch the iterations being performed by turning on the Verbose Output Setting. However this will show that the above is very very slow.

Each 'Thicken' iteration will only actually add a few pixels to the shape on each iteration. As such it can take a lot of iterations before the full 'hull' is completed. In this specific case, the image required 80 'Thicken' iterations, with a 8 kernel 'ConvexHull'. That means the above actually required 640 primative iterations, plus another 4 primative iterations needed to do the two 'Close' methods. That can take quite an amount of time.

Basically iterating using Hit And Miss Pattern Matching can be very very 'slow', and if an alternative technqiue can be found, it should be used instead.

You can use this to also find the what points of the original image caused the creation of this octogonal shape, by getting an intersection (Darken Compostion) and the edge of the convex hull and the original shape.

The above set of points can be reduced further by deleting any point which is not the end of line (matched using a 'LineEnds' kernel), or a octagonal corner (no kernel developed as yet).

Any connected shape that fits inside the convex hull, but also includes these points can and will generate the same octagonal convex hull.

Thicken with greyscale images

When handling a greyscale image 'Thicken' will add the 'Hit-And-Miss' foreground and background seperation result to the origin pixel.

This can thus be used to make the matching pixels brighter, even when the 'origin' pixel is not in the 'background' set.

For example, lets repeat the corner-find example from above but with a 50% grey version of the shape.

When using a HDRI version of Imagemagick with 'Thicken' it is probably a good idea to "-clamp" or "-auto-level" the results to prevent it overflowing the image pixel value range limits.

Thinning   ( )   (Subtracting Pixels from a Shape)

The 'Thinning' method is the dual of 'Thicken'. Rather than adding pixels, this method subtracts them from the original image.

For example lets remove any pixel that is 4 pixels in from the right edge.

For 'Thinning' to work properly the pattern matching kernel should have an origin containing a foreground pixel, otherwise the method has no matching pixel to remove from the shape.

Another way to generate a 'Thinning' operation is to Relative Complement (using a Minus composition) the results of 'HitAndMiss' from the original image. You can include that image at the start of the kernel list (to 'subtract' from) by using a 'Unity' kernel. For example... convert man.gif -set option:morphology:compose Minus \ -morphology HitAndMiss 'Unity ; 5x1+0+0:1,1,1,1,0' hmt_thinning.gif This works because of the way the Composition of Kernel Results has been ordered so as to allow this non-associative composition method. However this is an 'intersection' style of thinning, removing all the specified pixels of all the kernels in a single step, rather than 'iterative' style, that removes the pixels from each kernel in sequence. See Thinning Style for more info.

Thinning Edge Detector Output

One of the most common uses of thinning is to reduce the threshold output of an Edge Detector such as Sobel Convolution, to lines of a single pixel thickness, while preserving the full length of those lines.

Example using a Distance Gradient Image.

Thinning down to a Skeleton

'Thinning' images is actually more commonly used than 'Thicken', as it is used to reduce the shapes into more manageable forms, such as Skeletons. Which, as will be discussed later, are ment to be the center line of pixels between any two (or more) edges of the shape.

A skeleton important as it provides a very good description of a very complex shape. For example processing the image to find the number of loops, line segments, and how they are arranged, will tell you a lot about the shape that you have.

So lets produce a 'Thinned Skeleton' by 'Thinning' the edges of the man shape down repeatally, until only the center lines are left.

A Verbose report on the above would have shown that 18 iterations, with 8 kernels, totalling 144 primative iterations in total. this is actually a lot faster than finding its Convex Hull (above), as the thinning kernels remove whole rows and columns of pixels with each iteration, and not just a few at a time.

Note how the 'Skeleton' kernel set failed to expand the hole, so that it did not find the center line between the hole and the outside edge. This is a serious failing of all the thinning kernels, as is caused by all of them requiring at least two diagonal background pixels inside the hole before they will make any thinning match.

A solution is to Erode the image slightly to give the kernels something to work with. I will also only erode and thin the 'Red' and 'Green' channels, so as to leave original shape in blue.

You can also see that any hole in the image will be expanded to produce a very large but thin continuous loop of pixels.

Here is a close up of loop around the eroded hole. convert man_skeleton.gif -crop 22x22+47+29 +repage \ -scale 120x120 man_skeleton_zoom.gif

Note that it did not produce an exact center-line between the hole and the edge. Also as the shape was eroded, the lines do not go right the edge of the original the shape but stop one pixel short. That is the end of lines have been 'pruned' slightly.

The skeleton is also limited to octagonal lines, which means it is missing a lot of detail, though in this case that can be a good thing. See the section on Skeletons below.

This uses a traditional 'Skeleton' kernel, which as you can see produces 'thick' diagonal lines, so that all parts of the skeleton are '4-connected' or 'diamond connected'.

There are other variations of 'Skeleton' kernels, which will produce slight variations in the resulting 'Thinned Skeleton'.

Thinner Skeleton

This 'traditional' skeleton as mentioned has thick diagonals. But often this is not 'thin' enough. In some situations what you want is a slightly thinner skeleton. That is you want an '8-connected' skeleton rather than '4-connected'.

One soltuion is to use a different skeleton generation variant, such as generated using a 'Skeleton:2' kernel, (found on the HIPR2 Graphic Tutorial Website). For example... convert man.gif -channel GB -morphology Erode Diamond \ -morphology Thinning:-1 Skeleton:2 +channel man_skeleton_hipr.gif

And here is a zoom of the loop area, showing how the resulting skeleton is 8-connected, with thinner diagonals. convert man_skeleton_hipr.gif -crop 22x22+47+29 +repage \ -scale 120x120 man_skeleton_hipr_zoom.gif

However I have found such skeletons to not be as accurate as the 'traditional' skeleton. Basically in test cases I have found that the diagonals were 'thinned' on the wrong side. Basically because the side of the diagonals that is removed is controled purely by the order of the 'corner' thinning kernel in the kernel set, and not by any decision due to the nature of the shape.

The alternative is to take a 'traditional' skeleton, and thin it so that the diagonals are always thinned on the 'outside' of the diagonal, as defined by the end points of the diagonal.

The special 'ThinDiagonals' thinning kernel, is designed to do this, with a 'Corners' kernel being used afterward to 'finish'. So lets thin the previous 'traditional' skeletion further..

This technique of thinning a traditional 4-connected skeleton, is slightly slower, than simply directly using the 'Skeleton:2' variant. The extra thinning required 8 thinning iterations of the 8 kernels, or 64 primative iterations.

Alternately you can just use the 'Corners' kernel only, though that will just generate the 'HIPR' variant, with just a 'random' choice of which side of the diagonals was thinned.

In any case by starting with a 'traditional' 4-connected skeleton, you can then generated an 8-connected version (of some kind).

Skeleton Information

When you have a skeleton (perhaps even both a 4 and 8 connected version) the next step is usally to find out more information about the skeleton. For example how many 'free end of lines', 'line junctions', and 'line loops' are present.

Number of Line Ends

Here I use the a Hit And Miss Search for 'LineEnds' on the skeleton we generated previously (extracting it from the 'red' channel). I then Dilate those line ends into Rings and color them before merging with the original skeleton, to make their locations highly visible.

Note that the lines connting to each other, or to the loop of pixels were not found.

If you did a pixel count (using a Histogram Output) you would see that this skeleton generated 12 line ends.

Number of Line Junctions

You can get a rough count count of the number of line junctions in an image by using the 'LineJunctions' kernel with a 8-connected skeleton, preferably one that was thinned down from the original skeleton used for counting line-ends. Do not mix two different skeleton generation variants.

If you did try try this kernel directly with a traditional 4-connected skeleton, you will get multiple matches for some of the 'T' junctions, making the count very inaccurate.

The result as you can see are 12 line junctions, whcih for this specific shape is correct.

However for some junctions the 'LineJunctions' kernel is inaccurate. For example a 4-line diagonal 'X' junction will only produce 1 match, while a orthogonal '+' junction, will produce 4 matches. Both of these special junctions should produce 2 matches, to keep the line junction count correct.

As such to get an accurite count you will need to add 1 more value for every 'X' junction, and subtract 2 counts for every '+' junction.

For a skeleton that has no loops the number of junctions should be 2 less than the number of line ends. However if the number of line ends equals the number of line junctions it means you have one or more loops in the skeleton.

Now this skeleton has 12 line ends and 12 junctions. so it contains at least one continuious loop of pixels somewhere in the image.

Number of Loops

FUTURE: Connected Object Labeling

Pruning Lines

So you know this image has at least one loop. Supose you want to simply the shape to just those loop(s). The solution to to 'Prune' all the line ends repeatally until you have removed them all.

For a 4-connected skeleton such as this you can even use a smaller set of 'LineEnds' kernels to make process about twice as fast.

A Verbose report on this would have shown that this took 75 iterations with 4 kernels, resulting in 300 primative interations to 'Prune' all the lines with free ends from the image.

That is about twice as many operations as was used to find the skeleton, which shows how much more intensive this operation can be. Using a full set of 'LineEnds' kernels (8 kernels), would also have taken 75 iterations, but with twice as many kernels, making this 600 primative iterations.

Fast Pruning of Lines

Fast Complete pruning technique..

  1/  Find line ends, and line junctions.
  2/  Delete the line junctions to completely disconnect all line segments.
  3/  Flood fill, or use contitional dilate to remove 'line end' segments.
  4/  Restore line junctions.
  5/  use that as a map on original image to restore 'loops'.

We have already covered the first step... resulting in... convert man_skeleton.gif -channel R -separate +channel \ -morphology HitAndMiss LineEnds man_ends.gif

To disconnect (or separate) all the line segments you can use a 'LineJunctions' kernel. However the default kernel set will not completely disconnect 'T' junctions (just locate them).

To properly disconnect all line segment you will also need to add orthogonal 'T' kernels to the kernel set, and it is also best to include a '+' junction too. For example. convert man_skeleton.gif -channel R -separate +channel \ -morphology HitAndMiss 'LineJunctions;LineJunctions:3>;LineJunctions:5' \ man_disconnect.gif

Thinning with these matches will actually disconnect the segments, however you you must do this all in one step, (see Thinning Style), or it will not work corectly. convert man_skeleton.gif -channel R -separate +channel \ -set option:morphology:compose Darken \ -morphology Thinning 'LineJunctions;LineJunctions:3>;LineJunctions:5' \ man_line_segments.gif

Here is a zoom of the 'loop' showing the disconnected segments. convert man_line_segments.gif -crop 22x22+47+29 +repage \ -scale 120x120 man_line_segments_zoom.gif

At this point we can now remove any line segment that contains a match with the previously discovered 'line end'.

This can be done either by 'flood filling' from those 'seed' points, to delete them. However this only works for a 4 connected skeleton, which is what flood filling assumes.

Example Here

Alternativally we can use Conditional Dialation to find all all the points simultaneously, and remove them. Example Here - when Conditional Dilate or Erode is available.

If you now restore the line junctions, do one prune, and remove any single pixels that are left, you will now have removed all the line segments quickly.

Yes this seems like a lot of steps, but believe me it is still a lot faster than having to 'prune the end of lines' 300 times to get the same result.

Thinning Style - Iterating or Intersection

If you were to one 'pruning' of the end of the line segments, and compare it to the original image you will find that more often than not a line segment was pruned anywhere from 2 to 4 times, depending on the exact shape and orientation of the lines.

That is because by default each of the 'Thinning' kernels is re-iterated against the results of previous kernel. That is it removes all the pixels selected by one kernel, before moving on to the next kernel, which may (and does) select more pixels from the end of the line. In other words it will, by default, thin the end of the lines multiple times for one 'iteration' though the kernel list.

That means you can not rely on the Verbose Output to get a exact idea of how long all the lines were by counting the number of pixels removed by a single iteration of this operator.

However you can modify how 'Thinning' works, so that it removes only the set of pixels a single 'Hit-And-Miss' iteration would find. In other words only remove one set of pixels per iteration.

Basically you set the Multi-Kernel Composition Setting to use a 'Darken' compose method. For example...

Add Example here

What happened here is that each kernel of the Pattern Matching Kernels will applied only to the original image. Any pixels that matched the original, will then be collected together. That is a darkening, or minimum, or intersection, of the results of all kernels. That means only the matches found by all the kernels against the original image will be removed, all in on simultanious step.

The result is that even if a line end gets matched multiple times by multiple kernels, only that single pixel on the end that was matched will be removed, rather than 2 or more pixels.

In summary, adding a 'Darken' Multi-Kernel Composition Setting, will ensure the 'Thinning' method does 'Intersection Thinning', rather than 'Iterative Thinning'.

However, while this will make the pruning of line ends more well-behaved, it can change the overall result of a thinning.

Take the case of 'Thinning' some boxes by thinning both the left and right edges simultaneously.

Example here

The 'Intersection Thinning' actually deleted the center line completely! What is happening is that the shape was thinned down to a two pixel thickness, and then both sizes of the 'thick' center-line matched the pattern and both sides were 'thinned'. The same thing can happen with Thinning down Skeletons.

The 'Iterative Thinning' on the other hand...

Example here

As you can see it preserved the center line. That is because one set of kernels first thinned down one side of a 'thick' center-line, but then the later kernels did not match this 'thinner' center line, so it was not removed.

Essentially there are situations where 'Iterative Thinning', is better than 'Intersection Thinning', and visa-versa.

Pattern Matching Kernels

As mentioned a 'Pattern Matching' or 'Hit-And-Miss' kernel can contain 3 different types of elements, foreground, background, and 'don't care'.

A value of '1.0' or (white) matches foreground pixels. A value of '0.0' or (black) matches background pixels. You can use either a value of '0.5' or the special value of 'Nan' or '-' to represent pixel elements that are not part of the neighbourhood and tus you 'don't care' about.

The 'Hit-And-Miss' will only match places where the smallest (minimum) foreground pixel is larger than the largest (maximum) background pixel. It will then return the difference between these two values, or zero.

Peaks

The 'Peaks' kernel is an extension of the 'Ring' kernel shown previously. Two radii arguemnts will generate a 'ring' of background pixels, surrounding a single foreground pixel in the at the central 'origin'.

Here are some examples of some of the more useful 'Peak' kernels...

The above kernels can be used to either definitively locate a single pixel 'peaks' in a sea of darker pixels, or find any small shape that completely fits inside the larger ring.

Edges

The 'Edges' kernel set, will match any pixel on a flat edge of a shape. It does not match pixels on a sharp ninty degree corner, though it will match a corner pixel on a octagonal shape.

As you can see all the 90 degree rotations are generated, but they are ordered in a 'flip-flop' mirror ordering that generally produces better results.

Typically this kernel is used as a type of image 'Thinning' kernel, however as it stands it will fail to thin diagonal edges, or generate a proper skeleton of an image.

For example...

See the 'Skeleton' kernels below.

Corners

The 'Corner' kernels locate any diagonal corner pixel around the edges of an image. (See 'Hit-And-Miss' examples above.

Here for example I used it to try and thin all diagonal edges... convert man.gif -morphology Thinning:-1 Corners thin_corners.gif

It can be combined with the 'Edges' kernel to produce one method skeleton thinning. See the 'Skeleton' kernels below, for an example of this.

ThinDiagonals

The 'ThinDiagonals' kernel is an alternative to simply using a 'Corners' kernel to thin 4-connected diagonal lines down to a 8-connected diagonal lines.

This can be used to thin a 'traditional' 'Skeleton:1' result to produce a accurate 'thined' version, than what the HIPR 'Skeleton:2' produces.

Note the results should be completed by using a 'Corners' kernel, to locate and thin 90-degree corners. See Thinner Skeleton for an example of usage. Thin Diagonals Sub-Types By providing a 'type[,angle]' argument to the kernel you can select specific sub-types that was used to make up the above kernel set. This will let you select you own specific set of kernels, to thin diagonals in exactly the way you want them thinned. For example, you could seperatally search for and thin of the four types of diagonals (using both the above kernels with tha same angle value). This will let you do an iterative reducion of just one type of diagonal, aborting as soon as all those specific diagonals has been thinned. As it is the above kernel set will simply try to thin all the diagonals repeatally until they have all been thinned. By separatally thinging the four types you can reduce the total number of 'primative morphology steps' that needs to be processed. However each of the four diagonals should still be performed using both pairs of kernels (for each specific angle) so that both ends of each specific diagonal are thinned together. LineEnds The 'LineEnds' kernel set, as shown in Pruning Ends of Lines above, is designed to locate the end of lines. More specifically it find the ends of sharp points. As you can see, it will only match lines that have at least two pixels, with the matching pixel 'capped' or 'surrounded' by background pixels. For example, here we use 'Hit-And-Miss' to find all the line ends. convert lines.gif -morphology HitAndMiss LineEnds hitmiss_lineends.gif Yes there is a lot of line ends in this image. But you should note that lines which end in a 'loop' of some kind will not produce a match. Note that if you are 'Thinning' an image using this kernel using an 'iterative thinning' style (the default), successive kernels could match the same end of a line two or more times, thus shinking the line many times during a single iteration of the whole 'Thinning' method. See Thinning - Iterative vs Intesection for more details. Line End Sub-Types You can alos this kernel give a 'type[,angle]' arguments, which will return one of the single kernel defintions that was used to generate the above 'LineEnds' kernel set. These can then be Expanded into a Rotated Kernel List as you require, or rotated to a specific 'angle', as needed. The default 'LineEnds' set, actually uses the kernel defintion. 'LineEnds:1> ; LineEnds:2>' The 'LineEnds:4' is a traditional line end kernel, which is rotated in 3x3 kernel cyclic fashion to produce 8 kernels. However it fails to locate the last pixel of a line connecting to a orthogonal 'T' juncion. The default 'LineEnds' set, as defined above, however does work to find even that final pixel at 'T' junctions. LineJunctions Where 'LineEnds' find the ends of a group of lines, 'LineJunctions' will find points that form a junction of 3 or more lines. For example, here we use 'Hit-And-Miss' to find all the line junctions. convert lines.gif -morphology HitAndMiss LineJunctions hitmiss_junctions.gif Note however that for a full 'T' junction the point found is not at the exact itersection of the 'T' but one pixel down the 'tail' of the 'T'. Similarly a '+' intersection may in fact find four matches rather than just one central junction. The 'LineJunctions' kernel is generally used for two purposes. Count the number of line junctions in an image. Disconnect all line segments from each other. See Skeleton Information, and Fast Line Pruning for more details of these two aspects. The kernel actually only defines foreground pixels as such it can also be used more simply as a 'Erode' method. Line Junction Sub-Types This kernel also provides access to the various sub-types, by specifying 'type[,angle]' arguments. This can be used to search for specific types of line junctions. Not all the above kernels are used by the default 'LineJunctions' kernel set. In fact only the first two of the sub-types ('Y' Junctions, and Diagonal 'T' Junctions) are used, following this kernel definition... 'LineJunctions:1@ ; LineJunctions:2>' Ridges The 'Ridges' kernels are used to locate ridges and thin lines of pixels, such as in a Distance Gradient image. These Kernels are experimental and may change. The default is designed to locate a single pixel thick ridge lines. Ridges:2 A special expanded subtype that is designed to find two pixel thick ridge lines. The complexity is caused by the need to locate and mark a slanted line of this sort, including mirrors of those lines. This set of kernels is important as a 'Morphological Skeleton' actually consists both 1 and 2 pixel thick lines. ConvexHull The 'ConvexHull' kernel set, is designed to thicken shapes so as to produce a 'Octogonal Convex Hull' of the shape. That is the smallest octogonal shape that can contain the whole of the shape. There are two sets of 90 degree rotated kernels, one the mirror image of the other. As the origin is actually a 'background' element, it is really only ment to be used as a 'Thicken' pattern kernel. However the kernel will fail for images containing horizontal or vertical 'slots', such as we have in the 'man' shape. convert man.gif -morphology Thicken:-1 ConvexHull man_hull.gif The solution is to 'Close' these slots (and the central hole) before using 'ConvexHull'. convert man.gif -morphology Close Diamond \ -morphology Thicken:-1 ConvexHull \ -morphology Close Diamond man_hull_full.gif Note in the above I also repeated the 'Close' after using 'ConvexHull'. The reason is that any large 'holes' in an image will also be reduced by the 'Thicken' down down to single pixels, or orthongonal 'slots'. Repeating the 'Close' removes those holes without effecting the final shape. Here is another example, where the original shape (white) was expanded using a convex hull thickening (red). convert circles.gif -channel R \ -morphology Thicken:-1 ConvexHull circles_hull.gif As you can see the result is an octagonal shape, while the central hole was reduced down to a two pixel slot, ready to be closed. Skeleton As you will see generating 'skeletons' of a particular shape is not an easy matter. Even with the same kernel set, re-ordering the kernels can generate a difference variation on the final skeleton result. Because of this I have not implemented just one 'Skeleton' kernel set, but a number of them, which can be selected by giving a 'type' argument number. WARNING: Only the first two of the following kernel sets are finalized, the last two are classed as 'experimental' and may dissappear or be replaced. Skeleton:1 The first or default set 'Skeleton:1' is a traditional thinning kernel. This is basically exactly like the 'Edges' kernel above, but cyclically rotated in 45 degree increments. convert man.gif -morphology Thinning:-1 Skeleton thin_skeleton1.gif The result is a reasonable 'thinned skeleton' of a shape, though diagonals tend to remain a little thick on one side. basically the skelection produced is 4-connected, which will allow you to use a Fast Pruning technique. Also note that this (and all the other 'Skeleton' kernel sets) does not correctly expand single pixel hole in the image. In other words the skeleton around that hole is nothing like a true Medial-Axis Skeleton. For more details see Thinning Down to a Skeleton. Skeleton:2 The 'Skeleton:2' variant is almost exactly the same as the traditional 'Skeleton:1' version. It was provided by the HIPR2 Image Processing Resources documentation. convert man.gif -morphology Thinning:-1 Skeleton:2 thin_skeleton2.gif If you compare this with the previous set, you will notice that the internal pixel of the corners have been removed. This will then allow the thinning operation to remove the extra thickening from the diagonals. However this diagonal thinning is not symetrical, and highly dependant of the shape of the image, and the order in which the kernels are applied. Edge-Corner Skeleton The 'Skeleton:2' variant is very closely related to just using a combined 'Edges;Corners' kernel list. convert man.gif -morphology Thinning:-1 'Edges;Corners' thin_edge-corner.gif The only difference between this and what 'Skeleton:2' uses is the ordering of the kernels in the list. Note how the resulting skeleton also differs, even though the same set of kernels was used. This shows that generating skeletons by thinning is actually rather fragile, as just a simple change of order can produce different results in the connected skeleton. Generating Skeletons of shapes. From HIPR2 Morphology http://homepages.inf.ed.ac.uk/rbf/HIPR2/morops.htm The skeleton/MAT can be produced in two main ways. The first is to use some kind of morphological thinning that successively erodes away pixels from the boundary (while preserving the end points of line segments) until no more thinning is possible, at which point what is left approximates the skeleton. The alternative method is to first calculate the distance transform of the image. The skeleton then lies along the singularities (i.e. creases or curvature discontinuities) in the distance transform. This latter approach is more suited to calculating the MAT since the MAT is the same as the distance transform but with all points off the skeleton suppressed to zero. Note: The MAT is often described as being the `locus of local maxima' on the distance transform. This is not really true in any normal sense of the phrase `local maximum'. If the distance transform is displayed as a 3-D surface plot with the third dimension representing the grayvalue, the MAT can be imagined as the ridges on the 3-D surface. Definition?? Morphological Skeleton (by erosion?), (by thinning) Skeletons are calculated either by repeated thinning, or by distance transform, and finding the 'creases', or ridges on the 3d surface (watershed transform?). mat.gif -morphology HitAndMiss Ridges -threshold 0 mat.gif -morphology HitAndMiss LineEnds -threshold 0 mat.gif -morphology HitAndMiss Ridges\;LineEnds -threshold 0 mat.gif -morphology HitAndMiss Ridges\;Ridges2 -threshold 0 mat.gif -morphology TopHat Diamond -threshold 0 mat.gif -set option:morphology:compose Lighten \ -morphology TopHat '3@:-,1,- -,1,- -,-,-' -threshold 0 One definition of medial axis transform (MAT) uses the intensity of each point to represent the distance ot the boundary. That the skeleton was used as a mask for the distance transform. The distance transform method is more suited to this, and it is probably faster to calculate 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 foreground object. (generated by thickening) Identifying shape by their skeletons. distance between farthest 'end' points, 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 skeleton of the shape after it is been Opened a little to smooth its outline a bit. convert man.gif \ -morphology Open Diamond \ -morphology Distance:-1 Chebyshev \ -morphology TopHat Diamond \ -auto-level chebyshev_dist_skel.gif This is basically a morphological skeleton. 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 skeleton of the shape. convert man.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 gray-scale values. Here is an enlargement of the 'head' of the skeleton, 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 actual size (distance radius) of the maximal disks that makes up the skeleton, letting you re-create the original shape. Created: 4 January 2010 Updated: 13 June 2010 Author: Anthony Thyssen, <A.Thyssen@griffith.edu.au> Major Input: Fred Weinhaus, <fmw at alink.net> Examples Generated with: URL: http://www.imagemagick.org/Usage/morphology/