110/2/2003CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythComputer VisionGrouping and SegmentationProfessor Hagerhttp://www.cs.jhu.edu/~hager10/2/2003CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythGrouping and Segmentation• G&S appear to be one of the early processes in human vision• They are a way of *organizing* image content into “semantically related” groups• In some applications, segmentation is the crucial step (e.g. some types of aerial image interpretation).• We’ll just touch on a few simple approaches of image grouping and segmentation• We’ll also present a couple of useful geometric grouping methods.210/2/2003CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythGrouping• Grouping is the process of associating similar image features together10/2/2003CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythGrouping• Grouping is the process of associating similar image features together• The Gestalt School:– Proximity:tokens that are nearby tend to be grouped.– Similarity:similar tokens tend to be grouped together.– Common fate:tokens that have coherent motion tend to be grouped together.– Common region:tokens that lie inside the same closed region tend to be grouped together.– Parallelism:parallel curves or tokens tend to be grouped together.– Closure:tokens or curves that tend to lead to closed curves tend to be grouped together.– Symmetry:curves that lead to symmetric groups are grouped together.– Continuity:tokens that lead to “continuous ” (as in “joining up nicely ”, rather than in the formal sense): curves tend to be grouped.– Familiar Conguration:tokens that, when grouped, lead to a familiar object,tend to be grouped together310/2/2003CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. Forsyth10/2/2003CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. Forsyth410/2/2003CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. Forsyth10/2/2003CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. Forsyth510/2/2003CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. Forsyth10/2/2003CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythThe Hough Transform• How can we detect (group) extended line structures in images?y = m x + bxybm610/2/2003CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythThe Hough Transform• How can we detect extended line structures in images?b = - x m + ymbxy10/2/2003CS 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.710/2/2003CS 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 dimensionality10/2/2003CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythRANSAC: A More General Method• The Hough transform has the nice feature that it provides a method for detecting geometric structure in clutter.• The HT suffers from the curse of dimensionality.• RANSAC (Random Sample Consensus) is a robust estimation technique that avoids (to some degree) the curse of dimensionality810/2/2003CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythRANSAC: General IdeaHow to find the line in this?10/2/2003CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythRANSAC: General IdeaBasic observation: if we wereto choose the “right” pair of points910/2/2003CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythRANSAC: General IdeaBasic observation: if we wereto choose the “right” pair of points then it would be fairlyobvious that many other pointswould agreeAlgorithm:For some number of tries Npick a pair of pointsfit a line to these pointscount the number of other pts that agreeReturn: line parameters with bestagreement10/2/2003CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythRANSAC: General IdeaAlgorithm:For some number of tries Npick a pair of pointsfit a line to these pointscount the number of other pts that agreeReturn: line parameters with bestagreementQuestions: 1) How many points2) What do we mean “agree”1010/2/2003CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythRANSAC• # of points is N = log(1-p)/log(1-(1-ε)s)– assumes sampling is independent– p is the probability one of the samples is all inliers– s is sample size (2 for us)–ε is percentage of outliers• Consensus:– Assume the points (inliners) are contaminated with Gaussian noise– Distance to the line is a χ2mmodel where (in our case) m =1• Choose a probability threshold from χ21giving a distance t= 3.82 σ2 for α = .95• inliner if distance2< t2• outlier if distance2>= t210/2/2003CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythImage Segmentation: A Brief Overview• Segmentation– criteria– region group and counting1110/2/2003CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythSegmentation: Definitions• An affinity measure d(R1,R2) Æ or a homogeneity measure m(R) – note possibly d(R1,R2) = |m(R1) – M(R2)|• An 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 x10/2/2003CS 461, Copyright G.D. Hagerwith slides shamelessly stolen from D. ForsythSimple