ImageMagick Examples --
Morphology of Shapes

Index

ImageMagick Examples Preface and Index

Morphology Introduction

• Morphology Operator
• Basic Built-In Morphology Kernels
  • Unity,  Diamond,  Square,  Octagon,  Disk,  Plus,  Cross,  Ring,  Rectangle
  • User Defined Kernels
  • Image to User Kernel
• Iterating (Repeating) Morphology Operations
• Verbose Output of Changes (for monitoring)
• Displaying the Generated Kernel (for debugging purposes)
• Generating an 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
• Alternative Basic Morphology Techniques

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)

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
  • Skeleton Information
  • Pruning Lines
  • Fast Pruning of Lines
  • Thinning Style - Sequential vs Simultaneous
• Pattern Matching Kernels
  • Peaks,  Edges,  Corners,  Diagonals,  LineEnds,  LineJunctions, 
    Ridges,  ConvexHull,  Skeleton,  ThinSE

Distance Morphology Method

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

Conditional or Constrained Morphology

• Conditional Dilation
• Constrained Distance

Generating Skeletons from Shapes. Under Construction

• Distance to Skeleton
• Skeleton using Autotrace

Morphology modifies an image in various ways based on the nearby 'neighbourhood' of the other pixels that surround it. This in turn can provide a huge range of effects, Shape expansion and contraction (dilate/erode), to distance from edge, to thining down to a skeleton, or mid-line axis. Even the more anchiet method of 'convolution' techniques that provide blurring and sharpening techniques (next section), is in a way a type of morphology method. Essentually morphology is for the modification, determination, and discovery of the 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, perhaps repetitively, specific shapes can 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 highlight the individual elements of the 'kernel', and as you can see typical kernels are often very small. In fact the 'Disk' kernel show above is actually "", and that is one of the largest kernels shown above. However the 'kernels' are not really images. Just an array of floating-point values with one element specified to be the 'origin' of the kernel. This special element is the location of the pixel that will be 'effected' by the defined neighbourhood, and is typically though not always the center pixel of a symetrical kernel. 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, while others used for special purposes are of fixed size. For simple kernels, such as the first two, the 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, and can produce unexpected results, however it is sometimes faster than directly using a larger kernel, but again that is not always the case. The final size and shape of a 'Structuring Element', or 'SE', as a kernel is termed in morphology research papers, 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 shown, excluding the last one, are actually shaped. The parts that are transparent are not part of the defined 'neighbourhood' of the kernel. That is, they will do not have any valid value, and will not take part in any of the morphology calculations. Note how the second last kernel 'Corner #0' not only has 'on' values, but also 'off' values, 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 and related methods (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 large 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 (almost-black) at the edges to a maximum (pure-white) value in the center. However such kernels can also use negative, or even very large values, well beyond the normal range of other kernels. Remember a kernel is really just an array of values, and these could have any value, not just a 0 to 1 range. This type of kernel is especially important in 'Convolution Operations', a special method that has been around far longer than morphology itself. As a result IM has 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.

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 what 'neighbouring' pixels should effect the final result. Both are equally important and both 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 kernels that those methods may use later.

The "-morphology" operator (basic methods) and the initial set of kernels was added to ImageMagick version 6.5.9-0 by myself, while I was on a vacation in China. December 2009 to January 2010. However it is posible to perform simplified 'square' kernel morphology using the older and closely related "-convolve" method. See Alternative Basic Morphology Techniques below.

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 an odd number of pixels per side, 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 on results 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 generate a blank result. 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

The most minimal, though perhaps not the simplist kernel is the 'Diamond' built-in kernel. 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. Here is the result of a using 'Dilate' with the minimal 'Diamond' built-in kernel, and scaling the result larger to make it more visible.

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 are showing 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, as it is easiest to apply using other alterantive techniques. However it is not the most minimal kernel (see 'Diamond' above).

By default the 'Square' kernel uses a 3x3 pixel neighbourhood around the 'center'. magick pixel.gif -morphology Dilate Square -scale 800% 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).

Octagon

The 'Octagon' kernel is a 8 sided shaped kernel. And was specifically designed to match the 'Octagonal Distance Metric'. Do not confuse the two as they are very different kernels. Here are the resulting kernels for small radii... Note that at radius 1, you get the same kernel as a "Diamond" kernel. Because of this the default octagon size is of radius '2'.

From this point on I will be using a special kernel2image script to generate images of the kernels as they are much clearer than using a raw "dilate-scale" method (as above). Remember however the kernels are in generally very small, though Octagon and Disk kernels (see next) can become very large for specific uses.

The "Octagon" kernel was added in IM v6.6.9-4, along with the "Octagonal" distance kernel.

Disk

The 'Disk' kernel is as you would expect, a circular shape. And is commonly used when a very large morphological kernel is needed. Note however it is an aliased boolean circle. 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 'Disk:4.3' kernel is the default, and what I regard as the first true disk shape. Disks of this size or larger are especially good for generally rounding and smoothing image shapes. The final size of the kernel containing the disk is the 'radius' value rounded down, times 2 plus 1. As such the default 'Disk:4.3' 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. After that the kernel tends to mostly produce kernels that can also be generated using the previous kernel types. It is only as the radius gets large that true disk-shaped kernels start to emerge. The most important thing to note is that a disk with a fractional radius works a lot better than using an 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. The default size of a 'Plus' kernel is a radius of 2, producing 2 pixel 'arms' around the central 'origin'. A 'Plus:1' kernel happens to be the same as the default '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, such as I do later to display Skeleton Information. Basically it provides a method of Drawing Symbols, without needing to know exactly where the individual 'points' are located in the image.

Cross

The 'Cross' kernel is exactly like 'Plus' but rotated 45 degrees. It is also just a special kernel shape suitable for expanding pixels to mark the locations of various points

Ring

The 'Ring' kernel, like the 'Plus' kernel is also designed as a special 'shape' kernel for marking pixels and generating patterns on images. However it does not just take one radius, it can take two radii and is defined in the same way as Disk Kernels... 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', producing a 'Ring:2.5,3.5', which looks like a hollow octagonal shaped ring, that is ideal for circling a pixel. By varying the two radii you can create a 'ring' of any size and thickness. Small changes to the radii will add and remove very small numbers of pixels around the edges, allowing you for fine control of the look of the ring. If the two radii are within 1 pixel of each other you can also generate a ring consisting of sparsly separated dots, which can be useful as a special purpose neighbourhood. Small radii will also generate box-like kernels, that can also be useful. 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. In otherwords, a disk kernel but excluding the '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.

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 a 'geometry' argument to specify the exact size of the rectangular 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.

User Defined DIY 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 the argument of the previous 'Rectangle' kernel. It gives the size of the kernel, and optionally the 'offset' of the neighbourhood 'origin'. If only one number is supplied, it is the dimensions for an square kernel will be assumed.

Remember the geometry value is NOT a 'radius' argument but the overall kernal size.

If no 'geometry' or ':' is specified, then you are using the 'old' style specification. An 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. After the ':' (which is required after a 'geometry' specification) you then supply width × height floating point values separated by commas and/or whitespace. 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 morphological neighbourhood.

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

With a single pixel, Convolve works almost the same as Dilate, however Convolve uses the kernels values, expanding and adding neighbouring values together. Dilate on the other hand generally works using an on/off (boolean) shape and the maximum of all the neighbours. However when applied on a single isolated pixel with a boolean shape you get the same result. Note how you can add extra spacing (or even newlines) to the input string so as to separate the the individual rows of the rectangular kernel definition.

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... magick pixel.gif -morphology Dilate \ "5x3: nan,1,1,1,nan 1,1,1,1,1 nan,1,1,1,nan " \ -scale 800% k_user_5x3.gif

And finally here is an example of specifying a rectangular neighbourhood, that forms a 'L' shape around the 'origin'. I used '-' instead of 'nan' to specify the parts that is not part of the kernel. Note that the origin of this kernel is not even part of its own neighbourhood, it can be located anywhere inside the rectangular bounds of the kernel. magick pixel.gif -morphology Dilate \ "2x3+1+1: 1,- 1,- 1,1 " -scale 800% k_lman.gif

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

Convert an Image to an User Kernel

To make it easier to generate DIY kernels you can use the "image2kernel" script to create kernels. For example, here I magick a small flag (  ) into an user kernel data file ("flag_kernel.dat"), then use it to dilate an image with a couple of pixels in it. See also Generating an Image of the Kernel below, which can generate images (or generate enlarged pretty versions) of a kernel. This technique is also talked about in Alternatives to Drawing Symbols.

Iterating (Repeating) Morphology Operations

As you have seen you can generate a larger kernel, so as to apply a morphology over a larger neighbourhood. However in most 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 an using a larger kernel, but without the added computational cost of using a larger kernel.

