응축(condensation) 알고리즘은 시각적 시퀀스 및 기타 동적 시스템에서 객체를 추적하기 위한 확률적 방법이다. 이는 입자 필터(particle filter) 계열에 속하며, 시스템 상태의 확률 분포를 가중치가 부여된 무작위 표본 집합(입자라고 함)으로 표현한다. '응축'이라는 이름은 Conditional Density Propagation의 약어로, 시간에 따라 조건부 확률 밀도를 전파하는 핵심 작동 방식을 반영한다. 이 알고리즘은 1990년대 중반에 시각적 추적을 위한 실용적인 접근 방식으로 도입되었으며, 특히 선형 역학과 가우시안 잡음을 가정하는 기존의 칼만 필터(Kalman filter)가 부적합한 복잡한 환경에서 움직이는 객체를 추적하는 데 중점을 두었다.
이 알고리즘은 재귀적 예측-갱신 주기로 작동한다. 각 시간 단계에서 이전 집합에서 가중치에 비례하는 확률로 새 입자 집합을 추출하는데, 이 과정을 재표본화(resampling) 또는 선택(selection)이라고 한다. 선택된 각 입자는 객체의 새 상태를 예측하는 운동 모델에 따라 전파되며, 종종 불확실성을 고려하기 위해 무작위 잡음이 추가된다. 마지막으로 알고리즘은 각 예측 입자가 관찰된 이미지 또는 센서 데이터와 얼마나 잘 일치하는지 측정하여 이 우도(likelihood)에 기반하여 가중치를 할당한다. 가중치가 부여된 입자 집합은 객체 상태의 사후 분포를 근사하며, 추정 위치는 일반적으로 가중 평균 또는 가장 높은 가중치를 가진 입자이다.
역사적 발전
응축 알고리즘은 1990년대에 Michael I. Jordan과 캘리포니아 대학교 버클리 캠퍼스의 동료들에 의해 개발되었다. 기초 논문인 'Condensation - Conditional Density Propagation for Visual Tracking'은 1998년에 당시 옥스퍼드 대학교와 MIT 미디어 랩에 각각 재직 중이던 Michael Isard와 Andrew Blake에 의해 출판되었다. 이 연구는 1993년 Neil Gordon, David Salmond, Adrian Smith가 도입한 부트스트랩 필터(bootstrap filter)와 순차적 중요도 재표본화 기법과 같은 초기 입자 필터링 방법을 기반으로 구축되었다. 이 알고리즘은 객체 운동이 고도로 비선형적일 수 있고 관찰 모델이 폐색 또는 배경 잡음으로 인해 다중 모드일 수 있는 시각적 추적에서 칼만 필터의 한계를 해결하기 위해 특별히 설계되었다.
알고리즘 세부 사항
응축 알고리즘은 네 가지 주요 단계로 설명할 수 있다. 첫째, 초기화: N개의 입자 집합이 초기 사전 분포에서 추출되며, 각 입자는 동일한 가중치를 가진다. 둘째, 선택: 현재 집합에서 N개의 새 입자가 가중치에 비례하는 확률로 대체 추출된다. 이 단계는 높은 우도 영역에 입자를 집중시킨다. 셋째, 예측: 선택된 각 입자는 동적 모델(예: 무작위 보행 또는 등속 모델)을 통해 전파되며, 프로세스 불확실성을 나타내기 위해 가우시안 잡음이 추가된다. 넷째, 측정 갱신: 각 예측 입자는 우도 함수를 사용하여 현재 관찰과 비교되고, 그에 따라 가중치가 갱신된다. 그런 다음 주기는 다음 프레임에 대해 반복된다.
이 알고리즘의 주요 특징은 여러 가설을 동시에 유지할 수 있는 능력이다. 입자가 사후 분포의 여러 모드에 걸쳐 퍼질 수 있기 때문에, 알고리즘은 일시적인 폐색이나 모호한 상황을 통해 객체를 추적할 수 있다. 입자 수 N은 중요한 매개변수이다. 입자가 너무 적으면 근사가 부정확하고, 너무 많으면 계산 비용이 증가한다. 일반적인 구현은 상태 차원과 관찰 모델의 복잡성에 따라 수백에서 수천 개의 입자를 사용한다.
응용 분야
응축 알고리즘은 컴퓨터 비전과 로봇 공학에서 널리 적용되었다. 주요 용도는 시각적 추적으로, 비디오 시퀀스에서 사람의 머리나 손을 추적하고, 교통 감시에서 차량을 추적하며, 관절형 객체의 자세를 추적하는 것이다. 또한 의료 영상에서 심장의 움직임을 추적하거나 증강 현실에서 카메라 자세를 추정하는 데 사용되었다. 로봇 공학에서 이 알고리즘은 입자 필터를 사용하여 로봇이 알려진 지도에서 자신의 위치를 추정하는 방법인 몬테카를로 위치 추정(Monte Carlo localization)의 기반이 된다. 이 알고리즘의 유연성은 상태 공간이 음원의 위치나 정체인 음성 인식 및 오디오 소스 분리에도 사용되게 했다.
한계 및 확장
강점에도 불구하고 응축 알고리즘은 알려진 한계가 있다. 기본 버전은 입자 퇴화(particle degeneracy) 문제를 겪는데, 몇 번의 반복 후 대부분의 입자가 무시할 수 있는 가중치를 가지게 되어 계산 노력이 낭비된다. 재표본화는 이를 완화하지만, 특히 저잡음 시나리오에서 입자 집합의 다양성을 잃는 표본 빈곤(sample impoverishment)을 초래할 수 있다. 이러한 문제를 해결하기 위해 체계적 재표본화, 보조 입자 필터, 무향 입자 필터(unscented particle filter)와 같은 다양한 확장이 제안되었다. 또한 알고리즘은 복잡한 장면에서 어려울 수 있는 신중하게 설계된 우도 함수를 필요로 한다. 실제로 입자 수와 운동 모델 매개변수의 선택은 성능에 큰 영향을 미치며, 이러한 조정은 종종 경험적으로 수행된다.
다른 방법과의 관계
응축 알고리즘은 순차적 몬테카를로 방법이라고도 알려진 더 넓은 입자 필터 클래스의 특정 사례이다. 이는 부트스트랩 필터 및 샘플링 중요도 재표본화 필터와 밀접하게 관련되어 있다. 기계 학습의 맥락에서 입자 필터는 연속 상태를 가진 은닉 마르코프 모델과 같은 상태 공간 모델과 강화 학습의 정책 평가에 사용된다. 이 알고리즘은 복잡한 확률 분포를 근사하기 위해 무작위 샘플링을 사용하는 일반적인 몬테카를로 방법과도 연결된다. 선형 가우시안 시스템에 대한 최적 추정을 제공하는 칼만 필터와 비교할 때, 응축 알고리즘은 차선이지만 훨씬 더 일반적이며 비선형 역학과 비가우시안 잡음을 처리한다. 이러한 일반성 덕분에 컴퓨터 비전 커뮤니티에서 표준 도구가 되었으며, 확률적 로봇 공학과 시각적 추적의 기초 기법으로 남아 있다.
같이 보기
- 입자 필터
- 칼만 필터
- 시각적 추적
- 몬테카를로 방법