jackadamblog

How Dark Sky Works

2011-11-07T00:00:00-08:00

Dark Sky is a weather prediction and visualization app for the iPhone, iPad and iPod touch. For an overview, and to learn how you can help us, check out our Kickstarter page.

A lot of people have been wondering how Dark Sky works. In this post I’ll try to shed some light on what goes on under the hood.

Getting the data

All our radar data comes from the National Oceanic and Atmospheric Administration. NOAA operates a network of over 140 radar stations spread across the United States and its territories, and one of the advantages of being a US citizen is that you get access to this data for free. They’re mandated by law to make their information public, but they go above and beyond by providing real-time access via the web and FTP.

We download the raw radar data in binary format. But if you’re looking to get started playing around with weather radar, a better place to start is perhaps RIDGE, which boils the raw data into color-coded images that are easier to work with.

Cleaning it up

Weather radar is noisy. There’s lots of ground clutter, bug and bird migrations (!), and other artifacts that can be confused for precipitation. Here’s an example:

So we’ll need to clean this up. How do we do it? Well, the noise mostly consists of low-intensity data -- the light blue areas. One technique (which this gentleman writes more about), is to simply remove all low-intensity data. It clears away the noise, and leaves most of the actual precipitation data.

However, for our purposes, “most” isn’t good enough. By removing low-intensity data indiscriminately, we’re removing valuable data from the leading and trailing edges of the storms. This data is crucially important if we’re going to predict when it will start and stop raining. So we’ll have to be a little more clever.

After staring at enough radar images, it becomes pretty clear which signals are real precipitation data, and which are noise. Not only does noise tend to be low-intensity, but it has a recognizable “texture” which is distinct from actual storms. It’s easy to see with the eyes, but hard to explicitly quantify or define. So how do we write a program to remove it? This type of I-know-it-when-I-see-it, but ill-defined situation is ripe for some machine learnin’.

In this case, we opted for neural nets. Using the Fast Artificial Neural Network C-library, we trained a neural net with thousands of “blobs” of data hand-separated into two categories: noise, and not-noise.

The training process takes a while to run but the end result is a small, blazing fast program that accurately identifies somewhere between 90% and 95% of the noise, with very few false positives.

(To take care of the remainder, we spent an embarrassingly large amount of time and effort writing heuristic clean-up code by a tedious process of trial and error. But we’re keeping that part secret ;-)

The end result looks something like this:

Extracting storm velocity

Now that we have the radar data and we’ve cleaned it up, we come to the real meat of the app: velocity extraction.

But first, let me talk a little about the philosophy of our approach...

Weather is chaotic. It’s the quintessential non-linear dynamical system. Complicated fluid dynamics combined with a spinning globe, uneven terrain, and energy pumped into the system from the sun makes the weather extremely hard to predict with any accuracy. Meteorologists have spent a century coming up with increasingly sophisticated models and they still can’t reliably talk about the weather -- even generally -- much more than a week in advance.

So how can we justify our claim of being able to predict precipitation down to the very minute?

Well, here’s the thing: while the weather becomes chaotic and unpredictable at large timescales (hours to days), its behavior becomes increasingly linear at smaller and smaller timescales. To see this in action, take a look at cumulus clouds drifting across the sky. They tend to move in relatively straight lines:

We’ve found that precipitation bands are even more coherent and behave approximately linearly over the course of minutes, and in many cases up to an hour or more. So how do we go about quantifying this linear motion? Math, that’s how!

We use various computer vision algorithms to compare multiple radar image frames and create a map of velocity. Specifically, we use OpenCV, an open-source computer vision library, which comes with a number of optical flow and object tracking algorithms (for a great introduction to the topic and to see some sample code, check out this tutorial by David Stavens at the Stanford AI Labs).

The end result looks something like this:

Actually, we don’t draw little arrows. Instead, we encode the velocity in a more useful form: colors. We create a 3-channel image where the red channel represents velocity in the x-direction, the blue channel represents velocity in the y-direction, and the green channel represents change in storm intensity:

(If you’re so inclined, open the image in Photoshop and check out the color channels individually)

Prediction and Interpolation

So, now that we’ve extracted storm velocity, it’s time to use it to predict the future!

The reason we encode velocity data as an image is so we can pass it off to the GPU on the iPhone and iPad. Both the storm prediction and the smooth animations are calculated on the device itself, rather than the server, and all the magic happens directly on the GPU.

I’m going to be a little vague here, since this part constitutes our “secret sauce”, and is the component of our system that is in most active development. So instead, here’s a pretty video of the app in action:

Monitoring error

A prediction is worthless unless it is not only accurate, but reliably accurate. A large amount of our effort is focused on measuring the error rate of Dark Sky predictions. Some storms are more coherent and stable than others, so how far into the future we can project varies over time and at different geographical locations.

Whenever we process a new radar image, we go back to previous images and project them forward, creating a map of what we think the storm will look like in the present. We then compare this with the latest radar image to see how close we got.

We are constantly doing this check in real time, for every radar station. This lets us monitor our accuracy, and helps us quantify how effective future improvements are.

In conclusion...

So Dark Sky consists of a number of different moving parts that all need to fit together to create accurate predictions and pretty animations. This post glosses over many of the details, but I hope it helps get across the essential process and our approach to short-term weather forecasting.

It’s very much a numerical & statistical approach, rather than a meteorological one. Since we’ve launched the Kickstarter project, we’ve had several people (many of them meteorologists) criticize it because it eschews physical modeling of atmospheric fluid dynamics. And it’s true that our system will never be able to predict six hours in the future, let alone a day from now. But by focusing on the immediate future, and leaving everything beyond to the meteorologists, we can create a highly accurate app that is useful in a surprisingly wide range of applications.

So if you are excited by this as much as we are, please help us out by backing our Kickstarter project. Every dollar counts!

http://www.kickstarter.com/projects/jackadam/dark-sky-hyperlocal-weather-prediction-and-visuali

How Small Can You Make Your Stupid Face?

2011-09-10T00:00:00-07:00

Using High-Falutin’ Computer Vision Algorithms for Quantitative Face Reduction Analysis

When we saw this clip from the first episode of Workaholics on Comedy Central, it made us mad:

Here you have an individual who is asked to judge which of his friends can make the smaller face, but instead of taking this task seriously he hastily declares a winner based on scant evidence and with no discernible justification!

What does it say about the human race as a tool-building species that we still — after centuries of technological progress — have no means of objectively quantifying a person’s face reduction aptitude?

Videos such as this simply perpetuate (dare we say, celebrate?) a lack of scientific rigor.

This will not stand. Jack and I knew we had to do something. So we built Tiny Face, the world’s first mobile app for scientifically determining one’s face reduction percentage.

How it works is simple: The user is prompted to make their normal face followed by their tiny face, and the app then computes how much smaller the latter is compared to the former. It’s not about absolute face size, but rather how much smaller you can compress your face relative to your baseline "normal" face. Here’s an example output:

How does it work?

Face Detection

Face detection algorithms have been around for a while. We use OpenCV, an open-source library of computer vision algorithms (written in C, and easily compiled for the iPhone), to detect faces in the input image.

It’s pretty easy to use, since other people have done the hard work of training these magical algorithmic gizmos called Haar Classifiers using collections of thousands of sample faces. We simply took this classifier and fed it into OpenCV along with the input image, and out comes a bounding box around any faces! Like magic!

By doing this for both the normal face and the scrunched face, we get two bounding boxes whose areas we can compare to figure out how much smaller the face has become:

Not So Fast!

This method only works in tightly controlled situations where the user and camera are stationary, and the only thing that changes is the face. But if we were to turn this into an iPhone app, we’d have to deal with the real-world where we can’t expect people to hold themselves and the phone still.

The problem with simply comparing the bounding boxes of the normal and tiny faces is that moving the camera closer or father away results in unacceptable errors due to perspective scaling. For example:

