2D Barcode Error Correction


We're still playing with 2D barcodes and testing out how well they work with various Android devices.  One question that came up from our last test was how well they dealt with errors in the barcode, that is dirt, rips or parts missing entirely in the way.

The answer is pretty darn well.  Here's a barcode that still runs despite me scribbling all over it:

But there are vulnerabilities.  Specifically on QR codes, they are very sensitive to having one of the position detection patterns destroyed.  This QR code, while in much better shape than the one above, refused to read, just because the top left block was filled in.

Note of course that all these results are in the context of using the Barcode Scanner application on an Android phone.  There are almost certainly weaknesses in the scanning algorithm, but that's the state of the art for Java based QR Code reading, so it is what is relevant for us.

Also, we tried the same tests with DM codes with similar results.  Newer DM codes support the very same Reed Solomon error correction algorithm, and just like QR codes allow for up to 30% of the data being corrupted before failing entirely.  Again though, if you start messing with the position markers for DM codes, which are the left and right edges, you run into trouble more quickly.

Android Ideos and QR-Codes, practical limitations

We're a huge fan of the Huawie Ideos phones.  They are ridiculously cheap, $100 unlocked, and can be bought over the counter at Safaricom in Kenya or about $120 from NewEgg in the states.  That is a crazy pricepoint, totally blowing away any other Android phone and really making J2ME handsets mostly irrelevant as contenders for the kind of ICT4D projects Nyaruka undertakes.

Recently we've been working with a client and have been considering using these as a way of managing and tracking inventory.  After all, the cheapest barcode scanners are around the same price, and you don't get a built in touch screen, GSM connectivity, GPS and the ability to build the entire application on the device.  That makes the Ideos mighty tempting indeed.

One thing we were curious about though is just how well they would perform with high resolution 2D barcodes.  In our case, we'd like to have the option to encode quite a bit of data in the barcodes, so we were curious how the inexpensive Ideos optics would fare.

Methodology

We created and printed 2D bar codes encoding 23, 50, 100, 200, 500 and 1000 characters, then tested them at different sizes.  The codes were all generated at Invx.com, which seemed to do a decent job, even for our monster 1000 character barcode.

We printed each using a laser printer and scaled them from roughly 4"s to 2"s and finally 1" squared.  This was under normal lighting conditions using the most excellent "Barcode Scanner" app in the Android App store which uses the open source ZXing library.  We also tried things out with a Nexus S, and a Sidekick 4G.

Camera Specs

The big knock to the Ideos is that it is a fixed focus camera, despite being 3.15 megapixels.  What that means in this application is that you always need to hold the Ideos at a fixed distance from the code in order to get a sharp picture, which means that you start running into the limitations of the sensor resolution for the higher data QR codes.

The Sidekick4G and Nexus on the other hand, have autofocus cameras, which help greatly.  The Sidekick also has a 3 megapixel camera, but it is able to focus so fares much better.  The Nexus S has a 5 megapixel camera with auto-focus, so should be the best yet.

Scoring

For each phone and barcode, we ran a series of tests and ranked the performance as Fail, Poor, Good or Excellent.  Fail means that we either couldn't get the phone to read the barcode at all, or it was very, very difficult.  Ok means that it took a good bit of searching to read the barcode, but it did so consistently.  Good meant the barcode was easily read when well aligned and Excellent meant the barcode was instantly read even when misaligned or at an oblique angle.  Excellent readings have that magical quality to them where you just wave the phone in the general direction of the code and it picks it up.

Results

So what did we find?

Not surprisingly, auto focus made a huge difference.  Since the Ideos has a set focus point, you essentially always have to hold it roughly the same distance from the code.  That is reasonably easy to do and you get a feel for it, but it means that if the QR code is small, then the sensor won't be able to make out the details.  Here's a quick example that makes it clear:

That's the Ideos quite easily reading the 100 character 2" barcode and struggling on the 1" version.  You can see that the 2" code takes up a greater size so reads easily, but the smaller 1" code doesn't.  We can't move closer to the 1" code to make it fill the screen as then it becomes out of focus.