For example, here is a dialation of a single pixel using a 'Diamond:3' kernel... magick pixel.gif -morphology Dilate Diamond:3 -scale 800% k_diamond_x3.gif

But you can also achieve the same result by using a smaller 'Diamond' kernel (radius 1) three times... magick pixel.gif -morphology Dilate Diamond \ -morphology Dilate Diamond \ -morphology Dilate Diamond -scale 800% k_diamond_x3.gif

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.

A large 'Diamond:3' kernel has 81 elements to be processed per pixel in the image. But repeating a smaller 'Diamond' kernal 3 times has 3×9, or 27 kernel elements to process or pixel in the image. In this case it is 3 times faster. This is speed increase isn't much in this case but he savings are much greater as the size of the kernels increase.

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. magick pixel.gif -morphology Dilate:3 Diamond -scale 800% k_diamond_3.gif

Note the difference between this and the first example. All that has happened is that we have moved the ':3' from being the radius of the 'Diamond' kernel to the number of times the 'Dilate' method is to be used. Using an 'iteration' to make the effective neighbourhood bigger, works for most 'circular', or 'convex' 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 'concave' shape) will produce a very unusual results.

For example, this is not that same as going from 'Plus' (radius 2) to a double size 'Plus:4' kernel... magick pixel.gif -morphology Dilate:2 Plus -scale 800% k_plus_2.gif

Note that if you use a 'iteration' count of '0', the morphology will do nothing. This is an 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 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 an 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 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 "-define debug=True" option, which turns on the Verbose Operational Control. As the morphology operator iterates, it will report an 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 'Octagon' 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.

	MAGICK_THREAD_LIMIT=1 \ magick pixel.gif -define debug=true -morphology Dilate:-1 Octagon \ -scale 800% iterate_infinite.gif

Note the number of changes made in each iteration. Initially there were 20 pixels converted from black to white. Then 48 more on the next iteration, and so on. This number generally grows as the edge of the resulting shape gets larger, but then started to shrink again as shape hits the image boundary. On the fourth dialation the last 4 pixels (in the corners of the image) were filled in. On the last dilation (iteration 5) the image was already completely filled, as such no more changes to any pixel was performed. As no changes were made the morphology automatically aborts, giving a final number of changes for this stage of the operation. Using an infinite iteration of '-1' does have an internal limit. This is currently set to the maximum width or height of the image. This is done to prevent ImageMagick from going into a never ending loop. Typically however operations will finish long before that internal limit is reached. Some morphology methods are actually defined in terms of simpler more primitive methods. For example a 'Smooth' method for example is one such compound method. The "-define" output that is generated when using this method, shows the multiple internal steps that goes to make up its processing. If you look you can see that the 'Smooth' actually iterates, 4 more primitive 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 '*' indicates that the kernel was reflected (or rotated 180 degrees around origin) before being applied by the morphological primitive. This is required for some compound morphological methods, in this case the 'Close' method always uses a reflected kernel in its use of the 'Dilate' and 'Erode' primitive methods.

#6 => Changed 311 Total 637

This is a report of the results of applying the morphology primitive to the image. The 'hash' number is an incremental count of the number of primitive passes though the image. This gives you a good idea of how computationally intensive a compound morphology operator is. You then get a the actual number of pixels that were changed in some way during that pass. If this is the last of a number of iterations for this specific primitive and kernel, a total count of pixel modifications is also output. This does not however reflect the total number of pixels changed in total from start to finish, just the changes caused by the low-level iteration of the specific primitive, kernel operation. Some pixels may change multiple times by some morphological primitives.

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.

Warning the number of pixels that change, may not be correct on machines running a multi-threaded environment on modern multi-core machines! It is only guaranteed to be accurate when executed in a single threaded environment. I class this as a bug, but not a vital one. If this is a problem then ensure you set the environment variable "MAGICK_THREAD_LIMIT" to a value of '1' for that specific run of ImageMagick, as I did in the last two examples above. As of IM v6.8.4 you no longer need the "MAGICK_THREAD_LIMIT" environment setting, as the counts are correctly handled in a multi-threding environment.

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 define a special setting...

-define morphology:showkernel=1 -define convolve:showkernel=1

Any of the above defines causes IM to output (to 'standard error') all the information about 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 the 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. 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 (located at +0+0), which is not very common. 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 a repeat of the previous example 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 if morphology is available, precision can also be regarded as available.

Generating an Image of the Kernel

To make it easier to see kernels, rather than using Dilating or Convolution on an 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 an 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'. The script makes it a lot easier to view and understand the various kernels, and is used extensivally to generate the kernel images displayed in these example pages.

For example, here is how I generated the "Octagon" kernel image. kernel2image -10.1 -m "Octagon" kernel_octagon.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 an identification label of the extracted "Octagon" kernel, and shadow effects.

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

If you want to create a kernel from an existing image, a script "image2kernel" can be used to create a kernel data file from an image. This script normally takes a gray-scale image, but if a multi-colored image is given each channel of the image is converted as a separate kernel data file.

Here I create the User kernal data from a small flag image (  ), then use "kernel2image" to convert that data back into an enlarged 'kernel image' for display. image2kernel -qgm flag.gif flag_kernel.dat kernel2image -6.1 -m -ml "Flag" @flag_kernel.dat kernel_flag.gif

ASIDE: I could have generated the 'enlarged' version of the small image more directly with a similar script "enlarge_image, but that would have been displaying the image, and not the Kernel Data, "flag_kernel.dat".

Multiple Kernel List Handling

Generating Multiple Kernels

As of IM v6.6.2-0 you can specify multiple kernels which will be applied to the image one at a time. To specify multiple kernels you would just append each kernel definition together, separated by a semicolon ';'. A final semicolon at the end 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 almost equivalent to the the special 'Corners' pattern matching kernel (see below). except that it limits itself to corners of the actual shape, and not just any corner, background or foreground.

Expanding to a Rotated Kernel List

