Introduction
Look at a digital image. It is just a lot of pixels, but you may be able to see lines, shades of colors, shapes, structures...and then objects and entities Have you ever wonder how you are able to make sense of this mess of pixels?
In this article, we will be looking at one way of breaking an image into sub images using a technique known as outline tracing.
Background
Breaking an image to sub images is commonly known as Image Segmentation. There are 2 main approaches: Color and Outline.
In the Color approach, we group pixels in close proximity that have similar color into blobs.
In the Outline approach, we look for foreground pixels that have neighboring background pixels, and then connect them together to form a closed path. Pixels within the closed path will form the sub image.
Figure 1
Some preliminary concepts:
Neighboring pixels:
In Figure 1, the pixel marked X, has 8 neighbors (each 1 pixel away), in the directions, starting from TopLeft (1) clockwise to Left (8). The other directions in close-wise order are Top(2), TopRight(3), Right(4), BottomRight(5), Bottom(6) and BottomLeft(7)
Foreground and background pixels:
Foreground pixels are pixels that belong to the object (sub image) that we want to isolate. Background pixels are the rest of the pixels that are surrounding the object. In Figure 1, the darker pixels on the left and top are foreground pixels and the pixels to the right and bottom are the background pixels.
Outline:
Outline pixels are foreground pixels that have at least one neighbor that is a background pixel. In Figure 1, the darker pixels marked 1,2,3.. 10 are some of the outline pixels
Algorithm
1. Start with a pixel near to the object's outline
2. Find the nearest pixel to 1 that is an outline pixel. This is the First outline pixel.
3. Starting from the outline pixel in step 2, going clockwise, probing the neighbors, find the next outline pixels This is the Next outline pixel
4. Repeat 3 until we hit the pixel in step 2
As an illustration, in Figure 1, if we start with the pixel marked X, the First outline pixel would be the dark pixel marked 2. Going clockwise, the Next outline pixel is found in direction Bottom(6), this would be the pixel marked 3, From here, with reference to pixel 3, our start direction would be the next clockwise pixel from pixel 2, TopRight(3), We hit the next outline pixel at BottomLeft(7) pixel 4.
The code below implements the algorithm.
public string TraceOutlineN(Bitmap bm, int x0, int y0, int probe_width, Color fg, Color bg, bool bauto_threshold, int n)
{
...
while (!hitstart)
{
count++;
if (count > countlimit)
{
return "";
}
try
{
for (int i = 0; i <= 2 * n; i++)
{
diffx = i - n;
index1 = CoordsToIndex(x + diffx, y - n, bmpData.Stride);
cn[i] = ((x + diffx) >= 0 && (x + diffx) < max_width && (y - n) >= 0 && (y - n) < max_height) ?
Color.FromArgb(rgbValues[index1 + 2], rgbValues[index1 + 1], rgbValues[index1])
: Color.Empty;
}
for (int i = 2 * n + 1; i < 4 * n; i++)
{
diffy = i - 3 * n;
index1 = CoordsToIndex(x + n, y + diffy, bmpData.Stride);
cn[i] = ((x + n) >= 0 && (x + n) < max_width && (y + diffy) >= 0 && (y + diffy) < max_height) ?
Color.FromArgb(rgbValues[index1 + 2], rgbValues[index1 + 1], rgbValues[index1])
: Color.Empty;
}
for (int i = 4 * n; i <= 6 * n; i++)
{
diffx = i - 5 * n;
index1 = CoordsToIndex(x - diffx, y + n, bmpData.Stride);
cn[i] = ((x - diffx) >= 0 && (x - diffx) < max_width && (y + n) >= 0 && (y + n) < max_height) ?
Color.FromArgb(rgbValues[index1 + 2], rgbValues[index1 + 1], rgbValues[index1])
: Color.Empty;
}
for (int i = 6 * n + 1; i < 8 * n; i++)
{
diffy = i - 7 * n;
index1 = CoordsToIndex(x - n, y - diffy, bmpData.Stride);
cn[i] = ((x - n) >= 0 && (x - n) < max_width && (y - diffy) >= 0 && (y - diffy) < max_height) ?
Color.FromArgb(rgbValues[index1 + 2], rgbValues[index1 + 1], rgbValues[index1])
: Color.Empty;
}
}
catch (Exception e)
{
MessageBox.Show(e.ToString());
return "";
}
int index = 0;
string tests = "";
bool dir_found = false;
for (int i = start_direction; i < start_direction + (8 * n); i++)
{
index = i % (8 * n);
if (!cn[index].Equals(Color.Empty))
if (GetMonoColor(cn[index]) == gfg)
{
current_direction = index;
dir_found = true;
break;
}
}
if (!dir_found)
for (int i = start_direction; i < start_direction + (8 * n); i++)
{
index = i % (8 * n);
if (!cn[index].Equals(Color.Empty))
{
current_direction = index;
dir_found = true;
break;
}
}
if ((index >= 0) && (index <= 2 * n))
{
diffx = index - n;
x += diffx;
y -= n;
}
if ((index > 2 * n) && (index < 4 * n))
{
diffy = index - 3 * n;
x += n;
y += diffy;
}
if ((index >= 4 * n) && (index <= 6 * n))
{
diffx = index - 5 * n;
x -= diffx;
y += n;
}
if ((index > 6 * n) && (index < 8 * n))
{
diffy = index - 7 * n;
x -= n;
y -= diffy;
}
tests = x + "," + y + ";";
s = s + tests;
start_direction = (current_direction + (4 * n + 1)) % (8 * n);
bool bMinCountOK = (n > 1) ? (count > (max_height / 5)) : (count > 10);
if (bMinCountOK && (Math.Abs(x - x1) < (n + 1) && (Math.Abs(y - y1) < (n + 1))))
hitstart = true;
}
return s;
}
Using the code
public string TraceOutlineN(Bitmap bm, int x0, int y0, int probe_width, Color fg, Color bg, bool bauto_threshold, int n)
The parameters:
System.Drawing.Bitmap bm - This could be the Image property of a form or control
int x0, int y0 - x and y coordinates of the pixel in the Image to start probing for the outline
int probe_width - the number of pixels to probe (horizontally) to find the first outline pixel
Color fg - colour of foreground (normally set to Black)
Colr bg - color of the background (normally set to White)
bool bauto_threshold - option to calculate the threshold value to determine foreground and background
int n - connect outline pixels that are n pixels away. This value is set to 1 for tracing clean connected outlines.
Returns: String in the format of "x0,y0;x1,y1;x2,y2;..." holding the coordinates of the connected outline pixels
private void pictureBox1_MouseUp(object sender, MouseEventArgs e)
{
if (e.Button == MouseButtons.Right)
{
CTraceOuline trace = new CTraceOuline();
string s=trace.TraceOutlineN((Bitmap)pictureBox1.Image, e.X, e.Y,20, Color.Black, Color.White,true, 1);
if (s != "")
{
Graphics g = Graphics.FromImage(pictureBox1.Image);
Point[] p = trace.StringOutline2Polygon(s);
Form2 f2 = new Form2();
f2.BackgroundImage = (Bitmap)pictureBox1.Image.Clone();
GraphicsPath gp=new GraphicsPath();
gp.AddPolygon(p);
f2.Region = new Region(gp);
f2.Show();
f2.Left = e.X;
f2.Refresh();
g.DrawPolygon(new Pen(Color.Red, 1), p);
pictureBox1.Refresh();
}
else
{
MessageBox.Show("Failed tracing outline!");
}
}
}
The code above is triggered when the right mouse button is released. The mouse's x,y coordinate is used as the point to start a probe for 20 pixels to find the start outline pixel. Auto-Threshold is set, with foreground Black and background White, with connected pixels set at 1 pixel away.
The returned string value from the TraceOulineN() function is processed by StringOutline2Polgon() to get an array of points.
This array of points is used to create a polygon path in a GraphicsPath object which in turn can be used to create a Region object.
The Region object is assigned to a new form, so that the shape of the form takes the shape of the outline traced. The image has also been copied to the new form, so it would look like a lift-off from the traced object.
Demo
For the screenshot at the start of this article, I have pre-loaded a picture file of a bicycle. Right click on/near the edge of the rear wheel, and the bicycle get lifted off to the desktop!
You can also draw (left mouse drag) on the picture box to create a drawing, and then right click near the edge of a figure in your drawing. Double click on the picture box clears its content. Click the Reload button to reload the previously loaded image.
For the pop up figure (new form), you can drag it around, or right click on a sub region to remove the sub region. Note that in the screenshot, the 'hello" drawing has the 'O' such that you can see through it to the desktop. This is done by right clicking inside the 'O' to remove that sub region. Double click on the pop up figure will unload it from the desktop.
For the pop up figure, Alt-Left click (hold down the Alt key while doing a left mouse) on the figure will cause it to rotate 10 degree clockwise. Similarly Alt-Right click will rotate the figure 10 deg anticlockwise. You can also scale the pop up by Ctrl-Right Click to scale down and Ctrl-Left to scale up.
For more details on such image transformation, refer to my article
Matrix Transformation of Images in C#, using .NET GDI+
I have added a fun feature of call-out creation. Type some text in the text-box, then click 'Create Call-out' button. A call-out with your text message will pop up to the desktop.
More Demo
I have added some features to the demo to show more advanced and interesting use of the CTraceOutline class.
Figure 2 and 3 show the manual setting of Threshold and Color filtering.
Figure 2
In Figure 2, first disable Auto-Threshold and checked the green check-box, then slide the Threshold scroll-bar. As the scroll-bar is scrolled, the picture in the main picture-box will be converted to a mono picture shown in the smaller picture below the scroll-bar. Notice that as you scroll, some parts of the images (which does not contain the filtered color) will disappear. When the mono picture shows only the segment of the corresponding green circle, stop sliding and right click near to green edge of the top right circle in the main picture-box.
Figure 3
In Figure 3, we try to remove the noisy background behind the flower vase. Disable Auto-Threshold then select a color filter and slide on the threshold scroll-bar until you see a reasonable gap between the flowers and the background in the mono-color picture box. Then right click near the edge of the flowers in the main picture.
Figure 4
Figure 4 shows the use of N, the last parameter for the TraceOutlineN() function. N is the number of pixels between the outline pixels that we want to connect. This is useful for poor quality images where the outlines are not clearly connected. See the magnified section of the pixels in Figure 4, the edge pixels are not connected. The word 'Connect' is written using a hatch-brush. The hatch-bush is picked when we uncheck the Solid Brush check-box. For this image segment, the nearest neighboring outline pixel from any outline pixel is at least 2 pixels away. We can attempt to connect the edge pixels by setting N to > 1. In this case we set to 4, then right click near the edge of the image segment.
Points of Interest
The demo form can be minimized and it could be used to create pop up images or even to leave messages and reminders on desktop with the easy to use the call-out message creation feature. Have fun!
History
Version 1: 17 April 2014
3 May 2014 : Added in more features in demo to show more advance use of the CTraceOutline class
5 May 2014 : Added in feature to rotate images and regions
7 May 2014 : Added in scaling of images and regions. Added in call-out creation
9 May 2014: Fix bug on transformations and added in selection and loading of embedded resources. Also easier one step call-out creation
