冈萨版数字图像处理—双语课程复习.pptx

A set of pixels all of which are 4-connected to each other is called a 4-component;if all the pixels are 8-connected the set is an 8-component.4-component4-componentOnly one 8-component but two 4-component8-componentIllustration of different connected components1.The Euclidean distance between p and q is defined as:Different ways of measuring distanceUsing this method,the pixels having a distance less than or equal to some value r from(x,y)are the points contained in a disk of radius r centered at(x,y).pq2.The D4 distance(also called city block distance)between p and q is defined as:Using this method,the pixels having a D4 distance from(x,y)less than or equal to some value r form a diamond centered at(x,y).For example,the pixels with D4 distance 2 from(x,y)form the following contours of constant distance:The pixels with D4=1 are the 4-neighbors of(x,y).2211221022212D4 distanceDifferent ways of measuring distance cont3.The D8 distance(also called chessboard distance)between p and q is defined as:D8(p,q)=max(x-s,y-t)2222221112210122111222222D8 distanceDifferent ways of measuring distance contThe pixels with D8=1 are the 8-neighbors of(x,y).p2pp1p4p3Assume that p,p2,and p4 have value 1 and that p1 and p3 can have a value 0 or 1.For V=1,solve for Dm distance between p and p4.Solution:If p1 and p3 are 0,then Dm is 2.If p1 is 1,p3 are 0,then Dm becomes 3.Similarly,if p3 is 1 and p1 is 0,Dm also is 3.Finally,if both p1 and p3 are 1,Dm is 4.Example to illustrate finding Dm distanceContrast stretching(对比拉伸)Thresholding(二值化)Transformation functions=T(r)Characteristics of Gray-level transformation functionsS depends on only one pixel value r for calculation.This is called“point processing”Illustration of histogram equalization4x4 image Gray scale=0,9histogram0112233445566789No.of pixelsGray level233242433235242491609s x 9No.of pixelsGray Level(j)99998.486.163.330000161616161511600000145600876543210Perform histogram equalizationOutput image Gray scale=0,9Equalized histogram0112233445566789No.of pixels3663838663693838Results after histogram equalization 255 194 157 103 15 59 116 202 239 90 155 5 235 234 207 124 209 188 105 3 227 113 45 228 35255=11111111235=11101011188=10111100 155=10011011124=01111100 90 =01011010Bit-plane 7 imageBit-plane 2 image111100111000A simple bit-plane exampleMoving window example:find the minimum 242 116 235 105 35 4 59 5 188 228 52 190 155 209 45 15 51 113 124 113 103 90 154 238 227 157 239 207 69 119 194 202 234 3 51 107 242 242 116 235 105 35 4 4 242 242 116 235 105 35 4 4 59 59 5 188 228 52 190 190 155 155 209 45 15 51 113 113 124 124 113 103 90 154 238 238 227 227 157 239 207 69 119 119 194 194 202 234 3 51 107 107 194 194 202 234 3 51 107 107If moving window size is m x n,then the padded row and column should be(m-1)/2 and(n-1)/2 respectively.Original imagePadded image17241815235714164613202210121921311182529111121111910677101111131161113202210121921311182529Original imagemaskFiltered image10Illustration of a weighted average filterIllustration of Median filterDefinition:highlight fine detail in an image or to enhance detail that has been blurred.It is the opposite of averaging.Basic thinking:since averaging is analogous to integration,it is logic to conclude that sharpening could be accomplished by spatial differentiation.Image differentiation enhances edges and other discontinuities(such as noise)and deemphasizes areas with slowly varying gray-level values.Sharpening spatial filters(锐化滤波器)Implementing the Fourier transformProperties of Fourier transform(review)1.Translation(位移性质)Application of translation propertyWhen u0=M/2 and v0=N/2,it follows thatIn this casesimilarlyThe discrete Fourier transformcan be expressed in the separable formSeparabilityPeriodicityThe discrete Fourier transform has the following periodicity properties:F(u,v)=F(u+M,v)=F(u,v+N)=F(u+M,v+N)The inverse transform also is periodic:f(x,y)=f(x+M,y)=f(x,y+N)=f(x+M,y+N)The idea of conjugate symmetry was introduced in previous section,and is repeated here for convenience:F(u,v)=F*(-u,-v)The spectrum also is symmetric about the origin:Conjugate symmetryComponents characteristicsThe illumination component of an image generally is characterized by slow special variations,while the reflectance component tends to vary abruptly,particularly at the junctions of dissimilar objects.The above characteristics lead to associating the low frequencies of the Fourier transform of the logarithm of an image with illumination and the high frequencies with reflectance.The need for padding(补零)Some important facts that need special attention:1.For DFT,the periodicity is a mathematical by-product of the way in which the discrete Fourier transform pair is defined.Periodicity is part of the process,and it cannot be ignored.2.If periodicity issue is not handled properly,it will give incorrect results of some missing data.3.The following example shows details of need for padding.Padding of 2-D functionsTwo images f(x,y)and h(x,y)of sizes AB and CD,with period P in the x-direction and Q in the y-direction.To avoid wraparound error,we need to properly choose P and Q according to following principle:P A+C1 and Q B+D1The periodic sequences are formed by extending f(x,y)and h(x,y)as follows:fe(x,y)=f(x,y)0 x A1 and 0 y B1 0A x P or B y Q he(x,y)=h(x,y)0 x C1 and 0 y D1 0C x P or D y QPadding rulesEstimating the degradation functionThere are three principal ways to estimate the degradation function for use in image restoration:1.Observation2.Experimentation3.Mathematical modelingThe process of restoring an image by using a degradation function that has been estimated in some way sometimes is called blind deconvolution,due to the fact that the true degradation function is seldom known completely.In order to reduce the effect of noise in our observation,we would look for areas of strong signal content in the degraded image,so(x,y)is ignored.Using sample gray levels of the object and background,we can construct an unblurred subimage.Let the observed subimage be denoted by gs(x,y),and the constructed subimage be denoted byThen we getWe can apply this function to the whole image.Estimate H(u,v)for subimage1.Using an image acquiring device to get a similar degraded image by adjusting system parameter settings.2.Let a bright dot of light passing through the above system with the same parameter settings.Then we obtained a degraded image G(u,v)to impulse response.It follows thatwhich is the method used to determine PSF.Steps of experimentationEstimation by modeling(建模)In situations where degradation is caused by bad environmental conditions,estimation by experimentation is difficult to implement.Modeling will be a good way to solve the problem.There are standard models already constructed to model real world problems.For example,the Gaussian LPF is used sometimes to model mild,uniform blurring.We just need to identify the degradation and choose the right model.Another major approach in modeling is to derive a mathematical model starting from basic principles.We will know the detail from an example.Definition of Inverse filtering(逆滤波)Recall the image degradation model:If we divide G(u,v)by H(u,v)to get an estimate of F(u,v),then we get:This is called direct inverse filtering.Problems:1)F(u,v)is a random function whose Fourier transform is not known.2)If degradation function H(u,v)has zero or very small values,then the ratio N(u,v)/H(u,v)could easily dominate the estimate F(u,v).Solutions:from chapter 4,we already know that H(0,0)is equal to the average value of h(x,y)and this is usually the highest value of H(u,v)in the frequency domain.Thus by limiting the analysis to frequencies near the origin,we reduce the probability of encountering zero values.Solving inverse filtering problemsFrom the defining equation,we can derive the estimate in frequency domain such that it makes the error minimum.Note that if the noise is zero,then the noise power spectrum vanishes and the Wiener filter reduces to the inverse filter.(Wiener)filtering Frequency domain expressionSolution to constrained optimizationThe frequency domain solution to this optimization problem is given by the expressionwhere is a parameter that must be adjusted manually so that the constraint is satisfied,and P(u,v)is the Fourier transform of the functionwhich is the Laplacian operator.Note that the above equation reduces to inverse filtering if is zero.Ways to find the coefficients a,b,c,dThe four coefficients are easily determined from the four equations in four unknowns that can be written using the four known neighbors of(x,y).(x,y)(x4,y4)(x1,y1)(x2,y2)(x3,y3)v(x1,y1)=ax1+by1+cx1y1+dv(x2,y2)=ax2+by2+cx2y2+dv(x3,y3)=ax3+by3+cx3y3+dv(x4,y4)=ax4+by4+cx4y4+dx2=x1;y3=y1;x4=x3;y4=y2;Data compression is achieved when one or more of these redundancies are reduced or eliminated.Types of redundancyIn digital image compression,we discuss three basic data redundancies:1.Coding redundancy;2.Interpixel redundancy;3.Psychovisual redundancy.Illustration of variable-length coding不等长编码Illustration of variable-length coding contObjective:When pr(rk)is large,l2(rk)should be short,when pr(rk)is small,l2(rk)should be long.Psychovisual redundancy(视觉冗余)The human eye does not respond with equal sensitivity to all visual information,certain information simply has less relative importance than other information in normal visual processing.This information is said to be psychovisually redundant.It can be eliminated without significantly impairing the quality of image perception.The elimination of psychovisually redundant data results in a loss of quantitative information,so it is commonly referred to as quantization.It is an irreversible operation(visual information is lost),quantization results in lossy data compression.Characteristics of quantizationThe source encoder and decoderMapper is designed to reduce interpixel redundancies.(eg.Run-length coding).Quantizer reduces psychovisual redundancies,this operation is irreversible.Symbol encoder reduces coding redundancy,this operation is reversible.Three part of the source encoderFor an information source producing J possible source symbols a1,a2,aj,each with probability P(aj),then the average information per source output obtained from the source z,denoted H(z),isH(z)is called the uncertainty or entropy of the source.The entropy(熵)of the sourceUsing information theoryExample:compute the entropy of the following 8-bit gray level image of size 48.Method#1:view each pixel with equal probability of generating numbers from 0 to 255.Entropy per pixel is computed from formula:The total entropy is:Meaning:this particular image is but one of 2256(1077)equally probable 48 images that can be produced by the source.Huffman coding and decodingThe average length of this code is:Lavg=(0.4)(1)+(0.3)(2)+(0.1)(3)+(0.1)(4)+(0.06)(5)+(0.04)(5)=2.2 bits/symbolThe entropy of the source is:H(z)=-0.4log2(0.4)-0.3log2(0.3)-20.1log2(0.1)-0.06log2(0.06)-0.04log2(0.04)=2.1435Huffman code efficiency is:Huffman decodingHuffman code is an instantaneous uniquely decodable block code.The encoded symbols can be decoded by examining the individual symbols of the string in a left to right manner.For example,decoding the encoded string 010100111100 reveal that the first valid code word is 01010,which is the code for symbol a3.The next valid code is 011,which is for symbol a1.Continuing in this manner reveals the completely decoded message to be a3a1a2a2a6.Arithmetic coding contSource A contains a1 a2 a3 a4,p(a1)=0.2;p(a2)=0.2;p(a3)=0.4;p(a4)=0.2Any number in this range represents the message a1a2a3a3a4.For example,0.068 can be used to do so.Result:The entropy H(z)=0.58,a 5-symbol message reduces to 068,that is 3 symbols,this translates to 3/5=0.6 decimal digits per source symbol,which is close to the entropy.Illustration of Arithmetic decoding Given:pA=pB=0.25,pC=0.2,pD=pE=0.15Decode the number 0.386 How?By extracting and coding only the new information in each pixel;New information:the difference between actual and predicted value of that pixel.Lossless predictive coding Predictors in encoder and decoder are the same.Various local,global and adaptive methods can be used to generate the prediction.Lossless predictive coding modelCode only the predicted error.Linear predictor is common:Previous pixels are used to estimate the value of the current pixel.The previous pixels could be on the same row(column)with the current pixel(1-D prediction)or around the current pixel(2-D)General coding methodLossy predictive codingBecause the prediction at the decoder and encoder should be the same.A quantizer is added,nearest integer function is absorbed.Prediction error is within a limited range of outputs Predictor input has to be modified This closed loop configuration will prevent error built up at the decoder output.The output of the decoder is also the same asDelta modulation(DM)exampleThe predictor and quantizer are defined asNote the two distortions:1)granular noise;2)slope overload初始值初始化 too large too smallgranular noiseslope overloadrough surface;blurred edges;Decoder output figure8_22demo.mBasic approach to transform codingTwo dimensional matrix form of WHT and its inverseKronecker product直积、张量积A Hadamard matrix is a symmetric matrix whose elements are+1 and-1.WHTN can be generated using Matlab function hadamard(n)Illustration of Kronecker productReconstruction error vs.subimage sizeFor each transformed subimage,truncating 75%of the resulting coefficient,and taking the inverse transform of the truncated arrays Different ways of truncating coefficientsIn most transform coding systems,the retained coefficients are selected on the basis of maximum variance,called zonal coding,or on the basis of maximum magnitude,called threshold coding.The overall process of truncating,quantizing,and coding the coefficients of a transformed subimage is commonly called bit allocation.Bit allocation determines the number of bits to be used to code each coefficient based on its importance.PreviewSegmentation is to subdivide an image into its constituent regions or objects.Segmentation should stop when the objects of interest in an application have been isolated.Principal approachesSegmentation algorithms generally are based on one of two basic properties of intensity valuesdiscontinuity:to partition an image based on abrupt changes in intensity(such as edges)similarity:to partition an image into regions that are similar according to a set of predefined criteria.Line DetectionHorizontal mask will result with max response when a line passed through the middle row of the mask with a constant background.the similar idea is used with other masks.note:the preferred direction of each mask is weighted with a larger coefficient(i.e.,2)than other possible directions.Line DetectionApply every masks on the imagelet R1,R2,R3,R4 denotes the response of the horizontal,+45 degree,vertical and-45 degree masks,respectively.if,at a certain point in the image|Ri|Rj