Phone Vision 17–Sets

16 03 2011

Last time we were able to get a pretty decent binary image.  The question is, what do we do with it?  Before we can answer that, we need to make sure you’ve got a basic understanding of set theory.

Sets

In a binary image we can think of the objects of interest as a set of points.  Here is our binary image from last time:

image

I am going to focus on just the top puzzle piece so let’s extract it.  (The code for extracting this is not important for this lesson, but it is included in the code as GetPuzzleImage).

image

We are going to be working with this image for a while.  In this case, the black pixels will represent members of our set.

Universe

The universe is the set of all possibilities.  In the case of image processing this is typically the set of all of the pixels.  I have seen this referred to as E2 (for 2-dimensional Euclidean space).  In our case, the universe is…

image

As expected, the set of every possibility is all black.  This is important some operations rely on this set.

Empty Set

The empty set is, well, empty.

image

Since the boundary for our image is not a specified size, this is just an empty image. If the universe was a specified size then the empty set would often be represented by a completely white image.

Complement

The complement is everything in the universe that is not in the set.  The complement of our puzzle piece:

image

The puzzle piece is now a hole in the black image.

Union (⋃)

The union is the set of all elements in either of two sets.  If you have been playing along, this is very similar to the | (binary OR) operation mentioned in lesson three. Below we union the puzzle set with the set of its complement.  The output is the universe.

image

image

image

Intersection (⋂)

Finally, the intersection is the set of all shared members of two sets.  Below we intersect the puzzle set with its complement.  This is similar to the & (binary AND) operations mentioned way back in lesson 2.  Since the complement of a set  doesn’t share any elements with the original set the output is going to be the empty set.

imageimageimage

Pixel Set

In order to demonstrate these concepts (and a few in the future) I created a class called PixelSet that behaves similar to a mathematical set. 

Caution: This set is not optimized for use in actual applications.  You’ve been warned.

Elements

The elements of the set are represented by a Dictionary.

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

The key is the y-value for the pixel and the List<int> represents all x-values in that row.

 

Add

 

public void Add(int x, int y)

{

    List<int> columns = new List<int>();

    if (!_pixels.ContainsKey(y))

    {

        _pixels.Add(y, columns);

    }

    else

    {

        columns = _pixels[y];

    }

 

    if (!columns.Contains(x))

    {

        columns.Add(x);

    }

}

 

The add function is a little tricky because if the row (y-value) doesn’t have a representative in the set yet then we need to create a new list to contain them. If it does, then we need to use the existing list.

 

Remove

 

public void Remove(int x, int y)

{

    if (_pixels.ContainsKey(y))

    {

        if (_pixels[y].Contains(x))

        {

            _pixels[y].Remove(x);

            if (_pixels[y].Count == 0)

            {

                _pixels.Remove(y);

            }

        }

    }

}

 

Remove is included for completeness, but I’m not calling it from any location in the code.

 

Union

 

public void Union(PixelSet otherSet)

{

    foreach (int key in otherSet._pixels.Keys)

    {

        foreach (int col in otherSet._pixels[key])

        {

            Add(col, key);

        }

    }

}

 

A possible optimization here is to loop through the smallest set.  You would need to maintain a count, but since new members are added through Add that should be easy.

 

Intersect

 

public void Intersect(PixelSet otherSet)

{

    PixelSet intersection = new PixelSet();

    foreach (int key in otherSet._pixels.Keys)

    {

        if (_pixels.ContainsKey(key))

        {

            foreach (int col in otherSet._pixels[key])

            {

                if (_pixels[key].Contains(col))

                {

                    intersection.Add(col, key);

                }

            }

        }

    }

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

}

 

Once again you could change this to loop through the smallest set to speed this up.

 

Summary
 

I expect this will have been a review for many readers, but it’s important to have a grasp of this information before we head into the next lesson regarding erosion and dilation.  I’d also like to reiterate that this is not optimized for image processing.  My HD7 takes almost 8 times longer to execute some of these tight loops.

 

Download Code

http://cid-88e82fb27d609ced.office.live.com/embedicon.aspx/Blog%20Files/PhoneVision/PhoneVision%2017%20-%20Set%20Operations.zip

Up Next: Erosion and Dilation

Advertisements

Actions

Information

One response

16 03 2011
Phone Vision 16 – Binary Images «

[…] Up Next: Sets […]

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s




%d bloggers like this: