Hard Problems

I like to solve hard problems, which is good since that's my job. This involves significant analysis, and complex problem-solving time and time again.

I have been sharing some of the details of the complex problem solving required to produce features in Painter, but for once I will discuss a tiny, almost lost bit of work I did at my current job. This involves a problem I have been seeking to solve for at least ten years: the lofting problem.

You might be asking yourself how I can talk about it, since it involves my current work. The answer is that this work is now in the public domain, since the process I am about to describe is detailed quite explicitly in US Patents 7,227,551 and 7,460,129. It is also not particularly secret or unavailable since it can be had by using Core Image, part of Mac OS X, as I will indicate.

The Lofting Problem

A Text Mask to be Shaded

If you have a bit of masked information, like text, it is classic design to create a version of the text that is 3D. I'm not talking about extruded letters, which are kind of passé. I'm talking about surface texture that makes the letters look puffy. And stand out. Here you see some masked text. Optima extra bold.

While working on something quite different, another employee, Kok Chen, and I came across something truly amazing.

We solved the lofting problem.

The Wrong Answer

Now, to introduce you to this hard problem, let me show you what happens when you try to create puffy text in Painter.

Here is the result. To do this, I used Apply Surface Texture using Image Luminance, and cranked up the Softness slider.

But all this can do is soften the edge. It can't make the softness sharper near the edge, which is required to get a really classy rendering.

The Right Answer!

Using the lofting problem solution we thought of, you get a much better rendering. The corners have a shine that goes right into them, because the curvature of the surface is continuously approaching a sharp point at the corner. Yet remains pleasingly rounded in the center.

Think of a piece of rubber or flexible cloth tacked down to a hard surface at all points along its edge, and then puffed full of air from underneath: lofted.

I think you get the point. The difference is like night and day! Before I implemented this in Core Image, this was not an easy effect to achieve, and probably couldn't even be done without huge amounts of airbrushing.

In Core Image, you might use the Color Invert, Mask To Alpha, Height Field From Mask, and Shaded Material effects to achieve this. And you might have to use a shiny ball rendering as the environment map, like I did. By the way, you can mock up most of this in Core Image Fun House, an application that lives in the Developer directory. Core Image is a great tool to build an imaging application. Just look at Pixelmator!

But How Was This Solved?

Exactly! This was a very interesting problem in constraints. You see, the area outside the text is constrained to be at a height of zero. The area inside the text is initialized to be a height of 1. This is the first image in sequence.

Now blur the text with an 8-pixel radius. It creates softness everywhere, and puts some of the softness outside the text area, because blur actually is something that causes shades to bleed a bit. This is the second image in sequence.

Then you clamp the part outside the text to be zero height again. This recreates a hard edge, and creates the third image in sequence. I have recreated this process in Painter. The clamping was done by pasting in the original mask, choosing a compositing layer method of darken, and dropping the layer, collapsing it back onto the canvas.

Next I take that same image and blur it by a 4-pixel radius. This produces the fourth image in sequence.

I clamp it back to the limits of the original text by pasting, choosing a darken layer method, and dropping, producing the fifth image in sequence.

Notice after the clamp step, the edge remains hard but the inside is becoming more accommodating to the edge, yet remains smooth in its interior.

With the next images in the sequence, I blur with a 2-pixel radius, clamp to the edge of the original mask, then blur with a one pixel radius and clamp to the hard edge of the original mask again to get the final lofted mask.

The last image in sequence is the shaded result, using Apply Surface Texture in Painter.

I should confess that these images are done at a larger scale (3X) and then down sampled for your viewing pleasure. Also, Painter only keeps 8 bits per channel, so the result was a bit coarse, and had to be cleaned up using the softness slider in the Apply Surface Texture effect.

In Core Image, we use more than 8 bits per component and thus have plenty of headroom to create this cool effect at much higher resolution and with fewer artifacts.

It becomes clear that the last several frames of this sequence look practically the same. This is because the blurs are smaller and the effect of the clamping against the edge of the original mask is less prominent. Yet these last steps become very important when the result is shaded as a height field, because the derivatives matter.

Smart People and Hard Problems

It should seem obvious, but it really does take smart people to solve hard problems. And a lot of work. And trial and error. So I'm going to tender a bit of worship to the real brains that helped shepherd me on my way through life and career. To whom I owe so much. And I will explain their influences on me.

