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.

Picture before running Moore Neighbor Tracing algorithm
Picture before running Moore Neighbor Tracing algorithm

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
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;
}

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.

C# version of the code

Christopher Wells has made a C# version of the code which can be found at https://gist.github.com/cwellsx/e9a1d7092203073c40565455c9b5c79d

14 Responses

  1. Anonymous says:

    please help me my problem is implementation of cluster edge deletion in c++ thank you veryyyyyyyyy muchhhhhhhhhhhhhhhhhhhhhhh

  2. Anonymous says:

    Hi,

    Can you please post the link where the c# code is?

  3. Key says:

    Hi again!
    Thanks for this great article! It helps me a lot!
    Short question: I’ve changed it a little bit to use on C# + finding&storing all contours on the page. Can I post it in my blog, with all links here and your authorship, of course? Maybe it’ll be useful for someone, like this article was for me.
    Thanks

  4. Key says:

    Hi!
    Does this algorithm handles few contours on the image? And how to get few lists of ordered points, when there’re few contours on the image?
    Thanks,

  5. gwen says:

    Hi !
    very nice 🙂
    with your code, do you know if it is possible to have an ordered list of all the pixels on the contour ?
    thanks in advance for your response
    gwen

  6. Demetri says:

    Hi Erik,

    Really nice work here! I’m trying to integrate this into an app I’m writing for iOS that does basic tracing for a game. Since I can’t use the SDL framework on iOS, I’m using CoreGraphics to render my image data from disk…

    It’s not working for me right now and I’m guessing the issue may be the data format conversion (I haven’t figured out a good way to debug the issue since I can’t get your demo app to run on my machine due to crashes in the SDL framework). Do you by chance know the image data format that SDL renders?

    Thanks!
    Demetri

    • Erik Smistad says:

      Hi

      I think its just a linear array, like in the function above. It shouldn’t be difficult to just use the function above using your own favourite image library.

  7. MAHDI says:

    Please can i get program for border algorithm (data mining)
    thanks for your help
    mahdi

  8. yoon says:

    how to used this codes in csharp?

Leave a Reply

Your email address will not be published.