JPEG Simulator (E2)

[Josef]

Edit: A newer version with full compression/decompression capability can be found later in this thread, here.


Warning: If you're not a math geek, this will probably not interest you!

This expression simulates part of the JPEG image format compression algorithm called the Discrete Cosine Transform (DCT). I built it to see how hard the math would be. You can find out what's involved in the complete algorithm by reading this article:
JPEG - Wikipedia, the free encyclopedia

This expression cannot read from or write to real .JPG files, nor does it do the entropy encoding to actually compress the data. It just does block splitting, two-dimensional DCT, quantization, and inverse DCT to get the original image back with some added noise. For a complete compression/decompression simulation, see my later post.

To start with, the expression uses a ranger camera similar to my E2 webcam to capture an image of the player standing in front of the chip. It's been overclocked using the same technique as the webcam to 2144 Hz, and can take regular or anti-aliased pictures at about 2 seconds per 64x64 pic.

Once the picture has been stored in an array, it is then processed block by block. Typical block size is 8x8 pixels, although any block size is valid as long as the screen dimensions are a multiple of the block size and both are square shaped. Set the SRes value in the expression for the screen resolution and the Res value for the block size. A 64x64 pic with block size of 8 will be processed in 4 seconds and scales up linearly with the total number of pixels.

The first pass takes the one-dimensional DCT of each horizontal row of pixels in the block, puts those results in a 8x8 block in a new array, then moves on to the next block. The second pass does the same one-dimensional DCT on each vertical column of results from the first pass and begins as soon as the first pass finishes a block. The third and fourth passes do the inverse vertical DCT and inverse horizontal DCT respectively, and all four passes overlap eachother to complete in almost the same time as it takes to do a single pass.

In between the second and third pass is the quantization step. This is the point where the results from the DCT are normally divided (rounded in my example) by given quantization amounts so that the final block has a lot of zeros that represent visual frequencies with such low power that they can be eliminated from the image without much noticeable effect. The size of the quantization divisors determine the final quality of the image - low numbers give a high image quality but lower chance for compression, and high numbers give a low image quality and higher compressibility. A good reference on quantization can be found here.

I used a diagonally gradiated quantization table based approximately on the JPEG standard table and also negatively scaled it to resemble the JPEG "Quality" setting of 0-100 (0 for very low quality and 100 for almost perfect quality). You can actually set it to a number below zero to keep decreasing the quality (and theoretically further improving compressibility).


What the digital screens in the screenshots represent:

The screenshots attached show the simulated compression and decompression of a 64x64 image that has been separated into 8x8 blocks.

Screen 1 is the original image as seen by the chip. The only effect applied to it is optional anti-aliasing, which can be toggled by pressing the num key 1.

Screen 2 shows a summarization of the DCT table for each block of the image at that quality level. The upper left corner of each block normally equals the average grey value (0-255) of the entire block. I've colored it red if it's greater than zero and greyish if it equals zero, mostly to show the separation of the blocks. All the other dots within each block represent the various combinations of vertical and horizontal frequencies and are white if non-zero and black if zero. With lower quality settings there will be more values that round down to zero and therefore less white dots.

Screen 3 is what the compressed image would look like. It will contain noticeable visual artifacts at lower quality settings.

Screen 4 is the absolute difference between the pixels of screens 1 and 3, and is exaggerated.

The info screens show the quality and AA status, as well as a crude estimate of possible compression ratio (number of non-zero pixels in DCT table / total number of pixels) and the average absolute per-pixel error of the final image. An error of 1 means that on average each pixel is off by 1 shade of grey in its range of 0-255.


How to use it:

Spawn the "jpeg simulator" file
Press the +/- keys to adjust the quality
Press 1 to toggle AA
Press 0 to take a picture of yourself
Press Enter to compress it
Press period (.) to reset the expression and screens in case something breaks.

[Beer]

Now there's something unique. Nice job.. that's actually pretty cool.

[Bobsymalone]

That's really cool. How fast is the compression? Is it viable for less laggy digital screen videos?

[Josef]

I had thought about possible uses for live video transfer over regular wires, but you really can't beat wirelink when it comes to speed / lag.

Consider the following:
My webcam runs at 2948 Hz, 44x the standard tick rate of 67 Hz, and scans/draws 4 pixels per execution, or 11,792 pixels/second. This means a 32x32 digital screen with 1024 pixels gets updated just over 10 times per second, about the minimum to be considered "video" quality (pathetic screen size aside). Here's a new video I took to demonstrate the speed/quality of a Wirelink camera:
[ame="http://www.youtube.com/watch?v=X7DnQHi6oPw"]YouTube - Wiremod Webcam video 2[/ame]

Uncompressed, and with 8-bit grey values (256 shades), this works out to potentially 11.5 KB of data generated every second. The Wirelink way of writing directly to memory, even 1 byte at a time, handles this no problem.

Can it go faster? A sad fact is you will likely reach a limit on the number of E2 ranger calculations you can do per second where the hit on real game FPS becomes unplayable. I experimented on gm_flatgrass using a bumped up server tick-rate (300) and an E2 overclocked 8x (the most efficient configuration). I set the expression to take between 6 and 9 ranger readings per run which equates to webcam speeds of 14, 16, 19 and 21 FPS. I did not even send the pixels to a screen, just gathered and stored them in an array. At those four speeds and pointing away from the expression into the sky to have the minimum possible video card impact, my game ran at real speeds of 150, 110, 70, and 45 FPS. At 10 rangers per execution it slowed the game down to 20 FPS, below the theoretical webcam speed of 23.

How about better quality? Doubling the screen size to 64x64 would mean 4x the number of pixels need to be filled, so even at the reasonable game speed of 45 FPS this amounts to a video at just over 5 FPS. Maybe a better result could be achieved with interpolation, but it quickly becomes obvious that 512x512 video is out of the question.

So, back to the 32x32 video at 10 FPS and reasonable game performance, how much compression would it take to send this over a regular wire? Let's do the math. Plain old wires (not Wirelink) can change at a maximum rate of four times per game tick. If you try to use an overclocked E2 to send something over the wire any faster, the chip on the other end ignores the change. At the standard server tick rate of 67 Hz this means you can send at most 268 different values over one wire per second. Sending 11,792 pixels at this speed would require no less than 44 wires between sender and receiver chips (the same as overclock rate, coincidentally).

Now for some mathemagics. Since wiremod uses 32-bit floating point for all values this means it can perfectly represent all integers up to 2^24, so you can quite easily multiplex three 8-bit numbers into a single value*. For example, to turn the 8-bit numbers A B and C into one larger number D, you write:
D = A + B*2^8 + C*2^16

And to get your original numbers back you use a combination of floor and modulus. The expression would be:
A = D % 2^8
B = floor( D/2^8 ) % 2^8
C = floor( D/2^16 )

So now you only need 1/3 the number of wires to send across the raw video, so 15 wires. But wait, using Vectors will let you send a 3 value vector across a wire at once, so now you only need 5 wires! But what would it take to do it with just 1 wire?

The real JPEG standard at 50% quality yields an average compression ratio of 15:1. Judging by my earlier screenshots I think a series of 50% quality pictures sent as a 10 FPS video seems entirely reasonable, and you would only need a single wire to transmit it (with room to spare!)

Because calculating a DCT requires you to sum a whole row of input pixels to come up with an output entry in the DCT table, it works faster with smaller block sizes. At a block size of 4x4 my expression as it's written now will crunch 1 pixel per execution. Lower block size actually increases image quality too (see attached screenshot). Using either some more duplication of code within the expression or higher operating frequency, I believe it's possible to compress 11,792 pixels in real time, then decompress them on the other end with only a frame or two of buffer lag.

But like I said in the beginning, Wirelink really is the way to go for video as it negates the need for compression. Saving images to a memory chip or EEPROM compressed to decrease the file size would be a far better use for this.



