방송공학회논문지 2007 년제 12 권제 2 호 159 일반논문 -07-12-2-10 MPEG-7 BiM 부호화기및복호화기의구현 염지현 a), 김혁만 a), 김민제 b), 이한규 b) Implementation of Encoder and Decoder for MPEG-7 BiM Jihyeon Yeom a), Hyeokman Kim a), Minje Kim b), and Hankyu Lee b) 요 약 본논문은 MPEG-7 에서표준화한 BiM 부호화방식을이용하여, 특정스키마문서에따라작성된 XML 인스턴스문서를이진형태로부호화하고또한역으로복호화하는소프트웨어시스템의구현에관한것이다. 본논문에서는 BiM 부호화기및복호화기의소프트웨어구조를클래스계층구조로설계하고, 설계한 BiM 부호화기및복호화기를구현한다. 구현된 BiM 부호화기는평균 90% 에해당하는부호화효율을보였다. BiM 부호화기는 MPEG-7 스키마문서뿐만아니라 XML Schema 로정의된스키마문서에따르는어떤인스턴스문서도부호화할수있는범용소프트웨어로써, 디지털방송을포함한 XML 인스턴스문서의부호화가필요한많은응용분야에서사용될수있다. Abstract In the paper, we implemented a software system that encodes XML instance documents conforming to a schema document according to the MPEG-7 BiM compression method, and decodes the encoded documents vice versa. We designed software structures of BiM encoder and decoder as class hierarchies, and then implemented the structures. The implemented BiM encoder shows a compression ratio of 9.44% on the average. The BiM encoder is a general-purpose XML compressor that can encode any instance documents conforming to a schema document described in XML Schema language including the MPEG-7 schema. The BiM encoder thus can be used in many application fields including digital broadcasting environment, where encoding XML instance documents is needed. Keywords : XML, MPEG-7, BiM, 부호화기, 복호화기 Ⅰ. 서론 최근인터넷뿐만아니라, 방송환경에서도데이터교환 a) 국민대학교컴퓨터공학부 School of Computer Science, Kookmin University b) 한국전자통신연구원전파방송연구단방송미디어연구그룹 Broadcasting Media Research Group, Radio & Broadcasting Research Division, ETRI 교신저자 : 김혁만 (hmkim@kookmin.ac.kr) 및표현의표준으로 XML(Extensible Markup Language) 이부각되고있다. XML 인스턴스 (instance) 문서는텍스트포맷으로써, 태그를사용하여데이터를구별하여표현한다. 따라서, 인스턴스문서는일반적인텍스트파일과비교하면, 그크기가매우크다. 인터넷환경에서는인스턴스문서를그대로전송하더라도그크기가문제가되지않을수도있지만, 디지털방송환경에서는대역폭의제약으로텍스트포맷의인스턴스문서를그대로전송하는것은비
160 염지현외 : MPEG-7 BiM 부호화기및복호화기의구현 효율적이다. 따라서, 인스턴스문서가지니는비정규적인구조와장황함때문에, 인스턴스문서의텍스트포맷을바이너리포맷으로이진부호화하는방법이필요하다. 대표적인텍스트파일부호화기법으로는 zlib를이용한 gzip 부호화방법이사용되고있다 [1]. 하지만이방법은 XML 인스턴스문서에포함된태그들도일반텍스트로처리하기때문에, XML 문서의부호화효율을높이기위해서는 XML 문서부호화를위한별도의방법이필요하다. 이에따라, XML 인스턴스문서의부호화기법에관한여러연구가진행되어왔다. XML 문서부호화방법은크게스키마문서를이용하지않는방법과이용하는방법으로나눌수있다. 전자의경우에는대표적인방법이 XMill이다. XMill은사전 (dictionary) 부호화기법을통해부호화하며 gzip 보다는인스턴스문서부호화에효율적이라고알려져있다 [2]. 한편, 인스턴스문서부호화시스키마문서를이용하게되면, 인스턴스문서를통해시멘틱구조를정확하게알수있으므로더효율적인부호화가가능하다. 뿐만아니라스키마문서의구조를이용하여인스턴스문서를부분적으로부호화하거나, 부호화된인스턴스문서에대한질의혹은부분적수정또한가능할수있다. 스키마문서는 DTD 혹은 XML Schema로기술하므로, 스키마문서를어떤언어로기술하느냐에따라다른방법이존재한다. DTD로기술한스키마문서에따라작성된인스턴스문서를부호화하는대표적인방법으로 XGrid가있다 [3]. XML Schema로기술된스키마문서에따라작성된인스턴스문서를부호화하는대표적인방법으로는 BiM이있다. BiM은 MPEG 그룹에서 MPEG-7 국제표준의일부로표준화한부호화방식으로, 원래는 XML Schema로기술된 MPEG-7 스키마문서에따라작성된인스턴스문서를부호화하기위한것이었으나, 표준제정과정에서 MPEG-7 스키마문서에따르는인스턴스문서뿐만아니라, XML Schema 로기술한스키마문서에따라는어떤인스턴스문서도부호화할수있는범용부호화기법으로확장되었다 [4]. 본논문에서는 XML 인스턴스문서를보다효율적으로부호화하는기법으로 MPEG Forum에서표준화한 MPEG-7 BiM을구현하였다. 본논문의구성은다음과같다. 2장에서는인스턴스문서를부호화하는방법에대해서소개한다. 3장에서는 BiM 부호화의원리에대해서서술하고, 4장에서는 BiM 부 / 복호화기의구조를설계한다. 5장에서는설계한구조를어떻게구현하였는지를서술하며, 6 장에서는구현한 BiM 부호화기의성능을실험한다. 그리고마지막으로 7장에서는결론및추후연구에대해서술한다. Ⅱ. XML 인스턴스문서의부호화방법일반적으로인스턴스문서의구성을보면, 태그와같은구조정보와순수데이터의비율은 1:4 정도로, 구조정보가인스턴스문서의크기에대부분을차지한다. 따라서, 인스턴스문서를부호화하고자할때, 태그를얼마만큼효과적으로부호화할수있느냐가관건이다. 인스턴스문서를부호화하는방법은태그를부호화하는알고리즘에따라 gzip 부호화기법, 사전부호화기법, 오토마타를이용한기법으로나눌수있다. 1. gzip 부호화기법일반적인텍스트파일부호화기법으로대표적인것은 zlib을이용한 gzip부호화방법이다 [1]. Zlib은 Jean-loup Gailly와 Mark Adler 가고안한데이터부호화알고리즘으로, 디플레이트 (deflate) 알고리즘을사용한다. 디플레이트는 LZ77 알고리즘 [5] 과허프만코딩 [6][7] 의혼합된형태로무손실데이터부호화알고리즘이다. 즉, LZ77 알고리즘을사용하여중복된데이터스트링을제거하고, 중복제거된데이터의이진코드길이를줄이기위하여허프만코딩을적용함으로써데이터의크기를줄인다. 일반적으로 40-50% 이상의부호화효율을보이는 gzip은인스턴스문서에포함된태그들도일반텍스트로처리하기때문에, 인스턴스문서의부호화효율을높이기위해서는별도의방법이필요하다.
방송공학회논문지 2007 년제 12 권제 2 호 161 2. 사전부호화기법인스턴스문서의태그들은많은경우에반복되는패턴들로이루어질수있다. 이경우, 자주발생하는태그에대한사전테이블을구성하여, 태그를사전테이블에부여된특정이진코드로변환함으로써데이터의크기를줄일수있다. 즉, 사전부호화방법은새로운단어마다다른정수를부여하여데이터를변환한다. 그러나, 사전부호화에서부여한정수들간의크기는본래데이터의크기와다르므로본래데이터들로의복원이필요하다 [3]. 사전부호화기법을사용하여인스턴스문서를부호화하는방법은크게스키마문서를이용하지않는방법과이용하는방법으로나눌수있다. 전자의경우의대표적인방법으로 XMill이있으며, DTD로기술한스키마문서에따라작성된인스턴스문서를부호화하는대표적인방법으로 XGrind가있다. 2.1 XMill XMill은스키마문서를이용하지않고인스턴스문서를부호화하는대표적인방법으로, 1999년에 Hartmut Liekfe 와 Dan Suciu에의해개발되었고, AT&T 연구소에서고안되었다 [2]. XMill 은그림 1과같이순수데이터를구조정보 (structure) 와구분하고, 재그룹화전략 (regrouping strategy) 에의해의미상관련있는데이터들을컨테이너별로분류한 후, 각컨테이너에최적화된데이터부호화방법을적용하여부호화한다. 일반적으로 XMill은평균적으로 80% 이상의부호화효율을보이며, gzip 보다는인스턴스문서부호화에효율적이라고알려져있다 [2]. 그러나 XMill의입력인스턴스문서의크기가 20K 바이트보다작을경우, gzip 보다뚜렷한효과를얻지못하며, XMill은부호화된인스턴스문서를질의하거나갱신할수없는단점이있다 [9]. 2.2 XGrind XGrind 는 DTD로기술한스키마문서에따라작성된인스턴스문서를부호화하는대표적인방법으로, 2002년에 Pankai M.Tolani와 Jayant R.Haritsa 에의해개발되었다 [3]. XGrind 는 XMill 과유사하게기본적으로구조정보와데이터를분리하여부호화한다. 그림 2와같이 DTD로기술된스키마를통해구성한심볼테이블 (symbol table) 과인스턴스문서내의엘리먼트와애트리뷰트의사용빈도수를나타낸빈도테이블 (frequency table) 을기반하여데이터값은허프만코딩기법으로, 태그는사전부호화기법으로부호화한다. 그림 2. XGrind 의전체구조 Fig. 2. Structure of XGrind 그림 1. XMill 의전체구조 Fig. 1. Structure of XMill XGrind는부호화된인스턴스문서를복호화하지않고질의 (query) 하는것을지원하며본래의인스턴스문서의구조를얻을수있다. 따라서, XGrind는이러한특징으로
162 염지현외 : MPEG-7 BiM 부호화기및복호화기의구현 팜탑 (palm-top) 컴퓨터와같은자원이제한적인처리디바이스에서유용한애플리케이션이다. 2.3 오토마타를이용한기법오토마타란디지털컴퓨터의수학적인모델인오토마톤 (automaton) 의복수형으로서, 자동기계장치란뜻을가진다. 이것은입력장치, 출력장치, 저장장치, 제어장치를가지고있으므로현대적인디지털컴퓨터가작동하는이론적인메커니즘이라볼수있다. 오토마타는수학적방법론에바탕을둔디지털컴퓨터의추상적인모델이므로오토마타는다음과같은필수적인특징들을가지고있다. 첫째, 오토마타는입력데이터를읽을수있는기능을가지고있다. 입력데이터는입력파일에쓰여져있는알파벳상의스트링으로이루어져있다. 둘째, 오토마타는특정형태의출력기능을가지고있다. 즉, 0 이나 1 의출력을낼수있다. 셋째, 오토마타는임시저장장치 (storage device) 를가질수있으며, 넷째, 유한개의내부상태 (internal states) 를제어할수있는제어장치 (control unit) 을가지고있다. 이것의제어에따라상태가변화될수있다. 이와같은원리의오토마타를인스턴스문서를부호화하기위한방법으로사용할수있다. XML 스키마로기술된스키마문서에따라오토마타를구성하여, 생성된오토마타를사용하여인스턴스문서를부호화하는대표적인방법으로 BiM이있다. BiM에서는태그들을그림 3과같이스키마문서를이용하여미리구성한오토마타를이용해부호화하며, 데이터는 zlilb로부호화한다 [4]. 그림 3. BiM 의부호화과정 Fig. 3. Encoding process of BiM XML 스키마는 DTD보다정교하게스키마문서의구조를기술할수있기때문에, 최근에많은기업이나국제기구에서그사용이확산되고있다. 특히, 멀티미디어메타데이터표준인 MPEG-7/21/101과맞춤형방송표준인 TV-Anytime 스키마문서가 XML 스키마로기술될뿐만아니라, 이들의메타데이터부호화방법으로 BiM이표준으로채택되면서그중요성이더욱커지고있다 [8]. 따라서, 본논문에서는오토마타를사용하여인스턴스문서를부호화하는 MPEG-7 BiM의구조를설계하고구현하였다. Ⅲ. BiM 부호화의원리 BiM 부호화기는스키마문서의정의에따르는오토마타를사용하여입력인인스턴스문서를이진스트링으로부호화한다. 부호화하는방법은엘리먼트의바인딩타입 (binding type) 의종류에따라다르다. 엘리먼트가단순타입 (simple type) 으로정의된경우에는단순타입의종류에따라특정부호화코덱을사용한다. 예를들어일반텍스트는 zlib를사용하고, 날짜와시간에해당하는텍스트스트링은비트스트링으로변환하여크기를줄인다. 그러나엘리먼트가복합타입 (complex type) 으로정의된경우는 FSA(Finite State Automata) 를사용하여부호화한다. 스키마문서에서정의되는대부분의엘리먼트는복합타입으로정의된다. 전자의경우는부호화방법이매우잘알려져있으므로, 여기서는 FSA를사용한복합타입의부호화원리에대해서만설명하도록한다. FSA는그림 4와같이상태 (state) 와전이 (transition) 로구성된다 [4]. FSA의상태는입력데이터를내부처리규칙에따라결과값을도출및저장하고, 전이는상태의변화및그전이를이동하게하기위해수행될필요가있을조건등을설명한다. 상태에는단순상태 (simple state) 와타입상태 (type state) 가있으며, 전이는엘리먼트전이 (element transition), 루프전이 (loop transition), 코드전이 (code transition) 및단순전이 (simple transition) 로나누어진다. 루프전이에는루프시작전이 (loop start transition), 루프연속전이 (loop continue transition), 루프끝전이 (loop end
방송공학회논문지 2007 년제 12 권제 2 호 163 transition) 가있다. 코드전이에는전환전이 (shunt transition) 가있으며, 코드전이의부여된비트값으로부호화한다. 루프전이는반복횟수를정의할수있는세가지 XML 스키마컴포넌트, 즉엘리먼트, 지명모델그룹 (named model group), 컴포지터 (compositor) 등을오토마타로표현할때사용한다. 이때, 반복횟수가 0 이면루프전이대신전환전이를사용하여나타낸다. 단순상태와단순전이는오토마타를구성하기위하여사용하며, 이진부호화결과에는영향을미치지않는다. 과비슷하게새로운시작상태와끝상태를추가한다. 또한최소반복횟수가 0임으로엘리먼트가생략될수있음을표현하기위해새로운시작상태와새로운끝상태를코드전이의한종류인전환전이를사용하여연결하고, 전환전이에이진코드값 "0" 을할당한다. 마지막으로표 1의 4번경우와같이최소반복횟수가 0이고최대반복횟수가 "unbounded" 일때는, 위의 2, 3번과정과같이새로운시작상태와끝상태를추가하고, 엘리먼트가무제한반복될수있음을표현하기위해 2번과같이이전끝상태와이전시작상태를루프전이로연결한다. 그리고 3과같이엘리먼트가생략될수있음을표현하기위해새로운시작상태 표 1. 반복횟수에따른엘리먼트 FSA 의구성 Table 1. Composition of Element FSA according to occurrences 종류반복횟수 Element FSA 최소최대 그림 4. Finite State Automata 구성 Fig. 4. Composition of the finite state automata) 1 1 1 임의의엘리먼트에대한 FSA는반복횟수에따라서, 표 1과같이구성된다. 표 1의 1번경우와같이최소반복횟수 (minoccurs) 가 1이고, 최대반복횟수 (maxoccurs) 가 1 일경우, FSA는엘리먼트전이가시작상태와끝상태를연결하는형태를이룬다. 이때끝상태는엘리먼트의바인딩타입의타입상태가되며, 이러한형태가하나의엘리먼트를부호화하기위한 FSA의기본구조이다. 표 1의 2번경우와같이최소반복횟수가 1이고, 최대반복횟수가 "unbounded" 일때, 1번의기본구조에새로운시작상태와끝상태를추가한다. 그리고코드전이를사용하여새로운시작상태와이전시작상태를연결하고, 이전끝상태와새로운끝상태를루프끝전이를사용하여연결한다. 이때코드전이에는이진코드값 "1" 을할당한다. 또한, 이엘리먼트가무제한반복될수있음을표현하기위해이전끝상태와이전시작상태를루프연속전이를이용하여연결한다. 표 1의 3번경우와같이최소반복횟수가 0이고, 최대반복횟수가 1일경우에는, 1의기본구조에 2번 2 1 3 0 1 4 0 unbounded unbounded * 기호설명 단순상태코드전이루프전이 타입상태엘리먼트전이단순전이
164 염지현외 : MPEG-7 BiM 부호화기및복호화기의구현 와끝상태를전환전이를사용하여연결하고, 전환전이에이진코드값 "0" 을할당한다. 위와같은엘리먼트 FSA 구성원리에따라, 스키마문서전체에대한 FSA는스키마에서엘리먼트정의시중첩된순서및나열순서에따라차례대로진행되어해당엘리먼트 FSA가문서전체에대한 FSA에하나씩추가되며구성된다. 예를들어, 아래의예제스키마문서는한개의전역엘리먼트 AElement와바인딩타입 AElementType을정의한다. AElementType은세개의자식엘리먼트를 sequence 컴포지터를사용하여포함한다. 이와같은예제스키마문서를토대로문서의루트인 AElement의 FSA를구성하면그림 5 그림 5. 예제스키마문서의 FSA Fig. 5. FSA of example schema document 표 2. 예제인스턴스문서의부호화결과 Table 2. Encoding result of example instance document 의미 코드전이 반복횟수 1 s t 공백 B 이진스트링 1 00010 00110001 01110011 01110100 00100000 01000010 E L e m e n t 2 01000101 01101100 01100101 01101101 01100101 01101110 01110100 00110010 n D 공백 B E l e M 01101110 01100100 00100000 01000010 01000101 01101100 01100101 01101101 e N t 코드전이 1 s t 공백 01100101 01101110 01110100 0 00110001 01110011 01110100 00100000 D E l e m e n T 01000100 01000101 01101100 01100101 01100101 01100101 01101110 01110100
방송공학회논문지 2007 년제 12 권제 2 호 165 와같다. 굵은화살표가가리키는것이시작상태이고, 두겹의원은끝상태를나타낸다. 그림 5에서알수있듯이 AElement는최소반복횟수가 1이고, 최대반복횟수가 1이기때문에, 표 1의 1번처럼구성되고, AElementType 은세개자식엘리먼트를포함하므로 AElementType에대한FSA는각각세개의자식엘리먼트 FSA를연결하여구성된다. 즉, BElement는최소반복횟수가 1이고, 최대반복횟수가 "unbounded" 이므로, 표 1의 2번과같이구성되고, CElement는최소반복횟수가 0이고, 최대반복횟수가 1이기때문에, 표 1의 3번처럼나타낼수있다. 그리고, DElement는반복횟수의기본값인최소반복횟수가 1, 최대반복횟수가 1이므로표 1의 1번과같은기본구조로구성된다. 이렇게각각구성된세개의엘리먼트 FSA 는단순전이로연결되어하나의 FSA를형성한다. 그리고 AElement의 FSA와 AElementType에대한 FSA를단순전이로연결하여예제스키마문서를나타내는완전한 FSA 가구성된다. 스키마문서전체에대한 FSA를이용하여인스턴스문서를부호화하는과정은토큰 (token) 이구성된 FSA의시작상태에서시작하여인스턴스문서내의엘리먼트순서대로정의된 FSA의각상태들을이동하면서끝상태에도달할때까지수행된다. 토큰은오토마타이론에서는문법적으로의미를갖는최소의단위를의미하지만, MPEG-7 에서는현재활성화된상태를표현하기위한표식으로사용된다. 이때, 토큰이현재상태에서임의의다른상태로이동하는것을 "crossed" 라하고, 토큰이임의의상태로 "crossed" 되면해당상태가 "activated" 되었다고한다. "crossed" 와 "activated" 를반복하면서점진적으로부호화과정을수행한다. 이때임의의엘리먼트에대한부호화결과는세부분으로이루어진다. 즉, 임의의상태에서바인딩타입상태까지의경로중코드전이에할당된비트값, 엘리먼트가인스턴스문서에서나타난횟수, 그리고엘리먼트의실제데이터를이진부호화한값들로이루어진다. 예를들어, FSA를이용한부호화과정을위의예제스키마문서에맞게작성된아래의예제인스턴스문서를사용하여설명한다. 그림 5의 FSA에서나타나듯이, 시작상태에서 AElementType 타입상태 (1) 로토큰이이동하면, AElementType 타입상태는 "activated" 되고, AElementType 의자식엘리먼트의부호화를시작한다. 이과정에서는코드전이가발생하지않으므로, 부호화된값이없다. AElementType 타입상태에서단순전이, 코드전이, 엘리먼트전이를 "crossed" 하여, BElement의바인딩타입상태 (2) 로토큰이이동하게된다. 이때, 코드전이의비트값인 "0" 이추가된다. 그리고, BElement 는인스턴스문서에서 2 번나타나므로, 반복횟수 "2" 를vluimsbf5 형식으로부호화하여 "00010" 으로나타낸다. 그리고실제데이터인 "1st BElement", "2nd BElement" 를 zlib을사용하여부호화한다. 이와같은과정으로 BElement의부호화과정이이루어진다. CElement는스키마에서는정의되었지만, 인스턴스문서에서는사용하지않았다. 따라서, FSA의토큰은그림 5의 2번타입상태에서 CElement의바인딩타입상태 (3) 를지나지않고, 바로 DElement의바인딩타입상태 (4) 로이동하게된다. 즉, 코드전이의한종류인전환전이를사용하여CElement 부호화과정을생략 (skip) 하고, 전환전이의비트값인 "0" 을추가한다. DElement 는스키마의정의에서최소및최대반복횟수가모두 1이므로, 인스턴스문서에서반듯이 1번사용되어야한다. 따라서, 반복횟수를부호화하여나타내지않고, DElement의실제데이터인 "1st DElement" 만을부호화한다. 인스턴스문서의부호화의결과는표 2를통해확인할수있다. 이후그림 5 4 번타입상태가끝상태이므로 AElement 의전체부호화과정은종료된다. Ⅳ. BiM 부 / 복호화기의구조 1. BiM 부호화기의구조본논문에서설계한BiM 부호화기의구조는그림 6과같다. 그림 6에서 BiM 부호화기는크게 schema validator, schema manager, instance manager로구성된다. Schema validator 는 XML Schema로문서의구조를표현한스키마문서와 XML로표현되는인스턴스문서를입력으로하여, 인스턴스문서의유효적합성을점검한다. 스키마문서는
166 염지현외 : MPEG-7 BiM 부호화기및복호화기의구현 단일의문서로구성될수도있으며, 임포트 (include)/ 인클루드 (include)/ 재정의 (redefine) 메커니즘을사용하여여러개의스키마문서가복잡하게연결될수도있다 [6]. 또한, 인스턴스문서는해당스키마문서에기반한완벽한문서일수도있고, 계속생성되는중간단계의문서일수도있다. 그러나, 어떠한형태의인스턴스문서일지라도스키마문서에항상유효 (valid) 해야한다. 만약, 스키마문서의정의가올바르지않거나, 인스턴스문서가스키마문서에유효하지않은경우에부호화작업을수행하지않는다. 일반적으로 XML 스키마문서및 XML 인스턴스문서파싱을위한파서에는 DOM 파서와 SAX 파서가있다. DOM 파서와 SAX 파서의가장큰차이는문서에접근하는방식이다르다는것이다. DOM 파서는문서를하나의트리구조로구성하여트리의특정노드를접근하여그정의를추출한다. 반면, SAX 파서는문서를하나의긴문자열로취급하여그문자열을앞에서부터차례로읽어가면서정보를추출한다. 이에따라 DOM 파서는문서를파싱하기위해전체문서를메모리에읽어들임으로써 SAX 파서보다메모리를많이소모하는문제가있다. Schema manager는스키마문서내의정의된순서대로 XML 스키마컴포넌트를파싱한다. 따라서, DOM 파서보다는 SAX 파서를사용하는것이더욱효율적일수있으므로 SAX 파서를이용하여스키마문서를파싱하도록설계하였다. 파싱과정을통하여스키마의정의내용을내부자료구조로재정의하고, 스키마문서의각컴포넌트를기호화하여간소화된스키마문서인 raw 파일을만든다. Schema manager는 생성된 raw 파일을사용하여 FSA를구성한다. BiM 부 / 복호화기의가장큰특징중하나는위에서언급한것과같이스키마문서를기반으로인스턴스문서를부호화및복호화한다. 따라서입력스키마문서를구조화된 FSA로생성, 관리, 사용하는모듈은 BiM 부 / 복호화기의핵심이다. Instance manager는인스턴스문서를 schema manager 에서생성한 FSA를사용하여부호화하는작업을수행한다. 즉, 텍스트형태의인스턴스문서를이진비트스트링으로변환하는기능을담당한다. 부호화된이진청크 (binary chunk) 는 chunk writer가이진파일형태로출력한다. 2. BiM 복호화기의구조 그림 6. BiM 부호화기의구조 Fig. 6. Structure of BiM encoder BiM 복호화기의구조는그림 7과같다. 그림 7의 BiM 복호화기는크게 schema manager와 binary manager로구성된다. BiM 복호화기는스키마문서또는 raw 파일, 및이진부호화된인스턴스문서를입력으로한다. 그림 7의 schema manager 는그림 6의 BiM 부호화기에서언급한것과동일하다. 단, 입력파일로 BiM 부호화기에서이미생성한 raw 파일을입력으로받았을경우에는스키마컴파일작업은수행하지않고바로 FSA를생성한다. 결과적으로, 복호화시 raw 파일이주어질경우에는 BiM 부호화기에서이미수행한동일한작업을중복수행을하지않아도되는이점이생긴다. 그림 7. BiM 복호화기의구조 Fig. 7. Structure of BiM decoder Binary manager 는 schema manager 에서생성한 FSA 를
방송공학회논문지 2007 년제 12 권제 2 호 167 사용하여이진부호화된인스턴스문서의복호화과정을수행한다. 복호화의결과로메모리에인스턴스문서의 DOM tree 구조가생성된다. 이 DOM tree 를 instance writer를통해서원래의인스턴스문서로출력한다. Ⅴ. BiM 부 / 복호화기의구현여기서는 3장에서설계한 BiM 부호화기및복호화기의세부구현및구현된모듈간의상호동작에대해기술한다. 본논문에서구현한 BiM 부 / 복호화기는 Linux Fedora Core 4.0 (64 bit) OS 환경에서 C++ 로구현하였다, 설계한모듈중 schema validator는부호화과정을수행하기위한전처리과정으로서, Apache사에서개발한 Xerces 파서 ( 버전 2.7.0) [10] 를그대로사용하였다. 따라서여기서는설계한 MPEG-7 BiM 부 / 복호화기모듈중 schema manager, instance manager, binary manager에대하여만기술한다. 이세부분은총 350여개클래스에 10만여줄의코드라인으로구현하였다. 본장에서는구현한 BiM 부 / 복호화기의자료구조및동작을구현한클래스계층구조 (class hierarchy) 를중심으로기술한다. 여기서기술하는클래스계층구조는실제로구현한내용중중요부분만을요약한것이며, 클래스들간의관계는 UML 다이어그램으로표현하였다. 1. Schema manager의구현 Schema manager는 BiM 부 / 복호화기의공통모듈로서, 스키마문서를파싱하여문서의내용을내부구조로표현하고 raw 파일을출력하는 schema compiler, 그리고 FSA를생성하는 FSA constructor로구성된다. 먼저, schema compiler가파싱한스키마문서를내부구조로표현하기위해서본논문에서설계한클래스계층구조는그림 8과같다. 스키마문서에서표현하는요소중가장기본은엘리먼트와타입이다. 엘리먼트는오직하나의특정타입에바인딩 (binding) 된다. 타입에는 2장에서설명하였듯이크게복합타입과단순타입두종류가있다 [11]. 복합타입은일반적으로엘리먼트와애트리뷰트를정의한다. 정의하는방법은특정타입내에서새로운엘리먼트와애트리뷰트를정의하는방법과, 상위타입의정의를상속받아엘리먼트와애트리뷰트를확장하거나제한하는방법이다. 후자의방법은엘리먼트요소를확장또는제한할수있는지의여부에따라 "simplecontent" 와 "complexcontent" 로나뉜다. 이러한 XML 스키마의특징에따라, 본논문에서는클래스계층구조를 TypeDefinition를최상위클래스로정의하고, ComplexTypeDefinition과 SimpleTypeDefinition을 TypeDefinition의하위클래스로분류정의한다. 그리고 ComplexTypeDefinition은타입정의방법에따라, com- 그림 8. 스키마문서표현을위한클래스계층구조 Fig. 8. Class hierarchy for representing schema document
168 염지현외 : MPEG-7 BiM 부호화기및복호화기의구현 plexcontent 요소를사용하여확장하는 ComplexContent- TypeDefinition, simplecontent 기법을사용하여정의하는 SimpleContentTypeDefinition을나누어정의하도록설계하였다. 이외의 XML 스키마요소인, "sequence", "choice", "all" 과같은컴포지터와 "group" 요소인지명모델그룹을위한클래스도정의하였다. 예를들어, 그림 9의클래스들중 TypeDefinition 클래스와그의하위클래스인 Complex- TypeDefinition 클래스의정의는다음과같다. TypeDefinition 클래스는기본적으로전역으로정의된타입인경우에는타입이름을설정하고, "isanonymous" 변수를 false로한다. 그이외에엘리먼트에바인딩되어익명으로정의된타입인경우에는 "isanonymous" 변수만 true 로설정한다. "simplecontent" 또는 "complexcontent" 요소를사용하여상속받은복합타입이거나, "restriction", "list", "union" 요소를사용하여상속받은단순타입일경우에는 realizeinheritance() 메소드를사용하여현재타입을기준으로상위타입과하위타입들간의계층구조를정의한다. 즉, 상위타입의이름으로타입정의를추출하여 supertype 변수에설정하고, adddirectsubtype() 메소드를사용하여 supertype의하위타입에현재타입을추가한다. ComplexTypeDefinition 클래스는위에서설명한것과같이, 복합타입의정의를나타낸다. 만약, 복합타입이추상타입으로정의되어있을경우, 즉, "abstract" 속성이 "true" 일경우에는, 인스턴스문서에서엘리먼트의바인딩타입으로쓰일수없고, "xsitype" 속성을사용하여하위타입으로대체하여사용해야한다. 따라서, 본클래스에서이러 한경우에는 "isabstract" 변수를 true로설정한다. 그리고, "mixed" 속성을사용할경우, "mixed" 변수값을 true로설정한다. 이후에, FSA constructor 모듈에서 generatefsa() 메소드를사용하여, 현재타입에서정의한애트리뷰트와내용모델의 FSA를구성한다. 이를위해 generateattribute- FSA() 와 generatecontentfsa() 메소드를호출한다. 이와같이 schema manager가내부적으로사용하는자료구조를갖게함으로서, 후에부호화및복호화과정에서스키마문서의정의내용을얻기위해다시파싱하는일을거치지않고, 효율적으로스키마문서의구조를접근할수있도록한다. Schema compiler 는그림 8에서정의한자료구조를사용하여입력스키마문서를단순화시킨 raw 파일을생성한다. 아래는간단한예제스키마문서및이문서에서생성된 raw 파일을나타낸다. 예제스키마문서는 "schema" 요소에서 2개의네임스페이스 (namespace) 를기술하고, 인스턴스문서에나타나는엘리먼트는네임스페이스로한정 (qualified) 하고, 애트리뷰트는한정하지않도록 (unqualified) 규정한다. 이와같은 "schema" 요소의네임스페이스와속성 (property) 의정의는 raw 파일에서 1과 2와같이각각변환된다. 즉, 네임스페이스를 "NAMESPACES" 키워드를사용하여알파벳순서대로네임스페이스 URI를출력한다. 그리고속성은 "PROPERTIES" 키워드를나타내고속성의개수와해당값을표시한다. 여기서, QE는 "element- FormDefault" 가 "qualified" 라는것을의미하고, UQA는 "attributeformdefault" 가 "unqualified" 라는것을나타낸 그림 9. Finite State Automata 구성을위한클래스계층구조 Fig 9. Class hierarchy for construction of finite state automata
방송공학회논문지 2007 년제 12 권제 2 호 169 class TypeDefinition { const XMLCh *name; /* attribute declaration */ bool isanonymous; set<typedefinition *> subtypes; TypeDefinition *supertype; const XMLCh* getname(); /* method declaration */ short getderivationmethod(); void setanonymous(bool); void getanonymous(); bool hassupertype(); /* methods for processing supertype */ void setsupertype(const XMLCh *, short); TypeDefinition *getsupertype(); bool hassubtypes(bool); /* methods for processing subtypes */ void adddirectsubtype(typedefinition *); int getnumberofsubtypes(bool); int getsubtypeindex(const XMLCh *, bool); SubtypesIterator* getsubtypesiterator(bool); TypeDefinition* getsubtype(int, bool); void realizeinheritance(typedefinitions *); /* method for type realization */... } class ComplexTypeDefinition : public TypeDefinition { bool isabstract; /* attribute declaration */ bool ismixed; OccurrenceNode *attributes; OccurrenceNode *content; CompressionFSA *compressionattributesfsa; DecompressionFSA *decompressionattributesfsa; CompressionFSA *compressioncontentfsa; DecompressionFSA *decompressionattributesfsa; bool hasattributes(); /* method declaration */ void setabstract(bool); bool getabstract(); void generatefsa(); void setmixed(bool); void getmixed(); void generatefsa(); FiniteStateAutomata* generateattributesfsa(); FiniteStateAutomata* generatecontentmodelfsa(); void realize(typedefinitions *);... } 다. "schema" 요소내부에정의된 XML 스키마컴포넌트요소들은다음과같은간단한규칙에따라출력된다. 엘리먼트는 "#namespace"nameofelement", 복합타입은 "{#namespace"nameofcomplextype}", 단순타입은 "<#namespace"nameofsimpletype>" 형식으로표현한다. 예들들어, 예제스키마문서의 "MPEG7Type" 은복합타입으로두번째네임스페이스인 "urn:mpeg:mpeg7:schema:2001" 에서정의한다. 따라서, 이복합타입은raw 파일에서 "{2"MPEG7Type}" 으로나타낸다. 또한, 복합형식의속 성인 "abstract" 와 "mixed" 는 "ABSTRACT" 와 "MIXED" 와같은키워드를사용하여나타낸다. 컴포지터는각각 "SEQ", "CHO", "ALL" 키워드로나타내고, 반복횟수는 "[minoccurs, maxoccurs]" 형식으로표현함으로써복잡한스키마문서를단순한형태로변화시킨다. 이렇게단순화시키는효과는메모리를많이사용하는스키마문서의파싱과정을단순화한파일을읽는과정으로대치함으로써, 메모리관리측면에서이득을얻을수있다. FSA constructor 는생성된 raw 파일을사용하여 FSA를
170 염지현외 : MPEG-7 BiM 부호화기및복호화기의구현 생성한다. 본논문에서는 2장에서설명한 FSA의구성동작을그림 9와같은클래스계층구조로구현하였다. FSA는기능에따라부호화 FSA 및복호화 FSA로나누며, 그림 6에서는각각 CompressionFSA 및 DecompressionFSA 클래스에대응된다. 그리고 FSA의구성요소인상태와전이는각각 State 와 Transition 클래스로구현하며, 상태와전이에관련된데이터들은각각연결리스트 (linked list) 구조로표현하였다. 예를들어, FiniteStateAutomata 클래스의정의는다음과같다. FiniteStateAutomata 객체는그림 8의 ComplexType- Definition 객체가 generatefsa() 메소드를호출함으로써생성된다. FiniteStateAutomata 클래스는상태객체를생성하여 states 리스트에상태를추가하고, 상태와상태를전이로연결하거나다른임의의오토마타의상태들과현재상 class FiniteStateAutomata { StateLinkedList *states; /* attribute declaration */ void addstate(state *); /* method declaration */ void merge(finitestateautomata *); void merge(state *, State *); State* getfirststartstate(); State* getfirstfinalstate(); StateLinkedList* getstartstate(); StateLinkedList* getfinalstate();... } 태들과병합하는과정을수행한다. 이와같이, 상태와전이를생성하고병합하는과정을스키마문서에서정의된스키마요소들을 raw 파일에서표현된순서에따라반복적으로수행하면서 FSA가구성된다. 이러한 FSA 클래스계층구조를사용하여, 부호화시에는인스턴스문서에명시된엘리먼트의바인딩타입의타입상태를이동하면서이동경로상에있는전이의값을이진스트링으로변환한다. 반대로복호화시에는이진스트링의값으로상태를이동하며해당타입상태의정의를도출하여 DOM tree를재구성한다. 2. Instance manager와 binary manager의구현 BiM 부 / 복호화기의 Instance manager와 binary manager 는그림 10에서정의한클래스계층구조를사용한다. Type- Encoder 클래스를기반으로타입의특성에따라 Simple- TypeInstance와 ComplexTypeInstance 클래스로나누며, ComplexTypeInstance 클래스는정의방법에따라 Simple- ContentTypeInstance와 ComplexContentTypeInstance 클래스로세분화하여정의한다. 예를들어, 그림 7의클래스들중 TypeInstance 와 Complex- TypeInstance 클래스의정의는아래와같다. Instance manager는스키마문서를 FSA를사용하여부호화하는모듈로서, TypeInstance의하위클래스의객체가 (NAMESPACES"http://www.w3.org/2001/XMLSchema" "urn:mpeg:mpeg7:schema:2001") --- 1 (PROPERTIES2QEUQA)--------------------------------------------------------------------------------2 {2"Mpeg7Type} (ABSTRACT) (ATTR 0"timeUnit[0,1]{2"durationType} 0"mediaTimeUnit[0,1]{2"mediaDurationType} 0"mediaTimeBase[0,1]{2"xPathRefType} 0"timeBase[0,1]{2"xPathRefType}) (SEQ[1,1] (SEQ[1,1] 2"DescriptionMetadata[0,1]{2"DescriptionMetadataType} ))
방송공학회논문지 2007 년제 12 권제 2 호 171 그림 10. Instance manager 와 binary manager 의클래스계층구조 Fig 10. Class hierarchy for instance manager and binary manager startencoding() 메소드를호출함으로서부호화과정을시작한다. 복합타입의경우에는내용모델과애트리뷰트를부호화하기위해각각 encodecontent() 와 encodeattribute() 메소드를호출한다. 각메소드는 FSA의시작상태에서끝상태로이동하면서타입정의에따라 TypeInstance 클래스의 encodetypeinfo() 메소드를수행하여, 부호화된이진스트링을 Chunk 객체로저장한다. 이와같은반복적인과정을수행한후에, FSA의끝상태에도달하면 endencod class TypeInstance : public TypeEncoder { void encodetypeinfo(); /* method declaration */ void decodetypeinfo();... } class ComplexTypeInstance : public TypeInstance { void startencoding(); /* methods for encoding */ TypeEncoder* encodecontent(const XMLCh *); TypeEncoder* encodeattribute(const XMLCh *); void endencoding(); void endcontentencoding(); void endattributeencoding(); void startdecoding(bittobitdatainputstream *); /* methods for decoding */ TypeEncoder* decode(bittobitdatainputstream *); void enddecoding();... } ing() 메소드를호출하고, chunk writer는생성된 Chunk 객체들을전달받아이진파일형태 (*.bin) 로출력한다. Binary manger는 FSA를사용하여이진스트링을인스턴스문서로복호화하는모듈이다. 이진파일을읽어 BitToBitDataInputStream 객체를생성하고, TypeInstance 클래스의하위클래스의객체가 startdecoding() 메소드를호출하면서복호화가시작된다. 복합타입의경우에는 decode() 메소드를호출하여애트리뷰트와내용모델을 FSA 를사용하여복호화한다. 즉, BitToBitDataInputStream 객체의이진스트링의값에따라 FSA의시작상태에서끝상태로이동하면서, TypeInstance 클래스의 decodetypeinfo() 메소드를실행하여타입의정의를 DOM tree 형태로재구성한다. 동일한반복과정후에, FSA의끝상태에도달하여 enddecoding() 메소드가호출되면, instance writer가구조화된 DOM tree 구조를인스턴스문서 (*.xml) 로출력한다. Ⅵ. 실험및결과본장에서는 NIST MPEG CVS Repository [12] 에서제공하는예제인스턴스문서를대상으로 BiM의부호화효율을앞서설명한 gzip, XMill, XGrind과비교한다.
172 염지현외 : MPEG-7 BiM 부호화기및복호화기의구현 표 3. MPEG 인스턴스문서의통계적정의 Table 3. Statistical definition of MPEG instance documents 표 3은예제 MPEG 인스턴스문서 [7] 의정의를문서의크기, 최대중첩깊이 (nesting depth), 엘리먼트와애트리뷰트의개수및실제데이터의비율의관점에서나타낸것이다. 문서의크기는바이트단위로나타내었고, 최대중첩깊이는인스턴스문서내에서엘리먼트태그가중첩된정도를의미한다. 실제데이터의비율은인스턴스문서내에서태그및공백문자를제외한실제데이터의비율을나타낸다. 사용한예제는각각 MPEG-7 스키마와 MPEG-21 스키마에따라정의된인스턴스문서그룹으로나누어그특징을살펴볼수있다. MPEG-7 스키마문서는인클루드나임 포트를사용하여다른스키마문서를포함하지는않지만, 스키마문서자체가 500여개의타입정의와 1000여개의엘리먼트로구성된거대한구조이다. 한편 MPEG-21 스키마문서들은대부분인클루드와임포트메커니즘을사용하여다른스키마문서를포함하는복잡한구조로되어있다. 예를들어, 09-DIA-AQoS.xml의스키마문서인 MPEG-21 AQoS.xsd의경우에는 MPEG-7 스키마문서를포함한 10 개의다른스키마문서를포함하고있다. 표 4는예제 MPEG 인스턴스문서에대한부호화실험결과이다. 실험기준인부호화효율과부호화효율요소 표 4. BiM 부호화기를사용한결과 Table 4. Results of encoding instance files using BiM encoder)
방송공학회논문지 2007 년제 12 권제 2 호 173 (compression ration factor) 의정의는다음과같다. 부호화효율요소는 BiM의부호화효율과 gzip, XMill, XGrind의부호화효율을비교하기위한것으로, 식의 x 는비교대상인 gzip, XMill, XGrind를의미한다. 에서 CRXGrind 중 - 으로표시한것은 XGrind 애플리케이션의오류로해당인스턴스문서를부호화하지못한것을의미한다. CR = 1 - CRF = sizeof(compresed file) sizeof(original file) CR BiM CR x 그림 11은각부호화기법의실험결과를도식화하여비교한것이다. 인스턴스문서 3을제외한모든인스턴스문서에대한 BiM의부호화효율이다른부호화기법보다훨씬높은것을알수있다. 인스턴스문서 3은엘리먼트 3,556개중 4개를제외하고나머지 3,552개가 "gbsdunit", "Parameter", "Value" 이름의엘리먼트가반복적으로나타난다. Gzip의경우에는 LZ77 알고리즘과허프만코딩을사용하 기때문에, 동일한엘리먼트는반복적으로사용하면빈도수가높아지기때문에, 엘리먼트를부호화하는이진코드의길이를줄일수있다. XMill은사전부호화기법을사용하므로인스턴스문서내에사용하는엘리먼트의개수가상대적으로적어지므로인스턴스문서 3에대한부호화효율이 BiM 보다높게나타날수있다. 또한, 인스턴스문서를두부류로분류하여살펴보면, MPEG-7 스키마로정의된인스턴스문서에대한 BiM 의부호화효율이다른부호화기보다월등하게높은것을확인할수있다. MPEG-21 인스턴스문서는소수의엘리먼트가반복적으로나타나는반면, MPEG-7 인스턴스문서는중복되는엘리먼트의수가적으므로 MPEG-7 스키마로정의된인스턴스문서의경우다른부호화기보다 BiM의부호화효율이높게나타난다. 그림 12는각부호화기법의효율이인스턴스문서내의엘리먼트태그의최대중첩깊이와의관계를나타낸것이다. BiM의경우다른부호화기에비하여인스턴스문서내의엘리먼트태그의중첩깊이가깊을수록부호화기의효과를더욱얻을수있는것을알수있다. 부호화기법에따른부호화효율 1.00 0.90 0.80 0.70 부호화효율 0.60 0.50 0.40 0.30 0.20 0.10 0.00 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 MPEG 인스턴스문서 BiM gzip XMill XGrind 그림 11. 부호화기법에따른부호화효율 Fig 11. Compression ration according to encoding method
174 염지현외 : MPEG-7 BiM 부호화기및복호화기의구현 그림 12. 최대중첩깊이에따른부호화효율의변화 Fig 12. Compression ratio according to nesting depth 그림 13. 중복엘리먼트와실제데이터의비율에따른부호화효율의변화 Fig 13. Compression ratio compared with effective data ratio 그림 13은중복엘리먼트의비율과실제데이터비율에따른부호화효율의변화를도식화한것이다. 각부호화기를비교해본결과, gzip과 XMill의경우중복엘리먼트의비율이높을수록대부분부호화효율이높은반면, BiM은중복엘리먼트의비율의영향을적게받는것을알수있다. 그리고대부분부호화기는실제데이터보다엘리먼트태그가많은경우에부호화효율이높아지는것을할수있다. 또한, gzip 이나 XMill의경우는엘리먼트태그의이진코드의길이가전체태그의개수에따라정의되지만, BiM의경우에는엘리먼트의바인딩타입의정의에따라자식엘리
방송공학회논문지 2007 년제 12 권제 2 호 175 먼트의개수로이진코드의길이가결정된다. 따라서, gzip 과 XMill의경우에는중복되지않은엘리먼트의개수가많아질수록부호화효율은떨어질수있지만, BiM의경우에는거의영향을받지않는다. 결과적으로 BiM 부호화기를사용하여평균적으로약 90% 에해당하는부호화효율을얻을수있으며, 이것은 gzip보다약 37%, XMill보다약 47%, XGrind 보다약 8% 정도높은효과를얻은것으로확인하였다. 그리고 BiM 부호화기를사용한인스턴스문서의부호화효율은최대중첩깊이가클수록, 인스턴스내에서실제데이터의비율이적을수록높은것도확인할수있었다. Ⅶ. 결론본논문은 MPEG-7 BiM 표준에따라, 스키마문서의정의를사용하여인스턴스문서를이진부호화하는 BiM 부호화기와이진파일을스키마문서를정의를기반으로인스턴스문서로복호화하는 BiM 복호화기를설계및구현하였다. 구현한 BiM 부호화기는실험에사용한 NIST MPEG CVS Repository 데이터셋에대하여평균 9.44% 에해당하는부호화효율을보였다. 구현한 BiM 부 / 복호화기는 MPEG 인스턴스문서뿐만아니라 XML Schema로기술한스키마문서에따르는어떤인스턴스문서도부호화할수있는범용 XML 문서부 / 복호화기이다. 따라서, XML Schema 및 XML이사용되는모든응용분야에서활용될수있으며, 특히, 대역폭의제약이심한디지털방송환경에서의활용가치가매우높을것으로예상된다. 현재구현된시스템은아직최적화되어있지않다. 특히복호화기는매우작은메모리와낮은성능의 CPU가장착된휴대 형단말기에서실행되는경우가많을것이므로, 최적화에특히많은노력이필요하다. 앞으로는이를위한연구가필요할것이다. 참고문헌 [1] Jean-loup Gailly, Mark Alder, "Gzip", July 27th, 2003, Available at : http://www.gzip.org [2] H. Liefke, D. Suciu, "XMill: An efficient compressor for XML data", Proc. of the 2000 ACM SIGMOD, pages 153-164, May 2000. [3] P. M. Tolani and J. R. Haritsa, "XGRIND: A Query-friendly XML Compressor", Proc. of 18thInternational Conference on Database Engineering, pages 255-234, 2002. [4] ISO/IEC JTC1/SC29/WG11 (MPEG), "Information Technology Multimedia Content Description Interface Part 1: Systems", International Standard 15938-1, ISO/IEC FDIS 15938-1:2001, Sep. 2001 (m7673). [5] Jakob Ziv and Abraham Lempel, "A universal algorithm for sequential data compression", IEEE Transactions on Information Theory, 23(3), pp.337-343, 1977. [6] D.Huffman, "A Method for Construction of Minimum- Redundancy Codes", In Proceedings of IRE, September 1952. [7] R.Pajarola, "Fast Huffman Code Processing", UCI-ICS Technical Report No. 99-43, pp.1-6, 1999. [8] TV-Anytime Forum, "TV-Anytime Phase 1, Part 3 : Metadata, Sub-part2 : System aspects in a uni-directional environment", ETSI Standard, ETSI TS 102 822-3-2, V.1.3.1 Jan. 2006. [9] Smith S.Nair, "XML Compression Techniques : A Survey" [10] Apache XML project, Xerces Java Parser 2.7.0 Release, 2005, Available at: http://xml.apache.org/xerces-c/. [11] H. S. Thompson, D. Beech, M. Maloney, N. Mendelsohn, "XML Schema Part 1 : Structures Second Edition", Oct. 2004, Available at : http://www.w3.org/tr/xmlschema-1/ [12] ISO/IEC JTC1/SC29/WG11 (MPEG), NIST MPEG CVS Repository, Available at : http://mpeg.nist.gov/cvsweb/mpeg-7.
176 염지현외 : MPEG-7 BiM 부호화기및복호화기의구현 저자소개 염지현 2005 년 2 월 : 국민대학교컴퓨터학부컴퓨터과학전공 ( 학사 ) 2007 년 2 월 : 국민대학교전산과학과 ( 석사 ) 2007 년 3 월 ~ 현재 : 국민대학교컴퓨터공학과박사과정 주관심분야 : TV-Anytime, MPEG-7, 디지털방송, 맞춤형방송, 메타데이터압축 김혁만 1985 년 2 월 : 서울대학교컴퓨터공학과 ( 공학사 ) 1987 년 2 월 : 서울대학교컴퓨터공학과 ( 공학석사 ) 1996 년 2 월 : 서울대학교컴퓨터공학과 ( 공학박사 ) 1996 년 ~ 1999 년 : 한국통신멀티미디어연구소 1999 년 ~ 현재 : 국민대컴퓨터공학부부교수 주관심분야 : XML, 메타데이터, 비디오모델링및인덱싱 김민제 2004 년 2 월 : 아주대학교정보및컴퓨터공학부 ( 학사 ) 2006 년 2 월 : 포항공과대학교컴퓨터공학과 ( 석사 ) 2006 년 2 월 ~ 현재 : 한국전자통신연구원방송미디어연구그룹연구원 주관심분야 : 디지털방송, TV-Anytime, MPEG-7 이한규 1994 년 2 월 : 경북대학교전자공학과 ( 학사 ) 1996 년 2 월 : 경북대학교전자공학과 ( 석사 ) 1996 년 2 월 ~ 현재 : 한국전자통신연구원방송미디어연구그룹맞춤형방송연구팀팀장 주관심분야 : 신호처리, 멀티미디어지능형 / 양방향시스템