Bioimage Informatics Lecture 11 Spring 2012 Bioimage Data Analysis III Edge Detection Line Curve Detection Lecture 11 February 22 2012 1 Outline Review low level feature detection Overview of edge detection Line curve detection using the Hough transform 2 Review low level feature detection Overview of edge detection Line curve detection using the Hough transform 3 Feature Detection Points Particles Fluorescent speckles in a Xenopus extract spindle Vesicles transported in a Drosophila motor neuron 4 Feature Detection Lines Curves T Wittmann et al J Cell Biol 161 845 2003 http www cell com cell picture show Nikon Small World 2003 Torsten Wittmann UCSF Filamentous actin and microtubules structural proteins in mouse fibroblasts cells 1000x 5 An Image from Lab Visit Bovine pulmonary artery endothelial BPAE cells stained with a combination of fluorescent dyes Mitochondria were labeled with red fluorescent MitoTracker Red CMXRos F actin was stained using green fluorescent Alexa Fluor 488 phalloidin and blue fluorescent DAPI was used to label the nuclei Feature Detection Regions A neutrophil chasing a bacterium Devreotes Lab Johns Hopkins U Mitochondria in mouse hippocampal neuron James Lim LBNL 7 Marr s Theory of Visual Information Processing David Marr Jan 19 1945 Nov 17 1980 Three levels of cognition Computational level Algorithmic representation level Implementational level Three stages of vision Primal sketch 2 5D sketch 3D model Vision A computational investigation into the human representation and processing of visual information 8 Review low level feature detection Overview of edge detection Line curve detection using the Hough transform 9 Edge Detection What is an edge An edge point or an edge is a pixel at or around which the image intensities undergo a sharp change 10 Motivation Edge in Images The edge can be treated as a 1D signal when examined in the normal direction Gonzalez Woods DIP 3 e 11 Edge Can be Identified by Calculating Gradient Gonzalez Woods DIP 3 e 12 How to Calculate Image Gradient Calculation of image gradient follows standard numerical differentiation scheme 1 f x h f x hf x h 2 f x h3 2 1 2 f x h f x hf x h f x h3 2 f x0 h f x0 h h2 f x0 2h In an image the first and second derivatives I i j I i 1 j I i 1 j I x i j h2 x 2 h 2 I i j I i 1 j 2 I i j I i 1 j h I i j xx x 2 h2 13 Gradient Calculation is Sensitive to Noise Without image smoothing calculation of derivatives becomes highly sensitive to noise Gonzalez Woods DIP 3 e 14 Edge Detection Procedure Step I noise suppression Step II edge enhancement Step III edge localization Canny J A Computational Approach To Edge Detection IEEE Trans Pattern Analysis and Machine Intelligence 8 6 679 698 1986 15 Why Use Gaussian Kernel for Smoothing Gaussian kernel is not the only smoothing kernel It has several important advantages Convolution of a Gaussian with another Gaussian is Gaussian Efficiency Gaussian kernel is separable Repeated smoothing with a low pass filter will eventually converge to Gaussian smoothing 16 Combination of Noise Suppression and Gradient Estimation I Notation J raw image I filtered image after convolution with Gaussian kernel G A basic property of convolution G J I G Ix J x x x G J I G Iy J y y y Es x0 y0 I x2 x0 y0 I y2 x0 y0 Eo x0 y0 arctan I y x0 y0 I x x0 y0 Edge strength Edge orientation 17 Combination of Noise Suppression and Gradient Estimation II Gaussian kernel in 1D x2 1 2 e 2 2 First order derivative G x x G x e 3 2 x2 2 2 Second order derivative x G x e 3 2 x2 2 2 x2 1 2 Zero crossing 18 Combination of Noise Suppression and Gradient Estimation III Implementation 2 1 x 2 y 2 1 x2 1 1 1 y G x y x y exp 2 2 exp exp 2 2 2 x y 2 2 2 2 2 y x y x x y 1 G x x G y y G x y x y x dG x x G y y dx G x y x y y G x x dG y y dy Advantages Reduced computational cost Calculation of gradient can run in parallel in both directions 19 Edge Enhancement Step I For each pixel I x0 y0 calculate the gradient I I x x x0 y y y0 Step II Estimate edge strength Es x0 y0 I x2 x0 y0 I y2 x0 y0 Iy Ix Step III Estimate edge direction Eo x0 y0 arctan I y x0 y0 I x x0 y0 20 Calculation of Image Gradient y 1500 1500 100 100 1000 1000 200 300 500 200 500 300 400 400 0 0 500 500 500 500 600 600 1000 1000 700 700 1500 800 1500 800 2000 900 900 2000 1000 1000 200 400 600 800 1000 1200 2500 200 400 600 800 1000 1200 21 Non Maximum Suppression For each pixel I x0 y0 compare the edge strength along the direction perpendicular to the edge Iy An edge point must have its edge strength no less than its two neighbors 22 Hysteresis Thresholding The main purpose is to link detected edge points while minimizing breakage Basic idea Using two thresholds TL and TH Starting from a point where edge gradient magnitude higher than TH Link to neighboring edge points with edge gradient magnitude higher than TL 23 Influence of Scale Selection on Edge Detection Lindeberg 1999 Principles for automatic scale selection in B J ahne et al eds Handbook on Computer Vision and Applications volume 2 pp 239 274 Academic Press 24 Edge Detection Demo 25 Review low level feature detection Overview of edge detection Line curve detection using the Hough transform 26 Line Curve Detection by A variety of techniques are available Spatial domain e g by edge point detection and grouping Transform domain e g by Hough transform 27 Basic Concept of Hough Transform A simple example representing the lines passing through x0 y0 in the parameter space y1 a x1 b y2 a x2 b b x1 a y1 b x2 a y2 y1 a x1 b y2 a x2 b The two lines in the transform domain must intersect at a b 28 HT Algorithm Implementation Details Parameterization using y mx n fails for the case of vertical lines A different way of parameterization x cos y sin Exhaustive search the space of can be time consuming 29 Generalization 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 Circles with known radius but unknown center x xc y yc 2 2 R2 xc xi yc yi 2 2 R2 Ellipses with known major and minor semi axes but unknown center x xc a 2 2 …