资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Due to processing, storage, and sampling hardware considerations, the number of gray levels typically is an integer power of 2:,L = 2,k,k is called the bit depth.,Storage requirement calculation:,The number of,bits, b, required to store a digitized image is:,b = MNk,When M = N, this equation becomes:,b = N,2,k,The requirement of the gray level value L,Due to processing, storage, an,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-component,4-component,Only one 8-component but two 4-component,8-component,Illustration of different connected components,A set of pixels all of which a,1. The,Euclidean distance,between p and q is defined as:,Different ways of measuring distance,Using 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).,p,q,1. The Euclidean distance betw,2. The,D,4,distance (also called city block distance),between p and q is defined as:,Using this method, the pixels having a D,4,distance from (x,y) less than or equal to some value r form a diamond centered at (x,y). For example, the pixels with D,4,distance 2 from (x,y) form the following contours of constant distance:,The pixels with D,4,= 1 are the 4-neighbors of (x,y).,2,2,1,1,2,2,1,0,2,2,2,1,2,D,4,distance,Different ways of measuring distance cont,2. The D4 distance (also calle,3. The,D,8,distance (also called chessboard distance),between p and q is defined as:,D,8,(p,q) = max( x-s , y-t ),2,2,2,2,2,2,1,1,1,2,2,1,0,1,2,2,1,1,1,2,2,2,2,2,2,D,8,distance,Different ways of measuring distance cont,The pixels with D,8,= 1 are the 8-neighbors of (x,y).,3. The D8 distance (also calle,p,2,p,p,1,p,4,p,3,Assume that p, p,2, and p,4,have value 1 and that p,1,and p,3,can have a value 0 or 1.,For,V = 1, solve for,D,m,distance between p and p,4.,Solution:,If p,1,and p,3,are 0, then,D,m,is,2,.,If p,1,is 1, p,3,are 0, then,D,m,becomes,3,.,Similarly, if p,3,is 1 and p,1,is 0,D,m,also is,3,.,Finally, if both p,1,and p,3,are 1,D,m,is,4,.,Example to illustrate finding D,m,distance,p2pp1p4p3Assume that p, p2, an,Contrast stretching (,对比拉伸),Thresholding (,二值化),Transformation function,s,=,T(r),Characteristics of,Gray-level transformation functions,S,depends on only,one pixel value,r,for calculation.,This is called,“point processing”,Contrast stretching (对比拉伸)Thre,Illustration of histogram equalization,4x4 image,Gray scale = 0,9,histogram,0,1,1,2,2,3,3,4,4,5,5,6,6,7,8,9,No. of pixels,Gray level,2,3,3,2,4,2,4,3,3,2,3,5,2,4,2,4,Illustration of histogram equa,9,16,0,9,s,x,9,No. of pixels,Gray,Level(j),9,9,9,9,8.4,8,6.1,6,3.3,3,0,0,0,0,16,16,16,16,15,11,6,0,0,0,0,0,1,4,5,6,0,0,8,7,6,5,4,3,2,1,0,Perform histogram equalization,91609s x 9No. of pixelsGray 99,Output image,Gray scale = 0,9,Equalized histogram,0,1,1,2,2,3,3,4,4,5,5,6,6,7,8,9,No. of pixels,3,6,6,3,8,3,8,6,6,3,6,9,3,8,3,8,Results after histogram equalization,Output image Gray scale = 0,9,255 194 157 103 15,59 116 202 239 90,155 5 235 234 207,124 209 188 105 3,227 113 45 228 35,255=11111111235=11101011,188=10111100155=10011011,124=0111110090 =01011010,Bit-plane 7 image,Bit-plane 2 image,1,1,1,1,0,0,1,1,1,0,0,0,A simple bit-plane example,255 194 157 103 15,Moving 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 107,If moving window size is m x n, then the padded row and column should be (m-1)/2 and (n-1)/2 respectively.,Original image,Padded image,Moving window example: find th,17,24,1,8,15,23,5,7,14,16,4,6,13,20,22,10,12,19,21,3,11,18,25,2,9,1,1,1,1,2,1,1,1,1,9,10,6,7,7,10,11,11,13,11,6,11,13,20,22,10,12,19,21,3,11,18,25,2,9,Original image,mask,Filtered image,10,Illustration of a weighted average filter,172418152357141646132022101219,Illustration of Median filter,Illustration of Median filter,Definition:,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,(,锐化滤波器,),Definition: highlight fine det,Implementing the Fourier transform,Properties of Fourier transform (review),1. Translation (,位移性质,),Implementing the Fourier trans,Application of translation property,When u,0,= M/2 and v,0,= N/2, it follows that,In this case,similarly,Application of translation pro,The discrete Fourier transform,can be expressed in the separable form,Separability,The discrete Fourier transform,Periodicity,The 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),PeriodicityThe discrete Fourie,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 symmetry,The idea of conjugate symmetry,Components characteristics,The,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.,Components characteristicsThe,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.,The need for padding (补零)Some,Padding of 2-D functions,Two 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+D1,Padding of 2-D functionsTwo im,The periodic sequences are formed by extending f(x,y) and h(x,y) as follows:,f,e,(x,y),=,f(x,y)0 x A1 and 0 y B1,0A x P or B y Q,h,e,(x,y) =,h(x,y)0 x C1 and 0 y D1,0C x P or D y Q,Padding rules,The periodic sequences are for,Estimating the degradation function,There are three principal ways to estimate the degradation function for use in image restoration:,Observation,Experimentation,Mathematical modeling,The 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.,Estimating the degradation fun,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,g,s,(x,y),and the constructed subimage be denoted by,Then we get,We can apply this function to the whole image.,Estimate H(u,v) for subimage,In order to reduce the effect,1. 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 that,which is the method used to determine,PSF,.,Steps of experimentation,1. Using an image acquiring de,Estimation 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.,Estimation by modeling (建模)In,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.,Definition of Inverse filterin,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 problems,Problems: 1) F(u,v) is a rando,From 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 expression,From the defining equation, we,Solution to constrained optimization,The frequency domain solution to this optimization problem is given by the expression,where,is a parameter that,must be adjusted,manually,so that the constraint is satisfied, and,P(u,v),is the Fourier transform of the function,which is the Laplacian operator. Note that the above equation reduces to inverse filtering if,is zero.,Solution to constrained optimi,Ways to find the coefficients,a,b,c,d,The 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,),(,x,4,y,4),(,x,1,y,1),(,x,2,y,2),(,x,3,y,3),v(x1,y1) =,a,x1 +,b,y1 +,c,x1y1 +,d,v(x2,y2) =,a,x2 +,b,y2 +,c,x2y2 +,d,v(x3,y3) =,a,x3 +,b,y3 +,c,x3y3 +,d,v(x4,y4) =,a,x4 +,b,y4 +,c,x4y4 +,d,x2=x1; y3=y1;,x4=x3; y4=y2;,Ways to find the coefficients,Data compression is achieved when one or more of these redundancies are reduced or eliminated.,Types of redundancy,In digital image compression, we discuss three basic data redundancies:,1. Coding redundancy;,2. Interpixel redundancy;,3. Psychovisual redundancy.,Data compression is achieved w,Illustration of,variable-length coding,不等长编码,Illustration of variable-lengt,Illustration of variable-length coding cont,Objective:,When,p,r,(r,k,),is large,l,2,(r,k,),should be short, when,p,r,(r,k,),is small,l,2,(r,k,),should be long.,Illustration of variable-lengt,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.,Psychovisual redundancy (视觉冗余),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 quantization,The elimination of psychovisua,The source encoder and decoder,The source encoder and decoder,Mapper,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 encoder,Mapper is designed to reduce i,For an information source producing J possible source symbols a,1,a,2,a,j, each with probability P(a,j,), then,the average information per source output,obtained from the source,z, denoted,H(z), is,H(,z,),is called the uncertainty or,entropy,of the source.,The,entropy,(,熵,),of the source,For an information source prod,Using information theory,Example: 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 2,256,(10,77,) equally probable 48 images that can be produced by the source.,Using information theoryExampl,Huffman coding and decoding,The average length of this code is:,L,avg,= (0.4)(1) + (0.3)(2) + (0.1)(3) + (0.1)(4) + (0.06)(5) + (0.04)(5) = 2.2 bits/symbol,The entropy of the source is:,H(,z,) = -0.4log,2,(0.4)-0.3log,2,(0.3)-20.1log,2,(0.1)-0.06log,2,(0.06)-0.04log,2,(0.04) = 2.1435,Huffman code efficiency is:,Huffman coding and decodingThe,Huffman decoding,Huffman 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,a,3,. The next valid code is,011, which is for symbol,a,1,. Continuing in this manner reveals the completely decoded message to be,a,3,a,1,a,2,a,2,a,6,.,Huffman decodingHuffman code i,Arithmetic coding cont,Source A contains a,1,a,2,a,3,a,4, p(a,1,) = 0.2; p(a,2,) = 0.2; p(a,3,) = 0.4; p(a,4,) = 0.2,Any number in this range represents the message a,1,a,2,a,3,a,3,a,4,. 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.,Arithmetic coding contSource,Illustration of Arithmetic decoding,Given: p,A,= p,B,= 0.25, p,C,= 0.2, p,D,= p,E,= 0.15,Decode the number 0.386,Illustration of Arithmetic dec, 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., How? By extracting and codin,Lossless predictive coding model,Code only the predicted error.,Lossless predictive coding mod, 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 method, Linear predictor is common:G,Lossy predictive coding,Because 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 as,Lossy predictive codingBecause,Delta modulation (DM) example,The predictor and quantizer are defined as,Note the two distortions: 1) granular noise;,2) slope overload,初始值,初始化, too large, too small,granular noise,slope overload,rough surface;,blurred edges;,Decoder output,figure8_22demo.m,Delta modulation (DM) exampleT,Basic approach to transform coding,Basic approach to transform co,Two dimensional matrix form of WHT and its inverse,Kronecker product,直积、张量积,A Hadamard matrix is a symmetric matrix whose elements are +1 and -1.,Two dimensional matrix form of,WHT,N,can be generated using Matlab function,hadamard(n),Illustration of Kronecker product,WHTN can be generated using Ma,Reconstruction error vs. subimage size,For each transformed subimage,truncating 75% of the resulting coefficient,and taking the inverse transform of the truncated arrays,Reconstruction error vs. subim,Different ways of truncating coefficients,In 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.,Different ways of truncating c,Preview,Segmentation 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.,PreviewSegmentation is to subd,Principal approaches,Segmentation algorithms generally are based on one of two basic properties of intensity values,discontinuity: 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.,Principal approachesSegmentati,Line Detection,Horizontal 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 DetectionHorizontal mask,Line Detection,Apply every masks on the image,let R,1, R,2, R,3, R,4,denotes the response of the horizontal, +45 degree, vertical and -45 degree masks, respectively.,if, at a certain point in the image,|R,i,| |R,j,|,for all j,i, that point is said to be more likely associated with a line in the direction of mask i.,Line DetectionApply every mask,Gradient Masks,Gradient Masks,Diagonal edges with Prewitt and Sobel masks,Sobel masks have slightly superior noise-suppression characteristics which is an important issue when dealing with derivatives.,Diagonal edges with Prewitt an,Role of Laplacian operator in segmentation,The Laplacian generally is not used in its original form for edge detection for several reasons:,Unacceptably sensitive to noise;,The double edges it produces would complicate segmentation;,Unable to detect edge direction.,The role:,Using its zero crossing property for edge location;,Using it for the complementary purpose of deciding whether a pixel is on the dark or light side.,Role of Laplacian operator in,Laplacian of Gaussian,(LoG),Laplacian combined with smoothing as a precursor to find edges via zero-crossing. Consider the function:,where r,2,= x,2,+y,2, and,is the standard deviation,Convolve this function with an image blurs the image, the larger the,s,the more blur.,Expression of LoG:,Laplacian of Gaussian (LoG)Lap,-plane,problem of using equation y = ax + b is that value of,a,is infinite for a vertical
展开阅读全文