*You can actually use all 32 bits of the 32-bit floating point format to store 4 8-bit numbers, but there are a few problems with this method that would make it a hassle as a multiplexing scheme.

[Josef]

By the way, I've updated the attachments in my original post to fix the broken screens on dupe. It now supports on-the-fly changes to the digital screen size. Just change the SRes variable and the screens will reset themselves to the new size.

Next I will try the actual Huffman encoding that will do the compression of data. If that works, I may just try sending video over one wire

[Black Phoenix]

I must say that this is incredible, an analog compression chip would actually be really great to use with CPU - I already imagine possibilities for installing it on say BlackFOX. In theory it should be faster than just writing it in CPU, so try that.

[Josef]

I've never done anything in assembly programming. How fast can the wiremod CPU run anyway? I ask because I've already had a one-line E2 running at 24KHz and at a very playable 170FPS in singleplayer. Adding actual code would bog it down quite a bit I imagine, but enough to warrant using CPU? E2's high-level language seems easier when trying to get something from idea to program for the first time.

On that note, here's a sample E2 to find the optimal Huffman code for a given list of symbol probabilities. This could very well be overkill for a 32x32 image, as the space it would save would most likely be offset by the size of the Huffman table you'd need to store at the beginning of the image. Going with the sample table included in the JPEG Standard seems like a better idea for small images as I've found it's been within 5% of the optimal size in my test runs.

I will release another version of the JPEG Simulator once the compression part is in place. It will be a compress-only proof of concept for now.

What other sort of compression applications do you have in mind? (Lossy/Lossless?)

[Syranide]

Holy shit really

I would never guessed it to be even remotely feasible using the E2.

Really awesome work.

[gg12112]

This is really cool! Good job man!

[Josef]

One week and hundreds of test images later, I've approached what can be considered a crude simulation of the entire JPEG compression scheme. This newest chip captures an image at any resolution, performs Discrete Cosine Transformation on variably-sized blocks, sorts coefficients in zig-zag order, does run-length encoding on the resulting strings of zeros, assigns optimal (shortest-length) canonical Huffman codes for each unique symbol, adds a header containing info necessary to reproduce the file (in theory, haven't tested it yet), concatenates the variable length symbols into an array of 8-bit bytes, and transmits the entire thing to a receiver chip over a single vector wire at a rate of 36 bytes per game tick. Whew!

The next step will be to build the chip that can decompress the encoded image (and see how many bugs there are ). In theory, the final image should look exactly the same as the simulated one in Screen 3, as there is no further loss of information after the DCT stage.

Now for some compression results. The entire resultant data including header should come out to less than the original image. For example, screenshots 1-3 are of a 64x64 greyscale image:

Original uncompressed image size: 4096 bytes
At quality level 100 (nearly perfect) - Final size: 1990 bytes
At quality level 50 (minor image artifacts) - Final size: 728 bytes
At quality level 0 (moderate artifacts) - Final size: 584 bytes

Where the compression really shines is with large images and large ares of continuous or gradually changing tone. The image in screenshot 4 is 512x512 (262,144 bytes). At quality level 50 the only noticeable differences from the original image are some minor fringes at the contours, and it compresses to 11,169 bytes or 4% of it's original size! Quality 0 brings it down even further to about 3000 bytes (~1%) but with visible blocking.

How to use it:

Spawn the "jpeg compressor sim" adv. dupe ("jpeg2" is the E2 expression)
Edit the image size (SRes) and block size (Res) within the expression
Press the +/- keys to adjust the quality (+100 to -150)
Press 1 to toggle AA
Press 2 to toggle showing the intermediate DCT image (slows it down a bit)
Press 3 to toggle showing the simulated final compressed image (slows it down even more)
Press 0 to take a picture of yourself
Press Enter to compress it and transmit it to the receiver chip
Press period (.) to reset the expression and screens in case something breaks.

Within the expression, set Debug to 1, 2 or 3 and you'll get additional debugging info printed to the console.