数字图像处理冈萨雷斯英文Chapter 表示与描述.pptx
Image Representation and Description?Image 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 memory,faster to be processed-More“ready to be used”What kind of information we can use?-Boundary,shape-Region-Texture-Relation between regions第1页/共49页Shape Representation by Using Chain Codes Shape Representation by Using Chain Codes Chain codes:represent an object boundary by a connected sequence of straight line segments of specified lengthand 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.第2页/共49页Examples of Chain Codes Examples of Chain Codes Object boundary(resampling)Boundaryvertices4-directionalchain code8-directionalchain code(Images from Rafael C.Gonzalez and Richard E.Wood,Digital Image Processing,2nd Edition.第3页/共49页The First Difference of a Chain Codes The First Difference of a Chain Codes Problem of a chain code:a chain code sequence depends on a starting point.Solution:treat 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:1230Example:-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.第4页/共49页Polygon Approximation Polygon Approximation Object boundaryMinimum 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.第5页/共49页Polygon Approximation:Splitting Techniques Polygon Approximation:Splitting Techniques 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.第6页/共49页Distance-Versus-Angle Signatures Distance-Versus-Angle Signatures Represent an 2-D object boundary in term of a 1-D function of radial distance with respect to q.(Images from Rafael C.Gonzalez and Richard E.Wood,Digital Image Processing,2nd Edition.第7页/共49页Boundary Segments Boundary Segments Concept:Partitioning an object boundary by using vertices of a convex hull.Convex hull(gray color)Object boundaryPartitioned boundary(Images from Rafael C.Gonzalez and Richard E.Wood,Digital Image Processing,2nd Edition.第8页/共49页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 points 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!Convex Hull Algorithm Convex Hull Algorithm 第9页/共49页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 Llower10.While Llower contains more than 2 points and the last 3 points in Llower do not make a right turn11.Do delete the middle point 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.)Convex Hull Algorithm(cont.)第10页/共49页Skeletons Skeletons Obtained from thinning or skeletonizing processesMedial axes(dash lines)(Images from Rafael C.Gonzalez and Richard E.Wood,Digital Image Processing,2nd Edition.第11页/共49页Thinning Algorithm 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 at 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)=3第12页/共49页Thinning Algorithm(cont.)Thinning Algorithm(cont.)Step 1.Mark pixels for deletion if the following conditions are true.a)b)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)第13页/共49页Example:Skeletons Obtained from the Thinning Alg.Example:Skeletons Obtained from the Thinning Alg.(Images from Rafael C.Gonzalez and Richard E.Wood,Digital Image Processing,2nd Edition.Skeleton第14页/共49页Boundary Descriptors Boundary Descriptors 1.Simple boundary descriptors:we can use-Length of the boundary-The size of smallest circle or box that can totally enclosing the object2.Shape number3.Fourier descriptor4.Statistical moments第15页/共49页Shape Number Shape 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 Processing,2nd Edition.第16页/共49页Shape Number(cont.)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.第17页/共49页Example:Shape Number 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 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.第18页/共49页Fourier Descriptor Fourier Descriptor Fourier descriptor:view a coordinate(x,y)as a 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 formulaBoundarypoints第19页/共49页Example:Fourier Descriptor Example: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.第20页/共49页Fourier Descriptor Properties Fourier Descriptor Properties(Images from Rafael C.Gonzalez and Richard E.Wood,Digital Image Processing,2nd Edition.Some properties of Fourier descriptors第21页/共49页Statistical Moments Statistical Moments(Images from Rafael C.Gonzalez and Richard E.Wood,Digital Image Processing,2nd Edition.1.Convert a boundary segment into 1D graph2.View a 1D graph as a PDF function3.Compute the nth order moment of the graphDefinition:the nth momentwhereBoundarysegment1D graphExample of moment:The first moment=meanThe second moment=variance第22页/共49页Regional Descriptors Regional Descriptors Purpose:to describe regions or“areas”1.Some simple regional descriptors-area of the region-length of the boundary(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/4p第23页/共49页Example:Regional Descriptors Example:Regional Descriptors(Images from Rafael C.Gonzalez and Richard E.Wood,Digital Image Processing,2nd Edition.White pixels represent“light of the cities”%of white pixelsRegion pared to the total white pixels1 20.4%2 64.0%3 4.9%4 10.7%Infrared image of America at night第24页/共49页Topological Descriptors Topological Descriptors(Images from Rafael C.Gonzalez and Richard E.Wood,Digital Image Processing,2nd Edition.Use to describe holes and connected components of the regionEuler number(E):C=the number of connected componentsH=the number of holes第25页/共49页Topological Descriptors(cont.)Topological Descriptors(cont.)(Images from Rafael C.Gonzalez and Richard E.Wood,Digital Image Processing,2nd Edition.E=-1E=0Euler FormulaV=the number of verticesQ=the number of edgesF=the number of facesE=-2第26页/共49页Example:Topological Descriptors Example: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 connectedcomponents with 39 holes)Euler no.=1552The largestconnectedarea(8479 Pixels)(Hudson river)After thinning第27页/共49页Texture Descriptors Texture 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:Superconductor(smooth texture)Cholesterol(coarse texture)Microprocessor(regular texture)ABC第28页/共49页(Images from Rafael C.Gonzalez and Richard E.Wood,Digital Image Processing,2nd Edition.Statistical Approaches for Texture Descriptors Statistical Approaches for Texture Descriptors We can use statistical moments computed from an image histogram:wherez=intensityp(z)=PDF or histogram of zExample:The 2nd moment=variance measure“smoothness”The 3rd moment measure“skewness”The 4th moment measure“uniformity”(flatness)ABC第29页/共49页Divide into areasby anglesFourier Approach for Texture Descriptor Fourier Approach for Texture Descriptor OriginalimageFouriercoefficientimageFFT2D+FFTSHIFTSum all pixelsin each areaDivide into areasby radiusSum all pixelsin each areaConcept:convert 2D spectrum into 1D graphs第30页/共49页Fourier Approach for Texture Descriptor Fourier 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)AnotherimageAnother S(q)第31页/共49页Moments of Two-D Functions Moments of Two-D Functions The moment of order p+qThe central moments of order p+q第32页/共49页Invariant Moments of Two-D Functions Invariant Moments of Two-D Functions whereThe normalized central moments of order p+qInvariant moments:independent of rotation,translation,scaling,and reflection第33页/共49页Example:Invariant Moments of Two-D Functions Example:Invariant Moments of Two-D Functions(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第34页/共49页(Images from Rafael C.Gonzalez and Richard E.Wood,Digital Image Processing,2nd Edition.Invariant moments of images in the previous slideExample:Invariant Moments of Two-D Functions Example:Invariant Moments of Two-D Functions Invariant moments are independent of rotation,translation,scaling,and reflection第35页/共49页Principal Components for Description Principal Components for Description Purpose:to reduce dimensionality of a vector image while maintaining information as much as possible.LetMean:Covariance matrix第36页/共49页Hotelling transformation Hotelling 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.第37页/共49页Eigenvector and 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 l is a constantWe call e as an eigenvector and l l as eigenvalue of C第38页/共49页Example:Principal ComponentsExample:Principal Components(Images from Rafael C.Gonzalez and Richard E.Wood,Digital Image Processing,2nd Edition.6 spectral imagesfrom an airborneScanner.第39页/共49页(Images from Rafael C.Gonzalez and Richard E.Wood,Digital Image Processing,2nd Edition.Example:Principal Components(cont.)Example:Principal Components(cont.)Component l1 32102 931.43 118.54 83.885 64.006 13.40第40页/共49页Example:Principal Components(cont.)Example:Principal Components(cont.)Original imageAfter Hotelling transform第41页/共49页Principal Components for Description Principal Components for Description(Images from Rafael C.Gonzalez and Richard E.Wood,Digital Image Processing,2nd Edition.第42页/共49页Relational Descriptors Relational Descriptors(Images from Rafael C.Gonzalez and Richard E.Wood,Digital Image Processing,2nd Edition.第43页/共49页Relational Descriptors Relational Descriptors(Images from Rafael C.Gonzalez and Richard E.Wood,Digital Image Processing,2nd Edition.第44页/共49页(Images from Rafael C.Gonzalez and Richard E.Wood,Digital Image Processing,2nd Edition.Relational Descriptors Relational Descriptors 第45页/共49页Relational Descriptors Relational Descriptors(Images from Rafael C.Gonzalez and Richard E.Wood,Digital Image Processing,2nd Edition.第46页/共49页Relational Descriptors Relational Descriptors(Images from Rafael C.Gonzalez and Richard E.Wood,Digital Image Processing,2nd Edition.第47页/共49页Structural Approach for Texture Descriptor Structural Approach for Texture Descriptor(Images from Rafael C.Gonzalez and Richard E.Wood,Digital Image Processing,2nd Edition.第48页/共49页感谢您的观看！第49页/共49页