As of IM v6.2.2-0 you can 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. (mnemonic: '@' is circular)
'>'	Rotate (square or linear kernels only) in 90-degree increments. (mnemonic: 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'. (mnemonic: '<' 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 an 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, would just reproduce the first kernel exactly. This is discovered and the generation of rotated kernels 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 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 the specific kernel definition. Such kernels typically also provide 'sub-types' of the original single kernel definition, so that you can pick and choose specific kernels for specific purposes.

Multiple Kernel Result Merging: Re-iterate or Compose

When you have defined multiple kernels, the morphology method also needs to know how it should merge the results generated by multiple kernels. This can be controlled by the use of a global Define...

-define 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 resulting image from applying one kernel, for 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-iterates' the result of one kernel with the next kernel, in sequence. 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. See Gaussian vs Blur Kernels which demonstrates this use more throughly.
By setting the '{compose_method}' to any method other than 'None', the operation will NOT be re-iterated. Instead each kernel will be applied 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 '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 an 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 white shape, from any background pixel making it smaller. You can also think of it as expanding the black areas of the image. For example, here is a simple binary 'man-like' shape that has been eroded using a 'Octagon' 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 expands the white shapes, making a shape bigger according to the kernel (and the number of iterations) specified. Of course that also means it will 'erode' the black areas of the image. 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 an erosion by using 'Dilate' on the Negated Images. magick man.gif -negate \ -morphology Dilate Octagon -negate dilate_man_neg.gif

Open   ( )

Here is the effect of the 'Open' method, but this time using much larger 'Disk' kernel. As a result you will see that 'Open' smoothed the outline, by rounding off any sharp points, and remove any parts that is smaller than the shape used. It will also disconnect or 'open' any thin bridges. However it does not remove any 'holes', or gaps that may be present in the image. such as between the shapes 'legs'. Also 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 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, with the same kernel, 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, so that the iteration can be used to 'expand' the effective kernel, rather than uselessly repeating the compound operation. 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 effective 'neighbourhood' defined by the kernel larger. magick man.gif -morphology Open:2 Disk open_man_x2.gif

Here you can see that the resulting larger neighbourhood resulted in both the man's 'head' and 'feet' extremities being removed. The main body of the shape basically intact, though also smoother in appearance, while the leg gap remains untouched. This is the same effect as doubling the size of the kernel, though its exact shape may not be exactly the same as a kernel of double the radius.

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, causing the image to become first larger, then smaller. This is the opposite order of what 'Open' does. The results is that the external points of the image will be left as is, but any 'bays' smoothed and thickened, and 'holes' and 'gaps' closed. Disconnected objects that are very close together can be come linked together. 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 before and after the operation. magick 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'. Here we smooth the image using a mid-range 'Octagon:3' kernel. magick man.gif -morphology Smooth Octagon:3 smooth_man.gif

As you can see all the 'indents', 'gaps', 'holes', and 'points' have been smoothed and rounded off according to the size and shape of the kernel. 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 'primitive' 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 HereHowever 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. As a result... Because of their nature the Intensity Methods will ignore the current "-channel" setting completely. For example, here I use the binary and intensity variants of 'Dilate' Morphology (expand bright areas), on the built-in "rose:" image. As you can see the normal 'Dilate' method can generate different shades in each of the large dilated spots, as each channel is separately handled. The second intensity dilation however preserves the full color of the brightest spots, expanding them according to the boolean kernel shape. The intensity 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 are the results of using each of the four 'Intensity' variants on the built-in rose image.

magick rose: -morphology ErodeI Octagon:3 rose_erode_intensity.gif

magick rose: -morphology DilateI Octagon:3 rose_dilate_intensity.gif

magick rose: -morphology OpenI Octagon:3 rose_open_intensity.gif

magick rose: -morphology CloseI Octagon:3 rose_close_intensity.gif

The last two may be particularly suitable as a replacement operator for the Paint Operator. These methods are classed as experimental, and comments or problems with its use is welcome. If I do not hear comments, nothing more will be added!

Alternative Basic Morphology Techniques

For people with versions of IM older than v6.5.9-0 you can still implement
some basic morphology methods.

You can generate a kernel that is all ones. For example a 7x7 array of 1's
(radius=3), by use an extremely large sigma and specify the appropriate radius,
using 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.

Unfortunately 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 one of the previous basic morphology methods, and the original image, or some other morphological method. Essentially they return the changes that was 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 of the image results.

EdgeIn

The 'EdgeIn method, also called a 'Internal Gradient', find the pixels that an the Erosion removes 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 'Octagon' 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. An example of using 'EdgeIn' with the alpha channel, to extract edge pixels is shown in Sparse Color as a Fill Operator.

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. An example of using 'EdgeOut' with the alpha channel, is shown in Outline or Halo Transparency.

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. magick 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 TopHat' is the pixels that a Closing of the shape adds to the image. That is, the the pixels that were used to fill in the 'holes', 'gaps', and 'bridges'. 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. As you can see it works fine. For other examples see Sparse Color as a Fill Operator, using the 'EdgeIn' method to find the edge pixels of an image. Also Outline or Halo Transparency using 'EdgeOut' to expand the edges of an image with a specific color.

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. Taken
to extreme this creates Skeletons, see also Thinning Skeletons.

Restoring objects using Open (smoothed result) or Conditional Dilation.

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' operations in an image of slowly increasing size structuring elements, and measuring the resulting area, you can quickly get a summery of number of such shapes that can be found in the image. By taking the derivative (slope) of that result you get a 'spectrum' of the number and size those shapes that form the image. This graph is the 'granularity' of the image for some particular shape. See Granulometry (morphology), Wikipedia. The differences from one size to the next will also let you separate and count specific elements based on size, and in turn separate areas containing different sized and shaped elements. The result is a method of texture segmentation. Demonstration of determining the number and size a collection of shapes. However this requires a 'counting' method (to be added) to implement fully. Historical note...This usage was in fact the original driving force behind the original creation of morphology methods, at a Paris mining company, in the 1960's. It allowed the creators to create an automated system to analyze the grain structure of microscopic photos of mineral samples to determine their suitability for mining. That is, locate and count the size and amount of mineral in samples. For example: Two mineral ores may have the same amount of desired mineral (usually as grains or crystals in the rock), but only the ore with larger grains could be effectively mined as it allowed you to more easily separate the large pure mineral from the surrounding ore bearing rock. This was a very labour intensive task, which morphology made a lot easier.

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 an user defined 'L' shape against a special morphological test image (enlarged for viewing individual pixels).

for method in erode dilate open close; do magick test_morphology.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 internal definition), only the image negated.

---

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

As of IM v6.6.9-4, you can use any of the method names 'HitAndMiss', 'Hit_N_Miss' or just 'HMT', and the variants, to specify this morphology method. Before this version only the 'HitAndMiss' method name could be used.

For example we could look for a 'foreground' pixel, which has a 'background' pixel immediately 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 method 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 value of '1' meaning 'foreground', a value of '0' meaning 'background', and also a third element which can be specified as either 'Nan', or '-' or a value of '0.5' which means 'I Don't Care' or 'Any Pixel' What value you use for the 'origin' is very important as it will define whether you only want to 'hit' the foreground shape, or the background pattern. But if you specifically set the 'origin' value to a value of 'I Don't Care', then you can match either foreground and background pixels who has the correct surrounding neighbourhood. For example if I use a structured element like... You get any right edge pixels which are either inside or outside. As such you are now marking both sides of the shape boundary, and extracting a 2 pixel wide edge. However not all pixels match the patten, so not ever pixel is doubled, but in general that is what you get. The use of a 'I Don't Care' value for the 'origin' is actually very common, especially when we later look at Thicken and Thinning methods, which restrict themselves to either adding or removing pixels. By 'Not Caring' the same kernel definition could be used for either operation, as the operation itself defines what type of 'hits' you are interest in.
Here is another example, but this time I again limit my 'hits' to pixels that fall inside the shape but which form a North-West facing corner. By expanding this single corner to a set of 90 degree Rotated Corners by adding a '>' flag, we can find all corners that appear within the shape.

magick man.gif -morphology HMT "3>:0,0,- 0,1,1 -,1,-" hmt_corners.gif

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. Unfortunately the 'changed' pixel count is of all the pixels which are turned off by each kernel application. In other words 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 with the results of itself is usually useless as the image would have change so much you will probably end up with no matches afterward. You can, and as you see, use the results to modify the original image so as to generate a slightly different image.

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. Then you can use the 'LineJunctions' kernel set, which is designed specifically for this purpose. 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 especially 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...

magick lines.gif \( +clone \ -morphology HMT LineJunctions \ -morphology Dilate Ring \ -background red -alpha shape \ \) -composite hmt_junctions_rings.gif

You can now clearly see locations where this particular 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. Another similar 'Hit-And-Miss' kernel set is the 'LineEnds' kernel which can be used to find the free ends of all the lines in the image.

magick lines.gif \( +clone \ -morphology HMT LineEnds \ -morphology Dilate Ring \ -background red -alpha shape \ \) -composite hmt_lineends_rings.gif

HitandMiss - with foreground pixels only -> erodeHitandMiss - with background only -> negated dilate

Hit And Miss with Gray-scale Images

When the 'Hit-And-Miss' method is applied to a gray-scale 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 math) 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 gray-scale images this is equivalent 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. magick 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 NOT match foreground pixel, or you will essentially be adding a pixel, where a pixel is already present. In the above set the origin pixel to a background pattern, so only background patterns will actually match. An alternative is to always set the origin to a 'Do Not Care' element value. By doing this you will be able to use the same kernel pattern for thicken 'Thicken', and as you will see later for 'Thinning' as well. So the better rule is set origin to 'Do Not Care'.

Another way to generate a 'Thicken' operation is to generate a Union of the results of 'Hit-And-Miss' of this kernel with the special 'Unity' kernel so as to include the original image in the results. For example... magick man.gif -define 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 'Hit-And-Miss' method specifically sets this composition setting 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 'Octagonal Convex Hull'. That is, it will try to fill in all the gaps between the extremes until it produces a 'octagonal 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 primitive iterations, plus another 4 primitive iterations needed to do the two 'Close' methods. That can take quite a large amount of time. Basically iterating using Hit And Miss Pattern Matching can be very very 'slow', and if an alternative technique 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 octagonal shape, by getting an intersection (Darken Composition) and the edge of the convex hull and the original shape. Any connected shape that fits inside the convex hull, but also includes at least one pixel on every edge of the above convex hull, will generate the same octagonal convex hull.

Thicken with Gray-scale Images

When handling a gray-scale image 'Thicken' will add the 'Hit-And-Miss' foreground and background separation 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 MinusSrc composition) the results of 'Hit-And-Miss' 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... magick man.gif -define morphology:compose=MinusSrc \ -morphology HMT 'Unity ; 5x1+0+0:1,1,1,1,0' hmt_thinning.gif 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.

Line Connected-ness

FUTURE: 4-connected verses 8-connected linesSee discussion in IM forums, From 8-connected to 4-connected lines.

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 meant to be the center line of pixels between any two (or more) edges of the shape.A skeleton is 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 repeatedly, until only the center lines are left. A Verbose report on the above would have shown that 18 iterations, with 8 kernels, totalling 144 primitive 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 this specific skeleton thinning kernel, and is caused by the kernels all requiring at least background pixels before they will make any thinning match. You can use sets of skeleton thinning kernels to solve this problem. A simplier 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 has now expanded to produce larger continuous loop of pixels around it.

