9/28/2001CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythComputer Vision, Lecture 7Professor Hagerhttp://www.cs.jhu.edu/~hager9/28/2001CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythHough Transform Idea• Each edge point in an image is a constraint on line parameters:– constraint is a line– each unique point adds another constraint• Algorithm:– Initialize a 2-D array of counters to zero.– For each edge point (x,y), increment any counter which contains a parameter point (b,m) satisfying b = -x m + y– Threshold counters– Group edgels that belong to above threshold counters into contours– Optional: Refit lines to get higher precision.9/28/2001CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythHough Transform Variation• Problem:– m and b are, in principle, unbounded• rewrite as sin(t) x + cos(t) y = d• For each discrete value of t from 0 to pi, increment counter with nominal d minimal distance from exact value– coarse grid leads to grouping of distinct lines• in post-fitting stage, re-hough at higher resolution• Generalizations– Any linear in parameters model: e.g a x2+ b y2= 1 can use the same algorithm– For f(x,a) = 0, choose any cell ac s.t. f(x,ac) < t for some threshold t.• Limitations:– the curse of dimensionality9/28/2001CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythGrouping on Grouping• Grouping lines (recall Gestalt discussion)– group by proximity– µpro=( ls/g)2where g is the shortest distance between two endpoints– under some assumptions you can show 1/µprois proportional to the probability the two endpoints are close by accident– µpar= {ls}2/ θ s ll– µcol= {ls}2/θ s {ls+ g}• Algorithm:– compute µproand either µcolor µparfor all pairs– group pairs for which these values exceed threshold9/28/2001CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythImage Segmentation RoadMap• Segmentation– criteria– region group and counting• Simple Color Segmentation• Color Histograms and matching• Selection of Color Regions•Texture9/28/2001CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythSegmentation: Definitions• A distance measure d(R1,R2) Æ < or a homogeneity measure m(R) – note possibly d(R1,R2) = |m(R1) – M(R2)|• A similarity threshold τ (could operate on distance or homogeneity)• A region definition (e.g. square tiles)• A neighborhood definition– 4 neighbors– 8 neighborsx x 0 xxx x xx 0 xx x x9/28/2001CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythSimple Thresholding• Choose an image criterion c• Compute a binary image by b(i,j) = 1 if c(I(i,j)) > t; 0 otherwise• Perform “cleanup operations” (image morphology)• Perform grouping– Compute connected components and/or statistics thereof9/28/2001CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythAn Example: MotionDetecting motion:9/28/2001CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythThresholded MotionDetecting motion:50Candidate areas formotion9/28/2001CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythA Closer Look9/28/2001CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythColor: A Second Example• Color representation– DRM [Klinker et al., 1990]: if P is Lambertian, has matte line and highlight line– User selects matte pixels in R – Compute first and second order statistics of cluster– Decompose ellipsoid of variance of matte cluster– Color similarity is defined by Mahalanobis distance ),,( TRST)),(( yxIγ|)),((|1TIRS −−yxT9/28/2001CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythHomogeneous Color Region: Photometry9/28/2001CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythHomogeneous Region: PhotometrySamplePCA-fittedellipsoid9/28/2001CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythAfter thresholding an image, we want to know something about the regions found ... Binary Image ProcessingHow many objects are in the image?Where are the distinct “object” components?“Cleaning up” a binary image?9/28/2001CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythConnected Component Labeling10012Goal: Label contiguousareas of a segmented image with unique labelsx xxxx4 neighbors vs. 8 neighbors9/28/2001CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythMorphological OperatorsThe opening of a binary image A by S isA S = (A S) SThe closing of a binary image A by S isA S = (A S) SThe erosion of a binary image A by a mask S isA S = { x | x + b ∈ A, ∀ b ∈ S}Let Stbe the translation of a set of pixels S by t.St= { x + t | x ∈ S }The dilation of a binary image A by a mask S is thenstructuring elementA S = AbUb ∈ Ssummarized9/28/2001CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythThe “Poor Man’s” Closing• Note that median (or more generally any order statistic) filtering is one way of achieving similar effects. On binary images this canbe also implemented using the averaging filter9/28/2001CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythConnected Component Labeling10012Algorithm1. Image is A. Let A = -A;2. Start in upper left and work L to R, Top to Bottom, looking for an unprocessed (-1) pixel.3. When one is found, change its label to the next unused integer. Relabel all of that pixel’s unprocessed neighbors and their neighbors recursively.4. When there are no more unprocessed neighbors, resume searching at step 2 -- but do so where you left off the last time.9/28/2001CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythLimitations of Thresholding• A uniform threshold may not apply across the image• It measures the uniformity of regions (in some sense), but doesn’t examine the inter-relationship between regions.9/28/2001CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythMore General Segmentation• Region Growing:– Tile the image– Start a region with a seed tile– Merge similar neighboring tiles in the region body– When threshold exceeded, start a new region• Region Splitting– Start with one large