Home > Projects > Robust Machine Readable Codes

Robust Machine Readable Codes

article by Ben Lincoln

In early 2013, I was working on a couple of projects where I wanted to paint a few things to look as though they were props from a sci-fi film or videogame. I was thinking in particular of Aliens, Event Horizon, and EA's Dead Space series. Having machine-readable codes on things helps make them look like industrial or military equipment from the future, so I went about looking for an existing 2D machine-readable code that I could make stencils out of. Unfortunately, I came up empty - every 2D machine-readable code I found (QR Codes, etc.) used a simple bitmap design where each pixel was directly next to its neighbours, with no space in-between. This made it impossible to generate valid codes that could be stencil-painted (or rendered as a silhouetted cutout, for example).

I decided to make my own, and spent a little bit too much time making it internally-consistent and believable (or, at least I think it's believable). The design goals were:

1. Look awesome and robotic/militaristic, like something that a machine intelligence would invent, or which would not look out of place stencilled on an M41A pulse rifle.
2. Provide built-in multi-level redundancy to help protect against data loss in the event of damage to the markings.
3. Able to be rendered as a stencil without any special support (threads, etc.).

I think the result succeeded on all three counts. I call this system Robust Machine-Readable Codes, or "Armour" Codes. I also developed a basic code-generator which reads binary data from an input file and writes SVG output - you can download it and its source code at the bottom of this page. I leave an RMR decoder as an exercise for the reader. I hope it finds some value for other people with a similar need, e.g. prop-makers for films.

The system has a single sentinel/metadata design, and currently two different ways of representing each byte of data. The type 1 byte is slightly less space-efficient, but provides another means of orienting the reader in the event that some or all of the sentinels are unreadable.

Here are some basic "area identification" markings, e.g. that an autonomous indoor helicopter might use to orient itself. These use only the horizontal parity feature, where the final byte is a RAID5-style parity byte allowing any single missing byte on that row to be reconstructed if the markings are damaged.

Here are a few more elaborate examples. These use both horizontal and vertical parity, so that even if an entire row or column is damaged, it can be reconstructed using the parity values. One element of the "RMR Code Specification" is that when both horizontal and vertical parity are in use, the lower-rightmost byte represents the parity of the combined horizontal and vertical parity bytes.

An interesting possibility is to "spectrally multiplex" the codes. In these simple examples, red is used to represent the first kibibyte of data, green the second, and blue the third - allowing 3 KiB to be represented in the same physical space as 1 KiB in monochrome. An advanced machine intelligence with hyperspectral vision could easily layer many different narrow-band slices across a wide range of spectral frequencies. These examples use a basic plane-level interleaving, but there's no reason not to use byte-level interleaving, or row/column-level interleaving.

An additional element of the "RMR Code Specification" is that inverted colours are also allowed. This is to that when painting a marking on a black surface, white paint can be used for the RMR code itself, instead of having to paint a giant white rectangle and then paint the marking in black over that.

Finally, a few example photos of the codes as used for their originally-inteded purpose.

A few additional notes on redundancy

You can skip this section unless you really want to understand the thinking behind the design of this system.

Machine-readable codes generally need some sort of "sentinel" markings to orient the device performing the reading. For example, 1D barcodes use special begin/end values so that the codes can be read even if they are rotated 180 degrees. QR codes use a set of nested boxes at three corners for the same reason.

For the RMR code design, I wanted to allow as much data as possible to be recovered in the event that even a large section of the code was damaged. So each corner has a sentinel, and the sentinel markings for each corner are distinct, allowing the reader to orient itself even if only one of the sentinels remains. In addition, the two metadata strips which extend from each sentinel are orientied in a way unique to that sentinel, so if the sentinel itself is damaged, it should still be possible for the reader to orient itself.

The metadata strips describe five elements of the code:

1. The horizontal dimension (width) in bytes.
2. The vertical dimension (height) in bytes.
3. The type of code (currently 1 or 2).
4. Whether horizontal and/or vertical parity bits are present.
5. Whether or not the message includes a 128-bit UUID at the beginning (and end, for codes which exceed a threshold of total length).

By encoding the width and height of the code at each corner, even if only a small fragment of the total code remains, it should be possible to make a much more accurate guess to its full contents because the amount of missing data is known.

Similarly, although the UUID feature is not used in the examples on this page, if each message is assigned a UUID and those UUIDs are recorded, then as long as the UUID itself is readable, the entire message can be recovered by looking it up in the records.

Although the examples on this page are limited to three levels of redundancy (the byte-level parity bit, and the horizontal/vertical parity bits), lengthier data streams could easily incorporate multi-dimensional redundancy. For example, every third "page" of data could be a parity page. Then every third "cube" of data could be a parity cube, and so on into higher dimensions. This could even be combined with the "spectral multiplexing", so that e.g. red and green encoded data, and blue encoded the parity of red and green.

Download
File	Size	Version	Release Date	Author
RMR Code Generator (Binaries)	25 KiB	1.0	2013-05-19	Ben Lincoln
This is the .NET executable version of the RMR Code Generator command-line utility. If you want to use the tool, this is probably the file you want to download.

Download
File	Size	Version	Release Date	Author
RMR Code Generator (Source Code)	85 KiB	1.0	2013-05-19	Ben Lincoln
This is the source code for the RMR Code Generator command-line utility. If you want to make modifications to the tool, this is probably the file you want to download. You will need Visual Studio 2010 to load the solution/projects.

Download
File	Size	Version	Release Date	Author
RMR Code Samples	215 KiB	1.0	2013-05-19	Ben Lincoln
A few examples of input and output files. The output files are in SVG format and can be opened with e.g. Inkscape.

Last updated: 19 May 2013

You have Javascript disabled in your browser. This website will look a bit nicer if you turn it back on.

Copyright 2009-2013 Ben Lincoln, except where explicitly noted.

Copyright Information - Privacy Policy - Download Policy - Advertising Policy