중심 이동 기반의 스케일 적응적 물체 추적 알고리즘
상태바
중심 이동 기반의 스케일 적응적 물체 추적 알고리즘
  • CCTV뉴스
  • 승인 2011.08.08 00:00
  • 댓글 0
이 기사를 공유합니다

본 고에서는 물체를 구성하고 있는 컬러들의 기하학적 중심을 이용하여 물체의 크기에 적응적인 추적 알고리즘을 제안한다. 대부분의 크기 적응적 알고리즘은 표적 윈도우의 크기를 결정하기 위하여 히스토그램을 사용한다.

그러나 이러한 방법은 표적의 배경에 표적의 색상과 유사한 물체가 존재하거나 표적의 일부분이 폐색되었을 때 표적의 크기를 추정하는데 실패한다. 이것은 히스토그램이 영역에 대한 기하학적인 공간정보를 상실한 채 표적 컬러의 화소수하고만 연관되기 때문이다. 이러한 분석을 바탕으로 본 고는 표적 컬러의 화소수의 변화에 상대적으로 덜 민감한 표적의 컬러 중심을 이용한 크기 적응 알고리즘을 제안한다.

컬러의 중심들은 공간 정보를 가지고 있기 때문에 컬러 중심과 표적 영역의 크기에는 직접적인 상관관계가 존재한다. 표적의 크기 변화를 추정하기 위하여 각각의 표적 컬러에 대한 줌팩터를 추정한 후, 적절한 필터링 과정을 통해 하나의 줌팩터를 추정한다. 제안한 크기 추정 알고리즘은 중심 이동 기반의 추적 알고리즘과 결합된다. 제안된 크기 적응적 추적 알고리즘은 배경에 유사한 컬러가 존재하는 경우에도 안정적으로 작동하는 것을 실험으로 검증한다.

크기 적응적 중심 기반 추적 알고리즘

중심 이동 기반 객체 추적 알고리즘

이전 연구(1)에서는 표적 컬러들의 기하학적 중심 이동을 이용하여 다음 프레임의 표적 위치를 추적하는 안정적인 알고리즘을 제안하였다. 표적의 위치는 각 컬러 중심들의 가중평균으로 구해진다. 제안하는 크기 추정방법은 표적의 중심이 얼마나 정확하게 추정되느냐에 따라 성능이 좌우되기 때문에 표적의 위치를 정확하게 추정하는 것은 중요하다. 여기서 표적의 위치를 추정하는 알고리즘에 대해 간단하게 설명하고자 한다. m개의 컬러빈(color bin)을 갖는 물체의 중심 위치 y^는 다음과 같은 거리함수를 y^에 대해 최소화함으로써 구한다.

여기서 qu, p는 각각 초기 프레임 및 현재 프레임에서 컬러빈 u의 히스토그램을 의미하며, n은 현재 프레임을 나타내는 기호이다. 여기서 C은 n번째 프레임에서의 컬러 u에 해당하는 화소들의 위치벡터들의 평균벡터이다. 식 (1)의 거리함수 E(y^)의 최소값은 E(y^)을 y^에 대하여 미분한 함수를 0으로 놓음으로써, 즉 ▽E(y^)=qu(y^-C)=0으로 놓음으로써 구할 수 있다.




초기 프레임에서 표적의 중심위치를 계산한 후 다음 프레임(현재 프레임이 n번째 프레임이면  n+1번째 프레임)에서의 표적 위치를 찾기 위해 우선 이전에 구한 중심위치를 중심으로 검색윈도우를 설정한다.



그 후 검색영역 안에서 식 (2)를 이용하여 각 컬러들의 중심을 구하고, 초기 프레임에서 계산한 가중치를 이용하여 이들 컬러 중심들의 가중평균을 구한다. 초기 프레임에서 설정한 가중치를 사용하였기 때문에, 현재의 검색 윈도우 영역에 존재하는 컬러라 하여도 원래 표적에 존재하지 않았다면 표적 중심위치 계산 시 이 컬러에 대한 고려는 하지 않게 된다.

