Image Warps and HalftoningImage WarpingSlide 3MappingMapping ExamplesSlide 6Slide 7Forward MappingSlide 9Inverse MappingSlide 11ResamplingPoint SamplingTriangle FilteringGaussian FilteringFilter ComparisonImage Warping ExamplesScaleRotateSwirlQuantization ArtifactsUniform QuantizationSlide 23Dealing with QuantizationClassical HalftoningSlide 26Slide 27DitheringRandom DitherSlide 30Ordered DitherSlide 32Slide 33Floyd-Steinberg Error DiffusionSlide 35Image Warps and HalftoningImage WarpingScaleRotateWarpBasically, we have to move image pixelsThis is done by mapping the pixels from the source to the destination image (actually backwards) then resamplingwarpSource imageDestination imageImage WarpingOverviewMappingForwardInverseResamplingPoint samplingTriangle filter (bilinear interpolation)Gaussian filterMappingForward mapping:),(),( yxvuM ),(),(1yxMvuInverse mapping:uvxyMapping ExamplesScale (separately in horizontal and vertical)uvyvSxuSvu *;*xy5.09.0vuSSMapping ExamplesRotate counterclockwise θ degreesuvyvuxvu  )cos()sin(;)sin()cos(xyo30Mapping ExamplesGeneral functions of u and v:yvufxvufyx),(),(swirl rainfisheyeForward Mappingfor (int u = 0; u < umax; u++) {for (int v = 0; v < vmax; v++) { float x = fx(u,v); float y = fy(u,v); dst (x,y) = src(u,v);}}f(u,v)(x,y)source image destination imageForward MappingRotate 30oMultiple source pixels map to same destinationNo source pixels map to destinationNeed to resample destinationGenerate one sample for each pixelComplex to figure out where the nearest samples are for each pixelIterate over source imageInverse Mappingfor (int x = 0; x < xmax; x++) {for (int y = 0; v < ymax; y++) { float u = fx-1(x,y); float v = fy-1(x,y); dst (x,y) = src(u,v);}}f-1(u,v)(x,y)source image destination imageInverse MappingRotate -30oNeed to resample sourceGenerate source sample for each destination pixelMay oversample source, but oversampling is simpler than in forward caseIterate over destination imageResamplingf-1(u,v)(x,y)source image destination imageNeed to evaluate source image at arbitrary (u,v)(u,v) not generally integer coordinates3 methodsPoint samplingTriangle filteringGaussian filteringPoint SamplingJust find closest source pixel to each destination pixelint iu = round(u);int iv = round(v);dst(x,y) = src(iu, iv);Simple, but causes aliasingRotate -30oTriangle FilteringConvolve four closest source pixels to desired (u,v) with triangle filter (bilinear interpolation)Bilinear interpolation:a = lerp(src(u1,v2),src(u2,v2))b = lerp(src(u1,v1),src(u2,v1))dst(x,y) = lerp(a,b)(u1,v1) (u2,v1)(u1,v2) (u2,v2)(u,v)abGaussian FilteringCompute weighted sum of pixel neighborhoodWeights are normalized values of Gaussian function(u,v)wFilter ComparisonTradeoffsFast but aliased (point sampling)Slow and blurry (Gaussian)Point sampling Bilinear (triangle) GaussianImage Warping ExamplesUsing reverse mapping and Gaussian filteringfor (int x = 0; x < xmax; x++) {for (int y = 0; v < ymax; y++) { float u = fx-1(x,y); float v = fy-1(x,y); dst (x,y) = resample_src(u,v,w);}}f-1(x,y)source image destination image(u,v)wresample_src(u,v,w);Scale Scale(src,dst,sx,sy)float w = max(1/sx,1/sy);for (int x = 0; x < xmax; x++) {for (int y = 0; v < ymax; y++) { float u = x/sx ; float v = x/sy ; dst (x,y) = resample_src(u,v,w);}}Rotate Rotate(src,dst,θ)for (int x = 0; x < xmax; x++) {for (int y = 0; v < ymax; y++) { float u = x*cos(-θ)- y*sin(-θ); float v = x*sin(-θ)+ y*cos(-θ); dst (x,y) = resample_src(u,v,w);}}Swirl Swirl(src,dst,θ,cx,cy)for (int x = 0; x < xmax; x++) { for (int y = 0; v < ymax; y++)float u = (x-cx)*cos(-θ*|x-cx|)-(y-cy)*sin(-θ*|y-cy|)+cx;float v = (x-cx)*sin(-θ*|x-cx|)+(y-cy)*cos(-θ*|y-cy|)+cy;dst (x,y) = resample_src(u,v,w);}}Quantization ArtifactsErrors due to limited intensity resolutionWhy?Frame buffers only have so many bits per channelPhysical display devices have a limited dynamic range, especially hard copy devicesUniform QuantizationIxI(x)P(x)I(x)P(x)4 bits/pixelUniform QuantizationImages with increasing bits per pixel1 bit 2 bits 4 bits 8 bitsDealing with QuantizationHalftoning techniquesClassical, or brute force halftoningDithering methodsError DiffusionOther techniquesClassical HalftoningFirst VariantFirst, use dots of varying sizes to represent intensitiesSize of dot proportional to intensityI(x) P(x)Classical HalftoningNewspaper imageNYT 9/21/99Classical HalftoningWhat if your display device can’t display produce multiple dot sizes?Use cluster of pixelsNumber of “on” pixels in cluster proportional to intensityTrades spatial resolution for intensity resolutionDitheringAlgorithms to distribute errors among pixelsReduce objectionable regular artifactsReplace them with noiseOriginal – 8 bits/pixel Uniform quantization – 1 bit/pixelFloyd-Steinberg error diffusion – 1 bit/pixelRandom DitherRandomize quantization errorErrors appear as noiseIxI(x)P(x)IxI(x)P(x) ))()(()( xrandxIroundxP Random DitherOriginal – 8 bits/pixel Uniform quantization – 1 bit/pixelRandom dither – 1 bit/pixelOrdered DitherPatterned errors that try to minimize regular artifactsRecursively defined “Dither Matrix” stores pattern of thresholds2/22/2/22/2/22/2/22/)2,2(4)1,2(4)2,1(4)1,1(4nnnnnnnnnUDDUDDUDDUDDD20132D10280614412911135137154DOrdered Dither   ;),(),(),(),()),((;),(),(;mod;modyxIyxPelseyxIyxPthenjiDeifyxIyxIenyjnxiOrdered DitherOriginal – 8 bits/pixel Random dither – 1 bit/pixelOrdered dither – 1 bit/pixelFloyd-Steinberg Error DiffusionQuantization errors are spread over neighboring pixels to the right and below1Floyd-Steinberg Error DiffusionOriginal – 8 bits/pixel Random dither – 1 bit/pixelOrdered dither – 1 bit/pixelFloyd-Steinberg error diffusion – 1