Phone Vision 18 – Erosion and Dilation

23 03 2011

Our exploration of set theory last time was a precursor to discussing dilation and erosion.  Simply put, dilation makes things bigger and erosion makes things smaller.  Seems obvious right?  Let’s see if the mathematicians can muck it up.

Translation

This is not necessarily a fundamental set operation, but it is critical for what we will be doing. Translation can be described as shifting the pixels in the image. We can move it in both the x and y directions and we will represent the amount of movement using a point. To translate the set then, we simply add that point to every element of the set. For instance, using the point (20, 20) the puzzle is moved down 20 pixels and right 20 pixels like this:

image

The light blue area marks the original location.

Dilation

Dilation is an extension of translation from a point to a set of points. If you union the sets created by each translation you end up with dilation.  In the following diagram, the black pixels represent the original puzzle piece.  The light blue halo represents several translations of the original.  Each translation is translucent so I have tried to make the image large enough so you can see the overlap.  Notice how the hole is missing?

image

The set of points that were used to create the translated sets is called the structuring element.  A common structuring element is

{ (-1,-1), (0,-1), (1,-1),(-1,0), (0,0), (1,0),(-1,1), (0,1), (1,1) }

This will expand the image by one pixel in every direction.  If we think about this as a binary image, it might be represented by this:

image

Kinda reminds me of one of our convolution kernels.  Structuring elements are often called “probes”.  This one is centered at (0,0).

Using the PixelSet we created last time, the code is pretty straightforward.

public void Dilate(PixelSet structuringElem)

{

    PixelSet dilatedSet = new PixelSet();

    foreach(int translateY in structuringElem._pixels.Keys)

    {

        foreach(int translateX in structuringElem._pixels[translateY])

        {

            PixelSet translatedSet = new PixelSet();

            foreach (int y in _pixels.Keys)

            {

                foreach(int x in _pixels[y])

                {

                    translatedSet.Add(x + translateX, y + translateY);

                }

            }

            dilatedSet.Union(translatedSet);

        }

    }

    _pixels = new Dictionary<int,List<int>>(dilatedSet._pixels);

}

Here is the puzzle piece dilated by one pixel in all directions.  The hole is gone.

image

Erosion

Erosion is similar to dilation except that our translation is subtraction instead of addition and we are finding the intersection instead of the union.  Here is an image that has been eroded by 10 pixels in all directions.  The light blue area is the original puzzle.

 

image

 

public void Erode(PixelSet structuringElem)

{

    PixelSet erodedSet = new PixelSet(this);

    foreach (int translateY in structuringElem._pixels.Keys)

    {

        foreach (int translateX in structuringElem._pixels[translateY])

        {

            PixelSet translatedSet = new PixelSet();

            foreach (int y in _pixels.Keys)

            {

                foreach (int x in _pixels[y])

                {

                    translatedSet.Add(x – translateX, y – translateY);

                }

            }

            erodedSet.Intersect(translatedSet);

        }

    }

    _pixels = new Dictionary<int,List<int>>(erodedSet._pixels);

}

 

Here is the puzzle eroded by one pixel in all directions.  That hole is a little bigger.

image

Summary

Like I said at the beginning, dilation makes things bigger and erosion makes things smaller.  Interestingly, erosion is simply the dilation of the background and dilation is the erosion of the background.

Download Code

http://cid-88e82fb27d609ced.office.live.com/embedicon.aspx/Blog%20Files/PhoneVision/PhoneVision%2018%20-%20Erosion%20and%20Dilation.zip

Up Next: Opening and Closing


Actions

Information

3 responses

23 03 2011
Phone Vision 17–Sets «

[…] Up Next: Erosion and Dilation […]

20 04 2012
Ricardo

Hello very good article , but how i can apply this Algorithms to Images? For example i select some image and i want to apply this Functions is possible?

Thanks :).

30 04 2012
Rich

Actually, these techniques were meant to illustrate the idea, but they are probably way too slow for actual image processing.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s




%d bloggers like this: