In the previous blog, we discussed various contour tracing algorithms like radial sweep, Moore’s, etc. In this blog, we will discuss another famous contour tracing algorithm known as Suzuki’s algorithm. Many of the image processing libraries such as OpenCV uses this border following algorithm for the topological structural analysis of the image. This was one of the first algorithms that define the hierarchical relationships among the borders. This algorithm also differentiates between the outer boundary or the hole boundary. Before discussing this algorithm, let’s understand what is the outer and hole border. The below figure explains this pretty well. (Here we will be dealing with binary images (0 or 1)).

Now, let’s understand the algorithm using the following image.

Let’s say f_ij denotes the value of the pixel at location (i,j). The uppermost row, the lowermost row, the leftmost column, and the rightmost column of a picture compose its frame. In this, we assign a unique number to every new border found and we denote it by NBD. We assume the NBD of the frame as 1. Rest borders are numbered sequentially. We save the information of the parent of any border in LNBD or last NBD.

Steps:

• Start scanning the image from left to right until you find the object pixel. Decide whether it is an outer border or hole border. The criteria for checking the outer or hole border is shown in the image below. Thus while scanning if we found the situation as shown in the image below, we can easily tell whether it is the starting point of the outer or the hole border.

Perform the following steps only for pixels >0. Every time we begin to scan a new row, reset LNBD to 1.

Step-1

1. If it’s an outer border (i.e. f_ij = 1 and f_i,j-1 = 0) then increment the NBD and set (i2, j2) as (i, j-1).
2. Else if it is a hole border, increment NBD. Set (i2, j2) as (i, j+1) and LNBD = f_ij in case f_ij > 1.
3. Otherwise, go to step 3.

Step-2

Now, from this starting point, we will trace the border. This can be done as

1. Starting from (i2, j2) look around clockwise the pixels in the neighborhood of (i, j) and find a nonzero pixel and denote it as (i1, j1). If no nonzero pixels are found, set f_ij = -NBD and go to step 4.
2. Set (i2, j2) = (i1, j1) and (i3, j3) = (i,j).
3. Starting from the next element of the pixel (i2, j2) in the counterclockwise order, again traverse the neighborhood of the (i3, j3) in the counterclockwise direction to find the first nonzero pixel and set it to (i4, j4).
4. Change the value of the current pixel (i3, j3) as
   1. if the pixel at (i3, j3 +1) is a 0-pixel belonging to the region outside the boundary, set the current pixel value to -NBD.
   2. if the pixel at (i3, j3 +1) is not a 0-pixel and the current pixel value is 1, set the current pixel value to NBD.
   3. Otherwise, do not change the current pixel value.
5. if in step 2.3, we return to the starting point again i.e (i4, j4) = (i, j) and (i3, j3) = (i1, j1) go to step 3. Otherwise, set (i2, j2) = (i3, j3) and (i3, j3) = (i4, j4) and go back to step 2.3.

Step-3

If f_ij != 1 then set LNBD = |f_ij| and start scanning from the next pixel (i, j+1). Stopping criteria is when we reached the bottom right corner of the image.

The below images shows step by step the result of one iteration of Suzuki’s algorithm on the above image.

Similarly repeating the above steps, we will get the following output. The hierarchy relationship among borders is also shown below.

They also proposed another algorithm that only extracts the outermost border. OpenCV supports both hierarchical and plane variants of the Suzuki algorithm. You can find the full code here.

References Paper: Topological structural analysis of digitized binary images by border following

So, that’s it for Suzuki’s algorithm. Hope you enjoy reading.

If you have any doubts/suggestion please feel free to ask and I will do my best to help or improve myself. Good-bye until next time.