Tracing Boundary in 2D Image Using Moore Neighborhood Approach

• Download source - 2.2 KB

Introduction

This article is about the implementation of boundary tracing algorithm using Moore neighborhood concept in C++. Output is a set of continuous points along the boundary of object in 2D image. The current implementation supports only one connected object in the image.

Background

I had to resample the boundary points of a hole object in an image. I used Moore neighborhood concept for tracing the boundary of this hole object . And resampled the points using fraction of length of the boundary. Input image was like this:

Using the Code

Input image values are assumed to be 0 for background and 255 for foreground.

First, we have to find the starting pixel of the boundary. For that, we will traverse through the image row wise and assign the first non zero pixel as the starting pixel of the boundary.

Then, we trace through the boundary in clockwise direction, using Moore neighborhood approach until we reach the starting pixel again.

Algorithm:

1. Traverse 2D matrix in row wise
2. Set the first nonzero pixel as S(Starting of the boundary)
3. Set the current pixel as p ; Add this non zero pixel into a boundary pixel list
4. Set the previous pixel from where p is entered as b (Backtracked pixel )
5. Take a 3 * 3 neighborhood of p and search for the next clockwise nonzero pixel from b in clockwise direction
6. Repeat the steps 3 to 5 until p is same as S

/* 
* Description - Get the continuous boundary points
* Parameters
* InputImage    - Input image
* Width_i        - Width of the image
* Height_i        - Height of Image
* BoundaryPoints - Vector of boundary points (output)
*/
void TraceBoundaryPoints::GetContinousBoundaryPoints( unsigned char* InputImage, 
                                                      int Width_i, int Height_i, 
                                                      std::vector<Point2D>& BoundaryPoints )
{
    int nImageSize = Width_i * Height_i;
    if( NULL != InputImage )
    {
        int Offset[8][2] = {
                                { -1, -1 },       //  +----------+----------+----------+
                                { 0, -1 },        //  |          |          |          |
                                { 1, -1 },        //  |(x-1,y-1) | (x,y-1)  |(x+1,y-1) |
                                { 1, 0 },         //  +----------+----------+----------+
                                { 1, 1 },         //  |(x-1,y)   |  (x,y)   |(x+1,y)   |
                                { 0, 1 },         //  |          |          |          |
                                { -1, 1 },        //  +----------+----------+----------+
                                { -1, 0 }         //  |          | (x,y+1)  |(x+1,y+1) |
                            };                    //  |(x-1,y+1) |          |          |
                                                  //  +----------+----------+----------+
        const int NEIGHBOR_COUNT = 8;
        Point2D BoundaryPixelCord;
        Point2D BoundaryStartingPixelCord;
        Point2D BacktrackedPixelCord;
        int BackTrackedPixelOffset[1][2] = { {0,0} };
        bool bIsBoundaryFound = false;
        bool bIsStartingBoundaryPixelFound = false;
        for(int Idx = 0; Idx < nImageSize; ++Idx ) // getting the starting pixel of boundary
        {
            if( 0 != InputImage[Idx] )
            {
                BoundaryPixelCord.X = Idx % Width_i;
                BoundaryPixelCord.Y = Idx / Width_i;
                BoundaryStartingPixelCord = BoundaryPixelCord;
                BacktrackedPixelCord.X = ( Idx - 1 ) % Width_i;
                BacktrackedPixelCord.Y = ( Idx - 1 ) / Width_i;
                BackTrackedPixelOffset[0][0] = BacktrackedPixelCord.X - BoundaryPixelCord.X;
                BackTrackedPixelOffset[0][1] = BacktrackedPixelCord.Y - BoundaryPixelCord.Y;
                BoundaryPoints.push_back( BoundaryPixelCord );
                bIsStartingBoundaryPixelFound = true;
                break;
            }            
        }
        Point2D CurrentBoundaryCheckingPixelCord;
        Point2D PrevBoundaryCheckingPixxelCord;
        if( !bIsStartingBoundaryPixelFound )
        {
            BoundaryPoints.pop_back();
        }
        while( true && bIsStartingBoundaryPixelFound )
        {
            int CurrentBackTrackedPixelOffsetInd = -1;
            for( int Ind = 0; Ind < NEIGHBOR_COUNT; ++Ind )
            {
                if( BackTrackedPixelOffset[0][0] == Offset[Ind][0] &&
                    BackTrackedPixelOffset[0][1] == Offset[Ind][1] )
                {
                    CurrentBackTrackedPixelOffsetInd = Ind;// Finding the bracktracked 
                                                           // pixel's offset index
                    break;
                }
            }
            int Loop = 0;
            while( Loop < ( NEIGHBOR_COUNT - 1 ) && CurrentBackTrackedPixelOffsetInd != -1 )
            {
                int OffsetIndex = ( CurrentBackTrackedPixelOffsetInd + 1 ) % NEIGHBOR_COUNT;
                CurrentBoundaryCheckingPixelCord.X = BoundaryPixelCord.X + Offset[OffsetIndex][0];
                CurrentBoundaryCheckingPixelCord.Y = BoundaryPixelCord.Y + Offset[OffsetIndex][1];
                int ImageIndex = CurrentBoundaryCheckingPixelCord.Y * Width_i + 
                                    CurrentBoundaryCheckingPixelCord.X;
                if( 0 != InputImage[ImageIndex] )// finding the next boundary pixel
                {
                    BoundaryPixelCord = CurrentBoundaryCheckingPixelCord; 
                    BacktrackedPixelCord = PrevBoundaryCheckingPixxelCord;
                    BackTrackedPixelOffset[0][0] = BacktrackedPixelCord.X - BoundaryPixelCord.X;
                    BackTrackedPixelOffset[0][1] = BacktrackedPixelCord.Y - BoundaryPixelCord.Y;
                    BoundaryPoints.push_back( BoundaryPixelCord );
                    break;
                }
                PrevBoundaryCheckingPixxelCord = CurrentBoundaryCheckingPixelCord;
                CurrentBackTrackedPixelOffsetInd += 1;
                Loop++;
            }
            if( BoundaryPixelCord.X == BoundaryStartingPixelCord.X &&
                BoundaryPixelCord.Y == BoundaryStartingPixelCord.Y ) // if the current pixel = 
                                                                     // starting pixel
            {
                BoundaryPoints.pop_back();
                bIsBoundaryFound = true;
                break;
            }
        }
        if( !bIsBoundaryFound ) // If there is no connected boundary clear the list
        {
            BoundaryPoints.clear();
        }
    }
}

Output of the algorithm looks like this. Red indicates the traced boundary.

Points to Note

This algorithm works for closed region only. If the object is not a closed one, we have to do some preprocessing operations like morphological dilation or closing. If there are multiple objects trace the boundary of first object then mask the object using the boundary info and get next object so on. OpenCV library is used for loading and displaying the input and output images.

bwboundaries matlab function implements moore-neighbor tracing algorithm

Reference

• https://en.wikipedia.org/wiki/Moore_neighborhood