The first was Paul Gootherts. Paul is an extra smart guy, and, during high school, Paul taught me the basics of computer programming. He, in turn, got it from his dad, Jerome Gootherts. A competent programmer at 16 (or earlier, I suspect), I owe my livelihood to Paul and his wisdom; he also conveyed to me something that (I think his uncle told him): if you are good at one thing, you can find work. But if you can be good at two things, and apply what you know and cross-pollenate the two fields, then you can be a real success. I applied this to Painter, and almost all of my life. And perhaps someday I'll apply it to music as well. Paul helped me with problems in computation and number theory, and his superb competence led me to develop some of my first algorithms in collaboration with him.

The second was Derrick Lehmer, professor emeritus at UC Berkeley. He taught me that, though education is powerful, knowledge and how you apply it is even more powerful. And it's what you do with your life that is going to make the difference. This has guided me in far-reaching ways I can only begin to guess at. Professor Lehmer ("Don't call me Doctor; that's just an honorary degree") helped me with understanding continued fractions and their application to number theory and showed me that prime numbers and factorization are likely to remain the holy grail of mathematical pursuits. Oh, and his wife Emma (Trotskaia) Lehmer, who was also present, provided many hours of interesting conversation on our common subject: factoring repunits (numbers consisting of only ones). I must credit a few of my more clever number theoretic ideas to her.

Other smart people have also provided a huge amount of inspiration. Tom Hedges had a sharp eye and an insightful mind. He taught me that no problem was beyond solving and he showed me that persistence and a quick mind can help you get to the root of a problem. Even when nobody else can solve it. Tom helped me with Painter and validated so much that I did. Without Tom, it would have been hard to ship Painter at all!

I have probably never met as smart a person as Ben Weiss. When the merger between MetaTools and Fractal Design took place, I became aware of his talents and saw first hand how smart this guy is. He can think of things that I might never think of. He confirmed to me that the power of mathematical analysis is central to solving some of the really knotty problems in computer graphics. And he proceeded to famously solve the problem of making the median filter actually useful to computer graphics: a real breakthrough. I've seen Ben at work since Metacreations, and he is still just as clever.

While Bob Lansdon introduced me to Fourier-domain representation and convolutions, it was really Kok Chen that helped me understand intuitively the truly useful nature of frequency-domain computations. He introduced me to deconvolution and also showed me that there were whole areas of mathematics that I still needed to tap to solve even harder problems. Kok retired a few years back and I sincerely hope he is doing well up north! Kok basically put up with me when I came to Apple and helped me time and time again to solve the early problems that I was constantly being fed by Peter Graffagnino. When it came time to work with the GPU and later with demosaicing, Kok Chen consistently proved to be indispensable in his guidance.

There are plenty other people who I will always refer to as smarter than myself in various areas, but they will have to go unnamed until future posts.

Prime Numbers

When you need to keep a secret, it's all in the numbers. The prime numbers.

Number theory is the basis of many cryptosystems these days. The famous RSA public-key cryptosystem is based on computing a number that is the product of two large primes. And because that number is hard to factor, your secret is safe.

When I was a kid, I became interested in numbers. It started when I read The Lore of Large Numbers, by Phillip J. Davis, first published in 1961. There was also Mathematical Recreations and Essays, by H. S. M. Coxeter and W. W. Rouse Ball. This led to unusual things like memorizing pi to 50 places, so I could recite it at any time. And I am sure I impressed my parents to death by reciting it. I can still hear the cadence of the digits in my head. Pretty soon I became interested in computation.

I often used to ride my bike to the San Jose State Math Library to pore through its stacks of math periodicals. I was especially interested in the Journal of the Mathematics of Computation (known as J. Math. Comp. in the biz). You can access the back issues of this journal online.

Yeah, to say that I was a nerd might have been understating the issue! But my obsession led to an interest in computation and, in particular, such things as prime numbers, factoring, and continued fractions.

Also, remember that this obsession happened in the late 1960s, before I even touched my first computer.

Prime Numbers

You can think of prime numbers as the basis set for all integers greater than 1 because every such integer can be formed by the product of primes. Kids first get exposure to prime numbers in the fourth grade (or earlier) when they learn to reduce fractions.

You probably know that the prime number sequence starts with 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...

The prime number sequence thins out as you get to larger and larger numbers. This is obvious because with larger numbers, there are more and more factors that can possibly divide a number. The prime number theorem states that, as x gets larger, the number of primes less than x generally approaches x/ln(x). Note that ln(x) is the logarithm base e (2.71828...).

In any case, there are a lot of primes. There are, for example, 50,847,534 primes less than a billion. You can easily prove that there are an infinite number of them.

Meeting a Number Theorist

In the summer of 1972, I was in a program at UC Berkeley for promising high-school-age mathematicians, sponsored by the NSF and chaired by Professor Frantisek Wolf. Having studiously read J. Math. Comp. for years, one of my idols was Derrick H. Lehmer, one of the world's foremost number theorists. Professor Lehmer was at Berkeley at the time. One day Paul Gootherts and I worked up our courage and went up the his office in Evans Hall and introduced ourselves to him.

Imagine my surprise when I found that he and his wife Emma were packing up his office! He was retiring that very week. So I struck up a conversation with him. It seems that we were both looking at continued fractions and their use in producing approximations to square roots using irreducible rational numbers. His interest was in factoring theory. Apparently constructing the continued fraction for the square root of a number was useful in producing factors near to the square root of a number, which was in turn useful in a certain primality testing method he was researching.

I accompanied him to the computer lab in the basement of Evans Hall and watched as he loaded a huge deck of card into an IBM card duplicating machine. When it failed and destroyed some of his cards, he exclaimed, "oh, lord! it's eaten my cards!". Of course, no one was more passionate about the use of computers in mathematics than Lehmer.

His wife Emma was apparently from Russia. I noticed that she had dozens of Russian volumes on the shelves in their joint office. I also spoke with her because I had read her paper on repunit primes. Repunits are decimal numbers consisting only of a long chain of 1's. An obvious factor of 10^n - 1.

They were surprised to say the least to find a 16-year-old kid with such an interest in number theory.

My friend Paul Gootherts had implemented a multi-precise arithmetic package in Fortran that we had run many huge calculations on, using a reasonably-fast Control Data Corporation computer that he had timeshare access to. So there was plenty to show and talk about. We had brought our books of calculations. I think we had calculated the cube roots of the first fifty primes to a thousand places each.

Prime Quads

When, for a given integer n, four numbers of the form 30n+11, 30n+13, 30n+17, and 30n+19 are all prime, they are collectively called a prime quadruplet. This is a very dense arrangement of prime numbers. Some ready examples are (11, 13, 17, 19), (101, 103, 107, 109), and (191, 193, 197, 199). I took a particular interest in this arrangement after looking at D. H. Lehmer's table of primes under 100,000. With my number-obsessed vision, they practically jumped out at me. Hell, they still do.

When I went to Caltech, I spoke with resident number theorist Marshall Hall about writing a program to find prime quads, which I did. It took advantage of the fact that the center number 30n+15 was a single number that you could subject to a barrage of tests. Divide it by a prime and compute its remainder. That remainder cannot be one of four values, otherwise one of the four numbers in the quad will be composite. It was an exceptionally fast method of determine whether a prime quadruplet seems interesting enough to try to factor all four numbers.

Because of my interest, Hall introduced me to the Markov Spectrum.

Factoring and Primality Testing

The dumbest way of factoring a number is simply to divide it by all the prime numbers less than or equal to its square root. But there is an easy way to speed it up: divide the number by another number that is the product of n primes. Then the remainder, which you design to be significantly smaller than the original number, may be divided by each of the n primes in turn, looking for a zero remainder. This process makes the search about n times faster. This is because the remainder is much smaller and thus the divisions into the remainder will take less work. You can organize this into a binary tree to speed it up even further.

These days, a number field sieve may be used to factor unusually large numbers. But, I suppose that you can choose a thousand-digit number and it simply cannot be factored on any known hardware.

In order for this technique to be useful, it is not enough that factoring is hard, but determining primality must be easy also. And it does appear to be easier than factoring, and these advances have occurred in the last ten years. In 2002, Agarwal, Kayal, and Saxena (AKS for short) found a polynomial-time primality test. It has since been improved by Bernstein and Lenstra. Unfortunately, even an improved AKS algorithm still takes about a year to determine primality of a 100-digit number.

But practically, a randomized algorithm such as the Rabin-Miller method for compositeness testing is, on the average, much faster. The Jacobi Sums algorithm is very practical, having been used to determine primality of exceptionally large numbers (up to 3395 digits). The Elliptic Curve Primality Proving (ECPP) algorithm has been used on a 15071-digit number, with a running time of 5.1 GHz-years. Of course, it can be distributed to multiple processors to speed it up. On ECPP, a 100-digit number takes about 2 seconds to prove primality on the average. Much faster than one year! The Rabin-Miller algorithm is feasible on numbers with a million digits, but remember that it can only produce a certificate of compositeness. But it is fast: a 300-digit number takes about 23 GHz-seconds to certify compositeness.

So, people have been combining the approaches, by doing a fast compositeness test in parallel with a primality test. In this way, the running time of primality testing (with an early-out for a composite number) is minimized.