Grabcuts for image segmentation: a comparative study of clustering techniques
- Authors: Manzi, Nozuko Zuleika
- Date: 2019
- Subjects: Algorithms , Computer graphics
- Language: English
- Type: Thesis , Masters , MSc
- Identifier: http://hdl.handle.net/10353/14494 , vital:39995
- Description: Image segmentation is the partitioning of a digital image into small segments such as pixels or sets of pixels. It is significant as it allows for the visualization of structures of interest, removing unnecessary information. In addition, image segmentation is used in many fields like, for instance healthcare for image surgery, construction, etc. as it enables structure analysis. Segmentation of images can be computationally expensive especially when a large dataset is used, thus the importance of fast and effective segmentation algorithms is realised. This method is used to locate objects and boundaries (i.e. foreground and background) in images. The aim of this study is to provide a comparison of clustering techniques that would allow the Grabcuts for image segmentation algorithm to be effective and inexpensive. The Grabcuts based method, which is an extension of the graph cut based method, has been instrumental in solving many problems in computer vision i.e. image restoration, image segmentation, object recognition, tracking and analysis. According to Ramirez,et.al [47], the Grabcuts approach is an iterative and minimal user interaction algorithm as it chooses a segmentation by iteratively revising the foreground and background pixels assignments. The method uses min-cut/ max-flow algorithm to segment digital images proposed by Boykov and Jolly [9]. The input of this approach is a digital image with a selected v region of interest (ROI). The ROI is selected using a rectangular bounding box. The pixels inside the bounding box are assigned to the foreground, while the others are assigned to the background. In this study, the Grabcuts for image segmentation algorithm designed by [48] with a Gaussian Mixture Model (GMM) based on the Kmeans and Kmedoids clustering techniques are developed and compared. In addition, the algorithms developed are allowed to run on the Central Processing Unit (CPU) under two scenarios. Scenario 1 involves allowing the Kmeans and Kmedoids clustering techniques to the Squared Euclidean distance measures to calculate the similarities and dissimilarities in pixels in an image. In scenario 2, the Kmeans and Kmedoids clustering techniques will use the City Block distance measure to calculate similarities as well as dissimilarities between pixels in a given image. The same images from the Berkeley Segmentation Dataset and Benchmark 500 were used as input to the algorithms and the number of clusters, K, was varied from 2 to 5. It was observed that the Kmeans clustering technique outperformed the Kmedoids clustering technique under the two scenarios for all the test images with K varied from 2 to 5, in terms of runtime required. In addition, the Kmeans clustering technique obtained more compact and separate clusters under scenario 1, than its counterpart. On the other hand, the Kmedoids obtained more compact and separate clusters than the Kmeans clustering technique under scenario 2. The silhouette validity index favoured the smallest number of clusters for both clustering techniques as it suggested the optimal number of clusters for the Kmeans and Kmedoids clustering techniques under the two scenarios was 2. Although the Kmeans required less computation time than vi its counterpart, the generation of foreground and background took longer for the GMM based on Kmeans than it did for the GMM based on Kmedoids clustering technique. Furthermore, the Grabcuts for image segmentation algorithm with a GMM based on the Kmedoids clustering technique was computationally less expensive than the Grabcuts for image segmentation algorithm with a GMM based on the Kmeans clustering technique. This was observed to be true under both scenario 1 and 2. The Grabcuts for image with the GMM based on the Kmeans clustering techniques obtained slightly better segmentation results when the visual quality is concerned, than its counterpart under the two scenarios considered. On the other hand, the BFscores showed that the Grabcuts for image segmentation algorithm with the GMM based on Kmedoids produces images with higher BF-scores than its counterpart when K was varied from 2 to 5 for most of the test images. In addition, most of the images obtained the majority of their best segmentation results when K=2. This was observed to be true under scenario 1 as well as scenario 2. Therefore, the Kmedoids clustering technique under scenario 2 with K=2 would be the best option for the segmentation of difficult images in BSDS500. This is due to its ability to generate GMMs and segment difficult images more efficiently (i.e. time complexity, higher BF-scores, more under segmented rather than over segmented images, inter alia.) while producing comparable visual segmentation results to those obtained by the Grabcuts for image segmentation: GMM-Kmeans.
- Full Text:
Qualitative and quantitative properties of solutions of ordinary differential equations
- Authors: Ogundare, Babatunde Sunday
- Date: 2009
- Subjects: Differential equations , Lyapunov functions , Chebyshev polynomials , Algorithms
- Language: English
- Type: Thesis , Doctoral , PhD (Applied Mathematics)
- Identifier: vital:11588 , http://hdl.handle.net/10353/244 , Differential equations , Lyapunov functions , Chebyshev polynomials , Algorithms
- Description: This thesis is concerned with the qualitative and quantitative properties of solutions of certain classes of ordinary di erential equations (ODEs); in particular linear boundary value problems of second order ODE's and non-linear ODEs of order at most four. The Lyapunov's second method of special functions called Lyapunov functions are employed extensively in this thesis. We construct suitable complete Lyapunov functions to discuss the qualitative properties of solutions to certain classes of non-linear ordinary di erential equations considered. Though there is no unique way of constructing Lyapunov functions, We adopt Cartwright's method to construct complete Lyapunov functions that are required in this thesis. Su cient conditions were established to discuss the qualitative properties such as boundedness, convergence, periodicity and stability of the classes of equations of our focus. Another aspect of this thesis is on the quantitative properties of solutions. New scheme based on interpolation and collocation is derived for solving initial value problem of ODEs. This scheme is derived from the general method of deriving the spline functions. Also by exploiting the Trigonometric identity property of the Chebyshev polynomials, We develop a new scheme for approximating the solutions of two-point boundary value problems. These schemes are user-friendly, easy to develop algorithm (computer program) and execute. They compare favorably with known standard methods used in solving the classes of problems they were derived for
- Full Text: