资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,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,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,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,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,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).,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,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”,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,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,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,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,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,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,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,(,锐化滤波器,),Implementing the Fourier transform,Properties of Fourier transform (review),1. Translation (,位移性质,),Application of translation property,When u,0,= M/2 and v,0,= N/2, it follows that,In this case,similarly,The discrete Fourier transform,can be expressed in the separable form,Separability,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),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,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.,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 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,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,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.,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,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,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.,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 problems,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,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.,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;,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.,Illustration of,variable-length coding,不等长编码,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.,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 quantization,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,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,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.,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 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,.,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.,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, 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 model,Code 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 method,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,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,Basic approach to transform coding,Two dimensional matrix form of WHT and its inverse,Kronecker product,直积、张量积,A Hadamard matrix is a symmetric matrix whose elements are +1 and -1.,WHT,N,can be generated using Matlab function,hadamard(n),Illustration of Kronecker product,Reconstruction error vs. subimage size,For each transformed subimage,truncating 75% of the resulting coefficient,and taking the inverse transform of the truncated arrays,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.,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.,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.,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 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.,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.,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.,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:,-plane,problem of using equation y = ax + b is that value of,a,is infinite for a vertical line.,To avoid the problem, use normal line equation x cos,+ y sin,=, to represent a line instead.,vertical line has = 90,with equals to the positive y-intercept or = -90,with equals to the negative y-intercept.,x cos,+ y sin,=,-plane,=,90,measured with respect to x-axis,where D is the distance between corners in the image,Illustration of Hough Transformation,Local Processing,analyze the characteristics of pixels in a small neighborhood (say, 33, 55) about every edge pixels (x,y) in an image.,all points that are similar according to a set of predefined criteria are linked, forming an edge of pixels that share those criteria.,Criteria,the strength of the response of the gradient operator used to produce the edge pixel,an edge pixel with coordinates (x,0,y,0,) in a predefined neighborhood of (x,y) is similar in magnitude to the pixel at (x,y) if,|,f(x,y) - f,(x,0,y,0,) |,E,Criteria,the direction of the gradient vector,an edge pixel with coordinates (x,0,y,0,) in a predefined neighborhood of (x,y) is similar in angle to the pixel at (x,y) if,|,(x,y) - ,(x,0,y,0,) |,A,Criteria,A point in the predefined neighborhood of (x,y) is linked to the pixel at (x,y) if,both magnitude and direction criteria are satified.,the process is repeated at every location in the image.,a record must be kept.,simply by assigning a different gray level to each set of linked edge pixels.,Probability of erroneously classifying,background,object,错把背景像素当成目标像素的概率,错把目标像素当成背景像素的概率,Region-Based Segmentation,Basic Formulation,P(R,i,) is a logical predicate property defined over the points in set R,i,ex. P(R,i,) = TRUE if all pixel in R,i,have the same gray level,Region Growing,start with a set of “seed” points,growing by appending to each seed those neighbors that have similar properties such as specific ranges of gray level,Region Grow
展开阅读全文