SpaceX Falcon First Stage Landing (Part III)

This post is the third of a serie, explaining how at Aero Quartet we managed to recover the only existing pictures of the Falcon rocket “landing” on the Atlantic Ocean, first published on Elon Musk (SpaceX CEO) twitter on April 28.

In the previous posts, we explained why we have to focus our efforts on recovering frames F199 and F215, which are the only two keyframes that are almost error-free.

Brute Force Bit Flipping

In F199 we expect that by changing only one bit somewhere in the frame the picture will improve. The brute force approach consists in trying hundreds of positions until we find the right bit to flip.

F199 is about 20 kb in size, so we have 160,000 bits to test. But we can easily narrow down to a small region by finding where things start to go wrong, decoding-wise.

At first glance, decoding works fine in top 40% of the picture. Since MPEG4 Video is encoded from left to right, top to bottom, just as we read text on a page, and as image is made of blocks of 16×16 pixels, it’s easy to draw the line between good and bad in the picture. The highlighted rectangle below is where things go wrong: Before it all is good, after it all is bad.

So we can focus our bit-flipping effort on this area only. The cause of the problem must be here.
To find the bit positions inside the frame corresponding to this area, we can use several tricks. For example you make copies of the frame and write garbage information at a given position, and then you look at how the image is affected. By making a few iterations you will determine the position corresponding to beginning of area and to end of area. No rocket science involved here.

We have determined with this method a range that contains only 896 bits: from byte 6898 to byte 7010.
Now all we have to do is to try flip those bits one by one…

the Script to Flip Bits

Of course we don’t do this by hand, it would take days. I have written a couple of scripts to have the computer do the heavy lifting.

First of all, we will divide the range to test into 7 smaller ranges of 128 bits each. This is to make things easier for us humans who will have to visually verify the results eventually.
We will work on a video file (download) containing the single frame F199 that we try to repair. The 7 ranges have the following starting addresses (in hexadecimal):

0x4890 0x48a0 0x48b0 0x48c0 0x48d0 0x48e0 0x48f0

For each range, we run this ugly little bash script (everything is done under Mac OS X) that creates 128 copies of the video frame. Each copy differs from the original by exactly one bit that has been flipped.

mkdir f199-4890 # new folder where the 128 copies will be created
cd f199-4890
z="4890"; i=0; 
xxd -p -s 0x$z -l 16 ../f199.mov | ../flipBits.pl | sed "s/^/$z: /" | while read LINE; do
  cp ../f199.mov ./f$z-$i.mov ; echo $LINE | xxd -r - ./f$z-$i.mov ; let "i=i+1"; 
done

First, xxd extracts the 16 bytes at position 0x4890 from the original video f199.mov, and outputs them as an hex string: DF4E2D41FBBFFFB51D8412FF118A2C4F
Then flipBits.pl script (download) takes this hex string as input and creates the 128 variants, that it outputs, one per line:

5F4E2D41FBBFFFB51D8412FF118A2C4F
BF4E2D41FBBFFFB51D8412FF118A2C4F
... and 125 more and finally the last one ...
DF4E2D41FBBFFFB51D8412FF118A2C4E

Finally, we use xxd in reverse mode to apply the 128 variants back to the original video, and we create one file per variant.

You end up with a folder containing 128 video files, that you can review visually one by one until you find the needle in the haystack… Hey, f48e0-73 looks promising!

I’ve made it look easy, but I actually spent a few hours on this back in April, and my eyes were red after reviewing a few thousand pictures, before I stumbled upon f48e0-73.

Clean, Rinse, Repeat

Once you have improved an image, you can try to repeat to process on the same image:

• Figure out the range where decoder stops working
• Generate hundreds of variants of this image by flipping all bits in the range, one by one
• Visually pick the images that show an improvement

On the second frame F215, I have used this technique a well.

Other Techniques to Improve Further

Unfortunately, at Aero Quartet we have very limited resources and we couldn’t work on this repair as many hours as we would have liked.
After delivering the two improved pictures to SpaceX, we actually stopped our effort, but Robert from SpaceX had the excellent idea to crowdsource the effort to the many SpaceX fans on the Internet.

I have followed what they have been doing (and this series of posts is also aimed at helping them), and I’m very impressed by the results.

They have not only used the “bit-flipping” technique that I’ve explained above, but they also have built a customized ffmpeg tool that lets them play with macroblocks inside the image. That allows them to skip some bad macroblocks and have the decoder catch-up later when good macroblocks are found again.

The best results from are visible on this web page: http://spacexlanding.wikispaces.com