13,551,173 members
alternative version

#### Stats

12.4K views
16 bookmarked
Posted 7 Jun 2016
Licenced CPOL

# Tracing Boundary in 2D Image Using Moore Neighborhood Approach

, 12 Jun 2016
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

## Share

 Software Developer (Senior) India
No Biography provided

## You may also be interested in...

 Pro Pro

 First Prev Next
 Blind man with stick algorithm john morrison leon12-Jun-16 5:46 john morrison leon 12-Jun-16 5:46
 My vote of 5! jediYL9-Jun-16 17:14 jediYL 9-Jun-16 17:14
 Last Visit: 31-Dec-99 18:00     Last Update: 21-May-18 21:27 Refresh 1

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

Web03-2016 | 2.8.180515.1 | Last Updated 13 Jun 2016
Article Copyright 2016 by Udaya K Unnikrishnan