Moore-Neighbor Tracing Algorithm

Question

I wrote code to extract the contour of a hole, based mostly on the Moore-Neighbor Tracing algorithm. Only

a. instead of finding a shape, I'm finding a "hole"; and,

b. I'm looking for the (outer) boundary of the hole, i.e. the actual pixels that are not part of the hole but that are hole boundary.

public class MooreTrace : ITraceAlgorithm
{
 public List<Pixel> Trace(Image img)
 {
 Pixel hole_pixel;
 for (int i = 0; i < img.LenX; i++)
 for (int j = 0; j < img.LenY; j++)
 {
 hole_pixel = img.GetArrayElement(i, j);
 if (hole_pixel.Value == -1)
 // while goto statements are not highly approved of, as they create hard-to-read spaghetti code, 
 // this (breaking out of nested loops) is one of the rare cases where they should be used, 
 // as they are more coherent than setting up multiple flags, or using sub-methods that will return. 
 goto Hole_Exists;
 }
 // if here - no hole was found, simply return null
 return null;
 Hole_Exists:
 // What if hole is in (x,0) ? 
 if (hole_pixel.Yi == 0)
 {
 var next_pixel = GetNextPixel(hole_pixel, img);
 while (next_pixel.Value == -1)
 {
 hole_pixel = next_pixel;
 next_pixel = GetNextPixel(hole_pixel, img);
 }
 _start = 4;
 }
 else
 _start = 0;
 _8i = _start;
 var Boundary = new List<Pixel>();
 // priming the loop
 var first = GetClockWisePixel(hole_pixel, img);
 Boundary.Add(first);
 var boundary_pixel = GetClockWisePixel(hole_pixel, img);
 // stop condition:
 // A. reach the same first pixel we started from
 // B. in cases of enclaves with 1 space gap, this might cause a premature stop
 // we can make sure we are reaching it while completeing the full circle of the circle-wise turning
 // i.e. that the turning index (_8i) == 0 (minus the extra step that is taken) 
 // (also called Jacob's stopping criteria)
 while (!(boundary_pixel == first && _8i - 1 == _start))
 {
 if (boundary_pixel.Value != -1)
 {
 if (!Boundary.Contains(boundary_pixel))
 Boundary.Add(boundary_pixel);
 }
 else
 {
 Backtrack();
 hole_pixel = boundary_pixel;
 }
 boundary_pixel = GetClockWisePixel(hole_pixel, img);
 }
 return Boundary;
 }
 // +---+---+---+
 // | 1 | 2 | 3 |
 // |nw | n |ne |
 // +---+---+---+
 // | 0 | | 4 |
 // | w | | e |
 // +---+---+---+
 // | 7 | 6 | 5 |
 // |sw | s |se |
 // +---+---+---+
 private int[,] _8connected = new int[,] {
 {0, -1}, // 0 = w
 {-1, -1}, // 1 = nw
 {-1, 0}, // 2 = n
 {-1, 1}, // 3 = ne
 {0, 1}, // 4 = e
 {1, 1}, // 5 = se
 {1, 0}, // 6 = s
 {1, -1}, // 7 = sw 
 };
 private int _start;
 private int _8i; // index to keep where are we in the clock-wise clock 
 // 0 - w, 1 - nw, 2 - n, 3 - ne, 4 - e, 5 - se, 6 - s, 7 - sw
 private Pixel GetClockWisePixel(Pixel input, Image img)
 {
 int new_x, new_y;
 do
 {
 var x_offset = _8connected[_8i, 0];
 var y_offset = _8connected[_8i, 1];
 _8i = (_8i + 1) % 8;
 new_x = input.Xi + x_offset;
 new_y = input.Yi + y_offset;
 }
 // if edge pixels, move to next clockwise
 while (new_x < 0 || new_x >= img.LenX || new_y < 0 || new_y >= img.LenY);
 return img.GetArrayElement(new_x, new_y);
 }
 private void Backtrack()
 {
 // We want to go back to the last connected pixel we were in.
 // The return position might seem at first a bit redundant, as it returns us to a pixel already covered
 // it's crucial for the stop condition in certain cases... If we wouldn't mind missing enclaves
 // we could return one less to the next connected pixel not yet covered, and remove Jacob's stopping criteria...
 // There can be 2 cases where a new hole pixel was found in: 
 // diagonal - we will want to go counter clock 3 (+1 of the already advanced _8i) = -4 = +4
 // _8i index will be +1, i.e. 2,4,6 or 0
 // straight - we will want to go counter clock 2 (+1 of the already advanced _8i) = -3 = +5
 // _8i index will be +1, i.e. 1,3,5 or 7
 if (_8i % 2 == 1)
 _8i = (_8i + 5) % 8;
 else
 _8i = (_8i + 4) % 8;
 }
 private Pixel GetNextPixel(Pixel input, IImageMatrix img)
 {
 if (input.Yi + 1 < img.LenY)
 {
 return img.GetArrayElement(input.Xi, input.Yi + 1);
 }
 else if (input.Xi + 1 < img.LenX)
 {
 return img.GetArrayElement(input.Xi + 1, 0);
 }
 else
 return null; 
 }
}

Would be really happy to get 2 things:

1. Code Review - how to make it better, more clear, more simple, etc.

