Object Shape Analysis and Segmentation

CS 585 HW 4
Jithvan Ariyaratne & Nam Pham | Assignment Directory
Date: 4/3/2020


Problem Definition

The goal of this part of the programming assignment is for you to learn more about the practical issues that arise when designing a tracking system. You are asked to track moving objects in video sequences, i.e., identifying the same object from frame to frame:

  1. You may consider two frames at a time (or, more ambitiously, use multiple hypothesis tracking (MHT) with more than two frames).
  2. You may use a greedy, suboptimal bipartite matching algorithm (or, more ambitiously, implement an optimal data association algorithm).
  3. To estimate the state of each tracked object, you may use an alpha-beta filter (or, more ambitiously, a Kalman filter).

Problem 1: Multiple Object Tracking

Just in case you had any trouble segmenting images and distinguishing objects (multi-object labeling), we are providing segmentation and/or detections for the bat dataset. The segmentation of the bat dataset is provided in a set of label maps. There is one number per pixel, delimited by commas. Pixels with the value 0 are background. The maps are 1024 by 1024. The detections are given in a comma delimited file, one for each frame. There is one point per line. Each point is given as the X coordinate followed by the Y coordinate, delimited by commas.

Problem 2: Segmentation/ Localization/ Other

For the cell dataset, no segmentation is provided. It's your task to do both segmentation and tracking. Note: 1) The filopodia, which cells have during migration, are long "feet" that are difficult to outline automatically. 2) Some cells spit into daughter cells. Since accurate cell segmentation is very challenging, to obtain full credit, your focus should be on the multi-object tracking task (and detecting the birth of a new cell), while your segmentation result can be relatively coarse.

You do not need to use our segmentation/detection if you would like to see the results using your own algorithms. You may use any of your code from the previous assignments and any library functions you wish.

Display the results of your tracking algorithm on top of the original images. Use different colors to show that you successfully maintain track identity. Draw lines to show the history of the flight trajectories.


Method and Implementation

Problem 1: Multiple Object Tracking

We began by adding onto the progress we made on the bat dataset in Assignment 3.

We decided to do our tracking by implementing a Kalman Filter. We did this using OpenCV.


import cv2
import numpy as np
import random

class TrackItem:
  """ A data structure to keep track of items in a frame """
  def __init__(self, initial_position, id_, death_threshold):
    """ A item needs a flight history + Kalman filter """    
    # setup Kalman filter
    self.id = id_
    self.kalman = cv2.KalmanFilter(4, 2, 0)

We also display the tracking results on top of the original images. Randomizing the colors to show that we maintain track identity, and draw lines to show the history of the flight trajectories.


# randomize color
self.color = (100 + random.randint(0, 155), 100 + random.randint(0, 155), 100 + random.randint(0, 155))

# draw
def draw_history(self, image):
  if len(self.flight_history) >= 3:
    prev = self.flight_history[1]
    prev_position = TrackItem.extract_position_from_history(prev)
    cv2.circle(image, prev_position, 2, self.color, -1)

    for i in range(2, len(self.flight_history)):
      curr = self.flight_history[i]

      curr_position = TrackItem.extract_position_from_history(curr)
      prev_position = TrackItem.extract_position_from_history(prev)

      # draw
      cv2.line(image, prev_position, curr_position, self.color, 1)

      prev = curr

We implemented our tracking using Kalman filter and Hungarian matching algorithm. We get our predictions using Kalman Filter, match our tracked objects with measurements using Hungarian algorithm, and then correct our predictions with new measurements.


def update_iteration(self, possible_measurements, image):
    tracked_items = []
    considered_item_ids = []

    # make predictions
    for item in self.spotted_items:
      if not item.terminated:
        prediction = item.predict()
        tracked_items.append(prediction)
        considered_item_ids.append(item.id)

    # build the cost matrix
    X = len(tracked_items)
    Y = len(possible_measurements)

    cost_matrix = self.threshold * np.ones((X+Y, X+Y))
    for i in range(X):
      # create the probability distribution
      mean, cov = tracked_items[i]

      measure_space_mean = self.H_t @ mean
      measure_space_cov = self.H_t @ cov @ self.H_t.T
      iv = np.linalg.inv(measure_space_cov)

      assert(measure_space_cov.shape == (2, 2))

      for j in range(Y):
        measurement = possible_measurements[j]
        m_distance = distance.mahalanobis(measurement, measure_space_mean, iv)

        cost_matrix[(i, j)] = m_distance

    # solving cost matrix
    m = Munkres()
    results = m.compute(cost_matrix)

    for result in results:
      item_num, measure_num = result
      if item_num < X:
        # an actual item
        item_id = considered_item_ids[item_num]
        if measure_num < Y:
          measurement = possible_measurements[measure_num]
        else:
          if self.tracking_bats:
            # if tracking bats, missing measurements -> missing
            measurement = None
          else:
            # if tracking cells, missing measurements are from occlusion
            # -> assign closest measurement
            scores = cost_matrix[item_num, :Y]
            closest_measure_num = np.where(scores == np.amin(scores))[0][0]
            measurement = possible_measurements[closest_measure_num]

        item = self.spotted_items[item_id]
        correction, terminated = item.correct(measurement)
        if not terminated:
          item.draw_history(image)

      elif measure_num < Y:
        # new item detected!
        measurement = possible_measurements[measure_num]
        new_item = TrackItem(measurement, self.next_track_id, self.death_threshold)
        self.next_track_id += 1
        self.spotted_items.append(new_item)

