Click here to Skip to main content
13,551,173 members
Click here to Skip to main content
Add your own
alternative version

Tagged as

Stats

12.4K views
438 downloads
16 bookmarked
Posted 7 Jun 2016
Licenced CPOL

Tracing Boundary in 2D Image Using Moore Neighborhood Approach

, 12 Jun 2016
Rate this:
Please Sign up or sign in to vote.
Tracing the boundaries of an object in 2D image

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

License

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

Share

About the Author

Udaya K Unnikrishnan
Software Developer (Senior)
India India
No Biography provided

You may also be interested in...

Pro
Pro

Comments and Discussions

 
QuestionBlind man with stick algorithm Pin
john morrison leon12-Jun-16 5:46
memberjohn morrison leon12-Jun-16 5:46 
PraiseMy vote of 5! Pin
jediYL9-Jun-16 17:14
professionaljediYL9-Jun-16 17:14 

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

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

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web03-2016 | 2.8.180515.1 | Last Updated 13 Jun 2016
Article Copyright 2016 by Udaya K Unnikrishnan
Everything else Copyright © CodeProject, 1999-2018
Layout: fixed | fluid