I've got a few prototypes of content-aware image resizing running and the results are interesting, perhaps primarily because the algorithm works so well that usually you say "eh, what's the big deal?" Unless there are faces in the photo, but more on that later...

Coincidentally, I ordered some prints to send to my in-laws yesterday and was reminded of the annoyance of crop differences between the standard snapshot aspect ratios. Ah hah, thinks I! I should do one of those "mashup" things the kids are all talking about!

Ideally, you'd have:

• Easy access from your image software ("Oh, darn! Look at those default crop lines! Let me click on 'Crop Perfect'!)
• Integration into the printing process (see above.)
• Preview
• Maintain original file

Hmm.... There's no Picasa plugin API (although there's a Picasa Web Album API) and in my experience, all photo-printing places use an uploading plugin. Hmmm....

Any thoughts on strategy?

I've never played Halo nor Halo 2. I've now played the first level ("Groundfall" or somesuch) of Halo 3. Gotta' tell you: my initial impression is that it's not as entrancing as Gears of War or Call of Duty. The cutscenes make absolutely no sense to a newbie, the level design was nothing special (oh, the trees shake when you move past them. Cute.), the combat tactics weren't clear, and the controls seemed sub-optimal (I read in Wired that you were supposed to always be switching between grenades, guns, and fists. But to use your fists, you have to take your thumb off the "look" control, so it's hard to melee).

People talk about multiplayer, but let me clue you in to something about multiplayer: it's offputting to normal people. Normal people don't enjoy undergoing a series of losses before being buoyed up by the matchmaking system. Perhaps subsequent to the 10th match everything is wonderful as you slot into the ranks of your peers. But I'll tell you what -- I've never played 10 matches online in any game, because my first half-dozen matches have always been unpleasant. In racing games, people intentionally crash through the first corner; in first person shooters, you get picked off ten times in a single match.

Excel 2007: The problem is that the 3rd column contains =a2*b2 ... (the first 500 numbers for 2^32 pass, though...)

etc. etc.

Is there a pattern in there?

Helpful

casey chesnut has been playing around with augmented reality for the UMPC. I think he's going strictly for a technology demo, but the physical tags he's constructed seem to be about the right size for a conference badge. That'd be kind of cool -- hold up your UMPC in a crowd and get a "magic window" collection of homepage URLs?

Intel's announced the availability of a prototype C++ compiler implementing Software Transactional Memory, one of the central topics of this brilliant .NET Rocks show.

That's exciting, although I suspect that on just two cores STM will be disappointing.

I love this idea: a magnifying glass with a built-in expert system for identifying bugs. That's a nice combination of form and function. My thrill was clouded upon reading the that it only identifies "more than 50 real live bugs;" if you're going to do the hardware and firmware for this, it ought to be trivial to burn in the taxonomy for "thousands of real live bugs!" See, for instance, the remarkable 20Q orb.

Once upon a time, I fielded an expert system for identifying seabirds. One of the big problems was that interacting with the display necessarily meant taking your eyes off the seabird and, if you weren't experienced, that often meant considerable time before re-acquiring. But if you were an experienced birder, you didn't need the expert system. Plus display and battery life on the available portable computers of the time were problematic.

When the Palm came out, I investigated developing expert systems for them: the target niches were going to be birds, plants, and mushrooms. Too little market confidence and too few resources kept that one at the prototype stage.

Sadly, that "more than 50" line and the lack of "I don't know" button makes me wager that instead of having a real expert system, with inferencing and reasoning under uncertainty, the software is just a simple tree. Which, if I'm right, is pathetic -- all of that work to develop a device and then to cripple it, for lack of a couple of hundred lines of code.

I'm not one of those people for whom the task of composition is a somewhat mechanical extension of increasingly detailed outlines. Nonetheless, research consumes between 80-90% of the time I spend on a technical article (note I said time and not effort -- subjectively, writing text is two or three times harder than writing C++. You can satisfy a compiler.)

In this case, research will consist of:

