MorphoDiapo

This intends to be a visual tour of Mathematical Morphology's basics and especially how it can be applied to images and help in analyzing objects' shapes.

Click on a session's snapshot to look at its slides.

Feel free to read the printable version.

Disclaimer

For the sake of simplicity some shortcuts have been taken. Despite many efforts to avoid any serious mistakes some might have slept through anyway. Please feel free to send your comments via the dedicated form

Creative
      Commons License
MorphoDiapo by Thibauld Nion is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License. Permissions beyond the scope of this license may be requested via the contact form.

Context and motivation

These sessions started as a series of short seminars to present mathematical morphology to researchers and engineers working on text recognition and document understanding at A2iA, where the author was working at that time.

References

Most of what is explained here has been learned "from the sources" so to say, when the author was studying Mathematical Morphology at Mines ParisTech.

The session by session progression is partly reminiscent of Serra's Lectures on Mathematical Morphology

Some other general resources worth looking at:


Last updated: May the 11th, 2012

Introduction

slideshow for the introduction <<

Transcript

Move the mouse over here to see the transcript

Slide#1-2

We will consider here the applications of mathematical morphology to the field of image processing.

Our basic material will thus be a numerical image, which is nothing else than an array of values. For 2D images, each cell of the array is called a pixel.

Slide#3

Image processing tasks typically enter in the following categories:

  • filtering where an image is modified, for instance to remove noise or simplify the shapes present in the image
  • measures to try to summarize some features of the images in a few numbers
  • transform where an image is represented in various different "spaces" (e.g. Fourier and Hough transforms)
  • detection where the aim is to localize some objects in a picture either by finding their center point, bounding box or labeling their pixel (the later case is usually referred to as 'segmentation').

Slide#4

Certainly the biggest set of tools for image processing is inspired by calculus and function analysis.

Ultimately they are inspired by physics (ex: heat diffusion equation used to blur image). To a certain extent each pixel of an image can be associated to a cell of the finite element grids used by in material engineering computations.

A big part of these methods can be translated as linear algebra operators.

Slide#5

Mathematical morphology on the contrary defines operators that usually have very few in common with linear algebra.

As its name suggests it concerns the processing of shapes. A big part of mathematical morphology operators are designed to detect, remove or smooth objects. With this frame of mind even natural images are often described as collections of sometimes overlapping objects.

This discipline has strong ties to geometry and probability but historically its roots are deep in geology ! So much so that when dealing with gray-level images, morphological operators are described in terms of landscape evolutions.

Slide#6

At the theoretical roots of mathematical morphology lays the concepts of sets and their statistical properties.

Sets can be imagined as black and white images, with the white pixels indicating the inside of the set (the "object") and the black ones indicating the outside of the set (the "background").

A typical way to define the statistical properties of a set is to chose a (usually smaller) set as a "probe" and to measure the probability for this probe to intersect the object when it "falls" on the image. Another set of typical properties relates to the probability of the probe to be fully included in the object.

Most of this introduction to mathematical morphology will deal with binary images to remain at a the level where basic operations can be easily explained in terms of sets and objects. However, please keep in mind that these operators can be adapted to gray-level and color images.

Slide#7-8-9

As a first taste of those statistical measures, we can consider an image representing a collection of objects and wonder how it will be modified by keeping only the objects in which a "probe" can fit.

In mathematical morphology we design such probes as "structuring element". If we take a little rectangle as structuring element we can see that we can already remove the smaller objects.

By making it bigger, bigger object objects are removed, obviously. And by making it even bigger along the horizontal axis, we realize that objects that are not large enough in this direction are removed, which marks the difference of such a procedure with respect to eliminating objects based on their sole area.

Slide#10

Another illustration of the statistical measure is statistics one can do by measuring the number (and size !) of intersections of the objects with horizontal lines.

For binary images, pushing this concept to the point where we collect all such intersections for all the horizontal lines that make up the image, we get a full description of this image. No wonder that this kind of description (called Run-length encoding, RLE) is the base of a commonly used compression algorithm (ex. in png images).

