The Haar Transform

Saturday, June 24, 2006

9:52 AM

In my posts "15 Exercises to Know a Programming Language," I suggested some exercises investigating the Haar wavelet, the simplest wavelet. I intended to leave it as is so that people could discover this fascinating subject on their own, but a couple of questions I've received have made it impossible for me to hold my tongue.

 

Okay, to review: The Haar transform works by transforming an array of values into an array of average and differences-from-the-average. Thus, [8, 4] becomes [6, 2], since (8 + 4) / 2 = 6 and 8 - (8 + 4) / 2 = 2. Similarly, [8, 4, 3, 9] becomes, first, [6, 6, 2, -3] (1st and 3rd positions as per previous, 2nd and 4th same transform applied to 3 and 9).

 

What happens when you apply this transform to a real-world signal? For instance, a photo. The left of Figure 1 shows "Lena" in lovely 256x256 grayscale. The right of the figure is a visualization of the very first step of the Haar transform. Cool, huh?

The upper-left-most 64x64 block is now a quarter-resolution image of the original. That makes sense, since it's the average of the previously-created average. Now consider the 64x64 blocks as we move across (or down). First, we have the average of the edge-map: a low-resolution version of the 2-pixel scale edge map. The third block is edge-map of the average and the fourth block is an edge-map of the edge-map: hey! We're gathering data at different resolutions!

 

Okay, let's quickly revisit the fact that by scaling and clipping we're losing data, but if we just view this is a visualization of an underlying 256 x 256 array, notice how the "significant" data seems to be moving towards the edges: the upper-left (low-resolution version of the whole) is still recognizable, and in the lower-right (the both-directions edge-map of the edge-map) the data is becoming more chaotic: more "static-y." But in the middle we're creating a large area with large swaths of gray (I'm even stretching the grayscale so that there's at least one 0 and one 255 pixel). In other words, large areas where the real data are tending towards 0. If we fully recurse, what do we have?

The upper-left pixel is now the average grayscale value of the entire picture: the ultimate low-resolution version. The rest of the data can't be parsed by our eyes, but is easily compressed. Now, if you're really building a wavelet compressor, you don't scale and clip (as we did for this), but you clip when detail coefficients go below some epsilon. By experimenting with epsilon (making it dynamic?) you can get some very, very impressive compression results.

 

Some other interesting things to do with wavelets are scale the detail coefficients up and reconstruct the signal: this amplifies low-contrast aspects of the original. Implications of that are left as an exercise to those interested in steganography and forensics.

 

Wavelets can also be used to aide pattern recognition in signals, since minor variations "move" towards the detail coefficients.

 

Oh, and you should try wavelet processing on sound. Equally fascinating stuff.

Download: The Haar Transform.one

Modularity can be open or closed. Closed modularity is like a jigsaw puzzle. There are lots of individual pieces, but they can only be put together one way. Open modularity is like a tangram puzzle. There are only seven pieces, but they can be put together in hundreds of different combinations.

Novell today terminated CEO Jack Messman and CFO Joseph Tibbetts. Messman is replaced immediately by Ronald Hovsepian, Dana Russell is interim CFO.

Novell has long been the hardest-to-parse of the major OS vendors. To say they "owned" the network market in the early 90s is to understate things. Their fumbles have been extraordinary. Lately, I've liked their plan to become a major Linux vendor, but execution is everything, especially in the tricky world of making money by being a corporate supporter of OSS.

Yesterday, Tina and I went for a dive off Honokohau Harbor just north of Kailua Kona on the Big Island of Hawai'i, a 10-minute drive from our house. Tina and I mostly freedive; this was the first time we had tanks on our backs in five months. Two eagle rays cruised the margin at 70', where the coral slope changed to sand. We went out onto the sand flats to watch a flashing school of scads and stalk a plain of garden eels. Coming back, we saw our friends the eagle rays again, this time at a cleaning station, where we could watch them easily.