2. Understand the complexity of it. According to my calculations the tracing algorithm complexity is somewhere between \$O(\sqrt n)\$ to \$O(n)\,ドル where \$n\$ is the number of hole-pixels. The logic is as follows:

   • Finding the initial hole-position is determined by the image size, for a \$K \times L\$ pixels it will take on average \$\frac{K L - N}{2}\,ドル which is in the magnitude of \$O(K L)\$; Should I ignore this part?

   • In the best case, the shape is a perfect square. The tracing algo. will be around \12ドル\sqrt n\$ (\$\sqrt n\$ for each side, times 4 sides, times 3 for the algorithm redundancy - i.e. if we go right and down and find a hole pixel, we will now have to go up, right and down - just to get to the next hole - that's 3 steps). This is the same as \$O(\sqrt n)\$.

   • In the worst case, the shape is a perfect diagonal. Tracing algo. will be around \8ドルn\$ which is same as \$O(n)\$. This is because we will traverse the diagonal from two of its sides (x2) and for ~all hole pixels we will require 4 steps to move from one hole-pixel to another.

So which one is it?

---

You can check out (download and test) the entire project on github.

Hole in image:

Hole in image

Fixed with weighted average function:

Fixed with weighted average function

Fixed with regular average function:

Fixed with regular average function

Fixed with gradient average function:

Fixed with gradient average function

Fixed with spiral 8-connected function:

Fixed with spiral 8-connected function

• Vogel612: Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers .
• Maverick Meerkat: Ok... Didn't know.
• Vogel612: I suggest putting the bug you found into a self-answer and possibly asking a follow-up question :) no worries
• Cris Luengo: The boundary tracing algorithm cannot be characterized in terms of number of pixels in the hole, but should be characterized in therms of the number of pixels in the boundary. So, it is \$O(n)\$. There is no generic relationship between boundary length and surface area of a 2D shape.

Answer 1

I can't agree with the comments about goto and using sub methods.

Pixel hole_pixel;
for (int i = 0; i < img.LenX; i++)
 for (int j = 0; j < img.LenY; j++)
 {
 hole_pixel = img.GetArrayElement(i, j);
 if (hole_pixel.Value == -1)
 // while goto statements are not highly approved of, as they create hard-to-read spaghetti code, 
 // this (breaking out of nested loops) is one of the rare cases where they should be used, 
 // as they are more coherent than setting up multiple flags, or using sub-methods that will return. 
 goto Hole_Exists;
 }
// if here - no hole was found, simply return null
return null;
Hole_Exists:

It would be much cleaner by implementing a FindHolePixel() method which removes the need for a goto and the 3 lines comment as well, like so

Assuming img is an ImageMatrix instead of an Image:

private Pixel FindHolePixel(ImageMatrix imageMatrix)
{
 for (var i = 0; i < imageMatrix.LenX; i++)
 {
 for (var j = 0; j < imageMatrix.LenY; j++)
 {
 Pixel holePixel = imageMatrix.GetArrayElement(i, j);
 if (holePixel.Value == -1)
 {
 return holePixel;
 }
 }
 }
 return null;
} 

resulting in Trace() looking like so

public List<Pixel> Trace(ImageMatrix imageMatrix)
{
 Pixel holePixel = FindHolePixel(imageMatrix);
 if (holePixel == null) { return null;}

• Trace() is a public method. Public methods should always validate their method arguments.
• As you see I have added braces {} althought they might be optional. Omitting braces can lead to hidden and therefor hard to find bugs.
• Based on the .NET Naming Guidelines variables should be named using camelCase casing.
• You should think about returning an empty List<Pixel> instead of null if you are just iterating over the List<Pixel>. You wouldn't need a null check after calling Trace().

---

private Pixel GetNextPixel(Pixel input, IImageMatrix img)
{
 if (input.Yi + 1 < img.LenY)
 {
 return img.GetArrayElement(input.Xi, input.Yi + 1);
 }
 else if (input.Xi + 1 < img.LenX)
 {
 return img.GetArrayElement(input.Xi + 1, 0);
 }
 else
 return null; 
} 

The return null; seems dangerous to me because you are using the result without any null check. You may say thats not a problem because this won't happen but have you chaecked all edge cases ? What if your ImageMatrix is one gigantic hole ? Then you would get a NullReferenceException which always looks bad.

---

// What if hole is in (x,0) ? 
if (hole_pixel.Yi == 0)
{
 var next_pixel = GetNextPixel(hole_pixel, img);
 while (next_pixel.Value == -1)
 {
 hole_pixel = next_pixel;
 next_pixel = GetNextPixel(hole_pixel, img);
 }
 _start = 4;
}
else
 _start = 0;

• So what is special about a hole in (x,0) ? Comments should describe why something is done in the way it is. The line if (hole_pixel.Yi == 0) is just doing what your comment says.

• What does _start = 4; mean ? Using a well named constant would make the code easier to read.

• By first setting _start = 0; you could omit the else part.

• Whats the meaning/purpose/advantage of i in Pixel.Yi ?
• _start is used only inside the Trace() method. Why is it a class level variable ?
• You have holePixel and nextPixel, why don't you have firstPixel instead of first?

---

// priming the loop
var first = GetClockWisePixel(hole_pixel, img);
Boundary.Add(first); 

Here you make the assumption that firstPixel isn't a pixel of the hole but of the boundary. Will this always be true?

• VisualMelon: I'd want that null in GetNextPixel to be a throw/assert (with useful message): if you assume something will never happen, then you should document that, and when it does happen you will want to know about it.
• Maverick Meerkat: Thanks for taking the effort for such a thorough review! You make some valid points there. Some of them I already implemented in the Github project (named constants, camel case), some you made me realize just now. I disagree a bit about the goto but that's more ideological. If I'm not mistaken, the way I made it first/firstPixel will always be a boundary, unless the gigantic hole scenario which I didn't take into consideration at all and would probably run the app into an infinite loop...
• Maverick Meerkat: And new way does not include GetNextPixel, only GetClockwisePixel, so all the null issue there is avoided.