Lecture 24: SegmentationCS6670: Computer VisionNoah SnavelyFrom Sandlot ScienceAnnouncements• Final project presentations– Wednesday, December 16th, 2-4:45pm, Upson 315– Volunteers to present on Tuesday the 15th?• Final quiz this ThursdayDeblurring Application: Hubble Space Telescope• Launched with flawed mirror• Initially used deconvolution to correct images before corrective optics installedImage of starFast Separation of Direct and Global Images Using High Frequency IlluminationShree K. NayarGurunandan G. KrishnanColumbia UniversitySIGGRAPH 2006Michael D. GrossbergCity College of New YorkRamesh RaskarMERLsourcesurfacePDirect and Global IlluminationAA : DirectBB : InterrelectionCC : SubsurfaceDparticipating mediumD : VolumetrictranslucentsurfaceEE : Diffusion camera],[],[],[ icLicLicLgddirectglobalradianceDirect and Global Components: InterreflectionssurfaceicamerasourcePgjiLjiAicL ],[],[],[jBRDF and geometryHigh Frequency Illumination Patternsurfacecamerasourcefraction of activated source elements],[],[],[ icLicLicLgd+iHigh Frequency Illumination Patternsurfacefraction of activated source elementscamerasource],[],[],[ icLicLicLgd+],[],[ icLicLg)1(-i:21min2LLgSeparation from Two Imagesdirect global,minmaxLLLdOther Global Effects: Subsurface Scatteringtranslucent surfacecamerasourceijOther Global Effects: Volumetric Scatteringsurfacecamerasourceparticipating mediumijDiffuse InterreflectionsSpecularInterreflectionsVolumetric ScatteringSubsurfaceScatteringDiffusionSceneSceneDirect GlobalReal World Examples:Eggs: Diffuse InterreflectionsDirect GlobalWooden Blocks: Specular InterreflectionsDirect GlobalKitchen Sink: Volumetric ScatteringVolumetric Scattering:Chandrasekar 50, Ishimaru 78 Direct GlobalPeppers: Subsurface ScatteringDirect GlobalHandDirect GlobalSkin: Hanrahan and Krueger 93,Uchida 96, Haro 01, Jensen et al. 01,Cula and Dana 02, Igarashi et al. 05, Weyrich et al. 05Face: Without and With MakeupGlobalDirectGlobalDirectWithout MakeupWith MakeupBlonde HairHair Scattering: Stamm et al. 77,Bustard and Smith 91, Lu et al. 00Marschner et al. 03Direct GlobalPhotometric Stereo using Direct ImagesBowlShapeSource 1Source 2Source 3DirectGlobalNayar et al., 1991www.cs.columbia.edu/CAVEQuestions?From images to objectsWhat defines an object?• Subjective problem, but has been well-studied• Gestalt Laws seek to formalize this– proximity, similarity, continuation, closure, common fate– see notes by Steve Joordens, U. TorontoExtracting objectsHow could we do this automatically (or at least semi-automatically)?The Gestalt school• Grouping is key to visual perception• Elements in a collection can have properties that result from relationships • “The whole is greater than the sum of its parts”subjective contoursocclusionfamiliar configurationhttp://en.wikipedia.org/wiki/Gestalt_psychologySlide from S.LazebnikThe ultimate Gestalt?Slide from S.LazebnikGestalt factors• These factors make intuitive sense, but are very difficult to translate into algorithmsSlide from S.LazebnikSemi-automatic binary segmentationIntelligent Scissors (demo)Intelligent Scissors [Mortensen 95]• Approach answers a basic question– Q: how to find a path from seed to mouse that follows object boundary as closely as possible?GrabCutGrabcut [Rother et al., SIGGRAPH 2004]Is user-input required?Our visual system is proof that automatic methods are possible• classical image segmentation methods are automaticArgument for user-directed methods?• only user knows desired scale/object of interestqAutomatic graph cut [Shi & Malik]Fully-connected graph• node for every pixel• link between every pair of pixels, p,q• cost cpqfor each link– cpqmeasures similarity» similarity is inversely proportional to difference in color and positionpCpqcSegmentation by Graph CutsBreak Graph into Segments• Delete links that cross between segments• Easiest to break links that have low cost (similarity)– similar pixels should be in the same segments– dissimilar pixels should be in different segmentswA B CCuts in a graphLink Cut• set of links whose removal makes a graph disconnected• cost of a cut:ABFind minimum cut• gives you a segmentationBut min cut is not always the best cut...Cuts in a graphABNormalized Cut• a cut penalizes large segments• fix by normalizing for size of segments• volume(A) = sum of costs of all edges that touch AInterpretation as a Dynamical SystemTreat the links as springs and shake the system• elasticity proportional to cost• vibration “modes” correspond to segments– can compute these by solving an eigenvector problem– http://www.cis.upenn.edu/~jshi/papers/pami_ncut.pdfInterpretation as a Dynamical SystemTreat the links as springs and shake the system• elasticity proportional to cost• vibration “modes” correspond to segments– can compute these by solving an eigenvector problem– http://www.cis.upenn.edu/~jshi/papers/pami_ncut.pdfColor Image SegmentationExtension to Soft Segmentation• Each pixel is convex combination of segments.Levin et al. 2006- compute mattes by solving eigenvector