Level set based Image Segmentation Hang Xiao Jan12, 2013 Outline • Part1 : Level set method • Part2 : Image segmentation Part1 : Level set method In mathematics, a level set of a real-valued function f of n variables is a set of the form STANLEY OSHER 1988 Front propagating problems Ocean waves Image contour Burning flames Interface Propagation F = F(L, G, I) Inside Outside Outside F(L,G,I) : speed function L : local properties, e.g. curvature and normal direction G: Global properties, e.g. heat I: Independent properties, independ of the shape of the front, e.g. underlying fluid velocity Arrival time function Assume F > 0, hence the front moves “outward” T(x,y) : the arrival time, characterize the position of the expanding front Distance = speed * time 1D : 2D: : the initial location of the interface Time-depend level set function The stationary level set function F is constant to t Time-depend level set function F is inconstant to t Level set function properties Front formula: F By the chain rule, Inside Outside Hamilton-Jacobi equation Outside Level set method work flow Initialize level set function Φt=0 Compute speed F t++ Compute level set function in next state Φt+1 Reinitialize level set function Compute final zero level set Arrival time e.g. Example – simple curve evolution Simple curve Complex curves Level set Curvature Speed Property: Any simple curve will become a ball in the force of curvature Example – simple curve evolution Example – 3D surface 3D curvature Gaussian curvature Mean curvature Mean curvature Gaussian curvature Other examples The particle level set method was used to represent the interface separating water from air as water is being poured into a glass Level set method is used to simulate a ball catching on fire Part2 : Image segmentation Image segmentation models • Explicit method • Implicit method Inside Outside Interface front Evolution equation Energy minimization Outside The Chan-Vese Segmentation Model Assume the image is piecewise constant Energy : Sum of difference Add more regularizing terms The Chan-Vese Segmentation Model Energy function Energy Minimization Substituting into the Euler-Lagrange equation, and applying Green’s identity and Green’s theorem Effect of Parameters • μ controls the importance of the length of C in the minimization. – if μ ≫ 1, then a few large closed curves will retain in the steady state, compared to many small ones. This may be useful in ignoring noise, or grouping objects of similar characteristics • ν controls the the importance of area inside C. – If ν ≫ 1, like the geometric active contour model, it forces C to move strictly inward. Also, the speed at which C evolves inward increases. • The relative balance between λ1 and λ2 determines which side, inside or outside, has higher importance in minimizing the regional variance. – This is useful in segmenting blurred images: for example, if one wishes to completely enclose the blurred object, λ2 > λ1 will ensure this. Chan-Vese Examples Parameters: μ=1, ν=0, λ1 = λ2 =1, iterations = 41 Chan-Vese Examples Change in topology Parameters: μ=1, ν=0, λ1 = 1, λ2 =2, iterations = 45 Chan-Vese Examples Blurred and Noised Image Parameters: μ=1, ν=0, λ1 = 1, λ2 =2, iterations = 45 Chan-Vese Examples Chromatic Resemblance Parameters: μ=10^8, ν=0, λ1 = λ2 = 1, iterations = 40 Chan-Vese Examples Restriction on Curve Evolution Direction Parameters: μ=1, ν=0, λ1 = λ2 = 1, iterations = 40 Chan-Vese Examples Restriction on Curve Evolution Direction Parameters: μ=1, ν=10^6, λ1 = λ2 = 1, iterations = 40 Detection of lines and curves not necessarily closed Example of image for which the averages “inside” and “outside” are the same Detection of a simulated minefield, with contour without gradient. Time steps (dt) evalution E1: false negative error E2: false positive error Conclusion: The image can be segmented well in one iteration for timesteps greater than about 0.001. Overlap error after one iteration for small or large dt Iteration number evalution Overlap error vs. number of iterations for a small timestep Overlap error vs. number of iterations for a large timestep Conclusion: 1). When the timestep is small the segmentation converges. 2). However, if we take the timestep too large, the results diverge after a few iterations even though the segmentation is initially good. Top: The noisy image Bottom : the thresholding segmentation result max(E1, E2) = 0.5625, min(E1, E2) = 0.1222 Evaluation on noisy image: 1) Use the true segmentation from the noiseless image (ground truth) for forming the overlap error 2) Perform five iterations of the algorithm for each fixed value of c1, c2 3) Vary one parameter at a time and plot the overlap errors against that parameter. Overlap errors vs. length penalty μ. The best segmentation is obtained for μ ∼ 94. Overlap error vs. λ1. Changing λ1 from 1 does not improve the segmentation, since our foreground and background regions both have uniform intensity before noise is added. The results for varying λ2 are similar. Chan-Vese VS. Mumford-Shah Chan-Vese function 2001 Mumford-Shah function 1992 MS model CV model The Chan-Vese Segmentation Model The Chan-Vese Segmentation Model Energy function Energy Minimization Substituting into the Euler-Lagrange equation, and applying Green’s identity and Green’s theorem How to add area constant constraint? Generalizing to Vector-Valued Images Texture Segmentation 1. Generate sparse texture features by nonlinear diffusion filtering Brox, Weickert ’04, ’06 Texture Segmentation 2. Vector-Image based level set methods Brox, Weickert ’04, ’06 Texture Segmentation efficient coarse-to-fine scheme Brox, Weickert ’04, ’06 Coupling Multiple Active Surfaces (Dufour 2004) Needs N level set functions for N objects segmentation Multi-Phase Level Set methods Need log2N Level set functions for segmenting N objects Multi-Phase Level Set methods Results on a synthetic image, with a triple junction, using the 4-phase piecewise constant model with 2 level set functions. We also show the zero level sets of φ1 and φ2 Multi-Phase Level Set methods Brox, Weickert ’04, ’06 One Level Set without Coupling Based Multiple object segmentation Pros. And Cons. For level set method • Advantage – – – – – – – – – – – Capture Range Effect of Local Noise No Need of Elasticity Coefficients Suitability for Medical Image Segmentation Normal Computation Integration of Regional Statistics Flexible Topology Extension to high dimension Incorporation of Regularizing Terms e.g. volume Handling Corners Resolution Changes Jasjit S. et. al. 2002 Pros. And Cons. For level set method • Disadvantage – Initial Placement of the Contour – Hard to stop – Expensive running time Jasjit S. et. al. 2002 Thanks!!!