기술 요약: 이벤트 기반 클러스터링 알고리즘

문제 정의

이벤트 카메라는 고정된 프레임 이미지가 아닌 비동기적 이벤트 스트림을 생성함으로써 높은 동적 범위와 마이크로초 단위의 시간 해상도를 제공하는 패러다임의 전환을 나타냅니다. 그러나 이 희소하고 비동기적인 데이터를 효과적으로 처리하는 것은 여전히 어려운 과제입니다. 기존 방식들은 고해상도의 시간 순서가 있는 이벤트 스트림을 실시간으로 효율적으로 처리하는 데 어려움을 겪는 경우가 많습니다. 구체적으로, 시간 빈닝(temporal binning)에 의존하거나 과거의 이벤트를 다시 방문하지 않으면서도, 센서 해상도와 무관하게 계산 효율성을 유지하며 작고 국소적인 신호(객체)를 탐지할 수 있는 클러스터링 알고리즘이 필요합니다.

방법론

본 논문은 실시간으로 작은 이벤트 클러스터를 탐지하기 위해 설계된 새로운 비동기 이벤트 기반 클터링 알고리즘을 제안합니다. 이 접근 방식은 이벤트 데이터에 대한 그래프 이론적 해석에 기초하며, 이벤트 스트림을 단 한 번의 통과(single pass)로 처리합니다.

핵심 원리

알고리즘은 이벤트를 정점(vertex)으로, 이벤트를 에지(edge)로 하는 유향 그래프(directed graph)로 모델링하며, 에지는 시공간적 근접성을 나타냅니다. 이 알고리즘은 네 가지 상수 매개변수에 의존합니다:

• $\delta$: 클러스터 내 인접한 이벤트 간의 최대 시간 거리.
• $d$: 인접한 이벤트 간의 최대 공간 거리(픽셀 단위).
• $n$: 유효한 클러스터가 되기 위해 필요한 최소 이벤트 수.
• $m$: 유효한 클러스터를 지원하기 위해 필요한 최소 서로 다른 픽셀 수(과도하게 민감한 픽셀에서 발생하는 노이즈를 필터링하기 위함).

알고리즘 프로세스

알고리즘은 픽셀 좌표로 인덱싱된 동적 배열을 사용하여 이벤트($v_i = (t_i, x_i, y_i)$)를 순차적으로 처리합니다. 주요 데이터 구조는 다음과 같습니다:

• TimeSurface: 각 픽셀에 대한 가장 최근 이벤트의 타임스탬프를 저장합니다.
• 클러스터 추적 배열(Cluster Tracking Arrays): 특정 픽셀에 뿌리를 둔 클러스터의 속성(시작 시간, 종료 시간, 이벤트 수, 픽셀 수)을 저장합니다.
• 포인터 배열(Pointer Arrays): 픽셀을 현재 속해 있는 클러스터의 루트(root)와 연결합니다.

각 입력 이벤트에 대한 결정 로직은 세 가지 주요 조건을 따릅니다:

1. 오래된 클러스터 확인: 픽셀이 이미 대체된 클러스터를 가리키는 경우, 포인터를 재초기화합니다.
2. 기존 클러스터 연관: 픽셀이 유효한 클러스터를 가리키고, 현재 이벤트와 클러스터의 마지막 이벤트 사이의 시간 차이가 $\delta$ 이내라면, 해당 이벤트를 그 클러스터에 추가합니다.
3. 이웃 연관: 픽셀이 클러스터를 가리키지 않는 경우, 알고리즘은 최근 이벤트(within $\delta$)를 가진 픽셀이 있는지 $d$-이웃을 확인합니다.
   • 이웃이 기존 클러스터의 일부인 경우, 현재 이벤트를 해당 클러스터에 부착합니다.
   • 이웃이 클러스터의 일부가 아닌 경우, 이웃(또는 현재 이벤트)을 루트로 하는 새로운 클러스터를 생성합니다.

출력 및 필터링

알고리즘은 탐지된 클러스터 목록을 출력하며, 특히 클러스터가 크기($n$)와 공간적 지원($m$) 임계값을 충족하는 즉시 각 클서터의 루트(초기 이벤트)를 식별합니다. 이를 통해 클러스터링 프로세스가 완전히 완료되기 전에도 루트를 즉각적으로 식별할 수 있습니다. 출력에는 루트의 좌표, 타임스탬프, 총 이벤트 수 및 고유 픽셀 수가 포함됩니다.

주요 기여

1. 선형 시간 복잡도: 알고-리즘은 이벤트의 수를 $N$이라 할 때 $\Theta(N)$의 시간 복잡도를 달성합니다. 결정적으로, 실행 시간은 센서 해상도(픽셀 수)나 클러스터의 수와 독립적입니다.
2. 비동기, 단일 패스 처리: 계층적 응집(hierarchical agglomerative) 방식이나 시간 빈닝을 요구하는 방식과 달리, 이 방법은 과거 데이터를 다시 방문하지 않고 온라인으로 이벤트를 처리하므로 실시간 애플리케이션에 적합합니다.
3. 조기 루트 탐지: 크기 임계값을 초과하는 즉시 클러스터의 루트를 식별할 수 있는 독특한 기능은 저지연 탐지를 용이하게 합니다.
4. 노이즈 강건성: 알고리즘은 이중 임계값 메커니즘(이벤트 수 및 고유 픽셀 수)을 통합하여 노이즈가 많은 픽셀에서 발생하는 가짜 활동을 자연스럽게 필터링합니다.
5. 그래프 이론적 정식화: 이 방법은 클러스터링을 폴리포레스트(polyforest, 무방향 하부 구성 요소가 트리인 유향 비순환 그래프) 구축으로 명확하고 원칙적으로 해석합니다.

결과

논문은 백열등에 의해 생성된 100 Hz 주기 신호를 관찰하는 Prophesee EVK4-HD 이벤트 카메라를 사용한 이전 연구의 데이터를 사용하여 알고리즘의 효능을 입증합니다.

• 실험 설정: 램프를 덮어 신호를 희소하게 만들어, 주기당 불과 수십 개의 이벤트만 발생하도록 했습니다.
• 매개변수: 알고리즘은 $\delta = 2$ ms, $d = 1$, $n = 10$, $m = 5$ 조건에서 테스트되었습니다.
• 결과: 알고리즘은 각 신호 주기의 루트(각 클러스터의 첫 번째 양의 이벤트)를 성공적으로 식별하였으며, 이를 3D 시각화에서 정확하게 표시했습니다. 이는 노이즈가 있는 실제 이벤트 스트림에서 작은 국소 신호를 탐지하는 본 방법의 능력을 확인시켜 주었습니다.

의의 및 주장

저자들은 이 작업을 실시간 이벤트 기반 클러스터링을 위한 단순하면서도 강력한 프레임워크로 규정합니다. 주요 의의는 효율성과 저지연 뉴로모픽 비전 애플리케이션에 대한 적합성에 있습니다. 계산 비용을 센서 해상도로부터 분리하고 즉각적인 루트 탐지를 가능하게 함으로써, 이 알고리즘은 고속 이벤트 데이터 처리에 있어 중요한 병목 현상을 해결합니다. 논문은 이 방법이 객체 탐지, 추적, SLAM을 포함한 광범위한 응용 분야의 유용한 빌딩 블록 역할을 할 수 있으며, 이론적 명확성과 실용적 효율성 사이의 균형을 제공한다고 주장합니다.