Advanced
Improved Mean-Shift Tracking using Adoptive Mixture of Hue and Saturation
Improved Mean-Shift Tracking using Adoptive Mixture of Hue and Saturation
Journal of the Korea Institute of Information and Communication Engineering. 2015. Oct, 19(10): 2417-2422
Copyright © 2015, The Korean Institute of Information and Commucation Engineering
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License(http://creativecommons.org/li-censes/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : July 23, 2015
  • Accepted : August 28, 2015
  • Published : October 31, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
한동 박
정수 오
ojs@pknu.ac.kr

Abstract
색상을 이용한 Mean-Shift 추적 알고리즘은 배경이 객체와 유사한 색상을 가질 때 객체 추적을 실패하는 문제가 있다. 본 논문은 색상 대신 새로운 조합 데이터 이용해 개선된 Mean-Shift 추적 알고리즘을 제안하고 있다. 새로운 데이터는 서로의 상관도가 낮은 색상과 채도의 적응적인 조합으로 생성된다. 즉, 제안된 알고리즘은 객체와 배경을 잘 구분되는 주 색요소와 그렇지 않은 부 색요소 선택하고, 주 색요소와 부 색요소의 상위 4 비트를 각각 조합 데이터의 상위 4비트와 하위 4 비트에 할당한다. 제안된 알고리즘은 배경이 객체와 유사한 색상을 갖는 추적 환경에서도 채도를 주 색요소로 선택함에 의해 추적 오차를 최대 2.0~4.2 화소, 평균 0.49~1.82 화소를 유지하면서 적절하게 객체를 추적한다.
Keywords
Ⅰ. 서 론
컴퓨터 비전 분야에서 객체 추적은 많은 영역들에서 활용되고 있고 이를 위한 다양한 알고리즘들이 제안되고 있다 [1 - 4] . Mean-Shift 추적 알고리즘은 대표적인 객체 추적 알고리즘 중 하나로 객체 모델과 객체 후보 영역에서 히스토그램 역투영(histogram-backprojection)을 추적 데이터로 무게중심을 반복적으로 찾아가는 비모수(non-parametric) 알고리즘이다 [4 - 7] .
일반적인 Mean-Shift 알고리즘에서 객체 추적을 위한 히스토그램 역투영을 생성하기 위해 적(red), 녹(green), 청(blue) 각각 8 비트 혹은 4 비트로 구성하는데 이는 많은 정보가 요구되어 비효율적이다 [6 - 9] . 그래서 많은 경우 색요소인 색상(hue), 채도(saturation), 명도(value) 중 색상 8 비트만을 이용해 추적 데이터를 생성한다 [8 , 9] . 색상을 이용하면 조명에 의한 영향을 줄일수 있는 이점도 있다.
하지만 색상을 이용한 Mean- Shift 추적 알고리즘은 객체와 배경의 색상이 분명히 구분되는 선명한 추적 환경에서 그 성능이 우수하나 배경이 객체와 유사한 색상을 갖는 모호한 추적 환경에서 객체 추적이 실패할 가능성이 커진다.
본 논문에서는 모호한 추적 환경에서 색상을 이용한 Mean-Shift 추적 알고리즘의 성능 개선을 위해 색상과 그것과 상관도가 떨어지는 채도를 적응적으로 조합한 데이터를 이용한 Mean- Shift 추적 알고리즘을 제안한다.
적응적인 데이터 조합을 위해 먼저 프레임 단위로 객체 영역과 객체 주변 배경 영역을 지정하고, 영역들의 평균 색상과 평균 채도를 이용해 객체와 배경을 잘 구분할 수 있는 주(main) 색요소(색상 혹은 채도)와 그렇지 않은 부(secondary) 색요소를 결정하고, 주 색요소 상위 4비트와 부 색요소 상위 4비트를 각각 조합 데이터의 상위 4비트와 하위 4비트에 할당한다. 제안된 Mean-Shift 추적 알고리즘은 조합 데이터의 히스토그램 역투영을 추적 데이터로 사용한다.
객체 추적 실험을 통해 제안된 알고리즘은 선명한 추적 환경에서 기존 알고리즘과 동등한 성능을 유지하면서 모호한 추적 환경에서도 선명한 추적 환경처럼 추적이 가능함을 보인다.
Ⅱ. Mean-Shift 추적 알고리즘
Mean-Shift 알고리즘은 관심 영역 내에 데이터 분포가 가장 밀집된 위치를 찾아가는 알고리즘으로 히스토그램 역투영 알고리즘과 같이 사용해 객체 추적에 많이 사용되고 있다 [5 , 7 , 8] . 히스토그램 역투영 알고리즘은 영상을 색 데이터 대신 객체 모델과 객체 후보 영역의 데이터 히스토그램 비로 변환하는 것이다. 히스토그램 역투영을 위해 객체와 객체 후보 영역에서 히스토그램빈()의 값을 각각 식 (1)과 (2)로 얻는다.
PPT Slide
Lager Image
PPT Slide
Lager Image
여기서 x * 는 표적 영역의 중심과 화소( xi =1~ n )간 거리이고, b ( xi )는 xi 에 대응되는 데이터이고 Cq Cp 는 히스토그램 정규화를 위한 상수이고, k ( ), h , 그리고 nh 는 각각 커널 프로파일, 커널 크기, 커널 내 화소 수이다. δ 는 Kronecker delta function이며 a = 0일 때만 δ ( a ) = 1이다. 객체 추적을 위한 히스토그램 비는 식 (1)과 (2)를 이용해 식 (3)과 같이 계산된다.
PPT Slide
Lager Image
여기서 y 0 은 객체 후보 영역의 중심에서 시작하는 객체의 이전 위치이다. 식 (3)을 이용한 Mean-Shift 추적은 식 (4)을 이용해 반복적으로 새로운 객체 위치( y 1 )로 접근한다.
PPT Slide
Lager Image
여기서 g ( )는 앞서 언급한 k ( )의 Shadow Kernel 프로파일이다. 반복 접근을 위한 두 영역의 유사도 측정은 식 (5)의 Bhattacharyya 계수 ρ 를 사용한다 [5 , 7] .
PPT Slide
Lager Image
색상을 이용한 Mean-Shift 추적 알고리즘은 객체가 자신과 유사한 색상을 갖는 배경을 지날 때 추적에 실패하는 문제를 갖고 있다. 그림 1 은 Mean-Shift 추적의 예를 보여주고 있다. 그림 1 (a)는 객체와 배경의 색상이 서로 잘 구분되어 적절한 추적을 수행하는 것을 보여주고 있고 그림 1 (b)는 객체가 자신과 유사한 색상을 갖는 배경을 통과하면서 객체 추적을 실패하는 모습을 보여주고 있다. 영상에서 좌측상단의 작은 영상은 객체이고 박스는 추적된 객체이다.
PPT Slide
Lager Image
Mean-Shift 추적 예 (a) 객체 추적 1 (b) 객체 추적 2 Fig. 1 Example of Mean-Shift tracking (a) Object tracking 1 (b) Object tracking 2
Ⅲ. 제안된 알고리즘
제안된 알고리즘은 색상을 이용한 기존 알고리즘의 문제를 해결하고자 색상과 채도를 적응적으로 조합한 데이터를 이용해 추적 데이터를 프레임 단위로 그림 2 와 같이 생성하고 있다.
PPT Slide
Lager Image
추적 데이터 생성 Fig. 2 Generation of tracking data
조합 데이터를 생성하기 위해 색요소 중 색상과 채도를 이용하고 있는데 색상과 채도의 상관(corelation) HSC가 색상과 명도(value)의 상관 HVC보다 작기 때문이다. 표 1 은 임의의 자연계 영상에서 계산된 색요소간 상관을 보여주고 있다. 모든 영상에서 HSC가 작다.
색요소간 상관Table. 1 Corelation between attributes of color
PPT Slide
Lager Image
색요소간 상관 Table. 1 Corelation between attributes of color
추적 데이터 생성을 위한 ROI 블록은 주 색요소 결정 기준인 RateX 를 계산하는 영역을 그림 3 과 같이 지정한다. 전 프레임에서 추적된 객체 중심 위치를 중심으로 한 관심 객체 영역(①)과 객체 영역 주변에 크기가 2 배로 한 관심 배경 영역(②)을 지정한다.
PPT Slide
Lager Image
RateX 계산을 위한 영역 지정 Fig. 3 Range designation for RateX computation
RateX 블록은 그림 3 의 관심 영역에서 객체 영역(O)와 배경 영역(B)간 색상(H)의 다름과 채도(H)의 다름을 나타내는 RateX 를 다음 식과 같이 계산한다.
PPT Slide
Lager Image
PPT Slide
Lager Image
여기서
PPT Slide
Lager Image
는 색요소 x 의 영역 평균이다. RateX 가 크면 색요소 x 에 의해 객체와 배경이 서로 잘 구분된다. MainAC 블록은 식 6과 7을 이용해 추적 데이터의 주도 성분이 되는 주 색요소를 표 2 와 같이 결정한다. 상대적으로 큰 RateX 의 색요소를 추적 데이터를 위한 주 색요소로 결정하고 그렇지 못한 경우 (*)는 대비가 큰 색상을 주 색요소로 결정한다.
주 색요소 결정Table. 2 Decision of a main attribute of color
PPT Slide
Lager Image
주 색요소 결정 Table. 2 Decision of a main attribute of color
MixAC 블록은 색상을 대체할 조합 데이터를 생성한다. 조합 데이터는 색상과 채도의 상위 4비트(H7~H4, S7~S4)를 그림 4 와 같이 조합한다. 앞에서 결정된 주 색요소의 상위 4비트가 조합 데이터의 상위 4비트(M7~M4)에 위치하고 부 색요소의 상위 4비트가 조합 데이터의 하위 4비트(s3~s0)에 위치한다.
PPT Slide
Lager Image
두 색요소 조합 Fig. 4 Mixture of two attributes of color
그림 5 는 색요소 데이터와 조합 데이터의 히스토그램 역투영을 영상으로 비교하고 있다. 그림 5 (a)는 객체 추적 중 한 프레임을 보여주고 있다. 그림 5 (b)와 (c)는 각각 색상과 채도의 히스토그램 역투영으로 색상에서 객체와 배경이 구분되지 않으나 채도에서 구분되는 것을 보여주고 있다.
PPT Slide
Lager Image
히스토그램 역투영을 위한 영상 (a) 객체 (b) 색상 (c) 채도 (d) S-H조합 (e) H-S조합 Fig. 5 Images for histogram-backprojection (a) Object (b) Hue (c) Saturation (d) S-H mixture (e) H-S mixture
제안된 알고리즘은 표 1 에 의해 채도를 주 색요소로 결정하고 채도-색상 조합 데이터를 생성한다. 히스토그램 역투영이 그림 5 (c)에 보여주고 있다. 여기서도 객체와 배경이 적절히 잘 구분되고 있다.
일반적으로 동영상의 모든 프레임에서 색상 혹은 채도가 객체와 배경을 잘 구분시켜 줄 수는 없다. 그래서 제안된 알고리즘처럼 프레임 단위로 주 색요소를 선택하는 것은 의미가 있다.
또한 두 색요소를 조합하는 것은 그림 5 (e)와 같이 주색요소를 잘못 결정되었을 때 영향을 적게 받으며 객체와 배경의 구분을 가능하게 한다.
Ⅳ. 실험 결과
제안된 알고리즘의 성능 평가를 위해 표 3 의 모호한 추적 환경인 video1~4와 선명한 추적 환경인 video5에서 객체 추적이 수행되었다. 객체 추적은 영상 내 움직이는 객체를 사각형 형태로 선택하는 순간 시작된다. 선택된 객체 크기는 가로세로 모두 20~30 화소이다.
객체 주척을 위한 동영상들Table. 3 Videos for object tracking
PPT Slide
Lager Image
객체 주척을 위한 동영상들 Table. 3 Videos for object tracking
그림 6 는 video1를 이용한 객체 추적 중 한 프레임을 보여주고 있다. 객체와 색상이 유사한 배경 영역에서 기존 알고리즘은 객체를 벗어난 추적 모습(굵은 사각형)을 보여주는 반면에 제안된 알고리즘은 객체를 잘 추적하는 모습(가는 사각형)을 보여주고 있다.
PPT Slide
Lager Image
추적 결과의 비교 Fig. 6 Comparison of tracking results
그림 7 8 은 모호한 추적 환경인 video1,2와 video3,4에서 객체를 추적하는 동안 추적 오차를 실제 객체와 추적된 객체의 중심간 거리로 보여주고 있다. 범례에 표시된 숫자는 video 번호이다.
PPT Slide
Lager Image
추적 오차 (video1,2) Fig. 7 Tracking error (video1,2)
PPT Slide
Lager Image
추적 오차 (video3,4) Fig. 8 Tracking error (video3,4)
표 4 는 제안된 알고리즘의 추적 오차의 평균과 최대를 보여주고 있다. 단 분명한 추적 환경인 video5에는 괄호 안 기존 알고리즘의 결과를 같이 보여주고 있다. 모호한 추적 환경에서 기존 알고리즘은 video2를 제외한 모든 동영상에서 쉽게 추적에 실패하는 반면 제안된 알고리즘은 동영상에 따라 다소 차이가 있지만 최대 2.00~4.20, 평균 0.49~ 1.82 화소 간격을 유지하면서 잘 추적하고 있다. 분명한 추적 환경에서는 제안된 알고리즘은 기존 알고리즘과 비교해 최대 오차는 같고 평균오차가 불과 0.06 화소로 추적 성능이 동등하다.
추적 오차의 평균과 최대Table. 4 Average and maximum of tracking error
PPT Slide
Lager Image
추적 오차의 평균과 최대 Table. 4 Average and maximum of tracking error
표 5 는 추적되는 객체 중심이 실제 객체 영역내에 유지되는 동안 프레임당 Mean-Shift의 반복 횟수를 보여주고 있다. 모호한 추적 환경에서 기존 알고리즘(CA)은 3.18~3.50회인데 제안된 알고리즘(PA)은 1.72~2.04회이다. 그리고 분명한 추적 환경에서에서 단지 0.16회 차이만 난다.
프레임당 반복 횟수Table 5. Number of iterations per a frame
PPT Slide
Lager Image
프레임당 반복 횟수 Table 5. Number of iterations per a frame
Ⅴ. 결 론
본 논문에서는 Mean-Shift 추적 알고리즘에 사용되는 히스토그램 역투영을 프레임 단위로 색상과 채도의 적응적인 조합을 통해 생성하였다. 선명한 추적 환경에서 제안된 알고리즘은 기존 알고리즘과 동등한 성능을 보였고, 모호한 추적 환경에서는 객체와 배경을 잘 구분할 수 있는 색요소를 주도적으로 사용하여 기존 알고리즘보다 그 성능이 우위에 있고 두 성분을 조합함으로 주 색요소가 분명하지 않거나 잘못된 선택되어도 그 영향을 줄일 수 있었다. 모호한 추적 환경에서 기존 알고리즘은 유사 색상을 만나는 순간부터 객체에서 점점 멀어지는 반면 제안된 알고리즘은 최대 2.0~4.2 화소 간격내에서 평균 0.49~1.82 간격을 유지하며 객체 추적을 수행하였다. 또한 프레임당 수행되는 Mean-Shift의 횟수가 기존 알고리즘은 3.18~3.50인데 제안된 알고리즘은 1.72~2.04로 제안된 알고리즘의 우수함을 보여주고 있다.
Acknowledgements
This work was supported by a Research Grant of Pukyong National University (2015 year)
BIO
박한동(Han-dong Park)
부경대학교 융합디스플레이공학과 공학사
부경대학교 대학원 융합디스플레이공학과 재학
※관심분야 : 디지털영상처리, 비디오영상처리
오정수(Jeong-su Oh)
중앙대학교 대학원 전자공학과 공학석사
중앙대학교 첨단영상대학원 영상공학과 공학박사
현재 부경대학교 융합디스플레이공학과
※관심분야 : 디지털영상처리, 비디오영상처리, 적외선 신호처리
References
Yulmaz A. , Javed O. , Shah M. 2006 “Object tracking: A survey,” ACM Computing Surveys (CSUR) (13) 38 (4)
Weng S. , Kuo C. , Tu S. 2006 “Video object tracking using adaptive Kalman filter,” Journal of Visual Communication and Image Representation 17 (6) 1190 - 1208    DOI : 10.1016/j.jvcir.2006.03.004
Mae Y. , Shirai Y. , Miura J. , Kuno Y. “Object Tracking in Clustered Background Based on Optical Flow and Edges,” Pattern Recognition, 1996, Proc. of the 13th International Conf. 1996 vol. 1
Comaniciu D. , Meer P. 2002 “Mean Shift: A Robust Approach Toward Feature Space Analysis,” IEEE Transactions on PAMI 24 (5)    DOI : 10.1109/34.1000236
Comaniciu D. , Ramesh V. , Meer P. 2003 “Kernel-Based Object Tracking,” IEEE Transactions on PAMI 25 (5)    DOI : 10.1109/TPAMI.2003.1195991
Peng N. S. , Yang J. 2004 “Mean-Shift Blob Tracking with Kernel-Color Distribution Estimate and Adaptive Model Update Criterion,” Lecture Notes in Computer Science 3247 83 - 93
Ning J. , Zhang L. , Zhang D. , Wu C. 2012 “Robust Mean Shift Tracking with Corrected Background-Weighted Histogram,” IET Computer Vision 6 (1) 62 - 69    DOI : 10.1049/iet-cvi.2009.0075
Lee J. H. , Lee W. H. , Jeong D. S. “Object tracking method using back-projection of multiple color histogram models,” In Circuits and Systems, 2003. ISCAS'03. Proc. of the 2003 International Symposium on 2003 vol. 2 II-668 -
Wang H. , Suter D. “Color Image Segmentation Using GlobalInformation and Local Homogeneity,” Proc. of 7th Conf. of DICTA 2003