Previous | Next --- Slide 35 of 146
Back to Lecture Thumbnails
raymondx

I'm still a bit confused about how it's 4/3 the original image. If an image is NxN and we divide by 2 every time, shouldn't it take at minimum 3/2 the original image size (since N+N/2)?

mpotoole

Hmm let's see. An image of size N x N requires N^2 storage space. An image downsampled by a factor of 2 requires 1/4 N^2 storage space. So the total size of the pyramid will be the result of the following:

1 + 1/4 + 1/16 + 1/64 + 1/256 + ...
= (1/4)^0 + (1/4)^2 + (1/4)^2 + (1/4)^3 + ...
<= 1 / (1 - 1/4)   (*)
= 4 / 3

(*) See geometric series for proof.

If we were dealing with a 1 dimensional signal, it would require 1 + 1/2 + 1/4 + 1/8 + ... = 2 times the space to store its pyramid.

thuspake

You can also think of it as we're throwing away every other row and column so then the scale factor is going to be $\frac{1}{4}$ and then you just plug that into $\frac{1}{1-x} \rightarrow \frac{1}{1-.25} = 4/3$