그러므로 현재 프레임의 컬러의 변화나 화소수의 변화에 대해 어느 정도 안정적이며, 부분적인 폐색(occlusion)에 대해서도 안정적으로 표적의 중심이 구해지게 된다. 부분적인 폐색에 대해서도 추적 대상에 대한 추적이 가능한 이유는 추적 대상의 컬러중에서 폐색이 되지 않은 컬러들이 비록 소수일지라도 위치 추정시에 초기 프레임에서 이 컬러들이 차지하였던 면적에 비례하여 가중치를 주기 때문에 이들의 추정에 대한 영향력이 현재 프레임에서의 화소수에 의해서 결정되는 것이 아니기 때문이다.

중심의 차 벡터를 이용한 표적의 크기 추정

여기에서는 앞에서 기술한 표적의 위치 추적 알고리즘과 결합되는 크기 추정 알고리즘을 제안한다. 일단 표적의 위치가 앞의 알고리즘을 이용하여 계산되면 표적 영역은 표적의 새로운 크기에 적응하기 위하여 크기를 변경해야 한다. 대부분의 스케일 적응 알고리즘은 표적 컬러의 히스토그램을 이용하지만, 여기서는 컬러들의 기하학적 중심을 이용한다. 이는 다음의 사실들에 기인한 것이다.

우선 기하학적 중심들은 표적 컬러의 공간적 정보를 갖고 있다. 따라서 중심들은 표적 영역의 스케일과 직접적인 관련이 있다. 또한 유사한 배경 컬러로 인해 실제의 위치가 원하는 위치보다 많이 벗어난 컬러 중심들은 스케일 추정에 사용되지 않도록 쉽게 검출 및 제거가 가능하다.

스케일 추정을 위해 그림1과 같이 표적 영역을 네개의 작은 영역으로 나눈다. 그림 1의 윗 행과 아래 행은 각각 현재 프레임과 다음 프레임을 나타내고 두 프레임 사이에는 스케일의 변화가 있다고 가정한다. 표적 영역을 작은 영역으로 분할한 후 우선 각 영역에 대해 컬러들의 중심들을 각각 구한다. 그림 1(a), 1(b)는 현재 프레임에서 계산된 컬러 중심들을 나타낸 것이고, 그림 1(c), 1(d)는 다음 프레임에서 계산된 컬러 중심들을 나타낸 것이다.

그림 1에서 볼 수 있듯 서로 다른 영역에 존재하는 컬러 중심들 간 거리는 표적 영역의 크기와 직접적인 관련이 있다. 예를 들어 그림 1(a)와 1(c)에서 d과 d의 비율은 현재 프레임과 다음 프레임에 있는 표적의 폭(width) 비율을 계산할 때 사용될 수 있다. 하나의 컬러가 아닌 여러 컬러들로부터 구한 중심들을 이용하면 보다 안정적인 리사이징 비율을 얻을 수 있다. 알고리즘의 설명을 위해 d을 부분 영역 A와 B에 존재하는 컬러 u에 해당하는 중심 간 거리의 x성분이라고 정의한다. 즉,



로 정의한다. 여기서 C와 C는 각각 다음 프레임(n+1번째 프레임) 부분영역 A, B에서 컬러 u에 해당하는 화소들의 기하학적 중심의 x좌표를 의미한다. 마찬가지로 

  
도 정의할 수 있다. 다음으로 x축으로의 크기비율 d을 얻기 위해 d, d, d, d의 가중평균을 구한다. 즉, 

 
로 구하며, 이때 가중치는 각 부분영역에 존재하는 컬러 u의 개수를 고려하여 

 


의 형태로 구해지며, WAD,u, WCB,u, WCD,u도 동일한 방법으로 구해진다. 여기서  NA,u , NB,u, NC,u 그리고 ND,u는 각각 각 부분영역에서 컬러 u에 해당하는 화소의 개수를 의미한다.

