Down scaling video frames

I want to decode the video frames to a smaller size. Decoding them at full 
size and then scaling them down to the size I want isn't very efficient, but 
I can't see any way of avoiding that with the current decoding functions.

I'm going to try and figure out how easy it is to make theora do this. I'm 
wondering if anyone has tried this before or if there are any reasons why it 
can't be done?