1
$\begingroup$

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:

Binary structure of the 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.

enter image description here

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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

Original 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:

Original image with start and start-from

$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:

enter image description here

$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:

Move next

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:

Result

Wow. This was so long to explain...

Here is the specific point in the article: enter image description here

$\endgroup$
3
  • $\begingroup$ Thx for the long explanation, but i still have some problems with the second round. The case b is: "if the pixel (i3,j3+1) is not a 0-pixel" In our case i3, j3+1 is an zero pixel. So we should go with case a. I found another explanation on a website. There was the definition of case a a bit different. They add a small thing; The 0-Pixel has to belong to the higher tropoloigcal area. Then you dont have the problem that it has a negative number and you will find the hole boarder. $\endgroup$
    – Vanior
    Commented Aug 12, 2022 at 11:17
  • $\begingroup$ @Vanior: you didn't read case (b) completely. Check the edited version of the answer. $\endgroup$ Commented Aug 12, 2022 at 12:19
  • $\begingroup$ I think the misunderstanding comes from the wording, (3.4)(b) should read as follows: If the pixel (i3, j3 + 1) was not examined in the substep (3.3) and fi3,j3 = 1, then fi3,j3 <- NBD. The main confusion comes from the 0-pixel part and many implementations I have seen online check if that pixel is 0 (but this thinking is wrong, that pixel is undefined as it was not examined). $\endgroup$
    – kory
    Commented May 18, 2023 at 23:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.