Fun mosaic effect with Go

A few months ago I saw a cool mosaic effect in a Wired ad for CA Technologies. Here’s what part of the ad looked like:

Photomosaic of people in an office

I liked the ad, so I wondered how they did it. Can you see out how to create a similar effect? Take a minute to figure it out as an exercise.

Here’s what I came up with: divide the image into tiles. For each tile, compute an average overall color for that tile. Then go back and blend every pixel in that tile with the average color. So if a tile is partly dark and partly blue, the average color is a dark blue, so the blue in that tile becomes even darker. I like that the effect is pretty simple once you figure out how to do it.

Of course, once I had an idea of how to do it, I wanted to write some code and see whether I could recreate the effect. Go has good libraries for handling images and I’ve been meaning to try Go. I ended up with about 70 lines of moderately-ghastly Go code that did the job.

For this Creative Commons image (thanks Fuelrefuel/Wikimedia Commons!)

Photo of people in an office

I ended up with a photomosaic like this:

Photomosaic of people in an office

As far as I can tell, that’s pretty much the same filter that ran in the ad. Here’s another example. First, a picture of me:

Matt Cutts

and here’s the resulting mosaic’ed image:

Matt Cutts in mosaic form

That’s all the interesting stuff. You can stop reading now.

This part is boring. Really. No need to keep reading. The code I came up with is really ugly, but the pseudo-code is pretty simple:


- Read the picture into a go image
- Number of horizontal tiles = image_width / desired_tile_width
- Number of vertical tiles = image_height / desired_tile_height
- Loop through tiles with nested vertical and horizontal for loops
- For each tile, loop over the tile's pixels to compute average RGB values
- Loop over the tile's pixels again & set new_color = (avg_color+curr_color)/2
- Write the image out as a new picture

That’s it! I wanted a quick and dirty test, so I didn’t worry about things like the leftover pixels if the tiles didn’t evenly divide the image.

Let’s see, what else. Things I liked about Go:
– It’s super-easy to read and write images, so I could concentrate on the fun stuff.
– I like that documentation like this gives a clear, easy way to set up your environment. The golang tour is great too. And installing Go on Ubuntu is easy: “sudo apt-get install golang” and you’re done.
– The language makes a lot of sense to me, in a C kind of way.

Some things didn’t make as much sense to me, or at least I need to do more reading:
– My initial program just read a JPEG and wrote it back out, and the output image was considerably dimmer. I was just using default encoding values, so maybe some gamma values got left out, but it was a little weird. I was expecting read->decode->encode->write to be a no-op.
– When I read the JPEG into an image and tried to write directly to that image, Go gave me an error. That was a little strange. I ended up copying the JPEG to a new image and then I could write.
– In the spirit of just doing stuff without reading the documentation, it seemed like Go images stored their At() component colors with 16 bits of range (from 0..65536). But when I wanted to write colors with Set() it seemed like Go wanted 8 bits in the example I found. So for a while I was casting stuff with (uint8) and getting totally random bits written into the image. That also generated a fun image:

Random mosaic from converting a 16 bit-range color to uint8

but it took me a few minutes to figure out what was going on. I’m sure some reading would clear things up, but.. who cares? I was also doing some weird float arithmetic to compute color averages. This was just quick/dirty code, and I can read more about the nitty gritty later. As soon as I got the effect I wanted, I rapidly lost interest. I even hard-coded image filenames because I couldn’t be bothered to search for go command-line flag info. All in good fun.
– Arrays and slices are cool, but allocating 2D arrays and slices seems a little verbose.
– I like that Go’s designers have opinions and enforce them, at least 99% of the time. When you’re hacking ugly code, it was annoying to get the “you didn’t use this variable” errors. But I understand the rationale and it’s probably a good idea for writing Real Code that’s not intended to be thrown away.
– I was all set to grouse about go fmt’s enforced indentations/spacing, but it actually looks pretty reasonable. Basically, each indent is a tab. Then if you’re a 3 or 4 space indent kind of guy, you can configure your editor like vim or emacs to change how the tab width is displayed.

Historically, Python is my language of choice to knock out a quick script thing–I love Python dictionaries. But with Go’s speed, support for dictionaries/maps, and capability to do HTTP servers very easily, I might end up switching to Go. I think I’ll use Go for my next little fun project.