1. Integrating CodeAnalyst and Eclipse
2. Profiling a simple application
3. Implementing an image-processing application
4. Profiling it to discover a performance problem
5. Investigating that problem with CodeAnalyst
6. Ameliorating it
7. Evaluating the performance "win"
8. If not "big enough" go to 3 

In this case, my target sample application has two algorithms that I think will be difficult:

1. Seam-discovery (CPU intensive)
2. Seam-removal (Memory-manipulation intensive)

With seam-discovery, I know that even if I implement a known-good algorithm (such as graph-cuts), I am guaranteed to peg the CPUs. My big gamble professionally is that I'm a good enough programmer to find a Step 6 "win" that I can pull off in a reasonable amount of time. A safer bet would be to choose an algorithm that would have performance problems if intentionally implemented in a naive manner (for instance, a filter that just iterated across rows and columns and, at each pixel, retrieved the neighboring pixels and averaged them. Pretty easy to tune that up!)

Now, a confession. By the time you read this, I've been somewhere not-Hawai'i for a week or so. I'll carry print outs of this paper on content-aware image resizing and this paper on graph-cuts and study them on the plane tomorrow. I'll have my laptop with me and may noodle around with source code, but it's far more likely that I'll be working with pen and paper to see if I can "get" the algorithm intuitively. Other than that, I'm going to do my darnedest not to spend too much time thinking about computers.

Coming September 19th or thereabouts: Part 4, Research Gets Underway...

Some d00d named Leppie has written a Lisp for the DLR [via Jason Bock]

Alan Zeichick deserves a fortune in Amazon referral fees for this: iPod connector to RCA plugs. 

Probably the biggest difference between academic and commercial writing is this: academic writing is almost always concerned with algorithms and process, commercial writing is almost always driven by a specific set of technologies. In this case, I'm being paid by AMD to explain integration of CodeAnalyst and Eclipse CDT. So that dictates that I'll be using C++, which leads to a couple questions:

• Linux or Windows?
• What C++?

The Linux or Windows question is fairly easy for me to answer: I boot into Windows and run Linux in Virtual Machines. For an article on a profiler, the VM is a complication -- CodeAnalyst works within a VM, of course, but since I expect this article to get down to the hardware, I don't want any confusion about how toasty-warm my code is making my Opterons. So I'll be experiencing the code in Windows.

