Extensions to graph cut and lazy snapping segmentation algorithms

Image segmentation

Image segmentation is the process of delineating regions of interest on a given image. Generally, these regions are semantically meaningful and are of particular relevance to a given application. In medical applications, they often represent anatomical structures, tissues with specific properties or target organs. The outcome of segmentation is a labelled image in which pixels are classified into discrete categories, or, equivalently, a list of points located on the boundaries of the different regions of interest. Yet, image segmentation is not an end in itself and is often considered as a pre-processing step. In this case, further processing is applied to the extracted regions to obtain comprehensive information, such as computing the size of the segmented object (Maksimovic et al., 2000), analyzing pathological tissues (Comaniciu et al., 1999; Piqueras et al., 2015) or rendering 3D reconstructions of the organs (Cevidanes et al., 2005). In an image segmentation problem, it is common to assume that pixels from a single tissue/organ share similar physical properties, making them appear alike on the image. In computer vision, local image properties are called features and express information about the image data, such as pixel intensity, gradient magnitude or texture homogeneity.

Based on prior information about the expected segmentation results, a model can be used to describe the relationship between image features and a segmented label category, i.e., what makes a pixel more likely to belong to a given category (segmented region). However, for most applications, this is not sufficient. Therefore, regularization constraints are added to the model. For example, pixels from the same label category should satisfy a given homogeneity (smoothness) criterion or a particular shape constraint. Therefore, image segmentation can be related to defining and fitting a representative model which expresses application-specific requirements. Yet, this task is not trivial. Even with a good model, the context of the application may change, causing seg mentation failures. For example, in the case of automatic prostate segmentation, in which the context of the application is restrictively targeted, one of the best performance recorded on the MICCAI PROMISE12 challenge database (Litjens et al., 2014) yielded an accuracy score of 86.65%±4.35 (Yu et al., 2017). Although the approach achieved a remarkable score, critical applications, e.g., radiotherapy planning would require further expert verification and manual corrections. Image segmentation is naturally ill-posed and challenging (Peng et al., 2013). Many approaches have been investigated and proposed in the literature.

The goal of this chapter is not to do an exhaustive review of the literature of all existing approaches. Rather, we refer interested readers to the following surveys that address specific topics: using deformable models (McInerney & Terzopoulos, 1996), using unsupervised methods (Zhang et al., 2008), applied to ultrasound images (Noble & Boukerroui, 2006) or applied to color images (Luccheseyz & Mitray, 2001). For a given application, the choice of the segmentation approach depends on the nature of the task to achieve, the type of the images used, the properties of the structure to segment and other information characterizing the context of the application. In this thesis, we are interested in general purpose image segmentation tasks, i.e., when no prior information about the context of the application is known. In this case, instead of assuming any prior information, the context variability is managed by the user. Therefore, during the segmentation task, the user interactively guides the segmentation towards the desired results. These approaches are known as interactive image segmentation methods and require the use of an efficient communication mechanism between the user and the segmentation algorithm.

Segmentation as an interactive task The interactive segmentation task can be described as a three-block process (see Figure 1.1). The first block is the interactive block. It allows bilateral communication between the user and the computer through human-computer interaction (HCI) mechanisms; i.e., it defines the method and the devices used to feed parameters to the algorithm. The inputs/outputs are in a readable format for the user, e.g., numerical values or graphical contours. The second block is the computational block. It is in charge of finding the object boundary using a given algorithm. At this step, the inputs/outputs are translated into parameters readable by the algorithm. Once the segmentation results are obtained, they are displayed to the user in a readable format. This leads to the third block, the cognitive block, in which the user interprets the results. If they are not satisfactory, the user updates/modifies the inputs and the three blocks are reiterated, thereby creating a feedback loop between the user and the segmentation algorithm. Based on this, a straightforward interaction approach for image segmentation would be to consider a trial and error procedure. In this case, the user provides the input parameters at the beginning of the segmentation process and the results are obtained at the end of the computation. If the results are not satisfactory, the user adjusts the parameters and runs the segmentation again. Here, no intermediate results are recorded. The relationship between two successive iterations is solely based on the knowledge the user has gained from the previous trials.

Due to the minimal involvement of the user during the segmentation, this type of approach can be referred to as semi-automated. An example of such approaches is the active contour segmentation algorithm (Kass et al., 1988), in which the user specifies the positions of an initial contour that iteratively converges towards the object boundary. The user can be substituted using learning algorithms to exploit failures from previous trials, e.g., in deep convolutional neural network segmentation (Long et al., 2015). In this thesis, interactive segmentation methods refer to approaches where the intermediate results are displayed. For example, segmentation approaches that can be found in the ITKSNAP1 software. These require more involvement on part of the user. Here, the results of the previous iteration, e.g., the last position of the contour obtained, are injected into the next iteration with additional information provided by the user. To be efficient, this type of approach requires a more sophisticated interaction mechanism than semi-automated and automated approaches. Olabarriaga & Smeulders (2001) described three types of interaction mechanisms that can be used in segmentation tasks:

Region-based mechanism

In region-based approaches, the segmentation problem is defined as “finding pixels that belong to a particular object”. A typical example of region-based segmentation is the region growing algorithm (Adams & Bischof, 1994). Starting from a region located inside the object, often manually selected, the approach iteratively appends pixels adjacent to the region that share similar properties (e.g., pixel intensity). The process stops when two successive iterations yield the exact same region, meaning that no additional pixels were added to the region. This algorithm is based on the regional property of the object instead of its contour, which makes it more sensitive to heterogeneous tissues, for example. In the last two decades, scribble-based interaction mechanisms for region-based image segmentation have been widely used (Boykov & Jolly, 2001; Grady, 2006; Protiere & Sapiro, 2007; Falcao et al., 2004). Using the mouse to draw on the image, the interaction mechanism consists in labeling a few pixels from each object and a few pixels from the background of the image, with their respective label categories. For a binary segmentation, the two label categories represent foreground and background.

Based on the content of the image, the algorithm computes the most plausible separation between objects and background, according to these labels. This is similar to a region growing approach in which multiple regions grow at the same time. The assumption is that the speed of the growth is faster between pixels with similar properties, for example when pixels have similar intensities, i.e., with low gradient. Compared to contour-based approaches, region-based approaches offer the user more freedom. In a typical case, the region occupied by the object is sufficiently large to allow a variety of valid labelling possibilities. Depending on the shape, the position and the order in which the labels were drawn, the response of the segmentation algorithm varies. While the actions of the user consist in following the object boundary during a contour-based segmentation task, there exist a much greater diversity of scenarios in which labels can be drawn during a region-based segmentation task, all leading to similar results. Some of these are more efficient than others, which motivates this thesis to focus on region-based approaches in general, and scribble-based approaches in particular.

Table des matières

INTRODUCTION
CHAPTER 1 BACKGROUND
1.1 Image segmentation
1.2 Segmentation as an interactive task
1.3 Interactive mechanisms for image segmentation
1.3.1 Contour-based mechanism
1.3.2 Region-based mechanism
1.3.3 Hybrid mechanism
1.3.4 Sketching assistance
1.4 Graph-based segmentation
1.4.1 Building the graph
1.4.2 Segmentation strategy
1.5 Computational properties of graph-based segmentation
1.5.1 Graph cut segmentation
1.5.2 Lazy Snapping segmentation
1.5.3 Random walker segmentation
1.6 Graph reduction
1.6.1 Grid resampling
1.6.2 Arbitrary-shaped resampling
CHAPTER 2 RAPID INTERACTIVE SEGMENTATION USING A ROUGH CONTOUR DRAWING
2.1 Introduction
2.2 Related work
2.3 Proposed graph-reduction method
2.3.1 Layer construction
2.3.2 Segmentation
2.4 Interaction constraints and segmentation behavior
2.4.1 User interaction constraint
2.4.2 Sensitivity of the contour drawing
2.5 User study
2.5.1 Study design
2.5.2 Implementation
2.5.3 Results
2.5.3.1 Interaction
2.5.3.2 Computation time
2.6 Extension to other segmentation algorithms
2.6.1 Combination with super-pixels
2.6.2 Extensions to graph cut and lazy snapping segmentation algorithms
2.6.3 Adaptive multi-scale super-pixels
2.7 Conclusion
CHAPTER 3 TOWARDS REAL-TIME VISUAL FEEDBACK FOR INTERACTIVE IMAGE SEGMENTATION
3.1 Introduction
3.2 What is real-time segmentation feedback ?
3.3 FastDRaW segmentation
3.3.1 Extracting the region of interest
3.3.2 Properties of the ROI
3.3.3 Segmentation refinement
3.4 Results
3.4.1 Implementation details
3.4.2 Choice of down-sampling factor
3.4.3 User study
3.5 Conclusion
CHAPTER 4 THE EFFECT OF LATENCY IN VISUAL FEEDBACK ON USER PERFORMANCE
4.1 Introduction
4.2 Background
4.2.1 Latency in interactive applications
4.2.2 Interactive segmentation assessment
4.3 Experiment
4.3.1 Preparing the image dataset
4.3.2 Study design
4.3.3 Experiment progress
4.3.3.1 Training step
4.3.3.2 Evaluation step
4.3.4 Interaction mechanism
4.3.5 Segmentation method and computations
4.4 Measures
4.4.1 Overall time – tΩ
4.4.2 Labelling time – tΛ
4.4.3 Drawing speed – υ
4.4.4 Accuracy – A
4.4.5 Continuity of the strokes – ζ
4.4.6 Number of labels – N
4.5 Results
4.5.1 Overall time
4.5.2 Labelling time and drawing speed
4.5.3 Segmentation accuracy
4.5.4 Continuity of the strokes
4.5.5 Number of labels
4.6 Discussion
4.6.1 User performance
4.6.1.1 Automatic vs. user-initiated refresh method
4.6.1.2 Relationship between latency and drawing efficiency
4.6.1.3 Participant feedback
4.6.2 Segmentation performance
4.6.2.1 Relationship between latency and segmentation time
4.6.2.2 Segmentation accuracy
4.7 Conclusions
CONCLUSION AND RECOMMENDATIONS
APPENDIX I COMPUTATIONAL COMPLEXITY
APPENDIX II RANDOM PATH GENERATION
APPENDIX III IMAGES USED FOR THE USER EXPERIMENT
BIBLIOGRAPHY

Télécharger le rapport complet