Of Colorspaces and Image Compression (Part II)

Last week we discussed briefly how we can represent color using either RGB or a colorspace that’s more easily amenable to decimation by a psychovisual model.

This week, we’ll have a look at just how tolerant the human visual system is to color (hue/saturation) variations.

Of Colorspaces and Image Compression (Part I)

The art of lossy compression consists almost entirely in choosing a representation for your data in which you can easily figure out what data to destroy. That is, if you’re compressing sound, you must transform the waveform into a domain where you can apply a psychoacoustic model that will guide decimation, that is, the deletion of part of the information, part of the information that won’t be heard missing. If you’re rather compressing images—that will be our topic today—you must have a good psychovisual model that will help you choose what information to destroy in your image

The model can be very sophisticated—and therefore computationally expensive—or merely a good approximation of what’s going on in the observers’ eyes (and mind).

But let’s start with the beginning: representing color

Pruning Collatz, somewhatz

I’ve visited the Collatz conjecture a couple of times before. I’ve played with the problem a bit more to understand how attractors work in the Collatz problem.

So what is the Collatz conjecture? The conjecture is that the function

Always reaches one. But the catch is, nobody actually figured out how to prove this. It seems to be true, since for all the ever tried the function eventually reached 1. While it is very difficult to show that it reaches 1 every time, it’s been observed that there are chains, let’s call them attractors, such what when you reach a number within that chain, you go quickly to 1. One special case is the powers-of-two attractor: whenever you reach a power of two, it’s a downward spiral to 1. Can we somehow use this to speed up tests?

The Zero Frequency Problem (Part I)

In many occasions, we have to estimate a probability distribution from observations because we do not know the probability and we do not have enough a priori knowledge to infer it. An example is text analysis. We may want to know the probability distribution of letters conditional to the few preceding letters. Say, what is the probability of having ‘a’ after ‘prob’? To know the probability, we start by estimating frequencies using a large set of observations—say, the whole Project Gutenberg ASCII-coded English corpus. So we scan the corpus, count frequencies, and observe that, despite the size of the corpus, some letter combinations weren’t observed. Should the corresponding probability be zero?

Jouette’s Attractor

I have been reading a lot of mathematical recreation books of late. Some in English, some in French, with the double goal of amusing myself and of finding good exercises for my students. In [1], we find the following procedure:

Take any number, digits long, make this number . Make the number made of the sorted (decreasing order) digits of , and , the number made of the sorted (increasing order) digits of . Subtract both to get : . Repeat until you find a cycle (i.e., the computation yields a number that have been seen before).

Jouette states that for 2 digits, the cycle always starts with 9, for 3 digits, it starts with 495, for 4 digits, 6174, and for 5 digits, 82962. For 2, 3, and 4 digits, he’s mostly right, except that the procedure can also reach zero (take 121 for example: 211-112=99, 99-99=0). For 5 digits, however, he’s really wrong.

Perfect Hashing (part I)

A few days ago, a friend asked me how to write, if even possible, a hash function that had no collisions. Of course, it’s relatively easy to get a reasonably good hash function that will give the expected amount of collisions (especially when used as usual, modulo the size of the table). But what if we do not want collisions at all? What can we do?

There are some hash functions, known as perfect hash function, that will yield a different hash for every key from a a priori known set of keys, say . Are they hard to build? Fortunately, not really. Can we exploit the uniqueness of the hashed value to speed look-ups up? Yes, but it’s a bit more complicated.

Take That, Fermat!

You’ve certainly heard of Fermat’s last theorem stating that

has no integer solutions for . Well, guess what:

.

Take that, Fermat!

Yet Another Square Root Algorithm (part II)

last week, we saw that we could use a (supposed) efficient machine-specific instruction to derive good bounds (but not very tight) to help binary search-based and Newton-based square root extraction algorithms go faster. Last week, we saw that the technique did lead to fewer iterations in both algorithms.

Now, does the reduced number of iterations translate into actual, machine speed-up?

Yet another Square Root Algorithm

Computing (integer) square root is usually done by using a float square root routine and casting it to an integer, possibly with rounding. What if, for some reason, we can’t use floats? What are the possibilities?

One possibility is to use binary search to find the square root of a number. It may be a good choice because it will only perform a number of iterations that is half of the (maximum) numbers of bits of the number (we will explain why in a moment). Another possibility is to use Newton’s method to find the square root. It does a bit better than binary search, but not exceedingly so: on very small integers, it may iterate a third as much iterations as binary search, but on large integers, it will do only a bit fewer iterations. Can we do better? Yes!

Count Like an Egyptian (Part II)

In a previous entry, we discussed egyptian fractions and, in particular, a greedy algorithm to convert them. We noticed that, once in a while, the greedy algorithm generates a really large denominator, despite harmless-looking fractions:

So, I had an idea to, maybe, minimize the size of the maximum denominator.