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:
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).
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…
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.
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:
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.
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.
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
azzlsoft.com 