GridShift: A Faster Mode-seeking Algorithm for Image Segmentation and
  Object Tracking
  In machine learning and computer vision, mean shift (MS) qualifies as one of
the most popular mode-seeking algorithms used for clustering and image
segmentation. It iteratively moves each data point to the weighted mean of its
neighborhood data points. The computational cost required to find the neighbors
of each data point is quadratic to the number of data points. Consequently, the
vanilla MS appears to be very slow for large-scale datasets. To address this
issue, we propose a mode-seeking algorithm called GridShift, with significant
speedup and principally based on MS. To accelerate, GridShift employs a
grid-based approach for neighbor search, which is linear in the number of data
points. In addition, GridShift moves the active grid cells (grid cells
associated with at least one data point) in place of data points towards the
higher density, a step that provides more speedup. The runtime of GridShift is
linear in the number of active grid cells and exponential in the number of
features. Therefore, it is ideal for large-scale low-dimensional applications
such as object tracking and image segmentation. Through extensive experiments,
we showcase the superior performance of GridShift compared to other MS-based as
well as state-of-the-art algorithms in terms of accuracy and runtime on
benchmark datasets for image segmentation. Finally, we provide a new
object-tracking algorithm based on GridShift and show promising results for
object tracking compared to CamShift and meanshift++.
