A Graph Cut Framework for 2D/3D Implicit Front Propagation with Application to the Image Segmentation Problem

A Graph Cut Framework for 2D/3D Implicit Front Propagation with Application to the Image Segmentation Problem
Author: Noha Youssry El-Zehiry
Publisher:
Total Pages: 288
Release: 2009
Genre: Computer vision
ISBN:

Image segmentation is one of the most critical tasks in the fields of image processing and computer vision. It is a preliminary step to several image processing schemes and its robustness and accuracy immediately impact the rest of the scheme. Applicability of image segmentation algorithms varies broadly from tracking in computer games to tumor monitoring and tissue classification in clinics. Over the last couple of decades, formulating the image segmentation as a curve evolution problem has been the state-of-the-art. Research groups have been competing in presenting efficient formulation, robust optimization and fast numerical implementation to solve the curve evolution problem. From another perspective, graph cuts have been gaining popularity over the last decade and its applicability in image processing and computer vision fields is vastly increasing. Recent studies are in favor of combining the benefits of variational formulations of deformable models and the graph cuts optimization tools. In this dissertation, we present a graph cut based framework for front propagation with application to 2D/3D image segmentation. As a starting point, we will introduce a Graph Cut Based Active Contour (GCBAC) model that serves as a unified framework that combines the advantages of both level sets and graph cuts. Mainly, a discrete formulation of the active contour without edges model introduced by Chan and Vese will be presented. We will prove that the discrete formulation of the energy function is graph representable and can be minimized using the min-cut/max-flow algorithm. The major advantages of our model over that of Chan and Vese are: (1) A global minimum will be obtained because graph cuts are used in the optimization step and hence, our segmentation approach is not sensitive to initialization. (2) The polynomial time complexity of the min-cut/max-flow algorithm makes our algorithm much faster than the level sets approaches. Meanwhile, all the advantages associated with the level sets formulation such as robustness to noise, topology changes and ill-defined edges are preserved. The basic formulation will be presented for 2D scalar images. The GCBAC will be the core of this dissertation upon which extensions will be presented to establish the scalability of the model. Extensions of the model to segment vector valued images such as RGB images and volumetric data such as brain MRI scans will be provided. The dissertation will also present a multiphase image segmentation approach based on GCBAC. Further challenges such as intensities inhomogeneities and shared intensity distributions among different objects will be discussed and resolved in the course of this dissertation. The dissertation will include pictorial results, as well as, quantitative assessments that illustrate the performance of the proposed models.

Implicit Curve/surface Evolution with Application to the Image Segmentation Problem

Implicit Curve/surface Evolution with Application to the Image Segmentation Problem
Author: Hossam El Din Hassan Abd El Munim
Publisher:
Total Pages: 198
Release: 2007
Genre:
ISBN: 9780549051350

The theory in this dissertation will be extended beyond the applications domain to other theoretical and algorithmic developments. In particular, graph cuts will be investigated as an optimization technique to handle the energy minimization problems. Other applications of the theory will be investigated in areas such as video tracking and surveillance.

Point Process and Graph Cut Applied to 2D and 3D Object Extraction

Point Process and Graph Cut Applied to 2D and 3D Object Extraction
Author: Ahmed Gamal Eldin
Publisher:
Total Pages: 166
Release: 2011
Genre:
ISBN:

The topic of this thesis is to develop a novel approach for 3D object detection from a 2D image. This approach takes into consideration the occlusions and the perspective effects. This work has been embedded in a marked point process framework, proved to be efficient for solving many challenging problems dealing with high resolution images. The accomplished work during the thesis can be presented in two parts : In the first part, we propose a novel probabilistic approach to handle occlusions and perspective effects. The proposed method is based on 3D scene simulation on the GPU using OpenGL. It is an object based method embedded in a marked point process framework. We apply it for the size estimation of a penguin colony, where we model a penguin colony as an unknown number of 3D objects. The main idea of the proposed approach is to sample some candidate configurations consisting of 3D objects lying on the real plane. A Gibbs energy is define on the configuration space, which takes into account both prior and data information. The proposed configurations are projected onto the image plane, and the configurations are modified until convergence. To evaluate a proposed configuration, we measure the similarity between the projected image of the proposed configuration and the real image, by defining a data term and a prior term which penalize objects overlapping. We introduced modifications to the optimization algorithm to take into account new dependencies that exists in our 3D model. In the second part, we propose a new optimization method which we call "Multiple Births and Cut" (MBC). It combines the recently developed optimization algorithm Multiple Births and Deaths (MBD) and the Graph-Cut. MBD and MBC optimization methods are applied for the optimization of a marked point process. We compared the MBC to the MBD algorithms showing that the main advantage of our newly proposed algorithm is the reduction of the number of parameters, the speed of convergence and the quality of the obtained results. We validated our algorithm on the counting problem of flamingos in a colony.

Structural Priors for Multiobject Semi-automatic Segmentation of Three-dimensional Medical Images Via Clustering and Graph Cut Algorithms

Structural Priors for Multiobject Semi-automatic Segmentation of Three-dimensional Medical Images Via Clustering and Graph Cut Algorithms
Author: Razmig Kéchichian
Publisher:
Total Pages: 117
Release: 2020
Genre:
ISBN:

We develop a generic Graph Cut-based semiautomatic multiobject image segmentation method principally for use in routine medical applications ranging from tasks involving few objects in 2D images to fairly complex near whole-body 3D image segmentation. The flexible formulation of the method allows its straightforward adaption to a given application.\linebreak In particular, the graph-based vicinity prior model we propose, defined as shortest-path pairwise constraints on the object adjacency graph, can be easily reformulated to account for the spatial relationships between objects in a given problem instance. The segmentation algorithm can be tailored to the runtime requirements of the application and the online storage capacities of the computing platform by an efficient and controllable Voronoi tessellation clustering of the input image which achieves a good balance between cluster compactness and boundary adherence criteria. Qualitative and quantitative comprehensive evaluation and comparison with the standard Potts model confirm that the vicinity prior model brings significant improvements in the correct segmentation of distinct objects of identical intensity, the accurate placement of object boundaries and the robustness of segmentation with respect to clustering resolution. Comparative evaluation of the clustering method with competing ones confirms its benefits in terms of runtime and quality of produced partitions. Importantly, compared to voxel segmentation, the clustering step improves both overall runtime and memory footprint of the segmentation process up to an order of magnitude virtually without compromising the segmentation quality.

Image Segmentation for Stylized Non-photorealistic Rendering and Animation [microform]

Image Segmentation for Stylized Non-photorealistic Rendering and Animation [microform]
Author: Alexander Kolliopoulos
Publisher: Library and Archives Canada = Bibliothèque et Archives Canada
Total Pages: 216
Release: 2005
Genre:
ISBN: 9780494021699

This thesis approaches the problem of non-photorealistic rendering by identifying segments in the image plane and filling them using algorithms to render in artistic styles. Using segments as a 2D primitive for non-photorealistic styles is a natural extension of techniques artists often implicitly employ for purposes such as abstraction of unnecessary detail. The problem of segmenting an arbitrary 3D scene in a 2D view using geometric scene information is presented, and a solution based on spectral clustering is proposed. With an acceleration technique, segmentation can be performed in near real-time for interactive, artistic environments. This approach is automatic beyond the setting of segmentation parameters by a user, and it can be extended to temporally coherent non-photorealistic animation by segmenting adjacent frames together. A number of artistic rendering styles are applied within this segmentation framework to demonstrate the effects that such a system makes possible.

Geometric Image Segmentation Via Transform Invariant Rank Cuts

Geometric Image Segmentation Via Transform Invariant Rank Cuts
Author: Hussein Abdulhussein
Publisher:
Total Pages: 33
Release: 2012
Genre: Electronic Dissertations
ISBN:

This research propose a novel image segmentation algorithm, named as Transform Invariant Rank Cuts (TIRC). Based on salient 3D geometric information of natural scenes. The segmentation algorithm unities an emerging robust statistics technique called Robust PCA and its recent application in Transform Invariant Low-Rank Texture (TILT) extraction. This proposed novel algorithms address two critical issues that have handicapped the applications of the TILT feature. First, we propose a simple yet e cient algorithm to detect low-rank texture regions in natural images. Second, TIRC is a principled graph-cut solution to partition the TILT features into groups; each group represents a unique 3D planar structure. Using a TILT adjacency graph, the algorithm assigns a TILT feature as a node. Two nodes are connected if they are spatially adjacent, with the cut cost function defined as the total coding length of encoding the two texture regions as low-rank matrices separately. Finally, the classical graph-cut algorithm can be applied to partition the graph into sub-graphs, each of which represents a unique surface texture and 3D orientation. The efficacy and visual quality of this geometric image segmentation algorithm is demonstrated on a large urban scene database.

Power-law Graph Cuts

Power-law Graph Cuts
Author: Jiaxin Zhang
Publisher:
Total Pages: 35
Release: 2015
Genre:
ISBN:

In recent years, spectral graph cut algorithms such as normalized cuts, ratio cuts and ratio association have become more widely used. One reason is that they can be applied to a large range of tasks and easily implemented via standard eigenvector computations. Despite their good performance on a number of clustering problems, spectral graph cut algorithms still have some limitations: first, the number of clusters is required to be known in advance, however, this information is usually an unknown prior; second, algorithms based on graph cut objectives tend to produces cluster with uniform sizes. But in some cases, the true clusters exhibit a known size distribution; for example, in image segmentation, human-segmented images tend to yield segment sizes that follow a power-law distribution. In this paper, a general framework of power-law graph cut algorithm is proposed. The power-law graph cut algorithm does not fix the number of clusters upfront, and produces clusters whose sizes are power-law distributed. In order to achieve these goals, a Pitman-Yor exchangeable partition probability function (EPPF) is added to the graph cut objectives as a regularizer. Because relaxing via eigenvectors cannot solve the regularized objectives, a simple iterative algorithm is derived to locally optimize the objectives. Furthermore, we show that the proposed algorithm can be viewed as performing MAP inference on a particular Pitman-Yor mixture model. Finally, a set of experiments are conducted on various datasets to demonstrate the effectiveness of the power-law graph cut algorithm.

Handbook of Mathematical Methods in Imaging

Handbook of Mathematical Methods in Imaging
Author: Otmar Scherzer
Publisher: Springer Science & Business Media
Total Pages: 1626
Release: 2010-11-23
Genre: Mathematics
ISBN: 0387929193

The Handbook of Mathematical Methods in Imaging provides a comprehensive treatment of the mathematical techniques used in imaging science. The material is grouped into two central themes, namely, Inverse Problems (Algorithmic Reconstruction) and Signal and Image Processing. Each section within the themes covers applications (modeling), mathematics, numerical methods (using a case example) and open questions. Written by experts in the area, the presentation is mathematically rigorous. The entries are cross-referenced for easy navigation through connected topics. Available in both print and electronic forms, the handbook is enhanced by more than 150 illustrations and an extended bibliography. It will benefit students, scientists and researchers in applied mathematics. Engineers and computer scientists working in imaging will also find this handbook useful.