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.
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
Any chance you could put a (permissive) license on this code? Can’t use it commercially without one.
Sure, I release it under the BSD 2-clause license https://opensource.org/licenses/BSD-2-Clause
Can this code work in XCode for the iOS project?
can you provide this code in java plz
please help me my problem is implementation of cluster edge deletion in c++ thank you veryyyyyyyyy muchhhhhhhhhhhhhhhhhhhhhhh
Hi,
Can you please post the link where the c# code is?
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
Hi Key,
Can you please post the link to your blog where you placed the C# code ?
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
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
Sure, you can use the list datastructure from stl (http://www.cplusplus.com/reference/stl/list/) and add elements after line 86
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.
Please can i get program for border algorithm (data mining)
thanks for your help
mahdi
Download it from http://www.thebigblob.com/wp-content/uploads/Moore-Neighbor-Tracing-Algorithm.zip
how to used this codes in csharp?