[sldev] [patch] OpenJPEG DWT optimizations

Dzonatas dzonatas at dzonux.net
Wed Apr 4 00:30:33 PDT 2007


Hello,

Awesome!

I did some more tests on the DWT to figure out what and how it can be 
optimized further.

One of my tests had an overall end-to-end time inside of the DWT of 
about 10 seconds. I was able to shave off almost 3 seconds with some 
simple vectorization. That would mean 7 seconds left.  I went back to 
figure out what took the longest.  I cut out all the calculation and 
just simulated the data flow. That revealed a little over 6 seconds of 
pure data manipulation. That means it would in theory take around 1 to 2 
seconds just in pure calculation of the DWT in the lifting scheme of how 
it is setup now.

This means over 50% of the time spent in the the OpenJPEG DWT is in the 
overhead of data manipulation.

How does this compare with KDU?

First, I simply ran KDU with no options except to do the same input and 
output as the test above with OpenJPEG. The test showed that KDU ran in 
less than a second in the DWT.

Now, you may wonder how KDU does it less than a second. First, KDU 
defaults to heuristic samples so that similar input on calculation will 
give previous results. Next, KDU defaults to use 16 bit integer math 
instead of 32 bit as in OpenJPEG.   With 16 bit integer math, KDU is 
able to manipulate 8 integers in a vector and to perform a calculation 
over 4 integers in a vector. However, to JPEG2000 expects at least 32 
bit integer math, so that means KDU samples only a portion of every bit 
to fit in a 16 bit integer math. The basic run of KDU outputs an image 
that is not of its highest possible quality.  Quality is traded for speed.

KDU has an option "-precise" that forces it to use 32 bit integer math. 
I don't know the option to turn off its heuristics, but just with the 
-precise option added made KDU's speed increase up to 2 seconds just in 
DWT time for the same image.

That 2 seconds in DWT time in KDU is pretty close to the theoretical 
time I presented above, 2 seconds, for the DWT without the overhead of 
data manipulation. My bet is that KDU doesn't count the data 
manipulation time in its DWT time counter.

I'll look into an optimization for the data manipulation. =)

Enjoy

Francois-Olivier Devaux wrote:
> Hi,
>
> I went quickly through the patch, did some quick testing and it seems 
> to work great !
> Great speeding improvement !
>
> We'll have to do some more throughout testing with some strange images 
> sizes to test it deeply, but it seems the code will be integrated in 
> the next OpenJPEG version.
>
> Great job,
>
> François-Olivier
>



More information about the SLDev mailing list