CS585 Homework 3

Long Guo, U29294789; Shuzhe Luan, U71316165;

Problem Definition

Problem 1

  1. Implement a connected component labeling algorithm.
  2. Apply a technique to reduce the number of components.
  3. Implement the boundary following algorithm.
  4. For each relevant region/object, compute the area, orientation, circularity (Emin/Emax), and compactness.
  5. Implement a skeleton finding algorithm.

Problem 2

  1. Implement two segmentation algorithms.
  2. Apply the tools you implemented for part 1 to analyze your data.

Method and Implementation

Connected Component Labelling

We use BFS instead of DFS to traverse connected pixels. Not only can we avoid the stack overflow issue but also logging down the traversed nodes with ease on the queue.

Reducing Components

If the area of component we find is too low, more specifically, lower than a threshold we set, the component will be discarded.

Boundary Following

We implemented Moore-Neighbor Tracing algorithm to find the border of a connected component. The upper-left point will be found first in "right" direction, and the pointer moves clockwise in the immediate outer pixel. The algorithm ends when the pointer returns the starting point in the right.

Skeleton finding

We used erosion on cross kernel to find the remaining part of the image.

Experiments and Results

Exercise 1


Exercise 2


First we used background detection with createBackgroundSubtractorMOG2 to try to remove background.


Then we used skin detection to detect skin. The color space was transformed to YCrCb, and by using absolute thresholding it became a binary picture.


With some opening and closing to reduce noise and counting the size of connected components, the only obstacle was the pianist's hair. To solve this issue we calculated the moment of the connected component and find the one that "looks like" a hand.


This however wasn't the best solution though. We tried to adapt averaging on the image to reduce the size of piano, but it was too dark to get a good result.


  1. Subtract the background: we used MOG algorithm to extract bats from the orginal images.
  2. Segmentation: 2.1 Absolute threshold: using absolute threshold can have a good result if the bats are all far from each other. However, if they get too close, we cannot tell the difference.


2.2 Adaptive threshold: using adaptive can help us distinguish two bats that are near to each other. But if two bats overlap, the result is not good still.


  1. CLL: We have tried using Close to fill little gaps between different parts of bats, however, this operation can cause more trouble when the bats are really small. So, we just used OPEN to clean the noise.
  2. Judge : we calculate the minimal distance between the center of gravity of the connected component and the all dots in the connected component. If bats open their wings, the distance tend to be smaller. However, if the bats overlap their wings, we cannot know that whether the bats are opening or overlaping their wings.


We computed the difference between the first frame and every other frame, and accumulate the sum of every pixel on all frames. (Assuming 1 for "black" and 0 for "white") to find the background and pedestrian's locations on frame 1. Applying this mask with xor operation we can get a clean moving figures on every frame.


Then we tried different kernels to deal with persons close to each other. By calculating the width and height on every connected component we filter those too small nor too "fat".


The results was very promising, yet there may be still problems near the light as it obstructs the person. Furthermore, there may be still some issues on balancing between separating two persons and integrating different parts of a person.


We had some good results on the dataset. However, there are still many aspects that can be improved, such as removing the piano, and removing the obstacles.