본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

MPEG-7 시각 정보 기술자의 특성을 반영한 효율적인 멀티미디어 데이타 비트맵 인덱싱 방법
An Efficient Bitmap Indexing Method for Multimedia Data Reflecting the Characteristics of MPEG-7 Visual Descriptors

정진국   (삼성종합기술원  ); 낭종호   (서강대학교 컴퓨터학과UU0000674  );
  • 초록

    최근 멀티미디어 정보를 기술하기 위한 표준인 MPEG-7이 제안되어 이미지/동영상 검색 시스템과 간은 응용분야에서 사용되기 시작하였다. 그러나 MPEG-7 시각 정보 기술자들은 대부분 고차원으로 표현이 되고, 고차원에서 발생되는 문제인 "Curse of dimensionality" 때문에 기존의 인덱싱 방법(예를 들면 트리 구조를 이용하는 다차원 인덱싱 방법, 차원을 줄이는 방법, 양자화 등의 압축 기법을 이용하는 방법 등)으로는 효율적인 검색을 할 수 없다. 본 논문에서는 MPEG-7 시각 정보 기술자들의 특징을 반영한 효율적인 인덱싱 방법을 제안한다. 제안된 방법에서는 기술자를 속성 히스토그램으로 변형하고 히스토그램의 자 빈 값을 이진 형태로 표현하여 비트열을 생성하며, 이러한 비트열들을 이용하여 비트맵 인덱스를 구성한다. 질의 오브젝트가 입력되면 비트맵 인덱스를 이용하여 결과에 포함될 가능성이 있는 후보 오브젝트 리스트를 생성하게 되는데 즉, 각 오브젝트의 인덱스와 질의 오브젝트의 비트열에 대한 XOR(Exclusive OR) 연산을 수행하여서 후보 오브젝트 리스트를 생성한다. 그리고 이 리스트에 있는 오브젝트들에 대해서만 L1-norm과 같은, 기술자를 위해 사용되는 비교 연산식을 수행하여 최종 결과 오브젝트들을 사용자에게 보여주게 된다. 본 논문에서 제안하는 알고리즘은 단순한 비트 연산을 통해 검색 결과에 포함될 가능성이 있는 오브젝트들을 추출해낼 수 있기 때문에 빠른 시간 내에 검색을 마칠 수 있도록 해준다. 실험에 의하면 제안한 방법을 이용하는 경우, 90% 이상의 정확도를 유지하면서 검색 시간에서는 순차 검색에 비해 15배 이상의 속도 향상을 보임을 알 수 있었다.


    Recently, the MPEG-7 standard a multimedia content description standard is wide]y used for content based image/video retrieval systems. However, since the descriptors standardized in MPEG-7 are usually multidimensional and the problem called 'Curse of dimensionality', previously proposed indexing methods(for example, multidimensional indexing methods, dimensionality reduction methods, filtering methods, and so on) could not be used to effectively index the multimedia database represented in MPEG-7. This paper proposes an efficient multimedia data indexing mechanism reflecting the characteristics of MPEG-7 visual descriptors. In the proposed indexing mechanism, the descriptor is transformed into a histogram of some attributes. By representing the value of each bin as a binary number, the histogram itself that is a visual descriptor for the object in multimedia database could be represented as a bit string. Bit strings for all objects in multimedia database are collected to form an index file, bitmap index, in the proposed indexing mechanism. By XORing them with the descriptors for query object, the candidate solutions for similarity search could be computed easily and they are checked again with query object to precisely compute the similarity with exact metric such as Ll-norm. These indexing and searching mechanisms are efficient because the filtering process is performed by simple bit-operation and it reduces the search space dramatically. Upon experimental results with more than 100,000 real images, the proposed indexing and searching mechanisms are about IS times faster than the sequential searching with more than 90% accuracy.


  • 주제어

    멀티미디어 인덱싱 .   멀티미디어 내용기반 검색 .   비트맵 인덱싱.  

  • 참고문헌 (16)

    1. M.Martinez, Overview of the MPEG-7 Standard (version 5.0), ISO/IEC JTC1/ SC29/WG11/ N4031, March 2001 
    2. A. Yamada, M. Pickering, S. Jeannin, L. Cieplinski, and Jens, MPEG-7 Visual part of eXperimentation Model Version 9.0, ISO/IEC JTC1/ SC29/WG11/ N3914, January 2001 
    3. B.S. Manjunath, P. Salembier, and T. Sikora, Introduction to MPEG-7, John Wiley & Sons LTD, 2002 
    4. H. Lu, Y. Yeung Ng, and Z. Tian, 'T-tree or B-tree : Main Memory Database Index Structure,' Proceedings of 12th Australasian Database conference, pp. 65-73, 2001 
    5. R. Orlandic and B. Yu, 'Implementing KDB-Trees to Support High-Dimensional Data,' Proc. International Database Engineering and Applications Symposium, pp.58-67, 2001 
    6. K. Lin, and C. Yang, 'The Ann-tree: an Index for Efficient Approximate Nearest Neighbor Search,' Proceedings of 7th International Conference on Database Systems for Advanced Applications, pp. 174-181, 2001 
    7. Q. Yang, A. Vellaikal, and S. Dao, 'MB+- tree: A New Index Structure for Multimedia Databases,' Proceedings of International Workshop on Multimedia Database Management Systems, pp. 151-158, 1995 
    8. N. Beckmann, H.P, Kriegal, R. Schneider, and B. Seeger, 'The R*-tree: An Efficient and Robust Access Method for Points and Rectangles,' Proceedings of ACM SIGMOD Conference, pp. 321-331, 1990 
    9. S. Berchtold, D.A. Keim, and H.P. Kriegel, 'The X-tree: An Index Structure for High-Dimensional Data,' Proceedings of 22nd International Conference Very Large Databases, pp. 28-39, 1996 
    10. N. Katayama, and S. Satoh, 'The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries,' Proceedings of ACM SIGMOD Conference, pp. 369-380, 1997 
    11. K.V.R. Kanth, D. Agrawal, and A. Singh, 'Dimensionality Reduction for Similarity Searching in Dynamic Databases,' Proceedings of ACM SIGMOD Conference, pp. 166-177, 1998 
    12. E. Tuncel, H. Ferhatosmanoglu, and K. Rose, 'VQ-Index: An Index Structure for Similarity Searching in Multimedia Databases,' Proceedings of ACM International Conference on Multimedia, pp. 543-552, 2002 
    13. G.H. Cha, X. Zhu, D. Petkovic, and C.W. Chung, 'An Efficient Indexing Method for Nearest Neighbor Searches in High-Dimensional Image Databases,' IEEE Transaction on Multimedia, Vol. 4, No.1, pp. 76-87, 2002 
    14. C.C. Aggarwal, and P.S. Yu, 'The IGrid Index: Reversing the Dimensionality Curse for Similarity Indexing in High Dimensional Space,' Proceedings of ACM SIGKDD International Conference, pp. 119-129, 2000 
    15. P.O. Neil, and D. Quass, 'Improved Query Performance with Variant Indexes,' Proceedings of ACM SIGMOD Conference, pp. 38-49, 1997 
    16. P. Weber, H. J. Scheck, and S. Blott, 'A Quantitative Analysis and Performance Study for Similarity Search Methods in High Dimensional Space,' Proceedings of VLDB Conference, pp. 194-205, 1998 

 저자의 다른 논문

  • 낭종호 (45)

    1. 1996 "병렬화 컴파일러의 소개" 정보과학회지 = Communications of the Korean Institute of Information Scientists and Engineers 14 (7): 4.1~4.14    
    2. 1999 "대화형 멀티미디어 상영을 위한 멀티미디어 동기화 명시 모델" 정보과학회논문지. Journal of KISS (a):computer systems and theory. A 26 (2): 125~135    
    3. 1999 "멀티미디어 파일 시스템을 위한 효율적인 버퍼 관리 방안" 정보과학회논문지. Journal of KISS (a):computer systems and theory. A 26 (3): 271~281    
    4. 1999 "매크로블록 정보를 이용한 MPEG-1 비디오 스트림의 장면 변화검출" 정보과학회논문지. Journal of KISS (a):computer systems and theory. A 26 (4): 527~537    
    5. 2000 "MPEG 비디오 스트림에 대한 MC-DCT 영역에서의 자막 처리 방법" 정보과학회논문지. Journal of KIISE. 소프트웨어 및 응용 27 (10): 1003~1014    
    6. 2000 "아이큐브" 정보과학회지 = Communications of the Korean Institute of Information Scientists and Engineers 18 (10): 54~55    
    7. 2000 "MPEG 시스템 스트림상에서 오디오 정보를 이용한 장면 경계 검출 방법" 정보과학회논문지. Journal of KIISE. 소프트웨어 및 응용 27 (8): 864~876    
    8. 2000 "MPEG-1 비디오 스트림에 대한 압축 영역에서의 장면 전환 효과 처리" 정보과학회논문지. Journal of KIISE. 정보통신 27 (2): 109~122    
    9. 2000 "MPEG 비디오 스트림에서 줄거리 특성에 기초한 장면 경계 검출 방법" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 27 (1): 1~12    
    10. 2001 "폭발장면 자동 검출을 위한 저급 수준 비디오 특징의 추상화" 정보과학회논문지. Journal of KIISE. 소프트웨어 및 응용 28 (5): 389~401    

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기