Here is a close up of loop around the eroded hole. magick 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. That is, the disadvantage of the 'erode' soltion. The skeleton is also limited to octagonal lines, which means it is missing a lot of detail, though in this case that simplification can be a good thing. See the section on Skeletons below. This is 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 other variations in the resulting 'Thinned Skeleton'. Thinner, 8 Connected, SkeletonThis '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' skeleton.

One solution 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... magick man.gif -channel RG -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. magick 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 controlled 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 'Diagonals' thinning kernel, is designed to do this, with a 'Corners' kernel being used afterward to 'finish'. So lets thin the previous 'traditional' skeleton 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 primitive 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. However it will only take 1 pass of all 4 kernels, and as such it much much faster than using 'Diagonals'. In any case by starting with a 'traditional' 4-connected skeleton, you can then generated an 8-connected version (of some kind), Very easily.

Skeleton Information

When you have a skeleton (perhaps even both a 4 and 8 connected version) the next step is usually 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 EndsHere 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 all connect each other, or to the loop of pixels were not found. Only the free line ends were indicated. If you did a pixel count (using a Histogram Output) you would see that this skeleton generated 12 line ends. Number of Line JunctionsYou 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, which 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 an 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 accurate 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 continuous loop of pixels somewhere in the image. Number of LoopsFUTURE: Connected Object Labeling

Pruning Lines

So you know this image has at least one loop. Suppose you want to simplify the shape to just those loop(s). The solution to to 'Prune' all the line ends repeatedly 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 primitive integrations 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 primitive 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... magick man_skeleton.gif -channel R -separate +channel \ -morphology HMT 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. magick man_skeleton.gif -channel R -separate +channel \ -morphology HMT 'LineJunctions;LineJunctions:3>;LineJunctions:5' \ man_disconnect.gif

Thinning with these matches will actually disconnect the segments, however you must do this all in one step, (see Thinning Style), or it will not work correctly. magick man_skeleton.gif -channel R -separate +channel \ -define 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. magick 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 HereAlternatively we can use Conditional Dilatation 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 - Sequential or Simultaneous

If you were to do one single '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. For example (resulting image enlarged) is is a default line ends thining That is, because by default each of the 'Thinning' kernels is applied against the results of previous kernel, in sequence. That is, it removes all the pixels selected by one kernel, before appling the next kernel to that result, which may (and does) select more pixels from the same end of line. In other words it will, by default, thin the end of the lines multiple times for one complete 'iteration' though all the kernels provided. That means you can not rely on the Verbose Output to get an 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 through all the kernel would find. In other words apply all the kernels to the same image at the start of the interation, merge them, then remove just those pixels, once only for all kernels. That is, remove all the HMT selected pixels simultaniously. Basically you set the Multi-Kernel Composition Setting to use a 'Darken' compose method, which will do exactly that. Specifically merging all the selected pixels for a single removal of selected pixels. For example...

magick line.gif -channel GB -define morphology:compose=darken \ -morphology Thinning LineEnds line_simultaneous.gif

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, we will only remove a 'intersection' of the results of all kernels against the original, by using a 'darken' composition. But the removal is done all in one step for any one iteration through all the kernels. The result is that a line end will only ever get matched one time, even if multiple kernels could match that line end. And thus only the single pixel on the end will be removed, rather than 2 or more pixels, by different kernels. In summary, adding a 'Darken' Multi-Kernel Composition Setting, will ensure the 'Thinning' method does 'Simultaneous Thinning' (all kernels simultaneously), rather than 'Sequential Thinning' (one kernel at a time - the default).
However, while this will make the pruning of line ends more well-behaved, it will make it slower, and can change the overall result of a thinning. Take the case of 'Thinning' some boxes by thinning both the left and right edges simultaneously. The 'Simultaneous Thinning' actually deleted the center rectangle completely! What is happening is that the shape was thinned down to a two pixel thickness, and then both sides of the 'thick' center-rect matched the pattern and both sides were 'thinned'. The same thing will happen if you do this when Thinning down Skeletons. The default 'Sequential Thinning' on the other hand produced...

magick rect.gif -channel GB \ -morphology Thinning Edges rect_seqential.gif

As you can see it preserved one of the pixels (on the right) to be a skeleton center line. That is, because one set of kernels first thinned down one side of a 'thick' center-line, but the later kernels did not match this 'thinner' line, so it was not removed. Essentially there are situations where 'Sequential Thinning' (the default), is better than the special 'Simultaneous 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 thus 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 arguments 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 'peak' value in a sea of darker pixels, or find any small shape that completely fits inside the larger ring. They are especially useful to improve the contrast of a Correlation Pattern Match Search.

Edges

The 'Edges' kernel set, will match any pixel on a flat edge of a shape. It does not match pixels on a sharp ninety degree corner, though it will match a corner pixel on an 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' above for an example of its use. Here for example I used it to try and thin all diagonal edges...

magick man.gif -channel RG \ -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.

Diagonals