One interesting learning there is that you can work around that resolution if you have the freedom to make larger QR codes.  The 'optimum' size for a code for an Ideos is probably around 3"'s square, that would fill the frame at the exact distance where it is focused.  We didn't try this out, but I bet you could get a 200 character code reading excellently.

The benefit of the autofocus is obvious when you compare the Ideos results to the Sidekick, which has a similar resolution, though much better optics and autofocus.  The Sidekick has no problem reading even 500 character barcodes at 1".

For all practical purposes the Nexus doesn't do any better, which probably indicates that we are reaching the limits of the optics rather than the limits of the sensor sizes.

Practical Limits

So what are the practical limits?  On an Ideos, I would stick to ~100 characters or less on a 2" bar code, and ~50 characters or less on a 1" barcode.  At those sizes things work brilliantly, instant recognition at virtually any angle.

On an autofocusing device, you have a lot more flexibility.  Even at 1" you can easily decode codes with up to 500 characters.  For QR codes that seems to be the practical limit, though if you are willing to use a DataMatrix code you might be able to squeeze a bit more in.

QR Codes vs DataMatrix Codes

The two biggest 2D barcode standards for this kind of application are QR Codes and DataMatrix codes.  DataMatrix is actually the older standard, but due to leaving out support for Kanji characters, QR Codes were created in Japan and have been taking over.

There are some advantages and disadvantages to each.  QR Codes are more tolerant to being read at oblique or rotated angles.  The guide blocks in the corners seem to help tremendously here and I definitely noticed faster and more consistent reading for QR codes.

However, those blocks come at the cost of data density.  Here are the two 1000 character codes used in these tests, the QR code at left and the DM code at right.  You can see that the DM code requires less resolution to read, so by and large the DM codes tended to fail last, at least when good alignment was used.

Error Correction

One interesting feature of QR codes is that they are a bit more tolerant to errors.  You can cover up the bottom right corner of a QR code and it will usually still read, the DM codes are more sensitive here.  This might be an overstated benefit though, as I didn't have as much luck covering up the top right, left, or bottom left corners of QR codes, where the guide blocks are, so the practical cases where the error correction would come in seem minimal.

Error correction is something you can tune in QR codes, some generators lets you define more redundancy in the generated code.  However, this will presumably come with lower data density, so is probably very specific to your application.

Troublesome QR Code

Strangely, the lowest resolution QR code generated, of 23 characters, actually was troublesome to read in many cases.  Looking at it closely it looks like it contains one less control block than the 50 character code.  You can see that below, the 23 character on the left vs the 50 character on the right.  

This might just be a limitation or bug in the scanning software itself, but does point out that real world testing is still really important.  The DM code didn't display any such issues.

Full Results

Finally, here's the full results if you want to see the nitty gritty details:

Some quick thoughts on Pivot25

The Nyaruka team has been at Pivot25 for the past few days, presenting
Bizito as one of the finalists. It has been a fun time, it is great
to see what the technology scene is like here in Kenya. There is no
doubt that that Nairobi is much farther along than Kigali, but I view
that as encouragement as to what is yet to come for us in Rwanda.

But one thing that is the same, is the constant ask for access to
capital by various companies. A few presentations over the past few
days have had asks for six figures in funding, which gives me serious
pause. It seems like there is a belief that funding is the goal as
opposed to a necessary evil. The truth is just the opposite, as
software engineers, we have the unique advantage that we can build
systems to earn us money without doing physical work. Add to that
that all we really need is an internet connection, some ramen noodles
and an ample supply of coffee and the funding asks really make me
scratch my head.

One interesting exercise is to look at YCombinator as a comparison.
YCombinator is arguably the leading seed funder in the Silicon Valley
today. Companies compete in a similar way as we have here at Pivot25
to be one of the companies to be taken under their wing. And you know
how much they give? $20,000. And this is only the most promising,
most experienced, most qualified companies in the world. Their
graduates include the likes of DropBox and Loopt among countless other
visionaries.

