1Introduction (contd.) 1ECE 178: Introduction (contd.)Lecture Notes #2: more basics Section 2.4 –sampling and quantization Section 2.5 –relationship between pixels, connectivity analysisAck: Figures are mostly from Gonzalez & WoodsIntroduction (contd.) 2Light and the EM Spectrum2Introduction (contd.) 3Digial Image AcquisitionIntroduction (contd.) 4Sampling and Quantization3Introduction (contd.) 5Sampling & Quantization (contd.)Introduction (contd.) 6Digital Image: Representation4Introduction (contd.) 7Image Dimension: NxN; k bits per pixel.Storage RequirementIntroduction (contd.) 8Spatial Resolution5Introduction (contd.) 9Re-sampling…Introduction (contd.) 10Quantization: Gray-scale resolution6Introduction (contd.) 11…false contouringIntroduction (contd.) 12Sampling and Aliasing7Introduction (contd.) 13Relationship between pixels Neighbors of a pixel– 4-neighbors (N,S,W,E pixels) == N4(p). A pixel p atcoordinates (x,y) has four horizontal and four verticalneighbors:• (x+1,y), (x-1, y), (x,y+1), (x, y-1)– You can add the four diagonal neighbors to give the 8-neighbor set. Diagonal neighbors == ND(p).– 8-neighbors: include diagonal pixels == N8(p).Introduction (contd.) 14Pixel ConnectivityConnectivity -> to trace contours, define object boundaries,segmentation.In order for two pixels to be connected, they must be“neighbors” sharing a common property—satisfy somesimilarity criterion. For example, in a binary image withpixel values “0” and “1”, two neighboring pixels are saidto be connected if they have the same value.Let V: Set of gray level values used to defineconnectivity; e.g., V={1}.8Introduction (contd.) 15Connectivity-contd. 4-adjacency: Two pixels p and q with valuesin V are 4-adjacent if q is in the set N4(p). 8-adjacency: q is in the set N8(p). m-adjacency: Modification of 8-A to eliminatemultiple connections.– q is in N4(p) or– q in ND(p) and N4(p) Ç N4(q) is empty.Introduction (contd.) 16Connected components Let S represent a subset of pixels in animage. If p and q are in S, p is connected to q in S ifthere is a path from p to q entirely in S. Connected component: Set of pixels in S thatare connected; There can be more than onesuch set within a given S.9Introduction (contd.) 174-connected components– both r and t = 0; assign new label to p;– only one of r and t is a 1. assign that label to p;– both r and t are 1.• same label => assign it to p;• different label=> assign one of them to p andestablish equivalence between labels (they arethe same.)prtp=0: no action;p=1: check r and t.Second pass over the image to merge equivalent labels.Introduction (contd.) 18ExerciseDevelop a similar algorithm for 8-connectivity.10Introduction (contd.) 19Problems with 4- and 8-connectivity Neither method is satisfactory.– Why? A simple closed curve divides a plane intotwo simply connected regions.– However, neither 4-connectivity nor 8-connectivitycan achieve this for discrete labelled components.– Give some examples..Introduction (contd.) 20Related questions Can you “tile” a plane with a pentagon?11Introduction (contd.) 21Distance Measures What is a Distance Metric? For pixels p,q, and z, with coordinates (x,y), (s,t),and (u,v), respectively:D p q D p q p qD p q D q pD p z D p q D q z( , ) ( ( , ) )( , ) ( , )( , ) ( , ) ( , )! = ==" +0 0 iff Introduction (contd.) 22Distance Measures Euclidean City Block ChessboardD p q x s y te( , ) ( ) ( )= ! + !2 2D p q x s y t4( , ) = ! + !D p q x s y t8( , ) max( , )= ! !2 2 2 2 22 1 1 1 22 1 0 1 22 1 1 1 22 2 2 2
View Full Document