The 'Diagonals' 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 4-connected lines, by removing the outside set of pixels from a corner toward the center until complete. 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. Diagonals Sub-TypesBy 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 specify your own specific set of kernels, to thin diagonals in exactly the way you want them thinned. For example, you could separately thin each of the four types of diagonals (using both the above kernels with the same angle value). By doing this you can do an iterative reducing of each type of diagonal one at a time, aborting as soon as all those specific diagonals has been thinned, and thus reducing the overall number of 'primitive morphology steps' that are performed. example neededAs it is given, the default kernel set will simply try to thin all the diagonals simultaneously and repeatedly until they have all been thinned. That means the all the kernel will be applied until all the diagonals have been thinned, rather than just the diagonals that need thinning. That means it perform many 'primitive morphology steps' that are no longer needed, with most kernels making no changes to the image during each loop. full example neededRemember 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, such as when the diagonal is part of an 'arc'. There is a related discussion about this type of thinning/thickening operation in the IM forum, From 8-connected to 4-connected lines.

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. 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 shrinking the line many times during a single iteration of the whole 'Thinning' method. See Thinning - Sequence vs Simultaneous for more details. Line End Sub-TypesYou can also this kernel give a 'type[,angle]' arguments, which will return one of the single kernel definitions 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 definition. The 'LineEnds:3' is the orthogonal equivalent to the diagonal 'LineEnds:2', which will only find the line ends well away from any diagonal corner or junction. The 'LineEnds:4' is a traditional line end kernel, which is rotated in cyclic fashion to produce 8 kernels (for example 'LineEnds:4@). However it will fail to locate the last pixel of a line connecting to an orthogonal 'T' junction. The default 'LineEnds' set, as defined above, does however find that final pixel at 'T' junctions, using the same number of kernels.

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. The 'LineJunctions' kernel is generally used for two purposes.

• Count the number of line junctions in an image, and thus work toward a count of the number of line segments in the skeleton.
• Disconnect all line segments from each other.

Note however that at the 'T' and '+' junctions in the above image, the 'Y' junction kernel matches points that is one pixel one pixel away from the actual intersection. Because of this junction counts may not be exactly as expected, especially at the '+' where four matches were found rather than just the required two for a junction count. Caution is recommented. 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 be applied simply as a 'Erode' method, instead of as a 'Hit-and-Miss' method. Line Junction Sub-TypesThis 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. The kernels 'LineJunctions:2' can also be specified using 'LineJunctions:3,45', and similarly 'LineJunctions:5' and 'LineJunctions:4,45' are equivilent. The default 'LineJunctions' kernel set only uses the first two junction definitions (the 'Y' and diagonal 'T' junctions), in the following way... This is appropriate for a 8-connected line junctions. As discussed in IM Forums "Kernels used by LineJunctions" if you want to test for 4-connected line junctions only, you would need to look for orthogonal 'T' junctions, and a '+' junctions. However as the 'T' kernels will also hit a '+', you can cut the above down to just... A separate image test for just 4-way '+' junction can be used to separate them from 3 way 'T' junctions, if that is needed for determining line segment counts.

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:2A 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 'Octagonal Convex Hull' of the shape. That is, the smallest octagonal 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 meant 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.

The solution is to 'Close' these slots (and the central hole) before using 'ConvexHull'. magick 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 orthogonal '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). magick 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

Generating 'skeletons' by thinning of a particular shape is not an easy matter. Even with the same kernel set, re-ordering the kernels can generate a different variation on the final 'skeleton'. 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.

Skeleton:1

The first and default set, 'Skeleton:1', is a traditional thinning kernel, as what was first used. This is basically exactly like the 'Edges' kernel above, but cyclically rotated in 45 degree increments.

magick man.gif -channel RG \ -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 skeletion produced is 4-connected, which will allow you to use a Fast Pruning technique. Also note that this kernel set does not correctly expand single pixel hole in the image. In other words the skeleton around that hole is not even close to the center line between the hole and the rest of the image. 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 found in the HIPR2 Image Processing Resources documentation.

magick man.gif -channel RG \ -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 symmetrical, and highly dependant of the shape of the image, and the order in which the kernels are applied. The 'Skeleton:2' variant is very closely related to just using a combined 'Edges;Corners' kernel list.

magick man.gif -channel RG \ -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.

Skeleton:3

The 'Skeleton:3' was developed in a formal study of using Thinning Kernels (See ThinSE Kernels below), in a research paper "Connectivity-Preserving Morphological Image Transformations" by Dan S. Bloomberg, 1991. He developed quite a number of such skeletons, and tabled the results of the study. The following is the best one he was able to come up with, that will generate a 4 connected skeleton. However unlike previous skeletons this requires the use of 3 rotated kernels (12 total).

magick man.gif -channel RG \ -morphology Thinning:-1 Skeleton:3 thin_skeleton3.gif

It should be noted that the first group of rotated kernels contains just a single background pixel. That means this skeleton was able to open up the single pixel hole that is present in the 'man' shape, and produce a center line oriented skeleton. It does not generate too may branches, produces clean smooth lines, and also thins down completely. All in all this is one of the better skeleton thinning kernels.

ThinSE

The same research paper "Connectivity-Preserving Morphological Image Thansformations" by Dan S. Bloomberg, actually developed from first principles a complete range of minimal 3x3 'Thinning Structure Elements' that were all designed to preserve either 4-connected line or 8-connected lines. The 'ThinSE:{type}' kernel set is a list of all those structuring elements, and are listed below sorted into groups based on connectivity and strength in preservation. The '{type}' is a number based on the super-script (connected-ness) and sub-script element numbers used in the research paper. As such kernel 'ThinSE:41' is the first of the 4-connected line preserving elements. You can also add a rotation angle, or generate a set of rotated or mirror-rotated flags to the given kernel definition. The very last 'General Thinning Kernel, 'ThinSE:482', you may recognise as the being same kernel used to define the set of Edge Detection Kernel. This general kernel is actual the core kernel from which all the other thinning kernels shown above were developed. It is the default kernel of the set. Note that both general kernels 'ThinSE:481' and 'ThinSE:482' are the only kernels rotationaly related. That is 'ThinSE:481x45' is equivalent to 'ThinSE:482'. Many of the other built-in HMT kernel sets are actually internally defined in terms of these kernels. For example, the kernel set 'ThinSE:41 ; ThinSE:42 ; ThinSE:43', and its rotated expansion, will produce the 12 kernels used to create the 'Skeleton:3' set. This skeleton and was listed in the paper as being the best kernel set found to produce good thinned skeleton. The other skeleton generating thinning kernels are also defined using the above kernels.
Be warned however that some kernels, such as 'ThinSE:44', which while designed to preserve 'connected-ness', does not actually preserve line ends, and as such will cause a skeleton to be pruned down to a single point, or set of connected rings. All the kernels do not define the central origin value, which means you can these 'thinning kernels' are not only for 'Thinning Shapes', but also can be used 'Thicken Shapes' as well, to generate SKIZ (zones of influence). If you look carefully, you will probably note that each of the 4-connected kernels are actually also present in a negative and 180 rotated form in the 8-connected set, and visa-versa. For example 'ThinSE:41' and 'ThinSE:84' are negated rotations of each other. The reason is that 4 and 8 connectivity is closely related to each other via the duality of thinning and thicken morphological methods (using negated images). Essentually, a 4-connection preserving 'thinning kernel', which is then used to thicken an image, will result in a 8-connected background skeleton (unpruned SKIZ) around the shape, and visa-versa. So by using the negated forms (so thicken and thin methods are swapped) you can generate the other form of connected-ness for the same operation.

---

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 an anti-aliased shape to work with the distance method. And only with specially designed Distance Kernels. The distance kernel is applied to the image so that each pixel is assigned the smallest pixel value plus the kernel value for that distance. This is applied all over the image simultaneously, using an algorithm that does not require multiple iterations, as we saw in previous morphology methods. Because of this it is about as fast as a single primitive morphological operation, which is blindingly fast compared to say a Thinning Skeleton morpholgical method. As it is applied across the whole image, no 'iteration' argument is needed, as repeating (iterating) the same kernel operation will result in no further change to the result.

Before IM v6.6.9-4, a '-1' iteration count was needed, as the kernel was applied using a technique similar to a normal Erode. This is no longer needed, and any 'iteration' argument given, other than zero (no action), is now simply ignored.

Here is an example of using the 'Distance' method, on our 'man' shape. 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 closely, 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 can provide greater output value 'depth' than for example GIF, without any color loss like JPEG. It is also the reason why the Depth Setting "+depth" was used to ensure the output is reset to 16-bit depth (for my Q16 version of IM) even though I read in an 8-bit GIF source image. For users with a Q8 version of IM, I suggest you read about the 'scale' distance kernel option in Distance Kernels (below) to adjust the 'scaling values' used (see next section below). Using Q8 versions of IM with non-interger distance kernels (like this Euclidean Distance Kernel) is not recommended, though will produce a less accuriate result. See IM Examples section on Quality and Depth, for a better understanding of these two aspects.

By default the built-in Distance Kernels will apply a color value of "100 × {pixel_distance}" to each pixel. If a pixel is brighter that this, it is set to that value so that the smallest distance from a pixel to any edge is assigned. The result is that pixels along the very edge of a shape will be assigned a 100 unit value more than background color. The next pixel further in will be given 100 units more. Exactly how many units will be assigned is given by the Distance Kernel that is used. So lets look 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. In other words, we see a very dark, but not really completely black image.

Lets use the mathematical "-auto-level" to adjust the resulting color values so the brightest, or most distant pixel from an edge is set to white. This way we can actually see the full effect of the 'distance gradient' generated. magick distance.png -auto-level distance_man.gif As we no longer care about the exact 'distance' values generated for this image, just the visible effect of the distance, the image can now be saved and displayed using the GIF image file format.

This is what the 'Distance' method does. Generate a gradient across the given 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, for example a value of 3000 units (Q8 users can probably use a value of 20). magick man.gif -threshold 50% +depth \ -morphology Distance Euclidean:4,3000 distance_scaled.gif

Note that the distance gradient did not cover from black to white, with it reaching a peak at some grey-scale value. As we already know the 'distance of the peak, we can calculate that maximum peak to be 16.16 * 3000 => 48480 or about 74% grey. You can also use a percentage scaling factor, for example use a 8% color range value for each pixel distance from the edge. magick man.gif -threshold 50% +depth \ -morphology Distance Euclidean:4,8% distance_scale_percent.gif

As you can see this time we reached our maximum value limit before reaching the maximum distance. You can calculate that maximum distance that the distance gradient can cover is (100% at maximum range) / (8% per pixel) => 12.5 pixel_distance. Of course if you were using a HDRI version of ImageMagick the full distance values will be kept in memory, at least until you Clamp it value, or save it into a non-floating point image file format. You can also directly specify the maximum pixel distance you are interested in by using the special Distance Scaling Flag, '!'.

As we already know out shape as a maximum distance from edge of 16.16. least request a limit of 18 pixel. magick man.gif -threshold 50% +depth \ -morphology Distance Euclidean:4,'18!' distance_range.gif

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 gray) only the pixels that are a direct neighbour to 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', so as to make the shape 'clean n smooth'. For example... Of course this also has the effect of also 'closing' the gap between the shapes 'legs' too, which 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 magick that into new mask. The result is that any holes have been closed, but the outside boundary of the image has been preserved. 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 an 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 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 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 ScalingAs 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). An 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 'integer' distance kernels, with a scale factor of '1'. 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 '12.5%' of the color value range, then you will be able to get a distance metric of about 8 pixels before the distance overflows the color range limits of the IM version you are using. 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. It just does not have the range for the data values needed for may distance operations. Of course any scale (including full floating point) can be accurately used for a HDRI versions of IM, as the resulting color values are also stored as floating-point values. Just be sure to rescale the color range appropriately before attempting to save such an image to non-floating point image file formats.
A number of different distance measuring kernels are provided, with one that can be used in a two different ways. Each kernel provides to with different resulting 'distance metrics' for specifying the pixel distance from the edge, and basically define what is to be considered the 'nearest edge'.

Chebyshev (Chessboard) Distance Kernel

