Image contour tracing: Jacob's stopping criterion issue

Question

I am trying to adopt Moore-Neighbor contour tracing algorithm in my JavaScript project and at the moment I'm reading this tutorial on contour tracing: http://www.imageprocessingplace.com/downloads_V3/root_downloads/tutorials/contour_tracing_Abeer_George_Ghuneim/square.html

But I have a problem with understanding Jacob's stopping criterion. Tutorial explains this criterion as

Stop after entering the start pixel a second time in the same manner you entered it initially

As I understand, that means that if we entered the start pixel S at the first time with a certain absolute direction (for example, UP if we are searching the start pixel from the bottom left corner), we have to stop tracing after reentering the start pixel with the same absolute direction (UP, as the first time).

That sounds very clear, but I found some cases where this condition will never be fulfilled. One of these cases is shown on this picture: Jacobs stopping criterion issue

As you can see, the start pixel (marked as S) was initially entered with the UP direction (purple arrow), but the second and all the other times it will be entered with the LEFT direction (red arrow). So, Jacob's stopping criterion (enter the start pixel with the same direction as the first time) will never fulfill.

I guess, I've just misunderstood this part of the tutorial... I'll be really happy if you explain to me where I am wrong.

Answer 1

I think you would be better off using the Radial Sweep algorithm, described on the same website. It is very similar to the Moore-Neighbor algorithm but it does not track direction so you cannot use Jacob's stopping criterion.

The tutorial instead suggests a new criterion:

Stopping Criterion 2

Assume that each time a new boundary pixel, Pi, is found by the algorithm, it is inserted in the sequence of boundary pixels as such: P1, P2, P3, ..., Pi ; and is declared as the current boundary pixel. (Assume P1 is the start pixel). This means that we know the previous boundary pixel, Pi-1, of every current boundary pixel, Pi . (As for the start pixel, we will assume that P0 is an imaginary pixel -not equivalent to ANY pixel on the grid- which comes before the start pixel in the sequence of boundary pixels).

With the above assumptions in mind, we can define our stopping criterion: The algorithm terminates when:

a) the current boundary pixel, Pi, has appeared previously as pixel Pj (where j < i ) in the sequence of boundary pixels, AND

b) Pi-1 = Pj-1.

In other words, the algorithm terminates when it visits a boundary pixel, P, for a second time provided that the boundary pixel before P (in the sequence of boundary pixels) the second time around, is the same pixel which was before P when P was first visited.

With this criterion, the algorithm should be able to handle most cases, including the one on your picture and 8-connected patterns that are not 4-connected.

In theory you should even be able to use this criterion with the Moore-Neighbor algorithm.

Answer 2

I took a stab at it and I don't think you've gotten anything wrong here, but in fact have found a case where Moore neighbor tracing just does not close under Jacob's stopping criterion.

Interestingly enough, it does close under square tracing (using Jacob's stopping criterion) and under Theo Pavlidis' Algorithm. It also closes under Moore neighbor tracing if you neglect to use Jacob's stopping criterion, and will also close under Moore neighbor tracing using Jacob's stopping criterion if you simply flip the grid vertically.