Abstract
在本篇論文中，我們探討關於視訊與音樂資料的內涵式查詢的一些重要 問題。首先，我們描述用以表示影像、視訊與音樂的內涵的各種特徵值。 我們以物件模型為基礎，提出一個多媒體資料架構以及一個物件層時空間 模型來表示媒體物件間的時空間關係。在此多媒體資料架構中我們提出三 種新的合成關係。此外我們也提出一種多媒體查詢語言與兩種查詢介面讓 使用者來下達多媒體內涵式查詢。 第二，由於許多多媒體內涵式查詢問 題可以轉化為高維特徵值空間的最近鄰居搜尋問題，因此我們必須發展一 種有效率的最近鄰居搜尋演算法。我們所提出的方法是在每一維建立一個 索引。使用者在查詢時給定一個查詢樣本與相似度，此查詢樣本將被轉換 為高維特徵值空間中的一個點。我們藉由索引來取出每一維的可能答案， 在合併這些可能答案後移去超過相似度的點便可得到最終答案。第三，我 們基於圖像式索引的觀念提出一種視訊查詢模型。影像資料庫的二維字串 表示法被延伸成視訊資料庫的三維字串表示法。三維字串表示法可以用以 表示視訊資料與視訊查詢中的符號物件之時空間關係。視訊查訊處理因此 被轉換為三維字串比對問題。我們進一步設計一種稱為三維串列的資料結 構以及相關的演算法來加速三維字串的比對。最後，我們提出一種音樂資 料的內涵式查詢方法。在此方法中，各種主題特徵字串，如旋律字串、節 奏字串與和絃字串可以由音樂資料中抽取出作為表示其內涵的特徵值。音 樂查訊處理因此被轉換為主題特徵字串比對問題。我們提出一種考慮音樂 相似性的字串比對法。 AbstractIn this dissertation, we discuss important issues in content-based video and music data retrieval. First, we describe features used to model the content of image, video and music data. Based on the object model, we propose a multimedia framework and an object-level spatial/temporal model to represent the spatial/temporal relationships between media objects. Three new types of aggregation relationships composed of the composition, temporal, and spatial relationships are considered in the framework. To support content-based data retrieval, we propose a multimedia query language and two kinds of query interfaces for users to specify content-based queries. Second, since many content-based multimedia data retrieval problems can be transformed into the near neighbor searching problem in a multidimensional feature space, an efficient near neighbor searching algorithm is needed when developing a multimedia database system. We propose an approach to efficiently solve the near neighbor searching problem. In this approach, along each dimension an index is constructed according to the values of the feature points of the multimedia objects. A user can pose a content-based query by specifying a multimedia query example and a similarity threshold. The specified query example will be transformed into a query point in the multi- dimensional feature space. The possible result points in each dimension are then retrieved by searching the value of the query point in the corresponding dimension. The sets of the possible result points are merged one by one by removing the points which are not within the query radius. The result points and their distances from the query point form the answer of the query. Third, we propose a video query model based on the content of video and iconic indexing. The notion of two-dimensional strings is extended to three-dimensional strings (3D-Strings) for representing the spatial and temporal relationships among the symbols in both a video and a video query. The problem of video query processing is then transformed into a problem of three- dimensional pattern matching. To efficiently match the 3D- Strings, a data structure called 3D-List and its related algorithms are proposed. In this approach, the symbols of a video in the video database are retrieved from the video index and organized as a 3D-List according to the 3D-String of the video query. The related algorithms are then applied on the 3D- List to determine whether this video is an answer to the video query. Fourth, we propose an approach for content-based music data retrieval. In this approach, thematic feature strings, such as melody strings, rhythm strings, and chord strings are extracted from the original music objects and treated as the meta data to represent their contents. The problem of content- based music data retrieval is then transformed into the string matching problem. A new approximate string matching algorithm is proposed for content-based music data retrieval.