논문 13-38A-06-05 한국통신학회논문지 '13-06 Vol.38A No.06 http://dx.doi.org/10.7840/kics.2013.38a.6.486 객체검출을위한빠르고효율적인 Haar-Like 피쳐선택알고리즘 정병우, 박기영 *, 황선영 A Fast and Efficient Haar-Like Feature Selection Algorithm for Object Detection Byung Woo Chung, Ki-Yeong Park *, Sun-Young Hwang 요 약 본논문은객체검출 (object detection) 에사용되는분류기의학습을위한빠르고효율적인 Haar-like feature 선택알고리듬을제안한다. 기존 AdaBoost를이용한 Haar-like feature 선택알고리듬은학습샘플들에대한피쳐의에러만을고려하여형태적으로유사하거나중복되는피쳐가선택되는경우가많았다. 제안하는알고리듬은피쳐의형태와피쳐간의거리로부터피쳐의유사도를계산하고이미선택된피쳐와유사도가큰피쳐들을피쳐세트에서제거하여빠르고효율적인피쳐선택이이루어지도록하였다. FERET 얼굴데이터베이스를사용하여제안된알고리듬을사용하여학습시킨분류기와기존알고리듬을사용한분류기의성능을비교하였다. 실험결과제안한피쳐선택방법을사용하여학습시킨분류기가기존방법을사용한분류기보다향상된성능을보였으며, 동일한성능을갖도록학습시켰을경우분류기의피쳐수가 20% 감소하였다. Key Words : Haar-like Feature, Machine Learning, Classifier, Feature Selection, Object Detection ABSTRACT This paper proposes a fast and efficient Haar-like feature selection algorithm for training classifier used in object detection. Many features selected by Haar-like feature selection algorithm and existing AdaBoost algorithm are either similar in shape or overlapping due to considering only feature s error rate. The proposed algorithm calculates similarity of features by their shape and distance between features. Fast and efficient feature selection is made possible by removing selected features and features with high similarity from feature set. FERET face database is used to compare performance of classifiers trained by previous algorithm and proposed algorithm. Experimental results show improved performance comparing classifier trained by proposed method to classifier trained by previous method. When classifier is trained to show same performance, proposed method shows 20% reduction of features used in classification. 색 (image retrieval), 감시카메라, 첨단운전자지원시스템 (Advanced Driver Assistance System) 을객체검출 (object detection) 은영상에서얼굴이나비롯한많은분야에서사용된다 [1,2]. 객체검출이다차량같은특정종류의객체를찾는것으로영상검양한분야에서응용되기위해서는빠른처리속도가 주저자 : 서강대학교전자공학과 CAD&ES 연구실, jas8254@sogang.ac.kr, 학생회원 교신저자 : 서강대학교전자공학과 CAD&ES 연구실, hwang@sogang.ac.kr, 종신회원 * 서강대학교전자공학과 CAD&ES 연구실, cpky@miware.co.kr 논문번호 :KICS2013-04-199, 접수일자 :2013년 4월 30일, 최종논문접수일자 :2013년 6월 5일 486 Ⅰ. 서론
논문 / 객체검출을위한빠르고효율적인 Haar-Like 피쳐선택알고리즘 중요하다. Viola와 Jones에의해제안된 Haar-like feature [3] 와 AdaBoost [4] 에기반한객체검출기술은높은정확도와빠른처리속도를보여주어많은연구들에서응용되었다 [5-7]. Haar-like feature는적분영상 [3] 을사용하면빠르게계산할수있으며, AdaBoost 알고리듬은분별력이가장높은피쳐를선택하여강분류기를학습시키는데사용한다. 이들은여러강분류기들을간단한것에서복잡한것의순서로배치한 cascade 구조를사용하여정확도를유지하면서도처리속도가높은객체검출기를구현하였다 [8]. 객체검출에서는객체의자세, 주위환경또는이미지의상태에영향을적게받는피쳐들을사용해야한다. 기존의피쳐선택방법은 Wrapper model [9] 과 Filter model [10] 이있다. Wrapper model은미리정해진학습알고리듬의정확도를기반으로선택된피쳐세트의유용도를결정한다. 이방법은피쳐의개수가많아질수록유용도를계산하는데필요한시간이늘어난다는단점이있다 [9]. Filter model은피쳐선택을분류기의학습과정과분리하고다른어떠한학습알고리듬과는독립적으로피쳐세트를선택하는방법으로학습데이터의각종특징점들을추출하여이를기준으로피쳐세트를선택한다. Viola와 Jones가사용한 AdaBoost에기반한피쳐선택방법은 Wrapper model 방법보다빠르다 [11]. AdaBoost를이용한피쳐선택방법은가중치가고려된학습샘플들에대해서가장작은에러를보이는피쳐를선택하는것으로최적화된방법이아니다. 이를개선하기위하여 AdaBoost와함께부동탐색알고리듬 [12], 진화탐색알고리듬 [13] 을사용하는방법이제안되었다. 그러나이들방법도피쳐의에러만을고려하고피쳐의형태는고려하지않아이전피쳐와유사하거나중복되는피쳐가선택되는경우가발생한다. 기존연구에서는 PCA를이용하여분류기를구성하는피쳐의수를줄이는방법 [14] 이사용되었지만, 본논문에서는피쳐의에러와함께형태적유사도를고려하는피쳐선택방법을제안한다. 제안된방법을사용하면유사하거나중복되는피쳐가제거되어객체를더효율적으로기술할수있다. 논문의구성은다음과같다. 2절에서는연구배경을설명하고, 3절에서는 Haar-like feature의유사도계산방법과이를이용한효율적인피쳐선택방법을기술한다. 4절에서는제안된방법을사용하여학습시킨분류기와기존방법으로학습시킨분류기와비교한다. 5절에서는결론및추후과제를제시한다. Ⅱ. 연구배경 본절에서는 Viola와 Jones의객체검출기를구성하는 Haar-like feature, 적분영상과 AdaBoost 알고리듬에대해설명하고 AdaBoost를이용한피쳐선택방법에대해설명한다. 2.1. Haar-like feature Papageorgiou [15] 등은객체의공통적이특징을기술하기위해 Haar wavelet을사용할것을제안하였고 Viola와 Jones [3] 는이를확장시킨 Haar-like feature의사용을제안하였다. Haar-like feature는그림 1과같이두개이상의인접한사각형영역들로구성되며그값은영역들간의밝기차로정의된다. 2.2. 적분영상 Haar-like feature는적분영상을사용하면그크기와상관없이일정한연산량으로계산할수있다. 적분영상은각픽셀이영상의원점으로부터해당픽셀위치까지의사각형영역의모든픽셀들의합을갖는영상이다. 그림 2에서사각형 D영역의픽셀들의합은적분영상에서 4개의픽셀만을참조하여계산할수있다. 적분영상에서의픽셀 1은 A영역의픽셀들의합이며픽셀 2는 A와 B영역의합, 픽셀 3은 A, C영역의합, 그리고픽셀 4는 A, B, C, D영역의합이므로 D영역픽셀들의합은적분영상의 4개픽셀을참조하여 4+1-(2+3) 으로구할수있다 [3]. 2.3. AdaBoost 알고리듬객체검출기에서는객체와배경을분류하기위하여분류기를사용한다. 분류기는객체샘플들과배경의샘플들을사용하여학습시킨다. Viola와 Jones는분류기를학습시키기위해유사 AdaBoost 알고리듬을사용하였다 [3]. AdaBoost는성능이낮은약분류기들을조합하여강분류기를구성하는알고리듬으로약 그림 1. Haar-like feature. (a) 2 개의사각형으로구성된피쳐. (b) 3 개의사각형으로구성된피쳐. (c) 4 개의사각형으로구성된피쳐. Fig. 1. Haar-like feature. (a) features made of 2 rectangles. (b) features made of 3 rectangles. (c) feature made of 4 rectangles. 487
한국통신학회논문지 '13-06 Vol.38A No.06 A B 1 2 C D 3 4 그림 2. 적분영상의계산. D 영역의픽셀값들의합은 4+1-(2+3) 으로계산된다. Fig. 2. Calculation of integral image. The sum of pixels within rectangle D can be calculated as 4+1-(2+3). 분류기에의해옳게판정된샘플들의가중치는낮추고잘못판정된샘플들의가중치는높이는과정을반복하여강분류기를구성한다 [4]. 이과정은강분류기의성능이목표에도달할때까지반복된다. 그림 3은 AdaBoost 알고리듬을이용한분류기학습과정을보여준다. 2.4. 피쳐선택 Viola와 Jones는 AdaBoost를이용하여피쳐의과완전집합 (over-complete set) 에서분별력이가장큰피쳐를선택하여약분류기로사용했다 [3]. 피쳐의과과완전집합은객체크기의윈도우에피쳐영역의중첩을허용하며그림 1의피쳐들을크기와위치를변경해가며채워구성한다. 피쳐선택을위하여학습샘플들에대해과완전집합의모든피쳐들의에러를계산한다. 에러는샘플의가중치를고려하여계산하며에러가가장작은피쳐가선택된다. AdaBoost를이용한피쳐선택방법은최적화된방법은아니다. 이를개선하기위한여러연구가이루어졌다. Li 등은부동탐색알고리듬을 AdaBoost와결합한 FloatBoost [12] 를제안하였으며, Treptow와 Zell은피쳐선택에진화탐색알고리듬을사용하는방법을제안하였다 [13]. Abramson은힐크라이밍진화탐색알고리듬의사용을제안하였다 [16]. Ⅲ. Haar-like feature 유사도와이를활용한피쳐선택방법 AdaBoost에기반한피쳐선택방법은학습샘플들에대한피쳐의에러만을고려하므로유사하거나동일한피쳐가선택되는경우가발생한다. 본절에서는피쳐의에러와함께피쳐간의형태적유사도 그림 3. AdaBoost 학습과정. Fig. 3. Flow of AdaBoost training. 를계산하여이미선택된피쳐들과유사한피쳐들의중복되어선택되지않도록하는피쳐선택방법을제안한다. 3.1. 피쳐유사도피쳐유사도는피쳐의종류, 크기, 위치를고려하여계산한다. Haar-like feature는 (type, x, y, width, height) 로나타낼수있다. 여기에서 type 은 Haar-like feature의종류이며, x, y와 width, height 는 Haar-like feature의위치와크기이다. 피쳐간의형태적유사도를계산하기위해피쳐중심점위치 (cx, cy) 를추가하여 Haar-like feature를 (type, x, y, width, height, cx, cy) 로나타낸다. 피쳐유사도는같은종류의피쳐들에대해서만고려하며식 (1) 과같이계산한다. min min 피쳐거리 (1) 피쳐거리는두피쳐의중심좌표가, 일때, 로계산된다. 488
논문 / 객체검출을위한빠르고효율적인 Haar-Like 피쳐선택알고리즘 3.2. 제안하는피쳐선택알고리듬제안하는피쳐선택알고리듬에서는이미선택된피쳐와유사도가높은피쳐들을과완전집합에서제거한다. 그림 4는제안하는피쳐선택알고리듬을보여준다. 과완전집합의모든피쳐의중심점은최초에한번만계산한다. 학습샘플에대해에러가최소인피쳐를선택하고선택된피쳐에대해과완전집합의모든피쳐들의유사도를계산한다. 이때유사도가한계치보다큰피쳐들을과완전집합에서제거하여이후에선택되지않도록한다. 이미선택된피쳐와유사도가높은피쳐들이피쳐세트에서제거되므로이후에빠르고효율적인피쳐선택이가능하게된다. 이작업은매 boosting 단계에서반복된다. 그림 4. 제안된알고리듬. 어두운블록이기존알고리듬에서추가된부분. Fig. 4. Proposed Algorithm. Shaded block is the added part within previous algorithm. Ⅳ. 실험결과 기존피쳐선택알고리듬과제안한알고리듬을사용하여분류기를학습하고성능을비교하였다. FERET 얼굴데이터베이스 [17] 와인터넷에서정면얼 굴 6000장을수집하여 3000장을학습세트로, 나머지 3000장을테스트세트로사용하였다. 그림 5 는기존알고리듬과제안된알고리듬으로학습시킨분류기를구성하는피쳐중 18개씩을보여준다. 그림 5(a)~(f) 은기존알고리듬이선택한피쳐를보여주며, 그림 5(g)~(l) 은제안한알고리듬이선택한피쳐를보여준다. 기존알고리듬을사용한경우그림 5(a) 와 (f) 에서유사피쳐가선택되었다. 제안한알고리듬을사용한경우해당유사피쳐대신새로운피쳐가선택되었음을그림 5(l) 에서확인할수있다. 동일한성능목표에대하여기존방법과제안된방법으로분류기들을학습시키고분류기들을구성하는피쳐의수를비교하였다. 기존방법으로학습시킨경우는 200 개의피쳐가선택되었고, 제안된방법으로학습시킨경우는 160 개의피쳐가선택되어피쳐수가 20% 감소하였다. 그림 6은두분류기의성능을보여준다. 표 1은 FERET 얼굴데이터베이스의얼굴테스트샘플 3000 장에대한두분류기의처리속도를보여준다. 기존방법을사용하여학습시킨분류기의처리시간은평균 141.3 초가소요되었고, 제안한방법을사용하여학습시킨분류기의처리시간은평균 129.4 초가소요되어처리시간이 8.5% 개선되었다. 그림 7은동일한피쳐수를사용할때의성능을비교한것이다. 제안된방법을사용하여학습된분류기의성능이 1% 포인트향상되었다. Ⅴ. 결론및추후과제본논문은객체검출을위한 Haar-like feature 선 그림 5. 선택된피쳐의비교. (a)~(f) 기존알고리듬, (g)~(l) 제안된알고리듬. Fig. 5. Comparing selected features. (a)~(f) Previous algorithm, (g)~(l) Proposed algorithm. 489
한국통신학회논문지 '13-06 Vol.38A No.06 그림 6. 200 개피쳐의기존방법의분류기와 160 개피쳐의제안된방법의분류기성능비교. Fig. 6. Performance comparison of previous method with 200 features and proposed method with 160 features. 표 1. 동일한성능을보이는분류기의처리속도비교 Table 1. Execution time comparison when classifiers show same performance Previous Method(sec) Proposed Method(sec) Test 1 141.7 128.6 Test 2 142.0 130.6 Test 3 140.8 129.2 Test 4 140.7 129.1 Average 141.3 129.4 택에있어유사도가높은피쳐를제거하여효율적인피쳐선택알고리듬을제안하였다. 기존방법은에러률이적은피쳐를선택하는반면에, 제안된방법은유사도가낮으면서에러률이적은피쳐를선택한다. 제안된방법이기존방법에비해적은수의피쳐를사용함에따라객체검출에소요되는시간이 8.5% 단축되었음을확인하였다. 제안된방법으로활용가능한피쳐를추가적으로선택하여동일한수의피쳐를사용할경우분류기의검출률이 95.7% 에서 96.7% 로상승한것을확인하였다. 추후과제로는 2개의피쳐를비교하는것에서좀더나아가 3~4 개의피쳐를동시에비교가능하게알고리듬을확장하는것과 cascade로분류기를구성할때제거된피쳐정보의전달방법을개발할필요가있다. References [1] J. Lee, J, Ryu, S. Hong, and W. Cho, Local and global collaboration for object detection 그림 7. 동일한수의피쳐를사용한분류기들의성능비교. Figure 7. Performance comparison when classifiers use same number of features. enhancement with information redundancy, in Proc. 6th IEEE Int. Conf. Adv. Video and Signal Based Surveillance, pp. 358-363, Genova, Italy, Sep. 2009. [2] M. Yang, D. Kriegman, and N. Ahuja, Detecting faces in images: a survey, IEEE Trans. Pattern Anal. Mach. Intell., vol. 24, no. 1, pp. 34-58, Jan. 2002. [3] P. Viola and M. Jones, Robust real-time face detection, in Proc. 8th IEEE Int. Conf. Comput. Vision, vol. 2, pp. 747, Vancouver, Canada, July 2001. [4] Y. Freund and R. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Computational Learning Theory: J. Comput. Syst. Sci., vol. 55, no. 1, pp. 119-139, Aug. 1997. [5] J. Ren, N. Kehtarnavaz, and L. Estevez, Real-time optimization of Viola-Jones face detection for mobile platforms, in Proc. 7th IEEE Dallas Circuits and Syst. Workshop, vol. 1, no.1, pp. 1-4, Dallas, U.S.A., Oct. 2008. [6] M. Kolsch and M. Turk, Analysis of rotational robustness of hand detection with a Viola-Jones detector, in Proc. 17th Int. Conf. Pattern Recognition, vol. 3, pp. 107-110. Cambridge, U.K., Aug. 2004. [7] L. Acasandrei and A. Barriga-Barros, Accelerating Viola-Jones face detection for 490
논문 / 객체검출을위한빠르고효율적인 Haar-Like 피쳐선택알고리즘 embedded and SoC environments, in Proc. 5th ACM/IEEE Int. Conf. Distributed Smart Cameras, pp. 1-6, Ghent, Belgium, Aug. 2011. [8] P. Viola and M. Jones, Rapid object detection using a boosted cascade of simple features, in Proc. 2001 IEEE Comput. Soc. Conf. Comput. Vision and Pattern Recognition, vol. 1, pp. 511-518, Hawaii, U.S.A., Dec. 2001. [9] R. Kohavi and G. John, Wrappers for feature subset selection, Artificial Intell., vol. 97 no. 1-2, pp. 273-324, Dec. 1997. [10] H. Liu, H. Motoda, and L. Yu, Feature selection with selective sampling, in Proc. 19th Int. Conf. Mach. Learning, pp. 395-402, Sydney, Australia, July 2002. [11] P. Viola and M. Jones, Fast and robust classification using asymmetric AdaBoost and a detector cascade, Advances in Neural Inform. Process. Syst., vol. 14, pp. 1311-1318, Dec. 2001. [12] P. Pudil, J. Novovicova, and J. Kittler, Floating search methods in feature selection, Pattern Recognition Lett., vol. 15, no. 11, pp. 1119-1125, Nov. 1994. [13] A. Treptow and A. Zell, Combining Adaboost learning and evolutionary search to select features for real-time object detection, in Proc. IEEE Congr. Evol. Comput., pp. 2107-2113, Portland, U.S.A., June 2004. [14] J. Kim, S. Yu, K, Toh, D. Kim, and S. Lee, Fast on-road vehicle detection using reduced multivariate polynomial classifier, J. Korean Inst. Commun. Sci. (KICS), vol. 37A, no. 8, pp. 639-647, Aug. 2012. [15] C. Papageorgiou, M. Oren, and T. Poggio, A general framework for object detection, in Proc. Int. Conf. Comput. Vision, pp. 555-562, Mumbai, India, Jan. 1998. [16] S. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, 2nd Ed., Prentice Hall, 2003. [17] P. Phillips, H. Moon, P. Rauss, and S. Rizvi, The FERET evaluation methodology for face recognition algorithms, IEEE Trans. Pattern Anal. Mach. Intell., vol. 22, no. 10, pp. 1090-1104, Oct. 2000. 정병우 (Byung Woo Chung) 2011년 8월아주대학교전자공학과학사 2011년 9월~현재서강대학교전자공학과 CAD&ES 연구실석사과정 < 관심분야 > 패턴인식, 실시간시스템박기영 (Ki-Yeong Park) 1991년 2월한양대학교물리학과학사 2006년 8월서강대학교정보통신대학원석사 2007년~현재 : ( 주 ) 엠아이웨어부장 2008년~현재서강대학교전자공학과 CAD&ES 연구실박사과정 < 관심분야 > 패턴인식, 실시간시스템, 병렬처리시스템황선영 (Sun-Young Hwang) 1976년 2월서울대학교전자공학과학사 1978년 2월한국과학원전기및전자공학과공학석사 1986년 10월미국 Stanford 대학전자공학박사 1976년~1981년삼성반도체 ( 주 ) 연구원, 팀장 1986~1989년 Stanford 대학 Center for Integrated System 연구소책임연구원및 Fairchild Semiconductor Palo Alto Research Center 기술자문 1989~1992년삼성전자 ( 주 ) 반도체기술자문 1989년 3월~현재서강대학교전자공학과교수 < 관심분야 > SoC 설계및 framework 구성, CAD 시스템, Computer Architecture 및 DSP System Design 등 491