The 'Chebyshev' distance kernel is the simplest, and specifies that all pixel around the 'origin' is simply 1 distance unit from its neighbours. That is, all 8 neighbours are 'next' to each other. As such only are the immediate four neighbours a distance of 1 unit, but the diagonal neighbours are also exactly 1 unit away. This is often likened to the distance in squares that a 'King' or 'Queen' chess piece moves of a chessboard, and hence is often also known as a 'Chessboard' distance metric. Note however that distance kernels have use a default {scale} factor of 100 distance units, per pixel of distance. As such the distance is 100 units for every step away from the origin. This was also the kernel that was used in the previous examples above. Here is the actual kernel it generates... 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'. However so we can see what is going on lets use a slower 'Iterative Distance' morphology method using an infinite iteration count.

	magick man.gif -threshold 50% +depth \ -define debug=true -morphology IterativeDistance:-1 Chebyshev \ chebyshev_gradient.png magick identify -format 'Maximum Distance = %[max]' chebyshev_gradient.png magick chebyshev_gradient.png -auto-level chebyshev_gradient.gif rm chebyshev_gradient.png

The 'Iterative Distance' morphology method calculates distance by applying the distance kernel repeatally until no more changes in value are seen. This is much slower than the more normal 'Distance' method, which uses a two pass method to set the distance across the image as a whole. However the verbose output of 'Distance' method is far less interesting.

I turned on the Verbose flag so that the command will output how many pixels were changed (all white pixels) by the operation, during each interation (pass) through the image. Then I extracted the 'maximum' distance generated ('1400'), before adjusting the result (normalizing) into an image where you can see the resulting gradient. The maximum distance '1400', is value of the brightest pixels in the image (actually it is a cluster of 4 such pixels). This information is the most important result of this distance kernel (metric), as it represents the size of the largest square that will fit within this shape. Specially 14 pixel radius or a square of approximately (R-1)*2+1 => 27 pixels per side, centered on those 4 maximum pixels. As all the distances units in this kernel are always multiples of '100' then this final distance value should always be a multiple of '100', and will never have any fractional component. Basically this kernel will produce an integer distance, and you can a simple '1 unit' scale with this kernel without loss of any distance information. This is recommended if you are using a Q8 version of ImageMagick, or are applying this to very very large images.

Here is an magnification of the gradient between the shapes 'legs' which highlights the features of the distance gradient generated. magick 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 a specific feature of this simple form of distance metric, and directly reflect the square nature of the distance kernel itself. The above also shows the 4 maximum distance pixels in the figures 'belly' close to the top of the image. By centering a square on any of these 4 point you can generate the largest odd sized square that is wholly contained within the figure. However be warned that there may be a number of such 'peaks'.

Manhattan (Taxi Cab) 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. Because of this other more common names for this measure is 'Taxi Cab' or 'City Block' distance metric. 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'.

	magick man.gif -threshold 50% +depth \ -morphology Distance Manhattan manhattan_gradient.png magick identify -format 'Maximum Distance = %[max]' manhattan_gradient.png magick manhattan_gradient.png -auto-level manhattan_gradient.gif rm manhattan_gradient.png

I did not use 'Iterative Distance' this time, and even if I did the total count of pixels changed would not be accurite. Only the previous 'Chebyshev' kernel will set a pixel distance once and only once. Note how 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. This distance kernel is also a 'integer' kernel and as such you can set the scale to just '1 unit' without loss of information.

Here is an magnification of the gradient. magick 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, as eflected by the actual kernel values.

Octagonal Distance Kernel

The 'Octagonal' distance kernel is a little different than the other two. It is created by generating first a Manhattan distance for the pixels on the very edge, then using Chebyshev for the pixels that are 2 units distance from the edge. It then repeats using Manhattan distance for the 3 unit distance pixels, and so on. The result is an 'interleaving' or 'averaging' of distance resulting from using the two simpler kernels. As this kernel is based on an interleaving of two integer distance kernels, it is also an integer distance kernel. As such a scale of '1 unit' can be used to produce smaller values, for lower quality ImageMagick versions, or very large distance measurements. The distance shape is also a mixture of the two kernels and as such produces a the equivalent of the 'Octagon' shaped kernel. Here is the actual kernel it generates... Note that the kernel has a minimum and default size of radius 2, forming a 5x5 pixel kernel. This slightly bigger kernel is needed to generate the 'interleaving' of the kernels. The overall distance will generally be very slightly smaller than a true distance. Here we again calculate the maximum distance...

	magick man.gif -threshold 50% +depth \ -morphology Distance Octagonal octagonal_gradient.png magick identify -format 'Maximum Distance = %[max]' octagonal_gradient.png magick octagonal_gradient.png -auto-level octagonal_gradient.gif rm octagonal_gradient.png

The result of '1500' is an 'integer' distance, and actually falls between the too-small Chebyshev Distance, and the too-large Manhattan Distance. However in general it should be reasonably close to the real actual distance to the center of the shape, while remaining an 'integer' value.

Here is an magnification of the gradient. magick octagonal_gradient.gif -crop 25x20+39+69 +repage \ -scale 500% octagonal_magnify.gif

You can clearly see the 'octagonal' distances that have developed around the top of the leg gap. You can also see that the diagonal was generated using an interleaving of thick and thin diagonal lines.

Fractional Octogon Distance Kernel

A named distance kernel has not been provided. But it fits into the distance kernel sequence we are studing nicely at this point. You can generate another type of integer distance kernel using an octagonal shape. However the integer distance in this case uses an unit value of 2 per pixel, so really the distance values generated needs to be halved, generating a frational value from the small integers that are generated. This the name "Fractional Octogon". To do this we use an integer distance of 2 between neighbouring pixels, and 3 for the diagonal.

'3: 3,2,3
    2,0,2
    3,2,3'

As 'half integers' can be generated the smallest minimal scale that can be used is '2 units'. and while not as accurate a 'knights move' it does work well. The octogon of this kernel has 'points' in the orthogonal direction, rather than 'flats' as the previous kernel generates. It is related to, but not quite the same as the next 'Knights Move' kernel, and could be considered a sort of 'near integer' form of the 'knights' kernel. If you want to scaling this the same as previous IM distance kernels you can use. this kernel.

'3: 150,100,150
    100, 0 ,100
    150,100,150'

Here is an example

	magick man.gif -threshold 50% +depth \ -morphology Distance '3:3,2,3 2,0,2 3,2,3' \ fractional_gradient.png magick identify -format 'Maximum Distance = %[max]' fractional_gradient.png magick fractional_gradient.png -auto-level fractional_gradient.gif rm fractional_gradient.png

The result of '34' is an 'integer' distance, but needs to be divided by 2 to produce an actual maximum distance result of 17. however while this is also an integer, it could just as easilly come out as being a fractional distance of 16.5. This fractional aspect of distance results is why most kernels are defined using units of 100, and will in later kernels become more prevelent as we move away from purely integer distance kernels.

Here is an magnification of the gradient. magick fractional_gradient.gif -crop 25x20+39+69 +repage \ -scale 500% fractional_magnify.gif

The gradient (if you study the results carfully) is an octagonal shape. But it is hard to see the pixels that have common distance values. To see the shape more clearly, I have taken the above image and colored one set of pixels with the same color value, red. magick fractional_magnify.gif -fill red -opaque gray53 \ fractional_magnify_shape.gif

As you can see pixels of the same value are generally separated in a 'knight's move' pattern, but form lines that generate an octagonal shape. The octogon is however rotated 45 degrees from the Octagonal Distance Kernel It is also this shape difference that causes the final maximum distance to be larger. Essentually a larger octagon rotated in this way fits into the shape better, thus the larger maximal distance result. Another fractional distance 'interger' kernel that can be used is this one, though the distance is in terms of 3 units instead of 2. That is, the results need to be divided by 3 to get the distance in terms of pixel size, which is not really a great divisor to use. It is however another octagonal type distance metric.

'3: 4,3,4
    3,0,3
    4,3,4'

The Euclidean (Knights Move) Distance Kernel below also generates an octagonal style of shape (all 3x3 distance kernels do), but tries to be as accurite as posible along the diagonals. This may or may not be the best idea, but it is the most mathematically logical octagonal distance kernel of this type.

Chamfer Distance Kernels

A named distance kernel has not been provided. But it fits into the distance kernel sequence we are studing nicely at this point. A 'Chamfer' Distance kernel (not yet implemented), is defined using just the numbers (typically integers) that is to be used to fill in the distance matrix. You can for example give it 2 numbers to define any 3x3 'octagonal' type distance kernel, as described above. Here are the definitions of the pervious interget kernels,

Chebyshev	Chamfer:1,1
Manhattan	Chamfer:1,2
Fractional Octagon	Chamfer:2,3	/2

Fractional Octagon Alturnative

Chamfer:3,4

/3