최종적으로 컬러 u에 해당하는 x축으로의 줌팩터(zoom factor)는 

 
으로 정의된다. 여기서  d는 현재 프레임에서 d, d, d, d을 가중평균한 값이고, d도 같은 방식으로 다음 프레임을 사용하여 구한다. 줌팩터 z은 컬러  u에 대한 표적의 폭(x축 방향)의 스케일 비율을 추정한 것이다. y축에 해당하는 줌팩터도 동일한 방법으로 

와 같이 구할 수 있다.


이렇게 구한 줌팩터 z와  z는 각각 표적의 폭과 높이의 리사이즈 비율로 사용할 수 있다. 그러나 어떤 컬러의 줌팩터는 신뢰할 수 없는 값을 갖기도 한다. 배경에 유사한 컬러가 나타남으로 특정 컬러의 줌팩터는 우리가 원하는 값보다 커지거나 작아질 수 있기 때문이다. 따라서 본 고에서는 표적의 모든 컬러에 대해 줌팩터를 구한 후에 적절한 필터링 과정을 통해 신뢰할 수 있는 줌팩터를 선별, 이용하여 한쌍의 최종 줌팩터를 결정한다. 즉, 최종적인 줌팩터는 아래 식(10), (11)과 같이 나타낼 수 있다. 

여기서 아래 첨자 1,2,...,U는 각각의 컬러빈을 나타내며 f(.)은 신뢰할 수 있는 줌팩터들을 필터링하는 함수이다.
함수  f(.)는 여러 줌팩터 중에 1보다 너무 크거나 작은 값을 제거하는 과정을 담고 있다. 왜냐하면 연속된 프레임간에는 표적의 크기가 갑자기 변화하지 않기 때문에 이러한 줌팩터는 배경 컬러의 등장이나 표적의 폐색에 의해 발생했을 가능성이 크기 때문이다. 이렇게 선별된 줌팩터들에 대해서는 잡음제거에서 많이 사용되는 α-trimmed 필터링을 사용하여 최종적인 줌팩터를 구한다. 각각의 과정은 다음과 같다.

- 문턱값 적용 과정 : 1보다 너무 작거나 큰 줌팩터를 제거하는 과정이다. 결국 다음에 해당하는 줌팩터만을 사용하게 된다. 


여기서 0
- α-trimmed 과정 : ①의 과정을 통해 남은 줌팩터들에 대해 α-trimmed 평균을 이용하여 최종적인 줌팩터를 구한다. 이 과정은 남은 줌팩터들을 정렬하여 극단에 존재하는 α개의 줌팩터들을 제외한 줌팩터들에 대해 평균을 구하는 것이다. 줌팩터들의 필터링 과정을 그림3에 나타내었다.     

스케일에 적응적인 추적 알고리즘
중심 이동 기반의 위치 추적 알고리즘과 앞에서 설명한 스케일 추정방법을 결합시킨 스케일에 적응적인 추적 알고리즘의 전체 과정은 다음과 같다.

① 초기 프레임에서 표적의 위치와 크기를 설정한다.
② 다음 프레임에서 표적 영역과 중심은 같지만 크기는 그것보다 약간 큰 표적 검색 영역을 설정하고 컬러 중심을 구한다.
③ 계산된 컬러 중심들을 이용하여 표적의 위치를 계산한다.
④ 표적 영역을 추정된 위치로 이동시킨다.
⑤ 이동된 표적 영역을 네 개의 부분영역으로 나누고 각 영역에서 컬러 중심을 구한다.
⑥ 각 영역에서의 컬러 중심을 이용하여 모든 줌팩터를 구한다.
⑦ 필터링 과정을 이용하여 신뢰할 수 있는 하나의 줌팩터를 구한다.
⑧ 최종적으로 계산된 줌팩터를 이용하여 표적 영역을 리사이즈(resize)한다.
⑨ 다음 프레임을 입력받고 ②~⑧의 과정을 반복 수행한다.

