Due to the explosive growth of video data archives, the need to accurately index, search, and localize the desired video information for the purpose of efficient manipulation has been increased. Traditional video database access techniques based on the textual information have many drawbacks. To solve these problems, visual content based video retrieval methods have been introduced and developed by many researchers in recent years. The first step commonly taken for content-based digital video representation and retrieval is to detect shot boundaries. After the shot boundaries are identified, key frames are selected in each shot. With these key frames, most of the existing works compute the visual similarity between two video segments based on the key frames in order to retrieve desired video segments or represent and browse a video in a scene-transitive way using such tools as video poster or scene-transition graph. Therefore, the two key issues in the manipulation of video data for the purpose of information retrieval are video data structuring and video database searching and retrieval, which are the main components of this thesis.
First, as for video database searching and retrieval, we present a new distance measure and frame-level searching framework. Although most of users will typically be interested in the shot-level search and retrieval of video, exact locations at the frame-level may be necessary in many situations. However, little work has been performed on the frame-level video search. Even some existing methods usually concentrate on the definition of visual similarity and searching framework has attracted almost no attention. In this thesis, we focus on the exact localization of the video segments of interest at the frame level. The uniqueness of our approach lies in the computation of visual similarity measures adequate for frame-level video search and the candidate video segment selection method based on the visual content variation.
Secondly, as for video data structuring, clustering-based shot boundary detection and rate-constrained key frame selection method are devised. In the clustering-based shot boundary detection method, it is well known that the performance is highly dependent on the initial cluster centers. This phenomenon necessitates the appropriate estimation of initial cluster centers. In this thesis, we propose an abrupt shot change detection algorithm based on a modified k-means clustering. Complementary multiple features are used to increase the reliability of the detection and an adaptive estimation of initial cluster centers is proposed.
Lastly, the controllability of the total key frame number (i.e. key frame rate) depending on the storage, bandwidth, and computation capacity is an important requirement for key frame selection methods. However, conventional key frame selection methods need many trial-and-errors in order to select the desired number of key frames. In this thesis, we present two sequential key frame selection methods, aiming at selecting the desired number of key frames in order to control the computation load in the video searching by the user. The first one is based on the philosophy that temporal variation of a video segment should be equally distributed to each key frame. The second one iteratively selects key frames and break-points in order to reduce the distortion as much as possible, making both key frames and break-points locally optimal.
비디오 데이터의 양이 증가함에 따라 원하는 비디오 정보를 정확하게 검색하고 찾는 연구에 대한 필요성이 커지고 있다. 전통적인 비디오 데이터베이스 검색 기법은 주로 텍스트 기반으로 이루어졌으며 색인 과정에 사용자의 주관적 판단이 개입되기 쉽고 많은 시간이 필요하다는 단점이 있다. 이런 문제를 해결하기 위해 최근 들어 시각적 내용물을 사용한 비디오 검색 기법이 소개되고 연구되어 왔다.
내용물 기반의 비디오 표현 및 검색을 위해서는 먼저 비디오의 샷 경계를 찾아야 한다. 샷 경계를 찾은 후, 각 샷에서 주요 화면을 찾는다. 그리고 이 주요 화면으로 두 비디오 세그먼트 사이의 유사도를 정의한 후, 비디오 검색을 하거나 비디오를 표현하고 훑어보기 등을 한다 . 따라서 비디오 검색을 위해서는 크게 `비디오 데이터의 구조화`와 `비디오 검색 기법`이 필요하며, 본 논문에서는 이 두 가지에 관해서 다루었다.
먼저, 비디오 검색을 위해, 본 논문에서는 화면 단위의 검색 기법을 제안하였다. 지금까지는 대부분 샷 단위의 검색 방법이 많이 소개되어 왔지만, 무인 감시 환경에서 중요 사건을 시간대별로 찾거나, 스포츠 중계에서 느린 움직임 재생 화면을 찾기 위한 응용 분야 등 많은
경우에 있어서 화면 단위의 검색이 필요하다. 하지만 화면 단위의 검색 기법에 대한 연구는 거의 이루어지지 않았다. 현재까지 이루어진 화면 단위의 검색 방법은 대부분 시각적 유사도를 정의하는데 초점을 맞추었을 뿐, 검색 방법 자체에 대한 정량적 모델링 및 분석은 거의 없었다. 본 논문에서는 화면 단위의 비디오 검색을 위해 먼저 방향성이 있는 거리 값 계산 방법을 제안하였으며 내용물의 변화량을 고려한 후보 비디오 세그먼트 선택 기법을 제안하였다. 그리고 비디오 세그먼트의 통계적 특성을 이용해서 비디오 검색 방법의 시간과
성능을 정량적으로 분석하였다.
다음으로, 비디오 데이터의 구조화를 위해 클러스터링 기반의 샷 경계 검출 방법과 율-제한 주요 화면 선택 기법을 제안하였다. 클러스터링 기반의 샷 경계 검출에서는 성능이 초기 중심의 위치에 따라 달라진다는 사실에 착안하여, 주어진 데이터에 맞게 초기 중심을 적응적으로 계산하는 방법을 제안하였다.
그리고 계산 속도, 저장 능력, 전송 대역폭 등에 따라서 주요 화면의 개수를 조절하는 능력은 주요 화면 선택 기법이 가져야 할 필수적인 사항이다. 하지만 기존의 주요 화면 선택 기법들은 주요 화면의 개수를 조절하기 위해 여러 번의 시행 착오를 겪어야 한다. 본 논문에서는 시행 착오가 필요 없는 두 종류의 순차적 주요 화면 선택 기법을 제안하였다. 첫째 방법에서는 비디오의 내용물의 변화량이 각각의 주요 화면에 동일하게 배분되도록 주요 화면을 선택하였다. 그리고 둘째 방법에서는 주요 화면과 분절점이 각각 국부적으로 최적이 되도록 반복 과정을 통해 주요 화면을 선택하였다.
