VDCluster : 대용량 비디오 시퀀스를 위한 비디오 세그멘테이션 및 클러스터링 알고리즘

이석룡(Seok-Lyong Lee),이주홍(Ju-Hong Lee),김덕환(Doek-Hwan Kim),정진완(Chin-Wan Chung) 한국정보과학회 2002 정보과학회논문지 : 데이타베이스 Vol.29 No.3

본 논문에서는 비디오 저장이나 검색과 같은 비디오 정보 처리를 위한 중요한 기초 연구로써 비디오의 표현을 위한 효과적인 기법을 제안한다. 비디오 데이타 세트는 수초에서 수분 사이의 상연 시간을 갖는 비디오 클립들의 집합이며, 각 비디오 클립은 연속된 비디오 프레임들로 구성되어 있다. 이 비디오 클립은 다차원 데이타 시퀀스(multidimensional data sequence: MDS)로 표현될 수 있으며, 프레임 사이의 시간적인 정보를 고려하여 비디오 세그먼트로 나누어 지고, 한 클립 내에서 서로 유사한 세그먼트들은 다시 비디오 클러스터로 군집화된다. 따라서, 각 비디오 클립은 소수 개의 비디오 클러스터로 표현되어 진다. 본 논문에서 제안한 비디오 세그멘테이션 및 클러스터링 알고리즘 VDCLuster는 사전에 정의된 일정 수준의 클러스터링 품질을 보장하고 있으며, 다양한 비디오 시퀀스에 대한 실험을 통하여 알고리즘의 효과를 입증한다. In this paper, we investigate video representation techniques that are the foundational work for the subsequent video processing such as video storage and retrieval. A video data set is a collection of video clips, each of which is a sequence of video frames and is represented by a multidimensional data sequence (MDS). An MDS is partitioned into video segments considering temporal relationship among frames, and then similar segments of the clip are grouped into video clusters. Thus, the video clip is represented by a small number of video clusters. The video segmentation and clustering algorithm, VDCluster, proposed in this paper guarantee clustering quality to such an extent that satisfies predefined conditions. The experiments show that our algorithm performs very effectively with respect to various video data sets.

대규모 이미지 데이타베이스에서 고차원 색인 구조를 이용한 효율적인 내용 기반 검색 시스템

이동호(Dong-Ho Lee),박주홍(Ju-Hong Park),정진완(Chin-Wan Chung),김형주(Hyoung-Joo Kim) 한국정보과학회 1999 정보과학회논문지(B) Vol.26 No.1

이미지나 비디오, 오디오와 같은 멀티미디어 데이타들은 기존의 단순한 텍스트 기반의 데이타에 비하여 대용량적인 특성과 비정형적인 특성을 가지고 있어서 검색시 많은 어려움이 따른다. 본 논문에서는 대규모의 이미지 데이타베이스에서 효율적이고 신속하게 사용자가 원하는 이미지를 검색할 수 있는 내용 기반 검색 시스템을 제시한다. 이를 위해서 본 논문에서는 최근 여러 장점으로 인하여 신호 분석이나 이미지 압축 분야에 많이 사용되는 웨이브릿 변환을 이용하여 이미지 데이타로부터 내용 기반 검색에 사용되는 특징 벡터를 효율적으로 추출하는 기법과 유사성 측정 방법을 제안한다. 그리고, 이러한 특징 추출 방법과 유사성 측정 방법을 이용하여 내용 기반 질의 및 검색을 수행할 경우, 검색 조건을 만족하는 객체인데 실수로 검색해내지 못하는 경우인 false dismissals이 발생하지 않음을 보인다. 또한, 대규모 이미지 데이타베이스에서 신속한 내용 기반 검색을 지원하기 위하여 고차원 데이타에 대한 효율적인 색인을 제공하는 X-tree를 이용한 이미지 색인 방법을 보이며, 이것이 기존의 순차 검색이나 R*-tree를 이용한 색인 방법보다 신속하게 이미지 데이타들을 검색할 수 있다는 것을 다양한 실험을 통해 보인다. 마지막으로, QBIC에서 제안한 검색 적합성 측정 방법을 이용하여 본 논문에서 제안하는 내용 기반 이미지 검색 시스템의 검색 적합성을 보인다. There are many technically difficult issues in searching multimedia data such as image, video, and audio because they are more massive and more complex than simple text-based data. In this paper, we propose a content-based image retrieval method which can search large image databases efficiently by image content. For efficient feature extraction, we present a new method of extracting feature vector from image data using wavelet transform which is widely used in digital signal analysis and image compression. Then, we prove that there are no false dismissals in the case of searching image database using our proposed feature extraction and similarity measurement. We also show an image indexing method using X-tree that provides the efficient indexing for high-dimensional data to support fast retrieval in large image databases, and show that it supports faster retrieval than other method such as sequential scan or R*-tree through various experiments. Finally, we show the retrieval effectiveness of our content-based image retrieval system using the measurement proposed by QBIC system.

멀티미디어 데이타베이스에서 최근접 질의의 성능평가에 관한 분석 모델

이주홍,차광호,김형주,정진완(Ju-Hong Lee),Guang-Ho Cha,Hyoung-Joo Kim,Chin-Wan Chung 한국정보과학회 1999 정보과학회논문지(B) Vol.26 No.7

