1Bioimage InformaticsLecture 12, Spring 2012Bioimage Data Analysis (III): Line/Curve DetectionBioimage Data Analysis (IV)Image Segmentation (part 1)Lecture 12 February 27, 20122Outline• Review: Line/curve detection using the Hough transform• Steger’s line/curve detection algorithm• Intensity thresholding based image segmentation• A brief introduction to ITK3• Review: Line/curve detection using the Hough transform• Steger’s line/curve detection algorithm• Intensity thresholding based image segmentation• A brief introduction to ITK4Basic Concept of Hough Transform• A simple example: representing the lines passing through (x0, y0) in the parameter space. 1111yax bbxay2222yax bbxay1122yax byax b  The two lines in the transform domain must intersect at a,b5HT Algorithm Implementation Details• Parameterization using y=ax+b fails for the case of vertical lines. • A different way of parameterization:• Exhaustive search the space of [, ] can be time-consuming. xcosysin6Generalization of the HT Algorithm for Curve Detection• The HT algorithm is a voting algorithm. The key idea is to convert a (difficult) pattern recognition problem into a (simple) peak detection problem.• Hough transform can be generalized to detect circles, ellipses, or any curve that can be parameterized.• Examples222ccxxyyR222ci cixxyyR 22221ccxx yyabCircles with known radius but unknown centerEllipses with known major and minor semi-axes but unknown center22221ci cixx yyab7Evaluation of Parametric Transform Based Curve Detection• The curve to be detected can be of arbitrary form as long as it can be parameterized. • There are many extensions to HT based feature detection. • Strengths:- Handles occlusion and partial line/curves well. - Relatively robust to noise- Capable of detecting multiple instances• Limitations For curves with multiple parameters, the voting/search can be costly. Other shapes can also generate spurious peaks.M. Nixon & A. Aguado, Feature Extraction & Image Processing, Academic Press, 2nded., 2008.Some General Comments on HT-Based Techniques• Hough transform based feature detection is a evidence-gathering technique. It is equivalent to template matching but is sometimes less costly computationally. • Hough transform is often used in machine vision. • Machine vision often refers to application of computer vision in industrial applications. - Imaging condition can be controlled.- Feature geometry is often known or well defined. • Feature geometry in biological imaging data often is irregular and dynamic. This limits the application of HT-based approaches. 89Feature Detection: Lines/CurvesNikon Small World, 2003Torsten Wittmann, UCSFFilamentous actin and microtubules (structural proteins) inmouse fibroblasts (cells) (1000x)T. Wittmann et al, J. Cell Biol., 161:845, 2003. http://www.cell.com/cell_picture_show10• Review: Line/curve detection using the Hough transform• Steger’s line/curve detection algorithm• Intensity thresholding-based image segmentation• A brief introduction to ITKSteger’s Line/Curve Detection Algorithm11http://ias.in.tum.de/people/stegerC. Steger, M. Ulrich, C. Wiedemann, Machine Vision Algorithms and Applications, Wiley-VCH, 2008Basic Ideas of the Algorithm12• Identify the center of the line by searching for the maximum of the second order directional derivative.• To choose a kernel size such that there is one well defined peak. 3wLocal Curvature of a 1D Function• First derivative• Second derivative•Curvature1300fx0xfx00000 is a local minimum0 is a local maximumfx xfx x3221fxKfxFrist Directional Derivative of a 2D Function• The gradient vector of function f defines the maximum rate of change and direction of change. • The first directional derivative of a function14fxffy0sin , cos ( , )limsin cossin coshfxh yh fxyfhffxyfSecond Directional Derivative of a 2D Function• The Hessian matrix• The second directional derivative of a function15222222ffxxyHffyyxy 111222sinsin coscos0sinsin cos 0cosTTfHvvvvSteger’s Line Detection Algorithm (I)• Local intensity model (1D along the maximum curvature direction)16212px r rx rx *rrr*11Declare a center line point if 22x• Step 1: determine the local direction of intensity search from the eigenvector corresponding to the maximum eigenvalue.• Step 2: Calculate x* • Step 3: individual points are connected based on a directed search and linking process. 17Steger’s Line Detection Algorithm (II) xynn*222xx yyxx x xy x y yy yrn rnrrn rnn rnSteger’s Line Detection Algorithm (III)• Edge points can also be calculated by line detection in the gradient image. This is helped by knowledge of the direction of center line. • Unbalanced intensity profile can be corrected based on a look-up table. 1819• Review: Line/curve detection using the Hough transform• Steger’s line/curve detection algorithm• Intensity thresholding-based image segmentation• A brief introduction to ITK20Overview: Image Segmentation (I)• Definition Segmentation is the process of separating objects from background (Snyder & Qi)Segmentation is the partitioning of a dataset into continuous regions (or volumes) whose member elements have common, cohesive properties (Yoo in "Insight into Images").• Segmentation is an essential process in bioimage analysis; It is critical for many subsequent processes such as object recognition and shape analysis.21Overview: 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