The field of stereology, strongly tied to mathematical morphology, make it possible to estimate area and volume of objects by counting their intersections with certain lines or surfaces.

Slide#11-12

To wrap up this introduction with some historical perspectives, let's talk a little about the man that can be considered as the ancestor of mathematical morphology (among other things).

Buffon, a french naturalist, asked in 1733 about the chances for a needle falling on a wooden floor to cross two of the floor's strips.

Slide#13

Quite some time after Buffon, the field of geometric probability generated some more interest at the end of the 19th century, especially with Crofton's formula that (according Wikipedia) makes it possible to estimate the length of a curve to the expected number of times a "random" line intersects it.

We can then jump directly to the 20th century, with Choquet's efforts to formalize the description of sets by their probabilistic properties such as the ones we discussed before.

And this eventually leads us to the foundation of mathematical morphology by the combined effort of George Matheron and Jean Serra. The first one motivated by finding better statistical methods for the analysis of geology-related samples (petrographic samples, bores etc) and the second one motivated by the generalization of such tools to image processing.

Complements

References

  1. Wikipedia on Buffon's needle
  2. Geometric probability applications through historical excursion by Hyksova
  3. The birth of Mathematical Morphology by Matheron and Serra, ISMM 2000.
  4. "Lena as a grid" image from methodart
  5. Monument valley photo from PDPhoto.org
  6. Human nerve cells pictures from HIPR2's website
  7. Shape sorter image by Ella's dad (License CC-By)
  8. Portrait of Georges-Louis Leclerc, Comte de Buffon from Wikimedia Commons.

Erosion and Dilation

slideshow for the erosion and dilation operators <<

Transcript

Move the mouse over here to see the transcript

Slide#1

This presentation will deal with what are probably at the same time the most elementary and the most famous operators defined by Mathematical Morphology.

Erosion and Dilation are indeed very close to the statistical measures used to characterize sets and they are also the building blocks for most of the other morphological operators.

Slide#2

In the "introduction" session we talk about two ways to probe the shape of objects shown on a binary image.

Using a structuring element we can ask whether objects can contain this element or ask for the probability that this element intersects any objects, when "falling" on the image.

With this in mind, we're only a few steps away from defining the dilation and erosion operators.

Slide#3

Let's talk about the "probe" or "structuring element". In the following, we will consider it to be a set (so that it can be represented by a binary image) with the added property to have a "center".

