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++.
Code (0)
등록된 구현이 없습니다.
Tasks
Image SegmentationObject TrackingSegmentationSemantic SegmentationSimilar Papers 제목 키워드 기반
MeanShift++: Extremely Fast Mode-Seeking With Applications to Segmentation and Object Tracking
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…
ClusteringDensity EstimationImage SegmentationObject Tracking+1FSNet: Feasibility-Seeking Neural Network for Constrained Optimization with Guarantees
Efficiently solving constrained optimization problems is crucial for numerous real-world applications, yet traditional solvers are often computationally prohibitive for real-time use. Machine learning-based approaches ha…
Mode-Seeking on Hypergraphs for Robust Geometric Model Fitting
In this paper, we propose a novel geometric model fitting method, called Mode-Seeking on Hypergraphs (MSH),to deal with multi-structure data even in the presence of severe outliers. The proposed method formulates geometr…
Fast kNN mode seeking clustering applied to active learning
A significantly faster algorithm is presented for the original kNN mode seeking procedure. It has the advantages over the well-known mean shift algorithm that it is feasible in high-dimensional vector spaces and results …
Active LearningClusteringGeneral ClassificationBinarized Mode Seeking for Scalable Visual Pattern Discovery
This paper studies visual pattern discovery in large-scale image collections via binarized mode seeking, where images can only be represented as binary codes for efficient storage and computation. We address this problem…