多邊形描述及其應用

Abstract

本論文提出一個基於多邊形狀的模型，多邊形描述模型 (Polygon description)，來將資料分佈的形狀以數值的形式來加以 描述。藉由對系統因子取樣，就可以繪製資料分佈圖來顯示系統因子 間的資料相依性。由於系統行為隱含在資料的相依性中，因此本文提 出之用來描述資料分佈形狀的多邊形描述模型便可被用來代表抽象的 系統行為。另外，為了衡量兩個多邊形描述模型間的相似度，本文提 出了兩個相似度比較的方法 - 1) 變形距離估計 (Deforming distance estimation) 以及 2) 正交向量比對 (Normal vectors match)。基於一組預先定義的變形運算元 (Deforming operator)， 變形距離估計 尋找變形所需的最小成本之運算元組合來衡量兩多邊 形描述模型間的相似程度。而正交向量比對則透過尋找兩組正交向量 間的最佳對應來對齊兩個多邊形描述模型，並根據正交向量間的角度 差異來衡量多邊形描述模型間的相似度。一般來說，變形距離估計擁 有比較良好的擴充能力但侷限於使用二維的資料。正交向量比對可以 適用於任何在任何維度上，但要延伸應用在特定應用上卻頗為困難。 除此之外，基於多邊形描述模型，基於相似度的分群方法可以 利用多邊形描述模型來加以強化。透過多邊形描述的的幫助，我們可 以幫只有相似度資訊的資料建立一個虛擬的空間，並在該虛擬空間中 幫每個群計算其變異度。除此之外，多邊形描述的涵蓋區域也可以用 來描述一塊區域。利用多邊形描述模型來描述的多邊形區塊將可以在 各式各樣的多媒體應用中被使用，例如區域篩選，追蹤等等。透過本 論文中展示的變異度強化K-Medoid 模型可以知道多邊形的概念可以 在分群方法上發揮相當的功能。 相對於提出來的三個延伸方法 1)變形估計，2)基於相似度分群 法的虛擬幾何，以及 3) 多邊形區域描述，本論文展示了三個實際應 用 1)財金資料挖況，2) 可變大小索引縮圖，以及 3) 多邊形區域選 取。這些展示顯示的多邊形描述是一個可以容易的就被設計成各種應 用的多功能模型。這些應用包含了資料挖況，圖形識別，多媒體，與 資料分群等。 除此之外，透過多邊形模型來描述諸如股市行為等的抽象資料 也有助於我們觀察這些抽象的資料。也就是說，多邊形模型不光只是 一個在特徵空間中的特徵向量，多邊形模型還可以告訴我們許多關於 目標物的資訊。由於多邊形描述代表了資料分佈的形狀，透過觀察估 算出來的多邊形描述就可以得到許多有用的資訊。

Polygon descriptor, a polygon-based shape model, is proposed to represent the shape of a data distribution in numerical form. By sampling signals from the factors of a system, a data distribution can be drawn to show the data dependency among factors. Since data dependency implies the system behavior, abstract system behavior can therefore be represented by the proposed Polygon descriptor which models the shape of sample data distribution in numerical representation. In addition, two similarity measurement methods - 1) Deforming distance and 2) Normal vectors match, are proposed to measure the similarity between polygon descriptors. Deforming distance measures the similarity between polygon descriptors by finding a minimal-cost combination of predefined deforming operations which transform a polygon descriptor to the other. Normal vectors match finds a best mapping between two sets of normal vectors to align two polygon descriptors, and measures the similarity between Polygon descriptor according to the angle difference between normal vectors. In general, Deforming distance is much expandable but special designed for 2-D data. On the other hand, Normal vectors match is possible to be with data in any dimension but difficult to expand for specific applications.

The proposed Polygon descriptor can also contribute to similarity based clustering methods. Based on the concept of Polygon descriptor, a virtual geometry based on similarity data can be used to estimate the variance of each cluster. A demonstration, which clusters images by using the Polygon descriptor enhanced K-Medoid, shows that the proposed methods can also be useful to improve the ability of clustering methods. Besides, the coverage area of a polygon descriptor can be used as a region representation. By describing the interesting region in the polygon shape of a polygon descriptor, various multimedia application, including region selection, tracking and so on, can be carried out.

In correspondance with the three proposed extension methods, 1) measurement of shape deformation, 2) virtual geometry for similarity based clustering, and 3) polygon-based region representation, three real world application, 1) financial data mining, 2) variable-sized thumbnail of web gallery service, and 3) polygonal region selection, are also demonstrated in this dissertation. These demonstrations show that Polygon descriptor is a versatile method, which is simple to be extended in various application domains, such as data mining, pattern recognition, multimedia, data clustering and so on.

Besides, describing abstract objects, such as stock market behavior, can also help us visualize the abstract objects. That is,a polygon descriptor is not only a feature vector in feature space, but also a descriptor that tell us a lot of informations about the target object. Since a polygon descriptor represents the sample data distribution, observing a polgyon descriptor estimated from a set of sample data already reveals various information about the observed.