스케일 추정 알고리즘은 표적의 중심을 기준으로 4등분되기 때문에, 추정된 표적의 위치에 따라 그 성능이 크게 좌우된다. 그러므로 앞에서 설명한 컬러 중심의 가중평균을 이용한 위치 추정 과정과의 결합이 최적의 결합이 된다. 왜냐하면 표적 영역의 중심이 컬러 중심들의 가중평균이 아니라면, 평균 벡터들의 크기가 왼쪽이나 오른쪽, 어느 한쪽으로 기울어질 수 있어 리사이징이 한쪽 방향으로 편향될 가능성이 높아지기 때문이다.

실험 결과

제안한 알고리즘의 성능을 실험적으로 증명하기 위하여 평균이동(Meanshift) 기반으로 가장 잘 알려진 방법인 CAMShift와 Meansh
ift Blob 그리고 제안한 방법을 동일한 영상 시퀀스에 적용하여 보았다.
모든 실험에서는 256×256×256의 컬러를 8×8×8로 균일하게 양자화하여 사용하였다. [그림 3]은 비교적 복잡하지 않은 배경에 표적이 존재하는 경우를 실험한 결과이다. 배경이 복잡해 보이지는 않지만 표적과 아래 도로에 유사한 컬러가 존재함을 확인할 수 있다. CAMShift의 실험 결과는 [그림 3(a)]에서 보는 바와 같다.


앞에서 언급한 바와 같이 표적 영역을 표시하는 붉은색 타원이 시퀀스가 진행됨에 따라 도로 쪽으로 확산되어 나가는 것을 볼 수 있다. Meanshift Blob의 경우 추적 대상의 색상에 대한 분포와 유사한 색상 분포가 원래 추적 대상의 크기보다 작은 영역 안에서도 존재하기 때문에 표적 윈도우의 크기가 점차로 작아짐을 볼 수 있다.

이에 반해 제안한 방법은 [그림 3(c)]와 [그림 3(d)]에서 확인할 수 있는 바와 같이 안정적으로 추적 대상의 크기를 계산하고 있음을 확인할 수 있다. [그림 3(c)]에서는 표적 영역 내에 실제로 줌팩터를 연산하기 위하여 계산된 각 부분영역에 속한 컬러 중심들을 초록색 점들로 표시하였다.

[그림 4]는 표적의 주변에 움직이는 여러 배경이 존재하는 경우를 실험한 결과이다.


[그림 4(a)]에서 보듯 CAMShift는 [그림 3]의 결과와 마찬가지로 불안정하게 동작하여 추적에 실패함을 알 수 있다. Meanshift Blob 역시 크기를 제대로 추정하지 못하며, 결과적으로 추적에 실패하는 원인이 된다. 이에 반해 제안한 알고리즘은 [그림 4(c)]와 [그림 4(d)]에서 보는 바와 같이 추적 대상의 크기를 안정적으로 추정함을 확인 할 수 있다.

특히 표적이 다른 객체에 의해 부분적으로 폐색(occlusion)되는 경우에도 동작함을 볼 수 있다. 이는 폐색되지 않은 남은 컬러 중심들이 크기 추정과 추적을 수행하기 때문이다. [그림 4(c)]에서 추적 대상이 비록 부분적으로 폐색되더라도 초록색으로 표시되는 컬러 중심들이 남아 있음을 확인할 수 있다. 이 컬러 중심들에 의해 추적이 가능하게 된다.


[그림 5]는 추적 대상이 정면에서 접근하여 점차 그 크기가 커질 때의 크기 추정에 대한 실험 결과이다. 이 경우 크기 변화가 심하고 주위의 컬러들이 있어서 크기 추정이 어려운 경우로 CAMShift나 MeanShift Blob이 모두 실패하며, [그림 5]에는 제안한 알고리즘의 결과만을 나타내었다. 제안한 알고리즘의 프레임당 연산시간은 추적 대상의 크기와 영상의 크기에 따라 달라지면 추적 대상의 크기가 커질수록 연산시간이 늘어난다. 그러나 기본적으로 위치 추정에 사용된 빈들의 중심들이 크기 추정에 다시 사용되므로 추가적인 계산이 많이 요구되지 않으나 필터링 시에 사용되는 정렬에서 대부분의 연산시간이 사용된다.