All these kernals are simple radius 1 kernels. The values give can be regarded as the actual 'distance scaling' values it should be using. Note however that the previous Integer Octagonal kernel requires a 3 number radius 2 Chamfor Kernel to define it. The most well known Chamfer kernel is as radius 2 kernel, 'Chamfer:5,7,11', which generates a very accurate distance, and also generates an integer distance values making it well suited for Q8 users. Traditionally the kernel (chamfor 5,7,11) is of the form...

'5:  -   11   -   11   -
    11    7   5   7    11
     -    5   0   5    -
    11    7   5   7    11
     -   11   -   11   -'

OR multiply the above by 20, to produce the same pixel distance scaling (100) used normally by ImageMagick for distance kernels....

'5:  -   220   -   220   -
    220  140  100  140  220
     -   100   0   100   -
    220  140  100  140  220
     -   220   -   220   -'

Note how the kernel does not actually fill in ALL the kernel distances. That is because those values will get their distances from the other values already provided. that is you don't actually need to fill out the whole 2-diamentional array to fully define a distance kernel, though it is typically done for easier processing. Here is a list of other known Chamfer kernels (only using integer values) that I have found in my research.

Chamfer:3,4	/3
Chamfer:5,7,11	/5
Chamfer:99,141,221	/100
Chamfer:987,1414,2206	/1000
Chamfer:12,17,27,38,43	/12

The kernel highlighted in the above table is the most well known and commonly used Chamfor Distance Kernel. It generates image using only small integer values, as such the large distance gradent images can be stored without loss of precision. It is also very accurite, at least enough for just about every imaginable purpose. As a bonus the distance results do not create recursive decimal places just a single digit fraction when normalized. This is another reason why it is often selected by many image processing packages. The "Chamfer:5,7,11" should be regarded as the default "Chamfor" Distance kernel.

Euclidean (Knights Move) Distance Kernel

The 'Euclidean' kernel is generated using exact floating point distance numbers. But to make this work with non-HDRI versions of ImageMagick requires the use of a fractional diagonal distances. Such as the diagonal which has a value of the square root of 2, a value of about 1.4142 distance units. To allow this to work the distances are scaled by a value of 100 (as in all the above kernels), to produce a fractional percentage distance. Here is the default kernel it generates... Now by using the default radius of 1, while a big improvement on the previous kernels in terms of accuracy, still has some limitations. Basically, it provides a distance in terms of just 45 degree diagonals and orthogonal (X and Y) moves. That is, the distances are somewhat like a 'Knight's Move' in the game of chess. Here is the maximum distance and the 'distance gradient' image that was created using the default 'Euclidean' or 'Knight Move' kernel.

	magick man.gif -threshold 50% +depth \ -morphology Distance Euclidean knight_gradient.png magick identify -format 'Maximum Distance = %[max]' knight_gradient.png magick 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 it also happened to be the same as the 'Manhattan' distance. The actual distance to a pixel is actually the sum of the diagonal distance, plus the orthogonal (axis) distance. That is, not quite a perfect Euclidean distance, but it is the closest to it you can get while using the smallest distance kernel posible (of radius 1).

Here is an magnification of the gradient between the shapes 'legs'. magick 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 that you get in a 'integer' distance kernel. 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, though with points like a compass, rather than flats top and bottom as you get with the previous 'Octagonal' distance kernel. For general distance work (such as 'feathering') this default 'Euclidean' or 'Knights Move' kernel provides a good result. However as you do not get 'integer' distances, you can not use this using a distance scale factor of '1', making it less useful for Q8 versions of ImageMagick.

Larger Euclidean Distance Kernel

By increasing the 'radius' of the generated 'Euclidean' kernel and you produce an even more accurate 'Pythagorean' or true 'Euclidean' distance metric. The larger the radius the more accurate the result, but it will take longer for the morphological 'Distance' method 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 get a much greater loss of speed. See Distance with an Anti-Aliased Shape below for some examples of using very large 'Euclidean' kernels to improve accuracy. Here is a true 'Euclidean' kernel using the recommended radius of 4, which generates a larger 9×9 kernel... 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. Here is its application...

	magick man.gif -threshold 50% +depth \ -morphology Distance Euclidean:4 euclidean_gradient.png magick identify -format 'Maximum Distance = %[max]' euclidean_gradient.png magick 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 in unlikely for you to get more than one 'brightest' pixel in the image, unless the shape is very regular.

Here is an magnification of the gradient between the shapes 'legs'. magick 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.

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. Here is another comparision this time getting the distance away from a single black pixel close to the lower left corner, without any magnification of the pixels. These images clearly shows the lines along which pixels are thought to be closer to the starting pixel than you probably expect, and how the various kernels become smoother as they get more complex. Only the last shows no visible lines of 'closer pixels', but even at radius 4 they are present. For this kernel the lines only appear at a great distance from the source. A radius 7 produces even better results, but at a great cost in speed, though sometimes such accuracy is needed to avoid artifacts in the resulting image. Remember only the first three kernels will produce integer distances, which can be used on a Q8 version of ImageMagick (with appropriate scale adjustment, see the individual kernel description). And it is these that are typically what many image processing packages will use. Calculating distance from a single point will be looked at again later in Constrainted Distance examples below.

Special User defined Distance Kernels

You are not limited to the 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. magick man.gif -threshold 50% +depth \ -morphology Distance '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! magick man.gif -threshold 50% +depth \ -morphology Distance '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 kernel origin setting is probably wrong, or the origin was not a 'zero' value. This is not checked for by the morphology distance function.

Distance with an Anti-Aliased Shape

The Distance method works very well. But the best test of its functionality is to apply the distance function to a circle, and then Shade it so as to highlight even the smallest error that may be generated by the function. You can see from the above that while you do get a 'conical' looking result, it is far from the smooth 'cone'. It is covered by a network of radial ridges starting at the edges. If closely looking at the edge of the shaded cone, you will see that the cone does not have a smooth circular base of the original shape. It is highly 'aliased' or 'stair-cased', and it is these 'steps' that are being reflected by the distance function to form the radial ridges that is seen. The problem is that the distance method has no idea about the small 'grey' anti-aliasing pixels the circle uses around the edge to give it that smooth look. In fact any 'grey' pixel is generally being thought of as a whole pixel rather than the anti-aliased partial edge pixel they represent.

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. magick circle_shape.png -gamma 2 +level 0,100 -white-threshold 99 \ -morphology Distance Euclidean:4 -auto-level \ -shade 135x30 -auto-level +level 10,90% cone_antialiased.png

What was done was to first magick all those grey pixels from a representation of how much of the pixel was inside the circle boundary, to a representation of how far the pixel was from the edge of the circle. As you can see from the result almost all the staircase edge errors have been fixed. The final errors that are visible only occur away from the edge, and become more visible toward center of the 'cone'. They are caused by the iteration of the distance function, every 4 pixel (the size of the euclidean distance kernel) over and over. As such the minor inaccuracies become enhanced as we get further from the edge.

This is typically not a problem in most situations, but you can reduce, or possibly even eliminate even those small errors by using a larger Euclidean kernel, so as to produce a much more accurate and smoother result. However this does take longer to generate. magick circle_shape.png -gamma 2 +level 0,100 -white-threshold 99 \ -morphology Distance Euclidean:7 -auto-level \ -shade 135x30 -auto-level +level 10,90% cone_improved.png

The result is an almost perfect distance function for an anti-aliased or smooth shape. Here is another example, this time using the two User Defined Distance Kernels from the previous section. Without the special handling for anti-alised pixels, the above would not produce such a smooth gradient across the image. As it is we still need to restore the 'shape' of the original shape.

Feathering Shapes using Distance

The above technique can be applied to the Alpha Channel of a shape so as to properly 'feather' the object. For example, here is a 10 pixel 'smoothed' feather around an shaped object. This will preserve ALL edges exactly, unlike the simpler Blurred Feathering technique. 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" operator). As such I extracted the alpha channel so as to handle it as a grey-scale image, before merge it back into the final image. The special distance kernel will do three iterations of a 4 pixel Euclidean Kernel, to generate enough of a distance gradient close to the edge of the shape. The "-level" operator then magick that into a linear gradient form the edge ('0') to 10 pixels ('1000' units) into the shape.. The "-virtual-pixel" setting is also provided to ensure the any shape that touches the edge of the rectangular image container is also thought to be surrounded by transparency. The result of the distance function in this case is a 'linear ramp' or 'bevel' which can produce some sharp looking effects. As such an a small "-sigmoidal-contrast" modification will smooth this transition from transparency to opaque. The higher the strength ('3' in the above) the sharper the feathering will be at the edge. If you like to have the feather 'taper' more smoothly into transparency, replace the '0%' in the above code, with '50%' to place the 'shoulder' of the sigmoidal curve in the middle of the 10 pixel feather. Bitmap Shape FeatheringIf the shape is a bitmap, such as from a GIF image, or a Image Masks, then you can simplify the above feathering operation. For example... The key changes is that you don't have far less pre- and post-processing the distance function you can simply specify a special distance unit using '3!'. Which will generate a 3 pixel linear gradient around the edge of the shape. Another example of this type of feathering (a larger 'linear feather') can be seen in Thumbnails, Soft Edges. You can use "-sigmoidal-contrast" operator in the above to smooth out larger feathers, but be warned that at this time it processes transparency as 'matte' values rather than alpha values. as such a value of '100%' should be used instead of '05' in the previous solution. For bitmap shapes, it may be better to apply a "-blur 1x0.7" to the alpha channel, to smooth it slightly, before applying the previous, more complex distance feather to those results.