Added: Thanks to Tom Madams who whipped a prototype of this filter in video using Shadertoy!

Thanksgiving turkey hat

Because not every blog post has to be serious:

Me wearing a Thanksgiving turkey hat!

Special thanks to my friend Amy who crocheted this masterpiece! Amy also works with an awesome group of volunteers that crochets dolls for kids fighting cancer and other illnesses.

Playing with a USB Missile Launcher

This is the last half-finished “hairball” blog post about USB devices on Linux. I actually did manage to get a working program that controlled a USB foam missile launcher. Unfortunately, I didn’t document all the steps, so this blog post just sort of stops at some point.

I got a USB Missile Launcher for Christmas. The manufacturer, Dream Cheeky, provides software–but only for Windows XP. And I thought to myself, “wouldn’t it be fun to practice some USB reverse engineering skills?” Because another Christmas present was a USB protocol analyzer from Total Phase. I should note that plenty of other people have apparently already written drivers/software for USB missile launcher toys, but I wanted to poke around myself.

Total Phase makes a high-speed USB 2.0 protocol analyzer for $1200, or a regular-speed USB protocol analyzer for $400. Here’s a trick someone mentioned: if you get the cheaper protocol analyzer and need to work with a high-speed USB device, you may be able to plug the high-speed device into a low-speed USB hub to slow the device down.

I decided to start with ladyada’s excellent guide to hacking a Kinect by reverse engineering USB packets. So here’s what I did.

Step 1. Make sure the device works. It would suck to attempt to reverse engineer a broken device. I keep a Windows XP computer lying around, so I downloaded the software for it, installed the program, and plugged in the USB rocket launcher. After the install, XP wanted to restart, so I restarted the XP computer (unplugging my USB rocket launcher after the computer was off), then started the rocket launcher software back up, then plugged in the USB device. Sure enough, everything worked fine. The controls are: pan left/right, tilt up/down, and fire. Tip: the rocket launcher uses bursts of air, so don’t jam the foam rockets down hard on the launcher.

Step 2. Probe the device. I plugged the USB rocket launcher into a Linux machine running Ubuntu 10.04 (Lucid Lynx). I ran the command sudo lsusb -vv and the relevant info from the list of USB devices on my system was this:

Bus 002 Device 045: ID 0a81:0701 Chesen Electronics Corp. USB Missile Launcher
Device Descriptor:
  bLength                18
  bDescriptorType         1
  bcdUSB               1.10
  bDeviceClass            0 (Defined at Interface level)
  bDeviceSubClass         0 
  bDeviceProtocol         0 
  bMaxPacketSize0         8
  idVendor           0x0a81 Chesen Electronics Corp.
  idProduct          0x0701 USB Missile Launcher
  bcdDevice            0.01
  iManufacturer           1 Dream Link
  iProduct                2 USB Missile Launcher v1.0
  iSerial                 0 
  bNumConfigurations      1
  Configuration Descriptor:
    bLength                 9
    bDescriptorType         2
    wTotalLength           34
    bNumInterfaces          1
    bConfigurationValue     1
    iConfiguration          0 
    bmAttributes         0xa0
      (Bus Powered)
      Remote Wakeup
    MaxPower              100mA
    Interface Descriptor:
      bLength                 9
      bDescriptorType         4
      bInterfaceNumber        0
      bAlternateSetting       0
      bNumEndpoints           1
      bInterfaceClass         3 Human Interface Device
      bInterfaceSubClass      0 No Subclass
      bInterfaceProtocol      0 None
      iInterface              0 
        HID Device Descriptor:
          bLength                 9
          bDescriptorType        33
          bcdHID               1.00
          bCountryCode            0 Not supported
          bNumDescriptors         1
          bDescriptorType        34 Report
          wDescriptorLength      52
         Report Descriptors: 
           ** UNAVAILABLE **
      Endpoint Descriptor:
        bLength                 7
        bDescriptorType         5
        bEndpointAddress     0x81  EP 1 IN
        bmAttributes            3
          Transfer Type            Interrupt
          Synch Type               None
          Usage Type               Data
        wMaxPacketSize     0x0001  1x 1 bytes
        bInterval              20