This center might be placed just about anywhere but it is commonly chosen inside the structuring element (so that the center is usually part of this set, even if it's not compulsory). The main use for this center point is that it will help define the location of the structuring element when it "falls on" or "move over" an image: the pixel where the structuring element is located, is in fact the pixel whose position is the same as the structuring element's center.

We won't go very deep into the theoretical foundation, but to correctly understand (and implement !) morphological operations, it is imperative to understand what the symetrized of a structuring element is: the symetrized of the structuring element B is obtained by central symmetry around its center (if you consider its center as the origin of x and y axes, it corresponds to having symetrized(B) = {(-x,-y) for (x,y) in B})

The most commonly used structuring elements are convex (it helps with some of their theoretical properties) and with a center placed so that they are equal to their own symetrized. Typically, your everyday structuring element looks like a square, a segment, a rectangle, a hexagon or a disc.

Slide#4-5

Let's now define the dilation by a structuring element B.

For that we consider a binary image representing a set A (white pixels) on a black background, and we ask for all the points such that, once B's center is set to any of those points, B intersects A. Setting the color of all those point to white draws the dilated of A by B.

Slide#6

By actually trying to do this by hand it appears that the operation sort of "thickens" the set A, but it is important to note that it also modifies the shape of its border (it is not just an homothetic transformation).

By dilating an essentially rounded set A by a square structuring element, we can see that some "flat zones" appear on the dilated's boundary, and some sharp angles might appear too, in places where the set had concavities.

Slide#7

The dilation operation can actually be expressed in terms of an older operation called the Minkowski addition.

Dilating a set A by a structuring element B is equivalent to computing the Minkowski addition of A by the symetrized of B.

The dilation operation is usually noted with the Greek letter delta.

Slide#8-9

Let's now define the erosion by a structuring element B.

For that we consider the same binary image representing a set A (white pixels) on a black background, and we ask for all the points such that, once B's center is set to any of those points, B is still fully contained in A. Setting the color of all those point to white draws the eroded of A by B.

Slide#10

By actually trying to do this by hand it appears that the operation sort of reduces the set A, but it is important to note that it also modifies the shape of its border (it is not just an homothetic transformation).

By eroding an essentially rounded set A by a square structuring element, we can see that some "flat zones" appear on the eroded's boundary, and some sharp angles might appear too, in places where the set's boundary had convex "bumps".

Slide#11

The erosion operation can actually be expressed in terms of an older operation called the Minkowski subtraction.

Eroding a set A by a structuring element B is equivalent to computing the Minkowski subtraction of A by the symetrized of B.

The erosion operation is usually noted with the greek letter epsilon.

Slide#12

Let's have a quick look at some of the main mathematical properties that are common to erosion and dilation.

Both are increasing operations, meaning that they conserve the ordering (by inclusion) of sets.

When B and K are convex structuring elements, the erosion have the interesting property that the eroded (resp. dilated) by B of a set that is itself the eroded by K (resp. dilated) of an initial set X can be obtained by eroding (resp. dilating) X by a structuring element that is the eroded (resp. dilated) of K by B.

This may look a little complicated with this phrasing, but it is a very important property. For instance, it makes it possible to get the eroded of a set by a rectangle by applying an erosion by an horizontal segment and then by applying on this first result an erosion by a vertical segment (considering that they are really efficient algorithm to compute erosion and dilation be segments, this is a well known optimization trick).

If we want to erode a set by a square of size 2.s, the same property makes it possible to take its eroded by a square of size s and to erode it again by the same square of size s. This is quite useful when an algorithm requires to compute the eroded by structuring element of varying sizes, since it makes it possible to reuse intermediate results.

Slide#13-18

Its is interesting to observe the effect of the dilation and erosion on more complex shapes, like for instance the one we find on text.

We can quickly see that eroding text with a horizontal segment, tends to keep only the horizontal parts of the letters and ends with removing all text (because letters are essentially thin objects).

On the other hand, dilating the same text will tend to make letters letters and then words connects together up to the point where each line become a thick white horizontal band. A trick that is quite useful in document layout analysis and very close to what is called the smearing algorithm in this field.

Slide#19

Erosion and Dilation are quite frequently used as is because despite their somehow crude behavior they are quite efficient to remove small pixel size noise or to perform coarse image simplifications.

They can also be used to define a morphological reinterpretation of distance, allowing to compute inner and outer distances of a set.

They are also used to perform measure for the characterization of textures and also simulations (see reference#1).

Last but certainly not least, they are the building blocks of more complex morphological operators, some of which we might describe in the next sessions.

Complements

Puzzle

You think you've got it all? Try out this small puzzle !

Minkowski addition and dilation

Get some more intuition about the link between Minkowski addition and the dilation operations with a graphical summary.

References

  1. Prediction and simulation of Malaysian forest fires by random spread by Serra et al.
  2. Wikipedia on Minkowski addition

Closing and Opening

slideshow for the closing and opening operators <<

Transcript

Move the mouse over here to see the transcript

Slide#2

In the continuity of the erosion and dilation operators, we're still trying to play with the shapes of the objects present in an image.

The basic concept remain the tests for inclusion and intersection between the image's objects and a given probe, the structuring element.

Slide#3-4

The new operations we will see in this session, emerge from the following question: considering that dilation and erosion are dual operations and seem to work in "opposite ways", what happens when we apply one of them on the result of the other ? Do we get back the original image ?

The answer to this last question is unfortunately *no* in the general case, and this motivated researchers to study in what cases this is true, and to search if there was an interesting trick to make the erosion and dilation operations invertible.

Slide#5-8

When we consider the erosion of a set, some interesting properties arises (some of which have already be pointed at in previous sessions):

  • the eroded of a set is always included in the set
  • the erosion wipes out (among other things) the features so small that the structuring element can't fit in them and thus if we take the original image and add it such small feature, in many cases the erosion of this new image will the same as the erosion of the original.

This last observation tells us that the eroded of a set has actually many "inverted" so that it is not possible to correctly define an inverse for this operation.

However all inverses share the property of being greater (in the sense of inclusion) that the eroded.

This leads us to the definition of a new operator: the opening of a set X is the smallest inverse of its eroded.

By definition this opening will be included in the original set, but since its erosion must be the same, it won't be as "trimmed down" as the erosion itself.

Slide#9

The best thing about the opening is that it has an intuitive mathematical definition.

The opening of a set X by the structuring element B is the area covered by B when it moves inside X without ever overlapping the background.

And the other best thing is that it can be obtained algorithmically by eroding the set X by B, and then dilating the result by the symmetrized of B.

Note: the using the symmetrized of B is essential for this definition to be true in the general case (to get a feeling of why, see Why the symetrized switch ?), but, obviously, this has no effect if B is its own symetrized like a square, a circle or a segment with the center set at the origin.

The resulting image of the opening of a set X, is not so much a reduced version of the original image like in the case of the erosion (even if this remains true) but a simplified version of the original, where all the features smaller than the structuring element have been cut-out while the larger ones where mostly kept as-is.

However it is important to notice that the structuring element will influence the shape of the resulting objects' boundaries.

For instance, with a square structuring element, the rounded borders of the original image, will 'tend to' look more like straight lines in the opening.

Conversely, with a round structuring element the straight part of the original object's boundaries will 'tend to' be rounded in the opening.

Another well known action of the opening it to be able to disconnect objects that were in contact in the original image.

Slide#10-11

Similar observation can me made about the dilation that has many inverted, just like the erosion, except that, in this case the inverse are all contained in their common dilated.

By analogy with the opening operation, this suggests to define closing of a set as the largest (in the sense of the inclusion) inverse of its dilated.

Slide#12

The closing's intuitive definition for a set X with a structuring element B, is to be the area not covered by B when it moves outside X without ever overlapping it.

It can also be built by applying a dilation by B and then an erosion of the result by the symmetrized of B.

The same remarks apply as in the opening's case and the structuring element will also influence the shape of the resulting objects.

But, contrary to the opening, it is known for connecting objects that were not in contact in the original image.

Slide#13

The usual notation for the closing is to be represented with the Greek letter phi while the opening is represented with the Greek letter gamma.

Both operation are increasing, meaning that they conserve the inclusion relations of the original images.

Interestingly both are idempotent (this is understandable via their initial definition as the smallest or largest inverse of erosion or dilation).

Eventually, and as is expected from their definition, the closing is extensive, meaning that the closing of a set X contains ("is larger than") the set X itself. And the opening is anti-extensive, meaning that the opening of a set X is contained ("is smaller than") by the set X itself.

Slide#14-18

If we look now at how the closing operation modifies a paragraph of text, we can see that depending on the size of the square that is used of as a structuring element:

  • when the square's size is close to the letters size the letters are simplified (their holes are closed, and their rounded parts tend to look flatter) and since the inter-word letter space is smaller than the letters size, all letters are connected so that words start to look like squary blobs.
  • taking a slightly larger square will increase the "word as squary blobs" effect and start to connect the words with each other.
  • a big enough structuring element connects the lines via the tip and bottom of the tallest letters of each line
  • an even bigger structuring element will make a squary blob out of the full paragraph, but it is interesting to see that the blob's boundary, even if much simpler still matches the original paragraph's boundary.

Of course if there were other paragraphs around, a big enough structuring element would connect the paragraphs together.

Slide#19

Closing and opening operations have many applications and are widely used morphological operators.

Their ability to remove small features will keeping the larger ones makes them an interesting alternative to more classical operators like Gaussian convolution with the added benefice that they keep strong contours, and the disadvantage that the structuring element influences this contours as we previously saw.

The same property makes them interesting when an image needs to be simplified, for instance by removing an object's holes or the irregularities of an object's contour.

It can be (and actually has been) also used to propose different definitions for the connexion.

The ability of the opening to remove small features can be used to remove small objects in order to select only the larger ones.

Last but not least it is the main building block for a family of measures that make it possible to characterize the shapes present in an image. But we'll talk more about that in the next sessions.

Complements

Puzzle

You think you've got it all? Try out this small puzzle !

Why the symetrized switch ?

Get some more intuition about the erosion and dilation used for an opening (or a closing) are not made with the same structuring element, but with the structuring element and its symmetrized, with the following sketch.

Pixels and Probabilities

slideshow about pixels and probabilities <<

Transcript

Move the mouse over here to see the transcript

Slide#2

Going back to the historical lineage of mathematical morphology, we will see in this section how to compute the answer close to Buffon's question about the probability for a needle to cross two stripes, when dropped on his wooden floor.

Slide#3-7

Let's consider first a much simpler question: what's the probability for an elementary object (assimilating its size and shape an image's pixel) to fall on the white area of a black and white image ?

Assuming that this elementary object has no reason to fall frequently on a given place of the image that on any other place, the answer is actually very simple to compute for any black and white image: this is the number of white pixels divided by the total number of pixels in the image. Another way to say it is to consider the area of the white surface and divide it by the area of the whole image.

Slide#8

Now is a good time to remember the definition of the erosion as the region of the image where the center of the structuring element can be set and the structuring element still fits in the white area of the original image.

The result of this operation on a black and white image is another black and white image where only the pixels verifying the above condition are painted white.

Slide#9

It follows that we can now answer the question: what is the probability for a structuring element B, falling on the image, to be included in the white area of this image ?

We just have to measure the white area that remains after eroding the original image by B, and divide it by the total area of the image.

Slide#10

The same reasoning can be used for dilation whose effect on a black and white image is to paint in white the region where the structuring element's center can be set so that the structuring element itself intersects the white area of the original image.

Slide#11

We're now able to answer the question: what is the probability for a structuring element B, falling on the image, to intersect the white area of this image?

The procedures indeed identical to the one used to answer the "inclusion" question except that we replace the erosion by the dilation.

Remember that a structuring element B is just a "shape" and could represent just about any object, and that the same applies to the white area of the original image, that can represent any kind of object.

Even if Buffon's question is still more complicated to answer, you can see that we're already able to deal with questions of the same kind.

Slide#12-15

We will now move away from Buffon's needle and look at different uses for the probability measures we've just defined.

The most striking use is to consider how these measures evolve when when change the structuring element and especially when, having fixed its shape, we vary the size of the structuring element.

The "erosion curve" is a typical name given to the graph obtained by plotting the probability measures for s.e. of varying shapes.

If applied on a synthetic image made of two populations of squares (small squares and medium squares) and with a square as structuring element:

  • the curve starts at a point corresponding to the ration of the white area by the whole image's surface when the square is of the same elementary size as pixel
  • then due to erosions with greater and greater squares, the curve will decrease
  • and when the s.e. reaches the size of the medium squares present on the image, the curve suddenly drops to 0.

With this simple example, it is clear that the erosion curve can help analyze the size of objects present in an image.

Slide#16

Actually the erosion curve is more about shape (including size) that just "size" and if we look for the the same measure on a different image made only of segments with virtually no thickness, but different sizes anyway, the curve will stick to 0 almost everywhere.

Slide#17

If on the same image of segments we compute the erosion curve by choosing a more adapted structuring element, typically segments of varying length, then we get a curve whose main features give us info about the lengths of the segments presents in the image.

Slide#18

We will now consider erosion curves with yet another structuring element and see how it makes it possible to redefine a well known signal-processing measure.

The new structuring element is made of two points, separated by a distance h. The erosion of an object by this s.e. will get us the region of space where this s.e. can be centered and both points fit inside the object.

Slide#19-21

The erosion curve is obtained by varying the distance between the two points.

For a given distance h between the two points, the probability that the two points fall inside the original object, can be expressed as the probability for a point to fall in the intersection between this object and another version of this object shifted by -h along the same direction define by the two points of the structuring element.

Slide#22

Pushing the calculations a little further gets us to a formula that look very much like the formula of the auto-covariance function.

This specific erosion curve is called the Geometric Covariogram.

And it is indeed related to the auto-covariance and more precisely to an auto-covariance computed without making sure the signal have 0 means (ie without "centering" the signals). So much so that for a special mathematical model for textures and materials called the stationary random process, both functions are equal up to a constant.

Slide#23

Application wise it should be clear from the previous explanations that the erosion and dilation curves are interesting measures to analyze the shapes of objects on images.

To be more specific we can also point at a successful use of these curve for texture classification by G. Fricout.

Complements

References

Measuring Shapes

slideshow about shape measurements <<

Transcript

Move the mouse over here to see the transcript

Slide#2

We will start by enumerating a few interesting properties of the geometric covariogram presented in previous sessions, and see how it can help in analyzing the patterns present in an image.

Most of these properties will of course be old news with those familiar with the covariance function, since the geometric covariogram is closely related to it.

Slide#3

Most of the following properties have been studied for specific mathematical objects called RACS (RAndom Closed Sets). RACS is a mathematical model that allows to describe real-world materials and textures whose constitution doesn't obey any simple equation (contrary to what would be the case for periodical tilings for instance).

We won't describe RACS in further details, but this concept is important enough to be pointed at here. However, in our illustration we will consider the realisation of a specific RACS which we arbitrarily build as a set of small rectangles with no large scale order, but where the rectangles are gathers in medium sized clusters, each of those clusters being made of 4 rectangles each at the corner of an invisible rectangle, so that the clusters themselves have a rectangle-like "shape" (more specifically they have a rectangular convex hull).

Slide#4

Let's now compute the geometric covariogram with two horizontally aligned points, for the image we've just described.

The geometric covariogram depends on h, the distance between the two points that we take as structuring elements.

And for h=0 the value of the geometric covariogram is quite simply the probability for a single point to fall on the white surface, which here is equal to the total area of all the small rectangles that made up the clusters.

Slide#5

If h grows up to the width of the small rectangles, the probability of inclusion of our two points will decrease.

And if the separation between the small rectangles is big enough, this probability will be 0 when h is just bigger than the rectangles' width.

Slide#6

The probability will stick to zero until h is big enough to allow for one of the points to be in a rectangle while the other is in another rectangle.

On our specific images, this happens when h if of the width separating two rectangles of a same cluster.

Slide#7

The probability will then raise from 0. And for our specific image, it will find a maximum when h is equal to the sum of the width of a rectangle and the width separating two rectangles, because then the bi-point used as a probe by the geometric covariogram will fit in two rectangles at a time.

Slide#8

With a little bigger h, this is not true anymore an the bi-point will find it less an less places where it can fit.

Still in our specific image, the probability will decrease and eventually reach 0 when h is equal to the sum of the width separating two small rectangles of the same cluster and twice the width of those rectangles.

Slide#9

If h continues to grow, interesting things happens.

First of all, from the point of view of the measurement practitioner, it is crucial to remember that the measurements are made on an image whose size, and thus whose contained information, is finite.

Trying to investigate patterns whose typical size is of the same order as the image's size is a sure way to measure nonsense because you simply won't have enough representative data. In this matter, Shannon's sampling theorem is still a solid safeguard and when measuring the geometric covariogram on an image, you should consider with much suspicion (and even better not consider at all) whatever value you get for h greater or equal than the half of the image's width.

However let's assume of a moment that our illustration image covers a much bigger domain that what is actually does on the slides (and thus assuming that we can see much more clusters of those white rectangles).

Then we would find out that the geometric covariogram increases and eventually reaches a ceiling. This ceiling would typically be equal to the square of the first point of the covariogram (ie the square of the probability for a single point to fall inside a white rectangle), typically because for h big enough with respect to the patterns we described in our image, there is no dependence anymore between rectangles over this long distance, and thus the fact that one of the point falls in the rectangle doesn't tell us anything about whether the other point will also fall in a rectangle or not. The distance where this phenomena appears is usually called the "range".

Before having a look at another kind of measurement, it is important to note that all the observations we made to explain the step by step construction of the geometric covariogram's curve, are in practice reversed: you will typically measure the covariogram and look in the image to match the remarkable points of the curve with patterns of corresponding size.

Slide#10-11

As we saw, the geometric covariogram is a powerful tool to investigate the scales of the various patterns present in an image. Its curves features are related to the scales along a given direction, and if we measures the covariogram in all direction, we could somehow investigate a little more that the scales but also get some clues about shapes.

We will now talk about another kind of tools that gives us a direct measure of shapes' preponderance in an image.

This tool, called the granulometries is inspired by measurement that are typically made by mining companies to analyze the size of extracted rocks and the amount of material (e.g. mass) for each size population (e.g. for for calibration).

Granulometries have the added benefit to have a rather intuitive interpretation as a mathematical modeling of sieves !

Slide#12-15

While the geometric covariogram was built upon the erosion operation, the granulometries are based on the opening operations.

To measure the granulometry of an image, one must first chose the shape of the structuring element to be used.

Then the opening of the original image is computed by the structuring element, and the surface of the remaining white area is measured.

After that another structuring element is considered, typically with the same shape as the previous one but bigger (e.g. an homothetic of the initial s.e.), the opening of the original image is performed and the remaining white area is measured to get a second point of the granulometry.

The process continues with bigger and bigger structuring elements, to build the full curve of the granulometry.

Slide#16-18

By the property of the opening this process removes the objects that are smaller that the s.e. being used while keeping a fair part (depending on the object and the s.e.'s shapes) of the bigger objects.

To a certain extent what remains in the image after an opening by a given s.e. is what would remain in a sieve if the image's objects were filtered through it and if this sieve's holes had the shape of the structuring element.

Slide#19-20

The granulometric curve for a black and white image shows the number of pixels that are still painted white after each opening step.

It must be interpreted with care since this is a number of pixels and not the number of objects itself and there is usually no simple a priori relation between the number of objects (each possibility having any shape) and the number of white pixels.

Interestingly it is often easier to "visualize" the presence of different shapes through the derivative of the granulometry, that, quite logically, shows the amount of material removed after each opening.

Slide#21-23

In the literature we find several uses for the granulometries, as shape signatures for simple objects like disks, as classifiers for more complex objects like handwritten characters, and even as signature for a full document's image where the granulometry synthesizes information about the sizes of the letters, words, lines, paragraphs and paragraph clusters.

Slide#24

Throughout this session and the previous one we saw several important morphological measures: the erosion and dilation curve, the geometric curve as a specific case of erosion curve and also as a bridge to more classical digital signal processing technique and the granulometries.

Each time it was made clear that these measures helped in getting numbers related to the objects' shape.

In practice, they are indeed useful either to estimate some patterns and objects' sizes, typically in biology, material science and physics in general.

As we saw they are also used for image classification.

And last but not least, they are of great use for people who models random media (like materials or biological tissue) to help estimate a model's parameters or its validity.

Complements

References

A bird's eye view to the rest...

slideshow about other morphological techniques <<

Transcript

Move the mouse over here to see the transcript

Since most of the previous session covered on a selection of the basics of mathematical morphology with a final focus on measurements, the aim of this last session is to offer a glimpse at other tools and techniques that sprang from the field of mathematical morphology.

There won't, however, be many details given for each item and the interested reader should look elsewhere (starting with the referenced material from here) to learn more.

Slide#0

The hit or miss transform is a sister operation to the erosion and dilation operation, were the structuring element is composed of points that are expected to belong to the objects and points that are expected to belong to the background.

This is used to explore some topological features like corners and branching points and also to compute object's skeletons.

Slide#1-3

So far we've only talked about binary (black and white) images but all the operators and measures we saw are also defined for gray-scale images.

A simple way to bridge the gap between a gray-scale image (where objects' boundaries are usually fuzzy, provided that they even exists !) to the concept of an image as a collection of objects is to consider each level set separately, apply the desired operation on each, and then pile them up again to get a new gray-scale image.

For operation like erosion and dilation another way to implement them is to consider the structuring element much like the kernel of a convolution and walk it throughout the image. During an erosion, each pixel where the s.e. is centered, is given the minimum value of all pixels collected in its neighborhood (the neighborhood being defined at all the points superimposed with the structuring element). During a dilation, the same is done expect that the maximum is used.

Opening and closing are also defined for gray-scale image where their effect is similar to the binary case: they simplify the image. The closing also ensure that all pixels have a greater or equal value to their counterparts in the original image, and the opening ensures they have lower or equal values. This gives way to the possibility to remove the small pikes or with a little more effort to make them stand out.

Slide#4

In previous sessions we saw that in most cases the structuring element tended to influence the shape of a filtered image. For instance opening the image of a square with a small disc will be keep the square but soften its corners.

To workaround this issue a simple extension to the dilation operation as devised which consist of applying a standard dilation and intersecting its result (or taking the minimum, for gray-scale images) with the original image. This additional steps makes sure that a dilation doesn't "overflow" the original object's shape. This technique is called the geodesic dilation.

If iterated enough times, the geodesic dilation will tend to fill an object's inside space without ever overflowing it. This property makes it possible to define the opening by reconstruction that eliminates small objects smaller than the s.e. but perfectly reconstructs bigger objects (the dilation of the classical opening is replaced by a geodesic dilation repeated until idempotence).

Interestingly the same technique of iterating the geodesic dilation makes it possible to reconstruct objects starting with a single pixel, and thus opens the way to implementing object selection algorithm with any kind of destructive filtering so long as at least one pixel of each selected object is kept.

Slide#5

Mathematical morphology provides several advanced algorithms for object detection and segmentation.

The most famous one is the watershed transform that considers a gray-scale image as a landscape with valleys and mountains and reproduces the natural phenomenon of watershed according to which the way water falls and runs along the mountains' sides defines separated catchment basins that tend to merge at the same time as the water streams merge into bigger and bigger rivers until they reach the seas.

The watershed transform matches this concept of catchment basins with objects contours. Object contours being somehow ill defined on gray-scale images, it is sometimes rather difficult to get the desired results from the watershed transform. It is however at the core of numerous segmentation algorithms and the idea of considering a gray-scale image as a natural landscape is fundamental in many morphological operations.

Slide#6

Switching back to the domain of measurements which was one of the root concerns that lead to the inception of Mathematical Morphology.

A great body of work from G. Matheron was to devise a workable statistical measure that would make it possible to analyze geological phenomena that occur on very large scales and doesn't comply with the traditional hypothesis of stationarity.

This lead to the definition of a new measure called the variogram used for large scale estimations the ground's content (either related to its layered structure, the presence of reservoirs or its mineral composition). And eventually this founded the domain of geostatistics that while sharing the same root as most of the image processing techniques we talked about, is now pretty much living its own separate life in academics and industry.

Slide#7

After talking about operations to filter and analyze image, it is high time to see that mathematical morphology also offers a nice frame for image simulations.

Studying the concept of RACS (RAndom Closed Set) with the help of other probabilistic like point processed and the recycling of the structuring element as an "elementary grain" makes it possible to design models for many materials that have a granular composition.

The field of random media modeling has actually extended pretty far from the purely granular materials, finding applications for the simulation of fiber-based materials (eg paper) or biological tissue.

These simulations require the measures we talked about (covariogram and granulometries) in order to fit the parameters of the underlying models, and their results is also of great uses as a support for physical numerical simulations.

Slide#8

This is the end of this "tourist guide" through mathematical morphology and hopefully the courageous reader now has a good feeling about what it's is all about.

Don't forget, however, to check the references linked from here, as most of the concepts presented here, though fundamental, are also rather old and researchers have been working on the expansion of Mathematical Morphology since the 70's.

Complements

References