기술 요약: Tetris – 효율적이고 고충실도 비디오 객체 추적을 위한 타일 수준 샘플링

1. 문제 제기

Tetris 가 해결하는 핵심 과제는 **추적 물질화 (track materialization)**의 높은 계산 비용입니다. 이는 원시 비디오를 하류 분석 (예: 계수, 검색, 운동 분석) 을 위해 재사용 가능한 객체 추적 데이터로 변환하는 과정입니다. 현대의 탐지 기반 추적 (tracking-by-detection) 파이프라인에서 객체 탐지기는 실행 시간의 99.4~99.9% 를 소비합니다. 기존 시스템들은 **시간적 프레임 샘플링 (프레임 건너뛰기)**이나 **공간적 가지치기 (관심 영역, ROI 의 직사각형 자르기)**를 통해 이 비용을 줄이려 시도했으나, 이러한 접근법은 다음과 같은 중대한 한계를 겪습니다:

• 시간적 샘플링: 정밀한 궤적 재구성에 필요한 프레임 간 운동을 소거하여, 추적 단편화 또는 신원 전환 (identity switches) 을 초래합니다.
• 직사각형 ROI: 대각선 차량 경로와 같은 직사각형이 아닌 관련 영역을 밀착하여 감싸지 못하므로, 탐지기가 많은 양의 관련 없는 배경 픽셀을 처리하도록 강요합니다.

저자들은 정지 카메라 (stationary camera) 배포 (교통 및 감시에서 일반적) 가 기존 연구가 완전히 활용하지 못한 고유한 최적화 기회를 제공한다고 관찰합니다:

1. 공간적 무관성: 프레임당 공간 영역의 평균 94.5% 에 관심 객체가 포함되지 않습니다.
2. 공간적으로 변하는 샘플링 요구사항: 지역별 운동 패턴에 따라 서로 다른 영역이 다른 샘플링 속도를 견딜 수 있습니다 (예: 교차로에서 가속하는 차량은 정속도로 빠져나가는 차량보다 더 높은 샘플링이 필요합니다).
3. 밀착된 직사각형이 아닌 클러스터링: 관련 영역은 연결된 직사각형이 아닌 형태를 형성합니다; 축 정렬 바운딩 박스는 실제 관련 콘텐츠보다 40% 더 넓은 영역을 감쌉니다.

2. 방법론

Tetris 는 타일 기반 폴리노미노 (polyomino) 데이터 모델과 비디오 프레임을 정사각형 타일 그리드로 분해하는 실행 엔진을 도입합니다. 이는 사용자가 제공한 객체 탐지기와 추적기보다 상류 (upstream) 에서 세 가지 최적화된 연산자를 통해 파이프라인을 운영합니다:

A. 데이터 모델: 타일과 폴리노미노

• 타일: 각 프레임은 $T_S \times T_S$ 픽셀 그리드로 나뉩니다. 타일은 관련 (객체 포함) 또는 **무관 (배경)**으로 분류됩니다.
• 폴리노미노: 연결된 관련 타일은 **폴리노미노 (인접한 정사각형으로 형성된 임의의 2 차원 형태)**로 그룹화됩니다. 이를 통해 시스템은 직사각형 ROI 의 비효율성을 피하고 여러 타일에 걸쳐 있는 객체를 분할 없이 처리할 수 있습니다.

B. 실행 파이프라인

시스템은 탐지기 전에 세 가지 연산자를 실행합니다:

1. 관련성 분류: 경량 분류기 (ShuffleNet 기반) 가 각 타일의 관련성을 예측합니다. 기존 프록시 모델과 달리, 다음 세 가지 입력에 기반합니다:
   • RGB 타일 이미지.
   • 프레임 차이 이미지 (운동 포착).
   • 타일 위치 (차선이나 하늘과 같은 안정적인 장면 사전 지식 포착).
   • 출력: 관련 폴리노미노 집합.
2. 폴리노미노 가지치기 (ILP): 전체 프레임을 건너뛰는 대신, Tetris 는 학습된 최대 타일 샘플링 간격에 따라 특정 폴리노미노를 건너뜁니다.
   • 간격 학습: 일회성 훈련 단계에서 시스템은 다양한 샘플링 간격 ($\gamma \in \{1, 2, 4, 8, 16\}$) 에서 각 타일의 경험적 추적 실패율을 측정합니다.
   • 최적화: 사용자가 지정한 추적 실패율 허용치 $\bar{M}$에 대해, 시스템은 최대 간격 행렬 $\bar{G}_{\bar{M}}$을 유도합니다. 그런 다음 **정수 선형 계획법 (ILP)**을 구성하여 처리할 폴리노미노 부분집합을 선택합니다. 이는 각 타일이 특정 간격 제약을 만족할 만큼 충분히 자주 샘플링되도록 하면서 처리되는 타일의 총 수를 최소화합니다.