So my advice to some of the less experienced teams. Forget about the
funding and go build your idea, after work if you need to, using a
loan from your friends and family if necessary. If you don't believe
in your idea enough to suffer through eating ramen, or to sell your
family on it, then maybe you don't believe in your idea as much as you
say you do.

My point is the only expensive thing about starting a software startup
is paying engineers, and if you are one, then you should be able to do
it without raising money, and you'll be all the better for it.

Android's Achilles' Heel - The Sim Toolkit

Quite a few people, myself included, believe that Android is going to become absolutely huge in Africa.  Here in Rwanda, smartphones are becoming more and more prevalent for the upper tier consumers.  Though the Blackberry is the only smart phone sold by local carriers, it is not uncommon to see unlocked iPhones as well, no less a status symbol here as the rest of the world.

Of course the beauty of Android is that at any moment one of the carriers here could start selling them, unlike the iPhone, Android is open for anybody to sell on any network.  As a matter of fact, I have it on good authority that the biggest carrier here, MTN, will start carrying some Android handsets soon.  And as the price continues to drop, I'm sure they will become just as popular here as they have become in the West.

That is if it wasn't for one giant gotcha: Android's terrible support for the Sim Toolkit.

Now if you live in the States, you might not even know what the STK is, so a bit of explaining is in order.  Put simply, the STK allows carriers to load a simple set of menus and 'applications' on your SIM card.  Again, on your fancy iPhone, you may question the need or purpose for such a thing, but that's because you are still years behind and using a credit card.  Here, where credit cards are virtually unknown, the present and future of payments is Mobile Money, which is almost always delivered via.. you guessed it, the STK.

See, the STK works on virtually any device, from a $5 Alcatel to a $200 Nokia, these phones all implement the GSM standard and therefore allow anybody, both rich and poor to access services like Mobile Money.

Except if you have an Android handset.

Earlier versions of Android, up to 1.6, actually included a rather rough, but functional Sim Toolkit application, but at some point it was dropped, and even Google's own latest and greatest ROM's for its Nexus One and Nexus S handsets lack it.  As a matter of fact, I don't know of any devices running Android 2.3 that include it.

Thankfully, CyanogenMod has been forward porting the Sim Toolkit for a while now, and sure enough, Cyanogen 7.0 still has it.  But it is a buggy and unpleasant experience.  I tried to activate MTN Mobile Money today using my Nexus One, and half way through the process just gave up and used my $5 backup phone instead.  I can access most menus using Cyanogen, but only by force quitting the Sim Toolkit after every request.

I'm not the only one commenting on this, the web is full of people screaming that their fancy new $500 smartphone is too snobby, too highfaluting, to play with the rest of the world.

So here's a clue Google:

If you want Android to be relevant anywhere apart from the West, then start thinking about how we live day to day.  Build a browser that does wire compression before sending it down (oh hai Opera!), give us finer control over when background data is used, give us USSD API support, and for god sake's, implement a 20 year old standard so we can use the services that make our lives more convenient than yours.

On MobileActive's SMS Delivery Results in Egypt

A few days ago, MobileActive posted the results to some interesting work they did in Egypt, trying to quantify SMS latencies and whether they might indicate that filtering is taking place.  Essentially they wrote an Android application that allowed them to easily measure the SMS latencies between networks.  That application sent a variety of messages, some with 'safe' content and others with 'political' content.  The idea being to help quickly identity if networks are filtering or blocking messages based on their content.

While I applaud the effort, and I think it is an interesting project, I feel like there are some flaws in the methodology, significant enough flaws that MobileActive should have resisted even hinting at any conclusions before fixing them.

We do a lot of work with SMS here in Rwanda, we live and breath the stuff really, so we are pretty familiar with just how mysterious latencies can be.  We've done work in Ethiopia with Android phones and seen instant deliveries right after massive delays, all with just boring old numerical messages.  And we've done a lot of work here in Rwanda talking straight to the carrier's SMSC and seen similar things.  To put it simply, even under the best circumstances, making rhyme or reason to delivery failures, much less latency is a really hard task.

