Kodak YCC (Colorspaces II)

The Kodak 1 colorspace we saw last week doesn’t really capture the perceptual response to colors; the brightness is merely a mix of the RGB components, and the two other components are unbalanced “yellow vs blue” and “red vs cyan” channels. On the plus side, Kodak 1 can be computed in integers only, and perfectly reversibly. But what if we wanted a colorspace that is closer to our perception of colors?

Kodak 1 (Colorspaces I)

Images (and, by extension, video) compression depends strongly on the color space used. A color space is a (hopefully convenient) representation of colors. We’re all familiar with the RGB color space used by video hardware. The RGB color space is based on three standard primary colors: red, green, and blue. Combining these three colors, each with varying intensity, yields a wide gamut of perceived colors.

However, if RGB is intuitive, it is not a very good color space for compression because it doesn’t exploit any of our perceptual quirks. We’re very good at distinguishing small variation in brightness, but not so much in tint or saturation. Compression schemes need to exploit this in order to destroy information (and obtaining better compression). This is why almost all image and video compression algorithm out there use a different color space, one that represents color as brightness, and two (or more!) components that are more or less related to tint and saturation—or some other measure of difference of color.

Yes? No? Maybe? (Part II)

Last week, we had a look at how to implement a trool, or a tri-valued boolean what accepts true, false, and undefined. We remarked that the storage of an enum likely defaults to int, and that my poc wouldn’t play well with std::vector as that container has no specialization to deal with this new type.

A specialization would be interesting because we can do much better than using an integer to store three different values. We can do much, much better.

Yes? No? Maybe? (Part I)

Initializing arrays, or any variable for that matter, is always kind of a problem. Most of the times, you can get away with a default value, typically zero in C#C++, but not always. For floats, for example, NaN makes much more sense. Indeed, it’s initialized to not a number: it clearly states that it is initialized, consciously, to not a value. That’s neat. What about integers? Clearly, there’s no way to encode a NaI (not an integer), maybe std::numeric_limits::min(), which is still better than zero. What about bools?

Bool is trickier. In C++, bool is either false or true, and weak typing makes everything not zero true. However, if you assign 3 to a bool, it will be “normalized” to true, that is, exactly 1. Therefore, and not that surprisingly, you can’t have true, false, and maybe. Well, let’s fix that.

Paeth’s Method (Square Roots, Part VII)

In Graphics Gems [1], Paeth proposes a fast (but quite approximate) method for the rapid computation of hypotenuse,

.

The goal here is to get rid of the big bad because it is deemed “too expensive”—I wonder if that’s still actually true. First, he transforms the above equation:

.

This leaves us with the special case $\sqrt{1+u^2}, for which we can find the Taylor series

The numerators are given by A002596 and the denominators by A046161. So we can rewrite the whole thing as

.

*
* *

We’ll now try to get away with only a few terms of the series, and hope the precision isn’t too damaged. say we keep only the first two terms, how does it compare to other methods?

Let’s break down the graph:

• Blue: Circle of radius 10, the real hypotenuse;
• Green: True radius, 10;
• Dotted purple: Archytas, 3 iterations;
• Purple: Bakhshali’s method;
• Red: Paeth’s method.

Since Paeth’s method works well if , we may tweak it a bit. Letting

,

then letting

The imprecision is maximal when , or when the hypotenuse is at an angle of about 45 degrees.

*
* *

Originally, this hack was for considered for fast collisions/proximity testing. If you absolutely need a circular (or spherical) region, you need a square root, but that’s not the only option:

• metric, which is just the sum of absolute values ;
• metric, the usual euclidean distance;
• metric, which is .

The metric requires the square root, but the others are (if branches are cheap), rather inexpensive to compute—but they have counter-intuitive behavior. They might be useful for a first faster check, followed by Paeth’s method, followed by a full test.

---

[1] lan W. Paeth — VIII.5 A Fast Approximation to the Hypotenuse — in : Andrew Glassnet, ed., Graphics Gems, Morgan Kaufmann (1993), p. 427– 431

Encoding seeds

I was discussing procedural generation with one of my students when he brought up The Binding of Isaac, that delightfully quirky and creepy rogue-like game. One of the interesting features of the game is that the dungeons are randomly generated and that you can get the seeds for the dungeons and share them. A typical seed looks something like this:

QNFQ 8H7Z

So what does it encode?

Random Points on a Sphere (Generating Random Sequences III, Revisited)

While searching for old notes—that I haven’t found anyway—I returned to an old blog entry and I thought I was kind of unsatisfactory, with be best part being swept under the carpet with a bit a faery dust, and very handwavingly.

So let’s work-out how to uniformly distribute points on a sphere in a more satisfactory fashion.