June 2006

Below you will find a comparission of various deinterlacing filters, the interlaced source was created with mplayer using the phase=t and tinterlace=1 filters from the well known foreman video

all pictures where exported with mplayer -vo pnm and ppmtojpg --optimize --quality 90 why not -vo jpeg? well i didnt had -vo jpeg compiled in and -vo jpeg only accepts rgb input, so there wouldnt have been any advantage in using it …

Most deinterlacing filters only output one frame for every 2 fields that combined with the fact that some always choose the even, some always the odd and some always the first no matter if thats even or odd made this comparission less funny then i hoped originally, due to this little issue several filters (pp=ci and kerndeint IIRC) had to be feeded with vertically fliped video and tomsmocomp even needed -vf phase=b to output a frame based on the correct field and yes i of coarse did specify the top vs. bottom field first flag correctly as long as the filter had such an option …

Original non interlaced image
interlaced image mplayer -vf phase=t,tinterlace=1
mplayer -vf pp=lb (linear blend)
mplayer -vf pp=l5 (5tap lowpass filter)
transcode -J smartyuv
mplayer -vf pp=fd
mplayer -vf pp=md (median deinterlacer)
mplayer -vf pp=li (linear interpolate)
mplayer -vf pp=ci (cubic interpolate)
transcode -J dilyuvmmx
mplayer -vf kerndeint (Donald Graft’s adaptive kernel deinterlacer)
transcode -J smartdeinter (VirtualDub’s smart deinterlacer)
transcode -J tomsmocomp (Tom’s Motion Compensation deinterlacing filter)
mplayer -vf yadif=1:1
mplayer -vf yadif=3:1
mplayer -vf yadif=1:1,mcdeint=2:1:10
mplayer -vf yadif=3:1,mcdeint=2:1:10

ADPCM in general encodes differences between samples using a small number of possible difference values and adapts which values are allowed depending upon past difference values
( … we all know that)

ADPCM encoders normally work based on the principle that they select the best possible difference between the last sample and the current sample while ignoring both future and past, thats not optimal at all

a viterbi based encoder would select the optimal sequence of differences which minimize some distortion measure like the sum of squares, it achives this by successively finding the optimal encodings up to a specific state or in other words
instead of keeping a single sequence of encoded differenes of the past samples and then encoding the next difference
we keep track of the optimal sequence of differences/encoded bitstream up to the current sample for every state (0..88 step + a few sample values around the ideal one) next we just calculate the optimal bitstreams up to the next sample using the current sample and the optimal ones up to the last sample

maybe a concrete example would help, we use non adaptive DPCM here but the principle is the same …

lets say we have some input samples 0,2,6,4,-4
and our example encoder can encode +4,+1,-1,-4 differences
a conventional encoder would output 0,1,5,4, 0 distortion=18
optimal would be 1,2,6,2,-2 distortion=9
if we would force the first output to 1 and then use a conventional encoder 1,2,6,5, 1 distortion=27

viterbi encoder:

1. iteration
-2              distortion 4
-1              distortion 1
 0              distortion 0
 1              distortion 1
 2              distortion 4
2. iteration
 1, 0           distortion 5
 0, 1           distortion 1
 1, 2           distortion 1
-1, 3           distortion 2
 0, 4           distortion 4
3. iteration
-1, 3, 4        distortion 6
 0, 1, 5        distortion 2
 1, 2, 6        distortion 1
-1, 3, 7        distortion 3
 0, 4, 8        distortion 8
4. iteration
 1, 2, 6, 2     distortion 5
-1, 3, 7, 3     distortion 4
 0, 1, 5, 4     distortion 2
 1, 2, 6, 5     distortion 2
 0, 1, 5, 6     distortion 6
5. iteration
not possibl,-6
not possibl,-5
not possibl,-4
not possibl,-3
 1, 2, 6, 2,-2  distortion 9