CSE152, Spr 07 Intro Computer VisionFiltering Introduction to Computer VisionCSE 152Lecture 8CSE152, Spr 07 Intro Computer VisionAnnouncements• HW 1 is due today• See links on web page for reading on binary image processing (e-reserves)• Reading on filtering is in text• Next homework will be posted later today or tomorrow – I think…CSE152, Spr 05 Intro Computer VisionBinary System Summary1. Acquire images and binarize (tresholding, color labels, etc.).2. Possibly clean up image using morphological operators.3. Determine regions (blobs) using connected component exploration4. Compute position, area, and orientation of each blob using moments5. Compute features that are rotation, scale, and orientation invariant using Moments (e.g., Eigenvalues of normalized moments).CSE152, 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 VisionFour & Eight ConnectednessEight ConnectedFour ConnectedCSE152, Spr 05 Intro Computer VisionRecursive Labeling Connected Component Exploration21CSE152, 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 VisionMoments (related to moments of intertia)1100Given 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 objectThe order of the Mjkmoment is j +k.CSE152, Spr 05 Intro Computer VisionArea: Moment M001100Example:Example:Area of S !!Area of S !!CSE152, Spr 05 Intro Computer VisionComputing the centroid with Moments1100Example:Example:Center of gravity (Centroid) of S !!Center of gravity (Centroid) of S !!CSE152, 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 (j,k) the centralcentral((j,k)j,k)ththmomentmomentof S is given by:of S is given by:CSE152, Spr 05 Intro Computer VisionNormalized Moments1100Given a pair of nonGiven a pair of non--negative integers (j,k) the negative integers (j,k) the normalizednormalized((j,k)j,k)ththmomentmomentof S is given by:of S is given by:CSE152, Spr 05 Intro Computer VisionRegion orientation from Second Moment Matrix1. Compute second centralized moment matrix2. Compute Eigenvectors of Moment Matrix to obtain orientation3. Eigenvalues are independent of orientation, translation!⎥⎦⎤⎢⎣⎡02111120μμμμ• Symmetric, positive definite matrix• Positive Eigenvalues• Orthogonal EigenvectorsCSE152, Spr 05 Intro Computer VisionBinarization using Color• Object’s in robocup are distinguished by color. • How do you binarize the image so that pixels where ball is located are labeled with 1, and other locations are 0?• Let Cb=(r g b)Tbe the color of the ball.CSE152, Spr 05 Intro Computer VisionBinarization using Color• Let c(u,v) be the color of pixel (u,v)• Simple method• Better alternative (why?)– Convert c(u,v) to HSV space H(u,v), S(u,v) V(u,v)– Convert cbto HSV– Check that HS distance is less than threshold ε and brightness is greater than a treshold V>τ()⎩⎨⎧≤−=otherwise0||),(||if1),(2εbcc vuvubCSE152, Spr 05 Intro Computer VisionBlob TrackingCSE152, Spr 05 Intro Computer VisionMain tracking notions• State : usually a finite number of parameters (a vector) that characterizes the “state” (e.g., location, size, moments, pose) of thing being tracked. (e.g., Φ)• Dynamics: How does the state change over time? How is that changed constrained? (e.g., d Φ/dt)• Trajectory: Φ(t)• Prediction: Given the state at time t-1, what is an estimate of the state at time t?• Data Association: Given predicted state, and measurement of multiple blobs in image at time t,which blob is being tracked?CSE152, Spr 05 Intro Computer VisionOther ideas• Binarization of color images• Blob Tracking– Binary regions– State (e.g., x,y,orientation, scale, etc.)–Prediction– Data AssociationCSE152, Spr 05 Intro Computer Vision(From Bill Freeman)CSE152, Spr 05 Intro Computer VisionSmoothing by AveragingKernel:CSE152, Spr 05 Intro Computer VisionLinear Filters• General process:– Form new image whose pixels are a weighted sum of original pixel values, using the same set of weights at each point.• Properties– Output is a linear function of the input– Output is a shift-invariant function of the input (i.e. shift the input image two pixels to the left, the output is shifted two pixels to the left)• Example: smoothing by averaging– form the average of pixels in a neighbourhood• Example: smoothing with a Gaussian– form a weighted average of pixels in a neighbourhood• Example: finding a derivative– form a weighted average of pixels in a neighbourhoodCSE152, Spr 05 Intro Computer VisionConvolutionImage (I)Kernel (K)*Note: Typically Kernelis relatively small invision applications. -2112-1-1CSE152, Spr 05 Intro Computer VisionConvolution: R= K*IIR∑∑−=−=−−=2/2/2/2/),(),(),(mmhmmkkjhiIkhKjiRKernel sizeis m+1 by m+1m=2CSE152, Spr 05 Intro Computer VisionConvolution: R= K*IIR∑∑−=−=−−=2/2/2/2/),(),(),(mmhmmkkjhiIkhKjiRKernel sizeis m+1 by m+1m=2CSE152, Spr 05 Intro Computer VisionConvolution: R= K*IIR∑∑−=−=−−=2/2/2/2/),(),(),(mmhmmkkjhiIkhKjiRKernel sizeis m+1 by m+1m=2CSE152, Spr 05 Intro Computer VisionConvolution: R= K*IIR∑∑−=−=−−=2/2/2/2/),(),(),(mmhmmkkjhiIkhKjiRKernel sizeis m+1 by m+1m=2CSE152, Spr 05 Intro Computer VisionConvolution: R= K*IIR∑∑−=−=−−=2/2/2/2/),(),(),(mmhmmkkjhiIkhKjiRKernel sizeis m+1 by m+1m=2CSE152, Spr 05 Intro Computer VisionConvolution: R= K*IIR∑∑−=−=−−=2/2/2/2/),(),(),(mmhmmkkjhiIkhKjiRKernel sizeis m+1 by m+1m=2CSE152, Spr 05 Intro Computer VisionConvolution: R= K*IIR∑∑−=−=−−=2/2/2/2/),(),(),(mmhmmkkjhiIkhKjiRKernel sizeis m+1 by m+1m=2CSE152, Spr