2.1 CAM-shift

CAM-shift 알고리즘은 1998년 Gary R. Bradski에 의해 개발되었다. CAM-shift 알고리즘은 Mean-shift 알고리즘과 같이 색상의 밀도 중심을 추적하는 알고리즘이다. Mean-shift의 단점인 탐색 윈도우의 Scale 불변으로 인해 객체의 크기가 축소되거나 확장하게 되면 추적 대상의 색상이 차지하는 비율이 달라져 추적하고자 하는 대상이 아닌 배경이나 다른 이동 객체를 추적하는 문제점을 개선하기 위해 CAM-shift 알고리즘이 개발되었다. CAM-shift 알고리즘은 추적하는 객체의 크기 변화에 따라 탐색 윈도우의 크기를 조절하여 지속적으로 추적할 수 있게 개선된 알고리즘이다^[6-7].

영상에서 추적하고자 하는 객체를 탐색 윈도우로 지정하고 탐색 윈도우 내에서 $x,\: y$의 픽셀 위치 확률 값을 $I(x,\:y)$이라 하면 초기 모멘트(zeroth moment)는 식(1)로 구할 수 있다^[7].

식(1)의 $M_{00}$는 초기 모멘트이다. 그 다음 $x,\: y$의 첫 번째 모멘트는 식(2)로 찾을 수 있다.

탐색 윈도우의 중심 $x_{c},\: y_{c}$의 위치는 식(3)을 통하여 구할 수 있다.

Mean-shift의 출력 결과는 CAM-shift의 입력 결과로 사용이 된다. 다음 식(4)를 이용하여 두 번째 모멘트를 구할 수 있다.

탐색 윈도우의 너비($l$)와 길이($h$)를 구하기 위해서 너비와 길이 식의 구성 요소를 첫 번째 모멘트, 탐색 윈도우 중심 $x_{c},\: y_{c}$값 과 두 번째 모멘트를 이용하여 식(5), (6), (7)을 통해 구할 수 있다.

식(5), (6), (7)을 이용하여 탐색 윈도우의 너비와 길이를 구하는 식은 식(8), (9)와 같다.

식(8)에서 $l$은 너비이고 식(9)의 $h$는 길이를 나타낸다. 본 논문에서는 식(8), (9)를 이용하여 탐색 윈도우의 너비와 길이를 구한다.

2.2 CAM-shift의 문제점 분석

CAM-shift의 문제점은 색상 밀도 중심을 추적하는 것으로 인해 유사한 색상의 배경이나 다른 이동 객체와 겹침이 발생 시 또는 탐색 윈도우 지정 시 다중 색상이 탐색 윈도우 내부에 있을 경우 탐색 윈도우가 확장하여 추적하고자 하는 객체를 정확히 추적할 수 없는 문제점이 있다. 그림 1은 상기 문제로 인해 탐색 윈도우가 확장 되는 것을 나태 내는 그림이다.

그림 1-a, b는 탐색 윈도우 내부에 다중 색상이 검출되어 탐색 윈도우가 확장되는 것을 나타낸다. 1-c, d는 유사한 색상의 이동객체와 겹침이 발생되어 탐색 윈도우가 확장되는 것을 나타내는 그림이다.

4.1 객체 탐색 윈도우 지정

CAM-shift의 문제점인 추적하고자하는 객체의 색상이 다중 색상일 경우 지속적으로 추적에 어려움이 있고 유사한 색상의 배경 및 다른 이동 객체와 겹침 발생으로 인한 탐색 윈도우 확장을 제어하기 위해 CAM-shift를 입력 영상에 바로 적용하지 않고 전처리 단계를 거친다. 우선 입력 영상에서 추적하고자 하는 객체를 지정하기 위해 기존의 CAM-shift에서 사용하는 방법으로 직접 추적하고자 하는 객체를 지정한다. 그림 3은 탐색 윈도우 지정 결과를 나타낸다.

그림 3는 입력된 영상에서 추적하고자 하는 객체에 탐색 윈도우를 지정하는 과정을 나타내는 그림이다. 그림 3-a는 입력된 영상이고, 3-b는 3-a의 입력 영상으로부터 추적하고자 하는 객체에 탐색 윈도우를 지정한 결과를 나타낸 그림이다.

탐색 윈도우 지정 후 추적하고자하는 객체의 상체와 하체의 색상이 다를 경우를 위해 인체 비율 모델을 사용하여 탐색 윈도우 내부를 상체와 하체로 나누어 각각 다른 객체로 인식하게 한다^[9-10]. 인체 비율 모델은 그림 4와 같다.