---

Conditional or Constrained Morphology

Here we look at techniques where the repeated morphology operations are constrained or limited to a particular area or region of an image. Basically techniques that can be used to ensure that you do not 'overflow' or grow beyond some limit or area of interest. This generally requires a 'mask' image of some kind, and is typically done using a Write Protect Mask, to limit what pixels are updated.

Conditional Dilation

The Dilate Morphology Method as you know will expand a specific shape according to a given kernel neighbourhood. 'Conditional Dilation' is essentually the same thing, but sets a limit as to how far the dilation can spread when repeatedly applied to an image. A Draw Flood-Fill is in one sense the ultimate 'Conditional Dilation'. It will simply fill any orthogonal (Diamond Kernel neighbourhood) that happens to be the same color as the starting point. For example, we can select a single point in one of number of disks, and conditionally dilate (flood fill) until that disk has been completely recolored, seperating it from the other shapes. Similarly you can use the Floodfill Operator to do the same thing but only if the start point also matches an user provided 'conditional color'.

magick disks.gif \ -fill green -floodfill +10+40 white \ -fill blue -floodfill +30+50 white \ cond_dilate_floodfill.gif

In this case the 'green' floodfill 'hit a disk' (and filled it), while the 'blue' flood fill operation, did not match, so no disk was filled. The problem with such 'flood-fill' methods is that you can only dilate from a single user provided point. It is however very fast, and works on the image as a whole. Repeated or iterated Dilate is the same as floodfill but can have multiple starting points, but has no understanding of limits or bounds to the fill operation it provides. To limit its effects we need to provide not only the 'starting points' but also the 'conditional bounds' of the fill. To do this we create a Write Protect Mask (what parts of the image which are write protected). In the above we first used a Erode Method to locate any disk that is larger than a radius of 7 (diameter 7x2+1 => 15 pixels). We then 'Conditionally Dilate' the discovered points by the same amount so as to 'perfectly' restore the object found. Note that 'Conditional Dilatation' is very different to using an Open Method for object restoration. That method would have generated the internal 'diamond' shape of the kernel, rather that the exact shape of the original object. It also will not handle 'odd shaped' or 'off centered' seed points. The iteration number '15' is not critical, but should be large enough to completely restore the object.

Remember it is better to use a small kernel, such as a Diamond or Square with a Iteration Count when performing Basic Morphology Operations than using a much larger kernel, such as a Disk with a large radius. This becomes especially important when doing a Conditional Dialation, as large kernels could in effect 'jump' over gaps that separate multiple objects.

Do not use a '-1' or (near) infinite iteration count with a write mask. IMv7 Morphology currently will not realize that pixels are un-writable, and as such will not abort when it sees no more changes to the image, as it always sees changes, (which never gets written) around the edges of the shape. This will be fixed with IMv7, which provided a major internal re-structure that will let the operator be a little smarter with regards to write protected pixels.

Here is another example of the versitility of using a Write Protect Mask. Find the disks will be hit by a diagonal line across the image. Note the extra masking step (using a Multiply Composition), ensures that only objects the line actually goes though will be 'found'. Without this step, objects that is also close to the line, that is within the kernel radius of the 'seed points' (just touching in the above), would also be 'dilated'. Of course if you are wanting to include 'near objects' then by all means dilate the line (making it wider) with a disk kernel of the appropriate radius, before doing the initial masking step. that will give you more 'near' control than relying on the square kernel radius. In summery a Conditional Dialation could be regarded as a multi-point Draw Flood-Fill, that while slower, can be more versitle in selecting exactly what should be filled, or 'discovered'.

Constrained Distance

The Distance morphology method can be easily used to find how far a point within an object is from an edge. But it can also be used to find how distant each point within the object is from another point. For example, here I discover how far each point is from a single 'seed' point (as the crow flys)... The distance from a point is masked by the shape of the object as these are the only points we are interested in. The problem is that distance gradient above represents a 'as the crow flys' or direct distance to the 'starting point'. Simply masking that gradient by the object does not change that. Unfortunatally this is typically not what an user wants in the way of a "distance from the start point". If the shape represented an island, you would get quite wet if you wanted to take the 'direct route' from one end of this island to the other. What you really want is the distance that is limited to paths 'with-in the object'. That is, you want the distance to be 'constrained' by the object itself, and follows the smallest path possible, inside the object.To do this we can set up a Write Protect Mask so that as the distance gradient is calculated it does not cross (write to) the 'no go' areas or background of the image. The result as you can see is a correct 'distance across image' gradient, that clearly shows the largest distance (white) from the starting point is the other end of the island that is just a 'stones throw' across the gap in the object.
Note that I did not simply use a normal Distance Method but a lower level 'Iterative_Distance' morphology method. The normal Distance Method is a special 2-pass FAST distance method that is applied to the image as a whole. Because of this the write mask will not restrict its actions along a 'row' of pixels, and as such the write mask will have little effect. The result is that 'Distance' will have a tendency to 'jump' over horizontal gaps, regardless of the write mask. That is, the normal Distance Method is not properly 'constrained'. The 'Iterative_Distance' method however works more like a simpler Basic Morphology Method and is only applied incrementally to the local neighbourhood. It is actually more like a gradient form of 'dilate', and is in fact closely related to a True Gray-scale Morphology method. As it processes the image in smaller 'incremental steps' the 'Iterative_Distance' method will be 'constrained' by the write mask. Unfortunatally it is much also much slower. Instead of 2 passes though the image, the above performs 150 passes, as given by the Iteration Count to the morphology method. It is best to try and keep this iterative count as small as possible, but large enough to cover the largest distance that will be found within the image.

Do not use a '-1' or (near) infinite iteration count with a write mask. IMv7 Morphology does not understand that some pixels are un-writable, as as such will not abort when it sees no more changes to the image, as it always sees changes to 'un-writable pixels' around the edges of the shape. This will hopefully be fixed with IMv7, which provides a major internal re-structure that will let the operator be a little smarter, by understanding that some pixels are not writable, and thus avoid calculating, or counting them as having been 'changed'.

Finally you will notice that I used a Distance Kernel that only has a radius of 1, even though such kernels are not as accurate. This is important as a larger kernel could result in the distance gradient jumping across any gap that is smaller than its radius. See Conditional Dilate above. If more accuracy is needed, then you will need to ensure that their is no gaps that is smaller than the Distance Kernel you want to use. That includes gaps due to a sharp bend in the image edge.

---

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 not part of 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 gray-value, 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 HMT Ridges           -threshold 0
   mat.gif -morphology HMT LineEnds         -threshold 0
   mat.gif -morphology HMT Ridges\;LineEnds -threshold 0

   mat.gif -morphology HMT Ridges\;Ridges2  -threshold 0

   mat.gif -morphology TopHat Diamond              -threshold 0

   mat.gif -define 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)

Generally a SKIZ is pruned down to simple areas, or basins, by also eroding
end of line segments, unless they are attached to an image edge.

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. magick man.gif \ -morphology Open Diamond \ -morphology Distance Chebyshev \ -morphology TopHat Diamond \ -auto-level chebyshev_dist_skel.gif

This is basically a morphological skeleton. It only shows the pixels where a maximal 'square' (more commonly known as a 'Maximal Ball') 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 an Euclidean distance measure produces a better skeleton of the shape. magick man.gif \ -morphology Open Diamond \ -morphology Distance 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. magick 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.

Skeleton using Autotrace

Another alternative to skeleton generation, is to use the "AutoTrace" program and its special centerline option. Note that it assumes black on white for its processing due to it involvement with printing and font conversion. For example... Note that the centerline generated is in the form of a smooth curve due to the vector nature of the process. It is also disconnected, with gaps in skeleton loops, and disconnected branches. However I have not looked at how "autotrace" actually generates this skeleton. For other example of using "AutoTrace", see SVG Output Handling, and Raster to Vector Edging.

---