get-the-solution.net - Use boundary trace to find contour of object in images

Use boundary trace to find contour of object in images

on Dec 19, 2021 Regards: education; Article; image; C#;

Find object contour with Boundary tracing

Recently my task was to find the contour of an object in an image. For this kind of problem the algorithm “Moore boundary tracing” by Edward F.Moore described in the book “Digital Image Processing”[1] can be applied. You input a binary image (it won’t work with colour or grayscale images) and will retrieve all points of the contour. The implementation expects that the object in the image is represented by white pixels (255 = white) and the background by black pixels (0 = black). There are various methods to convert an image to a binary image using threshold approaches. An additional constraint is that the object isn’t allowed to touch the border of the image, otherwise the implementation will fail. An other weaknesses of the algorithm is that it ignores any “holes” in the object.

static Point GetUppermostLeftmostPointAsync(Image<Rgba32> image)
{
    for (int y = 0; y < image.Height; y++)
    {
        for (int x = 0; x < image.Width; x++)
        {
            var pixel = image[x, y];
            if (pixel is Rgba32 { R: = 255, G: = 255, B: = 255 }
            {
                return new Point(x, y);
            }
        }
    }
    throw new InvalidOperationException("No point ==1 found!");
}

In the first step we try to find the upper most left point of the object. We start at pixel 0,0 and keep going left while checkeing each of their values. If the pixels value is 0 (background) we move to the next pixel until we find the pixel which contains the value 255 (white). We store the position of the now detected object into b0 (9,3). The previous visited pixel position will be stored into c0 (8,3). We add the position of b0 to the contour list.

The next step is to examine the neighbor pixels, starting from c0 in a clockwise direction.

(Fig 2. Sample eximane neigbor in clockwise direction)

(Point b1, Point c1) ExamineNeighborsAsync(Image<Rgba32> image, Point c0, Point b0)
{
    Point point = c0;
    Point lastPoint = new Point();
    while (image[point.X, point.Y] is { R: < 254, G: < 254, B: < 254 })
    {
        lastPoint = point;
        if (point.X < b0.X && point.Y == b0.Y)
        {
            //c0|
            //  |b0|xx
            //von links eins rauf gehen bei zustand 
            point = new Point(point.X, point.Y - 1);
        }
        else if (point.X < b0.X && point.Y == (b0.Y - 1))
        {
            //  |c0 
            //  |b0|xx
            point = new Point(point.X + 1, point.Y);
        }
        else if (point.X == b0.X && point.Y == (b0.Y - 1))
        {
            //  |  |c0
            //  |b0|xx
            point = new Point(point.X + 1, point.Y);
        }
        [...]
    }

    return new(point, lastPoint);
}

These steps are repeated until we reach the initial upper most left point of the object (at 10,4).

    do
    {
        //Find the first neighbor labeled 1 and denote it by nk.
        var nkNK = ExamineNeighborsAsync(image, c, b);
        b = nkNK.b1;
        c = nkNK.c1;
        boundaryPoints.Add(b);
    }
    while (!(b.X == b0.X && b.Y == b0.Y));

We start examining the nearby neighbor with c0 from x=8,y=3. We move in a clockwise direction, to 8,2 and check if the pixels value is 255. Because the next value is not 255 we move forward to 9,2. Next pixel position is 10,2. Still no object detected, so we go forward to 10,3. Now we hit a pixel value of the object. Our new b is 10,3 and c is the previous visited pixel of b 10,2. We add b to the contour list.

As our b is not b0 we need to examine the next neighbor. We begin from the position c and move to 10,2 to 11,2. We proceed moving in a clockwise direction until we hit 10,4. We add the new point 10,4 as b to the list of contours.

These steps are repeated until b0 was reached by examing the next neighbor. When b = b0 all positions are collected for drawing the contour of the image. See the underneath sample.

(Fig 5. Input image) (Fig 6. New created image drawing all points of the contour)

I implemented the algorithm in csharp, using the libary ImageSharp for loading and working with the image pixel data. For the full sourcecode check out: ConsoleApp5BoundaryFollowingTracing

References

[1] Digital Image Processing 4th Edition Chapter 12 by Rafael Gonzalez (Author), Richard Woods (Author)