And that puts an enormous burden of proof to any experiment which claims to try to corrolate messages latencies to message content, and here I feel MobileActive should have known better and resisted any, even tentative and disclaimed, reporting of possible filtering.

It is hard to know exactly what the data showed, since the data isn't publicly available, but we do know that the study involved roughly 270 messages across a variety of networks.  One of the hypothesis they give is that Etisalat may be filtering messages based on the content of the message.  From the graphs provided it seems we can guess this is based on roughly 70 results, which seems to fit in with their totals.  Here's their graph of those results:

Now it is certainly tempting to look at this and start making hypothesis that political messages are being filtered, but we have to keep in mind our previous caveats about the reliability of SMS deliveries.  Specifically, especially when measuring something as unpredictable as SMS, we need to start with a valid hypothesis and then work out an experiment that makes sense.  Again, we don't know enough about MobileActive's methodology here to draw any conclusions, but here's some things I'd do:

1) Network latency is often cyclical, the network sometimes just acts up for a bit.  So when testing various messages it is important to both randomize the order that the messages are sent, and do multiple passes of the test at various times of the day.  If we skimp on either of these we may just be seing the artifacts of a network under load.

2) Are delays consistent across the same message?  From what I can tell this is the biggest flaw in the tests as a whole.  If every time I send a message saying "revolt now" it takes 20 seconds to deliver, then perhaps we have a case.  But if it is inconsistent, then we really need to start looking at what else can explain that latency.

3) If the hypothesis is that filtering is taking place, what do we think is the mechanism?  Clearly, any filtering that is automated would be completely lost in the noise of normal SMS delivery times.  Even the most sophisticated algorithm would take mere milliseconds to evaluate whether 160 characters should pass or not, you wouldn't be able to detect it via measuring the latency.  If the hypothesis is that some kind of manual filtering is taking place, such that actual humans are looking at the messages, then we should design our experiment to capture that.  For example, perhaps we can try to overload these mechanical turks by sending a large number of political messages in a short time period.  If the delays increase even further, then that's probably an indication that there is some human intervention taking place.  I find it very, very, hard to believe that any carrier has such a system in place that would still result in sub-minute deliveries, but if that is indeed our hypothesis, we could create an experiment to test it.

Perhaps my biggest complaint here is the lack of openness.  In our fast paced age of Twitter and Facebook and flashy headlines, we need to resist the temptation for sensationalism and be rigorous in our methodologies, especially on topics this important.  Not publishing the raw data that these results were based on just isn't acceptable, and if the excuse is one of not enough time, then the original article should have waited until that part was ready.  And just as you should always be skeptical of any benchmark which you can't run yourself, you should also be skeptical of any test using software you can't examine.  Again, lack of time is not an excuse, if you don't have time to make the process transparent, then you should just delay publishing your results.

MobileActive and others all do important work, but we must remember to maintain our standards, our scientific training, whenever sharing important information such as this.  It is all too easy to be drawn to the headline, to be taken over by the excitement of your results, and most importantly, all too easy to see patterns where none really exist.  We have all fallen victim to this, but it is our job as a community to call each other on it, to remind each other to be rigorous in our conclusions, to be peer reviewed and to never forget about that little thing called statistical significance.

I hope MobileActive stays true to their word and releases their Android client.  No need to clean it up guys, we won't judge you!  Let's all work together to get to the bottom of this most intriguing mystery.  We have lots of experience building Android apps and would be happy to lend a hand, as well as give our results on the Rwandan carriers.

Git Recipe: Making a Production Branch After the Fact

There are lots of different theories on the right way of branching on Github. One very neat one is flow, but perhaps you haven’t invested in using that for your particular project. In any case, there may just come a time when you decide after the fact that you should have created a remote branch.  Here’s how to do it easily in a few steps.

Step 1) Find the last commit you want included.

