In many interactive multimedia systems, efficient retrieval of multimedia information in a digital form is becoming an important issue. Among all multimedia types (text, image, graphic, audio, and video), video is the most challenging one since all other media information can be combined into a single data-stream of video. Thanks to the lowered cost of digital storage media, increased transmission rates, and improved compression techniques, the use of digital videos has increased tremendously for the last few years. However, tools available for video retrieval still remain primitive. To solve this problem, efficient video analysis and summarization techniques are required. In this dissertation, we consider two key issues for effective video retrieval: video shot change detection and fast exhaustive image search. As the first issue, automatic shot change detection has been recognized as an important research topic for video classification because manual approaches have too slow processing speed and expensive cost to be accepted in practice. Therefore, we propose an automatic clustering-based algorithm for shot change detection in MPEG-compressed videos with a small number of user-defined parameters. For accurate detection of abrupt and gradual shot changes, the proper selection and extraction of features are important. We first propose a fast edge image extraction scheme in the DCT domain on the basis of AC prediction. Then, by using the features extracted from the edge images and DC images, a two-stage clustering-based algorithm is proposed for shot change detection. In the first stage, the algorithm detects abrupt shot changes by employing 2-means clustering on the 2-D feature space of histogram and pixel differences between two neighboring DC frames. In the next stage, it subsequently explores gradual shot changes between two adjacent abrupt shot changes by performing a 2-step clustering scheme, which uses multiple features such as an edge energy diagram and several frame difference measures. Simulation results show that the proposed shot change detection algorithm is fast and accurate. On the other hand, if shot change detection is completed along with key frame selection in off line, the shot that the user wants can be found by the technique such as visual query by example, where the query image is compared with all key frames in the database according to a certain similarity measure for visual features like color histogram. In order to find the best match to the query, the exhaustive search should be performed literally. However, the straightforward exhaustive search algorithm is computationally expensive in large databases. To reduce its heavy computational cost, we present a fast exhaustive multi-resolution search algorithm based on image database clustering. For fast exhaustive search, the proposed algorithm partitions the whole image data set into a pre-defined number of clusters having similar feature contents. Next, for a given query, it checks the lower bound of distances in each cluster, eliminating disqualified clusters. Then, it only examines the candidates in the remaining clusters. To alleviate unnecessary feature matching operations in the search procedure, the distance inequality property is employed based on a multi-resolution data structure. The proposed algorithm realizes a fast exhaustive multi-resolution search for either the best match or multiple best matches to the query. Using luminance histograms as a feature in the experiment, we prove that the proposed algorithm guarantees exhaustive search with high search speed.
최근 들어 상호연동 디지털 멀티미디어 시스템들에서 정보 검색 기술이 차지하는 비중이 점점 커지고 있다. 문자, 정지 영상, 그래픽, 동영상 등 멀티미디어 정보 중에서 특히 동영상은 멀티미디어 정보의 총아로서 가장 중요하게 다루어지고 있다. 낮아진 디지털 저장 매체 가격, 넓어진 전송률, 고 압축 기술 등의 도움으로 디지털 동영상의 사용이 최근 몇 년간 급격하게 증가하였다. 그러나, 동영상 검색을 위한 기술들은 여전히 낮은 수준에 머물러 있다. 이런 불균형을 해소하기 위해서는 효율적인 동영상 분석이나 표현 기술이 반드시 필요하다. 이 논문에서는, 효과적인 동영상 검색을 위한 다음 두 가지 주제를 심도 있게 다룬다. 그 하나는 동영상 장면 전환 검출이며, 다른 하나는 고속 전역 영상 탐색이다. 일반적으로 수동 방식의 검출이 속도가 매우 느리고 비용이 많이 들기 때문에, 자동 장면 전환 검출은 동영상 분석에 있어 매우 중요하다. 또한, 대부분의 동영상들이 MPEG이나 H.26x등으로 압축되어 있는 경우가 많다. 그래서, 이 논문은 MPEG으로 압축된 동영상에서의 장면 전환 검출을 위해, 클러스터링 기반의 장면 전환 검출 기법을 새롭게 제안한다. 클러스터링 기법의 장점 중 하나는 사용자가 정의하는 파라미터의 수가 비교적 적다는 것이다. 한편, 급진적 장면 전환은 물론 점진적인 장면 전환을 정확하게 검출하기 위해서는 특징들 (features)을 적당히 선택하고 추출하는 것이 중요하다. 이를 위해, 이 논문은 AC예측 기반의 DCT영역 고속 에지 영상 추출 기법을 제안한다. 또한, 에지 영상들과 DC 영상들로부터 추출된 특징들을 이용하여 장면 전환을 검출하기 위한 2-단계 클러스터링 기반 기법을 제안한다. 장면 전환 검출의 기법의 첫 단계로, 이웃하고 있는 DC 프레임들 간의 화소 차이 (pixel difference) 및 히스토그램 차이 (histogram difference)로 구성된 2 차원 특징 공간에 2-평균 클러스터링 (2-means clustering)을 적용하여, 급진적 장면 전환을 검출한다. 다음 단계에서, 검출된 이웃하고 있는 급진적 장면 전환 시점 사이에 존재할 수 있는 점진적인 장면 전환을 2번의 클러스터링을 거쳐 검출한다. 이 단계에서는 에지 에너지 다이어그램과 여러 종류의 프레임 차이들 같은 특징들을 사용한다. 모의 실험 결과를 통해 제안한 장면 전환 기법이 매우 빠르고 정확함을 확인할 수 있다. 한편, 오프라인으로 장면 전환 검출과 키 프레임 선택이 끝나면, 사용자는 예를 통한 시각 질의 (Visual Query by Example)같은 방식을 통해 온라인으로 원하는 장면을 찾을 수 있다. 이를 위해 칼라 히스토그램 같은 시각 특징을 이용한 유사도 측정자에 따라, 질의 영상이 데이터베이스의 모든 키 프레임들과 비교된다. 질의 영상과 가장 정합되는 영상을 찾기 위해 데이터베이스 내의 모든 영상들에 대해 전역 탐색이 이루어져야 한다. 그러나, 대용량 데이터베이스에서 단순한 전역 탐색을 수행할 경우 그 계산량이 방대하다. 이 논문은 계산량을 줄이기 위해, 클러스터링 기반의 고속 다 해상도 전역 탐색 기법을 제안한다. 고속 전역 탐색을 위해, 제안한 기법은 먼저 전체 영상 데이터 집합을 유사한 특징을 갖는 일정 수의 클러스터들로 나눈다. 그런 다음, 주어진 질의 영상에 대해 각 클러스터 당 거리 하한치 (lower bound)를 구하여, 가능성 없는 클러스터들을 솎아낸다. 살아 남은 클러스터들에 대해서 질의자와 후보 간 비교를 실시한다. 탐색 과정에서 불필요한 정합 연산을 줄이기 위해, 다 해상도 데이터 구조 기반의 거리 부등식 성질을 유도하고 탐색에 적용한다. 제안한 기법은 주어진 질의에 대한 최정합자 (best match)는 물론 다수의 상위 최정합자들까지 정확하게 찾을 수 있다. 이 논문에서는 밝기 히스토그램 특징만을 다뤘지만, 다 해상도 구조가 가능한 모든 특징들에 대해 제안한 기법의 적용이 가능하다. 모의 실험 결과를 통해 제안한 기법이 빠른 탐색 속도는 물론 항상 전역 탐색을 보장함을 보인다.