3. 폴리노미노 패킹: 생존한 폴리노미노 (서로 다른 프레임에서 나올 수 있음) 는 First-Fit-Descending (FFD) 휴리스틱을 사용하여 고정 크기의 직사각형 캔버스에 패킹됩니다. 이는 원래 객체 크기를 유지하면서 탐지기 호출 횟수 ($|C|$) 를 최소화합니다.

C. 런타임 아티팩트와 파레토 프론티어

전체 데이터셋을 처리하기 전에 Tetris 는 일회성 준비 단계를 수행합니다:

• 사용자의 탐지기에 특화된 관련성 분류기를 훈련합니다.
• 최대 타일 샘플링 간격을 학습합니다.
• 시스템 구성 (추적 실패율 허용치 $\bar{M}$, 관련성 임계값 $T_r$, 전체 프레임 샘플링률 $s$ 포함) 을 스윕하여 처리량 - 정확도 트레이드오프의 파레토 프론티어를 생성합니다.
• 사용자는 처리량 또는 정확도 요구사항에 따라 운영 지점 (구성) 을 선택하며, 실행 엔진은 이를 나머지 비디오에 적용합니다.

3. 주요 기여

1. 타일 기반 폴리노미노 데이터 모델: 정밀한 시공간 가지치기를 가능하게 하는 새로운 추상화로, 직사각형 ROI 접근법보다 관련 없는 타일을 건너뛰고 직사각형이 아닌 객체 형태를 더 효율적으로 처리할 수 있게 합니다.
2. 최대 타일 샘플링 간격 학습: 타일별 간격 할당에 대한 지수적 탐색을 스칼라 추적 실패율 허용치에 대한 1 차원 스윕으로 변환하는 방법입니다. 이를 통해 ILP 가지치기기가 경험적으로 지역 운동 패턴에 샘플링 밀도를 적응시킬 수 있습니다.
3. 실행 엔진: 특정 탐지기나 추적기에 구애받지 않고 추적 충실도를 희생하지 않으면서 탐지기 호출을 줄이는 세 연산자 파이프라인 (분류, 가지치기, 패킹).

4. 실험 결과

저자들은 다양한 교통 시나리오를 포괄하는 7 개의 정지 비디오 데이터셋 (CalDoT, Amsterdam, 새로운 B3D 데이터셋 포함) 에서 Tetris 를 평가했습니다.

• 정확도 vs 처리량: 전체 프레임, 모든 프레임을 참조하는 파이프라인 대비 5% HOTA(고차 추적 정확도) 손실 범위에서:
  • Tetris 는 모든 7 개 데이터셋에서 5% 범위를 유지합니다.
  • 기존 시스템 (OTIF, LEAP) 은 7 개 중 3 개 데이터셋에서 이 범위를 초과합니다.
  • Tetris 는 이 정확도 수준에서 기존 시스템보다 1.5 배에서 17.4 배 더 높은 처리량을 달성합니다.
  • Tetris 는 참조 파이프라인보다 4.7 배에서 68.8 배 더 높은 처리량을 달성합니다.
• 더 높은 허용치: 10% HOTA 손실 범위에서 Tetris 는 기존 시스템보다 최대 24.7 배, 참조 파이프라인보다 91.2 배 더 높은 처리량을 달성합니다.
• 절대성 연구 (Ablation Studies):
  • 분류기에 프레임 차이 및 위치 입력을 추가한 결과 F1 점수가 평균 1.26% 향상되었습니다.
  • 패킹 알고리즘은 평균 패킹 효율 88.93% (최대 99.62%) 를 달성하여 캔버스 활용의 효율성을 입증했습니다.
  • 간격 학습을 위한 1 차원 허용치 스윕은 포괄적인 타일별 탐색의 파레토 프론티어 위에 있거나 그 근처에 있는 것으로 확인되어 휴리스틱의 효율성을 검증했습니다.

5. 중요성과 주장

이 논문은 Tetris 가 거친 시간적 샘플링과 직사각형 공간 가지치기를 넘어선 효율적인 비디오 분석의 중요한 발전이라고 주장합니다. 정지 카메라의 공간적 안정성을 활용함으로써 Tetris 는 상당히 감소된 계산 비용으로 **고충실도 추적 (정밀한 궤적)**을 달성합니다.

저자들은 그들의 접근 방식이 교통 모니터링 및 감시 분야의 정지 카메라 배포에 특히 효과적이라고 강조하며, 처리량과 추적 정확도의 균형을 맞추는 데 있어 기존 최첨단 시스템 (OTIF 및 LEAP) 보다 일관되게 우수하다고 주장합니다. 시스템이 지역 운동 패턴을 학습하고 적응할 수 있는 능력은 데이터를 공격적으로 가지치기 하더라도 높은 충실도를 유지하게 하며, 이는 균일 샘플링 전략이 lacking 한 능력입니다.

한계점: 현재 시스템은 정지 카메라라는 가정에 의존합니다. 공간적 패턴이 시간에 따라 변하는 이동 카메라로 이러한 타일 수준의 최적화를 확장하는 것은 향후 연구 과제로 식별되었습니다.