1Bioimage InformaticsLecture 13, Spring 2012Bioimage Data Analysis (IV)Image Segmentation (part 2)Lecture 13 February 29, 20122Outline• Review: Steger’s line/curve detection algorithm• Intensity thresholding based image segmentation• A brief introduction to ITK• Image segmentation performance evaluation3• Review: Steger’s line/curve detection algorithm• Intensity thresholding based image segmentation• A brief introduction to ITK• Image segmentation performance evaluationSteger’s Curve Detection Algorithm (I)4• Step 1: Identify maximal line width. Convolve image with a Gaussian kernel whose size satisfies:3w• Step 2: For each pixel, calculate the direction (nx, ny) with the maximal second directional derivative, which is the eigenvector corresponding to the largest eigenvalue of the Hessian matrix.5Steger’s Curve Detection Algorithm (II)222222ffxxyHffyyxy • Step 3: Calculate the first and second directional derivative• Step 4: Determine location of the local intensity maximum6Steger’s Curve Detection Algorithm (III)22 2xxyyxx x xy x y yy ynrnnHnfnfnnfn  xxyyxx yyfrnnffn fn*222xx yyxx x xy x y yy yfn fnrxrfnfnnfn 212px r rx rx • Step 5: Test whether it is a center line point• Step 6: Link individual center line pixels into a line/curve7Steger’s Curve Detection Algorithm (IV)*11if , the pixel is on the center line22otherwisexSteger’s Line Detection Algorithm (V)• Step 7: Correct for intensity imbalance if necessary89• Review: Steger’s line/curve detection algorithm• Intensity thresholding based image segmentation• A brief introduction to ITK• Image segmentation performance evaluation10Overview: Image Segmentation (I)• Definition Segmentation is the process of separating objects from background (Snyder & Qi in “Machine Vision)Segmentation is the partitioning of a dataset into continuous regions (or volumes) whose member elements have common, cohesive properties (Yoo in "Insight into Images").Image segmentation is the task of finding groups of pixels that “go together” (Szeliski in “Computer Vision”). • Segmentation is an essential process in bioimage analysis that is critical for many subsequent processes such as object recognition and shape analysis.11Overview: Image Segmentation (II)• There are many types of segmentation techniques:- Threshold-based segmentation- Region-based segmentation- Boundary/surface-based segmentation- Motion-based segmentation- Color-based segmentation- Others… • It is often very useful to combine multiple techniques for image segmentation. • For bioimage analysis, accuracy in segmentation is essential.12Thresholding-Based Segmentation (I)• Revisit the definition"Segmentation is the partitioning of a dataset into continous regions (or volumes) whose member elements have common, cohesive properties".• Intensity is the most frequently used property. • Multiple continuous regions of cohesive intensities will result in multiple peaks in intensity histogram.13Thresholding-Based Segmentation (II)• Thresholding-based segmentation is usually among the first options to be considered. - Simple; can be quite reliable- Easy to implement.• There are many refinements to the basic idea that work remarkably well.Basic Ideas of Thresholding-Based Segmentation (I)141 ,,0 ,if I x y Tgxyif I x y T2121 ,, , ,aif Ixy Tgxy b if T Ixy Tcif Ixy TBasic Ideas of Thresholding-Based Segmentation (II)16How to Set Thresholds (I)• There are several ways to set the thresholds. - Using local minima in the intensity histogram.- Use intensity histogram fitting with a mixture of Gaussians. • Example:0 50 100 150 200 250024681012x 10417Example Results0 50 100 150024681012x 10Threshold = 70Threshold = 6018Region Growth After Thresholding • Thresholded pixels need to be connected into regions, often through recursive region growth.• Morphological image processing is often required to remove noise-related irregularities.19How to Set Thresholds (II)• One way to fit multiple Gaussians• Determine the number of Gaussians- Bayesian information criterion (BIC)Reference: C. Fraley and A. E. Raftery. Model-based clustering, discriminant analysis and density estimation. Journal of the American Statistical Association, 97:611–631, 2002.Implementation in R : http://www.stat.washington.edu/mclust/BIC 2 logModelmaximized likelihoodNumber of parameters in model Number of measurementsMMMMlog p x M N nMlog p x MNMn20How to Set Thresholds (III)• Discriminant analysis (supervised classification)• Determine the threshold between two neighboring Gaussian 2212122212122222xxwwexp exp      21212 2 1 2122 22 2221 12 21 1211022 22wxx logw          1class jjMkkkwp xPx jwp x21• Review: Steger’s line/curve detection algorithm• Intensity thresholding based image segmentation• A brief introduction to ITK• Image segmentation performance evaluation22Introduction to ITK (I)• Started in 1999 through funding by the National Library of Medicine to support the Visible Human Project. • Website: http://www.itk.org/• ITK: insight toolkit- Open source software package for image registration and segmentation• Language: 55% C++; 25% C; XML 11%; Other 9% (as of Feb-27, 2012)23Introduction to ITK (II)•Scale- Approximately 2.2 million lines of code (as of Feb-27, 2012)- Initial cost: 718 person years, $39M (as of Feb-27, 2012)• Current release 4.0 (as of Feb-27-2012)24Introduction to MAT-ITK• Website: http://matitk.cs.sfu.ca/25• Review: Steger’s line/curve detection algorithm• Intensity thresholding based image segmentation• A brief introduction to ITK• Image segmentation performance evaluationReferenceHeimann et al, Comparison and Evaluation of Methods for Liver Segmentation From CT Datasets, IEEE TRANSACTIONS ON MEDICAL IMAGING, VOL. 28, NO. 8, pp.