2006 년 7 월전자공학회논문지제 43 권 SP 편제 4 호 19 논문 2006-43SP-4-3 MPEG-7 기반 DCT 영역에서의에지히스토그램고속추출기법 (Fast Extraction of Edge Histogram in DCT Domain based on MPEG-7 ) 엄민영 *, 최윤식 *, 원치선 **, 남재열 *** (Min young Eom, Yoon sik Choe, Chee Sun Won, and Jae Yeal Nam ) 요 약 오늘날대부분의멀티미디어데이터는압축된형태로저장되고전송된다. MPEG-7 에지히스토그램기술자는공간영역에서특징정보를추출하기때문에특징정보추출을위해필요로되는복호화과정과공간영역에서의필터링과정은특징추출시간과연산량을증가시키는원인이된다. 영상검색효율을높이기위하여본논문에서는 DCT 영역에서직접적으로에지히스토그램을추출하는기법을제안한다. DCT 계수들중 AC 계수로부터얻을수있는에지에대한정보를이용하여 DCT 영역에서직접적으로에지의방향과강도를구한다. 실험결과는제안하는기법을통해검색효율과연산량에서모두만족할만한결과를얻을수있음을보여준다. Abstract In these days, multimedia data is transmitted and processed in compressed format. Due to the decoding procedure and filtering for detection, the feature extraction process of MPEG-7 Edge Histogram Descriptor (EHD) is time consuming as well as computationally expensive. To improve efficiency of compressed image retrieval, we propose a new histogram generation algorithm in DCT domain in this paper. Using the information provided by the only two AC coefficients of DCT coefficients, we can get directions and strengths directly in DCT domain. The experimental results demonstrate that our system has good performance in terms of retrieval efficiency and effectiveness. Keywords : MPEG-7, DCT, EHD, Edge Ⅰ. 서론 인터넷과멀티미디어기술의발전으로멀티미디어정보가급격하게증가함에따라, 멀티미디어정보를보다효율적으로저장, 표현, 검색할수있는방법을필요 * 정회원, 연세대학교전기전자공학부 (Dep. of Electrical and Electronic Engineering, Yonsei University) ** 정회원, 동국대학교전자공학과 (Dep. of Electronic Engineering, Dongguk University) *** 정회원, 계명대학교정보통신공학부 (Dep. of Computer Science, Keimyung University) 본연구는한국과학재단목적기초연구 (R01-2003-000-10412-0) 지원으로수행되었음. 접수일자 : 2005년9월12일, 수정완료일 : 2006년6월15일 로하게되었다. 현재컴퓨팅환경에서대부분의멀티미디어정보는압축된형태로저장되고전송되어진다. 이에따라압축된정보를효율적으로표현하고검색할수있는능력은중요하다. MPEG-7 표준은멀티미디어데이터의내용을대표할수있는특징을추출하여이를기반으로색인과검출을수행할수있도록컬러, 질감, 움직임, 모양등의특징을추출하기위한비주얼기술자들을정의하고있다 [1][2]. 대부분의멀티미디어데이터들은압축된형태로저장되고전송되어지는데반해, 이러한기술자들은대부분공간영역에서특징을추출하며 IDCT를포함한복호화과정은특징추출시간을증가시키는원인이된다. 본논문에서는이러한단점을개선하고보다빠르고효율적인특징추출을위하여압축된형태의정보 (DCT 영 (317)
20 MPEG-7 기반 DCT 영역에서의에지히스토그램고속추출기법엄민영외 (0,0) (0,1) (0,2) (0,3) 표 1. local bin들의의미 Table 1. Meaning of local bins. Histogram bins Semantics (1,0) (1,1) (1,2) (1,3) BinCounts[0] Vertical of at (0,0) BinCounts[1] Horizontal of at (0,0) (2,0) (3,0) (2,1) (3,1) (2,2) (3,2) (2,3) (3,3) image-block BinCounts[2] 45-degree of at (0,0) BinCounts[3] 135-degree of at (0,0) BinCounts[4] non-directional of at (0,0) 그림 1. 와 image-block Fig. 1. s and image-blocks. BinCounts[5] Vertical of at (0,1). BinCounts[78] 135-degree of at (3,3). BinCounts[79] non-directional of at (3,3) (a)vertical (b)horizontal (c)45-degree (d)135-degree (e)non-directional 그림 2. 다섯가지종류의에지성분 Fig. 2. Five types of s. 역 ) 로부터특징을추출하는방법을제안한다. 제안하는알고리듬은공간영역에서의에지히스토그램기술자 (EHD:Edge Histogram Descriptor) 를압축영역에적용시키도록하기위한것이다. 에지의히스토그램을 DCT영역에서직접적으로추출하기위한방법으로 AC계수로부터에지의방향과강도를구한다. 제안한기법을사용하면 IDCT과정을거치지않고 DCT영역에서에지정보를추출할수있다. 본논문에서는 Ⅱ장에서기존의 MPEG-7 EHD에대해서설명하고 Ⅲ장에서는본논문에서제안하는 DCT 영역에서에지히스토그램을직접적으로추출하는기법에대해서설명한다. Ⅳ장에서는실험결과를통하여제안한기술자를사용하면기존의공간영역에서의기술자보다빠르고효율적으로특징을추출함을있음을보일것이다. 제안하는기법은압축영역에서멀티미디어가저장되고전송되는 JPEG과 MPEG 등의표준에적용되어효율적으로검색에사용될수있다. 이를이용하여멀티미디어데이터를효과적으로관리, 검색할수있고, 동영상내의영상검색에서도사용될수있을것이다. Ⅱ. MPEG-7 EHD [1] 에서 5가지종류의에지분포를표현한다. 는영상을 4 4 등분의겹치지않는영역으로나눔으로서정의된다. 즉, 영상은크기에관계없이항상 16개의같은크기의 로나누어진다. 각 를특성화하기위해, 각 에서의 5가지종류의에지히스토그램을생성한다. 에서의에지는 5가지종류인 vertical, horizontal, 45-degree diagonal, 135-degree diagonal, non-directional 로구분되어진다. 즉, 각 에서의히스토그램은해당 에서 5가지종류에지방향의발생빈도수를나타낸다. 그결과로각 에서 5개의 Bin들이나오게된다. 16개의 가있으므로, 하나의영상에대하여총 5 16 = 80개의히스토그램 Bin들이생성된다. 그림 1에서의 image-block 은에지정보를추출하는기본단위이다. 각 image-block 에대하여이 block이에지성분을가지고있는 block인지, 그리고어떤방향의에지를포함하고있는지를결정한다. 표 1. 은 EHD의 80개의히스토그램 Bin들의의미를나타낸다. EHD는공간영역에서에지를추출하기위해서공간영역에서디지털필터를적용시킨다. 이렇게하기위해서, 우선그림1에서의 image-block 을그림 3에서와같이 4개의 sub-block으로나눈후그림 4의 5가지방향의필터계수들과의필터링하여각방향의상대적인크기를구한다. 이로부터나온다섯가지방향에대한계수의값중가장큰값에해당하는방향이그 imageblock이가지고있는에지의방향으로결정된다. HD 는기본적으로 라불리는각로컬영역 (318)
2006 년 7 월전자공학회논문지제 43 권 SP 편제 4 호 21 Ⅲ. DCT 영역에서의에지히스토그램고속추출기법 본논문에서제안하는에지히스토그램의고속추출기법은공간영역에서의에지히스토그램기술자처럼 16 개의 에서의에지성분을판단하여 80개의 Bin을추출하는기법을그대로사용한다. 하지만압축영역에서이모든과정이이루어지기때문에 JPEG에서손실압축시표준으로사용되어지는 DCT계수들을이용하여이과정이 DCT 영역에서이루어지도록한다. 8 8 블록단위로 2차원 DCT가행해지기때문에 8 8 블록의 AC계수들을살펴봄으로서공간영역에서의에지성분을파악할수있다. 1. DCT 계수들의특성 JPEG 에서사용되는 2 차원 8 8 DCT 는다음과같다. (1) 그림 5는 (1) 식에의해구해진 DCT 계수블록이다. 계수들의특성을이용하여 DCT 계수블록으로부터공 image-bloock sub-block 0 1 2 3 그림 5. 8 8 DCT 계수블록 Fig. 5. 8 8 DCT coefficient block. AC01 AC02 AC10 AC20 AC11 그림 6. AC계수들의물리적인의미 Fig. 6. Physical meaning of AC coefficients. 간영역에서그블록이어떠한에지방향성분을가지고있는지에대한정보를얻어낼수있다. 각 DCT계수 는블록내의모든픽셀들의선형조합으로만들어진다. 이 DCT 블록을가지고에지방향에대한정보를추출해내기위한한가지접근방법은공간영역에서블록의픽셀값들과 DCT계수들간의관계를고찰하는것이다. DCT 블록에서좌측상단에있는계수는 DC이고, 이것은블록의평균밝기를의미한다. 또나머지계수들은 AC계수들이며, 각 AC계수들의값은특정방향과특정변화율을가지고그레이레벨값에서의변화를반영한다. 이관계를더자세히보기위해 을고려해보자. DCT의정의로부터 sub-block 그림 3. image-block 과그것의 sub-block Fig. 3. image-block and its sub-blocks (2) 1-1 1-1 (a) 1 1-1 -1 (b) 0 0 (c) 0 0 (d) 2-2 -2 2 (e) 라는사실을이용하면, (2) 식은다음과같이전개될수있다. 그림 4. 에지검출을위한필터계수 (a)vertical, (b)horizontal, (c)45-diagonal, (d)135-diagonal, (e)non-directional Fig. 4. Filter coefficients for detection. (a)vertical, (b)horizontal, (c)45-diagonal, (d)135-diagonal, (e)non-directional (3) (319)
22 MPEG-7 기반 DCT 영역에서의에지히스토그램고속추출기법엄민영외 식 (3) 의표현은 의값은본질적으로공간영역 에서의블록의위쪽부분과아래쪽부분간의수직방향으로의차이에의존한다는것을의미한다. 유사하게그림 6에 4개의다른계수들에대한의미도같이나타내었다. 2. AC 계수들을이용한방향추출 본논문에서는 과 을이용하여에지의대 략적인수직, 수평성분의크기를알수있고이두계수의비를이용하여대략적인에지방향을검출할수있음을이용하였다. 이러한 DCT 계수들의특징을이용하여공간영역에서의에지의방향을찾는알고리즘이 [3][4][5] 에제안되어있다. 하지만본논문의알고리듬에서는공간영역에서의에지의정확한각도보다그림7 에서어느영역에포함되는지만알면된다. 이런대략적인방향성분을추출하는데는 과 만을 이용하여충분히만족스러운결과를얻을수있다. 본논문에서는에지의방향성을찾기전에먼저 8 8 계수블록이에지영역에해당하는블록인지아닌지를판단한다. 이것은공간영역에서의분산을구하는식으로부터유도할수있다. (4) N N블록에서 DC값은공간영역에서의평균값의 N배가된다는사실과 Parseval의정리에의해 (4) 식은다음과같이표현할수있다. (5) 이곱해지기때문에이상수를고려하지않고 도 (7) 로블록간의상대적인분산의크기비교가가능하다. 이라고하면, (7) 계산량의감소를위해 (8) 을이용할수있다., (8) 일단, 에지블록이라고판단되면 과 의 비를사용하여그림 7의 1번영역안에포함되면 vertical, 2번영역안에포함되면 horizontal, 3번영역안에포함되면 45-degree diagonal, 4번영역안에포함되면 135-degree diagonal이라고판단한다. 본논문에서사용한두계수의비로에지의방향을판단하는알고리듬은그림 8와그림9로잘설명된다. 그림 7에서는 과 의비를 R로표시하였 다. R값에따라에지가그림 7에서어느영역에걸쳐있는지를알수있다. 예를들어, 그림 7의 3번영역에해당하고그림 9의 vertical dominant에서의 45 방향의에지의경우를고려해보자. 이 보다크다면분 명수평보다는수직방향에가까운에지일것이다. 과 의부호가같은경우는 135 보다는 45 에가까운에지일것이고다른경우는 135 에가까운에지이다. 그렇다면에지가걸쳐있는영역은그림 7에서 1-A영역과 3-B영역중하나로범위가좁혀진다. 여기서 1-A R=1 R=Thr R= R=Thr R=1 여기서 는 u,v번째 DCT계수를의미한다. 식 (5) 은식 (6) 처럼표현할수있다. 4-A 1-B 1-A 3-B 4-B 3-A R=Thr (6) 2-B 2-A R= 식 (6) 은 DC성분을제외한 N N DCT 계수들의제곱의합이다. 이것은 AC계수들의제곱의합에상수 을곱한것과같다. 모든계수들에상수 그림 7. 에지영역분류 Fig. 7. Edge region classification. (320)
2006 년 7 월전자공학회논문지제 43 권 SP 편제 4 호 23 vertical dominant horizontal dominant R1>Thr vert same polarity R1<Thr 45 AC01 > AC10 R1>Thr vert different polarity R1<Thr 135 R2>Thr horz same polarity R2<Thr 45 AC01 < AC10 R2>Thr horz different polarity R2<Thr 135 그림 8 에지방향검출방법 Fig. 8. Edge orientation detection method. AC01>0 AC01>0 AC01>0 AC01>0 AC10>0 AC10>0 AC10>0 AC10>0 영역인지 3-B 영역인지는임계값에의해결정할수있다. 즉, 과 의비가임계값보다크면그림7의 1-A영역으로보고작으면 3-B영역으로판단된다. non-directional 의경우는에지의강도에의해판별하는방법을사용하였다. 여기서에지의강도는 vertical dominant인경우는 값의절대값크기로, horizontal dominant인경우는 값의절대값크기로판단한다. 특정임계값보다강도가세면 4개의에지영역중하나로결정되고작으면 non-directional 로분류된다. 여기에서방향의임계값과강도의임계값은실험에의하여찾은값이다. 3. EHDiD (Edge Histogram Descriptor in DCT Domain) 3.2에서기술한방법을통해, DCT 영역에서의에지히스토그램기술자를구성할수있다. 이방법에의하여공간영역에서의에지히스토그램기술자에서필요로하는많은과정을생략하고압축영역에서직접적으로추출함으로서연산량을최대한줄일수있고, 이로인하여정보의고속추출을구현할수있다. 제안하는 DCT영역에서의에지히스토그램기술자를 EHDiD (Edge Histogram Descriptor in DCT domain) 이라지칭하였다. 그림 10에공간영역에서 EHD를사용하는것과 DCT 영역에서제안한방법을통해직접적으로 Bin값을추출하는과정을비교함으로서보여주고있다. 역양자화와 IDCT 과정이생략됨으로서공간영역에서의 EHD에비해연산량과속도의큰장점이있다. 또한특징을추출하여히스토그램을생성하는과정에서도제안한방법은단순히 과 의비로서히스토그램을생성할수있으므로특징추출과정에있어서도엄청난연산량의차이를가진다. 하지만실험을통해정보를추출하고매칭을통해각기술자의검색성능을비교해본결과검색성능은거의차이가없음을확인하였다. 그림 9. 에지방향검출알고리듬 Fig. 9. Edge orientation detection algorithm. 그림 10. 복호화단에서의 EHD와 EHDiD 비교 Fig. 10. Comparision of EHD and EHDiD in decoder. (321)
24 MPEG-7 기반 DCT 영역에서의에지히스토그램고속추출기법엄민영외 Ⅳ. 실험제안한방법의성능을평가하기위한실험은 3022개의 JPEG 자연영상으로데이터베이스를구축하였고, 그림 11. 에서보여지는것처럼, 데이터베이스에존재하는 6개의영상들을질의입력영상으로사용하였다. 각각의질의영상들은건물, 자동차, 세포, 독수리, 코끼리, 펭귄으로대표되어지는영상들이며데이터베이스안에는각질의영상과유사한영상들 (ground-truth images) 이각각포함되었다. 서로유사한건물영상 8 장, 자동차영상 13장, 세포영상 33장, 독수리영상 24 장, 코끼리영상 14장, 펭귄영상 20장, 각각이렇게 ground-truth images를구성하였다. 소프트웨어는 Experimentation Model (XM) V6.0과자체적으로구성한검색엔진을사용하였다. 그림 13과표2는 EHD와 EHDiD의성능을비교한것이다. 성능분석지표로는 MPEG-7 에서기술자간의성능을비교하는데주로쓰이는 NMRR과 ANMRR을 이용하였다 [2]. 다음식은 NMRR과 ANMRR 을구하는식이다. 여기서 (9) (10) (11) (12) (13) 여기서 는질의하는영상이속해있는그룹내의전체영상개수이고, 은 중가장 (a)query1 (b)query2 (c)query3 NMRR 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 EHDiD EHD 1 2 3 4 5 6 query (d)query4 (e)query5 (f)query6 그림 11. 질의영상들 Fig. 11. Query images. 그림 12. EHDiD 를이용한검색결과예 Fig. 12. Example of search result using EHDiD. 그림 13. EHD와 EHDiD의 NMRR 비교 Fig. 13. Comparison of NMRR between EHD and EHDiD. 표 2. EHD 와 EHDiD 의 NMRR 과 ANMRR 비교 Table 2. Comparison of NMRR and ANMRR between EHD and EHDiD. NMRR EHD EHDiD query1 0.7324561404 0.6315789474 query2 0.8135451505 0.5911371237 query3 0.2668495298 0.4868077325 query4 0.1331360947 0.1528599606 query5 0.7835497835 0.6594516595 query6 0.670212766 0.6773049645 ANMRR 0.5466544966 0.5331900647 (322)
2006 년 7 월전자공학회논문지제 43 권 SP 편제 4 호 25 그림 14. EHD 와 EHDiD 간계산량비교 Fig. 14. Comparison of complexity between EHD and EHDiD. 큰값을의미한다. 가결정되면 Rank는어떤데이터셋이있는이미지를질의했을때검색순위가 K값이하일경우, 검색의순위와같고 K값보다클경우는검색순위에상관없이항상 K+1의값을가진다. Rank가구해지면, 등이구해지고 (Nomallized Modified Retrieval Rank) 은항상 0에서 1 사이의값을가지며, 낮은값일수록좋은검색결과를나타낸다. 최종적으로 은 들에대한평균을나타낸다. 그림 13과표2의결과는질의영상에따라약간의차이가있지만 EHDiD의검색성능이 EHD보다평균적으로약간우위에있는것을표2의 에의해확인할수있다. 그리고 EHDiD는 EHD의특징추출과정을위해필수적인요소인 IDCT가생략되고역양자화과정역시단순하게할수있다. 따라서특징을추출하는과정또한매우단순하며이러한 EHDiD의장점은고속추출을가능하게한다. 그림 14 는연산량의비교를나타내주는그림으로서곱셈과덧셈에대한비교의그래프이다. 특히제안된 EHDiD의경우 EHD보다곱셈량에대하여약 581배정도줄어든것을볼수있다. 최종적으로검색성능과연산량의측면에서볼때제안된방법은기존공간영역에서추출하는 EHD 보다훨신좋은성능을보임을알수있다. 과시간을많이줄일수있는장점이있어고속추출이가능하다. 제안한 DCT영역에서의기술자를사용하여압축된형태의멀티미디어로구성된데이터베이스시스템에서의특징추출및검색에유용하게사용할수있어정지영상으로구성된 JPEG 기반의검색시스템뿐만아니라 MPEG에서의비디오브라우징및인터넷에서의검색시스템에도유용하게사용될수있다. 본논문에서는에지의방향과강도의임계값에대해서는실험적으로결정하였으나, 앞으로계속되는연구에서최적의임계값을선정하는통계적인분석에대한연구가지속될것이다. 참고문헌 [1] MPEG-7, "Text of ISO/IEC 15938-3/FDIS Information technology - Multimedia content description interface - Part 3 Visual", ISO/IEC JTC1/SC29/WG11/N4358, July 2001, Sydney [2] B. S. Manjunath, Philippe Salembier, Thomas Sikora, "Introduction to MPEG-7", WILLEY & SONS, LTD, pp. 183-184, 2002. [3] Bo Shen and Ishwar K. Sethi, "Direct feature extraction from compressed images", in IS&T SPIE: Storage and Retrieval for Image and Video Databases IV, vol. 1995-1996, CA, pp.33-49 [4] Seong-Whan Lee, Young-Min Kim, and Sung Woo Choi, "Fast Scence Change Detection using Direct Feature Extraction from MPEG compressed Videos", IEEE Trans on Vol.2, December 2000. [5] Michael Lee, Surya Nepal, Uma Srinivasan, "Role of Edge Detection in Video Semantics", Pan Sydney Workshop on Visual Information Processing (VIP2002), Australia, Conferences in Research and Practice in Information Technology, 22. Jin, J. S., Eades, P., Feng, D. D. and Yan, H., Eds., ACS. 59, 2003. [6] Chee Sun Won, Dong Kwon Park, and Soo-Jun Park, "Efficient Use of MPEG-7 Edge Histogram Descriptor", ETRI Journal, Volume 34, Number 1, February 2002. Ⅴ. 결론 본논문에서제안한 DCT 영역에서에지히스토그램고속추출기법을사용하면공간영역에서의에지히스토그램추출을위한많은과정을생략할수있어연산량 (323)
26 MPEG-7 기반 DCT 영역에서의에지히스토그램고속추출기법엄민영외 저자소개 엄민영 ( 정회원 ) 2001 년 9 월연세대학교전파공학과 ( 공학사 ) 2004 년 3 월연세대학교대학원전기전자공학과 ( 공학석사 ) 2004 년 3 월 ~ 현재연세대학교대학원전기전자공학과박사과정 최윤식 ( 정회원 ) 1979 년연세대학교전기공학과 ( 공학사 ) 1984 년 Case Western Reserve Univ. 시스템공학과 (M.S.E.E.) 1987 년 Pennsylvania State Univ. 전기공학과 (M.S.) 1990 년 Purdue Univ. 전기공학부 (Ph.D) 1990 년 ~1993 년 ( 주 ) 현대전자산업전자연구소책임연구원 1993 년 ~ 현재연세대학교전기전자공학부교수 원치선 ( 정회원 ) 1982 년고려대학교전자공학과 ( 공학사 ) 1986 년 Univ. of Massachusetts Amherst ( 공학석사 ) 1990 년 Univ. of Massachusetts Amherst ( 공학박사 ) 1989 년 ~1992 년금성사중앙연구소선임연구원 1992 년 ~ 현재동국대학교전자공학과교수 남재열 ( 정회원 ) 1983 년경북대학교전자공학과 ( 공학사 ) 1985 년경북대학교대학원전자공학과 ( 공학석사 ) 1991 년 University of Texas at Arlington 전기공학과 ( 공학박사 ) 1985 년 ~1987 년한국전자통신연구소연구원 1991 년 ~1995 년한국전자통신연구소선임연구원 1995 년 ~ 현재계명대학교정보통신학부부교수 (324)