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:
- Code Review - how to make it better, more clear, more simple, etc.
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 \$8n\$ 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:
Fixed with weighted average function:
Fixed with regular average function:
Fixed with gradient average function:
Fixed with spiral 8-connected function: