1、Image Processing Basic Concepts影像處理基本概念影像處理基本概念主講：周昌民I ma g e P r o c e s s i n g B a s i c C o n c eContentsImages sampling and resolutionManipulationFiltering,geometrical transformationscompression GIF,JPEG,JPEG2000C o n t e n t s I ma g e sSampling and resolutionAn input device(e.g.camera or scan
2、ner)will sample(measure)the colours in a scene at a number of finite points on a 2D rectangle.Resolution can refer to the number of points sampled(e.g.640 by 480)or the size of the dots(e.g.300 dpi).The pixel-depth is related to the number of quantisation levels used for each colour,e.g.24-bit colou
3、rS a mp l i n g a n d r e s o l u t i o n A n i n p uImage ManipulationWhy would we want to manipulate an image?Deficiencies in the imageFocus blur,motion blur,red-eye,poor lighting,noise,.Special effects requiredSepia,painting styles,combining images,.What methods are available?Pixel level processi
4、ngStatistical processingGroup of pixel processingGeometrical transformationsI ma g e Ma n i p u l a t i o n Wh y w o u l d w eImage ManipulationPixel level changesBrightness add an equal value to the R,G and B values of each pixelI ma g e Ma n i p u l a t i o n P i x e l l e v e l Image Manipulation
5、Pixel level changesContrast Multiply the RGB values by some value and reset overall brightnessI ma g e Ma n i p u l a t i o n P i x e l l e v e l Image ManipulationPixel level changesColour balance Vary the R,G and B brightnesses independentlyI ma g e Ma n i p u l a t i o n P i x e l l e v e l Image
6、 ManipulationPixel level changesColour manipulationGrey scale average RGB weighted to human perceptual system:approx.0.4R+0.4G+0.2BGreying out(e.g.disabled button)Blend pixel values with grey:e.g.R=(R+200)/2,G=(G+200)/2,etcI ma g e Ma n i p u l a t i o n P i x e l l e v e l Image ManipulationStatist
7、ical ProcessingHistogram equalisation(automatically adjust contrast)Create a histogram H with one bin for each grey scale allowed e.g.for G grey scalesfor each pixel(x,y),Himage(x,y)+;Create a cummulative histogram HcHc0=H0;for each grey scale g from 1 to G-1,Hcg=Hcg-1+Hc;Hcg is now increasing and H
8、cG-1 equals the number of pixels in the imageRescale Hc to the range of grey scales i.e.Hcg*=G/(width*height);Remap image grey scalesfor each pixel(x,y),image(x,y)=Hcimage(x,y);I ma g e Ma n i p u l a t i o n S t a t i s t i c a l Image ManipulationHistogram equalisationexample image with 90 pixels
9、and 10 grey scales 0-9 histogram=0,0,0,10,20,30,20,10,0,0Hc=0,0,0,10,30,60,80,90,90,90Hc=0,0,0,1,3,6,8,9,9,9new histogram=0,10,0,20,0,0,30,0,20,10Pushes intensities apartdark pixels get darkerlight pixels get lighter I ma g e Ma n i p u l a t i o n H i s t o g r a m e qImage ManipulationPixel group
10、processing e.g.ConvolutionNew pixel values are a weighted sum of neighbouring pixels original valuesA filter specifies the weights in the sumCan often use separable 1-D filters for efficiency.filter(i,j)=filter_x(i)filter_y(j)Different(positive and negative)filter coefficients(weights)have different
11、 effects e.g.Values like 1,4,6,4,1/16 will blur the pixelsValues like-1,-3,3,1/8 will perform edge detectionI ma g e Ma n i p u l a t i o n P i x e l g r o u p Image ManipulationPixel group processing changesBlurringUse a low-pass filter,e.g.1,4,6,4,1/16 applied along rows then columns.I ma g e Ma n
12、 i p u l a t i o n P i x e l g r o u p Image ManipulationPixel group processing changesEdge enhancement using unsharp masking.Subtracting the blurred version from the original leaves just the edgesAdd these edges back to the original to bring out the areas of contrast.I ma g e Ma n i p u l a t i o n
13、 P i x e l g r o u p Image ManipulationPixel group processing changesEdge detecting filtersFilters such as 1,3,-3,-1 can be applied either horizontally or vertically(usually after smoothing)to locate the intensity changes(edges)Horizontal edges(+127)Vertical edges(+127)I ma g e Ma n i p u l a t i o
14、n P i x e l g r o u p Image ManipulationPixel level changesCombined effectse.g.embossed=a*original+b*(127+edges at angle q)e.g.b,3b,127+a,-3b,bI ma g e Ma n i p u l a t i o n P i x e l l e v e l Image ManipulationPixel level changesArt effects e.g.charcoal sketch(looks like an edge detector)Also pai
15、nt strokes that perform local,directional blending of colours for pointillism etc.I ma g e Ma n i p u l a t i o n P i x e l l e v e l Image ManipulationGeometrical transformationsMap each pixel(x,y)to some other position(x,y)newImage(x,y)=oldImage(x,y)Uses backward coordinate mapping,can you see why
16、?would usually sample the from oldImage at non-integer position(x,y)using bilinear interpolation.Many simple effects e.g.Shearing:x=x+ay,y=yRotation:x=xsin(T)+ycos(T),y=xcos(T)-ysin(T)More complex effectsInterpolate translations of points across imageFree-form deformations,thin-plate splines etcI ma
17、 g e Ma n i p u l a t i o n G e o me t r i c a l Image ManipulationGeometrical transformationsRotation:x=xsin(T)+ycos(T),y=xcos(T)-ysin(T)I ma g e Ma n i p u l a t i o n G e o me t r i c a l Image ManipulationGeometrical transformationsUsing interpolated user-specified translationsI ma g e Ma n i p
18、u l a t i o n G e o me t r i c a l Image CompressionImage compression is required for storage and transmissionLossless compression methodsNo data is lost in the compressionSuitable to all kinds of data e.g.textLossy compression methodsData is thrown away in compression cycleChoose data which the hum
19、an visual system is insensitive to.e.g.small high frequency componentsFile formats:GIF,JPEG,JPEG2000I ma g e C o mp r e s s i o n I ma g e c o mp r e sImage CompressionRepetition supressione.g.Run-length encodingaaaaaabbbbbbccddddd.a6b6ccd5.Statistical encodinge.g.Huffman encodingUse short binary st
20、rings for common charactersUse longer binary strings for uncommon charactersaaadaabbbaacaaabbaacaabaab 8bits each=26*8=208bitsa 0 b 10,c 110,d 111 000111001010100011000010100011000100010=39bitsI ma g e C o mp r e s s i o n R e p e t i t i o n s uGIF image compressionGIF images use a mixtureRestricte
21、d colours(only 256 different colours)Run-length encodingStaistical encoding(LZW algorithm)Therefore GIF is lossless for images of less than 256 coloursi.e.they can be reconstructed exactly G I F i ma g e c o mp r e s s i o n G I F i ma g eLossy Image CompressionHuman eye is fairly insensitive to cer
22、tain kinds of image informationLarge objects generally more important than fine detail,textures etcQuite different to audio compressionIntensity more important than hueCan quantise colours more coarsely L o s s y I ma g e C o mp r e s s i o n H u ma n eJPEG Image CompressionAlgorithm overviewTransfo
23、rm and code each 8x8 block independentlyPerform Discrete Cosine Transform(DCT)on each blockDifferentially quantise blocks DCT valuesRun length encode in zig-zag pathStatistical encode resulting stringJ P E G I ma g e C o mp r e s s i o n A l g o r i t hJPEG Image CompressionThe Discrete Cosine Trans
24、form(DCT)Separates the images high and low frequency componentsRelated to the Fourier TransformThe DCT itself is reversible i.e.losslessDCT u,v12NCuCvx0N1y0N1cos2x1 u2Ncos2y1 v2Npixel x,yCu,Cv12for u,v01 otherwiseJ P E G I ma g e C o mp r e s s i o n T h e D i s cJPEG Image CompressionEach pixel in
25、the DCT block is a weighted sum of the pixels in the input blockThis diagram shows which weights are applied for each pixel in the DCT.A visual map of the DCTJ P E G I ma g e C o mp r e s s i o n E a c h p i xDifferential QuantisationQuantise higher frequency components with fewer levelsHuman eye is
26、 relatively insensitive to high frequency componentsThis is where data is thrown awayMore coarsely quantised frequency components require fewer bits to storeVarying the values in the quantisation matrix allows different compression levelsTrade off quality for small file size.D i f f e r e n t i a l
27、Q u a n t i s a t i o n Q u a n tZig-zag encodingThe lowest frequency component is at(0,0)and highest at(N,N)Use zig-zag path to encode blockUse run-length encoding on resulting stringtends to group 0 coefficientsUse Huffman encoding on run-length encoded stringZ i g-z a g e n c o d i n g T h e l o
28、w e s t f r eJPEG compressionAdditional stepsSome additional steps are performed to squeeze more compression out of the dataColourthe image is first converted to YUV colour space and the Y(luminance)is coded with higher quality than the 2 colour channels(U and V).The colour channels are also often d
29、own sampled i.e.reduced by a factor of 2 along rows and/or columnsPredictive compressionThe first element in the DCT block is essentially the brightness of the block.These values are coded separately using predictive compression to remove redundancy between blocksJ P E G c o mp r e s s i o n A d d i
30、 t i o n a l s t eJPEG decompressionDecode strings Reverse Huffman and run-length encodingzig-zag to reconstruct N by N blockDequantise block valuese.g.if quantised to 4 levels and decoded to 256 levels then multiply value by 64.Inverse DCT Very similar to DCTJ P E G d e c o mp r e s s i o n D e c o
31、 d e s t r i nJPEG 2000Completely different algorithm to standard JPEGUses EZW compressionBased on wavelet theoryDoesnt involve blocking of the data like standard JPEGBlocking artefacts are common in over-compressed JPEG images.J P E G 2 0 0 0 C o mp l e t e l y d i f f e r e n t JPEG 2000Wavelet tr
32、ansformsThe Fourier Transform(FT)converts a signal(or image)into its component frequenciesLooses spatial information e.g.doesnt tell us where the high frequencies are located in the imageDCT similar to an FT applied to each blockRetains some spatial information(i.e.the location of the block),but loo
33、ses frequency correlations between blocksWavelet Transform(WT)a(smooth)trade off between frequency and spatial representationJ P E G 2 0 0 0 Wa v e l e t t r a n s f o r msWavelet transformsFilter horizontally with two filters even pixels:low-pass filterodd pixels:high-pass waveletGroup low pass fil
34、tered components to left and high pass filtered to rightRepeat verticallyRepeat recursively on low-pass image.Wa v e l e t t r a n s f o r ms F i l t e r h o r i zExploiting subband correlationSubband correlation Although the wavelet transform decorrelates image information within a subband,there is
35、 still a high degree of correlation between subbands.Early wavelet methods struggled to find a compact way to exploit this correlationE x p l o i t i n g s u b b a n d c o r r e l a t i o nExploiting subband correlationZero-trees EZW encodes zeros,rather than the data.A zero at a coarse scale is a g
36、ood predictor of zeros at a finer scale.Can encode a lot of information in specifying just the root of a zero-tree.Similar to RL encodingE x p l o i t i n g s u b b a n d c o r r e l a t i o nSuccessive quantisationThe chances of finding a zero tree increase with a coarser quantisationMore small val
37、ues are set to zero.Successive quantisationQuantise the(remaining)image data using successively finer quantisation steps.This leaves a binary image to encode at each stepValues only 0 or 1Encode using zero treesZero trees completely specify a binary imageSuccessive zero-trees encode less significant
38、 bitsS u c c e s s i v e q u a n t i s a t i o n T h e c h aSuccessive quantisationSuccessive quantisation algorithm1.Choose an high quantisation step Q(half the max value)2.Until finest quantisation step,repeat 2.1 Quantise wavelet coefficients using Q ie.if(w(x,y)Q)w(x,y)=0;else w(x,y)=1;Creates a
39、 binary image of the most significant wavelet coefficients2.2 Encode binary image(w)using zero-trees and output(This is the highest order bits of the remaining data)2.3 Subtract the encoded data from the remaining dataw(x,y)=w(x,y)w(x,y)*Q2.4 half the quantisation step sizeQ=Q/23.EndS u c c e s s i
40、v e q u a n t i s a t i o n S u c c e s sJPEG 2000Hence the wavelet transform is encoded as a series of zero-trees representing successively less significant bits of the dataThe binary information is embedded in the zero-trees.Hence the name:Embedded Zero-tree Wavelet(EZW)compressionThe actual syste
41、m is actually more complex,but this gives the basic ideaJ P E G 2 0 0 0 H e n c e t h e w a v e l e t t r aSummarySampling and resolutionImage Manipulationpixel level,statistical and pixel groupImage CompressionGIF:Run-length and LZW compressionJPEG:DCT,zig-zag encoding,differential quantisationJPEG 2000:wavelet transforms,zero-trees,successive quantisation.S u mma r y S a mp l i n g a n d r e s o l u t i o n
