Unformatted text preview:

6.801/866Segmentation and Line FittingSegmentation and GroupingGeneral ideasBasic ideas of grouping in humansTechnique: Background SubtractionClassic Background Subtraction modelFinding FeaturesStatic Background Modeling ExamplesStatic Background Modeling ExamplesStatic Background Modeling ExamplesDynamic BackgroundMixture of Gaussian BG modelSegmentation as clusteringClustering AlgorithmsK-MeansK-MeansGraph theoretic clusteringImage Segmentation as Graph PartitioningSome Terminology for Graph PartitioningBoundaries of image regions defined by a number of attributesMeasuring AffinityEigenvectors and cutsExample eigenvectorScale affects affinityScale affects affinityMore than two segmentsMore than two segmentsNormalized cutsNormalized CutSolving the Normalized Cut problemNormalized cutsNormalized Cut As Generalized Eigenvalue problemNormalized cutsFittingFitting and the Hough TransformMechanics of the Hough transformLine fittingWho came from which line?Incremental line fittingIncremental line fittingIncremental line fittingIncremental line fittingIncremental line fittingK-means line fittingK-means line fittingK-means line fittingK-means line fittingK-means line fittingK-means line fittingK-means line fittingRobustnessSegmentation and Line Fitting6.801/866Segmentation and Line FittingT. DarrellSegmentation and Line Fitting• Gestalt grouping• Background subtraction•K-Means• Graph cuts• Hough transform• Iterative fitting(Next time: Probabilistic segmentation)Segmentation and Grouping• Motivation: vision is often simple inference, but for segmentation• Obtain a compact representation from an image/motion sequence/set of tokens• Should support application• Broad theory is absent at present• Grouping (or clustering)– collect together tokens that “belong together”• Fitting– associate a model with tokens–issues• which model?• which token goes to which element?• how many elements in the model?General ideas• tokens– whatever we need to group (pixels, points, surface elements, etc., etc.)• top down segmentation– tokens belong together because they lie on the same object• bottom up segmentation– tokens belong together because they are locally coherent• These two are not mutually exclusiveWhy do these tokens belong together?What is the figure?Basic ideas of grouping in humans• Figure-ground discrimination– grouping can be seen in terms of allocating some elements to a figure, some to ground– impoverished theory• Gestalt properties– elements in a collection of elements can have properties that result from relationships (Muller-Lyer effect)• gestaltqualitat– A series of factors affect whether elements should be grouped together• Gestalt factorsOcclusion is an important cue in grouping.Technique: Background Subtraction• If we know what the background looks like, it is easy to identify “interesting bits”• Applications– Person in an office– Tracking cars on a road– surveillance• Approach:– use a moving average to estimate background image– subtract from current frame– large absolute values are interesting pixels• trick: use morphological operations to clean up pixelslow threshhigh threshEM (later)80x60low threshhigh threshEM (later)160x120Classic Background Subtraction model• Background is assumed to be mostly static• Each pixel is modeled as by a gaussian distribution in YUV space• Model mean is usually updated using a recursive low-pass filterGiven new image, generate silhouetteby marking those pixels that are significantlydifferent from the “background” value.Finding Features2D Head / hands localization– contour analysis: mark extremal points (highest curvature or distance from center of body) as hand features– use skin color model when region of hand or face is found (color model is independent of flesh tone intensity)Static Background Modeling Examples[MIT Media Lab Pfinder / ALIVE System]Static Background Modeling Examples[MIT Media Lab Pfinder / ALIVE System]Static Background Modeling Examples[MIT Media Lab Pfinder / ALIVE System]Dynamic BackgroundBG Pixel distribution is non-stationary:[MIT AI Lab VSAM]Mixture of Gaussian BG modelStaufer and Grimson tracker:Fit per-pixel mixture model to observed distrubution.[MIT AI Lab VSAM]Segmentation as clustering• Cluster together (pixels, tokens, etc.) that belong together• Agglomerative clustering– attach closest to cluster it is closest to– repeat• Divisive clustering– split cluster along best boundary– repeat• Point-Cluster distance– single-link clustering– complete-link clustering– group-average clustering• Dendrograms– yield a picture of output as clustering process continuesClustering AlgorithmsK-Means• Choose a fixed number of clusters• Choose cluster centers and point-cluster allocations to minimize error • can’t do this by search, because there are too many possible allocations.• Algorithm– fix cluster centers; allocate points to closest cluster– fix allocation; compute best cluster centers• x could be any set of features for which we can compute a distance (careful about scaling)xj−µi2j∈elements of i'th cluster∑      i∈clusters∑K-MeansImageClusters on intensity (K=5) Clusters on color (K=5)K-means clustering using intensity alone and color aloneImageClusters on colorK-means using color alone, 11 segmentsK-means usingcolor alone,11 segments.Oversegmentation!K-means using colour andposition, 20 segmentsStill misses goal of perceptuallypleasing segmentation!Graph theoretic clustering• Avoid local minima; use global criteria• Represent tokens using a weighted graph.– affinity matrix• Cut up this graph to get subgraphs with strong interior linksImage Segmentation as Graph PartitioningBuild a weighted graph G=(V,E) from imageV: image pixelsE: connections between pairs of nearby pixelsregion same the tobelong j& iy that probabilit :ijWPartition graph so that similarity within group is large and similarity between groups is small -- Normalized Cuts[Shi&Malik 97][Malik]Some Terminology for Graph Partitioning• How do we bipartition a graph:disjointy necessarilnot A' andA A'A, ),(W)A'A,(∑∈∈=vuvuassoc∅=∩∈∈∑= BAwith BA, ),,W(B)A,(vuvucut[Malik]Boundaries of image regions defined by a number of attributes– Brightness/color–Texture–Motion– Stereoscopic depth– Familiar configuration[Malik]Measuring AffinityIntensityaff x, y()= exp


View Full Document

MIT 6 801 - Segmentation and Line Fitting

Download Segmentation and Line Fitting
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Segmentation and Line Fitting and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Segmentation and Line Fitting 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?