GAUSSIAN-LAPLACIAN PYRAMID: 1D REDUCE ------------------------------------- remember the "5-tap" 1D kernel is of the form \hat{w} = [0.25-a/2 0.25 a 0.25 0.25-a/2] for concreteness, let's choose a=0.4, giving us \hat{w} = [0.05 0.25 0.40 0.25 0.05] = 1/20*[1 5 8 5 1] consider a 9=2^3+1 pixel example image G_{k-1} = [6 8 1 5 1 9 5 7 9] let's find G_k = REDUCE(G_{k-1}) it will have ~half as many pixels, more specifically 5=2^2+1 pixels we only need to compute the odd pixels ..... since we'll throw the rest away .. "x" below means shouldn't/cannot compute G_{k-1} = [6 8 1 5 1 9 5 7 9] G_k = [? x ? x ? x ? x ?] this is just convolution with \hat{w}, but we only need to compute this convolution for the odd pixels eg. G_k(3) = [1 5 1 9 5] * 1/20*[1 5 8 5 1]' = 1/20*(1 + 25 +8 + 45 + 5) = 84/20 = 4.2 eg. G_k(2) = [6 8 1 5 1] * 1/20*[1 5 8 5 1]' = 1/20*(6 + 40 + 8 + 25 + 1) = 80/20 = 4.0 the only catch is what to do at the boundary conditions, G_k(1) and G_k(5) ... as suggested in lecture, we just use the part of the kernel that *does* overlap, reweighted so that it sums to 1. eg. G_k(1) = [x x 6 8 1] * 1/20*[1 5 8 5 1]' = [6 8 1] * 1/14*[8 5 1]' [reweighted] = 1/14*(48 + 40 + 1) = 89/14 = 6.4 eg. G_k(5) = [5 7 9 x x] * 1/20*[1 5 8 5 1]' = [5 7 9] * 1/14*[1 5 8]' [reweighted] = 1/14*(5 + 35 + 72) = 112/14 = 8.0 after computing everything we get G_k = [6.4 4.0 4.2 6.5 8.0] GAUSSIAN-LAPLACIAN PYRAMID: 1D EXPAND ------------------------------------- now let's find EXPAND(G_k) this is up-sampling a smaller image, ~doubling its resolution .. conceptually the reverse of the REDUCE function it will have the same number of pixels as G_{k-1}, 9=3^2+1 pixels we line things up and apply the same kernel as before, in the opposite direction, being careful to *reweight* the kernel so it sums to 1, given that ~half the pixels from the source G_k will be missing. G_k = [6.4 x 4.0 x 4.2 x 6.5 x 8.0] EXPAND(G_k) = [ ? ? ? ? ? ? ? ? ? ] eg. EXPAND(G_k)(5) = [4.0 x 4.2 x 6.5] * 1/20*[1 5 8 5 1]' = [4.0 4.2 6.5] * 1/10*[1 8 1]' [reweighted] = 4.4 eg. EXPAND(G_k)(4) = [x 4.0 x 4.2 x] * 1/20*[1 5 8 5 1]' = [4.0 4.2] * 1/10*[5 5]' [reweighted] = 4.1 so this shows that we get two modified kernels, 1/10*[1 8 1] and [0.5 0.5], for dealing with odd and even pixels respectively ... but again, we have to consider boundary conditions in a special way, reweighting the kernel so we just use the overlapping part, and so it sums to 1. eg. EXPAND(G_k)(1) = [x x 6.4 x 4.0] * 1/20*[1 5 8 5 1]' = [6.4 4.0] * 1/9*[8 1]' [reweighted] = 6.1 after computing everything we get EXPAND(G_k) = [6.1 5.2 4.3 4.1 4.4 5.4 6.4 7.3 7.8] GAUSSIAN-LAPLACIAN PYRAMID: 2D REDUCE/EXPAND -------------------------------------------- the 2D kernel function is separable and symmetric, ie. w(m,n) = \hat{w}(m)*\hat{w}(n) so we can convolve the 1D \hat{w} first across rows, and then across columns (or vice versa) ... this will give the same result as convolving with the 2D kernel w directly e.g. REDUCE for a 9x9 image .... - REDUCE across rows to get a 9x5 image - then REDUCE across columns to get a 5x5 image e.g. EXPAND for a 5x5 image .... - EXPAND across rows to get a 5x9 image - then EXPAND across columns to get a 9x9 image GAUSSIAN-LAPLACIAN BLENDING ALGORITHM ------------------------------------- To compute the Gaussian pyramid: G_0 = I [original image] G_k = REDUCE(G_{k-1}) [successively blur/reduce resolution] G_N [stop when the image is 1x1, or earlier] To compute the Laplacian pyramid: L_N = G_N [base case, use the smallest Gaussian pyramid image] L_k = G_k - EXPAND(G_{k+1}) [detail/difference between successive Gaussian pyramid levels] Blending algorithm: - input: images A,B (binary) mask M that specifies the blend (0=A,1=B) - pad everything to make them powers of 2 (plus 1), (2^N+1)x(2^N+1) - compute A's Laplacian pyramid AL_0,AL_1,...,AL_N - compute B's Laplacian pyramid BL_0,BL_1,...,BL_N - compute M's Gaussian pyramid MG_0,MG_1,...,MG_N - compute a Laplacian pyramid for the result, S, using linear interpolation, for every pyramid level k, SL_k(r,c) = (1-MG_k(r,c))*AL_k(r,c) + MG_k(r,c)*BL_k(r,c) we're simply doing linear interpolation over every pixel, with a blend mask given at different levels of detail - reconstitute the full-resolution image for S, by computing S=SG_0 from SL_0,SL_1,...,SL_N, SG_N = SL_N SG_k = SL_k + EXPAND(SG_{k+1}) BEIER-NEELY MORPHING -------------------- main idea is to specify corresponding line segment features in two images SPECIAL IMAGE COORDINATES RELATIVE TO A LINE SEGMENT we describe pixel coordinates of X relative to a line segment PQ in a special way [draw out the diagram] look at the perpendicular "projection" of X onto PQ .. ie. M = P + proj_{Q-P}(X-P) u: fraction of the way that M is from P to Q (0 means P, 1 means Q, can be negative or >1) u = dot( Q-P, X-P ) / ||(Q-P)||^2 v: signed distance from X to PQ, ie. signed distance from X to M v = dot( perp(Q-P), X-P ) / ||(Q-P)|| so the shortest distance from X to the line segment PQ is: distSeg(X,PQ) = { ||X-P|| if u < 0 { ||X-Q|| if u > 1 { |v| otherwise ONE-LINE WARPING ALGORITHM suppose the destination image contains line segment PQ and in the source image we have the corresponding line segment P'Q' for pixel X in the destination image, first compute its special (u,v) coordinates its corresponding pixel X' in the source image is then X' = P' + u * (Q'-P') + v * perp(Q'-P')/||(Q'-P')|| u * the source line segment (fraction along line segment) v * the unit perpendicular (signed distance) MULTIPLE-LINE WARPING ALGORITHM for multiple lines, weight the effect of the lines differently; for pixel X and line segment PQ, define the weight as: weight(X,PQ) = ( ||(Q-P)||^p / (a + distSeg(X,PQ) ) )^b - a close to 0 means huge weight when X is close to (or on) PQ - b controls relative falloff with distance, typically \in [0.5,2] - p controls dependence on line segment length, typically \in [0,1] So to handle multiple lines ... for each pixel X in the destination image: - for each line segment P_iQ_i, calculate the corresponding source pixel, X'_i, using the single line formula - the overall source pixel is the weighted average of the individually estimated source pixels \sum_i X'_i * weight(X,P_iQ_i) X' = ------------------------------ \sum_i weight(X,P_iQ_i) [ NOTE: the paper uses an equivalent, but more convoluted formula .. and there's a typo .... it should be D_i=X'_i-X, not D_i=X'_i-X_i ] OVERALL ALGORITHM input: input images A and B, with corresponding line segments compute morphed version M, for some morph parameter \alpha (M=A for \alpha=0, M=B for \alpha=1): - interpolate the line segments between A and B, according to \alpha, giving us a set of line segments for M ie. linearly interpolate the endpoints: p_M = (1-\alpha)*p_A + \alpha*p_B - morph from A to M => A' (using the multiple line warping algorithm, src=A, dst=M) - morph from B to M => B' (using the multiple line warping algorithm, src=B, dst=M) - linearly blend the morphed images, A' and B' M=A'*(1-\alpha)+B'*\alpha