数字图像处理冈萨雷斯英文Chapter 表示与描述.pptx

《数字图像处理冈萨雷斯英文Chapter 表示与描述.pptx》由会员分享，可在线阅读，更多相关《数字图像处理冈萨雷斯英文Chapter 表示与描述.pptx（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、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”W

2、hat 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 dire

3、ction.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 Cha

4、in 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

5、 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

6、)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 rotationalinv

7、ariant.第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 Ima

8、ge 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 Pro

9、cessing,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 Segmen

10、ts 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

11、 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 poin

12、ts 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

13、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

14、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 Processin

15、g,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”p2p9p3p

16、8p7p1p4p6p5LetT(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.

17、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

18、 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 t

19、hat 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

20、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

21、 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 Proces

22、sing,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,2

23、nd 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(I

24、mages 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 M

25、oments 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 mom

26、ent: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 R

27、2.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 th

28、e 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 connect

29、ed 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 vertices

30、Q=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 connectedco

31、mponents 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 micr

32、oscope 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 ca

33、n 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 Descr

34、iptor 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 Descri

35、ptor(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 Mom

36、ents 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 Rafa

37、el 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:Inv

38、ariant 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 m

39、aintaining 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 foll

40、owsRow 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 si

41、ze 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

42、 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 Hote

43、lling 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 Imag

44、e 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 Desc

45、riptors 第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页