1CSE152, Spr 06 Intro Computer VisionAnalysis of Binary Images Introduction to Computer VisionCSE 152Lecture 7CSE152, Spr 06 Intro Computer VisionThe appearance of colors• Color appearance is strongly affected by (at least):– Spectrum of lighting striking the retina– other nearby colors (space)– adaptation to previous views (time)– “state of mind”CSE152, Spr 06 Intro Computer VisionColor ReflectanceMeasured color spectrum is a function of the spectrum of the illumination and reflectanceFrom Foundations of Vision, Brian Wandell, 1995, via B. Freeman slidesCSE152, Spr 06 Intro Computer Visionslide from T. DarrelCSE152, Spr 06 Intro Computer VisionColor matching functions• Choose primaries, say P1(λ), P2(λ), P3(λ)• For monochromatic (single wavelength) energy function, what amounts of primaries will match it? • i.e., For each wavelength λ, determine how much of A, of B, and of C is needed to match light of that wavelength alone.• These are color matching functions)()()(λλλcbaprimaries are monochromatic at 645.2nm, 526.3nm, 444.4nmRGBCSE152, Spr 06 Intro Computer VisionCIE xyY (Chromaticity Space)2CSE152, Spr 06 Intro Computer VisionBlob Tracking for Robot ControlCSE152, Spr 05 Intro Computer VisionBasic Steps1. Labeling pixels as foreground/background (0,1).2. Morphological operators (sometimes)3. Find pixels corresponding to a region4. Compute properties of each regionCSE152, Spr 05 Intro Computer VisionHistogram-based Segmentation• Select threshold• Create binary image:– I(x,y) < T -> O(x,y) = 0– I(x,y) > T -> O(x,y) = 1Ex: bright object on dark background:Ex: bright object on dark background:TTGray valueGray valueNumber of pixelsNumber of pixelsHistogramHistogram[ From Octavia Camps]CSE152, Spr 05 Intro Computer VisionHow do we select a Threshold?• Manually determine threshold experimentally. – Good when lighting is stable and high contrast.• Automatic thresholding– P-tile method–Mode method– Peakiness detection– Iterative algorithmCSE152, Spr 05 Intro Computer VisionP-Tile Method• If the size of the object is approx. known, pick T s.t. the area under the histogram corresponds to the size of the object:TT[ From Octavia Camps]CSE152, Spr 05 Intro Computer VisionMode Method• Model intensity in each region Rias “constant” + N(0,σi):[ From Octavia Camps]3CSE152, Spr 05 Intro Computer VisionExample: Image with 3 regionsIdeal histogram:Ideal histogram:μμ11μμ33μμ22Add noise:Add noise:μμ11μμ33μμ22The valleys areThe valleys aregood places for good places for thresholdingthresholdingtotoseparate regions.separate regions.[ From Octavia Camps]CSE152, Spr 05 Intro Computer VisionFinding the peaks and valleys• It is a not trivial problem:[ From Octavia Camps]CSE152, Spr 05 Intro Computer Vision“Peakiness” Detection Algorithm• Find the two HIGHEST LOCAL MAXIMA at a MINIMUM DISTANCE APART: giand gj• Find lowest point between them: gk• Measure “peakiness”: – min(H(gi),H(gj))/H(gk)• Find (gi,gj,gk) with highest peakinessggiiggjjggkk[ From Octavia Camps]CSE152, Spr 05 Intro Computer VisionRegionsCSE152, Spr 05 Intro Computer VisionWhat is a region?• “Maximal connected set of points in the image with same brightness value” (e.g., 1)• Two points are connected if there exists a continuous path joining them.• Regions can be simply connected (For every pair of points in the region, all smooth paths can be smoothly and continuously deformed into each other). Otherwise, region is multiply connected(holes)CSE152, Spr 05 Intro Computer VisionConnected Regions111111111111111111111111111111• What are the connected regions in this binary image?• Which regions are contained within which region?4CSE152, Spr 05 Intro Computer VisionConnected Regions11111111111111111111111• What the connected regions in this binary image?• Which regions are contained within which region?CSE152, Spr 05 Intro Computer VisionFour & Eight ConnectednessEight ConnectedFour ConnectedCSE152, Spr 05 Intro Computer VisionAlmost obviousJordan Curve Theorem• “Every closed curve in R2divides the plane into two region, the ‘outside’ and ‘inside’ of the curve.”CSE152, Spr 05 Intro Computer VisionProblem of 4/8 Connectedness1111111111• 8 Connected:– 1’s form a closed curve, but background only forms one region.• 4 Connected– Background has two regions, but ones form four “open” curves (no closed curve)CSE152, Spr 05 Intro Computer VisionTo achieve consistency w.r.t. Jordan Curve Theorem1. Treat background as 4-connected and foreground as 8-connected.2. Use 6-connectednessCSE152, Spr 05 Intro Computer VisionRecursive Labeling Connected Component Exploration215CSE152, Spr 05 Intro Computer VisionRecursive Labeling Connected Component ExplorationProcedure Label (Pixel)BEGINMark(Pixel) <- Marker;FOR neighbor in Neighbors(Pixel) DOIF Image (neighbor) = 1 AND Mark(neighbor)=nil THENLabel(neighbor)ENDBEGIN MainMarker <- 0; FOR Pixel in Image DOIF Image(Pixel) = 1 AND Mark(Pixel)=nil THENBEGINMarker <- Marker + 1;Label(Pixel);END;ENDGlobals:Marker: integerMark: Matrix same size as Image,initialized to NILCSE152, Spr 05 Intro Computer VisionSome notes• How deep does stack go?• Iterative algorithms (See reading from Horn)• Parallel algorithmsCSE152, Spr 05 Intro Computer VisionProperties extracted from binary image• A tree showing containment of regions• Properties of a region1. Genus – number of holes2. Centroid3. Area4. Perimeter5. Moments (e.g., measure of elongation)6. Number of “extrema” (indentations, bulges)7. SkeletonCSE152, Spr 05 Intro Computer VisionMoments1100Given a pair of nonGiven a pair of non--negative integers (j,k) the negative integers (j,k) the discrete((j,k)j,k)ththmomentof S is :of S is :B(x,y)∑∑===nxmykjkjyxyxBM11,),(• Fast way to implement computation over n by m image or window• One objectCSE152, Spr 05 Intro Computer VisionArea: Moment M001100Example:Example:Area of S !!Area of S !!CSE152, Spr 05 Intro Computer VisionMoments1100Example:Example:Center of gravity (Center of gravity (CentroidCentroid) of S !!) of S !!6CSE152, Spr 05 Intro Computer VisionShape recognition by Moments11001100==??Recognition could be done by comparing momentsHowever, moments Mjkare not invariant under:•Translation•Scaling•Rotation•SkewingCSE152, Spr 05 Intro Computer VisionCentral Moments1100Given a pair of nonGiven a pair of non--negative integers (j,k) the negative integers