POCS and Color Spaces

If you’re doing image processing, you’ve probably had to transform your image from one color space to another. In video coding, for example, the RGB image is transformed into YPrPb or YCrCb so that most of the visually relevant information is packed into the Y component which is essentially brightness. Subsampling the chroma bands (Cr and Cb) provides additional means for compression with little perceptual quality loss. While the human eye is very good at detecting brightness variation, it’s not very good at detecting subtle changes in chroma, either saturation or hue.

The thing is that very often, there are color space transformation matrices found in text book but they’re not, due to rounding (and other possible errors), always exactly inverses of each other. This week, I will discuss how we can use projections onto convex sets (POCS) to make sure that reduced precision matrices are exactly (within a given precision) reversible.

Rediscovering The Past

Progress, as conceived by most people, consists in replacing older objects, techniques, or philosophies by newer, better, ones. Sometimes indeed the change is for the better, but sometimes it is just change for change—ever had an older device of some sort that was perfectly adequate for your usage, yet you still replaced it with a newer version with no net gain? Unfortunately, the same happens with ideas, especially with mathematics and computer science.

But there are lessons to be learnt from the past. I’m not talking about fables and cautionary tales; I’m talking about the huge body of science that was left behind, forgotten, superseded by modern techniques.

Being Shifty

Hacks with integer arithmetic are always fun, especially when they’re not too hard to understand (because some are really strange and make you wonder what the author was thinking when he wrote that). One such simple hack is to replace divisions or multiplies by series of shifts and additions.

However, these hacks make a lot of assumptions that aren’t necessarily verified on the target platform. The assumptions are that complex instructions such as mul and div are very slow compared to adds, right shifts or left shifts, that execution time of shifts only depends very loosely on the number of bit shifted, and that the compiler is not smart enough to generate the appropriate code for you.

Suggested Reading: Mrs. Perkins’s Electric Quilt

Paul J. Nahin — Mrs. Perkins’s Electric Quilt: And Other Intriguing Stories of Mathematical Physics — Princeton University Press, 2009, 391 pp. ISBN 978-0-691-13540-3

(Buy at Amazon.com)

In this book, you will discover the topic of mathematical physics—or physics mathematics, depending on how you look at it—through a series of counter-intuitive results (counter-intuitive for the non-physicist, that is). The author shows that with logic and (quite) a bit of mathematics, you can obtain surprising but correct results. A good part of the book rotates around the topic of gravity (boom, tss.) but also presents other topics such as air drag, partitionning squares into squares optimally, infinite resistor networks, and random walks. The narrative style is clear and simple; and while the mathematics in the book may seems scary at first, you still get the point; someone with just a little background in mathematics will still get the essential; someone with a better background in mathematics will get the best of it.

Another worthwhile note is that the typography of mathematical equations is simply exquisite; it is very well typeset. Something that is getting rare these days for a grand public book.

Soap Geometry

Sometimes, we look for relation between objects of different dimensionality, search for proportionality rules and try to factor away constants, or, at least, figure out what they are made of. A cute example of which came to me in the shower…

Knowing your weight, can you know how much soap you use?

A matter of interpretation

In calculus 101, amongst the first things we learn, is that the derivative a function is the slope of the tangent to the function, that is, the instantaneous slope at some point on the function. We have, for some function that the derivative is given by:

So the formulation looks like a slope, and it is taught that it is a slope as well; all the concepts surrounding differentiation are expressed in terms of slopes of tangents, and that’s OK, because that’s what they are.

But suddenly, in calculus 201, we learn how to find the anti-derivative of a function, also known as the integral. But the metaphor changes completely: we’re know talking about the area under the curve. Wait. What?

Suggested Reading: Prisoners Dilema

William Poundstone — Prionner’s Dilema — Anchor, 1993, 294 pp. ISBN 978-0385415804

(Buy at Amazon.com)

This book isn’t really an introduction to game theory, nor a von Neuman biography, nor a history lesson on the cold war era. Most of the book is devoted to either the cold war logic or to game theory, and little to von Neumann who, really, only serves as the main thread bringing game theory and the cold war together. Nevertheless, it’s a quite cromulent introduction, while not very math-oriented, to the fundamentals of game theory where two (or more) players are confronted and try to maximize their gain. Can or should player cooperate? If so, why?

If, like me, you think that the cold war is rather boring, just skip those part, it will still be a quite interesting read.

The Complex Beauty of Simplicity

As I have said before, some of my friends took the very wise decision to go back to school (that is, university) and, accordingly, they’re doing all the undergrad maths courses. As I try to help them whenever I can, I decided to ask them to solve a simple puzzle… or so I thought.

So the problem is as follows:

You have a circle of center , radius and some point , with . Find the projection of point against the circle with center and radius . The method should work whether is inside or outside the circle.

The Large Hideous Collatzer

Mathematics is still full of surprises. The solution to simple to state problems may elude mathematicians for centuries. One example is the celebrated Fermat’s Last Theorem (stating that equations of the form have no integer-only solutions for ) that was finally solved by Andrew Wiles with tools Fermat couldn’t possibly know nor understand¹.

Another one of those problems is the Collatz Conjecture. Proposed by Lothar Collatz in 1937, the conjecture is that a simple recurrence function—that we will discuss in detail in just a moment—terminates for all natural numbers. This one, however, isn’t solved yet.

Leafing Through Old Notes

Leafing through old notes, I found some loose sheets that must have been, at some time, part of my notes of my lectures on external data structures. I remember the professor. He was an old man—I mean old, well in his 70s—and he taught us a lot about tapes and hard drives and all those slow devices. As a youth, I couldn’t care less about the algorithms for tapes, but in retrospect, I now know I should have paid more attention. So, anyway, the sheets contains notes on how to compute average rotational latency and average (random) seek time.