그림 4는 인체 비율 모델의 그림이다. 인체 비율은 사람의 신장을 H라고 하였을 때 머리를 길이를 기준으로 7~8등분으로 나눌 수 있다. 본 논문에서는 인체를 7등분이라고 가정하고 상체와 하체를 나누었다. 상체를 전체 신장의 $2/7$으로 측정할 수 있고 하체는 $4/7$로 측정할 수 있다.

상체와 하체를 분할하는 식은 식(8)의 $l$을 이용하여 구할 수 있다. 상체와 하체를 나누는 식은 식(10)과 같다.

식(10)의 $Upper$는 상체를 의미한다. 탐색 윈도우는 머리 부분을 포함하지 않으므로 탐색 윈도우의 길이인 $l$을 전체를 6 등분으로 나누고 인체 비율 모델을 이용하여 상체 부분을 구해주는 식이다. $Lower$는 하체를 의미한다. 하체 부분을 구해주는 식으로 탐색 윈도우길이 $l$에서 상체부분인 $Upper$를 빼주어 하체 부분만 구한다.

4.2 탐색 윈도우 내부 특징점 추출

상체와 하체를 나눈 탐색 윈도우 내부에서 배경과 추적 객체를 분리하기 위해 추적 객체만의 특징점이 필요하다. 이 특징점은 탐색 윈도우 확장 제어에 사용된다. 특징점 추출은 해리스 코너 알고리즘을 이용한다. 우선 상체와 하체 각각 해리스 코너 특징점을 추출한다. 해리스 코너 특징점을 추출하는 식은 식(11), (12)와 같다^[11].

식(11)에서 $I_{x},\: I_{y}$는 이미지 픽셀 $(x,\: y)$에서 $x$방향, $y$방향의 편미분 값이고, $w(x,\: y)$는 윈도우 함수 이며 직사각형 커널 및 가우시안 커널이 사용된다. 행렬식 $M$의 Eigen Value를 $\lambda_{1},\:\lambda_{2}$라 하면 코너 검출식은 식(12)와 같다.

$\det(M)=\lambda_{1}\lambda_{2}$를 의미하고, $trace(M)=\lambda_{1}+\lambda_{2}$이다. $R$의 수식의 결과 값은 $R > 0 : corner$, $R < 0 : ed\ge$, $|R|$ 값이 매우 작은 값이면 평면을 의미한다. 본 논문에서는 $R > 0$ 값인 코너를 추출한다.

하지만 코너 특징점을 추출하면 추적하고자하는 객체의 특징점 뿐만 아니라 추적 객체 주변 배경의 코너점도 같이 추출되어 특징점으로서의 신뢰성이 떨어진다. 그 점을 보완하기 위해 지속적으로 상체와 하체 각각의 컬러 히스토그램을 추출하여 코너점과 컬러 히스토그램의 픽셀을 비교하여 추적하고자 하는 추적 객체의 상체와 하체의 최종 특징점을 결정한다^[12].

그림 5은 코너 특징점과 컬러 히스토그램의 픽셀 비교를 통한 추적 객체의 최종 특징점 판별을 나타내는 그림이다. 5-a의 그림은 상체 탐색 윈도우 내부에서 코너점을 추출한 결과를 나타내고, 5-b는 하체 탐색 윈도우 내부에서 코너점을 추출한 결과를 나타낸다. 5-c, d는 상체와 하체에서 추출한 컬러 히스토그램과 코너 특징점의 픽셀을 비교하여 최종으로 얻은 특징점의 결과를 파란색과 초록색으로 표시한 것을 나타낸다.

4.3 RANSAC을 통한 탐색 윈도우 제어

CAM-shift는 색상의 밀도 중심을 추적하는 특성상 추적하고자하는 객체와 유사한 색상의 배경 및 다른 이동 객체로 인해 탐색 윈도우가 확장을 하여 추적하고자하는 객체를 추적하기 어려워진다. 이점을 위해 탐색 윈도우 확장 제어가 필요하다. 우선 제안하는 탐색 윈도우의 확장 판단은 객체의 상체와 하체의 탐색 윈도우가 겹침이 발생 했을 시 탐색 윈도우 확장이라고 판단한다. 탐색 윈도우의 확장 판단의 예를 그림 6로 설명한다.