Then, in unusually shallow water I saw a school of Heller's barracuda coming towards me. The usually shy species swirled around me. Wow! I thought, not realizing that I was missing the main show. Suddenly, further away, I saw a giant trevally thrashing a barracuda like a terrier with a rat. It was big: probably a 50# fish. I hooted in my regulator and pointed so Tina would see it.

When we surfaced, Tina told me that the reason the barracuda had swirled around me was because the trevally was herding them, cutting back and forth at lightning speed, only a few feet away from me. She had seen the whole thing.

Freediving's nice, but we've decided to go back for another dive at that spot this weekend!

The Jolt Awards are the major industry award for software development tools (compilers, libraries, etc.). One problem we face every year is proper classification of tools. Traditionally, we try to refine / fine tune the previous year's categories (Development Environments; Libraries, Frameworks, and Components; etc.). Problems arise frequently balancing the number of products in a category (20 entries in one category, 3 in another), when clearly competitive products end up in different categories (happens all the time with categories "Web Development Tools" versus "Development Environments"), and when a product cuts across categories.

Brainstorming yesterday, we wondered if it would not be better to generate the categories dynamically. One idea was to use checkboxes for predefined activities ("defect tracking," "code generation," "GIS mapping") and use some form of entropy measure to divvy them up into our 12-or-so categories. Easy enough mathematically. Another, more dramatic idea, was to create a tagging system for software tools and see if we could come up with a more dynamic view. The main challenge we see is that it seems like a small world: there are only a few hundred tool releases every year and it's difficult to imagine many people becoming engaged in the task of tagging them.

Do the Web 2.0 dynamics of distributed collaboration apply to small numbers? A del.icio.us for software development tools?

Vista has built-in voice recognition capabilities. One of the things that really jumped out in the Tablet PC was that the correction interface makes all the difference when it comes to using alternative input techniques: a service pack released for the Tablet a year or so after the initial launch was a landmark in the usability of handwriting for text entry. I've just begun using voice recognition in Vista and am very impressed with the correction interface. It may have reached the tipping point for usability (at least with a sound-cancelling headset).

I take it as a given that every stock touted via spam is, in fact, the subject of some sort of pump-and-dump scheme. That is, someone currently owning significant amounts of the stock (or options) is praising it, with the intent of causing upward motion, at which time they will sell their shares. So stock spam should be a reliable leading indicator of a loss of value. Therefore... Oh, you can't sell penny stocks short.

Never mind.

"[Wayne Kelly is] pleased to announce the preliminary Beta release of the Gardens Point Ruby.NET compiler. Note: this is not just a Ruby/.NET bridge, nor a Ruby Interpreter implemented on .NET, but a true .NET compiler. The compiler can be used to statically compile a Ruby source file into a verifiable .NET v2.0 assembly or it can be used to directly execute a Ruby source file (compile, load and execute). Our implementation is not yet fully complete, but it is the only Ruby compiler that we know of for either the .NET or JVM platforms that is able to pass all 871 tests in the samples/test.rb installation test suite of Ruby 1.8.2.

Complete source code of our system can be downloaded from: http://plas.fit.qut.edu.au/Ruby.NET/Download.aspx

Apropos of yesterday's blog entries (XML: Unix Pipe or ASM? and WS-* vs. REST/POX: Revenge of Worse is Better): the always interesting Peter Coffee paints a picture of how WS-* approaches to SOA lead to success. Contrast with Brian Marick's Three Ages of Programming blog entry.

I recently talked to a former client for whom I'd architected a system 4-5 years ago. When I left, they had a technical staff of about 10 and 2 clients using the back-end system we developed. Today, they have the same size technical staff and 900 clients using the system for their back-end. Yeah, baby!

Fluffernutters banned from schools. Mmmm.... Fluffernutter. Between Fluff, Necco Wafers, Hoodsies, and Drake's Cakes, my Boston childhood was apparently in line with the "eat locally" value. I wonder where Spaghettios were invented...

Richard Gabriel's famous essay "The Rise of Worse is Better" (which, incidentally, I still think was originally published by me when I was editing AI Expert) details the "survival characteristics" of two approaches to software design: the "MIT approach" and the "New Jersey approach" (Bell Labs). He proposes these characteristics and values:

	MIT refinement	New Jersey refinement
