Mean-shift clustering

Mean-shift clustering algorithm is used to find high density clusters of events (or point) within a set of events. The dv-processing library provides an implementation of such an algorithm which is efficiently implemented for incoming streams of events from event cameras.

The algorithm can be summarized as follows:

  1. Given a set of coordinates, for each coordinate retrieve a neighborhood of events within a configured window.

  2. Calculate the mean of coordinates for the retrieved neighborhood.

  3. Shift the initial coordinates by a mode, which is a vector going from the initial point to the mean coordinate multiplied by a learning rate factor.

  4. If the mode of a vector is lower than a configured threshold, the coordinate is considered to have converged into a cluster center, otherwise repeat from step one.

_images/mean_shift_clustering.gif

An approximate visualization of a mean-shift clustering algorithm to find centers of coordinate clusters in a 2D plane.

This algorithm is useful to find event clusters that could be used as point of interest in event processing algorithms.

Sample usage

The following code sample shows the use of mean-shift clustering implementation to find and track clusters of events on simulated events.

 1#include <dv-processing/cluster/mean_shift/event_store_adaptor.hpp>
 2#include <dv-processing/core/event.hpp>
 3#include <dv-processing/data/generate.hpp>
 4#include <dv-processing/visualization/events_visualizer.hpp>
 5
 6#include <opencv2/highgui.hpp>
 7
 8int main() {
 9    // Use VGA resolution
10    const cv::Size resolution(640, 480);
11
12    // Initialize a list of clusters for synthetic data generation
13    const std::vector<dv::Point2f> clusters(
14        {dv::Point2f(100.f, 100.f), dv::Point2f(462.f, 25.f), dv::Point2f(105.f, 340.f), dv::Point2f(540.f, 420.f)});
15
16    // Generate some random events for a background
17    dv::EventStore events = dv::data::generate::uniformlyDistributedEvents(0, resolution, 10'000);
18
19    // Declare a region filter which we will use to filter out-of-bounds events in the next step
20    dv::EventRegionFilter filter(cv::Rect(0, 0, resolution.width, resolution.height));
21
22    for (const auto &cluster : clusters) {
23        // Generate a batch of normally distributed events around each of the cluster centers
24        filter.accept(dv::data::generate::normallyDistributedEvents(0, cluster, dv::Point2f(15.f, 15.f), 5'000));
25
26        // Apply region filter to the events to filter out events outside valid dimensions
27        events += filter.generateEvents();
28    }
29
30    // Initialize mean shift clustering algorithm, with initial parameters of:
31    // bandwidth = 100, this is pixel search radius around a point
32    // conv = 0.01, the search converges when the magnitude of mean-shift vector is below this value
33    // maxIter = 10000, maximum number of mean-shift update iterations
34    // numStartingPoints = 100, number of randomly selected starting points
35    dv::cluster::mean_shift::MeanShiftEventStoreAdaptor meanShift(events, 100.0f, 0.01f, 10000, 100);
36
37    // Perform the mean-shift, the algorithm returns a tuple of center coordinates, labels, count of event in
38    // the cluster, and variances of the cluster
39    auto [centers, labels, counts, variances] = meanShift.fit();
40
41    // Let's assign the cluster size to the response value of the center keypoint
42    for (int i = 0; i < centers.size(); i++) {
43        centers[i].response = static_cast<float>(counts[i]);
44    }
45
46    // Sort the estimated centers by the number of events in cluster, the values are sorted in descending order
47    std::sort(centers.begin(), centers.end(), [](const auto &a, const auto &b) {
48        return a.response > b.response;
49    });
50
51    // Choose top four center with most events; these centers should be close to initial hardcoded cluster centers
52    if (centers.size() > 4) {
53        centers.resize(4);
54    }
55
56    // Use event visualizer to generate a preview image
57    dv::visualization::EventVisualizer visualizer(resolution);
58    auto preview = visualizer.generateImage(events);
59
60    // Draw markers on each of the center coordinates
61    for (const auto &center : centers) {
62        cv::drawMarker(preview, cv::Point2f(center.pt.x(), center.pt.y()), dv::visualization::colors::red);
63    }
64
65    // Show the preview image with detected cluster centers
66    cv::namedWindow("Preview", cv::WINDOW_NORMAL);
67    cv::imshow("Preview", preview);
68    cv::waitKey();
69
70    return 0;
71}
_images/clustering_preview.png

Expected output of the mean-shift sample usage, four cluster centers marked with red crosses.