0 0 13 views

**Unformatted text preview:**

Computer Vision Spring 2006 15 385 685 Instructor S Narasimhan Wean 5403 T R 3 00pm 4 20pm Announcements Homework 1 is due on Thursday in class Homework 2 will be out on Thursday Start homeworks early Post questions on bboard Binary Images Properties and Methods Lecture 4 Binary Images Images with only two values 0 or 1 Simple to process and analyze Very useful for industrial applications Binary Images Obtained from gray level or color image g x y by Thresholding Characteristic Function b x y 1 if g x y T 0 if g x y T Topics Discussed Geometric Properties Continuous and Discrete Binary Images Multiple Objects Connectivity Sequential iterative processing Selecting a Threshold Bimodal Histogram Threshold Geometric Properties of Binary Images Assume b x y b x y is continuous only one object Area Zeroth Moment A b x y dx dy y Position Center of Mass First Moment 1 x x b x y dx dy A 1 y y b x y dx dy A x Geometric Properties of Binary Images b x y Orientation Difficult to define Axis of least second moment For mass Axis of minimum inertia y y x y x r Minimize x E r b x y dx dy 2 Which equation of line to use y x y r y mx b x 0 m We use x sin y cos 0 are finite Minimizing Second Moment Find and that minimize E for a given b x y We can show that So r x sin y cos E x sin y cos b x y dx dy 2 dE Using 0 we get A x sin y cos 0 d Note Axis passes through the center So change co ordinates x x x x y y y y Minimizing Second Moment We get E a sin 2 b sin cos c cos 2 where a x 2 b x y dx dy b 2 x y b x y dx dy c y 2 b x y dx dy second moments w r t We are not done yet x y Minimizing Second Moment 2 2 E a sin b sin cos c cos b dE Using 0 we get tan 2 a c d sin 2 b b 2 a c 2 cos 2 a c b 2 a c 2 Solutions with ve sign must be used to minimize E Why Emin roundedness Emax Discrete Binary Images Assume b x y is discrete only one object b Area Zeroth Moment A ij j Position Center of Mass First Moment 1 x i bij A b i j i 1 y j bij A Second Moments a i bij 2 b 2 ij bij c j 2 bij Note a b c are defined w r t origin Multiple Objects Need to SEGMENT image into separate COMPONENTS regions Non trivial Connected Components b x y Maximal Set of Connected points A Remember Graph Theory A B are connected Path exists between A B along which b x y is constant y B x Connected Component Labeling Region Growing Algorithm a Start with SEED point where b x y 1 b Assign LABEL to seed point c Assign SAME LABEL to its Neighbors with b x y 1 d Assign SAME LABEL to Neighbors of Neighbors Terminates when a component is completely labeled Then pick another UNLABELED seed point What do we mean by Neighbors Connectedness 4 connectedness 8 connectedness Neither is perfect What do we mean by Neighbors Jordan s Curve Theorem A Closed Curve 2 connected regions Consider B 4 C 8 C 0 1 0 B1 O1 B1 B O B 1 0 1 O2 B2 O3 O B O 0 1 0 B1 O4 B1 B O B Hole without Closed curve Connected Backgrounds with closed Ring Solution to Neighborhood Problem Introduce Asymmetry a OR b Using b 0 1 0 1 0 1 0 1 0 B O1 O1 B B O2 B O2 B Two separate Line Segments Hexagonal Tessellation Asymmetry makes a SQUARE grid like HEXAGONAL grid Sequential Labeling Algorithm D B C A Raster Scan Note We want to label A B C D are already labeled Sequential Labeling Algorithm 0 0 0 1 D X X 1 0 B 0 1 label A new label label A label D label A label B X X X 0 0 0 C 1 0 B C 1 label A background label A label C If label B label C then label A label B Sequential Labeling Algorithm 0 B C 1 What if label B not equal to label C Sequential Labeling Algorithm 0 B C 1 What if label B not equal to label C Solution Let label A label B 2 Create EQUIVALENCE TABLE Resolve Equivalence in Second Pass 2 1 7 3 6 4 Morphological Operations Euler Number Number of Bodies B Number of Holes H B i A E 1 E 2 E 0 Eimage Enon overlapping regions Iterative Modification Allows us to incrementally change image Example Etch thin object to produce SKELETON Conservative Operations Do not change the Euler number of image 0 0 0 0 0 0 0 0 E 0 0 1 0 0 0 0 E 1 New Body Euler Differential 1 Euler Differential E Note If E 1 for center pixel 0 1 1 If E 1 for center pixel 1 0 1 We want to find Neighborhoods with E 0 0 1 0 0 0 0 E 1 1 1 1 0 0 1 E 0 1 1 Each pixel has 64 neighborhoods 0 1 E 1 0 1 1 1 0 1 0 E 1 Only 5 different sets of neighborhoods possible N 1 N 0 N 1 N 2 0 1 0 1 0 E 2 Problem with Parallel Implementation 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 E 0 Solution Use Interlaced Subfields No two neighbors have the same label Apply parallel operations to ONE subfield at a time 1 2 3 1 2 3 2 3 1 2 3 1 3 1 2 3 1 2 1 2 3 1 2 3 2 3 1 2 3 1 3 1 2 3 1 2 Notation for Iterative Modification Specify Neighborhood Set S for which the same action must be taken For example S N 0 Consider pixel i j aij 1 if Neighborhood of i j S bij value of pixel i j cij new value of pixel i j 16 Boolean Functions Finding Skeletons Use S N 0 Zero Euler Differential Set Use 5th Column in the Boolean Functions Table Thinning without changing Euler Number Other Tricks Expanding Thinning the Background Noise Removal Thin and Expand Finding Skeletons Use S N 0 Zero Euler Differential Set Use 5th Column in the Boolean Functions Table Thinning without changing Euler Number Announcements Homework 1 is due on Thursday in class Homework 2 will be out on Thursday Start homeworks early Post questions on bboard Next Two Classes 1D Signal and 2D …