다차원 색인 트리를 이용하는 최근접 질의는 멀티미디어 데이타베이스템에서 자주 사용되는 중요한 질의 형식으로서 그 성능 분석은 질의 성능 개선을 위해 중요하다. 지금까지 다차원 트리에서의 질의 성능 분석 모델에 관한 대부분의 연구는 R 트리와 같은 특정 트리에서의 범위 질의에 대한 분석만을 주로 다루고 있었으나 최근 다차원 색인 트리에서 최근접 질의에 대한 성능 모델[1]이 발표되었다. 그러나 이 모델은 1-최근접 질의만을 다루고 있다. 본 논문에서는 다차원 색인 트리에서 일반적인 k-최근접 질의의 성능 분석 모델을 제시한다. 이 모델은 다차원 색인 트리의 종류나 k-최근접 질의 처리 알고리즘의 종류에 관계 없이 적용되는 모델이다. 모델의 기본 개념으로서 지역 평균 볼륨과 가변 밀도 함수의 개념을 소개한다. 본 모델의 이점은 다음과 같다: 임의의 데이타 분포를 가진 데이타 집합에 대해서도 적용 할 수 있고, 1-최근접 질의뿐 아니라 k-최근접 질의에서도 잘 적용되며, 색인 트리에 저장된 데이타로 곧바로 분석하므로 시간이 많이 소요되는 시뮬레이션 없이 빠르게 분석할 수 있다. 본 모델의 정확성을 평가하기 위해서 여러 가지 분포의 데이타 집합에 관하여 실험하였다. 실험 결과는 저차원 또는 중차원 데이타 집합에 대하여 데이타의 분포에 관계없이 정확한 결과를 보여주고 있다. The k-nearest neighbor query in multidimensional index tree is one of the most frequently used query types in multimedia databases. It is important to analyze the performance of the k-nearest neighbor query for its performance improvement. Until now, most of the analytic models are restricted to a particular type of the index tree, for example, the R-Tree and they concentrate on the analysis of the range query. Recently, a cost model [1] was reported for nearest neighbor queries. However, the model considered only 1-nearest neighbor queries rather than k-nearest neighbor queries. In this paper, we present an analytic model for the performance of the k-nearest neighbor query in multidimensional index trees. This model is independent of kinds of multi-dimensional index trees and k-nearest neighbor algorithms. As a basis of the model, we introduce the concept of the regional average volume and the varying density function. The advantages of our model are in particular as follows: It is applicable to any type of datasets with arbitrary distributions (uniform and non-uniform ones), works for the k- as well as 1-nearest neighbor query, and is a dynamic analysis method which enables a rapid analysis without requiring a time-consuming simulation of data. To estimate the accuracy of our model, we conducted a various range of experiments on the datasets with various distributions. The results show that our analytic model is accurate for the data sets with non-uniform distributions as well as uniform distributions in low and mid dimensions.

분산 멀티미디어 데이타베이스에 대한 수집 융합 알고리즘

김덕환(Deok-Hwan Kim),이주홍(Ju-Hong Lee),이석룡(Seok-Lyong Lee),정진완(Chin-Wan Chung) 한국정보과학회 2001 정보과학회논문지 : 데이타베이스 Vol.28 No.3

웹에서의 멀티미디어 데이타베이스가 발달함에 따라 분산 멀티미디어 데이타에 대한 검색 기능의 필요성이 높아지고 있다. 그러나 지금까지는 주로 웹상에 분산된 텍스트 데이타베이스를 선택하고 선택된 텍스트 데이타베이스에 대해서 질의 결과를 결합하는 연구가 이루어졌을 뿐 멀티미디어 데이타베이스에 대해서는 연구가 미진하였다. 웹상의 멀티미디어 데이타베이스는 자율적이고 이질적인 특성을 가지고 있고 주로 내용 기반으로 검색된다. 멀티미디어 데이타베이스에서의 수집 융합 문제는 웹상의 이질적인 멀티미디어 데이타베이스에서 내용 기반 검색으로 검색된 결과를 병합하는 것을 다룬다. 이 문제는 분산 멀티미디어 데이타베이스의 검색에 매우 중요하지만 아직까지 연구된 바가 없다. 본 논문은 웹상에서 이질적인 멀티미디어 데이타베이스의 수집 융합을 처리하는 새로운 알고리즘을 제안한다. 본 논문은 데이타베이스에서 검색할 객체의 개수를 추정하는 휴리스틱 방법과 선형 회귀 분석을 이용한 알고리즘을 사용한다. 그리고 실험에 의해서 이 알고리즘들의 효율성을 보였다. 이 알고리즘들은 향후 웹상의 멀티미디어 데이타베이스들에 대한 분산 내용 기반 검색 알고리즘들의 기본이 될 수 있다. With the advances in multimedia databases on the World Wide Web, it becomes more important to provide users with the search capability of distributed multimedia data. While there have been many studies about the database selection and the collection fusion for text databases distributed in the Web, a few researches have been attempted for the case of multimedia databases. The multimedia databases on the Web have autonomous and heterogeneous properties and they use mainly the content based retrieval. The collection fusion problem of multimedia databases is concerned with the merging of results retrieved by content based retrieval from heterogeneous multimedia databases on the Web. This problem is crucial for the search in distributed multimedia databases, however, it has not been studied yet. This paper provides novel algorithms for processing the collection fusion of heterogeneous multimedia databases on the Web. We propose two heuristic algorithms for estimating the number of objects to be retrieved from local databases and an algorithm using the linear regression. Extensive experiments show the effectiveness and efficiency of these algorithms. These algorithms can provide the basis for the distributed content based retrieval algorithms for multimedia databases on the Web.