Advanced
Histogram Equalization Based Color Space Quantization for the Enhancement of Mean-Shift Tracking Algorithm
Histogram Equalization Based Color Space Quantization for the Enhancement of Mean-Shift Tracking Algorithm
Journal of Broadcast Engineering. 2014. May, 19(3): 329-341
Copyright © 2014, The Korean Society of Broadcast Engineers
  • Received : December 02, 2013
  • Accepted : May 21, 2014
  • Published : May 30, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
장원 최
윤식 최
용구 김
ygkim@kgit.ac.kr

Abstract
커널 기반 평균 이동 물체 추적(kernel-based mean-shift object tracking) 방법은 신뢰할 수 있는 물체 추적의 실시간 구현이 가능하기 때문에 최근 많은 관심을 받고 있다. 이 알고리즘은 표적 모델과 표적 후보 간의 히스토그램 유사성 비교를 통해 최적의 평균이동 벡터를 찾는데, 실시간 구현을 위해 대부분의 알고리즘에서는 색-공간의 균일 양자화를 수행한다. 하지만, 영상의 명암 분포가 편중되어 있는 경우 색-공간의 양자화 후 히스토그램 분포가 몇 몇 빈에 집중되기 때문에 히스토그램 유사성 비교의 정확도를 감소시키게 되고, 따라서 추적의 성능이 저하될 수 있다. 이러한 문제를 해결하기 위해 히스토그램 빈을 적응적으로 조절하는 비-균일 양자화 알고리즘이 제안되었으나 높은 복잡도로 인해 실시간 추적 알고리즘에 부적합한 단점을 갖고 있다. 이에 본 논문에서는 표적 모델에 대한 히스토그램 평활화를 수행한 후 색-공간의 균일 양자화를 수행하는 형태의 고속 비-균일 양자화 기법을 제안함으로써, 색-공간 양자화 후에도 표적 모델의 명암 분포가 전 색-영역에 고르게 분포되도록 함으로써 실시간 평균 이동 추적 기법의 추적 성능이 개선될 수 있도록 하였다. 제안하는 색-공간 양자화 기법을 통해 표적 모델과 비교 후보군 사이에 비교 대상이 되는 색 요소가 증가하게 되며, 보다 정확도 높은 히스토그램 유사성 결과를 얻을 수 있었다. 물체 추적용 영상을 통한 실험 결과, 제안하는 알고리즘은 복잡도 증가가 거의 발생하지 않는 동시에, 기존 비-균일 양자화 알고리즘 결과와 유사하거나 좀 더 나은 추적 결과를 보여주었다.
Keywords
Ⅰ. 서 론
컴퓨터 비전(computer vision)의 주요 연구 분야 중 하나인 물체 추적은 연속된 장면에서 추적의 대상이 되는 물체의 위치를 찾는 기술로, 현재 HCI(human-computer interaction), 비디오 색인, 자동 보안 시스템 등의 분야에서 널리 사용되고 있다. 물체 추적 연구는 일반적으로 크게 점(point), 커널(kernel), 그리고 실루엣(silhouette) 기반의 방식으로 나눌 수 있는데 [1] , 최근에는 높은 추적 신뢰도를 제공하면서 실시간 응용 프로그램의 구현이 용이한 커널 기반 물체 추적 방법이 높은 관심을 받고 있다. 여기서 실시간 물체 추적을 가능하게 하는 핵심 기술은 평균 이동(meanshift) 기법으로, 이를 이용하면 주변의 최적 위치를 빠르게 추적할 수 있다.
이와 같은 장점으로 인해 평균 이동 방법을 적용한 다양한 커널 기반 물체 추적 알고리즘들이 제안되었는데, 대표적 연구로는 Bhattacharyya 유사성 측도(Bhattacharyya similarity measure) 및 Epanechnikov 타원형 커널을 이용한 색 히스토그램 기반의 물체 추적 알고리즘을 들 수 있다 [2] . 이 기법은 표적 모델(target model)과 표적 후보(target candidate) 간에 커널 가중치가 적용된 색 히스토그램을 비교하여 최적의 유사성을 갖는 후보 영역 위치를 빠르고 정확하게 계산하는 평균 이동 표적 위치 추정(mean-shift target localization) 알고리즘이다. 또한 이를 토대로 물체 추적의 정확도 향상을 위한 연구가 다양한 방면으로 진행되었는데, 대표적으로는 새로운 물체 표현 모델을 사용하는 방식들 [3 , 4 , 13] , 물체의 크기 변화 및 방향 변화를 고려하는 기법들 [5 , 6] , Bhattacharyya 계수를 대신하는 새로운 유사성 측도를 사용하는 기법들 [7 , 8] , 그리고 대상 영역의 물체를 배경에서 분리하는 방법들 [9 , 10] 등을 들 수 있다.
이처럼 다양한 연구들은 Comaniciu의 알고리즘 [2] 을 기반으로 추적 정확도를 개선하고자 노력한 결과이며, 많은 성능 향상을 보여주었다. 앞서 언급한 연구에서 사용하고 있는 색 히스토그램은 실시간 구현을 위해 색-공간을 균일 양자화(uniform quantization)하여 얻고 있는데, 색 히스토그램의 빈(Bin)들을 양자화 한 소수의 대표값으로 변환함으로써 추적 알고리즘이 사용하는 반복적 유사도 계산에서 큰 연산량 감소 효과를 얻는다. 하지만 이러한 색공간 양자화 방식은 히스토그램 유사성 비교 결과의 정확도를 감소시키게 되며, 특히 추적하고자 하는 모델 히스토그램이 일부 영역에 편중되어 분포하고 있는 경우 큰 문제점을 발생시킬 수 있다. 즉, 표적 모델의 색 히스토그램이 특정 영역에 집중되어 있는 경우, 균일 히스토그램 양자화로 인해 특징 색들이 대부분 동일한 값의 빈(bin)으로 변환될 수 있으며, 이로 인해 발생하는 비교 대상 히스토그램 빈의 감소는 히스토그램 유사성 비교 결과의 신뢰도를 감소시킬 수 있다.
이러한 문제점을 보완하기 위해 히스토그램 빈 개수 및 영역을 적응적으로 조절하는 비-균일 양자화 알고리즘이 제안되었다 [12] . 이 알고리즘은 커널 영역의 화소 값들을 클러스터링(clustering)하여 분류한 후, 각각의 클러스터에 적합한 최적의 히스토그램 빈 영역을 색-공간 내에서 설정함으로써 비-균일 히스토그램 양자화를 수행한다. 이와 같은 비-균일 히스토그램 양자화를 통해 히스토그램이 색-공간의 일부에 편중된 영상에서도 높은 정확도의 물체 추적 결과를 얻을 수 있지만 설정된 클러스터의 개수에 따라 물체 추적 정확도가 크게 좌우되며, 알고리즘 복잡도가 매우 높기 때문에 실시간 물체 추적에 적용하기 어려운 단점이 있다. 따라서 본 논문에서 목표로 하는 실시간 물체 추적의 정확도 향상을 위해서는 고속으로 비-균일 히스토그램 양자화를 수행하는 알고리즘이 요구된다.
이에 본 논문에서는 영상의 색 히스토그램 분포를 조절하여 색-공간 양자화를 수행함으로써, 표적 모델의 히스토그램이 전체적으로 분산될 수 있는 고속 비-균일 색-공간 양자화 기법을 제안한다. 색 히스토그램의 분산은 영상의 명암 대비를 조절하는 것이기 때문에 이를 통해 물체와 배경을 보다 선명하게 구분할 수 있게 되며, 이는 물체 추적을 보다 정확하게 할 수 있는 장점을 갖는다. 또한 분산된 색 히스토그램은 양자화 후에도 전체 히스토그램 영역에 분산된 값을 유지하기 때문에 이로 인해 증가되는 히스토그램 비교 후보군은 히스토그램 유사성 비교의 정확도를 높일 수 있다. 본 논문에서 제안하는 비-균일 양자화 기법은 색 히스토그램 평활화 기법 [11] 을 통해 고속으로 히스토그램 분포를 조절한 후 색-공간 균일 양자화를 적용하는 방식으로, 결과적으로는 비트 심도(bit-depth)가 8인 색-공간 별로 28바이트(byte) 크기의 양자화 테이블로 구현된다. 히스토그램 평활화가 편중된 색-공간 분포를 가진 영상을 평활한 색-분포를 가지도록 변환하는 기법이기 때문에, 평활화 결과에 균일 양자화를 적용하는 것은 표적 모델의 특징을 이루는 높은 히스토그램 빈 값을 가지는 색 영역 부근에서는 간격이 좁은 양자화를 수행하고, 반대로 낮은 히스토그램 빈 값을 가지는 색 영역들은 크게 하나로 묶어주는 결과를 제공한다. 또한 이러한 비-균일 양자화 기법은 기존의 균일 양자화가 제공하는 고속 추적의 장점은 유지하면서 명암 대비가 개선된 형태로 히스토그램 유사도 계산을 가능하도록 함으로써, 기존 비-균일 양자화 알고리즘과 비슷한 물체 추적의 정확도를 얻을 수 있도록 한다.
본 논문의 구성은 다음과 같다. 제 2장에서는 기존 평균 이동 물체 추적 알고리즘의 소개 및 색-공간 균일 양자화 방법을 설명한다. 3장에서는 2장에서 확인한 기존 알고리즘의 문제점을 해결하기 위하여 색 히스토그램 평활화를 기반으로 한 비-균일 색-공간 양자화 방식을 설명하고, 이를 적용한 평균 이동 물체 추적 알고리즘을 제안한다. 4장에서는 제안하는 기법의 성능을 보여주기 위한 실험 및 결과를 보여주고, 5장에서 본 논문의 결론을 맺는다.
Ⅱ. 평균 이동 물체 추적 알고리즘
본 장에서는 기존 평균 이동 물체 추적알고리즘의 분석을 통해 비-균일 색-공간 양자화 기법의 필요성을 설명한다. 커널 기반 평균 이동 물체 추적은 추적하고자 하는 물체가 포함되어 있는 표적 모델과 이의 비교 대상이 되는 표적 후보간의 색 히스토그램 유사성을 비교한 후 최적의 표적 후보 위치를 결정한다. 표적 모델은 물체 추적 첫 장면에서만 설정되며, 표적 모델 및 표적 후보 모델 간 히스토그램 유사성의 비교를 위한 Bhattacharyya 계수는 같이 정의된다 [2] .
PPT Slide
Lager Image
위 식에서 u 는 히스토그램 빈 위치를,
PPT Slide
Lager Image
PPT Slide
Lager Image
m 개의 히스토그램 빈을 가지며 각각 등방성 커널 k ( x )로 가중치가 적용된 표적 모델과 y위치에서의 표적 후보 히스토그램이며, 이들 히스토그램은 다음과 같이 정의된다.
PPT Slide
Lager Image
여기서 x i * 는 표적 모델의 i-번째 화소 좌표를, x i 는 표적 후보의 i-번째 화소 좌표를 의미하며, k ( ⋅ )는 커널 함수 [2] , n nh 는 표적모델 및 표적 후보의 화소 개수를 뜻한다. 또한 δ 함수는 Kronecker 델타 함수이며, q 함수는 RGB색-공간 화소에 균일 양자화를, b 함수는 양자화 된 RGB색-공간 화소를 0과 m 사이의 1차원 빈 값으로 매핑시키는 함수이다.
식 (1)과 같이 Bhattacharyya 계수는 표적 모델과 표적 후보 간 같은 위치의 히스토그램 값들을 곱한 후 이를 모두 더하여 얻게 되며, 값이 높을수록 두 커널 간 유사성이 높다고 할 수 있다. 따라서 두 히스토그램에서 유사한 값을 가지는 빈이 많을수록 높은 Bhattacharyya 계수를 얻을 수 있다. 또한 식 (2)에서 볼 수 있듯이,
PPT Slide
Lager Image
PPT Slide
Lager Image
는 등방성 커널 k ( x )로 가중치가 적용되기 때문에 커널 중심에서 멀어질수록 히스토그램에 영향이 작아지게 되며, 가까울수록 큰 영향을 준다. 즉, 커널 중심에 가까운 화소일수록 Bhattacharyya 계수의 계산 시 보다 많은 영향을 준다. 표적 모델
PPT Slide
Lager Image
는 물체 추적을 하고자 하는 첫 장면에서 계산되며, 표적 후보
PPT Slide
Lager Image
는 현재 영상 위치에서 표적이 있을 것이라 예상되는 영역에서 얻는다. 표적 후보 영역에서의 초기 위치인 y 0 는 이전 장면의 물체 추적 성공 위치와 동일하며, 이후 Bhattacharyya 계수가 최대가 되는 위치 y 1 은 다음과 같은 계산을 반복함으로써 얻을 수 있다.
PPT Slide
Lager Image
위 식에서
PPT Slide
Lager Image
는 현재 표적 후보의 위치를 나타내고, g ( x ) = - k' ( x )이며, 각 화소 위치 x i 에 대한 평균 이동 가중치 wi 는 다음의 식으로 주어진다.
PPT Slide
Lager Image
이 후, 평균이동 벡터
PPT Slide
Lager Image
가 0에 수렴할 때까지
PPT Slide
Lager Image
PPT Slide
Lager Image
으로 재설정 후, 새로운
PPT Slide
Lager Image
을 찾는 것을 반복하여 최적의
PPT Slide
Lager Image
을 찾는다. 즉, 화소 위치 x i 에 대한 평균 이동 가중치 wi 는 표적 모델
PPT Slide
Lager Image
과 표적 후보
PPT Slide
Lager Image
에서 양자화 된 색상 b ( q (x i ))에 해당하는 빈 값의 비율로 얻게 되며, 따라서 평균 이동벡터
PPT Slide
Lager Image
계산에 표적 모델과 표적 후보 모델의 히스토그램 비율이 절대적인 영향을 미치고 있음을 알 수 있다.
이와 같이, 표적 모델과 표적 후보 모델의 색-공간 히스토그램은 평균 이동 알고리즘의 핵심인 평균 이동 벡터 계산에 영향을 준다. 하지만 실시간 물체 추적을 목표로 하는 평균 이동 알고리즘에서는 복잡도 감소를 위해 색-공간 (히스토그램) 양자화를 수행하며, 히스토그램이 특정 영역에 편중되어 분포하는 영상에서는 양자화로 인해 특정 히스토그램 빈에 값이 집중되는 현상이 발생할 수 있다. 그림 1 은 이를 확인하기 위해 Campus1 실험 영상에서 표적 모델의 색 히스토그램 분포도 및 색-공간 균일 양자화의 결과를 도시한 것이다. 그림 1 (b)의 가로축은 표적 모델 RGB 채널의 28개 히스토그램 빈을, 세로축은 빈도수를 의미하며, 그림 1 (c)의 가로축은 RGB 채널을 통합한 히스토그램 분포도로, 224개의 히스토그램 빈을 212개로 색-공간 별 균일 양자화를 수행하여 색-공간을 병합한 인덱스를 의미하며 1) , 세로 축은 등방성 커널 k ( x )로 가중된 양자화된 히스토그램 빈도수를 표현한 것이다. 그림 1 (a)와 1 (b)에서 볼 수 있는 바와 같이, 이 표적 모델은 명암 비가 좋지 않기 때문에 RGB세 채널의 히스토그램이 모두 좁은 범위에 분포되어 있는 것을 알 수 있다. 따라서 이로 인해 그림 1 (c)와 같이 양자화가 적용된 표적 모델 히스토그램이 몇 몇 빈에 집중되어 있는 것을 확인할 수 있다.
PPT Slide
Lager Image
Campus1 실험 영상에서의 표적 모델 히스토그램 분포도 (a) 표적 모델 영상 (b) RGB 채널의 히스토그램 분포 (c) 양자화가 적용된 표적 모델 히스토그램 Fig. 1. Histogram distribution of target model of Campus1 test sequence (a) target model image (b) Histogram distribution of RGB channels (c) quantized target model histogram distribution
이와 같이 명암비가 좋지 않은 영상은 표적 모델과 더불어 표적 후보 또한 소수의 히스토그램 빈에 값이 몰리게 되며, 따라서 표적 모델과 표적 후보 사이의 히스토그램 비교 후보군이 감소하게 되고, 양자화 오차가 평균이동 알고리즘에 큰 영향을 미칠 수 있게 된다. 즉, 그림 2 (c)와 같이 표적 모델
PPT Slide
Lager Image
및 표적 후보
PPT Slide
Lager Image
의 히스토그램이 몇 몇 히스토그램 빈에 집중되어 서로 중복되는 빈의 개수가 줄어든다. 이로 인해 두 히스토그램의 비율로 결정되어지는 wi 값은 소수의 빈을 제외하고는 모두 0으로 계산되며, 이는 wi 를 가중치로 하여 얻어지는 평균 이동 벡터 계산 결과의 정확도 감소 원인이 된다. 실제로 그림 2 (c)에서 얻은 표적 모델과 표적 후보 히스토그램을 분석한 결과, 표적 모델 히스토그램에서 0이 아닌 값을 갖는 빈은 전체 212개의 빈 중에 119개였으며 표적 후보 히스토그램에서는 71개였다. 또한 서로 중복되어 wi 계산에 영향을 줄 수 있는 빈은 고작 49개에 그쳤다. 따라서 이러한 문제점을 해결하기 위해서는 표적 모델 및 표적 후보 모델의 색 히스토그램 분포를 조절하여 비교 후보군을 충분히 확보함으로써 평균 이동 벡터 계산 결과의 정확도를 높이는 기법이 요구된다 할 수 있다.
PPT Slide
Lager Image
Campus1 실험 영상에서의 표적 모델과 표적 후보 모델 히스토그램 분포도 (a) 표적 모델영상 (b) 표적 후보 영상(c) 양자화가적용된표적 모델과 표적 후보 모델 히스토그램 Fig. 2. Histogram distribution of target model and target candidate model of Campus1 test sequence (a) target model image (b) target candidate model image (c) quantized target model and target candidate model histogram distribution
기존의 평균 이동 추적 기법들에서는 R, G, B 각 색-공간을 보통 16으로 (색-공간 별) 균일 양자화 하여 16x16x16=212 개의 히스토그램 빈을 생성하고, 이를 이동 추적에 사용하였다.
Ⅲ. 비-균일 색-공간 양자화를 이용한 평균 이동 물체 추적 기법
앞서 언급한 바와 같이, 영상의 색-공간 히스토그램 분포가 편중된 경우 색-공간 균일 양자화로 인해 특정 히스토그램 빈들에만 값이 존재하는 현상이 발생하며, 이는 히스토그램 유사성 비교 결과의 신뢰도를 감소시킬 수 있다. 이러한 문제를 해결하기 위해 색-공간 내에 물체의 색이 존재하는 영역을 그 색 분포에 따라 비-균일하게 대표화 할 수 있는 비-균일 양자화 알고리즘이 제안되었다 [12] . 이 알고리즘은 커널 영역 내 화소 값들을 클러스터링하여 분류한 후, 각 클러스터의 직교정규 변환(orthonormal transform) 결과를 이용하여 최적의 히스토그램 빈 영역을 계산한다. 이를 통해 클러스터 개수만큼의 비-균일한 히스토그램 빈 영역을 색-공간 내에 생성하게 되며, 클러스터 개수는 클러스터링 변수 값에 따라 자동으로 결정된다. 즉, 히스토그램 빈 영역을 색-공간에서 비-균일하게 설정하여 유사한 화소끼리 히스토그램을 구성하도록 하였으며, 이를 통해 히스토그램이 편중된 영상에서도 보다 정확한 히스토그램 비교 결과를 얻을 수 있다. 하지만 이 알고리즘은 클러스터의 개수에 따라 물체 추적의 정확도가 크게 좌우되며, 또한 클러스터의 개수가 증가할수록 알고리즘 복잡도가 급증한다. 특히 색-공간에서 비-균일하게 설정된 히스토그램 빈 영역 간의 중복 영역 확인이 필요하므로 클러스터 개수가 증가할수록 이를 위한 연산량이 늘어난다. 따라서 본 논문에서 목표로 하는 실시간 물체 추적 기법에는 적용하기 어려운 알고리즘이라 할 수 있다.
이에 본 논문에서는 색-공간 양자화 후에도 히스토그램 분포가 전 영역에 균일하게 분산될 수 있도록 하는 고속 비-균일 색-공간 양자화 기법을 제안한다. 비-균일 양자화는 양자화 하고자 하는 값의 분포 및 특징에 따라 양자화구간 길이를 서로 다르게 설정하는 기술로, Lloyd-max 양자화, 벡터 양자화 등 다양한 기법이 존재한다. 하지만 앞서 설명한 기존 알고리즘과 같이 대부분의 비-균일 양자화 기법은 구현하는 복잡도가 매우 높기 때문에 실시간 물체 추적 알고리즘에 적용하기에는 어려움이 있다. 따라서 본 논문에서는 각각의 색-공간에 히스토그램 평활화를 적용한 후 균일 양자화를 적용함으로써, 결과적으로는 고속으로 비-균일 색-공간 양자화를 수행하는 결과를 얻을 수 있도록 하였다. 색 히스토그램 평활화 기법 [11] 은 영상의 히스토그램을 이용하여 정규화 된 누적 분포를 구한 후, 조정인자를 곱하여 원래의 명암 값을 재분배한다. 명암 대비가 개선된 영상은 히스토그램 분포도가 전 영역에 고르게 분산되어 있으며, 이에 균일 양자화를 적용함으로써 결과적으로 영상의 특징을 이루는 높은 히스토그램 빈 값을 가지는 색 영역에서 간격이 좁은 양자화를, 반대의 경우에는 간격이 넓은 양자화를 수행하는 비-균일 색-공간 양자화 결과를 얻을 수 있다. 또한 색 히스토그램 평활화는 간단한 연산을 통해 구현이 가능하기 때문에 기존 알고리즘에 비해 복잡도 증가가 거의 발생하지 않는다. 따라서 본 논문에서 제안하는 기법을 통해 고속으로 비-균일 색-공간 양자화를 수행할 수 있으며, 이를 통해 얻어지는 히스토그램은 명암 대비가 개선된 형태이기 때문에 보다 높은 정확도의 물체 추적을 가능하게 한다.
본 논문에서 제안하는 비-균일 색-공간 양자화를 위해, 우선 영상의 색 히스토그램 평활화 및 양자화를 표적 모델의 각 색-공간에 적용한 후, 여기서 구하게 되는 양자화 테이블 T 를 이용하여 표적 후보에도 각 색-공간의 양자화를 수행한 후, 그 결과를 이용하여 물체 추적을 수행한다. 그림 3 은 본 논문에서 제안하는 기법의 전체 흐름도를 보여준다.
PPT Slide
Lager Image
제안 트래킹 기법의 전체 흐름도 Fig. 3. Flow chart of the proposed tracking algorithm
표적 모델의 화소 x * = {x * 1 ,x * 2 ,⋯,x * nh }가 RGB 색-공간에서 각각 L 단계의 값을 가지고 있는 경우, 이의 평활화를 위해 우선 표적모델의 히스토그램을 정규화 하여 다음과 같은 확률 밀도 함수(PDF, probability density function)를 계산한다.
PPT Slide
Lager Image
여기서 C 는 색-공간을 의미하며( C ∈{ R , G , B }), nh 는 표적 모델의 전체 화소수를, nkC 는 표적 모델 내에서 C 색-공간의 화소값이 k 인 화소들의 개수를 의미한다. 이를 이용하여 누적 분포 함수(CDF, cumulative distribution function)를 다음과 같이 계산한다.
PPT Slide
Lager Image
히스토그램 평활화는 히스토그램을 전 영역으로 균일하게 매핑하는 역할을 수행하며, 이때 원 화소값 k 와 평활화로 인해 변환된 화소값 k′ 및 이의 양자화 된 결과는 식 (7)과 같이 정의할 수 있다.
PPT Slide
Lager Image
여기서 ⌊‧⌋기호는 가우스 기호를 의미하며, QC 는 각 색-공간 당 양자화 단계 수를 의미한다. 위와 같이 표적모델에 양자화 테이블 T = { TR , TG , TB }를 RGB 색-공간에 각각 적용함으로써 본 논문에서 제안하는 비-균일 양자화 결과를 얻을 수 있다. 위와 같이 계산된 양자화 테이블을 이용하여 색 히스토그램 평활화가 적용된 표적모델
PPT Slide
Lager Image
를 다음과 같이 재 정의할 수 있다.
PPT Slide
Lager Image
PPT Slide
Lager Image
위의 식과 마찬가지로 표적 후보에도 표적 모델에서 계산한 양자화 테이블 T 를 적용하는데, 표적 후보에서 별도로 색-공간 평활화를 수행하지 않고 표적 모델에서 계산된 양자화기를 그대로 사용하는 것은, 추적 물체의 색-공간 분포 특성을 이용한 비-균일 색-공간 양자화기를 설계하여 이를 통해 평균 이동 추적 알고리즘을 수행하는 것으로 이해할 수 있다. 따라서 표적 모델의 히스토그램 분포도 및 그에 따른 가중치를 표적 후보에 반영할 수 있게 되며, 표적 후보와는 상관없이 표적 모델에서 히스토그램 평활화를 한 번만 수행하게 되어 전체적인 알고리즘 복잡도에 거의 영향을 주지 않는 장점을 가진다.
앞서 제안한 히스토그램 평활화 및 균일 양자화를 적용한 표적 모델
PPT Slide
Lager Image
과 표적 후보
PPT Slide
Lager Image
를 이용하여 커널 내의 화소 x i 에 대한 가중치 wi 를 다음의 식과 같이 구할 수 있고,
PPT Slide
Lager Image
위에서 계산한 wi 를 이용하여 식 (3)과 같이 바차타야 계수가 최대가 되는 위치 y 1 를 구함으로써 본 논문에서 제안하는 비-균일 색-공간 양자화가 적용된 평균 이동 물체 추적이 수행된다. 본 논문에서 제안하는 비-균일 색-공간 양자화가 적용된 표적 모델
PPT Slide
Lager Image
과 표적 후보
PPT Slide
Lager Image
는 색-공간 양자화 후에도 0이 아닌 값을 가지는 빈들이 히스토그램 전 영역에 고르게 분포하게 되며, 이를 통해 보다 많은 화소에 대한 가중치 wi 를 얻을 수 있다. 따라서 본 논문에서 제안하는 기법을 통해 보다 많은 화소들이 영향으로 주는 평균이동 벡터
PPT Slide
Lager Image
를 계산을 할 수 있으며, 이로 인해 히스토그램 분포가 편중된 영상에서도 정확도 높은 물체 추적 결과를 얻을 수 있다.
Ⅳ. 실험 및 결과
본 논문에서 제안하는 기법의 성능 검증을 위해, 그림 4 와 같이 6개의 물체 추적용 실험 영상을 사용하였다. 각 실험 영상은 장면 당 물체의 실제 좌표 정보를 갖고 있기 때문에 본 논문에서는 이 좌표값과 실험적으로 얻은 추적 좌표값 사이의 추적 오차를 구함으로써 물체 추적의 정확도를 평가하였다. 각 실험 영상에서 단일 객체를 물체 추적 목표로 정하였으며, 각 객체로는 움직이는 사람 및 사물 등을 설정하였다. 또한 평균 이동 기법에 사용되는 커널로는 Epanechnikov 커널을 사용하였고, 색-공간 양자화가 미치는 물체 추적 성능에 대한 객관적 검증을 위해 가장 기본적인 평균 이동 물체 추적 기법에 해당하는 D. Comaniciu [2] 의 알고리즘에 기존 비-균일 양자화 기법 [12] 과 본 논문에서 제안하는 비-균일 양자화 기법을 적용하여, 그 추적 결과 및 복잡도를 비교함으로써 제안하는 기법의 성능을 검증할 수 있도록 실험을 설계하였다.
PPT Slide
Lager Image
실험영상에서 물체 추적을 위한 첫 번째 장면. (a) Campus1 영상 (b) Campus2 영상 (c) Fight_RunAway2 영상 (d) Egtest05 영상 (e) Baseball 영상 (f) Corridor 영상 Fig. 4. The first frame for the object tracking of test sequence. (a) Campus1 sequence (b) Campus2 sequence (c) Fight_RunAway2 sequence (d) Egtest05 sequence (e) Baseball sequence (f) Corridor sequence
우선, 히스토그램 평활화로 인한 히스토그램 분포도 변화를 확인하기 위해 표적 모델 및 표적 후보에 히스토그램 평활화를 적용한 결과를 분석하였다. 그림 5 그림 1 과 같은 표적 모델에 히스토그램 평활화를 적용한 후의 히스토그램 분포도를 보여준다. 그림 1 과는 달리 표적 모델에 히스토그램 평활화가 적용된 후에는 그림 5 (a)와 같이 커널 내 물체와 배경의 구분이 보다 선명해 진 것을 확인할 수 있는데, 이는 그림 5 (b)와 같이 RGB 색-공간에 히스토그램 빈이 고르게 분산되었기 때문이다. 또한 그림 5 (c) 및 6 (c)를 통해 표적 모델 및 표적 후보에 제안하는 양자화가 적용된 후에도 히스토그램이 전 영역에 분포되어있는 것을 볼 수 있으며, 이를 통해 본 논문에서 제안하는 비-균일 색-공간 양자화가 목표 효과를 충실하게 달성하고 있음을 알 수 있다. 정량적으로 보면 wi 계산에 영향을 주는 빈은 기존 49개에서 히스토그램 평활화 후에 298개로 크게 증가하였으며, 이와 같이 히스토그램 비교 후보군의 증가로 인해 보다 정확도가 높은 평균 이동 벡터를 구할 수 있었다. 또한 정성적으로 보면, 그림 1 (a)에 비해 그림 5 (a)가 배경과 사람이 보다 선명하게 분리되어 보이는 것을 확인할 수 있는데, 이를 통해 사람과 배경이 혼동되지 않고 분리되어 히스토그램 비교를 수행할 수 있기 때문에 보다 높은 정확도의 물체 추적 결과를 얻을 수 있는 것이다.
PPT Slide
Lager Image
Campus1 실험 영상에서 히스토그램 평활화가 적용된 표적 모델의 히스토그램 분포도 (a) 표적 모델 영상 (b) RGB 채널에서의 히스토그램 분포 (c) 양자화가 적용된 표적 모델 히스토그램 Fig. 5. Histogram distribution of target model which are applied histogram equalization in Campus1 test sequence (a) target model image (b) Histogram distribution in RGB channel (c) quantized target model histogram distribution
PPT Slide
Lager Image
Campus1 실험 영상에서 히스토그램 평활화가 적용된 표적 모델과 표적 후보의 히스토그램 분포도 (a) 표적 모델 영상 (b) 표적 후보 영상 (c) 양자화가 적용된 표적 모델과 표적 후보의 히스토그램 Fig. 6. Histogram distribution of target model and target candidate which are applied the histogram equalization in Campus1 test sequence (a) target model image (b) target candidate image (c) quantized target model and target candidate histogram distribution
표 1 은 실험 영상 및 추적 대상 물체에 대한 세부 특징을 설명하는 것으로, 각 테스트 시퀀스의 해상도, 추적 대상 물체의 크기 (커널크기) 및 물체 추적의 특징을 비교하기 좋은 시퀀스 구간(장면 범위) 등을 나타내고 있다. 제안하는 알고리즘을 객관적으로 평가하기 위해 크게 2가지 형태의 실험 군을 설정하였는데, 명암비가 좋지 않은 실험 영상(Campus1, Campus2, Fight_RunAway2)과 상대적으로 명암비가 좋은 일반 영상(Egtest05, Baseball, Corridor)으로 나누어 실험을 진행하였다. 또한 물체 추적 시 커널의 크기는 대략 추적 물체의 1.2배 정도가 되도록 설정하였으며, 비트심도 8비트의 컬러 영상(28+8+8개의 빈)을 24+4+4개로 양자화 하도록 설정하였다.
실험 영상들의 상세 설명
PPT Slide
Lager Image
Table 1. The specification of the test sequences
표 2 는 본 논문에서 제안하는 기법과 기존 알고리즘의 물체 추적 비교 결과를 보여준다. 표에서 평균 거리 오차는 각 장면 별 실제 물체 위치와 추적된 물체 위치와의 거리의 평균을 의미하며, 알고리즘 속도는 한 장면 추적에 걸리는 평균 속도를 의미한다. 또한 기존 비-균일 양자화 알고리즘의 결과는 클러스터의 개수를 변경해가며 얻은 최소의 평균 거리 오차를 나타낸다.
제안하는 기법과 기존 알고리즘과의 물체 추적 결과 비교
PPT Slide
Lager Image
Table 2. The comparison of object tracking results with proposed method and previous algorithm
표 2 의 결과에서, D.Comaniciu 등이 제안한 평균 이동 물체 추적 기법에 기존의 비-균일 양자화 기법 [12] 을 적용한 결과와 D. Comaniciu 등의 방식에 제안하는 양자화 기법을 적용한 결과를 비교해 보면, 본 논문에서 제안하는 알고리즘이 모든 실험 영상에서 기존 기법의 결과에 상당하는 우수한 물체 추적 결과를 보여주고 있는 것을 알 수 있다. 특히, 명암비가 좋지 않은 실험 영상(Campus1, Campus2 및 Fight_RunAway2)에서 제안 기법은 물체 추적에 모두 성공한 것을 볼 수 있다. 그림 7 , 8 과 같이 Campus1 및 Campus2 영상은 전체적으로 명암비가 좋지 않기 때문에 커널 내 물체와 배경의 구분이 명확하지 않으며, 이러한 문제점이 D. Comaniciu 등의 방법과 기존 비-균일 양자화 기법에서 추적 실패로 이어졌다. 하지만 본 논문에서 제안하는 비-균일 색-공간 양자화를 이용하면 명암비가 좋지 않은 영상에서도 물체와 배경을 보다 쉽게 구분할 수 있으며, 이와 같은 명암 대비 조절로 인한 히스토그램 비교 후보군의 증가는 보다 정확도 높은 물체 추적을 가능하게 한다는 것을 알 수 있다. 히스토그램 비교 후보군의 증가로 인한 물체 추적의 정확도 향상은 Corridor, Baseball 및 Egtest05 영상의 결과에서도 확인할 수 있는데, 표 2 에서 볼 수 있는 바와 같이 Corridor 영상의 평균 거리 오차는 히스토그램 평활화를 적용할 경우 대략 20%가 감소하였으며(D. Comaniciu 등의 기법과 비교), Egtest05 영상에서도 12% 정도 감소하였다. 즉, 본 논문에서 제안하는 비-균일 양자화 기법이 균일 양자화 기법에 비해 보다 정확한 물체 추적 성능을 제공하는 것이다.
PPT Slide
Lager Image
Campus1 실험 영상을 이용하여 기존 알고리즘(윗행)과 제안한 방법으로 추적한 결과 (아래행). 왼쪽에서 오른쪽으로 910, 949, 970, 990번째 장면 Fig. 7. Experimental results of the previous algorithm(upper row) and the proposed algorithm(lower row) using Campus1 test sequence. From left to right, the frames 910, 949, 970, and 990.
PPT Slide
Lager Image
Campus2 실험 영상을 이용하여 기존 알고리즘(윗행)과 제안한 방법으로 추적한 결과 (아래행). 왼쪽에서 오른쪽으로 140, 200, 250, 300번째 장면의 일부분 영상 Fig. 8. Experimental results of the previous algorithm(upper row) and the proposed algorithm(lower row) using Campus2 test sequence. From left to right, the some part image of the frames 140, 200, 250, and 300.
기존의 비-균일 양자화 알고리즘 [12] 이 추적 성능 면에서 Campus1 시퀀스를 제외하고는 가장 우수한 결과를 나타내고 있다. 하지만 D. Comaniciu 등의 기본 알고리즘에서 비-균일 양자화로 얻은 성능 개선은 제안 기법과 거의 유사한 것을 볼 수 있고, Campus1 시퀀스의 경우에는 제안 기법만이 추적에 성공하는 것을 알 수 있다. 또한, 비-균일 양자화 알고리즘의 복잡도를 비교해 보면 대략 73배에서 최대 5,235배까지 제안 기법에 비해 높은 계산량을 요구하는 것을 볼 수 있다. 그림 9 는 Fight_RunAway2 영상에서 클러스터 개수에 따른 기존 비-균일 양자화 알고리즘의 성능을 보여준다. 클러스터의 개수가 426개 이하인 경우에는 물체 추적에 실패하기 때문에 그림에서 제외하였으며, 커널 크기(61x33) 및 알고리즘의 특성 상 최대 클러스터 개수인 2,013개부터 알고리즘 성능 결과를 확인하였다. 그림에 보이는 바와 같이, 클러스터 수가 많을수록 제안하는 알고리즘보다 높은 추적 성능을 보여주지만, 알고리즘이 요구하는 복잡도가 크게 증가하는 것을 확인할 수 있다. 특히, 클러스터의 수가 가장 작은 경우에도 알고리즘 속도가 한 장면 당 0.0885초가 소요되기 때문에, 일반적인 비디오의 프레임률(30프레임/초)을 처리할 수 없고, 따라서 실시간 물체 추적에 적용하기 어려운 복잡도를 가진다 하겠다.
PPT Slide
Lager Image
Fight_RunAway2 실험 영상에서 클러스터 개수에 따른 기존 비-균일 양자화 알고리즘의 성능 Fig. 9. Performance of the previous non-uniform quantization algorithm with the change the number of cluster in Fight_RunAway2 test sequence.
이와 같은 결과를 종합해보면 본 논문에서 제안하는 비-균일 색-공간 양자화 기법이 평균 이동 물체 추적의 성능을 개선할 수 있음을 알 수 있고, 특히 명암비가 좋지 않은 영상에서의 실시간 물체 추적에 매우 효과적임을 알 수 있다.
Ⅳ. 결론 및 향후 연구
본 논문에서는 커널 기반 평균 이동 알고리즘에서 색-공간 양자화로 인해 발생하는 히스토그램 불균일 분포 현상을 해결하기 위해 고속 비-균일 색-공간 양자화 기법을 제안하였다. 제안 알고리즘은 표적 모델에 색-공간 히스토그램 평활화를 적용한 후 균일 양자화를 적용하는 방식으로, 색-공간 양자화 후에도 히스토그램이 전체적으로 분산되는 결과를 얻을 수 있으며, 이를 통해 보다 정확한 평균 이동 벡터를 구할 수 있게 되었다. 또한 표적 모델 생성 시에만 히스토그램 변환 함수를 적용하고, 생성된 비-균일 양자화 방법이 반복적으로 수행하는 추적 후보 모델에는 단순 적용만 되기 때문에 복잡도 증가가 거의 발생하지 않으며, 이는 실시간 고속 추적을 목표로 하는 커널 기반 평균 이동 알고리즘에 적합하다고 할 수 있다. 6개의 물체 추적용 실험 영상을 통해 본 논문에서 제안하는 기법의 성능을 검증한 결과, 기존의 비-균일 양자화 알고리즘에 비해 매우 낮은 복잡도를 가지는 동시에 유사한 물체 추적 성능 향상 결과를 얻을 수 있었으며, 특정 영상에서는 좀 더 나은 물체 추적 결과를 보이기도 하였다. 향후에는 기존 비-균일 양자화 알고리즘보다 정교하며 실시간 추적이 가능하도록 하는 양자화 방법에 대해 연구를 진행할 계획이며, 본 논문에서 제안하는 알고리즘에서 고려하지 못한 객체의 시간 변이에 따른 가려짐, 변형, 명암비가 수시로 변동되는 영상에서의 물체 추적을 위해 표적 모델 업데이트를 이용한 적응적 양자화 방법에 대해서도 연구를 진행할 예정이다.
BIO
최 장 원
- 2008년 2월 : 연세대학교 전기전자공학과 학사
- 2008년 9월 ~ 현재 : 연세대학교 전기전자공학과 석박사 통합과정 재학 중
- 주관심분야 : 영상 부호화, 2D/3D 이미지 신호처리, 영상 개선 처리
최 윤 식
- 1979년 2월 : 연세대학교 전기공학과 학사
- 1984년 5월 : Case Western Reserve 대학 시스템 공학과 석사
- 1987년 5월 : Pennsylvvania 주립 대학 전기공학과 석사
- 1990년 12월 : Purdue 대학 전기공학부 박사
- 1993년 3월 ~ 현재 : 연세대학교 전기전자공학 교수
- 주관심분야 : 비디오/영상 신호 처리 및 해석
김 용 구
- 1993년 : 연세대학교 전기공학과 졸업
- 1995년 : 연세대학교 전기및컴퓨터공학과 공학석사
- 2001년 : 연세대학교 전기전자공학과 공학박사
- 2001년 ~ 2002년 : 연세대학교 전파통신연구소 박사후연구원
- 2002년 ~ 2006년 : ㈜온타임텍 멀티미디어연구소 연구소장/이사
- 2006년 ~ 2009년 : 연세대학교 전기전자공학부 연구교수
- 2009년 ~ 현재 : KGIT 뉴미디어학부 교수
- 주관심분야 : 모바일 비디오/영상 통신, 3D/UHD 멀티미디어 신호처리 및 응용
References
Yilmaz A. , Javed O. , Shah M. 2006 “Object tracking: a survey“ ACM Computing Surveys Article 13 38 (4)    DOI : 10.1145/1177352.1177355
Comaniciu D. , Ramesh V. , Meer P. 2003 “Kernel-based object tracking“ IEEE Trans. PAMI 25 (5) 564 - 577    DOI : 10.1109/TPAMI.2003.1195991
Birchfield S. T. , Rangarajan S. 2005 “Spatiograms versus histograms for region-based tracking” in Proc. CVPR San Diego 1158 - 1163
Zhou H. , Yuan Y. , Shi C. 2009 "Object tracking using SIFT features and mean shift" Computer Vision and Image Understanding 113 (3) 345 - 352    DOI : 10.1016/j.cviu.2008.08.006
Collins R. T. 2003 "Mean-shift blob tracking through scale space" in Proc. CVPR Pittsburg II-234 - II-240
Yilmaz A. 2007 "Object tracking by assymmetric kernel mean shift with automatic scale and orientation selection" in Proc. CVPR Minneapolis 1 - 6
Zhao Q. , Yang Z. , Tao H. 2010 "Differential earth movers distance with its applications to visual tracking" IEEE Trans. PAMI 32 (2) 274 - 287    DOI : 10.1109/TPAMI.2008.299
Leichter I. 2012 "Mean shift trackers with cross-bin metrics" IEEE Trans. PAMI 34 (4) 695 - 706    DOI : 10.1109/TPAMI.2011.167
Jeyakar J. , Babu R. V. , Ramakrishnan K. R. 2008 "Robust object tracking with backgroundweighted local kernels" Computer Vision and Image Understanding 112 (3) 296 - 309    DOI : 10.1016/j.cviu.2008.05.005
Ning J. J. , Zhang L. , Zhang D. , Wu C. 2012 "Robust mean-shift tracking with corrected background-weighted histogram" IET Comput. Vis. 6 (1) 62 - 69    DOI : 10.1049/iet-cvi.2009.0075
Jai A. K. 1989 “Fundamentals of Digital Image Processing” Prentice Hall
Li P. 2008 “An Adaptive Binning Color Model for Mean Shift Tracking” IEEE Trans. CSVT 18 (9) 1293 - 1299
Choi E. , Lee S. , Kang M. G. 2010 “Object Tracking Algorithm Using Weighted Color Centroids Shifting” Journal of broadcast engineering 15 (2) 236 - 247    DOI : 10.5909/JBE.2010.15.2.236