Tracking(추적)이란?

추적은 특정 물체를 여러 프레임에 걸쳐 계속 추적하는 거다.

예를 들어, 영상에서 한 번 선택한 얼굴이나 물체가 계속 어디로 움직이는지 찾아내는 거다.

추적을 할 땐 ROI가 정해져 있다고 먼저 가정하고 시작한다.

 

---

 

Mean Shift(평균 이동)에 대해 알아보자

Mean Shift는 밀도 함수의 최대값(peak)을 찾는 방법이다.

간단히 말해, 데이터가 가장 많이 몰려 있는 중심을 찾는 과정이다.

이 알고리즘은 반복적(iterative) 방식으로 조금씩 이동하면서 밀도가 높은 곳을 향해 점점 더 가까이 가는 거다.

 

 

Mean Shift가 어떻게 작동하나?

1. 초기 위치 설정
   • 먼저, 관심 영역(ROI)을 하나 선택한다. 그림에서 파란색 원이 그 역할을 하고 있다.
     • 원 안에는 여러 데이터 포인트(Features)가 있다.
2. 중심점(무게 중심) 계산
   • 현재 원 안에 있는 모든 점들의 평균 위치(Center of Mass)를 계산한다.
     • 이 중심점이 지금 데이터가 가장 밀집된 위치를 나타낸다.
3. Mean Shift 벡터로 이동
   • 계산된 중심점으로 원을 이동
     • 그림에서 노란색 화살표가 바로 Mean Shift 벡터다. 원이 밀도가 더 높은 쪽으로 이동한다.
4. 반복(iterative) 과정
   • 이 과정을 계속 반복해서 더 이상 이동할 필요가 없을 때까지(수렴할 때까지) 진행한다.
   • 결국 밀도가 가장 높은 곳(밀도 함수의 최대값)에 도달하게 되는 거다.

 

정리하자면 Mean Shift는 데이터를 쫓아다니면서 가장 밀집된 위치를 찾아내는 방법이다. 반복적으로 무게 중심을 계산하고, 그 쪽으로 이동하는 방식이다. 

 

---

 

이제 Histogram Back-Projection(히스토그램 역투영)에 대해 알아보자

간단히 말해서, 모델 이미지에서 색 분포를 분석한 후, 그 정보를 목표 이미지(Target Image)에 투영해서 우리가 관심 있는 부분(예: 손)만 강조하는 방법이다.

이 기술은 주로 색 기반 추적이나 물체 탐지에 사용된다.

예를 들어, 동영상에서 특정 색상의 물체(손, 얼굴 등)를 계속 추적할 때 유용하다.

 

Histogram Back-Projection 과정

1. 모델 이미지에서 히스토그램 추출
   • 첫 번째로 모델 이미지에서 특정 영역(예: 손)의 색상 분포를 분석
     • 여기서는 Hue-Saturation(색상-채도) 히스토그램을 사용한다.
     • 이걸 통해 손이 어떤 색 범위를 가지고 있는지 파악한다.
2. 히스토그램 역투영(Back-Projection)
   • Target 이미지(다른 프레임 또는 사진)에서 각 픽셀이 모델 이미지의 색 분포에 얼마나 맞는지 계산한다.
     • 즉, 모델 이미지에서 뽑아낸 히스토그램과 일치하는 픽셀들을 강조하는 거다.
3. 확률 맵 생성
   • 최종적으로, 각 픽셀이 모델 이미지와 일치할 확률을 나타내는 맵을 만들어낸다.
     • 이 맵이 아래에 있는 흑백 이미지. 손과 비슷한 색상인 픽셀은 흰색으로, 그렇지 않은 픽셀은 검은색으로 표현

 

이 역투영은 실시간 추적에서 빠르고 효율적이다.

색상-채도 정보는 밝기 변화에 덜 민감하기 때문에 조명 변화에도 문제 없다.

 

---

 

이제 Mean Shift를 이용한 추적을 알아보자

이 과정은 세 단계로 나눌 수 있다.

1. 초기화(Initialization)
2. 히스토그램 역투영(Histogram Backprojection)
3. Mean Shift Localization(Mean Shift 기반 위치 조정)

 

1. 초기화(Initialization)

• 첫 번째 프레임에서 우리가 추적할 물체(예: 차)를 먼저 탐지
• 이 차의 색상 히스토그램을 계산해서 Object Model(객체 모델)로 저장해.
  • 이 히스토그램은 이 차가 가진 색 분포 정보를 나타내고, 이 정보를 바탕으로 나중에 다른 프레임에서도 비슷한 색상을 찾아 추적할 수 있다.

 

2. 히스토그램 역투영(Histogram Backprojection)

