Click here to Skip to main content
Click here to Skip to main content
Go to top

Fun with Outlines

, 8 May 2014
Rate this:
Please Sign up or sign in to vote.
Techniques in tracing outlines in a drawing

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++;

                //fallback to prevent infinite loop
                if (count > countlimit)
                {

                    return "";
                }

                //getting all the neighbours' pixel color
                try
                {
                    //processing top neighbours left to right
                    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;

                    }

                    //processing right neighbours top to bottom
                    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;

                    }

                    //processing bottom neighbours right to left                    
                    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;

                    }

                    //processing left neighbours bottom to top    
                    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;

                //find the first valid foreground pixel                
                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 no foreground pixel found, just find the next valid pixel 

                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;

                        }

                    }

                // find the next direction to look for foreground pixels
                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;
                }


                //store the found outline
                tests = x + "," + y + ";";

                s = s + tests;

                start_direction = (current_direction + (4 * n + 1)) % (8 * n);


                //adaptive stop condition

                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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Yang Kok Wah
Software Developer (Senior)
Singapore Singapore
Yang Kok Wah is a Software Specialist in a leading System/Solution Integration Company in Singapore. He has more than 20 years experience in software development, specializing in areas of Biometrics, Smartcards and Image Processing. He has worked with VB, C#, Java and C/C++. He graduated from University of London with BSc(Hons) in Computing and also holds a Business Administration degree from National University of Singapore.
 
In his free time, he writes computer programs as a form of relaxation. He likes Graphics, Games, AI and Image Processing.

Comments and Discussions

 
Questionnice article Pinmemberd47427-May-14 1:47 
AnswerRe: nice article PinmemberYang Kok Wah7-May-14 2:58 
QuestionPixel inside PinmemberTheQult30-Apr-14 7:40 
AnswerRe: Pixel inside PinmemberYang Kok Wah1-May-14 6:27 
QuestionGreat article about a technique known as outline tracing! PinprofessionalVolynsky Alex18-Apr-14 21:25 
AnswerRe: Great article about a technique known as outline tracing! PinmemberYang Kok Wah19-Apr-14 1:09 
GeneralRe: Great article about a technique known as outline tracing! PinprofessionalVolynsky Alex19-Apr-14 6:02 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web02 | 2.8.140926.1 | Last Updated 8 May 2014
Article Copyright 2014 by Yang Kok Wah
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid