The Raymond and Beverly Sackler

Tel-AvivUniversity

The Raymond and Beverly Sackler

Faculty of Exact Sciences

School of Computer Sciences

Image Segmentation using 1D Matching:

a Combined Segmentation and Editing Tool

By

Alon Shmueli

Prepared under the supervision of

Prof. Daniel Cohen-Or

Dr. Hayit Greenspan

Submitted in partial fulfillment of the requirements
for the degree of M.Sc. in Tel-AvivUniversity

May 2007

Acknowledgments

I want to thank Eyal Zadicario for accompanying me the whole way, for giving me the initial idea on the way of interaction, and for many more good ideas along the way.

I also want to thank my dear wife, Nitza Shmueli, for giving me all the support I needed throughout the way.

Contents

Abstract......

1.Introduction

1.1.The Segmentation Problems

1.2.Image segmentation Categories

1.3.Contour-Based Interactive Segmentation

1.4.Medical Image Segmentation

2.Active Contours and Level Set Methods

2.1.Active Contour Models ("Snakes")

2.2.Level Set

2.3.The Narrow Band Approach

2.4.The Fast Marching Approach

2.5.Geodesic Active Contours

2.6.Active Regions and Level Sets

3.Live Wire Methods

3.1.Live Wire (Intelligent Scissors)

3.2.Live Wire and Live Lane

3.3.Phase-Based Live-Wire

4.Graph Cut Methods

4.1.Graph Cut

4.2.Grab Cut

4.3.Lazy Snapping

5.Interactive Segmentation by 1D Ray Matching

5.1.Proposed User Interface

5.2.Image Segmentation using 1D Rays – Previous Work

5.3.Algorithm Outline

5.4.1D Ray Matching

5.5.Regularization Term

5.6.Multi Scaling

5.7.Interaction and Editing Details

5.8.Results

6.Conclusions

7.Reference

Listof Figures

Figure 1: Snake detecting Subjective Contours Illusion

Figure 2: Embedding the curve in a higher dimension

Figure 3: The scalar functionin the image plane.

Figure 4: Updating the function only in a narrow band

Figure 5: Constructing the Fast Marching surface T

Figure 6: A piecewise constant "Cartoon" image

Figure 7: Live Wire behavior

Figure 8: The effect of "On the Fly Training"

Figure 9: Global Phase vs. Local Phase

Figure 10: Detecting edges using Local Phase in a single dimensional signal..

Figure 11: Brush-strokes interaction in Graph Cut segmentation

Figure 12: The segmentation problem as a Graph Cut problem

Figure 13: Defining the Graph Cut edge weights.

Figure 14: Interaction using GrabCut

Figure 15: Border segmentation in Lazy Snapping

Figure 16: Ray Segmentation user interaction

Figure 17: Neighbors regulatory term.

Figure 18: Editing the polygon

Figure 19: The Multi-Scale benefit

Figure 20: Segmenting thin structures

Figure 21: Segmentation of an object with blurred edge.

Figure 22: Comparison to other methods

Figure 23: Segmentationwith margin

Figure 24: Segmenting a multi-parts object

Figure 25: Overcoming disturbing edges

Figure 26: Overcoming occlusions.

Abstract

Interactive image segmentation has become more and more popular among researched in recent years. Interactive segmentation, as opposed to fully automatic one, supply the user with means to incorporate his knowledge into the segmentation process. However, in most of the existing techniques, the suggested user interaction is not good enough since the user cannot intuitively force his knowledge into the tool or edit results easily. Therefore, in ambiguous situation, the user has to revert to tedious manual drawing.

I present here a novel method developed as a combined segmentation and editing tool. It incorporates a simple user interface and a fast and reliable segmentation based on 1D segment matching. The user is required to click just a few "control points" on the desired object border, and let the algorithm complete the rest. The user can then edit the result by adding, removing and moving control points, where each interaction is follows by an automatic, real-time segmentation by the algorithm.

Before introducing my work I present a very extensive survey on "Contour Based Interactive Image Segmentation" techniques. It includes a detailed review of Active Contours methods ("Snakes", Level Sets, Fast Marching Methods, Geodesic Active Contours etc.), Live Wire methods (Live Wire, Phased Wire etc.) and Graph Cut methods (Graph Cut, Grab Cut and Lazy Snapping).

In the second part of the work I describe my "Ray Segmentation" method: The user initialize the process with set of "control points" one the objects border. The system then connects them to an initial polygon and iterates on it until convergence. In each iteration, each contour point tries to move to the best next location along the polygon's normal. Best location is achieved by comparing a 1D neighborhood in the normal direction, between the candidate point and two neighboring control points along the polygon. The comparison process is implemented as simple correlation between two 1D profiles (also called "segments" or "rays").

For better convergence a regulatory term is introduced. This term is designed to prevent a point from moving too far from the previous iteration's local contour. The few adjacent contour points are projected onto the current point’s normal and their average is calculated (to produce a 1D shift along the normal). Any new candidate location for the current point is panelized for diverting away from this neighbors' recommended location (shift). Averaging on the recommended location is weighted, where neighbors with higher "confidence level" contribute more to the average.

The algorithm operates as a real-time tool, responding immediately to user actions on any average modern computer. Convergence is reached in a low number of iterations, even when initialized from a remote initial solution, due to an adaptive, multi-scale approach. The highest scale level in use takes into account the size of object to segment, allowing the algorithm to reach the right contour, for objects of any size, even if initialized far from it.

The algorithm is benchmarked on both medical as well as on realistic (photographic) images and shows its added values versus other image segmentation tools. We compare results with the Fast Marching (Level Sets) method as well as the Live Wire method, showing the extra versatility and the ability to segment objects in highly complex situations.

1.Introduction

1.1.The Segmentation Problems

Image segmentation is the problem of extracting (segmenting, cutting-out) foreground objects from background in an image. It is one of the most fundamental problems in computer vision and has interested many researches throughout the years. As the use in computers increase through the years, reliable image segmentation is needed in more and more application, in the industrial, medical and personal fields. Fully automatic segmentation is still an open problem due wide variety of possible objects'combination, and so it seems that the use of human "hints" isinevitable.Interactive image segmentation has therefore become more and more popular among researched in recent years. The goal of interactive segmentation is to extract object(s) from background (or just split the image into continues classes) in an accurate way, using user knowledge in a way that requires minimal interaction and minimal response time. This paper will starts by describing general ways to categorize segmentation techniques, continues with an extensive survey of current contour-based interactive image segmentationtechniques, and ends by introducing a new combined editing and segmentation tool.

1.2.Image segmentation Categories

Extensive work has been done in the field of image segmentation. Traversing the huge amount of existing techniques,it could be helpful if we could categorize them into groups. When coming to do so one immediately understands it's a multi-dimensional task. That is, there are multiple ways to categorize a segmentation method.I present here a list of possible categorization parameters. This doesn't include validation (e.g: accuracy, efficiency), only the a-priori "type of segmentation". For a more extensive talk about Medical Image Segmentation techniques see [38, 41]. For an extensive survey on man-machine user interaction in segmentation see[17].

1. Automatic vs. Interactive - Automatic segmentation takes no user input while Interactive (or semi-automatic) segmentation uses user "hints" for initialization or guidance. Examples for fully-automatic methods are the watershed algorithm [51], Marching Cubes [26], normalized cuts [43], Split and merge (see chapter 10 in [20]) etc. Interaction methods vary from "initialize and let go" (Level Sets [1,27,39,44-47], Region Growing methods (chapter 10 in [20])), through specifying "constrains" (Snakes [23], Graph Cuts [4,5,42]), to "full-guidance" through-out the process (Live Wire [15-16,30-35,37-38,50]).
2. Region vs. Contour Detection– The segmentation algorithm can either try to "label" each pixel to be foreground or background (Graph Cuts methods, Region Growing methods like Adobe Magic Wand [2], Thresholding methods etc) or look for the separating contour that defines the objects (Snakes, Level Sets, Live Wire). The most advanced methods today combine both attitudes (Geodesic Active Regions [40], Lazy Snapping [25]) and therefore generally give the best results.
3. Usage of Knowledge – Some methods are knowledge based, i.e. they try to match the object to one of a pre-defined set of images (using Classification [14]), or try to deform a known template to the object at hand (Deformable Templates [58]). Other method assume some prior assumptions and build a model that the object must comply with,like having a smooth curvature (Snakes & Level Sets) orasmooth local statistics (Markov Random Fields). Finally there are methods who assume nothing on the object (Live Wire, Thresholding, use of Morphological Operators)
4. Use of Training (related to "Knowledge Based methods")– Some knowledge based methods require pre-training stage before starting the segmentation (Clustering (supervised learning) methods, e.g: k-nearest-neighbors). Other methods only assume a model and "teach" themselves on the fly building some knowledge base from one image to another (Classification (unsupervised learning) methods, e.g: K-Means). See [14] for more an extensive discussion on these issues.
   In another,very popular, type of "training", information prorogates throughout the segmentation of a single image from segmented parts to none segmented parts. Segmented pixels build some knowledge-base on the object or borderline which serve when examining non-segmented pixels (Live Wire, Markov Random Fields methods, some Neural Networks).
5. Use of Hard Constraints– Some algorithms require themselves to make sure a certain piece of knowledge will be reflected in the final segmentation. This is called Hard Constraints or Seed Points (Graph Cut, Region Growing). Other impose some general model which is sometime called Soft Constraints
6. Intensity / Color / Texture – The basic information to segment can be either the intensity (mostly in grey-level images) or the color (in color images). It is also common to attach a "feature vector" to each pixel or its small environment and to segment them. The last attitude usually proves better when coming to segment a highly textured image.
   It is very common for a new segmentation algorithmto emerge as a gray-level segmentation and later develop to handle color and textured images. An example from the Graph Cut world is the evolution from the original gray-scale Graph Cut [5] to color methods like GrabCut [42] and LazySnapping [25] and to textured-base Graph Cuts like[29]. Another example from the Level Sets world is the evolution from Level Sets [27] and Geodesic Active Contours (GAC) [9] to texture-based variants like [22].
7. Medical / Realistic Images – Those are the two most common types of images that segmentation algorithm try to benchmark on. The two types are relatively different and therefore many of the algorithms tune themselves to only one of the types see further discussion on characteristics on Medical Images in section 1.4.
8. Segmentation with Transparency – Some systems, especially the once dealing with realistic images, extend segmentation to "image-cutout", that is, the ability to cut the segmented object out and put it onto another background in a realistic way. This involves giving some of the pixels (especially the ones close to the border) a mixed labeling of "foreground" and "background" rather then a binary one. This issue is usually called "Border Mating".For examples see Lazy Snapping [25] and GrabCut [42].
9. Local / Global Solution – Manysegmentation methodstry to prove that the final obtained segmentation is some minimization of a pre-defined functional. The difference is whether this minimum is a local one (Snakes & Level Sets) or a global one (Graph Cuts) and therefore is less dependant on initialization.
10. Dimensionality – Some methods are naturally extendable from the 2D case to upper dimensions, or even originally formulated in N-D (Graph Cut, Level Sets). For others the native world is 2D, where extensions to 3D usually involve applying the same method to each slice.

1.3.Contour-Based Interactive Segmentation

Out of all the all possible combinations above I've chosen to focus in this thesis on Contour-Based Interactive Image Segmentation techniques. Therefore the outline of the rest of the work will be as follows:

Chapter 2 will cover methods called Active Contour Models, that is,Snakes and Level Sets. Those methods start with a contour drawn by the user and iteratively deform it to get the final, best describing object(s) contour.The methods iteratively minimize a pre-defined energy functional which is usually a balance of two forces: externalforces, that attract the contour to its place and internal forces that keep the contour smooth. Minimizing the functional is achieved using variational calculus methods, in which the equivalent partial differential equations (PDE) is found (usually using Euler-Lagrange equation) and then numerically solved (using finite differences).

Chapter 3 will cover the Live Wire methods. These methods let the user control("steer") something like an evolving "wire" that gradually wraps the object throughout the segmentation process. The "wire"snaps to the desired border-line and eventually generates the desired closed contour. Live Wire methods are based on Dynamic Programming to find the shortest path (in a weighted graph induced by the image) of the "wire" from the current mouse point to the border.

Chapter 4 will describe the Graph Cut based algorithms. In this method the image is converted into a graph, in which pixels are nodes and connection are edges. The segmentation problem is reduced to finding the minimal cut in the graph, which will split the foreground pixels from the background ones. This is achieved by an optimal min-cut/max-flow algorithm that finds the globally optimal solution. In fact, Graph Cut is a region-based segmentation but I will introduce some variant which incorporate contour knowledge too.

Chapter 5 describes my combined segmentation and editing algorithm, described briefly in the "Abstract". It first details previous work done in using 1D profiles to infer 2D segmentation. It then describes the new proposed user interaction scheme and the algorithm in details. Finally, it shows results of applying the algorithm to medical and realistic images and compares results with other methods.

1.4.Medical Image Segmentation

The use of digital images in medicine has become very popular these days. All diagnostic imaging devices are computerized and can manipulate digital data. This includes Magnetic Resonance Imaging (MRI), Computed Tomography (CT), Ultrasound imaging and more. All those devices can manipulate images, perform measurements and export it in a digital way. A natural need for image segmentation comes from various analyses and measurements that can be done, for example,to detect pathologies.

A more extensive use of image segmentation comes from medical therapy devices.Procedures such asminimal invasive surgeries (e.g: guided surgeries)and non invasive surgeries (e.g: X-Ray radiation, Focused Ultrasound etc.)become more and more popular and require detailed computerized feedback to compensate for the lack of direct visual contact by the surgeon. In many such systems the user has to segment some object(s) in order to prepare the treatment plan as well as to avoid hurting other sensitive objects. A good interactive segmentation tool can save a lot of time, replacing manual drawing by the surgeon.

Medical images tend to suffer much more noise than realistic images to due the nature of the acquisition devices. This of course poses great challenges to any image segmentation technique. In order to reduce noise many devises increase the (already existing) partial voluming, that is, they average acquisition on a thick slice. This (among other reasons) leads to blurring the edges between the objects, which make decisions very hard for automatic tools.

The different acquisition modalities, the different image manipulations and variability of organs all contribute to a large verity of medical images. It can be safely said that there is no single image segmentation method that suit all possible images. Furthermore, the expert user can decide to draw part of an object, a cluster of object or an object with margin, and may request that the segmentation border pass where there is no or edges. This can pose great problems for any segmentation method. It is clear that the need for combined editing-segmentation tool is needed where the expert can give the computer some hints/marks as to where he/she want the contour to pass and let the computer complete the non-marked parts. This is the exact motivation for the interactive segmentation method presented here.