내용기반이미지검색을위한 MPEG-7 우위컬러기술자의효과적인유사도 837 내용기반이미지검색을위한 MPEG-7 우위컬러기술자의효과적인유사도 (An Effective Similarity Measure for Content-Based Image Retrieval using MPEG-7 Dominant Color Descriptor) 이종원 낭종호 (Jongwon Lee) (Jongho Nang) 요약본논문에서는 MPEG-7 DCD 를이용하여내용기반이미지검색을할때적합한유사도측정방법을제안한다. 제안한방법은이미지에서추출한도미넌트컬러의비율에따라유사도를측정할수있도록하였다. 실험결과제안한방법은 MPEG-7 DCD 의 QHDM[1] 에의한검색결과보다전역 DCD 를사용할경우 ANMRR 이 18.9% 의성능향상을보였으며블록별 DCD 를사용할경우 47.2% 라는높은성능향상을보였다. 이는제안한방법이 DCD 를이용하여내용기반이미지검색을할때효과적인유사도측정방법임을보여준다. 특히, 영역기반의이미지검색방법에유용하게적용할수있을것으로보인다. 키워드 : 내용기반이미지검색, MPEG-7, 도미넌트컬러기술자, 유사성측정, 영역기반검색 Abstract This paper proposes an effective similarity measure for content-based image retrieval using MPEG-7 DCD. The proposed method can measure the similarity of images with the percentage of dominant colors extracted from images. As the result of experiments, we achieved a significant improvement of 18.92% with global DCD and 47.22% with local DCD in ANMRR than the result by QHDM. This result shows that the proposed method is an effective similarity measure for content-based image retrieval. Especially, our method is useful for region-based image retrieval. Key words : Content-based Image Retrieval, MPEG-7, Dominant Color Descriptor, Similarity Measure, Region-based Retrieval 1. 서론 디지털카메라의확산과카메라기능을가진휴대폰의보급으로자신이찍은사진을블로그와각종인터넷카페, 미니홈피등을통해공유하는것은보편적인일이되었다. 이에따라정보검색도텍스트위주의검색뿐만아니라이미지에대한검색요구도증대하고있다. 이미지검색은이미지에붙인이름이나키워드등텍스트를 정회원 : 청강문화산업대학 e스포츠게임과교수 jw@ck.ac.kr 종신회원 : 서강대학교컴퓨터공학과교수 jhnang@sogang.ac.kr 논문접수 : 2010년 2월 19일심사완료 : 2010년 5월 31일 CopyrightC2010 한국정보과학회ː개인목적이나교육목적인경우, 이저작물의전체또는일부에대한복사본혹은디지털사본의제작을허가합니다. 이때, 사본은상업적수단으로사용할수없으며첫페이지에본문구와출처를반드시명시해야합니다. 이외의목적으로복제, 배포, 출판, 전송등모든유형의사용행위를하는경우에대하여는사전에허가를얻고비용을지불해야합니다. 정보과학회논문지 : 컴퓨팅의실제및레터제16권제8호 (2010.8) 이용하는방법과이미지자체의내용기반으로검색하는방법이있다. 이중이미지의급격한증가로이미지에대한부가적인정보를알수없는경우도많아이미지의내용에기반한검색방법에대한연구가요구되고있다. 내용기반이미지검색방법 (Content-Based Image Retrieval, CBIR) 은이미지를추상화하는과정과추상화된이미지의유사성을검색하는과정, 색인을만드는과정등크게세과정으로나눌수있다. 이미지를추상화하는과정은각이미지를구별할수있는특성값을추출하는것이다. 유사성을검색하는과정은추출된특성값의거리를비교하여유사한이미지를찾는과정이다. 색인을만드는과정은추출된이미지특성값을빠르게검색할수있도록구조적으로배열하는방법이다. 이미지의특성을추출하는방법으로 MPEG-7에서는컬러와질감, 객체의모양등다양한시각정보기술자를제안하였다 [1]. 이중컬러기반기술자는 Dominant Color Descriptor (DCD), Scalable Color Descriptor
838 정보과학회논문지 : 컴퓨팅의실제및레터제 16 권제 8 호 (2010.8) (SCD), Color Structure Descriptor (CSD), Color Layout Descriptor(CLD) 등 4개다. 이중본논문에서는 DCD를이용한내용기반이미지검색방법에서이미지의유사성을측정하는새로운방법을제안하고구현하였다. MPEG-7 DCD에서사용한유사성측정방법인 Quadratic Histogram Distance Measure(QHDM)[1] 은 [2] 와 [3] 에서지적한바와같이유사도측정에있어사람이인식하는유사성과차이를보이는경우가있다. 이에따라 [2] 에서는컬러의비율의산술적차이를고려하여새로운측정방법을제시하였고, [3] 에서는도미넌트컬러의팔레트를통합하여히스토그램의교집합으로유사성을측정하는방법을제시하였다. 그러나두방법모두도미넌트컬러의비율의변화에따라유사도를비례적으로계산하지못한다는단점이있다. 본논문에서는각도미넌트컬러의비율의비례관계를유사도측정에반영하여유사도를측정하는새로운방법을제안하였다. 실험결과 QHDM 대비제안한거리측정방법을사용할경우와비교해보면 MPEG-7에서제안한성능평가방법인 ANMRR에서 18.9% 의성능이향상되었다. 또한, 이미지의지역적특성을반영할수있도록블록기반으로 DCD를추출하고, 이를전역기반 DCD를이용한방법과비교하여실험한결과블록기반 DCD 추출이 ANMRR 성능평가에서 34.9% 의성능향상을보였으며, 전역기반DCD를 QHDM으로측정한결과와비교하면 47.2% 의높은성능향상을보였다. 2. MPEG-7 DCD 와관련연구 MPEG-7 DCD는이미지의컬러특성을소수의도미넌트컬러와해당컬러의비율로정의한다. DCD는식 (1) 과같이정의된다. (1) 은추출된도미넌트컬러의개수이고, 는 3-D 컬러벡터 ( 예 : RGB), 는 가이미지에서차지하는비율이다. 이미지에서추출된도미넌트컬러개수인 은이미지마다다를수있으나최대 8개다. 두이미지에서추출된 DCD를 라고할때유사성을측정하는 QHDM은다음과같이정의된다. (2) 식 (2) 에서 은두컬러 과 의유사성을나타내는계수로식 (3) 과같이정의한다. max (3) 여기서 은두컬러의유클리드거리로 이다. max 로계산한다. 임계치 는두컬러의거리의최대치를나타낸다. 그러나 [2,3] 에따르면 QHDM은일부의경우사람이인식하는이미지의유사성과일치하지않는결과를산출하고있다. [2] 에서는 QHDM의문제점을두가지로정리하였다. 첫째, 검색대상이미지의도미넌트컬러개수가증가하면잘못된결과의원인이되고, 둘째, 질의이미지와대상이미지에서같은도미넌트컬러가추출될경우대상이미지에서해당도미넌트컬러의비율이높으면잘못된결과를산출한다. [2] 에서사용한예를살펴보자. 그림 1 유사도측정이미지 (a: 질의이미지 ( ), b:, c: ) 그림 1에서질의이미지 (a) 와대상이미지 (b,c) 의거리를 QHDM으로계산해보면다음과같다. 즉, 시각적으로는 b보다는 c가 a와더유사한것같으나 QHDM으로는 b가더유사한것으로측정된다. 이는대상이미지의도미넌트컬러의개수가많을경우 식 (2) 에의해거리가가까운것으로산출될수 있기때문이다. 도미넌트컬러가같을경우식 (3) 에의해 의값은 1이되고따라서같은컬러임에도식 (2) 에의해잘못된결과가산출된다. 이에따라 [2] 에서는식 (4) 와같이새로운유사성측정방법을제안하였다. min (4) 두도미넌트컬러의비율의차이에두컬러의비율중작은값을곱한것이다. 이렇게할경우실제사람이인
내용기반이미지검색을위한 MPEG-7 우위컬러기술자의효과적인유사도 839 식하는컬러의비율을거리계산에반영할수있다. 그러나식 (4) 는단순히두컬러의비율의산술적인차이만반영할뿐 와 의비례관계를반영하지못한다는단점이있다. 예를들어 이고 라고하면, 이다. 또 이고 라면 가되어컬러의비율은 2배로증가하였지만유사도측정값은 2배로증가하지않는다. [3] 에서는 DCD의유사성측정방법으로 Merged Palette Histogram Similarity Measure(MPHSM) 를제안하였다. 이것은 DCD의컬러를통합하여공통팔레트를만들고팔레트에서두 DCD의히스토그램의교집합을구하여식 (5) 와같이합산하는것이다. 식 (5) 에서 는히스토그램을뜻하고, 는컬러의비율이다. min (5) MPHSM은두이미지에서히스토그램의교집합으로거리를측정하므로무조건작은값에의해유사도가결정된다는단점이있다. 예를들어두히스토그램의값이 이고 이면 가된다. 만약 이라고하여도 는 0.5가된다. 과 가모두 와의유사도가같게나오는것이다. 이는히스토그램에서큰값은전혀고려하지않고무조건작은값만으로거리를측정하였기때문이다. 3. 유사도측정방법제안 3.1 유사도측정 MPEG-7 DCD를이용하여이미지의유사도를측정할경우추출된도미넌트컬러의비율의증가나감소에따라유사도도비례적으로측정되어야한다. 또한질의이미지와대상이미지에서같은컬러가추출되었더라도한이미지에서해당컬러가차지하는비율이낮을경우유사도는낮게나와야한다. 따라서본논문에서는 [3] 과같이무조건작은비율값만반영하는문제를해결하고, [2] 에서도미넌트컬러의비율의비례관계를정확하게반영하지못하는단점을해결하기위해유사도측정방법을수정하여제안한다. 본논문에서제안하는방법은우선, 도미넌트컬러의비율의비례값을구하여도미넌트컬러의비율에비례하여측정하고, 여기에 [2] 와같이작은비율값을곱하여유사도를작은비율값에따라조정하였다. 두이미지의 DCD를, 라고하자. 은추출된도미넌트컬러이고, 는각이미지에서 i 번째와 j 번째도미넌트컬러가차지하는비율이다. 이때두 DCD의유사도는다음과같이두도미넌트컬러사이의거리와비율간의거리로측정한다. (6) 는두도미넌트컬러사이의거리 (Color Distance) 로식 (3) 을적용한다. 는도미넌트컬러의비율간의거리로식 (7) 과같이계산한다. min min min max max min (7) max 식 (7) 에서 min max 는도미넌트컬러의비율값의차이를비교한다. 는컬러의비율값의비례관계의임계치로임계치이하일경우거리계산에반영하지않는다. 식 (7) 에서마지막에곱하는 min 는두컬러의비율중작은값에따라유사도를조절한다. 만약두이미지의도미넌트컬러의비율이같다면비율의크기에관계없이무조건높은유사도가나오게되므로 min 를반영하여비중을조정해야한다. 예를들어, 두도미넌트컬러의비율이 30% 로같게나왔다면식의뒷부분을계산하면 1이아니라, 이된다. 두도미넌트컬러의비율이 40%, 20% 로다르다면, 계산결과는 이된다. 식 (7) 에서는결과값이작을수록유사도가높은것으로판단한다. 3.2 블록기반유사도측정이미지전역에서추출한 DCD만비교할경우이미지의전체적인특성은비교가되지만, 부분적인유사성을비교하지못한다는단점이있다. 따라서이미지를블록으로구분하여각영역의유사도를비교하고각영역별로가중치를부여하여비교하면사용자가흥미를가지는부분에주의하여비교할수있다 ([4,5]). 본논문에서는효율적인계산을위해영역을 2 2, 3 3, 4 4 등동일크기의블록으로나누어서비교한다. 블록단위로유사도를비교할때같은위치의블록끼리만비교하거나모든블록과비교하여평균값으로측정하는것이가능하다. 이미지검색은정확한일치를찾는것보다는유사한이미지를검색하는것이므로, 다른위치에있는블록과도비교하여가장유사도가높은블록과의거리와위치를고려하는것이중요하다. 그러나같은블록끼리만비교할경우같은내용이지만위치가다를경우비교가불가능하고, 모든블록과비교한평균
840 정보과학회논문지 : 컴퓨팅의실제및레터제 16 권제 8 호 (2010.8) 값은이미지전체의특성추출과유사해지는단점이있다. 따라서본논문에서는블록의위치변화를고려하고, 블록단위의 DCD 특성을반영하여비교하기위해서유사도가가장높은블록과의거리와위치를반영하는방법을제안한다. 이경우 DCD의유사도측정은식 (8) 과같이수정하여적용할수있다. (8) 여기서 는블록의집합을나타내며, 는블록의개수를나타낸다. 는블록간도미넌트 컬러의유사도로식 (7) 을사용한다. 은대상이미지에서질의이미지의블록과유사도가가장높은블록의 DCD값을뜻한다. 은각블록에부여한가중치로합은 1이다. 은블록의위치에따른거리를측정한것으로식 (9) 와같이측정한다. (9) 은블록의위치를구하는함수다. 는유사도가높은블록이같은위치이면 0이고, 위치가멀어질수록거리가증가한다. 는블록별유사도에대한가중치이고, 는블록의위치에대한가중치로 이다. 검색한결과를 ground truth와비교하여 MPEG-7에서제시한성능평가방법인 ANMRR(Average Normalized Modified Retrieval Rank) 를사용한다. NMRR은단순히검색결과에정답이검색되었는지뿐만아니라검색결과중정답의순위를측정한다. ANMRR은질의이미지에대한 NMRR의평균값이다. ANMRR은낮을수록성능이좋은것이다. 4.2 실험결과 4.2.1 유사도측정방법비교 MPEG-7 DCD의유사도측정방법인 QHDM과 [2] 의 LBA, [3] 의 MPHSM과본논문에서제안한방법의성능을비교한결과는그림 1과같다. 그림 2를보면본논문에서제안한방법이 ANMRR 에서 QHDM 대비 18.9% 의성능향상을보였으며, MPHSM 대비 10.5% 의성능향상을보였다. LBA와대비해서는 2.3% 의성능향상을보였다. QHDM에비하여제안한방법이높은성능을보인것은식 (7) 에서 min 을곱함으로서실제로이미지에서도미넌트컬러가차지하는비율을거리측정에반영하였기때문이다. 이것은유사한방법을사용한 LBA도성능이높게나타난것을보면알수있다. 4. 실험결과 4.1 실험환경과성능평가방법본실험에서는 MPEG-7의실험모델 (Experiment Model, XM) 을바탕으로블록기반으로 DCD를추출하는기능과제안한방법에의해유사도를측정하는부분을구현하였다. DCD 추출을위해, 로설정하였다. 이는 MPEG-7에서권고한임계치범위내의값을적용한것이다 [1]. 는 30% 로설정하였다. 실험데이터로는 MPEG-7의 XM[6] 에서함께제공되는이미지데이터베이스인 Common Color Dataset(CCD) 를사용하였다. CCD는총 5,000여개의이미지로구성되어있으며 Common Color Query(CCQ) 로 50개의이미지를사용한다. CCQ에대한 ground truth도제공된다. Ground truth는대략질의이미지별로 3~32개의이미지로설정되어있다. 본실험에서는 DCD의유사도를 QHDM, [2] 에서제안한방법 (LBA), [3] 에서제안한 MPHSM과본논문에서제안한방법으로비교한다. 또한전역 DCD를사용하는경우와블록기반 DCD를사용하는경우의검색결과를비교한다. DCD 유사도측정의성능평가는 50개의 CCQ를각각 그림 2 유사도측정방법별성능비교 (ANMRR) 4.2.2 전역대블록기반유사도측정비교그림 3은전역대이미지를블록으로나누어출한 DCD를기준으로유사도를측정하여 ANMRR로성능을비교한것이다. 실험에서는이미지를 4 4로총 16개의블록으로나누어유사도를측정하여비교하였다. 비교는전역 DCD를사용한경우와블록으로나누어같은위치의블록만비교한경우, 제안한방법과같이가장유사도가높은블록의 DCD과위치를고려한경우를비교하였다. 세경우모두본논문에서제안한방법을사용하여유사도를측정하였다. 전역 DCD는식 (7) 을사용하였고, 같은위치의블록간비교는식 (7) 을사용하여비교한뒤블록개수로나누어평균값을구하였다. 식 (8) 에서 로가중치를주었고, 는반영하지않았다.
내용기반이미지검색을위한 MPEG-7 우위컬러기술자의효과적인유사도 841 그림 3 전역대블록단위검색의성능비교 (ANMRR) 그림 3의결과를보면전역 DCD 대비제안한방법이 ANMRR에서 34.9% 의성능향상을나타냈다. 같은위치의블록과비교하는경우와대비하여보면 14.3% 의성능향상을나타냈다. 단순히블록으로나누어비교하기만해도, 전역 DCD 대비 13.9% 의성능향상을나타냈다. 전역 DCD를 QHDM으로검색했을경우 ( 그림 2) 과비교하여보면제안한방법이 47.2% 라는높은성능향상을나타냈다. 이는블록별특성과블록의위치를반영하는것이내용기반이미지검색에있어서효과적임을나타낸다. "A fast MPEG-7 dominant color extraction with new similarity measure for image retrieval," Journal of Visual Communication and Image Representation, vol.19, pp.92-105, 2008. [ 3 ] L.M. Po, and K.M. Wong, "A New Palette Histogram Similarity Measure for MPEG-7 Dominant Color Descriptor," Proc. of IEEE Int. Conf. on Image Processing(ICIP'04), pp.1533-1536, 2004. [4] Q. Tian, Y. Wu, and T.S. Huang, "Combine User Defined Region-of-Interest and Spatial Layout for Image Retrieval," Proc. of IEEE Int. Conf. on Image Processing(ICIP'2000), pp.746-749, vol.3, 2000. [5] M.R. Mustaffa, F. Ahmad, R.W.O.K. Pahmat, and R. Mahmod, "Dominant Colour Descriptor with Spatial Information for Content-based Image Retrieval," Proc. of IEEE Int. Symposium on Information Technology(IT SIM 2008), vol.3, pp.1-9, 2008. [6] A. Yamada, M. Pickering, S. Jeannin, L. Cieplinski, J.R. Ohm, and M. Editors, Eds., MPEG-7 Visual Part of Experimentation Model Version 8.0, Oct. 2000, ISO/IEC JTC1/SC29/WG11/N3673. 5. 결론 본논문에서는 MPEG-7 DCD를이용한내용기반이미지검색에서이미지의유사도측정을위해새로운방법을제안하고실험을통해검증하였다. 실험결과제안한방법은 MPEG-7 DCD의 QHDM에의한검색결과보다전역 DCD를사용할경우 ANMRR이 25.2% 의성능향상을보였으며블록별 DCD를사용할경우 51.2% 라는높은성능향상을보였다. 이는제안한방법이 DCD를이용하여내용기반이미지검색을할때효과적인유사도측정방법임을보여준다. 특히, 제안한방법은전역 DCD보다블록별 DCD를이용한검색에높은성능향상을보여영역기반의이미지검색방법에유용하게적용할수있을것으로보인다. 그러나본논문에서는블록별 DCD를추출하고유사도를측정하는과정에서사용자가관심을갖는부분 (ROI, Region-of-Interest) 에대한고려가없다. 따라서향후 ROI에기반한효과적인검색방법이연구되어야한다. 참고문헌 [1] B.S. Manjunath, P. Salembier, and T. Sikore, Introduction to MPEG-7 Multimedia Content Description Interface, John Wiley & Sons Ltd., England, 2002. [2] N.C. Yang, W.H. Chang, C.M. Kuo, and T.H Li, 게임 QA 이종원 1987 년서강대학교전자계산학과 ( 학사 ) 1996 년서강대학교공공정책대학원정보처리학과 ( 석사 ). 2003 년서강대학교대학원컴퓨터공학과 ( 박사수료 ). 현재청강문화산업대학 e 스포츠게임과부교수. 관심분야는멀티미디어검색, 서버및보안, 낭종호정보과학회논문지 : 컴퓨팅의실제및레터제 16 권제 4 호참조