그림 6은 탐색 윈도우 확장 판단을 나타내는 그림이다. 6-a는 유사한 색상의 객체가 추적 객체와 겹침 발생 전이라 상체와 하체의 탐색 윈도우가 확장하지 않아 탐색 윈도우끼리 겹침이 발생하지 않으므로 탐색 윈도우 확장이라고 판단하지 않은 것을 나타내고, 6-b는 유사한 색상의 객체가 겹침이 발생하여 상체의 탐색 윈도우가 확장하여 하체 탐색 윈도우와 겹침이 발생하여 탐색 윈도우 확장이라 판단한다.

탐색 윈도우가 확장하는 것을 제어하기 위해 모델 예측 알고리즘을 사용한다. 모델 예측 알고리즘은 정확성이 중요하다. 하지만 측정된 원본 데이터 중에 노이즈(Noise) 즉 거짓정보(Outlier)가 포함되어 있다. 이러한 거짓정보는 모델을 정확히 예측하는 것을 방해한다. 이러한 거짓정보를 제거하기 위해 Inlier와 Outlier 분류에 강한 RANSAC 알고리즘을 사용한다. 일반적인 모델 예측 알고리즘은 많은 데이터를 사용하여 모델 예측율을 높인다. 하지만 RANSAC 알고리즘은 초기 데이터를 최소로 이용하고 일관된 데이터의 집합을 확장시켜 나아가면서 주어진 원본 데이터에서 반복적으로 일부를 임의로 선택하는 과정을 반복하여 최적의 모델을 예측하는 프로시져(Procedure) 형태를 가지는 알고리즘이다^[13]. 추적 객체의 상체와 하체 탐색 윈도우에서 각각 구한 최종 특징점을 RANSAC의 데이터로 사용한다. Inlier와 Outlier를 분류하여 지속적으로 Inlier를 중심으로 Ellipse Fitting을 하여 새로운 탐색 윈도우를 만들어 주어 겹침이 발생하는 상황에서 탐색 윈도우의 확장을 제어하여 추적하고자 하는 객체를 지속 적으로 추적할 수 있게 한다.

탐색 윈도우를 RANSAC 알고리즘을 통해 제어하기 위해 우선 타원을 모델링 하여야 한다. 타원 모델링 식은 식(13)과 같다^[13-15].

식(13)는 타원을 모델링하기 위한 타원 방정식이다. 상기 식(13)에서 $n$개의 데이터 $(x_{1},\: y_{1}),\:(x_{2},\: y_{2}),\:\cdots ,\:(x_{n},\: y_{n})$를 대입하여 만들어지는 식을 행렬로 표시하면 식(14)와 같다. $n$개의 데이터는 최종으로 추출한 객체의 특징점을 사용하였다.

식(14)는 $n$개의 데이터 $(x_{1},\: y_{1}),\:(x_{2},\: y_{2}),\:\cdots ,\:(x_{n},\: y_{n})$를 대입하여 만들어지는 식을 행렬로 표시한 것이다. 본 논문에서는 데이터의 개수를 최소 6개로 지정하였다. 상기 식(14)는 $Ax = 0$과 같이 표현되고, $x = 0$가 아닌 다른 해는 SVD(singular value decomposition)로 분해하여 구할 수 있다. SVD는 행렬을 대각행렬 D와 두 개의 직교행렬 $U$, $V$로 다음 식(15)으로 같이 분해한다.

식(15)에서 해는 V의 마지막 컬럼(Column) 벡터가 된다. 그리고 $n$개의 데이터를 임의로 선택하여 Inlier와 최적의 모델을 찾기 위한 식은 식(16)과 같다.

식(16)에서 $p$는 $n$번의 sampling 중 적어도 한번은 Inlier만 추출할 확률이고, 본 논문에서는 $p$를 90%로 설정하였다. $m$은 한 번에 뽑는 샘플 수, $\alpha$는 입력 데이터 중 Inlier의 비율이다. $n$번의 횟수가 높을수록 확률은 높아지지만 무한정으로 $n$의 횟수를 늘릴 수는 없다. 최적의 $n$의 횟수를 구하는 식은 식(17)과 같다.

상기 수식들과 같은 방법으로 구한 타원 모델링과 Inlier를 기준으로 탐색 윈도우 설정하여 지속적으로 CAM-shift의 새로운 탐색 윈도우를 적용시켜 겹침 발생 시 탐색 윈도우가 확장되지 않고 확장을 제어하여 추적 객체만 지속적으로 추적하게 한다.