Mœud deux

August 7, 2018

Pairing functions are fun. Last week, we had a look at the Cantor/Hopcroft and Ullman function, and this week, we’ll have a look at the Rosenberg-Strong function—and we’ll modify it a bit.

Read the rest of this entry »


Mœud

July 31, 2018

Pairing functions are used to reversibly map a pair of number onto a single number—think of a number-theoretical version of std::pair. Cantor was the first (or so I think) to propose one such function. His goal wasn’t data compression but to show that there are as many rationals as natural numbers.

Cantor’s function associates pairs (i,j) with a single number:

…but that’s not the only way of doing this. A much more fun—and spatially coherent—is the boustrophedonic pairing function.

Read the rest of this entry »


Pairing Functions

September 27, 2011

Sometimes you have to encode reversibly two (or more) values onto a single one. The typical example of a pairing function that encodes two non-negative integers onto a single non-negative integer (therefore a function f:\mathbb{Z}^*\times\mathbb{Z}^*\to\mathbb{Z}^*) is the Cantor function, instrumental to the demonstration that, for example, the rational can be mapped onto the integers.

In a more pragmatic way, it may be necessary to encode two values onto one for data compression purposes, or to otherwise exploit a protocol that does not allow many distinct values to be sent separately. The simplest way of pairing two integer is to interleave their bits, for example, with something like:

Read the rest of this entry »


Live Video Color Gamut

December 22, 2009

The other day—well, a year ago or so—I was invited to visit CBC’s digital TV studios in Montréal by the SMPTE Montréal. We were shown around, even in the somewhat small control rooms. Amongst all the displays, dials, monitors, and misc. blinkenlights, I noticed a small LCD display showing an hexagonal projection of the current show’s color gamut in YC_rC_b (or maybe YP_bP_r?), probably for quality assessment purposes. I thought it was pretty cool, actually.

example-cropped

Let’s see how we can realize this projection with as little CPU time as possible.

Read the rest of this entry »