1Image Warping,Compositing &MorphingAdam FinkelsteinPrinceton UniversityCOS 426, Spring 2003Image Processing• Quantizationο Uniform Quantizationο Random ditherο Ordered ditherο Floyd-Steinberg dither • Pixel operationsο Add random noiseο Add luminanceο Add contrastο Add saturation• Filteringο Blurο Detect edges• Warpingο Scaleο Rotateο Warp• Combiningο Compositeο MorphImage Processing• Quantizationο Uniform Quantizationο Random ditherο Ordered ditherο Floyd-Steinberg dither • Pixel operationsο Add random noiseο Add luminanceο Add contrastο Add saturation• Filteringο Blurο Detect edges• Warpingο Scaleο Rotateο Warp• Combiningο Compositeο MorphImage Warping• Move pixels of imageο Mappingο ResamplingSource image Destination imageWarpOverview• Mappingο Forwardο Reverse• Resamplingο Point samplingο Triangle filterο Gaussian filterMapping• Define transformationο Describe the destination (x,y) for every location (u,v) in the source (or vice-versa, if invertible)vuyx2Example Mappings• Scale by factor:ο x = factor * uο y = factor * vScale0.8yxvuExample Mappings• Rotate by Θ degrees:ο x = ucosΘ -vsinΘο y = usinΘ + vcosΘRotate30vuyxExample Mappings• Shear in X by factor:ο x = u + factor * vο y = v• Shear in Y by factor:ο x = uο y = v + factor * uShear X1.3Shear Y1.3vuvuyxyxOther Mappings• Any function of u and v:ο x = fx(u,v)ο y = fy(u,v)Fish-eye“Swirl”“Rain”Image Warping Implementation I• Forward mapping:for (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);}}Source imageDestination image(u,v)(x,y)fForward MappingRotate-30vuyx• Iterate over source image3Forward Mapping - NOTRotate-30vuyxMany source pixels can map to same destination pixel• Iterate over source imageForward Mapping - NOTRotate-30vuyxMany source pixels can map to same destination pixelSome destination pixels may not be covered• Iterate over source imageImage Warping Implementation II• Reverse mapping:for (int x = 0; x < xmax; x++) {for (int y = 0; y < ymax; y++) {float u = fx-1(x,y);float v = fy-1(x,y);dst(x,y) = src(u,v);}}Source imageDestination image(u,v)(x,y)fReverse MappingRotate-30vuyx• Iterate over destination imageο Must resample sourceο May oversample, but much simpler!Resampling• Evaluate source image at arbitrary (u,v)Source imageDestination image(u,v)(x,y)(u,v) does not usuallyhave integer coordinatesOverview• Mappingο Forwardο Reverse» Resamplingο Point samplingο Triangle filterο Gaussian filter4This method is simple, but it causes aliasingPoint Sampling• Take value at closest pixel:ο int iu = trunc(u+0.5);ο int iv = trunc(v+0.5);ο dst(x,y) = src(iu,iv);Rotate-30Scale0.5vuyxTriangle Filtering• Convolve with triangle filterInput OutputFigure 2.4 WolbergTriangle Filtering• Bilinearly interpolate four closest pixelsο a = linear interpolation of src(u1,v2) and src(u2,v2) ο b = linear interpolation of src(u1,v1) and src(u2,v1)ο dst(x,y) = linear interpolation of “a” and “b”(u1,v1)(u2,v2)(u2,v1)(u1,v2)(u,v)abGaussian Filtering• Convolve with Gaussian filter Input OutputFigure 2.4 WolbergWidth of Gaussian kernel affects blurinessWidth of Gaussian kernel affects blurinessGaussian Filtering• Compute weighted sum of pixel neighborhood:ο Weights are normalized values of Gaussian function(u,v)Filtering Methods ComparisonPoint Bilinear Gaussian• Trade-offsο Aliasing versus blurringο Computation speed5Image Warping Implementation• Reverse mapping:for (int x = 0; x < xmax; x++) {for (int y = 0; y < ymax; y++) {float u = fx-1(x,y);float v = fy-1(x,y);dst(x,y) = resample_src(u,v,w);}}Source imageDestination image(u,v)(x,y)fImage Warping Implementation• Reverse mapping:for (int x = 0; x < xmax; x++) {for (int y = 0; y < ymax; y++) {float u = fx-1(x,y);float v = fy-1(x,y);dst(x,y) = resample_src(u,v,w);}}Source imageDestination image(u,v)(x,y)fwExample: Scale• Scale (src, dst, sx, sy):float w ≅ max(1.0/sx,1.0/sy);for (int x = 0; x < xmax; x++) {for (int y = 0; y < ymax; y++) {float u = x / sx;float v = y / sy;dst(x,y) = resample_src(u,v,w);}}Scale0.5yxvu(u,v)(u,v)(x,y)(x,y)Example: Rotate• Rotate (src, dst, theta):for (int x = 0; x < xmax; x++) {for (int y = 0; y < ymax; y++) {float u = x*cos(-Θ) - y*sin(-Θ);float u = x*sin(-Θ) + y*cos(-Θ);dst(x,y) = resample_src(u,v,w);}}Rotate45vu(u,v)(u,v)x = ucosΘ -vsinΘy = usinΘ +vcosΘyx(x,y)(x,y)Example: Fun• Swirl (src, dst, theta):for (int x = 0; x < xmax; x++) {for (int y = 0; y < ymax; y++) {float u = rot(dist(x,xcenter)*theta);float v = rot(dist(y,ycenter)*theta);dst(x,y) = resample_src(u,v,w);}}Swirl45yxvu(u,v)(u,v)f(x,y)(x,y)Image Processing• Quantizationο Uniform Quantizationο Random ditherο Ordered ditherο Floyd-Steinberg dither • Pixel operationsο Add random noiseο Add luminanceο Add contrastο Add saturation• Filteringο Blurο Detect edges• Warpingο Scaleο Rotateο Warp• Combiningο Compositeο Morph6Overview: combining images• Image compositingο Blue-screen mattesο Alpha channelο Porter-Duff compositing algebra• Image morphingο Specifying correspondencesο Warpingο BlendingEven CG folks can win an OscarSmith PorterCatmullDuffImage Compositing• Separate an image into “elements”ο Render independentlyο Composite together• Applicationsο Cel animationο Chroma-keyingο Blue-screen mattingDobkin meets the KingBlue-Screen Matting• Composite foreground and background imagesο Create background imageο Create foreground image with blue backgroundο Insert non-blue foreground pixels into backgroundProblem: no partial coverage!Alpha Channel• Encodes pixel coverage informationοα= 0: no coverage (or transparent)οα= 1: full coverage (or opaque)ο 0 < α < 1: partial coverage (or semi-transparent)•Example: α = 0.3PartialCoverageSemi-TransparentorCompositing with AlphaControls the linear interpolation of foreground and background pixels when elements are composited.α = 1 0 < α < 1α = 0 0 < α < 17Pixels with Alpha• Alpha channel convention:ο (r, g, b, α) represents a pixel that is α covered by the color C = (r/α, g/α, b/α)»Color comonents are premultiplied by α»Can display (r,g,b) values directly»Closure in composition algebra• What is the meaning of the following?ο (0, 1, 0, 1) = ?ο (0, 1/2, 0, 1) = ?ο (0, 1/2, 0, 1/2) = ?ο (0, 1/2, 0, 0) = ?Full green, full coverageHalf green, full
View Full Document