Digital Image Processing - UGent

1 Digital Image ProcessingDr. ir. Aleksandra PizuricaProf. Dr. Ir. Wilfried Philips8 February Tel: 09 en InformatieverwerkingUNIVERSITEIT GENTT elecommunicatie en InformatieverwerkingUNIVERSITEIT GENTI mage : 6/2/2007 A. Pizurica, Universiteit Gent, 2006-2007 Chain Chain codes represent a boundary by a connected sequence of straight-line segments of specified length and direction. Typically this representation is based on a 4- or 8-connectivity The direction of each segment is coded by numbers and the resulting chain code is a sequence of numbers01234-connected graph03003332123211210chain code:030033321232112108-connected : 6/2/2007 A. Pizurica, Universiteit Gent, Advantage:a compressed contour representation Disadvantages: chain code depends on the starting point can be solved: treat the chain code as a circular sequence and redefining the starting point so that the resulting sequence of numbers is the smallest possible integer Operations such as scaling and rotation result in different contours that in practice cannot be normalized(due to a finite grid) and hence in different chain codes.

2 This problem cannot be completely solved but its effect can be reduced by resampling to a coarser grid before chain coding and by a proper orientation of the resampling gridultrasound imageSick regions( delineated by a doctor)Can be interesting in cases where a number of contours need to be stored, like in medical follow-up examinations : 6/2/2007 A. Pizurica, Universiteit Gent, codesa Digital contour with resampling grid superimposedresampledchain code for 4-connectivitychain code for : 6/2/2007 A. Pizurica, Universiteit Gent, 2006-2007 Poligonal Digital boundaries carry information which may be superfluous for certain applications. Boundary approximationscan be sufficient in such cases. Linear piecewise (polygonal) approximations are the most frequently used ones These approximations produce a polygon which closely resembles original boundary line We will illustrate two examples of polygonal approximations called perimeter polygons and polygonal approximation by : 6/2/2007 A.

3 Pizurica, Universiteit Gent, 2006-2007 Minimum perimeter polygonsOne type of polygonal approximation is minimum perimeter polygonsThink of the object boundary rubber band and imagine it is allowed to shrink until it is : 6/2/2007 A. Pizurica, Universiteit Gent, 2006-2007 Polygonal approximation by 1x1xNy2y3step 2x1xNy2y3step 3x1xNy2y3y4step 4 The optimalpiecewise linear approximation means estimating the polygon vertices in such a way that total error is minimized. This can be a non-trivialand computationally intensive optimization approach! l In practice splitting techniques, which are fast are often used Splitting techniques divide a curve segment recursively until each curve segment is approximated with a linear segment with acceptable error. Mean square error or maximal error is used as a criterion;Furthest point from the : 6/2/2007 A.

4 Pizurica, Universiteit Gent, Polygonal approximation by splittingA practical splittingprocedure can be:step 1 Look for the two points that are furthest apart (Aand B) and join them by a line segment ABstep 2 Look for the boundary points that are furthest apart from AB inboth parts of the boundary (Cand D)step 3connect the points by line segments (AC, CB, BD, DA). For each segment check if the distance between its points and the corresponding points of the true boundary is smaller than a threshold. If yes, stop, otherwise subdivide the segment : 6/2/2007 A. Pizurica, Universiteit Gent, 2006-2007 SignaturesA signature is a 1-D functional representation of a : 6/2/2007 A. Pizurica, Universiteit Gent, 2006-2007 Skeletons A medial axisor skeletonrepresentation is a popular tool in object recognition.

5 Skeletons provide a compact and often highly intuitive representation. Shape skeletons have been used , , in object recognition andrepresentation, industrial inspection ( , inspection of printed circuit board) and in medical imaging. The skeleton of a region is often defined via the medial axis transformation (MAT).The MAT of a region Rwith border Bis as follows: for each point pof R, we find its closest neighbor in B. If phas more then one such points, it is said to belong to the medial axis (skeleton) of R. Boundary : 6/2/2007 A. Pizurica, Universiteit Gent, 2006-2007 Fourier descriptors (FDs)tz(t) = x(t)+jy(t)jyxFFTmagnitude spectrumA closed curve can be described by the curve coordinates x(t), y(t). The waveformes x(t), y(t)are periodic with period 2 . The waveforms can be sampled and combined to produce a complex periodic waveform withperiod Nz(n)=x(n)+jy(n) n=0,1.

