# 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

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.

### 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,

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

Hi. Yes you can, no problem

• Anonymous says:

Hi Key,

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,

Hi

Images with few contours should be no problem

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 ?
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

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)