Problem with "Topological Structural Analysis of Digitized Binary Images by Border Following" by Suzuki Abe

Question

I have a Problem with the Paper "Topological Structural Analysis of Digitized Binary Images by Border Following" by Suzuki and Abe. In the Chapter "Appendix I: The Formal Description of Algorithm 1" I think I found an issue:

Consider this input image:

We start by finding the first not zero pixel and decide that it is a start point for an outer border. If we follow the algorithm in the paper, it looks like this after the detection of the outer border.

But if it looks like this one, we will never found the hole border, because the hole border starting point is found when the value $f$ of pixel $(i,j)$ is higher than 1, and the value of pixel $(i,j+1)$ is 0.

In my opinion the step (3.3) is wrong, if you compare the algorithm to the pictures in the paper.

Answer 1

Your output has a mistake, since it's giving -2 to left pixels. Let's add some coordinates to your image:

You start in raster scan order and hit step (1)(a): it's an outer border, so $NBD\leftarrow2$, $(i,j)\leftarrow(1,1)$, $(i_2,j_2)\leftarrow(1,0)$. Let's call $P_{start}\equiv(i,j)$, and $P_{from}\equiv(i_2,j_2)$.

Then you move to step (2) and set its parent to 1.

Now the counterclockwise border following algorithm:

(3.1 aka InitPhase): search clockwise around $P_{start}$ starting from $P_{from}$ a nonzero pixel. You check in order: $(1,0)$, $(0,0)$, $(0,1)$, $(0,2)$, and eventually you find $(1,2)$. Now you set $(i_1,j_1)\leftarrow(1,2)$. Let's call $P_{start\mbox{-}from}\equiv(i_1,j_1)$. In our case we have the following result:

$P_{start}$ is yellow and $P_{start\mbox{-}from}$ is green. You need the starting point and the original direction to detect multiple passes through it, and avoid stopping too early.

(3.2 aka Setup): $(i_2,j_2)\leftarrow(1,2)$ and $(i_3,j_3)\leftarrow(1,1)$. Let's call $P_{cur}\equiv(i_3,j_3)$ and $P_{prev}\equiv(i_2,j_2)$.

(3.3 aka FindNext): search counterclockwise around $P_{cur}$ starting from the next of $P_{prev}$ a nonzero pixel. You check in order: $(0,2)$, $(0,1)$, $(0,0)$, $(1,0)$, $(2,0)$, and eventually you find $(2,1)$. Now you set $(i_4,j_4)\leftarrow(2,1)$. Let's call $P_{next}\equiv(i_4,j_4)$. In our case we have the following result:

$P_{prev}$ is pink, $P_{cur}$ is green, and $P_{next}$ is blue.

(3.4 aka SetValue): the image at $(i_3,j_3+1)=(1,2)$, the pixel to the right of $P_{cur}$, and at $P_{cur}$ is nonzero, so we are in case (b): $f(P_{cur})\leftarrow2$.

(3.5 aka MoveNext): $P_{prev} \leftarrow P_{cur}$ and $P_{cur} \leftarrow P_{next}$.

---

Let's do it again!

(3.3 aka FindNext): search counterclockwise around $P_{cur}$ starting from the next of $P_{prev}$ a nonzero pixel. You check in order: $(1,0)$, $(2,0)$, $(3,0)$ and eventually $P_{next}\leftarrow(3,1)$. We have the following result:

Watch out: here is the trick

(3.4 aka SetValue): the image at $(i_3,j_3+1)=(2,2)$, the pixel to the right of $P_{cur}$, is not a 0-pixels examined in the substep (3.3). In fact we examined $(1,0)$, $(2,0)$, $(3,0)$. So we are again in case (b): $f(P_{cur})\leftarrow2$.

Now you can keep going. The final result (before resuming the raster scan) will be:

Wow. This was so long to explain...

Here is the specific point in the article: