Author Archives: [maven]

Rate-Distortion Graph

Leave a reply

I’ve invested a bit of time in getting some nice rate-distortion graphs out of my wavelet image compression library. Now that it’s embedded, the process is fairly easy: Compress once into a single file and then decompress only enough bits from the file until the desired rate is achieved. As such, the graph also shows the quality over the progress of the file.

Here is an example of one such graph, for a 708×1024 image of Mena Suvari (which unfortunately comes from a JPEG source and thus has block noise), as the Lena image (notice the name similarity? ;)) is past its prime IMO, especially the color version has plenty of noise in the blue channel. The image was encoded in the YCoCg colour-space, which explains the slightly higher quality of the green channel and why even the highest rate is not lossless. Compared to the RGB version, the YCoCg representation incurs a mean-square error of ~0.25 (which results in the root mean-square error of 0.5 shown).

Rate / Distortion curve for a colour image of Mena Suvari

In theory, the rate/distortion graph should have a negative, but monotonically increasing derivative (which in normal language means something like “bigger improvements are closer to the beginning of the file”). We try achieve this by scheduling data units (which are essentially bitplanes of blocks) by how much they reduce the error in the coded image for each bit of their size. There are two reasons for this “close-but-not-quite-monotonically-increasing-slope”. One is that the error (distortion) is not computed exactly; instead I use an approximiation that based on the wavelet transform used. The other is the fact that we deal with packets / data units / blocks of finite size, and as soon as more than one channel is written to a single file, it becomes evident that a single packet will only improve a single channel – which in turn means the other channels have a stagnating improvement (zero derivative) for the size (or duration) of that packet.

These plots also make it easier to spot differences (usually either improvements or regressions) for changes in the code, so I’ve created graphs for all my test images, so that I can make these comparisons more easily in the future.

I’ve also taken an old pre-3.1 version (thank you, darcs!) that still used the recursive quantizer selection to produce similar plots (taking much longer as the image had to be compressed anew for each rate) and the result was pretty much a draw, in spite of the embedded version having to store a bit more sideband data (number of bitplanes for each block in the header, and which block is coded next in the bitstream itself). All of which makes the embedded version the “better choice”, due to its other advantages such as simpler code and “compress once, decompress at any rate”.

Patenting CPU instruction sets and $150 PCs

Leave a reply

Via a blurb on ArsTechnica about a Chinese $150 PC, I’ve stumbled upon the Story of Lexra, a now out-of-business semiconductor IP provider. A few things in that article struck me as interesting, namely

  • You cannot patent an instruction set.
  • “You can patent designs and methods that are necessary to implement a particular unusual instruction that is part of the instruction set.“
  • Guess what Intel has patents for MMX instructions on… Although this point is now moot, as AMD and Intel have cross-licensing agreements, it was an interesting way to stop AMD from offering “fully compatible” CPUs (which resulted in AMD offering 3Dnow).
  • “One interesting problem with the patent system is that one institution, the PTO, determines whether a patent is valid but a different institution, the courts, determine whether one infringes. It is entirely possible for the two institutions to interpret a patent differently and for either a non-infringer to be wrongly convicted or an infringer to get away with their crime.“

Scary, isn’t it?

Phoenix Wright – Ace Attorney (Nintendo DS)

Leave a reply

Phoenix Wright is a bit an odd title for Western gamers, but I sincerely hope that more niche titles like it make their way over here from Japan. It’s a strongly structured adventure (although some would argue it is not much more than a heavily scripted visual novel), but that is not to its detriment in my opinion.

In your role as defense attorney, you alternatingly look for clues / evidence, and then progress to the actual trial, where you cross-examine witnesses to uncover contradictions in their testimonies. While that may not sound like much, the contradictions become increasingly hard to find and the overall story (as in the crimes themselves with their motivations and their relation to each other) meshes all of that into an interesting narrative.

There are 5 cases altogether, 4 of which are ported from the Japanese GBA game, and a much longer 5th case, which was specifically written for the DS and uses many of the system’s features very well (touch-screen, microphone, 3D graphics). Overall, the game took me about 10-12h to complete, and I very much enjoyed finding clues and contradictions, although as mentioned before, the structure is very rigid and usually there is only one correct way of doing things.

Size-optimising Code

Leave a reply

I try to keep my image compression code fairly simple; it doesn’t do the best lossy compression, it doesn’t to the best lossless compression, but it does both fairly well, fairly fast, and without introducing much code bloat.

As a measure of this, I simply look at the size of the resulting executable for my simple test-application, wako. This can of course be very misleading, but it certainly is some measure of complexity, and I try to maintain its size below 40,000 bytes. But generally speaking, I want to do this by simplifying the code and making it more reusable, not by applying some complicated tricks that make the code harder to read but result in smaller a smaller binary.

So after fixing a problem in the implementation (using a fixed factor to convert from a floating point error-estimate of the mean-square error to a fixed point representation, which could then overflow), the code had grown above the “magic 40,000” mark. This was due to the fact that many channels can be interleaved into a single file, but to do that properly they each have to have comparable error estimates.

One obvious place to reduce the size, is the very basic command-line argument parser (which is not part of the library itself, but the sample application), which when commented out, reduces the size of the binary by 8kb! Rewriting this explicit parser to be data-/table-driven did not reduce the size as much as hoped, but it was enough.

39,849

As an aside, did you know the order of declarations within a structure has a non-negligible effect on code-size? 😉

Wavelet 3.2

Leave a reply

As I’ve taken a two-day vacation pre-easter, I’ve gotten some more work done on my Wavelet Image Compression Library (and not played games as some of my colleagues were led to believe ;)).
Before this version all the subbands of an octave (i.e. HD, VD, and DD coefficients) were written as a single block in an interleaved manner. The changes I’ve made give each subband its own block, which increases the number of blocks, and thus allows for better and more fine-grained scheduling (which increases compression performance). Unfortunately, this led to a three times slower error estimation, which I then managed to cunningly avoid by computing the estimate for 3 blocks at a time.
Other changes include a more consistent behaviour for the -bpp command line switch, bug fixes to the scheduling where my accumulated fixed-point error estimates would overflow, and quite a few other things.
A experimental change was an exact error estimation, which I’ve then removed again as the code became unreadable, it was slow as hell, and didn’t actually help that much.
There is now a Darcs repository here (don’t try browsing there) from which you can get the current version and against which you can send me patches. You can also read my totally unfunny changelog entries if you need more information on the changes between versions.

Alastair Reynolds – “Pushing Ice”

Leave a reply

I finished reading Alastair Reynolds “Pushing Ice” about a week back. I was sceptical as it didn’t take place in the Revelation Space universe and was put off by the mediocre Amazon-reviews, but I think the people who gave it those marks didn’t understand it at all.
He manages to convey so much more in 500 pages (which I finished in the span of 2 days) than – say – Peter F. Hamilton in 2000… You have to pay some attention as much information is given in passing or has to be inferred, but this is to the books’ credit, not to its detriment.
It starts of as an amalgam of so many things – alien artifact / first contact story, moving on with strong influences of some Arthur C. Clarke books, but it pulls through brilliantly into something I never saw coming, never forgetting the human touch (and reminding me that fights between women are scary!).
I even liked the ending (which I rarely do), because it stops where it ought to.
Very recommended!

Cocoa and Objective C

5 Replies

I am currently writing a graphical user interface (GUI) for my Wavelet Image Compression Library that will allow for selecting and inspecting compression settings. As my “main computer” for the past year has pretty much been an Apple Mac mini (with an x86 laptop for Linux (work) and Windows (games)), I decided to write it in Cocoa, learning the Objective-C language and the Cocoa class library / ApplicationKit at the same time.

I quite like the language (ignoring the message send syntax in square [] brackets) as you’re always aware when you’re doing OO stuff like sending messages, or writing simple C-code. It is very dynamic as essentially all binding happens at runtime and dynamically (which you of course pay a speed penalty for, but that shouldn’t matter much for high-level GUI code).
The Objective-C class library (“Foundation”) is very clean, always making a distinction between mutable and immutable versions of objects, and seems very complete with all the conveniences of modern OO.
Using the Interface Builder to create not only the actual interface, but instantiate classes and bind actions / outlets is a very nice touch. You can usually get a semi-functional mock-up of your application without writing any code at all, especially when using things like Cocoa Bindings, which allows for introspection via Key-Value-Coding (KVC) conformant objects. In essence, the AppKit “knows” how to access your member variables and set them according to the rules you defined in Interface Builder.

There are also some things which aren’t so nice. Documentation in some areas is lacking (e.g. using NSTreeController without CoreData or a dataSource), some things that look simple on the surface definitely aren’t under the hood (Key-Value-Observation replacing some of my objects by proxies, but at least they remembered to properly override isEqual: ;)). Memory management is also something which my head took some time to wrap itself around properly: every object is reference counted, but the crux is NSAutoreleasePool which is a bit like poor-man’s garbage collection. My problem with that wasn’t what it does, but when it does it. Oh, and namespace support would be nice…
Today’s challenge was to extend the NSOpenPanel of an NSDocument-based application with an accessoryView. I got it working in the end, but it wasn’t trivial (subclass NSDocumentController, changing stuff around in the Interface Builder to make sure the subclass is instantiated first, creating a separate .nib file for the accessoryPanel and praying that the View gets released properly).

Most of the time it’s a joy to work with, and a welcome change of pace from the dreadful writing of Windows GUIs in MFC. I only wish a decent Objective-C compiler with Foundation class library were available there as well (GNUStep doesn’t count, unfortunately). Might be an interesting idea to try to get Objective-C working on Microsoft’s .NET platform…