Multi-level thresholding and Delaunay triangulation based methods for image segmentation and biomolecular data analysis

Abstract

This thesis investigates effective algorithms for image segmentation and their corresponding applications in many fields. Image segmentation classifies or clusters an image into several regions according to the features of the image. It is the fundamental procedure of image analysis. Over recent years, a large number of image segmentation algorithms have been developed. They are extensively applied in both science and daily life. In the first part of this thesis, a hierarchical multilevel thresholding method is proposed. In order to realize multilevel image thresholding fast and effectively, a tree structure is introduced to express the histogram hierarchy. During each level of the tree structure, the image is segmented by utilizing a three-level thresholding algorithm based on maximum fuzzy entropy principle. An edge similarity function is introduced for evaluating the performance of the proposed multilevel thresholding method according to the edge matching metric, which is proven to be effective by several experiments. Our experimental results show that the proposed multilevel thresholding method outperforms in retaining edge information. In the second part of the thesis, the application of our proposed multilevel thresholding in content-based image retrieval is explored. The hue, saturation and value (HSV) color space is uniformly quantized into 256 bins, and the multilevel thresholding algorithm is used to segment color images into five levels. An edge direction histogram, as the image feature descriptor of multilevel thresholded color images are introduced for the purpose of content-based image retrieval. Euclidean distance and cosine distance are utilized for computing the distances between image feature descriptor vectors. Compared to using an edge direction histogram of the original images, the proposed method outperforms in achieving higher average precision and recall with both distance measurements in most cases, with both the Euclidean distance and the cosine distance. The third part of the thesis focuses on blood cell segmentation. Blood cell segmentation is critical in medical image processing and plays an important role in cell analysis and clinical diagnosis. A new segmentation method is proposed for segmenting blood cell images. Delaunay triangulation is firstly used to construct cell images by extracting edge points. The useful boundary edges are retained by a statistical analysis of the Delaunay triangles. Based on the retained edges and the rough cell regions, a fuzzy curve tracing method is used to identify the smooth cell boundaries accurately. Our proposed method can automatically and accurately identify the cell region with a smooth closed curve. The techniques developed from image segmentation are not only used in the areas of computer vision, but also extended to geometrical molecular structure analysis. At the end of this thesis, we show another application of alpha shapes, subcomplexes of Delaunay triangulation, in understanding nucleosome structures. In this thesis, we mainly study the relationship between geometric patterns of hydrogen bonds and periodic dinucleotides in nucleosome structures. Statistical analysis of hydrogen bonds between the DNA chain and the histones in nucleosomes shows that there is a periodicity about 10 base pairs along the DNA sequence. This periodicity also exists in dinucleotides which are found to be highly correlated with these hydrogen bonds. By analyzing the components of these protein-DNA hydrogen bonds, we find that more than 86% of them are formed in periodic dinucleotides and one or more hydrogen bonds exist in the majority of periodic dinucleotides. We use the alpha shape model to study the geometric properties of hydrogen bonds in nucleosomes, and find that periodic dinucleotides have convex surface curvatures, which indicates that they have close contact with the histones. In summary, new effective algorithms for image segmentation and their applications are studied in this thesis. A multilevel thresholding method is proposed and used in content-based image retrieval by combining with an edge direction histogram. A new blood cell segmentation algorithm is presented to identify the cell boundaries accurately. The alpha shape model is utilized to study the geometric properties of nucleosome structures.

Date of Award	15 Feb 2013
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Hong YAN (Supervisor)