Image Processing and Recognition

PYRAMIDAL DECOMPOSITION

The pyramidal decomposition algorithm (Burt, Adelson) is a redundant invertible transformation. It recursively transforms a sequence c_n=c^o_n into two sequences obtained by averaging (smoothing) and decimation,

c¹_k = ∑_n w_n-2k c^o_n

The superscipt is the level of the pyramidal decomposition. The sequence c¹_n is a "decimated" version of the original sequence, and is the starting point for the next step. The "blurred" version of the sequence at level 0,

c^0,b_n = ∑_k w_n-2k c¹_k

The difference sequence is

d^o_n = c^o_n - c^0,b_n

And the reconstruction of the original sequence (the inversion of the transform) is

c^o_n = d^o_n + ∑_k w_n-2k c¹_k

The coefficients of this operator should satisfy certain constraints:

w_n must be real;
w_n=w_-n (symmetric);
∑_n w_n = 1 (resolution of the identity);
∑_n w_2n = ∑_n w_2n+1 (regularity).

Example

w₀=a,
w₁=w_-1=1/4,
w₂=w_-2=1/4 - a/2
others zero.

Since a limited number of coefficients is non-zero, it is convenient to rewrite the formulas with the sums over the coefficents indices,

c¹_k = ∑_m=-M^M w_m c^o_{(m+2k) mod N}
c^0,b_n = ∑_m=-M^M w_m c¹_{(n-m)/2 mod N/2}

where the second sum runs on n-m even only.

Coefficient count

Counting the number of coefficients for an original sequence of lenght N, there are N terms in c⁰ and d⁰, N/2 in c¹ and d¹, and so on. Therefore the pyramidal decomposition contains some redundance, as the number of coefficients is increased.

Marco Corvi - Page hosted by geocities.com.