C280, Computer VisionProf. Trevor [email protected] 8: AlignmentLast time: Texture• Texture is a useful property that is often indicative of materials, appearance cues• Texture representations attempt to summarize repeating patterns of local structure•Filter banks useful to measure redundant variety of •Filter banks useful to measure redundant variety of structures in local neighborhood– Feature spaces can be multi-dimensional• Neighborhood statistics can be exploited to “sample” or synthesize new texture regions– Example-based technique particularly good for synthesisProblem Sets…• PS 0/1 graded by end of week• PS 1: stragglers by end of day today; solnsreleased tomorrow morning•PS 2: released yesterday•PS 2: released yesterday– More programming centric– More open ended– Shorter, choice of problems…– Due two weeks from yesterdayRoadmap• Previous: Image formation, filtering, local features, (Texture)…• Today: Feature-based Alignment – Stitching images together– Homographies, RANSAC, Warping, Blending– Global alignment of planar models• Next lecture (Thu): Dense Motion Models–Local motion / feature displacement–Local motion / feature displacement– Parametric optic flow• No classes next week: ICCV conference• Oct 6th: Stereo / ‘Multi-view’: Estimating depth with known inter-camera pose• Oct 8th: ‘Structure-from-motion’: Estimation of pose and 3D structure– Factorization approaches– Global alignment with 3D point modelsToday: Alignment• Homographies• Rotational Panoramas•RANSAC•• Global alignment• Warping• BlendingMotivation: Recognition Figures from David LoweMotivation: medical image registrationMotivation: Mosaics• Getting the whole picture– Consumer camera: 50˚x 35˚Slide from Brown & Lowe 2003Motivation: Mosaics• Getting the whole picture– Consumer camera: 50˚x 35˚– Human Vision: 176˚x 135˚Slide from Brown & Lowe 2003Motivation: Mosaics• Getting the whole picture– Consumer camera: 50˚x 35˚– Human Vision: 176˚x 135˚• Panoramic Mosaic = up to 360 x 180°Slide from Brown & Lowe 2003Motion modelsMotion models• What happens when we take two images with a camera and try to align them?• translation?•rotation?•rotation?• scale?• affine?• perspective?• … see interactive demo (VideoMosaic)SzeliskiImage WarpingImage Warping• image filtering: change range of image• g(x) = h(f(x))fhf• image warping: change domain of image• g(x) = f(h(x))x xfxhfxSzeliskiImage Warping• image filtering: change range of image• g(x) = h(f(x))hf g• image warping: change domain of image• g(x) = f(h(x))hfgSzeliskiParametric (global) warping• Examples of parametric warps:translationrotationaspectaffineperspectivecylindricalSzeliskiImage Warping• Given a coordinate transform x’ = h(x) and a source image f(x), how do we compute a transformed image g(x’) = f(h(x))?f(x) g(x’)x x’h(x)SzeliskiForward Warping• Send each pixel f(x) to its corresponding location x’ = h(x) in g(x’)• What if pixel lands “between” two pixels?f(x) g(x’)x x’h(x)SzeliskiForward Warping• Send each pixel f(x) to its corresponding location x’ = h(x) in g(x’)• What if pixel lands “between” two pixels?•Answer: add “contribution” to several pixels, f(x) g(x’)x x’h(x)•Answer: add “contribution” to several pixels, normalize later (splatting)SzeliskiInverse Warping• Get each pixel g(x’) from its corresponding location x’ = h(x) in f(x)• What if pixel comes from “between” two pixels?f(x) g(x’)x x’h(x)SzeliskiInverse Warping• Get each pixel g(x’) from its corresponding location x’ = h(x) in f(x)• What if pixel comes from “between” two pixels?•Answer: resamplecolor value from •Answer: resamplecolor value from interpolated (prefiltered) source imagef(x) g(x’)x x’SzeliskixyInverse warpingxx’T-1(x,y)y’f(x,y) g(x’,y’)xGet each pixel g(x’,y’) from its corresponding location (x,y) = T-1(x’,y’) in the first imagexx’Q: what if pixel comes from “between” two pixels?A: Interpolate color value from neighbors– nearest neighbor, bilinear…Slide from Alyosha Efros, CMU>> help interp2Bilinear interpolationSampling at f(x,y):Slide from Alyosha Efros, CMUInterpolation• Possible interpolation filters:– nearest neighbor– bilinear–bicubic(interpolating)–bicubic(interpolating)– sinc / FIR• Needed to prevent “jaggies”and “texture crawl”SzeliskiPrefiltering• Essential for downsampling (decimation) to prevent aliasing• MIP-mapping [Williams’83]:1.build pyramid (but what decimation filter?):1.build pyramid (but what decimation filter?):• block averaging• Burt & Adelson (5-tap binomial)• 7-tap wavelet-based filter (better)2. trilinear interpolation• bilinear within each 2 adjacent levels• linear blend between levels (determined by pixel size)Szeliski2D coordinate transformations• translation: x’ = x + t x = (x,y)• rotation: x’ = R x + t• similarity: x’ = s R x + t•affine:x’ =A x + t•affine:x’ =A x + t• perspective: x’ ≅≅≅≅ H x x = (x,y,1)(x is a homogeneous coordinate)• These all form a nested group (closed w/ inv.)SzeliskiBasic 2D TransformationsBasic 2D transformations as 3x3 matrices=110010011''yxttyxyxTranslate=110000001''yxssyxyxScaleΘΘΘ−Θ=11000cossin0sincos1''yxyx=110001011''yxshshyxyxRotate ShearSource: Alyosha Efros2D Affine TransformationsAffine transformations are combinations of …=wyxfedcbawyx100''Affine transformations are combinations of …• Linear transformations, and• TranslationsParallel lines remain parallelGraumanProjective TransformationsProjective transformations:• Affine transformations, and=wyxihgfedcbawyx'''• Projective warpsParallel lines do not necessarily remain parallelGraumanImage alignment• Two broad approaches:– Direct (pixel-based) alignment• Search for alignment where