Mean Shift, Histogram Backprojection 기반의 Object Tracking

 

이번 포스트에선 객체 추적에 사용되는 방법인 Mean Shift, Histogram Backprojection에 대해 다뤄보겠습니다.

 

글의 핵심 내용은 다크 프로그래머님의 블로그를 참고했습니다. https://darkpgmr.tistory.com/64

[영상추적#1] Mean Shift 추적

 

잘못된 내용 혹은 이해가 어려운 부분이 있다면 언제든 피드백 부탁드립니다.

---

2D Histogram

이번 Object Tracking 내용을 이해하기 위해선, 가장 먼저 2D Histogram에 대해 이해해야 합니다.

히스토그램 위키피디아

 

일반적으로 우리는 머신 러닝 등에서 위의 이미지처럼 보여지는 1D Histogram에 대해 다뤘습니다.

이러한 1D Histogram은 한가지 속성에서 얻어지는 값을 기반으로 만들어집니다. 

 

예를 들어, 1D Histogram은 1채널 Gray Scale 이미지의 픽셀 값을 기반으로 하여 만들 수 있습니다.

그렇다면 2D Histogram은 어떻게 만들어낼 수 있을까요?

 

바로 RGB와 같은 2개 이상의 다른 속성을 갖는 이미지 등을 기반으로 이를 만들어낼 수 있습니다.

 

하지만 RGB 이미지를 기반으로 한 2D Histogram의 경우, 3개 색상 픽셀을 대표하기 어렵습니다.

그래서 컬러 이미지에 대한 2D Histogram은 주로, Ycrcb나 HSV 색을 주로 활용합니다.

 

실제 샘플 이미지에 대해 Histogram을 도출해보겠습니다. 이 때의 색공간은 HSV를 기반으로 합니다.

 

 

 

왼쪽의 예시 이미지를 기반으로, 2D Histogram을 도출한 경우 오른쪽과 같은 Histogram을 얻습니다.

해당 Histogram은 어떠한 의미를 담고 있을까요?

 

1D Histogram이 흑백 영상의 픽셀 값을 담고 있듯이, 2D는 Hue와 Saturation을 x, y 좌표 형태로 갖습니다.

이를 해석해본다면 입력 이미지가 갖는 Hue, Saturation 정보를 담고 있다고 할 수 있습니다.

 

이러한 Histogram에 HSV 색공간의 색을 넣어준다면 어떠한 모습을 보일까요?

 

이렇게 오른쪽의 이미지와 같이 이미지가 주로 갖고 있는 Hue 값과 Saturation 값이 나타나게 됩니다.

 

이러한 결과를 통해 2D Histogram은 H와 S 값을 x, y 좌표로 갖는다는 의미가 이해 되었을거라 생각합니다.

 

다음은 Histogram Backprojection에 대해 다뤄보겠습니다.

---

Histogram Backprojection

앞서 구해보았던 2D Histogram을 기반으로 우리는 Histogram Backprojection을 구할 수 있습니다.

 

Histogram Backprojection은 입력 이미지에 대해 특정 색상에 속할 확률을 계산합니다.

이러한 Histogram Backprojection은 Image Segmentation 등의 과제에서 활용됩니다.

 

설명으론 어려울 수 있는데, 어떻게 계산되고 활용되는지 쉽고 자세하게 다뤄보도록 하겠습니다.

 

 

앞에서 활용했었던 이미지를 기반으로, 입력 이미지와 특정 색상을 갖는 영역을 정의해보겠습니다.

정의한 영역은 Segmentation이 필요한 영역의 색상을 대표하는 이미지라고 이해해주시면 될 것 같습니다.

 

입력도 있고, 찾고자 하는 색상도 정의했으니 Histogram Backprojection을 구해주면 됩니다.

Histogram Backprojection을 구하는 방법은 특정 영역의 픽셀 값을 2D Histogram으로 만들어주어야 합니다.

 

이후 만들어진 Histogram과 Segmentation이 필요한 이미지를 함께 OpenCV 함수에 전달해주면 됩니다.

 

# RGB 2 HSV converting
original_img = cv2.cvtColor(original_img, cv2.COLOR_RGB2HSV)
img_roi = cv2.cvtColor(img_roi, cv2.COLOR_RGB2HSV)

# cal hist and normalize for cropped image
calc_roi_hist = cv2.calcHist([img_roi], [0, 1], None, [180, 256], [0, 180, 0, 256])
normalized_hist = cv2.normalize(calc_roi_hist, calc_roi_hist, 0, 255, cv2.NORM_MINMAX)

# back projection
calc_backprojection = cv2.calcBackProject([original_img], [0, 1], normalized_hist, [0, 180, 0, 256], 1)

# convolution
e_object = cv2.getStructuringElement(cv2.MORPH_ELLIPSE, (5, 5))
post_processing_bp = cv2.filter2D(calc_backprojection, -1, e_object)

# binary
threshold = 50
_, binary = cv2.threshold(post_processing_bp, threshold, 255, 0)
mask = cv2.merge((binary, binary, binary))

# visualization
original_img = cv2.imread('../Images/Sample.png')
original_img = cv2.cvtColor(original_img, cv2.COLOR_BGR2RGB)
filtered_img = cv2.bitwise_and(original_img, mask)

plt.imshow(filtered_img)

 

구해진 Backprojection을 기반으로 노이즈 제거 후 Mask를 생성한 다음 Segmentation을 진행한다면?

 

Mask를 정의하는 Threshold에 따라, 위와 같이 내가 선택한 색상과 유사한 영역만이 선택됩니다.

이렇게 OpenCV의 Backprojection을 통해 Segmentation을 간편하게 수행하는 방법을 알게되었습니다.

 

Segmentation의 전체적인 내용은 알았는데, 이것만으론 Backprojection이 어떻게 구하는지 알기 어렵습니다.

그렇다면 Backprojection은 어떻게 계산되어 구해지는 걸까요?

---

Histogram Backprojection 계산 과정

OpenCV에서 사용되는 calcBackProject()의 함수는 다음 4가지 단계로 동작합니다.

 

1. 입력 이미지와 타겟 이미지에 대해 각각 HSV 변환 후 Histogram을 계산

2. 타겟 Histogram을 입력 Histogram으로 나눈 비율 값을 마치 확률 값처럼 사용

3. 입력 이미지의 Hue와 Saturation을 가져와, Histogram에서 도출된 확률 값 팔레트에서 값을 입력

  > 아래에서 자세하게 설명 예정

4. 원형 Kernel Convolution을 통한 노이즈 제거, 패턴 강조 및 Threshold 기반의 Mask 생성

 

위에서 정리한 각각의 단계에 대해 아래에서 하나씩 다뤄보도록 하겠습니다.

 

1. 입력 이미지와 타겟 이미지에 대해 각각 HSV 변환 후 Histogram을 계산

 

첫번째 단계는 위의 이미지 결과와 같이 입력과 타겟에 대해 각각 Hue/Saturation Histogram을 계산합니다.

 

Histogram Backprojection의 핵심은 타겟의 색상과 유사한 색상에 대해 높은 확률을 부여하는 것입니다.

그렇기에 먼저 각 이미지의 색상 정보를 담는 Histogram을 만들어주어야 합니다.

 

2. 타겟 Histogram을 입력 Histogram으로 나눈 비율 값을 확률 값처럼 사용

두 Histogram 모두 같은 (180, 256) shape을 갖기에 타겟을 입력으로 나누어 비율로 구할 수 있습니다.

Histogram 비율(확률) 예시

 

구해진 비율(확률)은 위의 예시처럼 0 ~ 1 사이의 값을 갖습니다. 

높은 비율(확률)일수록, Histogram에서 가장 많이 등장한 주요 색상이라고 생각해주시면 됩니다.

 

3. 입력 이미지의 Hue와 Saturation을 가져와, Histogram에서 도출된 팔레트에서 값을 입력

Histogram Backprojection 과정 중, 가장 이해하기 어려울 수 있는 부분이라 할 수 있습니다.

 

앞서 정의한 R이라는 팔레트는 타겟 이미지의 Hue/Saturation 값을 기반으로 한 확률을 의미합니다.

 

어떠한 새로운 이미지가 입력되었을 때, 해당 이미지에 대한 Hue/Saturation 값이 있을 것입니다.

예를 들어, 300 x 300 크기의 HSV 이미지는 각 픽셀마다 Hue와 Saturation 값이 존재합니다.

 

이 때, 팔레트 R에 존재하는 Hue와 Saturation 위치의 확률 값을 가져와 픽셀마다에 할당하게 됩니다.

 

 

위의 그림에서 설명한 것처럼, 모든 픽셀에 대해 확률 값을 할당하게 됩니다.

이를 통해 만들어진 확률 맵은 타겟 Histogram과 유사한 색상일수록 큰 값을, 아닐수록 작은 값을 갖습니다.

 

 

결과적으로 위와 같은 형태의 이미지가 만들어지며, 이를 Histogram Backprojection이라 합니다.

이러한 Backprojection 이미지를 Threshold를 통해 Mask로 만들어주면 Segmentation이 가능하게 됩니다.

 

4. 원형 Kernel Convolution을 통한 패턴 강조 및 Threshold 기반의 Mask 생성

 

앞선 과정에서 만들어진 Backprojection 이미지에 대해, 원형 Filter로 Convolution 연산을 수행한 결과입니다.

 

기존 낮게 활성화된 관심 영역들이 Convolution 연산 이후, 크게 활성화 된 것을 확인할 수 있습니다.

 

만약 이러한 Convolution 연산을 수행하지 않고, Segmentation을 수행한다면?

 

 

위와 같이, 관심 영역에 크게 빈 공간이 생기게 되고, 제대로 Segmentation이 수행되지 않은 모습을 볼 수 있습니다.

 

이와 반대로, Convolution 연산을 수행한 뒤의 결과물은 아래와 같습니다.

 

우리가 보고자 하는 관심 영역을 빠진 공간 없이, 잘 나타내고 있음을 확인할 수 있습니다.

 

여기까지, Histogram과 Histogram Backprojection에 대해 다뤄보았습니다.

 

이제 이러한 정보들을 기반으로, Mean Shift 방법과 결합하여 Object를 Tracking 해보도록 하겠습니다.

---

Mean Shift Algorithm

Mean Shift는 이미지에서 이동하는 객체를 추적하기 위해 사용되는 방법 중 하나입니다.

 

앞선 Backprojection을 다시 살펴보았을 때, 이미지는 우리가 관심 있는 영역에 대해 크게 활성화 되어있습니다.

크게 활성화 된 영역이라면, Backprojection 이미지에서 큰 값을 갖는 영역이라고 할 수 있습니다.

 

Mean Shift 알고리즘은 초기 위치를 시작으로 일정 반경 이내의 중심으로 위치를 반복적으로 이동합니다.

이 때의 중심이란, 크게 활성화되어 큰 값을 갖는 영역을 의미합니다.

 

https://iphoong.tistory.com/11

 

그렇기에 Mean Shift를 사용한 Object Tracking은 Backprojection과 함께 사용됩니다.

그렇다면, 일정 반경 이내에서 어떠한 방식으로 중심을 계산하고 찾을 수 있을까요?

 

OpenCV에선 Moments를 통해 구할 수 있고, 영역 이내의 픽셀을 통해서도 직접 정의할 수 있습니다.

직접 중심을 계산하기 위해선 무게의 합, x 좌표의 무게, y 좌표의 무게를 계산해야 합니다.

 

무게의 합은 영역 내 전체 픽셀의 합으로 간단하게 정의할 수 있습니다.

또한 x 좌표의 무게는 x 좌표들과 해당하는 픽셀들을 곱해서 얻을 수 있으며, y 무게 또한 동일합니다.

 

최종 무게 중심은 (x / 전체 무게, y / 전체 무게)로 정의할 수 있습니다.

이렇게 정의된 무게 중심을 기반으로, (x, y) 위치를 지속적으로 수렴하기 전까지 변경하게 됩니다.

 

지금까지 다룬 Histogram, Backprojection, Mean Shift를 통해 Object Tracking을 구현할 수 있습니다.

다음 파트에선 Object Tracking에 대해 다뤄보겠습니다.

---

Mean Shift 기반의 Object Tracking

Histogram과 Mean Shift를 통해 Tracking을 구현하기 위해선 가장 먼저 Object를 정의해야 합니다.

 

저의 경우엔 아래 주소의 샘플 영상들에서 person-bicycle-car-detection 영상을 활용했습니다.

https://github.com/intel-iot-devkit/sample-videos?tab=readme-ov-file

GitHub - intel-iot-devkit/sample-videos: Sample videos for running inference

 

Object를 선정하는 과정에선, Background가 최대한 적게 들어가도록 객체를 정의하는 것이 좋습니다.

추적할 Object를 선정한 후엔, Object의 Histogram을 기반으로 입력 이미지에 대해 Backprojection을 구합니다.

 

 

위 이미지는 다음 Frame의 입력 영상에 대해 계산된 Histogram Backprojection의 시각화 결과입니다.

추적이 필요한 객체와 유사한 색상에 대해선 높은 값, 아닌 부분은 작은 값을 갖는 것을 알 수 있습니다.

 

또한 위 이미지는 초기 입력의 다음 Frame이기 때문에, 추적이 필요한 객체의 위치가 조금 변화하게 됩니다.

그렇다는 것은 우리가 정의한 Window(일정 반경)안의 객체의 픽셀 중심이 변화한 것을 의미합니다.

 

변화한 중심을 찾아주기 위해 Mean Shift를 사용하며, 이를 통해 Window의 좌표를 지속적으로 업데이트합니다.

이를 전체 이미지에 대해 반복적으로 수행하고, 시각화된 결과를 저장해서 영상으로 만든다면?

 

 

이런식으로 찾고자 하는 Object의 위치를 지속적으로 추적하고 있는 것을 확인할 수 있습니다.

> RGB 채널로 저장을 하지 않아서, 이미지가 비오는 날처럼 나오게 되었습니다.

 

단, 위와 같이 가장자리로 갈수록 배경이 크게 포함되는 경우에 대해선 한가지 과정을 추가해주어야 합니다.

 

# convolution kernel
e_object = cv2.getStructuringElement(cv2.MORPH_ELLIPSE, (w, h))
window = window * e_object

 

Mean Shift에 사용할 Backprojection Window에 대해 Window에 내접하는 타원형 Mask를 사용하는 것입니다.

직접적으로 Window에 대해 Mask를 곱해주는 것만으로도, 가장자리에 존재하는 Background를 억제할 수 있습니다.

제가 사용한 데이터 또한, 차의 색상과 주차장의 바닥 색이 거의 유사하여 해당 연산을 넣어주어야 했습니다.

 

이 외에도, Epanechnikov Kernel 같은 중심을 기준으로 가중치를 조절하는 커널을 사용할 수도 있습니다.

상황에 맞추거나, 결과물의 퀄리티에 따라 선택해서 적용해주면 될 것 같습니다.

 

마지막으로 한가지를 더 추가한다면, 객체의 크기에 따라 변하는 가변 Window를 사용하는 것입니다.

Mean Shift를 통해 구해진 무게 중심에서 다양한 크기의 Window를 놓고 Histogram을 계산합니다.

 

계산된 Window의 Histogram들과 추적할 객체가 담긴 타겟 이미지의 Histogram의 유사도를 측정합니다.

모든 Window에 대해 유사도를 측정한 뒤, 가장 큰 유사도를 갖는 Window를 선택하면 됩니다.

 

 

저의 경우엔, 일정한 범위 안에서 랜덤으로 변화하는 Width, Height를 사용했습니다.

조금 더 정밀하게 구현하기 위해선 정의된 여러 Box를 사용하거나 하는 등의 방법이 있습니다.

 

이렇게 Mean Shift, Histogram Backprojection을 통해 Object Tracking을 구현해보았습니다.

중간중간 어려운 개념이 있었지만, 대체로 잘 구현된 것을 볼 수 있었습니다.

---

 

이번에 다룬 Mean Shift, Histogram Backprojection을 통해 나름 성공적으로 Tracking을 수행할 수 있었습니다.

 

하지만 이러한 방법은 색상을 기반으로 하기에 추적할 객체의 색과 배경 혹은 다른 객체와의 색이 달라야 합니다.

색상이 유사한 경우 제대로 된 추적이 어려울 가능성이 높습니다.

 

이와 반대로, 추적할 객체의 색상이 독립적이고 폐쇄적인 환경에선 아주 잘 동작할 수도 있습니다.

다른 글에선 Mean Shift 이외 알고리즘 기반의 Tracking 등을 다뤄보고자 계획 중에 있습니다.

 

감사합니다.