We could just ask users to keep their camera and face steady. But, as any software developer can tell you, most users are terrible awful cheating sons-of-bitches (haha! We love our users!).

So how do we correct for this?

Feature Tracking

If we knew the distance from the camera to the face in both images, we could compensate for perspective. Unfortunately, there’s no way to get the absolute distance from each image alone (until the iPhone comes equipped with 3D camera or laser range-finder).

But we can compare the two images, and employ a nifty trick:

Take a look at the photos above. In the before and after images she’s changed the size of her face, but other aspects of her head / body are unaltered. These include her hairline, the shape of her head, shoulders, clothing, freckles, jewelry, etc.

If we can identify these features in both images, we can compare how their sizes and positions differ and compute the relative change in scale between them.

Fortunately, OpenCV comes with neat ways to identify and track features from one image to the next. Using the position of the face, we can draw a box around the likely location of the entire head and body, and then run these algorithms to find features in common:

By then comparing the distance between these points in both images, we can calculate by how much the camera has moved closer or farther away, and compensate accordingly. Presto!

Actually, while this works in theory, it doesn’t always work in practice. In our tests we found that users move around quite a bit between images, leading to inconsistent lighting, blurring, and all sorts of similar nastiness.

In fact, we weren’t able to find a single feature tracking algorithm that could handle all these situations. So we resorted to using multiple ones, including the Lucas-Kanade method and SIFT - Scale Invariant Feature Transform.

We run them all (after passing the images through various cleaning stages), and then "sanity check" the resulting numbers to determine which results are likely to be most accurate.

So there you go. After countless hours of tweaking numbers and nearly spraining our faces generating hundreds of test images, we’d got ourselves our very first iOS app!

You can check out user-submitted faces at Tiny Face website and buy the app — only 99¢! — from the App Store for the iPhone 4, iPod touch and iPad 2.

WARNING FROM YOUR MOM: Prolonged use of this app can cause your face to freeze like that, young lady.

The Tiny Humanity Bubble

2011-02-04T00:00:00-08:00

Mankind has been broadcasting radio waves into deep space for about a hundred years now — since the days of Marconi.

That, of course, means there is an ever-expanding bubble announcing Humanity’s presence to anyone listening in the Milky Way. This bubble is astronomically large (literally), and currently spans approximately 200 light years across.

But how big is this, really, compared to the size of the Galaxy in which we live (which is, itself, just one of countless billions of galaxies in the observable universe)?

To answer that question, I put together the following diagram of our galaxy with the "Humanity Bubble" embedded within it. You’ll need to click on it to get the full resolution image and zoom in on the highlighted region.

This makes me feel small, sad, and alone.

Hold me.

Update:

In response to my depression over the smallness of our presence, johnohara on the Hacker News thread says:

[That is] One man’s opinion.
For me, I am grateful I live in a time when I can use a human invention to view images, taken by another human invention, of galaxies 13.5 billion light years away that probably no longer exist and be educated enough to sit down and calculate in terms of miles just how far those specks of light have traveled. Aristotle, Caesar, DaVinci, Newton, Kepler, Napoleon, Faraday and Einstein never saw what I have seen from my desktop. Sad? No. Privileged.

thasc, in the comments below, concurs:

For a tiny, young little species, that’s one heck of a lot of ground covered! We actually register as visible on a relatively low-res image of the Galaxy! Go us!

Indeed.

(p.s. Since we’re inside the Milky Way, obviously we cannot take photographs of it. This is an artistic rendering of what it might look like, which I stole from Wikipedia. The artist is Nick Risinger.)

3D Rotating Molecules on the iPhone/iPad

2010-10-29T00:00:00-07:00

Turns out, canvas kinda sucks for developing full-screen animations on the iPhone and iPad. Without hardware acceleration and a more efficient clearing mechanism, it just doesn’t cut the mustard.

But all hope is not lost... CSS 3D transforms to the rescue!

Check out this 3D molecule simulation we put together:

You can rotate the molecule around with your fingers, and pinch to zoom in and out. At blisteringly high frame rates. Try it out yourself.

(It currently works on iOS devices, Safari, and the latest dev version of Chrome... basically, any browser that supports true CSS 3D transformations / animations.)

So how does it work?

Take a gander at this simplified example, consisting of four rotating circles:

We apply the following CSS animation to the container holding the circles...

#container {
    [...]
    -webkit-transform-style: preserve-3d;
    -webkit-animation-name: spin;
    -webkit-animation-duration: 4s;
    -webkit-animation-iteration-count: infinite;
    -webkit-animation-timing-function: linear;
    }
    
@-webkit-keyframes spin {
    0%    { -webkit-transform: rotateY(0deg); }
    100%  { -webkit-transform: rotateY(360deg); }
    }

Which tells the container to spin around the y-axis perpetually. Notice, however, that the circles don’t look like three-dimensional spheres... instead, they appear as flat circles painting onto the plane of the container. In order to simulate the atoms of a molecule, we need honest-to-goodness 3D balls.

To accomplish this in CSS, we take advantage of a technique called "billboarding". Billboarding involves rotating an object (in our case, each of the colored balls), in such as way that it remains facing directly at the camera at all times. This is a fairly common technique in the world of 3D gaming, used to render things such as trees and grass — and in our case, it gives the illusion that the circles are really spheres.

Now, there isn’t any built-in method for billboarding an object using CSS 3D transforms, but its easy to fake: We simply need to rotate each circle individually in the opposite direction from the rotation of the parent container. We do this by defining an equal-but-opposite CSS animation, and apply it to the balls:

.ball {
    [...]
    -webkit-transform-style: preserve-3d;
    -webkit-animation-name: reverse-spin;
    -webkit-animation-duration: 4s;
    -webkit-animation-iteration-count: infinite;
    -webkit-animation-timing-function: linear;
    }
    
@-webkit-keyframes reverse-spin {
    0%    { -webkit-transform: rotateY(360deg); }
    100%  { -webkit-transform: rotateY(0deg); }
    }

Notice that the reverse-spin animation starts at 360 degrees and ends at 0 degrees, whereas the original spin animation was the opposite. Ta da! The results can be seen here:

Things become a little more complicated when it comes to arbitrary rotations about multiple axes in response to touch gestures (as seen in the molecule demo), but you get the idea! Pretty neat, huh?

The Unfortunate State of Canvas Animations on the iPhone / iPad

2010-10-28T00:00:00-07:00

Over the next several months, Jack and I will be building a series of fun little interactive online games for a client. In years past, these type of (animation-heavy) games would have undoubtedly been built in Flash. Our client, however, is forward-thinking enough to let us try ditching Flash and implementing them all with HTML / CSS / JS (a.k.a. “HTML5”).

Part of the rationale of moving away from Flash is that we want (at least some of) these games to be playable on the iPad and iPhone. The target demographic is younger school-age kids, and the iPad is poised to take off in that space.

Now, when it comes to building rich, graphical, animated games in HTML5, the obvious first step is to investigate Canvas. We’ve done so, and we’ve come to a couple conclusions:

Canvas is entirely unsuited to generating full-screen animations on any iOS device. The frame-rates are unacceptably low.
Clearing the canvas between frames is surprisingly expensive.

Here’s the test I used, so you can try it out yourself:
http://demos.jackadam.net/canvas_test

It’s pretty much the simplest animation you can perform with canvas... drawing a single circle moving across the screen.

If you don’t have an iPhone / iPad, here’s a video of the test in action:

As you can see, frame-rates on the iPad vary from "unacceptably bad" at fullscreen to "okay, I guess" at the relatively tiny resolution of 250x250.

And notice how much snappier the animation becomes when we stop clearing the canvas between frames! Canvas was originally designed to generate static images, not animations, and the standard canvas clearing method (calling ctx.clearRect(0, 0, width, height)) appears to be quite expensive.

