Advanced
Fast MOG Algorithm Using Object Prediction
Fast MOG Algorithm Using Object Prediction
Journal of the Korea Institute of Information and Communication Engineering. 2014. Nov, 18(11): 2721-2726
Copyright © 2014, 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, 2014
  • Accepted : September 10, 2014
  • Published : November 30, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
정수 오
ojs@pknu.ac.kr

Abstract
배경제거를 위해 GMM(Gaussian Mixture Models)을 이용하는 MOG(Model of Gaussian) 알고리즘에서 각 화소들에서 수행될 모델변수 계산과 객체 분류는 방대한 계산을 요구하여 MOG 알고리즘의 활용들에 큰 걸림돌이 되고있다. 본 논문은 객체 예측을 근간으로 단순한 모델변수 계산과 객체 분류 생략을 부분적으로 수행하는 고속 MOG 알고리즘을 제안한다. 전자는 모델변수에 거의 영향을 주지 않는 화소에서 적용되고, 후자는 객체 예측이 확실히 믿을만한 화소에 적용된다. 동영상을 이용한 기존 알고리즘과 제안된 알고리즘의 비교 실험에서 제안된 알고리즘은 단순 모델변수 계산과 객체 분류 생략을 각각 77.75%와 92.97% 이상을 수행하지만 영상 단위와 이동 객체 단위의 평균 분류 정확도 측면에서 각각 99.98% 이상과 99.36% 이상을 유지시켜 주고 있다.
Keywords
Ⅰ. 서 론
동영상에서 이동 객체를 분리하기 위해 배경제거가 필수적으로 적용되고 있다 [1 - 3] . 배경제거를 위한 많은 알고리즘들이 연구되고 있는데 MOG 알고리즘은 대표적인 예이다. MOG 알고리즘은 영상의 모든 화소에서 시간 축에 대해 GMM을 수행하여 배경과 이동 객체를 구분한다 [4 - 7] . MOG 알고리즘은 화소마다 3~5개의 가우시안 모델을 채택하고 복수의 모델들을 배경으로 채택할 수 있어 신호등, 깃발, 나뭇잎 같이 능동적으로 변화하는 배경에 더욱 효율적이다 [4 , 5] . 그러나 MOG 알고리즘은 매 프레임마다 모든 화소들에서 GMM의 변수들을 갱신하여 많은 계산이 요구되고, 이는 시스템에 부담으로 작용된다. 그래서 MOG 알고리즘은 자주 영상 크기나 프레임 수를 줄여서 적용하고 있다.
본 논문은 MOG 알고리즘에서 객체 예측을 통해 계산적으로 부담이 큰 모델변수들의 계산을 선택적으로 단순화시키고 객체 분류를 생략하는 고속 MOG 알고리즘을 제안한다. MOG 알고리즘에서 모델들의 변수들은 정확한 값이 아닌 예측된 값이고, 배경과 이동 객체의 모델들이 분명히 구분되어 있다. 그래서 제안된 알고리즘은 이미 분류된 객체 정보를 이용해 먼저 현 화소를 분명 객체(이동 객체, 배경)과 불분명 객체로 예측하고, 분명 객체로 분류된 화소가 모델 평균에 근접하면 모델 변수에 영향이 적으므로 변수 갱신을 단순히 상수의 가감으로 구현하고, 또한 분명 객체에서 프레임간 화소차이가 적으면 주변 정보로 예측된 객체가 신뢰되므로 객체 분류를 생략하고 있다.
제안된 알고리즘의 성능을 평가하기 위해 1차원 영상 신호를 이용해 단순한 모델변수 계산의 유효성을 평가하고, 객체 예측을 시각적으로 보여주고 그 유효성을 평가한다. 또한 기존 알고리즘과 제안된 알고리즘을 동영상에 적용하여 계산량과 객체 분류 정확도에 대한 비교 평가를 수행하여 제안된 알고리즘이 계산량을 크게 줄이면서도 객체 분류 정확도를 기존 알고리즘만큼 유지하는 것을 보일 것이다.
본 논문의 구성은 서론에 이어 2장에서 MOG 알고리즘을 기술하고, 3장에서 제안된 객체 예측을 이용한 고속 MOG 알고리즘을 기술하고, 4장에서 기존 알고리즘과 제안된 알고리즘을 비교분석하고, 마지막으로 5장에서 결론을 맺는다.
Ⅱ. MOG 알고리즘
MOG 알고리즘은 모든 화소에서 시간 축의 화소들에 대해 GMM을 수행하여 배경과 이동 객체를 구분한다. 시간 t 의 각 화소( Xt )에서 K개의 가우시안 모델로 구성되는 GMM은 식 (1)과 같이 표현된다 [4 , 5] .
PPT Slide
Lager Image
여기서 μ k,t , k,t , w k,t 는 모델 변수인 가중치, 평균, 표준편차로 프레임마다 식 (2)에 의해 갱신된다.
PPT Slide
Lager Image
여기서 α 는 learning rate로 0.01~0.001이 사용되고 있고, ω , μ , σ 는 화소 밝기( Xt )와 모델 평균( μk )의 차이가 5 σ 2 k 보다 작아 매칭되는 모델에서만 갱신된다. 또한 p 는 근사화된 계산( α / ω k,t )이나 작은 상수를 사용하는데 여기서는 전자를 사용한다 [7] . K개 가우시안 모델 중 식(3)을 만족하는 모델들을 배경으로 결정한다.
PPT Slide
Lager Image
여기서 k α / σ 로 계산되는 주도 모델의 순서이다.
식 (1)~(3)의 계산은 프레임마다 모든 화소에서 수행되어 MOG 알고리즘의 활용에 부담을 주고 있다. 표 1 은 추후 실험될 동영상에서 배경을 추출할 때 배경제거 시간에 대한 영역별 계산 분포를 보여주고 있다. 배경제거에서 모델변수 계산과 객체 분류가 평균적으로 69.25%와 22.28%로 대부분 계산 시간을 차지하고 있는 것을 보여주고 있다.
계산시간 분포(%)Table. 1 Distribution of computation time(%)
PPT Slide
Lager Image
계산시간 분포(%) Table. 1 Distribution of computation time(%)
Ⅲ. 제안된 고속 MOG 알고리즘
본 장에서 객체 예측을 통해 부분적으로 단순 모델변수 계산과 객체 분류를 생략하는 고속 MOG 알고리즘을 기술한다. 그림 1 은 제안된 알고리즘의 블록도이다.
PPT Slide
Lager Image
제안된 고속 MOG 알고리즘 Fig. 1 Proposed fast MOG algorithm
객체예측은 그림 2 와 같이 이미 결정된 주변 객체 정보를 이용해 식 (4)와 같이 예측하는 것이다. 즉 동일한 객체로 둘러싸인 경우만 같은 객체로, 이동 객체의 경계는 배경에 인접해 불분명한 객체로 예측되도록 하여 객체예측의 신뢰성이 높다. MO와 BG는 각각 분명한 객체로 분류되는 이동 객체와 배경이고, MOBG는 객체 예측이 어려운 불분명한 객체이다. CO는 예측될 객체이고 COx는 현 프레임에서 이미 분류된 객체이고, POx는 이전 프레임에서 분류된 객체이다. COx과 POx는 이동 객체이면 1을 배경이면 0을 갖는다.
PPT Slide
Lager Image
PPT Slide
Lager Image
객체예측을 위한 화소들 Fig. 2 Pixels for object prediction
단순 모델변수 계산은 분명한 객체로 예측된 화소에서 모델 평균( μk )과 화소 밝기(X)의 차이가 α 2 k 보다 작은 화소, 즉 모델 중심부에 근접한 화소에서만 식 (5)와 같이 수행된다.
PPT Slide
Lager Image
배경과 이동 객체의 모델들이 대부분 분명히 구분되어 있고 모델 중심부에 근접한 화소로 제한하여 단순화된 식 (5)는 모델변수에 미세한 영향을 주지만 객체 분류에 영향을 주지 않는다. 반면, 모델 평균과 화소 밝기 차이가 큰 덜 분명한 객체와 불분명한 객체에서는 단순계산에 의해 모델변수 오차가 커질 수 있고 이로 인해 객체 분류에 영향을 줄 수 있어 기존 모델변수 계산 방식인 식 (2)를 사용한다.
전·현 프레임의 주변 객체 정보를 이용해 분명한 객체로 예측된 화소가 전·현 프레임의 화소 밝기 차이(| X-1 - X| )가 일정 값(T) 보다 작을 때 예측된 객체는 더욱 신뢰할 수 있어 객체 분류를 생략하여 앞에서 예측된 객체를 그 화소의 객체로 결정한다. 반면, 전·현 프레임의 화소 밝기 차이가 어느정도 있으면 예측된 객체를 확신할 수 없으므로 식 (3)의 기존 객체 분류를 수행하여 화소의 객체를 결정한다. 잘못 분류된 객체들은 다음 프레임의 객체 예측에 영향을 주므로 T를 모델 분산의 최소와 최대 분산의 중간 값인 4로 낮게 선택하였다.
Ⅳ. 실험 및 고찰
성능 평가를 위해 기존 MOG 알고리즘과 제안된 고속 MOG 알고리즘을 표 1 의 3가지 동영상에 적용하였다. in1은 실내 환경의 단순한 동영상이고, out1은 일반도로의 다소 복잡한 교통환경 동영상이고, out2는 학교내 단순한 교통환경 동영상이다. 실험 동영상들은 640x360의 해상도, 24Hz의 프레임 주파수의 영상이고 각각 프레임 수는 3000, 6000, 4500이다. 그러나 처리속도를 고려해 실제 실험에서는 프레임 주파수를 8Hz로 다운 샘플링하였다.
실험을 위한 동영상Table. 2 Videos for experiment
PPT Slide
Lager Image
실험을 위한 동영상 Table. 2 Videos for experiment
표 3 은 이동 객체를 포함하여 밝기 변화가 큰 위치의 화소에서 시간에 따른 기존 MOG와 고속 MOG에서 생성된 평균, 분산, 가중치, 분류된 이동 객체(ㅁ)를 비교하고 있다. 두 알고리즘에서 모델변수들의 변화 속도가 미세한 차이가 있으나 그 변화 추이가 거의 같아 분류된 이동 객체는 일치하고 있다. 이로 단순 모델변수 계산의 유효함을 판단할 수 있다.
모델변수들의 비교Table. 3 Comparison of model’s parameters
PPT Slide
Lager Image
모델변수들의 비교 Table. 3 Comparison of model’s parameters
그림 3 은 영상의 일부에서 객체예측 결과를 보여주고 있다. 검은 영역과 흰 영역은 각각 분명한 배경과 이동 객체로 예측한 영역이고 중간 밝기의 영역은 객체 예측이 어려운 불분명한 객체 영역이다. 이동 객체의 경계는 객체간 변화가 발생하여 보다 정확한 모델링이 필요하고, 제안된 알고리즘도 이들에 불분명 객체로 적절하게 예측하고 있다.
PPT Slide
Lager Image
객체 예측 Fig. 3 Object prediction
표 4 는 고속 MOG 알고리즘의 기존 알고리즘과 비교해 단순한 모델변수 계산과 객체 분류 생략을 선택한 비율을 보여주고 있다. 단순 모델변수 계산은 73.69%~ 84.17%를 객체 분류 생략을 90.62%~94.68%를 선택하여 계산 부담을 크게 줄여주고 있다. 제안된 알고리즘은 in1처럼 이동 객체 경계가 적을수록 더 효율적이다.
고속 MOG의 계산 감소(%)Table. 4 Computation reduce of the fast MOG(%)
PPT Slide
Lager Image
고속 MOG의 계산 감소(%) Table. 4 Computation reduce of the fast MOG(%)
기존 MOG 알고리즘에 대한 제안된 고속 MOG 알고리즘의 객체제거 정확도를 비교하기 위해 우선 (6)~(8)같은 평가식을 정의하고 있다. 식 (6)은 영상 단위의 분류 정확도를 표현하기 위한 식으로 전체 영상에서 분류된 객체가 일치하는 화소들의 비율이고, 식 (7)과 (8)은 이동 객체 단위의 분류 정확도를 표현하기 위한 식으로 각 MOG 알고리즘에서 검출된 이동 객체들에 대한 동시에 검출된 이동 객체의 비율이다.
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
표 5 는 영상 단위의 분류 정확도 측면에서 제안된 고속 MOG 알고리즘은 기존 MOG 알고리즘과 비교하여 99.97%이상의 화소에서 일치함을 보여주고 있고, 이동객체 단위의 분류 정확도 측면에서 98.03% 이상의 화소에서 일치함을 보여주고 있다. 이동 객체에서 오류는 주로 바람에 흔들이는 나뭇가지에서 화소 단위로 발생하고 있어 무시할 수 있다.
분류 정확도의 비교(%)Table. 5 Comparison of the classification accuracy(%)
PPT Slide
Lager Image
분류 정확도의 비교(%) Table. 5 Comparison of the classification accuracy(%)
Ⅴ. 결 론
MOG 알고리즘은 동영상에서 움직이는 객체를 검출하기 위한 대표적인 배경제거 알고리즘이다. 프레임의 모든 화소에서 수행되는 GMM 모델링과 객체 분류를 위한 방대한 계산은 MOG 알고리즘 사용에서 있어 가장 큰 문제이다. 제안된 알고리즘은 객체 예측을 근거로 부분적으로 단순 모델변수 계산과 객체 분류 생략을 채택하는 고속 알고리즘이다. 본 논문은 이동 객체를 포함하는 화소를 대상으로 단순 계산된 모델변수들이 기존 알고리즘의 모델변수들과 동일한 변화 추이를 보이는 것을 보여주었고, 객체 예측 결과를 시각화하여 제안된 객체 예측 알고리즘이 적절함을 보여 주었다. 동영상 실험을 통해 제안된 알고리즘은 평균적으로 77.75%이상과 92.97%이상을 단순 모델변수 계산과 객체 분류 생략을 채택하면서도 기존 알고리즘과 비교하여 영상 단위의 정확도 측면에서 99.97~99.99%, 객체 단위의 정확도 측면에서 98.03~99.99%를 유지시켜주고 있다. 따라서 제안된 고속 MOG 알고리즘은 기존 MOG 알고리즘을 충분히 대체할 수 있을 것이다.
Acknowledgements
이 논문은 부경대학교 자율창의학술연구비(2014년)에 의하여 연구되었음
BIO
오정수(Jeong-su Oh)
중앙대학교 대학원 전자공학과 공학석사
중앙대학교 첨단영상대학원 영상공학과 공학박사
현재 부경대학교 이미지시스템공학과
※관심분야 : 디지털영상처리, 비디오영상처리, 적외선 신호처리
References
McIvor A. M. 2000 “Background subtraction techniques,” Proc. of Image and Vision Computing 1 (3) 155 - 163
Mayo Z. , Tapamo J. R. “Background Subtraction Survey for Highway Surveillance,” in Proc. Annu. Symp. PRASA 2009 77 - 82
Cheung S.S. , Chandrika K. 2004 "Robust techniques for background subtraction in urban traffic video," Pro. of SPIE. 5308 (1) 881 - 892
Stauffer C. , Grimson W. 1999 "Adaptive background mixture models for real-time tracking," IEEE Computer Society Conference on 2 246 - 252
Stauffer C. , Grimson W. 2000 “Learning Patterns of Activity Using Real-time Tracking,” IEEE Trans. on PAMI 22 (8) 747 - 757    DOI : 10.1109/34.868677
Bouwmans T. , El Baf F. , Vachon B. 2008 "Background modeling using mixture of gaussians for foreground detection-a survey." Recent Patents on Computer Science 3 (1) 219 - 237    DOI : 10.2174/2213275910801030219
Power P.W. , Schoonees J.A. 2002 “Understanding background mixture models for foreground segmentation,“ Proc. of image and vision computing 2002 266 - 271