Barcodes can be quite resilient to redaction. Not only is the pattern a strong visual signal, but also the encoded string that often has a rigidly defined structure. Here I present a method for recovering the data from a blurred, pixelated, or even partially covered barcode using prior knowledge of this higher-layer structure. This goes beyond so-called "deblurring" or blind deconvolution in that it can be applied to distortions other than blur as well.
It has also been a fun exercise in OpenCV matrix operations.
As example data, specimen pictures of Finnish driver's licenses shall be used. The card contains a Code 39 barcode encoding the cardholder's national identification number. This is a fixed-length string with well-defined structure and rudimentary error-detection, so it fits our purpose well. High-resolution samples with fictional data are available at government websites. Redacted and low-quality pictures of real cards are also widely available online, from social media sites to illustrations for news stories.
Nothing on the card indicates that the barcode contains sensitive information (knowledge of a name and this code often suffices as identification on the phone). Consequently, it's not hard to find pictures of cards with the barcode completely untouched either, even if all the other information has been carefully removed.
All cards and codes used in this post are simulated.
We'll start by aligning the barcode with the pixel grid and moving it into a known position. Its vertical position on the driver's license is pretty standard, so finding the card's corners and doing a reverse perspective projection should do the job.
Finding the blue EU flag seemed like a good starting point for automating the transform. However, JPEG is quite harsh on high-contrast edges and extrapolating the card boundary from the flag corners wasn't too reliable. A simpler solution is to use manual adjustments: an image viewer is opened and clicking on the image moves the corners of a quadrilateral on top of the image. cv::findHomography() and cv::warpPerspective() are then used to map this quadrilateral to a 857×400 rectangular image, giving us a rectified image of the card.
Reduction & filtering
The bottom 60 pixel rows, now containing our barcode of interest, are then reduced to a single 1D column sum signal using cv::reduce(). In this waveform, wide bars (black) will appear as valleys and wide spaces (white) as peaks.
In Code 39, all characters are of equal width and consist of 3 wide and 9 narrow elements (hence the name). Only the positions of the wide elements need to be determined to be able to decode the characters. A 15-pixel convolution kernel – cv::GaussianBlur() – is applied to smooth out any narrow lines.
A rectangular kernel matched to the bar width would possibly be a better choice, but the exact bar width is unknown at this point.
The format of the driver's license barcode will always be *DDMMYY-NNNC*, where
- The asterisks * are start and stop characters in Code 39
- DDMMYY is the cardholder's date of birth
- NNN is a number from 001 to 899, its least significant bit denoting gender
- C is a modulo-31 checksum character; Code 39 doesn't provide its own checksum
These constraints will be used to limit the search space at each string position. For example, at positions 0 and 12, the asterisk is the only allowed character, whereas in position 1 we can have either the number 0, 1, 2, or 3 as part of a day of month.
If text on the card is readable then the corresponding barcode characters can be marked as already solved by narrowing the search space to a single character.
It's a learning adventure so the decoder is implemented as a type of matched filter bank using matrix operations. Perhaps it could be GPU-friendly, too.
Each row of the filter matrix represents an expected 1D convolution output of one character, addressed by its ASCII code. A row is generated by creating an all-zeroes vector with just the peak elements set to plus/minus unity. These rows are then convolved with a horizontal Lanczos kernel.
The exact positions of the peaks depend on the barcode's wide-to-narrow ratio, as Code 39 allows anything from 2:1 to 3:1. Experiments have shown it to be 2.75:1 in most of these cards.
The 1D wave in the previous section is divided into character-length pieces which are then multiplied per-element by the above matrix using cv::Mat::mul(). The result is reduced to a row sum vector.
This vector now contains a "score", a kind of matched filter output, for each character in the search space. The best matching character is the one with the highest score; this maximum is found using cv::minMaxLoc(). Constraints are passed to the command as a binary mask matrix.
Barcode alignment and length
To determine the left and right boundaries of the barcode, an exhaustive search is run through the whole 1D signal (around 800 milliseconds). On each iteration the total score is calculated as a sum of character scores, and the alignment with the best total score is returned. This also readily gives us the best decoded string.
We can also enable checksum calculation and look for the best string with a valid checksum. This allows for errors elsewhere in the code.
The barcodes in these images were fully recovered using the method presented above:
It might be possible to further develop the method to recover even more blurred images. Possible improvements could include fine-tuning the Lanczos kernel used to generate the filter bank, or coming up with a better way to score the matches.
The best way to redact a barcode seems to be to draw a solid rectangle over it, preferably even slightly bigger than the barcode itself, and make sure it really gets rendered into the bitmap.
Printing an unlabeled barcode with sensitive data seems like a bad idea to begin with, but of course there could be a logical reason behind it.