6 ,N-1 The Fourier transform coefficients of this signal are the Fourier descriptorsof the curve = =102exp)()(NnNnkjnzkZ Matlab demo : 6/2/2007 A. Pizurica, Universiteit Gent, 2006-2007 Some properties of Fourier descriptorsZ(0)represents the center of gravityof the curve z(n) = x(n)+jy(n)jyxFFT = =102exp)()(NnNnkjnzkZ |Z(k)|kTranslationzt(n) = z(n)+z0, z0= x0+jy0 affects only Z(0): Zt(0)=Z(0)+z0 Rotationzr(n) = z(n)ej phase shiftof the coefficients Zr(0)=Z(k) ej Scalingzs(n) = az(n) scalingthe coeffs. by same amount Zs(0)=aZ(k) Change starting pointzt(n) = z(n1-n0) modulationNknjtekZkZ02)()( =The coefficient magnitude |Z(k)|is rotation invariant and the magnitude of the N-1 coefficients |Z(k)|, k=1,..,N-1is translation invariant as well. () = =10221)()(NkkZkZECan be used as error measurefor matching curves z1(t) and z2(t)Matlab demo : 6/2/2007 A.

7 Pizurica, Universiteit Gent, 2006-2007 Example: Shape reconstruction from FDsSquare: 84 pointsfirst 2 FDsfirst 8 FDsfirst 16 FDsfirst 56 FDsfirst 64 FDsfirst 72 FDsfirst 81 FDsall 84 FDs050100050100150200250 Magnitude spectrumMatlab demo : 6/2/2007 A. Pizurica, Universiteit Gent, 2006-2007 Statistical shape of a boundary can now be described by simple moments such as mean, variance,.. The n-th moment of vabout its mean mis:connect end points of the boundary segment and rotate)(0iAiivpvm ==Using only first few moments is usually sufficient to differentiate between (clearly distinct) different shapesp(vi)is the probability of occurrence of value vi. These are estimated by the values of the normalized histogram (normalized = area under is 1)normalized histogramp(vi)viviidivide inAamplitude intervals)()()(10iKininvpmvv = = : 6/2/2007 A.

8 Pizurica, Universiteit Gent, momentsAn alternative approach is to normalize (scale) the samples after rotation such that the total area equals 1 and to treat this as a histogram. Connect end points of the boundary segment and rotateg(r)r)()()(10iKininrgmrv = = )(10iKiirgrm ==The moments are now defined aswith the mean Now Kis the number of points on the boundary, and the n-th moment n(r)is directly related to the shape of g(r).The second moment measures the spread of the curve and the third moment measures its : 6/2/2007 A. Pizurica, Universiteit Gent, 2006-2007 Topological descriptorsOne topological descriptor is Euler numberE, defined in terms of the number of holes H and the number of the connected components C as: E=C-HTopological properties are used for higher-level and global descriptions of regions in the Image .

9 An example of a topological property is the number of holes or the number of connected components in the region with two holesA region with three connected componentsEuler number=0 Euler number= : 6/2/2007 A. Pizurica, Universiteit Gent, 2006-2007An example of an Image representationoriginal imageThresholded imageThe largest connected componentskeleton 2002 R. C. Gonzalez & R. E. WoodsTexture : 6/2/2007 A. Pizurica, Universiteit Gent, 2006-2007 Texture descriptorssmooth texturecoarse textureregular texture 2002 R. C. Gonzalez & R. E. : 6/2/2007 A. Pizurica, Universiteit Gent, 2006-2007 Statistical texture of the simplest approaches is using statistical moments of the gray level histogram. Let z denote gray levels and p(zi),I=0,1,..,L-1 the corresponding histogram, where L is the number of distinct gray levels.

10 The n-th moment of zabout the mean m is)()()(10iLininzpmzz = = )(10iLiizpzm ==Note .0110== andThe second moment (the variance 2(z)= 2(z)) is often used in texture description. The third moment 3(z)describes the skewness (asymmetry) of the histogram and the fourth moment 4(z)its relative flatness. Other useful texture descriptors based on the histogram include a measure of uniformity average entropy ==102)(LiizpU)(log)(210iLiizzpe = = : 6/2/2007 A. Pizurica, Universiteit Gent, Statistical texture descriptorsHistogram based descriptors are limited in the sense that they cannot express information about relative positions of pixel values with respect to each other. One approach to solve this is to use a two-dimensional histogram called co-occurrence matrix. The co-occurrence matrix counts the number of grey value transitions in a given direction and at a given distance d0 0 0 1 21 1 0 1 12 2 1 0 01 1 0 2 00 0 1 0 1 Example: =111134134 CCo-occurrence matrix for d=1, horizontal rightSome useful descriptors derived from the co-occurrence matrixMaximimum probability contrast uniformityentropy)(max,,jijic ijjicji,)( ijjic2, ijjijicc,2, : 6/2/2007 A.