But when writing about Eclipse, surely I should imagine that my target audience is not strictly Windows-based. So it seems logical to set up a compiler-chain based on GNU C++: I know that will be portable. (Note: I'll probably cross-compile with at least Microsoft C++ and compare the experience. That might give me enough information for, if not an article, at least a column.)

Since the article is supposed to emphasize multicore/multichip development and in C++, it's a no-brainer that I'll be using OpenMP.

My next thought is unit-testing. For one thing, I just don't develop anything without unit-testing anymore. For another, repeatability is critical to the article. For a third, I expect to hit some hard problems along the way and unit-testing is the best way to maintain momentum in the face of brain-twisters. I have not compared C++ unit-testing frameworks, but Boost has a test component, and while there may well be better, I know that Boost won't be poor.

Version control is not the same issue in an article that it is in professional development, but you can never over-estimate the benefit of a backup: I'll be using Subversion against a local server.

Since I know that I'll be doing image-processing, I'd just as well use a library or two to handle file-loading and basic pixel manipulation. If I were building an application, I'd definitely tend towards GTK+. However, I want to keep things as simple as possible around the algorithm(s) that I'll be developing, so I'm going to see how far I can get with this project, CImg, which seems nice and minimal.

So my initial tool list is:

• CodeAnalyst : Profiler
• Eclipse CDT : IDE
• GCC : Compiler-chain
• OpenMP : Shared-memory parallel programming
• Boost.Test : Unit-testing
• Subversion : VCS
• CImg : Image-processing library

If I need or change libraries, I'll make mention of it in forthcoming posts.

Next: Part 3, Research Begins...

I'm on .NET Rocks this week talking about concurrency -- a sure sign that Carl and Richard have run out of interesting people to talk to. Nonetheless, I try to not make too many mistakes when explaining Shared Memory Parallel, Software Transactional Memory, Message Passing, etc.

If you are interested in concurrent programming, you'll eventually come across the Byzantine Generals problem. Mark Nelson has a good post explaining it.

I thought I'd try blogging the development of a technical article; it might prove interesting to, I dunno', 3 people in the world.

I've been contracted to write a 2,500-words-plus-listings article on using AMD's CodeAnalyst profiler with Eclipse, especially relating to multithreaded / multicore development. So that's a pretty beefy article, about twice the length of a typical technical article in a print magazine. CodeAnalyst works with native code, so my sample program(s) pretty much have to be written in C++ -- anything else would limit the audience.

AMD targets an experienced audience, so the educational goals for the article are "The reader will be able to..."

• ... enable and gather data using CodeAnalyst from within Eclipse CDT
• ... navigate within the main profiles provided
• ... recognize the profile most clearly associated with their performance limits
• ... determine the source-code lines associated with a performance issue
• ... after making code changes, compare the performance of subsequent runs"

Which is a heck of a lot of ground to cover. So the end result will be something like an advanced tutorial that you might get towards the end of a piece of documentation.

My professional goals are to deliver a technically sound article that satisfies my client's goals within a profitable range of hours. I can control that primarily by manipulating my sample program(s); the amount of time I need to research the actual use of Eclipse or CodeAnalyst is minimal, since I know both products. The research aspect of the article -- always the most time-consuming in a technical article -- will be the development of sample program(s) that:

• have a performance-limit that can be ameliorated,
• are comprehensible, and
• can be distributed (this limits my use of libraries)

My personal goals are to make sample programs that are interesting in and of themselves. This is a weakness on my part, but what can you do? In this particular case, I hope to implement some significant part of the algorithms used for content-aware image resizing. I have no intention, or interest, in recreating the GUI shown in the video. I have neither the time nor, quite honestly, the mindset -- once I see the algorithm work, I can guarantee you that my interest in this will virtually disappear. That's one reason why I'm not rich.

Next up: Part 2, Gathering Tools

Following the lead of the SFWA, which issued a takedown to a fan site based on nothing but the existence of the strings "Asimov" or "Silverberg" in a text file, I've demanded that NBA.com remove all pages that refer to "Larry O'Brien." Those bastards have been distributing my source code long enough.

The key to content-aware image resizing (and other recent image algorithms) is the discovery of "seams" -- paths of pixels that don't differ much from each other. Such seams are   places where the picture can be "pulled apart" gracefully. In image resizing, the seam is discarded and the two remaining pieces glued together -- when done time and time again, the result is the astonishing resizing behavior.

In the image in this post, a blown-up anti-aliased letter "R", an obvious seam exists straight down the left side. A not-quite-as-good seam might be along the right side, but cutting diagonally back across the tail of the "R."

Other people have used seams to automate collaging and masking. All very interesting, but the point of this post is to talk very briefly about the algorithms used to generate the seams.

Optimal seam generation is NP-hard. So it boils down to what works efficiently. Graph-cuts are the preferred method, but I just can't get out of my head that the simple path-finding method called A* might be effective.

The thing that is nagging at me is that A* uses a cost approximation to figure out the next step forward; it seems to me that when manipulating many seams, using approximations that might last for dozens of seams would have a big benefit. The other obvious thing about A* is that the approximations are easy to build: recursively develop lower-and-lower resolution images.

For instance, when the above image is converted into brightness values, you can average neighbors to create the values shown in yellow, and average those to create the values in red. (Did you think "Haar wavelet"?)

Initially, this looks promising (the left-most yellow column is a clear winner), but at coarse levels, it's deceptive (For the red, lowest-resolution "image," you would clearly be drawn towards the right side for initial processing.

Intuitively, you would think that most images would have several side-by-side seams (i.e., that would show up at  coarser levels). Also, after seam removal, you would be able to "mark dirty" the approximations (i.e., the coarser calculations) and trigger recalculation as the amount of removed seams became significant (and, obviously, not recalculate areas through which the seam did not pass).

This is kind of killing me, because I don't have time to explore an algorithm that I only suspect will be efficient.

Grrr....