Moore Neighbor Contour Tracing algorithm

1. Moore Neighborhood

The Moore neighborhood of a pixel, P, is the set of 8 pixels which share a vertex or edge with that pixel. These pixels are namely pixels P1, P2, P3, P4, P5, P6, P7 and P8 shown in Figure 1 below.
The Moore neighborhood (also known as the 8-neighbors or indirect neighbors) is an important concept that frequently arises in the literature.

http://www.imageprocessingplace.com/downloads_V3/root_downloads/tutorials/contour_tracing_Abeer_George_Ghuneim/moore.html

Contour Tracing

 

2. Moore Neighbor Contour Tracing Algorithm in C++

This post shows the implementation of Moore’s neighbor tracing algorithm in C++. This algorithm performs what is called contour tracing i.e.
tracing the borders or boundaries of, in this case, a binary image. The two images below illustrates what the algorithm does with a pure black and white/binary image.

Short explanation of how the algorithm works

Pad the image with a white 1 pixel wide border. Start scanning from the top-left position and scan each pixel from left to right downwards. When a black pixel is found, trace around the contour in a clockwise direction. Tracing the contour is done by checking the 8 neighbors and see if they are black. The neighbors are checked in a clockwise manner. When we are finished tracing the contour, we start scanning again from were we started to trace and a variable “inside” is set to true. This variable will be set back to false when a white pixel is encountered. This variable is used to prevent processing of non-contours.

A good and more detailed explanation of how this simple little algorithm works can be found here

The implementation

The function below uses a 1D pixel array which definition you can find in the header file included in the source along with some other definitions and functions that are needed to run the function. The code below simply show the implementation of the actual algorithm. The C++ files can be downloaded here along with some test files using the SDL library

The C++ files can be downloaded here along with some test files using the SDL library

The algorithm is in the contour-tracing.cpp file and the main.cpp file contains a test run of the algorithm which displays the result to the screen and saves it as a bitmap image using SDL.

pixel * mooreNeighborTracing(pixel * image, int width, int height)
{
  bool inside = false;
  int pos = 0;

  // Need to start by padding the image by 1 pixel
  pixel * paddedImage = padImage(image, width, height, WHITE);

  // Allocate new image as a 1D array
  pixel * borderImage = (pixel *)malloc(sizeof(pixel) * (height+2) * (width+2));

  // Set entire image to WHITE
  for(int y = 0; y < (height+2); y ++)
  {
    for(int x = 0; x < (width+2); x ++)
    {
      borderImage[x + y*(width+2)] = WHITE;
    }
  }

  for(int y = 0; y < (height+2); y ++)
  {
    for(int x = 0; x < (width+2); x ++)
    {
      pos = x + y*(width+2);

      // Scan for BLACK pixel
      if(borderImage[pos] == BLACK && !inside)    // Entering an already discovered border
      {
        inside = true;
      }
      else if(paddedImage[pos] == BLACK && inside)  // Already discovered border point
      {
        continue;
      }
      else if(paddedImage[pos] == WHITE && inside)  // Leaving a border
      {
        inside = false;
      }
      else if(paddedImage[pos] == BLACK && !inside)  // Undiscovered border point
      {
        borderImage[pos] = BLACK;   // Mark the start pixel
        int checkLocationNr = 1;  // The neighbor number of the location we want to check for a new border point
        int checkPosition;      // The corresponding absolute array address of checkLocationNr
        int newCheckLocationNr;   // Variable that holds the neighborhood position we want to check if we find a new border at checkLocationNr
        int startPos = pos;      // Set start position
        int counter = 0;       // Counter is used for the jacobi stop criterion
        int counter2 = 0;       // Counter2 is used to determine if the point we have discovered is one single point

        // Defines the neighborhood offset position from current position and the neighborhood
        // position we want to check next if we find a new border at checkLocationNr
        int neighborhood[8][2] = {
            {-1,7},
            {-3-width,7},
            {-width-2,1},
            {-1-width,1},
            {1,3},
            {3+width,3},
            {width+2,5},
            {1+width,5}
          };
        // Trace around the neighborhood
        while(true)
        {
          checkPosition = pos + neighborhood[checkLocationNr-1][0];
          newCheckLocationNr = neighborhood[checkLocationNr-1][1];

          if(paddedImage[checkPosition] == BLACK) // Next border point found
          {
            if(checkPosition == startPos)
            {
              counter ++;

              // Stopping criterion (jacob)
              if(newCheckLocationNr == 1 || counter >= 3)
              {
                // Close loop
                inside = true; // Since we are starting the search at were we first started we must set inside to true
                break;
              }
            }

            checkLocationNr = newCheckLocationNr; // Update which neighborhood position we should check next
            pos = checkPosition;
            counter2 = 0;             // Reset the counter that keeps track of how many neighbors we have visited
            borderImage[checkPosition] = BLACK; // Set the border pixel
          }
          else
          {
            // Rotate clockwise in the neighborhood
            checkLocationNr = 1 + (checkLocationNr % 8);
            if(counter2 > 8)
            {
              // If counter2 is above 8 we have traced around the neighborhood and
              // therefor the border is a single black pixel and we can exit
              counter2 = 0;
              break;
            }
            else
            {
              counter2 ++;
            }
          }
        }
      }
    }
  }

  // Remove white padding and return it
  pixel * clippedBorderImage = (pixel *)malloc(sizeof(pixel) * (height) * (width));
  for(int x = 0; x < width; x ++)
  {
    for(int y = 0; y < height; y ++)
    {
      clippedBorderImage[x+y*width] = borderImage[x+1+(y+1)*(width+2)];
    }
  }
  return clippedBorderImage;
}

 

https://www.eriksmistad.no/moore-neighbor-contour-tracing-algorithm-in-c/

Moore Neighbor Contour Tracing Algorithm in C++ – Erik Smistad