This one’s easy, just go to your project, check out your commits and decide where things started going awry. You want the hash for that commit (not tree not parent), as that’s where you are going to branch. It should look something like:

ff96b9182a2648bfb65f

Step 2) Create your new branch.

I assume you already have your repo checked out from Github, yes?  Ok, great, then just go create your new branch.

git branch production ff96b9182a2648bfb65f

Step 3) Add it to Github

Almost there.  Now we just need to push it to Github so others can use it.

% git push origin production

That’s it.  You can checkout, merge and do everything else as you would with any Git branch, and others can track your branch straight from Git.

Ahh, git so powerful, yet so obtuse.

Adding a view permission to Django models

A common request in Django is to use Django's permission model to control who can view particular object types.  This is pretty natural, especially as Django already provides default permissions on all models to 'create', 'modify' and 'delete'.

There are various answers to that question on the web, but none of them seemed particularly elegant.  After some more hunting around, I found that adding the view permission was most naturally done in a post_syncdb hook.  Whenever you issue a 'syncdb' command, all content types can be checked to see if they have a 'view' permission, and if not, create one.

Just grab this gist and throw it in your __init__.py in a management/ directory of one of your apps.  It needs to live under a management directory or it won't be discovered with the syncdb hook.

Once there, it should automatically create a view permission for all your objects upon your next syncdb.

How Github destroyed two years of work with a new favicon

Let me first get one thing straight.

I love Github.

I love how they allow me to collaborate with others, I love their simple functional interface, I love their 404 Page and I love, love, the cute Octocat.  They have done source code hosting right, so right that I find myself annoyed when a library I want to use isn't hosted there, because I know that if I want to tweak it a bit, submitting those changes back will be a bit more painful.

In short, I want to marry Github and raise our cute adorable Octocat children into our twilight years.

But this weekend, they drove me a bit bonkers.  I was coding about on some new SMS apps, hooking in my housemate's Kinyaranda dictionary for on the go lookups, and I kept finding myself hunting for my Github tab.

See, Github changed their favicon a few days ago, and my brain still hasn't adjusted.  So everytime I wanted to hop back to Github to read some code in a library I was using, or do a quick search, I got stuck.  I sat there staring at my tabs for a few seconds, looking in vain for the little 'git' beacon.

Don't believe me?  Take the test yourself, try to find the git tab here:

Nice work, you found that quick!  

Ok, now what what about this one?

Took you a tad longer didn't it?

I use Github daily, a ton, and I still haven't totally adjusted to the new Octocat icon.  It just isn't as distinctive as the old icon and my eye doesn't catch it.  I'm sure I will adapt, of course I will adapt, but in the meantime I'm going to waste a second or two every time I'm looking for that damn 'git' tab.

Which got me thinking, just how much time is going to be gobbled up by this innocuous change?

Getting traffic numbers for a website is an imprecise science.  Quancast claims that Github get's 1M unique visitors a month, while Compete says something like 500k a day.  For the sake of simplicity, let's just go with 1M, since I'm mostly interested in how long each user will take to adapt.

So let's say each of those visitors is like me, and gets just a tiny bit confused by the new icon.  Let's say that over the course of the few days it takes to adapt, they waste 15 seconds on Github tab hunts.  Using everybody's favorite method of multiplying small things by big things we get:

15 seconds * 1,000,000 = 15 million seconds

15 M seconds / 3600 seconds =~ 4166 hours

4166 hours / (40 hours * 50 weeks) =~ 2 years

Holy crap!  Github just ate two years of productivity with a favicon change!  Someone ring the alarms!

Ok, so ya, this is all pretty ridiculous.  All sorts of things steal our time every day, let's not even get into how many person years of productivity Facebook has eaten.  ("one billion years!" pinky on lip)  But what it does illustrate is both how integral a part of our work day Github has become for so many of us, and how once a site becomes that integral, then tiny things can make big differences.

