🤖 machine learning

Event Driven Clustering Algorithm

This paper presents a novel asynchronous, event-driven clustering algorithm that achieves linear time complexity and resolution-independent runtime for real-time detection of small event clusters in event camera data by leveraging spatio-temporal proximity.

Original authors: David El-Chai Ben-Ezra, Adar Tal, Daniel Brisk

Published 2026-08-06

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: David El-Chai Ben-Ezra, Adar Tal, Daniel Brisk

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to understand a bustling city, but instead of seeing a static photograph or a video recording, you only get a chaotic stream of tiny, glowing sparks. Each spark appears at a specific spot and time, flashing only when something changes—like a car turning a corner or a leaf falling. This is how "event cameras" work. Unlike regular cameras that take a picture every fraction of a second (even if nothing is happening), these special sensors act like a million tiny, independent detectives. They only shout out when they see a change in light, creating a super-fast, super-efficient stream of data that can capture motion so quick it's invisible to the human eye. This technology is a game-changer for robots and self-driving cars because it sees the world with incredible speed and clarity, even in the dark or blinding sun. However, there's a catch: this stream of sparks is messy and unorganized. To make sense of it, computers need to figure out which sparks belong together to form a single object, like a bird or a ball, without getting confused by random noise.

This is where the new research by David El-Chai Ben-Ezra, Adar Tal, and Daniel Brisk comes in. They have invented a clever, lightning-fast method to group these sparks into meaningful clusters in real-time. Think of their algorithm as a super-organized party planner who never looks back. As the sparks (events) arrive one by one, the planner instantly decides: "Does this new spark belong to the group I'm currently watching?" If it's close enough in space and time to an existing group, it joins in. If it's far away, it starts a brand new group. The magic of their method is that it doesn't need to stop and re-check the whole party list every time a new guest arrives; it makes a decision immediately and moves on. This means the computer can process millions of sparks per second without slowing down, no matter how big the camera is.

The researchers found that this "one-pass" approach is incredibly efficient, taking time that grows only linearly with the number of events. In simpler terms, if you double the number of sparks, the computer takes exactly double the time, not a million times longer. They also built in a safety net to ignore fake sparks caused by sensor noise. The algorithm waits until a group of sparks gets big enough and comes from enough different spots to be considered a real object before announcing, "Hey, we found something!" This allows the system to identify the very beginning of an object (the "root" of the cluster) almost instantly, which is crucial for robots that need to react in the blink of an eye.

In their tests, the team used data from a real event camera watching a light bulb flicker. They set their rules so that a valid group needed at least 10 sparks and to come from at least 5 different pixels. The algorithm successfully spotted the start of every flicker cycle, marking the exact moment each new pattern began. They didn't just guess; they proved mathematically that their method works in linear time and demonstrated it with real data. While they focused on finding small, localized signals, their approach offers a solid, reliable foundation for building smarter, faster vision systems that can see the world as it really happens, not just as a series of snapshots.

Technical Summary: Event Driven Clustering Algorithm

Problem Statement

Event cameras represent a paradigm shift in visual sensing, offering high dynamic range and microsecond temporal resolution by generating asynchronous streams of events rather than fixed-frame images. However, effectively processing this sparse, asynchronous data remains challenging. Existing methods often struggle to efficiently handle high-resolution, temporally ordered event streams in real-time. Specifically, there is a need for clustering algorithms that can detect small, localized signals (objects) without relying on temporal binning or revisiting past events, while maintaining computational efficiency independent of sensor resolution.

Methodology

The paper proposes a novel, asynchronous, event-driven clustering algorithm designed to detect small event clusters in real-time. The approach is grounded in a graph-theoretic interpretation of event data and operates on a single pass through the event stream.

Core Principles

The algorithm models the event stream as a directed graph where vertices are events and edges represent spatio-temporal proximity. It relies on four constant parameters:

$\delta$ : Maximum temporal distance between adjacent events in a cluster.
$d$ : Maximum spatial distance (in pixels) between adjacent events.
$n$ : Minimum number of events required for a valid cluster.
$m$ : Minimum number of distinct pixels required to support a valid cluster (to filter noise from overly sensitive pixels).

Algorithmic Process

The algorithm processes events sequentially ( $v_i = (t_i, x_i, y_i)$ ) using a set of dynamic arrays indexed by pixel coordinates to maintain state. Key data structures include:

TimeSurface: Stores the timestamp of the most recent event for each pixel.
Cluster Tracking Arrays: Store properties (start time, end time, event count, pixel count) for clusters rooted at specific pixels.
Pointer Arrays: Associate pixels with the root of the cluster they currently belong to.

The decision logic for each incoming event follows three primary conditions:

Outdated Cluster Check: If the pixel points to a cluster that has been superseded, pointers are re-initialized.
Existing Cluster Association: If the pixel points to a valid cluster and the time difference between the current event and the cluster's last event is within $\delta$ , the event is added to that cluster.
Neighborhood Association: If the pixel does not point to a cluster, the algorithm checks its $d$ $d$ -neighborhood for pixels with recent events (within $\delta$ $δ$ ).
- If a neighbor is part of an existing cluster, the current event is attached to that cluster.
- If a neighbor is not part of a cluster, a new cluster is created with the neighbor (or the current event) as the root.

Output and Filtering

The algorithm outputs a list of detected clusters, specifically identifying the root of each cluster (the initial event) as soon as the cluster meets the size ( $n$ ) and spatial support ( $m$ ) thresholds. This allows for immediate identification of cluster roots before the clustering process is fully complete. The output includes the root's coordinates, timestamps, total event count, and distinct pixel count.

Key Contributions

Linear Time Complexity: The algorithm achieves a time complexity of $\Theta(N)$ , where $N$ is the number of events. Crucially, the runtime is independent of the sensor resolution (number of pixels) and the number of clusters.
Asynchronous, Single-Pass Processing: Unlike hierarchical agglomerative methods or approaches requiring temporal binning, this method processes events online without revisiting past data, making it suitable for real-time applications.
Early Root Detection: A distinct feature is the ability to identify the root of a cluster immediately once the size threshold is exceeded, facilitating low-latency detection.
Noise Robustness: The algorithm incorporates a dual-threshold mechanism (event count and distinct pixel count) to naturally filter out spurious activity from noisy pixels.
Graph-Theoretic Formulation: The method provides a clear, principled interpretation of clustering as the construction of a polyforest (a directed acyclic graph where underlying undirected components are trees).

Results

The paper demonstrates the algorithm's efficacy using data from a prior study involving a Prophesee EVK4-HD event camera observing a 100 Hz periodic signal generated by an incandescent lamp.

Experimental Setup: The lamp was covered to create a sparse signal, resulting in only a few dozen events per period.
Parameters: The algorithm was tested with $\delta = 2$ ms, $d = 1$ , $n = 10$ , and $m = 5$ .
Outcome: The algorithm successfully identified the root of each signal period (the first positive event in each cluster), marking them accurately in a 3D visualization. This confirmed the method's ability to detect small, localized signals in noisy, real-world event streams.

Significance and Claims

The authors position this work as a simple yet powerful framework for real-time event-based clustering. The primary significance lies in its efficiency and suitability for low-latency neuromorphic vision applications. By decoupling computational cost from sensor resolution and enabling immediate root detection, the algorithm addresses critical bottlenecks in processing high-speed event data. The paper claims the method serves as a useful building block for a wide range of applications, including object detection, tracking, and SLAM, offering a balance between theoretical clarity and practical efficiency.