MeanShift++: Extremely Fast Mode-Seeking With Applications to Segmentation and Object Tracking

• URL: http://arxiv.org/abs/2104.00303v1
• Date: Thu, 1 Apr 2021 07:14:11 GMT
• Title: MeanShift++: Extremely Fast Mode-Seeking With Applications to Segmentation and Object Tracking
• Authors: Jennifer Jang, Heinrich Jiang
• Abstract summary: MeanShift is a popular mode-seeking clustering algorithm used in a wide range of applications in machine learning. We propose MeanShift++, which uses a grid-based approach to speed up the mean shift step. The runtime is linear in the number of points and exponential in dimension, which makes MeanShift++ ideal on low-dimensional applications.
• Score: 40.662116703422846
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: MeanShift is a popular mode-seeking clustering algorithm used in a wide range of applications in machine learning. However, it is known to be prohibitively slow, with quadratic runtime per iteration. We propose MeanShift++, an extremely fast mode-seeking algorithm based on MeanShift that uses a grid-based approach to speed up the mean shift step, replacing the computationally expensive neighbors search with a density-weighted mean of adjacent grid cells. In addition, we show that this grid-based technique for density estimation comes with theoretical guarantees. The runtime is linear in the number of points and exponential in dimension, which makes MeanShift++ ideal on low-dimensional applications such as image segmentation and object tracking. We provide extensive experimental analysis showing that MeanShift++ can be more than 10,000x faster than MeanShift with competitive clustering results on benchmark datasets and nearly identical image segmentations as MeanShift. Finally, we show promising results for object tracking.

Related papers

• RSC: Accelerating Graph Neural Networks Training via Randomized Sparse Computations [56.59168541623729]
  Training graph neural networks (GNNs) is time consuming because sparse graph-based operations are hard to be accelerated by hardware. We explore trading off the computational precision to reduce the time complexity via sampling-based approximation. We propose Randomized Sparse Computation, which for the first time demonstrate the potential of training GNNs with approximated operations.
  arXiv  Detail & Related papers  (2022-10-19T17:25:33Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  We propose a class of novel distributed Adam-type algorithms (emphi.e., SketchedAMSGrad) utilizing sketching. Our new algorithm achieves a fast convergence rate of $O(frac1sqrtnT + frac1(k/d)2 T)$ with the communication cost of $O(k log(d))$ at each iteration.
  arXiv  Detail & Related papers  (2022-10-14T01:42:05Z)
• Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
  Person Re-Identification (ReID) matches pedestrians across disjoint cameras. Existing ReID methods adopting real-value feature descriptors have achieved high accuracy, but they are low in efficiency due to the slow Euclidean distance computation. We propose a novel Sub-space Consistency Regularization (SCR) algorithm that can speed up the ReID procedure by 0.25$ times.
  arXiv  Detail & Related papers  (2022-07-13T02:44:05Z)
• Towards Real-Time Visual Tracking with Graded Color-names Features [10.475679500780574]
  MeanShift algorithm has been widely used in tracking tasks because of its simplicity and efficiency. Traditional MeanShift algorithm needs to label the initial region of the target, which reduces the applicability of the algorithm. We develop a tracking method that combines the background models and the graded features of color-names under the MeanShift framework.
  arXiv  Detail & Related papers  (2022-06-17T11:38:37Z)
• GridShift: A Faster Mode-seeking Algorithm for Image Segmentation and Object Tracking [22.899276998185716]
  Mean shift (MS) is a popular mode-seeking algorithm for clustering and image segmentation. GridShift employs a grid-based approach for neighbor search, which is linear in the number of data points. The runtime of GridShift is linear in the number of active grid cells and exponential in the number of features.
  arXiv  Detail & Related papers  (2022-06-05T15:08:34Z)
• GPU-accelerated Faster Mean Shift with euclidean distance metrics [1.3507758562554621]
  Mean-shift algorithm is widely used to solve clustering problems. In previous research, we proposed a novel GPU-accelerated Faster Mean-shift algorithm. In this study, we extend and improve the previous algorithm to handle Euclidean distance metrics.
  arXiv  Detail & Related papers  (2021-12-27T20:18:24Z)
• VersaGNN: a Versatile accelerator for Graph neural networks [81.1667080640009]
  We propose textitVersaGNN, an ultra-efficient, systolic-array-based versatile hardware accelerator. textitVersaGNN achieves on average 3712$times$ speedup with 1301.25$times$ energy reduction on CPU, and 35.4$times$ speedup with 17.66$times$ energy reduction on GPU.
  arXiv  Detail & Related papers  (2021-05-04T04:10:48Z)
• Gradient Coding with Dynamic Clustering for Straggler-Tolerant Distributed Learning [55.052517095437]
  gradient descent (GD) is widely employed to parallelize the learning task by distributing the dataset across multiple workers. A significant performance bottleneck for the per-iteration completion time in distributed synchronous GD is $straggling$ workers. Coded distributed techniques have been introduced recently to mitigate stragglers and to speed up GD iterations by assigning redundant computations to workers. We propose a novel dynamic GC scheme, which assigns redundant data to workers to acquire the flexibility to choose from among a set of possible codes depending on the past straggling behavior.
  arXiv  Detail & Related papers  (2021-03-01T18:51:29Z)
• Faster Mean-shift: GPU-accelerated clustering for cosine embedding-based cell segmentation and tracking [12.60841328582138]
  We propose a novel Faster Mean-shift algorithm, which tackles the computational bottleneck of embedding based cell segmentation and tracking. The proposed Faster Mean-shift algorithm achieved 7-10 times speedup compared to the state-of-the-art embedding based cell instance segmentation and tracking algorithm. Our Faster Mean-shift algorithm also achieved the highest computational speed compared to other GPU benchmarks with optimized memory consumption.
  arXiv  Detail & Related papers  (2020-07-28T14:52:51Z)
• A Study of Performance of Optimal Transport [16.847501106437534]
  We show that network simplex and augmenting path based algorithms can consistently outperform numerical matrix-scaling based methods. We present a new algorithm that improves upon the classical Kuhn-Munkres algorithm.
  arXiv  Detail & Related papers  (2020-05-03T20:37:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.