• 새로운 프레임(Target Image)에서, 우리가 저장한 모델 이미지의 색 분포와 일치하는 픽셀을 찾는다.
• Backprojection 이미지가 나오는데, 이건 목표물과 비슷한 색상을 가진 부분을 강조한 거를 말한다.
  • 흑백 이미지에서 흰색이 강조된 부분이 차와 비슷한 색상의 영역

3. Mean Shift Localization(Mean Shift 위치 조정)

• 이제 이 Backprojection 이미지에서 Mean Shift 알고리즘을 사용한다.
  밀도가 높은 곳으로 상자를 이동시키는 거다.
  • 이 과정에서 무게 중심(density mean)을 계산하고, 그 쪽으로 빨간 상자(차를 감싼 ROI)를 이동시킨다.
• 이 과정을 여러 프레임에 걸쳐 반복하면서, 차량이 이동하더라도 그 경로를 계속 따라가며 추적하는거다.

 

---

 

이제 CamShift에 대해 알아보자. Mean Shift보다 한 단계 업그레이드된 기술이다.

Mean Shift는 추적하는 물체가 커지거나 작아져도 탐색 창 크기가 고정돼 있어서 유연한 추적이 어렵다.

근데 이제 CamShift는 물체 크기에 따라 탐색 창의 크기를 조절할 수 있는 기능이 추가된 거다.

그래서 물체가 움직이거나 커졌다/작아져도 잘 따라간다.

 

---

이제 Optical Flow(광류)에 대해 알아보자.

Optical Flow는 이미지에서 밝기 패턴의 겉보기 움직임을 분석하는 거다.

즉, 연속된 프레임(영상의 각 순간) 사이에서 픽셀의 움직임을 추적하는 거다.

마치 두 프레임 사이에서 물체가 어떻게 이동했는지를 알아내는 거다.

 

 

빨간 점이 각 프레임에서 점점 오른쪽 아래로 움직이고 있는 것을 볼 수 있다.

이 움직임을 Δx와 Δy로 표현할 수 있다. (각 프레임에서 픽셀이 이동한 거리)

 

Optical Flow의 대표적인 방법에 KLT(Kanade-Lucas-Tomasi) 알고리즘이 있다.

이 알고리즘은 연속된 프레임 사이에서 픽셀의 움직임을 추적하는 데 유용하다.

주로 특징점(feature point)을 추적하는데 사용된다.

예를 들어, 동영상에서 물체의 코너나 엣지 같은 중요한 점을 골라 그 점들이 어떻게 움직이는지를 추적한다.

 

KLT 알고리즘의 주요 가정으로는

연속된 프레임 사이에서 같은 물체의 픽셀은 밝기(intensity)가 변하지 않는다고 가정한다.

I(x,y,t)=I(x+Δx,y+Δy,t+Δt)

즉, 특정 시간 t에 픽셀의 값은, 시간이 조금 지난 후에도 동일한 위치에서 유지된다고 보는 거다.

 

정리하자면 KLT 알고리즘은 특징점의 움직임을 추적하기 위해 연속된 프레임 간의 픽셀 이동을 계산하는 알고리즘이다.

Optical Flow 방정식을 사용해, 각 특징점이 어떻게 이동했는지 계산하고 추적하는 거다.

 

다만, KLT 알고리즘은 작은 움직임을 잘 추적하지만, 큰 움직임에는 약하다.

예를 들어, 프레임 간 물체가 멀리 이동하면, 기존 KLT는 이 차이를 제대로 잡지 못한다.

그래서 등장한 게 바로 Image Pyramid(이미지 피라미드)다.

 

이미지 피라미드는 원본 이미지를 여러 크기로 축소한 버전들로 쌓아 올린 구조를 말한다.

상위 레벨일수록 이미지가 작아지고, 하위 레벨일수록 원본 크기에 가깝다.

이렇게 여러 해상도로 이미지를 만들어두면, 큰 움직임도 작은 이미지에서 쉽게 추적할 수 있다.

 

Pyramid KLT의 동작 원리

1. 피라미드의 최상단(작은 이미지)부터 시작
   • 상위 레벨에서는 이미지가 작기 때문에 큰 움직임도 상대적으로 작게 보이게 된다.
     • 예를 들어, 물체가 20픽셀 움직였다면, 작은 해상도에선 그 차이가 줄어든다.
2. 작은 이미지에서 KLT 알고리즘 수행
   • 최상단 이미지에서 KLT 알고리즘으로 픽셀의 움직임을 계산한다.
3. 결과를 한 단계 아래로 내려서 보정
   • 한 레벨 아래로 이동하면서, 이전 레벨에서 계산한 움직임을 warp(왜곡)하고 업샘플링(확대)한다.
   • 이렇게 점진적으로 원본 이미지 크기로 내려오면서 움직임을 더 정밀하게 조정한다.
4. 최종 결과
   • 원본 해상도에 도달했을 때, 큰 움직임과 작은 움직임을 모두 정확히 추적할 수 있게 된다.