Tag Archives: contour tracing algorithms

Suzuki’s Contour tracing algorithm OpenCV-Python

2 Replies

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)).

outer and hole border

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

image to perform suzuki algorithm

Let’s say fij 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.
Criteria for outer or 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. fij = 1 and fi,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 = fij in case fij > 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 fij = -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 fij != 1 then set LNBD = |fij| 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.

Step1 Suzuki algorithm
Step 2.1 Suzuki algorithm
Step 2.2 Suzuki algorithm
Step 2.3 Suzuki algorithm
Step 2.4.2 Suzuki algorithm
Step 2.5 Suzuki algorithm

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

Final output Suzuki algorithm

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.

Contour Tracing

Leave a reply

In the previous blogs, we discussed various image segmentation methods which result in partitioning the image into sub-regions. Now, the next task is to represent and describe these regions in a form suitable further image processing tasks such as pattern classification or recognition, etc. One can represent these regions either in terms of the boundary (external feature) or in terms of the pixels comprising the regions (internal feature). So, in this blog, we will discuss one such representation known as Contours.

Contours in simple terms is a curve joining all the continuous points (along the boundary), having some similar property such as intensity. Once the contours are extracted, we can use them for shape analysis, and various object detection and recognition tasks, etc. So, let’s discuss different contour tracing (i.e. detecting the boundary of a region) algorithms. Some of the most common algorithms are

Square Tracing algorithm

This was one of the first approaches to extract contours and is quite simple. Suppose background is black (0’s) and object is white (1’s). Start iterating over the binary or segmented image row by row starting from left to right. If you detect white pixel (i.e. 1) go left otherwise go right. Here, left and right direction is subjective to how you entered that pixel. Stopping condition is if you entered the starting pixel a second time in the same manner you entered it initially. This works best with 4-connectivity as it only checks left and right and misses diagonal directions.

Moore Boundary Tracing algorithm

Start iterating row by row from left to right. Then traverse the 8-connected components of the object pixel found in the clockwise direction from the background pixel just before the object pixel. Stopping criteria is same as above. This removes the above method limitations.

Radial Sweep

This is similar to the Moore algorithm. After performing the first step of Moore algorithm, draw a line segment connecting the two object pixels found. Rotate this line segment in the clockwise direction until an object pixel is found in the 8-connectivity. Again draw the line segment and rotate. Stopping criteria is when you encounter the starting pixel, a second time, with the same next pixel. For a demonstration, please refer to this.

These are some of the few algorithms for contour tracing. In the next blog, we will discuss the Suzuki’s Algorithm one that OpenCV uses for finding and drawing contours. Hope you enjoy reading.

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

References: Wikipedia, Imageprocessingplace