Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Image Segmentation
Preview
Segmentation subdivides an image to regions or objects Two basic properties of intensity values
Discontinuity
Edge detection
Similarity
Thresholding Region growing/splitting/merging
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Detection of Discontinuities: Point detection
Mask operation
R = wi zi
9
Point detection
Isolated point R T
whose gray value is significantly different from its background
i =1
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Detection of discontinuities: Line detection
Mask operation
Preferred direction is weighted by with a larger coefficient The coefficients in each mask sum to zero response of constant gray level areas Compare values of individual masks (run all masks) or run only the mask of specified direction
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Image Segmentation: Line detection
Example: interested in lines of -45o Run the corresponding mask All other lines are eliminated
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Detection of discontinuities: Edge detection
Basic formulation
Edge: a set of connected pixels that lie on the boundary between two regions
Local concept in contrast to more global boundary concept To be measured by grey-level transitions Ideal and blurred edges
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Edge detection
First derivative can be used to detect the presence of an edge (if a point is on a ramp)
The sign of the second derivative can be used to determine whether an edge pixel lie on the dark or light side of an edge
Second derivative produces two value per edge Zero crossing near the edge midpoint Non-horizontal edges define a profile perpendicular to the edge direction
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Edge detection
Edges in the presense of noise
Derivatives are sensitive to (even fairly little) noise Consider image smoothing prior to the use of derivatives
Edge definition again
Edge point whose first derivative is above a pre-specified threshold Edge connected edge points Derivatives are computed through gradients (1st) and Laplacians (2nd)
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Edge detection: Gradient operators
Gradient
f Vector pointing to the direction of Gx x maximum rate of change of f at f = = f G y coordinates (x,y) y Magnitude: gives the quantity of the increase (some times referred to as 2 1/ 2 gradient too) f = mag (f ) = [Gx2 + G y ] f G x + G y Direction: perpendicular to the 1 G x direction of the edge at (x,y) ( x, y ) = tan Gy Partial derivatives computed through 2x2 or 3x3 masks
Sobel operators introduce some smoothing and give more importance to the center point
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Edge detection: Gradient operators Detecting diagonal edges
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Edge detection: Examples
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Edge detection: Examples
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Edge detection: Examples
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Edge detection
Laplacian
2 f 2 f Second-order derivative of a 2-D function f = 2 + 2 y x
2
Digital approximations by proper masks Complementary use for edge detection
Cons: Laplacian is very sensible to noise; double edges Pros: Dark or light side of the edge; zero crossings are of better use Laplacian of Gaussian (LoG): preliminary smoothing to find edges through zero crossings
h( r ) = e
r2 2 2
r 2 = x2 + y2
r 2 2 2 2 2 h( r ) = e 4
r2
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Edge detection
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Edge detection
Example: Edges through LoG zero-crossings on an angiogram image
27x27 Gaussian mask, 3x3
Laplacian Thinner than the gradient edges Closeed loops (spagetti effect) Zero-crossing calculation is not straighforward
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Edge linking and boundary detection Local processing
Analyze pixels in a small neighborhood following predefined criteria. Connect similar (labeled edge) points
Strength of the gradient vector response f Gx + G y ; f ( x, y ) f ( x0 , y0 ) E Gradient vector direction ( x, y ) = tan 1 (Gx / G y ) Both magnitude and angle criteria should be satisfied
( x, y ) ( x0 , y0 ) < A
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Edge linking and boundary detection Example: find rectangular shapes similar to license plate
Find gradients Connect edge points Check horizontal-vertical proportion
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Edge linking and boundary detection Global processing via the Hough transform
Determine if points lie on a curve of specified shape Consider a point (xi,yi) and the general line equation yi = axi + b Write the equation with respect to ab-plane (parametric space) b = xi a + yi Write the equation for a second point (xj,yj) and find the intersection point (a,b) on the parametric space All points on a line intersect at the same parametric point
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Edge linking and boundary detection Computational aspects of the Hough transform
Subdivision of the parametric space into accumulator cells The cell at (i,j) with accumulator values A(i,j) corresponds to (ai,bj) For every point (xk,yk) vary a from cell to cell and solve for b: b = xk a + y k If ap generates bq, then increment the accumulator A(p,q)=A(p,q)+1 At the end of the procedure, a value of Q in A(i,j) corresponds to Q points in the xy-plane lying on the line y = ai x + b j
K different incremens of a generate K different values of b; for n different image point, the method involves nK computations (linear complexity)
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Edge linking and boundary detection Hough transform: handling the vertical lines
Through normal representation x cos + y sin = Instead of straight lines, there are sinusoidal curves in the parameter space The number or intesecting sinusoids is accumulated and then the value Q in the accumulator A(i,j) shows the number of colinear points lying on a line x cos j + y sin j = i
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Edge linking and boundary detection Example: two lines connecting three points each
Fig (d) indicates that the Hough transform exhibits a reflective adjacency relationship
Summary of Hough transform for edge linking
Compute the gradient Specify subdivisions in the parametric plane Examine the counts of the accumulator cells Examine the continuity relationship between pixels in a chosen cell
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Edge linking and boundary detection Example: Hough transform removing gaps (no longer than 5 pixels) between edge pixels
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Edge linking and boundary detection Global processing via Graph-Theoretic Techniques
Graph G=(N,U): a set of nodes N and a set U of arcs (ni, nj).
In a directed arc ni is called parent and nj is called successor. Expansion: identifying successors of a node Starting (0 or root) level, last (goal) level Cost c(ni, nj) associated with an arc; Path n1, n2,,nk, with each ni, being a successor of nj-1. Cost of a path is the sum of costs of the arcs constituting the path. Edge element defined between two neighboor pixels p and q (xp, yp) (xq, yq) Associate cost with an edge element c( p, q) = H [ f ( p ) f (q )]
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Edge linking: examples of graph search
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Thresholding Foundation
Histogram dominant modes: two or more Threshold and thresholding operation
T = T [x, y, p( x, y ), f ( x, y )]; 1 if f ( x, y ) > T g ( x, y ) = 0 if f ( x, y ) T
Illumination
Image is a product of reflectance and illuminance Reflection nature of objects and backaground Poor (nonlinear) illumination could impede the segmentation The final histogram is a result of convolution of the histogram of the log reflectance and log illuminance functions Normalization if the illuminance function is known
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Thresholding Basic Global Thresholding
Threshold midway between maximum and minimum gray levels Appropriate for industrial inspection applications with controllable illumination Automatic algorithm
Segment with initial T into regions G1 and G2 Compute the average gray level m1 and m2 Compute new T=0.5(m1+m2) Repeat until reach an acceptably small change of T in successive iterations
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Thresholding Basic Adaptive Thresholding
Divide the image into sub-images and use local thresholds
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Thresholding Optimal Global and Adaptive Thresholding
Histograms considered as estimates of probability density functions Mixure probability p( z ) = P1 p1 ( z ) + P2 p2 ( z ); P1 + P2 = 1 Select the value of T that minmizes the average T error in making the decision that a given pixel E (T ) = P2 p2 ( z )dz + P 1 p1 ( z ) dz belongs to an object of to the background
Minimizing the probability of eroneous classificaion
Differentiate the error equation and solve for T
T
P2 p2 (T ) = P 1 p1 (T )
Estimating the densities using simple models, e.g. Gaussian
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Thresholding
Boundary Characteristics for Histogram Thresholding
Consider only pixels lying on and near edges Use gradient or Laplacian to preliminary process the image
0 if f < T s ( x, y ) = + if f T if f T and 2 f 0 and 2 f < 0
Transition from light background to dark object is characterized (-,+), object interior is coded by either 0 or +, transition from object to background (+,-)
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Thresholding Thresholds based on several variables
Color or multispectral histograms Thresholding is based on finding clusters in multi-dimensional space Example: face detection
Different color models
Hue and saturation instead of RGB
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Region-based segmentation Basic formulation
Every pixel must be in a region Points in a region must be connected Regions must be disjoint Logical predicate for one region and for distinguishing between regions
Region growing
Group pixels from sub-regions to larger regions Start from a set of seed pixels and append pixels with similar properties
Selection of similarity criteria: color, descriptotors (gray level + moments) Stopping rule
Region splitting and merging
Quadtree decomposition
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Chapter 10 Image Segmentation
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Chapter 10 Image Segmentation
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Chapter 10 Image Segmentation
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Chapter 10 Image Segmentation
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Chapter 10 Image Segmentation
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Chapter 10 Image Segmentation
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Chapter 10 Image Segmentation
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Chapter 10 Image Segmentation
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Chapter 10 Image Segmentation
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Chapter 10 Image Segmentation
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Chapter 10 Image Segmentation
2002 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 2nd ed.
www.imageprocessingbook.com
Chapter 10 Image Segmentation
2002 R. C. Gonzalez & R. E. Woods
