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:
- Date Issued: 2019
Sketch-based digital storyboards and floor plans for authoring computer-generated film pre-visuals
- Authors: Matthews, Timothy
- Date: 2012
- Subjects: Computer graphics , Computer vision
- Language: English
- Type: Thesis , Masters , MSc
- Identifier: vital:10463 , http://hdl.handle.net/10948/d1008430 , Computer graphics , Computer vision
- Description: Pre-visualisation is an important tool for planning films during the pre-production phase of filmmaking. Existing pre-visualisation authoring tools do not effectively support the user in authoring pre-visualisations without impairing software usability. These tools require the user to either have programming skills, be experienced in modelling and animation, or use drag-and-drop style interfaces. These interaction methods do not intuitively fit with pre-production activities such as floor planning and storyboarding, and existing tools that apply a storyboarding metaphor do not automatically interpret user sketches. The goal of this research was to investigate how sketch-based user interfaces and methods from computer vision could be used for supporting pre-visualisation authoring using a storyboarding approach. The requirements for such a sketch-based storyboarding tool were determined from literature and an interview with Triggerfish Animation Studios. A framework was developed to support sketch-based pre-visualisation authoring using a storyboarding approach. Algorithms for describing user sketches, recognising objects and performing pose estimation were designed to automatically interpret user sketches. A proof of concept prototype implementation of this framework was evaluated in order to assess its usability benefit. It was found that the participants could author pre-visualisations effectively, efficiently and easily. The results of the usability evaluation also showed that the participants were satisfied with the overall design and usability of the prototype tool. The positive and negative findings of the evaluation were interpreted and combined with existing heuristics in order to create a set of guidelines for designing similar sketch-based pre-visualisation authoring tools that apply the storyboarding approach. The successful implementation of the proof of concept prototype tool provides practical evidence of the feasibility of sketch-based pre-visualisation authoring. The positive results from the usability evaluation established that sketch-based interfacing techniques can be used effectively with a storyboarding approach for authoring pre-visualisations without impairing software usability.
- Full Text:
- Date Issued: 2012
A framework proposal for algorithm animation systems
- Authors: Yeh, Chih Lung
- Date: 2006
- Subjects: Computer programming , Computer algorithms , Computer graphics
- Language: English
- Type: Thesis , Masters , MCom
- Identifier: vital:10488 , http://hdl.handle.net/10948/d1019680
- Description: The learning and analysis of algorithms and algorithm concepts are challenging to students due to the abstract and conceptual nature of algorithms. Algorithm animation is a form of technological support tool which encourages algorithm comprehension by visualising algorithms in execution. Algorithm animation can potentially be utilised to support students while learning algorithms. Despite widespread acknowledgement for the usefulness of algorithm animation in algorithm courses at tertiary institutions, no recognised framework exists upon which algorithm animation systems can be effectively modelled. This dissertation consequently focuses on the design of an extensible algorithm animation framework to support the generation of interactive algorithm animations. A literature and extant system review forms the basis for the framework design process. The result of the review is a list of requirements for a pedagogically effective algorithm animation system. The proposed framework supports the pedagogic requirements by utilising an independent layer structure to support the generation and display of algorithm animations. The effectiveness of the framework is evaluated through the implementation of a prototype algorithm animation system using sorting algorithms as a case study. This dissertation is successful in proposing a framework to support the development of algorithm animations. The prototype developed will enable the integration of algorithm animations into the Nelson Mandela Metropolitan University’s teaching model, thereby permitting the university to conduct future research relating to the usefulness of algorithm animation in algorithm courses.
- Full Text:
- Date Issued: 2006
An investigation of hair modelling and rendering techniques with emphasis on African hairstyles
- Authors: Patrick, Deborah Michelle
- Date: 2005 , 2013-10-17
- Subjects: RenderMan , Hairstyles -- Africa , Hairstyles -- Computer simulation -- Africa , Hairdressing of Black people , Computer graphics
- Language: English
- Type: Thesis , Masters , MSc
- Identifier: vital:4639 , http://hdl.handle.net/10962/d1006561 , RenderMan , Hairstyles -- Africa , Hairstyles -- Computer simulation -- Africa , Hairdressing of Black people , Computer graphics
- Description: Many computer graphics applications make use of virtual humans. Methods for modelling and rendering hair are needed so that hairstyles can be added to the virtual humans. Modelling and rendering hair is challenging due to the large number of hair strands and their geometric properties, the complex lighting effects that occur among the strands of hair, and the complexity and large variation of human hairstyles. While methods have been developed for generating hair, no methods exist for generating African hair, which differs from hair of other ethnic groups. This thesis presents methods for modelling and rendering African hair. Existing hair modelling and rendering techniques are investigated, and the knowledge gained from the investigation is used to develop or enhance hair modelling and rendering techniques to produce three different forms of hair commonly found in African hairstyles. The different forms of hair identified are natural curly hair, straightened hair, and braids or twists of hair. The hair modelling techniques developed are implemented as plug-ins for the graphics program LightWave 3D. The plug-ins developed not only model the three identified forms of hair, but also add the modelled hair to a model of a head, and can be used to create a variety of African hairstyles. The plug-ins significantly reduce the time spent on hair modelling. Tests performed show that increasing the number of polygons used to model hair increases the quality of the hair produced, but also increases the rendering time. However, there is usually an upper bound to the number of polygons needed to produce a reasonable hairstyle, making it feasible to add African hairstyles to virtual humans. The rendering aspects investigated include hair illumination, texturing, shadowing and antialiasing. An anisotropic illumination model is developed that considers the properties of African hair, including the colouring, opacity and narrow width of the hair strands. Texturing is used in several instances to create the effect of individual strands of hair. Results show that texturing is useful for representing many hair strands because the density of the hair in a texture map does not have an effect on the rendering time. The importance of including a shadowing technique and applying an anti-aliasing method when rendering hair is demonstrated. The rendering techniques are implemented using the RenderMan Interface and Shading Language. A number of complete African hairstyles are shown, demonstrating that the techniques can be used to model and render African hair successfully. , GNU Ghostscript 7.07
- Full Text:
- Date Issued: 2005
Implementing non-photorealistic rendering enhancements with real-time performance
- Authors: Winnemöller, Holger
- Date: 2002 , 2013-05-09
- Subjects: Computer animation , Computer graphics , Real-time data processing
- Language: English
- Type: Thesis , Masters , MSc
- Identifier: vital:4580 , http://hdl.handle.net/10962/d1003135 , Computer animation , Computer graphics , Real-time data processing
- Description: We describe quality and performance enhancements, which work in real-time, to all well-known Non-photorealistic (NPR) rendering styles for use in an interactive context. These include Comic rendering, Sketch rendering, Hatching and Painterly rendering, but we also attempt and justify a widening of the established definition of what is considered NPR. In the individual Chapters, we identify typical stylistic elements of the different NPR styles. We list problems that need to be solved in order to implement the various renderers. Standard solutions available in the literature are introduced and in all cases extended and optimised. In particular, we extend the lighting model of the comic renderer to include a specular component and introduce multiple inter-related but independent geometric approximations which greatly improve rendering performance. We implement two completely different solutions to random perturbation sketching, solve temporal coherence issues for coal sketching and find an unexpected use for 3D textures to implement hatch-shading. Textured brushes of painterly rendering are extended by properties such as stroke-direction and texture, motion, paint capacity, opacity and emission, making them more flexible and versatile. Brushes are also provided with a minimal amount of intelligence, so that they can help in maximising screen coverage of brushes. We furthermore devise a completely new NPR style, which we call super-realistic and show how sample images can be tweened in real-time to produce an image-based six degree-of-freedom renderer performing at roughly 450 frames per second. Performance values for our other renderers all lie between 10 and over 400 frames per second on homePC hardware, justifying our real-time claim. A large number of sample screen-shots, illustrations and animations demonstrate the visual fidelity of our rendered images. In essence, we successfully achieve our attempted goals of increasing the creative, expressive and communicative potential of individual NPR styles, increasing performance of most of them, adding original and interesting visual qualities, and exploring new techniques or existing ones in novel ways. , KMBT_363 , Adobe Acrobat 9.54 Paper Capture Plug-in
- Full Text:
- Date Issued: 2002
Designing and implementing a virtual reality interaction framework
- Authors: Rorke, Michael
- Date: 2000
- Subjects: Virtual reality , Computer simulation , Human-computer interaction , Computer graphics
- Language: English
- Type: Thesis , Masters , MSc
- Identifier: vital:4623 , http://hdl.handle.net/10962/d1006491 , Virtual reality , Computer simulation , Human-computer interaction , Computer graphics
- Description: Virtual Reality offers the possibility for humans to interact in a more natural way with the computer and its applications. Currently, Virtual Reality is used mainly in the field of visualisation where 3D graphics allow users to more easily view complex sets of data or structures. The field of interaction in Virtual Reality has been largely neglected due mainly to problems with input devices and equipment costs. Recent research has aimed to overcome these interaction problems, thereby creating a usable interaction platform for Virtual Reality. This thesis presents a background into the field of interaction in Virtual Reality. It goes on to propose a generic framework for the implementation of common interaction techniques into a homogeneous application development environment. This framework adds a new layer to the standard Virtual Reality toolkit – the interaction abstraction layer, or interactor layer. This separation is in line with current HCI practices. The interactor layer is further divided into specific sections – input component, interaction component, system component, intermediaries, entities and widgets. Each of these performs a specific function, with clearly defined interfaces between the different components to promote easy objectoriented implementation of the framework. The validity of the framework is shown in comparison with accepted taxonomies in the area of Virtual Reality interaction. Thus demonstrating that the framework covers all the relevant factors involved in the field. Furthermore, the thesis describes an implementation of this framework. The implementation was completed using the Rhodes University CoRgi Virtual Reality toolkit. Several postgraduate students in the Rhodes University Computer Science Department utilised the framework implementation to develop a set of case studies. These case studies demonstrate the practical use of the framework to create useful Virtual Reality applications, as well as demonstrating the generic nature of the framework and its extensibility to be able to handle new interaction techniques. Finally, the generic nature of the framework is further demonstrated by moving it from the standard CoRgi Virtual Reality toolkit, to a distributed version of this toolkit. The distributed implementation of the framework utilises the Common Object Request Broker Architecture (CORBA) to implement the distribution of the objects in the system. Using this distributed implementation, we are able to ascertain that CORBA is useful in the field of distributed real-time Virtual Reality, even taking into account the extra overhead introduced by the additional abstraction layer. We conclude from this thesis that it is important to abstract the interaction layer from the other layers of a Virtual Reality toolkit in order to provide a consistent interface to developers. We have shown that our framework is implementable and useful in the field, making it easier for developers to include interaction in their Virtual Reality applications. Our framework is able to handle all the current aspects of interaction in Virtual Reality, as well as being general enough to implement future interaction techniques. The framework is also applicable to different Virtual Reality toolkits and development platforms, making it ideal for developing general, cross-platform interactive Virtual Reality applications.
- Full Text:
- Date Issued: 2000
Virtual sculpting : an investigation of directly manipulated free-form deformation in a virtual environment
- Authors: Gain, James Edward
- Date: 1996
- Subjects: Computer simulation , Computer graphics , Virtual reality
- Language: English
- Type: Thesis , Masters , MSc
- Identifier: vital:4660 , http://hdl.handle.net/10962/d1006661 , Computer simulation , Computer graphics , Virtual reality
- Description: This thesis presents a Virtual Sculpting system, which addresses the problem of Free-Form Solid Modelling. The disparate elements of a Polygon-Mesh representation, a Directly Manipulated Free-Form Deformation sculpting tool, and a Virtual Environment are drawn into a cohesive whole under the mantle of a clay-sculpting metaphor. This enables a user to mould and manipulate a synthetic solid interactively as if it were composed of malleable clay. The focus of this study is on the interactivity, intuitivity and versatility of such a system. To this end, a range of improvements is investigated which significantly enhances the efficiency and correctness of Directly Manipulated Free-Form Deformation, both separately and as a seamless component of the Virtual Sculpting system.
- Full Text:
- Date Issued: 1996
Initial findings of an investigation into the feasibility of a low level image processing workstation using transputers
- Authors: Cooke, Nicholas Duncan
- Date: 1990 , 2013-02-07
- Subjects: Image processing , Computer graphics , Fourier transformations -- Data processing , Transputers
- Language: English
- Type: Thesis , Masters , MSc
- Identifier: vital:4679 , http://hdl.handle.net/10962/d1006702 , Image processing , Computer graphics , Fourier transformations -- Data processing , Transputers
- Description: From Introduction: The research concentrates primarily on a feasibility study involving the setting up of an image processing workstation. As broad as this statement concerning the workstation may seem, there are several factors limiting the extent of the research. This project is not concerned with the design and implementation of a fully-fledged image processing workstation. Rather, it concerns an initial feasibility study of such a workstation, centered on the theme image processing aided by the parallel processing paradigm. In looking at the hardware available for the project, in the context of an image processing environment, a large amount of initial investigation was required prior to that concerned with the transputer and parallel processing. Work was done on the capturing and displaying of images. This formed a vital part of the project. Furthermore, considering that a new architecture was being used as the work horse within a conventional host architecture, the INTEL 80286, several aspects of the host architecture had also to be investigated. These included the actual processing capabilities of the host, the capturing and storing of the images on the host, and most importantly, the interface between the host and the transputer [C0089]. Benchmarking was important in order for good conclusions to be drawn about the viability of the two types of hardware used, both individually and together. On the subject of the transputer as the workhorse, there were several areas whlch required investigation. Initial work had to cover the choice of network topology on whlch the benchmarking of some of the image processing applications were performed. Research into this was based on the previous work of several authors, whlch introduced features relevant to this investigation. The network used for this investigation was chosen to be generally applicable to a broad spectrum of applications in image processing. It was not chosen for its applicability for a single dedicated application, as has been the case for much of the past research performed in image processing [SAN88] [SCH89]. The concept of image processing techniques being implemented on the transputer required careful consideration in respect of what should be implemented. Image processing is not a new subject, and it encompasses a large spectrum of applications. The transputer, with image processing being hlghly suited to it, has attracted a good deal of research. It would not be rash to say that the easy research was covered first. The more trivial operations in image processing, requiring matrix type operations on the pixels attracted, the most coverage. Several researchers in the field of image processing on the transputer have broken the back of this set of problems. Conclusions regarding these operations on the transputer returned a fairly standard answer. An area of image processing which has not produced the same volume of return as that concerning the more trivial operations, is the subject of Fourier Analysis, that is, the Fourier Transform. Thus a major part of this project concerns an investigation into the Fourier Transform in image processing, in particular the Fast Fourier Transform. The network chosen for thls research has placed some constraint upon the degree of parallelism that can be achleved. It should be emphasized that this project is not concerned with the most efficient implementation of a specific image processing algorithm on a dedicated topology. Rather, it looks at the feasibility of a general system in the domain of image processing, concerned with a hlghly computationally intensive operation. This has had the effect of testing the processing power of the hardware used, and contributing a widely applicable parallel algorithm for use in Fourier Analysis. 3 These are discussed more fully in Chapter 2, which covers the work related to tbis project. The results of the investigation are presented along with a discussion of the methods throughout the thesis. The final chapter summarizes the findings of the research, assesses the value of the investigation, and points out areas for future investigation.
- Full Text:
- Date Issued: 1990