Re:Ex-YouTube Man Builds Graphics Card for Entire Internet
by astrange on Friday May 31, 2013 @03:30AM
(#5797347)
> JPEG encoding, for instance, utilizes an O(n*log(n)) frequency analysis algorithm called a Discrete Cosine Transform.
Scuse me?
JPEG's frequency transform is a set of fixed linear transforms and is always 8x8, so this step is just O(n) of the area of the image. Also, it's not really "a DCT", just any approximation that will look good when run through the approximation of the opposite transform at the other side.
The compression steps after are the most difficult, since they have poor ILP and can involve division. But JPEG is really simple, it's not a burden these days.
One interesting part of it is minimizing the memory use of your application, by using the smallest possible ring buffer for pixels rather than keeping the whole image in memory at once.
Scuse me?
JPEG's frequency transform is a set of fixed linear transforms and is always 8x8, so this step is just O(n) of the area of the image. Also, it's not really "a DCT", just any approximation that will look good when run through the approximation of the opposite transform at the other side.
See http://multimedia.cx/eggs/dct-pr/.
The compression steps after are the most difficult, since they have poor ILP and can involve division. But JPEG is really simple, it's not a burden these days.
One interesting part of it is minimizing the memory use of your application, by using the smallest possible ring buffer for pixels rather than keeping the whole image in memory at once.