I did experiment with alternative clearing methods, including:

Creating an empty canvas on page load, grabbing its contents with getImageData and sending it to the canvas on the page with putImageData.
Replacing the canvas element with a new one each frame.
Forcing a refresh of the canvas element by resetting it’s width every frame (Using canvas.width = canvas.width+0)

All of which you can experiment with in the above demo. None of these, however, improved clearing performance significantly.

As a result of these tests, we’ve decided to ditch canvas as a viable option for fullscreen games on iOS.

(And straight-up DOM manipulation via Javascript doesn’t fare much better when you’re doing anything more complicated than moving a handful of elements around.)

That only leaves one option for us: CSS transitions.

Stay tuned...

JPEGs with Alpha Channels?!?

2010-10-04T00:00:00-07:00

I wanted a reasonably sized photographic image with a 24-bit alpha channel. So I used a JPEG for what JPEGs are good for and a PNG for what PNGs are good for...

I combined them using an HTML5 canvas element and then inserted into the DOM. The results look the same as using a normal 24-bit PNG but are one-half to one-sixth the size. In one case we got a 573KB 24-bit PNG down to a 49KB JPEG with a 4KB PNG alpha-mask!

On a recent project I did this using jQuery and scanning the CSS for background-images, but this could easily be achieved without any special CSS using valid HTML5 syntax by referring to a normal JPEG throug the src of an img element and adding a new data-alpha-src attribute with the URL of a 24-bit PNG that is just a mask.

<img src="image.jpg" data-alpha-src="alpha.png" />

This little demo¹ works in the newest versions of Firefox, Chrome, and Safari (including Safari for iOS). For Internet Explorer support, I used the wonderful FlashCanvas². It’s fine in IE8 but it’s inconsistent in IE7. This might be solved by waiting for DOM to be ready. At the time of this writing the IE9 beta does not support globalCompositeOperation, so we’ll have to wait and see.

Recently we’ve taken on two different projects that involve lots of large sprites being animated around landscapes. Normally sites like this (we typically see them done in Flash) necessitate painful loading screens. By using this JPEG-alpha trick we should be able to keep load times to a minimum.

Here is the JavaScript code from the demo:

;(function() {

  var create_alpha_jpeg = function(img) {

    var alpha_path = img.getAttribute('data-alpha-src')
    if(!alpha_path) return

    // Hide the original un-alpha'd
    img.style.visiblity = 'hidden'

    // Preload the un-alpha'd image
    var image = document.createElement('img')
    image.src = img.src
    image.onload = function () {

      // Then preload alpha mask
      var alpha = document.createElement('img')
      alpha.src = alpha_path
      alpha.onload = function () {

        var canvas = document.createElement('canvas')
        canvas.width = image.width
        canvas.height = image.height
        img.parentNode.replaceChild(canvas, img)

        // For IE7/8
        if(typeof FlashCanvas != 'undefined') FlashCanvas.initElement(canvas)

        // Canvas compositing code
        var context = canvas.getContext('2d')
        context.clearRect(0, 0, image.width, image.height)
        context.drawImage(image, 0, 0, image.width, image.height)
        context.globalCompositeOperation = 'xor'
        context.drawImage(alpha, 0, 0, image.width, image.height)

      }
    }
  }

  // Apply this technique to every image on the page once DOM is ready
  // (I just placed it at the bottom of the page for brevity)
  var imgs = document.getElementsByTagName('img')
  for(var i = 0; i &lt; imgs.length; i++)
    create_alpha_jpeg(imgs[i])

})();

In the head element I linked to FlashCanvas:

<!--[if lte IE 8]><script src="flashcanvas.js"></script><![endif]-->

... and I threw in this to avoid a flicker of the un-alpha’d JPEG:

<style>img[data-alpha-src]{visibility: hidden;}</style>

Plastics trucker hats are available from Americorp. [↩]
This technique uses the globalCompositeOperation operation, which requires FlashCanvas Pro. Free for non-profit use or just $31 for a commercial license. [↩]