Ohta (Colorspaces III)

April 24, 2018

Let’s continue with lesser known color spaces. In 1980, Yu-Ichi Ohta [1] to segment images based on colors, and to do this, introduced a new colorspace—or more precisely, two variants of the same color space.

Ohta’s concern wasn’t image coding but region separation. He supposed (without much evidence) that a color space with a basis close to the principal components of the colors in the image should be maximally discriminant. He then proposed that the colorspace

Read the rest of this entry »

Yes? No? Maybe? (Part II)

March 27, 2018

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.

Read the rest of this entry »

Pretty Printing a Tree in a Terminal

December 6, 2016

More often than I’d like, simple tasks turn out to be not that simple. For example, displaying (beautifully) a binary tree for debugging purpose in a terminal. Of course, one could still use lots of parentheses, but that does not lend itself to a very fast assessment of the tree. We could, however, use box drawing characters, as in DOS’s goode olde tymes, since they’re now part of the Unicode standard.


Read the rest of this entry »

Serializing Trees

September 6, 2016

Quite a while ago I discussed using flat arrays and address calculations to store a tree in a simple array. The trick wasn’t new (I think it’s due to Williams, 1964 [1]), but is only really practical when we consider heaps, or otherwise very well balanced trees. If you have a misshapen tree, that trick doesn’t help you. It doesn’t help you either if you try to serialize a misshapen tree to disk.

But what if we do want to serialize arbitrarily-shaped trees to disk? Is it painful? Fortunately, no! Let’s see how.

Read the rest of this entry »

Interpolation Search

January 19, 2016

We all know about binary search. It’s been with us such a long time. Knuth thinks it’s first appearance in print is in the Moore School Lectures, in 1946. The technique search for an item in a list by halving, iteratively, the searched portion. Its complexity is O(\log n) for a list of n values, making it a very efficient algorithm for searching.

One may even be tempted to think that it’s in fact optimal, that we can’t do significantly better. Is that so?

Read the rest of this entry »

A Bit About Bit-Fields

January 5, 2016

Let’s make a detour through low-level programming this week. Let’s talk about bit-fields and some of their quirks.


Read the rest of this entry »

the Dutch Flag Problem

December 29, 2015

While preparing my lecture notes on sorting, I rediscovered the Dutch flag problem proposed by Edsger W. Dijkstra quite a while ago. This problem is relevant in the context of sorting, especially for variants of Quicksort, where you want to create not two but three partitions.


Like many problems, the Dutch flag problem has a very simple statement. Say you have an array with three types of value, how can you arrange them so that all the items of the first type is at the beginning of the array, the items of the third at the end (and, of course, leaving the second type between the two)?

Read the rest of this entry »