# Object Shape Analysis and Segmentation

CS 585 HW 3
Ziliang ZHU
Teammates: Siyang Li, Yuqi GUO
Date: 24/02/2020

## Problem Definition

The current problems are:
1. Implement a connected component labeling algorithm and apply it to the data below. Show your results by displaying the detected components/objects with different colors.
2. If your output contains a large number of components, apply a technique to reduce the number of components, e.g., filtering by component size, or erosion.
3. Implement the boundary following algorithm and apply it for the relevant regions/objects.
4. For each relevant region/object, compute the area, orientation, and circularity (Emin/Emax). Also, identify and count the boundary pixels of each region, and compute compactness, the ratio of the area to the perimeter.
5. Implement a skeleton finding algorithm. Apply it to the relevant regions/objects.

The result can be used to analysis pictures. For example, gesture detection and tumor detection.
The anticipated difficulties are implementing these functions without using the opencv library, and find appropriate algorithm to get the desired result.

In problem 1, for the sequential labeling part, the second pass is hard to implement. Because we find the equivalence relations in the first pass and had to implement the union-find algorithm to deal with the equivalence relations tuples. Therefore for some complicated images with many components, the equivalence relations set is huge and therefore really time consuming to execute. Also in order to fulfill the requirements to get multiple components with larger area than the others, we also have to sort the area or set a threshold for the area of the components.

For the boundary following part,The Moore-Neighbor Tracing algorithm is as follows:

Begin

• Set B to be empty.
• From bottom to top and left to right scan the cells of T until a black pixel, s, of P is found.
• Insert s in B.
• Set the current boundary point p to s i.e. p=s
• Backtrack i.e. move to the pixel from which s was entered.
• Set c to be the next clockwise pixel in M(p).
• While c not equal to s do

•    If c is black
• insert c in B
• set p=c
• backtrack (move the current pixel c to the pixel from which p was entered)
else
• advance the current pixel c to the next clockwise pixel in M(p)
end While
End

As for the skeleton finding part, by its definition, a pixel belongs to the skeleton if none of its four neighbors are more distant to the boundary of this object. Therefore, we iterate from an object's boundary, check all pixels for their neighbors' status and determine whether they are skeleton pixels or not. Then we make the boundary one pixel smaller than the original one and recursively call the function again. Eventually, all pixels in the object are examined, and all skeleton parts are stored and outputed.

In problem 2, for the piano hands problem, it is better to use HSV channels to differentiate the hands and the white part of the piano. But it is still hard to only take the hands part because in this dataset, there are many other parts that are in similar color to the hands. Therefore applying a ROI solves the issue. However, the result still suffers from lighting conditions where hands are hidden under shadows.

For the bats problem, using a absolute threhold would focus out obvious bats in the image. It is not complete, if we had more time we would try playing with adaptive thresholding or ther methods to figure out how to catch the bats in lighter sky as well. We try to use compactness levels to figure out which bats' wings are spread out, but it may not be the perfect idea.

We use a background differentiation for the pedestrian problem. We calculate the average of all frames in the scene as the background indicator, and do a substraction on each frame with the background. Using the absolute value of this difference value map, we produce a grayscale image of moving pedestrians on each frame, later converted into binary image. Then we perform the algorithms earlier, sequential labeling and thresholding, to calculate the number of pedestrians on each frame. The frames are output together as a video in the form of avi.

The sequential labeling part is function sequential_labeling(img, invert = True, erosion = False) in sequrntil.py.
The boundary following part is function boundary_following(img_label) in boundary_following.py
Compute the area, orientation, and circularity (Emin/Emax), count the boundary pixels of each region, and compute compactness is in calc.py.
The skeleton finding part is function find_skeleton(bound, bg_pix=(0,0), ske_mask=None) in find_skeleton.py

## Experiments

We perform the founctions on four pictures:'open-bw-full.png', 'open-bw-partial.png','open_fist-bw.png', 'tumor-fold.png', and get the component Labeling, biggest component, boundary, skeleton for each picture, and for each component in the picture, we calculate the the area, orientation, circularity (Emin/Emax), oundary pixels of each region, and compactness, the ratio of the area to the perimeter.

## Results

 Original Image Component Labeling Biggest Component Boundary Skeleton

For problem 1 task 4, Here are the results:
open-bw-full.png : {'area': 32002, 'perimeter': 1272.5, 'ratio_area_perim': 25.14891944990177, 'compactness': 50.59859540028748, 'orientation': -26.96920948222597, 'circularity': 0.439956845834296}
open-bw-partial.png : {'area': 12872, 'perimeter': 1109.5, 'ratio_area_perim': 11.601622352410995, 'compactness': 95.63317666252331, 'orientation': 35.20431708259405, 'circularity': 0.25191932771350733}
open_fist-bw.png : {'area': 33643, 'perimeter': 1865.0, 'ratio_area_perim': 18.039142091152815, 'compactness': 103.3862913533276, 'orientation': -12.340577575464577, 'circularity': 0.43239992965057367}
tumor-fold.png : {'area': 46456, 'perimeter': 2083.5, 'ratio_area_perim': 22.297096232301417, 'compactness': 93.4426607973136, 'orientation': 31.314814885453778, 'circularity': 0.010921087881198341}

For problem 2:

## Discussion

The results show that our method is generally successful. To imporve the method, we can adapt the algorithm to color images.

## Conclusions

Our method can perform well on binary pictures, and to improve it we can adapt it to colorimages in the future.

## Credits and Bibliography

I complete this homework with my teammates Siyang Li and Yuqi GUO.