**
**

Basic information theory however shows that if you sample a signal at f,

and there are frequencies higher then f/2 present in this signal, you will

get a 'beat signal ' (interference with the sampling frequency) known as 'aliasing'.

I tried two well known open source packages, mjpegtools and bbmpeg, both use

averaging and seem to be content with the interference this causes.

Because I needed to resize DVB-s 720 x 576 PAL high quality images either

to SVCD 480 x 576 or CVD 352 x 576 format, I did look a bit deeper into this,

and tried to make a better resizer, without the aliasing artefacts.

The solution in theory is simple:

Filter out everything (low pass) starting just below half sample frequency.

(For a correct digitalization process according to Nyquist we need to sample

at at least 2 x f, where f is the maximum frequency in our signal).

Now since we are talking video, we need to be fast, and I wanted to have

more possibilities to do things in the frequency domain (for other reasons).

A low pass can be made by doing a Fourier transform followed by a reverse

Fourier transform, when in the frequency domain we set some components to

zero (the high frequency components we do not want).

Big problem with the fft and reverse fft (fft = fast Fourier transform),

is always the speed.

Since a lot of computations are required for every line in every frame,

the processing could become un-acceptable slow.

I was lucky to find the fftw package for Linux (Unix), that does a 720

point fft on my system in about 190 micro seconds.

Since in the image processing chain the next thing is a (very slow)

mpeg2encoder, the extra overhead in time the fft and reverse fft cause,

is not a real problem (8 hour processing time is normal for a > 1 hour movie).

on an Athlon, perhaps more on a Pentium with the same clock speed.

Only an amount of this time is used in the resizer code, most in the

mpeg2 coder.

Also the tendency is to ever faster systems, the speed issue will become

less and less important.

For one frame of 720 x 576 we need to apply the fft and reverse fft one

time for the luminance Y signal, and 1 time for each chrominance

signal, U and V, for each line.

U and V however contain only 1/4 of the info, so we do an fft and reverse

fft for these of (720 / 2) is 360 points (576 / 2) = 288 times.

For Y we do a 720 point fft and reverse 576 times.

So per picture we do 576 = 288 + 288 = 1152 fft reverse fft operations.

These are some test values on a Duron 950 (from the wfft test suite):

720 points forward 189.592896 us

720 points backward 178.331604 us

360 points forward 88.463379 us

360 points backward 83.996216 us

So, as an estimate, for one picture, the time taken is:

576 x (190 + 178) + 2 x 288 x (88 + 84) = 311040 us, or 311 ms

(slightly more then 3 frames per second).

To give an idea, for a 90 minute movie at 25 pictures / second, it takes

90 x 60 x 25 x 311 ms = 41985 seconds, or 699 minutes or 11.7 hours.

This is WITHOUT optimizing anything in the software, wfft can do

multidimensional array processing and has a 'plan' function that can find

the best fft algo for your system,

These rather long processing times (add an other few hours for the mpeg2

coder) are not that big of a problem, normally I leave the computer

overnight making the resized copy.

All this shows that using Fourier transforms is now within the reach

of the average computer owner, and better video processing techniques

are just around the corner (think also object recognition, filtering

of specific interference, special effect etc.)

Drawbacks:

Speed and quality is a tradeoff, there ARE artefacts introduced, in the

code I had to limit the outcome of the reverse fft so it is within range.

When presented with a luminance of 0-255, after the reverse fft negative

values were found on some frames, and values > 265 I have seen.

These rather large errors can perhaps be reduced by using a more precise

fft / reverse fft algo.

New:

Added an option to set cutoff frequency and slope.

Selecting a gradual slope reduces 'ripples' in black at low cutoff frequencies.

See the .lsm text on the download page for details.

This all needs more investigation.

In some case the picture looks 'hairy' (all these small seemingly random

errors give an impression you are looking at a lot of irregular dots,

like register overflows?)

Will I use it? YES.

Original 720x576 testcard.

mjpegtools yuvrescaler 352x576,

note the aliasing appearing as low frequency vertical bands.

rescaler-yuv 352x576,

the high part of the spectrum set to zero before the reverse transform.

So just AT Niquist f / 2!

**
Processor load when using rescaler-yuv as a pipe between mpeg2dec and mpeg2enc,
(when decoding, and recoding as a resized video mpeg2 stream).
Values obtained from top:
mpeg2enc CPU usage 51.8% mem usage 16.5%
resizer-yuv CPU usage 42.9% memory usage 0.4%
mpeg2dec CPU usage 4.1% memory usage 0.6%
**

Download resizer-yuv and other programs source code (C) from the download page.

References:

The fft is based on the fftw package by Matteo Frigo and Steven G. Johnson.

mjpegtools by many authors.

bbmpeg rescaler is based on the work of Brent Beyeler.

The linux port of bbmpeg to transcode is by Gerhard Monzel.

Transcode by Dr Ostreich, with contributions by many others and me.

click here to see some handy GPL programs for the Linux platform.