Device Status:     0x0000
  (Bus Powered)

Note that my Vendor ID = 0x0a81 and my Product ID = 0x0701. Also note that bNumEndpoints = 1. An endpoint is a channel for USB data communication. Then we get the Endpoint info:

      Endpoint Descriptor:
        bLength                 7
        bDescriptorType         5
        bEndpointAddress     0x81  EP 1 IN
        bmAttributes            3
          Transfer Type            Interrupt
          Synch Type               None
          Usage Type               Data
        wMaxPacketSize     0x0001  1x 1 bytes
        bInterval              20

According to ladyada’s write-up, the “IN” means that data goes IN to the computer from the device, and the “Interrupt” transfer type is good for sending large amounts of small data quickly (e.g. a USB mouse).

Step 3. Prepare your Linux system to talk to the device. First, let’s review ladyada’s steps, which is for Windows. She installs libusb-win32 and then runs a program called inf-wizard to make a driver shell. Then plugging the device into Windows will attach the LibUSB-win32 device driver. Next, she installed Python and PyUSB.

I wanted to stick with Linux. I didn’t need libusb-win32 or inf-wizard.exe, and I already had Python installed. So my next step was to download PyUSB, extract the zip into a directory, change into that directory, then run sudo python setup.py install in that directory to install PyUSB. Since you’re installing PyUSB system-wide, you do need to run that command with “sudo” to run it as root.

Step 4. Write a short program on your Linux machine to talk to the device. I made a file missile-launcher.py and executable access with “chmod ugo+rx missile-launcher.py” next. Here’s the short program I ended up with:

#!/usr/bin/python

import usb.core
import usb.util
import sys
 
# find our device
dev = usb.core.find(idVendor=0x0a81, idProduct=0x0701)
 
# was it found?
if dev is None:
    raise ValueError('Device not found')

# Linux kernel sets up a device driver for USB device, which you have
# to detach. Otherwise trying to interact with the device gives a
# 'Resource Busy' error.
try:
  dev.detach_kernel_driver(0)
except Exception, e:
  pass # already unregistered
 
# set the active configuration. With no arguments, the first
# configuration will be the active one
dev.set_configuration()
 
print "all done"

Note that my “idVendor=0x0a81, idProduct=0x0701″ parameters use the values I found from lsusb -vv. If you compare against ladyada’s short program you’ll notice one major difference. My code has these lines:

# Linux kernel sets up a device driver for USB device, which you have
# to detach. Otherwise trying to interact with the device gives a
# 'Resource Busy' error.
try:
  dev.detach_kernel_driver(0)
except Exception, e:
  pass # already unregistered

Ladyada’s PyUSB program for Windows didn’t have anything like that. But when I ran the program under Linux, I got the error message “usb.core.USBError: Resource busy”. It turns out that the Linux kernel tries to use a default kernel driver, and that prevents my program from talking to the device. Detaching the kernel driver lets me talk to the device just fine. I picked up this tip Ken Shirriff’s post about a USB panic button with Linux and Python. In theory you could also unbind the USB device from a command-line, but I prefer to do it right in my PyUSB program directly.

Note that you will need to run the python program as root, e.g. “sudo ./missile-launcher.py” or else you’ll get a warning message like “usb.core.USBError: Access denied (insufficient permissions)”.

At this point, you have a small working program that opens up a connection to the USB rocket launcher. If the USB rocket launcher isn’t plugged in, you’ll get a “Device not found” error, and if the USB device is plugged in, you’ll get an “all done” message and the program exits gracefully.

Step 5: Try to read from the USB device. In ladyada’s guide, she tried sending 0b11000000 = 0xC0 (“Read Vendor data from Device”) to a Kinect. I got no response from that, but I did get a response sending 0b10000000. That corresponds to sending:
– a ‘1’ to read from the device
– a message type of ’00’ = standard. Ladyada got a response sending to ’10’ = vendor
– ‘000’ (reserved bits, so always 0)
– ’00’ to say the recipient of the message is the device.
Then sending a request of 0 got back a result of two zero bytes:

bRequest  0
array('B', [0, 0])

Interestingly, running the same program again would get a “usb.core.USBError: Unknown error” response. At that point, I would unplug the USB device and then plug it back in to reset it. I didn’t get any other responses from trying to send message types of class or vendor (as opposed to standard), nor did I get any responses from try to send messages to the interface or endpoint (as opposed to the device). See ladyada’s guide for more details about fuzzing the device and what all the various bit fields mean.

Step 6: Set up the Linux computer to use the Total Phase Beagle. The CD worked nicely with HTML documentation on it. First, you copy some udev rules so that the device is writable by anyone when the Beagle is plugged in:


cd /media/Total Phase/drivers/linux/
sudo cp 99-totalphase.rules /etc/udev/rules.d/
sudo chmod 644 /etc/udev/rules.d/99-totalphase.rules

If you’ve already plugged in the Beagle, you’ll need to unplug it and plug it back in for these rules to fire. Next, you’ll need the Data Center software. You can get it off the CD, but I’d recommend downloading the latest software and user’s manual from the website instead. My CD had software version 4.20 for example and the website was up to 5.01. Extract the software zip file (either from online or the CD). Then follow the directions in the online manual (or user manual PDF). The directions according to the manual are

  1. Install the USB drivers and Data Center software. Copying the udev rules is enough for USB drivers on Linux. Unpacking the zip is all you need for the Data Center software, because the executable is self-contained.
  2. Plug the Beagle analyzer into the analysis machine. This was my Linux machine.
  3. Plug the Beagle analyzer into the bus to be analyzed. In this case, this was my XP computer. Don’t plug the USB missile launcher in yet though.
  4. Start the Data Center software. Run the program “Data Center” in the directory you extracted from the .zip file. Follow the rest of the instruction in the Quick Start section.

A big challenge: running a 50 mile race

You may have heard of my 30 day challenges, where I try something new for 30 days. Those challenges are great to try out a new habit and see how you like it.

But I’m also a big believer in picking out really big goals too. In 2010 I trained for a few months so I could climb Kilimanjaro, for example. For 2011, I went skydiving and ran my first marathon in San Francisco. 2012 ended up being a blur: lots of work, plus trips and time with family. I still managed to run a couple more marathons and finish a Tough Mudder race back in Kentucky.

Which brings me to my big goal for 2013. On April 6th, 2013, I’m going to try to run 50 miles for the American River 50. It’s an ultramarathon from Sacramento to Auburn with flat ground for the first half and single-track dirt trails on the second half. The cutoff limit for finishing is 13 hours. As a running friend put it, “You really just need to make the 32 mile cutoff in 7.5 hours or so; after that you could walk the rest of the way!”

In theory, if you run the American River 50 in 11 hours then you can qualify for the Western States 100-Mile Endurance Run. But I’ve gotten a chance to run the trail half of the course a couple times now, and I don’t think there’s any way I can finish that fast. So I’m just shooting to finish in 13 hours. By the way, if you’re interested in ultramarathons (any race longer than a marathon) or trail running, there’s a great documentary about the 2010 Western States race called Unbreakable.

So that’s what I’ll be doing this weekend. Wish me luck, and if anyone want to suggest running music, please leave a comment pointing to a good YouTube video for running. Thanks!

My Halloween costume for 2012: Matt Romney!

My fellow Americans, I’d like to introduce my latest Halloween costume: Matt Romney!


Mitt Romney? No, it's Matt Romney!

My five-point plan for the Mitt Romney Halloween costume went like this:

  1. Start with a suit and tie.
  2. Put a little silver in my sideburns. My wife used some silver and white eye shadow.
  3. Swoosh the hair up a little bit and lock it in with hairspray.
  4. Take off the glasses, and
  5. Add a flag. Boom!

This was a fun, easy, comfortable costume. I practiced a few of Mitt Romney’s catchphrases and I think people really enjoyed seeing “Matt Romney” around the Googleplex.

My wife and I are also trying something new for Halloween. I remember as a kid when I got a full-size candy bar for Halloween–it blew me away! I still remember those neighbors as really cool. Recently someone reminded me of that experience.

So this year, the first couple dozen kids who stop by our house are in for a nice treat:


A lot of full-size Halloween candy.

Happy Halloween, everyone! You might also enjoy seeing some of my other Halloween costumes.

css.php