Lair Of The Multimedia Guru

November 27, 2005

The snow wavelet

The default wavelet used by the snow codec in ffmpeg is a symmetric biorthogonal compact 9/7 wavelet with rational coefficients with properties very similar to the famous biorthoginal daubechies 9/7 wavelet, it was found by bruteforce search with the goal of having a simple lifting implemenattion and having many vanishing moments or almost vanishing moments, the daubechies wavelet has (4,4) our wavelet has (4,2) vanishing moments
The lifting coefficients are:

dau97 snow
-0.443506852 -15/32
-0.882911075 -4/5
0.052980118 1/16
1.586134342 3/2

The resulting wavelet and scaling functions look like:

One thing which is still annoying is the 4/5, while this can be approximated pretty well by a multiplication and a shift right but this tends to overflow so something like

x += x+x;
x += x>>4;
x += x>>8;
x >>= 2;

is needed, this one only differs from 4/5 by a factor of ~0.00001, alternatively the 4/5 can be merged into the unquantization step so that

\ | /|\ | /|\ | /|\ | /|\
 \|/ | \|/ | \|/ | \|/ |
  +  |  +  |  +  |  +  |   -15/32
 /|\ | /|\ | /|\ | /|\ |
/ | \|/ | \|/ | \|/ | \|/
  |  +  |  +  |  +  |  +   -4/5
\ | /|\ | /|\ | /|\ | /|\
 \|/ | \|/ | \|/ | \|/ |
  +  |  +  |  +  |  +  |   +1/16
 /|\ | /|\ | /|\ | /|\ |
/ | \|/ | \|/ | \|/ | \|/
  |  +  |  +  |  +  |  +   +3/2
is changed to
\ | /|\ | /|\ | /|\ | /|\
 \|/ | \|/ | \|/ | \|/ |
  +  |  +  |  +  |  +  |   -3/8
 /|\ | /|\ | /|\ | /|\ |
/ | \|/ | \|/ | \|/ | \|/
 (|  + (|  + (|  + (|  +   -1
\ + /|\ + /|\ + /|\ + /|\  +1/4
 \|/ | \|/ | \|/ | \|/ |
  +  |  +  |  +  |  +  |   +1/16
 /|\ | /|\ | /|\ | /|\ |
/ | \|/ | \|/ | \|/ | \|/
  |  +  |  +  |  +  |  +   +3/2

Now lets compare quality between the snow and daubechies 9/7 wavelets, this comparission has been done with JasPer with this change and tinypsnr (from ffmpeg) The used test image was the 256×256 lena grayscale image

Daubechies 9/7 wavelet Snows 9/7 wavelet
size PSNR
618 24.02
1283 27.32
3194 31.80
6503 36.82
13079 42.93
22945 47.14
size PSNR
622 24.03
1295 27.33
3212 31.82
6519 36.83
12981 42.87
22941 47.18
Filed under: Wavelets — Michael @ 22:09

November 25, 2005

Fast CRC

Ok kids, today we will look at how to quickly calculate a crc checksum, the naive way is to xor the crc polynomial with various shifts into the data to remove all 1 bits except the last 32 (or whatever length our crc polynom has) which from a mathemathical point of view is the data_polynom modulo the crc_polynom over GF(2)
now noone does that except maybe a few very smart or very stupid people :-) everyone else uses a 8bit->32bit look up table which simply contains the 32bit crc for each 8bit data polynom, more precissely:
LUT[i]= (i<<|CRC_POLY|) GF2_MOD CRC_POLY where GF2_MOD is the modulo operation between 2 binary polynoms over GF(2)
the actual code which uses this LUT looks approximately like:

for (i = 0; i < length; i++)
    crc = LUT[(crc&0xFF) ^ *buffer++] ^ (crc >>8);

a much faster method is to use 4 LUTs so that they gives the crc checksum 0,1,2,3 bytes ahead:
LUT[j][i]= (i<<(|CRC_POLY| + j*8)) GF2_MOD CRC_POLY
with that we can calculate the crc then by:

while(buffer<end-3){
    crc ^= le2me_32(*(uint32_t*)buffer); buffer+=4;
    crc =  tab[3][ crc     &0xFF]
          ^tab[2][(crc>>8 )&0xFF]
          ^tab[1][(crc>>16)&0xFF]
          ^tab[0][(crc>>24)     ];
}
while(buffer<end)
    crc = tab[0][(crc&0xFF) ^ *buffer++] ^ (crc >>8);

actually working code should be in ffmpeg/libavutil soon, if not ill post my messy proof of concept code

Filed under: Optimization — Michael @ 2:43

November 23, 2005

Testing Upload

Below you will hopefully find images of various amphibians i stumbled across with my camera about 6 month ago.
Frog1Toad1Frog2Frog3Frog4

Filed under: Nature,Pictures — Michael @ 20:59

Fast approximate max of 2 integers

Maybe you are lucky and your cpu instructon set has a fast maximum_of_2_integers instruction, but more likely you wont be so lucky, in that case a simple bitwise OR might be worth a thought.
Note: max(a,b) ≤ a|b < 2 * max(a,b)
This approximation is surprissingly more usefull then it seems at first

Filed under: Optimization — Michael @ 7:27

Fast greatest common divisor

How do we find the greatest common divisor of 2 integers? Try all integers which are ≤ then the arguments and select the largest which divides both with no remainder, works but its too slow. Or maybe factorize both, take the common factors and multiply them together like they probably told you in school, but thats still far too slow for anything but the small numbers in school excercies
(more…)

Filed under: Optimization — Michael @ 7:08

November 22, 2005

Fast integer square root

How to calculate the square root of an integer? (unsigned int)sqrt(x) sure but that is slow on many CPUs (~127 cpu cycles on a P3) it also needs a FPU, which may or may not be a problem, how can we do this quicker? lets see
(more…)

Filed under: Optimization — Michael @ 17:21
« Previous Page

Powered by WordPress