That's a lot of responsibility, and something kind of unique about web apps in general.  We don't get to pick when to upgrade to the new favicon.  It gets pushed out, and we adapt, or if the change is bad enough, we leave.  But we don't get to say, no, this is good enough, I'm not upgrading to the Octocat favicon.

Imagine if tomorrow Google decided that Gmail should be served in Esperanto only, because they've decided that Esperanto is the one true language.  What could we do except complain?  We don't get to choose to keep the old native language Gmail, we are forced forward.  And yes, of course even if such a ridiculous scenario happened, the market would adjust and somebody would figure out a workaround, but think of the productivity lost in the process.

That is the double edged sword with our growing dependence on web apps, we get instant updates that we love, and we get instant updates that we hate, all without lifting a finger.  That is a compromise I'm comfortable with, the sites I really rely upon understand that power and exercise caution.  

I trust Github and Google to make good decisions, I trust them to change things out from under me because more often than not those changes are improvements.  But our vulnerability is complete, we show our soft underbelly to these sites every single day, giving them permission to do as they will, only asking that they be gentle.

So it's a good thing Octocats are so cute, otherwise I might never forgive them for the two years of work they just erased from history.

Skype's Crazy Regex Easter Egg

Today I was chatting with a colleague on Skype, and as is often the case, misspelled something in my rush to get something across.

A habit I picked up in the IRC days, days I realize have not ended for some, is to use the Perl syntax for doing a regex substitution to indicate a correction.  For example, if you wrote "hello wrld", I would indicate my correction using "s/wrld/world/".  Crazily enough, this now works in Skype.  It just edits your previous post inline!

Some experimentation shows that it isn't a full regular expression engine, it will only do straight word substitution.  It also assumes the 'g' or 'global' flag, so all words that match your string will be replaced, not just the first.

But it is super cool stuff, a brief demonstration:

Noticed how I mispelled word as wrd.  No worries, I can edit that post with the regex:

Hats off to Skype on this one, neat stuff.

Update: I forgot that there's also another IRC'ism that Skype supports.  /me.  You can type "/me is bored" and Skype will turn this into "Nic Pottier is bored" in a specially formatted block.  Anybody know any others?

RapidSMS XForms 0.3.2 Released

Although we've been improving our XForms app for RapidSMS regularly, we recently made some further enhancements at UNICEF's request that make it deserve a new release.  So without further ado, let me present XForms 0.3.2.

The changes made include:

  1. you can now configure which character needs to lead keywords.  By default this is an empty string, but you can set it to a '+' or '-' to ignore all messages which do not include it.
  2. you can now configure which character needs to lead commands.  By default this is the '+' character, but you may change it to '-' or nothing at all.
  3. you can now pick which character (in addition to spaces) can be used to split and group values.  By default fields are separated by spaces when no command arguments are used, but you can change this to be ',', ';', ':' or '*'.  Note that we decided not to support splitting on '.' as it introduced too much ambiguity when trying to parse decimal values.
  4. some significant work has been done to make parsing more tolerant of errors or mistypes.  Specifically, keyword matching now uses edit distance to try to account for typos.  We have also made the parsing of commands and separators a bit more tolerant, though it obviously does not work in all cases.
  5. you can easily add new custom field types, with their own parsing.  This can allow you to create a new field type such as 'age' and have it parse items such as '6mos' or '1y', putting the result in a numeric field representing the number of days.
  6. we've added templating support for the responses.  You can refer to variables which were parsed by their command and the templating syntax is the same as Django's.  IE, you can do something like: "Thanks {{ name }}, your report is confirmed."

We've also beefed up our unit tests even further, demonstrating all the above features, so you should look there for examples dealing with code.  The unit tests demonstrate both creation of custom fields and custom handlers.  You can also check the documentation for further help.

You can find the 0.3.2  release in PyPi or the latest code on GitHub.  We recommend using the PyPi version unless you need something specific on tip.  We had some bugs in our packaging earlier that made that more difficult but they should be resolved now.  Our thanks go to UNICEF for allowing us to continue working on this fun project.