Simplicity: The design must be simple, both in implementation and interface	It is more important for the interface to be simple than the implementation.	It is more important for the implementation to be simple than the interface. Simplicity is the most important consideration in design.
Correctness: The design must be correct in all observable aspects.	Incorrectness is simply not allowed.	It is slightly better to be simple than correct.
Consistency:	The design must not be inconsistent. A design is allowed to be slightly less simple and less complete to avoid inconsistency. Consistency is as important as correctness.	The design must not be overly inconsistent. Consistency can be sacrificed for simplicity in some cases, but it is better to drop those parts of the design that deal with less common circumstances than to introduce either implementational complexity or inconsistency.
Completeness: The design must cover as many important situations as is practical.	All reasonably expected cases must be covered. Simplicity is not allowed to overly reduce completeness.	All reasonably expected cases should be covered. Completeness can be sacrificed in favor of any other quality. In fact, completeness must sacrificed whenever implementation simplicity is jeopardized. Consistency can be sacrificed to achieve completeness if simplicity is retained; especially worthless is consistency of interface.

Gabriel's greatest leap was to put aside his emotional attachment to the MIT approach and observe that even in the intentionally bad picture presented here, the New Jersey approach (labeled "worse-is-better") has "better survival characteristics" than the MIT approach.

When considering my previous post on whether XML is the assembly language or UNIX pipe of Web 2.0, I realized that this was yet another battleground for these two philosophies, but ironically, the "usual suspects" seem to have reversed positions: it's primarily the large vendors who are promoting the MIT-like WS-* stack and the academics / free-thinkers / entrepreneurs who are promoting the simplicity of REST/POX.

Since, as I made it clear in the previous post, I'm a REST/POX proponent, this is somewhat dismaying. Particularly worth deep consideration is the final part of Gabriel's article, where he discusses how the approaches, once popular, evolve towards reuse and flexibility.

The sharp and capable Clemens Vaster says that "XML is the assembly language of Web 2.0," drawing a complexity/productivity analogy to higher-level programming languages, which everyone but Steve Gibson thinks are worthwhile tools. The upshot: "[we] have arrived at the point where matters have gotten so complicated that a layer of abstraction over pretty much all things XML has become a necessity for everyone who makes their money building customer solutions."

Not everyone agrees: James Speer balks andTomas Restrepo says that that Clemens is conflating XML and WS-*.

I disagree even more vehemently. One of my favorite recent quotes was Ray Ozzie's quip that "RSS is the UNIX pipe of the Web." In addition to being encouragingly the sort of quote (technical, insightful, engaged with current trends) to encourage Microsoft watchers, I heartily agree with the implicit emphasis on flexibility.

One of the defining characteristics of assembly language is that it is inflexible: it's hard to write high-abstraction-level code in ASM (possible, but it's not facilitated by the language). Another characteristic is that it is dominated by implementation idioms. What springs to mind is is XOR AX,AX which a generation of x86 programmers used to set a register to 0 because it was mildly faster than MOV. Because all abstractions leak, all "blackbox" systems are fuzzy and imperfect. No matter how worthwhile the aspirations of the WS-* stack, in practice systems using the stack will gather implementation-specific peculiarities. Perhaps no more than any other framework, but when tools are used to generate significant amounts of code, they inevitably produce low-abstraction code. Look at interface designers and the naive way they align controls: not by using a variable or directly referencing a dominant control, but by generating the same code over and over.

Similarly, if the XML moving between our Web 2.0 services is primarily tool-generated and difficult to comprehend, that will stand in the way of intermediaries adding value, which are an essential part of Web architectures. RSS is successful, not in spite of being "really simple," but in large part due to being so. The same is true of HTML. The same will be true of the next major innovation in Web 2.0.

My "knowing" exercises made the Digg homepage. Now I have to resist the temptation to check the comments every 15 minutes...

Failed...Okay, this time for sure...