Clustering Learning And Image Segmentation On "Complex" Structure

The notion of complex structure visually implies that the clusters hidden in the data set may be i) the arbitrary shapes, i.e. the majority of them are the non-convex manifold structures, besides the compact and convex clouds of data points; ii) contaminated by a great deal of noise or outliers; iii) overlapping or intersecting; iv) the different densities; v) the large scale. The digital image is the most traditional example of such types of data with complex structures. In the representation of the data configuration, it explicitly manifests that intra-cluster similarity is smaller than the inter-cluster similarity. This contradicts the normal purpose of clustering. Most of the existing clustering algorithms hence fail in dealing with such data. As a result, the learning of complex structure clustering currently becomes one of the hot topics and mainstreams in the fields of data mining and image segmentation.Obviously, this problem is very challenging. This dissertation will investigate and deliberate upon this difficult issue. Some meaningful and promising methods are presented. They can discover the clusters with complex structures effectively and efficiently. Moreover, parts of them are successfully applied to the problem of gray image segmentation. In the following, the main contributions of this dissertation are summarized and partitioned into two sections:Section I. Clustering of Complex Structure:(1) A heuristics structure-connectedness based clustering algorithm is presented. Concretely, two neighborhood based density indexes are first defined, which utilize the Euclid and polynomial kernel distance respectively. The data points then perform three different structural roles within the data organization, i.e. the centriod, the hub and the outlier. Next, the connectivity between the centriods and a normalized path-based structural metric are built. After this, the data points are clustered in a heuristics way. Experimental results indicate that the proposed algorithm is robust to the noise, efficient and effective on finding the clusters with arbitrary shapes and on separating the overlapping clusters.(2) Two objective-function-based clustering algorithms, i.e. fuzzy c-means (FCM) and normalized cuts (Ncuts) are greatly improved by embedding the structure-consistency into the similarity between data. Specifically, there are two different structure-consistency embedded similarities. They are respectively the similarity of density-consistency and the similarity of manifold-consistency. Accordingly, two similarity matrixes can be defined and embedded into FCM and Ncuts. Experimental results indicate that the two modified algorithms have the much better performance of clustering. They become robust to the noise, effective on finding the clusters with arbitrary shapes and different densities. Moreover, they can effectively separate the intersecting clusters.Section II. Complex Structure Clustering Based Image Segmentation:(1) A gray-neighborhood based directed tree (GNDT) algorithm for image segmentation is presented. Concretely, a gray-neighborhood based density factor is first defined. All the grays in the image then become the dense grays or sparse grays. Only the dense grays are provide with the ability of propagation and thus can be taken as the root nodes to construct new directed trees. The collection of pixels with the grays which are the nodes of the same directed tree form an expected segmented region. Because GNDT considers no spatial information between pixels, it has a constant computational complexity O(256) which is independent of the image size. Experimental results indicate that GNDT is robust to the selection of the initial root node and effective to preserve the details of image.(2) A scale-based connected coherence tree (CCT) algorithm for image segmentation is presented. Concretely, incorporating with spatial neighborhood information between pixels, a neighborhood based coherence factor is first defined. All the pixels in the image then become the seed pixels or non-seed pixels. Only the seed pixels are provided with the ability of propagation and thus can be taken as the root node to construct new connected coherence trees. Next, a connected coherence segmentation criterion is specified, and thereby the notions of equivalence class and coherence class are further introduced. This theoretically ensures the separability of an arbitrary image. Finally, the collection of pixels which are the nodes of the same connected coherence tree form a coherence class. Each coherence class just corresponds to an expected segmented region. Experimental results indicate that GNDT can achieve a semantic segmentation efficiently and effectively, that is, one object of interested belongs to the same segmented region as a whole.