상향식 분리 경로 및 다중 객체 추적에의 응용

우리는 경로 연결성 사전 정보를 제공하기 위해 추가적인 \emph{리프트(들어 올린)} 간선을 도입하는 분리 경로 문제의 확장판을 제안한다. 이로 인해 도출되는 최적화 문제를 리프트된 분리 경로 문제(Lifted Disjoint Paths Problem)라고 부른다. 본 문제는 정수 다중물류 흐름 문제와 3-SAT 문제로부터의 환원을 통해 NP-난해임을 보인다. 실용적인 전역 최적화를 가능하게 하기 위해, 고품질의 선형 계획(LP) 이완을 생성하는 여러 유형의 선형 부등식을 제안한다. 또한, 제안된 선형 부등식들을 효과적으로 분리하기 위한 효율적인 커팅 평면 알고리즘을 제안한다. 리프트된 분리 경로 문제는 다중 객체 추적에 자연스럽게 적용될 수 있으며, 장거리 시간적 상호작용에 대해 우아한 수학적 형식을 제공한다. 리프트된 간선은 ID 전환을 방지하고, 사람을 재식별하는 데 도움을 준다. 본 연구에서 제안하는 리프트된 분리 경로 추적기는 입력 탐지 결과에 대해 거의 최적의 할당을 달성한다. 그 결과, MOT 챌린지의 세 가지 주요 벤치마크에서 모두 최고 성능을 기록하며, 기존 최첨단 기법들보다 크게 개선된 성능을 보였다.