We attempted the challenge for proper handling of situations when objects touch and occlude each other by allowing for a short time window in which the tracker will rely on predicted data to trace the path until the objects no longer occlude each other. We also implemented a termination deadline, where if within n frames we cannot find new measurement for this item, we will terminate that object and stop tracking. If we detect new measurements that do not match any existing bats, we will create a new track for it.


# missing from occlusion
if self.tracking_bats:
  # if tracking bats, missing measurements -> missing
  measurement = None
else:
  # if tracking cells, missing measurements are from occlusion
  # -> assign closest measurement
  scores = cost_matrix[item_num, :Y]
  closest_measure_num = np.where(scores == np.amin(scores))[0][0]
  measurement = possible_measurements[closest_measure_num]

# code handling termination
if self.frame_missing >= self.death_threshold:
  self.terminated = True

# code handling birth
elif measure_num < Y:
  # new item detected!
  measurement = possible_measurements[measure_num]
  new_item = TrackItem(measurement, self.next_track_id, self.death_threshold)
  self.next_track_id += 1
  self.spotted_items.append(new_item)

Problem 2: Segmentation/ Localization/ Other

We began by trying the method we used on the pedestrian dataset in Assignment 3.


    diff = cv2.absdiff(cropped_og_img, cropped_img)
    gray = cv2.cvtColor(diff, cv2.COLOR_BGR2GRAY)
    blur = cv2.GaussianBlur(gray, (5,5), 0)
    _, thresh = cv2.threshold(blur, 20, 255, cv2.THRESH_BINARY)
    kernel = cv2.getStructuringElement(cv2.MORPH_RECT, (10, 10))
    cropped_dilated = cv2.dilate(thresh, kernel, iterations=1)

We then adapted our code to include the Tracker we made for Problem 1.


    count = tracker.get_num_tracks()
    tracker.update_iteration(possible_measurements, img)

We also updated our counter to reduce false updates and register cell births.


    cv2.putText(img, "Number of Cells: {}".format(count), (10, 20), cv2.FONT_HERSHEY_SIMPLEX, 1, (0, 0, 255), 1)

We cropped the image such that only the cells in the plate were being tracked and not background disturbances.


Experiments

The datasets had either very light or dark backgrounds which made it hard to add good visualization to the line tracing. We attempted to use HSV colours instead of BGR to increase line saturation, however we came accross issues such as the lines not being able to maintain the same color over time.

We also experimented with different kinematic models. At first, we only keep track of our position in our state. However, after experimenting, we have decided to keep track of BOTH position and velocity. This helps us create better predictions and better tracking overall


Results

Problem 1: Multiple Object Tracking

Grayscale Segmented

Problem 2: Segmentation/ Localization/ Other

Cells

Discussion

  1. We have successfully utilized Kalman filter and Hungarian algorithm to track objects in a frame. The simple cases where there is no occlusion works almost all the time; we can see a very coherent history path of the objects.
  2. However, we sometimes have difficulty deciding the death window time of an object. If we limit the death window, sometimes an object is occluded for too long and we lose track of it. If we extend the death window, sometimes a death object is not terminated properly and mistakenly take another measurement as itself.
  3. Deciding appropriate gating is another issue. We try to keep a relatively small area of gating for densely populated area of objects. However, sometimes when the object is too large and moving too fast, its next iteration is out of our prediction gating, and we cannot match predictions with measurements correctly.

Conclusions

We were able to create an accurate tracker that can be repurposed for many applications.


Credits and Bibliography

CS 585: Lecture 6-10 (2/11/2020 - 3/5/2020)
CS 585: Lab 5-8 (2/11/2020 - 3/5/2020)
https://docs.opencv.org/
http://www.cs.unc.edu/~welch/media/pdf/kalman_intro.pdf