[그림 3]의 시퀀스에 대한 평균 연산시간은 프레임당 3.4ms, [그림 4]의 시퀀스에 대해서는 4.5ms, [그림 5]에 대해서는 7.3ms 정도 걸린다. 이는 실시간으로 추적이 가능함을 보여준다. 

[표 1]은 제안한 알고리즘에 대하여 검색영역을 다양한 크기로 주었을 때의 중심위치와 추적 대상의 크기에 대한 추정 에러를 픽셀단위로 나타낸 것이다. [표 1]의 에러 측정을 위해 [그림 3], [그림 4], [그림 5]에서 쓰인 각 실험 시퀀스들의 30번째 프레임마다 뽑아낸 프레임에 대하여 눈대중으로 추적 대상의 위치와 크기를 측정하여 참값으로 사용하였으며, 이 참값과 알고리즘에 의해 추정된 위치 및 크기 간의 차이를 에러로 정의하였다.

사용한 프레임 수는 20개 정도이다. 위치의 에러는 Ground truth 위치와 측정된 위치간의 Euclidean 거리를 픽셀의 단위로 측정하였다. 크기의 에러는 단순히 면적의 크기의 차이를 픽셀의 단위로 나타낸 것이다.

[표 2]는 각 알고리즘들에 대하여 위치와 크기의 추정에 대한 평균 에러를 나타내었다. 이때 사용한 프레임들은 CAMShift나 MeanS
hift Blob이 추적에 크게 실패하기 이전까지의 프레임들을 사용한 것들이다. [표 1]과 [표 2]에서의 Cavier Walk 시퀀스는 추적 알고리즘의 비교를 위해 자주 쓰이는 시퀀스로 인터넷상에서 얻을 수 있으며, 이 시퀀스에 대해서는 위치와 크기의 참값이 주어졌기 때문에 추가로 본 시퀀스를 그림으로 나타내지는 않았으나 실험비교에 사용하였다. [표 2]를 통해 제안한 알고리즘이 위치 및 크기 추정을 안정적으로 수행함을 확인할 수 있다.

결론

본 고는 컬러들의 중심을 이용하여 표적의 스케일의 추정하는 크기 적응적 추적 알고리즘을 제안하였다. 제안한 방법은 일반적인 방법과 달리 컬러들의 기하학적 중심을 이용하기 때문에 화소의 개수에 그다지 민감하지 않다. 따라서 배경에 유사한 색상이 존재하더라도 비교적 안정적으로 동작할 수 있으며 이를 실험을 통해 검증하였다. 제안한 방법은 중심 이동 기반의 위치 추적 알고리즘과 결합된 형태로 제시되었다. 그러나 제안된 스케일 추정 방법은 중심 이동 기반의 위치 추적 알고리즘뿐 아니라 기존의 평균이동 추적 방법, 파티클 필터 기반의 추적 방법 등 다양한 추적 알고리즘과의 결합이 가능하다. 따라서 추후 연구를 통하여 제안한 방법을 다른 추적 알고리즘에 적용시킬 것이다.

 각주_ (1) S. H. Lee, E. Choi, and M. G. Kang, "Object tracking based on area weighted centroids shifting with spatiality constraints," IEEE Int. Conf. Image Processing, San Diego, USA, 2008.




글 강문기 공학박사 / 연세대학교 전자공학과 교수·연세대학교 TMS 정보기술 사업단
     이석호 공학박사 / 동서대학교 컴퓨터정보공학부 전임강사 
     최은철 / 연세대학교 TMS 정보기술 사업단









댓글삭제
삭제한 댓글은 다시 복구할 수 없습니다.
그래도 삭제하시겠습니까?
댓글 0
0 / 400
댓글쓰기
계정을 선택하시면 로그인·계정인증을 통해
댓글을 남기실 수 있습니다.