색상과 채도의 적응적 조합을 이용한 개선된 Mean-Shift 추적

Improved Mean-Shift Tracking using Adoptive Mixture of Hue and Saturation

  • cc icon
  • ABSTRACT

    색상을 이용한 Mean-Shift 추적 알고리즘은 배경이 객체와 유사한 색상을 가질 때 객체 추적을 실패하는 문제가 있다. 본 논문은 색상 대신 새로운 조합 데이터 이용해 개선된 Mean-Shift 추적 알고리즘을 제안하고 있다. 새로운 데이터는 서로의 상관도가 낮은 색상과 채도의 적응적인 조합으로 생성된다. 즉, 제안된 알고리즘은 객체와 배경을 잘 구분되는 주 색요소와 그렇지 않은 부 색요소 선택하고, 주 색요소와 부 색요소의 상위 4 비트를 각각 조합 데이터의 상위 4비트와 하위 4 비트에 할당한다. 제안된 알고리즘은 배경이 객체와 유사한 색상을 갖는 추적 환경에서도 채도를 주 색요소로 선택함에 의해 추적 오차를 최대 2.0~4.2 화소, 평균 0.49~1.82 화소를 유지하면서 적절하게 객체를 추적한다.


    Mean-Shift tracking using hue has a problem that it fail in the object tracking when background has similar hue to the object. This paper proposes an improved Mean-Shift tracking algorithm using new data instead of a hue. The new data is generated by adaptive mixture of hue and saturation which have low interrelationship . That is, the proposed algorithm selects a main attribute of color that is able to distinguish the object and background well and a secondary one which don’t, and places their upper 4 bits on upper 4 bits and lower 4 bits on the mixture data, respectively. The proposed algorithm properly tracks the object, keeping tracking error maximum 2.0~4.2 pixel and average 0.49~1.82 pixel, by selecting the saturation as the main attribute of color under tracking environment that background has similar hue to the object.

  • KEYWORD

    Mean-Shift , 객체 , 추적 , 색상 , 채도

  • Ⅰ. 서 론

    컴퓨터 비전 분야에서 객체 추적은 많은 영역들에서 활용되고 있고 이를 위한 다양한 알고리즘들이 제안되고 있다[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)로 얻는다.

    image
    image

    여기서 x*는 표적 영역의 중심과 화소(xi=1~n)간 거리이고, b(xi)는 xi에 대응되는 데이터이고 CqCp는 히스토그램 정규화를 위한 상수이고, k( ), h, 그리고 nh는 각각 커널 프로파일, 커널 크기, 커널 내 화소 수이다. δ는 Kronecker delta function이며 a = 0일 때만 δ(a) = 1이다. 객체 추적을 위한 히스토그램 비는 식 (1)과 (2)를 이용해 식 (3)과 같이 계산된다.

    image

    여기서 y0은 객체 후보 영역의 중심에서 시작하는 객체의 이전 위치이다. 식 (3)을 이용한 Mean-Shift 추적은 식 (4)을 이용해 반복적으로 새로운 객체 위치(y1)로 접근한다.

    image

    여기서 g ( )는 앞서 언급한 k ( )의 Shadow Kernel 프로파일이다. 반복 접근을 위한 두 영역의 유사도 측정은 식 (5)의 Bhattacharyya 계수 ρ를 사용한다[5,7].

    image

    색상을 이용한 Mean-Shift 추적 알고리즘은 객체가 자신과 유사한 색상을 갖는 배경을 지날 때 추적에 실패하는 문제를 갖고 있다. 그림 1은 Mean-Shift 추적의 예를 보여주고 있다. 그림 1(a)는 객체와 배경의 색상이 서로 잘 구분되어 적절한 추적을 수행하는 것을 보여주고 있고 그림 1(b)는 객체가 자신과 유사한 색상을 갖는 배경을 통과하면서 객체 추적을 실패하는 모습을 보여주고 있다. 영상에서 좌측상단의 작은 영상은 객체이고 박스는 추적된 객체이다.

    Ⅲ. 제안된 알고리즘

    제안된 알고리즘은 색상을 이용한 기존 알고리즘의 문제를 해결하고자 색상과 채도를 적응적으로 조합한 데이터를 이용해 추적 데이터를 프레임 단위로 그림 2와 같이 생성하고 있다.

    조합 데이터를 생성하기 위해 색요소 중 색상과 채도를 이용하고 있는데 색상과 채도의 상관(corelation) HSC가 색상과 명도(value)의 상관 HVC보다 작기 때문이다. 표 1은 임의의 자연계 영상에서 계산된 색요소간 상관을 보여주고 있다. 모든 영상에서 HSC가 작다.

    추적 데이터 생성을 위한 ROI 블록은 주 색요소 결정 기준인 RateX를 계산하는 영역을 그림 3과 같이 지정한다. 전 프레임에서 추적된 객체 중심 위치를 중심으로 한 관심 객체 영역(①)과 객체 영역 주변에 크기가 2 배로 한 관심 배경 영역(②)을 지정한다.

    RateX 블록은 그림 3의 관심 영역에서 객체 영역(O)와 배경 영역(B)간 색상(H)의 다름과 채도(H)의 다름을 나타내는 RateX를 다음 식과 같이 계산한다.

    image
    image

    여기서 는 색요소 x의 영역 평균이다. RateX가 크면 색요소 x에 의해 객체와 배경이 서로 잘 구분된다. MainAC 블록은 식 6과 7을 이용해 추적 데이터의 주도 성분이 되는 주 색요소를 표 2와 같이 결정한다. 상대적으로 큰 RateX의 색요소를 추적 데이터를 위한 주 색요소로 결정하고 그렇지 못한 경우 (*)는 대비가 큰 색상을 주 색요소로 결정한다.

    MixAC 블록은 색상을 대체할 조합 데이터를 생성한다. 조합 데이터는 색상과 채도의 상위 4비트(H7~H4, S7~S4)를 그림 4와 같이 조합한다. 앞에서 결정된 주 색요소의 상위 4비트가 조합 데이터의 상위 4비트(M7~M4)에 위치하고 부 색요소의 상위 4비트가 조합 데이터의 하위 4비트(s3~s0)에 위치한다.

    그림 5는 색요소 데이터와 조합 데이터의 히스토그램 역투영을 영상으로 비교하고 있다. 그림 5(a)는 객체 추적 중 한 프레임을 보여주고 있다. 그림 5(b)와 (c)는 각각 색상과 채도의 히스토그램 역투영으로 색상에서 객체와 배경이 구분되지 않으나 채도에서 구분되는 것을 보여주고 있다.

    제안된 알고리즘은 표 1에 의해 채도를 주 색요소로 결정하고 채도-색상 조합 데이터를 생성한다. 히스토그램 역투영이 그림 5(c)에 보여주고 있다. 여기서도 객체와 배경이 적절히 잘 구분되고 있다.

    일반적으로 동영상의 모든 프레임에서 색상 혹은 채도가 객체와 배경을 잘 구분시켜 줄 수는 없다. 그래서 제안된 알고리즘처럼 프레임 단위로 주 색요소를 선택하는 것은 의미가 있다.

    또한 두 색요소를 조합하는 것은 그림 5(e)와 같이 주색요소를 잘못 결정되었을 때 영향을 적게 받으며 객체와 배경의 구분을 가능하게 한다.

    Ⅳ. 실험 결과

    제안된 알고리즘의 성능 평가를 위해 표 3의 모호한 추적 환경인 video1~4와 선명한 추적 환경인 video5에서 객체 추적이 수행되었다. 객체 추적은 영상 내 움직이는 객체를 사각형 형태로 선택하는 순간 시작된다. 선택된 객체 크기는 가로세로 모두 20~30 화소이다.

    그림 6는 video1를 이용한 객체 추적 중 한 프레임을 보여주고 있다. 객체와 색상이 유사한 배경 영역에서 기존 알고리즘은 객체를 벗어난 추적 모습(굵은 사각형)을 보여주는 반면에 제안된 알고리즘은 객체를 잘 추적하는 모습(가는 사각형)을 보여주고 있다.

    그림 78은 모호한 추적 환경인 video1,2와 video3,4에서 객체를 추적하는 동안 추적 오차를 실제 객체와 추적된 객체의 중심간 거리로 보여주고 있다. 범례에 표시된 숫자는 video 번호이다.

    표 4는 제안된 알고리즘의 추적 오차의 평균과 최대를 보여주고 있다. 단 분명한 추적 환경인 video5에는 괄호 안 기존 알고리즘의 결과를 같이 보여주고 있다. 모호한 추적 환경에서 기존 알고리즘은 video2를 제외한 모든 동영상에서 쉽게 추적에 실패하는 반면 제안된 알고리즘은 동영상에 따라 다소 차이가 있지만 최대 2.00~4.20, 평균 0.49~ 1.82 화소 간격을 유지하면서 잘 추적하고 있다. 분명한 추적 환경에서는 제안된 알고리즘은 기존 알고리즘과 비교해 최대 오차는 같고 평균오차가 불과 0.06 화소로 추적 성능이 동등하다.

    표 5는 추적되는 객체 중심이 실제 객체 영역내에 유지되는 동안 프레임당 Mean-Shift의 반복 횟수를 보여주고 있다. 모호한 추적 환경에서 기존 알고리즘(CA)은 3.18~3.50회인데 제안된 알고리즘(PA)은 1.72~2.04회이다. 그리고 분명한 추적 환경에서에서 단지 0.16회 차이만 난다.

    Ⅴ. 결 론

    본 논문에서는 Mean-Shift 추적 알고리즘에 사용되는 히스토그램 역투영을 프레임 단위로 색상과 채도의 적응적인 조합을 통해 생성하였다. 선명한 추적 환경에서 제안된 알고리즘은 기존 알고리즘과 동등한 성능을 보였고, 모호한 추적 환경에서는 객체와 배경을 잘 구분할 수 있는 색요소를 주도적으로 사용하여 기존 알고리즘보다 그 성능이 우위에 있고 두 성분을 조합함으로 주 색요소가 분명하지 않거나 잘못된 선택되어도 그 영향을 줄일 수 있었다. 모호한 추적 환경에서 기존 알고리즘은 유사 색상을 만나는 순간부터 객체에서 점점 멀어지는 반면 제안된 알고리즘은 최대 2.0~4.2 화소 간격내에서 평균 0.49~1.82 간격을 유지하며 객체 추적을 수행하였다. 또한 프레임당 수행되는 Mean-Shift의 횟수가 기존 알고리즘은 3.18~3.50인데 제안된 알고리즘은 1.72~2.04로 제안된 알고리즘의 우수함을 보여주고 있다.

  • 1. Yulmaz A., Javed O., Shah M. 2006 “Object tracking: A survey,” [ACM Computing Surveys (CSUR)] Vol.38 google
  • 2. Weng S., Kuo C., Tu S. 2006 “Video object tracking using adaptive Kalman filter,” [Journal of Visual Communication and Image Representation] Vol.17 P.1190-1208 google doi
  • 3. Mae Y., Shirai Y., Miura J., Kuno Y. 1996 “Object Tracking in Clustered Background Based on Optical Flow and Edges,” [Pattern Recognition, 1996, Proc. of the 13th International Conf.] google
  • 4. Comaniciu D., Meer P. 2002 “Mean Shift: A Robust Approach Toward Feature Space Analysis,” [IEEE Transactions on PAMI] Vol.24 google doi
  • 5. Comaniciu D., Ramesh V., Meer P. 2003 “Kernel-Based Object Tracking,” [IEEE Transactions on PAMI] Vol.25 google doi
  • 6. 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] Vol.3247 P.83-93 google
  • 7. Ning J., Zhang L., Zhang D., Wu C. 2012 “Robust Mean Shift Tracking with Corrected Background-Weighted Histogram,” [IET Computer Vision] Vol.6 P.62-69 google doi
  • 8. Lee J. H., Lee W. H., Jeong D. S. 2003 “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] P.II-668 google
  • 9. Wang H., Suter D. 2003 “Color Image Segmentation Using GlobalInformation and Local Homogeneity,” [Proc. of 7th Conf. of DICTA] google
  • [] 
  • [] 
  • [] 
  • [] 
  • [] 
  • [그림 1.] Mean-Shift 추적 예 (a) 객체 추적 1 (b) 객체 추적 2
    Mean-Shift 추적 예 (a) 객체 추적 1 (b) 객체 추적 2
  • [그림 2.] 추적 데이터 생성
    추적 데이터 생성
  • [표 1.] 색요소간 상관
    색요소간 상관
  • [그림 3.] RateX 계산을 위한 영역 지정
    RateX 계산을 위한 영역 지정
  • [] 
  • [] 
  • [표 2.] 주 색요소 결정
    주 색요소 결정
  • [그림 4.] 두 색요소 조합
    두 색요소 조합
  • [그림 5.] 히스토그램 역투영을 위한 영상 (a) 객체 (b) 색상 (c) 채도 (d) S-H조합 (e) H-S조합
    히스토그램 역투영을 위한 영상 (a) 객체 (b) 색상 (c) 채도 (d) S-H조합 (e) H-S조합
  • [표 3.] 객체 주척을 위한 동영상들
    객체 주척을 위한 동영상들
  • [그림 6.] 추적 결과의 비교
    추적 결과의 비교
  • [그림 7.] 추적 오차 (video1,2)
    추적 오차 (video1,2)
  • [그림 8.] 추적 오차 (video3,4)
    추적 오차 (video3,4)
  • [표 4.] 추적 오차의 평균과 최대
    추적 오차의 평균과 최대
  • [표 5.] 프레임당 반복 횟수
    프레임당 반복 횟수