1、Digital Image ProcessingChapter 11:Image Description and Representation12 September 2007Image Representation and Description? Objective:To represent and describe information embedded inan image in other forms that are more suitable than the image itself.Benefits:- Easier to understand- Require fewer

2、 memory, faster to be processed- More “ready to be used”What kind of information we can use?- Boundary, shape- Region- Texture- Relation between regionsShape Representation by Using Chain Codes Chain codes: represent an object boundary by a connected sequence of straight line segments of specified l

3、engthand direction.4-directionalchain code8-directionalchain codeWhy we focus on a boundary?The boundary is a good representation of an object shapeand also requires a few memory.(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.Examples of Chain Codes Object

4、 boundary(resampling)Boundaryvertices4-directionalchain code8-directionalchain code(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.The First Difference of a Chain Codes Problem of a chain code: a chain code sequence depends on a starting point.Solution: tre

5、at a chain code as a circular sequence and redefine thestarting point so that the resulting sequence of numbers forms an integer of minimum magnitude.The first difference of a chain code: counting the number of directionchange (in counterclockwise) between 2 adjacent elements of the code.Example:123

6、0Example: - a chain code: 10103322 - The first difference = 3133030 - Treating a chain code as a circular sequence, we get the first difference = 33133030Chain code : The first difference 0 1 1 0 2 2 0 3 3 2 3 1 2 0 2 2 1 3The first difference is rotationalinvariant.Polygon Approximation Object boun

7、daryMinimum perimeterpolygonRepresent an object boundary by a polygonMinimum perimeter polygon consists of line segments that minimize distances between boundary pixels.(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.Polygon Approximation:Splitting Techniqu

8、es 1. Find the line joiningtwo extreme points0. Object boundary2. Find the farthest pointsfrom the line3. Draw a polygon(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.Distance-Versus-Angle Signatures Represent an 2-D object boundary in term of a 1-D functi

9、on of radial distance with respect to q.(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.Boundary Segments Concept: Partitioning an object boundary by using vertices of a convex hull.Convex hull (gray color)Object boundaryPartitioned boundary(Images from Raf

10、ael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.Input : A set of points on a cornea boundaryOutput: A set of points on a boundary of a convex hull of a cornea1. Sort the points by x-coordinate to get a sequence p1, p2, ,pnFor the upper side of a convex hull2. Put the point

11、s p1 and p2 in a list Lupper with p1 as the first point3. For i = 3 to n4. Do append pi to Lupper5. While Lupper contains more than 2 points and the last 3 points in Lupper do not make a right turn6. Do delete the middle point of the last 3 points from LupperTurnRightOK!TurnRightOK!TurnLeftNOK!Conve

12、x Hull Algorithm For the lower side of a convex hull7. Put the points pn and pn-1 in a list Llower with pn as the first point8. For i = n-2 down to 19. Do append pi to Llower While Llower contains more than 2 points and the last 3 points in Llower do not make a right turn Do delete the middle point

13、of the last 3 points from Llower12. Remove the first and the last points from Llower13. Append Llower to Lupper resulting in the list L14. Return LTurnRightOK!TurnRightOK!TurnLeftNOK!Convex Hull Algorithm (cont.) Skeletons Obtained from thinning or skeletonizing processesMedial axes (dash lines)(Ima

14、ges from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.Thinning Algorithm Neighborhoodarrangementfor the thinningalgorithmConcept: 1. Do not remove end points2. Do not break connectivity3. Do not cause excessive erosionApply only to contour pixels: pixels “1” having a

15、t least one of its 8neighbor pixels valued “0”p2p9p3p8p7p1p4p6p5LetT(p1) = the number of transition 0-1 in the ordered sequence p2, p3, , p8, p9, p2.Notation:=Let00111p1001ExampleN(p1) = 4T(p1) = 3Thinning Algorithm (cont.) Step 1. Mark pixels for deletion if the following conditions are true. a) b)

16、 T(p1) =1c)d) p2p9p3p8p7p1p4p6p5Step 3. Mark pixels for deletion if the following conditions are true. a) b) T(p1) =1c)d) Step 4. Delete marked pixels and repeat Step 1 until no change occurs.(Apply to all border pixels)Step 2. Delete marked pixels and go to Step 3.(Apply to all border pixels)Exampl

17、e: Skeletons Obtained from the Thinning Alg. (Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.SkeletonBoundary Descriptors 1. Simple boundary descriptors: we can use- Length of the boundary- The size of smallest circle or box that can totally enclosing the o

18、bject2. Shape number3. Fourier descriptor4. Statistical momentsShape Number Shape number of the boundary definition: the first difference of smallest magnitudeThe order n of the shape number: the number of digits in the sequence1230(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image P

19、rocessing, 2nd Edition.Shape Number (cont.) Shape numbers of order 4, 6 and 8 (Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.Example: Shape Number Chain code: 0 0 0 0 3 0 0 3 2 2 3 2 2 2 1 2 1 1First difference:3 0 0 0 3 1 0 3 3 0 1 3 0 0 3 1 3 0Shape No.0

20、 0 0 3 1 0 3 3 0 1 3 0 0 3 1 3 0 31. Original boundary2. Find the smallest rectanglethat fits the shape3. Create grid4. Find the nearest Grid.(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.Fourier Descriptor Fourier descriptor: view a coordinate (x,y) as a

21、 complex number (x = real part and y = imaginary part) then apply the Fourier transform to a sequence of boundary points.(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.Fourier descriptor :Let s(k) be a coordinate of a boundary point k :Reconstruction formu

22、laBoundarypointsExample: Fourier Descriptor Examples of reconstruction from Fourier descriptorsP is the number of Fourier coefficients used to reconstruct the boundary(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.Fourier Descriptor Properties (Images from

23、 Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.Some properties of Fourier descriptorsStatistical Moments (Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.Convert a boundary segment into 1D graphView a 1D graph as a PDF functio

24、nCompute the nth order moment of the graphDefinition: the nth momentwhereBoundarysegment1D graphExample of moment:The first moment = meanThe second moment = varianceRegional Descriptors Purpose: to describe regions or “areas” 1. Some simple regional descriptors- area of the region- length of the bou

25、ndary (perimeter) of the region- Compactnesswhere A(R) and P(R) = area and perimeter of region R2. Topological Descriptors3. Texture4. Moments of 2D FunctionsExample: a circle is the most compact shape with C = 1/4pExample: Regional Descriptors (Images from Rafael C. Gonzalez and Richard E. Wood, Di

26、gital Image Processing, 2nd Edition.White pixels represent “l(fā)ight of the cities” % of white pixelsRegion no. compared to the total white pixels 20.4% 64.0% 4.9% 10.7%Infrared image of America at nightTopological Descriptors (Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processin

27、g, 2nd Edition.Use to describe holes and connected components of the regionEuler number (E):C = the number of connected componentsH = the number of holesTopological Descriptors (cont.) (Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.E = -1E = 0Euler Formula

28、V = the number of verticesQ = the number of edgesF = the number of facesE = -2Example: Topological Descriptors (Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.Original image:Infrared imageOf Washington D.C. areaAfter intensityThresholding(1591 connectedcomp

29、onents with 39 holes)Euler no. = 1552The largestconnectedarea (8479 Pixels)(Hudson river)After thinningTexture Descriptors (Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.Purpose: to describe “texture” of the region.Examples: optical microscope images:Super

30、conductor(smooth texture)Cholesterol(coarse texture)Microprocessor(regular texture)ABC(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.Statistical Approaches for Texture Descriptors We can use statistical moments computed from an image histogram:wherez = int

31、ensityp(z) = PDF or histogram of zExample: The 2nd moment = variance measure “smoothness” The 3rd moment measure “skewness” The 4th moment measure “uniformity” (flatness)ABCDivide into areasby anglesFourier Approach for Texture Descriptor OriginalimageFouriercoefficientimageFFT2D+FFTSHIFTSum all pix

32、elsin each areaDivide into areasby radiusSum all pixelsin each areaConcept: convert 2D spectrum into 1D graphsFourier Approach for Texture Descriptor (Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.Originalimage2D Spectrum(Fourier Tr.)S(r)S(q)AnotherimageAn

33、other S(q)Moments of Two-D Functions The moment of order p + qThe central moments of order p + qInvariant Moments of Two-D Functions whereThe normalized central moments of order p + qInvariant moments: independent of rotation, translation, scaling, and reflectionExample: Invariant Moments of Two-D F

34、unctions (Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.1. Original image2. Half size3. Mirrored4. Rotated 2 degree5. Rotated 45 degree(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.Invariant moments of images in

35、 the previous slideExample: Invariant Moments of Two-D Functions Invariant moments are independent of rotation, translation,scaling, and reflectionPrincipal Components for Description Purpose: to reduce dimensionality of a vector image while maintaining information as much as possible.LetMean:Covari

36、ance matrixHotelling transformation LetThen we getandThen elements of are uncorrelated. The component of y with the largest l is called the principal component. Where A is created from eigenvectors of Cx as followsRow 1 contain the 1st eigenvector with the largest eigenvalue.Row 2 contain the 2nd eigenvector with the 2nd largest eigenvalue.Eigenvector and Eigenvalue Eigenvector and eigenvalue of Matrix C are defined asLet C be a matrix of size NxN and e be a vector of size Nx1.IfWhere l is a constantWe call e as an eigenvector and l as eigenvalue of CExample: Prin